Designing a Distributed Rate Limiter

Rate limiting is a critical mechanism for protecting services from abuse, cascading failures, and resource exhaustion. In a distributed environment, the challenge is enforcing limits consistently across multiple server instances.

1. Token Bucket Algorithm

The Token Bucket algorithm is a widely used rate-limiting strategy:

1. A bucket has a maximum capacity of $N$ tokens.
2. Tokens are added to the bucket at a constant rate of $R$ tokens per second.
3. Each incoming request consumes a single token.
4. If the bucket is empty, the request is rejected with a 429 Too Many Requests status code.

This algorithm allows for handling sudden bursts of traffic while enforcing a strict average limit over time.

2. Distributed Architecture with Redis

In a horizontally scaled application cluster, storing token balances in-memory on individual web servers leads to inconsistency. We solve this by centralizing rate limiting using Redis:

• Redis Keys: Store mapping from client identifiers (e.g., IP address or User ID) to token bucket variables.
• Atomic Updates: Use Redis EVAL with Lua scripts or transactions to read and update token counts atomically, avoiding race conditions under high concurrency.
• Expiration: Set key TTLs (Time To Live) to automatically clean up inactive buckets.

3. Handling Edge Cases

• Race Conditions: Two parallel requests from the same user hit different server nodes. If they query Redis simultaneously, they could both read a balance of 1 and proceed. Utilizing Redis Lua scripts guarantees operation atomicity.
• Multi-Tier Limits: Enforce short-term (e.g. 5 requests per second) and long-term (e.g. 1000 requests per hour) buckets simultaneously to defend against both brute-force spam and continuous scraping.