How to Design a Rate Limiter: Algorithms, Architecture, and Trade-offs

4. Sliding window

The accurate answer that fixes the fixed-window edge case. Two variants:

Sliding window log: Store the timestamp of every request in the last window. On each request, count timestamps newer than now - window_size. Accurate, but memory grows with request rate.

on request(client_id):
  log = get_log(client_id)
  cutoff = now - window_size
  log.remove_older_than(cutoff)
  if len(log) < limit:
    log.add(now)
    return ALLOW
  else:
    return DENY

Sliding window counter: Weighted combination of current and previous fixed-window counts. Approximates the sliding log with O(1) memory.

on request(client_id):
  current = count_in_current_window(client_id)
  previous = count_in_previous_window(client_id)
  window_progress = (now % window_size) / window_size
  # Weight previous window by how much of it overlaps "the last window from now"
  estimated = previous * (1 - window_progress) + current
  if estimated < limit:
    increment_current(client_id)
    return ALLOW
  else:
    return DENY

Strengths: much more accurate than fixed window, no boundary-burst problem. Weaknesses: log variant is memory-heavy; counter variant is an approximation (off by a few percent under adversarial patterns).

When to use: when fixed window's inaccuracy matters — billing-linked limits, security-critical limits (login attempts), tight SLAs with customers.

Picking among the four

The decision usually looks like:

• Token bucket — default choice for API rate limiting (allows bursts, memory-efficient, widely supported)
• Leaky bucket — when you specifically need smooth output (protecting fragile downstream systems)
• Fixed window counter — simple throttling where accuracy doesn't matter
• Sliding window — when boundary-burst accuracy matters (security, billing, strict SLAs)

In an interview, lead with token bucket and explicitly compare against the others. "I'd use token bucket because it handles bursts naturally and is simple to implement in Redis. If we needed stricter accuracy — say this were a login rate limit for security — I'd switch to sliding window log."

API design

The rate limiter exposes a minimal API to the services in front of it:

POST /v1/ratelimit/check
  Body: { client_id, endpoint, [optional: cost] }
  Returns: {
    allowed: bool,
    remaining: int,
    reset_at: timestamp
  }

Three things to note:

1. The cost parameter. Not every request consumes one token — an expensive search might cost 10 tokens, a cheap GET might cost 1. Passing the cost gives the caller control without changing the API.
2. The response contains remaining and reset_at. Clients can surface these as response headers (X-RateLimit-Remaining, X-RateLimit-Reset) so well-behaved clients self-throttle.
3. This is a synchronous check. Every request waits for the response. That's why latency matters so much — the rate limiter latency is added to every API call.

When the check denies a request, the caller should return HTTP 429 Too Many Requests with a Retry-After header indicating when the client can retry.

For the deeper treatment of API design, see mastering the API interview.

Data model and storage

At 1.7M QPS, the storage has to be:

• In-memory (disk reads are too slow)
• Atomic (multi-threaded checks must not race)
• Distributed-safe (state must be shared across all rate limiter instances)
• TTL-aware (we don't want to store counters for clients that went inactive forever)

That's Redis, essentially by definition. For the Redis deep dive, see Redis in system design.

Redis data structures for each algorithm:

• Fixed window: INCR client:endpoint:window_id with EXPIRE at window end. One command, atomic, trivial.
• Token bucket: Hash per client with fields tokens and last_refill. Use a Lua script to do refill + consume atomically (critical — otherwise two concurrent checks can both pass when only one should).
• Sliding window log: Sorted set keyed by client. Members are timestamps, scores are timestamps. Use ZADD to add, ZREMRANGEBYSCORE to trim old entries, ZCARD to count.
• Sliding window counter: Two counters per client (current + previous window) with weighted logic in the check.

For all algorithms beyond fixed window, use Lua scripts for atomic multi-step logic. Redis guarantees single-threaded execution of Lua scripts — eliminating race conditions that would otherwise require distributed locks.

Architecture: where does the rate limiter live?

Three common placement patterns, each with trade-offs:

Pattern 1: API gateway rate limiting

Rate limiting lives in the API gateway (Nginx, Kong, AWS API Gateway, Cloudflare), in front of all services.

Pros: Traffic never reaches your services if it's rate-limited — maximum protection. Centralized configuration. Usually has built-in rate limiting features you don't have to build yourself.

Cons: Gateway becomes a single point of contention. Custom rate limiting logic (per-endpoint costs, tier-specific limits) may require gateway extensions.

When to use: As the default for public-facing APIs. Combine with the next pattern for per-service control.

Pattern 2: Middleware rate limiting in the service

Rate limiting is a library/middleware inside each service (e.g., a middleware in Express.js, a filter in Spring Boot).

Pros: Service-specific logic, easy customization, no separate infrastructure.

Cons: Each service has to implement/maintain rate limiting. Traffic already hit your service before being rate-limited.

When to use: For internal service-to-service rate limiting where the overhead of a separate gateway isn't justified.

Pattern 3: Sidecar rate limiter

A separate rate limiter service (process or container) that every service calls before processing a request. Envoy's rate limiting service is the canonical example.

Pros: Centralized logic, language-independent, updatable without touching services.

Cons: Extra network hop per request (latency). Another service to operate.

When to use: Large microservice architectures where centralization matters and latency budget allows.

The common production pattern: Pattern 1 at the edge (coarse rate limiting) + Pattern 2 or 3 internally (fine-grained per-service rate limiting). Two layers, each doing what it's best at.

For the deeper architecture discussion, see load balancer vs reverse proxy vs API gateway.

The distributed rate limiting problem

Now for the part that actually makes this a senior-level interview question. Everything above assumes a single rate limiter instance. In production, you have hundreds of service instances, each potentially doing their own rate limit checks. This creates real correctness problems.

The naive approach — per-instance rate limiting — breaks immediately. If the limit is "100 req/sec per user" and you have 10 service instances, each maintaining its own counter, a user could actually get 1,000 req/sec (100 on each instance). No good.

The standard solution — centralized Redis. All rate limit state lives in a single Redis cluster. Every service instance checks Redis on every request. Redis handles the atomicity via Lua scripts or INCR.

This works, but raises new problems:

Problem: Redis becomes a bottleneck

At 1.7M QPS, a single Redis node can't handle it. Solution: Redis Cluster with sharding by client_id. Each rate limit key lives on one shard; cluster fans out across many nodes. Add shards as QPS grows.

Problem: Redis latency adds to every request

Even with Redis at sub-millisecond, at 1.7M QPS you're doing 1.7M network round trips per second. Solutions:

• Connection pooling to amortize TCP overhead
• Pipelining multiple checks into one round trip where possible
• Local caching with periodic Redis sync — each service keeps a small local bucket, syncs with Redis every few hundred requests. Trades a small amount of accuracy for significant latency savings. Used by Stripe's rate limiter.

Problem: Redis fails

When Redis is down, you have three options, each a trade-off:

1. Fail closed (deny all requests). Most correct — you genuinely don't know if the request is allowed. Costs availability.
2. Fail open (allow all requests). Preserves availability. Costs protection — a DDoS during a Redis outage goes through.
3. Fall back to local counters per instance. Allows more than the intended limit, but puts an upper cap on damage. Usually the right answer.

Most production rate limiters fail open OR fall back to local counters. Failing closed on your rate limiter taking down your whole API is a bad outcome.

This trade-off connects directly to CAP theorem and PACELC — rate limiters usually pick availability over perfect consistency, accepting that during network partitions they'll over-allow rather than under-allow.

Problem: consistency across regions

If your service runs in multiple regions, do you want a global rate limit or a per-region limit? Global is harder (cross-region Redis replication is slow) but more correct. Per-region is easy but can allow more than the nominal global limit.

Most systems use per-region rate limits with periodic reconciliation, accepting the inaccuracy. If you truly need strict global limits, you accept the latency hit of cross-region coordination.

How real companies do it

Anchoring your interview answer in real-world practice is powerful. A few documented approaches:

Stripe uses token bucket with Redis-backed state, heavily tuned for latency. They famously wrote about pushing Redis to handle hundreds of thousands of rate limit checks per second from thousands of workers, using local caches + Redis reconciliation.

GitHub's API uses fixed-window counters exposed via standard HTTP headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset). They also use a secondary rate limit for anti-abuse — a sliding window that catches burst patterns the fixed window misses.

Twitter (now X) uses a multi-tier approach — coarse gateway-level limiting at the edge, per-endpoint limits internally, and aggressive rate limiting on write endpoints vs read endpoints.

AWS API Gateway uses token bucket with configurable burst and steady-state rates. You configure two numbers: the sustained rate and the burst capacity.

Common interview follow-up questions

Once you've designed the initial rate limiter, expect these follow-ups:

• "How do you handle a hot shard in the Redis cluster?" (Composite keys with write sharding — if user_id "celebrity" is a hot key, split it into "celebrity:0", "celebrity:1", ... "celebrity:9", aggregate on read.)
• "What happens when the Redis cluster becomes unavailable?" (Fallback strategy — local counters + log for reconciliation, or fail-open with monitoring.)
• "How do you support different limits for different customer tiers?" (Store limits in a separate config store, looked up per-client on check. Cache config aggressively.)
• "How does this interact with autoscaling?" (When new service instances spin up, they should reuse the shared Redis state — the rate limit is per-user, not per-instance.)
• "What's the memory footprint at scale?" (Walk through the math — 500M users × 50 bytes ≈ 25GB, need multi-shard Redis.)
• "How do you prevent clients from bypassing the rate limiter by using many IPs?" (Rate limit by account/API key primarily, fall back to IP for unauthenticated requests, use device fingerprinting for abuse detection — but that's a separate anti-abuse system.)
• "How do you rate-limit by multiple dimensions simultaneously (per-user AND per-endpoint AND per-IP)?" (Multiple parallel checks with AND logic — deny if any limit is exceeded. Each check is its own Redis key.)
• "How would you design a rate limiter for a high-traffic event — Black Friday, ticket sales?" (Pre-provision Redis capacity, implement priority tiers, use request queuing instead of rejection for premium users. The ticketing system case study covers the flash-sale version of this.)

If you can handle six of these eight without hesitating, you've nailed the interview.

Putting it all together

The one-sentence version: Rate limiting caps request rate per client to protect your system. Use token bucket by default, back it with Redis for distributed state, accept small accuracy trade-offs in exchange for availability during failures, and place the rate limiter at the API gateway for maximum reach.

In an interview, structure your answer like this:

1. Clarify requirements out loud (what counts as a client, what are the limits, what's the latency budget)
2. Do rough capacity estimation (QPS, memory, Redis sizing)
3. Pick an algorithm (token bucket by default, explain why you'd pick differently)
4. Describe the data model and storage (Redis, data structure per algorithm, atomicity via Lua)
5. Place the rate limiter architecturally (gateway + service middleware, usually both)
6. Discuss distributed correctness (centralized Redis, local cache + sync, Redis failure strategy)
7. Handle the follow-ups gracefully — and notice that most of them are about failure modes, not happy paths

That structure separates juniors ("I'd use token bucket") from seniors ("I'd use token bucket for typical API rate limiting, back it with Redis Cluster sharded by client_id, implement the refill+consume logic in a Lua script for atomicity, fall back to per-instance counters if Redis goes unavailable, and expose standard X-RateLimit-* headers for well-behaved clients to self-throttle").

Good luck with your next interview.

Keep learning

Related posts for the topics this guide touched:

• Redis Guide for System Design — the deep dive on the storage backend that makes rate limiting work.
• Caching for System Design — related concept; rate limiting and caching overlap in several patterns.
• Mastering the API Interview — rate limiting is a core API design topic.
• Load Balancer vs Reverse Proxy vs API Gateway — where rate limiting fits in the request path.
• High Availability in System Design — relevant for rate limiter failure modes.
• CAP Theorem vs PACELC — the framework for understanding the consistency trade-offs in distributed rate limiting.
• Grokking Idempotency — related correctness concept for safe retries after 429s.
• How to Design a Ticketing System — a case study where rate limiting is the critical component (flash sales).
• Rate limiting is one of the 15+ case studies in Grokking System Design.-

For the full system design interview roadmap, start with my complete system design interview guide.