I spent my first two years at Google working on Google Checkout, and I walked away with two great lessons. One was the lesson I learned from Pat Helland on building scalable systems. The other was admitting a fundamental trade off in system design. Like many things, it seems obvious in retrospect, but you would be surprised at the number of people who keep trying for everything [cf, OceanStore].

What do I mean by these? Consistency: Someone in Tokyo and someone in Chicago make a query on a piece of data and both observe the same state. Survivability: The system continues to function even in the face of a catastrophic outage such as the loss of power in New York state in 2003. Speed: How long does it take to mutate a single piece of data.

Scenario 1: Consistency and Survivability

If you want consistency and survivability, then you are forced to make each write in your system to backends on different failure domains. Failure domains may be quite large, as shown by the New York State 2003 power outage of 2003. This implies geographically distributed backends, and you can't beat the speed of light. A ping from Mountain View to Atlanta takes 60 ms on Google's network; and the speed of light puts the lower bound at 22 ms.

At Google, systems which choose consistency and survivability include Google Docs and our global Chubby cell. This trade off has the advantage of requiring no operator interaction when one of our clusters goes offline. However, it comes at a cost: writes which could have taken 2 ms take 200 ms. An application which makes 100 writes for each user action might work well enough in the former case but won't in the latter. Therefore, Google Docs and users of Global Chubby must be much more frugal with their writes.

If two systems are independently modifying a piece of data, it may be difficult (or impossible) to resolve the combined effects of those modifications. What does it mean for an order to be canceled and shipped (so-called "forked state")¹ ? To maintain consistency during a network partition, at most one side will win ownership of each piece of data. The other side will at best have a read-only version that may be stale.

Scenario 2: Consistency and Speed

If you're willing to forgo survivability, you can get consistency and speed in a variety of ways. The simplest way is to have one computer and a single copy of the data (a global "master"). To reduce your mean time between failure, you can put a quorum system like RAID or GFS in place so that when individual components fail, your system keeps humming along. However, if your entire site goes offline due to a fiber cut or other catastrophic failure, you have an outage.

The common approximation to survivability chosen by people who choose consistency and speed is to have a replica which lags a certain distance behind the master and is located elsewhere. The replica has a consistent view of the world: it's just a bit out of date. Such replicas are often used to serve read-only versions of the data, and there are approaches to force-promote a replica to be master if the master is lost, but care must be taken regarding the possibly-stale state of existing objects.

Scenario 3: Speed and Survivability

How does Google provision web search for the world? We don't synchronize the index.

Google has S search clusters each of which can serve Q search queries per second. Each search cluster receives a continuous stream of background updates that bring it to a close approximation of the "current" state of the Internet. However, there's no need for each cluster to be strictly in sync with the others. Maybe you have the blog post that was made ten minutes ago in your search results and I don't. In return for such small inconsistencies, Google provides web search which is always on and always fast.

Even though I've framed the survivability versus speed trade off here as one involving geographically distributed backends, the trade off arises at lower levels as well. GFS trades some survivability for speed: write completion does not wait for disk commit, only memory commit to three chunk servers. If all three chunk servers lose power before their disk caches are flushed, the writes are lost. We've found this trade off acceptable given the speed up: disk seeks take about 10 ms, whereas memory references take only 10 ns.

¹ Maybe Amazon knows what it means to have an order be independently shipped and canceled. Amazon's Dynamo Paper indicates that many of their objects are written to have mergable histories.

Horror

• Cube Zero (2004)
• 28 Weeks Later (2007)
• Oldboy (2003)
• Collapse: How Societies Choose to Fail or Succeed. Jared Diamond (2005)
• Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox (2007)

Curiosities

• The Curious Incident of the Dog in the Night Time. Mark Haddon (2004)
• Kolya (1996)
• The Age of Turbulence. Alan Greenspan
• Life beyond Distributed Transactions: An Apostate's Opinion. Pat Helland

Fantasy

• Psychonauts. Double Fine Productions (2005)
• Casablanca (1942)
• Serenity (2005)
• Eat Drink Man Woman (1994)
• Love Potion #9 (1991)

• The Iraq war was a mistake, a war sold on a folio of lies.
• The government has taken too broad a license to invade and monitor its citizens.
• Tariffs are just more government taxes - get rid of them.

• We tax and spend too much.
• We must stop the government from taking land through eminent domain.
• America should withrdraw from the WTO and other meddling international organizations.

• Fetuses should be protected by law.

{ int c = 5;
  { int q = c + 1; // yes, that's the old c you're using
    int c = c + 1; // no, that's not the old c you're using 
  }
}