Walkthrough: Design a Rate Limiter

The requirement, and the naive trap

"Allow at most N requests per user per window." The obvious fix — a per-user counter reset every minute — has a nasty edge: a client can fire N requests at 0:59 and another N at 1:01, 2N in two seconds, while never breaking the per-minute rule.

interface RateLimiter {
  boolean allow(String userId);   // true = let the request through
}

We'll build the naive fixed window to expose the flaw, then fix it with a token bucket.

<!--STEP-->

Fixed window: simple, and its boundary bug

class FixedWindowLimiter implements RateLimiter {
  private final int limit;
  private final long windowMs;
  private final Map<String, long[]> state = new ConcurrentHashMap<>();  // [windowStart, count]

  FixedWindowLimiter(int limit, long windowMs) { this.limit = limit; this.windowMs = windowMs; }

  public synchronized boolean allow(String userId) {
    long now = System.currentTimeMillis();
    long[] s = state.computeIfAbsent(userId, k -> new long[]{ now, 0 });
    if (now - s[0] >= windowMs) { s[0] = now; s[1] = 0; }   // new window
    if (s[1] < limit) { s[1]++; return true; }
    return false;
  }
}

Correct for the literal rule, but the boundary burst from Step 1 is real: the counter snaps back to 0 at a fixed instant, so two adjacent windows can each admit the full limit back-to-back. To smooth bursts we change algorithms.

<!--STEP-->

Token bucket: bursts, bounded

Picture a bucket holding up to capacity tokens, refilling at refillPerSec. Each request removes one token; an empty bucket rejects. Capacity caps the burst size; the refill rate caps the sustained rate.

capacity = 5, refill = 1/sec
t=0s  [#####]  -> 5 quick requests OK, bucket empties
t=1s  [#....]  -> +1 token, 1 request OK
t=5s  [#####]  -> refilled back to cap (never exceeds capacity)

This is why token bucket is the default: it absorbs short spikes up to capacity yet enforces a smooth long-run rate — exactly what fixed windows fail to do.

<!--STEP-->

Implementing lazy refill

Don't run a background thread ticking every bucket — compute tokens on demand from elapsed time. It's cheaper and exact.

class TokenBucket {
  private final double capacity, refillPerMs;
  private double tokens;
  private long lastRefillMs;

  TokenBucket(double capacity, double refillPerSec) {
    this.capacity = capacity; this.refillPerMs = refillPerSec / 1000.0;
    this.tokens = capacity; this.lastRefillMs = System.currentTimeMillis();
  }

  synchronized boolean tryConsume() {
    long now = System.currentTimeMillis();
    tokens = Math.min(capacity, tokens + (now - lastRefillMs) * refillPerMs);  // lazy refill
    lastRefillMs = now;
    if (tokens >= 1) { tokens -= 1; return true; }
    return false;
  }
}

On each call we add elapsed * rate tokens (capped at capacity) before deciding. No timer threads, no per-bucket scheduling — the math does the work.

<!--STEP-->

Per-user buckets, and the distributed catch

class TokenBucketLimiter implements RateLimiter {
  private final Map<String, TokenBucket> buckets = new ConcurrentHashMap<>();
  private final double capacity, refillPerSec;

  TokenBucketLimiter(double capacity, double refillPerSec) {
    this.capacity = capacity; this.refillPerSec = refillPerSec;
  }

  public boolean allow(String userId) {
    return buckets
      .computeIfAbsent(userId, k -> new TokenBucket(capacity, refillPerSec))
      .tryConsume();
  }
}

ConcurrentHashMap isolates users so one heavy user can't block others, and computeIfAbsent creates a bucket atomically on first sight. One caveat to say out loud: this state is per-process. Behind a load balancer, three servers keep three independent buckets and the real limit becomes 3×. The distributed fix is shared state — a Redis counter or token bucket keyed by user.

Practice it for real: the Rate Limiter problem in the ladder tests fixed-window and token-bucket behaviour on hidden traffic patterns.