Design a Rate Limiter

Understanding the problem

This is a low-level design question, so the interesting part is not how it scales to a billion users. It is how cleanly it models the problem in objects and how it behaves when a dozen threads hit the same client key in the same millisecond. A rate limiter has a tiny public surface: one method that answers "may this call proceed." Underneath sits a surprising amount of subtlety. It covers which counting algorithm you pick, how the limiter attaches to the work it protects, and where you guard the mutable state that every thread wants to touch. Get those three right and the design is done.

Picture the shape before any code. A Caller invokes a service. Instead of calling the raw service, it calls a Rate-limited wrapper that holds a Rate limiter and the real service inside it. The wrapper asks the limiter "may this key proceed," the limiter consults the Per-key bucket state for that client, and on a yes the wrapper delegates to the real work while on a no it rejects. Three collaborators, one guarded piece of state, and an interface thin enough that nothing calling the service can tell the limiter is there.

The Morgan Stanley angle

Set the register first, because it decides how you should answer. Morgan Stanley is an enterprise-Java shop, and its design questions run as low-level design. The rate limiter shows up in almost exactly this framing: build a decorator that rate-limits a function. A panel here is not waiting for you to estimate queries per second across a fleet. It is watching whether you reach for a clean interface, name a design pattern by the right name, and then hold the design together when concurrency is added. The technical rounds lean Core Java and threading, and that is where candidates are separated. Treat this as an object-modeling and thread-safety problem, and you are answering in the room's language.

Functional requirements

Keep the core to the allow-or-deny decision and let the interviewer widen it. The limiter has to answer one question fast: given a key, is this call within the configured limit right now. It has to track a separate allowance per key, so one noisy client cannot spend another client's budget. It has to attach to an existing service without rewriting that service. And its limit, the count and the window, has to be configurable rather than hard-coded.

Non-functional requirements

Reason through each target, because these are what draw the class boundaries later. Correctness under concurrency is the property everything else bends around. Many threads will call the limiter at once, some for the same key and some for different keys, and the answer has to stay right. A limit of a hundred means at most a hundred pass. It never means a hundred and three because three threads read the same count before any of them wrote it back. This is a check-then-act problem, and naming it as one early is the signal a Java panel is listening for.

Latency and footprint come next, and they push toward the same shape. The check sits on the hot path in front of real work, so it has to be constant time and allocate nothing surprising: read the key's state, update it, decide. Memory is per key, and keys can be unbounded over time, so the design has to hold only the active ones and evict the state for keys that have gone quiet, or a long-lived process leaks. Fairness matters too, since a limiter that lets one thread starve while another sails through is a subtle bug that shows up only under load.

Now scope it honestly, because scope is what makes this low-level design. The target is a single process. This is a library that lives inside one JVM, guarding calls made on that JVM's threads, which is why the hard part is the in-memory concurrency, not a network. A limiter shared across a whole fleet is a real and different problem. Name it (a shared counter in something like Redis), then set it aside as out of scope. That keeps the conversation on the object design and the threading the round actually tests.

• Correctness under threads: no check-then-act race. A limit of N lets at most N through even when many threads hit one key together. The read-modify-write on the counter is atomic, or it is wrong exactly when it is busiest.
• Constant time on the hot path: O(1) per decision. The check runs in front of real work, so it reads and updates one key's state and returns. No scanning a log of timestamps, no allocation storm.
• Bounded memory: state only for active keys. Per-key state in a concurrent map, with idle keys aged out. Unbounded keys over a long-lived process would otherwise leak until the heap gives up.
• Single process by design: in-JVM library, not a service. This is LLD: one process, real threads, no network. A fleet-wide limiter is a shared counter in Redis, named and then scoped out so the round stays on objects and concurrency.

One framing choice is worth stating out loud because it steers everything downstream. The limiter is a policy, and the work it protects is a separate thing. If you fuse the two, every service that wants limiting has to be edited, and the counting logic gets copied around. If you keep them apart, one limiter implementation can wrap any service, and swapping the algorithm never touches the service. That separation is the seam the decorator will sit on, and it is the difference between a design that reads as senior and one that reads as a first draft.

The counting algorithm

Before the objects, settle how the counting works, because the algorithm decides what state each key holds. Know these four. They trade accuracy against memory and against how they treat bursts. Work up from the simplest, since the interviewer wants to hear why the obvious counter leaks before you land on the one you would ship.

So the state per key is two numbers, a token count and a last-refill timestamp, and every decision is a small read-modify-write over them. Hold that thought, because it is the exact thing concurrency will attack: two threads that both read the same token count, both see one token left, and both decide to spend it. The algorithm is settled; the correctness now lives in how that update is guarded.

A clean object design: the decorator

Now the object model, which is where a low-level design round spends most of its minutes. The requirement to wrap an existing service without changing it names the pattern outright: the decorator. A decorator implements the same interface as the thing it wraps, holds a reference to that thing, adds its behavior around the delegated call, and returns. Because it shares the interface, every caller keeps calling the same type and cannot tell a limiter was slipped in front. The limiting logic lives in exactly one class, and any service that fits the interface can be wrapped.

Read the diagram by role. Blue is the caller at the edge, violet is an object we write, green is the mutable state, and amber is the reject path. The wrapper and the limiter are separate collaborators on purpose: the wrapper knows how to delegate, the limiter knows how to count, and neither has to know the other's internals.

Name the classes and what each is responsible for, because the interviewer grades the boundaries as much as the code. Four types carry the design. Keep the split between them clean.

// The contract the real service and its decorator both satisfy.
interface OrderService {
    OrderResult place(Order order);
}
// The policy, kept as an interface so the algorithm can be swapped.
interface RateLimiter {
    boolean tryAcquire(String key);
}
// The decorator: same interface as the service it wraps, so the
// caller cannot tell it is there. It counts nothing itself.
final class RateLimitedOrderService implements OrderService {
    private final OrderService delegate;
    private final RateLimiter limiter;
    RateLimitedOrderService(OrderService delegate, RateLimiter limiter) {
        this.delegate = delegate;
        this.limiter = limiter;
    }
    @Override
    public OrderResult place(Order order) {
        if (!limiter.tryAcquire(order.clientId())) {
            throw new RateLimitExceededException(order.clientId());
        }
        return delegate.place(order);
    }
}

The Morgan Stanley angle

This is the part a Morgan Stanley round is most likely to name explicitly, so use the vocabulary. Call it a decorator, and be ready to contrast it with the patterns the same interviewers pair it against. A Singleton comes up if they ask how the limiter is shared, and a Factory if they ask how the right limiter is chosen per service. There is also a Strategy view of the swappable RateLimiter interface. The low-level design questions here reward pattern fluency and clean layering, the same instinct behind the "write the whole service on paper, Controller to Service to DAO to Entity" prompt that also shows up. Say why the decorator earns its place, that it keeps limiting composable and the service single-purpose, rather than only reciting that it is one.

Thread safety: where the design is won or lost

This is the section the round is really testing, because in an enterprise-Java loop the concurrency is where people are cut. The limiter is called by many threads at once, and the token bucket's two-number update is a read-modify-write: read the token count, add the lazy refill, check for a token, spend it. If two threads run that sequence interleaved on the same key, both can read one token remaining, both can decide to spend it, and the limit is breached by exactly the amount you were trying to prevent. Every fix below is about making that sequence indivisible. Work up from the version that looks safe and is not.

Say two Java specifics by name, because the panel is listening for them. First, computeIfAbsent on a ConcurrentHashMap creates a key's bucket exactly once even when threads race to create the same one, which is why the map needs no external lock for setup. Second, the guarded update has to cover the whole read-modify-write, not just the increment: refilling and spending are one indivisible step, or a thread can refill on stale tokens between another thread's read and write. The state that many threads mutate is small and its guard is narrow, and that keeps a per-key lock cheap.

// One bucket per key, in a ConcurrentHashMap, so lookup and
// one-time creation are safe with no global lock.
final class TokenBucketRateLimiter implements RateLimiter {
    private final int capacity;
    private final double refillPerMilli;
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();
    private final Clock clock;
    TokenBucketRateLimiter(int capacity, double refillPerSecond, Clock clock) {
        this.capacity = capacity;
        this.refillPerMilli = refillPerSecond / 1000.0;
        this.clock = clock;
    }
    @Override
    public boolean tryAcquire(String key) {
        // computeIfAbsent creates the bucket exactly once under a race.
        Bucket bucket = buckets.computeIfAbsent(key,
            k -> new Bucket(capacity, clock.millis()));
        return bucket.tryConsume(refillPerMilli, capacity, clock.millis());
    }
}
// The mutable state lives here, and the whole read-modify-write
// is guarded so refilling and spending are one indivisible step.
final class Bucket {
    private double tokens;
    private long lastRefillMillis;
    Bucket(int capacity, long now) {
        this.tokens = capacity;
        this.lastRefillMillis = now;
    }
    synchronized boolean tryConsume(double refillPerMilli, int capacity, long now) {
        long elapsed = now - lastRefillMillis;
        tokens = Math.min(capacity, tokens + elapsed * refillPerMilli);
        lastRefillMillis = now;
        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }
}

The Morgan Stanley angle

Concurrency is the gate at Morgan Stanley, so treat this as the part of the answer to slow down on instead of rush past. The technical rounds go deep on threading and the collections underneath it. Expect synchronized versus compare-and-swap, and how a HashMap behaves under concurrent writes versus a ConcurrentHashMap. Immutability comes up too, and the memory model that makes a guarded write visible to the next reader. A strong answer walks the check-then-act race out loud, fixes it with the narrowest guard that works, and only then discusses when a lock-free version earns its keep. If you can also say why the guard has to wrap the refill and the spend together, not just the decrement, you are demonstrating the exact depth the loop is built to find.

What the round rewards

The bar here is a clean object model and correct concurrency. Recruiters describe the design conversation as a discussion more than a whiteboard capacity exercise, so narrate the mechanism plainly. State the interface, pick the token bucket and say why, and name the decorator and why it keeps the service single-purpose. Then spend real time on the thread-safety and the tradeoffs. Expect the interviewer to push on the concurrency and the pattern vocabulary, because those are the surfaces this loop actually tests.

Common questions