When Redis goes away

Most write-ups of distributed rate limiters say that concurrent requests break a naive token bucket. Very few show it happening. I'd built a token-bucket middleware for Express with its state in Redis, and before trusting my fix I wanted to watch the bug happen.

The experiment: a bucket with capacity 100 and a refill rate of zero, so exactly 100 requests may ever be admitted. Fire 1,000 checks at it and count how many get through. Ten trials per configuration, on a 4-core i5-7500 with Redis 8.4 on localhost.

The naive version

Read the count, decide in JavaScript, write the count back:

async function naiveCheck(client, key) {
  const [tokens] = await client.hmGet(key, ['tokens']);
  const t = tokens === null ? K : Number(tokens);
  if (t < 1) return false;
  await client.hSet(key, { tokens: String(t - 1) });
  return true;
}

The first row is the control: one request at a time, and the naive version is correct.

The second row surprised me. The usual explanation is that this race needs several servers sharing one bucket. It doesn't. A single Node process with just two requests in flight admitted exactly 200, in all ten trials. Both requests go out on the same Redis connection, so the commands arrive in the order read, read, write, write. Both reads see the same count, both writes store the same decremented value, and two requests spend one token. The limit gets multiplied by the concurrency, as reliably as clockwork. More processes just make it noisier.

You don't have to take my word for the order. Here is MONITOR while one process runs two naive checks at a time against a bucket holding 3 tokens:

[0 127.0.0.1:51358] "HMGET" "wire" "tokens"
[0 127.0.0.1:51358] "HMGET" "wire" "tokens"
[0 127.0.0.1:51358] "HSET" "wire" "tokens" "2"
[0 127.0.0.1:51358] "HSET" "wire" "tokens" "2"
[0 127.0.0.1:51358] "HMGET" "wire" "tokens"
[0 127.0.0.1:51358] "HMGET" "wire" "tokens"
[0 127.0.0.1:51358] "HSET" "wire" "tokens" "1"
[0 127.0.0.1:51358] "HSET" "wire" "tokens" "1"
...

One connection (port 51358), two reads, then two writes of the same value. Six requests got through on three tokens.

The last row is worse than over-admission. At 8 requests in flight per process, the bucket never emptied at all. With 32 reads landing on the same value, almost every write overwrites another, so the stored count barely moves while 1,000 requests walk through.

The fix

A lock in the application layer just moves the race into whatever implements the lock. Instead, the whole read-refill-decide-write cycle runs inside Redis as one Lua script, and Redis runs a script without letting anything else in between:

local t   = redis.call('TIME')
local now = (tonumber(t[1]) * 1000) + math.floor(tonumber(t[2]) / 1000)

local state       = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens      = tonumber(state[1])
local last_refill = tonumber(state[2])
if tokens == nil or last_refill == nil then
  tokens = capacity
  last_refill = now
end

-- A backwards clock must not mint or destroy tokens.
local elapsed = now - last_refill
if elapsed < 0 then elapsed = 0 end
tokens = math.min(capacity, tokens + (elapsed / 1000) * rate)

The clock comes from Redis's TIME, not from the calling server, because servers' clocks disagree, and a shared bucket refilled by skewed clocks refills at the wrong rate. It admitted exactly 100 in every trial of every configuration.

One detail took me a while. When a request is denied, nothing was consumed, so the script doesn't rewrite the state. But it still has to refresh the key's expiry. Otherwise a client that keeps hammering a full bucket would eventually let its own bucket expire, and get handed a fresh, full one.

The cost, from the repo's benchmark at one request at a time over loopback, is 0.16 to 0.18 ms added at the median across three runs. I'd been quoting 0.4 ms from an older measurement. Today's number is smaller, and it's the one I can reproduce.

Dead is easy. Hung is not.

A rate limiter that fails whenever Redis does would take the API down with it. So RedisStore gives every check a 250 ms budget. When Redis is unusable, it either lets the request through or rejects it, depending on a failOpen option (there's no answer that's right for every service). Allowed and denied requests are counted separately in degraded mode, so an outage doesn't look like a traffic spike on a dashboard. The client also disables node-redis's offline queue, because that queue is what once let a Redis blip hang every request indefinitely.

Then I measured each check while I broke Redis in two different ways: SIGKILL (the process is gone, connections are refused) and SIGSTOP (the process is frozen, but the kernel keeps its TCP connections open). 300 sequential checks per phase:

A dead Redis is the cheap case. The socket closes, the client marks itself not ready, and every check fails immediately, faster even than a healthy one. A hung Redis is the expensive one. The connection still looks alive, so the client keeps sending, and every single request waits the full 250 ms for an answer that never comes. That's more than 10,000 times the cost of a dead Redis, for as long as the hang lasts, with nothing in the middleware that notices it's been the same failure 300 times in a row.

What's missing is a circuit breaker: after a few consecutive timeouts, stop asking Redis for a cooldown period, and go straight to the degraded decision. I haven't built it yet. The open questions are how many timeouts should trip it and how you probe for recovery without making one unlucky request pay 250 ms each time.

Recovery works without help, at least: after SIGCONT the next check succeeded normally, and after a full restart the client reconnected and reloaded the script on its own.

A trap I fell into while measuring this

The first time I ran the outage test, one check during the hung phase took 30 minutes. The second time, 25. It wasn't Redis. The Mac's power log showed it had gone to sleep for 1,808 and 1,523 seconds, which matched the two stalls. Timers can't fire while the machine is asleep, so neither could the 250 ms timeout. This is the same trap I wrote about in five ways my benchmarks lied to me, and I still walked into it. The numbers above come from a run under caffeinate -dims, where the slowest of the 300 hung checks took 253 ms.

Both experiments are in the repo under experiments/. If you've tuned a circuit breaker in front of Redis, I'd like to know what thresholds you landed on: email me.

References

• Redis, Scripting with Lua: scripts run atomically, and nothing else executes while one is running.
• Redis, TIME and MONITOR.
• node-redis, whose disableOfflineQueue option is what makes a dead Redis fail fast.
• Martin Fowler, CircuitBreaker: the piece this limiter is still missing.
• The middleware, the race and outage experiments, and the benchmark: rate-limiter.