Atomic rate limiting across gateway instances with Redis Lua

SENTINEL is a distributed rate limiter and API gateway I built. The obvious way to implement its token bucket looks correct in unit tests and is wrong as soon as more than one gateway instance runs. This post walks through why, and how SENTINEL avoids it by moving the decision into a Redis Lua script.

The naive version

A token bucket needs two numbers per client: how many tokens are left, and when the bucket was last refilled. The obvious implementation reads them, does the math in Java, and writes them back:

Map<Object, Object> state = redis.opsForHash().entries(key);   // 1. read
long tokens = refill(state, now);                              // 2. compute
if (tokens >= 1) {
    redis.opsForHash().put(key, "tokens", String.valueOf(tokens - 1));  // 3. write
    return ALLOWED;
}
return REJECTED;

With one gateway instance and light traffic you'd rarely see a problem. But SENTINEL runs several gateway instances behind a load balancer, all sharing one Redis.

The race

Two requests from the same tenant land on two gateways at the same moment, with one token left:

Both requests are allowed, so the limit is exceeded. Under real concurrency the overshoot grows with the number of instances. That's a classic check-then-act race: the read and the write are separate operations, and anything can happen between them.

Making it atomic

Redis runs a Lua script as a single, uninterruptible operation: no other command runs on that Redis while the script executes. So the fix is to move the whole read → refill → decide → write sequence into one script:

local key = KEYS[1]
local max_tokens = tonumber(ARGV[1])
local window_seconds = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])

local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1] or max_tokens)
local last_refill = tonumber(data[2] or current_time)

local elapsed = current_time - last_refill
if elapsed > 0 then
  local refill_rate = max_tokens / window_seconds
  local new_tokens = math.floor(elapsed * refill_rate)
  if new_tokens > 0 then
    tokens = math.min(max_tokens, tokens + new_tokens)
    last_refill = last_refill + (new_tokens / refill_rate)
  end
end

if tokens >= 1 then
  tokens = tokens - 1
  redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
  redis.call('EXPIRE', key, window_seconds)
  return 1
end

redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
redis.call('EXPIRE', key, window_seconds)
return 0

Now it doesn't matter how many gateways call it at once: Redis serialises the scripts, so each request sees the result of the one before it. The Java side just executes the script and reads a 1 or 0:

Long result = redisTemplate.execute(
    tokenBucketScript,
    Collections.singletonList("token_bucket:" + key),
    String.valueOf(maxRequests),
    String.valueOf(windowSeconds),
    String.valueOf(currentTime)
);

A subtle bug: slow rates starving

Look at this line again:

last_refill = last_refill + (new_tokens / refill_rate)

The tempting shortcut is last_refill = current_time whenever a refill happens. That throws away the fraction of a token earned since the last whole token. For high limits you'd never notice, but take a FREE-tier tenant at 10 requests per minute (one token every 6 seconds) whose client calls every 5 seconds. At 5 s no whole token has accrued; at 10 s one has, and the shortcut resets the clock to 10 s, discarding 4 seconds of progress. The client ends up earning a token every 10 seconds instead of every 6, quietly enforcing a stricter limit than configured. Advancing last_refill only by the time actually converted into whole tokens keeps the leftover progress, so slow rates refill correctly.

Failing open

What if Redis is down? A rate limiter that rejects every request when its store is unavailable turns a Redis outage into a full API outage. SENTINEL fails open: if the script returns nothing, the request is allowed and the outage shows up in metrics instead of in customers' error rates. For a rate limiter whose job is protecting downstream services, that's the right trade-off. A payment-fraud check might choose the opposite.

Takeaways

• Any read-modify-write on shared state across instances needs atomicity. In Redis, a Lua script is the simplest way to get it (a MULTI/EXEC transaction can't branch on the values it reads).
• Keep the script small and deterministic: it blocks Redis while it runs.
• Be deliberate about failure modes: decide up front whether your limiter fails open or closed.

The same pattern powers SENTINEL's other three algorithms (sliding window log, fixed window counter and sliding window counter). You can see the project write-up here.