RAFTSTORE 502: Linearizable Reads

In RAFTSTORE 501, we followed an async_write from proposal to callback. The callback notifies the client that the write has completed. By the time it runs, the write has already been applied to RocksDB.

For reads, Raftstore provides the async_snapshot API, which returns a RocksDB snapshot. The caller uses the returned snapshot to read RocksDB and serve point reads, batch reads, and scans.

Raftstore's async_snapshot must provide linearizable reads. A linearizable read must observe every write that completed before it began.

What a Linearizable Read Must See

This rule preserves real-time ordering:

async_write
    request --- replicate --- apply --- complete
                                           |
                                           | must be visible
                                           v
async_snapshot                             request --- snapshot

If a client successfully writes k = v and then reads k, the read cannot return the old value. Without this property, the system would be hard to reason about: a client could not even read back a write that had already succeeded.

When a write and read overlap, they are concurrent: neither operation completed before the other began. The read may return either the old or new value, because either order is valid.

Recall from ROCKSDB 403 that taking a RocksDB snapshot records the latest internal sequence number at that moment. To satisfy the rule above, Raftstore must take the snapshot after all earlier completed writes have been applied.

The Slow Baseline

One naive approach is to propose an empty Raft entry for every read and take the RocksDB snapshot when that entry is applied. This guarantees linearizability: Raft orders the entry after all preceding writes, and applies entries in order.

propose an empty Raft entry
            |
            v
replicate, commit, and apply it
            |
            v
take a RocksDB snapshot

This is correct but too expensive. A read would pay nearly the full cost of a write without changing data.

The Leader Intuition

Set aside the brief period immediately after an election and consider the normal case.

Every completed async_write has already been applied to the leader's RocksDB. The leader may have newer entries that are committed but not yet applied, but those writes have not completed. Its RocksDB therefore contains every write that a new linearizable read is required to observe.

The read does not need another Raft entry or additional apply work. It only needs to establish that this peer is still the leader.

This is the idea behind a lease read.

Lease Read

In the normal case, the leader's RocksDB already contains every completed write. The only remaining question is whether this peer is still the leader.

Raftstore answers this question with a leader lease, an extension to the basic Raft protocol. The leader sends heartbeats to the followers. When a quorum acknowledges the leader's recent Raft messages, the leader establishes or renews its lease.

The lease period is shorter than the election timeout. While the lease remains valid, another peer cannot win an election and become the leader. The local peer can therefore trust that its leadership is still current.

For a typical leader, this is enough:

leader lease is valid
          |
          v
take a local RocksDB snapshot
          |
          v
serve the read

This is called a lease read, or local read. It is the fast path: no new Raft entry, no apply work, and no network round trip for the read itself.

The fast path is not immediately available in two cases.

First, the leader may have just won an election. Its Raft log contains the committed history, but its RocksDB state may still be catching up. Before serving a local read, it must apply an entry from its current term.

new leader
    |
    v
apply an entry from the current term
    |
    v
all earlier committed entries have reached RocksDB

Raft applies entries in order. Once an entry from the current term has been applied, every earlier committed entry, including entries from previous terms, has also been applied.

Second, the leader's lease may be expired or uncertain. In that case, the peer cannot determine from local state alone whether it is still the leader. It uses ReadIndex instead.

ReadIndex

ReadIndex confirms leadership through a quorum without adding a new entry to the Raft log.

The leader sends heartbeats for the pending read and waits for acknowledgements from a quorum:

lease is uncertain
        |
        v
send ReadIndex heartbeats
        |
        v
quorum confirms leadership
        |
        v
take a RocksDB snapshot

Once the quorum responds, the peer knows that it is still the leader. As long as its local RocksDB state is ready, Raftstore can take the snapshot and serve the read.

If the peer discovers a newer term, it is no longer the leader and rejects the request. If it cannot contact a quorum, it cannot safely complete the read.

ReadIndex is slower than a lease read because it requires a network round trip, but it is still much cheaper than proposing an empty Raft entry. It confirms leadership without writing, persisting, or applying a new log entry.

The Complete Flow

async_snapshot
      |
      v
is the local peer the leader?
      |
      +-- no --> reject
      |
      v
has it applied into its current term?
      |
      +-- no --> wait or use ReadIndex
      |
      v
is the leader lease valid?
      |
      +-- yes --> take a RocksDB snapshot
      |
      +-- no --> ReadIndex confirms a quorum --> take a snapshot

The returned snapshot includes every write that completed before the read began. That is a linearizable snapshot.

Keyboard shortcuts