Chain Replication and Ordered Failover

By the end of this lesson, you will be able to...

• Trace when an update is merely in flight and when a chain has committed it.

• Explain why the tail is the ordinary safe read point in basic chain replication.

• Review a failover plan for its epoch, committed-prefix, and catch-up requirements.

Idea in one sentence: Chain replication gives one object an ordered update path: the head accepts writes, the tail establishes the committed prefix, and failover must preserve that prefix before serving clients again.

Core Insight

Harbor Point has one scarce allocation bucket: the final unit of a thinly traded municipal bond. Two desks may try to reserve it at once. The system must not tell both desks that they own it, and a completed reservation must not disappear after a replica failure.

The team could use a repair-oriented leaderless design. For this bucket, however, it wants a simpler promise: completed operations form one visible order. Chain replication earns that promise by arranging replicas in a line rather than treating them as interchangeable copies.

chain epoch 42

[head A]  ->  [middle B]  ->  [tail C]

An update enters at A, moves through B, and reaches C. The tail is not just the last machine in a diagram. It is the point that has received the committed prefix, so ordinary committed reads go there.

The Situation

The allocation service receives two commands in this order:

reserve#881: reserve the last unit for desk North
release#882: release that reservation

Each replica applies and forwards updates in the chain's order. At a moment during normal operation, replicas can legitimately have different prefixes:

A: reserve#881, release#882
B: reserve#881
C: reserve#881

Nothing is wrong yet. release#882 is simply in flight. The system needs a rule that tells clients which prefix is safe to call committed. In basic chain replication, that rule is: the tail's prefix is committed.

The Initial Model

The first reasonable model is “the head is the leader, so success at the head means success for the object.” That is attractive because clients send writes to the head and the head may already have stored release#882.

It works only for accepting and sequencing incoming work. It does not work as a completion rule. If A crashes before release#882 reaches C, the tail cannot safely show that release as committed. A client told that the release had completed would have a promise the chain never earned.

client -> A: release#882
A applies release#882
A crashes before forwarding it to B and C

C still contains only reserve#881

The missing distinction is between accepted by the head and committed at the tail.

The Mechanism Step by Step

Plain meaning:

Move every update through one ordered path, then let the final replica define the history ordinary readers may trust.

In this scenario:

North's reservation enters at A, reaches B, then reaches C. Only after C applies it can the client learn that the chain committed it.

Technical name:

This is chain replication. The sequence stored at the tail is the chain's committed prefix.

Here is one illustrative write trace. The sequence numbers are teaching values, not output from a specific product.

Starting state
  epoch=42, A=B=C at sequence 880

1. client -> A: reserve#881
   A appends 881 and forwards it to B.

2. A -> B: reserve#881
   B applies 881 after its existing prefix, then forwards it to C.

3. B -> C: reserve#881
   C applies 881 after its existing prefix.

4. C -> client (often through the chain's acknowledgement path)
   "881 is committed in epoch 42."

The important invariant is not that every replica is equal at every instant. It is that replicas process one order and the tail has a prefix that is safe to expose as complete. A and B may already contain later work, but that work is not yet part of the ordinary committed view.

A Worked Read Trace

After step 4, a client asks whether North owns the unit. A tail read has a direct answer:

client -> C: GET allocation/MUNI-CA-17
C has committed prefix through 881
C returns: reserved_by=North, sequence=881

Now suppose release#882 has reached A but not C.

A: 881, 882
B: 881
C: 881

Reading from A would expose an in-flight release. Reading from C returns the last committed state. This is why “read the closest replica” weakens the basic chain contract even when the close replica is usually up to date.

Can the system ever read elsewhere? Yes, but only with an additional safety rule. CRAQ is one example of a read-mostly extension that lets non-tail replicas serve versions they can prove are clean. The base lesson remains: a faster read path must prove an equivalent committed version; proximity is not proof.

So far: the tail gives a small, inspectable answer to “what completed?” The head sequences work, but the tail earns client-visible commitment.

Ordered Failover Is a New Epoch

The hard case is not forwarding an update. It is changing the chain while updates are in flight.

Assume B fails. The control plane wants to replace this chain:

old epoch 42: A -> B -> C
new epoch 43: A -> C

Treating that as a load-balancer change is unsafe. Before clients use epoch 43, the system needs a controlled transition:

1. Fence or stop requests that still name epoch 42.
2. Identify C's committed prefix from the old chain.
3. Reconcile any updates accepted upstream but not present at C.
4. Ensure A and C agree on the starting prefix for epoch 43.
5. Publish epoch 43 and route writes to its head and reads to its tail.

Step 3 matters because upstream replicas may have updates that the old tail never committed. The new epoch must not silently turn them into completed writes. A correct system can retry, abort, or resolve those in-flight operations according to its protocol, but it must preserve the boundary between the old committed prefix and uncommitted work.

For example, suppose H accepted 507 and M may or may not have received it, while T reports a durable committed prefix through 506:

old epoch 18 state
  H: 506, 507 accepted
  M: unknown after the failure
  T: 506 committed

safe starting fact for epoch 19
  committed prefix = 506
  update 507 = unresolved, not silently committed

The coordinator can inspect durable records and retry 507 with an idempotency key, or report an indeterminate result that the client resolves by querying the new epoch. What it cannot do is infer completion merely because H received the command. This small distinction prevents a reconfiguration from turning a timeout into a duplicate allocation.

Tail failure is more delicate. The service cannot simply pick a convenient survivor as a new tail and resume reads. It must establish which survivor contains the old committed prefix, or recover that prefix from durable records, before publishing the new read point. Head failure has a different danger: clients may keep sending writes to a dead or obsolete entry point, so epoch fencing and retry logic matter first.

The Trade-off, Limits, and Signals

Chain replication improves the clarity of a single object's history. The trade-off is direct: each write pays for ordered hops through the chain, and each ordinary committed read depends on a special tail. That cost is worthwhile when a wrong order harms the product more than a little extra latency or a restricted failover path.

The chain also makes delay easier to locate. If the head accepts work quickly but tail commitment grows slow, the problem is not an abstract “replication lag” number: one link, a disk flush, or the tail itself is holding the committed prefix back. That diagnosis is valuable, but it does not remove the cost. Longer chains and slow tails directly lengthen the interval in which an update is accepted but still in flight.

The mechanism does not make a multi-object workflow atomic. One chain can give an ordered history for one object or partition. A reservation that must coordinate two buckets still crosses authority boundaries. It also does not remove the need for durable storage, membership control, or an exact retry policy.

Choose a chain when a local, ordered contract is worth the routing and reconfiguration discipline. A repair-friendly preference store may prefer leaderless availability. A scarce allocation bucket may prefer the tail-defined history.

Common Confusions

Confusion: The head and tail have the same completion role.

Why it is tempting: The head receives the client request first.

Better model: The head accepts and sequences updates. The tail marks the prefix that basic committed reads may trust.

Confusion: Failover means sending traffic to any live replica.

Why it is tempting: Capacity routing often works that way.

Better model: Chain failover installs a new epoch. It must preserve the old committed prefix and handle in-flight updates before clients trust the new head or tail.

Confusion: Reading an internal replica is always safe if it is fast.

Why it is tempting: It often contains the newest messages.

Better model: It may contain work the tail has not committed. A non-tail read needs an explicit proof that its version is safe.

Check Your Understanding

Check: A has applied updates 881 and 882, while tail C has applied only 881. What should an ordinary committed read return, and why?

Think first, then reveal.

Answer: It should return the state after 881 from C. Update 882 is still in flight because the tail has not applied it; returning it from A would expose uncommitted work.

Check: A reconfiguration wants to move from A -> B -> C to A -> C. What makes the word “epoch” more than a label?

Answer: It fences the old configuration and defines the prefix from which the new chain may continue. Clients must not mix old and new routing as if both chains were simultaneously authoritative.

Practice: Review a Failover Plan

An inventory service runs epoch 18: H -> M -> T. The middle replica becomes unreachable while the head has accepted update 507 but the tail has committed only through 506. The team proposes to route new writes directly from H to T immediately and continue returning successes.

Write the smallest safe plan. State what happens to update 507, when reads may resume, and which signal you would watch during the transition.

A good answer should mention:

• Fencing epoch 18 before clients can mix its routes with epoch 19.
• Establishing the tail's committed prefix, 506, as the safe boundary.
• Treating 507 as in-flight: reconcile, retry, or return an outcome according to the protocol; do not silently call it committed.
• Catching up and agreeing on the new chain's starting prefix before it serves normal reads and writes.
• Monitoring epoch-transition time, tail commit lag, and in-flight replay or mismatch counts.

Connections

• Replication Lag and Read-Your-Writes models why a replica that has not applied a required position cannot safely satisfy a fresh read; a chain makes the tail the default committed point.
• Sharding and Authority Boundaries changes the scale of this mechanism: each shard can have its own replicated authority, but cross-shard work needs a separate design.

Resources

• [PAPER] Chain Replication for Supporting High Throughput and Availability — Focus: Study head-to-tail update propagation, tail reads, and failure handling as one protocol.
• [PAPER] Object Storage on CRAQ — Focus: Compare its safe non-tail-read extension with the base tail-read rule.
• [BOOK] Designing Data-Intensive Applications — Focus: Compare an ordered replication path with leaderless quorum and leader-based replication choices.

Key Takeaways

• The head accepts and orders updates; the tail defines the prefix ordinary clients may treat as committed.
• Internal replicas can legitimately contain in-flight work, so proximity alone does not make them safe read points.
• A chain failover is an epoch transition that must preserve the old committed prefix and explicitly handle in-flight updates.
• Chain replication buys a clear per-object history at the cost of write hops, a special tail, and correctness-sensitive reconfiguration.