Rate Limiting Algorithms

Introduction: The “Noisy Neighbor”

Imagine you have a free API. One user writes a script that accidentally sends 10,000 requests per second. Your database crashes, and all your other users are blocked.

Rate Limiting is the practice of restricting the number of requests a user (or service) can make in a given timeframe. It is the primary defense against DDoS attacks, brute-force login attempts, and runaway scripts.

What Problem does it solve?

• Input: A stream of requests from various users.
• Output: Accept or Reject (429 Too Many Requests).
• The Promise: Fairness (one user can’t hog all resources) and Stability (the system stays alive even under heavy load).

Core Algorithms

1. Token Bucket

• Logic: A bucket holds “Tokens.” Each request consumes one token. Tokens are added back at a fixed rate (e.g., 10 tokens/sec). If the bucket is empty, requests are rejected.
• Pros: Allows for Bursts. If a user hasn’t made requests for a while, they can send a few requests quickly until the bucket is empty.
• Use Case: Most popular; used by AWS, Stripe, and Spring Cloud.

2. Leaky Bucket

• Logic: Imagine a bucket with a small hole at the bottom. Requests enter at any speed, but they “leak” out at a fixed, constant rate. If the bucket overflows, requests are dropped.
• Pros: Perfectly smooths out traffic. No bursts allowed.
• Use Case: Traffic shaping in network routers.

3. Fixed Window Counter

• Logic: Divide time into windows (e.g., 1 minute). Each window has a counter.
• Cons: “Edge Problem.” If a user sends 100 requests at 00:59 and 100 at 01:01, they effectively sent 200 requests in 2 seconds, even if the limit is 100/min.

4. Sliding Window Log / Counter

• Logic: Tracks the exact timestamp of each request.
• Pros: Most accurate; no edge problems.
• Cons: High memory usage (must store every timestamp).

Typical Business Scenarios

• ✅ API Monetization: Limiting a “Free Tier” to 100 calls/day and a “Pro Tier” to 10,000 calls/day.
• ✅ Login Protection: Preventing hackers from trying 1,000 passwords per second (Brute Force).
• ✅ External Service Protection: If you use OpenAI’s API, you limit your own outgoing requests to match their quota.

Performance & Complexity

• Time: $O(1)$ for Token Bucket (using a simple timestamp calculation).
• Space: $O(1)$ per user for Token/Leaky bucket.

Summary

“Rate Limiting is the ‘Safety Valve’ for your API. Token Buckets allow for bursts of energy, while Leaky Buckets ensure a perfectly smooth and predictable flow of work.”