One backoff ladder became four, and the first retry went from ten minutes to sixty seconds

Notifio is a desktop app that polls rental search pages from your own machine and tells you the moment a new listing appears. Polling somebody else's site on a schedule means occasionally being told to go away, and I have written before about the general problem of doing that without getting banned.

This post is about the specific thing I got wrong in that design, twice, in the same file.

The original policy was one exponential ladder starting at ten minutes and topping out at an hour, applied to any wall a site put up, keyed by the search URL that hit it. Every one of those three decisions was wrong, and the file that replaced it is 123 lines with no dependencies:

challenge     1.0m → 3.0m → 8.0m → 15.0m → 30.0m
rate_limited  2.0m → 5.0m → 15.0m → 30.0m
denied        5.0m → 15.0m → 30.0m → 60.0m
error         30s → 2.0m → 5.0m

Mistake one: the state belongs to the site, not to the request

This is the bug I would most want somebody else to avoid, because it hid for a long time behind symptoms that looked like two unrelated problems.

Backoff was keyed by search URL. A user monitoring five different searches on one rental site therefore had five independent failure counters against one host. The site refuses us, search one starts waiting, and searches two through five carry on knocking, because as far as they are concerned nothing has happened. Each of them then gets refused in turn and starts its own ladder, at its own offset.

The result was two complaints that I chased separately for a while:

• We stayed blocked. There was always some search that had not yet learned the site was refusing us, so the host kept receiving traffic through the entire backoff period.
• Recovery was slow. The five ladders were offset from each other, so the host was never quiet and the counters kept climbing instead of resetting.

One line of the module header now says what the key is and why:

/**
 * Keyed by host, not by search URL. A refusal comes from the site, so it
 * applies to every search on it. Keying by URL meant five searches on one site
 * each kept their own counter, and each went back to knocking while the others
 * were standing down: both why we stayed blocked and why recovery was slow.
 */

The general rule, which is easy to state and easy to get wrong in a client with any concurrency: back-pressure state is keyed by whatever refused you. Not by the request, not by the job, not by the user's configuration object. The host said no, so the host is the key. If five of your workers can independently rediscover the same refusal, you have not implemented backoff, you have implemented five slower clients.

Mistake two: one number answering four questions

The other thing the old ladder did was treat every refusal identically, which is how it ended up starting at ten minutes. When any interstitial counts as a hard block, you have to be pessimistic, because you cannot tell a Cloudflare splash screen from a permanent ban.

The fix was upstream: classify the wall first.

/**
 * What kind of wall a site put up. They deserve very different waits: an
 * interstitial clears itself in seconds, a rate limit is temporary and often
 * comes with a Retry-After, and a flat refusal needs the user to go and pass
 * the check by hand.
 */
export type BlockKind = 'challenge' | 'rate_limited' | 'denied';

Once the caller can say which of those it saw, one ladder becomes four, and each one can be argued about on its own terms:

/**
 * The wait after each consecutive failure, in ms. The last entry is the ceiling.
 *
 *  - challenge    : an interstitial we could not get through. Usually transient,
 *                   and by the time it is recorded the scraper has already
 *                   tried to read past it and to wait it out, so the first
 *                   retry can come quickly.
 *  - rate_limited : the site asked us to slow down. Its own Retry-After wins
 *                   whenever it asks for longer.
 *  - denied       : a flat refusal. It needs the user to go and pass a check by
 *                   hand, so retrying hard achieves nothing.
 *  - error        : network or browser trouble, most likely at our end.
 *
 * These are far shorter than the flat ten-minutes-to-an-hour ladder they
 * replace. That one was written when any challenge counted as a block, so it
 * had to be pessimistic about how often it would fire. Ten minutes of not
 * looking at a rental site is ten minutes of rooms going to somebody else.
 */
export const LADDERS: Record<BackoffKind, number[]> = {
  challenge:    [60_000, 180_000, 480_000, 900_000, 1_800_000],
  rate_limited: [120_000, 300_000, 900_000, 1_800_000],
  denied:       [300_000, 900_000, 1_800_000, 3_600_000],
  error:        [30_000, 120_000, 300_000],
};

That last sentence of the comment is the whole product argument, and it is why the tuning is not symmetric. For most software, a backoff that is too long is invisible and a backoff that is too short gets you banned, so the safe direction is obvious. Here, being late is the failure the user is paying to avoid. A room posted at 14:02 on a site like Kamernet is gone by 14:20, so a ten-minute stand-down after a splash screen that cleared itself in four seconds is not caution, it is the product not working.

denied still gets the long ladder, because a flat refusal needs the user to open the site and pass a check by hand. Retrying aggressively cannot fix that, so waiting costs nothing.

Three policies in one expression

export function delayFor(
  kind: BackoffKind,
  failures: number,
  retryAfterMs?: number,
  random: () => number = Math.random
): number {
  const ladder = LADDERS[kind];
  const step = ladder[Math.min(Math.max(failures, 1) - 1, ladder.length - 1)];
  const jittered = Math.round(step * (0.85 + random() * 0.3));
  return Math.min(Math.max(jittered, retryAfterMs ?? 0), MAX_WAIT_MS);
}

The return line is the part worth reading twice. Math.max(jittered, retryAfterMs ?? 0) means a site's Retry-After is a floor and never a ceiling: it can make us wait longer than we planned, never shorter. A site asking us to come back in five seconds does not get to shorten a wait we imposed for our own reasons. Math.min(..., MAX_WAIT_MS) caps the whole thing at an hour, because Retry-After is a number from somebody else's server and a header saying 86400 should not put a search to sleep for a day.

The jitter is the other half of mistake one:

/**
 * Jitter matters because several searches usually share a cycle: without it,
 * every host blocked in the same cycle comes back in the same instant, which
 * is the burst that got them blocked in the first place.
 */

Fixing the key without adding jitter would have converted five staggered clients into one synchronised thundering herd, which is worse in a different way. The two changes are the same fix.

A network blip is not a refusal

The registry counts consecutive failures, and a change of kind resets the count:

/**
 * Record a failure and return the new wait.
 *
 * A different kind of failure starts its own ladder rather than inheriting a
 * count from an unrelated one: a network blip should not be punished with the
 * wait earned by three refusals.
 */
record(host: string, kind: BackoffKind, retryAfterMs?: number, now = Date.now()): BackoffEntry {
  const previous = this.entries.get(host);
  const failures = previous && previous.kind === kind ? previous.failures + 1 : 1;
  ...
}

Whether that is right depends on your failure modes. If the kinds are correlated in your system, resetting on a change of kind is exploitable and you would want one shared count. Here they genuinely are not: a dropped wifi connection has nothing to do with the site's opinion of us, and inheriting a denied ladder's count for it meant a five-minute pause over a two-second hiccup.

The monitor adds one more guard on top of the error ladder, and it lives in the monitor rather than in the policy file for a reason:

/**
 * Consecutive hard errors on a host before it is made to wait.
 *
 * One failed scrape is usually a blip (a renderer crash, a dropped wifi
 * connection) and the next cycle recovers, so backing off immediately would
 * turn a two-second hiccup into minutes of not looking.
 */
const ERROR_GRACE = 2;

The split of responsibility is stated at the top of the monitor's backoff section, and it is the thing that keeps the policy file readable:

// The ladders and the per-host ledger live in backoff.ts. What stays here is
// only the decision about *when* to record a failure, which is the part that
// needs to know what the monitor just saw.

How long to wait is policy, and it is pure. Whether this thing that just happened counts as a failure needs the scrape result, the site's config, and the last few cycles. Keeping those in separate files is what makes the first one testable.

Coming back in, and being able to read the policy

When a host's wait is up, exactly one of its searches goes back in as a probe, and the others keep waiting until it reports. That half is its own post: when a block clears, only one search goes back in.

The module takes its clock and its randomness as arguments, which means the ladders can be run rather than reasoned about. The app has no test framework, so this is a file you execute with tsx, and the first thing it prints is the policy itself:

Backoff ladders (no jitter)

   challenge     1.0m → 3.0m → 8.0m → 15.0m → 30.0m
   rate_limited  2.0m → 5.0m → 15.0m → 30.0m
   denied        5.0m → 15.0m → 30.0m → 60.0m
   error         30s → 2.0m → 5.0m

Checks
   ok    first challenge retry is one minute  1.0m
   ok    challenge ladder tops out at 30 minutes  30.0m
   ok    a transient error waits half a minute
   ok    a flat refusal waits longer than a challenge
   ok    every wait grows with consecutive failures
   ok    jitter spreads retries out  40 distinct values of 40
   ok    jitter stays within 15% of the step  2.6m to 3.4m
   ok    a site's Retry-After wins when it is longer
   ok    a shorter Retry-After does not shorten our own wait
   ok    an absurd Retry-After is capped at an hour

Registry
   ok    a recorded host is waiting
   ok    an unrelated host is not
   ok    consecutive failures of one kind accumulate
   ok    a different kind of failure starts its own count
   ok    and uses its own ladder
   ok    soonest() finds the host that comes due first

Printing the ladder table above the assertions was an afterthought that turned out to be the most useful line in the file. Backoff is the sort of policy that gets described in a comment as "exponential with jitter" and then never looked at again, and nobody reviewing a diff can tell you what the third consecutive rate limit costs. Now the answer is a command, and when I change a number the table changes in front of me.

The two assertions I would copy into any backoff suite are the two about Retry-After: that a longer one wins, and that a shorter one is ignored. Those encode a decision about who is in charge, and that decision is invisible in a Math.min/Math.max chain until somebody "simplifies" it.

What I would take from this

The original ladder was not too aggressive or too conservative. It was one number answering four different questions, keyed to the wrong thing, and no amount of tuning the number was going to fix either of those. Both times I thought I had a tuning problem I actually had a modelling problem: the code could not distinguish a splash screen from a ban, and it could not distinguish a host from a search.

If you are tempted to adjust a backoff constant, it is worth asking first whether the thing you are adjusting is one policy or several wearing the same hat. If you want to see what the fast version buys, the app is at notifio.app/download and how it behaves when a site pushes back is written up in notifio.app/help.