Design a Rate Limiter

Step 1: Requirements

Functional:

1. Limit requests per key. A key is whatever identifies the caller: an API key, a user ID, an IP address, or a combination (such as user + endpoint, where an endpoint is one URL path of the API).
2. Support many rules with different limits and time windows: per plan, per endpoint, per region, and global.
3. When a request is over the limit, return HTTP 429 (the status code for "Too Many Requests") with Retry-After and rate-limit headers.
4. Allow rule changes without redeploying (releasing new code for) the services.
5. Optional: soft limits (only warn or write a log, do not block) and per-customer overrides (special limits for one customer).

Non-functional:

• Low latency: add less than 1–2 ms per request (p99, which means 99 out of 100 requests).
• High throughput: more than 100,000 checks per second, and growing.
• Highly available: the limiter must never become the reason the API is down.
• Accurate enough: a small over-allowance (letting a few percent too many through) is acceptable. Big errors are not.
• Distributed: the same limit must apply across many API servers (and work reasonably across regions).
• Observable: you can see who is being limited, and why.

Step 2: Estimation

Assumptions:

• Peak of 100,000 API requests per second (the busiest time), across all servers.
• About 10 million different keys active per day (API keys, users and IPs).
• On average, each request is checked against 2 rules (for example, the plan limit for the key + a limit for the endpoint).

So this means:

• Memory is small. Everything fits in an in-memory store (a database that keeps data in RAM, so it is very fast), such as Redis. Redis is an open-source in-memory data store that keeps keys and values in memory and answers in well under a millisecond.
• Throughput is high. 200,000 operations per second needs a Redis cluster with several shards. A shard is one part of the data, kept on its own node (machine), so the work is shared. One Redis node handles only very roughly 100,000 simple operations per second.
• The latency budget is tight, so we should use as few network round trips as possible (one atomic call per check, or checks sent together in a batch). An atomic call is one that cannot be split or interrupted.

Step 3: API and rule model

The limiter's internal interface (how other parts of the system call it):

check(keys: [ {rule_id, key} ], cost = 1) →   { allowed: bool, limit, remaining, reset_seconds, retry_after_seconds }

Rules as configuration (stored in one central place, and cached, which means copied, on each gateway):

rules:  - id: plan-free    match: { plan: free }    key: api_key    algorithm: token_bucket    capacity: 100          # the biggest burst allowed    refill_per_second: 1.67  # about 100 per minute  - id: plan-pro    match: { plan: pro }    key: api_key    algorithm: token_bucket    capacity: 2000    refill_per_second: 33.3  - id: login-per-ip    match: { route: "POST /login" }    key: client_ip    algorithm: sliding_window_counter    limit: 10    window_seconds: 60    fail_mode: closed      # security-sensitive: block requests if the limiter is down  - id: sms-global    match: { route: "POST /otp/send" }    key: global    algorithm: token_bucket    capacity: 500    refill_per_second: 200  # protects the SMS provider

Responses to clients (post 43):

HTTP/1.1 429 Too Many RequestsRetry-After: 18RateLimit-Limit: 100RateLimit-Remaining: 0RateLimit-Reset: 18

Successful responses should include the RateLimit-* headers too, so clients can slow down before they are blocked. A header is an extra named line of information sent with an HTTP message. Retry-After is a standard HTTP header that tells the client how many seconds to wait. The RateLimit-* names come from an IETF draft (a proposed internet standard that is not final yet) that is still changing, and many APIs use the older X-RateLimit-* names instead.

Step 4: High-level design

Where should it run?

A common design: the API gateway enforces most limits. (An API gateway is the single front door that all API requests pass through.) It calls a shared counter store. Services add business-specific limits ("max 5 OTPs per phone number per hour") where needed.

Step 5: Deep dives

Deep dive 1: Choosing the algorithm per rule

(See post 43 for how each algorithm works.)

• Token bucket for plan limits. A bucket fills with tokens at a steady rate, and each request takes one. It allows short bursts, and the burst size and the rate are easy to explain to customers.
• Sliding window counter for abuse limits like login attempts. It counts requests in the last N seconds. It is smooth and cheap, and it avoids the problem where a caller sends a full burst at the end of one window and another at the start of the next.
• Leaky bucket / global token bucket (a leaky bucket is a queue that lets requests out at one fixed speed, like water dripping from a small hole) for protecting downstream systems (SMS and payment providers). They send requests on at a steady rate.
• Concurrency limits (how many requests per key are running at the same moment) for expensive endpoints like exports and reports. These limit how many at once, not how many per minute.

Deep dive 2: Atomic counting in Redis

Here is the classic race condition (two things happen at the same time and clash). Two gateway nodes read "99 of 100", and both allow the request. That makes 101. Fix it with atomic operations:

• Fixed window: INCR + EXPIRE. INCR is a Redis command that adds 1 to a counter in one atomic step. EXPIRE tells Redis to delete the key after some time.
• Token bucket or sliding window: a small Lua script (a short program that runs inside Redis) that reads, updates and returns the decision in one atomic step (post 43 has an example). Redis runs scripts one at a time, so there are no races.

Use fewer round trips:

• Check several rules in one script call, or pipeline them (send many commands in one go and read all the answers together).
• Keep keys for the same user on the same Redis shard using hash tags. Redis only hashes the part inside the curly braces to choose the shard. For example, rl:{api_key_123}:plan and rl:{api_key_123}:route land on the same shard, so a single script can update them together in Redis Cluster.

Key names and expiry: (TTL means time to live, the time after which Redis deletes a key.)

rl:{<key>}:<rule_id>          e.g.  rl:{ak_9f2c}:plan-proTTL ≈ time for the bucket to refill fully (or window × 2) → keys that nobody uses expire on their own

Deep dive 3: Performance, local caching and batching

A Redis call for every request adds a network round trip. This is typically well under 1 ms inside the same zone. Ways to make it faster:

• Local rule cache: rules rarely change, so each gateway keeps them in its own memory and reloads them every few seconds (or when it receives a push message).
• Local "definitely blocked" cache: once a key is over its limit, remember "blocked until time T" locally, and reject more requests from it without calling Redis. This helps a lot during attacks.
• Local pre-allocation (token leasing): for keys with very many requests, a gateway can reserve a batch of tokens (say 50) from Redis and spend them locally. It talks to Redis again when they run out. There are fewer Redis calls, but the count is a little less accurate.
• Approximate local limiting for extreme scale: each of N gateways enforces about limit / N locally and syncs from time to time. It is very fast, but less accurate when traffic is not spread evenly across the gateways.

Deep dive 4: Failure handling

What happens if Redis is slow or down?

• Use a short timeout (for example, 5–20 ms; a timeout is the longest you wait for an answer) so the limiter never adds a big delay (post 41).
• Circuit breaker around Redis (post 42). This is a switch that stops calls to a service that keeps failing. If Redis is failing, skip the calls for a while.
• Fail open or fail closed, per rule:
  • Fail open (allow the traffic) for general API plan limits. Availability matters more, and this is usually the right default.
  • Fail closed (block the traffic) for security-critical rules like login, OTP and password reset, where letting attackers through is worse. Or fall back to local limits on each node, which still give rough protection.
• Redis high availability: replicas (copies) plus automatic failover (a spare takes over when the main node dies). Use Redis Cluster (Redis split into shards that fail over by themselves), Sentinel (a helper program that watches Redis and promotes a replica when the main node dies) or a managed service (a cloud company runs Redis for you). Losing some counters during a failover is acceptable, because the limits just start again for a short time.

The limiter must never take the API down. Load-test it (send it a lot of test traffic), and practise what happens when it fails (post 40).

Deep dive 5: Multiple regions

If the API runs in India, Europe and the US, where do counters live?

• Per-region counters (the common choice): each region enforces limits with its own Redis. It is fast and simple. A client that uses several regions at once could get up to about N times the limit (N is the number of regions). Reduce this by giving each region a share of the limit, or by sending each customer to one home region.
• Global counters in one region: accurate, but they add delay between regions (100 ms or more) to every request. This is usually not acceptable.
• Async sync between regions (for example CRDT-style counters, special counters that can be merged without conflicts, post 28). The regions share their usage every few seconds. The result becomes accurate after a short time (eventually accurate). It is a good middle choice for strict enterprise quotas.

Deep dive 6: Rules management

• Store rules in a database or a Git repository (reviewed like code), with a small admin page for support teams.
• Send the rules out by letting gateways poll (ask for updates) every few seconds, or by pushing updates to them (for example, through a pub/sub channel, where subscribers get messages that a publisher sends).
• Validate (check) rules before you apply them. Also support dry-run / shadow mode: write "would have blocked" to the log without blocking, so you can test a new rule safely.
• Support per-customer overrides ("customer X gets 10 times the limit on their launch day"), with an end date.

Deep dive 7: Monitoring

Track:

• checks per second and limiter latency (p50 is the typical request, p99 is the slow end),
• blocked requests by rule, key, plan and endpoint (top offenders),
• Redis health (latency, memory, errors), plus fail-open / fail-closed events,
• customer impact: are paying customers being limited when they should not be? That is a sign that you should change the plans or rules.

Send an alert when blocked requests suddenly jump (it may be an attack, or a bad rule) and when the limiter has errors.

Wrap-up

• Key decisions: enforce at the API gateway with Redis Cluster counters; atomic Lua scripts; token bucket for plans, sliding window for abuse, global buckets for fragile downstreams; rules as cached config; 429 + headers.
• Trade-offs: per-region counters (fast, slightly too generous) or global accuracy; fail open for availability or fail closed for security; local shortcuts for speed or exact counts.
• Next steps: adaptive limits that change with the health of the backend (see load shedding, post 44), usage dashboards for each customer, and a link to billing.