thatmattbone.com

Building web applications is tricky business, and one unique challenge is deciding where to put the computation for a particular task. When building a rich GUI, we know to keep our heavy computations out of the event loop and then organize our code as we wish. But in web apps, the absurd number of choices over where to place a computation, when (and if) to perform it, and the implementation technology for actually getting it done can be overwhelming.

Let’s consider a fairly simple task, displaying the first one hundred prime numbers on a web page, and explore a few of ways we can accomplish this. We’ll look at three main layers: the client side, the server side, and the data layer. We’ll also examine various implementation strategies and technologies for the layers. For all the actual computations, we’ll use various implementations of the sieve of Eratosthenes. The details of this aren’t terribly important, though it’s pretty simple to understand if you’ve never encountered it before.

You can follow along with each example below at whereiscomputation.thatmattbone.com, and the source for each example is available on github. While the examples are served up with Pyramid web framework and Python 3.3, this, too, isn’t terribly important and we’ll explore a few different languages and technologies.

Client Side

Let’s start by avoiding the problem. If our task is really just as simple as displaying the first one hundred prime numbers, then why even bother computing them? We can just search for the answer, plop into a static file and display it on a page. No computation necessary:

<p id="primes">
   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
   61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
   131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191,
   193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
   263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
   337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401,
   409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
   479, 487, 491, 499, 503, 509, 521, 523, 541
</p>

While this isn’t the most enlightening of examples, it is helpful since it serves as an acceptance test for all the other examples to follow. If we can compute the first one hundred primes and and display them (comma-separated) as text in a DOM node with an id of primes, then we’ll know we have the answer we’re looking for. In fact, it’s even pretty easy to write an automated test to verify that all our examples are returning what we expect.

Now on to something a bit more interesting. Using a sieve implementation in javascript, it’s easy to compute the primes on the client-side and display them, too:

document.getElementById("primes").innerHTML = sieve(541).join(", ");

While there are any number of plugins available for browsers that could perform this computation, for better or (probably) for worse, Javascript has become the ubiquitous new assembly language of our time. Performing this computation in Javascript places the burden of computation on each client while removing this burden from the server. In effect, we have a moronically simple distributed system where we ship each “node” (i.e. web browser) the code we’d like them to run and hope they all come up with the same answer. Short of piping the answer into over-caffeinated brains clamoring for prime numbers, the results are simply discarded.

For such a trivial problem it makes no difference, but delaying computation and shipping code to clients and allowing them to expend their cycles instead of the servers’ cycles can sometimes be a huge win. While browser implementations vary and we can never be sure each and every client will do exactly what we expect with our source code, in actual web applications some of these “distributed computations” do send their results back to the server in the form of POST requests, etc, and we can mitigate risk by doing careful validation on the server-side.

Server-side

Speaking of the server-side, this is another place to perform our computation. Consider our prime sieve implemented in python 3:

def sieve(max_n):
  number_map = {n: 0 for n in range(2, max_n + 1)}

  for n in number_map.keys():
      current_n = n + n
      while current_n <= max_n:
          number_map[current_n] += 1
          current_n += n

  return [n for n, count in number_map.items() if count == 0]

Using almost any webframework we’d like, we can run this code during each request/response cycle, pipe the results to a template, and end up with something shooting out over the wire that’s identical to our pre-computed version. For this example actually performing the computation might seem like a waste, but by really doing work we could easily send out a variable number of primes (dependent on, let’s say, a GET parameter).

Like the client-side, performing computation on the server-side is a trade-off. We are forced to expend more cycles of our own but with increased confidence that the correct results will be returned. By reducing the computational burden on the client, too, we may open ourselves up to a wider range of slow or low-powered devices.

Another approach is to perform computation on both the client and the server-side. Basically this amounts computing some of the result on the server and then computing the rest of the result (or recomputing a larger result) on the client-side. For a touch of the practical, something like this is generally done when bootstrapping Backbone.js models. The data structures necessary to initialize the app are computed (or serialized or retreived) on the server-side while all further updates are requested by the client-side. For Backbone.js this hybrid approach is useful because it reduces the load time of a webapp by cutting back the number of roundtrips to the server needed to initialize the app. In addition to reducing load times (or the perception of load times), this hybrid approach is also useful for deferring computation or loading of resources that aren’t necessary in the common case.

Data Layer

Most web applications have some sort of data layer where data is stored and retrieved. Much to the chagrin of developers, sysadmins, and basically all non-database nerds, computation can often be performed inside of the data layer. We don’t need to debate the merits of this here, but we should notice that this is just another example of moving computation around with its own tradeoffs. Generally when computation is done in the data layer, it’s performed closer to the data which can often be tremendously beneficial for performance.

Unfortunately the contrived example of computing primes isn’t really operating on much data. We might be able to imagine a database table of integers that we use inside a prime sieve as an example, but we can also simply perform the computation inside the data layer to make a point. Here’s an example of a postgres function for computing primes, and it’s exactly the same as the previous python example except for the boilerplate used to create it:

CREATE OR REPLACE FUNCTION prime_sieve(max_n integer)
RETURNS integer[] AS
$$
number_map = {n: 0 for n in range(2, max_n + 1)}

for n in number_map.keys():
    current_n = n + n
    while current_n <= max_n:
        number_map[current_n] += 1
        current_n += n

return [n for n, count in number_map.items() if count == 0]
$$
LANGUAGE plpython3u VOLATILE COST 100;

Which is called in sqlalchemy with:

primes = session.execute(select([func.prime_sieve(LAST_PRIME)])).fetchall()[0][0]

Again, it’s pretty clear with this example that we’ve simply moved the computation (and in this case the code itself almost verbatim) from one layer to another, but not all web apps use a relational database. Nosql solutions seem to grow more popular by the second, and some nosql solutions have support for moving the computation into the data layer, too. Starting with redis 2.6.0, this can be accomplished with lua. Here’s our lua script to compute some primes:

local max_n = tonumber(ARGV[1])
local number_map = {}
for n = 2, max_n do
   number_map[n] = 0
end

for n, value in pairs(number_map) do
   local current_n = n + n
   while current_n <= max_n do
      number_map[current_n] = number_map[current_n] + 1
      current_n = current_n + n
   end
end

local primes = {}
for n, value in pairs(number_map) do
   if value == 0 then
      table.insert(primes, n)
   end
end
return primes

And it is called with a redis client in a similar fashion:

r = redis_connection()
sieve = r.register_script(sieve_lua)  # a string containg the lua code above
primes = sieve(args=[LAST_PRIME])

Lua is a handy little extension language available in many applications, but why stop there? We can take this little joy ride to absurd new heights by patching redis to implement the functionality we’d like. Then we just call the new primes command we’ve created:

$ ./redis-cli 
redis 127.0.0.1:6379> PRIMES 10
1) "2"
2) "3"
3) "5"
4) "7"

Which with the wonderfully extensible redis-py library is easily called like any other command (under the hood):

r = redis_connection()
primes = r.execute_command("primes", LAST_PRIME)

While opening up the (suprisingly readable and enjoyable) redis source code and patching it for our own devious purposes is not the most maintable approach, it sure is fun.

Who Cares?

It’s easy to not care about these kinds of fundamentals when we’re trying to get CashScamSpamBot420Beta up and ready to attract fists of cash from angel investors, but ultimately these things do matter in systems that are destined to live for extended periods of time. Being mindful of the dangers of premature optimization, it’s still important to think about how our apps can scale up (in terms of users) and scale down (in terms of target devices). Moving computation around and performing it only when necessary can be an important thing to consider. Some layers of our architecture like the client and server-side might be easier to expand horizontally, but also we might not need this if we move a critical computation closer to the data. Like all things, it’s important to consider the trade-offs.

Finally, one import approach that we’ve not explictly explored here is getting computation out of the request/response cycle. This is another case of avoiding the problem. Deferring computation to a message queue, pre-computing lookup tables, and caching are all examples of avoiding computation in the critical path of getting data out to users. These techniques are incredibly important approaches in real web applications, and we should definitely not forget them.

One More Thing

I’ve been thinking about this post for a couple of years now and trying to come up with various ways to perform the example task. Hacking redis was by far the most fun, but there are obviously oodles of more ways to do this. If you’re bored, feel free to fork the project on github, and contribute your own devious methods whether they’re calling out to services, OCRing prime number tables from ancient texts, or farming out the computation to your pet crow. Just promise to have as much fun as I did.