DEVOURED
Finding bugs in Raft implementations
Researchers at Antithesis found critical safety and liveness bugs in widely used Raft consensus implementations like HashiCorp Raft using deterministic simulation testing.
What: By running Raft nodes in a simulation environment with random fault injection, the team identified race conditions in heartbeat handling and deadlocks in leadership transfer that violate state machine safety.
Why it matters: This illustrates that formal verification of an algorithm design does not guarantee the safety of its production implementation, as developers often make flawed assumptions when translating specs to code.
Takeaway: If you are running distributed systems, consider using simulation testing platforms like Antithesis to verify your consensus implementations under simulated network failure rather than relying solely on unit tests.
Deep dive
- Methodology: Used Antithesis to run 3-node Raft clusters under network partition and fault stress.
- HashiCorp Raft Bug 1: Race condition where async heartbeats update state (currentTerm) on the network thread, conflicting with the main thread logic.
- HashiCorp Raft Bug 2: Deadlock during leadership transfer where a global flag is set and never cleared, preventing further commits.
- HashiCorp Raft Bug 3: Livelock where failing to discard stale log entries after an InstallSnapshot causes the node to reject subsequent AppendEntries indefinitely.
- Formal Proof Limits: Highlights that formal models (TLA+) often omit implementation details like snapshotting and network RPC mapping, leading to divergence.
- Testing Insight: Basic "Chain of Blocks" testing workflows can uncover critical safety violations when combined with aggressive, fault-injected simulation.
Decoder
- Raft: A consensus algorithm designed to be understandable while providing total order delivery for replicated state machines.
- Total Order Delivery: A property where all nodes in a distributed system receive and execute messages in the exact same sequence.
- State Machine Safety: The guarantee that if any server has applied a particular log entry to its state machine, no other server will ever apply a different command for the same log index.
- Liveness Violation: A condition where a system stops making progress, even if it does not technically crash or corrupt data.
- TLA+: A formal specification language used to model, design, and verify concurrent and distributed systems.
Original article
Full article content is not available for inline reading.
Explore all 42 articles in today's digest
Fresh dev news, AI-digested daily. Never miss a trend at devoured.fyi