AI
Why etcd Correctness Is Hard to Maintain
etcd is the source of truth for Kubernetes and every critical infrastructure object stored in the cluster. During the 3.5 release roughly four years ago, maintainer rotation left gaps in tribal knowledge. New maintainers lacked the experience to catch multi-layered bugs, and several correctness issues slipped through. The team built a Jepsen-inspired robustness framework using model-based validation, which reproduced all 3.5 inconsistencies and traced some bugs back to the 3.0 release. But that framework brought its own costs: verifying correctness against a model is NP-hard, failure injection required PhD-student collaborations, and only senior maintainers could distinguish real bugs from flakes.
How Antithesis Explores State Space
Antithesis runs software inside a deterministic virtual machine. The same inputs always produce the same state, which makes every bug reproducible. Its autonomous search decides which faults to inject, which scripts to run, and which code areas to focus on. The Mario analogy makes this concrete: Antithesis was given the directional inputs and Mario’s XY coordinates, then explored hundreds of paths through level one on its own. The same approach applies to etcd. A 12-hour test generates hundreds of thousands of timelines, each branching from interesting states rather than restarting from scratch.
Splitting Timelines to Multiply Futures
When Antithesis reaches an interesting state, it splits the current timeline into multiple futures instead of continuing down a single path. Four timelines that share a common starting state, call it state A, can each diverge into different futures from that exact point. No new timeline needs to replay everything from the beginning. Antithesis reuses previously reached states as branch points and concentrates exploration energy there. This matters most for rare bugs: when a rare situation appears, Antithesis immediately fans out to explore many different outcomes of that situation.
Finding and Amplifying a Four-Year-Old Bug
The integration found a stale read bug traceable to the etcd 3.5 release. A follower node reported an older version of state even though it had observed the relevant commit, breaking etcd’s strong consistency guarantee. Initially the bug appeared once every 450 hours of real-world time, roughly once every 19 days. Post-test analysis pinpointed which events correlated with the failure: a container hang drove probability to 60%, and a subsequent network delay pushed it to 100%. Tuning those two fault rates made the bug appear 20 times more often, so it became reproducible every day.
Root Cause: Read Index Retries and Queue Reordering
etcd uses a read index protocol so followers can serve linearizable reads without sending every request through Raft. The 3.5 release added read index retries: if a read timed out after half a second due to a leader change or network issue, the follower could retry. Under a combination of a thread pause on the leader and a delayed heartbeat response, a retry reused the same read index ID. That reuse reordered the leader’s read queue, letting an old heartbeat falsely confirm a newer read. The follower then returned stale data to the client. The fix was changing the retry to always generate a new ID.
Q&A
How does Antithesis decide which new inputs to generate? It uses an instrumented fuzzer that splits timelines whenever it encounters a new code edge, a new server message, or an SDK hint from the application. ▶ 26:06
How do you prevent the state space from exploding? The etcd team runs a traffic script and a separate model-based validation script, scoping traffic to historically problematic request patterns and avoiding dimensions like database size that do not affect correctness. ▶ 27:56
Notable Quotes
so uh during a 3.5 release around 3 four years ago we uh the maintainer rotation uh led to a lot of knowledge un uh not being written led to it a lot of testing being missed Marek Siarkowicz · ▶ 02:03
so we saw it once every 450 hours of real world time. Uh which is roughly once every 19 days. Marcus Hodgson · ▶ 14:18
we just tuned the setting there and just by doing that we found the bug roughly 20 times more often than we originally did. Marcus Hodgson · ▶ 16:46
the fix was just changing the retry to change ID to never duplicate. Marek Siarkowicz · ▶ 23:31
Key Takeaways
- A four-year-old etcd correctness bug stayed hidden because reproducing it required simultaneous thread pause and network delay.
- Antithesis cut the time to reliable reproduction by 20x through targeted fault-rate tuning, not code changes.
- Antithesis is now free for any CNCF project to use; the etcd team moved testing in under a year.
About the Speaker(s)
Marek Siarkowicz is a Senior Software Engineer at Google, working on etcd, API machinery, and Kubernetes scalability. He began his career at Warsaw startups, where he developed a passion for open source and extreme programming.
Marcus Hodgson is an engineer at Antithesis. He graduated from Yale University in 2024 with a BS in Mathematics, where he was a varsity swimmer. His focus at Antithesis is helping engineering teams build higher-quality software through deterministic simulation testing.