Friday, September 21, 2018

NewSQL database systems are failing to guarantee consistency, and I blame Spanner

The CAP theorem famously states that it is impossible to guarantee both consistency and availability in the event of a network partition. Since network partitions are always theoretically possible in a scalable, distributed system, the architects of modern scalable database systems fractured into two camps: those that prioritized availability (the NoSQL camp) and those that prioritized consistency (the NewSQL camp). For a while, the NoSQL camp was clearly the more dominant of the two --- in an “always-on” world, downtime is unacceptable, and developers were forced into handling the reduced consistency levels of scalable NoSQL systems. [Side note: NoSQL is a broad umbrella that contains many different systems with different features and innovations. When this post uses the term “NoSQL”, we are referring to the subset of the umbrella that is known for building scalable systems that prioritize availability over consistency, such as Cassandra, DynamoDB (default settings), Voldemort, CouchDB, Riak, and multi-region deployments of Azure CosmosDB.]
Over the past decade, application developers have discovered that it is extremely difficult to build bug-free applications over database systems that do not guarantee consistency. This has led to a surprising shift in momentum, with many of the more recently released systems claiming to guarantee consistency (and be CP from CAP). Included in this list of newer systems are: Spanner (and its Cloud Spanner counterpart), FaunaDB, CockroachDB, and YugaByte. In this post, we will look more deeply into the consistency claims of these four systems (along with similar systems) and note that while some do indeed guarantee consistency, way too many of them fail to completely guarantee consistency. We will trace the failure to guarantee consistency to a controversial design decision made by Spanner that has been tragically and imperfectly emulated in other systems.

What is consistency anyway?

Consistency, also known as “atomic consistency” or “linearizability”, guarantees that once a write completes, all future reads will reflect that value of the write. For example, let’s say that we have a variable called X, whose value is currently 4. If we run the following code:
X = 10;
Y = X + 8;
In a consistent system, there is only one possible value for Y after running this code (assuming the second statement is run after the first statement completes): 18. Everybody who has completed an “Introduction to Programming” course understands how this works, and relies on this guarantee when writing code.
In a system that does not guarantee consistency, the value of Y after running this code is also probably 18. But there’s a chance it might be 12 (since the original value of X was 4). Even if the system returns an explicit message: “I have completed the X = 10 statement”, it is nonetheless still a possibility that the subsequent read of X will reflect the old value (4) and Y will end up as 12. Consequently, the application developer has to be aware of the non-zero possibility that Y is not 18, and must deal with all possible values of Y in subsequent code. This is MUCH more complicated, and beyond the intellectual capabilities of a non-trivial subset of application developers.
[Side note: Another name for "consistency" is "strong consistency". This alternate name was coined in order to distinguish the full consistency guarantee from weaker consistency levels that also use the word "consistency" in their name (despite not providing the complete consistency guarantee). Indeed, some of these weaker consistency levels, such as "causal consistency", "session consistency", and "bounded staleness consistency" provide useful guarantees that somewhat reduce complexity for application developers. Nonetheless, the best way to avoid the existence of corner case bugs in an application is to build it on top of a system that guarantees complete, strong consistency.]

Why give up on consistency?

Consistency is a basic staple, a guarantee that is extremely hard to live without. So why do most NoSQL systems fail to guarantee consistency? They blame the CAP theorem. (For example, the Amazon Dynamo paper, which inspired many widely used NoSQL systems, such as Cassandra, DynamoDB, and Riak, mention the availability vs. consistency tradeoff in the first paragraph of the section that discussed their “Design Considerations”, which lead to their famous “eventually consistent” architecture.) It is very hard, but not impossible, to build applications over systems that do not guarantee consistency. But the CAP theorem says that it is impossible for a system that guarantees consistency to guarantee 100% availability in the presence of a network partition. So if you can only choose one, it makes sense to choose availability. As we said above, once the system fails to guarantee consistency,  developing applications on top of it without ugly corner case bugs is extremely challenging, and generally requires highly-skilled application developers that are able to handle the intellectual rigors of such development environments. Nonetheless, such skilled developers do exist, and this is the only way to avoid the impossibility proof from the CAP theorem of 100% availability.
The reasoning of the previous paragraph, although perhaps well-thought out and convincing, is fundamentally flawed. The CAP theorem lives in a theoretical world where there is such a thing as 100% availability. In the real world, there is no such thing as 100% availability. Highly available systems are defined in terms of ‘9s’. Are you 99.9% available? Or 99.99% available? The more 9s, the better. Availability is fundamentally a pursuit in imperfection. No system can guarantee availability.
This fact has significant ramifications when considering the availability vs. consistency tradeoff that was purported by the CAP theorem. It is not the case that if we guarantee consistency, we have to give up the guarantee of availability. We never had a guarantee of availability in the first place! Rather, guaranteeing consistency causes a reduction to our already imperfect availability.
Therefore: the question becomes: how much availability is lost when we guarantee consistency? In practice, the answer is very little. Systems that guarantee consistency only experience a necessary reduction in availability in the event of a network partition. As networks become more redundant, partitions become an increasingly rare event. And even if there is a partition, it is still possible for the majority partition to be available. Only the minority partition must become unavailable. Therefore, for the reduction in availability to be perceived, there must be both a network partition, and also clients that are able to communicate with the nodes in the minority partition (and not the majority partition). This combination of events is typically rarer than other causes of system unavailability. Consequently, the real world impact of guaranteeing consistency on availability is often negligible. It is very possible to have a system that guarantees consistency and achieves high availability at the same time.
[Side note: I have written extensively about these issues with the CAP theorem. I believe the PACELC theorem is better able to summarize consistency tradeoffs in distributed systems.]

The glorious return of consistent NewSQL systems

The argument above actually results in 3 distinct reasons for modern systems to be CP from CAP, instead of AP (i.e. choose consistency over availability):
(1)    Systems that fail to guarantee consistency result in complex, expensive, and often buggy application code.
(2)    The reduction of availability that is caused by the guarantee of consistency is minute, and hardly noticeable for many deployments.
(3)    The CAP theorem is fundamentally asymmetrical. CP systems can guarantee consistency. AP systems do not guarantee availability (no system can guarantee 100% availability). Thus only one side of the CAP theorem opens the door for any useful guarantees.
I believe that the above three points is what has caused the amazing renaissance of distributed, transactional database systems --- many of which have become commercially available in the past few years ---  that choose to be CP from CAP instead of AP. There is still certainly a place for AP systems, and their associated NoSQL implementations. But for most developers, building on top of a CP system is a safer bet. 
However, when I say that CP systems are the safer bet, I intend to refer to CP systems that actually guarantee consistency. Unfortunately, way too many of these modern NewSQL systems fail to guarantee consistency, despite their claims to the contrary. And once the guarantee is removed, the corner case bugs, complexity, and costs return.

Spanner is the source of the problem

I have discussed in previous posts that there are many ways to guarantee consistency in distributed systems. The most popular mechanism, which guarantees consistency at minimal cost to availability, is to use the Paxos or Raft consensus protocols to enforce consistency across multiple replicas of the data. At a simplified level, these protocols work via a majority voting mechanism. Any change to the data requires a majority of replicas to agree to the change. This allows the minority of replicas to be down or unavailable and the system can nonetheless continue to read or write data.
Most NewSQL systems use consensus protocols to enforce consistency. However, they differ in a significant way in how they use these protocols. I divide NewSQL systems into two categories along this dimension: The first category, as embodied in systems such as Calvin (which came out of my research group) and FaunaDB, uses a single, global consensus protocol per database. Every transaction participates in the same global protocol. The second category, as embodied in systems such as Spanner, CockroachDB, and YugaByte, partitions the data into ‘shards’, and applies a separate consensus protocol per shard.
The main downside of the first category is scalability. A server can process a fixed number of messages per second. If every transaction in the system participates in the same consensus protocol, the same set of servers vote on every transaction. Since voting requires communication, the number of votes per second is limited by the number of messages each server can handle. This limits the total amount of transactions per second that the system can handle.
Calvin and FaunaDB get around this downside via batching. Rather than voting on each transaction individually, they vote on batches of transactions. Each server batches all transactions that it receives over a fixed time period (e.g., 10 ms), and then initiates a vote on that entire batch at once. With 10ms batches, Calvin was able to achieve a throughput of over 500,000 transactions per second. For comparison, Amazon.com and NASDAQ likely process no more than 10,000 orders/trades per second even during peak workloads [Update: there has been some discussion about these numbers from my readers. The number for NASDAQ might be closer to 100,000 orders per second. I have not seen anybody dispute the 10,000 orders per second number from Amazon.com, but readers have pointed out that they issue more than 10,000 writes to the database per second. However, this blog post is focused on strictly serializable transactions rather than individual write operations. For Calvin's 500,000 transactions per second number, each transaction included many write operations.]
The main downside of the second category is that by localizing consensus on a per-shard basis, it becomes nontrivial to guarantee consistency in the presence of transactions that touch data in multiple shards. The quintessential example is the case of someone performing a sequence of two actions on a photo-sharing application (1) Removing her parents from having permission to see her photos (2) Posting her photos from spring break. Even though there was a clear sequence of these actions from the vantage point of the user, if the permissions data and the photo data are located in separate shards, and the shards perform consensus separately, there is a risk that the parents will nonetheless be able to see the user’s recently uploaded photos.
Spanner famously got around this downside with their TrueTime API. All transactions receive a timestamp which is based on the actual (wall-clock) current time. This enables there to be a concept of “before” and “after” for two different transactions, even those that are processed by completely disjoint set of servers. The transaction with a lower timestamp is “before” the transaction with a higher timestamp. Obviously, there may be a small amount of skew across the clocks of the different servers. Therefore, Spanner utilizes the concept of an “uncertainty” window which is based on the maximum possible time skew across the clocks on the servers in the system. After completing their writes, transactions wait until after this uncertainty window has passed before they allow any client to see the data that they wrote.
Spanner thus faces a potentially uncomfortable tradeoff. It is desirable that the uncertainty window should be as small as possible, since as it gets larger, the latency of transactions increases, and the overall concurrency of the system decreases. On the other hand, it needs to 100% sure that clock skew never gets larger than the uncertainty window (since otherwise the guarantee of consistency would no longer exist), and thus larger windows are safer than smaller ones.
Spanner handles this tradeoff with a specialized hardware solution that uses both GPS and atomic clocks to ensure a minimal clock skew across servers. This solution allows the system to keep the uncertainty window relatively narrow while at the same time keeping the probability of incorrect uncertainty window estimates (and corresponding consistency violations) to be extremely small. Indeed, the probability is so small that Spanner’s architects feel comfortable claiming that Spanner “guarantees” consistency.
[It is worth noting at this point that systems that use global consensus avoid this problem entirely. If every transaction goes through the same protocol, then a natural order of all transactions emerges --- the order is simply the order in which transactions were voted on during the protocol. When batches are used instead of transactions, it is the batches that are ordered during the protocol, and transactions are globally ordered by combining their batch identifier with their sequence number within the batch. There is no need for clock time to be used in order to create a notion of before or after. Instead, the consensus protocol itself can be used to elegantly create a global order.]

Spanner Derivatives


Spanner is a beautiful and innovative system. It was also invented by Google and widely used there. Either because of the former or latter (or both), it has been extremely influential, and many systems (e.g., CockroachDB and YugaByte) have been inspired by the architectural decisions by Spanner. Unfortunately,  these derivative systems are software-only, which implies that they have inherited only the software innovations without the hardware and infrastructure upon which Spanner relies at Google. In light of Spanner’s decision to have separate consensus protocols per shard, software-only derivatives are extremely dangerous. Like Spanner, these systems rely on real-world time in order to enforce consistency --- CockroachDB on HLC (hybrid logical clocks) and YugaByte on Hybrid Time. Like Spanner, these systems rely on knowing the maximum clock skew across servers in order to avoid consistency violations. But unlike Spanner, these systems lack hardware and infrastructure support for minimizing and measuring clock skew uncertainty.

CockroachDB, to its credit, has acknowledged that by only incorporating Spanner’s software innovations, the system cannot guarantee CAP consistency (which, as mentioned above, is linearizability).
YugaByte, however, continues to claim a guarantee of consistency [Edit for clarification: YugaByte only makes this claim for single key operations; however, YugaByte also relies on time synchronization for reading correct snapshots for transactions running under snapshot isolation.]. I would advise people to be wary of these claims which are based on assumptions of maximum clock skew. YugaByte, by virtue of its Spanner roots, will run into consistency violations when the local clock on a server suddenly jumps beyond the skew uncertainty window. This can happen under a variety of scenarios such as when a VM that is running YugaByte freezes or migrates to a different machine. Even without sudden jumps, YugaByte’s free edition relies on the user to set the assumptions about maximum clock skew. Any mistaken assumptions on behalf of the user can result in consistency violations.
In contrast to CockroachDB and YugaByte, FaunaDB was inspired by Calvin instead of Spanner. [Historical note: the Calvin and Spanner papers were both published in 2012]. FaunaDB therefore has a single, elegant, global consensus protocol, and needs no small print regarding clock skew assumptions. Consequently, FaunaDB is able to guarantee consistency of transactions that modify any data in the database without concern for the corner case violations that can plague software-only derivatives of Spanner-style systems.
There are other differences between Calvin-style systems and Spanner-style systems that I’ve talked about in the past. In this post we focused on perhaps the most consequential difference: global consensus vs. partitioned consensus. As with any architectural decision, there are tradeoffs between these two options. For the vast majority of applications, exceeding 500,000 transactions a second is beyond their wildest dreams. If so, then the decision is clear. Global consensus is probably the better choice.
 
[Editor's note: Daniel Abadi is an advisor at FaunaDB.]

45 comments:

  1. Very interesting read and well written! Shameless plug: I'm a master student in compsci and currently looking for an interesting 6 month research topic for my thesis in exactly this kind of topic (distributed database systems). While I have an interest in theory, I spent most of my time on practical stuff and have a hard time finding something worthy to research. Maybe any suggestions/tips?

    ReplyDelete
    Replies
    1. I'm working on a high level description of interesting problems in this area that I'd be happy to share offline. But either way, I'm recruiting PhD students --- you should apply to join my group at UMD!

      Delete
    2. I'm a German student from TUM currently visiting Osaka University (Japan, relocated this week) for my master thesis. Both my supervisors gave me freedom of choice for my topic, so I would love to collaborate, but applying for PhD isn't really possible right now. Yoi can reach me at herrd (at) in.tum.de if you would like to continue the conversation in private.

      Delete
  2. CTO of YugaByte here. We firmly stand by our claims, and I wanted to explain more.

    From the post by Daniel:
    << CockroachDB, to its credit, has acknowledged that by only incorporating Spanner’s software innovations, the system cannot guarantee CAP consistency (which, as mentioned above, is linearizability).

    YugaByte, however, continues to claim a guarantee of consistency. I would advise people not to trust this claim. YugaByte, by virtue of its Spanner roots, will run into consistency violations when the local clock on a server suddenly jumps beyond the skew uncertainty window. >>

    The statement about YugaByte DB is incorrect.

    1. With respect to CAP, both Cockroach DB (https://www.cockroachlabs.com/blog/limits-of-the-cap-theorem/) and YugaByte DB (https://docs.yugabyte.com/latest/faq/architecture/#how-can-yugabyte-db-be-both-cp-and-ha-at-the-same-time) are CP databases with HA and there is really no difference in the claims.

    2. With respect to Isolation level in ACID, YugaByte DB does not make the linearizability (called external consistency by Google Spanner) claim. YugaByte DB offers Snapshot Isolation (detects write-write conflicts) today and Serializable isolation (detect read-write and write-write conflicts) is in the roadmap (https://docs.yugabyte.com/latest/architecture/transactions/isolation-levels/).

    3. We have publicly claimed that we do rely on NTP and max clock skew bounds to guarantee consistency. For example, slide 43 of our NorCal DB Day talk (https://www.slideshare.net/YugaByte/yugabyte-db-architecture-storage-engine-and-transactions) we mention we are “relying on bounded clock sync (NTP, AWS Time Sync, etc).”

    ReplyDelete
    Replies
    1. Hi Karthik,

      Thanks for commenting on my post.

      I am quite confused by your statement that YugaByte does not claim linearizability. The C of CAP is linearizability (see the original CAP theorem https://users.ece.cmu.edu/~adrian/731-sp04/readings/GL-cap.pdf). By claiming to be CP from CAP, you are claiming linearizability.

      CockroachDB also makes the same CP claim. However, they explicitly walk back from this claim (https://www.cockroachlabs.com/blog/living-without-atomic-clocks/). In contrast, YugaByte documentation makes no effort to walk back from this claim. Rather, the documentation seems to indicate that YugaByte is linearizable at: https://blog.yugabyte.com/jepsen-testing-on-yugabyte-db-database/ and https://docs.yugabyte.com/latest/develop/learn/acid-transactions/.

      Also, I would encourage you to read the Herlihy-Wing paper on linearizability published in 1990. You seem to be confusing linearizability with ACID isolation levels, which are actually a different concept. Peter Bailis has a good blog post on the difference: http://www.bailis.org/blog/linearizability-versus-serializability/.

      On your third point, we agree. However, the point of my post is that relying on max clock skew without hardware support is dangerous. I’m going so far as to say that it’s so dangerous that it is incorrect to claim consistency guarantees when you make such assumptions.

      I would really encourage YugaByte to consider using global consensus instead of partitioned consensus. I believe you will find it much easier to support serializability (which as you said, is on your road map) and linearizability.

      Delete
    2. From the Peter Bailis link you had:

      > Linearizability is a guarantee about single operations on single objects.

      Our references to "linearizability" in the Jepsen blog and the docs are in the context of single key operations; happy to update to update our docs to clarify that further.

      For multi-key transactions in YugaByte DB, our docs clearly point out that we offer Snapshot Isolation today and Serializable Isolation is in our roadmap (https://docs.yugabyte.com/latest/architecture/transactions/isolation-levels/).

      Delete
    3. OK, great. Thanks for the clarification and for reading my post. I'd be happy to follow up with you or your team if you have any questions about the research on distributed transactions coming out of my lab.

      Delete
    4. Thank you as well Daniel for looking into YugaByte. Would love to talk you, understand your research and what your team is working on - that sounds very exciting.

      BTW, do you mind rewording the following:
      << YugaByte, however, continues to claim a guarantee of consistency. I would advise people not to trust this claim. YugaByte, by virtue of its Spanner roots, will run into … >>

      to maybe something like:
      << YugaByte claims Snapshot Isolation (with Serialization Isolation in its roadmap) as the consistency guarantee. But by virtue of its Spanner roots, YugaByte will run into … >>

      We really do not believe in putting out incorrect information, so would greatly appreciate it. I will connect with you on linkedin. Thanks!

      Delete
    5. Sorry small type: "Serialization Isolation" should be "Serializable Isolation"

      Delete
    6. Sure, I can update the post to clarify YB's claims. Quick question just to make sure I fully understand:

      In the YB documentation at: https://docs.yugabyte.com/latest/architecture/transactions/transactional-io-path/, for the sentence: "If ht_read < ht_record ≤ definitely_future_ht, we don’t know if this record was written before or after our read request started. But we can’t just omit it from the result, because if it was in fact written before the read request, this may produce a client-observed inconsistency. Therefore, we have to restart the entire read operation with an updated value of ht_read = ht_record." --- when you use the word "inconsistency" in that sentence, are you talking about a violation of linearizability, or a different meaning of the word "consistency". It seems from context of the rest of that sentence that you are talking about linearizability, but I want to double check.

      Delete
    7. Yes, you are right - we are referring to linearizability being violated.

      Delete
  3. Great post, very informative.
    Curious to get your take on TiDB (https://github.com/pingcap/tidb) and its transaction model as it relates to consistency guarantee.
    One of its engineers wrote about how it differs from Spanner and Cockroach here: https://dzone.com/articles/tick-or-tock-keeping-time-and-order-in-distributed-1

    ReplyDelete
    Replies
    1. I haven't had a chance to look into TiDB in detail yet, but it sounds like they don't rely on clock synchronization, in which case they wouldn't run into the problems discussed in this post.

      Delete
    2. TiDB developer here, at the very beginning of TiDB (~4 years ago), we've deeply discussed which transaction model we should apply, at the end, we choose Google Percolator's transaction model, even though it reply on a centralized TSO, but I don't think throughput is a big problem when you deploy the whole cluster in one IDC (most of our OLTP adoptions have <5ms avg latency), the real challenge is HA, we solved this problem by using Raft to choose a leader across multiple TSOs.

      Delete
    3. I would also love to see a follow-up/addendum that covers TiDB's approach! In my mind TiDB and CockroachDB are neck-and-neck in terms of features, development timeline, and target audience, so it seems like a glaring omission in an otherwise fantastic post! Either way, this has already become my go-to article to share when people ask what "NewSQL" means, thanks for this great writeup.

      Delete
  4. Spanner TrueTime is used for deciding the timestamp of the transaction. If the transaction touches more than one shard it uses two phase commit as mentioned in the spanner paper [1]: "If a transaction involves more than one Paxos
    group, those groups’ leaders coordinate to perform twophase
    commit."

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

    ReplyDelete
    Replies
    1. Yes, that is another disadvantage of Spanner vs. Calvin. I discussed that in a previous post on my blog (http://dbmsmusings.blogspot.com/2017/04/distributed-consistency-at-scale.html) so I didn’t discuss that in this one. But multi-shard transactions in Spanner also pay the commit wait time cost of clock skew uncertainty in order to avoid linearizability violations. It was only that disadvantage that I discussed in this post.

      Delete
  5. Though mild, there is certainly aacontradiction in conceding that the CAP theorem is flawed because its claims are too absolute/theoretical (agreed btw!) but then giving these systems a hard time for using a more practical level of consistency than that which CAP relies upon.

    Linearizability is not the be all and end all. We should applaud these practical, productionized contributions to the space, as long as their tradeoffs are clear!

    ReplyDelete
    Replies
    1. I do not believe linearizable consistency is impractical. As I said in my post, it’s the safest way to avoid buggy code. But yes, I’m all for applauding practical, productionized contributions to the space, such as all of the database systems referred to in this post, including the NoSQL solutions. I’m just trying to communicate to people that blindly going with partitioned consensus instead of global consensus (just because Spanner does it) is a bad idea.

      Delete
  6. Daniel, you did not mention one of the biggest downsides of a central oracle design: latency (especially read latency). For example, say your database is set up with nodes in both US and European data centers that each store data for users located nearby. You have to decide where to locate your central oracle - which customers will get higher latencies?

    By contrast, bounded-timestamp systems can read/write locally in both US and Europe with no cross-ocean coordination necessary. That solves a real business problem for global companies, which means that the engineering will eventually catch up. Cloud providers will eventually install atomic clocks/GPS systems in all their DCs and make TrueTime-like APIs for developers to use. At that point, Cockroach/YugaByte can become fully linearizable with minimal effort.

    Your arguments have merit, but they come with an expiration date.

    ReplyDelete
    Replies
    1. This post did not discuss a central oracle. It discusses the difference between partitioned vs global consensus. Consensus requires communication across geographic regions, so yes, both partitioned and global consensus add necessary latency to evert transaction. If you don’t need to guarantee strong consistency, aka linearizability, you can avoid consensus and get better latency. I actually did include a link to my PACELC theorem in my post which explicitly discusses the latency vs. consistency tradeoff (that is the L and C of PACELC). But this post assumes from the beginning that you want full linearizable consistency. With that assumption, we looked at the difference between partitioned vs global consensus. Bounded timestamp systems do not guarantee linearizability, and thus were out of scope of this post. However, I did say in my post that there will always be a place for NoSQL/weaker consistent systems. I just believe that strong consistency will lead to fewer bugs in the long run, and most developers should default to a consistent system, and only move away if they have stringent latency requirements.

      As far as the expiration date you mentioned: you are assuming everybody will be running their DB in the cloud. I definitely agree that more and more DBs will run in the cloud over time, but there will always be a market for non-cloud deployments and I don’t think YugaByte or CockroachDB will want to give up on that market. BTW: there are other advantages of global consensus over partitioned consensus not mentioned in this post. Much of the system becomes much cleaner with global consensus. Perhaps I’ll write a post on that subject in the future. Also, as I alluded to in a comment response above, global consensus can also potentially avoid the need for 2PC.

      Delete
    2. You're setting up a straw man, though. Your argument is that NewSql software-only databases should use global consensus because you've solved the scalability problem, and that's the "main downside of the first category". But that's only true in a single DC deployment. In that special (but obviously very important) case, it's not hard to knock down the straw man.

      But Spanner and Cockroach were designed from the ground-up to be geographically distributed databases. In that scenario, latency becomes as big a problem to grapple with as scalability. And Calvin-style systems will exhibit much higher latencies when its nodes are spread across widely separated DC's, because every consistent read and write must contact a global sequencer. By contrast, Spanner offers the same linearizabiity guarantee (admittedly with some tiny chance of failure), but without paying that latency cost.

      Your argument is that Calvin is a "better starting point" for software-only distributed databases. But by failing to acknowledge the different design goals for the two categories, you're giving an incomplete picture of the real tradeoffs involved. Also, I think you're looking backwards rather than forwards. Oracle RAC largely solved the problem of a consistent DB in a single DC almost 20 years ago. While I'm sure Calvin improves upon their design, it's still an evolution, not a revolution. Why not turn your attention to the fascinating and still emerging problem of building a consistent, geographically distributed DB with low latencies?

      P.S. - You're probably already aware, but AWS exposes an atomic clock / GPS service that apps can use to keep very accurate time: https://aws.amazon.com/about-aws/whats-new/2017/11/introducing-the-amazon-time-sync-service/.

      Delete
    3. Just to clarify one factual statement: Calvin was also designed for multi-region deployments. Calvin's most well-known architectural innovation is its deterministic engine (not discussed in this post) which was (partially) motivated by performance problems with georeplication (see e.g. http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf and better explained in: http://www.cs.umd.edu/~abadi/papers/abadi-cacm2018.pdf).

      I chose not to discuss latency in this post (despite my previous writings on the latency vs. consistency tradeoff) because the issue is somewhat orthogonal. Partitioned consensus vs. global consensus have the same latency. It is true that read-only transactions in Spanner can avoid global consensus (and still be linearizable), but there is also a version of Calvin where this is true as well (the subject of a likely future post).

      Delete
    4. "Partitioned consensus vs. global consensus have the same latency."

      Say I have a partitioned table, with one partition in Europe and the other in the US (say they're 100ms apart). Two small, independent transactions commit in both locations, with linearizability as a requirement.

      Spanner can commit both txns in <1ms (my understanding is the team has reduced the uncertainty interval below 1ms). Calvin, as I understand it, would require at least 100ms to commit one or the other txn, depending on where the sequencer was located.

      Is my understanding correct?

      Delete
    5. No, that's not correct!

      Spanner runs Paxos on every transaction that updates data, so it takes 100ms as well!

      Delete
    6. Ah, but all the replicas for each partition would be located in the same region (such as AWS availability zones). I don't need to cross the ocean to achieve consensus.

      Delete
    7. Oh, sorry. I misunderstood the case you were presenting. Does Cloud Spanner even support that configuration? But yes, if you are willing to pay the increased availability vulnerability of region outage, then that would be another difference between partitioned consensus and global consensus (aside from the scalability issue I discussed in the post). However, I do not believe such configurations are common in practice.

      Delete
    8. As I mentioned above, this is on the frontier of what's possible in ACID databases. To my knowledge, Cloud Spanner doesn't yet support it (but internal Spanner might), but Cockroach does (see https://www.cockroachlabs.com/blog/geo-partitioning-one/).

      As for whether such configs are common, in a narrow sense they're not, because they've never been possible/practical before! In a wider sense, they're actually ubiquitous, since every global company works around the lack of a geo-distributed database by running different databases (or shards) in every region, and then having some kind of sync'ing protocol to download regional data into a central database for analysis and reporting. This is costly to setup and maintain and invites consistency errors.

      As for availability vulnerability, the choice is in the hands of the DBA. Availability zones are almost as good as separate DC's for HA and DR. But if that's not good enough for your app, then by all means put your replicas in 3 DC's in the US and 3 DC's in Europe. You still don't need to pay US-Europe latency.

      Think it over more; hopefully you see the other side of the argument more clearly now.

      Delete
    9. "By contrast, bounded-timestamp systems can read/write locally in both US and Europe with no cross-ocean coordination necessary."

      It deservers a full blog post, but FaunaDB does not require any cross-datacenter coordination on read-only transactions, so the read latency cannot possibly be better.

      For writes, well, if you want them to be linearized and highly available, you have to replicate the data to multiple datacenters. Unfortunately we have not solved the speed of light issue quite yet.

      FaunaDB sequencers can be pinned to a single datacenter only which would mimic the lower latency/lower availability scenario you describe.

      Delete
    10. You're making my point for me, then. FaunaDB decided to give up the strict serializability that Calvin offers for read-only transactions. Why? Because Calvin's consistency comes at the cost of high latencies in geo-distributed scenarios. Every design has its drawbacks, and this is one of Calvin's.

      Do you see the disconnect here? Daniel is criticizing non Calvin-based databases for not being perfectly consistent, but at the same time FaunaDB has chosen to give up on perfect consistency by default. In fact, FaunaDB is less consistent than CockroachDB for read-only transactions, since Cockroach will uphold strict serializability for txns that read or write the same keys (see https://www.cockroachlabs.com/blog/living-without-atomic-clocks/).

      You're going to run into further consistency problems if you try to reduce write latencies without relying on clocks. If you pin your sequencer to a Europe DC, then US DC's are going to have high write latencies. If you move to having a sequencer in each region, then you'll give up strict serializability. You've got to give up either latency or consistency if you don't use synchronized clocks.

      That's the beauty of Spanner's solution. They get to have their cake (low latency) and eat it too (strict serializability). Now it's just a question of bringing that technology and engineering to non-Google databases.

      Delete
  7. We recently open sourced our project https://github.com/rubrikinc/kronos which tackles some of the clock synchronization problems in the absence of atomic clocks. We have integrated it with CockroachDB and have seen promising results. In practice we have seen it steadily maintains offsets within the cluster within a few hundred microseconds depending on RTT between nodes (which is acceptable for normal operations) and system clock jumps on nodes don't impact this service. Offsets can get a bit higher depending on inter node clock drifts, but they are periodically corrected.

    ReplyDelete
    Replies
    1. If people continue to create software-only Spanner-style DBs, there will definitely be a need for that type of project. But I remain convinced that Calvin is a better starting point for software-only distributed DBs.

      Delete
  8. have you seen the Huygens clock sync paper https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf?

    re Calvin: a lot of real world applications cannot be structured as deterministic server-side transactions.

    ReplyDelete
    Replies
    1. On my to-do list :)

      Re:Calvin. Yes, I agree. Interestingly, FaunaDB significantly reduced the deterministic requirements relative to Calvin. There are some downsides of reducing these deterministic requirements that would require another post to discuss, but the upside is that they work for more applications than Calvin can. This post just focused on global consensus, and Calvin and FaunaDB are equivalent in that regard.

      Delete
  9. Hi Daniel, great post.

    However, this claim "Calvin was able to achieve a throughput of over 500,000 transactions per second" seems to be limitation for large scale internet company. For example, I use to work for Ola (A ride hailing company similar to Uber) and I can say that a single system use to generate a load of over 1Million Transaction /Second. Of course we could use application level sharding but that might again introduce more bugs and load on developers to redo the data model.

    ReplyDelete
    Replies
    1. Can you please give more details about that application? It is the consensus of the research community that applications that require 1M xact/sec either don't exist or are otherwise extremely rare. What is a "transaction" in that application? (Remember that a transaction consists of potentially many writes that must occur atomically). In other words, what is the "event" that generates a transaction in that application, which requires traditional atomic ACID guarantees?

      (I'm currently writing a report describing challenges for the DB research community moving forward. I would love to have examples of real applications that actually require 1M xacts/sec).

      Delete
    2. BTW: Please also see my response to Lu Pan below. I'm really searching for applications that require 1M xact/sec where the transactions can't be combined or sent to separate databases.

      Delete
  10. This comment has been removed by the author.

    ReplyDelete
  11. Great post! I also have a question on the 1/2 Million txn per second claim. 1) Are the numbers of Amazon and NASDAQ client purchase txns instead of database txns? Usually the write amplification is significant, that lots of metadata and other stuff are written at the same time for indexing, offline ML, etc. 2) do you think we can also optionally do reads out of paxos, for certain queries that do not require strong consistency to improve throughput? In practice, I would assume Calvin type of distributed databases are more read heavy (maybe Kafka + materialized views for write heavy workload?). Anyway for read heavy workload, most of reads usually do not require strong consistency. Doing those out side of paxos, should improve throughput a lot.

    ReplyDelete
    Replies
    1. First: Yes ---- only linearizable reads in Calvin must go through consensus. Other reads can go to the closest replica (and run as of a serializable snapshot at that replica) and thus avoid consensus. The same is true for FaunaDB.

      As far as my examples, I'm talking about database txns. However, I'm assuming that much of the write amplification can either (1) be combined into a single transaction or (2) are written to different databases.

      For data that is "insert-only" (i.e. will not get updated), there is basically no isolation penalty by combining into a single transaction. But if you can argue why they have to be separate transactions (at a fundamental level), but yet still write data to the same database, I'm very curious to hear the argument.

      Delete
    2. Thanks for the reply!

      > However, I'm assuming that much of the write amplification can either (1) be combined into a single transaction

      Absolutely true! It's just usually when more operations are batched into one transaction, reliability drops.

      I was thinking, for conditional queries (read-modify-write), batched query has a much higher chance of failing, because it fails as long as one key fails to satisfy the condition.

      But yeah you are right, for "insert-only", which is more log-like workload, batching is great! :)

      Delete
  12. Don't settle for eventual consistency https://yokota.blog/2017/02/17/dont-settle-for-eventual-consistency/

    ReplyDelete
  13. Database Comparison: An In-Depth Look at How MapR-DB Does What Cassandra, HBase, and Others Can't https://mapr.com/blog/database-comparison-an-in-depth-look-at-mapr-db/

    ReplyDelete
  14. Cassandra claims a _strong_ consistency if read consistency level + write consistency level > number of replicas.

    https://docs.datastax.com/en/cassandra/3.0/cassandra/dml/dmlAboutDataConsistency.html

    however, this guarantee, too, relies on no clock skew as Cassandra uses the most recent write as the winning write.

    ReplyDelete