System Design Interview: Designing a Distributed Rate Limiter in Go

“Design a distributed rate limiter” is a question where the first three minutes are enough to tell someone who has run production systems from someone who just read a blog post. The limiter itself isn’t hard. The assumptions behind it are: who gets limited, how accurately, and what happens when Redis dies.

1. Taking the question: ask before you draw

For the first three or four minutes I only ask questions. Every answer changes the design completely.

Limited along which dimension? User, API key, IP, or tenant? A B2B SaaS counts quota per tenant, because the party that pays is also the party that generates load. A public API goes by API key. IP is only a secondary layer: NAT packs thousands of people behind one IP.

What’s the latency budget? The limiter sits on the critical path. If the system’s p99 is 200ms, this layer has to stay under 5ms, and that number decides whether you call Redis once, twice, or not at all.

How accurate does it need to be? “Exactly 1000 requests per minute, not one more” is a very different thing from “don’t let a tenant go over by more than 1.5x”. The first forces every request through a single atomic point. The second allows handing out quota in batches.

If Redis dies, fail-open or fail-closed? Fail-open lets traffic straight into the system, which is dangerous if the limiter is the only thing shielding the database. Fail-closed returns 429 to everyone, which for a public API is a self-inflicted outage.

Single-region or multi-region? With multi-region, each region gets its own Redis and the global limit becomes an approximate sum. Or every region calls one central Redis, which adds 100-200ms and blows the latency budget.

Do we need burst? A client that opens a page, fires 20 parallel requests, then goes quiet for ten seconds is perfectly normal. A hard window of 60 requests/minute blocks it unfairly.

Do we need to show remaining quota? If the client needs X-RateLimit-Remaining, then the allow decision has to carry the remaining balance, meaning the atomic script returns more than one bit.

I turn my assumptions into a short paragraph and ask the interviewer to confirm. Building on a wrong assumption is the fastest way to lose points.

2. Requirements and back-of-envelope

Say the interviewer settles on this: a multi-tenant API, 50,000 req/s at peak, p99 for the limiting layer under 5ms, burst needed, a few percent of error tolerated, single-region, Redis backend.

Keys: 200,000 tenants times 8 route groups (not individual URLs) gives 1.6 million live keys. A token bucket keeps tokens and ts in one hash, around 150 bytes per key. That’s about 240MB before replicas, enough that you have to shard.

Latency: one EVAL inside the same availability zone costs 0.2-0.5ms, which fits the 5ms budget. Across regions it becomes 30-150ms, so the limiter never calls Redis across regions.

Throughput: Redis is single-threaded. One strong instance does around 100,000 simple commands per second, but a Lua script is heavier than GET or INCR, so in practice it’s 50,000-80,000 runs per second. With a 50,000 req/s peak, a single shard is too close to the ceiling, so I plan for three to four shards.

3. The middleware contract

The rate limit layer is middleware wrapping the handler: it runs before the handler and returns exactly one decision plus metadata.

Key: rl:{tenant_id}:{route_class}:{window}. I use route_class (read, write, export) instead of the raw path. Raw paths make keys explode with query strings and open a hole: add one odd parameter and you get a new bucket, which means a free extra quota.

The limit itself doesn’t go into the key. Config lives in a tier + route_class table, loaded into memory and refreshed periodically, so changing a quota needs no migration.

type Decision struct {
	Allowed    bool
	Limit      int
	Remaining  int
	ResetAt    time.Time
	RetryAfter time.Duration
}

type Limiter interface {
	Check(ctx context.Context, key string, cost int) (Decision, error)
}

func RateLimit(l Limiter, keyFn func(*http.Request) string, fallback Decision) func(http.Handler) http.Handler {
	return func(next http.Handler) http.Handler {
		return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
			d, err := l.Check(r.Context(), keyFn(r), 1)
			if err != nil {
				// Redis error: handle per the policy agreed during requirements clarification.
				// fallback is a decision from the local limiter, not a constant.
				d = fallback
			}

			h := w.Header()
			h.Set("X-RateLimit-Limit", strconv.Itoa(d.Limit))
			h.Set("X-RateLimit-Remaining", strconv.Itoa(max(d.Remaining, 0)))
			h.Set("X-RateLimit-Reset", strconv.FormatInt(d.ResetAt.Unix(), 10))

			if !d.Allowed {
				h.Set("Retry-After", strconv.Itoa(max(1, int(math.Ceil(d.RetryAfter.Seconds())))))
				w.WriteHeader(http.StatusTooManyRequests)
				return
			}
			next.ServeHTTP(w, r)
		})
	}
}

Three details are easy to get wrong. X-RateLimit-Reset is an absolute epoch in seconds, while Retry-After is the number of seconds to wait. Mixing the two makes clients retry at the wrong time. The headers must be set even when the request is blocked. And max(a, b) is a builtin since Go 1.21.

4. Comparing algorithms and why I pick one

Fixed window is the cheapest, one INCR and one EXPIRE, but it has a boundary flaw. A limit of 60 requests/minute allows 60 at 11:59:59 and 60 more at 12:00:00. That’s 120 requests in two seconds.

A sliding window log is perfectly accurate, but RAM scales with the number of requests: 60 elements times 1.6 million keys is nearly a hundred million elements. It only fits when the key count is small, such as brute-force protection per account.

A sliding window counter is an approximation: two counters (current and previous window), interpolated by elapsed time. The error is a few percent, it gets worse when traffic is heavily skewed to one side, and it doesn’t allow burst.

A token bucket keeps a refill rate of R tokens/second and a capacity of B. A request takes one token, an empty bucket rejects, and burst is capped at B. State is two numbers. The model matches real behavior: quiet, then a sudden spike.

A leaky bucket drains at a fixed rate through a queue. It smooths traffic well, but adds queueing delay and needs memory for the queue. In practice it’s more a traffic shaper than a limiter. The GCRA variant has state as small as a token bucket and is what redis-cell uses.

I pick the token bucket for three reasons. I need burst, so fixed window and the sliding counter don’t fit. The state is only two numbers, so RAM is acceptable. And golang.org/x/time/rate implements exactly these semantics, so the local tier and the Redis tier share one model. The price: two state fields have to be updated atomically, which leads to the Lua script in section 6.

5. The single-node version in Go

Before going distributed, I can always describe the single-machine version.

type bucket struct {
	lim      *rate.Limiter
	lastSeen atomic.Int64 // unix nano
}

type localStore struct {
	mu      sync.RWMutex
	buckets map[string]*bucket
	rate    rate.Limit
	burst   int
	ttl     time.Duration
}

func (s *localStore) limiterFor(key string) *rate.Limiter {
	now := time.Now().UnixNano()

	s.mu.RLock()
	b, ok := s.buckets[key]
	s.mu.RUnlock()
	if ok {
		b.lastSeen.Store(now)
		return b.lim
	}

	s.mu.Lock()
	defer s.mu.Unlock()
	if b, ok := s.buckets[key]; ok { // re-check after taking the write lock
		b.lastSeen.Store(now)
		return b.lim
	}
	b = &bucket{lim: rate.NewLimiter(s.rate, s.burst)}
	b.lastSeen.Store(now)
	s.buckets[key] = b
	return b.lim
}

rate.NewLimiter(rate.Limit, int) takes a rate in tokens/second and a bucket capacity. The bucket starts full, so the very first request bursts right away. rate.Every(d) is equivalent to rate.Limit(1/d.Seconds()). rate.Limit(0) blocks everything, and rate.Inf lets everything through.

The map is only safe with a janitor: a goroutine that runs every minute and deletes keys whose lastSeen is older than the TTL (usually 2 * burst / rate). Without it the map grows without bound, and an attacker only needs to send millions of distinct keys to eat all your RAM, so add an element cap or LRU eviction.

Allow() rejects immediately when tokens run out. Wait(ctx) holds the request until a token is available, which turns the limiter into a queue. Every waiting request occupies a goroutine and a connection exactly when the system is overloaded. I use Allow for public APIs and Wait for background jobs, where backpressure is what you want. ReserveN returns a *Reservation, and Delay() tells you how long to wait, which is exactly what you need to compute Retry-After.

6. Going distributed: why you can’t read then write

On one instance, a mutex is enough. Across several instances, the naive approach is to GET the token count, compute in Go, then SET it back. Two instances can both see a token left and both let the request through, so the limit gets exceeded by up to the number of instances. At 50,000 req/s, a race window of a few hundred microseconds is enough to let hundreds of requests slip through every minute.

WATCH/MULTI/EXEC is logically correct, but every collision means retrying the whole thing, and under high load the retry rate grows with contention. Lua is one round trip for the read, the computation, the write, and setting the TTL.

Lua is atomic because Redis processes commands on a single thread, and while a script runs it doesn’t slip other clients’ commands in between. That’s no interleaving, not a transaction-style rollback. The consequence: a long-running script blocks the whole server, so keep it O(1).

-- KEYS[1]: rate limit key
-- ARGV[1]: rate (tokens/second)  ARGV[2]: burst  ARGV[3]: cost  ARGV[4]: ttl (seconds)
local key   = KEYS[1]
local rate  = tonumber(ARGV[1])
local burst = tonumber(ARGV[2])
local cost  = tonumber(ARGV[3])
local ttl   = tonumber(ARGV[4])

-- Use Redis's clock as the single time source for every instance.
local t   = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

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

if tokens == nil then
  tokens = burst
  ts     = now
end

local delta = now - ts
if delta < 0 then delta = 0 end        -- guard against the clock going backwards
tokens = math.min(burst, tokens + delta * rate)

local allowed = 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
end

redis.call('HSET', key, 'tokens', string.format('%.6f', tokens), 'ts', string.format('%.6f', now))
redis.call('EXPIRE', key, ttl)

local wait = 0
if allowed == 0 then
  wait = (cost - tokens) / rate
end

return { allowed, math.floor(tokens), math.ceil(wait * 1000) }

var tokenBucket = redis.NewScript(luaSource)

func (l *RedisLimiter) Check(ctx context.Context, key string, cost int) (Decision, error) {
	res, err := tokenBucket.Run(ctx, l.rdb, []string{key},
		l.ratePerSec, l.burst, cost, l.ttlSeconds).Int64Slice()
	if err != nil {
		return Decision{}, err
	}
	return Decision{
		Allowed:    res[0] == 1,
		Remaining:  int(res[1]),
		RetryAfter: time.Duration(res[2]) * time.Millisecond,
	}, nil
}

Two traps in the script. Numbers in Lua are doubles, and HSET converts them to strings using the default representation, so I format explicitly with string.format('%.6f', ...). And the TTL must be longer than burst / rate. If it’s shorter, the key expires midway, the bucket is recreated full, and the tenant quietly goes over its limit.

The INCR variant also comes up a lot, and the correct version has to be a single script:

-- Atomic fixed window: INCR and PEXPIRE in the same script run
local n = redis.call('INCR', KEYS[1])
if n == 1 then
  redis.call('PEXPIRE', KEYS[1], ARGV[1])
end
if n > tonumber(ARGV[2]) then
  return { 0, 0 }
end
return { 1, tonumber(ARGV[2]) - n }

What the interviewer wants to hear: calling INCR and EXPIRE as two separate commands is not atomic. If the process dies or the connection drops between the two, the key lives forever with no TTL. The counter never resets, the tenant is blocked permanently, and memory leaks. Avoid it by combining them in Lua, by SET key 0 EX <n> NX before the INCR, or by EXPIRE key <n> NX in Redis 7.

7. A two-tier architecture to cut round trips

flowchart LR
  C["Client"] --> MW["Go middleware"]
  MW --> L{"Local bucket<br/>RAM, ~µs"}
  L -- "tokens left" --> OK["Handler processes"]
  L -- "local bucket empty" --> RD[("Redis<br/>token bucket via Lua EVAL<br/>atomic, ~1ms")]
  RD -- "tokens left" --> OK
  RD -- "empty" --> R429["429 + Retry-After"]
  RD -. "periodic quota sync" .-> L

Calling Redis for every request is correct but expensive: 50,000 round trips per second, each one a chance for latency to climb. The two-tier architecture trades accuracy for latency.

Static split: divide the global limit evenly by the number of instances, and each instance decides locally. It’s cheap, but wrong when load is uneven. An instance receiving three times the traffic starts rejecting early while the total still has quota to spare.

Batch leasing: an instance keeps a local bucket and only calls Redis when it needs a refill. It asks for a batch of 200 tokens and spends them down, so for a large tenant one round trip serves 200 requests. The cost: over-admission is bounded by the number of instances times the batch size, and the unspent quota of a dead instance is stuck until the lease expires.

Asynchronous sync: count locally and push to Redis every 100ms. It’s the cheapest in latency and the worst in accuracy, because a spike within 100ms multiplied by the number of instances can overshoot the limit by a lot.

Multi-region: each region has its own bucket, and a global bucket hands out batches of tokens to each region periodically, a hierarchical token bucket. The more you push checks to local, the lower the latency and the lower the accuracy. For an absolute hard limit, every request must go through one synchronous atomic check.

8. Production traps

Hot key. A tenant taking 20% of the traffic has a key that lands in exactly one hash slot, heating one shard while the others sit idle. Redis Cluster shards by hash slot, and you can’t choose where a key goes. The fix: split the key into k elements with a random suffix and divide tokens evenly, or give that tenant a dedicated Redis cluster.

Clock skew. If every instance takes its own time.Now(), a skew of a few hundred milliseconds makes buckets diverge. Let Redis be the single time source: the script uses redis.call('TIME') and instances only send parameters. The script runs on the master, so replica lag isn’t a concern.

Redis connection loss. Fail-open loses the shield, fail-closed creates your own outage. The pragmatic answer is a local fallback tier: when Redis errors, each instance switches to a limit equal to the total divided by the number of instances, accepts the approximation, and records a metric for the degraded mode. Pair it with a circuit breaker with a 20-50ms timeout.

Thundering herd on reset. Fixed window resets every key at the same wall-clock moment, so thousands of clients that were just blocked all retry at once. A token bucket is better because it recovers continuously per key. Add two cheap measures: offset the window boundary by a hash of the key, and add jitter to Retry-After.

9. Observability: what to measure to know the limiter is alive

Three groups of metrics: allow/deny counters split by scope (tenant, global, IP) and tier; a latency histogram for the limit layer itself, because a 5ms budget only means something if you measure it; and a Redis error counter. Don’t label by raw tenant id, since a few hundred thousand tenants means a few hundred thousand time series.

Alert on an unusual rise in deny rate (bad config or an attack), on Redis errors above zero, and on the p99 of EVAL exceeding the budget. An unusually low deny rate is also worth an alert: it usually means the limiter just stopped working.

Verification has three parts: a load test to confirm p99 stays within budget and the number of requests accepted per window matches the limit within a predefined error margin; a chaos test that kills Redis to confirm fail-open doesn’t push the database past its safe limit; and unit tests that pass time explicitly into AllowN/ReserveN.

10. Wrapping up, and the follow-ups that come up often

I don’t need the interviewer to remember that I know Lua. What’s more memorable is that every choice maps to a trade-off I can state: token bucket because I need burst; Lua because I need an atomic read-compute-write; two tiers to cut round trips; Redis time because I need a shared time source.

A few follow-ups that come up often:

• Limit both IP and user? Two independent layers, reject if either layer rejects, and check the local layer first.
• Heavy and light requests counted the same? No: cost goes into the script (10 for heavy, 1 for light), matching AllowN in the local tier.
• Want an absolute hard limit? Drop the lease, send every request through one synchronous atomic check, and accept the round trip.

And if I could keep only one thing from that interview: the clarifying questions at the start aren’t a formality. They are the design.