Implementation

This chapter builds a token bucket and a sliding window counter in Python, then ports the token bucket to C++, Java and TypeScript. The clock is injected so tests can control time.

Python: token bucket and sliding window counter

import threading
import time
from typing import Callable


class TokenBucket:
    def __init__(self, rate: float, capacity: float,
                 clock: Callable[[], float] = time.monotonic) -> None:
        if rate <= 0 or capacity < 1:
            raise ValueError("rate must be > 0 and capacity >= 1")
        self.rate, self.capacity, self.clock = rate, capacity, clock
        self.tokens = float(capacity)
        self.updated = clock()
        self.lock = threading.Lock()

    def try_acquire(self, cost: float = 1.0) -> tuple[bool, float]:
        """Return (allowed, seconds to wait before retrying)."""
        with self.lock:
            now = self.clock()
            elapsed = max(0.0, now - self.updated)
            self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
            self.updated = now
            if self.tokens >= cost:
                self.tokens -= cost
                return True, 0.0
            return False, (cost - self.tokens) / self.rate


class SlidingWindowCounter:
    def __init__(self, limit: int, window: float,
                 clock: Callable[[], float] = time.time) -> None:
        self.limit, self.window, self.clock = limit, window, clock
        self.index = int(clock() // window)   # current window number
        self.current = self.previous = 0
        self.lock = threading.Lock()

    def allow(self) -> bool:
        with self.lock:
            now = self.clock()
            index = int(now // self.window)
            if index != self.index:
                # Next window: current becomes previous; a longer gap resets both
                self.previous = self.current if index == self.index + 1 else 0
                self.current, self.index = 0, index
            weight = 1.0 - (now - index * self.window) / self.window
            if self.previous * weight + self.current < self.limit:
                self.current += 1
                return True
            return False

• clock: defaults to time.monotonic, which never jumps backwards the way the wall clock can after an NTP correction. The window counter uses wall-clock time so window numbers line up with calendar time.
• max(0.0, ...) keeps tokens from shrinking if time ever goes backwards; min(self.capacity, ...) caps the burst no matter how long the client was idle.
• The second return value (cost - tokens) / rate is the time until enough tokens are back, which maps straight onto Retry-After. A cost above capacity can never succeed, so reject it up front.
• threading.Lock makes read, compute and write one unit, so two threads cannot spend the same token.
• The window counter shifts counters only when the window number changes, and zeroes the previous count after a gap of more than one window.

A fake clock makes the behavior deterministic in tests.

t = [0.0]
bucket = TokenBucket(rate=1, capacity=3, clock=lambda: t[0])
print([bucket.try_acquire()[0] for _ in range(4)])  # [True, True, True, False]
print(bucket.try_acquire())                          # (False, 1.0)
t[0] = 1.0
print(bucket.try_acquire())                          # (True, 0.0)

For one bucket per key, use a dict[str, TokenBucket]. A full bucket is indistinguishable from a brand-new one, so evicting idle keys never changes a decision.

C++

#include <algorithm>
#include <chrono>
#include <mutex>

class TokenBucket {
public:
    using Clock = std::chrono::steady_clock;

    TokenBucket(double rate, double capacity)
        : rate_(rate), capacity_(capacity), tokens_(capacity), updated_(Clock::now()) {}

    bool allow(double cost = 1.0) {
        std::lock_guard<std::mutex> lock(mutex_);
        auto now = Clock::now();
        std::chrono::duration<double> elapsed = now - updated_;
        tokens_ = std::min(capacity_, tokens_ + elapsed.count() * rate_);
        updated_ = now;
        if (tokens_ < cost) return false;
        tokens_ -= cost;
        return true;
    }

private:
    double rate_, capacity_, tokens_;
    Clock::time_point updated_;
    std::mutex mutex_;
};

// TokenBucket bucket(2.0, 5.0); eight quick allow() calls: 5 true, then 3 false

steady_clock is the C++ counterpart of Python's monotonic: it never goes backwards.

Java

public final class TokenBucket {
    private final double rate, capacity;
    private double tokens;
    private long updatedNanos;

    public TokenBucket(double rate, double capacity) {
        this.rate = rate;
        this.capacity = capacity;
        this.tokens = capacity;
        this.updatedNanos = System.nanoTime();
    }

    public synchronized boolean allow(double cost) {
        long now = System.nanoTime();
        double elapsed = (now - updatedNanos) / 1_000_000_000.0;
        tokens = Math.min(capacity, tokens + elapsed * rate);
        updatedNanos = now;
        if (tokens < cost) return false;
        tokens -= cost;
        return true;
    }
}
// new TokenBucket(2.0, 5.0): eight quick allow(1.0) calls give 5 true, then 3 false

System.nanoTime() is a monotonic source meant for measuring elapsed time, and synchronized plays the role of the Python lock.

TypeScript

export class TokenBucket {
  private tokens: number;
  private updated: number;

  constructor(
    private readonly rate: number,
    private readonly capacity: number,
    private readonly now: () => number = () => performance.now() / 1000,
  ) {
    this.tokens = capacity;
    this.updated = this.now();
  }

  allow(cost = 1): boolean {
    const now = this.now();
    this.tokens = Math.min(this.capacity, this.tokens + (now - this.updated) * this.rate);
    this.updated = now;
    if (this.tokens < cost) return false;
    this.tokens -= cost;
    return true;
  }
}

const bucket = new TokenBucket(2, 5);
console.log(Array.from({ length: 8 }, () => bucket.allow()));
// [true, true, true, true, true, false, false, false]

JavaScript runs on a single thread, so no lock is needed. Once several processes or servers share one limit, use the Redis approach from the last chapter.

Summary

• A token bucket needs only two values: the token count and the time of the last update.
• A sliding window counter needs a window number and two counters.
• Injecting the clock makes time-dependent code deterministic to test.
• When threads share a bucket, guard read, compute and write with a lock.