Design a Rate Limiter Class

Token bucket mechanics

A token bucket holds up to capacity tokens and refills at rate tokens per second. Each request consumes one token; if none are available, the request is rejected (or delayed). Capacity sets the allowed burst, and rate sets the sustained throughput. Refill lazily: on each call, add elapsed * rate tokens, capped at capacity, instead of running a timer. For per-user limits, keep a map from user id to bucket and evict idle buckets. Alternatives to mention: fixed window counters (simple but bursty at window edges), sliding window log (accurate but memory heavy) and sliding window counters. A distributed limiter usually keeps bucket state in a shared store such as Redis and updates it atomically.

Thread-safe token bucket

Java; uses a monotonic clock.

interface RateLimiter {
    boolean tryAcquire();
}

class TokenBucket implements RateLimiter {
    private final double capacity;
    private final double refillPerNano;
    private double tokens;
    private long lastRefill;

    TokenBucket(double capacity, double tokensPerSecond) {
        this.capacity = capacity;
        this.refillPerNano = tokensPerSecond / 1_000_000_000.0;
        this.tokens = capacity;
        this.lastRefill = System.nanoTime();
    }

    @Override
    public synchronized boolean tryAcquire() {
        long now = System.nanoTime();
        tokens = Math.min(capacity, tokens + (now - lastRefill) * refillPerNano);
        lastRefill = now;
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;
    }
}

class PerUserLimiter {
    private final java.util.concurrent.ConcurrentHashMap<String, TokenBucket> buckets = new java.util.concurrent.ConcurrentHashMap<>();
    boolean allow(String userId) {
        return buckets.computeIfAbsent(userId, id -> new TokenBucket(10, 5)).tryAcquire(); // assumed limits
    }
}

Use a monotonic clock

Wall-clock time can jump backwards or forwards; System.nanoTime in Java or time.monotonic in Python is safer for measuring elapsed time.

Quick check: In a token bucket, what does the capacity control?

• The number of users
• The maximum burst of requests allowed at once
• The refill rate per second
• The request timeout