Chapter Six: Building for Billions

Addendum: Big O notation

As I said in the chapter, the core concept of scalability is marginal cost, and we can achieve that in various ways (splitting the load, getting a wholesale discount by scaling up, etc).

But there’s another facet of scalability, which is how quickly something grows. Things can grow linearly, exponentially, “logarithmically,” etc.

Let’s do a thought experiment.

Say you were a hairdresser. You are asked to give a nice haircut to 100 people.

If on average it takes you 10 minutes to do one haircut, it’ll take you 1000 minutes to do 100. Simple.

Now, say you had to show 100 people how you give haircuts.

You could show them all one at a time, but you can also show them all at once! It only takes you the time to do one haircut, i.e. approx 10 minutes, to show all of them.

Giving a haircut to 100 people at the same time is impossible, but showing them is.

So you could say that doing haircuts scales linearly (N people, 1 haircut each, Nx10 minutes).

But showing haircuts takes constant time no matter how many people (N people, 1 showing, only 1×10 minutes).

So far in the book, we described the scalability of a process was using words.  It was more intuitive, i.e “this process is more scalable than the other.”

Now, we’re arriving at a way to describe scalability more objectively on paper. This brings us to the “Big O” notation. (That’s not a zero, but the English letter O.)

In the haircut example above, the first process, scaling linearly, is noted as “O(N)” — to do N of this, you have to it N times.

The constant-time process is noted as “O(1)” — to do N of this, you have to do it 1 times.

I’ll take one more quick example before I mak the “big reveal” of why we’re talking about this.

Let’s say you were to find page number 30 in a book that has 100 pages. How many “flips” should it take you to find it?

One way to do it is to flip one page at a time, counting, until you reach page 30. But is there a way to do it more quickly? Yes, there is a more optimal way to do it.

Well, you could open the book randomly in the middle, and see the page. If you’re beyond 30 (say 52 for example), then you know you have to only look in the first half of the book. Then you again try to open the middle page in the first half, and see that this time you reached page 28. You now flip just 2 pages to get to 30.

Overall, it took you only 3-4 flips!!!

This is an example of logarithmic scaling: it means the process becomes faster over time! This is faster than O(N) linear scaling, but still not as fast as O(1). Get it?

Logarithmic scaling is denoted as O(logN). Don’t get scared of the mathematical notation, you won’t be quizzed on it or something.

So — why are we talking about this? It’s because two software programs that accomplish the exact same thing can have very different speeds.

Good programmers always try to choose an optimal algorithm for a given program, so that it has a faster runtime.

This is important for you to understand as a hiring filter for engineers. At many tech companies, the first round of interviews for new engineers has a dreaded coding interview where they’re challenged to come up with the optimal algorithm to solve a problem.

But naturally, when you’re at a company like Google or Facebook, and writing programs that run on billions of webpages or millions of user profiles etc, you don’t want to be writing slow programs which take forever.

This was just a brief introduction to Big O notation, but you can search more tutorials on Youtube if you like – it teaches you a new way of thinking of how to solve real-world problems, and it gets better with practice!

Addendum #2: Cloud Migration

Here’s an article from Wired Magazine about Dropbox’s “epic exodus” from AWS to their own data centers.