Random Routing, Idle Dynos — Java Bug Hunt
Modelled on Heroku's routing layer, February 2013. Rap Genius published an analysis showing that Heroku's router was assigning requests to dynos at random…
- Language: Java
- Layer: Backend
- Difficulty: Medium
- Concepts: Networking, Concurrency, Limits
- Modelled on: Heroku · 2013
- Visible tests: a lone dyno takes the request; an idle dyno beats a busy one
- Reward: 50 XP for a complete fix
Incident
- Severity: SEV-2 (priority: High)
- Ticket: BUG-ROUTER-1302
- Reported by: platform customer (latency analysis)
- Time to fix: 20 minutes, the target for a medium incident
Failing checks on the shipped build
- an idle dyno beats a busy one — the idle dyno must get the request: expected web.2 but got web.1
How to work this incident
- Read the report: write down the expected behaviour and the actual one in a sentence each.
- Reproduce it: run the visible tests and find the failing check that matches the report.
- Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
- Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
- Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.
Briefing
Modelled on Heroku's routing layer, February 2013. Rap Genius published an analysis showing that Heroku's router was assigning requests to dynos at random rather than to dynos that were free. Single-threaded dynos (a typical Rails app of the time) queued requests behind slow ones while other dynos sat idle, and the queueing time did not show up where customers were looking. Heroku acknowledged the behaviour and that its documentation had not reflected it.
This project is a reconstruction: Router.route picks a dyno from the pool using a random number.
Fix route so each request goes to the least-loaded dyno, deterministically.
Bug report
BUG-ROUTER-1302 · Priority: High · Reported by: platform customer (latency analysis)
Router.route(dynos) must:
- return the dyno with the FEWEST in-flight requests (Dyno.inFlight)
- break ties by list order: the earliest dyno in the list wins
- increment the chosen dyno's inFlight by one
- throw IllegalStateException for an empty list
The router's random source must not influence the choice.
Observed: requests land on dynos already working through a queue while other dynos report zero in-flight requests.
Logs
[router] at=info path=/songs/42 dyno=web.1 queue=3 service=2104ms
[router] at=info dyno=web.2 queue=0 (idle 41s)
[router] at=info path=/artists dyno=web.1 queue=4 service=2388msThe code as shipped
src/router/Router.java (editable)
class Router {
private final SeqRng rng;
Router(SeqRng rng) {
this.rng = rng;
}
Dyno route(List<Dyno> dynos) {
if (dynos.isEmpty()) throw new IllegalStateException("no dynos");
Dyno pick = dynos.get(Math.floorMod(rng.next(), dynos.size()));
pick.inFlight++;
return pick;
}
}Read-only context: src/router/Dyno.java.
Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More Java bug hunts.