CMD Guide
Home › Hands-On Builds › Backend Primitives

Build a Rate Limiter

Build a Rate Limiter

Rate limiting is the first line of defence for any backend: it protects a service from overload, abuse, and runaway clients, and it's asked about in almost every system-design interview. You already know the theory — this project makes you build a production-shaped one from an empty file, in Go and Java, and prove it works under concurrency. That gap — from "I can explain a token bucket" to "I've shipped one and debugged its race" — is exactly what separates a strong candidate from the engineer a top team hires.

Play with it first

Before you write code, build intuition. The simulator below runs all four classic algorithms against live traffic — drag the limit, burst capacity, and incoming rate, switch the traffic pattern to Bursty, and watch which algorithm absorbs the spike and which throttles hard. Notice how Token Bucket lets a burst through up to its capacity while Leaky Bucket smooths output to a flat rate.

The spec

Build a limiter with this contract, then grow it in milestones:

Milestones

Reference implementation — Token Bucket (Go)

Lazy refill is the whole trick: instead of a timer topping up tokens, we compute how many would have been added since the last call. O(1), no goroutines.

package main

import (
	"math"
	"sync"
	"time"
)

type TokenBucket struct {
	mu         sync.Mutex
	capacity   float64   // max burst
	tokens     float64   // current tokens
	refillRate float64   // tokens added per second (the steady limit)
	last       time.Time
}

func NewTokenBucket(ratePerSec, capacity float64) *TokenBucket {
	return &TokenBucket{
		capacity: capacity, tokens: capacity,
		refillRate: ratePerSec, last: time.Now(),
	}
}

// Allow reports whether one request may proceed now.
func (tb *TokenBucket) Allow() bool {
	tb.mu.Lock()
	defer tb.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(tb.last).Seconds()
	tb.tokens = math.Min(tb.capacity, tb.tokens+elapsed*tb.refillRate) // lazy refill
	tb.last = now

	if tb.tokens >= 1 {
		tb.tokens--
		return true
	}
	return false
}

type Limiter struct {
	mu        sync.Mutex
	buckets   map[string]*TokenBucket
	rate, cap float64
}

func NewLimiter(rate, cap float64) *Limiter {
	return &Limiter{
		buckets: make(map[string]*TokenBucket),
		rate:    rate,
		cap:     cap,
	}
}

func (l *Limiter) Allow(key string) bool {
	l.mu.Lock()
	b, ok := l.buckets[key]
	if !ok {
		b = NewTokenBucket(l.rate, l.cap)
		l.buckets[key] = b
	}
	l.mu.Unlock()      // release the map lock before the per-bucket lock
	return b.Allow()
}

Reference implementation — Token Bucket (Java)

package limiter;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public final class TokenBucket {
    private final double capacity;
    private final double refillPerSec;
    private double tokens;
    private long lastNanos;

    public TokenBucket(double ratePerSec, double capacity) {
        this.capacity = capacity;
        this.refillPerSec = ratePerSec;
        this.tokens = capacity;
        this.lastNanos = System.nanoTime();
    }

    public synchronized boolean allow() {
        long now = System.nanoTime();
        double elapsed = (now - lastNanos) / 1_000_000_000.0;
        tokens = Math.min(capacity, tokens + elapsed * refillPerSec); // lazy refill
        lastNanos = now;
        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }
}

// Per-key (M3): computeIfAbsent gives atomic create-on-first-use.
final class Limiter {
    private final Map<String, TokenBucket> buckets = new ConcurrentHashMap<>();
    private final double rate, cap;
    public Limiter(double rate, double cap) { this.rate = rate; this.cap = cap; }
    public boolean allow(String key) {
        return buckets.computeIfAbsent(key, k -> new TokenBucket(rate, cap)).allow();
    }
}

Break it

The concurrency race. If you remove the lock (in Go) or the synchronized keyword (in Java) on allow(), the read-modify-write of tokens is no longer atomic. Under high concurrency, multiple threads will read a stale token count, allowing more requests than the capacity bounds. Here is the class to demonstrate this race:

package limiter;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

final class UnsafeTokenBucket {
    private final double capacity;
    private final double refillPerSec;
    private double tokens;
    private long lastNanos;

    public UnsafeTokenBucket(double ratePerSec, double capacity) {
        this.capacity = capacity;
        this.refillPerSec = ratePerSec;
        this.tokens = capacity;
        this.lastNanos = System.nanoTime();
    }

    // No synchronized keyword -- check-then-act is broken
    public boolean allow() {
        long now = System.nanoTime();
        double elapsed = (now - lastNanos) / 1_000_000_000.0;
        tokens = Math.min(capacity, tokens + elapsed * refillPerSec);
        lastNanos = now;
        if (tokens >= 1.0) {
            try { Thread.sleep(5); } catch (InterruptedException ignored) {} // widen the race window
            tokens -= 1.0;
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws InterruptedException {
        int threadsCount = 50;
        CountDownLatch latch = new CountDownLatch(1);
        UnsafeTokenBucket bucket = new UnsafeTokenBucket(1, 1); // cap = 1
        AtomicInteger allowed = new AtomicInteger(0);

        Thread[] threads = new Thread[threadsCount];
        for (int i = 0; i < threadsCount; i++) {
            threads[i] = new Thread(() -> {
                try {
                    latch.await();
                    if (bucket.allow()) {
                        allowed.incrementAndGet();
                    }
                } catch (InterruptedException ignored) {}
            });
            threads[i].start();
        }

        latch.countDown(); // fire all threads at once
        for (Thread t : threads) t.join();

        System.out.println("Allowed count: " + allowed.get() + " (expected max: 1)");
        // Output will be > 1 because threads raced past the check before decrementing.
    }
}

Optimise — trade-offs

AlgorithmGainsCostsWhen to use
Token BucketAbsorbs sudden bursts up to capacity; O(1) time and memory.Slightly more complex to calculate than Fixed Window.API gateway protection where occasional legitimate bursts are fine.
Leaky BucketSmooths request rate to a flat, constant speed.Adds processing latency by queueing requests.Egress traffic shaping (calling external APIs with hard limits).
Fixed WindowExtremely simple implementation; low memory.Double-limit burst at window boundaries (2× limit).Simple usage-based quota enforcement (e.g., daily limits).
Sliding Window CounterSaves memory vs Sliding Window Log while preventing boundary bursts.Approximation based on past window overlap.High QPS systems needing smooth rate limiting with low memory overhead.

Tests to write (this is the real learning)

Extensions — take it further

What you've mastered when this is done

🔩 Production depth — In-process Rate Limiter

Spine: distributed-correctness · private lab · not a tool list

Production angle

Correct single-process limiting is the baseline for fairness and self-protection. Production outages happen when teams stop here and deploy N replicas each allowing R — effective limit NR.

Worked failure: race on tokens

  1. Two threads read tokens=1, both decrement to 0, both allow.
  2. Under load, admit rate exceeds R; dependency collapses.

Fix shape: atomic read-modify-write under mutex or CAS; lazy refill from timestamps; property tests under concurrency.

Bridge (must internalize)

After green single-process tests, draw N boxes and ask what global R is. That question is the only reason the next two limiter labs exist.

When-NOT

Need cluster-wide policy → shared store / edge. Need strict smooth egress → leaky bucket / queue, not pure burst tokens.

Related: Cross-process · Distributed limiter · API gateway theory.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build a Rate Limiter? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build a Rate Limiter** (Hands-On Builds) and want to truly understand it. Explain Build a Rate Limiter from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build a Rate Limiter** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build a Rate Limiter** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build a Rate Limiter** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

Build a Write-Ahead Log (WAL) →