Tuesday, November 27, 2012

A Time for Everything from Railways to Databases

I read with interest a recent Wired post about Google Spanner- possibly one of the largest databases in existence.  What piqued my interest was a historical parallel I’d picked up watching an episode of ‘History Detectives’ a while back.  In the episode, they researched a strange clock that, it turned out, was used to synchronize time across railway stations in the Midwest.

A little history of time (no, not _that one_). Prior to the 18th century, towns kept accurate time by using sundials.  Communication and travel were slow, and it generally didn’t matter if Ye Ole Pocket Watch was a few minutes off.  When it did matter, travelers could set their clocks by the town sundial and generally be within a few minutes of accuracy.  The late 1700s and early 1800s saw rail travel invented and (pun intended) pick up steam.  It doesn’t take a math wiz to know that if a train leaves Oxford Station for London at 11am, and one leaves London Station for Oxford at 11am on the same track, both going 50 MPH, it ain’t good. The need to coordinate times between train stations to avoid wrecks and unhappy customers, among other things, led to time standardization and the telegraph.  Greenwich would send out a message right on the dot, and the local operators would set their clocks, ensuring that Oxford sent their train out right at 11:05 so that it could just miss the one coming from London at 11:00.  The History Detectives ‘Chicago Clock’ would take that time and send it down the track as far as New Orleans at high noon, so that all the stations on the line had accurate times.

The two hundred years since have seen travel and communication speeds increase.  Trains got faster and started flying.  Cars and highways came, and telegraph systems evolved in large part to help schedule them, build them,  or to avoid traveling at all.  The principles are largely the same as the railroad networks:  time is key in keeping systems in sync, be it landing your flight to Hong Kong, or making sure your most recent Facebook post shows up in the right order.  (Actually, the latter can afford to be off by a bit more than the former- a fact many large systems exploit). 

In Google’s case, it was important to sync times between data centers across the globe that host their cash cow ad network.  Without accurate time across their datacenters, transactions could potentially be stored out of order.  Just like the Oxford-bound train, this is bad news for a database, where to have any hope of accurately replicating geographically, you need to know the order in which transactions are created.  When billions of transactions occur per second, and come from all over the planet, you need a really accurate clock in every building to precisely tag each transaction with a time that every other building will know is accurate when the transaction arrives.  Even a J.B. Mayo clock won’t cut it.  So, Google did the only reasonable thing and built a redundant clock based on GPS and atomic clocks, to be installed in each data center.  This way, when an ad purchase in Mumbai is copied to the Houston data center, they know it was purchased a millisecond before one in Topeka.

And there you have it:  the most massive database on the planet owes a nod to the steam engine and a 19th century clock.