CAP Theorem and Consistency Models Explained Simply

Once data lives on more than one machine, the copies can disagree. Deciding what to do about that is one of the central problems in system design.

An example#

You change your profile photo. Your friend, reading from another copy of the database, may still see the old one for a moment.

Write --> Copy A (new photo)
              ... sending to the others ...
Read  --> Copy B (old photo)

Is that acceptable? For a photo, yes. For a bank balance, no. That is the choice.

The CAP theorem#

For a distributed data store, CAP names three properties:

• Consistency: every read gets the latest write.
• Availability: every request gets a response.
• Partition tolerance: the system keeps working if the network between nodes fails.

Network failures do happen, so partition tolerance is not optional. The real choice is what to do during a partition:

Note that "pick two of three" is a simplification. When the network is healthy, a system can offer both consistency and availability.

PACELC#

PACELC adds what CAP leaves out: even without a partition, you trade latency against consistency. Waiting for every copy to confirm a write is safer, but slower.

if Partition:   choose Availability or Consistency
Else:           choose Latency or Consistency

Consistency models#

Stronger models cost more latency and availability. Use the weakest model that the feature can tolerate.

Quorums#

With N copies, you can choose how many must confirm a write (W), and how many to read (R). If R + W is greater than N, a read always overlaps a recent write, so it sees the latest value.

import itertools


def always_overlap(n, r, w):
    nodes = range(n)
    return all(set(a) & set(b) for a in itertools.combinations(nodes, w) for b in itertools.combinations(nodes, r))


print(" N  W  R  overlap?")
for n, w, r in [(3, 2, 2), (3, 3, 1), (3, 1, 3), (3, 1, 1), (5, 3, 3)]:
    print(f"{n:>2} {w:>2} {r:>2}  {always_overlap(n, r, w)}")

 N  W  R  overlap?
 3  2  2  True
 3  3  1  True
 3  1  3  True
 3  1  1  False
 5  3  3  True

The code checks every possible choice of nodes. N=3, W=2, R=2 is a popular balance: it survives one failed node, and reads stay current. W=1, R=1 is fast, but reads may be stale. Databases such as Cassandra let you choose per query.

Handling conflicts#

If two people change the same record on different copies, the system must resolve it:

This small example shows last write wins losing an update, and a merge that does not:

copy_a = {"cart": {"tea"}, "ts": 100}
copy_b = {"cart": {"coffee"}, "ts": 101}

winner = max(copy_a, copy_b, key=lambda c: c["ts"])
print("Last write wins:", winner["cart"])
print("Merge (union):  ", sorted(copy_a["cart"] | copy_b["cart"]))

Last write wins: {'coffee'}
Merge (union):   ['coffee', 'tea']

Choosing per feature#

One product can use different levels:

Common mistakes#

Practice#

n, w = 5, 2
print("Smallest R:", n - w + 1)

Smallest R: 4

Key takeaway#

Next: Load Balancing.