Eliminating the read-availability trade-off in LogDevice's consensus
LogDevice, Meta's distributed log storage system, has long relied on a variant of Flexible Paxos to order records durably across data centers. But that flexibility came with a cost: when acceptors failed, the system could lose the ability to elect a new leader and, consequently, the ability to serve reads. We removed that weakness by decoupling the leader-election quorum size from the write set, so failover no longer requires a read quorum of the full acceptor set.
What LogDevice is for
LogDevice was built as a transaction log and write-ahead log, where low latency and high write availability are critical. Over time its role expanded to secondary index updates, machine-learning training pipelines, monitoring stats, and general data analytics. The common thread across every use case is that lost write availability means lost data: for write-ahead logs, it triggers system unavailability; for data sinks, incoming data often exists only in memory and cannot be buffered elsewhere during an outage.
Read availability matters less. Most data is consumed as it is written — less than one percent of reads target data older than three hours — so a brief delay in delivery is tolerable, and uninterrupted access to older data is a lower priority.
Paxos and its trade-offs
Paxos lets multiple participants agree on a single value in an unreliable environment. The original formulation assigns three roles — proposers, acceptors, and learners — and runs in two phases. In phase one, a proposer seeks votes to become leader for a term; in phase two, that leader stores a value with acceptors. Each phase requires a majority of acceptors, which guarantees that the set of votes for any successful leader election intersects the set needed to reach agreement on a value, preventing conflicting outcomes.
Multi-Paxos is an optimization: if the same proposer is kept across multiple slots, phase one need not be repeated. The elected leader proceeds with phase two for slot after slot until a competing proposer interrupts.
Flexible Paxos relaxes the symmetry of the two phases' quorums. The phase-two write set need not be a majority of acceptors; it only needs to intersect every possible leader-election quorum. This decoupling is powerful — the acceptor set can be made arbitrarily large without increasing storage overhead — but it has a side effect. In vanilla Paxos, a majority quorum for phase two means any two successful value agreements intersect. In Flexible Paxos, that guarantee is lost unless the read quorum is expanded accordingly.
Separating read and write scaling
Without Flexible Paxos, growing the acceptor set forces more data copies: each pair of added acceptors requires at least one additional copy of every agreed value, capping useful capacity at less than double the largest acceptor's capacity. Flexible Paxos removes that constraint, making acceptor-set capacity effectively infinite. It also opens placement options — a large acceptor set can be spread across geographically distributed locations without storage penalties — which suits a streaming system that tracks where consumers are and moves data closer to them. Losing one or several regions still leaves enough acceptors to accept writes.
The cost, however, is on the read side. In Flexible Paxos the quorum needed for a safe read is not a majority but the potentially much larger set required to guarantee intersection with any successful write. That raises the computational cost of reads, which matters under leader failure when partially written values could exist.
LogDevice's existing safeguards
LogDevice deviates from vanilla Paxos in ways that mitigate the read-quorum problem for its workload. The recovery process that runs on each leader election can block reads of new writes until it completes, and it guarantees that once any acceptor returns a value, that value is the exclusively agreed one for the slot. During normal operation — when no leader has failed — that allow reads to proceed without a read quorum at all.
In practice, with a replication factor of three, losing a read quorum meant losing the ability to elect a new leader much more often than losing data availability. The teams' early decision to introduce a separate membership mechanism, backed by ZooKeeper, let them fully reconfigure acceptors regardless of the current set's availability. But that approach sacrifices linearizable writes: without a read quorum on the old set, there is no way to prove the previous leader has stopped writing. Read availability was still lost for newly written data.
The stuck-recovery problem at fleet scale
Across a large fleet, maintenance and organic failures routinely combined into a "stuck recovery" — the most common violation of read service-level agreements. Each episode required manual intervention: an operator would inspect the unavailable machines, judge that they had been down long enough to hold nothing relevant, and allow recovery to bypass the quorum.
The obvious question was whether the system could make that judgment itself.
Electing a leader with a write-set quorum
The key insight is that leader election only needs to rule out in-flight writes. Any active leader writes to a dynamic "write set" of acceptors, which it monitors and prunes as members fail. Since all in-flight operations happen only on that write set, a quorum there is sufficient to elect a new leader safely. The problem is propagating the write-set information to prospective leaders.
That propagation happens naturally through Flexible Paxos itself. Any successful phase-two write is visible to all future leaders, so a special reconfiguration record — recording that the write set changed — is picked up by the next leader during election. The same leader that adjusts the write set persists it, so it can guarantee that excluded acceptors are not used after the change, and that new acceptors are only used once a record containing them exists.
In practice, a leader that loses acceptors can shrink the leader-election quorum almost immediately. The only residual risk of being unable to elect a leader is the narrow window where both a quorum of acceptors is lost and the leader fails at almost the same time.
This approach draws on observations from DPaxos, which also recognized that only acceptors participating in in-flight operations matter. DPaxos handles this differently — the active leader continuously announces the acceptor set it will use next — but that strategy introduces its own complexities that the research paper explores in detail.
Outcomes after rollout
Prior to this change, stuck recovery events were a recurring problem. Since the rollout completed, we have not seen a single occurrence, and the improvement shows up directly in our read availability figures. The chart below contrasts the fraction of time we missed our aspirational availability target in the period before the change (left of the dotted line) against the period after it (right of the dotted line).
The fix also removed the need to rely on a membership change to trigger leader election. With recovery no longer blocking on that fallback, we have since added support for linearizable writes and are currently building an “exactly once” delivery mode.
