Skip to content

linearizability.md

Latest commit

 

History

History
77 lines (59 loc) · 3.42 KB

linearizability.md

File metadata and controls

77 lines (59 loc) · 3.42 KB
Raw

Linearizability

A read on raftkv is linearizable iff it returns a value that reflects every Put that completed before the read was issued, and never returns a stale value.

What can go wrong with naive leader reads

If a leader simply returns whatever is in its local state machine, the read can be stale: a new leader may have been elected and committed a Put that the old leader has not learned about yet. From a client's perspective, the old leader's Get returns a value from before a Put that the system already acknowledged.

The implemented approach: read-quorum via heartbeat

RaftNode::confirm_leadership (called by KvServiceImpl::Get) does the following:

  1. Verifies the node is currently the leader.
  2. Captures the current term T.
  3. Initiates a fresh round of AppendEntries heartbeats to all peers.
  4. Counts successful responses (term acks at term T) including self.
  5. Once a majority (including self) ack at term T, the leader is confirmed for this read.
  6. Only then does the leader read from its state machine.

This is the "ReadIndex" approach without the index part: instead of returning a specific committed index to the client and waiting for the state machine to catch up, we simply guarantee the leader is still the leader at the moment of the read. Since the leader has applied every committed entry up to commit_index_, and the leader's own commit_index_ can only increase, the read sees at least every Put that was acknowledged before the read started.

Why a heartbeat round-trip is needed

Without confirming leadership, a "former leader" (network-partitioned, hasn't yet realized it lost the lease) could serve stale data. The heartbeat round-trip rules this out: if the former leader has been displaced, at least one of its AppendEntries will come back with a higher term, and the node steps down before the read returns.

Leader leases (deferred)

A more efficient implementation grants the leader a lease that lets it serve reads without a heartbeat for the lease duration. This requires:

  • A time-based lease (the leader knows it owns the leader role until time T_lease).
  • All servers agreeing not to elect a new leader before T_lease.

Clock skew makes this subtle: the lease must be slightly shorter than the minimum election timeout to give the system room to re-elect on lease expiry. Etcd, Consul, and Spanner all do variants of this.

Leader leases are explicitly deferred to v4 of raftkv. They are not implemented because the heartbeat-confirmation approach is correct and simpler, and the latency cost (one RTT per Get) is not a study goal.

Followers do not serve reads

Followers reject Get with NOT_LEADER and a hint to the current leader. A future variant (deferred, v3) could support follower reads with a read-index: the client asks the leader for commit_index, then a follower waits until its last_applied >= commit_index, then serves the read. This trades latency (still one round-trip to the leader) for throughput (followers absorb the actual read work).

Caveats

  • If the client times out before the heartbeat round completes, the read may have already returned; the caller cannot assume the read happened.
  • The leader's confirm_leadership is best-effort: if a peer is slow, the read may stall up to the gRPC RPC timeout (200 ms by default).
  • No client-side retry-on-leader-change is implemented in this repo. The client must handle NOT_LEADER and follow the leader_hint.