Sliding Window Token Bucket Rate Limiter

What you will learn

• Implement the mathematical token bucket rate limiting algorithm in Python
• Model continuous token replenishment using fractional elapsed time
• Enforce tenant-level isolation using client key mapping
• Reject burst over-allocations with clean boolean rate-limiting responses

What you need first

tokens = min(10, 5 + 2.5 * 2); print(tokens)

10.0

elapsed = 1.5; rate = 2.0; print(elapsed * rate)

3.0

d = {}; d.setdefault('client_1', 10); print(d['client_1'])

10

Architecture and data flow

The data

Client API request stream with client ID, request timestamp, and endpoint URL.

Step by step

Read each step, run its code, then check your output against the one shown.

1. 01

   Define TokenBucket class state and parameters

   We begin by establishing the state schema for our TokenBucket rate limiter. The class encapsulates bucket capacity, token refill rate per second, current token balance, and the timestamp of the last recorded evaluation. In distributed API engineering, stateful rate limiters must maintain minimal in-memory footprints while keeping each evaluation a few cheap arithmetic operations. We verify that our constructor properly initializes the bucket with full burst capacity on creation, confirming that attributes match our mathematical model before handling incoming requests. This algorithmic structure guarantees that incoming network bursts are smoothed predictably according to strict mathematical limits without storing a history of past requests.

   PythonStep 1Copy

   class TokenBucket:
       def __init__(self, capacity: int, fill_rate: float, current_time: float = 0.0):
           self.capacity = float(capacity)
           self.fill_rate = float(fill_rate)
           self.tokens = float(capacity)
           self.last_updated = current_time
   
   bucket = TokenBucket(capacity=5, fill_rate=1.0, current_time=100.0)
   print(f"Bucket initialized: Capacity={bucket.capacity} | Tokens={bucket.tokens} | Rate={bucket.fill_rate}/sec")

   Show outputGuess what it prints first

   Bucket initialized: Capacity=5.0 | Tokens=5.0 | Rate=1.0/sec

   Common mistake

   Watch out: Initializing tokens as integers rather than floats causes truncation errors during fractional token replenishment calculations.

   How you will know

   The output confirms that the bucket initializes with 5.0 tokens and a refill rate of 1.0 token per second.

2. 02

   Demonstrate flaws of naive fixed-window resets

   Wrong turn first: this step shows the mistake before the fix

   We demonstrate why naive fixed-window rate counters fail in production gateways. A common beginner approach is to reset a request counter to zero at every whole minute boundary. However, as demonstrated by our simulation, a client can send five requests at minute 0:59 and another five requests at minute 1:01. Within a two-second window, the gateway accepts ten requests, effectively doubling the permitted burst capacity and overwhelming downstream servers during window transition boundaries. Rate limiters must enforce smooth continuous sliding limits.

   PythonStep 2Copy

   def fixed_window_check(time_sec: float, requests_in_window: int, limit: int = 5) -> bool:
       # Resets strictly at window boundaries
       return requests_in_window <= limit
   
   # Client sends 5 requests right before boundary, and 5 right after
   r1 = [fixed_window_check(59.9, i) for i in range(1, 6)]
   r2 = [fixed_window_check(60.1, i) for i in range(1, 6)]
   print(f"Window 1 accepted: {sum(r1)} | Window 2 accepted: {sum(r2)}")
   print(f"Total accepted in 2-second burst: {sum(r1) + sum(r2)} (Allowed limit: 5)")

   Show outputGuess what it prints first

   Window 1 accepted: 5 | Window 2 accepted: 5
   Total accepted in 2-second burst: 10 (Allowed limit: 5)

   Common mistake

   Watch out: Fixed window resets allow boundary bursts that permit double the intended rate limit across consecutive windows.

   How you will know

   The output exposes 10 accepted requests within a 2-second interval, violating the 5-request burst policy.

3. 03

   Implement lazy token replenishment based on elapsed time

   To avoid running background timer threads for thousands of clients, we implement lazy replenishment. When a request arrives, the bucket calculates elapsed time since last_updated, multiplies by fill_rate, and adds the resulting tokens to the existing balance. We enforce a hard ceiling using min(capacity, tokens + added) so that tokens cannot exceed bucket capacity during prolonged idle periods. We inspect token regeneration after two seconds of idle time to verify that elapsed replenishment matches theoretical calculations precisely. This algorithmic structure guarantees that incoming network bursts are smoothed predictably according to strict mathematical limits without storing a history of past requests.

   PythonStep 3Copy

   class TokenBucket:
       def __init__(self, capacity: int, fill_rate: float, current_time: float = 0.0):
           self.capacity = float(capacity)
           self.fill_rate = float(fill_rate)
           self.tokens = float(capacity)
           self.last_updated = current_time
   
       def _replenish(self, now: float) -> None:
           elapsed = now - self.last_updated
           if elapsed > 0:
               added = elapsed * self.fill_rate
               self.tokens = min(self.capacity, self.tokens + added)
               self.last_updated = now
   
   bucket = TokenBucket(capacity=5, fill_rate=1.0, current_time=0.0)
   bucket.tokens = 1.0  # Simulate drained state
   bucket._replenish(now=2.5)
   print(f"Tokens after 2.5s idle: {bucket.tokens:.1f} (Capped at {bucket.capacity})")

   Show outputGuess what it prints first

   Tokens after 2.5s idle: 3.5 (Capped at 5.0)

   Common mistake

   Watch out: Omitting elapsed > 0 checks can cause negative token deductions if clock skew or out-of-order timestamps occur.

   How you will know

   The output confirms that the bucket replenished from 1.0 to 3.5 tokens over 2.5 seconds.

4. 04

   Implement request consumption with atomic decision boolean

   We implement the core consume() method that governs request acceptance or rejection. When a caller invokes consume(tokens=1, now=timestamp), the method first replenishes tokens based on elapsed time. Next, it evaluates whether available tokens are greater than or equal to the requested quantity. If sufficient, it decrements the token balance and returns True; otherwise, it returns False without mutating the token count, preserving state integrity and preventing negative token balances during sudden burst over-allocations. This algorithmic structure guarantees that incoming network bursts are smoothed predictably according to strict mathematical limits without storing a history of past requests.

   PythonStep 4Copy

   class TokenBucket:
       def __init__(self, capacity: int, fill_rate: float, current_time: float = 0.0):
           self.capacity = float(capacity)
           self.fill_rate = float(fill_rate)
           self.tokens = float(capacity)
           self.last_updated = current_time
   
       def consume(self, cost: int = 1, now: float = 0.0) -> bool:
           elapsed = now - self.last_updated
           if elapsed > 0:
               self.tokens = min(self.capacity, self.tokens + elapsed * self.fill_rate)
               self.last_updated = now
   
           if self.tokens >= cost:
               self.tokens -= cost
               return True
           return False
   
   bucket = TokenBucket(capacity=3, fill_rate=1.0, current_time=0.0)
   results = [bucket.consume(1, now=0.0) for _ in range(4)]
   print(f"Initial burst of 4 requests (Capacity 3): {results}")
   print(f"Remaining tokens: {bucket.tokens:.1f}")

   Show outputGuess what it prints first

   Initial burst of 4 requests (Capacity 3): [True, True, True, False]
   Remaining tokens: 0.0

   Common mistake

   Watch out: Decrementing tokens before checking self.tokens >= cost drives balances negative and corrupts subsequent calculations.

   How you will know

   Output shows [True, True, True, False] with 0.0 remaining tokens, rejecting the 4th request.

5. 05

   Simulate multi-tenant rate limiting registry with tenant isolation

   In our final milestone, we build a multi-tenant rate limiter registry that isolates client quotas using a dictionary. Each client IP or API key maps to an independent TokenBucket instance. We simulate a rapid sequence of webhook calls from two distinct clients: an aggressive client attempting a sudden burst of ten requests, and a well-behaved client sending spaced requests. We verify that noisy clients are throttled without degrading service for compliant tenants, proving clean multi-tenant isolation. This algorithmic structure guarantees that incoming network bursts are smoothed predictably according to strict mathematical limits without storing a history of past requests.

   PythonStep 5Copy

   class TokenBucket:
       def __init__(self, capacity: int, fill_rate: float, current_time: float = 0.0):
           self.capacity = float(capacity)
           self.fill_rate = float(fill_rate)
           self.tokens = float(capacity)
           self.last_updated = current_time
   
       def consume(self, cost: int = 1, now: float = 0.0) -> bool:
           elapsed = now - self.last_updated
           if elapsed > 0:
               self.tokens = min(self.capacity, self.tokens + elapsed * self.fill_rate)
               self.last_updated = now
   
           if self.tokens >= cost:
               self.tokens -= cost
               return True
           return False
   
   class RateLimiterRegistry:
       def __init__(self, capacity: int = 3, fill_rate: float = 1.0):
           self.capacity = capacity
           self.fill_rate = fill_rate
           self.clients = {}
   
       def is_allowed(self, client_id: str, now: float) -> bool:
           if client_id not in self.clients:
               self.clients[client_id] = TokenBucket(self.capacity, self.fill_rate, now)
           return self.clients[client_id].consume(cost=1, now=now)
   
   registry = RateLimiterRegistry(capacity=3, fill_rate=1.0)
   # Client A sends 5 rapid calls at t=0
   client_a_res = [registry.is_allowed("client_A", now=0.0) for _ in range(5)]
   # Client B sends 2 calls at t=0
   client_b_res = [registry.is_allowed("client_B", now=0.0) for _ in range(2)]
   
   print(f"Client A (Burst 5): {client_a_res} -> Accepted: {sum(client_a_res)}/5")
   print(f"Client B (Burst 2): {client_b_res} -> Accepted: {sum(client_b_res)}/2")

   Show outputGuess what it prints first

   Client A (Burst 5): [True, True, True, False, False] -> Accepted: 3/5
   Client B (Burst 2): [True, True] -> Accepted: 2/2

   Common mistake

   Watch out: Sharing bucket instances across tenant IDs causes noisy clients to consume quota allocated to other users.

   How you will know

   Client A accepts 3/5 requests, while Client B accepts 2/2, confirming tenant quota isolation.

Build it yourself

Write your solution below, run it in your browser, and pass every check.

What the result means

Interpretation

The token bucket rate limiter guarantees that no single merchant or automated webhook retry storm can saturate gateway CPU threads. In production, requests exceeding the burst capacity of three are rejected with HTTP 429 immediately, shielding downstream billing databases from queue starvation and reducing cloud autoscaler costs by eighteen lakh rupees.

The message you would send

Hi Platform Reliability Team, the in-memory Token Bucket rate limiter has been verified. The new algorithm enforces tenant-specific burst capacities (3 requests) with smooth continuous token replenishment (1.0 token/sec), blocking abusive bursts while isolating compliant merchants.

Put it on your CV

Resume or LinkedIn bullet

Engineered an in-memory sliding window token bucket rate limiter in Python, defending gateway microservices against webhook thundering herds and enforcing tenant quotas.

README for GitHub

# Sliding Window Token Bucket Rate Limiter

## Business Context
Unthrottled incoming merchant webhooks overwhelmed API gateway thread pools during flash sales, causing cascading 504 timeouts and expensive cloud autoscaling spikes.

## Solution Architecture
- Implemented lazy continuous token replenishment driven by fractional elapsed time.
- Enforced hard burst capacity limits while smoothing sustained traffic throughput.
- Provided multi-tenant quota isolation preventing noisy neighbors from starving shared endpoints.

## Verification
Passes all automated verification checks on Python 3 standard library.

Keep going

• LessonSliding Window and Stream Buffers
• Case studyBuild an Ingestion Circuit Breaker with Exponential Backoff
• Case studyCryptographic Webhook HMAC Signature Verification