The Replicated Log

Define the problem

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.

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.

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.

Parts of the replicated log