A Lockless Rate Limiter on Redis

Nov 18, 2024

Every process in our fleet calls the same third party APIs, and every provider enforces a quota. Blow the quota and you get 429s, or worse, a temporary ban. So dozens of independent processes need to agree on a shared rate, with no coordinator and no shared memory.

I built this at Sprinto. The design is generic and small enough to explain in one page.

The obvious design, and why I skipped it

The obvious design is a distributed lock around a counter in Redis: acquire, read, decide, write, release. Locks over a network bring their own diseases. Lease timeouts, dead holders, retry storms, and a paragraph of edge cases per line of logic.

The observation that removes all of it: Redis already runs commands one at a time. If the entire decision (read the bucket, refill it, take a token or refuse) happens inside one Lua script, it is atomic by construction. No lock, because there is nothing to interleave.

-- one atomic decision, executed inside Redis
refill = elapsed_since_last_refill * (limit / interval)
tokens = min(tokens + refill, limit)
if tokens > 0 then
  tokens = tokens - 1
  return ALLOWED
else
  return DENIED, when_to_retry
end

The whole limiter is a token bucket stored as one small Redis hash, and one script that any process can call. The processes never coordinate with each other. They each talk to the same atomic decision.

The details that carry the weight

Refill on demand, not on a timer. Nothing refills buckets in the background. The refill happens inside the script, computed from the time since the last refill, right before a token is taken. Zero timers, zero background work, and an idle bucket costs nothing.

Tell the caller when to come back. A denied caller should not poll in a blind loop. The math that refused the token also knows when the next token arrives (interval divided by limit, plus any suspension). The script returns that, the caller sleeps exactly that long, plus a small random jitter so a crowd of waiters does not wake up in lockstep.

Limits change on the fly. Providers change their quotas, and some responses tell you the real limit only at run time. The bucket config lives in Redis next to the bucket, so one process can update the limit and every process obeys it on their next call, no deploy, no restart.

Suspension is first class. When a provider returns a 429 with a retry-after, the right move is to stop the whole fleet, not just the process that got the error. A suspend key with a TTL does exactly that: every caller sees the suspension and its remaining duration in the same atomic decision.

Two tiers when the provider has two limits. Some APIs enforce both per second and per minute limits. Compose two buckets, per second on the outside, per interval on the inside. A call passes both gates or waits at the first one that refuses.

Buckets clean up after themselves. Config carries an inactivity expiry, refreshed on every call. Stop calling an API and its bucket evaporates. No janitor process.

The lesson

The instinct that matters here is not about rate limiting. It is this: when many workers contend over something virtual, a lock is the last resort, not the first. Prefer making the whole decision atomic in one place, or collapsing duplicate work into one flight. I used the same instinct in the token refresh design, and it produced simpler systems both times.