CSE Roadmap

Common tier · about 4 hours · 6 parts

Part 4 of 6 · 2 min read

Costs and limits

Consensus is a breakthrough with a price.

Think of a rule that nothing is decided unless more than half the committee is in the room. Safe, but a meeting with too few members is stuck, and every decision waits for the vote.

The DDIA book says consensus brings concrete safety properties to a system where everything else is uncertain, and it stays fault tolerant while a majority works. It can implement linearizable operations (module 6) safely. But:

  • Voting is a kind of synchronous replication. Many databases use asynchronous replication, accepting that committed data can be lost on failover, for performance. Consensus does not accept that, and pays in latency.
  • A strict majority is always needed. Three nodes tolerate one failure, five tolerate two. If the network cuts the nodes in two, only the majority side makes progress; the other side is blocked. This is the CAP choice of module 7.
  • Fixed membership. Most algorithms assume a fixed set of voters. Dynamic membership exists but is less well understood.
  • Timeouts cause trouble. In networks with variable delay, a node may wrongly think the leader died. Safety survives, but frequent elections can leave the system doing more electing than working.
  • Edge cases. Raft has been shown to misbehave if one network link is persistently unreliable while everything else works: leadership can bounce or the leader can keep being forced out. More robust algorithms are an open research problem, says the book.

A worked example of node counts.

Nodes Majority Failures tolerated Note
3 2 1 Common minimum
4 3 1 No better than 3 for failures, with one more node to run
5 3 2 Common for important data
7 4 3 More tolerance, but slower voting

An even number adds cost and no tolerance. This is why clusters use 3, 5 or 7.

Check yourself:

  • Why do consensus systems usually have an odd number of nodes?
  • What happens to the minority side of a split network?