Master Rate Limiting - System Design

Rate limiting: purpose and high-level design

Rate limiting is a system-design technique used to prevent abuse and protect server performance/resources by limiting how many requests are processed within a given time window.

• Example: If a server can safely handle about 100 requests per minute, that’s typically used as a soft guideline rather than a strict hard limit—exceeding it can lead to overheating, degraded performance, or even crashes.
• Placement: A rate limiter is generally placed in front of the server.
  • If requests are within the allowed threshold, the rate limiter allows them.
  • If the threshold is exceeded, it rejects requests.
• Common rejection response: HTTP 429 Too Many Requests.

Algorithms for implementing rate limiting (core ideas)

1) Token Bucket Algorithm

Idea: Maintain a bucket of tokens with a maximum capacity. Tokens are added over time by a refiller.

• A refiller adds tokens at a fixed rate (e.g., 3 tokens/sec).
• For each incoming request:
  • Consume one token if available → request is allowed.
  • If no token is available → request is dropped/rejected (often 429).

Pros

• Easy to implement and widely used (e.g., mentioned: Amazon/Stripe).
• Supports bursty traffic (as long as tokens exist).
• Memory efficient.

Cons

• Requires careful tuning of bucket capacity and refill rate for production use.

---

2) Leaky Bucket Algorithm (“Lee bucket”)

Idea: Use a fixed-capacity queue/buffer. Requests enter quickly, but are drained at a fixed rate.

• Requests are enqueued rapidly.
• The system drains/processes them at a fixed rate controlled by a “leak.”
• If the buffer is full, additional requests are dropped (often 429).

Pros

• Produces smooth outgoing traffic at a stable rate.
• Memory efficient due to a bounded queue size.

Cons

• Bursts can fill the queue with old requests, causing newer ones to be rejected before processing.
• Requires tuning both queue capacity and drain rate.

---

3) Fixed Window Counter Algorithm

Idea: Split time into non-overlapping fixed intervals (e.g., per second/minute) and count requests per interval.

• Keep a counter per window:
  • Increment the counter per request.
  • If the counter exceeds the threshold, reject until the next window begins (quota reset).

Edge/boundary problem (“bug”)

• Traffic spikes near the boundary can effectively allow more than the intended quota across a short overlap between windows.
• Example: processing can exceed the intended rate when requests straddle the end of one window and the start of the next.

Pros

• Simple.
• Resets quota cleanly at window boundaries.
• Often “safe enough” if slight overshoot is acceptable.

Cons

• Can allow burstiness at window edges beyond the configured limit.

---

4) Sliding Window Log Algorithm

Idea: Avoid fixed-window boundary issues by tracking timestamps for requests inside the last N seconds.

For each request:

• Remove timestamps older than the sliding window start.
• Count remaining timestamps within the last N seconds.
• If the count ≤ threshold → accept; otherwise reject.

Key behavior: the window slides continuously by expiring old entries.

Trade-off: requires more bookkeeping (timestamp log) than simple counters.

---

5) Sliding Window Counter Algorithm (Hybrid)

Idea: A compromise between fixed-window counting and sliding behavior.

• Uses fixed windows, but estimates how much of the previous window should contribute based on partial overlap.
• When a request arrives partway through the current fixed window, it accounts for:
  • the remaining fraction of the previous window’s quota (based on overlap),
  • plus the current window’s count.

This aims to be more accurate than fixed-window counters while avoiding the full cost of a complete timestamp-log approach.

Description given: “a sliding window within fixed window sizes.”

Tutorial/analysis structure emphasized in the video

The material follows this progression:

1. Definition and necessity of rate limiting
2. Walkthrough of five main algorithms: 1) Token Bucket 2) Leaky/Leaky Bucket 3) Fixed Window Counter 4) Sliding Window Log 5) Sliding Window Counter (hybrid)
3. Highlights:
   • the edge burst problem in fixed windows
   • how sliding windows (log/counter) address it

Main speaker/source

• Primary speaker: the video presenter (introduced as “Hey everyone welcome back…” and continuously explains throughout).
• Secondary reference mentioned: a book/article by “bit by bite go” for rate-limiting concepts (referenced as not sponsored).