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).
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.
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.
> 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.
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.
It's interesting to see that the creators of BigTable and the early proponents of eventual consistency have invested the last 4.5 years building a system that adds back strong consistency guarantees.
If the Spanner paper is as important as BigTable, ACID may become the new goal for those building distributed systems.
Full disclosure: I'm with FoundationDB, which is a distributed NoSQL database with high performance cross-node ACID transactions. http://www.foundationdb.com
> It's interesting to see that the creators of BigTable and the early proponents of eventual consistency have invested the last 4.5 years building a system that adds back strong consistency guarantees.
I think it's a large misconception that these are competing ideas. They're not. They just represent different use cases: search results don't need to be consistent within seconds of events. Customer information, however, does.
I agree that different projects prefer different tools, but these data stores most certainly do compete with each other for developer's use within Google.
Per the paper: "At least 300 applications within Google use Megastore (despite its relatively low performance) because its data model is simpler to manage than Bigtable’s, and because of its support for synchronous replication across datacenters."
So, the current trade off is ACID vs. performance, but I think the interesting point is that ACID is winning more and more now that a distributed ACID database is available to their developers.
Again, according to Google: "We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions."
I'm with FoundationDB, which is a distributed NoSQL database with high performance cross-node ACID transactions.
Which isn't at all comparable with Spanner, since Spanner works between clusters/datacenters, unlike FoundationDB.
"Distributed" is getting severely overloaded when it comes to databases. We need to stop calling databases with sub-millisecond latency to other nodes "distributed". They're not distributed, they're clustered, and the techniques you can use with them are vastly different.
Consistent transactions with a clustered database are a solved problem, full stop, and available to every developer with virtually any database backend, simply by building your transactions on top of Apache Zookeeper, and running whatever durable database you want underneath.
Doing consistent distributed transactions at a global scale, which is what Spanner does, is so far novel. Doing ACID transactions in a 24-node cluster (what is described at FoundationDB's website, for instance) isn't impressive these days, and if that's all Google had done, you'd see a collective yawn around the web.
ACID and NoSQL are not mutually exclusive, although that is a common misconception due to the fact that almost all NoSQL databases gave up ACID in exchange for BASE (eventual consistency), making the development of their distributed databases much easier. However, ACID is simply a set of properties that allows you to group a set of reads & writes to a database into a transaction that is Atomic, Consistent, Isolated, and Durable. That set of reads & writes does not need to be SQL - in our case, it is a set of reads from and writes to a database of ordered keys and values.
For example, you could read the values associated with keys "a" and "b" and "c" and based on that information, make a change to the values associated with keys "c" and "d" and then commit the transaction. The transaction then either fails completely (if one of the keys you read had been written to since your read, in which case you re-try the transaction) or succeeds completely. That is an ACID transaction in a (NoSQL) key-value store.
That sounds useful, but not as useful as transactions on joins.
It's great to have transactions when you have to cross reference data, on a key/value store, although you can have range queries I submit that kind of operations is less frequent.
But still, it sure is great to be able to run a batch of operations with the confidence it will be transactional, I'm sure there are many use cases that can benefit from it.
Oddly enough, it's strange that there aren't more NoSQL engines offering this feature as once you have MVCC you've done the hard part and AFAIK several NoSQL db have MVCC.
Yep, those types of operations are less frequent in k/v stores, but we believe it is because of the lack of ACID in most of them. When you have ACID and ordering you can use transactions to keep data and multiple indexes on that data in synch, and use range operations to query the indexes.
You can build all manner of higher level data structures with a transactional ordered k/v store, which is why our concept of "layers" is possible: www.foundationdb.com/#layers
Just to clarify what the CAP theorem says: If one node parts, then that node is either inconsistent or not available. A fault-tolerant database could potentially stay up with a single unavailable node.
No, they haven't broken the CAP theorem. If the network were to partition badly enough, Spanner would lose its quorum and would become unavailable, at least for guaranteed-consistent operations.
In practice, a network partition bad enough to bring down something like Spanner is pretty rare. (I worked at Google for four years, and I can't recall such a partition occurring.) But in theory it's certainly possible.
"As Fikes points out, Google had to install GPS antennas on the roofs of its data centers and connect them to the hardware below."
This is usually one of the first things an enterprising sysadmin does at companies when they first start thinking about time - drop a GPS receiver on the roof (and they usually come up with a bunch of cool graphs showing where all the satellites are over time).
Soon thereafter, and a bit of reading about the NTP protocol, they realize that just adding:
server 0.pool.ntp.org
server 1.pool.ntp.org
server 2.pool.ntp.org
server 3.pool.ntp.org
to their ntp.conf is sufficient for 99.99% of all endeavors which require accurate time, outside of big physics, and, apparently Google's Spanner Database.
This part was a bit incomplete:
"Typically, data-center operators keep their servers in sync using what’s called the Network Time Protocol, or NTP. This is essentially an online service that connects machines to the official atomic clocks that keep time for organizations across the world. But because it takes time to move information across a network, this method is never completely accurate,"
Much of the purpose (and math) behind the NTP protocol is to deal with network lag. And it does a pretty good job doing so.
"This implementation keeps uncertainty small (generally less than 10ms) by using multiple modern clock references (GPS and atomic clocks)"
So - apparently 10ms is their breakpoint - 10ms is about the limit of what you can expect out of NTP, so I guess it makes sense that if Google needs to do 10ms or better, something of their own invention would be required. Cool graph on the paper showing that 99.9% of variance across data centers thousands of kilometers apart are < 10ms deviation.
Data Centers don't lose network connectivity - designed to have ingress and egress far enough apart that a local disaster can't take down the entire ring. Also, as I noted, one of the first things that enterprising sysadmins do is toss a Stratum-0 receiver (GPS receiver) on the roof, which feeds into the NTP protocol.
Finally - the entire purpose behind TrueTimeAPI is to sync up spanner's commits so they are consistent across the replicated/sharded nodes. Without Network, that database capability would come to a halt way before network time became a problem.
The bigger issue is the <10ms requirements. NTP over the Internet does not get you that consistently, and certainly not at the 99.9% success that Google was able to achieve with TrueTime API.
Also:
> “We can commit data at two different locations — say the West Coast [of the United States] and Europe — and still have some agreed upon ordering between them,” Fikes says, “So, if the West Coast write happens first and then the one in Europe happens, the whole system knows that — and there’s no possibility of then being viewed in a different order.”
That's a large enough scale that you have to deal with relativity (light takes almost precisely 0.03 seconds to go from Palo Alto to Paris, eg). So in some sense there is no correct ordering. Anyone know how they deal with this? Have they just chosen some arbitrary point to make their reference frame, for purposes of ordering commits?
you're confusing finite speed of light and relativity - they're not really the same (although they are of course related). the relativistic sense of "no correct ordering" is irrelevant to the problem that google are solving (two observers, watching google's machines, from different, high-speed spaceships, may still disagree about the order of what happens in paris and the usa, or even in two machines in the same datacentre, but google doesn't care).
The entire underpinnings of GPS relies on the speed of light to calculate positions as the GPS satellites send their position, velocity and a current time stamp. These can be used to generate a distance from the satellite based on the velocity of the light. Through multiple distance readings of multiple satellites a position can be determined. Relativity does in fact play a role since the satellites are not geosynchronous they are moving in comparison to Earths reference frame. This creates non negligible errors in GPS which have been accounted for in the GPS equations. If they hadn't been we would have much more error in GPS
there are at least two relativistic effects involved in gps timings - http://www.aapt.org/doorway/tgru/articles/ashbyarticle.pdf - but they would not be solved if the satellites were in geosynchronous orbit as the earth itself does not have a single non-accelerating reference frame.
If you want more detail, this article links a research paper that describes the system in detail. Very clever focussing on the timebase as a way to improve distributed consistency; I'd always assumed NTP was sufficient. http://static.googleusercontent.com/external_content/untrust...
The part of the article that stood out to me is that Spanner is used in F1, the new backend datastore for AdWords. That's a significant vote of confidence.
"Advertising revenues made up 97% of our revenues in 2008 and 2009, and 96% of our revenues in 2010. We derive most of our additional revenues from offering display advertising management services to advertisers, ad agencies, and publishers, as well as licensing our enterprise products, search solutions, and web search technology."
2010 Revenue: 29.321 Billion
Therefore, advertising brought in >$28 Billion in 2010 (Therefore they average $1 Million in advertising revenue ever ~19 minutes, hence the laughable understatement of the article)
If you read the Spanner paper, there is a hierarchy of timers involved. GPS is one level, but every datacenter also has machines equipped with atomic clocks. I suspect even with GPS failure they could run entirely on atomic clocks, it would just increase their uncertainty, which would increase the commit times (Spanner is based on the idea that a transaction is committed when the time at which it was committed is guaranteed to have passed). As far as I know, it could actually run really slowly without special timing equipment.
>I suspect even with GPS failure they could run entirely on atomic clocks, it would just increase their uncertainty
Using GPS is an operational convenience, not a necessity, I would think. If GPS didn't exist, they would have to have a master atomic clock, say, in Mountain View. Then they would have to bring each remote clock to Mountain View, synch it with the master, and then ship it (running continuously) to its final destination.
I remember perusing an HP catalog in the late eighties. You could buy a portable "traveling clock" for around $40,000. It was intended to be used to synchronize remote clocks. Here is a 1965 article from the Hewlett-Packard Journal, which describes the process:
The article shortened "GPS-disciplined clock" to "GPS clock", which makes it inaccurate. The GPS clock is simply used to keep another clock accurate. (I use this setup at home; a timing GPS produces an accurate pulse-per-second, but the system clock is responsible for maintaining the time between pulses.)
(And if you're wondering, 15ns-accurate GPS clocks are $30 on eBay.)
“We can commit data at two different locations — say the West Coast [of the United States] and Europe — and still have some agreed upon ordering between them,”
I'm a bit confused by this. How will this solve the situation when the first transaction renders a second transaction forbidden. To keep it simple, say an account with only $10 and two transactions trying to withdraw $10 each.
It's been a while since I last read the paper, but I think the second transaction would fail (optimistic locking) and must be re-tried (and as such would see the updated balance).
Argh, "And, yes, you do need two separate types of time keepers" - No, you must establish a quorum of time keepers. Almost everyone's advice when setting up high reliability time keeping systems is to use 1 clock, or >3. 2 is no better than 1.
And the British use "spanner" where the Americans use "wrench." lucian1900 has it right. And because of that, you're either going to spend ages finding (or creating) words to market by, or you're going to just name the thing, get over it, and get back to work.
Also, keep in mind that this service was never meant to be public-facing. So, unlike Bing which was named with a Chinese interpretation in mind, Google doesn't need to care whether its internal service has a bad connotation in German colloquialism.
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.