Consensus and Replication at Depth

Define the problem

Several machines hold copies of the same data. A change arrives, and the copies must not end up with different truths.

A majority is more than half of a group. A decision is safe when a majority has accepted it.

Two majorities of one group always overlap. They share at least one machine, and that machine carries the earlier decision into the next one.

How a leader election works

Leader election chooses one machine as leader for a stretch of time. The other machines act as followers.

Each follower waits to hear from the leader. A regular heartbeat message proves the leader is still alive.

Silence starts an election. A follower that hears nothing for a set time becomes a candidate and asks the others for votes.

A candidate that wins a majority of votes becomes the new leader. It then sends heartbeats, and the group settles again.

Random waiting times stop repeated tied elections. Each candidate waits a different random time before standing again.

How consensus reaches a decision

The leader receives a proposed change. It spreads the change to the followers before the change counts as decided.

The followers write the change into their write-ahead log and answer. Writing first keeps the change safe if a machine restarts.

A majority of 3 servers is 2 servers. That group tolerates 1 failure.

A majority of 5 servers is 3 servers. That group tolerates 2 failures.

A majority of 7 servers is 4 servers. That group tolerates 3 failures.

Once a majority holds the change, the leader reports it as decided. A later leader overlaps that majority, so the decision survives.

How consensus fails

A group with no majority makes no decisions. It stays safe, but it stops accepting changes.

A slow leader triggers elections it does not deserve. The group wastes time changing leaders instead of deciding.

Elections themselves can tie. Two candidates can split the votes so that neither reaches a majority.

A network failure can strand a leader with a minority of the group. That leader must stop deciding, because its group cannot reach a majority.

Consensus trade-offs

Bigger groups tolerate more failures. They also decide more slowly, because more machines must answer.

Odd group sizes are the common shape. Even sizes add a machine without adding protection.

Consensus protects agreement, not speed.

Consensus trades speed for one shared decision that failures cannot split.

A shared history

A replicated log is an ordered list of entries, copied to several machines in the same order on every machine. Its high-water mark is the point up to which entries are agreed and safe to apply.

Machines must agree on more than one decision. They must agree on a whole history of changes, in one order.

Order matters. A withdrawal before a deposit gives a different balance than the same events reversed.

A replicated log gives every machine the same history. Each machine applies the entries in the same order and reaches the same state.

An entry is one change, in order.

A segment is one fixed-size part of the log.

The high-water mark is the last entry safe to apply.

A follower copy is the same log on another machine.

How the log grows

The leader appends each new entry at the end of its log. Every entry carries a sequence number, so gaps are easy to spot.

Followers copy entries from the leader in order. A follower that falls behind asks for the entries it missed.

An entry counts as agreed once a majority of machines holds it. Until then, it stays a proposal that a new leader may drop.

Machines apply entries only up to the high-water mark. The high-water mark moves forward as majorities form behind it.

Segments keep the log manageable

A segmented log stores the log as fixed-size parts. Each part is a segment, and a full segment closes before the next one starts.

Segments make copying and repair cheaper. A follower that missed a stretch can fetch whole segments instead of single entries.

Old segments leave through log compaction. Once every machine has applied a segment, keeping it adds cost without adding safety.

Segments also bound the damage from a damaged file. Only one part of the log needs repair, not the whole history.

Estimate the log's growth

Suppose a service accepts 10,000 writes a second, and each write becomes one entry of 1 KB.

10,000 entries a second × 1 KB an entry = 10 MB of new log a second.

10 MB a second × 86,400 seconds = 864 GB of new log a day on each machine.

Three copies hold 864 GB × 3 = 2,592 GB of new log a day in total.

In this demo a segment holds 1 GB, which is 1,000 MB. At 10 MB a second, one segment fills in 100 seconds.

Where the log breaks

Suppose the high-water mark stands at entry 40. Entries up to entry 40 are agreed and safe to apply.

Entry 41 becomes safe only when a majority holds it and the mark moves past it.

A leader can fail after appending an entry that no follower received. The next leader drops that entry, and the client hears that the write failed.

The client must retry safely, which is why writes need idempotency. A retried write must not land twice.

A follower with a damaged segment cannot apply entries past the damage. It fetches the segment again from a healthy copy.

Log trade-offs

The log makes history explicit and repair simple. The price is storage on every copy and time spent copying.

Applying only to the high-water mark keeps every machine safe. It also means a just-written entry may not be visible yet.

A replicated log turns agreement into one shared history, applied in the same order everywhere.

Detecting failure

A failure detector is a part of a system that watches other machines and reports which ones seem to have failed. A gossip protocol spreads that news by machines telling a few neighbours at a time, again and again.

A machine that stops answering may be dead. It may also be slow, busy, or cut off by the network.

From the outside, these cases look identical. Silence is the only signal, and silence has many causes.

So a failure detector reports suspicion, not certainty. The rest of the system decides what to do with a suspicion.

Heartbeats and timeouts

Each machine sends a heartbeat at a steady rhythm. In this design, one heartbeat leaves every second.

A watcher records the time of the last heartbeat from each machine. A growing gap means a growing reason to worry.

A fixed timeout draws one hard line. Silence longer than the line marks the machine as failed.

The line is a trade-off in disguise. A short line reacts fast and cries wolf, while a long line stays calm and reacts late.

A fixed timeout judges by one fixed waiting time. Slow networks can trigger it.

Gossip spreads the news

Checking every machine from one place does not scale. The watcher itself becomes a bottleneck and a single point of failure.

A gossip protocol shares the watching instead. Each machine watches a few others and passes on what it learns.

News travels in rounds. In each round, every machine that knows a fact tells one machine that does not.

Doubling seven times turns 1 knowing machine into 128 knowing machines.

Doubling ten times reaches 1,024 machines. Big groups hear the news within a few rounds.

Gossip is slow per round and cheap per machine. It suits large groups, where news within a few rounds is fast enough.

Phi accrual refines suspicion

Phi accrual is a failure detector style that turns silence into a rising score. The score is called phi, and it grows the longer the silence lasts.

Phi builds from the usual gap between one machine's heartbeats. A normal silence keeps phi low, while an unusual silence pushes phi high.

Each service sets a threshold for phi. Crossing the threshold marks the machine as suspected, not proven dead.

One threshold can serve machines with different rhythms. Each machine gets judged against its own past behaviour.

Phi accrual costs more to build and explain. It repays that cost where false alarms are expensive.

Phi accrual judges by a suspicion score rising with silence. It is harder to set and explain.

Detection trade-offs

A wrong suspicion can start an unneeded election. A missed failure can leave a dead leader in place.

No detector removes this risk. It only chooses which mistake to make more often.

A failure detector reports suspicion, never certainty, and the design must stay safe under both mistakes.

The stale holder problem

A lease is a time-limited right that lets one machine hold a role until a set moment, after which the right ends on its own. A fencing token is a rising number handed out with each lease, used to reject work from holders whose lease has ended.

A leader can freeze for a while and then wake up. While it sleeps, the group may elect a replacement.

The old leader wakes believing it still leads. Two leaders now issue orders, and the orders can conflict.

Stopping the old leader is impossible from outside. The system must instead make its late work harmless.

How a lease works

A lease grants a role for a fixed stretch of time. When the time runs out, the right ends without any message.

The holder renews the lease while it works. Renewal is a short message sent well before the expiry moment.

In this design the lease lasts 10 seconds and the holder renews every 3 seconds. A healthy holder therefore renews with 7 seconds to spare.

Expiry needs no agreement. Leases assume machine clocks stay close, and a lease system states that assumption instead of hiding it.

How a fencing token works

Each new lease carries a fencing token. The token is a number that rises with every grant.

Suppose one lease carries token 41. The next lease carries token 41 + 1, which is token 42.

Every piece of work from a holder carries its token. The store compares the token on the work with the highest token it has seen.

Work with an older token is rejected. Work with the current token goes ahead.

A stale holder, fenced out

Holder A leads under token 41. Holder A freezes, and its lease expires while it sleeps.

The group elects holder B. Holder B receives a new lease with token 42, and the store notes the higher token.

Holder B writes its first change. The store accepts it, because the token is current.

Holder A wakes and sends the write it prepared before freezing. The store sees token 41, below the recorded 42, and rejects the write.

No message ever reached holder A. Fencing worked because the store, not the stale holder, enforced the rule.

Lease and fencing trade-offs

Short leases replace a bad holder quickly. They also expire during brief network trouble and cause extra elections.

Long leases ride out brief trouble. They also leave a frozen holder's role empty for longer.

Fencing adds a check to every write. That small cost buys safety against the rarest and worst failure in this category.

A lease bounds how long a stale holder can act, and a fencing token makes its late work powerless.

When the network splits

A network partition is a failure that splits a group of machines into parts that cannot reach each other, while each part keeps running. Split-brain is the fault in which two parts each believe they lead, and accept work that conflicts.

A partition is a failure of the network, not of a machine.

Machines in a partition are healthy. Their messages simply cannot cross to the other part.

Each part sees silence from the rest. Each part must guess whether the others died or merely became unreachable.

Acting on the wrong guess creates split-brain. Refusing to act at all keeps the data safe and stops the service.

Majorities decide who may continue

A group of 5 splits into parts of 3 and 2. Only the part of 3 holds a majority, so only that part may decide.

A group of 4 can split into parts of 2 and 2. A majority of 4 is 3, so neither part may decide.

Odd group sizes avoid the deadlocked split. That is one reason consensus groups favour odd sizes.

The minority part should say so plainly. Its requests fail fast, or wait, instead of pretending to serve.

How split-brain damages data

Suppose both parts of a group accept writes during a partition. Each part builds its own version of the truth.

One part sells the last seat. The other part sells the same seat to someone else.

When the network heals, the two versions meet. Some conflicts have no fair merge, and one accepted write must be undone.

Prevention beats repair. A part without a majority must refuse writes before the damage happens.

Staying safe during a partition

Designs place copies across separate data centers. A failure inside one data center then cannot strand a majority by itself.

A third small site can break ties. It holds no data and only votes on which part may continue.

Reads can continue where writes cannot. A minority part may serve older data if it labels the data as possibly stale.

Every part needs a way back. When the link heals, the minority part copies the majority's log before serving again.

Partition trade-offs

Refusing minority writes protects the data. It also turns a network failure into an outage for some users.

Allowing both parts to write keeps the service up. It also risks conflicts that no merge can settle fairly.

CAP named this choice first. Majorities are the machinery that makes the choice real.

Split-brain is prevented by majorities, not by hoping the network stays whole.

From CAP to PACELC

PACELC is a rule that extends CAP by asking what a system trades away during a partition and during normal operation. It says a system chooses between availability and consistency in a partition, and between latency and consistency the rest of the time.

CAP applies only while a partition lasts. It says nothing about the far longer time when the network is healthy.

Most running hours have no partition. A design rule that ignores those hours misses the everyday trade-off.

PACELC fills the gap. Its name packs the two choices into one short rule.

Read the letters

P stands for partition. When a partition happens, A is availability and C is consistency, and the system picks one.

E stands for else, meaning normal operation. In normal operation, L is latency and C is consistency, and the system picks one again.

The two picks are independent. A system can favour consistency in a partition and still favour latency on normal days.

Naming both picks is the point. A design that states only its partition behaviour hides half of its character.

The everyday latency choice

A consistent answer often needs agreement across copies. Agreement takes messages, and messages take time.

A round trip inside one data center takes about 0.5 milliseconds. A round trip across an ocean takes about 150 milliseconds.

Suppose an answer must return within 100 milliseconds. Checking a copy across an ocean needs a round trip of about 150 milliseconds.

150 − 100 = 50, so the check alone finishes 50 milliseconds late.

Choosing the near copy answers faster. The near copy may hold older data, so the answer may be stale.

In normal operation, the cost is slower answers or older answers.

The partition choice, revisited

During a partition, majority machinery decides who may act. A part without a majority chooses between refusing work and risking conflict.

Choosing availability keeps every part answering. Choosing consistency keeps one truth and lets the other part wait.

Neither pick is a moral judgement. The right pick follows from what the data means to its users.

In a partition, the cost is an outage or conflicting data.

How to answer with PACELC

In an interview, state the partition pick first. Then state the normal-day pick, with the latency cost attached.

A complete answer can be one sentence. This design stays consistent in a partition and accepts slightly stale reads to stay fast on normal days.

Consensus, logs, leases, and fencing are how the chosen behaviour is enforced.

PACELC says the trade-off never sleeps, because normal days test consistency against latency just as partitions test it against availability.

Group size, majority, and failures tolerated