Think of a highway toll system. A single toll booth at the entrance of a major city works perfectly when traffic is light, but the moment you scale to millions of vehicles per day, that single booth becomes the chokepoint that causes the very congestion it was meant to regulate. You build more lanes, distribute the toll collection, and now each booth processes its slice of traffic independently. But here is the twist: you still need to enforce a per-vehicle daily limit across all booths, not just at one. That is the core problem of distributed rate limiting at scale.

The naive implementation of a rate limiter places a single Redis instance or a database table as the sole arbiter of whether a request is allowed. Every API gateway node, before forwarding a request, asks the central coordinator: “has this user exceeded their limit?” At modest scale, this works. At 100+ gateway nodes each fielding thousands of requests per second, the coordinator becomes a serialization bottleneck, a single point of failure, and an added 5-15ms of latency on every single request path. A 10ms overhead multiplied across millions of requests per day is not an engineering inconvenience, it is a product-level SLA violation that triggers escalations and on-call pages.

The deeper challenge is the local vs global limit tradeoff. Each gateway node can maintain an in-process counter that is blindingly fast - a simple atomic increment in memory costs nanoseconds. But if node A has seen 900 requests from user X while node B has seen 900 requests from the same user, and the global limit is 1000 requests per minute, you are already at 1800 - double the limit - with no node aware that a violation is occurring. The opposite extreme, serializing every check through a single global store, sacrifices the latency guarantees that make an API gateway competitive. The winning design lives in the middle: local approximation with periodic global synchronization and a shared authoritative store for the final guard.

We need to solve for sub-millisecond enforcement latency under normal conditions, eventual global consistency within a bounded error window, graceful degradation when the shared store is unreachable, and operational simplicity that allows limit overrides without a service restart simultaneously.

Requirements and Constraints

Functional Requirements

• Enforce per-user request rate limits (e.g., 1000 requests per minute per user)
• Enforce per-tenant (organization) rate limits independently of per-user limits
• Support multiple limit tiers (free, pro, enterprise) with different quotas
• Provide a limit override API to temporarily raise or lower limits for specific users or tenants
• Return 429 Too Many Requests with a Retry-After header when limits are exceeded
• Track and expose current usage metrics per user and tenant

Non-Functional Requirements

• Enforcement decision latency: under 1ms at the 99th percentile (p99)
• Global consistency lag: at most 500ms between a limit being hit on one node and being enforced on all nodes
• Throughput: support 500,000 requests per second across the gateway fleet
• Availability: rate limiter must degrade gracefully (fail open) if the Redis cluster is unreachable
• Accuracy: allow at most 5% overage above configured limits during normal operation
• Durability: limit configurations survive gateway node restarts and Redis failovers

Constraints

• No single point of failure in the enforcement path
• Redis Cluster with 6 nodes (3 primary, 3 replica) - no standalone Redis
• Gateway fleet may scale from 20 to 200+ nodes dynamically via autoscaling
• Each gateway node has 512MB memory budget for rate limiting state
• Limit configuration changes must propagate within 30 seconds

High-Level Architecture

The system is composed of four major layers working in concert. The API Gateway Fleet runs 100+ stateless nodes, each with a Local Counter Layer holding an in-process approximate count. The Redis Rate Store acts as the globally authoritative counter backend, sharded across a Redis Cluster. The Config Service stores rate limit configurations and serves them to gateway nodes via a push/pull mechanism. Finally, the Gossip Synchronizer runs as a lightweight sidecar on each gateway node, periodically broadcasting local counts to peers and reconciling the global view.

When a request arrives at any gateway node, the decision sequence is: check the local counter first (nanoseconds), then if the local count is within the pre-allocated local budget, allow immediately. If the local budget is exhausted, or if a random sampling roll triggers a sync, the node performs an atomic Redis operation to check and increment the global counter. Redis responds with the current global count, and the node makes the final allow-or-deny decision. The gossip layer runs asynchronously, sharing aggregate counts between nodes every 100ms to rebalance local budgets without touching Redis.

Component Deep Dives

The Local Counter Layer

The Local Counter Layer’s job is to answer the majority of rate limit checks in under 100 nanoseconds without touching the network.

Each gateway node maintains an in-process hash map keyed by (user_id, window_start_epoch_second). The value is a 64-bit atomic counter. When a request arrives, the node increments the counter and compares it against the node’s local budget, which is a fraction of the global limit allocated to this specific node. The node budget is calculated as global_limit / num_active_nodes * local_budget_fraction, where local_budget_fraction defaults to 0.7 - meaning each node can pre-authorize 70% of its fair share before requiring a Redis round-trip.

The tricky design decision is what happens when the local budget is exhausted. A hard stop here would cause false negatives: a user who has consumed their node’s local budget but has ample global quota remaining would be incorrectly rejected. Instead, exhausting the local budget triggers a Redis sync, which returns the current global count and optionally re-allocates a fresh local budget from the remaining global headroom.