Distributed Read/Write Paths

A storage request typically passes through four layers: routing, replica interaction, local storage, and response. Partitioning determines which nodes to contact, replication protocols determine which nodes to wait for, local persistence determines how a single node recovers, and read/write semantics determine what success means. These responsibilities collectively form the system, but no single system is required to use consistent hashing, Raft, and the same WAL simultaneously.

First, refer to Replication Strategies to distinguish between leader-based and leaderless approaches. This article uses two independent paths to illustrate their differences.

Leaderless Write: The Coordinator is Not a Fixed Leader

The client can contact any node to act as the request coordinator. The coordinator finds the set of replicas for the key based on partition metadata, sends the write request to the replicas, and waits for a specified number of successful responses. The next request may be coordinated by a different node and does not require a prior leadership election.

Assume the number of replicas N=3, and the write acknowledgment count W=2. Once A and B complete, success can be returned, while C may still be catching up. This means the operation has met the declared acknowledgment condition, but it does not imply that all replicas are updated simultaneously, nor does it imply that concurrent writes to the same key have been globally ordered.

Each replica typically records the change in a local log and updates in-memory structures, which are then flushed to disk data files. Whether the ACK waits for the flush depends on the storage engine and configuration; one cannot uniformly assume that every implementation performs an fsync before every write. The log ensures local recovery, and W determines the replica acknowledgment threshold; the two must be analyzed together.

Deriving Quorum Intersection

Within a fixed set of N replicas, let the write set size be W and the read set size be R. If the two sets are disjoint, their total size is at most N; therefore, R + W > N guarantees that they share at least one replica.

This set-theoretic conclusion requires premises such as a fixed replica set and responses that truly represent the requested write state. It is not a complete linearizable register algorithm:

• Concurrent writes may succeed on different subsets of nodes, requiring a definition of how to compare or retain versions.
• A timed-out write may have propagated to a minority of nodes; subsequent reads might see it. A timeout does not equal a rollback.
• If response versions are ordered by an unreliable physical clock, a larger value does not necessarily represent a later business event.
• If sloppy quorum writes to temporary substitute nodes, reads from the original replica set no longer necessarily intersect with the actual write set.

Therefore, one cannot simply write "the latest value is read in all cases" based solely on R+W>N. One must continue to explain version ordering, read repair/write-back, failed writes, and membership change rules.

How a Failed Write Can Cause Regression in Two Quorum Reads

Initially, A, B, and C all hold version 0. A write for version 1 reaches only A and times out without obtaining W=2 acknowledgments. Next, no new writes occur: the first read of A and B retrieves the newer version 1; after the first read completes, the second read of B and C can only retrieve version 0. Both reads satisfy R=2, and R+W>N, yet "seeing a new value first, then an old value" still occurs.

from itertools import combinations

replicas = {"A": 1, "B": 0, "C": 0}  # Numbers are ordered versions, not physical time
quorums = list(combinations(replicas, 2))
assert all(set(w) & set(r) for w in quorums for r in quorums)

def read(nodes):
    return max(replicas[node] for node in nodes)

assert read(("A", "B")) == 1
assert read(("B", "C")) == 0

# Change protocol: before the first read returns, write the selected version back to a majority.
chosen = read(("A", "B"))
for node in ("A", "B"):
    replicas[node] = max(replicas[node], chosen)
assert all(read(nodes) == 1 for nodes in quorums)

Set theory has not failed: that timed-out write never formed a successful set of W=2. If the first read wants to treat the local version as a stable, observable result, it requires additional propagation rules; after the write-back to the majority in the example above, every subsequent read of a majority will inevitably encounter that version.

This explains the motivation for Cassandra's blocking read repair to maintain monotonic quorum reads; specific guarantees are detailed in Read Repair. The model only contains a single-value, ordered version, fixed replica, and no new writes scenario; one cannot generalize "adding a repair" into a complete multi-writer linearizable algorithm. Multi-writers must also solve unique version generation, concurrent ordering, and protocol conditions for all read/write phases.

Why Does the Value Regress When Both Reads Target a Majority?

First, reading AB then BC with write-back disabled reproduces 1→0; after resetting and enabling write-back, performing the same reads allows B to acquire version 1 before the first read returns, so the second read can also encounter it. What is stabilized here is a version that has already been read: the failed write itself never received W acknowledgments and cannot be secretly counted as a successful write to apply the intersection proof.

Leaderless Read: Collecting Versions, Not Returning on the Fastest Response

The coordinator collects responses satisfying the read consistency level, then merges versions according to system rules. If one version causally covers another, the older version can be discarded; if two versions are concurrent, vector clocks can only identify concurrency and cannot arbitrarily decide which business value is correct.

For example, two clients simultaneously modify a shopping cart: one adds an item, the other deletes an item. Using set union might cause deleted items to reappear; choosing based on the latest timestamp might discard concurrently added items. The storage read path must integrate with the business rules of Conflict Resolution.

Read repair can replenish data upon discovering lagging replicas, but it may block reads or proceed in the background; it cannot be uniformly called asynchronous. Cassandra's behavior is determined by corresponding table configurations and the read path; see Read Repair.

Leader Replication: Determining Log Order First, Then Executing State Changes

Raft also uses partial replica acknowledgments, typically a majority; the difference lies in log consistency, terms, election constraints, and commit rules, which collectively maintain a committed prefix. It is not a protocol that "requires all replicas to acknowledge."

After the leader replicates the current term's log to a majority, it advances the commit according to the protocol; the commit of entries from previous terms is subject to additional rules. committed and applied are two distinct positions: the log is determined, but the local state machine may not have executed to that point yet. See the Raft Paper and this repository's Raft.

Read requests cannot be assumed to be linearizable simply because they are "sent to the leader." An old leader may not know that a new leader has been elected after a partition; a safe read requires confirming leadership, determining the read position, and waiting for the local state machine to apply to that position. Allowing reads from followers can reduce latency, but it must be explicitly clear whether it is a stale read, a timestamp-based snapshot read, or a strong-consistency read with additional synchronization conditions.

Why Might a Local Read Only See 41 When 43 is Committed?

Assume the local state has applied up to log 41, with a balance of 50; logs 42 (+5) and 43 (-2) are both committed, but the apply thread has not executed them yet. A strong-consistency read determines via protocol that it needs to read at least up to 43; it cannot directly read the current balance of 50. Merely knowing commit_index=43 does not instantly change the memory state to 53.

commands = {42: 5, 43: -2, 44: 100}
applied, balance, committed = 41, 50, 43

def read_if_ready(leadership_confirmed, read_index):
    if not leadership_confirmed or applied < read_index:
        return None  # Cannot return based on this read request's conditions yet
    return balance

assert read_if_ready(True, 43) is None
while applied < committed:
    applied += 1
    balance += commands[applied]
assert read_if_ready(True, 43) == 53
assert read_if_ready(False, 43) is None
assert applied == 43 and balance != 153  # Uncommitted 44 cannot be applied

The model takes valid leadership confirmation and the read barrier as inputs and does not implement the ReadIndex protocol. Actual systems must also ensure that the confirmation belongs to the term and protocol process that the current read request depends on, satisfying the corresponding commit prerequisites; one cannot cache the last successful heartbeat as a permanently valid True. Raft's read-only request conditions are described in Section 8 of the Raft Paper.

One confirmation resolves "whether this node is qualified to determine the safe position for this read," while the other wait resolves "whether the local state machine has executed to that point." Even if consensus network latency is low, apply queue backlog will slow down strong-consistency reads; troubleshooting should look at both the distance from commit to apply and the execution time.

Raft Log vs. Local WAL: Logical Responsibilities Can Be Separated, Physical Implementation Can Be Combined

The consensus log saves the sequence of operations decided by the cluster, while the local WAL helps the storage engine recover states that have not yet fallen into stable data files. The state machine can be an in-memory structure, B-tree, LSM engine, or other implementation; it does not need to wrap another WAL.

If a system chooses to skip the state machine layer WAL, it must prove that snapshots, persisted consensus logs, and apply progress are sufficient for recovery, and that log truncation does not delete the unique recovery source first. One cannot directly deduce "local persistence can be relaxed arbitrarily" from "Raft logs already exist."

Similarly, batch fsync, log merging, and apply batching are implementation choices. The number of disk synchronizations corresponding to a single business write should be measured and explained via source code for specific systems; one cannot apply a fixed multiplier to all distributed databases.

Hints, Repair, and Substitute Replicas

Hinted handoff saves pending write information when the target is temporarily unreachable and replays it upon recovery. It is a recovery mechanism with retention periods and capacity limits, not an additional formal replica available for any consistency level. In Cassandra, whether hints can satisfy requests depends on the consistency level; a normal quorum cannot automatically count storing a hint as an acknowledgment from the target replica. The Hints Documentation provides clear boundaries.

Sloppy quorum, on the other hand, allows reachable nodes outside the normal replica set to accept temporary replicas. This changes the premises for read/write intersection and requires subsequent migration and repair. It is a design from the Dynamo paper and should not be used to reverse-engineer the internal replication mechanism of DynamoDB from its billing model.

How to Read a System Architecture Diagram

Trace a request along the path: What is the routing basis? Who determines write order? What does ACK cover: log appending, persistence, replication, or apply? What might be left behind if the request times out? What boundary can the read see? Who replenishes missing replicas?

Throughput also considers replication network, log writing, state machine writing, compaction, and background repair. Each layer amplifies different resources. The next article, Anti-Entropy and Data Repair, continues to explain how background recovery closes this loop.

References

• Dynamo Paper: Replica Interaction and Recovery Design
• Raft Paper: Commit and State Machine Safety
• Cassandra: Read Repair
• Cassandra: Hints

Keywords: quorum, N/W/R, coordinator, leader, committed, applied, WAL, read repair, hinted handoff