Design a Rate Limiter — Token Bucket, Sliding Window, and Distributed Limits

"Design a rate limiter" sounds like a five-minute answer — count requests, block past the limit. Then the interviewer starts pulling threads: Which algorithm, and what's the burst behaviour at the window edge? Where does the counter live when you have 500 app servers? What happens to two requests that read the same counter at the same millisecond? What if the counter store goes down — do you block everyone or let everyone through? Those follow-ups are the whole interview. Here's how to answer all of them.

A rate limiter caps how many requests a client can make in a window — 100 requests per minute per user, say — and returns 429 Too Many Requests past that. It protects your system from abuse, runaway clients, and cost blow-ups, and it sits inline on every single request, so it has to be fast, memory-cheap, and correct across a whole fleet of servers. The two things that make it interesting: which counting algorithm you pick, and how you keep the count consistent when it's distributed. (New to the method? Start with the framework.)

TL;DR — the design at a glance

Concern	Decision
Algorithm	Token bucket (allows bursts, O(1) memory) or sliding-window counter (accurate, smooth)
Where it lives	API gateway / middleware, in front of app servers
State store	Redis — shared across all servers so the limit is global
Atomicity	Redis + a Lua script (or INCR) so concurrent requests can't over-count
On store failure	Fail open (don't take the API down because the limiter is down) — usually
Response	429 + Retry-After and X-RateLimit-* headers

• The two hard parts are the algorithm and making it distributed — everything else is glue.
• Fixed window is simplest but allows a 2× burst at the window boundary — know this trap.
• Sliding-window log is exact but stores every request timestamp (memory-heavy). Sliding-window counter approximates it at O(1) memory.
• Token bucket is the industry default (Stripe, AWS): stores just {tokens, lastRefill}, allows controlled bursts, enforces a steady average.
• With many servers, a local counter means the real limit is N × servers. Use a shared store (Redis) for a true global limit.
• The shared counter has a read-modify-write race — fix it with atomic ops (Redis INCR / Lua scripts).
• Fail open vs fail closed is a real decision: fail open for general throttling, fail closed for security limits (e.g., login attempts).
• Rate-limiting by IP is fooled by NAT and proxies (many users, one IP) and by attackers rotating IPs — combine signals.

The one mental shift: a rate limiter is inline on every request, so its cost is paid by all traffic, all the time. That reframes every choice — the algorithm must be O(1), the store lookup must be atomic and sub-millisecond, and the failure mode must not take your whole API down with it.

Step 1 — Requirements & scope

Functional:

• Limit a client (by user ID, API key, or IP) to N requests per window.
• Return 429 with a Retry-After when the limit is exceeded.
• Support different rules per endpoint and per tier (free vs paid).

Parked: billing/quotas over long periods, per-user analytics dashboards.

Non-functional:

• Low overhead — it runs on every request; target well under a millisecond added.
• Accurate enough — small over/under-counting at the margins is usually fine; exactness costs memory.
• Distributed — must work across a horizontally-scaled fleet.
• Highly available — the limiter failing must not fail the API (decide the failure mode explicitly).

Step 2 — Back-of-envelope estimates

Say the API peaks at 1,000,000 requests/sec. Every one needs a limit check, so the limiter must sustain 1M checks/sec and add < 1 ms each.

Memory: token bucket stores {tokens, lastRefill} — roughly a few dozen bytes per active client. Even 100M active clients ≈ a few GB, which fits comfortably in Redis. (Sliding-window log, storing every timestamp, would be far larger — a reason to avoid it for busy clients.)

Step 3 — The rule model & response

A rule is just:

{ clientId, limit, windowSeconds }      # e.g. 100 requests / 60s per user

And the check returns an allow/deny plus metadata for the caller:

HTTP 200  X-RateLimit-Limit: 100
          X-RateLimit-Remaining: 42

HTTP 429  Too Many Requests
          Retry-After: 27
          X-RateLimit-Remaining: 0

Returning Retry-After and the remaining count is good manners — well-behaved clients back off instead of hammering you.

Step 4 — Where the state lives

The counter state goes in a fast in-memory store — Redis — keyed by client (and optionally endpoint):

key = "rl:{clientId}:{endpoint}"
value = depends on algorithm (a count, or {tokens, lastRefill}, or a timestamp set)

Why not just keep it in the app server's memory? Because you have many app servers, and a per-server counter means the effective limit is N × (number of servers) — the client blows past your intended limit. A shared store gives one global count. (More on the local-vs-shared trade in Step 7.)

Step 5 — High-level architecture

The limiter is middleware at the edge — in the API gateway or a thin service every request passes through — backed by a shared Redis:

  Client ──▶ [ API Gateway / rate-limit middleware ] ──▶ [ App servers ]
                        │  check + update (ATOMIC)
                        ▼
                 [ Redis: per-client counters ]
                        │
       allowed ─▶ forward request      exceeded ─▶ 429 Too Many Requests

Put it at the gateway so rejected traffic never reaches (or costs) your app servers.

Step 6 — Deep-dive: the counting algorithms

This is the core of the interview. Five options, from naive to production.

1. Fixed window counter

Count requests per fixed clock window (e.g., per minute). INCR a per-window key; reject when it exceeds the limit; the key resets each window.

• Pro: dead simple, O(1) memory, one atomic INCR.
• Con — the boundary burst: a client can send the full limit at 00:00:59 and the full limit again at 00:01:00 — 2× the limit in ~1 second, because the window reset in between. A real problem for anything you're actually protecting.

2. Sliding window log

Store a timestamp for every request (a Redis sorted set). On each request: drop timestamps older than now − window, count what's left, and allow if under the limit.

• Pro: perfectly accurate — a true rolling window, no boundary burst.
• Con: memory grows with request volume — a busy client can store thousands of timestamps. Expensive at scale.

3. Sliding window counter (the sweet spot)

Approximate the rolling window using just two fixed-window counts — the current and previous window — weighted by overlap:

estimated = current_count + previous_count × (overlap fraction of the window)
# 30s into the current minute:  prev_count × 0.5 + current_count

• Pro: O(1) memory (two counters), smooths the boundary burst, close enough for almost everything. This is what many CDNs use.
• Con: an approximation — slightly off if traffic is very bursty, but rarely enough to matter.

4. Token bucket (the industry default)

Picture a bucket that holds up to C tokens and refills at r tokens/sec. Each request takes one token; an empty bucket means reject.

  refill: +r tokens/sec, capped at capacity C   (C = max burst size)
                     │
                     ▼
        [ bucket: tokens ]  ── request takes 1 token ──▶  allow if ≥1, else 429

allow(client):
  now = time()
  tokens = min(C, tokens + (now - lastRefill) * r)   # lazily refill
  lastRefill = now
  if tokens >= 1:
    tokens -= 1
    return ALLOW
  return DENY

• Pro: stores only {tokens, lastRefill} (O(1)); allows controlled bursts up to C while holding the average at r; refills lazily so there's no background timer. Used by Stripe, AWS, and most API gateways.
• Con: two tunables (capacity and refill rate) to reason about.

5. Leaky bucket

Requests enter a fixed-size FIFO queue and are processed at a constant rate; overflow is rejected. Where token bucket allows bursts, leaky bucket smooths them out into a steady stream — useful for shaping traffic to a downstream that needs a constant rate.

What to pick: token bucket for a general API limiter (efficient, burst-friendly), or sliding-window counter when you want accuracy without the log's memory cost. Reach for fixed window only when the boundary burst genuinely doesn't matter.

Step 7 — Making it distributed (the second hard part)

A single-server token bucket is easy. The interview's real target is the fleet.

Problem 1 — local counters don't add up. If each of 500 servers keeps its own bucket, a client gets 500 × limit. Fix: a shared store (Redis) that all servers read and write, so there's one authoritative count.

Problem 2 — the read-modify-write race. Two requests for the same client hit two servers at the same instant, both read tokens = 1, both decide "allowed," both decrement — the client got two through a bucket that had one. Fix: atomicity. For fixed window, INCR is atomic. For token bucket or sliding window, wrap the whole read-check-write in a Redis Lua script, which runs atomically on the server — no interleaving.

Problem 3 — the Redis round trip on every request. That's latency added to all traffic. Mitigations:

• Co-locate Redis (same region/AZ) and pipeline.
• Hybrid / local approximation — count locally and reconcile with the shared store periodically; trades a little accuracy for a lot less latency at extreme throughput.
• Sticky routing — hash each client to a fixed server (consistent hashing) so its local bucket is authoritative — no shared store, but it complicates load balancing and failover.

Problem 4 — Redis as a hot spot / SPOF. Shard counters by clientId and replicate for failover. A single extremely hot client can make its key a hotspot; if that's real, shard that client's budget across keys.

Step 8 — Trade-offs & wrap-up

• Accuracy vs memory vs latency: sliding-window log (exact, heavy) → sliding-window counter (approx, light) → token bucket (burst-friendly, light) → fixed window (simplest, boundary burst).
• Fail open vs fail closed: if Redis is unreachable, do you allow everything (fail open — protects availability, risks overload) or block everything (fail closed — protects the resource, risks an outage)? Default to fail open for general throttling; fail closed for security-critical limits like login or payment attempts.
• Shared vs local state: shared is accurate but adds a network hop; local is fast but approximate. Pick per latency budget.

The design checklist

• Scoped: limit by client, 429 + Retry-After, per-endpoint/tier rules.
• Estimated the check rate (inline on every request) and per-client memory.
• Chose an algorithm and justified it (token bucket / sliding-window counter).
• Called out the fixed-window boundary burst.
• State in a shared store (Redis) for a global limit.
• Made the update atomic (INCR / Lua) to kill the race.
• Addressed latency (co-locate, hybrid, or sticky routing).
• Decided fail open vs fail closed — and why.

In production at Mattrx

Mattrx's public API peaks at roughly 3,200 req/sec spread across tenants, and originally there was no per-tenant ceiling at all. A single aggressive tenant — usually a runaway scraper or an over-eager batch job — could burst hard enough to push API p99 into the seconds and drag every other tenant's latency down with it. Moving a per-tenant token bucket to the gateway meant those bursts now collect 429s instead of stealing shared capacity, and it was one of the changes that helped hold API p95 at 120ms (down from 480) while flattening the p99 tail.

Metric	Before	After
API p95 latency	480 ms	120 ms
p99 during a single-tenant burst	multi-second spikes	flat, no cross-tenant spike
Blast radius of one abusive tenant	all tenants degraded	isolated to that tenant (429 + Retry-After)
Per-tenant request budget	none	token bucket, 200 burst / 100 req/s
Enforcement point	none	gateway, before routing and business logic

Rate limiting was a contributor here, not the whole story — the p95 win landed alongside query and caching work — but per-tenant isolation is what keeps one tenant's traffic from becoming everyone's problem.

The architecture at Mattrx

  React dashboard / API clients  (~3,200 req/sec peak)
        │
        ▼
  [ Azure App Service · .NET 9 API ]
        │  rate-limit middleware (tenant from the bearer token)
        ▼
  [ Azure Cache for Redis ]  ── atomic Lua token bucket, one per tenant
        │
   allow ─▶ forward to CQRS handlers      deny ─▶ 429 + Retry-After

Production implementation (Mattrx)

The gateway runs this middleware ahead of routing, and the read-refill-check-decrement is a single atomic Redis Lua script so concurrent gateway instances can never double-spend a tenant's budget.

using System.Globalization;
using System.Security.Claims;
using Microsoft.AspNetCore.Builder;
using Microsoft.AspNetCore.Http;
using Microsoft.Extensions.Logging;
using StackExchange.Redis;

namespace Mattrx.Api.Gateway.RateLimiting;

public sealed record TokenBucketPolicy(int Capacity, double RefillPerSecond);

public sealed class TenantRateLimitMiddleware(
    RequestDelegate next,
    IConnectionMultiplexer redis,
    ILogger<TenantRateLimitMiddleware> logger)
{
    // Atomic read -> refill -> check -> decrement, executed entirely inside Redis.
    // Because it is one script, two gateway instances cannot race and over-spend
    // the same tenant's budget. Returns { allowed(0|1), retryAfterSeconds }.
    private const string TokenBucketLua = """
        local capacity = tonumber(ARGV[1])
        local refill   = tonumber(ARGV[2])   -- tokens per second
        local now      = tonumber(ARGV[3])   -- unix ms
        local wanted   = tonumber(ARGV[4])

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

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

        local elapsed = now - ts
        if elapsed < 0 then elapsed = 0 end
        tokens = math.min(capacity, tokens + (elapsed * refill / 1000.0))

        local allowed = 0
        local retry_after = 0
        if tokens >= wanted then
            tokens = tokens - wanted
            allowed = 1
        else
            retry_after = math.ceil((wanted - tokens) / refill)
        end

        redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
        -- Reclaim idle buckets once a full refill window has elapsed.
        redis.call('PEXPIRE', KEYS[1], math.ceil((capacity / refill) * 1000) + 1000)

        return { allowed, retry_after }
        """;

    // Public-API default: 200-token burst, 100 req/s sustained, per tenant.
    private static readonly TokenBucketPolicy DefaultPolicy = new(Capacity: 200, RefillPerSecond: 100);

    public async Task InvokeAsync(HttpContext context)
    {
        var tenantId = ResolveTenantId(context.User);
        if (tenantId is null)
        {
            // Unauthenticated traffic is rejected by auth middleware upstream;
            // there is no per-tenant bucket to meter here.
            await next(context);
            return;
        }

        var policy = DefaultPolicy;
        // Hash tag keeps a tenant's key on one slot under Redis Cluster.
        var bucketKey = (RedisKey)$"ratelimit:{{tenant:{tenantId}}}:public-api";
        var nowMs = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();

        var db = redis.GetDatabase();
        var raw = (RedisValue[])(await db.ScriptEvaluateAsync(
            TokenBucketLua,
            [bucketKey],
            [policy.Capacity, policy.RefillPerSecond, nowMs, 1]))!;

        if ((long)raw[0] == 1)
        {
            await next(context);
            return;
        }

        var retryAfter = Math.Max(1, (int)raw[1]);
        logger.LogWarning(
            "Rate limit exceeded for tenant {TenantId} on {Path}; retry after {RetryAfter}s",
            tenantId, context.Request.Path, retryAfter);

        context.Response.StatusCode = StatusCodes.Status429TooManyRequests;
        context.Response.Headers.RetryAfter = retryAfter.ToString(CultureInfo.InvariantCulture);
        context.Response.Headers["X-RateLimit-Limit"] =
            policy.Capacity.ToString(CultureInfo.InvariantCulture);

        await context.Response.WriteAsJsonAsync(new
        {
            error = "rate_limited",
            message = "Per-tenant request quota exceeded.",
            retryAfterSeconds = retryAfter
        }, context.RequestAborted);
    }

    // Tenant identity comes from the verified token, never from a query/route/header
    // the caller controls, so a client cannot target another tenant's bucket.
    private static string? ResolveTenantId(ClaimsPrincipal user)
    {
        if (user.Identity is not { IsAuthenticated: true })
        {
            return null;
        }

        return user.FindFirstValue("tenant_id")
            ?? user.FindFirstValue("https://mattrx.com/claims/tenant_id");
    }
}

public static class TenantRateLimitMiddlewareExtensions
{
    public static IApplicationBuilder UseTenantRateLimiting(this IApplicationBuilder app)
        => app.UseMiddleware<TenantRateLimitMiddleware>();
}

The tenant id is read from the authenticated principal rather than any caller-supplied argument, so one client can never spend down another tenant's bucket, and an empty bucket short-circuits with a 429 plus a Retry-After derived from the refill rate so well-behaved clients back off deterministically.

The honest stuff: caveats and when it's overkill

1. A single-server app doesn't need any of this. An in-memory token bucket is the whole solution — don't reach for distributed Redis until you actually have a fleet.
2. Fixed window's boundary burst is a real vulnerability. Don't use it to protect anything where a momentary 2× spike hurts (login, expensive endpoints).
3. Sliding-window log will eat your memory for high-volume clients — it stores every request. Avoid it unless you truly need exactness at low volume.
4. Fail open is a security hole for the wrong limits. For brute-force protection (logins, OTP), a downed limiter that fails open just disabled your defense — fail closed there.
5. IP-based limiting is blunt. NAT and corporate proxies put thousands of users behind one IP (you'll throttle innocents), and attackers rotate IPs (you won't catch them). Combine IP with user/API-key signals.
6. The Redis hop is on every request. At extreme scale it's a real latency and cost line item — that's when hybrid/local approximation earns its keep.
7. Clock skew breaks windows. Across servers, use the store's clock (Redis TIME) or a single source, not each server's wall clock, or your windows drift.

The model to carry forward

A rate limiter is an algorithm choice wrapped in a distributed-consistency problem. Pick the algorithm from what you're protecting — token bucket for burst-tolerant APIs, sliding-window counter when you want smoothness without the memory of a log. Then accept that the moment you have more than one server, correctness lives in a shared, atomic counter, and design around its latency and failure mode. Say "fail open, because I won't take the API down to protect it" out loud, and you've shown the judgment the question is really testing.

Three habits this problem teaches:

1. Name the boundary burst. It's the detail that separates "I've read about fixed windows" from "I've used them."
2. Make the shared update atomic, always. The read-modify-write race is the bug that quietly lets everyone past the limit.
3. Decide the failure mode on purpose. Fail open or closed is a one-sentence answer that shows you thought past the happy path.

Further reading

• How to Crack Any System Design Interview: A Repeatable Framework
• Design a URL Shortener (bit.ly) — The Complete Walkthrough
• We Replaced REST with Kafka and Cut Failures by 90%

---

Prepping for a system design round and want the rate-limiter follow-ups drilled — or the next "Design X" walked through the same way? I'm always happy to help; reach me at randhir.jassal@gmail.com.