posted on December 31, 2012
- tagged as: python , javascript , software , systems
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.
There are comments .