7 ms·

Spanner, TrueTime and the CAP Theorem [pdf]

125 points by wwarner 9y ago

manigandham 9y ago
To head off the usual comments, Spanner (as quoted in the source) is a CP system and this is a rather disingenuous and unfortunate marketing spin by Eric Brewer that conflates availability of the network infrastructure with availability of a distributed quorum in a network partition. How reliable your network is has nothing to do with what happens when it inevitably does have a failure.
- deleted 9y ago
  [deleted]
- elvinyung 9y ago
  I remember having an argument with a distributed systems professor about whether banks were AP or CP. He said that they were strongly consistent because they would always have redundant network links to prevent partitions, and refused to consider the hypothetical case of a network partition. That was the day I dropped the course.
  - eternalban 9y ago
    Banks are logically CP. ("Your deposit will be available by the next business day.") Technological advances are however, per Professor, reducing (or entirely eliminating) service availability gaps. But should the branch office partition from the main office, then the system will revert to strict CP.
    - manigandham 9y ago
      That's AP. It's better customer service to be available so you always get an answer, it's just out of date. Deposit being available next day means eventually your balance will be made consistent after all the settlement occurs. Banking is an AP, eventually consistent, event-sourced system. All transactions are logged as pending and then processed later. If something is invalid, then it gets denied or reversed as another transaction. This is why you see deposits held, limits on ATM withdrawals, and charges on credit cards that take days to show up. Some systems do the processing constantly so it seems instant but its never "real-time". In fact, Eric Brewer himself talks about this concept, usually called BASE as an alternative to ACID: https://www.infoq.com/presentations/NoSQL-History https://www.infoq.com/presentations/NoSQL-History http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on-why-banks-are-base-not-acid-availability.html http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on...
- wwarner 9y ago
  For me, the paper was of interest because of the ways that Spanner reduces the surface area of faults through controlling the networking and the application of a global clock.
- thesandlord 9y ago
  (I work for Google Cloud) Half this paper covers what happens during a network partition, the other part talks about the historic data backing up the claims that they are super rare. There is even a whole section called "What happens during a Partition". On the first page: > The purist answer is “no” because partitions can happen and in fact have happened at Google, and during (some) partitions, Spanner chooses C and forfeits A. It is technically a CP system. We explore the impact of partitions below. And the conclusion states as a fact that outages will occur: > Spanner reasonably claims to be an “effectively CA” system despite operating over a wide area, as it is always consistent and achieves greater than 5 9s availability. As with Chubby, this combination is possible in practice if you control the whole network, which is rare over the wide area. Even then, it requires significant redundancy of network paths, architectural planning to manage correlated failures, and very careful operations, especially for upgrades. Even then outages will occur, in which case Spanner chooses consistency over availability.
  - zzzcpan 9y ago
    You can think of this a bit differently, that the network is asynchronous and is effectively always partitioned. This helps to highlight the trade offs between CP and AP, since it becomes obvious that you need to wait to get consistency and if you don't wait you can get it only eventually. Also becomes obvious that CA systems cannot actually exist, and 5 9s availability has absolutely nothing to do with any of that.
    - muxator 9y ago
      Fair point. This is a very clever way of looking at it, thanks.
    - theptip 9y ago
      This is a much more sophisticated way of carving up the problem -- for those interested in reading more, Kleppmann has discussed this extensively: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html https://martin.kleppmann.com/2015/05/11/please-stop-calling-...
  - 9y ago
- vikiomega9 9y ago
  But isn't network reliability a necessary condition for distributed consensus?
  - manigandham 9y ago
    No. A query takes place and the network is either working or not at that instant, and the system reacts accordingly. CP means it might not be available, but if it is then you'll get the latest data. AP means you'll always get an answer, but it might not be the latest data. You can make your network reliable in the sense that better infrastructure lowers failures, but nothing is 100% so CAP is about what happens in the inevitable failure scenario. Whether you have 0 failures or 1 per hour doesn't affect CAP at all and has nothing to do with magically making something CA.
    - vikiomega9 9y ago
      My comment is that you cannot have CP without a reliable network, an unreliable network is equivalent to a partition event. This might be a naive assertion, but how else do you have a partition event? I'm confused about what you were trying to say. The post talks about being effectively CA which is what I understood about spanner when I came across the system.
      - manigandham 9y ago
        The network is either working or not at any given instant. During that instant, CAP determines how the system responds. Reliability is the graph of many instants over some period of time, so 50% reliability over a day means it's not working roughly half of the instants measured for 24 hours. So it doesn't whether your network is 1%, 99%, or 100% reliable because CAP is saying that when a partition exists, this is how the system works. If the network is 100% reliable, then sure, partitions never happen and you can be CA, but since that is not possible and partitions will always happen eventually, you have to be either CP or AP - and Spanner chooses CP, which is the only accurate description.
- solipsism 9y ago
  Pardon the eyeroll, but that's incredibly pedantic. Brewer is not being disingenuous here, he's being forthright. Spanner is a product. "Effectively CA" is what customers care about. The fact that it's "technically not CA" is only important academically, and for the very small subset of customers for whom even the very tiny chance of loss of availability is problematic.
  - manigandham 9y ago
    Accuracy is not pedantic, especially when claiming something which is impossible. If customers don't care about availability than they also don't care about the difference between CP or CA, so why not just stick to CP which is real? Perhaps disingenuous was too harsh, but my issue is that it took plenty of time for CAP to be well-understood and this marketing material does more harm than good by creating confusion. There are better ways of product marketing that don't try to fudge descriptions with technicalities.
  - theptip 9y ago
    The point that the GP is making is there is no such thing as "effectively CA". CA is a specific academic term with a specific meaning; there's no reason to introduce it into the conversation if you're not going to follow that meaning. By all means call this system a "ultra-high availability strongly consistent datastore", but it's still not CA. (It's all the more disappointing that it's Brewer himself, the original author of the CAP theorem, that's engaging in this hand-waving).
jacksmith21006 9y ago
Love this paper.
shalabhc 9y ago
> Spanner’s external consistency invariant is that for any two transactions, T1 and T2 (even if on opposite sides of the globe):if T2 starts to commit after T1 finishes committing, then the timestamp for T2 is greater than the timestamp for T1. This is impressive. But what exact point in time is when 'T2 starts to commit'? Is it when the user pushes the submit button on their device? When the request reaches a Google server? When it reaches a Spanner server within Google? The point I'm getting at is given the uncertain 'delay' between the time the user interacts with the system and the 'time of commit', is time based linearizability a useful property? Could it be made simpler with actor based linearizability? Or revision based?
- mgraczyk 9y ago
  The way the timestamp is chosen depends on properties of the transaction. In the worst cases, servers must wait until the true time interval has passed an older commit before assigning a timestamp.
- wwarner 9y ago
  I agree that this is the best line in the paper. I interpret it to mean that while a second transaction is in progress, if a commit log comes in it's an extremely cheap operation to check the timestamp and ignore it.
- pishpash 9y ago
  There is no global time and no simultaneity. What is this notion that T2 is greater than T1 when they are separated by some significant distance? The sentence doesn't even make sense.
  - jasonwatkinspdx 9y ago
    We synthesize idealized ephemeris time via a cohort of atomic clocks. Google's TrueTime tracks this along with the local uncertainty. This allows Spanner to explicitly wait out uncertainty windows, establishing a single externally consistent order to all possible observers, even in the presence of hidden communication channels. This is the whole point of the system, and what the article covers. What you're saying about time isn't even exactly true in the general case where we need account for relativity. While observers of clocks in different locations may not agree on clocks alone, they will agree on the total spacetime interval. In any case, accounting for relativity is only necessary in high precision radio frequency systems operating between ground and orbit like GPS. And even then we can still track the frequency and phase offsets of the oscillators in real time and establish their relationship to idealized ephemeris time. So yes, the sentences in the article DO make sense. EDIT: at least the ones concerning time and consistent orders due. The words about effectively CA are ... not great.
bogomipz 9y ago
This was an interesting read. Can anyone recommend any other Spanner literature that dives more into the design and data model?
- rajathagasthya 9y ago
  The original paper: http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/39966.pdf http://static.googleusercontent.com/media/research.google.co... Acolyer's condensed blog post: https://blog.acolyer.org/2015/01/08/spanner-googles-globally-distributed-database/ https://blog.acolyer.org/2015/01/08/spanner-googles-globally...
  - bogomipz 9y ago
    This is great, thanks.
remcob 9y ago
I always wondered how distributed systems like Spanner/TrueTime would scale when we build a datacenter on Mars. Mars-Earth round-trip-times are in the order of minutes. We are lucky that earthbound round-trip-times are nearly imperceptibly short. Interplanetary internet is going to pose interesting challenges.
chisleu 9y ago
The author doesn't seem to think about systems with query-level tuning of CAP systems. Cassandra and many others offer the ability to time how much consistency you want in order to increase availability or deal with partitions. It is likely Spanner is doing this behind the curtain.
- manigandham 9y ago
  The author originally came up with the CAP theorem and Spanner is a CP system. It doesn't change consistency settings, it just relies on Google's private networking to maintain a very high level of network reliability, so they're claiming "CA" by saying P almost never happens.
  - chisleu 9y ago
    I was impressed with BigQuery. Everything from the interface, to the UDF support, to the high quality libraries. CloudSpanner sure reads like magic beans intended to solve a problem people don't have anymore.
- ztorkelson 9y ago
  I'm of the opinion that while those sorts of knobs sound good on the surface, they're kind of missing the point. The benefit of having strong consistency is that one doesn't have to think about the many ways concurrent transactions might interleave and conflict. (At least insofar as it comes to correctness.) Allowing weaker consistency is in some ways similar to the varying transaction isolation levels of other relational databases. Most practitioners won't fully consider or appreciate the anomalies that can arise when consistency is relaxed, leading to bugs. Those practitioners that do understand the anomalies can easily get bogged down in the combinatorial complexity of the problem. Spanner is compelling in large part because it simplifies all of this for the average developer. It provides two consistency models: snapshot (read-only, point-in-time), and serializable (read-write, up-to-date). And it does so in a way that is both highly available (but not CA, despite the unfortunate wording in this paper) and with predictable performance. This is really valuable: it reduces the cognitive burden which developers might otherwise have, and can serve to increases software reliability.
readams 9y ago
Brewers "CAP Twelve Years Later" paper was to me very unsatisfying since it basically advocated that systems should be CA but then have a special mode where you can recover from partitions. The problem is that having code that can successfully recover from a partition when consistency is gone ends up looking exactly like the code that you'd write if you're on a nosql database except it won't be well-tested. In this paper he's toeing the Spanner line which takes the more traditional CP route, but tries to make partitions rare and achieve high availability. But I remain confused why Brewer had adopted this confusing stance on his own CAP theorem what causes a lot of people to think it's not real or that it's been solved, which ignores the real tradeoffs. Spanner doesn't "solve" CAP of course. The "12 years later" paper though was really a disservice.

125 points by wwarner 9y ago

To head off the usual comments, Spanner (as quoted in the source) is a CP system and this is a rather disingenuous and unfortunate marketing spin by Eric Brewer that conflates availability of the network infrastructure with availability of a distributed quorum in a network partition. How reliable your network is has nothing to do with what happens when it inevitably does have a failure.

deleted 9y ago
[deleted]
elvinyung 9y ago
I remember having an argument with a distributed systems professor about whether banks were AP or CP. He said that they were strongly consistent because they would always have redundant network links to prevent partitions, and refused to consider the hypothetical case of a network partition. That was the day I dropped the course.
- eternalban 9y ago
  Banks are logically CP. ("Your deposit will be available by the next business day.") Technological advances are however, per Professor, reducing (or entirely eliminating) service availability gaps. But should the branch office partition from the main office, then the system will revert to strict CP.
  - manigandham 9y ago
    That's AP. It's better customer service to be available so you always get an answer, it's just out of date. Deposit being available next day means eventually your balance will be made consistent after all the settlement occurs. Banking is an AP, eventually consistent, event-sourced system. All transactions are logged as pending and then processed later. If something is invalid, then it gets denied or reversed as another transaction. This is why you see deposits held, limits on ATM withdrawals, and charges on credit cards that take days to show up. Some systems do the processing constantly so it seems instant but its never "real-time". In fact, Eric Brewer himself talks about this concept, usually called BASE as an alternative to ACID: https://www.infoq.com/presentations/NoSQL-History https://www.infoq.com/presentations/NoSQL-History http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on-why-banks-are-base-not-acid-availability.html http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on...
wwarner 9y ago
For me, the paper was of interest because of the ways that Spanner reduces the surface area of faults through controlling the networking and the application of a global clock.
thesandlord 9y ago
(I work for Google Cloud) Half this paper covers what happens during a network partition, the other part talks about the historic data backing up the claims that they are super rare. There is even a whole section called "What happens during a Partition". On the first page: > The purist answer is “no” because partitions can happen and in fact have happened at Google, and during (some) partitions, Spanner chooses C and forfeits A. It is technically a CP system. We explore the impact of partitions below. And the conclusion states as a fact that outages will occur: > Spanner reasonably claims to be an “effectively CA” system despite operating over a wide area, as it is always consistent and achieves greater than 5 9s availability. As with Chubby, this combination is possible in practice if you control the whole network, which is rare over the wide area. Even then, it requires significant redundancy of network paths, architectural planning to manage correlated failures, and very careful operations, especially for upgrades. Even then outages will occur, in which case Spanner chooses consistency over availability.
- zzzcpan 9y ago
  You can think of this a bit differently, that the network is asynchronous and is effectively always partitioned. This helps to highlight the trade offs between CP and AP, since it becomes obvious that you need to wait to get consistency and if you don't wait you can get it only eventually. Also becomes obvious that CA systems cannot actually exist, and 5 9s availability has absolutely nothing to do with any of that.
  - muxator 9y ago
    Fair point. This is a very clever way of looking at it, thanks.
  - theptip 9y ago
    This is a much more sophisticated way of carving up the problem -- for those interested in reading more, Kleppmann has discussed this extensively: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html https://martin.kleppmann.com/2015/05/11/please-stop-calling-...
- 9y ago
vikiomega9 9y ago
But isn't network reliability a necessary condition for distributed consensus?
- manigandham 9y ago
  No. A query takes place and the network is either working or not at that instant, and the system reacts accordingly. CP means it might not be available, but if it is then you'll get the latest data. AP means you'll always get an answer, but it might not be the latest data. You can make your network reliable in the sense that better infrastructure lowers failures, but nothing is 100% so CAP is about what happens in the inevitable failure scenario. Whether you have 0 failures or 1 per hour doesn't affect CAP at all and has nothing to do with magically making something CA.
  - vikiomega9 9y ago
    My comment is that you cannot have CP without a reliable network, an unreliable network is equivalent to a partition event. This might be a naive assertion, but how else do you have a partition event? I'm confused about what you were trying to say. The post talks about being effectively CA which is what I understood about spanner when I came across the system.
    - manigandham 9y ago
      The network is either working or not at any given instant. During that instant, CAP determines how the system responds. Reliability is the graph of many instants over some period of time, so 50% reliability over a day means it's not working roughly half of the instants measured for 24 hours. So it doesn't whether your network is 1%, 99%, or 100% reliable because CAP is saying that when a partition exists, this is how the system works. If the network is 100% reliable, then sure, partitions never happen and you can be CA, but since that is not possible and partitions will always happen eventually, you have to be either CP or AP - and Spanner chooses CP, which is the only accurate description.
solipsism 9y ago
Pardon the eyeroll, but that's incredibly pedantic. Brewer is not being disingenuous here, he's being forthright. Spanner is a product. "Effectively CA" is what customers care about. The fact that it's "technically not CA" is only important academically, and for the very small subset of customers for whom even the very tiny chance of loss of availability is problematic.
- manigandham 9y ago
  Accuracy is not pedantic, especially when claiming something which is impossible. If customers don't care about availability than they also don't care about the difference between CP or CA, so why not just stick to CP which is real? Perhaps disingenuous was too harsh, but my issue is that it took plenty of time for CAP to be well-understood and this marketing material does more harm than good by creating confusion. There are better ways of product marketing that don't try to fudge descriptions with technicalities.
- theptip 9y ago
  The point that the GP is making is there is no such thing as "effectively CA". CA is a specific academic term with a specific meaning; there's no reason to introduce it into the conversation if you're not going to follow that meaning. By all means call this system a "ultra-high availability strongly consistent datastore", but it's still not CA. (It's all the more disappointing that it's Brewer himself, the original author of the CAP theorem, that's engaging in this hand-waving).

jacksmith21006 9y ago

Love this paper.

shalabhc 9y ago

> Spanner’s external consistency invariant is that for any two transactions, T1 and T2 (even if on opposite sides of the globe):if T2 starts to commit after T1 finishes committing, then the timestamp for T2 is greater than the timestamp for T1. This is impressive. But what exact point in time is when 'T2 starts to commit'? Is it when the user pushes the submit button on their device? When the request reaches a Google server? When it reaches a Spanner server within Google? The point I'm getting at is given the uncertain 'delay' between the time the user interacts with the system and the 'time of commit', is time based linearizability a useful property? Could it be made simpler with actor based linearizability? Or revision based?

mgraczyk 9y ago
The way the timestamp is chosen depends on properties of the transaction. In the worst cases, servers must wait until the true time interval has passed an older commit before assigning a timestamp.
wwarner 9y ago
I agree that this is the best line in the paper. I interpret it to mean that while a second transaction is in progress, if a commit log comes in it's an extremely cheap operation to check the timestamp and ignore it.
pishpash 9y ago
There is no global time and no simultaneity. What is this notion that T2 is greater than T1 when they are separated by some significant distance? The sentence doesn't even make sense.
- jasonwatkinspdx 9y ago
  We synthesize idealized ephemeris time via a cohort of atomic clocks. Google's TrueTime tracks this along with the local uncertainty. This allows Spanner to explicitly wait out uncertainty windows, establishing a single externally consistent order to all possible observers, even in the presence of hidden communication channels. This is the whole point of the system, and what the article covers. What you're saying about time isn't even exactly true in the general case where we need account for relativity. While observers of clocks in different locations may not agree on clocks alone, they will agree on the total spacetime interval. In any case, accounting for relativity is only necessary in high precision radio frequency systems operating between ground and orbit like GPS. And even then we can still track the frequency and phase offsets of the oscillators in real time and establish their relationship to idealized ephemeris time. So yes, the sentences in the article DO make sense. EDIT: at least the ones concerning time and consistent orders due. The words about effectively CA are ... not great.

bogomipz 9y ago

This was an interesting read. Can anyone recommend any other Spanner literature that dives more into the design and data model?

rajathagasthya 9y ago
The original paper: http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/39966.pdf http://static.googleusercontent.com/media/research.google.co... Acolyer's condensed blog post: https://blog.acolyer.org/2015/01/08/spanner-googles-globally-distributed-database/ https://blog.acolyer.org/2015/01/08/spanner-googles-globally...
- bogomipz 9y ago
  This is great, thanks.

remcob 9y ago

I always wondered how distributed systems like Spanner/TrueTime would scale when we build a datacenter on Mars. Mars-Earth round-trip-times are in the order of minutes. We are lucky that earthbound round-trip-times are nearly imperceptibly short. Interplanetary internet is going to pose interesting challenges.

chisleu 9y ago

The author doesn't seem to think about systems with query-level tuning of CAP systems. Cassandra and many others offer the ability to time how much consistency you want in order to increase availability or deal with partitions. It is likely Spanner is doing this behind the curtain.

manigandham 9y ago
The author originally came up with the CAP theorem and Spanner is a CP system. It doesn't change consistency settings, it just relies on Google's private networking to maintain a very high level of network reliability, so they're claiming "CA" by saying P almost never happens.
- chisleu 9y ago
  I was impressed with BigQuery. Everything from the interface, to the UDF support, to the high quality libraries. CloudSpanner sure reads like magic beans intended to solve a problem people don't have anymore.
ztorkelson 9y ago
I'm of the opinion that while those sorts of knobs sound good on the surface, they're kind of missing the point. The benefit of having strong consistency is that one doesn't have to think about the many ways concurrent transactions might interleave and conflict. (At least insofar as it comes to correctness.) Allowing weaker consistency is in some ways similar to the varying transaction isolation levels of other relational databases. Most practitioners won't fully consider or appreciate the anomalies that can arise when consistency is relaxed, leading to bugs. Those practitioners that do understand the anomalies can easily get bogged down in the combinatorial complexity of the problem. Spanner is compelling in large part because it simplifies all of this for the average developer. It provides two consistency models: snapshot (read-only, point-in-time), and serializable (read-write, up-to-date). And it does so in a way that is both highly available (but not CA, despite the unfortunate wording in this paper) and with predictable performance. This is really valuable: it reduces the cognitive burden which developers might otherwise have, and can serve to increases software reliability.

readams 9y ago

Brewers "CAP Twelve Years Later" paper was to me very unsatisfying since it basically advocated that systems should be CA but then have a special mode where you can recover from partitions. The problem is that having code that can successfully recover from a partition when consistency is gone ends up looking exactly like the code that you'd write if you're on a nosql database except it won't be well-tested. In this paper he's toeing the Spanner line which takes the more traditional CP route, but tries to make partitions rare and achieve high availability. But I remain confused why Brewer had adopted this confusing stance on his own CAP theorem what causes a lot of people to think it's not real or that it's been solved, which ignores the real tradeoffs. Spanner doesn't "solve" CAP of course. The "12 years later" paper though was really a disservice.