Rate Limiter

Design an in-process rate limiter library that services call before handling a request. It must limit per key (user, API key, or IP), support several algorithms, and stay correct under concurrent access.

Clarifying Questions

Is the limit per key, global, or both, and how many distinct keys do we expect?
Which algorithms matter: token bucket for bursts, or a sliding window for strict fairness?
Single process, or must limits hold across a fleet of servers?
On rejection, does the caller need the retry time or only a yes or no?
Can limits change at runtime per customer tier?

Core Requirements

Check and consume a permit for a key in one atomic call.
Support token bucket, fixed window, and sliding window log algorithms behind one interface.
Configure limits per rule, such as per customer tier or per endpoint.
Return a decision with remaining permits and a retry-after time.
Evict idle keys so memory stays bounded.
Stay correct when many threads hit the same key at once.

Canonical class breakdown

RateLimiter: Facade that resolves the rule for a request, finds the key's limiter state, and returns a Decision.

RateLimitRule: Immutable config: limit, window or refill rate, burst size, and the algorithm to use.

RuleResolver: Maps a request context (tier, endpoint, key type) to a RateLimitRule.

LimiterAlgorithm (interface) / TokenBucket, FixedWindow, SlidingWindowLog: Encapsulates per-key state and the tryAcquire logic for one algorithm.

KeyStore (interface): Concurrent map from key to algorithm state with idle eviction; swappable for a Redis-backed store.

Clock (interface): Supplies the current time so tests can advance it deterministically.

Decision: Value object with allowed, remaining, and retryAfter, ready for the caller to turn into response headers.

Java sketchjava

// Java skeleton

enum Algorithm { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG }

interface Clock {
    long nowNanos();
}

record RateLimitRule(String name, long limit, Duration window, long burst, Algorithm algorithm) {}

record RequestContext(String key, String tier, String endpoint) {}

record Decision(boolean allowed, long remaining, Duration retryAfter) {}

interface RuleResolver {
    RateLimitRule resolve(RequestContext ctx);
}

interface LimiterAlgorithm {
    Decision tryAcquire(long permits, long nowNanos);
}

class TokenBucket implements LimiterAlgorithm {
    private final long capacity;
    private final double refillPerNano;
    private double tokens;
    private long lastRefillNanos;
    public synchronized Decision tryAcquire(long permits, long nowNanos) {
        /* refill lazily from elapsed time, then take permits if available */
    }
}

class FixedWindow implements LimiterAlgorithm { ... }

class SlidingWindowLog implements LimiterAlgorithm {
    private final Deque<Long> timestamps; // memory grows with the limit
    public synchronized Decision tryAcquire(long permits, long nowNanos) { ... }
}

interface KeyStore {
    LimiterAlgorithm getOrCreate(String key, RateLimitRule rule);
    void evictIdle(Duration idleFor);
}

class InMemoryKeyStore implements KeyStore {
    private final ConcurrentHashMap<String, LimiterAlgorithm> states;
    private final ConcurrentHashMap<String, Long> lastAccess;
    ...
}

class RateLimiter {
    private final RuleResolver rules;
    private final KeyStore store;
    private final Clock clock;
    public Decision check(RequestContext ctx) {
        RateLimitRule rule = rules.resolve(ctx);
        return store.getOrCreate(rule.name() + ":" + ctx.key(), rule)
                    .tryAcquire(1, clock.nowNanos());
    }
}

Key Decisions to Defend

LimiterAlgorithm is a Strategy: token bucket suits bursty APIs, a sliding window log suits strict fairness, and caller code stays the same.
Token bucket refills lazily on each call from elapsed time, so there is no timer thread per key.
State is synchronized per key (a lock or compare-and-set on the bucket), so one hot key never serializes every other key.
Clock is injected; time-based logic without it is nearly impossible to unit test.
KeyStore is an interface, so moving to Redis with a Lua script changes one class when limits must hold across servers.

Likely follow-ups

· Limits must hold across 50 servers, what moves to Redis and what stays local?
· The shared store is unreachable, do you fail open or closed?
· A tenant needs a daily quota and a per-second limit at once, how do rules compose?
· Sliding window logs for 10M keys use too much memory, what do you change?

Dive Deeper

This version of the rate limiter question is about class design and concurrency, with the distributed version as the follow-up. Interviewers watch for a clean algorithm interface, lazy token refill from elapsed time, and per-key synchronization that avoids a global lock. An injected Clock is a strong signal that you test time-based code. The best answers also name the memory cost of a sliding window log and offer the sliding window counter as the cheaper approximation.

All OOD Prompts