# CAP theorem **URL:** \ **Category:** Elasticsearch\ **Created:** [June 13, 2010, 4:51am UTC](https://discuss.elastic.co/t/cap-theorem/3014 "2010-06-13T04:51:17Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![talsalmona](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/talsalmona/32/3316_2.png) [@talsalmona](https://discuss.elastic.co/u/talsalmona)\ **Post date:** [June 13, 2010, 4:51am UTC](https://discuss.elastic.co/t/cap-theorem/3014/1 "2010-06-13T04:51:17Z")
Hi, According to the CAP theorem ([http://en.wikipedia.org/wiki/CAP\_theorem](http://en.wikipedia.org/wiki/CAP_theorem) and [http://books.couchdb.org/relax/intro/eventual-consistency](http://books.couchdb.org/relax/intro/eventual-consistency)), ElasticSearch can satisfy two of the following: - Consistency - Availability - Partition Tolerance My guess is Availability and Partition Tolerance are the ones supported by ElasticSearch and consistency is eventual, meaning that two clients may sometimes get different results when executing the same query. Am I right? Thanks, Tal ---
**Author:** ![Sergio\_Bossa](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/sergio_bossa/32/3312_2.png) [@Sergio\_Bossa](https://discuss.elastic.co/u/Sergio_Bossa)\ **Post date:** [June 13, 2010, 8:27am UTC](https://discuss.elastic.co/t/cap-theorem/3014/2 "2010-06-13T08:27:13Z")
On Sun, Jun 13, 2010 at 6:51 AM, Tal [talsalmona@gmail.com](mailto:talsalmona@gmail.com) wrote: > My guess is Availability and Partition Tolerance are the ones > supported by Elasticsearch and consistency is eventual, meaning that > two clients may sometimes get different results when executing the > same query. > Am I right? Nope, AFAIK (please Shay correct me if wrong) Elasticsearch provides per-document consistency, meaning that writes will be atomically executed on the "document owner" shard and synchronously replicated to replica shards. Regarding A vs P, I honestly don't know how Elasticsearch behaves in case of network partitions: Shay will surely be able to spread some light (discussion is interesting indeed). Cheers, Sergio B. -- Sergio Bossa [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![kimchy](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/kimchy/32/44952_2.png) [@kimchy](https://discuss.elastic.co/u/kimchy)\ **Post date:** [June 14, 2010, 12:29pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/3 "2010-06-14T12:29:29Z")
Hi, When it comes to CAP, in a very high level, elasticsearch gives up on partition tolerance. This is for several reasons: 1. I personally believe that \*within the same data center", network partitions very rarely happen, and when they do, its a small set (many times single) machine that gets "partitioned out of the network". When a single machine gets disconnected from the network, then thats not going to affect elasticsearch. When it come to cross data centers, a solution that gives up on consistency can be built on top of elasticsearch, either by elasticsearch (in the future), or now, by using messaging in some form to replicate changes between two data centers. 2. When it comes to search engines, and inverted index, its very hard to the point of impossible to build a solution that tries to resolve consistency problems on the fly as most products do (the famous "read repair"). When you search, you search over a large amount of docs and you can't read repair each one all the time. Key value / column based solutions have life easy.... . -shay.banon On Sun, Jun 13, 2010 at 11:27 AM, Sergio Bossa [sergio.bossa@gmail.com](mailto:sergio.bossa@gmail.com)wrote: > On Sun, Jun 13, 2010 at 6:51 AM, Tal [talsalmona@gmail.com](mailto:talsalmona@gmail.com) wrote: > > > My guess is Availability and Partition Tolerance are the ones > > supported by Elasticsearch and consistency is eventual, meaning that > > two clients may sometimes get different results when executing the > > same query. > > Am I right? > > Nope, AFAIK (please Shay correct me if wrong) Elasticsearch provides > per-document consistency, meaning that writes will be atomically > executed on the "document owner" shard and synchronously replicated to > replica shards. > Regarding A vs P, I honestly don't know how Elasticsearch behaves in > case of network partitions: Shay will surely be able to spread some > light (discussion is interesting indeed). > > Cheers, > > Sergio B. > > -- > Sergio Bossa > [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![Sergio\_Bossa](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/sergio_bossa/32/3312_2.png) [@Sergio\_Bossa](https://discuss.elastic.co/u/Sergio_Bossa)\ **Post date:** [June 16, 2010, 3:06pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/4 "2010-06-16T15:06:45Z")
On Mon, Jun 14, 2010 at 2:29 PM, Shay Banon [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > 1. I personally believe that \*within the same data center", network > partitions very rarely happen, and when they do, its a small set (many times > single) machine that gets "partitioned out of the network". When a single > machine gets disconnected from the network, then thats not going to affect > elasticsearch. More specifically, how does ES cope with partitioned nodes? Say we have 3 nodes (a, b, c) with 'c' as the master, and a partition happens as follows: (a, b) (c), how does ES behave? How does it avoid split brain problems? -- Sergio Bossa [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![kimchy](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/kimchy/32/44952_2.png) [@kimchy](https://discuss.elastic.co/u/kimchy)\ **Post date:** [June 16, 2010, 7:30pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/5 "2010-06-16T19:30:13Z")
You can't avoid split brain, it will happen once you get network partitioning, the question is how do you resolve it, and also, what the effect of the split brain is. In your scenario, once the split will happen, either (a) or (b) will become master of the sub cluster. If (c) got total disconnection, then its great, since clients won't be able to see it as well, so no data will be lost. If, on the other hand, clients got partitioned with (c) as well, then they will continue to work with (c), while other clients will work with (a) and (b). Once the network partition is resolved, then some sort of data resolution needs to occur, either by discarding the small cluster, or by doing version / conflict resolution. -shay.banon On Wed, Jun 16, 2010 at 6:06 PM, Sergio Bossa [sergio.bossa@gmail.com](mailto:sergio.bossa@gmail.com)wrote: > On Mon, Jun 14, 2010 at 2:29 PM, Shay Banon > [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > > > 1. I personally believe that \*within the same data center", network > > partitions very rarely happen, and when they do, its a small set (many > > times > > single) machine that gets "partitioned out of the network". When a single > > machine gets disconnected from the network, then thats not going to > > affect > > elasticsearch. > > More specifically, how does ES cope with partitioned nodes? > Say we have 3 nodes (a, b, c) with 'c' as the master, and a partition > happens as follows: (a, b) (c), how does ES behave? How does it avoid > split brain problems? > > -- > Sergio Bossa > [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![Sergio\_Bossa](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/sergio_bossa/32/3312_2.png) [@Sergio\_Bossa](https://discuss.elastic.co/u/Sergio_Bossa)\ **Post date:** [June 17, 2010, 8:29am UTC](https://discuss.elastic.co/t/cap-theorem/3014/6 "2010-06-17T08:29:29Z")
On Wed, Jun 16, 2010 at 9:30 PM, Shay Banon [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > You can't avoid split brain, it will happen once you get network > partitioning, Not sure about this statement. While I'm far from being a distributed systems expert, you're probably way more than me, I think the impossibility result pretty depends on the system assumptions. Clearly, it's impossible to avoid split brain in fully asynchronous networks with lost messages. But, while you're forced to keep the assumption above for partition tolerant _and_ available systems, ES doesn't aim at tolerating partitions (as you stated in your previous mail), so you can actually avoid split brains by employing quorum algorithms and tolerating only a given number of "failures" (because consistency needs to be preserved), blocking the eventually partitioned nodes until they get reconnected. You could also choose to embrace partition tolerance over availability, and adopt the solution above but avoid to block partitioned nodes and just assume a fail-stop for them, or, assign a static "owner" to a given index/shard, so that if the owner fails/gets partitioned all writes to its index/shard will be prohibited to keep consistency. > If, on the other hand, clients got > partitioned with (c) as well, then they will continue to work with (c), > while other clients will work with (a) and (b). This kind of solutions describes indeed an available and partition tolerant system, because both ends of your partition stay available and you're actually sacrificing consistency. > Once the network partition is resolved, then some sort of data resolution > needs to occur, either by discarding the small cluster, or by doing version > / conflict resolution. Which is very hard for indexed data. Moreover, if this needs to be done manually, users may actually miss inconsistencies or mess up things ... I honestly thought ES provided some kind of algorithm to avoid inconsistencies, it doesn't seem to be the case. I'm not saying it's bad, just that it's different than I expected. Thanks for your attention, Sergio B. -- Sergio Bossa [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![kimchy](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/kimchy/32/44952_2.png) [@kimchy](https://discuss.elastic.co/u/kimchy)\ **Post date:** [June 17, 2010, 12:37pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/7 "2010-06-17T12:37:11Z")
Maan, discussion for this should be done over a beer and not over emails, its very hard to convey all the different aspects and trying to write short answers just missed the point, but I will try and write something... . What I meant when I said you can't get around split brains was actually you can't avoid network partitions, the question is what you do with it, and if split brains can be avoided or not. One of the things I don't like (even in respectable projects) is the "assertions" that this product do that or do this, especially since CAP relates to point of time .... First thing to note is the fact that a search engine is very different than key value or column based storage systems. A typical search query hits huge amount of data, and you want to keep scoring correct for them without needing to "repair" each search doc per search. Another point is to differentiate between what elasticsearch does now, and what it is designed to do in its final version. It is certainly architected in a way to solve most things, and behave based on what the use decided to give up on, but its simply not implemented yet... (I will point what is not implemented later). So, one of the main problem when network partitioning happens is that you can't know if the node that got partitioned is down or not reachable, and the question is how do you handle it. It gets even worse if that node that was partitioned got partitioned with clients connected to it, that keep on working against it. It gets even more interesting in systems that reallocate shards in the event of node failure (or node getting partitioned out) as elasticsearch does. The main problem with the above is the fact that clients (that got partitioned with the offending node(s)) might still be sending data to them, and in which case you have two options. The first is to _not_ allow them to do changes (search might still be ok), and the other is to allow them to write and reconcile once the network partitioning is resolved. Lets start with not allowing writes. For that, you need to identify when writes will not be allowed. This is much simpler to do when you have a fixed location master(s), since if you lost connection to it (or to a quorum of them), you basically get into this mode. In elasticsearch there is no fixed location master OOB, so the other option is to do some sort of quorum across all the nodes in the cluster. Thats not simple, mainly because a cluster of elasticsearch might be reduced to a smaller size intentionally. One simple option to solve this is to have the user define a "minimum" size of cluster that should be up, and if its not, the nodes will not allow writes. This will be in elasticsearch and its actually not that difficult to implement. This actually solves a lot of cases. Assuming you managed to identify it and block writes, then resolving the network partitioning once it is solved is simple, you just treat the other nodes as fresh ones. As a side note, elasticsearch is architected in a way that implementing fixed location masters should be possible, and then you can easily implements "big table"/"hadoop" like solution. This will also be available as an option in the GA elasticsearch version. Yet another option is to allow writes always, and reconcile changes when a network partitioning is resolved. This can be solved in elasticsearch case by adding version/timestamp for each doc indexed, and the reconciliation will occur when the network partitioning is resolved (and not do read repair). Two identical shards, one from each network partition area, will get reconciled based on the changes done to them (either through versioning / vector clock / timestamp). The typical problem with this is handling deletes, usually by adding delete markers (tombstone) but there is full proof solution for this since you will need to delete those at some point (its explained, in cassandra case, here: [http://wiki.apache.org/cassandra/DistributedDeletes](http://wiki.apache.org/cassandra/DistributedDeletes)). This is also something that I do want to support in elasticsearch, but more into the future. Hope the above make sense, and explain things (I skipped some things, otherwise this email will need to be turned into a book 😉 ). Let me finish with a personal rant. My problem with CAP theorem is that it seems so simple, 3 simple rules that only two can be realized , that people make the mistake of really simplifying distributed systems and missing a lot of "fine prints" in those systems. My other problem is with the dynamo paper, which again, really simplifies distributed systems and is, IMO, a patch built on top of another patch. I would say that if Amazon would have written "dynamo paper, the revenge of Mr. Vogel", it would have been much much longer ;). For example, not many people are aware of Cassandra delete handling, and the fact that they might get lost. You can insert and then delete, and that delete might get lost because of its deletion handling. Another problem is that inserts might get lost as well..., with hinted handoff. Or couchdb, that looses all the "history" of changes once a compaction occurs, so you can't really resolve changes properly once a compaction has run. And this list goes on for other solutions. Or with terractotta, where not using sync writes (which syncs to disk) means that you might loose data in the event of a failure (as far as I know). Or if you don't have enough mem to get berkley btree nodes loaded into them. Or when you go server with hot backup, and what happens when they get partitioned (what really happens, btw? you are more of a terracotta expert than myself..., even more interesting is what happens with server arrays). I am not saying that those are not good products, and I would even say that you probably have to solve things in the manner that they chose to solve them, but, those "fine prints" are things that typical users won't know and assume that those products are "magical" almost as much as the ipad. -shay.banon On Thu, Jun 17, 2010 at 11:29 AM, Sergio Bossa [sergio.bossa@gmail.com](mailto:sergio.bossa@gmail.com)wrote: > On Wed, Jun 16, 2010 at 9:30 PM, Shay Banon > [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > > > You can't avoid split brain, it will happen once you get network > > partitioning, > > Not sure about this statement. > While I'm far from being a distributed systems expert, you're probably > way more than me, I think the impossibility result pretty depends on > the system assumptions. > Clearly, it's impossible to avoid split brain in fully asynchronous > networks with lost messages. > But, while you're forced to keep the assumption above for partition > tolerant _and_ available systems, ES doesn't aim at tolerating > partitions (as you stated in your previous mail), so you can actually > avoid split brains by employing quorum algorithms and tolerating only > a given number of "failures" (because consistency needs to be > preserved), blocking the eventually partitioned nodes until they get > reconnected. > You could also choose to embrace partition tolerance over > availability, and adopt the solution above but avoid to block > partitioned nodes and just assume a fail-stop for them, or, assign a > static "owner" to a given index/shard, so that if the owner fails/gets > partitioned all writes to its index/shard will be prohibited to keep > consistency. > > > If, on the other hand, clients got > > partitioned with (c) as well, then they will continue to work with (c), > > while other clients will work with (a) and (b). > > This kind of solutions describes indeed an available and partition > tolerant system, because both ends of your partition stay available > and you're actually sacrificing consistency. > > > Once the network partition is resolved, then some sort of data resolution > > needs to occur, either by discarding the small cluster, or by doing > > version > > / conflict resolution. > > Which is very hard for indexed data. Moreover, if this needs to be > done manually, users may actually miss inconsistencies or mess up > things ... > > I honestly thought ES provided some kind of algorithm to avoid > inconsistencies, it doesn't seem to be the case. I'm not saying it's > bad, just that it's different than I expected. > > Thanks for your attention, > > Sergio B. > > -- > Sergio Bossa > [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![Sergio\_Bossa](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/sergio_bossa/32/3312_2.png) [@Sergio\_Bossa](https://discuss.elastic.co/u/Sergio_Bossa)\ **Post date:** [June 17, 2010, 4:07pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/8 "2010-06-17T16:07:41Z")
On Thu, Jun 17, 2010 at 2:37 PM, Shay Banon [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > Maan, discussion for this should be done over a beer and not over emails, > its very hard to convey all the different aspects and trying to write short > answers just missed the point, but I will try and write something... . I know, I know, but "a few" miles separate us, so no beers and chats, and the only things remaining are emails 😉 You gave a very satisfying and informative answer, and I think it's actually very important for ES end users: because they may think ES is magical (like the iPad as you said), but it isn't. It currently sacrifice consistency in case of partitions in the terms you explained, and you are planning to implement a bunch of cool features to make ES suit different needs: those are all important bits of information, and I think users will be grateful for them. At least, I am 😉 Thanks, Cheers! Sergio B. -- Sergio Bossa [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![kimchy](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/kimchy/32/44952_2.png) [@kimchy](https://discuss.elastic.co/u/kimchy)\ **Post date:** [June 19, 2010, 9:55pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/9 "2010-06-19T21:55:57Z")
Well, next time I am in Rome (well, never been, so first time I will be there 😉 )... . Happy the answers make sense, btw, you did not answer regarding the terracotta ones, this is something that I always wanted to know about but could not find anything in the docs... . -shay.banon On Thu, Jun 17, 2010 at 7:07 PM, Sergio Bossa [sergio.bossa@gmail.com](mailto:sergio.bossa@gmail.com)wrote: > On Thu, Jun 17, 2010 at 2:37 PM, Shay Banon > [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > > > Maan, discussion for this should be done over a beer and not over emails, > > its very hard to convey all the different aspects and trying to write > > short > > answers just missed the point, but I will try and write something... . > > I know, I know, but "a few" miles separate us, so no beers and chats, > and the only things remaining are emails 😉 > > You gave a very satisfying and informative answer, and I think it's > actually very important for ES end users: because they may think ES is > magical (like the iPad as you said), but it isn't. > It currently sacrifice consistency in case of partitions in the terms > you explained, and you are planning to implement a bunch of cool > features to make ES suit different needs: those are all important bits > of information, and I think users will be grateful for them. At least, > I am 😉 > > Thanks, > Cheers! > > Sergio B. > > -- > Sergio Bossa > [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![Sergio\_Bossa](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/sergio_bossa/32/3312_2.png) [@Sergio\_Bossa](https://discuss.elastic.co/u/Sergio_Bossa)\ **Post date:** [June 20, 2010, 1:37pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/10 "2010-06-20T13:37:46Z")
On Sat, Jun 19, 2010 at 11:55 PM, Shay Banon [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > Well, next time I am in Rome (well, never been, so first time I will be > there 😉 )... . Anytime 😉 > Happy the answers make sense, btw, you did not answer > regarding the terracotta ones, this is something that I always wanted to > know about but could not find anything in the docs... . Sorry, missed your questions 🙂 Anyways, Terracotta should work as follows: 1. In case of client or server failure, using async writes, there's no data loss provided you run an active/passive pair: the passive one will take the transaction over and complete it as the new active. 2. In case of active/passive server partitioning, the currently active one will keep its clients connected with, while the passive one will elect itself as a master, but with no attached clients, and there will be so no split brain; once the partition heals again, the server which kept the attached clients will zap the other one and downshift it to passive state. In the end, you could have a split brain only if you had one server and a bunch of clients on one switch, and another server and another bunch of clients on another switch, and the switches get partitioned ... a pretty bizarre network configuration, provided you're not running in the cloud ... so, Terracotta also has its own split brain vulnerabilities, which are IMHO less common than the ES ones, but Terracotta is master based so it's easy to manage coordination, while ES is decentralized and yadda-yadda-yadda ... you get the idea 🙂 Hope that answers your questions ... feel free to ask more obviously 😉 Cheers! Sergio B. -- Sergio Bossa [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![kimchy](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/kimchy/32/44952_2.png) [@kimchy](https://discuss.elastic.co/u/kimchy)\ **Post date:** [June 20, 2010, 9:56pm UTC](https://discuss.elastic.co/t/cap-theorem/3014/11 "2010-06-20T21:56:00Z")
Interesting. First of all, in most cases, you have both es clients ("native clients") and the nodes within the same network switch, so the changes are identical to terracotta for split brain with clients. So, now I understand, TC has sync replication between active and passive servers, and writing to disk (in async manner, I presume). Yet another question in the TC case then. Lets assume you have two server, active and passive, both, I assume, write to the local disk their state. Now, you bring down the active server, the passive becomes active (master), and clients starts writing to new active server. Now, I bring down the last server, which is active, and afterwards, start the first server, which, I assume, becomes active and starts to receive client requests. Now, that server has an old view of the data, since clients have been performing changes to the other server while it was down. How does TC recover from that? -shay.banon On Sun, Jun 20, 2010 at 4:37 PM, Sergio Bossa [sergio.bossa@gmail.com](mailto:sergio.bossa@gmail.com)wrote: > On Sat, Jun 19, 2010 at 11:55 PM, Shay Banon > [shay.banon@elasticsearch.com](mailto:shay.banon@elasticsearch.com) wrote: > > > Well, next time I am in Rome (well, never been, so first time I will be > > there 😉 )... . > > Anytime 😉 > > > Happy the answers make sense, btw, you did not answer > > regarding the terracotta ones, this is something that I always wanted to > > know about but could not find anything in the docs... . > > Sorry, missed your questions 🙂 > Anyways, Terracotta should work as follows: > > 1. In case of client or server failure, using async writes, there's no > data loss provided you run an active/passive pair: the passive one > will take the transaction over and complete it as the new active. > 2. In case of active/passive server partitioning, the currently active > one will keep its clients connected with, while the passive one will > elect itself as a master, but with no attached clients, and there will > be so no split brain; once the partition heals again, the server which > kept the attached clients will zap the other one and downshift it to > passive state. > In the end, you could have a split brain only if you had one server > and a bunch of clients on one switch, and another server and another > bunch of clients on another switch, and the switches get partitioned > ... a pretty bizarre network configuration, provided you're not > running in the cloud ... so, Terracotta also has its own split brain > vulnerabilities, which are IMHO less common than the ES ones, but > Terracotta is master based so it's easy to manage coordination, while > ES is decentralized and yadda-yadda-yadda ... you get the idea 🙂 > > Hope that answers your questions ... feel free to ask more obviously 😉 > Cheers! > > Sergio B. > > -- > Sergio Bossa > [http://www.linkedin.com/in/sergiob](http://www.linkedin.com/in/sergiob) ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [July 6, 2017, 4:23am UTC](https://discuss.elastic.co/t/cap-theorem/3014/12 "2017-07-06T04:23:08Z")