Pet peeve: eventual consistency isn't for scalability and performance, it's for availability. In a well designed system, the whole debate only matters during in a failure condition: a strongly consistent system gives up availability upon a certain kind of failure, an eventually consistent system gives up consistency upon a certain kind of failure.
There are strongly consistent scalable "NoSQL" systems e.g., BigTable. Megastore even provides complex distributed cross row transactions.
In a well tuned system, loss of availability (in a failure scenario) could be minimize to seconds. What this means for performance is that you have systems which encounter second-long latency spikes upon failures.
It also isn't a binary switch:
1) Quorums can be used to achieve read-your-write consistency in the case of simple failures (loss of 1 node out of 3).
2) There's multiple kinds of relaxed consistency models. One of them is serializable consistency: you may get a stale read, but the the order of reads is the same as the order of writes. This is used by PNUTs and can be achieved by serializing the writes through a single master. This means that there's (again, for a short time period) loss of write availability in a failure, but there's no loss of read availability.
3) Paxos/multi-Paxos can be used to achieve atomic writes (all available nodes receive the write) while withstanding simple failures (similar to quorum protocols... and I believe multi-Paxos uses quorum protocols under the cover to improve liveness over "raw" Paxos). This is at the cost of higher latency (and complexity). [Edit: In this case, you're dealing with full-blown strong consistency, but with -- at the cost of latency -- the ability to tolerate certain kinds of simple failures/trivial partitions]
Clustrix looks interesting, but it looks like it addresses the scalability and performance issues with RDBMS, but not the availability feature. If an RDBMS were to drop the "A" and "I" in ACID (C in "ACID" means serializable view of the execution, which is not the same as the C in "CAP": the latter means all nodes in a cluster agreeing upon what the data is which isn't required for the former), it would be possible to build a highly available, low latency RDBMS; but it would also not be as useful without atomic and isolated cross row transactions.
[Disclaimer: I work on a Dynamo-style database, but fond of PNUTs as an architecture (more difficult to implement, but IMO a better fit for plurality of web applications) and generally fascinated and interested in distributed systems, databases and systems programming in general]
I like the content of this post, but I take issue with the idea that the debate only matters in a failure condition. That's academically true, but practically misleading. When developing my app, I have to assume any part of the system could fail at any time. Thus my whole app needs to be written with failure in mind.
In an ACID system, that means my transactions either happen or don't, and it's on me to figure out whether they did or not. Sometimes I'll need to do some investigating after a failure to find out what succeeded and what rolled back.
In an eventually consistent system, I need a contingency plan for every operation on the system. Now that contingency plan might be very simple, such as "Whatever happened, happened and last writer wins." The CALM conjecture paper does a decent job of describing when this might be a workable contingency plan. More complicated operations require increasingly complex contingency plans. This is why Cassandra is now offering counters as an API feature, because something as simple as counters is really hard to get right in all failure scenarios.
If you fit the CALM description and require multi-data center availability, then EC is probably a good bet. It may still be a good bet otherwise, but the availability comes along with a much more difficult app development picture, failures or no.
> This is why Cassandra is now offering counters as an API feature
This is specific to Cassandra, where the development team chose not to implement optimistic locking via version vectors. That said the counters patch essentially implements a vector of counters, very similar conceptually to a vector clock.
That said, there are some scenarios where quorums (in absence of an agreed upon view of the cluster e.g., a zookeeper-based failure detectors) could mean concurrent vector clocks, which means it's up to the application to reconcile it.
If your application can not reconcile a split brain scenario on its own and depends on a total order then yes, it's not a good fit for EC.
As I've said, I also think that serializable consistency is easier for applications to deal with (they can assume a total order) than eventual consistency but provides the strong benefit of read availability (something, quite frankly, most Internet applications require).
Most complex applications have points where consistency can be relaxed (either somewhat or fully) and points where consistency is needed.
In "we chose consistency" and "we chose availability" cases, the applications will have to deal with the consequences of those choices: much as developers may handwave the implications of an eventually consistent system (since it returns right results most of the time, not thinking whether or not their application is sensitive to a non-serializable order) they might also implement ad-hoc, poorly thought out HA solutions on top of strong consistent systems -- often times losing both availability and consistency.
The typical usage scenario of masking MySQL failures and latency by using memcache comes to mind. VoltDB is very correct to remove the need to use memcached for read latency (a caching layer in front of a database which already a cache which sits on top of a file system with a cache is a caching layer too many), but in many cases I've seen memcached used to accept reads (and sometimes writes) while the underlying database is unavailable.
Finally, the whole debate about atomicity is quite meaningless if (like many applications) you're fronting your data access layer with an RPC framework (your RPC call may go through to a database and perform a write even it times out to the application i.e., implying non-atomicity).
The CALM paper is a big move into the right direction: being able to determine synchronization points at which ACID transactions (or weaker forms of synchronizations if permissible e.g., quorums and version vectors) can be used. Incidentally, I also think a declarative language (whether like Bloom/Bud or closer to SQL) is a good way to express the constraints and let a system (which may not be all that different from a query planner) determine whether those points occur.
As for RPC, whether the client is informed of success or failure has nothing to do with atomicity. The guarantee is that the transaction either happens completely or not at all, and nothing more.
Agreed, it can be very frustrating that under certain failure scenarios, it's unclear whether the transaction completed or rolled back. Still, given atomicity, a correctly designed system can't be left in an inconsistent state. At times, it's up to the application to discover (or re-discover) that state.
Systems that offer atomicity for single record operations can actually make the same assurances, but may require complicated escrow systems and compensating transactions.
Eventual consistency often gives up the ability to develop applications against the system, because more reasoning about the state of the system has to be embedded in the application logic. For a better description of this problem, see this post from an AWS employee:
Note that his "right answer" for performance (not availability, so it's a bit of an aside from your comment) is to dynamically repartition, which is what Clustrix does. Note that we can actually do this type of repartitioning on just the "hot" data, using MVCC to avoid any downtime (unlike Mongo, which blocks all writes).
By the way, the Google Megastore project I believe you're referring to is not actually eventually consistent in the same way that, say, Cassandra is. Megastore is fully ACID within an entity group, meaning that lowering eventually consistency down to the per-node level was not the solution that Google went with. BigTable is also not eventually consistent.
Entirely agree with you, eventual consistency and quorums protocols all have their drawbacks. Difficult of developing against that (and the natural reaction of just "handwaving" the consistency model rather than using optimistic locking with a vector clock at the identified synchronization points) is the main one. I have, however, also seen the situation where developers would fail to understand how to correctly deal with availability and build ad-hoc, poorly thought-out HA layers on top of non-HA systems. The typical memcache + MySQL deployment is the prime example of that: there's neither the high availability, nor an understandable consistency/cache coherence model.
> Note that his "right answer" for performance (not availability, so it's a bit of an aside from your comment) is to dynamically repartition, which is what Clustrix does. Note that we can actually do this type of repartitioning on just the "hot" data, using MVCC to avoid any downtime (unlike Mongo, which blocks all writes).
Dynamic repartitioning is also what HBase/BigTable do ("tablet splitting"). The MVCC approach is interesting way around the unavailability window, by the way.
> By the way, the Google Megastore project I believe you're referring to is not actually eventually consistent in the same way that, say, Cassandra is. Megastore is fully ACID within an entity group, meaning that lowering eventually consistency down to the per-node level was not the solution that Google went with. BigTable is also not eventually consistent.
Yes, I did not mean that Megastore is eventually consistent. It is not, it's ACID compliant and uses Paxos. Real question: was this not stated clearly in my comment (I'd like to edit to clarify if it is)?
Megastore, however, is an example of a "NoSQL" system and I meant to use it as proof that not all "NoSQL" systems give up consistency: ACID is orthogonal to the query language.
Quite frankly I find the whole query language debate (and "NoSQL" marketing gimmick) to be quite pointless, the distributed systems and systems programming aspects are a lot more interesting to me.
> Yes, I did not mean that Megastore is eventually consistent. It is not, it's ACID compliant and uses Paxos. Real question: was this not stated clearly in my comment (I'd like to edit to clarify if it is)?
I was interpreting the nod to Megastore in the context of the first sentence, which seemed pretty strongly about eventual consistency. Nothing to worry about, though - your followup comments are very clear!
> Megastore, however, is an example of a "NoSQL" system
Looking at Google's recent papers, they actually seem to be moving more in a SQL-ish direction. Dremel, in particular, appears to be a variant of SQL that allows easier access to nested and/or repeated columns. I thought Megastore was in a similar vein, but at that moment I can't seem to find the link that made me believe that (other than seeing that it uses strongly typed schemas).
Regardless of the benefits of a SQL-like language as an interface, however, I think you have a good point: the underlying architectural decisions about things like consistency or stability are very interesting, but often obscured.
A large part of the message I'm trying to convey is:
1. A DBMS is much more than just the interface. I'm going to write more on the subject. Whether you're using SQL, datalog, BSON, etc. -- there's a broader set of desirable features that's more important than the query language.
2. I'm not saying I agree with what the NoSQL folks are saying, or their justifications. Let's be honest: there's a prevalent sentiment that relational SQL based databases do not scale, and even further, that they somehow cannot scale. That's just not true.
I saw a video the other day of some guy at Google giving a talk about the database behind the app engine. At one point someone in the audience asked about scale and SQL. His response was "Well, how well does SQL scale?" Everyone in the room laughed.
> I saw a video the other day of some guy at Google giving a talk about the database behind the app engine. At one point someone in the audience asked about scale and SQL. His response was "Well, how well does SQL scale?" Everyone in the room laughed.
Sell your strength, don't attack others weakness. Demonstrate how your product is actually very similar to megastore (strong consistency, use of distributed transactions) and differs only in the query language ("GQL" itself is very similar to SQL to the point where an application developer could care less about which one is using). It looks like this is case the case (except I believe you guys are using 2PC instead of Paxos, in which case you want to clearly state the availability scenarios which Paxos addresses and at what costs).
Of course the problem with systems like megastore is that the overhead they introduce is seldom worth the compromises the application developers have already made. Incidentally, form what I hear, Megastore is not used very frequently outide of the app engine: application developers at Google itself are comfortable with using Spanner/BigTable directly but aren't comfortable with the additional overhead of distributed transactions as used by Megastore. App engine, customers, on the other hand aren't particularly interested in low a in the first place but aren't used to design patterns used on top of systems like BigTable.
By the way, I think Clustrix is a great product. I remember reading the white papers/specs when it came out and I'll make sure to scan it over again. Just why in the (imo, useless) SQL/NoSQL marketing circus rather than focus on the product's strength?
I personally think MongoDB is a poor comparison choice: it has the buzz, but there are some serious flaws in its distribution architecture (namely ill defined consistency and partitioning model) and the outdated disk persistence story (Mendel Rosenblum wrote his dissertation in 1992; building a log structured database is no less risky than cloning circa-1995 MyISAM). Comparison with another strongly consistent system like HBase or HyperTable would be more fit.
There are strongly consistent scalable "NoSQL" systems e.g., BigTable. Megastore even provides complex distributed cross row transactions.
In a well tuned system, loss of availability (in a failure scenario) could be minimize to seconds. What this means for performance is that you have systems which encounter second-long latency spikes upon failures.
It also isn't a binary switch:
1) Quorums can be used to achieve read-your-write consistency in the case of simple failures (loss of 1 node out of 3).
2) There's multiple kinds of relaxed consistency models. One of them is serializable consistency: you may get a stale read, but the the order of reads is the same as the order of writes. This is used by PNUTs and can be achieved by serializing the writes through a single master. This means that there's (again, for a short time period) loss of write availability in a failure, but there's no loss of read availability.
3) Paxos/multi-Paxos can be used to achieve atomic writes (all available nodes receive the write) while withstanding simple failures (similar to quorum protocols... and I believe multi-Paxos uses quorum protocols under the cover to improve liveness over "raw" Paxos). This is at the cost of higher latency (and complexity). [Edit: In this case, you're dealing with full-blown strong consistency, but with -- at the cost of latency -- the ability to tolerate certain kinds of simple failures/trivial partitions]
Clustrix looks interesting, but it looks like it addresses the scalability and performance issues with RDBMS, but not the availability feature. If an RDBMS were to drop the "A" and "I" in ACID (C in "ACID" means serializable view of the execution, which is not the same as the C in "CAP": the latter means all nodes in a cluster agreeing upon what the data is which isn't required for the former), it would be possible to build a highly available, low latency RDBMS; but it would also not be as useful without atomic and isolated cross row transactions.
[Disclaimer: I work on a Dynamo-style database, but fond of PNUTs as an architecture (more difficult to implement, but IMO a better fit for plurality of web applications) and generally fascinated and interested in distributed systems, databases and systems programming in general]