The CAP Theorem

-
The first explanation I heard about the CAP Theorem reduced it to "consistency, availability, network partition tolerance: pick two out of three". However, as catchy as this statement was, I discovered that it wasn't accurate. In fact, the CAP Theorem has been widely misunderstood and misused since it was named in 2000 and formalized in 2002. In this blog post, I'll compile and clarify what I have learned from papers, blogs, books, and my distributed systems engineering class.

C, A, and P 

Let's define each of the letters before talking about the CAP theorem.

Consistency

Gilbert's and Lynch's 2002 paper considers only the linearizability consistency model. Linearizability is a guarantee on individual reads and writes of a single object. A total order on all operations must exist such that each operation appears to have executed instantly and atomically at some point between when it was called and when it sent back a response.

Time constraint for linearizability. Assume the value of x is initially 0. The blue bars are Client 1's requests. The red bars are Client 2's requests. 
Specifically,  the total order must follow two kinds of constraints:
  1. Time. Non-concurrent operations must obey real time constraints. For example, the first scenario in the diagram shows how reads that return before a write is called must return the old value. The second scenario in the diagram shows how reads that are called after a write returns must return the new value. Finally, in the third scenario, the read and write are concurrent (overlapping), so the read may return either the old value or the new value. 
  2. Value. Once a read returns some value, later reads must also return that value (or the value of a later write).
Note: Linearizability and serializability are two different concepts! Serializability is a property of transactions involving isolation. While linearizability concerns a single object, serializability is about potentially multiple objects. A system with serializable transactions is one where transactions appear to run serially even though they may have run concurrently in reality. In fact, serializability is the strongest isolation level.  

Availability

Availability means that "every request received by a non-failing node in the system must result in a response" eventually. Note that this means any node. If a client is disconnected from a leader in a single-leader system,  

Network Partition Tolerance 

Network partitions are not a design feature - they will happen in every distributed system. They are defined as faults where nodes are alive but disconnected from one another over an asynchronous network. 

What is the CAP Theorem? 

A distributed system cannot be both consistent and available. 

CP

Under network partitions, applications that need to be linearizable may become unavailable. For example, they may return an error, or wait until the network is up again. 

AP 

Under network partitions, applications that remain unavailable can continue to respond to requests despite nodes being disconnected from other. (Each node can continue to respond to requests independently.) 

What are the limits of the CAP Theorem? 

Criticism of relying too heavily and simplistically on the CAP Theorem (e.g. from Stonebraker, Abadi, Kleppmann), can be summarized as:
  • The CAP Theorem doesn't cover many, many types of errors that are frequently encountered in real world distributed systems. For example, nodes that went down, human errors, and application errors are not covered. 
  • Designing a distributed system should not boil down to such a simple statement. There are many complicated tradeoffs to make. 
  • Using the CAP Theorem to automatically give up consistency is bad practice. As Stonebraker wrote, "In the real world, giving up consistency does not improve availability. Hence, you are giving up consistency in exchange for nothing. This is a horrible engineering tradeoff, and the CAP theorem, therefore, encourages engineers to make awful decisions." This is because network partitions don't happen as often as other errors, so giving up consistency doesn't give us anything in return. 

Conclusion 

The CAP Theorem should be used with caution when working with distributed systems because it can be misleading, and is specific to network partition faults. However, it was historically influential, especially for the NoSQL databases trend. 

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each i...
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized...
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients s...
Read more