distributed consensus advanced
Advanced Distributed Consensus covers optimized implementations and variants of consensus protocols (Raft, Multi-Paxos, and beyond) that achieve high throughput and low latency for replicated state machines in production distributed systems — going beyond basic correctness to address real-world performance, batching, pipelining, and multi-group scalability.
Multi-Paxos Optimizations: Basic Paxos requires 2 round-trips per value (Prepare + Accept). Multi-Paxos elects a stable leader that skips the Prepare phase for subsequent proposals, achieving single round-trip (Accept only) in steady state. Further optimizations:
- Batching: Group multiple client requests into a single consensus round. A leader accumulates requests for a configurable window (e.g., 1ms or 100 requests) then proposes the batch as one log entry. Amortizes consensus overhead across many operations, increasing throughput 10-100x while adding small latency.
- Pipelining: Don't wait for one proposal to complete before starting the next. The leader issues proposals for log slots n, n+1, n+2... concurrently, with each Accept round in flight simultaneously. Increases throughput by overlapping consensus rounds with network latency.
- Parallel commit: For commutative operations, multiple log positions can commit independently without total ordering. Generalized Paxos and EPaxos exploit this for higher throughput on non-conflicting operations.
Raft Optimizations:
| Optimization | Mechanism | Benefit |
|---|---|---|
| Log batching | Bundle entries per AppendEntries | Higher throughput |
| Pipelining | Send next batch before ack | Hide network latency |
| Read leases | Leader serves reads without consensus | 10-100x read throughput |
| Pre-vote | Check electability before election | Avoid disruptive elections |
| Joint consensus | Two-phase membership change | Safe reconfiguration |
| Learner nodes | Non-voting replicas | Read scaling |
Read Optimizations: Linearizable reads typically require a consensus round (to confirm leadership is current). Alternatives: ReadIndex — leader confirms majority heartbeat, then serves read from current commit (one round trip, no log entry); Lease-based reads — leader holds a time-based lease during which it's guaranteed to be leader, serving reads locally with no communication (requires synchronized clocks within lease duration).
Multi-Group Consensus: A single Raft/Paxos group becomes a bottleneck at high throughput. Production systems shard data across many consensus groups (e.g., TiKV uses one Raft group per data region, CockroachDB per range). Challenges: colocated groups — a single server participates in thousands of Raft groups, requiring efficient multiplexing of heartbeats and log storage; cross-group transactions — operations spanning multiple groups require two-phase commit layered above consensus; and group management — splitting, merging, and rebalancing groups as data grows.
State Machine Replication Pitfalls: Log compaction — unbounded log growth requires periodic snapshotting; snapshot transfer to slow followers must not block normal operation. Membership changes — adding/removing nodes safely requires consensus protocol support to avoid split-brain. Disk I/O — consensus requires durable writes (fsync) on the critical path; batching fsync operations is essential for performance.
Advanced consensus protocols achieve the seemingly impossible — strong consistency with throughputs of millions of operations per second and sub-millisecond latency — through careful engineering of batching, pipelining, and read optimizations that reduce the cost of agreement to its theoretical minimum.