Rate Limiter

What is an API rate limiter?

A rate limiter controls how many requests a client can make in a given time window. Visit the Twitter API twice a second or a thousand times a minute and you cross a threshold; the next request gets a 429. The interesting engineering problem is not the counting itself; it is counting atomically across a fleet of servers without a per-request distributed lock, while keeping reject latency under 5ms and surviving Redis node failures without cascading 429s that bring your entire service down.

The central design question is: what happens to application traffic when the shared counter store is slow or unavailable? The answer drives the limiter's failure mode, timeout budget, and operational safeguards.

TL;DR

Put the limiter at the gateway, resolve the client identity and endpoint rule from an in-memory cache, and run the decision in one atomic Lua script against a Redis Cluster. Use two tagged window counters for an inexpensive sliding-window approximation, return 429 with standard rate-limit headers, and keep rules in a durable management service. A short Redis timeout, per-node circuit breaker, and higher local emergency limit let the application fail open when the shared counter store is unavailable.

Scope and assumptions

• The design targets API traffic shaping in one region across multiple availability zones; the gateway fleet is stateless.
• Limits are keyed by API key, authenticated user, or trusted client IP, and may vary by endpoint and tier.
• A 5–10% overshoot during a burst is acceptable for traffic shaping. Billing-grade quotas and exact per-request auditability are separate designs.
• Rule changes are infrequent compared with requests, so each gateway may cache them locally and receive invalidations asynchronously.
• Redis is an optimization and coordination dependency for counters, not a source of business data. The backend remains responsible for authorization and business-level quotas.

Functional Requirements

Core Requirements

1. Limit requests from a client to N per time window (for example, 1,000 req/min per API key).
2. Return HTTP 429 with a Retry-After header when the limit is exceeded.
3. Rules can vary per endpoint and per client tier (free vs. premium).
4. Rules are configurable without a code deploy.

Below the Line (out of scope)

• Billing or quota enforcement
• Full WAF protection or DDoS mitigation
• Geographic restrictions

The hardest part in scope: The distributed counter race condition. Counting requests in a single process is trivial. Counting them accurately across dozens of stateless servers sharing a Redis instance, without a lock per request, under sub-second time windows is the actual engineering challenge. The deep dives focus on this race, the algorithm choice, and the failure path.

Billing and quota enforcement are below the line because they require integration with a payments system and a separate overage billing model. To add them, tie the rate limit rules to a subscription_tier column in a billing table. When a request arrives, the rule lookup resolves the tier and checks the billing system for active quotas.

The rate limiter becomes a quota enforcer rather than just a traffic shaper.

WAF and DDoS mitigation are below the line because they require packet-level inspection, IP reputation scoring, and bot fingerprinting. These belong in a dedicated network appliance (CloudFlare, AWS WAF) sitting upstream of the rate limiter. The rate limiter handles API-level semantics; a WAF handles transport-level threats.

Geographic restrictions are below the line because they require a GeoIP lookup on every request and a rules table with a region dimension. To add them, tag the request context with a region code and add a region column to the LimitRule table. Rules then resolve on (api_key, endpoint, region) instead of (api_key, endpoint).

Non-Functional Requirements

Core Requirements

• Latency: The rate-limiting check adds less than 5ms p99 to every request. At 5ms, rate limiting is invisible to users but measurable in profiling.
• Availability: 99.99% uptime. On limiter failure, the system fails open (allows traffic) rather than failing closed (rejects all traffic).
• Throughput: Handle up to 1M requests per second across the fleet without degrading check latency.
• Scale: Support 10,000 concurrent API keys, each with independent per-key, per-endpoint, per-tier rules.
• Consistency: Prevent more than a 5-10% overshoot on the stated limit under burst conditions. Exact accuracy is not required, but wild overruns (10x the limit) are not acceptable.

Below the Line

• Sub-millisecond p99 latency (requires co-locating Redis with every app server, operationally complex)
• Persistent audit log of every reject event (needed for billing-grade enforcement but not for throttling)

Read/write ratio: Every incoming API request triggers one Redis counter write (INCR) and one implicit read (INCR returns the new value). This is roughly 1:1, not the read-heavy ratio we see in most systems. Rule lookups are the exception: rules update infrequently (perhaps once per hour), so rule reads are cached in memory on each gateway node. The counter INCR is the performance-critical operation on every single request, and it must be atomic.

The 1:1 counter read/write ratio means we cannot rely on read-heavy optimizations like CDN caching. The counter must be incremented and checked atomically on every call. This pushes toward Redis INCR, which combines the read (returns the new value) and the write (increments the counter) in a single atomic command.

Call out the 1:1 ratio early: it rules out read-heavy caching patterns for the counter itself and points directly to an atomic increment/check operation.

30-second answer

Rate-limit at the API gateway. Resolve the most specific identity and rule, then use an atomic Redis Lua script to read the current and previous window counters, increment the current one, and return the decision plus remaining capacity. Redis Cluster key tags keep both counters on one shard. Cache rules in memory, emit 429 and Retry-After when needed, and fail open through a local emergency limiter if Redis times out so a limiter incident does not become an application outage.

5-minute explanation

1. State the contract. Support per-identity and per-endpoint limits, runtime rule changes, and standard response headers. Target sub-5ms limiter overhead and allow bounded burst error.
2. Explain why local state fails. A counter in one gateway is correct only until load balancing sends the same client to another node.
3. Choose shared state. Put counters in Redis, where INCR is atomic. Replace fixed windows with a two-counter sliding-window approximation when boundary bursts matter.
4. Make the request path cheap. Resolve API key/user/IP and tier from local caches; execute one Lua script per request; keep the backend behind the allow decision.
5. Close the failure loop. Bound Redis calls to a few milliseconds, trip a circuit breaker after consecutive failures, use a local emergency ceiling, alert on fallback, and restore normal enforcement through a half-open probe.

45-minute interview approach

1. 0–3 min — Clarify scope. Confirm identity types, endpoint-specific rules, burst tolerance, single- versus multi-region deployment, and whether the goal is traffic shaping or billing-grade quota enforcement.
2. 3–8 min — Establish the numbers. Write down request rate, active identities, window sizes, p99 latency, availability target, and the acceptable overshoot. The request path is roughly one counter write per incoming request.
3. 8–13 min — Define entities and APIs. Sketch LimitRule, ClientIdentity, RequestCounter, the rule-management API, the internal check contract, and the 429 headers.
4. 13–22 min — Draw the baseline. Show the gateway fleet, Redis counter store, rules cache, backend, and the allow/reject flow. Explain why a local counter and an unbounded database call do not meet the numbers.
5. 22–35 min — Prioritize the hard parts. Spend most of the time on fixed versus sliding windows, Lua atomicity and Redis Cluster key tagging, identity resolution, and the Redis failure path. These decisions determine correctness and latency.
6. 35–40 min — Cover reliability, security, and operations. Discuss timeouts, circuit breaking, fail-open behavior, Redis failover, trusted proxy headers, key revocation, metrics, and alerting.
7. 40–44 min — Compare alternatives. Explain when token buckets, sliding logs, local per-node limits, or fail-closed behavior are appropriate, and why they are not the default here.
8. 44–45 min — Recap and invite follow-ups. Restate the one-request path, the accuracy boundary, and the behavior during Redis failure.

Core Entities

• LimitRule: The configuration for how many requests are allowed per window for a given combination of (key_type, tier, endpoint). Carries the limit N, the window duration in seconds, and the rule ID.
• RequestCounter: The current count of requests for a specific client in the current time window. Stored in Redis as a key with a TTL equal to the window duration. Never persisted to a relational database.
• ClientIdentity: The resolved identifier used for rate-limit bucketing (API key, user ID, or IP address). Determines which LimitRule applies to a given request.

Full schema details for the rules table, including indexes, tier columns, and composite key structure, are deferred to the deep dives. The three entities above are sufficient to drive the API design and High-Level Design.

API Design

The rate limiter is middleware, not a public-facing API. Clients never call it directly; it intercepts requests at the gateway layer. Two explicit interfaces are worth defining: the management API for configuring rules, and the internal check API used by gateway components that are not collocated with the limiter logic.

Configure a rate limit rule:

POST /rate-limit-rules
Body: {
  key_type: "api_key",
  tier: "free",
  endpoint: "/search",
  limit: 100,
  window_seconds: 60
}
Response: { rule_id: "rl_abc123" }

Get a rule:

GET /rate-limit-rules/{rule_id}
Response: { rule_id, key_type, tier, endpoint, limit, window_seconds }

Internal rate check (used by distributed gateway nodes that delegate to a centralized checker):

POST /check
Body: { key: "api-key-abc123", endpoint: "/search", tier: "free" }
Response: {
  allowed: true,
  remaining: 45,
  limit: 100,
  reset_at: 1720000060
}

When a request is rejected, the response includes the full set of throttle headers:

HTTP 429 Too Many Requests
Headers:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 0
  X-RateLimit-Reset: 1720000060
  Retry-After: 37
Body: { error: "rate_limit_exceeded", retry_after_seconds: 37 }

The X-RateLimit-* headers appear on every response, including successful ones, so well-behaved clients can self-throttle before hitting the limit. Retry-After is expressed in seconds (not an absolute timestamp) so client libraries can implement exponential backoff without timestamp arithmetic.

High-Level Design

1. Single server naive: in-memory counter per API key

A single-server in-memory counter handles the basic rate check but silently fails the moment a second gateway node is deployed.

The simplest rate limiter runs on a single server with an in-memory hash map from API key to request count. No external dependencies, no network calls.

Components:

• Client: Makes API requests to the gateway server.
• API Gateway (with in-memory map): On each request, increments the counter for the requesting API key. If the counter exceeds the configured limit for the current window, returns 429. Otherwise, forwards to the backend.
• Backend Service: Handles business logic. Only sees requests that passed the rate limit check.

Request walkthrough:

1. Client sends a request with an API key header.
2. Gateway extracts the API key from the X-API-Key header.
3. Gateway looks up the current counter for api_key in the local hash map.
4. If the counter exceeds the configured limit, return 429 with Retry-After.
5. Otherwise, increment the counter and forward the request to the Backend Service.
6. A background goroutine (or scheduled task) resets counters at each window boundary.

This design works on one server and adds zero latency overhead. The failure is obvious: deploy two gateway instances and each maintains its own counter. A client sending 100 requests per minute routes through round-robin load balancing, hitting each instance for 50 requests per minute.

Both counters stay under the 100-request limit. The client sends 200 requests per minute against a nominal 100-request limit, and neither server knows. The rate limiter is silently broken.

The single-server version is correct. The multi-server version is wrong in a way that ordinary per-node metrics may not catch, because every node believes it is enforcing the limit. This failure is best exposed by distributed load testing and a cross-node counter-accuracy metric.

2. Distributed tracking with a centralized Redis counter

Moving counters to a shared Redis instance gives all gateway nodes a consistent global view, solving the distributed counting problem.

Move the counters out of each server's memory and into a shared Redis instance. All gateway nodes read from and write to the same counter state.

Components:

• Load Balancer: Distributes incoming requests across the API Gateway fleet. No rate-limiting logic here; it is purely a traffic distributor.
• API Gateway Fleet: Multiple stateless gateway nodes. All share a single Redis connection pool. Rate limit state is no longer local to any node.
• Redis Counter Store: Holds one key per (api_key, window) pair. Each key is an integer incremented atomically with Redis INCR. The TTL equals the window duration so old window keys expire automatically without any cleanup job.
• Backend Service: Receives only requests that pass the centralized counter check.

Request walkthrough:

1. Client sends a request.
2. Load Balancer routes to any gateway node (round-robin or least-connections).
3. Gateway constructs the Redis key: rl:{api_key}:{window_start} where window_start = floor(now / window_seconds) * window_seconds.
4. Gateway calls INCR rl:{api_key}:{window_start}. Redis atomically increments and returns the new count.
5. If the returned count exceeds the configured limit, return 429.
6. Otherwise, forward to the Backend Service.
7. On the first INCR for a new window (count == 1), Gateway also calls EXPIRE rl:{api_key}:{window_start} {window_seconds} to attach a TTL.

All gateway nodes share the same Redis key namespace, so counts are globally accurate across the fleet. This is the baseline design; it solves the distributed counting problem cleanly and is where most teams start. The remaining questions are which windowing algorithm to use, how to handle Redis failures, and how to resolve rules per tier and endpoint.

All of those go to the deep dives.

3. Configurable rules per tier and endpoint

A Rules Service with per-node in-memory caching adds configurable per-tier, per-endpoint rules with zero added latency per request.

Not every client has the same limit. A free-tier API key gets 100 req/min on /search; a premium key gets 1,000. These rules must be configurable at runtime without a code deploy, and they must not add a database query to every request path.

Components:

• Rules Service: A separate service that owns the LimitRule table and exposes a CRUD management API. Publishes rule changes to a pub/sub channel so gateway nodes can refresh promptly.
• Rules Cache (in-memory per node): Each Gateway node caches the rules map in local memory, refreshed every 60 seconds from the Rules Service. A rule lookup is now a hash map read (CPU-bound), not a network round-trip.
• Redis Counter Store: Unchanged. The key now includes the endpoint to support per-endpoint limits: rl:{api_key}:{endpoint}:{window_start}.

Request walkthrough:

1. Client sends a request with an API key header.
2. Gateway resolves the ClientIdentity: extract API key from header, look up the tier from a cached key-to-tier map.
3. Gateway resolves the applicable LimitRule from the local in-memory rules cache using (key_tier, endpoint).
4. If no explicit rule exists, fall back to the global default rule (for example, 60 req/min for free-tier traffic).
5. Gateway calls INCR rl:{api_key}:{endpoint}:{window_start} in Redis.
6. If the returned count exceeds the rule's limit, return 429 with Retry-After and X-RateLimit-* headers.
7. Otherwise, forward to the Backend Service.

The 60-second local cache on each gateway node means a newly configured rule takes up to 60 seconds to propagate to all nodes. For a rate limiter this is acceptable: the window is typically 60 seconds, so at most one window is enforced under the old rule. For security-critical changes (revoking a compromised API key), add a pub/sub invalidation channel that triggers immediate cache refresh on all nodes.

This tradeoff matters because relying only on the 60-second TTL can leave a revoked key active for a full minute. Use pub/sub invalidation for security-critical changes and retain the TTL as a recovery path.

Critical flows

• Allow: The gateway resolves identity and rule from local caches, calls the atomic Redis script, adds rate-limit headers, and forwards the request only when the decision is allowed.
• Reject: The script returns the remaining capacity and reset time; the gateway returns 429 Too Many Requests with Retry-After without calling the backend.
• Configure: An operator updates a LimitRule; the Rules Service persists it and publishes an invalidation so gateway caches refresh without a deploy.
• Degrade: A bounded Redis timeout records a failure; the circuit breaker switches the node to the local emergency ceiling, emits an alert, and probes Redis before returning to global enforcement.

Deep dives

1. Which rate-limiting algorithm should we use?

The baseline design uses a fixed window counter, keyed on {window_start}. This is fast and simple, but it has a well-known spike problem. The deep dive is about whether to replace it with something more accurate.

2. How do we store counters at distributed scale?

The choice of counter storage determines both the accuracy of global limits and the throughput ceiling of the rate limiter as a whole.

3. How do we handle Redis failures without cascading 429s?

Redis is the shared state backbone for the rate limiter. When it goes down, every rate limit check fails. The decision of what to do with those requests during the outage determines whether you have a graceful degradation or a complete service outage.

4. How do we identify clients and resolve rules across tiers?

The rate limiter needs to know who is making a request and which rule applies. This sounds simple but has edge cases that repeatedly cause production incidents, especially around shared IPs and anonymous traffic paths.

Final Architecture

The key insight: every request pays for exactly one in-memory hash map lookup (rules resolution) and one atomic Redis round-trip (Lua sliding window check). The circuit breaker ensures the gateway continues serving traffic when Redis is unavailable. Accuracy degrades gracefully from exact (Redis healthy) to approximately permissive (local emergency limiter) rather than from exact to a service outage.

Interview Cheat Sheet

• Scope to four core behaviors up front: per-key limits, 429 with headers, per-tier rules configurable at runtime, and no code deploy required to update rules.
• State the read/write ratio explicitly: every incoming request triggers one Redis INCR. The rate limiter is write-heavy on the counter store, unlike most systems where reads dominate.
• Redis INCR is atomic. It reads, increments, and returns the new value in a single operation. No distributed lock is needed around it, ever.
• Fixed window counter has a boundary spike bug: a client can send double the configured rate across a window boundary. Always name this when asked about algorithm choices; it signals you know the failure mode.
• Sliding window counter beats fixed window with no memory overhead. Blend two adjacent INCR counters weighted by elapsed fraction. A 5-10% overshoot in high-concurrency bursts is acceptable and should be stated in the NFRs.
• Sliding window log is more accurate but stores one sorted set entry per request. Use it only for billing-grade quota enforcement where exact limits are contractually guaranteed.
• Use a Lua script on Redis to make the window check and INCR fully atomic in one round-trip. Use EVALSHA (not EVAL) to avoid resending the script body on every request.
• Use curly-brace key tagging (rl:{api_key}:current and rl:{api_key}:prev) so both window keys always land on the same Redis Cluster shard. Lua scripts in Redis Cluster can only touch keys on one shard.
• Identity resolution priority: API key first (most specific, carries tier), user ID second (authenticated session), IP third (anonymous, tightest limit). Never downgrade to IP when a higher-priority identity is present.
• Cache rules in memory on each gateway node with a 60-second TTL. A rule lookup is an O(1) hash map read, not a network call. Zero added latency per request for rule resolution.
• Fail-open, never fail-closed. When Redis is unavailable, a per-node circuit breaker trips and the gateway passes traffic through a local emergency limiter set to 10x the normal limit. Service stays up; rate limit accuracy degrades temporarily.
• Redis Sentinel provides HA: 1 primary and 2 replicas per shard, with Sentinel promoting a replica in under 30 seconds on primary failure. This minimizes the time the circuit breaker spends in the OPEN state.
• Emit X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset on every response including successful ones. Well-behaved clients use these to self-throttle before hitting the limit.
• For security-critical key revocations, add a pub/sub invalidation channel to push immediate cache evictions to all gateway nodes rather than waiting for the 60-second TTL refresh.

Reliability, security, and operations

Reliability

• Use Redis Cluster with replicas and automatic failover, but keep the Redis client timeout below the request latency budget. A replica failover must not turn into a fleet-wide request queue.
• Treat counter state as expendable. If Redis loses a window, the system may temporarily allow more traffic, but it must not reject all application traffic or block gateway threads.
• Keep the global default rule locally available so a cache miss or Rules Service outage still has a bounded policy. Alert when the circuit breaker opens or rule propagation exceeds its target.

Security

• Prefer API keys or authenticated user IDs over IPs. Only trust forwarding headers added by a known proxy; never accept an arbitrary client-supplied X-Forwarded-For value as the identity.
• Hash or redact API keys in logs and metrics. Protect the rule-management API with strong operator authentication and authorization, and audit changes to high-impact limits.
• Separate rate limiting from WAF and DDoS controls. Add subnet or device-level safeguards for anonymous traffic without allowing an attacker to bypass limits by rotating untrusted identity fields.

Operations

• Measure decision latency, allowed/rejected counts, Redis errors and timeouts, circuit state, local-fallback volume, rule-cache age, and counter-store memory/cardinality.
• Load-test window boundaries, hot keys, Redis failover, partial network loss, rule invalidation, and recovery from an open circuit. Verify the observed overshoot against the stated 5–10% tolerance.
• Sample or aggregate reject logs rather than persisting every request by default. Keep enough dimensions—endpoint, identity type, rule ID, and outcome—to diagnose abuse and capacity problems without logging secrets.

Trade-offs and alternatives

• Fixed window vs. sliding window: Fixed windows are cheapest and easiest to operate but permit boundary bursts. The two-counter sliding approximation improves behavior with bounded memory; a sliding log or token bucket is better when exactness or smooth refill matters.
• Centralized Redis vs. local counters: Redis gives a fleet-wide view and predictable enforcement. Local counters remove a network hop but multiply the effective limit by node count unless traffic is carefully partitioned and failures are accepted.
• Fail-open vs. fail-closed: Fail-open protects application availability and is the right default for traffic shaping. Fail-closed is appropriate only for a security or contractual quota where blocking legitimate traffic is safer than admitting excess traffic.
• Approximate vs. exact accounting: Approximation is a good fit for abuse control. Billing-grade quotas need durable per-event records, stronger atomicity, and a reconciliation path rather than only ephemeral counters.

Follow-up questions

• How would the design enforce one global limit across regions? (Choose a home region or accept regional limits; synchronous cross-region writes usually violate the latency target.)
• How would you apply different costs to expensive endpoints? (Use weighted token consumption or a separate rule cost, and make the Lua update atomic.)
• How do you combine per-user, per-IP, and global service limits? (Evaluate multiple keys in one script or use an ordered set of checks with a clear failure policy.)
• What changes for billing-grade quotas? (Use an append-only usage record and reconciliation; do not rely on a best-effort cache counter.)
• How do you roll out a new rule safely? (Version rules, publish invalidations, measure propagation, and support rollback to the prior version.)

Common mistakes

• Keeping the authoritative counter in each gateway's memory.
• Using separate INCR and EXPIRE commands without handling the crash window.
• Calling a Lua script with keys that hash to different Redis Cluster shards.
• Trusting the leftmost client-provided X-Forwarded-For address.
• Making Redis calls unbounded or failing closed by default.
• Treating rate limiting as a replacement for authentication, authorization, WAF, or DDoS mitigation.

Test Your Understanding

Why does a local counter fail after horizontal scaling? Each node sees only its own share of a client's requests, so the effective limit grows with the number of nodes.

Why use a Lua script? It makes the read, decision, increment, and TTL update one atomic Redis operation.

What is the fixed-window boundary problem? A client can send one full burst at the end of one window and another at the start of the next.

Why are Redis Cluster hash tags needed? All keys touched by one Redis Cluster script must be assigned to the same shard.

What should happen when Redis is unavailable here? Fail open through a bounded local emergency limiter, record the degradation, and alert operators.

Which identity should win when several are present? Use the most specific trusted identity—API key, then authenticated user, then client IP.

Recap

The gateway owns the decision, local caches keep rule lookup cheap, and an atomic Redis script keeps shared counters consistent across nodes. A sliding-window approximation controls boundary bursts while a circuit breaker and local emergency ceiling preserve application availability during Redis failures. The design is intentionally approximate for traffic shaping; exact usage enforcement belongs in a separate durable quota system.

Related concepts

Token bucket, sliding-window counters, API gateways, Redis Cluster and key tagging, circuit breakers, cache invalidation, trusted proxy identity, WAF/DDoS protection, and usage-based quota accounting.