Machine coding · not HLD

Rate limiter

A partner key is allowed 100 calls per minute. The 101st call in that minute must return false. A minute later the same key must be allowed again. If allow() reads System.currentTimeMillis() and a static map, you cannot freeze time in a test or swap the algorithm.

This page designs an in-process allow(key) with a swappable and an injected . Redis sliding logs across nodes belong on the related System Design note: Rate limiter .

Three questions to lock

Which algorithm?

(burst plus refill) or ; both are strategies.

Which clock?

Inject Clock. Tests set FakeClock, allow 100 times, then advance one minute.

Which lock?

Lock the bucket so two requests cannot both spend the last token.

What actually happens after the hundredth allow

The partner-key story above is the whole machine-coding problem. RateLimiter.allow(key) returns a boolean: whether this caller may proceed under a budget. The algorithm is a or a , stored as a so you can swap it without rewriting the limiter. Time comes from an injected , never from LocalDateTime.now() inside the bucket. A map of key to is the store. Mention idle-key eviction only if you talk about memory; it is not required for the first green tests.

If you cannot write the frozen-clock test, the design is coupled to the wall clock. See deterministic design. Jumping to Redis is the HLD conversation (see the System Design note in the hero). Here you are designing a class you could put in front of a single-process API. Strategy lives on the algorithm seam.

Simple rule of thumb

Those three questions in the hero decide the class shape before you type a line of Java.

Name the algorithm. A is plus refill. A is a count in the last N ms. Both are a passed into the RateLimiter constructor. Burst of 10 with slow refill is a different feel from a hard 100/minute window; say which one you are implementing.

Inject the clock. Tests set a , run the allow loop, then advance time. If that test needs Thread.sleep, Clock is missing.

Lock per key. Two requests for the same key must not both see one token. Lock the , not the whole map, unless N is tiny and you said so.

Rule of thumb

allow(key) returns boolean. Inject , lock per , and treat token bucket or sliding window as a constructor . A process-local HashMap is not a Redis cluster.

How allow() runs under a lock

Once the rule of thumb is fixed, the call path is short: look up the key, lock that state, ask the clock, then let the refill and consume.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

sequenceDiagram
    participant C as Caller
    participant L as RateLimiter
    participant B as KeyState
    participant Clock as Clock

    C->>L: allow("api-key")
    L->>B: lock per key
    L->>Clock: instant()
    B->>B: refill from elapsed
    alt tokens >= 1
        B->>B: consume 1
        L-->>C: true
    else
        L-->>C: false
    end

Responsibility walk

Type	Job
RateLimiter	Owns a map of keys, locks per KeyState, and asks the strategy using Clock.instant().
RateLimitStrategy	or as swappable strategies.
KeyState	Holds tokens or a timestamp list. Mutate only under that .
Clock	Injected ; tests use FakeClock to advance time.

Java API sketch

java

interface RateLimitStrategy {
  boolean allow(KeyState state, Instant now);
}

class TokenBucket implements RateLimitStrategy {
  private final double ratePerSecond; // refill rate
  private final double burst;         // max / initial capacity
  public TokenBucket(double ratePerSecond, double burst) {
    if (ratePerSecond <= 0 || burst < 1) throw new IllegalArgumentException();
    this.ratePerSecond = ratePerSecond;
    this.burst = burst;
  }
  public boolean allow(KeyState state, Instant now) {
    state.refill(now, ratePerSecond, burst);
    if (state.tokens < 1) return false;
    state.tokens -= 1;
    return true;
  }
}

class SlidingWindow implements RateLimitStrategy {
  private final int limit;
  private final Duration window;
  public boolean allow(KeyState state, Instant now) {
    state.evictOlderThan(now.minus(window));
    if (state.size() >= limit) return false;
    state.add(now);
    return true;
  }
}

class RateLimiter {
  private final Clock clock;
  private final RateLimitStrategy strategy;
  private final ConcurrentHashMap<String, KeyState> keys = new ConcurrentHashMap<>();

  boolean allow(String key) {
    KeyState state = keys.computeIfAbsent(key, k -> new KeyState());
    synchronized (state) {
      return strategy.allow(state, clock.instant());
    }
  }
}

One hundred allows, then a minute

The sketch above is only proven when a test can freeze time. This is that test: a plus (100.0/60.0, 100).

Numbers to know

100 tokens/min is 100.0/60.0 per second, with burst capacity 100.
Loop allow 100 times: all true. The 101st allow is false.
Advance 60 seconds on FakeClock; the next allow is true again.

Tests that prove the seams

java

@Test
void hundredThenBlockedThenRefill() {
  FakeClock clock = new FakeClock(T0);
  // 100 tokens/min ≈ 100/60 per second; burst capacity 100
  RateLimiter lim = new RateLimiter(clock,
      new TokenBucket(/* tokens per second */ 100.0 / 60.0, /* burst */ 100));
  for (int i = 0; i < 100; i++) assertTrue(lim.allow("k"));
  assertFalse(lim.allow("k"));
  clock.advance(Duration.ofSeconds(60));
  assertTrue(lim.allow("k"));
}

Two threads on the same key at 100: only one extra allow may sneak if you skipped the per-key lock (see concurrency below). Different keys proceed in parallel.

What still breaks, and what the follow-up changes

The test in Numbers to know above goes green and you can still fail the interview on a race, a wall clock, or a Redis digression. These are the cases to name out loud.

Invalid cases

System.currentTimeMillis() in the bucket: you cannot test refill after 60 seconds.
Two threads both consume the last token: lock per key, not the whole map.
Negative rate or zero window: reject the bad config at construction.
Shared without a lock: lost refills look like extra allows.
Jumping to Redis in the first sentence: that is the other interview, not this round.

Concurrency

Different keys should proceed in parallel (ConcurrentHashMap plus a per-state lock). The same key is a critical section around refill and consume. Parallel across keys and serialized per key is the locking design, not one global synchronized allow(). See thread safety.

Still fails when…

The limiter reads the wall clock, so you cannot unit-test refill.
A single global lock serializes unrelated keys that should proceed in parallel.

What the follow-up changes

Swap to by passing a new strategy class.
Idle key eviction bounds memory and is not needed for first green tests.
Distributed limiting is the System Design note; a HashMap is not Redis.

Wrap-up

You have the call path, the frozen-clock test, and the races that still break it. Use the forty-five minute plan in a machine-coding round, then follow the related notes.

How to spend forty-five minutes

0–8Write allow(key) on FakeClock and assert 100 allows, then a block.
8–20Advance the FakeClock 60 seconds and assert allow returns true.
20–32Add a per-key lock so two threads cannot both take the last token.
32–40Swap in a sliding-window strategy if the interviewer asks for it.
40–45Name Redis as the other interview (HLD vs LLD), then stay on allow(key).

Key takeaway

You're done when allow(key) rejects after the configured budget, advancing a FakeClock restores allowance, different keys can proceed in parallel under per-key locking, and you can name whether you built a or a hard window. Redis-cluster limiting belongs on the related System Design note.