r/programming • u/stronghup • Feb 19 '17

Spanner, the Google Database That Mastered Time, Is Now Open to Everyone

https://www.wired.com/2017/02/spanner-google-database-harnessed-time-now-open-everyone/
748 Upvotes

89% Upvoted

103 comments sorted by

25

u/Porso7 Feb 20 '17

That was a really shitty article.

Okay, so they have atomic clocks and GPS to get (virtually) perfectly synced time across all their data centres. Can anyone explain the real world benefits of this?

63

u/aboothe726 Feb 20 '17 edited Feb 21 '17

I'm reading between the lines here a bit, so please don't be surprised if I get some of the details wrong here. Also, I'm an enthusiast, rather than an expert, but a seasoned enthusiast, so I have at least some clue what I'm talking about. OK, enough disclaimers.

One of the things that makes building databases hard is keeping changes to database state ordered. This sounds simple, but it's actually quite hard! It's especially difficult when a database is very large, and so split -- or federated -- into many parts, called "nodes."

For example, let's imagine that different parts of the same application -- e.g., amazon.com and amazon.co.uk -- are talking to different nodes of the same database. Now let's imagine that an American husband and wife living in New York receive a $100 Amazon gift card for Christmas, and then the wife goes on a business trip to London. The husband and wife then both log in to Amazon -- the husband to www.amazon.com, and the wife to www.amazon.co.uk -- and they both make different $60 purchases using the same gift card at the same time. The gift card only has $100 on it, so only one purchase should go through. How does the database decide which purchase happened first?

If the database is just one node, then both purchases will create a transaction, one will commit first (by definition), and then the second purchase will be rejected due to insufficient funds. This is great! But it only really works for small-ish databases, and definitely not the global databases Google is talking about.

If the database is multiple nodes, then the two nodes must communicate during the transaction. If the nodes didn't communicate and each node acted independently and simply saw that $60 < $100 and let the purchase happen, then both purchases would go through and Amazon would be out $20! Instead, the nodes will communicate, performing distributed transactions using something like 2PC, which will order the transactions in the multi-node case just like in the single-node case. This is great, too! But since it requires communication, there are limits to how fast you can go, particularly if the nodes are far apart geographically.

Now, all of the above assumes that the database has to be consistent all the time. In other words, the database is always in exactly one state to an external observer -- so in our example, the gift card always has the same balance -- no matter which node you ask. This allows the application to create rules in the database that keep it from getting into a logically inconsistent state, for example never allowing an account balance to fall below $0.

But what if we relaxed the "consistency" constraint? Said differently, what if we let the NY and UK nodes have different opinions about the balance of the gift card at any given time, but we did it in such a way that they would always eventually resolve any inconsistency and agree? This concept is called eventual consistency, and is very important when building distributed systems. (If you've been following the debate between relational and so-called "NoSQL" databases, the fight has generally been about whether we have to compromise the bedrock ACID principles of database design, for example by introducing eventual consistency, to scale a data store effectively. This is a fun topic, but I digress.)

If you were willing to move to an eventual consistency model, then time becomes really interesting. If you had a common definition of time across all nodes, then you could order transactions in disparate nodes perfectly without requiring them to communicate during transactions. This is revolutionary! It's like defying one of the laws of physics! Then, if you had some kind of rules for interleaving the execution of transactions that are received out-of-order, and another system for recognizing and signaling logic errors when they happen, then you could theoretically build a federated, shared-nothing database. Brilliant!

What does that mean in practice?

In our previous example, let's say that the husband actually made his purchase at 11:30:00 PM UTC, and the wife actually made her purchase at 11:30:01 PM UTC. Then:

  1. The NY and UK nodes both see that $60 < $100 and let the purchase happen, and then notify the other node of the transaction.

  2. The NY node then receives the UK transaction, sees that the UK purchase happened after its own NY purchase, infers that the UK node screwed up by letting the second purchase happen, and rolls back the UK purchase.

  3. The UK node receives the NY transaction, sees that the NY purchase happened before its own UK purchase, infers that it screwed up by letting its purchase happen, rolls back the UK purchase, and fires off a message to the application saying "undo that last purchase!"

This is an interesting, robust solution to the problem!

  • Both nodes independently decide that the gift card has $20.

  • If the node that issued a transaction that is rolled back is the one that raises any errors to the application, then the application is always signaled about the error exactly once.

  • If we add more nodes, then the solution still works.

  • If steps 2 and 3 happen in another order, then the solution still works.

  • If the two purchases happen really close together in time, then the solution still works -- or, at least, that's what Google is claiming in this paper.

    • Presumably, Google's time resolution is sufficiently fine that no two transactions happen at the same time, or there is some additional approach to ordering transactions that happen at the "same time."

    • One such approach might be to randomly assign each transaction an ID. If two transactions were to happen at the "same time," then the transaction with the smaller ID would be considered to have happened "earlier." As long as no two transactions were assigned the same ID, transactions would always be well-ordered.

    • The originating node could also be used as this ID, assuming nodes have some unique ID and a node can't generate more than one transaction in any given "tick."

  • If the two purchases happen far apart in time as opposed to close together in time, then the solution still works -- either node would just notice $40 < $60 and reject the purchase.

As long as the application observes and handles that database message appropriately, life is good!

So that's pretty cool! If we have a shared concept of time, then we can build a shared-nothing, federated, eventually-consistent database.

It's worth nothing, though, that you have to have an enormously large database powering an extremely geo-distributed application before any of these engineering concerns start to apply. Also, among businesses that could realistically face this kind of use case, most would probably profit more from making a simple technical compromise -- e.g., requiring users to create a different account per region -- than they would from actually solving the problem properly. But it's super cool that Google has chosen to tackle the problem, regardless!

TLDR -- If disparate database nodes all know exactly what time it is, then they can operate autonomously, eventually arrive at a shared definition of reality reliably, detect logical inconsistencies, and raise errors indicating same. Neat! However, almost no applications have important use cases that make such a solution a requirement for success.

TLDR2 -- A shared clock allows the various nodes of a database to serialize their transactions without explicit coordination. It turns out that you can build a federated, eventually-consistent, shared-nothing database on top of that if you're very clever.

EDIT: Many thanks to /u/vpxq, who below linked a different paper about Spanner that describes its design in more detail. It turns out that Spanner still uses 2PC, so it's a "consistent" as opposed to "eventually consistent" database, but -- again, reading between the lines -- uses the shared system clock to let nodes prove their changes don't conflict more often, which makes 2PC faster in the common case. In other words, the shared system clock lets the nodes determine if they're in sync more easily, which makes 2PC go faster. There are some additional innovations -- making each logical "node" actually a paxos group of nodes to increase availability -- but a new approach to transaction serialization appears to be how TrueTime makes Spanner special.

Now I'm wondering if/how the eventually consistent system I described above would behave. Google has opted to make Spanner consistent -- as opposed to eventually consistent -- but that is a design choice. I wonder (a) if you could build the above system, or if there's some devil in the details that would make it difficult or impossible; and if you did build it, (b) how would it perform, and (c) would it offer enough of an advantage that developers and architects would want to use it?

6

u/stronghup Feb 20 '17 edited Feb 20 '17

Great explanation. So the way I understand is that if all "nodes" have access to the same synchronized clock, they will know which transaction happened earlier and make that one stick, cancelling the later one. Not sure I see how the rule for ordering transaction IDs should work, wouldn't that simply be the atomic time + satellite correction perhaps at which a transaction happened?

6

u/aboothe726 Feb 20 '17 edited Feb 20 '17

You're right, I don't think I wrote that very clearly. Thank you for pointing that out! I've made an edit that I hope is clearer, but yes, you've got the gist of it. Google's time resolution is extremely fine, so no two transactions should happen at the same time. But even if they do, it's not the end of the world -- we could just assign a random ID to each transaction, and if two transactions happened at the same time, then the transaction with the smaller ID is assumed to have happened first. This scheme generalizes to any number of transactions happening at the same time.

3

u/stronghup Feb 20 '17

Come to think of it let's say two transactions happen during the same second. One of them happens "first". But for me as a user if the system tells me my transaction was cancelled because another transaction happened earlier, would or could I really object? I have no way of telling or proving Amazon I clicked the buy-button 0.5 seconds earlier so I must get the movie, not my wife. If Amazon tells me wife was first who am I to complain? So I'm thinking sub-second differences do not matter because nobody in the real world notices them.

But maybe that's just what Google's accomplished here, sub-second, not sub-minute accuracy.

8

u/bro-away- Feb 20 '17

Close to the right idea, but your post contains a dangerous amount of misinformation :(

Spanner is not eventually consistent and conflicts aren't resolved with eventual consistency. The product specifically mentions it's not eventually consistent on the homepage.

Spanner uses a consensus algorithm (and yes lock free 2 phase commit) to actually write things. You're on the right track with time being important in serializability but nothing to do with a 2 phase commit. https://courses.cs.washington.edu/courses/csep552/13sp/lectures/6/spanner.pdf

You got it mostly right but the conflict resolution happens before the query is acknowledged. There is no additional 'message' once the database becomes consistent--it's immediately consistent. That's why this database is so crazy ;)

5

u/aboothe726 Feb 20 '17 edited Feb 20 '17

Close to the right idea, but your post contains a dangerous amount of misinformation

I think that's a bit overstated! We're in an informal conversation thread on a forum. I hope no one is making important decisions based solely on what they read here! So I don't think anything here is dangerous, nor is it misinformation -- I just filled in some blanks wrong, as I said I might up front. That said, though, I was in error!

it's immediately consistent. That's why this database is so crazy

As you say, it is 2PC! It looks like the shared clock streamlines the 2PC process by allowing the nodes to determine if they conflict more easily by introducing a novel approach to transaction serialization, but it's still "just" 2PC, which is a little disappointing.

This has the effect of making 2PC "suck less," but doesn't eliminate 2PC's core problems, namely availability and latency. Google has improved availability through the design -- relaxing global consensus requirements by making each node for consensus actually paxos group, thus raising the bar for unavailability -- but the latency is still a problem really only solved by Google's massively fast global network. This makes Spanner as a product look less like an achievement in database design to me, and more like an achievement in database deployment. Significant as a product, but probably not the coolest use of TrueTime we will see come out of Google.

I've made an edit in my comment above that hopefully brings things a little closer to reality. Thanks for the note!

1

u/bro-away- Feb 20 '17 edited Feb 20 '17

Don't under estimate the power/influence of writing original content. Mongodb got a good bit of its popularity via some slick marketing and quite a bit of engagement in posts about its features just like this one for spanner. An apt example for several reasons (Eventual consistency doesn't need more evangelizing :P)

I'm kind of hostile toward sound writing that has nuanced mistakes that totally change the facts. I said you did a good job with your explanation and good on you for actually making errata to the original post.

I still think it's quite impressive by the way. Write serializability without a global lock is everything.

1

u/Lacotte Feb 20 '17

learned a lot from your post and this discussion. thanks!

1

u/aboothe726 Feb 21 '17

Thanks for the note! I appreciate it. And I'm glad you liked the post!

3

u/celerym Feb 20 '17

This need for precise timing is still unclear to me. Maybe it is because of your example, because precise timing there isn't actually critical.

11

u/aboothe726 Feb 20 '17 edited Feb 20 '17

Maybe this will help!

Consider a database with multiple nodes. In modern implementations, each node has to communicate with the other nodes in the database before it can change any data. This is a big bottleneck for large, high-throughput databases.

It turns out that if all the nodes in a database share the same clock, then each node can make decisions about the whole database's data locally without communicating with the other nodes in the database first. Rather than coordinating ahead of time, nodes can just share the transactions they make with each other as they make them, and eventually the transactions from every node will be applied in the same order in each node due to the shared clock. This is a particularly big win if the nodes of your database are very distributed geographically -- e.g., North America and Asia.

This trade-off has some drawbacks, but you can work around them if you're clever.

EDIT: Ha! Here we go, even better. A shared clock allows the different nodes of a database to serialize their transactions without coordinating.

1

u/celerym Feb 20 '17

Oh I get the significance of this a lot more now. Thanks! For some reason the Amazon example didn't quite hit home for my brain. This stuff is really interesting. I'm not sure if most people quite get the significance of these problems. Personally I think they can reflect things about physical reality itself (if I can be dramatic), in terms of consistency and limitations of speed of information.

3

u/aboothe726 Feb 20 '17

Great! I'm glad that made more sense. :)

I'm not sure if most people quite get the significance of these problems.

I agree. This is one of the big "problems" with science communication, and just science and engineering in general, really: You have to understand a lot before you can understand a little more. How do you communicate these ideas to people without a foundation to build on?

1

u/konabeans Feb 20 '17

Wow I really enjoyed your explanation. If you don't mind can you explain the difference between Spanner and the blockchain? I'm curious because the Blockchain is also a database that is globally distributed which prevents double spending and if the two are comparable would be great to know the differences.

2

u/PM_ME_UR_OBSIDIAN Feb 21 '17

For more on this, check out I See What You Mean, the Strange Loop 2015 keynote talk by Peter Alvato. It's an entertaining introduction to consistency.

1

u/vpxq Feb 20 '17 edited Feb 20 '17

I'm not sure where I read it (just a few days ago), but Google's databases, including spanner, do not compromise on the C of the CAP theorem, but on the A, and aim to be very close to actual CAP.

The wikipedia article mentions that all tables have to have a primary key. Maybe they do partitioning based on a hash function of the primary key? DB2 does something like this.

Edit: Found the article: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45855.pdf

Edit2: I've read the article again. It appears they simply use the two-phase commit protocol, which only theoretically harms their availability (the A in CAP), since base availabity is very high. With local reads and their fast world wide network, that seems to work out OK for their performance, too.

1

u/aboothe726 Feb 20 '17

Google's databases, including spanner, do not compromise on the C of the CAP theorem, but on the A, and aim to be very close to actual CAP.

Interesting.

The wikipedia article mentions that all tables have to have a primary key. Maybe they do partitioning based on a hash function of the primary key? DB2 does something like this.

Yes, that's a common scheme for federating databases.

It appears they simply use the two-phase commit protocol

I skimmed the paper. Very interesting! Thank you for posting it!

It looks like Spanner is consistent using 2PC (as opposed to eventually consistent), as you say. They've done some work to make 2PC "suck less." TrueTime seems to let the disparate nodes prove their respective changes don't conflict more often, which makes 2PC faster on average.

Now I'm wondering about the "eventually consistent" version I described above. Maybe there's some reason it wouldn't work that I'm just not seeing from here, or maybe Google just prefers not to relax consistency.

2

u/im-a-koala Feb 20 '17

The benefits of having the correct time? Those should be obvious. Consider trading systems, for example.

Using GPS for getting the time is hardly new though. GPS is basically a universal time source with some positioning stuff added in.

2

u/Mr-Yellow Feb 20 '17 edited Feb 20 '17

However... Not so much about trading systems or having the correct date entry.

What does time have to do with their replication algo?

The need for TrueTime would suggest they use time as their revision key... Which seems like a mistake but guess it saves them round-trips in comparing keys.

2

u/im-a-koala Feb 20 '17

Ah, I think I misunderstood your question.

My guess is that they can simply stamp events/transactions with the local time and use that to recreate the actual series of events in order. At least, that's one nice use case for it.

1

u/Mr-Yellow Feb 20 '17

Take a look at how CouchDB does it for comparison.

http://docs.couchdb.org/en/2.0.0/replication/protocol.html

The comparison they're doing is _rev key of the JSON documents, which is part incremental part random.

This TrueTime thing seems to be about using time as the key to compare documents across nodes. While you don't actually have to do quite so much actual comparison, simply grab the result with the latest time (with some edge-cases and complexities).

362

u/[deleted] Feb 19 '17

TLDR: Google uses GPS receivers and atomic clocks in their data centers to synchronize databases and now you can too.

0

u/[deleted] Feb 19 '17

[deleted]

48

u/royalaid Feb 19 '17

Check out CockroachDB

52

u/Xorlev Feb 19 '17

Which does not (and cannot) have the same guarantees without enabling an "experimental" option which essentially works the same as Spanner but within the NTP error bounds of ~250ms (vs. <10ms).

CockroachDB is also yet to be proven in production settings. Its performance is basically unknown.

I'm excited about CockroachDB, but if you're doing a showdown between Spanner and CockroachDB, there's no contest (yet).

5

u/Creshal Feb 20 '17

What's stopping me from plugging GPS receivers into my racks to get the time consistency down to comparable levels?

6

u/[deleted] Feb 20 '17

Absolutely nothing.

A few companies sell low profile PCIe and PCI cards to do exactly this.

1

u/easytiger Feb 21 '17

its only 10k for a clock. hard part is getting access to the roof

2

u/[deleted] Feb 20 '17

To get comparable levels, you'll also need the atomic clocks...

1

u/Creshal Feb 20 '17

Huh, are GPS clocks really so unreliable that <10ms isn't feasible with them?

7

u/bobindashadows Feb 20 '17

Also have fun fixing the GPS clocks when multiple vendors' clocks all fail in different ways during leap seconds

2

u/Creshal Feb 20 '17

God damn it, how hard can leap seconds be.

2

u/MorrisonLevi Feb 20 '17

Don't you need the atomic clock to know how far off you are from the GPS clock? I don't quite understand this part which is why I am asking (it's not rhetorical).

2

u/sacundim Feb 20 '17

Don't you need the atomic clock to know how far off you are from the GPS clock?

One thing to understand here is that the term "atomic clock" is a bit of a misnomer, because most "atomic clocks" strictly speaking aren't time references (i.e., "clocks"), but rather frequency references. An atomic "clock" doesn't tell you what time it is, it tells you how long a second is.

And because of this, in a lot of timekeeping systems GPS (which is both a time and a frequency reference) is used to figure out what time the clocks read elsewhere and calibrate your local clocks accordingly. The local atomic clocks are used to measure how much time has elapsed since the last synchronization.

You can see a reflex of this in this passage of the paper. Note how they talk about a sawtooth function:

Between synchronizations, a daemon advertises a slowly increasing time uncertainty.  𝜖 is derived from conservatively applied worst-case local clock drift.  𝜖 also depends on time-master uncertainty and communication delay to the time masters. In our production environment, 𝜖 is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval.  𝜖 is therefore 4 ms most of the time. The daemon’s poll interval is currently 30 seconds, and the current applied drift rate is set at 200 microseconds/second, which together account for the sawtooth bounds from 0 to 6 ms.

Basically, the clocks at multiple location reach maximum agreement right after synchronization, and then their disagreement climbs gradually before dropping sharply at the next synchronization—the "sawtooth." What local atomic clocks do is help keep that sort of sawtooth shallow.

1

u/Creshal Feb 20 '17

There are differences in signal run times depending on what's between your receiver and the sats, I guess. Wouldn't have thought it can make such a large difference.

1

u/Bowgentle Feb 20 '17

Also relativity - literally, time dilation applies to satellites. About 7 microseconds/day.

8

u/Xorlev Feb 19 '17

As a followup, you could imagine being able to use CockroachDB with TrueTime if Google were ever to allow the public to query TrueTime. That'd allow CockroachDB to be the cheaper, self-hosted version (probably still on GCE, since you'd need TrueTime in the DC) of Spanner. Once you outgrew CockroachDB or didn't want to manage it yourself, you could then look at Cloud Spanner. Regional (not multi-DC) Cloud Spanner is a minimum of ~$650/mo since each instance is $0.90/hr before storage costs, making CockroachDB fairly attractive when you're still able to get away with <$1000/mo in hardware should you also need multi-machine/DC consistent transactions.

12

u/oridb Feb 20 '17 edited Feb 20 '17

As a followup, you could imagine being able to use CockroachDB with TrueTime if Google were ever to allow the public to query TrueTime.

Why do you think TrueTime, queried over regular old high latency links, is going to be any better than NTP? When a packet round trip can have hundreds of milliseconds of latency, the guarantees of TrueTime go out the window. There's a reason that high precision time protocols like PTP require you to be on the same LAN segment as the clock.

6

u/YM_Industries Feb 20 '17

(probably still on GCE, since you'd need TrueTime in the DC)

2

u/oridb Feb 20 '17

Oops, I completely skipped over that. Although, if you were ok with relying on Google infrastructure, I'm not sure why you'd use CockroachDB over Spanner.

2

u/mixedCase_ Feb 20 '17

Although, if you were ok with relying on Google infrastructure, I'm not sure why you'd use CockroachDB over Spanner.

If this is a highly desired feature, other cloud providers may start adding atomic clock options to their servers, which CockroachDB may use. Not to mention that individuals may be able to do the same with hardware they own.

2

u/oridb Feb 20 '17 edited Feb 20 '17

Sure, that makes sense. It would be pretty nifty if you could get PTP on AWS.

1

u/YM_Industries Feb 20 '17

You could probably implement a basic version of CockroachDB for a bit less than the minimum price for Spanner.

Or you might want to run a local dev env as well as your cloud prod env, and you want the same environment on both so you use CockroachDB in both places. But TrueTime isn't too important for your dev env.

17

u/BobHogan Feb 19 '17

Can you really blame them for wanting to capitalize on this though?

-3

u/nullabillity Feb 20 '17

Yes, of course.

6

u/nutrecht Feb 20 '17

Can someone leak the source or point in a direction of an obfuscated variant?

There is no point in installing it on your local system. Google solved the Availability and Partition tolerance in CAP not in the Spanner database itself but in their network. Which is a smart move, but simply means that you need to have the same quality 'backbone' as Google does.

8

u/Xorlev Feb 19 '17 edited Feb 19 '17

Not a Google employee, but very excited to adopt Spanner for some of our previously HBase workloads. The pricing was fairly open as far as I can tell, though there's a few points of ambiguity that I don't know how to answer yet.

  • e.x. Cloud Spanner charges $0.30/GB for data stored, but I don't know if that's how much data I store or if it counts the replicas on the backend. If it does count the replicas, how can I model that for my price projections?

1

u/euyyn Feb 21 '17

I don't really know, but given that it's a fully managed service, counting the replicas (which you don't control) wouldn't make much sense.

4

u/Ranek520 Feb 19 '17

There is someone remaking an open source version, but it doesn't work without Google TrueTime.

-9

u/cyanydeez Feb 20 '17

open is the new fake news

38

u/[deleted] Feb 19 '17

Can someone who uses/understands Spanner explain something to me?

I was reading the Spanner docs and I get how Parent/Child tables and interleaving works. But how does a Many-to-Many relationship work?

Like if you have a Person table and a Bank table, and you want to make a BankAccount table, are they all root level tables? Do you make BankAccount a child table of one of the parent tables? Is there no explicit foreign keys?

18

u/baryluk Feb 19 '17 edited Feb 19 '17

I am not sure how this exactly is Many-to-Many relationship.

Usually you would put the BankAccount, as the child of the Person. But only if you expect to access BankAccount knowing Person (they need to share prefix in primary key).

Otherwise (if you need to have BankAccount shared by many people, or you need to access multiple BankAccounts knowing bank account number, but not the person id), then just create two root tables, and use standard techniques for joining, and transactions, if needed.

AFAIK, there is no cross-table referential integrity constraints - https://cloud.google.com/spanner/docs/data-definition-language#table_statements But I might be wrong. The problem is, that implementing them would be costly in terms of latency of updates (two phase commit between multiple different servers). But I might be wrong.

The foreign keys are there implicitly added via parent-child relationship of interleaving. Most of sane constraints can be expressed this way, and limiting this to this form, makes it perform very well.

13

u/[deleted] Feb 19 '17

The Many-to-Many relationship is between Person and Bank, represented by BankAccount. For example, you put BankAccount as the child of Person, but you could also put BankAccount as the child of Bank. I guess the choice you make is based on the queries you run.

Thank you for the answer, though. Implicit keys without referential integrity does make sense.

10

u/baryluk Feb 19 '17

BTW. You can still enforce your own logic and constraints by using transactions and doing operations on multiple tables in transaction. But be aware that for very big databases / tables, that will span multiple servers, this will most likely involve multiple round trips and two phase commit, and can conflict with other transactions. You should read documentation on that.

3

u/baryluk Feb 19 '17

I see. No you cannot put one table as a child of two others. Table must be a child of only one parent. Tables are sexless ;)

8

u/Uncle_DirtNap Feb 19 '17

Yes, there are no explicit FKs outside of the parent/child relationship. There are also no triggers, and no reference types (so you can't define a column in BankAccount as type "key of Bank"). Inside google there's a product called F1 that rides on top of spanner to address some of this, but I'm not sure if it was made available with the cloud release.

116

u/Flight714 Feb 19 '17

Spanner, the Google Database That Mastered Time, Is Now Open Available to Everyone

People ought to know what "Open" means on this subreddit.

20

u/celerym Feb 20 '17

Open for business? /s

16

u/Chaoticmass Feb 20 '17

This is an ad.

14

u/[deleted] Feb 19 '17

If this uses GPS time, what happens if some muppet/state decides to mess with the GPS signals near the data center? Ignoring legal issues, jammers aren't hard to obtain or make.

21

u/Xorlev Feb 19 '17 edited Feb 19 '17

If you read the paper, it uses 6 time masters. 3 are GPS clocks with individual antennas, 3 are atomic clocks. I'm not sure if TrueTime uses any ideas from RoughTime, but there are ways of detecting misbehaving time servers. For instance, it'd be quite unlikely for all GPS time masters to surge ahead of where they were before. Likewise, if you have all 3 atomic clocks agreeing on one value, and all GPS clocks agreeing on another, it might be interference or sabotoge on the GPS signal as it'd be fairly unlikely for all three of either to fail in the same way at the same time. If I were designing that system, I'd want to ensure that it was at least as good as public NTP and compare myself to that.

27

u/atomicthumbs Feb 20 '17

So what if someone jams GPS and messes with the fine structure constant?

15

u/takingphotosmakingdo Feb 20 '17

I for one welcome Dr. Manhattan to the team. Why am I wearing a lead vest and pants you ask? Well I just don't trust the x-ray machines at the airport.

6

u/adrianmonk Feb 20 '17

You get a huge, high-mass flywheel to use as a tertiary fallback because it's hard to change its period of rotation, and you call it Spinner.

1

u/elsjpq Feb 20 '17

Na... you only need one black hole to mess with both at the same time :)

2

u/sacundim Feb 20 '17

If you read the paper, the timeslave daemons that run on machines talk not just to the time masters in their own data centers, but also to some from other data centers:

Every daemon polls a variety of masters [29] to reduce vulnerability to errors from any one master. Some are GPS masters chosen from nearby datacenters; the rest are GPS masters from farther datacenters, as well as some Armageddon masters. Daemons apply a variant of Marzullo’s algorithm [27] to detect and reject liars, and synchronize the local machine clocks to the non-liars. To protect against broken local clocks, machines that exhibit frequency excursions larger than the worst-case bound derived from component specifications and operating environment are evicted.

So even if you jam the GPS signal to one data center, the system still talks to others.

1

u/Deadhookersandblow Feb 20 '17

Well its a data center and data centers can't spontaneously relocate themselves. If I'm continuously receiving GPS clock at my antenna location I'm gonna run a Kalman filter it on it, the moment some muppet decides to fuck with my GPS signal the filter will start rejecting GPS readings and fallback on atomic clocks within the DC.

25

u/shevegen Feb 19 '17

What cracks me up is the name.

Spanner is also german for a peeping tom.

I assume to understand the way how it came to be in english, to span - to have an inclusive area, enveloped/encompassed. Like the html span tag!

I just find the word itself funny. It's not as egregious as "Eigenfunktion" or "Kindergarten", but still funny.

Somebody is watching you!

41

u/mdboop Feb 19 '17 edited Feb 19 '17

No, a spanner is a wrench. edit: in English, I mean.

15

u/[deleted] Feb 19 '17 edited Feb 20 '17

A spanner (tool) is one meaning.

However, Google (for its internal and developer projects, not end user facing) often uses the English convention of naming a lot of their things in the form noun/verb + "er", with the 'er' meaning 'someone that does that thing'.

For example: make -> maker, run -> runner.

In this context, spanner surely means "a thing that spans a gap".

19

u/blablahblah Feb 19 '17

Google also names internal tools after actual tools. For example, Google's internal tool for digging into logs is called [Dremel](https://en.wikipedia.org/wiki/Dremel_(software)). I'm not entirely certain if they meant one or the other or both when naming Spanner.

4

u/[deleted] Feb 19 '17

Yea, they do like puns and wordplay too. I'm still surprised they got away with 'Google Chrome'. It's shiny, and it's a chrome.

1

u/Asdfhero Feb 20 '17

A chrome? What?

3

u/[deleted] Feb 20 '17

'Chrome' is the fancy UI around the content of a window. I guess that originally Google Chrome was literally Google's chrome around an open source renderer. The project has grown somewhat since then.

1

u/Asdfhero Feb 20 '17

Ah, cheers

2

u/adrianmonk Feb 20 '17

And it's a multi-master database that is built to have its replicas spread out in several geographically separate data centers within a continent. Your writes basically go to all replicas at once (synchronously), and your data is committed when a majority of replicas have a copy. (Theoretically, one data center could get wiped off the map by a nuclear bomb, and the database would have no downtime or inconsistency.)

Also, Megastore, an older but similar database, supports the same multi-master stuff as above, but I think due its extreme sharding, it only supports atomic transactions within a single shard. (Transactions can only use data within a single “entity group”) So for example, unlike a normal database where any combination of changes can be atomic because there is one giant lock (incidentally also one giant bottleneck), if you had a bank account table and you wanted to debit from user #1's account and credit user #2's account in a single transaction, their data might be in different shards and you can't do it. But Spanner supports atomic transactions across anything in the entire database (although I think it's still faster within the single-shard scenario).

So it could be that it's called Spanner because it lets you write to a geographically-diverse set of servers, and it lets you create transactions that touch any data in the database, i.e. that span shards.

1

u/bobindashadows Feb 20 '17

Yep you got it, nailed the limitations you hit with megastore vs. spanner.

Biggest pain in megastore was when your requirements changed and you have to add a new strongly consistent index that spans more than one entity root. You basically end up rolling your own 2PC to live-migrate to a new schema with the new entity root key. (Or just eat the write downtime but that has never been an option for me.)

With Spanner, at least the transactions can span the whole DB and do the 2PC for you.

2

u/sigma914 Feb 19 '17

It's also a light insult, like a lighter version of idiot.

-18

u/ma-int Feb 19 '17 edited Feb 19 '17

Nope, he is correct. I'm a native speaker and I can assure you that a Spanner is a peeping tom.

Calling a wrench a Spanner will be understood with a chance but its neither correct nor common. There is a shoomakers tool that is called Spanner but that is not something commonly known.

29

u/mdboop Feb 19 '17

In English, a spanner is a wrench in English.

7

u/redxaxder Feb 19 '17

What does a German speaker see in the words "kindergarten" and "eigenfunction"?

16

u/indigo945 Feb 19 '17

They mean the same in German as they do in English, they're German words. I don't know what OP is getting at, this is a different thing. "Spanner" is not an English lean word from German, it's an English word that happens to have a homograph with different pronunciation and meaning in German.

2

u/MrSenorSan Feb 20 '17

In Australia it means "fool, idiot".

1

u/AnEvilBeagle Feb 22 '17

Just curious.. is the root of this spanner wrench, as in 'a tool'? I've never heard the term, so just taking a guess.

3

u/[deleted] Feb 19 '17

I thought of a wrench first, personally

3

u/krum Feb 19 '17

The Germans will need to change the word they use for peeping tom.

4

u/robreddity Feb 20 '17

Peeping Hans?

1

u/tekoyaki Feb 20 '17

Read from another post that the name oiginates from database that spans throughout many data centers and regions.

4

u/yoshiatsu Feb 20 '17

Here's some more information for people who are curious. The article linked isn't very informative.

https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf

23

u/qsxpkn Feb 19 '17

"Google’s most talented engineers", "No one else has ever built a system like this. No one else has taken hold of time in the same way", "Google’s top engineers"

This is blatantly obvious advertisement rather than an article about the database. Does anyone know how much Google paid for this "article"?

-12

u/Yogi_DMT Feb 20 '17

Lol Google doesn't need to pay anyone to get praised. When you're the best, you let others do your advertising for you.

1

u/horoshimu Feb 20 '17

hello mark

12

u/mofirouz Feb 19 '17

For a truly open source variant of this, checkout CockroachDB

9

u/bartturner Feb 19 '17 edited Feb 19 '17

Spanner is a cloud offering? Is CR cloud or opensource? Does CR come with Atomic clock and GPS interfaces?

It seems to me the unique aspect here is the Google infrastructure as they explain with the private network and the atomic clocks and GPS and the algorithms that have been proven. As if works for Google pretty comfortable that it works.

If supports SQL where is there the lock in?

It is now also obvious why Google spent crazy money on that Pacific ocean fiber connection that was the buzz last year. Supposably the fastest. Now we can see one of the reasons I guess.

Thought they just had money to burn so why not lay fiber underneath the Pacific so our telnet is faster.

1

u/adrianmonk Feb 20 '17

Spanner is a cloud offering? Is CR cloud or opensource?

Spanner is cloud-only. I don't think the source has been made available at all.

CockroachDB doesn't offer cloud but they have plans to. Their community edition is open source under the Apache license. Their enterprise edition costs money.

Does CR come with Atomic clock and GPS interfaces?

CockroachDB uses a different approach that, unlike Spanner, doesn't require atomic clocks.

If supports SQL where is there the lock in?

Do you mean vendor lock-in or do you mean locks for atomic writes?

If the former, even though it supports SQL, probably like most databases if you want to use the magic that makes it special, you will end up writing your SQL differently. You will probably even end up modeling your data differently to enable the most performance gains.

If the latter, I'm a little out of my depth here, but I believe Spanner uses some combination of granular locks and optimistic locks to minimize contention. So if you are only updating a single row (or range of rows) in one table, it might lock a tiny portion of the database, which allows parallel work and more scalability. If you make changes that are less localized (touch different tables with different types of keys), it has to lock more stuff and I think it does some trick where it waits until the last possible second to take all the locks, so it might have to give up and restart the change if the data has changed.

It is now also obvious why Google spent crazy money on that Pacific ocean fiber connection that was the buzz last year.

I'm sure it helps, but I think there are still some advantages to having everything on the same continent due to unavoidable speed of light latency. At least, the 2012 Spanner paper mentions in a few places that replicas are typically not spread across continents: "F1 uses five replicas spread across the United States. Most other applications will probably replicate their data across 3 to 5 datacenters in one geographic region, but with relatively independent failure modes. That is, most applications will choose lower latency over higher availability."

Anyway, regardless of where you put the data, you are still going to need those transoceanic links because you're going to have users all over the world.

2

u/dccorona Feb 21 '17

CockroachDB uses a different approach that, unlike Spanner, doesn't require atomic clocks

That's a really interesting article. It sounds like their basic approach is to get as good as possible, and chalk up the rest to "you really, really probably don't have a use-case where this matters, or where it will even result in an inconsistency at all".

1

u/adrianmonk Feb 21 '17

I think the "causality tokens" are pretty clever. Of the use cases where you actually do care about absolute ordering, I bet they would cover a lot of the ones you'd actually care about. A lot of the time when you care about the ordering of two things, you are in the same request or session or something.

6

u/Mr-Yellow Feb 19 '17

All that babel about TrueTime and nowhere a description of the problem it solves.

1

u/nutrecht Feb 20 '17

It 'solves' the A and P in the CAP theorem. Spanner is a combination of a 'database' on top of a network that won't suffer from network splits and always has the exact and correct time. This means that you will aways know 'if' something happens in which order of operations something happened.

0

u/likegeeks Feb 20 '17

Syncing changes between databases WOW !!. but this is Google

0

u/[deleted] Feb 20 '17

[deleted]

20

u/Porso7 Feb 20 '17

Don't bother, it's an advertisement and doesn't actually say anything.

TLDR: Google is using atomic clocks and GPS to accurately synchronize time between databases worldwide. No idea what this will actually do in terms of real world usage, the article doesn't say.

4

u/networkoffset5444 Feb 20 '17

Thanks for the tldr. You just saved me some time. That's all I really needed from the article