Hacker News Reader

Comment by flyinglizard | Hacker News Reader

What kind of accuracy exists between servers inside the same data center? I assume there are some internal delays (OS stacks, switches, etc) when synchronizing time inside a server group.

I mean, even if you had a picosecond accurate clock available for use inside a server farm, you would still need a way to query it with a known (not necessarily zero; just known) latency to synchronize several machines. Servers are not known latency machines (unless specialized hardware is involved).

How is that accomplished?

And what happens when two transactions happen below the system accuracy limit? (like two transactions pertaining to the same data, 20ns apart, in different servers; impossible to order).

Surely they have solved this, I just wonder how.

View on HN

Looking at the paper it looks like instead of dealing with exact moments in time (eg timestamps) they have ranges (they call them intervals).

From the Spanner paper: "TrueTime explicitly represents time as a TTinterval, which is an interval with bounded time uncertainty (unlike standard time interfaces that give clients no notion of uncertainty)"

By representing time as intervals you can tell if one interval is definitely before or after another interval. If the intervals overlap however, then it means there's some uncertainty. I haven't quite got through the paper far enough to undersand how this kind of thing is handled. :-)

But I'm guessing that this kind of design means they're always consciously designing with error in mind. There's probably some acceptable amount of error in timing that they're able to carefully manage.

Edit: link to the paper for the lazy [pdf] http://static.googleusercontent.com/external_content/untrust...

Edit 2: It looks like the error typically ranges from 0 to 7ms averaging around 4ms. Outages can cause spikes in this error margin.

They handle uncertainty by delaying the transaction commit. Suppose you commit a transaction and at that moment, the error bar for time (on the server that handles your transaction) is 4 ms. The server will wait 4 ms to tell you the transaction completed. The result is that if two transactions commit near-simultaneously, it's random which will be assigned a lower timestamp, but guaranteed that no one will observe either transaction until after the timestamp at which that transaction is deemed to have committed. Basically, they handle the window of uncertainty by pausing access to the affected rows so that no one can peek into the window.

Temporal row-level locking.

> I mean, even if you had a picosecond accurate clock available for use inside a server farm, you would still need a way to query it with a known (not necessarily zero; just known) latency to synchronize several machines. Servers are not known latency machines (unless specialized hardware is involved).

I think it's just a case of traditional NTP (which is itself based on atomic clocks and/or GPS) done over 'the Internet' is subject to too much latency that it becomes unreliable for their needs (e.g. Spanner).

By putting the equivalent of their own NTP master servers (based on GPS and atomic clocks) in each of their major data centres they solve that part of the problem. The possible LAN latency is much more controllable and reliable, to within tolerances that makes Spanner workable.

The clever bit isn't putting their own NTP master servers in each data centre, it's how Spanner works when using this info. The article puts far too much emphasis on the former whilst glossing over the latter.

Their alternative to NTP (and, it should be noted, NTP is never once mentioned in their paper), TrueTime API is actually pretty impressive. They are able to maintain <10ms latency 99.9% of the time across data centers all over the world. That's not something you can easily do with NTP over the internet. Placing Stratum-0 receivers (and, in fact, Stratum 0 devices) in their data centers isn't unheard of, but that alone won't get you the kind of global-temporal-synchronization that Google is able to achieve with TrueTime API.

I'm looking very forward to the paper on that protocol/system which will hopefully be forthcoming - They tease it with this: "This section describes the TrueTime API and sketches its implementation. We leave most of the details for another paper: our goal is to demonstrate the power of having such an API."

I'd be worried about much more than 20ns. Someone email the ntp list not to long ago asking about getting nano-second resolution time, and one of the responses pointed out that light travels about a foot in a second. So do you want the time on this side of the room, or that side?

A foot a second is off by several orders of magnitude. It's closer to 300 thousand km per second in vacuum, and around 200 thousand km per second in fiber.

He obviously means a foot in a nanosecond.

Light travels about 300000 km in a second. I think you meant nano-second.

Presumably you meant, "travels about a foot in a nanosecond." From Google, "the speed of light / (10^9) = 0.299792458 m / s" -> about one foot.

As explained by Grace Hopper: http://highscalability.com/blog/2012/3/1/grace-hopper-to-pro...

Printable nanosecond for reference: http://blog.jgc.org/2012/10/a-downloadable-nanosecond.html

Whoops, meant nanosecond. Thanks.

TrueTime measures a point in time plus/minus an error interval. The API allows a program to query for when a time/error pair has definitely passed. Each transaction acquires locks using 2-phase locking. At commit time, the time/error are read and the decision to commit is stored durably using Paxos. The locks are then held until the time of the transaction has definitely passed. This guarantees that no process which grabs the locks after they are released can commit at an earlier time than previous holders of the lock.

Reply on news.ycombinator.com