7 ms·

How to beat the CAP theorem

183 points by icey 15y ago

rxin 15y ago
Good write up, Nathan. Nonetheless, you started by saying you were going to challenge the basic assumptions of how data systems should be built, but the resulting system architecture is in fact very similar to a lot of data streaming systems that the academia and industry have proposed and built for a number of years. An example of such system is Google's Percolator [1]. In essence, you separate the system into two parts, a read-only part and a real-time part. CAP explains fundamental trade-offs in OLTP type of queries, whereas this system design is catered towards streaming, analytical queries. These are two very different contexts. [1] http://research.google.com/pubs/pub36726.html http://research.google.com/pubs/pub36726.html
- nathanmarz 15y ago
  I was under the impression that Percolator was a purely incremental system. I'll have to give the paper another read to see if they're using a hybrid batch/realtime approach. The system I described isn't limited to any particular "type" of query. It's a way of supporting arbitrary queries on arbitrary data, which encapsulates everything. Most people assume mutable state and incremental updates when building data systems. This is in fact the approach that almost all databases take. These are the assumptions I challenged.
  - VladRussian 15y ago
    >Most people assume mutable state and incremental updates when building data systems. This is in fact the approach that almost all databases take. These are the assumptions I challenged. it isn't assumptions. It is requirements for some systems. You drop requirements - you get a breathing room and can build a different system.
    - nathanmarz 15y ago
      Mutability and incremental updates are never requirements. Requirements have to do with performance and resource usage: X amount of space, Y amount of memory, Z amount of latency, etc. Mutability and incremental updates are approaches. I showed a different approach with immutability at the core which leads to a system with some amazing properties.
      - eru 15y ago
        I hope that examples like this and git make more people see the value of immutability. In the context of functional programming the same concept is called purity.
heyrhett 15y ago
Wow, this article is full of clear, coherent, well thought out points... and references!
ww520 15y ago
OP adds confusion by calling data immutable. Data has a well accepted common usage of being updatable. Event is the term what OP wants. Event is a snapshot of fact happened in time and cannot be changed and it's immutable. What OP described in general is the append-log based approach to storing and querying data. There are a whole bunch databases and file systems built on the append-log idea. It's well worth the time to check out the research in this area to see the benefits and pitfalls of the approach. Also check out the Complex Event Processing topic which bears similarity to what OP described.
- nathanmarz 15y ago
  Like I said, I was going to break your assumptions on data systems. Treating data as mutable (whether you use MVCC or append logs or any other approach) leads to major complexity problems, as I detailed in the post.
  - ww520 15y ago
    Redefining the meaning of general term just creating more confusion about the point you want to make. Why not use precise definition. The term "data" is really really general and it's bad to convey what you really mean. Are you talking about data value? Data object? Data record? Data version? Data event? Quoting from your blog, "A piece of data is a fact that you know to be true at some moment of time." That's called an Event. That's a snapshot of fact in time. MVCC is one way to do transaction. The blog didn't deal with transaction at all so I don't see the comparison. Append log-based databases do the closest to what you described in avoiding changing data in place and recompute/precompute data at query time. It's a very simple mechanism. What complexity problem do you see with it?
- RickHull 15y ago
  > OP adds confusion by calling data immutable. Data has a well accepted common usage of being updatable. I find this point to be generally contentious. Certainly in the realm of programming languages, data is often held immutable. I think mutable vs. immutable data is an important distinction with wide-ranging implications, so I find being explicit here adds clarity rather than confusion.
seabee 15y ago
I wrote my thesis on an immutable data store as a means to beat CAP. I didn't get quite as far as your other observations though, as mine was in the context of continuation web frameworks. Very nice write-up however.
- nathanmarz 15y ago
  Thank you. Got a link to your thesis anywhere? Would love to read it.
  - seabee 15y ago
    It's not in a state I would like to make public yet. Sufficient to get my degree, but the quality is poor due to personal circumstances. However I sent you a link via your contact form.
chrisdew 15y ago
This looks like Event Sourcing / CQRS. Is that correct?
- nathanmarz 15y ago
  There are similarities. It's really closer to functional programming than anything else.
perlgeek 15y ago
> The key is that data is immutable. Immutable data means there's no such thing as an update, so it's impossible for different replicas of a piece of data to become inconsistent. I'm not following that point. Suppose you have an event-souring data store as the OP suggests, and some nodes go out of sync. So one of the nodes records that Sally now lives in Atlanta, the other doesn't. The query for Sally's location asks for the last update. One node says Atlanta, the other still says Chicago. What's that, if not inconsistent? Only appending data means you don't corrupt old data, but you still can get conflicting responses from different parts of your system.
- herge 15y ago
  You add a version number or timing information to each update. Node A says Atlanta, with version 42. Node B says Chicago, with version 41. 42 > 41, so you go with Atlanta.
  - VladRussian 15y ago
    when you have fault in the system so you can't access node A, node B returns Chicago with version 41 and you proceed with it if your system choice is Availability at the price of Consistency, or you wait for the node A if you choice Consistency at the price of Availability.
- IgorPartola 15y ago
  This is the key point. You either set your writes to be synchronous or asynchronous, depending on whether you want consistency or high availability. The point of having no updates means that you have less possibility for conflicts when sites A and B are appended to simultaneously. This means robust replication even with async writes.
- nathanmarz 15y ago
  What you're describing is a query. "What is Sally's current location?" Queries can be inconsistent during partitions. This is what eventual consistency means. But once the partition clears, the queries will be consistent again. The data is immutable. Both "Sally lives in Atlanta as of time X" and "Sally lives in Chicago as of time Y" are true. This is far, far different from databases based on mutable state. In order for a database like that to be eventually consistent, you need to do read-repair to enforce consistency. This is besides the other problems I brought up with mutable databses, such as a lack of human fault-tolerance.
pierrebai 15y ago
How does the system deal with real-world data that has cross-datum consistency requirements? Many system mnodeling real-world have this issue: accounting, inventory, ... I'm also annoyed by the repeated mantra that you must have partition tolerance. In fact, most naïve systems are designed without it, with some central authority that must always be accessible. (Any system that is stricly a tree with an essential root node is like that. Any partition that does not include the root node cannot do any work, thus the system is not partition tolerant.) You can then have CA (by requiring that all requests and updates must propagate to the root.)
- IgorPartola 15y ago
  You then do not have the A part of CA. Your root node is not accessible => your entire system is not accessible.
- nathanmarz 15y ago
  The system computes functions on all the data you have. That describes every possible data system. In the realtime layer where you compensate for the last few hours of data, you'll need an incremental strategy to maintain that "cross-datum" consistency.
Maro 15y ago
In practice, beating the CAP theorem inside the data center is achieved by using a 2-tiered system. Have a set of lightweight controller processes which use a consistent majority voting algorithm (Paxos) to replicate the state of the cluster. Since it's lightweight, you can run 5 or 7 of them, meaning 2 or 3 can die. This is enough Availability in practice, per customer input. Have a set of data nodes which actually store the data. Put groups of 3 of these in replica sets and use consistent replication (Paxos). If one or two of them goes down, the controllers reconfigure the replica set, so you get Availability even if 2 of 3 goes down. (Customers love that they get Consistency but 2 of 3 can go down.) This scheme is used in my company's product. The idea comes from academic/Google papers, and is used in other products, too. The scheme does not work for multi-datacenter use-cases. If you want that, you have to give up consistent replication (Paxos) inside the replica sets and use some kind of eventual consistency. This variation of the 2-layered scheme is used by one of the popular competing NoSQL systems.
- VladRussian 15y ago
  >Beating the CAP theorem inside the data center is fairly easy in practice by using a 2-tiered system. >Have a set of lightweight controller processes which use a consistent majority voting algorithm (Paxos, Consistency, Partition Tolerance) to replicate the state of the cluster. Since it's lightweight, you can run 5 or 7 of them, meaning 2 or 3 can die. This is more than enough Availability in practice, per customer input. it isn't beating of the CAP theorem. It is decreasing the Partition Tolerance and thus getting more Availability while preserving Consistency in full accordance with CAP.
iandanforth 15y ago
A few days ago I posted my frustration with Cassandra counters, this article articulates a solution elegantly: 'if you make a mistake or something goes wrong in the realtime layer, the batch layer will correct it.' The resiliency of this protection however is limited by the time it takes to do a full re-processing of the historical data. If there is a processing mistake in your real-time layer, it is likely to exist in your batch layer as well, thus invalidating the pre-computed results as well.
- nathanmarz 15y ago
  But you can always correct the mistake and recompute things. Unlike systems based on mutable data, mistakes aren't permanent.
  - ww520 15y ago
    If the transaction log is kept for the mutable system, you can always replay the transaction to arrive at the correct state. Most systems truncate the transaction log after a checkpoint to save space. If space is not an issue, you can always keep the transaction log since the beginning.
pdbne 15y ago
I'm not sure if you're trolling here: > The CAP theorem has been beaten. > As you are about to see, a system like this not only beats the CAP theorem, but annihilates it. The CAP theorem states that you can't have all three of strong consistency, partition tolerance, and availability at once. This is a proven fact (http://www.cs.cornell.edu/courses/cs6464/2009sp/papers/brewer.pdf http://www.cs.cornell.edu/courses/cs6464/2009sp/papers/brewe...). I don't see how your proposed system provides strong consistency. Eventual consistency is not strong consistency. Let's pretend the HDFS deployment in your batch workflow is partitioned from the rest of the system: sorry, but you won't be able to get strongly consistent data from it, and you'll have to either read stale data or simply block until the partition ends. This is pedantic, the CAP theorem is pretty specific. Now, if you're saying something about the eventual consistency of logically monotonic facts in the system (see the CALM conjecture, now theorem: http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/ http://databeta.wordpress.com/2010/10/28/the-calm-conjecture...), which I think you are, then I agree that you have a system providing (even provable) eventual consistency. The basic idea is that if code is logically monotonic, meaning the set of facts it operates on continues to grow over time, then it will obey eventual consistency properties. If I'm not mistaken, your notion of "immutable data" is equivalent to restricting programs to operate on logically monotonic data (in your examples, this is accomplished by making data take the form "fact X is true at time T").
- nathanmarz 15y ago
  I never said anywhere that it provides strong consistency. You still choose between availability and consistency. What you beat is the complexity the CAP theorem normally causes. You regain the ability to easily reason about your systems. "There is another way. You can't avoid the CAP theorem, but you can isolate its complexity and prevent it from sabotaging your ability to reason about your systems." "What caused complexity before was the interaction between incremental updates and the CAP theorem. Incremental updates and the CAP theorem really don't play well together; mutable values require read-repair in an eventually consistent system. By rejecting incremental updates, embracing immutable data, and computing queries from scratch each time, you avoid that complexity. The CAP theorem has been beaten."
lenary 15y ago
I love that research is going into disproving already superseded theories.
dr_rezzy 15y ago
Great write up. You really nail the essence of a true data driven approach (DDA) to solving problems. Simplification of the data world view can lead to great things. The key to your batch computation example is proper data modeling IMO. This leads to flexibility which is crucial for a design to be successful. I feel people will stumble with the content of this post because of the lack of proper understanding of DDA.
relaunched 15y ago
While I don't have an answer on how to beat CAP theorem...I know someone who is working on it as we speak, as well as many other issues associated with the cloud. View his tweet below: @eric_brewer Eric Brewer I will be leading the design of the next gen of infrastructure at Google. The cloud is young: much to do, many left to reach. 10 May via web
jgavris 15y ago
'How to tolerate CAP, according to application / system specifications..'
balakk 15y ago
If I am not completely mistaken, the pattern that's being hinted is called Command-Query Responsibility Segregation(CQRS) in certain circles: http://cqrsinfo.com/documents/cqrs-introduction/ http://cqrsinfo.com/documents/cqrs-introduction/ While making the problem easier, I do not know if this actually "solves" the CAP theorem issues.
- joeyespo 15y ago
  At a high level, CQRS is simply separating your reads from your writes. It follows the observation that most web-related DB queries are in the form of reads and much fewer writes. I don't know about solving the CAP theorem, but it does a very nice job of scaling horizontally.
gfodor 15y ago
Nice post! To me, the logical next step is a mathematical framework for proving that all major relational operators (and in partition intolerant mode, ACID) can be implemented using this approach -- if such a model can be cleanly laid out it could drive the future of database systems.
mononcqc 15y ago
This doesn't beat the CAP theorem. The approach can be quickly described as a log-based append-only database with read-repair code based on last-write-wins. The system will have inconsistent views for the whole time a netsplit lasts. If I have two nodes, A and B, and that they both hold a piece of data related to a meeting M0 at 11 on Monday, then a netsplit happens, the strategy suggested won't help with the following case: Jim and Peter have access to node A, and Mary and Julie have access to the node B. Because there is a netsplit between A and B, communication is impossible there. However, Jim and Peter agree to move the meeting M0 to 3PM on Monday, and we call it {A,M1}. Mary and Julie, however, agree to move the meeting to 1PM on Tuesday. We call it {B,M1}. Now, the M1 record on A and B is no longer the same. If the netsplit isn't resolved before Monday, then inconsistent data will have caused the loss of our team meeting! When the netsplit is resolved and we consult the meeting, the approach of the blog post will pick either B's version of M1 or A's version of M1 based on the map-reduce we've had. To the reader, we'll have discarded either of them. This is why the last write wins -- it's the latest state in the log of events, the other one is ignored. Last-write-wins is a default mode to be used on read-repair, and nothing solving the problem of losing consistency. During the netsplit, views of the data remain inconsistent. The way to keep them consistent would have been to have A and B blocking writes. As such, we would have kept Jim, Peter, Julie and Mary from writing new meeting times and made sure that they all had the same hour presented. An easy way to test whether you beat the CAP theorem or not is to imagine your system functional during a week-long netsplit. Either it keeps on working with inconsistent data, or it has a way to keep it consistent. The CAP theorem tells us it's impossible to do both at once, and the blog post didn't disprove that, but merely provided a way to resolve conflicts in data in an automatic way. I would expect someone to 'beat' the CAP theorem as much as I would expect someone to 'beat' the Pythagorean theorem. The blog is interesting in its own approach to make the CAP theorem simpler to handle, but misses its own point of beating it.
Uchikoma 15y ago
Beating the CAP theorem by proofing it by dropping the requirement for consistency? Sorry to be conservative and following Aristotelean logic, but this title does not make sense.
- lmm 15y ago
  Indeed, it's not quite "beating". "How to get full availability and eventual consistency (the best you can do under CAP) with no effort in the application layer" might have been a truer title. Nevertheless, this is something useful.
curveship 15y ago
Thanks for the long and interesting article. Two comments, one an observation I'd be interested in hearing your response to, the second a bit of a devil's advocate question. First, in your write-up, you describe data as singular, but of course, it's often a tuple. To take a concrete example, let's say that Sally, in order to make her move from Atlanta to Chicago, goes to U-Haul's website and reserves a 14' truck for Monday. She thinks a bit more and decides that she needs a bigger truck, so she goes to the site and changes her reservation to a 17' truck. After even more thinking, she decides she really won't be ready by Monday, so she changes her reservation date to Tuesday. Let's call these three moments t0, t1 and t2. So her order has changed from: t0: 14' truck, Monday t1: 17' truck, Monday t2: 17' truck, Tuesday BUT, it so happens that U-Haul has implemented a datastore like you suggest, one that is only "eventually consistent", and when Sally made her change at t2, the node she was talking to hadn't heard yet about the switch from a 14' to a 17' truck. So the actual tuples that were recorded were: t0: 14' truck, Monday t1: 17' truck, Monday t2: 14' truck, Tuesday Now you're in a pickle: how can you tell that the record stored at t2 was partially out of date, verses the possibility that maybe Sally really did want to change back to a 14' truck at the same time she changed the date to Tuesday. To solve this, you need to do two things: the table that records new items is different from the ones that record updates, in that the new item tables contain full tuples, while the update tables are radically normalized, to the extent that they'll usually have just two columns: a key and an atomic replacement value. So what we'd actually record is: t0: 14' truck, Monday in the "new reservation" table t1: 17' truck in the "reservation item change" table t2: Tuesday in the "reservation date change" table I don't have any knee-jerk opposition to a schema like that, but it seems to me you'll run into two issues: - all the usual issues with extreme normalization, like performance and massive and complicated joins. And since, as I understand it, your realtime iterative db is consuming the same data stream as your main store, it will face this same performance penalty, at least in its input. - your schema darn well better be in BCNF, or enforcing data constraints across the hyper-normalized update tables is going to get very hairy very fast. Like here, let's say that U-Haul has a policy that it never rents 17' trucks on Tuesdays (I don't know why, maybe they wash them on Tuesdays). Since when Sally made her switch to Tuesday, the node she was talking to thought she was still renting a 14' truck, it was happy to record the change. But when your batch process comes along and tries to resolve the two updates, what does it do? There's no obvious answer (going with the last consistent state -- 17' for Monday -- is certainly wrong, as we know that's no longer what Sally wants). In other words, you're back in the "read repair" complexity and hell you thought you'd avoided. Second point ... eh, I think I've well overspent my word budget. In summary: a devil's advocate would say that the realtime db you've called just an "optimization" is, in fact, the real db, since if the realtime and batch dbs differ, at least at any time other than when a new batch update lands, then you'll go with the value from the realtime db (if, during normal operation, batch says a count is 4 but realtime says 5, you report 5). So what you've really done is attached a fairly massive auditing system onto the same-old database design. Its job is to periodically check that no inconsistencies have been introduced between nodes. It's a clever auditing system, in that the immutable model means it may have a leg up on deciding what the right result is, but still just an auditing system. tl;dr: won't this lead to hyper-normalization, and is it really a new db design or just a new kind of auditing system edit: formatting, tl;dr

183 points by icey 15y ago

rxin 15y ago

Good write up, Nathan. Nonetheless, you started by saying you were going to challenge the basic assumptions of how data systems should be built, but the resulting system architecture is in fact very similar to a lot of data streaming systems that the academia and industry have proposed and built for a number of years. An example of such system is Google's Percolator [1]. In essence, you separate the system into two parts, a read-only part and a real-time part. CAP explains fundamental trade-offs in OLTP type of queries, whereas this system design is catered towards streaming, analytical queries. These are two very different contexts. [1] http://research.google.com/pubs/pub36726.html http://research.google.com/pubs/pub36726.html

nathanmarz 15y ago
I was under the impression that Percolator was a purely incremental system. I'll have to give the paper another read to see if they're using a hybrid batch/realtime approach. The system I described isn't limited to any particular "type" of query. It's a way of supporting arbitrary queries on arbitrary data, which encapsulates everything. Most people assume mutable state and incremental updates when building data systems. This is in fact the approach that almost all databases take. These are the assumptions I challenged.
- VladRussian 15y ago
  >Most people assume mutable state and incremental updates when building data systems. This is in fact the approach that almost all databases take. These are the assumptions I challenged. it isn't assumptions. It is requirements for some systems. You drop requirements - you get a breathing room and can build a different system.
  - nathanmarz 15y ago
    Mutability and incremental updates are never requirements. Requirements have to do with performance and resource usage: X amount of space, Y amount of memory, Z amount of latency, etc. Mutability and incremental updates are approaches. I showed a different approach with immutability at the core which leads to a system with some amazing properties.
    - eru 15y ago
      I hope that examples like this and git make more people see the value of immutability. In the context of functional programming the same concept is called purity.

heyrhett 15y ago

Wow, this article is full of clear, coherent, well thought out points... and references!

ww520 15y ago

OP adds confusion by calling data immutable. Data has a well accepted common usage of being updatable. Event is the term what OP wants. Event is a snapshot of fact happened in time and cannot be changed and it's immutable. What OP described in general is the append-log based approach to storing and querying data. There are a whole bunch databases and file systems built on the append-log idea. It's well worth the time to check out the research in this area to see the benefits and pitfalls of the approach. Also check out the Complex Event Processing topic which bears similarity to what OP described.

nathanmarz 15y ago
Like I said, I was going to break your assumptions on data systems. Treating data as mutable (whether you use MVCC or append logs or any other approach) leads to major complexity problems, as I detailed in the post.
- ww520 15y ago
  Redefining the meaning of general term just creating more confusion about the point you want to make. Why not use precise definition. The term "data" is really really general and it's bad to convey what you really mean. Are you talking about data value? Data object? Data record? Data version? Data event? Quoting from your blog, "A piece of data is a fact that you know to be true at some moment of time." That's called an Event. That's a snapshot of fact in time. MVCC is one way to do transaction. The blog didn't deal with transaction at all so I don't see the comparison. Append log-based databases do the closest to what you described in avoiding changing data in place and recompute/precompute data at query time. It's a very simple mechanism. What complexity problem do you see with it?
RickHull 15y ago
> OP adds confusion by calling data immutable. Data has a well accepted common usage of being updatable. I find this point to be generally contentious. Certainly in the realm of programming languages, data is often held immutable. I think mutable vs. immutable data is an important distinction with wide-ranging implications, so I find being explicit here adds clarity rather than confusion.

seabee 15y ago

I wrote my thesis on an immutable data store as a means to beat CAP. I didn't get quite as far as your other observations though, as mine was in the context of continuation web frameworks. Very nice write-up however.

nathanmarz 15y ago
Thank you. Got a link to your thesis anywhere? Would love to read it.
- seabee 15y ago
  It's not in a state I would like to make public yet. Sufficient to get my degree, but the quality is poor due to personal circumstances. However I sent you a link via your contact form.

chrisdew 15y ago

This looks like Event Sourcing / CQRS. Is that correct?

nathanmarz 15y ago
There are similarities. It's really closer to functional programming than anything else.

perlgeek 15y ago

> The key is that data is immutable. Immutable data means there's no such thing as an update, so it's impossible for different replicas of a piece of data to become inconsistent. I'm not following that point. Suppose you have an event-souring data store as the OP suggests, and some nodes go out of sync. So one of the nodes records that Sally now lives in Atlanta, the other doesn't. The query for Sally's location asks for the last update. One node says Atlanta, the other still says Chicago. What's that, if not inconsistent? Only appending data means you don't corrupt old data, but you still can get conflicting responses from different parts of your system.

herge 15y ago
You add a version number or timing information to each update. Node A says Atlanta, with version 42. Node B says Chicago, with version 41. 42 > 41, so you go with Atlanta.
- VladRussian 15y ago
  when you have fault in the system so you can't access node A, node B returns Chicago with version 41 and you proceed with it if your system choice is Availability at the price of Consistency, or you wait for the node A if you choice Consistency at the price of Availability.
IgorPartola 15y ago
This is the key point. You either set your writes to be synchronous or asynchronous, depending on whether you want consistency or high availability. The point of having no updates means that you have less possibility for conflicts when sites A and B are appended to simultaneously. This means robust replication even with async writes.
nathanmarz 15y ago
What you're describing is a query. "What is Sally's current location?" Queries can be inconsistent during partitions. This is what eventual consistency means. But once the partition clears, the queries will be consistent again. The data is immutable. Both "Sally lives in Atlanta as of time X" and "Sally lives in Chicago as of time Y" are true. This is far, far different from databases based on mutable state. In order for a database like that to be eventually consistent, you need to do read-repair to enforce consistency. This is besides the other problems I brought up with mutable databses, such as a lack of human fault-tolerance.

pierrebai 15y ago

How does the system deal with real-world data that has cross-datum consistency requirements? Many system mnodeling real-world have this issue: accounting, inventory, ... I'm also annoyed by the repeated mantra that you must have partition tolerance. In fact, most naïve systems are designed without it, with some central authority that must always be accessible. (Any system that is stricly a tree with an essential root node is like that. Any partition that does not include the root node cannot do any work, thus the system is not partition tolerant.) You can then have CA (by requiring that all requests and updates must propagate to the root.)

IgorPartola 15y ago
You then do not have the A part of CA. Your root node is not accessible => your entire system is not accessible.
nathanmarz 15y ago
The system computes functions on all the data you have. That describes every possible data system. In the realtime layer where you compensate for the last few hours of data, you'll need an incremental strategy to maintain that "cross-datum" consistency.

Maro 15y ago

In practice, beating the CAP theorem inside the data center is achieved by using a 2-tiered system. Have a set of lightweight controller processes which use a consistent majority voting algorithm (Paxos) to replicate the state of the cluster. Since it's lightweight, you can run 5 or 7 of them, meaning 2 or 3 can die. This is enough Availability in practice, per customer input. Have a set of data nodes which actually store the data. Put groups of 3 of these in replica sets and use consistent replication (Paxos). If one or two of them goes down, the controllers reconfigure the replica set, so you get Availability even if 2 of 3 goes down. (Customers love that they get Consistency but 2 of 3 can go down.) This scheme is used in my company's product. The idea comes from academic/Google papers, and is used in other products, too. The scheme does not work for multi-datacenter use-cases. If you want that, you have to give up consistent replication (Paxos) inside the replica sets and use some kind of eventual consistency. This variation of the 2-layered scheme is used by one of the popular competing NoSQL systems.

VladRussian 15y ago
>Beating the CAP theorem inside the data center is fairly easy in practice by using a 2-tiered system. >Have a set of lightweight controller processes which use a consistent majority voting algorithm (Paxos, Consistency, Partition Tolerance) to replicate the state of the cluster. Since it's lightweight, you can run 5 or 7 of them, meaning 2 or 3 can die. This is more than enough Availability in practice, per customer input. it isn't beating of the CAP theorem. It is decreasing the Partition Tolerance and thus getting more Availability while preserving Consistency in full accordance with CAP.

iandanforth 15y ago

A few days ago I posted my frustration with Cassandra counters, this article articulates a solution elegantly: 'if you make a mistake or something goes wrong in the realtime layer, the batch layer will correct it.' The resiliency of this protection however is limited by the time it takes to do a full re-processing of the historical data. If there is a processing mistake in your real-time layer, it is likely to exist in your batch layer as well, thus invalidating the pre-computed results as well.

nathanmarz 15y ago
But you can always correct the mistake and recompute things. Unlike systems based on mutable data, mistakes aren't permanent.
- ww520 15y ago
  If the transaction log is kept for the mutable system, you can always replay the transaction to arrive at the correct state. Most systems truncate the transaction log after a checkpoint to save space. If space is not an issue, you can always keep the transaction log since the beginning.

pdbne 15y ago

I'm not sure if you're trolling here: > The CAP theorem has been beaten. > As you are about to see, a system like this not only beats the CAP theorem, but annihilates it. The CAP theorem states that you can't have all three of strong consistency, partition tolerance, and availability at once. This is a proven fact (http://www.cs.cornell.edu/courses/cs6464/2009sp/papers/brewer.pdf http://www.cs.cornell.edu/courses/cs6464/2009sp/papers/brewe...). I don't see how your proposed system provides strong consistency. Eventual consistency is not strong consistency. Let's pretend the HDFS deployment in your batch workflow is partitioned from the rest of the system: sorry, but you won't be able to get strongly consistent data from it, and you'll have to either read stale data or simply block until the partition ends. This is pedantic, the CAP theorem is pretty specific. Now, if you're saying something about the eventual consistency of logically monotonic facts in the system (see the CALM conjecture, now theorem: http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/ http://databeta.wordpress.com/2010/10/28/the-calm-conjecture...), which I think you are, then I agree that you have a system providing (even provable) eventual consistency. The basic idea is that if code is logically monotonic, meaning the set of facts it operates on continues to grow over time, then it will obey eventual consistency properties. If I'm not mistaken, your notion of "immutable data" is equivalent to restricting programs to operate on logically monotonic data (in your examples, this is accomplished by making data take the form "fact X is true at time T").

nathanmarz 15y ago
I never said anywhere that it provides strong consistency. You still choose between availability and consistency. What you beat is the complexity the CAP theorem normally causes. You regain the ability to easily reason about your systems. "There is another way. You can't avoid the CAP theorem, but you can isolate its complexity and prevent it from sabotaging your ability to reason about your systems." "What caused complexity before was the interaction between incremental updates and the CAP theorem. Incremental updates and the CAP theorem really don't play well together; mutable values require read-repair in an eventually consistent system. By rejecting incremental updates, embracing immutable data, and computing queries from scratch each time, you avoid that complexity. The CAP theorem has been beaten."

lenary 15y ago

I love that research is going into disproving already superseded theories.

dr_rezzy 15y ago

Great write up. You really nail the essence of a true data driven approach (DDA) to solving problems. Simplification of the data world view can lead to great things. The key to your batch computation example is proper data modeling IMO. This leads to flexibility which is crucial for a design to be successful. I feel people will stumble with the content of this post because of the lack of proper understanding of DDA.

relaunched 15y ago

While I don't have an answer on how to beat CAP theorem...I know someone who is working on it as we speak, as well as many other issues associated with the cloud. View his tweet below: @eric_brewer Eric Brewer I will be leading the design of the next gen of infrastructure at Google. The cloud is young: much to do, many left to reach. 10 May via web

jgavris 15y ago

'How to tolerate CAP, according to application / system specifications..'

balakk 15y ago

If I am not completely mistaken, the pattern that's being hinted is called Command-Query Responsibility Segregation(CQRS) in certain circles: http://cqrsinfo.com/documents/cqrs-introduction/ http://cqrsinfo.com/documents/cqrs-introduction/ While making the problem easier, I do not know if this actually "solves" the CAP theorem issues.

joeyespo 15y ago
At a high level, CQRS is simply separating your reads from your writes. It follows the observation that most web-related DB queries are in the form of reads and much fewer writes. I don't know about solving the CAP theorem, but it does a very nice job of scaling horizontally.

gfodor 15y ago

Nice post! To me, the logical next step is a mathematical framework for proving that all major relational operators (and in partition intolerant mode, ACID) can be implemented using this approach -- if such a model can be cleanly laid out it could drive the future of database systems.

mononcqc 15y ago

This doesn't beat the CAP theorem. The approach can be quickly described as a log-based append-only database with read-repair code based on last-write-wins. The system will have inconsistent views for the whole time a netsplit lasts. If I have two nodes, A and B, and that they both hold a piece of data related to a meeting M0 at 11 on Monday, then a netsplit happens, the strategy suggested won't help with the following case: Jim and Peter have access to node A, and Mary and Julie have access to the node B. Because there is a netsplit between A and B, communication is impossible there. However, Jim and Peter agree to move the meeting M0 to 3PM on Monday, and we call it {A,M1}. Mary and Julie, however, agree to move the meeting to 1PM on Tuesday. We call it {B,M1}. Now, the M1 record on A and B is no longer the same. If the netsplit isn't resolved before Monday, then inconsistent data will have caused the loss of our team meeting! When the netsplit is resolved and we consult the meeting, the approach of the blog post will pick either B's version of M1 or A's version of M1 based on the map-reduce we've had. To the reader, we'll have discarded either of them. This is why the last write wins -- it's the latest state in the log of events, the other one is ignored. Last-write-wins is a default mode to be used on read-repair, and nothing solving the problem of losing consistency. During the netsplit, views of the data remain inconsistent. The way to keep them consistent would have been to have A and B blocking writes. As such, we would have kept Jim, Peter, Julie and Mary from writing new meeting times and made sure that they all had the same hour presented. An easy way to test whether you beat the CAP theorem or not is to imagine your system functional during a week-long netsplit. Either it keeps on working with inconsistent data, or it has a way to keep it consistent. The CAP theorem tells us it's impossible to do both at once, and the blog post didn't disprove that, but merely provided a way to resolve conflicts in data in an automatic way. I would expect someone to 'beat' the CAP theorem as much as I would expect someone to 'beat' the Pythagorean theorem. The blog is interesting in its own approach to make the CAP theorem simpler to handle, but misses its own point of beating it.

Uchikoma 15y ago

Beating the CAP theorem by proofing it by dropping the requirement for consistency? Sorry to be conservative and following Aristotelean logic, but this title does not make sense.

lmm 15y ago
Indeed, it's not quite "beating". "How to get full availability and eventual consistency (the best you can do under CAP) with no effort in the application layer" might have been a truer title. Nevertheless, this is something useful.

curveship 15y ago

Thanks for the long and interesting article. Two comments, one an observation I'd be interested in hearing your response to, the second a bit of a devil's advocate question. First, in your write-up, you describe data as singular, but of course, it's often a tuple. To take a concrete example, let's say that Sally, in order to make her move from Atlanta to Chicago, goes to U-Haul's website and reserves a 14' truck for Monday. She thinks a bit more and decides that she needs a bigger truck, so she goes to the site and changes her reservation to a 17' truck. After even more thinking, she decides she really won't be ready by Monday, so she changes her reservation date to Tuesday. Let's call these three moments t0, t1 and t2. So her order has changed from: t0: 14' truck, Monday t1: 17' truck, Monday t2: 17' truck, Tuesday BUT, it so happens that U-Haul has implemented a datastore like you suggest, one that is only "eventually consistent", and when Sally made her change at t2, the node she was talking to hadn't heard yet about the switch from a 14' to a 17' truck. So the actual tuples that were recorded were: t0: 14' truck, Monday t1: 17' truck, Monday t2: 14' truck, Tuesday Now you're in a pickle: how can you tell that the record stored at t2 was partially out of date, verses the possibility that maybe Sally really did want to change back to a 14' truck at the same time she changed the date to Tuesday. To solve this, you need to do two things: the table that records new items is different from the ones that record updates, in that the new item tables contain full tuples, while the update tables are radically normalized, to the extent that they'll usually have just two columns: a key and an atomic replacement value. So what we'd actually record is: t0: 14' truck, Monday in the "new reservation" table t1: 17' truck in the "reservation item change" table t2: Tuesday in the "reservation date change" table I don't have any knee-jerk opposition to a schema like that, but it seems to me you'll run into two issues: - all the usual issues with extreme normalization, like performance and massive and complicated joins. And since, as I understand it, your realtime iterative db is consuming the same data stream as your main store, it will face this same performance penalty, at least in its input. - your schema darn well better be in BCNF, or enforcing data constraints across the hyper-normalized update tables is going to get very hairy very fast. Like here, let's say that U-Haul has a policy that it never rents 17' trucks on Tuesdays (I don't know why, maybe they wash them on Tuesdays). Since when Sally made her switch to Tuesday, the node she was talking to thought she was still renting a 14' truck, it was happy to record the change. But when your batch process comes along and tries to resolve the two updates, what does it do? There's no obvious answer (going with the last consistent state -- 17' for Monday -- is certainly wrong, as we know that's no longer what Sally wants). In other words, you're back in the "read repair" complexity and hell you thought you'd avoided. Second point ... eh, I think I've well overspent my word budget. In summary: a devil's advocate would say that the realtime db you've called just an "optimization" is, in fact, the real db, since if the realtime and batch dbs differ, at least at any time other than when a new batch update lands, then you'll go with the value from the realtime db (if, during normal operation, batch says a count is 4 but realtime says 5, you report 5). So what you've really done is attached a fairly massive auditing system onto the same-old database design. Its job is to periodically check that no inconsistencies have been introduced between nodes. It's a clever auditing system, in that the immutable model means it may have a leg up on deciding what the right result is, but still just an auditing system. tl;dr: won't this lead to hyper-normalization, and is it really a new db design or just a new kind of auditing system edit: formatting, tl;dr