Read Index and Leader Leases: Serving Reads Without a Log Entry

Appending a read to the log and waiting for it to commit gives a correct linearizable read and costs a full replication round trip for something that changes nothing. For a workload that is read-heavy, that cost dominates. The alternatives are to have the leader confirm it is still the leader before answering, or to have it hold a time-bounded promise from its followers that nobody else can be elected. The first is a quorum round trip with no disk write; the second is free per read but depends on clocks being roughly right. Choosing between them is choosing which assumption to lean on.

Why a local read is not linearizable

A leader’s state machine reflects entries up to its apply point. A write that has been committed but not yet applied is not visible to a read served from the state machine, so a client that writes and then reads from the same leader can see the old value. That is a staleness window of one apply cycle, and it is fixable by applying synchronously.

The harder problem is that the leader may no longer be the leader. A leader partitioned from its followers continues to believe it holds leadership until it learns otherwise, and under a protocol without a step-down mechanism it never learns. It will serve reads from a state machine that has stopped advancing while a new leader on the majority side accepts writes. The read returns a value that is older than a write the client already received an acknowledgement for, which violates linearizability in the most direct way: the read is concurrent with the write and returns the pre-write value, but the write completed before the read started.

So the read path needs to establish two things: that the state machine includes every committed entry, and that the node answering is the leader at the time of the answer. Applying synchronously handles the first. The second needs a quorum interaction or a lease.

Read index: a heartbeat round with a fence

The read-index approach has the leader record its current commit index, then confirm with a quorum that it is still leader, then wait for its state machine to apply up to that index, then answer.

The confirmation is an AppendEntries exchange carrying no new entries, which is the same message the leader sends as a heartbeat. A follower that receives it from a leader at least as up-to-date as itself responds with success. When the leader has responses from a majority for the current term, it knows that no other node could have been elected in a later term without at least one of those nodes having voted, and that node would have had to move to the later term and reject the heartbeat. The leader’s term is therefore current, and its commit index is a valid lower bound on what any subsequent leader must contain.

The recorded commit index is the important detail. A leader that confirms leadership at time T and then answers from a state machine that has applied only up to an index from before T could miss an entry committed between the confirmation and the read. Recording the index at the moment of confirmation and waiting for the apply loop to reach it makes the read reflect everything committed up to the confirmation point.

The wait is where the latency goes. If the apply loop is behind, the read waits for it, and the wait is proportional to the apply backlog. A leader under heavy write load can have a backlog of many entries, so a read can take longer than a write. This is why implementations often apply entries as soon as they are committed rather than batching, and why the read-index path is sometimes described as “confirm leadership, then queue behind the applier”.

For follower reads, the same index can be used differently. A follower asks the leader for the current commit index, waits until its own apply point reaches that index, and answers locally. The follower does not need to confirm leadership itself; it trusts the leader’s index. The result is linearizable only if the follower’s request to the leader was served after the leader confirmed leadership, which the leader ensures by handling the request through the same read-index path. The benefit is that the expensive quorum round happens once per batch of follower reads rather than once per read, and the follower absorbs the apply wait locally.

Leases and the clock assumption

A lease is a promise with an expiry. Two implementations are common, and they differ in who holds the deadline.

In the follower-granted form, the leader asks its followers for a promise not to grant a vote to any other candidate for a fixed duration, and each follower records the expiry against its own clock before replying. The leader, having collected promises from a majority, knows that no other candidate can assemble a majority until the earliest of those expiries passes, so it can answer reads locally until then.

In the leader-estimated form, nothing is stored on the followers. The leader measures the round trip of its own heartbeat exchange on a monotonic clock, and treats the lease as valid for the election timeout minus the measured elapsed time. The reasoning is that a follower which responded to the heartbeat cannot have moved to a later term before that response, and the election timeout is the earliest moment at which it could vote for someone else, so the remaining interval is safe for the leader to serve reads.

The strictness is the whole safety argument in both forms. The leader’s lease must expire strictly before any follower’s promise can be broken, with the margin covering the maximum clock-rate difference between the machines and the message delay. A leader that treats its own elapsed interval as authoritative without that margin can answer a read after a follower has already granted a vote to a new leader.

This is why leases are described as depending on bounded clock drift rather than on synchronized clocks. The nodes do not need to agree on the time; they need their clocks to advance at approximately the same rate, so that a duration measured on one node is a duration measured on another within a known error. A follower’s clock that runs fast shortens its promise, which is harmless. A clock that runs slow extends it, which is the dangerous direction, and is why the margin is subtracted rather than assumed away. A clock that jumps backward is worse than drift and cannot be bounded at all, so lease arithmetic uses a monotonic clock and treats a wall-clock adjustment as irrelevant to the interval.

The payoff is that a read costs one local state-machine lookup and no network round trip. The cost is that the leader must keep its lease renewed, which means heartbeats must continue at a rate that keeps the lease valid, and a leader that cannot reach a quorum loses its lease and must stop answering reads. The check-quorum mechanism is the same idea applied to the leader’s own step-down decision, and the two are usually implemented together.

Comparing the two paths

Read index costs a quorum round trip per read batch and requires no clock assumption beyond the ones the protocol already makes. It is safe under arbitrary clock skew and arbitrary pauses, because the confirmation is a message exchange rather than a time interval.

A lease costs nothing per read and requires a bounded-drift assumption plus a monotonic clock. It is unsafe if a node’s clock jumps backward or if the lease duration is computed without subtracting drift.

The latency comparison depends on the deployment. In a local network, a quorum round trip is on the order of a millisecond, and read index is cheap enough to use for every read. In a wide-area deployment where the replicas are hundreds of milliseconds apart, a lease turns a read into a local operation and the difference is large. The bandwidth comparison is one-sided: read index generates O(n) messages per read batch, leases generate O(n) per lease renewal regardless of read volume.

There is a third option that avoids both: read from a follower and accept staleness, with the client supplying a bound. This is not linearizable, but it is often what a read-heavy workload actually wants, and the protocol’s job is to make the staleness bounded and visible rather than to pretend it does not exist. A follower that reports its commit index with the response lets the client decide whether the value is fresh enough, and the client can retry against the leader if it is not.

The interaction with leadership changes

Both mechanisms have to handle the moment of transition. A leader that has answered a read under a valid lease and then loses leadership has already returned a value that was correct at the time; the problem is a read that is in flight when the transition happens.

Under read index, the read either completes its quorum confirmation before the transition or fails to, and the confirmation is against the leader’s term. A leader that has been superseded will find that its heartbeats are rejected, so it will not complete the confirmation, and the read will be retried. There is no window in which the read is answered from a stale state.

Under a lease, the window exists if the lease outlives the leadership. The lease is supposed to prevent the transition for its duration, so a transition during the lease means the lease was violated, which means either the clock assumption failed or the lease arithmetic was wrong. There is no third possibility, and this is why lease implementations are tested with clock manipulation rather than only with network faults.

The state machine’s apply point interacts with both. A read that is answered from a state machine that has not applied a committed entry is stale regardless of how leadership was confirmed. The apply must be ordered before the answer, and the ordering must be observable: an implementation that hands the read to the apply loop and returns whatever the loop produces after the next batch has a race between the read’s index and the batch’s contents.

Reads during a partition

The partition case is the one that distinguishes a correct implementation from a plausible one. A leader isolated from its followers cannot reach a quorum, so read index fails and the read is not answered. Under a lease, the leader can answer reads until the lease expires, and then it cannot. Both behaviours are correct: the read is answered only while the leader can still prove it is the leader, and the proof has a bounded lifetime.

The failure mode to avoid is answering reads indefinitely from a leader that has lost contact. A lease with no expiry, or an expiry computed from the leader’s own clock without reference to the followers’ promises, is exactly that failure. It is also the failure that a naive implementation produces, because the leader’s state machine is healthy and the read succeeds locally, and nothing in the local state indicates a problem.

What the read path says about the system

A replicated system’s read path is where its assumptions become visible. A system that serves reads only through the log is assuming nothing about clocks and paying for it in latency. A system that serves reads under a lease is assuming bounded drift and paying for it in the complexity of the lease arithmetic. A system that serves reads from followers with a reported commit index is not claiming linearizability at all, and saying so is more honest than claiming it and relying on the reader not to notice.

The choice also determines what happens during a partition, which is the operational question that matters most. A read path that fails closed under partition is safer and less available; a read path that fails open is the opposite. Neither is wrong, and the quorum arithmetic that determines when a quorum is reachable is the same arithmetic that determines when the read path can answer.