Fewer False Deaths, Shorter Tails: Failure Detection and Request Routing for a Dynamo-Style Key-Value Store
Dynamo-style key-value stores trade consistency for availability, but two parts of their design remain fragile. Failure detection relies on fixed timeouts, so packet loss or a slow node makes healthy nodes look dead, while longer timeouts delay the detection of real failures. Request handling sends every read to all replicas and spreads keys, not traffic, so one slow replica inflates tail latency and one popular key overloads its replicas. We build a complete Dynamo-style store with SWIM membership in a deterministic simulator and replace these two parts. Suspicion lasts longer when it is unconfirmed and shortens as independent nodes confirm it; reads go to the replicas that have answered fastest lately, are hedged when slow, avoid overloaded nodes, and spread hot keys over temporary extra replicas. Against a classic baseline on identical seeds and faults, false death verdicts at 20% packet loss fall from 77.7 to 0.3 per run, the 99th-percentile latency with one slow node falls from 1338 ms to 210 ms, and a key receiving half of all traffic leaves the busiest node at 1.16x the average load instead of 2.25x. The costs are about 0.5 s slower failure detection on a clean network, 2 s under high latency, and 5-8 ms per request when nothing is wrong.
Authors
- Martim Baltazar (ORCID: https://orcid.org/0009-0001-9327-9420)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24243378
- Primary Topic
- Distributed systems and fault tolerance
- Type
- preprint