8 ms·
Inside Google Spanner, the Largest Single Database on Earth
- sneak 14y agoDoes this mean that Google datacenters are vulnerable to GPS jamming and/or spoofing now?
- josephagoss 14y agoThey have atomic clocks as a backup
- RobAley 14y agoNo, because they have the atomic clocks as a backup/double check.
- alanctgardner2 14y agoIf 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.
- rwmj 14y agoPlease someone tell me where you can buy an atomic clock :-?
- teraflop 14y agoHere you go: http://www.thinksrs.com/products/PRS10.htm http://www.thinksrs.com/products/PRS10.htm
- DanBC 14y agoAgilent used to do them, but someone else does them now: (http://www.home.agilent.com/en/pd-1000001383%3Aepsg%3Apro/primary-frequency-standard?cc=GB&lc=eng http://www.home.agilent.com/en/pd-1000001383%3Aepsg%3Apro/pr...) (http://www.symmetricom.com/ http://www.symmetricom.com/)
- timdoug 14y agoeBay. :) http://www.ebay.com/sch/i.html?_nkw=FE-5680A http://www.ebay.com/sch/i.html?_nkw=FE-5680A
- cynwoody 14y ago>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: http://www.hpl.hp.com/hpjournal/pdfs/IssuePDFs/1965-04.pdf http://www.hpl.hp.com/hpjournal/pdfs/IssuePDFs/1965-04.pdf
- deleted 14y ago[deleted]
- jrockway 14y agoThe 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.)
- sneak 14y agoWhich is why I listed spoofing in addition to jamming.
- herge 14y agoOnly from James Bond villans. I am sure that the U.S. armed forces have a very secure scheme to prevent this.
- Bakkot 14y agoView all pages: http://www.wired.com/wiredenterprise/2012/11/google-spanner-time/all/ http://www.wired.com/wiredenterprise/2012/11/google-spanner-... 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?
- andrewcooke 14y agoyou'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). they've chosen gps time as a universal clock.
- whitewhim 14y agoThe 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
- andrewcooke 14y agothere are at least two relativistic effects involved in gps timings - http://www.aapt.org/doorway/tgru/articles/ashbyarticle.pdf 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.
- flyinglizard 14y agoWhat 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.
- dhotson 14y agoLooking 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/untrusted_dlcp/research.google.com/en//archive/spanner-osdi2012.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.
- snewman 14y agoThey 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.
- Sarien 14y agom( "Spanner" is the colloquial German word for voyeur. Not the best name for a database. :)
- lucian1900 14y agoAlmost everything means something unexpected in some language somewhere.
- Inufu 14y agoSpanner is also a kind of butterfly in German: http://de.wikipedia.org/wiki/Spanner_(Schmetterling) http://de.wikipedia.org/wiki/Spanner_(Schmetterling) ;)
- delinka 14y agoAnd 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.
- hahainternet 14y ago"Spanner" means 'foolish' or 'stupid' in the UK
- jrockway 14y agoAre there any words in the UK that don't mean "foolish" or "stupid"?
- kami8845 14y agoYes. "fag" means cigarette.
- aptwebapps 14y agoIdiomatic churn is rather high over there, isn't it? I guess at some point you run out of unique sound combinations.
- nlavezzo 14y agoIt'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 http://www.foundationdb.com
- shin_lao 14y agoFrom what I understand of this specific project, they "solved" the consistency problem (which is quite a feat, granted). They don't say they have an ACID NoSQL database, which is, to me, an oxymoron: ACIDity is useful if you have a powerful query language. In the end don't you fear that you might simply reinvent SQL? Or, am I missing something?
- Evbn 14y agoWhich part of acid is relevant specifically to SQL (joins, I assume you mean)?
- nlavezzo 14y agoACID 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.
- philip1209 14y ago"[. . .] the company’s online ad system — the system that makes its millions [. . . ]" That is an understatement.
- skeletonjelly 14y agoIs there a breakdown of their income sources? I would have guessed this is the prime income earner by a large margin.
- philip1209 14y agoFrom their 2010 10-K: "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) Source: http://investor.google.com/documents/20101231_google_10K.html http://investor.google.com/documents/20101231_google_10K.htm...
- awavering 14y agoIt's an expression, not an understatement.
- NelsonMinar 14y agoIf 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/untrusted_dlcp/research.google.com/en/us/archive/spanner-osdi2012.pdf 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.
- logn 14y agoAlso see: http://news.ycombinator.com/item?id=4526710 http://news.ycombinator.com/item?id=4526710
- Charlesmigli 14y agoInteresting article. Mainly on the timing aspect though. tl;dr version here http://tldr.io/tldrs/50b375dd52b89ec3440000df http://tldr.io/tldrs/50b375dd52b89ec3440000df
- eze 14y agoPast and current Googlers that frequent HN are notoriously absent from this thread. Come on, guys! Surely your NDA must allow some vague commentary...
- euyyn 14y agoWell, I don't know of the details of Spanner, but even if I did I wouldn't dare trying the limits of that NDA. Job's too nice to lose over that :)
- sargun 14y agoArgh, "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.
- sargun 14y agoArgh, "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.
- sargun 14y agoArgh, "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.
- ghshephard 14y agoI had to chuckle when I read this: "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. Reading about the True Time Api at: http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/ko//archive/spanner-osdi2012.pdf http://static.googleusercontent.com/external_content/untrust... "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.
- emmelaich 14y agoUsing NTP is ok until your network connection is broken for hours. Think backhoe into the fibre.
- ghshephard 14y agoData 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.
- abhijat 14y ago> VC is Google shorthand for video conference That is the case nearly everywhere, I think :-)
- Too 14y ago“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.
- plasma 14y agoIt'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).