# Rate Limiter — decision log

The Phase 5 answer key. Every entry is a question an interviewer actually asks — *"why is the clock
injected?"*, *"what exactly does the lock protect?"*, *"why isn't that an `AtomicLong`?"* — and the
answer that earns the mark: **what change or failure the decision anticipates, and what it would cost
without it.**

Nine files, none of them big. `RateLimiter` is the largest at just over 200 lines including javadoc
and is the only class that touches more than one budget; `RateLimitAlgorithm` is a three-method
interface with no implementation of its own.

| File | One reason to change |
|---|---|
| `RateLimiter` | how budgets are stored, how locks are taken, or how the commit is sequenced changes |
| `KeyBudget` | what one key's state is, or what guards it, changes |
| `RateLimitAlgorithm` | the operations a counting rule has to support change |
| `FixedWindowAlgorithm` | the fixed-window convention itself changes |
| `TokenBucketAlgorithm` | the refill or burst convention itself changes |
| `AlgorithmFactory` / `StandardAlgorithms` | which class enforces which `Algorithm` constant changes |
| `Scopes` | *whose* budgets a request has to satisfy changes |
| `Availability` | what one rule reports about one request changes |
| `RateLimiterApi`, `Algorithm`, `Rule`, `ClientKey`, `Decision`, `Clock`, `ManualClock`, `Entry` | given by the contract, not ours to change |

---

## The injected clock, which is the reason this problem exists twice in the corpus (C3, F5)

Every rule a rate limiter enforces is a rule about time: a hundred a minute, a bucket refilling over
ten seconds, a denial that reports how long to wait. **None of it is observable without controlling
time.** A limiter that calls `Instant.now()` can be tested in exactly one way — by sleeping — and a
suite that sleeps for a minute to watch one window roll over is a suite nobody runs twice. All 28 base
tests drive a `ManualClock` and not one of them sleeps; the whole base suite finishes in under two
seconds.

The design consequence is not "pass a clock in and be done". It is **where the clock is read**:

- `RateLimiter.tryAcquire` and `RateLimiter.remaining` each call `clock.now()` **exactly once**, on
  their first line, and pass that one `Instant` to everything downstream. That is the only place in
  the codebase that reads a clock.
- `RateLimitAlgorithm`'s stated terms **forbid** an implementation from reading a clock at all. The
  instant arrives as a parameter.

Why that matters, and it is the answer to *"couldn't each algorithm just read the clock itself?"*: a
key with an hourly rule and a per-second rule must be judged at **one** instant, or a request can be
inside one window and outside another at the same time, and a `Decision` assembled from two different
readings is not a decision about anything. Reading it in one place makes that structural instead of
something every algorithm has to remember. It is also why the fixed window keeps no "when did this
window start" field: the window is `floorDiv(nanosSinceEpoch, windowNanos)`, a function of the instant
alone, so two limiters started an hour apart agree about where the boundaries are and a restart does
not silently hand everybody a fresh allowance.

**And why the instant is not a parameter on `tryAcquire` instead** — the question worth having an
answer to, since passing an `Instant` in would also be testable. Three reasons, all in `Clock`'s
javadoc: the invariant stops being yours ("this client gets a hundred a minute" becomes "…provided
every caller passes an honest timestamp", and a limiter is precisely a device for not trusting the
caller); one request must see one instant, which a parameter makes the caller's job; and monotonicity
becomes enforceable in one place rather than being a question every bucket has to answer about what a
negative elapsed period means.

---

## Concurrency, because the ceiling is the whole point (E1, E2, E3, E4)

### The shared mutable state, named out loud

Two pieces, and **telling them apart is most of the design**:

1. **The map from key to budget.** Mutated by `configure` and `reset`, read by every request. What has
   to be atomic here is a *single-entry replacement* — which is exactly what a `ConcurrentHashMap`
   gives. Publishing a new `KeyBudget` through it is also a **safe publication**, so a thread that
   reads the new reference is guaranteed to see a fully constructed budget.
2. **The algorithm instances inside each budget.** Guarded by that budget's own `ReentrantLock`.

There is **no lock in `RateLimiter`**: the map does not need one and the budgets bring their own.

### Why the counters are not an atomic, which is the trap

The unit that must be atomic is not one counter update. It is **check every rule, then charge every
rule** — several reads and several writes across several objects, all of which must see the same
instant and none of which may be charged if any of them refuses. **No concurrent collection and no
`AtomicLong` can express that.** A candidate who reaches for `AtomicLong` here is not being slightly
sub-optimal; he is solving a different problem confidently. This is the decision to be able to defend,
not the absence of one.

That is also why `KeyBudget` exposes `lock()`/`unlock()` instead of making every method
`synchronized`. A single request may need **several** budgets at once — `Scopes` decides how many —
and check-then-charge across them is only atomic if every one is held for the whole of it. A budget
cannot know what else is in the set, so it cannot order the acquisition. `RateLimiter` can, and does,
in one method. The precondition is checked rather than trusted (`requireLocked`), because a missed
lock produces lost updates under load and passes every single-threaded test — and it throws
`AssertionError`, deliberately **not** `IllegalStateException`, because the contract promises the API
never throws that and this can only fire in response to a bug in this file.

### Lock granularity and order

One lock **per key**, not per process. Two keys have nothing in common and must not queue behind each
other; a limiter with one global lock becomes the bottleneck it was installed to prevent.

`RateLimiter.locked(List, Supplier)` is the only code in the design that acquires more than one lock,
and it takes them **strictly in the order `Scopes` returned** — which that interface documents must be
globally consistent — releasing in reverse and counting what it actually acquired, so a failure
part-way through leaves nothing held. One method, one order, no cycle.

**The honest qualification:** with `Scopes.own()` returning one key, a request takes exactly one lock,
so in the base problem a cycle is *unreachable* rather than *avoided*. The discipline is written down
anyway because the day it returns two is the day it would otherwise have to be invented under
pressure — and curveball 02 is that day. It turns on a shared backstop cap, every request then holds
two locks for the whole of check-then-charge, and its own test runs 128 threads across two callers
specifically so that an emergent order **hangs** rather than merely returning a wrong number.

### What the stress suite actually proves, and what it cost to make it prove anything

Four scenarios, and the clock is **frozen** for the whole of every collision. That is what makes the
numbers exact rather than statistical: with a stopped clock, "k units available" means *precisely* k
allowed, and any other integer is a bug. Against a wall clock every thread would arrive at a slightly
different instant and a lost update would be indistinguishable from a legitimate refill.

Two deliberately broken variants of this reference were built to check the suite earns its place, and
**both pass the base suite 28/28** — which is the entire point of having a stress suite at all:

- **No lock across check-then-charge** (`locked` reduced to `return body.get()`): caught on **10 of 10**
  independent runs at the shipped parameters, by three of the four scenarios independently. WIDE — at
  a single collision with only 8 threads it was still caught 9 times out of 10.
- **A plain `HashMap` for the budgets**: caught on **10 of 10** runs, by scenario 4 and only scenario 4,
  while scenario 4 passes every time on the first variant. The two bugs are cleanly separated, so the
  suite says *which* mistake was made.

A pleasing side effect worth pointing at, because it is invariant placement paying for itself: several
of the observed failures on the first variant were not assertions at all but
`IllegalArgumentException: remaining cannot be negative, got -3` thrown by **`Decision`'s own compact
constructor**. Putting the consistency check in the value type meant a torn count could not be quietly
reported, and the suite got that for free rather than needing a checker for it.

**One measurement was discarded rather than reported.** An early sweep point at `CROWD = 4` appeared
to catch the unlocked variant 10/10 — but scenario 1 derives its limit as `CROWD / 8`, so at 4 threads
the limit is 0 and `Rule` refuses it outright. The *correct* reference "failed" 5/5 there too. That
row was a false positive of the sweep harness, not a detection, and a catch rate measured against a
suite that also fails good code is worth nothing. The real floor is `CROWD = 8`.

---

## The algorithm seam, and why it is two seams and not one (B1, B2, C1, C2)

`Algorithm` is a contract **enum with no behaviour on it** — a selector. Where the behaviour lives is
the design decision, and it is split deliberately across two interfaces, because two questions look
like one and are not:

- *How does a fixed window count?* → `RateLimitAlgorithm`, one implementation per behaviour.
- *Which class counts a `FIXED_WINDOW` rule?* → `AlgorithmFactory` / `StandardAlgorithms`, an
  `EnumMap` of `Rule → RateLimitAlgorithm` functions.

Collapsing them means a `switch (rule.algorithm())` somewhere, and the natural somewhere is
`KeyBudget` — **the class that owns the locking and the all-or-nothing commit**, the one place in this
design where a careless edit is a correctness bug rather than a behaviour change. Keeping the mapping
as *data* means the class that assembles budgets never learns how many algorithms exist.

Two supporting choices worth defending: an `EnumMap` rather than a `HashMap` because the key is an
enum, so it is an array lookup with no hashing and no iteration-order surprises; and a
`Function<Rule, RateLimitAlgorithm>` rather than a prototype to clone, because an algorithm built from
its own `Rule` cannot later be given the wrong limit. And a **missing registration throws, naming the
constant** — the alternative, falling back to "allow everything", would turn a one-line omission into
a silently unlimited client, which is the worst failure this component has.

**Curveball 01 is the measurement that checks the claim rather than repeating it:** a sliding-window
log is a third, unrelated implementation of the same three methods, and it measured
`reference_diff = 1` — the single `implementations.put(...)` line whose whole job is to be the only
line.

### Why `check` and `take` are two methods

Not API taste. It is what makes the contract's all-or-nothing rule **expressible at all**. A single
`tryTake()` would charge the first rule before discovering the second refuses, which is exactly the
leak the contract forbids: under load the loose hourly quota evaporates without one request getting
through. The base suite's `evaluationIsAllOrNothing` and the stress suite's second scenario both check
the consequence directly, the second one under 200 threads.

`Availability` is a value and not a boolean for a related reason: the wait is only computable at the
moment of the check — a fixed window knows where its boundary is, a bucket knows its deficit and refill
rate — and neither fact is recoverable afterwards from outside. Returning the boolean alone would force
the caller to ask a second question only the algorithm can answer, which is how one seam becomes two
that have to agree. It is deliberately **not** a `Decision`: this is one rule's opinion, and a
`Decision` is the answer to the whole request. Collapsing them would mean every algorithm knowing about
all the others.

---

## The token bucket's balance, which is the one genuinely subtle piece of arithmetic (A5)

A continuous refill means fractional tokens, and the two obvious ways of holding a fraction are both
wrong:

- **A `double` drifts.** Add `1.0/3` three times and you do not have one token. An allowance that
  quietly erodes over a week is a bug nobody can reproduce.
- **Whole tokens refilled once per `window/limit` discards the remainder.** Three refills of a third of
  a token each add up to nothing, so a bucket refilled by anything other than exact multiples of its
  tick loses budget.

So the balance is held in **token·nanoseconds**: one token is `windowNanos` units. Refilling for `e`
nanoseconds adds exactly `e × limit` — integer, exact, no division, no drift; spending subtracts
`windowNanos`; whole tokens available is `credit / windowNanos`, and the remainder **stays in the
bucket**. `tokenBucketCarriesFractions` in the base suite is the test that fails every implementation
that rounds each fragment down.

And this is why `Rule` refuses a rule whose `limit × window` overflows a `long` of nanoseconds. That
invariant lives in the **contract**, not in the algorithm, because it is precisely the bound inside
which this representation stays exact — it looks like an implementation detail and is not, and refusing
the rule is far better than silently drifting.

Two smaller decisions in the same class: elapsed time is **clamped to one window before it is
multiplied**, because more than a window's idleness fills the bucket anyway and clamping first is what
keeps `elapsed × limit` inside a `long` after a fortnight's silence; and refill is **lazy, on the way
past**, with no timer, because a `ScheduledExecutorService` ticking every bucket would do work
proportional to the number of *idle* keys and would make the answer depend on when the scheduler ran
rather than on what the clock says.

---

## Reconfiguration is a swap, not an edit (A7, D3)

`configure` builds a **whole new `KeyBudget`** and puts it in the map. Three things fall out of that,
none of which had to be implemented:

- **"Atomic with respect to `tryAcquire`"** — a request holds one budget reference for its lifetime, so
  it sees the entire old rule set or the entire new one, never a mixture. This costs **no lock at all**:
  an immutable object published through a `ConcurrentHashMap` is safely published, and the reference
  read is a single field read.
- **"Discards the key's counters"** — the old counters live in the old budget, and the old budget is
  garbage.
- **A rejected rule list changes nothing**, because validation happens while building the new budget,
  before the map is touched.

`reset` is the same move with the same rules: `computeIfPresent`, so resetting a key nobody configured
does not invent a budget for it.

`rulesFor` returns the budget's own `List.copyOf` list **directly rather than copying again**, and that
is the interesting half of the immutability boundary: the list is already immutable, `Rule` is a record,
and the caller cannot reach anything mutable through it. The base suite checks both directions that
matter — adding to what was handed out throws, and a snapshot taken before a reconfiguration does not
change afterwards.

---

## Errors: three mechanisms, on purpose (D2)

- **A denial is a `Decision`, not an exception.** Being rate limited is the single most ordinary thing
  that happens to a rate-limited caller. An exception for it would make the normal path the exceptional
  one and cost a stack trace per denied request at exactly the moment the system is busiest.
- **`IllegalArgumentException` for configuration that could never make sense**, thrown from the value
  types themselves (`Rule`, `ClientKey`) so no invalid instance can exist, plus duplicate rule names in
  `KeyBudget.of` — because a denial naming a rule that matches two rules explains nothing.
- **Never `IllegalStateException`.** The contract states it as a promise: there is no state this API can
  be in that makes a well-formed request impossible. The reference keeps that promise even in its own
  internal precondition check, which is why `requireLocked` throws `AssertionError`.

---

## `Scopes`: the one genuine up-front bet, and how it settled (C2, E3)

This is the seam to be honest about, because when it was written it had **one implementation and one
line of body**. The price is stated in its javadoc before the benefit: a functional interface, a
one-line default, and returning a `List` where a single value would do.

The defence was never "I predicted a requirement". It was that the alternative to a list is a second
budget appearing as a second field somewhere, checked in a second place, **with an acquisition order
nobody wrote down**. The list is what makes the lock order a stated, total property of one object
rather than an emergent one, and the order is the part that would have been genuinely expensive to
retrofit.

**Curveball 02 settled the bet at `reference_diff = 0`** — a three-line `BackstopScopes` and a wiring
line in `Entry`. But the honest version of that story includes what writing it found:

> `remaining(key)` read `budgets.get(key)` directly instead of going through `scopeOf(key)`, while
> `tryAcquire` went through `Scopes` properly. Under `Scopes.own()` the two are indistinguishable — one
> budget or none either way — so **the base suite passed 28/28 with the bug in place**. Under a second
> scope it is plainly wrong: `remaining` would tell a caller they had 95 left and the very next
> `tryAcquire` would refuse them under a cap it had never consulted.

The fix went into `reference/src/RateLimiter.java` — route `remaining` through `scopeOf`, and extract
the "tightest figure across the scope" loop `decide` already contained into a `fewestRemaining` helper
both call — **before** curveball 02's baseline was measured, per the corpus rule to fix the reference
rather than the budget. Measured against the pre-fix code, the curveball would have cost **13 lines**
for the cheapest correct absorption or **20** done properly, and every one of them inside
`RateLimiter`. A seam honoured by one of the two methods that answer questions about it is not a seam;
it is a coincidence.

---

## A requirement that was measured and deliberately not shipped

**Weighted requests** — letting one call cost more than one unit — was built end to end as a candidate
third curveball, because it is the most realistic extension a real rate limiter gets. It was measured
and then dropped, and the number is the reason:

| | measured |
|---|---|
| `reference_diff` for weighted requests | **60** across 5 files |
| current corpus maximum (`middleware-router`, the documented "new dimension" case) | 47 |
| what shipped as curveball 03 instead | 19, one file |

The diagnosis is *not* that the seams are wrong. `RateLimitAlgorithm.check(Instant)` /
`take(Instant)` bake in one unit per request because the base contract lists "weights or costs other
than one unit per request" as out of scope **in writing**, and building the permits dimension in
advance would have been speculative generality of exactly the kind `Scopes`' javadoc goes out of its
way to justify not committing to twice. The unit of charge is a genuinely new dimension: every
algorithm must understand it (`used + permits <= limit`; `credit >= permits × windowNanos`), and the
retry arithmetic changes with it, since the wait for *n* tokens is not derivable from the wait for one.
There is no cheaper honest absorption — a design in which the interface never learns about permits
cannot report a positive wait for a request it can partially satisfy.

It was dropped anyway, on judgement rather than on the rule: at ~30 real edits across five files it
would be a typing exercise in a timed round, it would set a new corpus maximum by 28%, and
`middleware-router` already teaches the "new dimension" lesson at 47. Counting denials teaches
something this problem can teach uniquely instead — **counting a request-level event exactly once
across a multi-rule, multi-budget decision, under contention** — and lands at 19, inside the range
where the capped budget still discriminates.

---

## What is deliberately absent

- **No background thread, no timer, no scheduled refill.** Everything is brought up to date lazily on
  the way past. This is stated in the contract and it is load-bearing for testability: a timer would
  make the answer depend on when the scheduler ran.
- **No eviction of idle keys.** A `KeyBudget` per key lives for the life of the limiter. In a real
  system with unbounded keys this is a leak, and the right fix is a size-bounded or time-bounded map —
  which is `lru-cache`'s problem, not this one. Say so; do not build it.
- **No distribution, no shared store.** The first thing anyone says about a rate limiter, and out of
  scope on purpose. Worth being able to say *what breaks*: per-process buckets mean `n` instances admit
  `n × limit`, and the standard answers are a shared counter with its own atomicity or per-instance
  limits set to `limit / n` with the accompanying unfairness.
- **No `AtomicLong` for the rate-limit counters**, for the reason given above — and, instructively,
  `ConcurrentHashMap<ClientKey, AtomicLong>` **is** the right answer for curveball 03's denial count.
  Same problem, two different answers, because the unit that has to be atomic is a different size in
  each case. Being able to state that difference is what E2 and E4 are actually asking for.
- **No fixed-window smoothing.** The `2×limit` burst across a boundary is accepted, documented
  behaviour, not a defect. A fixed window that smoothed it would be a sliding window wearing a fixed
  window's name — and the sliding window is curveball 01.
