Rate Limits Look Different From the Other Side 🚦

On Tuesday, Gabor Koos published Rate Limiting Without the Refill Loop: Token Bucket vs GCRA. We read it in a week spent on the receiving end of other people's limiters. What a limiter stores is a fair debate, but the caller never sees your storage. The caller sees your rejection.

Two ways to store the same allowance

Both algorithms enforce a sustained rate and a bounded burst; the article's example is 100 calls per second with a burst of 20.

A token bucket stores a balance and its last update time. Each arrival adds the credit earned since then, capped at the burst, and admits the call if a whole token is available.

GCRA, the Generic Cell Rate Algorithm, stores one timestamp: the theoretical arrival time (TAT), the next call's slot on an evenly spaced schedule. At this rate the emission interval is 10 ms. Calls may run ahead of the schedule by a tolerance of burst - 1 intervals, 190 ms here. A call arriving before TAT - tolerance is rejected; an admitted one moves TAT one interval past the later of the old TAT and now.

The article shows these are one limiter in two units: the balance is the burst minus the distance from now to TAT in intervals, and substituting that into the bucket's one-token test gives GCRA's admission rule. With continuous refill, matching settings and starting state, unit-cost calls and no refunds or reservations, they admit identical traffic.

What differs is bookkeeping. The bucket keeps two values that must change together, plus a refill policy with precision traps. GCRA is compare-and-advance on one value, and a rejection's retry hint is one subtraction from it, TAT - tolerance - now; five milliseconds after a full burst, that is 5 ms. The bucket gets the same number by dividing its missing fraction of a token by the rate. Either way it is the earliest retry under current state, not a reservation.

The author concludes that neither is more correct; the choice is about which state a team can explain and operate. We agree. From the other side, a different question matters.

What the other side looked like this week

This week we submitted URLs to search engines, queried their webmaster tools and fetched pages, and collected four kinds of "no".

Google Search Console lets you request indexing for about 11 URLs per day per property. The 12th request answers "Quota exceeded … try again tomorrow", without saying whose tomorrow: requests we made the next morning in our time zone, UTC+8, were still refused. Once, with quota still left, a request answered only "Something went wrong, please try again later"; the same URL was accepted when retried later. A quota rejection and a transient error looked different only by luck of wording.

Bing Webmaster Tools: when several of our scripts queried it in parallel, every page of the tool started answering with a JSON "too many requests" message. We stopped for a while. It never said how long.

IndexNow returns 403 for the first submission with a freshly created key, until the search engine has fetched the key file from our site. A wrong key also returns 403. The status cannot tell "wait a minute" from "misconfigured", so our submit script keeps the response body. For a new key, retrying a minute later works.

Reddit refused our fetches with 429, then with 403 from another endpoint.

Each case made us guess, and guessing is how clients end up hammering, giving up too early, or filing a ticket.

What makes a rejection legible

From the caller's chair, a good refusal has four properties:

• A distinct status. 429 for "too many", not a 403 that also means "never", and not a generic error.
• A machine-readable reason. Which limit tripped, per key, per IP or per day, in a body a script can parse.
• When to retry. A Retry-After in seconds, or an absolute time with a time zone. "Tomorrow" is not a time.
• Discoverable limits. Documented numbers, or a remaining budget, so a client can pace itself.

Our own limiter throws the answer away

We are not in a position to lecture. One of our login flows sends SMS and voice one-time codes, with per-phone, per-IP and global daily caps plus a minimum resend interval. When a tester tripped the per-phone cap, the app said "failed to send": the client had swallowed the server's 429 into the same message as a delivery failure. Nothing on screen said that waiting was the fix.

Our website's shared limiter guards the endpoints where every call costs money (SMS, AI chat, speech synthesis) and our server readiness probes. It is a fixed window in SQLite on Cloudflare D1, with one atomic upsert per key, so check and update happen together, as the article requires of either algorithm:

INSERT INTO rate_limits (key, count, reset_at)
VALUES (?1, 1, ?2)                         -- ?2 = now + window
ON CONFLICT (key) DO UPDATE SET
  count    = CASE WHEN rate_limits.reset_at <= ?3   -- ?3 = now
                  THEN 1 ELSE rate_limits.count + 1 END,
  reset_at = CASE WHEN rate_limits.reset_at <= ?3
                  THEN excluded.reset_at ELSE rate_limits.reset_at END
RETURNING count;

The returned count includes the current request, so the check is count > limit. Blocked requests still increment the count but never extend reset_at, so a client that keeps retrying is not banned indefinitely. In production it fails closed when the database is unavailable, because a broken limiter on a paid endpoint costs more than a false rejection.

The flaw is the return type: a boolean. The reset time is in the row we just wrote, and we discard it, so our 429s cannot carry an accurate Retry-After. The fix is small:

// the upsert now ends with: RETURNING count, reset_at
let retryAfter = 0;
for (const rule of rules) {
  const { count, reset_at } = await upsert(rule, now);
  // several keys may trip; the caller has to wait for the last one
  if (count > rule.limit) retryAfter = Math.max(retryAfter, reset_at - now);
}
return { limited: retryAfter > 0, retryAfter };
 
// in the endpoint
const { limited, retryAfter } = await checkLimits(rules);
if (limited) {
  return Response.json(
    { error: "rate_limited", retryAfter },
    { status: 429, headers: { "Retry-After": String(retryAfter) } },
  );
}

A fixed window is cruder than either algorithm in the article, and GCRA would make this no harder: store TAT instead of a count and reset time, and the hint is TAT - tolerance - now.

A checklist for both sides

For servers:

• Use 429 for rate limits; keep 403 for problems waiting will not fix.
• Name the limit that tripped, in a body a script can read.
• Have the limiter return its reset or next-eligible time, not a boolean, and send it as Retry-After.
• If you must say "tomorrow", name the time zone. Seconds are better.

For clients:

• Budget before you send: with 11 requests a day, the 12th is a scheduler bug. Serialize work against a shared quota.
• On 429, wait at least the server's hint, then check again. Without a hint, back off exponentially with jitter, and stop at a deadline.
• Keep the response body; when two causes share a status, it is what tells them apart.
• Never swallow a 429 into a generic error. Show "try again in N minutes"; it is the one failure a user can fix by waiting.

The algorithm decides who gets through. The rejection decides what everyone else does next.