Consistency, CAP, and consensus
Distributed databases must decide what guarantees to offer when networks fail. The CAP theorem and consensus algorithms frame these trade-offs.
Network partitions
In a distributed system, messages can be delayed or lost, and nodes cannot always tell whether another node has crashed or is merely unreachable. A network partition splits nodes into groups that cannot communicate. Since partitions cannot be ruled out in practice, systems must decide how to behave when one occurs.
The CAP theorem
Proposed by Eric Brewer in 2000 and proved by Seth Gilbert and Nancy Lynch in 2002, the CAP theorem says that during a network partition a system cannot provide both consistency, meaning every read sees the most recent write (linearisability), and availability, meaning every request to a working node gets a response. Systems choose CP, refusing some requests to stay consistent, or AP, answering but possibly with stale data.
Beyond CAP: PACELC
CAP describes only behaviour during partitions. Daniel Abadi's PACELC extension adds: else, when the network is healthy, systems trade latency against consistency. Keeping replicas in tight agreement requires waiting for communication, while answering from the nearest replica is faster but may be stale. This everyday trade-off often matters more than rare partitions.
Consistency models
Linearisability is the strongest common model: the system behaves as if there were a single copy and every operation took effect instantly at some point between its start and end. Sequential and causal consistency are weaker; causal consistency ensures that if one write could have influenced another, everyone sees them in that order. Eventual consistency promises only that replicas converge if writes stop.
Consensus
Consensus lets a group of nodes agree on a value, such as which node is leader or the order of log entries, even if some nodes fail. Leslie Lamport's Paxos (published in 1998) and Raft (2014, by Diego Ongaro and John Ousterhout, designed for understandability) are the best-known algorithms. They need a majority, so a 5-node group tolerates 2 failures.
Raft in brief
In Raft, nodes elect a leader by majority vote for a numbered term. The leader appends client commands to its log and replicates them to followers; an entry is committed once a majority has stored it, then applied in order by every node. If the leader fails, a new election begins. Systems such as etcd, CockroachDB, and many configuration services use Raft-style replication.
NewSQL and distributed SQL
Distributed SQL databases, such as Google Spanner (described in 2012), CockroachDB, and YugabyteDB, combine SQL and ACID transactions with horizontal scaling. They partition data into ranges, replicate each range with consensus, and coordinate transactions across ranges. Spanner uses tightly synchronised clocks, with GPS and atomic-clock references, to order transactions globally.
Worked example
A 5-node Raft cluster: a leader needs votes from 3 nodes. A partition splits nodes into groups of 3 and 2. The group of 3 can elect a leader and keep committing writes; the group of 2 cannot form a majority, so it refuses writes rather than diverging. When the partition heals, the minority nodes discard any uncommitted entries and catch up. This is a CP choice: consistency is kept, and availability is sacrificed in the minority.
Key takeaways
Networks can delay or lose messages and partition nodes. CAP (Brewer 2000, proved 2002) says that during a partition a system must choose between linearisable consistency and availability: CP or AP. PACELC adds the everyday latency-versus-consistency trade-off. Consistency models range from linearisable through causal to eventual. Consensus algorithms such as Paxos and Raft let majorities agree; 5 nodes tolerate 2 failures. Raft elects leaders by term and commits entries on majority storage. Distributed SQL systems such as Spanner and CockroachDB combine consensus replication, partitioning, and ACID transactions.
Flashcard
Nodes split into non-communicating groups
Check your understanding
A 3-node consensus cluster loses one node. Can it still commit writes?