What is DRL(distributed rate limiter)
DRL decides whether a client (user, IP, or API key) will proceed to origin/application server, using rate limiting counters. Eg: 100 HTTP req/sec. if 101 arrives with in second, 429(too many requests) should be returned to client
Requirements
1. DRL run in multiple regions
Since DRL runs in several regions(US, India etc) atomic counters to be
shared across regions so the limit is enforced for the fleet — not per
machine.
2. System must be scalable: Adding rate-limiter nodes should
not crash the system.
3. Thread-safe: Concurrent checks from many threads/pods must
update counters atomically so two simultaneous requests cannot both
pass when only one token remains.
4. Low-latency: Rate limiting counters are checked hot path so
least latency.
High Level Design
Where the limiter sits. Global LB → Regional LB → AZ LB → Rate Limiter
It sits behind AZ LB
Why RL does not sit behind Global LB?
- The global LB’s job is geo routing and health: steer traffic
to a region, fail over when a region is down.
- Token-bucket check(at RL) needs a nearby Redis round-trip on
every request, if Redis fails it will be worldwide single point of
failure
- Identity check cannot be done at Global level. Customers present
X-API-Key, JWT bearer tokens, or mTLS client certs. TLS
Termination happen on the API Gateway which cannot be placed
before global LB.
Block Diagram
Two regions (US and India). Each region has regional Redis for live token buckets and talks to a shared global Redis (or config store) for rules and tenant metadata.
+--------------------------------+
| Global Load Balancer |
Client -------------------------------->| Geo Routing |
+---------------+----------------+
|
+---------------------------+---------------------------+
| |
v v
+-------------------------+ +-------------------------+
| Regional LB (US) | | Regional LB (India) |
+------------+------------+ +------------+------------+
| |
v v
+--------POD 1 -----+ +-POD2 --+ +-------------- POD ------------+
| API Gateway | | API GW | | API Gateway |
| - SSL Termination | | | | - SSL Termination |
| - Authentication | |------- | | - Authentication |
| - Routing | | - Routing |
| - Rate Limiter | | - Rate Limiter |
+-------------------+ +---------------+---------------+
| |
Read/Update Token Bucket Read/Update Token Bucket
| |
+- Redis Cluster LB -------+ |
|--------------------------| |
| |
--------------------------------------------- v
| |
+---------US POD:6379 ---+ +-- Redis Pod 2 --+ +--------- IN POD:6379 --------+
| Regional Redis(US) runs | | | | |
| - Lua script atomically | | |<------------->| |
+---------------+---------+ +------------------+ | +------------------+-----------+
| | |
v | v
Backend Services | Backend Services
|
|
+-----------------+
| config sync svc |
+-----------------+
/\
Global Config Store (Redis/DB/Etcd)
+---------------------------------+
| - Rate limit policies |
| - API Keys |
| - Tenant quotas |
| - Configuration |
+---------------------------------+
Request flow
A Customer authenticate and send request.
The global load balancer resolves the hostname, routes to least loaded
AZ LB
The AZ LB inside that zone selects a healthy API Gateway pod, which
does SSL Termination.
API GW pod(Does Rate Limiting)
- Terminates TLS if needed
- Validate the API key
- Fetch the tenant rules from regional redis and runs the token-bucket
Lua script
Why Lua with Redis?
Redis embeds a Lua interpreter. Redis guarantees Execute the
entire Lua script as 1 atomic operation.
Redis does not natively support Python, Java, C++, Go inside
the Redis server.
- If tokens remain, the gateway forwards to the correct microservice
and returns the response; if not, it responds with
429 Too Many Requests
Regional Redis vs Global Redis
Usage:
1. Sharding inside the cluster is by hash(rule_id + tenant). This
ensures high write QPS, sub‑ms latency, and thread-safe increments.
When an admin changes a tenant’s limit in its Tenant UI, the update
lands in global Redis/config and fans out to all regional API
gateways;
2. To Enforce Global limits, 100 requests/sec Globally
Tenants logs into US or IN only 100req/sec are allowed. Regional Redis
cannot Enforce this
Suppose tenant wants Entire world 100 requests/sec
Solution-1(Bad): All Regional API GW nodes talk to global
redis. Lead to High latency, Global bottleneck, Lower availability,
Expensive network traffic
US API GW ------\
\
India API GW-----> Global Redis
/
Europe API GW ---/
Solution-2(Good): Distribute regional limits or regional tokens by global allocator
|
|
Sequence Diagram
End-to-end path for one API call through the India region.
%%{init: {'themeVariables': {'fontSize': '13px'}, 'sequence': {'actorMargin': 36, 'messageMargin': 24, 'boxMargin': 8, 'useMaxWidth': true}}}%%
sequenceDiagram
autonumber
actor Customer
box LightBlue Global Edge
participant GLB as Global LB
Geo Routing
participant RLB as Regional LB India
participant AZLB as AZ LB
end
box LightGreen Datacenter
participant GW as API Gateway Pod
SSL · Auth
Rate Limiter
participant RedisLB as Redis Cluster LB
participant RRedis as Regional Redis
Token Bucket
participant API as Backend Services
end
box LightYellow Global Config
participant Sync as Config Sync Svc
participant GStore as Global Config Store
rules · API keys · quotas
end
Customer->>GLB: HTTPS API request
X-API-Key=tenant_acme
Note over GLB: Geo + health only
no rate-limit check
GLB->>RLB: Route to India region
RLB->>AZLB: Route to AZ pod
AZLB->>GW: Forward to gateway pod
GW->>GW: TLS terminate + validate API key
tenant_acme identified
GW->>Sync: refresh rules or cached policy
Sync->>GStore: GET rule:tenant_acme
GStore-->>Sync: rate=100/min, burst=20
Sync-->>GW: rule returned
GW->>RedisLB: EVAL token_bucket.lua
bucket:api:tenant_acme
RedisLB->>RRedis: route to Redis pod
RRedis-->>RedisLB: allowed=true, remaining=17
RedisLB-->>GW: allowed=true, remaining=17
alt tokens remaining
GW->>API: Forward allowed request
API-->>GW: 200 OK + body
GW-->>Customer: 200 OK
X-RateLimit-Remaining: 17
else bucket empty
RRedis-->>RedisLB: allowed=false, retry_after=12s
RedisLB-->>GW: allowed=false, retry_after=12s
GW-->>Customer: 429 Too Many Requests
Retry-After: 12
end
Note over Sync,GStore: Config sync pushes
policy updates to all regions
Algorithms
Fixed Window Counter
Divide time into fixed windows (e.g., 00:00–00:59, 01:00–01:59). Maintain a counter per window. When a request arrives, increment the counter. If the counter exceeds the limit, reject the request. The counter resets at the window boundary.
Window 1 (12:00 - 12:01) Window 2 (12:01 - 12:02)
|-------4 req--------| |-------4 req--------|
| | | | |
drop
Sliding Window
Maintain the sliding window (let suppose 60 seconds). And fixed tokens
are allowed in this window.
Sliding window counts only requests within the last N seconds by
remembering when each request arrived. It never resets abruptly at a
fixed boundary.
Last 60 seconds at 12:01:05: 80 requests
Sliding Window Counter (Approximate Sliding Window)
Approximate sliding window combines two adjacent fixed windows and weights them to approximate the true moving interval.
Window A (11:00 - 11:01): 60 req
Window B (11:01 - 11:02): 30 req
Weighted count ≈ 15 + 30 = 45 requests
Leaky bucket
Leaky bucket releases requests at a steady pace. Incoming requests may queue briefly, but the output rate stays smooth.
Bucket leaks 1 request/sec
Burst of 10 requests → 1 allowed each second until the burst is drained
Token bucket
Each request consumes one token — if none remain, deny immediately.
That matches how clients and gateways behave.
Runs inside atomic Lua script on Redis.
Bucket capacity 10, refill 1 token/sec
Start with 10 tokens. A burst of 10 is allowed immediately, then 1 more
request per second as tokens refill.
# Token bucket state (per rule + subject key)
bucket:{rule_id}:{subject} → {
tokens: FLOAT,
last_refill: TIMESTAMP
}
function allow_request(bucket, now, rate, capacity):
elapsed = now - bucket.last_refill
refill = elapsed * rate
bucket.tokens = min(capacity, bucket.tokens + refill)
bucket.last_refill = now
if bucket.tokens >= 1:
bucket.tokens -= 1
return allowed, bucket.tokens
else:
return denied, 0
# Example:
# capacity=10, rate=1 token/sec
# start with 10 tokens → 10 requests allowed immediately
# then 1 request allowed per second as tokens refill