Random Routing, Idle Dynos

Medium

· Backend

Incident

SEV-2

BUG-ROUTER-1302

Priority: High · reported by platform customer (latency analysis)

Time to fix: 20 min

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

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. 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.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

Heroku · 2013

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.

Code map

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;
    }
}

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

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

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. 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.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. 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=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.

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.