Rate Limiting Algo — Sliding Window

This piece follows Rate Limiting Algo — Fixed Window. It was originally published on Medium.

#Sliding Window Rate Limiting

After the Fixed Window failure, the lesson was obvious: time boundaries are artificial; traffic is not.

So we looked for something mathematically correct — something that actually enforces “requests in the last N seconds,” not “requests in the same minute on a clock.”

That led us to Sliding Window rate limiting.

#Sliding Window: The Core Idea

Instead of counting requests in rigid, clock-aligned buckets, sliding window rate limiting answers a simpler question:

How many requests has this client made in the last 60 seconds, right now?

No boundaries. No resets. Just continuous time.

There are two ways to implement this.

#1. Sliding Window Log

Correct — and completely impractical

The most accurate approach is also the simplest to explain.

#How it works

• Store the timestamp of every request.
• On each new request:
  • Remove timestamps older than 60 seconds
  • Count remaining timestamps
  • Allow the request only if the count ≤ limit

Mathematically, this is perfect.

#Why Sliding Window Log Explodes

Now put real numbers on it.

Example

• Users: 10 million
• Limit: 100 RPM
• Worst case timestamps stored: 10M × 100 = 1 billion timestamps

That’s a billion list entries sitting in Redis.

At that scale:

• Redis memory explodes
• GC pressure increases
• Latency becomes unpredictable
• Throughput collapses

This is why Sliding Window Log is academically correct but operationally unusable.

Nobody runs this at scale.

#2. Sliding Window Counter

The practical compromise

To fix the explosion problem, we relax precision slightly and introduce buckets.

#How it works

Instead of storing every timestamp:

• Divide the window into smaller fixed buckets
• Count requests per bucket
• Sum buckets to approximate the sliding window

Example

• Window: 60 seconds
• Buckets: 6 × 10 seconds
• Limit: 100 requests

Buckets:

B1: T-60 → T-50
B2: T-50 → T-40
B3: T-40 → T-30
B4: T-30 → T-20
B5: T-20 → T-10
B6: T-10 → T-0

Allow the request if:

B1 + B2 + B3 + B4 + B5 + B6 ≤ 100

#Why Sliding Window Counter Works

• Memory is bounded (fixed number of buckets)
• Redis keys are small and predictable
• No timestamp lists
• O(1) operations per request

This is why sliding window counters are widely used in real systems.

#Where Sliding Window Counter Still Breaks

The compromise introduces a subtle but dangerous flaw: microburst amplification at bucket boundaries.

Let’s walk through it carefully.

#Example: Boundary Burst

Assume the system can safely handle:

100 RPM ≈ 1.67 RPS

Bucket state:

T-60 → T-50 (B1): 0
T-50 → T-40 (B2): 0
T-40 → T-30 (B3): 0
T-30 → T-20 (B4): 0
T-20 → T-10 (B5): 50
T-10 → T-0  (B6): 50

Now imagine:

• User sends 50 requests at second 50
• Then sends 50 requests at second 51

From the algorithm’s perspective:

• Total = 100 → allowed

From the system’s perspective:

• 100 requests arrived in ~2 seconds
• Effective rate ≈ 50 RPS
• That’s ~30× higher than safe capacity

The limit is respected. The system still takes a massive hit.

#The Fundamental Trade-off

Sliding Window Counter:

• Fixes clock-boundary resets
• Controls long-term averages
• Keeps memory and CPU bounded

But it does not smooth traffic.

It enforces how much work is allowed, not how fast it arrives.

That’s why sliding window counters still allow sharp spikes — and why systems that depend on smooth load (DBs, auth, payments) can still fail under microbursts.

#Verdict

• Sliding Window Log — Correct, precise, unusable at scale.
• Sliding Window Counter — Practical, efficient, but burst-blind.

Sliding windows improve fairness and accounting, but they do not protect backend stability under bursty traffic.

And that realisation leads directly to the next algorithm.

The follow-up is Rate Limiting — Token Bucket & Leaky Bucket — token bucket, leaky bucket, and why layering them is what production systems actually do.