Eric Brewer presented CAP in a keynote at the PODC. The best slides are on page 4. With XA you forfeit partitions and get CA (consistency + availability). With majority protocols you forfeit availability and get CP (consistency + partition tolerance). XA == CA is easy for me to remember and then I know that majority protocols provide CP.
CAP was proved in a paper by Gilbert and Lynch. This paper defines availability and partition tolerance as used by CAP.
- availability - every request received by a non-failing node must result in a response
- partition tolerance - The network will be allowed to lose arbitrarily many messages sent from one node to another. Every node receiving a request from a client must respond, even though arbitrary messages that are sent may be lost.
What does this have to do with MySQL? I think we will be talking about CAP much more in the future. I found an interesting presentation that explained current MySQL solutions (DRBD, master-slave, master-master, NDB/Cluster) in terms of CAP, but it didn't have enough notes to explain the content.
Posts
In the worst case you cannot have all three. But for the most common partitioning events, the "majority protocols" can keep running. For example, when a single node becomes partitioned, they keep running. That's the most common failure. If you have three data centers, the most common failure is that one of the data centers becomes separated.
ReplyDeleteAlso, not all "majority protocols" actually require a majority to keep going. For example Paxos needs a quorum (which have the property that any two quora must interesect). A majority is clearly a quorum, but there are other sets of quora. For example, in a two dimensional grid, if you define a quorum to include an entire row and an entire column, then all pairs of quora intersect, but you only need O(sqrt(N)) members.