Consistency Models, CAP & PACELC

By the end of this lesson you will be able to name the main consistency models, explain CAP correctly (not the popular wrong version), use PACELC to describe real trade-offs, and see why "last write wins" can silently lose data while CRDTs do not.

What does "consistent" mean?

When data has several copies, a read might reach a copy that has not seen the latest write. A consistency model is a promise about what reads can return.

Think of a cricket score shown in three places: the stadium scoreboard, a TV channel and a phone app. The stadium is always right. The TV may be two seconds behind. A phone app may be ten seconds behind. If all three eventually show the same score once play stops, that is eventual consistency. If every screen always showed exactly the stadium's score at the same instant, that would be strong consistency, and it would be much harder and slower to build.

From strongest to weakest, the models you will hear most:

Stronger models are easier to program against but cost latency and availability. Weaker models are faster and more available but push work onto the application. The replication lesson showed how read-your-writes and monotonic reads are built in practice.

The CAP theorem, stated correctly

Eric Brewer proposed the CAP idea in 2000, and Seth Gilbert and Nancy Lynch proved a formal version in 2002. It talks about three properties:

• C, Consistency: here it means linearizability, every read sees the latest write.
• A, Availability: every request to a working node gets a non-error answer.
• P, Partition tolerance: the system keeps running even when the network splits nodes into groups that cannot talk to each other.

The popular summary "pick any two of three" is misleading. Networks do fail, so partitions are not optional. The real statement is: when a network partition happens, a system must choose between consistency and availability. When there is no partition, it can have both.

Step 1: run a small model. Two replicas, one in Mumbai and one in Chennai, lose their link. A user writes in Mumbai, and another user reads in Chennai.

class Replica:
    def __init__(self, name):
        self.name, self.data = name, {"seats_left": 5}

class Cluster:
    def __init__(self, mode):
        self.mode = mode                       # "CP" or "AP"
        self.a, self.b = Replica("Mumbai"), Replica("Chennai")
        self.partitioned = False

    def write(self, replica, key, value):
        other = self.b if replica is self.a else self.a
        if self.partitioned and self.mode == "CP":
            return "ERROR: cannot reach the other replica, write refused"
        replica.data[key] = value
        if not self.partitioned:
            other.data[key] = value            # normal replication
        return "ok"

    def read(self, replica, key):
        if self.partitioned and self.mode == "CP":
            return "ERROR: might be stale, read refused"
        return replica.data[key]

for mode in ["CP", "AP"]:
    c = Cluster(mode)
    c.partitioned = True                       # the network link breaks
    print(f"{mode}: write in Mumbai  -> {c.write(c.a, 'seats_left', 4)}")
    print(f"{mode}: read in Chennai  -> {c.read(c.b, 'seats_left')}")

CP: write in Mumbai  -> ERROR: cannot reach the other replica, write refused
CP: read in Chennai  -> ERROR: might be stale, read refused
AP: write in Mumbai  -> ok
AP: read in Chennai  -> 5

Step 2: compare. The CP choice keeps data correct by refusing requests during the partition, so it is not fully available. The AP choice keeps answering, but Chennai shows 5 seats when only 4 are left. Neither is "better". A seat-booking system should not sell the same seat twice, so it leans CP for the booking step. A "likes" counter can be a little wrong for a minute, so it leans AP.

Real CP systems usually let the side with a majority of nodes keep working and only refuse requests on the minority side. Consensus algorithms such as Raft and Paxos do exactly this, and they power coordination services like etcd and ZooKeeper.

PACELC: the part CAP leaves out

Partitions are rare. What about the normal case? Daniel Abadi's PACELC formulation adds it:

• If Partition (P): choose Availability (A) or Consistency (C).
• Else (E), in normal operation: choose lower Latency (L) or Consistency (C).

The "else" half matters every day. To be strongly consistent, a write must wait for replicas, often in other zones or regions, to confirm. That adds latency to every request, not just during failures.

Many databases let you choose per request, for example Cassandra's consistency levels (ONE, QUORUM, ALL), so one system can be PA/EL for a product view counter and closer to PC/EC for something more important.

When copies disagree: resolving conflicts

An AP system accepts writes on both sides of a partition. When the network heals, it must merge them. The simplest rule is last write wins (LWW): keep the value with the newest timestamp. It is easy, but it depends on clocks, and clocks on different machines are never perfectly in step. LWW can silently throw away a write.

def lww_merge(a, b):
    return a if a["ts"] >= b["ts"] else b

# Two shopping-cart updates during a partition. Meera's phone clock runs 3 s fast.
mumbai = {"value": ["kurta", "jhumka"], "ts": 1_000.0 + 3}   # earlier, but clock is ahead
chennai = {"value": ["kurta", "saree"], "ts": 1_002.0}       # really happened later
print("LWW keeps:", lww_merge(mumbai, chennai)["value"])

LWW keeps: ['kurta', 'jhumka']

The saree, which was added later in real time, is lost because the other machine's clock was ahead. Amazon's Dynamo paper describes keeping both versions (tracked with vector clocks) and letting the application merge them, such as taking the union of two carts.

A cleaner answer for some data types is a CRDT (conflict-free replicated data type): a structure designed so that merging in any order always gives the same result. The simplest is a grow-only counter, where each replica counts its own increments and the total is the sum.

class GCounter:
    """Grow-only counter CRDT: each replica only increments its own slot."""
    def __init__(self, replica_id):
        self.id, self.counts = replica_id, {}

    def increment(self, n=1):
        self.counts[self.id] = self.counts.get(self.id, 0) + n

    def merge(self, other):
        for rid, c in other.counts.items():
            self.counts[rid] = max(self.counts.get(rid, 0), c)

    def value(self):
        return sum(self.counts.values())

mumbai, chennai = GCounter("mumbai"), GCounter("chennai")
mumbai.increment(120)      # likes counted in Mumbai during the partition
chennai.increment(75)      # likes counted in Chennai at the same time
print("Before merge:", mumbai.value(), chennai.value())

mumbai.merge(chennai)
chennai.merge(mumbai)
chennai.merge(mumbai)      # merging twice changes nothing
print("After merge :", mumbai.value(), chennai.value())

Before merge: 120 75
After merge : 195 195

No likes are lost, and merging is safe to repeat. Collaborative editors and some databases use richer CRDTs for sets, maps and text.

Common mistakes

• Saying "we chose CA". Any system spread across a network must handle partitions; CA only describes a single machine.
• Treating CAP as a property of a whole product. Different features can make different choices.
• Trusting timestamps from many machines to order writes. Clocks drift; LWW can lose data.
• Forgetting the latency cost of strong consistency in normal operation, which PACELC highlights.
• Using eventual consistency for money or seat counts without a strongly consistent step to guard the critical decision.

Key points

• Consistency models range from linearizable (strong) to eventual, with causal, read-your-writes and monotonic reads in between.
• CAP: during a network partition, a distributed system must choose consistency or availability.
• PACELC adds that in normal operation, you trade latency against consistency.
• Consensus protocols like Raft let a majority keep working consistently while a minority refuses.
• Last write wins depends on clocks and can drop writes; vector clocks and CRDTs merge safely.

class GCounter:
    def __init__(self, rid):
        self.id, self.counts = rid, {}
    def increment(self, n=1):
        self.counts[self.id] = self.counts.get(self.id, 0) + n
    def merge(self, other):
        for r, c in other.counts.items():
            self.counts[r] = max(self.counts.get(r, 0), c)
    def value(self):
        return sum(self.counts.values())

class PNCounter:
    def __init__(self, rid):
        self.p, self.n = GCounter(rid), GCounter(rid)
    def increment(self, k=1):
        self.p.increment(k)
    def decrement(self, k=1):
        self.n.increment(k)
    def merge(self, other):
        self.p.merge(other.p)
        self.n.merge(other.n)
    def value(self):
        return self.p.value() - self.n.value()

a, b = PNCounter("a"), PNCounter("b")
a.increment(10); a.decrement(3)
b.increment(4); b.decrement(1)
a.merge(b); b.merge(a)
print(a.value(), b.value())

10 10