Why simulate time instead of using real time.sleep()?

Because the interesting behavior here depends on exact elapsed time (1 second, 0.2 seconds apart), and a real clock introduces timing noise that would make the printed output slightly different on every run. Passing `now` in as an argument makes the limiter's behavior fully deterministic and testable, which is also how production rate limiters are usually unit-tested.

Is the fixed-window bug in this lesson a real bug people hit in production?

Yes — it's one of the most commonly cited rate-limiter mistakes, precisely because a naive per-second or per-minute counter reset is the first thing most people implement. It doesn't show up in normal traffic spread evenly across a window; it only appears when requests happen to cluster right at a window boundary, doubling the effective limit for that instant.

Which algorithm would a real system actually use?

Token bucket is common for allowing controlled bursts (a user can spend a saved-up allowance quickly, then waits for it to refill) — many API gateways (AWS API Gateway, Stripe's public docs) describe token-bucket-shaped limits. Sliding window log is exact but costs more memory (one timestamp per request in the window); a sliding window *counter* (weighted average of two adjacent fixed windows) is a common middle ground production systems use instead of a full log.

Does token bucket have the same boundary problem as fixed window?

No — token bucket has no window boundaries to cluster around at all. Its allowance refills continuously based on elapsed time, so there's no instant where the count resets to zero and lets a second burst through immediately after the first.

Rate Limiting: Token Bucket and the Fixed-Window Boundary Bug

A token bucket lets a burst through and then throttles once it’s spent; a naive fixed window can let exactly double its stated limit through if requests land on either side of a reset.

Token bucket: burst absorption, then real throttling

class TokenBucket:
    def __init__(self, capacity, refill_rate_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate_per_sec
        self.last_refill = 0.0

    def _refill(self, now):
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

    def allow(self, now):
        self._refill(now)
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=5, refill_rate_per_sec=1)

# A burst of 8 requests arriving at t=0 (simulated clock, not real sleep)
print("Burst of 8 requests at t=0:")
for i in range(8):
    result = bucket.allow(now=0.0)
    print(f"  request {i + 1}: {'accepted' if result else 'REJECTED'} (tokens left: {bucket.tokens:.1f})")

print()
print("After waiting 3 simulated seconds (3 tokens refill):")
for i in range(4):
    result = bucket.allow(now=3.0)
    print(f"  request {i + 1}: {'accepted' if result else 'REJECTED'} (tokens left: {bucket.tokens:.1f})")

$ python token_bucket.py
Burst of 8 requests at t=0:
  request 1: accepted (tokens left: 4.0)
  request 2: accepted (tokens left: 3.0)
  request 3: accepted (tokens left: 2.0)
  request 4: accepted (tokens left: 1.0)
  request 5: accepted (tokens left: 0.0)
  request 6: REJECTED (tokens left: 0.0)
  request 7: REJECTED (tokens left: 0.0)
  request 8: REJECTED (tokens left: 0.0)

After waiting 3 simulated seconds (3 tokens refill):
  request 1: accepted (tokens left: 2.0)
  request 2: accepted (tokens left: 1.0)
  request 3: accepted (tokens left: 0.0)
  request 4: REJECTED (tokens left: 0.0)

The first 5 of 8 requests succeed immediately — that’s the whole starting bucket, spent as a burst, not spread out. The remaining 3 are rejected outright. Three simulated seconds later, exactly 3 tokens have refilled (at 1/sec), so exactly 3 of the next 4 requests succeed.

The fixed-window boundary bug, and why sliding window avoids it

import math

class FixedWindowLimiter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.window_start = None
        self.count = 0

    def allow(self, now):
        window = math.floor(now / self.window_size)
        if window != self.window_start:
            self.window_start = window
            self.count = 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

class SlidingWindowLog:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.timestamps = []

    def allow(self, now):
        cutoff = now - self.window_size
        self.timestamps = [t for t in self.timestamps if t > cutoff]
        if len(self.timestamps) < self.limit:
            self.timestamps.append(now)
            return True
        return False

# 5 requests/second limit. Send 5 requests right at the end of window 1 (t=0.9)
# and 5 more right at the start of window 2 (t=1.1) -- 0.2s apart in real time.
fixed = FixedWindowLimiter(limit=5, window_size=1.0)
print("Fixed window (limit 5/sec), 5 requests at t=0.9 then 5 more at t=1.1:")
accepted = 0
for t in [0.9] * 5 + [1.1] * 5:
    if fixed.allow(t):
        accepted += 1
print(f"  accepted: {accepted}/10 requests within a 0.2s real-time span")

sliding = SlidingWindowLog(limit=5, window_size=1.0)
print()
print("Sliding window (limit 5/sec), same request timing:")
accepted = 0
for t in [0.9] * 5 + [1.1] * 5:
    if sliding.allow(t):
        accepted += 1
print(f"  accepted: {accepted}/10 requests within a 0.2s real-time span")

$ python fixed_vs_sliding.py
Fixed window (limit 5/sec), 5 requests at t=0.9 then 5 more at t=1.1:
  accepted: 10/10 requests within a 0.2s real-time span

Sliding window (limit 5/sec), same request timing:
  accepted: 5/10 requests within a 0.2s real-time span

The fixed window resets its counter the instant the clock crosses from window 0 into window 1, so 5 requests just before the boundary and 5 more just after both see an empty counter — 10 requests, double the stated limit, in a 0.2-second real span. The sliding window has no reset instant at all; it always looks back exactly one second from now, so it correctly counts all 10 requests as landing in the same real time span and rejects half of them.

Practice

1. Compare recovery speed at two different refill rates after draining the bucket.

class TokenBucket:
    def __init__(self, capacity, refill_rate_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate_per_sec
        self.last_refill = 0.0

    def _refill(self, now):
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

    def allow(self, now):
        self._refill(now)
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

for rate in [1, 5]:
    bucket = TokenBucket(capacity=5, refill_rate_per_sec=rate)
    for i in range(5):
        bucket.allow(now=0.0)  # drain the bucket
    result = bucket.allow(now=1.0)
    print(f"refill_rate={rate}/s: after waiting 1s, request {'accepted' if result else 'REJECTED'} (tokens: {bucket.tokens:.1f})")

$ python refill_rate_comparison.py
refill_rate=1/s: after waiting 1s, request accepted (tokens: 0.0)
refill_rate=5/s: after waiting 1s, request accepted (tokens: 4.0)

Both accept the request, but the 5/s bucket has 4 tokens left over afterward while the 1/s bucket has exactly 0 — the refill rate controls sustained throughput, not just whether a single request gets through.

2. Set a large capacity with a slow refill rate, and see burst allowance and sustained rate behave as two separate limits.

class TokenBucket:
    def __init__(self, capacity, refill_rate_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate_per_sec
        self.last_refill = 0.0

    def _refill(self, now):
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

    def allow(self, now):
        self._refill(now)
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

# High burst capacity, low sustained rate
bucket = TokenBucket(capacity=10, refill_rate_per_sec=2)

print("Initial burst of 10 at t=0:")
accepted = sum(1 for _ in range(10) if bucket.allow(now=0.0))
print(f"  accepted: {accepted}/10")

print("Immediately try 5 more at t=0 (bucket now empty):")
accepted = sum(1 for _ in range(5) if bucket.allow(now=0.0))
print(f"  accepted: {accepted}/5")

print("Try 5 more after waiting 1 simulated second (2 tokens refilled):")
accepted = sum(1 for _ in range(5) if bucket.allow(now=1.0))
print(f"  accepted: {accepted}/5")

$ python burst_vs_sustained.py
Initial burst of 10 at t=0:
  accepted: 10/10
Immediately try 5 more at t=0 (bucket now empty):
  accepted: 0/5
Try 5 more after waiting 1 simulated second (2 tokens refilled):
  accepted: 2/5

capacity and refill_rate are independent knobs — a large capacity allows a generous one-time burst, while the refill rate alone governs how fast the bucket earns back capacity for the next one, regardless of how big that first burst was.

3. Fill a sliding window to its limit, confirm the next request is rejected, then confirm it's accepted once the oldest entry ages out.

class SlidingWindowLog:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.timestamps = []

    def allow(self, now):
        cutoff = now - self.window_size
        self.timestamps = [t for t in self.timestamps if t > cutoff]
        if len(self.timestamps) < self.limit:
            self.timestamps.append(now)
            return True
        return False

sliding = SlidingWindowLog(limit=3, window_size=1.0)

for t in [0.0, 0.1, 0.2]:
    result = sliding.allow(t)
    print(f"t={t}: {'accepted' if result else 'REJECTED'}")

result = sliding.allow(0.3)
print(f"t=0.3: {'accepted' if result else 'REJECTED'} (window full of requests from 0.0-0.2)")

result = sliding.allow(1.05)
print(f"t=1.05: {'accepted' if result else 'REJECTED'} (t=0.0 has aged out of the 1-second window)")

$ python sliding_window_aging.py
t=0.0: accepted
t=0.1: accepted
t=0.2: accepted
t=0.3: REJECTED (window full of requests from 0.0-0.2)
t=1.05: accepted (t=0.0 has aged out of the 1-second window)

By t=1.05, the cutoff is 0.05 — t=0.0 no longer survives the t > cutoff filter, but 0.1 and 0.2 still do, leaving room for exactly one more request before the window fills again.

4. Spread the same 10 requests evenly across 2 full seconds instead of clustering them at the boundary, and confirm fixed window behaves correctly.

import math

class FixedWindowLimiter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.window_start = None
        self.count = 0

    def allow(self, now):
        window = math.floor(now / self.window_size)
        if window != self.window_start:
            self.window_start = window
            self.count = 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

fixed = FixedWindowLimiter(limit=5, window_size=1.0)
# 10 requests spread evenly across 2 full seconds, not clustered at a boundary
timestamps = [0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8]
accepted = sum(1 for t in timestamps if fixed.allow(t))
print(f"10 requests spread across 2 full seconds (0.2s apart): {accepted}/10 accepted")

$ python fixed_window_fair_case.py
10 requests spread across 2 full seconds (0.2s apart): 10/10 accepted

All 10 are accepted here, correctly — 5 land in window [0, 1) and 5 in window [1, 2), each exactly at the limit. Fixed window isn’t broken in general; it’s specifically the clustering right at a boundary crossing (the main example above) that lets it double its stated limit.

Token bucket: burst absorption, then real throttling

The fixed-window boundary bug, and why sliding window avoids it

Practice

Frequently Asked Questions