Skip to content

CRAFT Design

Jump to bottom
Brian Szmyd edited this page Jul 6, 2026 · 20 revisions

CRAFT: Client Assisted RAFT

Scope. This page is the protocol: a store-agnostic design for replicating a single-writer block volume by letting the client order its own writes. It defines what CRAFT does and why it is correct, independent of any particular storage engine. It includes the client's design, which is small and stated throughout: honor the login handshake, carry the term and dLSN on every write and read, and route reads around the per-replica Missing map the client maintains. What it leaves out is the client's implementation, where the interesting choices (how the Missing map is stored and compressed, batching, retry and transport tuning) depend on the client's memory budget and transport and are not correctness-bearing. The client is not some other team's problem to wave off: during a logout the server side becomes the client (the self-elected stand-in that drives convergence while detached, see Reconfiguration), so this design has to cover that role. The concrete storage-engine implementation (component map, journal backing, durability verification, reconfiguration mechanics, and the work breakdown) lives on the companion page CRAFT on HomeBlocks.

Contents

The concrete implementation (component map, journal backing, durability verification, reconfiguration mechanics, and the work breakdown) is on CRAFT on HomeBlocks.

What CRAFT is

CRAFT (Client Assisted RAFT) is a replication protocol for single-writer block volumes. Its one defining move is to split the data path from the consensus path:

  • Data path (hot, leaderless). The single client that owns a volume assigns each write a monotonic LSN and broadcasts it directly to all replicas in parallel. A write is durable once a quorum acks the journal append. The RAFT leader plays no role here.
  • Consensus path (cold, RAFT). RAFT is used for only four things: leader election, the single-writer session (InternalLogin / InternalLogout → term + client_token + lease), recovery watermarks (SyncRSCommitLSN), and membership changes. Write data never enters the RAFT log, only LSN watermarks and session tokens do.

A second structural choice runs through everything: durability, readability, and index apply are decoupled. Appended (quorum journaled the data, durable) is what makes a write readable: an eligible replica serves appended entries directly, from the LBA index if applied, or from the journal-tail overlay if not. Committed (applied to the LBA index) happens strictly in dLSN order at the contiguous commit frontier, so every replica walks the same apply sequence and reaches the same stable state with no per-entry version checks. The client drives the frontier lazily, via commit, keep_alive, or piggybacked on the next write; it advances eagerly and independently per replica, never as a synchronous quorum step.

Glossary

Sequence numbers & watermarks

Term Meaning
LSN Log Sequence Number.
dLSN Data LSN: the per-partition number the client assigns to each write (its "position"). Dense (contiguous) within a partition. This is the only LSN CRAFT itself uses.
rLSN RAFT log index. Distinct from dLSN (data is not in the RAFT log).
last_append_lsn Highest LSN a replica has appended (present in its journal).
commit_lsn (≡ Synced) The contiguous committed prefix on a replica (Empty slots skipped): everything ≤ it is present and applied. The fill watermark.
rs_commit_lsn The replica-set commit LSN chosen at login = max(quorum.last_append).
L (login dLSN) The dLSN login returns (= rs_commit_lsn). Boundary at/below (≤) which the client cannot name a write's LBA (prior-session data).
H (readLSN / horizon) Per-read horizon: the read reflects writes ≤ H. Normally the client's contiguous quorum-acked prefix; precisely, a read may carry any H provided no unresolved slot ≤ H overlaps its range (see the failed-write note in Resync).
startLSN The joining member's promotion watermark and its backlog/tail boundary. Initialized to the replica-set dLSN at the moment of the member change; advanced to the snapshot's commit_lsn at each snapshot (re-)pin (recorded in the snapshot metadata). Promotion requires the member's commit_lsn ≥ the current startLSN.

Every LSN here is a dLSN. The watermarks and parameters in this section (last_append_lsn, commit_lsn, rs_commit_lsn, all_committed_lsn, the read horizon H / readLSN, startLSN) all live in the per-partition dLSN space. rLSN is internal to the consensus library and never appears in a CRAFT RPC, field, or watermark, so a bare _lsn suffix always means dLSN here.

Slot / write states (a slot is one dLSN on one replica)

State Meaning
Appended A write present on a quorum (durable), not yet applied to the index. Readable on an eligible replica via the journal-tail overlay, but only up to a read's horizon H. (A replica may physically hold a sub-quorum write above H that it received but that has not reached quorum: held, never served, until H passes it or it is resolved away.)
Committed Applied to the LBA index, strictly in dLSN order at the contiguous commit frontier. An apply/reclaim state, not a readability gate.
Missing A write known to exist but not held here; must be fetched from a peer (or declared Empty).
Empty A slot proven never quorum-durable (a quorum of nodes positively known to lack it). Declared only by the leader; the verdict rides SyncRSCommitLSN (empty_slots[]) or the login. A permanent no-op hole that commit skips. A non-responding minority may still hold data there; the reconciliation rule (see Resync) discards it.

Write kind (orthogonal to slot state). A slot's payload is either a data write (a reference to stored blocks) or a zero write (all_zeros, no blocks). Both are ordered by dLSN and merge identically (highest dLSN per LBA wins, data or zero). Empty is different again: not a write kind but a proven-never-durable no-op the commit skips.

Consensus & session

Term Meaning
RAFT / Raft Consensus protocol (leader election + replicated log). CRAFT uses it only on the cold path.
Paxos The older consensus family Raft descends from.
term The CRAFT session term, stored by InternalLogin (distinct from RAFT's internal election term). Bumped on each login, including the forced re-login after a membership change, and carried on every IO to fence stale clients.
client_token Identifies the single writer; set by InternalLogin.
quorum A majority of the replica set (2 of 3).
f Number of tolerated failures (f = 1 for a 3-node set).
RS / Replica Set The nodes holding one partition's copies (typically 3).
partition The independent replica-set CRAFT replicates. A volume comprises one or more partitions; a given LBA maps to exactly one partition, so overlapping writes always land in the same partition (which is why the per-partition dLSN is a sufficient merge key).
volume Comprises one or more partitions. CRAFT operates per-partition (dLSN).

RPCs, RAFT entries & rules

Term Meaning
SyncRSCommitLSN RAFT entry that advances the replica-set commit watermark; the primary resync trigger. Carries the client_token (session verification) and the leader's empty_slots[] verdicts; the leader resolves every slot ≤ the watermark before proposing.
InternalLogin RAFT entry that sets client_token + term (single-writer enforcement).
InternalLogout RAFT entry recording logout / lease expiry: marks "no active client" and authorizes the leader stand-in.
lease Locally-evaluated client liveness (the watchdog); acted on only once InternalLogout commits.
watchdog Per-replica client-liveness timer, reset by writes / keep_alive; expiry triggers GetRSCommitLSN + SyncRSCommitLSN, and past the lease, the logout path.
GetRSCommitLSN Non-RAFT peer query of a replica's {commit_lsn, last_append_lsn}. Carries the is_login quiesce flag. Code: get_rs_commit_lsn / get_lsns.
keep_alive Client RPC: commit + watchdog reset. Its response carries {commit_lsn, last_append_lsn}, feeding the client's Missing map and the reconfig promotion gate; its request carries all_committed_lsn so members can reclaim journal opportunistically.
FetchData Non-RAFT peer pull of missing journal slots (the resync data path).
ETERM / ENOTLEADER Rejection codes: stale session term on IO; login sent to a follower.
overlay read A read served directly from an appended-but-not-yet-applied journal entry (the journal-tail overlay). No index write happens on the read path. (Formerly CommitAndRead, before apply became strictly in-order.)
journal-tail overlay Per-replica in-memory map (LBA → highest-dLSN unapplied entry) over (commit_lsn, last_append]; rebuilt from the journal on restart. What makes appended entries readable before apply. Reads consult it only up to the horizon H; entries above H (the not-yet-quorum tail) are held but never served.
all_committed_lsn The set-wide floor: min over voting members' reported commit_lsn. Computed by the client from keep_alive/commit responses (or by the stand-in leader from polls) and piggybacked back out so members reclaim journal opportunistically.
merge key The convergence rule: highest dLSN per LBA wins, on every replica.

Conceptual touchstones

Term Meaning
PacificA Primary-backup replication framework (consensus only for config); a CRAFT touchstone.
CORFU Shared-log storage architecture (clients write directly to storage units); a CRAFT touchstone.

The concrete components (the replication-device class, the journal backend, the RPC frontend, and the membership binding) are defined on CRAFT on HomeBlocks.

Storage & durability

Term Meaning
LBA Logical Block Address.
FUA Force Unit Access: every write is durable on completion (write-through; no writeback cache, no FLUSH).
thin The volume is thin-provisioned: an LBA never written holds no storage and reads as zero. CRAFT preserves thinness end to end (write, read, resync).
all_zeros (zero write) A write that names only an LBA range, with no payload (the WRITE_ZEROES / discard-to-zero op). It carries a dLSN and merges like any write, but allocates nothing; on apply it unmaps the range.
hole A sub-range of a read result that carries no data: never written, unmapped by a zero write, or an all-zero region collapsed at read time. Returned as a marker, not a materialized zero buffer; the reader treats it as zeros. A hole is not Missing (a hole is a resolved answer; Missing means "fetch this slot").

Background: Raft, Paxos, PacificA, CORFU, and CRAFT

CRAFT borrows one idea each from a few well-known systems. If these names are unfamiliar this is the quick map; if they're familiar, it pins down exactly which idea CRAFT takes from each.

Raft & Paxos: consensus protocols. Both solve agreement among distributed nodes despite failures: how a set of replicas commit to the same ordered log of operations. Paxos is the older, foundational family; Raft was designed to be easier to understand and implement while giving the same replicated-log guarantees (an elected leader replicates an ordered log to followers). They answer "how do replicas agree?"

PacificA: primary-backup replication for storage. A framework for keeping replicas of a log-based storage shard consistent. A primary orders the writes and forwards them to backups; correctness across failures is delegated to a separate, consensus-backed configuration manager that owns membership. The key idea: keep consensus off the per-write path and pay for it only on rare reconfiguration. It answers "how do I replicate a storage shard with a primary and backups?"

CORFU: a shared-log architecture. Turns a cluster of flash devices into one global append-only log shared by many clients. A sequencer hands out log positions; clients then write directly to the storage units at those positions (no primary in the data path); a separate consensus-backed layer handles reconfiguration and hole-filling. It answers "how do I expose one global durable log across many devices, with clients writing directly?"

How they layer. Raft/Paxos are general-purpose "get a consistent log." PacificA is a specific primary-backup replication scheme with consensus only for config. CORFU is a shared-log abstraction others build on, where clients write straight to storage.

System The question it answers
Paxos / Raft How do replicas agree on an ordered log?
PacificA How do I replicate a storage shard with a primary + backups, keeping consensus off the write path?
CORFU How do I expose one global durable log across many devices, with clients writing directly?
CRAFT How do I replicate a single-attach block volume when the client itself can order the writes?

How CRAFT fits. CRAFT takes one idea from each and specializes it for single-attach block volumes:

  • From PacificA: keep consensus off the write path; use a separate consensus layer only for configuration-class decisions. CRAFT's consensus layer is Raft, and it touches only the cold path: leader election, InternalLogin (who is the single writer + term), SyncRSCommitLSN (recovery watermark), and membership. Raft here plays exactly PacificA's "configuration manager" role. The twist: PacificA still has a primary node that orders and forwards writes; CRAFT has no data-path primary at all.
  • From CORFU: the writer assigns positions (LSNs) and writes directly to every storage replica, bypassing any leader/primary on the hot path. The difference: CORFU runs a separate sequencer serving many concurrent clients over a shared log; CRAFT relies on block volumes being single-attach, so the one client per volume is its own sequencer: no sequencer service and no per-write coordination.

In one line: CRAFT = CORFU-style direct-to-replica writes by a client that is its own sequencer, with Raft as a PacificA-style configuration manager that never touches the data path. That combination is only safe because a block volume has a single writer (see The contract CRAFT owes).

PacificA to CORFU to CRAFT: the same design elements

The lineage in one picture: consensus (blue) stays off the data path in all three, the data path (orange) gets more direct, and the sequencer (yellow) moves from an external service in CORFU into the single client itself in CRAFT. The bottom band places CRAFT among the block replicators: some carry the write through a leader or ordered chain (Ceph, EBS, arrays); DRBD and RAID1 are already leaderless single-writer broadcast, and CRAFT's one clean data-path delta is quorum-ack (never wait for the slowest replica); the rest (leaderless, stale-replica reads, peer resync) it shares and refines, not invents (see the feature matrix below).

Adjacent systems: where CRAFT sits. The four above are conceptual ancestors (where CRAFT's ideas come from). The systems CRAFT sits among are block-volume replicators, compared by feature below. The honest read of this table: CRAFT is not the first leaderless block replicator (DRBD is already there) and not the first to read from a stale replica (RAID1 does that too); it shares most columns with DRBD9/RAID1, and its one clean, isolated win is quorum-ack. Everything else it inherits or refines.

System Replicas Leaderless data path Write hops to ack Read hops Quorum-ack (not sync-to-all) Read from a stale replica Server-side resync Consensus off data path
Ceph RBD N (3) ✗ primary OSD 2 1 (primary) ✗ ✗ ✓ ✓ Paxos mons
Amazon EBS 2 * ✗ chain R (chain) 1 ✗ commit at tail ✗ ✓ ✓ Physalia
Array / controller 2 ✗ controller 2 1 ✗ ✗ ✓ ✗
RAID1 (md) 2 ✓ 1 1 ✗ all mirrors ✓ coarse § ✗ host-driven ✗
DRBD9 2-N (≤32) ✓ 1 1 ✗ sync-to-all † ~ gated ¶ ✓ peer-to-peer ~ own quorum ‡
CRAFT 2-N (≤20) ✓ 1 1 ✓ ✓ per-write ✓ ✓ Raft

Legend: ✓ yes, ✗ no, ~ partial. Write hops to ack = serial network traversals before a write is durable: a parallel broadcast fans out in 1, routing through a primary adds one (2), a chain adds one per replica (R); this is the latency axis in "Why broadcast-quorum, not chain replication" below. Read hops = 1 for everyone (unicast to one replica); CRAFT serves even uncommitted data from that replica's overlay, so it stays 1 hop with no peer fetch. * EBS replicates within an AZ as a short chain; exact count is not public. † DRBD9's majority quorum governs write permission (split-brain avoidance), not per-write majority-ack; a healthy protocol-C write is synchronous to every connected peer, so it waits for the slowest. ‡ DRBD9 quorum is built in, but fencing is usually delegated to an external cluster manager (Pacemaker/STONITH). § md RAID1 already serves reads from a partially-synced mirror: read_balance picks a rebuilding disk for sectors below its recovery_offset watermark, and the write-intent bitmap lets it route around dirty regions. This is coarse (linear watermark / region bitmap) and 2-way; CRAFT's version is per-dLSN, N-way, and client-routed (the "multi-dimensional dirty-bitmap" of the read deep-dive). DRBD gates application reads on an UpToDate peer; serving from a resyncing (SyncTarget) node is not the normal path.

What the table says (honestly). CRAFT shares most of this table with DRBD9/RAID1: leaderless, 1-hop writes, single-hop reads, peer resync, and even reading from a partially-synced replica (RAID1 pioneered that with its recovery watermark). The one column where CRAFT is genuinely alone among these block replicators is quorum-ack: it commits a write at a majority, so a write never waits for the slowest up replica (the laggard becomes Missing and resyncs), the latency-under-a-slow-replica property none of the sync-to-all systems have. The stale-replica read is not new either; CRAFT generalizes RAID1's 1-D watermark to a per-(replica, LBA, dLSN), N-way, client-routed map, a granularity refinement, not a new capability. The write-hops column draws the latency picture the "why not chain" argument rests on. Net: CRAFT is a refinement of the DRBD/RAID1 line (quorum-ack for latency, finer-grained dirty state, consensus-integrated membership/fencing) on a log-structured storage substrate, not a new category. That is the honest claim, and it is still worth building.

Related work (closest prior art). Beyond the ancestors above and the matrix systems, the nearest published designs are: Hermes (ASPLOS 2020), a broadcast-based, leaderless, linearizable protocol with logical timestamps and local reads, which CRAFT resembles minus the multi-writer invalidation machinery that single-attach lets it drop; CRAQ (USENIX ATC 2009), which apportions reads across chain replicas with versioned entries and a tail check for dirty objects; ABD (Attiya, Bar-Noy, Dolev, JACM 1995), the classic majority-quorum replicated register that a block device is an array of; Dynamo (SOSP 2007), quorum writes with last-writer-wins and hinted handoff, the lineage of CRAFT's merge key and Missing-map resync; and Longhorn (CNCF), the closest shipping single-writer fan-out block engine. Full citations in References.

Why broadcast-quorum, not chain replication. Chain replication (EBS) sends a write head to tail down the replica chain, one hop each, so the client uplink carries the write only once and replica-to-replica traffic stays in the storage tier. Its whole advantage is bandwidth locality, and it pays off only when that replica-to-replica traffic rides a separate or cheaper storage fabric (FC SAN, RDMA backend, a dedicated storage network). The target deployment has none: one generic Ethernet, shared top-of-rack switches for client-to-storage and storage-to-storage alike, symmetric PHYs (25 to 100 Gbps). On a shared fabric the aggregate is topology-invariant: a write of size W at RF=3 injects 3W into the same switches whether the client broadcasts it or the chain forwards it, so chain's locality advantage evaporates.

What remains is where the egress originates, and on a shared fabric that favors broadcast. Chain shifts 2W of egress onto storage NICs (the head and middle nodes each receive and forward, 2x); broadcast keeps storage NICs at 1x (receive only) and concentrates 3x on the client. For single-attach that is the better allocation: client hosts are sparse (few volumes each), storage nodes are dense (many volumes each), so sparing the storage NICs from forwarding is the right trade. CRAFT's steady-state storage-to-storage traffic is near zero (that path is resync-only); chain is storage-to-storage on every write.

With bandwidth neutralized, latency decides, and broadcast wins: one round-trip to quorum versus up to N serial hops to the chain tail. The residual cost is the client host's NIC egress (3x the aggregate write bandwidth under broadcast), a per-client provisioning ceiling of about NIC/3 (roughly 1 GB/s per client at 25 Gbps, 4 GB/s at 100 Gbps), not a fabric bottleneck; chain would only relocate those bytes onto the same shared storage NICs while adding hop latency. So CRAFT takes the latency win and accepts client-side egress concentration, which single-attach makes cheap. On a dedicated storage fabric this calculus flips and chain is the better choice: that is the deployment assumption to revisit if it ever changes.

The contract CRAFT owes (block-device semantics)

CRAFT is a single-writer block device, not a transactional or linearizable store. Holding it to the right (weaker) contract is what makes the design tractable. It owes exactly:

  • Durability: a write that was acked survives crash, up to f failures. All CRAFT I/O is FUA (see Durability model): there is no FLUSH op and no writeback cache, so "acked" already means "durable." Un-acked (in-flight) writes have undefined outcome on crash; the filesystem/application owns crash consistency for them. We do not treat in-flight writes as transactions.
  • Read-after-write: only for causally ordered ops (the app waited for the write's ack before issuing the read). Concurrent read+write to the same LBA is a race with an undefined result, by the block contract.
  • Read stability: once a newer value of an LBA has been observed, a later read does not regress to an older one.
  • Replica convergence: all replicas eventually agree on the same value per LBA.

Not owed: cross-LBA ordering, atomicity of concurrent overlapping writes, transactions.

Consequence: there is no order among in-flight I/O. All submitted I/O races naturally; the application serializes (waits for ack) when it needs ordering. So the dLSN is not preserving application order (there is none for concurrent I/O). Its job is to be a deterministic merge key: highest dLSN to an LBA wins, on every replica, so replicas converge to the same value even when two writes race. The client assigns dLSNs in submission order; "highest-LSN-per-LBA wins everywhere" is the whole rule. No overlapping-write serialization logic is needed.

Why (motivation)

  1. Kill the leader bottleneck. Classic RAFT funnels every byte through the leader (client → leader → log → fan-out → apply). The leader's egress is N× the write bandwidth and it double-writes (log, then state machine). CRAFT pushes the fan-out onto the client and writes data to the journal once, a throughput and write-amplification win.
  2. Lower write latency. Client → replica broadcast is one hop to durability (quorum append) vs. two through a leader.
  3. The single-writer constraint is essentially free here. Block volumes are single-attach (EBS-like), so there is naturally one writer per volume. Given one writer, that writer is the total-order authority. You don't need consensus to order writes. That is the load-bearing insight that makes a leaderless, consensus-free data path safe. RAFT is then only needed for the genuinely ambiguous things: who is the one writer (split-brain) and what is durable after a crash (recovery watermark).
  4. Keep RAFT small and off the hot path. Login and resync are low-frequency, so the RAFT log stays tiny and never carries data.

Durability model: FUA write-through

All CRAFT I/O is FUA (write-through): every write is durable the moment it is acked. A guest FLUSH is accepted and acked immediately as a satisfied no-op: under FUA-always nothing is ever cache-dirty, so there is nothing to flush (a filesystem journal commit that issues PREFLUSH still gets success, correctly, because everything it would flush is already durable). FLUSH is also not an ordering barrier, and never was: since Linux removed hardware I/O barriers (2.6.37, 2010) the block layer provides no reorder fence at all. Ordering is the guest's, enforced by waiting for a write's completion before issuing the next, and CRAFT honors exactly that, because a completion (ack) means quorum-durable: the earlier write is durable before the next is even submitted. So no ordering among in-flight I/O, acked = durable is not a weakening, it is the literal block contract. (The only media-level guarantee beyond durability is single-write atomicity via RWF_ATOMIC / atomic write units, which is nascent and which CRAFT does not yet expose.) Durability must be write-through; otherwise a simultaneous restart of all replicas could lose acknowledged writes.

Requirement on the journal backend. A CRAFT write must await the journal-append completion before acking the client, and that completion must fire only after the bytes are on stable media, never on buffering. Given that, quorum-ack implies quorum-durable implies an all-replicas restart cannot lose an acked write. A write-through, group-committing journal satisfies this directly: concurrent appends batch into one synchronous device write and ack together, which suits the broadcast-and-await-quorum pattern. Device-level power-safety (the drive honoring FUA / write-cache-off / power-loss-protection) is a deployment property the backend inherits.

The concrete verification that this backend requirement is met, with source references, is on CRAFT on HomeBlocks.

Login

Login establishes a new term, converges replica state to a starting dLSN, and enforces single-writer exclusivity, all before any IO is accepted. It is leader-only; a follower replies ENOTLEADER plus the leader endpoint.

sequenceDiagram
    autonumber
    participant C as Client (initiator)
    participant L as Leader (S1)
    participant S2 as Replica S2
    participant S3 as Replica S3

    C->>L: login(client_token, vol_id)
    Note over L: Leader-only. Follower replies<br/>ENOTLEADER + leader endpoint.

    Note over L,S3: Phase 1: collect replica LSN state (non-RAFT broadcast)
    L->>S2: GetRSCommitLSN(is_login=true, term, my_commit, my_append)
    L->>S3: GetRSCommitLSN(is_login=true, term, my_commit, my_append)
    S2-->>L: {commit=5, last_append=7}
    S3-->>L: {commit=10, last_append=11}
    Note over L: rs_commit_lsn = max(quorum.last_append) = 11

    opt Leader behind (self.last_append < 11)
    L->>S3: FetchData(missing slots up to 11)
    S3-->>L: JournalSlot[] (lba,len,data)
    Note over L: append to own journal
    end

    Note over L,S3: Phase 2: SyncRSCommitLSN(11) via RAFT (data NOT in log)
    L->>S2: RAFT replicate SyncRSCommitLSN(11, token)
    L->>S3: RAFT replicate SyncRSCommitLSN(11, token)
    Note over S2,S3: on apply, if behind FetchData up to 11.<br/>commit_lsn = 11. (no truncation here, login-only step below)

    Note over L,S3: Phase 3: InternalLogin(token, term+1) via RAFT
    L->>S2: RAFT replicate InternalLogin(token, T+1)
    L->>S3: RAFT replicate InternalLogin(token, T+1)
    Note over S2,S3: store client_token, term=T+1.<br/>reject IO with any other term

    Note over L,S3: Phase 4: truncate stale tail (login-only, after InternalLogin commits)
    L->>S2: truncate(11) if last_append > 11
    L->>S3: truncate(11) if last_append > 11
    Note over L: leader truncates its own tail too<br/>if last_append > 11
    Note over S2,S3: drop appended-but-not-quorum entries above rs_commit_lsn

    L-->>C: LoginResult{members, dLSN=11, term=T+1}
    Note over C: open a queue per member, begin IO at dLSN+1
Loading

The watermark rs_commit_lsn = max(quorum.last_append) is forced, not a tuning choice; see the recovery-watermark deep-dive. The poll set includes the leader itself (its {my_commit, my_append} ride the request), so the max is taken over a quorum of the full member set. Only last_append feeds the watermark; the polled commit_lsn serves the other jobs of this RPC: it is a contiguity certificate (everything ≤ it is applied on that member, no holes), so it bounds the leader's fetch-or-verdict work to (min commit, rs_commit], seeds the journal-reclaim floor (all_committed_lsn, the leader's only source when no client is attached), and carries the reconfig promotion gate on watchdog polls.

Everything in this protocol is per-partition: one replication instance, one RAFT group, one term, one login, one dLSN space per partition. A client attached to a multi-partition volume runs an independent CRAFT session per partition.

Fencing the old session (quiesce barrier). A replica quiesces old-session writes the moment it receives the login poll: GetRSCommitLSN carries an is_login flag, and on it a replica stops acking data writes from any prior term, then reports last_append. This makes max(quorum.last_append) capture every write quorum-acked before the barrier (quorum intersection), so login truncation above rs_commit_lsn can never discard an acked write, and a would-be zombie writer is rejected (explicit error) rather than acked-then-silently-truncated. Watchdog/periodic GetRSCommitLSN polls carry is_login=false and never quiesce (they ride the live tail). The quiesce releases on either of: an explicit login-aborted signal the leader sends when it cannot reach quorum, or a replica-side quiesce timeout (a small multiple of the login round-trip) that fires if that signal is lost, so a failed or partitioned login can never wedge the current owner. Assumption: the attach layer (CSI) should also hard-fence the prior client on failover (reservation / network revoke); the quiesce barrier is CRAFT-side defense-in-depth.

Leader behind (Phase 1b) fallback. The leader fetches missing slots ≤ rs_commit_lsn from any peer holding each; a slot ≤ rs_commit_lsn absent from the whole responding quorum was never quorum-durable and is marked Empty. If a quorum cannot be reached, the login fails and the client retries (or RAFT elects a new leader).

Write, Commit, Read, and readLSN protection

Write. The client assigns ++next_lsn, broadcasts write(term, lsn, lba, len, data) to all replicas. Each validates term, appends the data to its journal at slot lsn (zero-copy, may arrive out of order), advances last_append_lsn, and acks, per write, since in-flight I/O is unordered. Durable at quorum-ack (Appended), and readable once Appended on an eligible replica: served from the journal-tail overlay until it is applied. A replica may receive a write before it is quorum-acked (the client broadcasts to all) and does journal it, but that sub-quorum entry sits above the horizon H, and a replica serves only versions ≤ H (see Read): it is held, never read, until the write becomes quorum-durable (H passes it) or is resolved away. That is exactly what makes eager broadcast safe: a lone replica holding a not-yet-quorum write cannot leak it. No LBA-index update happens on the write itself.

Thin writes (all_zeros). A write comes in two forms. A data write carries a payload (the case above). A zero write names only its range, write(term, lsn, lba, len, all_zeros), with no payload: the WRITE_ZEROES / discard-to-zero op. It still takes a dLSN and is appended, journaled, and quorum-acked exactly like a data write, and it merges by the same rule (highest dLSN per LBA wins, data or zero), so a later zero write correctly overwrites earlier data and a later data write correctly overwrites an earlier zero. It just carries no blocks; on apply it unmaps its range (see Read for how that reads back). The client emits a zero write when a cheap client-side scan finds an all-zero buffer, which keeps a thin volume from allocating storage for zeros. The server does not re-scan an ordinary data write (no double scan), so an all-zero buffer that still arrives as a data write is stored as data, correctly but not thin-optimally; the read path normalizes it back to a hole (below).

Commit (apply): strictly in dLSN order. In-flight I/O has no block-level order, but replicas must converge, so they need an agreed order, and dLSN is that order (client-assigned, total). CRAFT enforces it by apply order, not by version checks: the index applies entries only at the contiguous commit frontier (commit_lsn), in dLSN order, skipping Empty. Blind overwrite is then correct by construction, every replica reaches the same stable state, the index at any checkpoint is an exact prefix of the write history (clean snapshots), and crash recovery is deterministic (prefix, then in-order replay, then overlay). The rejected alternative, out-of-order apply, would need a dLSN version in every index entry (overwrite-iff-higher) plus partial-overlap splits and stale-block accounting. Superseded blocks are reclaimed at apply time. The client drives the frontier (lazily, via commit / keep_alive / piggyback); readability is per-write and does not wait for it: a higher LSN is readable (overlay) while a lower one is still a hole, with overlaps resolved by the merge key (highest LSN per LBA wins, enforced by the apply order and, above the frontier, by the overlay tracking the highest dLSN per LBA).

The per-partition scalar commit_lsn (≡ Synced) is the contiguous applied prefix, the highest LSN with no unresolved hole below it (Empty slots are skipped). It is the fill watermark used by resync and reconfiguration, and the read gate in the ≤ L region (below); individual writes above it are readable from the overlay, which is why readability is not tied to it.

commit() is best-effort per replica: it advances commit_lsn to just below the first Missing hole (applying present entries in order, skipping Empty) and returns the achieved watermark; a stall at a hole is not an error (resync fills it), and it pauses only apply + block reclaim above the hole, never reads. Recovery: the journal is FUA-durable and is only reclaimed below the checkpointed frontier, so on restart the replica rebuilds the overlay (its appended-above-commit_lsn set) from the journal; every appended entry is again readable, so no readable slot (≤ H, hence covered by the horizon guarantee) is ever lost.

Read: the readLSN protection. Reads are unicast to one replica, and the client decides where it is safe to read: it knows the LBA range of every write it issued. Each read carries a horizon H (the readLSN) = the client's contiguous quorum-acked prefix: every LSN ≤ H above L is quorum-durable (acked, not merely submitted), and everything ≤ L is covered by the login watermark guarantee (held in full by the login leader). Either way, a read never reflects a write that could vanish, and a servable replica always exists. The replica returns the latest version ≤ H for the range: if that write is not yet applied, it serves it straight from the journal-tail overlay (an overlay read: it already holds the data, so no fetch, and no out-of-order index write); writes above H are ignored even if the replica holds them (the sub-quorum tail, see below). A replica may serve read([lba, lba+len), H) iff:

  1. it is filled up to the login dLSN L (Synced ≥ L; L = the dLSN login returned = rs_commit_lsn). At/below L are prior-session writes whose LBAs the client can't name, so it must hold all of them; and
  2. above L, it has no Missing slot ≤ H overlapping [lba, lba+len); the client checks this against its LBA-aware per-replica Missing map.

So readability is per-LBA-overlap, not "no holes": a hole on an unrelated LBA does not block the read. Because the client only routes a read to a replica that can serve it, the read path never fetches from a peer. Inline fetch is resync-only. Consequence: login cannot complete until ≥1 member is filled to L (the leader fetches itself whole during login), and that member is the sole reader until each peer independently reaches Synced ≥ L.

Thin reads (holes). A read returns a sparse result: data extents interleaved with holes. For each LBA in the range the replica takes the highest-dLSN slot ≤ H that covers it and decides: a data slot yields a data extent; a zero slot, or an LBA that no slot ≤ H covers, yields a hole. As a final step it also scans the data it would return and collapses any all-zero region to a hole, so a data write that happens to hold zeros reads back thin just like an explicit zero write (this is where the server's read-time scan lives, deliberately not on the write path). A hole is returned as a marker; the client reads it as zeros and allocates nothing. Crucially a hole is not Missing: a hole is a resolved "reads as zero here" answer, while Missing means "this replica lacks the slot, route elsewhere". The client routes reads around Missing slots (eligibility above); it never routes around holes, which are a normal servable answer. Overlay reads are unaffected: a tail slot ≤ H may be a zero write, and the overlay tracks it as the highest-dLSN entry per LBA just like a data write.

Two-sided read safety (why a sub-quorum write can't leak). The eligibility rule above is the client side: never route a read to a replica missing a needed write ≤ H. The replica side is the horizon clamp: it serves only the latest version ≤ H, so a not-yet-quorum write it happens to hold (an entry above H, e.g. a broadcast only it received) is held but never returned. Both guards are needed and both key off H. There is no race: H is fixed when the read is issued and is monotonic (the client advances it past a write only once that write is quorum-acked), so a read that reaches a replica while a higher write is still sub-quorum simply ignores it, and the next read carries a higher H. The replica never needs to know quorum status; H carries that knowledge for it.

sequenceDiagram
    autonumber
    participant C as Client (initiator)
    participant R1 as Replica (overlapping hole)
    participant R2 as Replica (eligible)

    Note over C: horizon H = client's contiguous quorum-acked prefix.<br/>Client knows every write's LBA and each replica's Missing map.
    Note over C,R1: R1 has a Missing slot <= H overlapping [lba, lba+len) -> INELIGIBLE, skip
    Note over C,R2: R2 filled to L (Synced >= L) and no overlapping Missing <= H -> eligible
    C->>R2: read(term, H, lba, len)
    Note over R2: serve latest <= H from the index, or from the<br/>journal-tail overlay if not yet applied (no fetch). ignore anything above H
    R2-->>C: data
    Note over C,R2: Client routes only to a servable replica, so the READ PATH NEVER FETCHES.<br/>Peer fetch is resync-only.
Loading

CRAFT quorum-but-not-in-sync: LBA-overlap read routing

Worked example: three replicas with independent apply frontiers (everything quorum-durable is readable via the overlay, up to H); a read of LBA 13 that the client routes around S1's hole, served by S2 with no read-path fetch; and a sub-quorum in-flight write (106, received by S1 only, above H): next_lsn has moved to 107, but H holds at 105, and a replica serves only ≤ H, so S1 holds 106 without ever returning it until it quorum-acks or is resolved.

Two regions, split at the login dLSN L. At/below L are prior-session writes the client can't reason about per-LBA, so a member needs a full contiguous fill (Synced ≥ L) before it serves any read. Above L are this session's writes, gated per read by LBA-overlap. Synced ≥ L is the same "reach the watermark" gate as reconfig promotion (commit_lsn ≥ startLSN).

The client's job: keep an accurate LBA-aware Missing map per replica. It removes entries on write-ACKs, and learns resync-fills from {commit_lsn, last_append_lsn} carried in each keep_alive / get_lsns response (pruning any Missing slot ≤ that replica's commit_lsn); staying conservatively stale when unsure (treat a slot as Missing, route elsewhere) is safe, at the cost of under-using a replica. From the same reports it computes all_committed_lsn (the set-wide min) and piggybacks it on its next keep_alive/write, letting members reclaim journal opportunistically (the journal-reclaim floor, defined under Resync below). The map is interval-compressed and bounded: on overflow it collapses that replica to a single dirty-window summary (ineligible for reads until the commit_lsn certificate clears it; see the degraded-member note in Resync). After login the client initializes the horizon H := L: every slot ≤ L is held by the fully-filled login leader, and the Synced ≥ L gate routes reads at that horizon only to filled members, so reads are safe there while Phase-2 resync restores full replication in the background. (A slot ≤ L held by the leader alone means its other holder is already unavailable; losing the leader too before resync heals is a second failure, the same dual-failure accounting as the reconfiguration live-tail note.) Above L, the client advances H with its own contiguous quorum-acked prefix. H is per-read, and the precise safety rule is: a read may carry any H provided no unresolved slot ≤ H overlaps its range (a failed sub-quorum write is unresolved until the leader's round fills or Empties it; see Resync). So a failed write fences only the ranges it overlaps, never the whole horizon: acked writes above it stay readable.

Resync / catch-up: the FetchData loop

SyncRSCommitLSN is the primary recovery mechanism. It carries only an LSN watermark plus Empty verdicts (no data). The leader resolves every unresolved slot ≤ the watermark before proposing (below); on apply, a replica that is behind fills its missing slots from its peers, obeys the verdict list, then advances its commit watermark.

sequenceDiagram
    autonumber
    participant L as Leader (S1)
    participant S3 as Lagging replica (S3)
    participant P as Ahead peer (S2)

    Note over L,P: Trigger: login / keep_alive watchdog / periodic checkpoint<br/>(every N LSNs) / client request (failed write)
    Note over L: leader resolves every unresolved slot <= N first:<br/>fetch it from a holder, or record an Empty verdict on<br/>quorum-lacks evidence. never proposes past an unresolved slot
    L->>S3: RAFT replicate SyncRSCommitLSN(N, token, empty_slots[])
    L->>P: RAFT replicate SyncRSCommitLSN(N, token, empty_slots[])

    Note over S3: on apply: last_append < N<br/>=> missing slots {m1..mk} <= N
    loop until no missing slot <= N
        S3->>P: FetchData([missing lsns])
        S3->>L: FetchData([missing lsns])
        P-->>S3: JournalSlot[] {lsn,lba,len,data | all_zeros | is_empty | omitted}
        L-->>S3: JournalSlot[] {lsn,lba,len,data | all_zeros | is_empty | omitted}
        Note over S3: fill present slots (leader guaranteed to hold<br/>every non-Empty slot <= N). slots in empty_slots[] are<br/>permanent no-op holes: discard any local data there
    end
    Note over S3: commit_lsn = N (contiguous Synced<br/>watermark advances through N)

    Note over L,P: New/replacement member: bulk BACKLOG (<= startLSN) arrives first<br/>via the snapshot path (checkpoint-sourced index+blocks). THIS loop fills the<br/>tail. Promote learner -> voter when commit_lsn >= startLSN.
Loading

Declaring Empty (leader verdict). FetchData returns one of present+data, present+zero (an all_zeros write, no payload), not-present-here, or known-Empty, per slot. The peer's obligation is exact: it returns is_empty=true only for a slot it has positively marked Empty (via a prior verdict); for a slot merely absent from its journal it omits the entry from the response (that reads as not-present-here). So a responder never reports Empty for data it simply lacks. The verdict itself is made in exactly one place: the leader, as a precondition of proposing SyncRSCommitLSN(N). The leader resolves every unresolved slot ≤ N: it fetches the slot from any holder (after which it can serve it to the others), or, when a quorum of nodes is positively known to lack it (itself included; non-responders never count), records an Empty verdict. With N=3 the leader plus one confirming peer suffices, and it is safe by quorum intersection: any quorum known to lack a slot intersects every possible write quorum, so a quorum-durable write can never be declared Empty. If the leader can assemble neither a copy nor a confirming quorum, it does not propose past the slot. Verdicts ride the entry (empty_slots[]), so fill-vs-Empty is RAFT-serialized: replicas never declare Empty unilaterally (two replicas racing under asymmetric reachability could otherwise diverge, one filling from a holder while the other declares Empty off a timeout), they fill present slots and obey the verdict list. Commit advances past Empty slots but never past an unresolved Missing one. This makes mid-session resync structurally identical to login Phase 1b.

Reconciliation (Empty beats held data). A replica can hold Appended data in a slot the leader has since declared Empty (e.g. it was unreachable during the verdict round). On applying the entry that carries the verdict (or the login entries, for login-declared Empties) it discards that data. This is safe for the same reason login truncation is safe: a verdict-Empty slot was provably never quorum-durable, so the data was never acked, and discarding it is what keeps replicas convergent. Held data can never have been applied before the verdict arrives, because of the resolved-prefix rule below.

Resolving a failed (sub-quorum) write. A write that reaches only a minority (slot k lands on A alone; B and C never ack) is surfaced to the app as an IO error: it was never acked, so its outcome is undefined and both futures are legal. The client does not undo anything (it cannot even distinguish "B never appended" from "B appended and the ack was lost"); it requests an immediate resolution round (the client-request SyncRSCommitLSN trigger) instead of waiting for the periodic cadence. The leader resolves k like any other slot: fetch it from A, in which case the failed write simply completes late (the same benign false-include as the login watermark), or verdict it Empty if A is unreachable (A discards its copy via reconciliation when it rejoins). The failed slot is never reused: a retry of the same app write gets a fresh dLSN. Two invariants keep the unresolved window safe:

  1. Resolved-prefix-only. The client's commit targets and the leader's sync watermarks only ever cover resolved slots, so no replica, including the holder A, applies k before the verdict. No un-apply path is ever needed.
  2. Unresolved-slot read fencing (client). An unresolved slot acts like a Missing slot on every replica in the client's map. A read of a range it overlaps either runs at a horizon below it (serving the old data, which is stable under both futures) or, if the range also carries a later acked write, stalls until resolution: stalling is contract-compliant, while serving stale data for an acked write, or serving the unresolved data that an Empty verdict would then take back, is not. Ranges that do not overlap the failed slot are unaffected: acked writes above it stay readable throughout (per-read H + overlay).

Degraded member: bounded Missing tracking and re-admission. Missing sets are interval-compressed on both sides (a contiguous outage is one range, not one entry per write), and the client's per-replica map is bounded: past the bound it collapses to a single summary, "dirty over (X, Y], LBAs unknown", keeping live tracking above Y while the member is reachable. A summarized member serves no reads (an unknown-LBA window can overlap anything): the window behaves exactly like the below-L region, a stretch whose LBAs the client cannot name, healed only by a full contiguous fill. The client keeps broadcasting writes and keep_alive to it while reachable (the live edge stays warm, so resync owes only the window) and may fire the client-requested sync trigger to hurry healing. Re-admission needs no new machinery: the commit_lsn contiguity certificate in each keep_alive / get_lsns response clears the summary once it reaches Y, the same rule that prunes individual Missing entries. A member whose window fell past the journal retention floor takes the snapshot path instead (baseline resync); the concrete trigger that fires it is on the implementation page.

Journal reclaim (bounding the log). The journal is not kept forever. Each member may reclaim slots below a floor = min(checkpointed apply frontier, all_committed_lsn). The first term is local crash-safety: the journal backs the overlay and index replay, so a member never reclaims above what it has durably applied. The second is the peers' resync reach: all_committed_lsn is the min commit_lsn over voting members, which the client computes from the {commit_lsn, last_append_lsn} in each keep_alive / commit response and piggybacks on its next message, so every member may truncate below it (a member never re-fetches below its own monotonic commit_lsn, so a stale min is merely conservative). Login converges the whole set exactly (Phase 2 drives everyone to rs_commit_lsn); between logins the piggyback advances it opportunistically. A silent member freezes the min until the retention window relegates it to the snapshot path, which is what lets the log stay bounded without freezing membership. When no client is attached, the stand-in leader computes and distributes the same value from its polls.

Thin resync. Because reads and fetches expose holes (a never-written or zero-written range returns no data), baseline resync and FetchData copy only the mapped extents; the receiving member allocates nothing for holes, so a thin volume stays thin across a resync or a member replace. A fetched slot that is a zero write carries the all_zeros marker (distinct from Empty and from omitted), which the lagging member applies as the same range unmap.

Truncation is login-only. SyncRSCommitLSN apply (watchdog / periodic) never truncates: above-watermark appends are the live tail the current client is still writing. Truncation above rs_commit_lsn is a login-only action, performed by the leader on every member (itself included) after InternalLogin commits. A member that missed the login truncates itself: applying the login entries from the RAFT log reveals a stale-term tail above the synced watermark, which it drops before anything else. That ordering is load-bearing because the new session reuses slot numbers above rs_commit_lsn: a replica cannot accept a new-term write before applying InternalLogin (the term check rejects it), and applying InternalLogin is exactly where it truncates, so stale-session and new-session data can never coexist in a slot.

Reconfiguration (membership change)

Principle: lean on the underlying store for the mechanics; CRAFT owns only the data-plane gating the store cannot see. The store's membership machinery is consensus-log-based, so it is blind to CRAFT data (which never enters the log); CRAFT interposes exactly the data-plane gates below. The concrete binding to the store's member-replace / learner / snapshot / checkpoint primitives, and the small CRAFT-owned build list, are on CRAFT on HomeBlocks.

Constraint: single-member-at-a-time (add-one / remove-one; compose for bigger moves). This is the data-plane safety mechanism across a change: a quorum-acked write is held by ≥2 members of the old set and at most one member leaves, so at least one holder survives into the new set; the resync loop then restores it to full width (see the live-tail note below). No joint consensus.

Reduced-availability window is control-plane only. A replace flips the outgoing member OUT to a non-voting learner and adds the incoming member IN as a learner, so voting runs 2-of-2 for the catch-up duration (a voter failure in that window stalls the cold path, elections and logins, until recovery). The data plane is unaffected: the client keeps writing 2-of-3 to the still-synced set (the outgoing member is a learner but still holds and journals data, and the client refreshes its member set only at re-login on completion), and the data path is leaderless, so a running session keeps flowing even if a voter fails in the window. This is the data / consensus split doing its job.

Catch-up is pull-based (so the client never broadcasts to a catching-up member): the backlog (≤ startLSN) comes via the store's point-in-time snapshot / baseline-resync path; the tail + small gaps come via the existing SyncRSCommitLSN → FetchData loop above. If the tail grows too large for FetchData (the missing list runs past the journal retention window), fall back to a fresh snapshot, which advances startLSN.

Promotion (learner → voter) is gated by CRAFT's commit_lsn ≥ startLSN, not the consensus library's log-index monitor (blind to CRAFT data, since data isn't in the log). startLSN starts as the dLSN at the moment of the change and advances with each snapshot (re-)pin (see Frozen view); the member reports commit_lsn in its keep_alive response. This gate is the data-plane quorum-safety mechanism for the backlog: a member must hold data through startLSN before it can count as a poll-quorum participant.

The live tail across removal: healed by resync, not fenced. Promotion protects the backlog. For the live tail: a write acked by {A, OUT} just before OUT leaves still has A as its surviving holder in the new set, and the other members were already sent it (the client broadcasts to all; a member without it is either acking late or already faulted) or will pull it via the normal SyncRSCommitLSN → FetchData loop. Losing that write now requires A to fail before resync lands it on a second member, on top of whatever kept the broadcast copy from landing in the first place: a dual failure, outside the f = 1 contract. A login can only miss the write if A is down at poll time (the poll is a broadcast; every responder counts). The identical window exists if OUT dies instead of being removed, and no fence can be placed on a death, so CRAFT does not fence removal: the data plane stays unaffected by a planned change, and the brief single-holder exposure is the same degraded-then-heal window every unplanned failure already creates.

Frozen view: a point-in-time snapshot. The backlog payload is read from a point-in-time freeze of the committed index + blocks (the store's checkpoint), so writes that land after the freeze cannot mutate it and no verify-on-read is needed for what the snapshot ships. The snapshot's startLSN = the commit_lsn at the freeze, carried in its metadata so the tail FetchData loop resumes correctly. The freeze is bounded (time / size): a transfer that exceeds the bound re-pins a fresher freeze and restarts with the new startLSN. It is restartable: the follower checkpoints its receive cursor + startLSN, so a leader failure mid-transfer restarts cleanly. The concrete snapshot-callback binding (payload iterator, receive handler, resumable object stream) is on CRAFT on HomeBlocks.

Self-elected stand-in client (recovery while detached). A replace can run with no client attached, but CRAFT data-plane convergence normally rides client activity: the RAFT leader proposes SyncRSCommitLSN (a client cannot propose a RAFT entry), triggered by the client's keep_alive / commit traffic, its watchdog, or the periodic checkpoint. When detached there is no traffic to ride, so the leader self-elects as a stand-in client to drive just that. No app IO when detached means no live tail, so it is pure backlog catch-up. Leader-only, so no stand-in split-brain.

Logout / lease: hybrid. A locally-evaluated lease (the keep_alive watchdog) detects that the client is gone; a committed RAFT InternalLogout / lease-expiry entry grants the authority to act. The leader self-elects only after that entry commits (serialized, survives leader failover, avoids a new leader re-deciding blindly), and yields on the next committed InternalLogin. The committed logout also marks "no active client", which sharpens the login fencing boundary (a following login is unambiguously a fresh session).

Re-login on completion. When the change completes, a term bump forces an attached client to refresh its member set. Re-login is triggered by ETERM: the client re-logins to the leader presenting its client_token; the leader accepts only if that token is the current owner (returns a fresh term + members) and rejects a superseded token, so a deposed client cannot reclaim the volume. In-flight writes are re-driven under the new term.

Skinny mode: decoupled data and config durability

CRAFT has two independent durability axes, because the data plane and the consensus plane are separate systems (that separation is the whole design):

  • Data durability N (N >= 2): the number of data replicas. A write is durable when a majority of the N data members have journaled it. N is the data-plane replication factor: what survives disk / host loss.
  • Config durability M (M >= 3, typically odd): the number of consensus voters (the RAFT group). A majority of M elects a leader, commits the writer session, agrees a recovery watermark, and commits a membership change. M keeps the control plane available across voter loss.

Data members are always RAFT voters (a replica is tracked and reconfigured through the RAFT group, so it must be in it), which forces N <= M: N > M is not a configuration. The M - N voters that are not data members are arbiters. So there are two member kinds:

  • data + voter: a normal replica.
  • voter only (arbiter / witness): votes, stores no data (M - N of them).

When N == M there are no arbiters and every member both stores and votes: the symmetric configuration (classic three-way is N = M = 3). Skinny mode is N < M (the only way N and M can differ), where the voter set is a strict superset of the data set. Note N = 2 forces skinny: two data members alone give only M = 2 voters, which tolerates no voter loss, so a config-durable two-copy volume needs at least one arbiter to reach M >= 3.

Config N M Members Character
Symmetric (N=M) 3 3 3 data+voter Redundant through one data loss; majority-of-3 write keeps the quorum-ack latency win.
Skinny (N<M) 2 3 2 data+voter, 1 arbiter RAID1 replacement: two copies plus a witness, at two-copy cost. Majority-of-2 is both, so no quorum-ack slack.
Skinny (N<M) 2 5 2 data+voter, 3 arbiters Two copies, five-voter control plane (tolerates two voter losses). Config-resilient, data-lean.
Skinny (N<M) 3 5 3 data+voter, 2 arbiters Three copies plus a two-voter cushion; keeps the quorum-ack write and tolerates two voter losses.

Skinny mode replaces a two-way mirror (RAID1 / DRBD two-way) at two-copy data cost while folding in what those systems delegate to an external cluster manager: consensus-managed failover, single-writer fencing, and safe online member replace.

The load-bearing safety rule: the two quorums never mix. Durability is decided by the data quorum (a majority of the N data members) and is never derived from the consensus quorum. An arbiter's vote counts toward M, never toward a write's durability. This is what makes a witness safe here where it is the classic trap elsewhere: a write on too few data copies can never be reported durable, because CRAFT does not infer durability from a RAFT ack. Systems that conflate the two (a witness vote satisfying a "majority-durable" write) hit the well-known arbiter bug; CRAFT's data / consensus split rules it out by construction.

Roles that follow from the split (identical in every configuration):

  • Client I/O targets data members only. Writes, reads, and keep_alive go to data members; arbiters are never an I/O target. LoginResult hands the client the data set as its I/O targets; it may hit an arbiter at most for a leader redirect at login, then never again.
  • The leader is always a data-and-voter member, never an arbiter: it holds the recovery watermark (rs_commit_lsn = max over data members) and is the post-login sole reader while peers catch up. Arbiters are voters but election-ineligible. Failover works as long as one leader-eligible data member sits in a surviving voter majority.
  • Arbiters are excluded from all data-side accounting: not a FetchData source, not in the all_committed_lsn reclaim floor, not part of the "quorum known to lack" for Empty verdicts. An arbiter's listener treats data applies as no-ops.

The two planes degrade independently. Losing data members lowers the live N; losing voters lowers the live M; neither event touches the other quorum. So a volume can be data-degraded but config-healthy (lost a copy, voters fine, so it can add and resync a replacement) or config-stuck but data-intact (lost a voter majority, so the data is safe on its members but there is no leader until voters return). A symmetric N = M = 3 set that loses two members is both at once (one copy and one voter left, no majority) and fail-stops on its own; a skinny N=2, M=3 set that loses one data member is only data-degraded (a voter majority survives), which is precisely why skinny mode has to make the degraded-write policy explicit where the symmetric set gets fail-stop for free.

The degraded-write policy (when the live N cannot meet the data quorum). Because the write-ack threshold is a data-plane property and arbiters are never data copies, surviving voters do not make an under-replicated write more durable. Two policies, both consistency-safe, differ only in the promise:

  • Fail-stop (recommended default): do not ack a write that cannot reach its data quorum. The volume keeps serving reads but parks or errors writes until a rebuild restores a copy. Preserves acked implies the promised N-durability.
  • Degraded-accept (explicit opt-in, RAID1 parity): keep acking to the surviving copies, mark the volume degraded, rebuild urgently. Acked writes in this window carry only the reduced copy count (single-copy f = 0 at the extreme) until the rebuild restores N: exactly RAID1's degraded contract.

In both, the surviving voters keep the control plane alive so a replacement data member can be added and resynced online (normal snapshot plus FetchData, promoted at commit_lsn >= startLSN), which restores N. Availability, not durability, is the arbiter's contribution.

Rejected alternative: arbiters stay data-less. It is tempting to close the single-copy window by having a surviving data member also ship journal bytes to an arbiter (holding them without applying), so a degraded write lands on two members. It works, but it turns the witness into a part-time data member (durable journal, FetchData duty, watermark re-entry), most of a data member's machinery for a transient gain. The honest way to hold durability through a rebuild is a higher N (another data copy), not a shape-shifting witness. Raising N and raising M are the two clean knobs; blurring an arbiter into a data copy is neither.

Correctness deep-dives

1. The recovery watermark max(quorum.last_append) is forced

Login computes rs_commit_lsn = max over a polled quorum of last_append_lsn. It can look like over-committing (promoting an LSN only one node holds), but under block semantics it is the only correct choice; there is no decision to make.

Indistinguishability. N=3, quorum=2. An LSN k shows up on exactly one node of the polled quorum. Two scenarios are observationally identical from {S2,S3}:

  • Case A: k reached S1+S2 (true quorum, durable, client acked the app), then S1 went unavailable. Poll {S2,S3}: only S2 has k.
  • Case B: k reached only S2, never made quorum, client never got its ack. Poll {S2,S3}: only S2 has k.

To never drop the durable one (A) you must include k, which means you sometimes also include the non-durable one (B).

Cost asymmetry makes "include" the safe direction. false-exclude = drop an LSN the app was told was durable → silent committed-data loss (catastrophic). false-include = land an in-flight write whose absence was never promised to anyone → benign (the filesystem already handles crash consistency for in-flight writes; the new term fences the old client out).

The theorem to write into the design. If k was ever quorum-acked, ≥2 nodes hold it; any polled quorum of 2 intersects that set, so at least one polled node reports last_append ≥ k, hence max(quorum.last_append) ≥ k. The real constraint this names: write-quorum ∩ poll-quorum ≠ ∅, always, automatic on fixed membership. Across a membership change the guarantee is carried differently: at most one member leaves, so every quorum-acked write keeps at least one surviving holder, and resync restores full width; losing the tail then takes a dual failure. See the live-tail note in Reconfiguration.

2. Read eligibility: LBA-overlap, not a contiguous gate

Reads are unicast to one client-chosen replica, and readability is per-LBA, not per-contiguous-LSN. A replica may serve read([lba, lba+len), H) iff it is filled to L (the two-region split below) and it holds every write ≤ H overlapping the range; equivalently, no Missing slot ≤ H overlaps [lba, lba+len). A hole on an unrelated LBA is irrelevant. Gating reads on a contiguous Synced prefix would be wrong twice over: it linearizes independent in-flight I/O (holding a higher LSN's readability for an unrelated lower one) and it lets one slow or lost write stall all higher reads, which is poison for a block device.

The client enforces it. It knows the LBA range of every write it issued and keeps a per-replica, LBA-aware Missing map, so it only routes a read to a replica that can serve it. Hence the read path never fetches. Peer fetch is resync-only.

Mental model (from the RAID1 it replaces). This per-replica Missing map acts as a multi-dimensional dirty-bitmap. A RAID1 mirror keeps a one-dimensional dirty-region log so a stale mirror resyncs only the dirty regions instead of the whole disk; CRAFT keys the same idea by (replica, LBA range, dLSN). Reads route around exactly the stale ranges of each replica and resync fetches exactly those, so a partially-behind replica still serves every range it is clean on.

Crucially, unlike a RAID1 bitmap the dirty state is not opaque to the replicas. A RAID1 dirty-region log lives in the writer (the md host, the DRBD primary) or an array controller, so the copies are dumb and that one writer drives every resync. In CRAFT the same information is materialized in each replica's own slot state (Missing / Empty / the commit_lsn watermark), so replicas resync from each other via SyncRSCommitLSN + FetchData with no client in the loop. That moves resync traffic off the client and is why catch-up is server-side, not writer-driven (vs md RAID1, whose host drives resync from a writer-side bitmap; DRBD9 also resyncs peer-to-peer, so this is a delta over RAID1, not over DRBD). The one clean data-path delta that separates CRAFT from DRBD is quorum-ack; the stale-replica read this map enables is a finer-grained (per-dLSN, N-way) version of what md RAID1's recovery watermark already does, not a new capability. See the feature matrix in Background.

The one place a contiguous watermark is right: the login dLSN L. At/below L are prior-session writes whose LBAs the client cannot name, so it can't run the overlap check there: a member must be fully filled to L (Synced ≥ L) before it serves any read. Above L (this session's writes) LBA-overlap governs. So the true rule is a two-region split at L, and Synced ≥ L is the same "reach the watermark" gate as reconfig promotion (commit_lsn ≥ startLSN).

Consequence: login can't finish until ≥1 member is filled to L (the leader syncs itself whole), and that member is the sole reader until each peer reaches Synced ≥ L, a window kept short by there usually being few in-flight I/Os, and by the leader-stand-in having pre-driven resync while detached.

References

Consensus.

  1. Ongaro, D., and Ousterhout, J. In Search of an Understandable Consensus Algorithm (Raft). USENIX ATC, 2014. https://raft.github.io/raft.pdf
  2. Lamport, L. The Part-Time Parliament. ACM Transactions on Computer Systems 16(2), 1998. (Paxos.)

Replication protocols.

  1. Lin, W., Yang, M., Zhang, L., and Zhou, L. PacificA: Replication in Log-Based Distributed Storage Systems. Microsoft Research, MSR-TR-2008-25, 2008.
  2. Balakrishnan, M., Malkhi, D., Prabhakaran, V., Wobber, T., Wei, M., and Davis, J. D. CORFU: A Shared Log Design for Flash Clusters. USENIX NSDI, 2012.
  3. van Renesse, R., and Schneider, F. B. Chain Replication for Supporting High Throughput and Availability. USENIX OSDI, 2004.
  4. Terrace, J., and Freedman, M. J. Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads. USENIX ATC, 2009.
  5. Katsarakis, A., Gavrielatos, V., Katebzadeh, M. R. S., Joshi, A., Dragojevic, A., Grot, B., and Nagarajan, V. Hermes: A Fast, Fault-Tolerant and Linearizable Replication Protocol. ASPLOS, 2020. https://arxiv.org/abs/2001.09804
  6. Attiya, H., Bar-Noy, A., and Dolev, D. Sharing Memory Robustly in Message-Passing Systems (ABD). Journal of the ACM 42(1), 1995.

Storage systems.

  1. Brooker, M., Chen, T., and Ping, F. Millions of Tiny Databases. USENIX NSDI, 2020. (Amazon EBS chain replication and the Physalia configuration store.)
  2. Weil, S. A., Brandt, S. A., Miller, E. L., Long, D. D. E., and Maltzahn, C. Ceph: A Scalable, High-Performance Distributed File System. USENIX OSDI, 2006. (RBD / RADOS.)
  3. DeCandia, G., Hastorun, D., Jampani, M., et al. Dynamo: Amazon's Highly Available Key-value Store. ACM SOSP, 2007.
  4. LINBIT. The DRBD 9.0 User's Guide. https://linbit.com/drbd-user-guide/drbd-guide-9_0-en/
  5. The Linux Kernel. RAID arrays (md). https://docs.kernel.org/admin-guide/md.html
  6. Longhorn (CNCF). Cloud-Native Distributed Block Storage for Kubernetes. https://longhorn.io

The storage-substrate references (for the concrete implementation) are on CRAFT on HomeBlocks.

HomeBlocks

CRAFT

Clone this wiki locally