Step 1 · The pattern
Three replicas, any can answer
The same data lives on three replicas. The app sends each read to one of them and gets an answer in a few milliseconds.
- read
- fast answer
In short
Hedged requests: how it works and how it breaks
Even a healthy server is slow now and then: a background job runs, a queue backs up, a disk stalls. Most requests take milliseconds and a few take seconds, and at scale those few are what users notice. If the data lives on several replicas, the slowness is usually tied to one machine at one moment, so another replica would have answered quickly. The blunt version of that idea sends every request to two replicas and keeps the first answer. It works, and it doubles the load, which can push busy replicas into the very slowness you were avoiding. A hedged request is the careful version. Send one copy. Only if it has been outstanding longer than nearly all requests normally take, send a second copy elsewhere, use whichever answers first, and cancel the other. The extra load is a few percent, and the slow tail mostly disappears.
How this comes up in interviews
"Most reads from your replicated store are fast, but a small fraction take seconds. How would you cut that slow tail?"
Then they ask
- Why not send every read to two replicas and keep the first answer?
- How do you choose when to send the second copy, and how much extra load does that add?
- In which situation does hedging make things worse instead of better?
A strong answer covers
- Occasional slowness is usually tied to one machine at one moment, so another replica would answer quickly.
- Sending everything twice works but doubles the load, which can cause the slowness you were avoiding.
- Hedge: send one copy, and send a second elsewhere only if the first is outstanding longer than nearly all requests take.
- Use whichever answers first and cancel the other. The extra load is a few percent.
- It only helps when the cause is local to one replica. If all are slow, the second copy is more load.
Points to cover, not a script. Say them in your own words and tie them to a system you have worked on.
On one page: the track cheat sheet.
Sources: The Tail at Scale (Dean & Barroso, Google, CACM 2013) ↗ · The Tail at Scale: full article in Communications of the ACM ↗ · Report a problem
Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.