Durability, Scalability, Availability

I had a client who didn’t understand why caching was breaking things on their site. Of particular nuisance was the polls. To be fair, grasping why something as seemingly easy and as prevalent at large  works without caching and not with caching can be confusing. Here is the email I wrote to help educate them and now you!

I think it is necessary at this point to explain why things are cached and why caching has an impact on editorial and functionality. Specifically this is in reference to the polls. It’s going to take a bit to grasp what is happening so please read slow and bare with me.

Full web page caching or HTTP acceleration is done in part to effectively reduce the load experienced by an application and also to mask performance bottlenecks in the application to users.

Without caching every time a user makes a request that request eventually has some action that is performed by business logic in the application and ultimately the database. That action can actually be one or THOUSANDS of connections and queries. Those thousands of queries per user request are normally NOT unique as in one request will normally cause the same exact connections and queries to be performed as the next request for the same content. So as the number of users goes up the number of requests go up and ultimately the number of connections and queries will go up (however far more dramatically).

Here are some scenarios:

1 user makes 1 request for 1 page that takes 500 queries to render = 500 queries on the database.

1 user makes 3 requests for 3 different pages each taking 500 queries to render = 1500 queries on the database.

2 users each make 3 requests for 3 different pages each taking 500 queries to render = 3000 queries.

It’s linear when you look at it in this fashion but if you think about how the database actually performs transactions you will see that it becomes EXPONENTIAL in terms of the performance hit.

The database performs each transaction in a fashion that is sometimes blocking only allowing a single transaction to request a certain record at a single time (rare in read only scenarios) OR the io needed to service requests can actually cause the processor to wait while the hard disks are saturated (common on high volume, data intensive applications). This wait time experienced by the processor can quickly add up to minutes of wait time experienced by an individual request as the queries stack up waiting for the hard disks to return the data to the queries in the queue ahead of them…

There are many ways to solve this problem but the first is always to remove the waste.

Why perform all those non-unique calculations over and over again when you can just do them once, store the results and then return those stored results when the same non-unique request comes back again?

That is caching.

There are many levels of caching.

We can cache the query results for each query performed on the database. Every single one of the thousands of unique queries is currently kept cached automatically by the datbase for a certain period of time until it is thrown away to make room for “Hotter” queries.

We can also cache the results of the processing of the business logic (in the case of web applications this is usual some sort of html or xml output) those results can be used to produce an actual .html file on the hard disk.
This called “page level” caching.

Hotness explained (this is not unique to databases this is for most simple caching algorithms)

If a certain request is made for a certain piece of data lets assign it an importance value of 1.

If a subsequent request is made for that same data lets add 1 to that importance value so that it is now 2

If no other request is made for that data it’s value stays at 2 for some period of time.

Now let’s graph this importance or hotness value:

The x axis is some deliniation of the volume of data. Lets just presume that all your data is in a single directory and it all has random alphabetical filenames. Then X would possibly start at at AKURALEJD and end at ZNFNALHE. NOTE the filenames are RANDOMLY assigned to the data.

The Y axis is the hotness or importance value assigned to each piece of data so the Hotter the data the higher it is plotted on the Y axis.

What you will find is that SOME portion of the data is hotter than others. The plot of said hotness follows a bell curve.

So why not just cache ALL possible data ever produced by an application?

Memory is limited. We can’t possibly account for every single unique view of the data. SO we can only keep a portion of that data in the cache. There for we draw vertical lines on our graph starting at the middle of the bell curve and expanding them until the content contained in distance between them is equal to amount of available memory. After that the “tail ends” remain un-cached.

(see the attached image for a visual representation)

Now what happens when what’s hot changes? Well we have to make room in the cache so that this new data can be put in. How do we know what to throw out of the cache to make room? Well we introduce a lifetime or a TTL (Time To Live) on each element in the cache.

So in it’s most basic form a TTL will tell the cache to “Throw out anything older than X”

That means that as time goes on if something HAS not been requested in a longer period of time than the TTL is set to then it will eventually make it’s way out of the cache.

This aging process also allows for the content that is cached to be “refreshed” or updated periodically. SO if you add NEW data or change data in the application then those changes will eventually make their way into the cache and ultimately be seen by people making requests for cached data.

Ok so that all sounds good so why all the issues with caching?

Before we get into this we need to take an even farther step back. Let’s look at how our content is uniquely named.

When it comes to the web our content is uniquely named by it’s URL (uniform resource locator) See: http://en.wikipedia.org/wiki/Uniform_Resource_Locator

That URL is there for all the cache has to say distinguish one thing from another. With a unique URL the cache is able to determine what is what or more technically what the “STATE” is for that URL. The web used to be so simple.

What webservers do with URL’s:
I will briefly explain the two most common functions a web server performs. These are:

Responding to GET requests. (commonly associated with clicking a link)

Responding to POST requests. (commonly associated with pushing a submit button)

NOTE that BOTH are “REQUESTS” there for if you click a link OR click a submit button you are basically “REQUESTING” something from the webserver. In the case of a POST request most times you are also sending something extra to the webserver (for instance a contact form OR your answers to a poll!)

Once the webserver receives your request it will check to see if it is a GET or a POST and then it will check to see what file was requested and then if the file is of a certain type it will sometimes offload the request to some application server (for instance PHP running in as a cgi process). This application server (PHP for instance) will then process the request (taking into account the information in the GET or POST, making needed database queries etc.) and then returns the response back to the webserver which will in turn return the response to your browser.

That response may or may return unique information depending on what was passed in the GET or POST request to the webserver (and ultimately to the application server) NOTE: In the past ALL requests both GET and POST caused the browser to refresh the page. THAT fact alone is what defined WEB 1.0.

Enter AJAX.

Now web 2.0… We no longer have Unique URLS for every piece of content. More importantly we don’t have page refreshes upon every request. The same URL/page might look one way when you first visit it and then let’s just say (for the sake of a timely example) you submit a poll for instance. If the submission of that poll does not navigate you away from the page to a new URL well then you will never see that poll updated as your submission will only return the same exact cached page that you first saw. THEREFOR you will see the UNSUBMITTED poll once again.

So then how do we deal with caching AND AJAX?

We do so in one of two ways.

By maintaining STATE or at least some subset of the state on the client side (within the browser’s cookies).

OR

By caching only small parts of a page that don’t change and allowing the other parts of a page to remain UNCACHED. This is commonly called “partial caching”.

So why not use partial caching on my project?

Partial caching is entirely application dependent. It has to be architected into the application from the start. You unfortunately cannot “just add” partial caching because someone has to take the time to determine which portions of an application CAN be cached and which portions CANNOT. Most times off the shelf web applications cannot have partial caching added on top of them. Most traditional CMS applications and legacy web applications are not Web 2.0 “savy” enough.

Drupal falls into a gray area. Some modules are smart enough. Others are not. In general you cannot use partial caching with drupal without a lot of legwork.

SO we use the page level caching described above. Now what?

Well now we have to take into account the functionality implications of a page looking the same way no matter what every time you visit it. Sounds like it doesn’t fix anything, and it doesn’t, without some tricks.

To start we can tell the cache to NEVER respond to a POST request with cached content. That means that every time someone submits a poll then show them the results. The results are generated each time by the application server and then the unique response is sent back to the browser.

Why does the poll still NOT work on the site then.

The long and the short of it:

It does. BUT unfortunately the poll is one of those modules that was not written to be used with page level caching.

What’s happening is this:

The first time you visit the site (or at least before ever taking the poll) you get there by typing www.yourpage.com into your browser. That is a GET request and the homepage is retrieved from the cache. You see the poll and you ARE allowed to vote and you DO see your results. Your request is sent via a POST to the application servers and your response is returned by the application servers… NOT the cache because it was a POST request.

Then you navigate away from that page and everything is fine. Then let’s say you come back to the home page by clicking the logo in the top left. That is a GET request. The homepage is returned FROM THE CACHE this time and you do NOT see your results in the poll. You see a poll that has not been taken yet. Because that is how the homepage is cached.

SO then you try to take the poll again and this time it doesn’t let you submit. Why? Because the poll module in drupal was built to only allow ONE vote per person per poll. That means that you CANT submit the poll more than once.

So since you have already submitted and since the poll is cached as unsubmitted you are stuck with an unsubmittable poll.

DARN! How do we fix this?

The easy way: Make the polls allow more than one vote per person per poll. Really why is that so bad? Think about it.

The hard way: Rewrite the poll module correctly to refresh itself via another Ajax call for an un-cached version of the results. This means essentially writing a new poll module.

I hope that explains why the polls are not working. Maybe you picked up a thing or two a long the way.

I will go into the details later but I am thoroughly convinced that youtube is one of the largest most racist places on the internet. You would be hard-pressed to find a more high profile site with the N-word used so frequently in a derogatory sense. Anyway more recently in parallel I have been looking for some way of getting my hand’s on enough data to put Hadoop to the test. About a week ago the two idea’s converged in my head and I had a vision of creating an application that would consume all of the comments on youtube (or at least as many as it can swallow) and then using a little linguistic regexp magic figure out who is the MOST racist user on Youtube. I started out by writing the basic mapper in python in my previous post. It is only good for a single video however. I new I would need a spider and I was planning on writing my own (python has some awesome dom and xml parsing: beautiful soup mini-dom, expat) but decided that for future use it might be better to make use of something based on lucene. I have been using solr quite a bit lately but was hoping for something a little more lightweight. Luckily I was able to remember the name of the spider that came out shortly after lucene was made available. Nutch! It hasn’t had the glory that Solr has had in recent years (I don’t understand why these two projects exist and don’t converge?) but it turns out that it is now based on Hadoop by default! In fact little to my knowledge but it looks like Hadoop was actually spawned by Nutch?! Anyway I spent some time setting up nutch on a hadoop cluster today and I have to say it is still not the easiest thing in the world to work with. I am still new to Hadoop and was following this Nutch tutorial very closely. Unfortunatley it glazes over setting up the slave nodes so I plan to fill in the details here and offer them to the community. One thing that it fails to mention that I should have know from my other Hadoop tutorials (never underestimate the minutia!) hdfs configurations need to use FULLY qualified hostnames! you can’t just user your machine name even though you may be able to ping each machine on a local subnet with just the hostname and even though you can telnet from the slave machine to say an Httpd instance running on the namenode you WILL get silent failure when trying to telnet to the namenode daemon’s port. Check your firewalls of course but even if they are turned off on both your master and slave it is quite pssible you will just see:

$telnet master 9000

telnet: connect to address 192.168.0.1: Connection refused

however if you try the same thing from the master machine itself it works!? (assuming your name node is currently running and supposedly listening on port 9000)

This of course through me for a loop and I assumed it was everything from firewalls to bad interconnects between my machines. Strange that I never thought about the hostnames. I guess it was because all other services between them have been working fine. If anyone has any idea why hdfs has a problem with this I would love to know.

Here is my python script for grabbing the latest 1000 comments (the api only allows access to the latest 1000 unfortunately) and then checks them against a regexp for matching agains known racist words. Right now it is just looking for the N word. This script will be one of the inner MAP tasks in a series of Map-Reduce steps.

#!/usr/bin/env python

import sys

import gdata.youtube

import gdata.youtube.service

import re

racist_pattern = re.compile(’.*igger.*’, re.IGNORECASE)

#import pprint

#pp = pprint.PrettyPrinter(indent=4)

yt_service = gdata.youtube.service.YouTubeService()

#yt_service.developer_key = “”     #turns out the developer key isn’t necessary

urlpattern = ‘http://gdata.youtube.com/feeds/api/videos/%s/comments?start-index=%d&max-results=50′

for line in sys.stdin:

video_id = line.strip()

index = 1

url = urlpattern % (video_id, index)

#print url

comments = []

while url:

if index < 20:

comment_feed = yt_service.GetYouTubeVideoCommentFeed(uri=url)

#comments.extend([ comment.content.text for comment in comment_feed.entry ])

for comment in comment_feed.entry:

if racist_pattern.match(comment.content.text):

print ‘%s\t%s\n’ % (comment.author[0].name.text, comment.content.text)

#print [ 'Author: %s\t Comment: %s\n' % (comment.author[0].name.text, comment.content.text) for comment in comment_feed.entry ]

url = comment_feed.GetNextLink().href

index += 1

else:

#currently the google youtube gdata api will not support over 1000 comments

url = ‘http://gdata.youtube.com/feeds/api/videos/%s/comments?start-index=951&max-results=49′ % video_id

comment_feed = yt_service.GetYouTubeVideoCommentFeed(uri=url)

for comment in comment_feed.entry:

if racist_pattern.match(comment.content.text):

print ‘%s\t%s\n’ % (comment.author[0].name.text, comment.content.text)

#comments.extend([ comment.content.text for comment in comment_feed.entry ])

#print [ 'Author: %s\t Comment: %s\n' % (comment.author[0].name.text, comment.content.text) for comment in comment_feed.entry ]

break

I have been using Varnish for quite some time and have always wished that there was some way for Varnish to know to serve “Stale” pages when the upstream application servers are swamped. There is actually a feature request for this on the Varnish Trac system here. NOTE: this feature should not really be necessary unless you have underestimated the ability of your application servers to handle your traffic. However even after proper capacity planning sometimes you get well… DUGG. We all know the “digg effect” (formerly referred to as the “slashdot effect”) and it’s repercussions (500, Guru meditation, Houston we have a problem!) There are many ways to skin a cat, but none would be as simple as this (considering we have an existing varnish setup). I should note that simply getting “Dugg” or “Slashdotted” normally wouldn’t take down a site with a proper reverse proxy setup based on Varnish. If your TTL is appropriate and you are using an appropriate GRACE value (for you Squid readers: “stale-while-revalidate“) then you will probably not saturate your app servers. Unfortunately if your content is good and your UI is right then maybe, just maybe a certain percentage of your new readers will stick around. And here is where it gets scary for the app servers. Maybe just, maybe your new readers will start to navigate in ways that your cache is not used to. Maybe they will start to hit those really OLD articles that haven’t been requested in months! If you think about your sites content vs it’s popularity you it will look something like this:

No matter what you do there will always be something that falls into those “long tails” if your traffic patterns shift suddenly you can very well start to make a lot more request to your upstream servers than you (or more importantly your reverse proxy) expected.

Back to the task at hand. What can I do while I wait for the Varnish team to put this feature through? EASY… use Squid! There are so many debates over which reverse proxy is currently the fastest, which one is easier to setup or integrate with legacy apps etc. I’m certainly NOT trying to get into that! In fact I will skirt the issue entirely saying this: when the features are right and you can afford to use it then why not? NOW don’t get me wrong. Afford can mean a lot of things. Take it as you will. I personally HATE using software, ANY software when I don’t have to. In fact I try to design my stacks as small as possible. As a general rule LESS SOFTWARE IS BETTER! It means less maintenance, less quality assurance… less hastle! However there are situations like the one I described above when you are put between a rock and a hard place. I can either:

A) Swap Varnish out completely and start using squid.

B) Augment my http acceleration layer with squid.

C) Buy more application servers and avoid the issue.

I wish, I wish, I wish C was always an option. Unfortunately not all client’s can afford to simply throw more money at the problem. If I had my choice I would scale horizontally off to the…horizon. SO I now get to choose between A and B. A is what my Sysadmin gut feeling (about never using more software than necessary) is telling me to do. BUT A also has the Test Engineer in me screaming “You will have to test everything all over again!”

Sooo here is another instance where the REAL WORLD comes crashing down on good systems engineering. C is the cheapest most cost effective solution. It could be said that maintaing another piece of software over time is going to be more costly than the upfront cost of swapping out Varnish entirely. But consider this…the Varnish feature that I was mentioning earlier… has already been assigned. It is only a matter of time before someone decides to pick it up and implement it. Hell I might even go ahead and do it if I can find the time. (BTW if your reading this month’s past the publish date of this post then you should definitely check that Trac ticket and see what has become of it.)

C it is. Now I am going to have to dust off my Squid skills and install that beast again. (Of course I couldn’t get through an article about varnish and squid with out some opinion…. Setting up Squid is not the easiest thing in the world!)

After nearly a decade of the “cobler’s children have no shoes” I have decided to pick this blog back up again and write about my experiences as a software architect. I am planning a few articles on my work specializing in highly durable, highly available, horizontally scalable open source architectures pertaining not only to the web but to any massively concurrent application. Any questions, comments or topic suggestions are gladly accepted.