CAP Theorem

  • CAP
  • CAP Theorem
  • Consistency, Availability, Partition tolerance
Image of Author
October 12, 2022 (last updated April 28, 2023)

CAP stands for Consistency, Availability, and Partition tolerance. The CAP Theorem approximately states that you can only have any two of these three desirable features in a distributed data store.

The definition of these three terms can be vague. As of this writing, the wikipedia article on CAP Theorem defines them as follows:

Consistency: Every read receives the most recent write or an error.

Availability: Every request receives a (non-error) response, without the guarantee that it contains the most recent write.

Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

In a distributed data system, partitions are a given. Therefore, there will be at least some delay between nodes in the distributed data system. This means that you must have partition tolerance. So, the real tension is between consistency and availability.

As a quick example, let's say we are both using software that depends on the same distributed data store that contains at least two nodes, node-1 and node-2. We each are reading from different nodes. You click "+" on your software which sends a write request to increment a number. Node-1 updates. We then both submit a read request for that number, yours to node-1, and mine to node-2. Importantly, at this time, node-1 has not propagated the update to node-2. What should the results of my read request to node-2 be? Arguably, if we optimize for consistency, node-2 should wait for the update to its node before sending a response. This waiting effects availability, but ensures consistency. If we instead optimize for availability, I would send the old number immediately, and eventually send the new number once my node was updated. The CAP Theorem rigorously encapsulates this tensions.

Consistency in ACID

The Wikipedia Page on ACID redirects to the Wikipedia Page on Consistency (database systems), which actually gives two separate definitions,

consistency (or correctness) refers to the requirement that any given database transaction must change affected data only in allowed ways. Any data written to the database must be valid according to all defined rules, including constraints, cascades, triggers, and any combination thereof.

Consistency can also be understood as after a successful write, update or delete of a Record, any read request immediately receives the latest value of the Record.

The first is the definition as relates to ACID, which the second is essentially equivalent to the definition mentioned earlier.

Eventual Consistency

Eventual consistency is odd terminology, in my opinion, because it is both obviously desirable, and arguably trivial because 'eventually' can take as long as your algorithms need.

The reason it's discussed at all at all, at least as far as I can tell, is it groups together a collection of behaviors that are fundamentally non-trivial: conflict resolution and corruption resistance.

Conflict resolution, or reconciliation, addresses the question of conflicts in a distributed data store. The most common example is conflicting writes.

Corruption resistance is ensuring you have healthy nodes with accurate data. Arguably, over time, you have eventual inconsistency. Energy needs to be spent maintaining system integrity, resisting entropy, etc.