In-Memory Rate Limiter

The Rate Limiter system design case covers the distributed, Redis-backed version. This lesson is the single-process, in-memory implementation — the class design an interviewer expects when the scope is explicitly "no Redis, just Java."

Pluggable algorithm via Strategy

interface RateLimiter {
    boolean tryAcquire(); // true = request allowed, false = rate-limited
}

Same Strategy shape used throughout this course — a caller depends only on RateLimiter, never on whether the concrete algorithm is token bucket or sliding window, matching the algorithm comparison covered in the Rate Limiter case study.

Token bucket implementation, with correct synchronization

class TokenBucketRateLimiter implements RateLimiter {
    private final int capacity;
    private final double refillRatePerSecond;
    private double availableTokens;
    private long lastRefillTimestamp;

    TokenBucketRateLimiter(int capacity, double refillRatePerSecond) {
        this.capacity = capacity;
        this.refillRatePerSecond = refillRatePerSecond;
        this.availableTokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    public synchronized boolean tryAcquire() { // synchronized — see below for why this is necessary here
        refill();
        if (availableTokens >= 1) {
            availableTokens -= 1;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsedSeconds = (now - lastRefillTimestamp) / 1_000_000_000.0;
        double tokensToAdd = elapsedSeconds * refillRatePerSecond;
        if (tokensToAdd > 0) {
            availableTokens = Math.min(capacity, availableTokens + tokensToAdd);
            lastRefillTimestamp = now;
        }
    }
}

Why synchronized, specifically: tryAcquire() is a classic check-then-act sequence (check availableTokens >= 1, then decrement) — without synchronization, two threads could both read availableTokens = 1, both pass the check, and both decrement, allowing 2 requests through on a budget of 1 (the same race shape as HashMap Concurrency Variants' putIfAbsent example). A synchronized method is the simplest correct fix here; a ReentrantLock would work identically, and for extremely high-throughput scenarios, an AtomicLong-based lock-free refill/decrement (storing tokens as a fixed-point integer, using CAS) would avoid blocking entirely — worth naming as the next optimization step if throughput under contention becomes the bottleneck.

Per-user vs global rate limiting: the key design change

class PerUserRateLimiter {
    private final Map<String, RateLimiter> userLimiters = new ConcurrentHashMap<>();
    private final Supplier<RateLimiter> limiterFactory; // e.g. () -> new TokenBucketRateLimiter(10, 1.0)

    boolean tryAcquire(String userId) {
        RateLimiter limiter = userLimiters.computeIfAbsent(userId, id -> limiterFactory.get());
        return limiter.tryAcquire();
    }
}

Global rate limiting needs exactly one RateLimiter instance shared across every caller. Per-user limiting needs one instance per user, looked up by key — the data structure itself changes from "a single object" to "a map of objects," not just a parameter. ConcurrentHashMap.computeIfAbsent() here does double duty: it's both the lookup and the atomic "create on first use" — exactly the pattern covered in HashMap Concurrency Variants, avoiding a separate check-then-create race on top of the token bucket's own internal race.

A practical concern this raises: userLimiters grows unboundedly as new users make requests and never shrinks — a production version needs an eviction policy (an LRU cache, see Thread-Safe LRU Cache, or a TTL-based expiry) for inactive users' limiter entries, otherwise this is exactly the unbounded-growth memory leak pattern from Memory Leaks in Java.

Follow-up questions this topic invites — and their answers

Q: Why store availableTokens as a double rather than an int? A: Refilling continuously based on elapsed real time (rather than in discrete per-second ticks) produces fractional token amounts between refill checks — using a double lets the bucket refill smoothly and precisely rather than only in whole-token jumps tied to a fixed timer interval.

Q: What's the tradeoff of synchronized vs a lock-free CAS-based implementation here? A: synchronized is simpler to reason about and correct by construction, at the cost of threads blocking under contention; a CAS-based approach (see Visibility & Memory Model's Atomic classes section) avoids blocking but requires more careful implementation to keep the refill-then-decrement logic correct under retry — worth the complexity only if profiling shows lock contention is an actual bottleneck.

Q: How would you rate-limit by IP address instead of user ID? A: Structurally identical to PerUserRateLimiter — swap the map's key from userId to a normalized IP string; the only real design question is normalization (IPv6 vs IPv4, handling requests behind a shared NAT/proxy where many users share one IP) rather than anything about the rate-limiting mechanism itself.

Q: Does this in-memory design work correctly across multiple application server instances? A: No — each instance would have its own independent bucket, so a user could get capacity-times-instance-count total throughput by hitting different instances, defeating the limit. This is exactly the gap the Rate Limiter system design case's Redis-based approach closes, by centralizing bucket state somewhere all instances share.