Rate Limiter

• 1M registered API keys or clients.
• 100K clients are concurrently active during a busy minute.
• Average active client rate is 10 requests per second, so steady load is about 1M limiter checks per second.
• Peak traffic is 3x steady load, so design for about 3M limiter checks per second.
• Most rules use token bucket or sliding window counter with one compact state record per active key and endpoint.
• A small set of sensitive endpoints use sliding window log for exactness.

Steady limiter checks: 100K active clients x 10 requests per second = 1M checks per second. Peak target: 1M x 3 = 3M checks per second.

Compact counter memory: if a fixed window, sliding counter, or token bucket state costs roughly 200 bytes after Redis object overhead and key name overhead, then 1M active composite keys cost about 200 MB. With 5M active composite keys across endpoint specific rules, the counter store is about 1 GB before replication. With one replica, budget roughly 2 GB plus overhead.

Sliding window log memory is much larger because it stores request events. At 1M requests per second and a 60 second window, there are 60M timestamp entries. At roughly 80 to 120 bytes per sorted set entry, that is about 4.8 GB to 7.2 GB for one minute of history, before replication. This is why exact sliding logs should be reserved for lower volume or high value rules.

Throughput sizing is usually driven by Redis script evaluations. If one primary shard handles 50K to 100K atomic checks per second with healthy p99 latency, a 3M QPS peak needs 30 to 60 primary shards plus replicas, careful client pooling, and key distribution that avoids hot shards.

Create an index on scope, status, priority for fast rule selection. Add indexes on endpoint_pattern and key_pattern if queries frequently filter by them in the admin UI. Enforce uniqueness on a normalized tuple such as scope, key pattern, endpoint pattern, algorithm, and active version to prevent ambiguous duplicate rules.

Rule lookup should be cached in gateways or a config service because every request cannot query SQL. Gateways should subscribe to rule version changes and fall back to the last known good rule set if the config service is unavailable.

Rules may reference tenants, product tiers, or API products in other domain tables, but the limiter should denormalize the selectors it needs for fast evaluation. Audit tables can store rule changes, actor identity, reason, and previous values for compliance.

Redis data structures are the core counter store:

• Strings with INCR and EXPIRE for fixed window counters. This is simple and fast, but has the boundary burst problem.
• Sorted sets for sliding window log. Store request timestamps as scores, remove old entries, count remaining entries, and add the new event if allowed. This is exact but memory heavy.
• Hashes or compact strings for token bucket and leaky bucket state, storing fields such as token count, last refill time, or next allowed time.
• Lua scripts combine read, compute, write, and expire into one atomic operation so concurrent requests across many gateways do not race.

For very large deployments, shard Redis keys by identity or tenant. Use hash tags only when multiple keys must be co-located for a single script.

Fixed window is the simplest algorithm. For a rule like 1000 requests per minute, compute the current window id from the timestamp, then increment a Redis key such as rule plus identity plus minute. If the incremented count is at or below the limit, allow; otherwise deny. The key expires slightly after the window ends.

Its strength is operational simplicity: one counter key, one atomic increment, one expiry, tiny memory footprint, and easy Retry-After calculation. It is a good default for low risk endpoints, coarse abuse protection, and rules where exact rolling behavior is not required.

The classic weakness is the boundary burst problem. A client can send 1000 requests in the last second of minute N and 1000 more in the first second of minute N plus 1, effectively sending 2000 requests in about two seconds while still respecting 1000 per calendar minute. Mitigations include smaller sub windows, sliding window counter, token bucket, or lowering the limit to account for burst risk.

Sliding window log is the most accurate rolling window approach. Store each accepted request timestamp in a Redis sorted set. On each request, remove entries older than now minus window, count the remaining entries, and allow only if the count is below the limit. This exactly answers whether the client made fewer than N requests in the last W seconds.

The downside is memory and CPU. A hot key with 10K requests per second and a 60 second window stores up to 600K entries for one client and one rule. Cleanup and counting are also more expensive than a scalar increment. Use this when correctness is worth the cost, such as write APIs, fraud sensitive operations, or low volume high value endpoints.

Sliding window counter is the common compromise. Keep counts for the current fixed window and the previous fixed window, then weight the previous count by how much of it overlaps the current rolling window. For example, estimated usage equals current count plus previous count times remaining window fraction. It removes most boundary burst behavior while storing only a few counters. It is approximate because it assumes previous window traffic was evenly distributed.

Token bucket is often the best interview default for public APIs because it naturally supports bursts while enforcing a long term average rate. Each key has a bucket with capacity B and refill rate R tokens per second. A request costs C tokens. On each check, refill based on elapsed time, cap tokens at B, then allow only if at least C tokens remain.

This model maps well to product tiers. A free plan might refill at 5 requests per second with burst capacity 20. An enterprise plan might refill at 500 requests per second with burst capacity 5000. The bucket lets clients batch briefly without being punished, but sustained traffic above the refill rate eventually drains the bucket.

In Redis, store current tokens and last refill time. Use Redis server time inside the Lua script or pass gateway time only if clock skew is bounded. The script should compute remaining tokens, update state, set an expiry based on the time needed to fully refill, and return retry time when denied. Token bucket is less exact than a sliding log for a strict per minute quota, but it is much more memory efficient and user friendly.

Leaky bucket smooths traffic rather than merely capping it. Conceptually, requests enter a bucket and leak out at a constant rate. If the bucket backlog exceeds capacity, new requests are rejected. In synchronous API limiting, it is often implemented as a virtual schedule: keep the next allowed time, move it forward by one interval for each accepted request, and reject if the next allowed time drifts too far into the future.

This is useful when the backend cannot tolerate bursts, such as an expensive downstream dependency, a legacy database, or an email sending provider. It produces smoother traffic than token bucket, but it can feel harsher to clients because even legitimate bursts may be denied or queued.

The tradeoff is latency versus rejection. If the limiter queues requests, it protects the backend but increases user visible latency and needs queue management. If it rejects instead, it is simpler and bounded, but clients must retry. In interviews, describe leaky bucket as an optional algorithm for smoothing, not as the only global limiter.

A single node in-memory counter is correct only when all traffic for a key is routed to that node, which is rarely true after horizontal scaling. If ten gateways each enforce 100 requests per minute locally, the true global allowance becomes up to 1000 requests per minute. Sticky routing can reduce this, but it complicates failover and load balancing.

Centralized Redis fixes the core coordination problem by making the counter update atomic and shared. Do not implement the check as separate get, compare, and set calls because concurrent requests will race. Use one Lua script or server side function that performs cleanup, counting, incrementing, expiry, and retry time calculation atomically.

For Redis Cluster, every script can only atomically operate on keys in one hash slot. Design keys so a single rate limit decision uses one key, or use hash tags to co-locate the small set of keys needed by the same script. Avoid cross slot multi key operations on the hot path.

Time is part of every rate limiting algorithm. Fixed windows need a window boundary, sliding logs need timestamp scores, token buckets need elapsed refill time, and leaky buckets need a next allowed time. If gateway clocks differ by hundreds of milliseconds, edge cases become inconsistent. Prefer Redis server time for centralized algorithms or ensure NTP and monotonic time discipline for local fallback.

The failure policy must be explicit. Fail-open allows traffic when Redis is slow or unavailable, preserving availability but risking abuse and cost spikes. Fail-closed blocks traffic when the limiter cannot verify allowance, protecting critical backends but potentially causing a customer visible outage. A strong design supports per rule policy: fail-open for read traffic, fail-closed or low local emergency limits for payments, login attempts, and expensive write APIs.

Multi-region systems add another tradeoff. A single global Redis region gives stronger limits but adds latency and creates a blast radius. Local regional buckets give low latency and availability but can overshoot the global limit. A practical compromise is to allocate regional budgets from a global quota and reconcile usage asynchronously.

Alternatives include application level quotas checked in service code, CDN or WAF level coarse throttling, client side SDK throttling, queue based admission control, and downstream concurrency limits. These are complementary. CDN throttling is excellent for unauthenticated volumetric abuse, while API key aware limits usually require gateway authentication and a shared counter store.

Do not use a distributed rate limiter as the only protection for CPU intensive jobs, long running workflows, or scarce backend resources. Those need admission control, queues, per worker concurrency limits, cancellation, and capacity planning. Also avoid exact global rate limits when the product only needs approximate fairness; the latency and availability cost may not be justified.