PHASE 4Intermediate ~13 min· topic 15 of 18Level 3

Problem 4.15 — Rate Limiter (LLD)

In one line

The bridge problem between LLD and HLD: algorithms, concurrency-safe counters, and where Redis takes over. Revisit it in Phase 12 for the distributed version.

0/18 · 0%

Think of it like this

A nightclub bouncer letting people in at a steady pace instead of everyone rushing the door at once. The bouncer has a rulebook (allow so many people per minute) and the same idea protects a server from being overwhelmed.

Key ideas

01
Algorithms: Fixed window, Sliding window log, Sliding window counter, Token bucket, Leaky bucket.
02
Token bucket is the interview favorite: refill rate + capacity; allow if tokens ≥ 1.
03
In-memory rate limiter: per-key state in a ConcurrentHashMap — must be thread-safe under concurrent requests.
04
Distributed: state moves to Redis (Lua INCR + EXPIRE) — keyed by user/IP/API key.
05
Response contract: HTTP 429 + Retry-After header; allowlist/denylist exemptions.
06
Dimensions: per user, per IP, per API key, per endpoint — one limiter per dimension key.
07
Why headers: X-RateLimit-Limit/Remaining/Reset so clients self-throttle.

Java / Spring map

→
Bucket4j, or hand-roll TokenBucket + a ConcurrentHashMap<String, TokenBucket> — write it yourself at least once.

Code & diagrams

TokenBucketLimiter.javajava

Concurrency-safe in-memory token bucket + per-key registry.

public class TokenBucket {
  private final double capacity;
  private final double refillPerSecond;
  private double tokens;
  private long lastRefillNanos;

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

  public synchronized boolean tryConsume() {   // synchronized: state is shared
    refill();
    if (tokens >= 1) { tokens -= 1; return true; }
    return false;
  }
  private void refill() {
    long now = System.nanoTime();
    double secs = (now - lastRefillNanos) / 1_000_000_000.0;
    tokens = Math.min(capacity, tokens + secs * refillPerSecond);
    lastRefillNanos = now;
  }
}

public class RateLimiter {
  private final Map<String, TokenBucket> buckets = new ConcurrentHashMap<>();
  private final TokenBucket defaults;

  public RateLimiter(TokenBucket defaults) { this.defaults = defaults; }

  public boolean allow(String key) {
    TokenBucket b = buckets.computeIfAbsent(key, k -> new TokenBucket(
        defaults.capacity, defaults.refillPerSecond));
    return b.tryConsume();
  }
}

// Servlet/controller usage:
// if (!rateLimiter.allow("user:" + userId)) return 429 with Retry-After;
// Shared across all threads of ONE instance. Across instances → Redis (Phase 12).

Explain without notes

What changes between a single-instance and multi-instance deployment of this class? Name the exact failure.

Why did we use synchronized on a per-bucket basis instead of locking the whole map?

Practice

Implement the Sliding Window Counter variant and compare memory with Token Bucket.

Write the Redis Lua script that makes the same decision atomically across instances.

Trade-offs

↔
Token bucket = smooth bursts but slightly 'bursty' vs fixed window = strict per-window quota but spiky at boundaries.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Stateful · Redis & caching patterns

Cache-aside with a stampede lock, TTLs, rate limiting, and sessions in Redis.

Networking · Nginx caching, compression & rate limiting

Rate limiting and caching at the edge of your service.

Completion checklist

I can implement a thread-safe limiter and explain exactly why Redis is needed at scale.

Back to phase

Command Palette