Rate Limiter

Decide, per client, whether this request gets through or gets rejected - and make the "how" (token bucket versus sliding window) a decision you can change without touching anything that calls the limiter.

Requirements

Functional

• A caller asks the limiter "should this request from client X be allowed" and gets a yes/no answer.
• Limiting is per client key (a user id, an API key, an IP), not global across every caller.
• Two different limiting algorithms should be supported: a token bucket (bursty, refills over time) and a sliding window (a hard cap over a rolling time period).
• A client that hasn't made a request in a while shouldn't be penalized by state left over from long ago.

Non-functional

• Checking a request must be an operation on that one client's state only - it must never scan every client to decide about one of them.
• Swapping the algorithm for all clients, or for one specific client, must be a configuration change, not a code change.

Design

RateLimiter is an interface with one method - allow(clientKey) - and everything about how the decision is made lives inside the implementation. RateLimiterRegistry keeps one algorithm instance per client key, created lazily, so the check for any one client never has to look at another client's state.

1. 1The caller only knows a client key - never which algorithm is behind it.
2. 2The registry looks up or lazily creates that client's limiter instance, isolated from every other client.
3. 3The registry delegates the actual decision to the client's own limiter instance.
4. 4A token bucket computes accrued tokens; a sliding window drops timestamps outside the window - both lazily, on this call.

Because the algorithm is entirely behind allow, a token bucket and a sliding window are interchangeable from every caller's point of view - the registry could even hand out different algorithms to different client tiers without those callers noticing.

Class diagram

implements

RateLimiterRegistry hands each client key its own RateLimiter instance; TokenBucket and SlidingWindow are interchangeable strategies behind the same allow() call.

Code

import java.util.*;

import java.util.function.Supplier;

 

interface RateLimiter {

boolean allow();

}

 

class TokenBucketLimiter implements RateLimiter {

private final int capacity;

private final double refillRatePerSec;

private double tokens;

private long lastRefillMillis;

 

TokenBucketLimiter(int capacity, double refillRatePerSec) {

this.capacity = capacity;

this.refillRatePerSec = refillRatePerSec;

this.tokens = capacity;

this.lastRefillMillis = System.currentTimeMillis();

}

 

public synchronized boolean allow() {

long now = System.currentTimeMillis();

double elapsedSec = (now - lastRefillMillis) / 1000.0;

tokens = Math.min(capacity, tokens + elapsedSec * refillRatePerSec);

lastRefillMillis = now;

 

if (tokens >= 1) {

tokens -= 1;

return true;

}

return false;

}

}

 

class SlidingWindowLimiter implements RateLimiter {

private final int maxRequests;

private final long windowMillis;

private final Deque<Long> timestamps = new ArrayDeque<>();

 

SlidingWindowLimiter(int maxRequests, long windowMillis) {

this.maxRequests = maxRequests;

this.windowMillis = windowMillis;

}

 

public synchronized boolean allow() {

long now = System.currentTimeMillis();

while (!timestamps.isEmpty() && now - timestamps.peekFirst() > windowMillis) {

timestamps.pollFirst();

}

if (timestamps.size() < maxRequests) {

timestamps.addLast(now);

return true;

}

return false;

}

}

 

class RateLimiterRegistry {

private final Map<String, RateLimiter> limiters = new HashMap<>();

private final Supplier<RateLimiter> factory;

 

RateLimiterRegistry(Supplier<RateLimiter> factory) {

this.factory = factory;

}

 

boolean allow(String clientKey) {

RateLimiter limiter = limiters.computeIfAbsent(clientKey, k -> factory.get());

return limiter.allow();

}

}

Design decisions

• RateLimiter is a Strategy with exactly one method. A narrower interface means a token bucket and a sliding window can differ completely in their internal state (a token count and a refill timestamp versus a deque of request timestamps) while callers only ever see allow(key) - the algorithm choice is invisible past that one call.
• State is per-client-key, held in the registry, not inside a single shared limiter instance. If one RateLimiter object tracked every client's counters internally, every check would contend on the same object; keying a fresh instance per client means each client's rate limiting is independent and there's no shared mutable state to reason about across clients.
• The token bucket computes elapsed time on each call instead of running a background refill timer. Refilling lazily - "how many tokens would have accrued since I was last checked" - means an idle client costs nothing between requests; a timer-based refill would tick for every client whether or not it's making requests.
• What's missing for a real system: this keeps every client's state in local process memory, which doesn't work once there's more than one instance behind a load balancer - a real deployment needs the counters in a shared store (Redis is the usual choice) with atomic increment-and-check, since two instances racing to check the same client's budget is exactly the bug a rate limiter exists to prevent.

Common follow-ups

• How would you give different client tiers different limits (free vs. paid)? RateLimiterRegistry's factory currently produces the same kind of limiter for every key; making it tier-aware means the factory becomes a function of the client key, or looks up a tier-to-config map, instead of being one fixed supplier. RateLimiter and its implementations don't change at all.
• Is RateLimiterRegistry.allow's lookup-or-create step safe under concurrent access from many threads? Not as shown - a plain map's check-then-insert is a race: two threads could both see a brand-new client key as absent and each create a separate limiter for it, undermining the very isolation the registry exists to provide. It needs a concurrency-safe map or a lock around the lookup-or-create step.
• How would you scale this across multiple service instances behind a load balancer? Move client state out of local process memory into a shared store, typically Redis, with atomic increment-and-check. RateLimiter.allow() as an interface doesn't need to change, but its implementation becomes a thin client issuing an atomic command instead of holding local fields.
• A client makes zero requests for a week, then bursts - does TokenBucketLimiter penalize or reward that? It rewards it, up to capacity - allow() computes elapsed time since the last refill and adds tokens proportionally, capped at capacity, so a week of inactivity just means the bucket sits full and the client gets a full burst allowance on return.

Check yourself

Question 1 of 4

Why does RateLimiterRegistry create one RateLimiter instance per client key instead of one shared instance for everyone?