Random Routing, Idle Dynos — Java Bug Hunt

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=2388ms

The 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.