App Architecture and the Basics of Scale

Motivation
Recently a friend asked me about building applications. He is a graphics designer, and doesn't want to learn how to write code. He just wants to get a "big-picture" view of some of the common themes that arise when designing applications today. This blog post is aimed at people like him - interested but non-technical.

I'm going to start off by saying that what I'm about to describe does NOT describe all the different types of software being written today. In fact I know developers who never touch these issues. But my feeling is that this will be accurate for the vast majority of developers.

What Kind of Applications are We Talking About?
Here are some examples:

1. A blogging platform
2. An order and procurement system
3. A recruitment platform
4. A corporate HR system
5. A corporate finance system
6. A (software) bug tracking system
7. An email and chat platform

These are all very different, but let's see what's similar for most or all of them.

1. There are UI elements through which users can enter data. Very often these take the shape of forms.
2. There are UI elements which show data to users. This could be:
1. the data which they, or other users entered into the system,
2. data from external systems (machinery, sensors, the Internet),
3. the results of aggregation and computation, generally shown in a report. Think of "monthly sales totals", or your bank statement.
4. Often people want to see entire collections of similar data (your MakeMyTrip search results); these are displayed in a list.
3. There are processes which run in the background which actually do something with this data. These processes may only involve computers (generating your bank statement), or sometimes other people (processing your loan request). For something like email, one process would be the delivery of mail, which might involve looking up email addresses from nicknames; another process would be receiving mail, and running it through a spam filter.
4. All this data has to be stored somewhere, since it is generally not just sent from user to user. Even in the case of a chat system, users generally want a history of their chats stored for later. So there needs to be a database.

More and more applications today are being developed on the browser - whether Internet-facing or inside an organization, the browser is the portal of choice. We can book hotels, apply to university, check football scores... all through a single portal.

(I am completely ignoring stand-alone applications like Photoshop, Excel, Mathematica, StarCraft... I'm not understating their importance, but they're not relevant right now).

Another medium which is gaining in popularity is the mobile app. They don't run in browsers, but many of them provide functionality which would be natural on a browser. Many of them (LinkedIn, Facebook, Twitter) actually have browser counterparts.

How They Work

The following flow is widely applicable:

1. A request arrives at some endpoint. For web applications, an endpoint is just a URL, like http://www.my-awesome-app.com/login 
2. The web server decides whether or not the application can handle this request. For this to happen, the application needs to have told the web server what it can handle. Anything not on that list is a fail.
3. If the request is valid, and the endpoint exists, the web server forwards it to the appropriate handler in the application.
4. The handler takes the request and does what it needs to. This usually involves talking to the database. The list of tasks which needs to be performed fall into a workflow. Workflows will have portions which are straightfoward - "after checking that their ZIP code is valid, check their area code" - and portions which are conditional - "if their account balance is too low then deny their ATM request. Otherwise give them their money".
5. If the request has arrived "bearing data", it gets written to the database. Before that, there will usually be
1. validation e.g. the user entered their birth date. People from the future are not allowed.
2. clean-up or sanitization e.g. the user entered their name all in lowercase, so the application capitalizes the first letter
6. If the request is for data from the database, the application will ask the database for the data. When it comes back, maybe it gets re-formatted, or cleaned-up, before being sent back to the user
7. Many types of requests need to be authorized, so that not just anybody can get into the system and do just anything. Sometimes this is done using usernames and passwords. Sometimes it is outsourced to another service (sign in with Facebook!).

In summary (and since I'm too lazy to draw a picture):

    User --> Web Server --> Application --> Database --> Application --> Web Server --> User

Scaling Them Up

Now suppose you have more users - more customers, more employees, whatever. It might be obvious that the system will slow down, but how exactly does this happen?

Let's consider an analogy from the real world (which is actually more than an analogy, it really works just like this). Think of a fast-food restaurant, say one which makes sandwiches. They have 4 cashiers where customers place their orders (their requests) and the cashier forwards their order to the kitchen (the application, which starts the workflow). The workflow might look like this:

1. Get some bread
2. Put mustard on the bread
3. Put meat and cheese on the bread
4. Put the bread in the oven for 3 minutes
5. Put it on a plate with some chips and signal that its ready

Then the cashier would pick it up and give it to the user. We also assume that the restaurant hasn't figured out how to let a cashier serve more than one customer at a time - which means that until the sandwich has been made, that cashier's tied up.

Now imagine that the restaurant has a lot of customers one day. What happens?

Well, the cashiers work pretty fast, so they can handle the load. And the cooks are pretty fast too. But:

1. The oven can only handle one sandwich at a time, so there's more waiting there

Okay, so the customers wait. But if this happens repeatedly, the restaurant owners will want to do something about it. They have a few options, all of which will have an impact, but none of which will "solve" the problem permanently.

1. Buy a bigger oven
2. Buy more ovens
3. Hire more cooks

(Also, until the kitchen problem is solved, there's no point in hiring more cashiers).

Here's the analogy: The oven is the database server. A bigger oven is a more powerful server - more memory, faster CPU. More ovens means more database servers. The cooks are the application servers and the cashiers are the web servers.

The cashiers are all the same, and their job is easy. The cooks are all similar, but maybe some specialize in Reubens and some in pastrami on rye. 

The database is the real work-engine, that's where the time is spent. The performance of the application will eventually just be the performance of the database.

Terminology

Let me close with some terminology.

• Scaling up: This means making a component more powerful, generally by throwing CPU and RAM at it
• Scaling out: Add more components of the same type at that layer (like hiring more cashiers). Scaling out is cheaper (2 Marutis are cheaper than a Mercedes), but the application needs to have been designed to work that way.
• High Availability: A deployment that is fault-resistant due to intentional redundancy. Like having extra cooks waiting in case a working cook gets sick or injured.
• Disaster Recovery. How does the application react when something really bad happens e.g. the data center gets hit by a hurricane, or a virus attack. DR strategies generally involve setting up an entirely separate (and geographically separated) center, ready and waiting for such scenarios. Of course if they're ready and waiting, they cost money even while there's no disaster in-progress!
• Replication: Keep copies of the data, to protect against drive failure. Disk drives are mechanical objects, and they are the components which fail first and fail often. Data must always be stored in multiple locations

One part I left out is the entire portion of flow between the client and the web servers i.e. the network part. I left it out because one generally has no control over the network, especially if one is using the Internet. Your control starts at the web front-end, and that's where you start optimizing.

1+2+3+... = -1/12 ... huh?

Recently a video did its rounds on social media, showing how the sum of the natural numbers was $\frac{-1}{12}$. Naturally there was some skepticism from some of my friends, so I decided to write up a short note to clarify the situation.

You can find the video here, and for the more mathematically inclined, a blog post by Terry Tao.

What I'm going to show is that there is a slightly more rigorous way of interpreting the manipulations performed in the YouTube video, while pointing out the parts which are still not fully kosher.

(Could I start by saying that the sum doesn't work "because of physics"? Thank you.)

Infinite Sums

In case your response upon watching that video was "Wait a minute! That sum is clearly infinity" - you're not wrong. The typical way to define an infinite sum is as the limit of its partial sums i.e. 

$$S = a_1 + a_2 + a_3 + \cdots = \sum _{n=1} ^ \infty a_n $$

is defined to be 

$$ lim _{N \rightarrow \infty} \sum_{n=1} ^N a_n$$

and according to this definition, the sum $1+2+3+\cdots$ is certainly $\infty$.

And it gets worse - there are sums whose partial sums don't even have a limit. Here's an example which is actually from the video; the sum

$$S_1=1-1+1-1+1-1+ \cdots$$

has partial sums alternating between 1 and 0. In the video, he says that since the partial sums alternate in this way, the sum must be the "average" of these two values i.e. 1/2. 

I'm going to show you another way of seeing this. We won't actually use this sum, but it's a good way to start.

Start with the series expansion

$$\frac{1}{1-x} = \sum _{n >= 0} x^n$$

Let's first see why the fraction $\frac{1}{1-x}$ has that series expansion (you've probably seen this before):

$$(1-x) (1+x+x^2+x^3\cdots) = (1+x+x^2+x^3\cdots) - x (1+x+x^2+x^3\cdots)$$

which becomes

$$ = (1+x+x^2+x^3\cdots) - (x+x^2+x^3\cdots) $$
just by multiplying by $x$. Now all the powers of $x$ cancel, leaving only

$$ (1-x) (1+x+x^2+x^3\cdots) = 1$$

and therefore

$$(1+x+x^2+x^3\cdots) = \frac{1}{1-x}$$

Now this is fine as far as algebra goes i.e. symbolic manipulation. But what happens when we want to plug in values for $x$, say $x=500$?

Well, you can't. The problem is that the infinite sum will just stop making sense. The values of $x$ for which the sum does make sense is called its domain of convergence. For the sum $\sum x^n$, the domain of convergence is just the interval $-1<x<1$ (take my word for it - if we get into that level of detail I'll never get done here).

Okay, so 

1. When $x$ is between -1 and 1, the value of the fraction $\frac{1}{1-x}$ matches with the limit of partial sums i.e. the infinite sum of $\sum x^n$.
2. When $x=1$, both the fraction and the sum clearly blow up - the fraction gets a zero in the denominator and the sum just becomes $1+1+1+1+\cdots$. 
3. But what happens at $x=-1$?

Let's compute - I'm going to plug in some values of $x$, starting at $-0.1$ and going down to $-0.9$. You can imagine $x$ moving to the left on the number line as you go down the rows of this table: 

For each row, I've listed the first few terms of the series along with their signs so that it looks like a sum (as if I've plugged values of $x$ into $1+x+x^2+\cdots$). Then in the sixth column I have the infinite sum itself (well, not quite infinite, I did the computation with $1+x+\cdots + x^{1000}$). The final column has the value of the fraction for this value of $x$.

Here's what you're supposed to notice about this table:

1.  The sum $\sum x^n$ matches the fraction $\frac{1}{1-x}$. Of course if I had shown more digits after the decimal points they would eventually have differed, because the sum only used 1000 terms.
2. Both of these get closer to $1/2$ as $x$ gets closer to $-1$ (the bottom rows)
3. The second column is getting closer to -1, the third column to +1, the fourth to -1 and the fifth to +1.

I've attempted to draw a graph which to show (3). The different colors correspond to the rows of the table. Take a look at each block of colored bars.

1. The first one is $x^0$, which is just 1, no matter what $x$ is
2. The second one is $x^1$, so you can see the dark blue bar is for $x=-0.5$ and the red one is for $-1$
3. The third one is for $x^2$, etc...

Every time you move from blue to red in a colored block, it's like going down the rows of the table.

Now what I'm trying to show you here is how the individual terms of the series $1+x+x^2+\cdots$ get closer to $1-1+1-1+\cdots$ as $x \rightarrow -1$. So when you look at the series, this is a way you can picture it changing as $x \rightarrow -1$.

I would have been nice if I had also indicated the sums of these terms, but my graphing skills only go so far... anyway from the table you can see that they approach $1/2$. 

(And of course if you plug $x=-1$ into the fraction $\frac{1}{1-x}$, you get $1/2$, no magic there). 

So what have you just seen? What I just showed you was that $1+x+x^2+\cdots \rightarrow 1/2$ as $x \rightarrow -1$, i.e 

$$ 1-1+1-1+1- \cdots = 1/2$$
To summarize, I'm going to state all this in a very particular way:

1. There is a function $f(x) = \frac{1}{1-x}$,
2. with a series expansion $1+x+x^2+x^3\cdots$
3. and there is also a point $x=-1$ 
4. which allows us to view the sum $1-1+1-\cdots$ as $f(-1)$.

LET ME REITERATE: The sum $1-1+1-\cdots$ has no meaning according to the definitions of infinite sums. We are specifically interpreting it as the specialization of a series at a point on the boundary of the domain of convergence.

The sum $S_2$

The next sum in the video is 

$$ S_2 = 1 - 2 + 3 - 4 + \cdots $$

which they claim equals $1/4$.

If you believe what I said in the last section, this one is easy. Just differentiate

$$ \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots $$

with respect to $x$; you get

$$ \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots$$

and plug in $x=-1$ to get

$$ \frac{1}{4} = 1 - 2 + 3 - 4 + \cdots$$

A different kind of series

We just interpreted $1 - 2 + 3 - 4 + \cdots$ as the specialization of $$1 + 2x + 3x^2 + 4x^3 + \cdots$$ at $x=-1$. Now we're going to look at it differently, as the specialization at $x=-1$ of

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Here comes the non-kosher part: I'm going to ask you to believe that since
$$1 - 2 + 3 - 4 + \cdots = 1/4$$
using the series
$$1 + 2x + 3x^2 + 4x^3 + \cdots,$$
it continues to be $1/4$ even when we use this new series

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Accepting this for the moment, the final series we need is

$$ g(x) = \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots$$

Very similar, but now we have a + sign on every term.

Step 1. Make a modification of $g(x)$ which only uses even numbers.

This is easy - we just divide it by $2^x$; watch:

$$\frac{g(x)}{2^x} = \frac{1}{2^x} \left ( \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots \right )$$

$$ = \frac{1}{2^x} + \frac{1}{4^x} + \frac{1}{6^x} + \cdots$$

Cool.

Step 2. Now we subtract it from $g(x)$, first once:

$$ g(x) - \frac{g(x)}{2^x} =  \frac{1}{1^x} +  \frac{1}{3^x} +  \frac{1}{5^x} + \cdots $$

and then again:

$$ g(x) - \frac{g(x)}{2^x}- \frac{g(x)}{2^x} = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots $$

(Looking familiar!) Let's simplify the left-hand side by grouping the $g(x)$'s

$$g(x) (1 - \frac{1}{2^x}- \frac{1}{2^x} ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots$$

$$g(x) \left (1 - \frac{2}{2^x} \right ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x}  +  \frac{1}{5^x}+ \cdots $$

If we plug $x=-1$ into the left-hand side, we get $g(-1) (1-4)$, and if we plug it into the right-hand side we get $1 - 2 + 3 - 4 + \cdots =1/4$. 

Diving by $1-4$ gives us $$g(-1) = -1/12$$

And... what is $g(-1)$? Go ahead, look at the definition, you will get

$$1+2+3+4+\cdots = -1/12$$

The Non-Kosher Step

Why am I uncomfortable with saying that 

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$
approaches $1/4$ as $x \rightarrow -1$?

Remember that whole bit above where I drew the graphs of those series and said "well, the series approaches 1/4 as $x$ approaches -1"? I showed you a table and hopefully convinced you that what I was doing wasn't complete nonsense. (Okay, I drew the graphs for $S_1$, but it works for $S_2$ as well. Try it in Excel or something).

We can't do that here.

Not only can we not approach $x = -1$, we can't even cross $x=+1$! The series converges when $x>1$, and blows up at $x=1$, but even if you try to evaluate it at $x=0.99$ it won't work. It just blows up.

So how did I jump from $x=1$, across 0 all the way to $x=-1$?

Well, that's why this is the non-kosher step. And I don't have an explanation which doesn't involve more machinery.

But it's not "because of the physics".