One round trip: atomic rate limiting with Redis Lua

Here is the whole bug a distributed rate limiter exists to prevent. A tenant is allowed 100 requests a minute and has used 99. Two requests arrive at the same moment on two different instances.

1. Instance A reads the counter: 99.
2. Instance B reads the counter: 99.
3. Both decide 99 is under 100, so both allow.
4. Both write 100.

Two requests went through one free slot, and the counter says everything is fine. Make the counter faster and the window gets smaller, but the race is still there. The fix is to make read, decide and write one indivisible step.

The options I ruled out

The design record for go-rate-limiter weighs four ways to get atomicity. Three were rejected:

Redis runs a Lua script to completion before it serves any other command, so nothing can interleave with the read-decide-write sequence inside it. The trade-off is explicit in the record: Redis becomes a hard dependency of the check path.

The token bucket script

A token bucket holds up to capacity tokens and refills at refill_rate per second. Instead of a background job topping buckets up, the script refills lazily: on each call it works out how many tokens accrued since the last one.

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now_ms = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'last_refill_ms')
local tokens = tonumber(data[1])
local last_refill_ms = tonumber(data[2])

if tokens == nil then
  tokens = capacity
  last_refill_ms = now_ms
else
  local elapsed_ms = math.max(0, now_ms - last_refill_ms)
  local refill = (elapsed_ms / 1000.0) * refill_rate
  tokens = math.min(capacity, tokens + refill)
  last_refill_ms = now_ms
end

local allowed = 0
local retry_after = 0

if tokens >= cost then
  allowed = 1
  tokens = tokens - cost
else
  if refill_rate > 0 then
    retry_after = math.ceil((cost - tokens) / refill_rate)
  end
end

redis.call('HSET', key, 'tokens', tokens, 'last_refill_ms', last_refill_ms)

if refill_rate > 0 then
  redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 60)
end

Three details matter. math.max(0, ...) means a request carrying an older timestamp can never produce negative refill. math.min(capacity, ...) caps the burst. And the EXPIRE lets an idle tenant's bucket disappear once it would be full anyway, so memory does not grow with every key ever seen.

Calling it from Go

The scripts are embedded in the binary and loaded into Redis once at startup. Each check then sends only the script's SHA and its arguments.

//go:embed scripts/*.lua
var luaScripts embed.FS

func (r *RateLimiter) checkTokenBucket(ctx context.Context, key TenantRouteKey, rule entity.Rule, cost int64) (entity.RateLimitDecision, error) {
	nowMs := time.Now().UnixMilli()
	redisKey := TokenBucketKey(key)

	result, err := r.client.EvalSha(ctx, r.tokenBucketSHA, []string{redisKey},
		rule.BucketCapacity,
		rule.RefillRate,
		nowMs,
		cost,
	).Int64Slice()
	if err != nil {
		return entity.RateLimitDecision{}, fmt.Errorf("%w: %v", domainerrors.ErrRateLimitBackend, err)
	}
	return parseDecision(result, rule)
}

A sliding window without storing every request

A true sliding window stores a timestamp per request. This one keeps just two counters, the current fixed window and the previous one, and weights the previous window by how much of it still overlaps the last window seconds.

local prev_count = tonumber(redis.call('GET', prev_key) or '0')
local curr_count = tonumber(redis.call('GET', curr_key) or '0')
local window_start = curr_window * window
local elapsed = now - window_start
local weight = 1 - (elapsed / window)
local estimate = prev_count * weight + curr_count

if estimate + cost > limit then
  local retry_after = math.ceil(window - elapsed)
  local reset_at = window_start + window
  local remaining = math.max(0, math.floor(limit - estimate))
  return {0, remaining, reset_at, retry_after}
end

Twenty seconds into a 60-second window, two thirds of the previous window still counts. It is an approximation, but it avoids the classic fixed-window problem of a full burst at the end of one window followed by another at the start of the next. A deny also returns before incrementing, so rejected traffic does not eat future quota.

Deciding what failure means

If Redis is unreachable the service cannot know the counter, so it has to pick a direction. It returns 503 and fails closed. Failing open means unlimited traffic during an outage. Returning 429 would be misleading, and a client might retry forever. The cost is stated plainly: a short Redis blip blocks checks rather than bypassing limits.

Measuring it honestly

k6 at a constant arrival rate, 15 seconds per tier, against one API instance on a local Docker stack sharing a MacBook with Postgres, Redis and Prometheus. Latency is the full HTTP round trip including auth, not Redis alone.

p50 is under a millisecond; p95 is not, so I do not claim sub-millisecond latency. The 5,000 req/s row is where one instance falls over, and I have not isolated why yet. A benchmark that only shows the tiers that pass tells you nothing about where the edge is.

What I would do differently

• Handle NOSCRIPT. Scripts are loaded once at startup, so a Redis restart that loses its script cache would return 503s until the app restarts. Falling back to EVAL fixes that.
• Use Redis TIME instead of time.Now(). With several instances, clock skew affects refill and window rollover.
• Cache authentication. Rules sit behind a 30-second cache, but key and tenant lookups still hit Postgres on every check.