Closing the TOCTOU Gap in Redis Rate Limiting

Rate limiters look simple but contain a subtle concurrency trap. Here's how we found and fixed it in XCloak.

The Original Implementation

A sliding window rate limiter in Redis works by maintaining a sorted set of request timestamps:

1. Remove timestamps older than the window
2. Count how many remain
3. If count < limit: add the new timestamp and allow the request
4. If count ≥ limit: reject

Implemented naively in Go:

pipe := rdb.Pipeline()
pipe.ZRemRangeByScore(ctx, key, "-inf", windowStart)
pipe.ZCard(ctx, key)
cmds, _ := pipe.Exec(ctx)

count := cmds[1].(*redis.IntCmd).Val()
if count >= limit {
    return false // rejected
}

rdb.ZAdd(ctx, key, &redis.Z{Score: now, Member: now})
return true

The bug: ZRemRangeByScore + ZCard execute atomically in the pipeline, but ZAdd is a separate command. Between the pipeline and the ZAdd, another goroutine (or another backend replica) can run the same pipeline, see the same count, pass the limit check, and also call ZAdd.

Two concurrent requests both see count = 9 (limit = 10), both pass, both call ZAdd. The window now has 11 entries, and two requests slipped through a limit of 10.

Under load — a credential stuffing attack, for example — this can allow significantly more requests than intended.

The Fix: Atomic Lua Script

Redis's EVAL command executes a Lua script atomically — no other command can interleave:

local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])  -- milliseconds
local limit  = tonumber(ARGV[3])

-- Expire old entries
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)

-- Count current window
local count = redis.call('ZCARD', key)

-- Reject if at limit
if count >= limit then
  return 0
end

-- Admit and record (unique member to handle same-millisecond requests)
redis.call('ZADD', key, now, now .. '-' .. redis.call('INCR', key .. ':seq'))
redis.call('EXPIRE', key, math.ceil(window / 1000) + 1)
return 1

All three operations — expire, count, add — happen in a single atomic step. Two concurrent goroutines cannot both see count = 9 and both add an entry. The second one will see count = 10 after the first has added its entry.

script := redis.NewScript(luaScript)
result, err := script.Run(ctx, rdb, []string{key}, nowMs, windowMs, limit).Int()
return result == 1, err

The fix is about 15 lines of Lua. The impact is significant: under a credential stuffing attack at 100 concurrent requests per second, the old implementation allowed roughly 2–3× the intended request rate. The new implementation holds the limit exactly.