Syllabus · A5
Invariant placement — no invalid instance can exist
The idea
No invalid instance can exist
The distance between a validate() method and what an interviewer is scoring is one call somebody has to remember.
Take remaining on a rate limiter's answer: how many requests a caller has left. A check-then-charge with no lock across it means one thread checks at 97 used and charges at 103, so limit - used is -3. In contrast/a/, where each consumer checks what it reads, that -3 travels seven calls and nothing notices. The customer gets a 200, a header reading X-RateLimit-Remaining: -3, and 103% of quota used. No exception, no alert, no failing test.
Move the same rule into Decision's compact constructor and the identical bug throws after two calls, with remaining cannot be negative, got -3. The top frame is the type that owns the rule.
That is not a hypothesis. corpus/rate-limiter/reference/DECISION_LOG.md records it. While a stress suite was being proved against a broken variant, several failures arrived as Decision's own compact constructor throwing that message. Nobody had written a test for it.
The message is part of the invariant. IllegalArgumentException: -3 names neither the field nor the value, and you read it at 1am.
Some invariants need no if. Algorithm.FIXED_WINDO is a build failure reading cannot find symbol, where "fixed_windo" is a perfectly good String. That is placement by type, and the compiler does it for nothing.
Refuse rather than repair. contrast/b-normalising/ clamps the -3 to zero, detects nothing, and costs 8 lines more than having no invariant at all.
Worked walkthrough
NOTES — seven files, twelve refusals, and one bug nobody wrote a test for
Compile and run from the directory holding the sources:
..\..\..\.toolchain\jdk-21\bin\javac.exe -d out *.java
..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Mainjavac -Xlint:all exits 0 and prints nothing. Real output, from exactly this code:
== What a valid budget looks like ==
rules [hourly, burst]
remaining after 3 requests 2
refused after 5 requests [burst]
allowed(2) Decision[allowed=true, remaining=2, deniedBy=, retryAfter=PT0S]
denied("burst", 200ms) Decision[allowed=false, remaining=0, deniedBy=burst, retryAfter=PT0.2S]
== One field at a time ==
ClientKey.of(" ") java.lang.IllegalArgumentException
a client key cannot be blank
Rule.fixedWindow("hourly", 0, 1h) java.lang.IllegalArgumentException
rule hourly: limit must be at least 1, got 0
Rule.fixedWindow("hourly", 100, PT0S) java.lang.IllegalArgumentException
rule hourly: window must be positive, got PT0S
Rule.tokenBucket("firehose", 10_000_000_000, 1h) java.lang.IllegalArgumentException
rule firehose: limit 10000000000 over PT1H is too large to count exactly in nanoseconds
== Four fields that have to agree ==
Decision.allowed(-3) java.lang.IllegalArgumentException
remaining cannot be negative, got -3
new Decision(true, 97, "burst", PT0S) java.lang.IllegalArgumentException
an allowed request was not denied by burst
new Decision(true, 97, "", PT2S) java.lang.IllegalArgumentException
an allowed request has nothing to wait for, got PT2S
Decision.denied("", PT2S) java.lang.IllegalArgumentException
a denial must name the rule that refused
Decision.denied("burst", PT0S) java.lang.IllegalArgumentException
a denial must say when to come back, and it must be later than now, got PT0S
new Decision(false, 97, "burst", PT2S) java.lang.IllegalArgumentException
a denied request has nothing remaining, got 97
== An invariant that spans a collection ==
Budget.of(acme, [hourly, hourly]) java.lang.IllegalArgumentException
client acme has two rules called hourly; a denial naming that rule would not say which one refused
Budget.of(acme, [hourly, null]) java.lang.NullPointerException
rule at index 1 for client acme
budget.rules().add(hourly) java.lang.UnsupportedOperationException
(no message)
== Closed type versus checked value ==
Algorithm.valueOf("FIXED_WINDO") java.lang.IllegalArgumentException
No enum constant Algorithm.FIXED_WINDO
RuleByString("hourly", "fixed_windo", ...) java.lang.IllegalArgumentException
rule hourly: unknown algorithm "fixed_windo", expected one of [FIXED_WINDOW, TOKEN_BUCKET]
RuleByString("hourly", "fixed_window", ...) java.lang.IllegalArgumentException
rule hourly: unknown algorithm "fixed_window", expected one of [FIXED_WINDOW, TOKEN_BUCKET]
Rule("hourly", Algorithm.FIXED_WINDOW, ...) built, and no typo was reachable to check for
== A concurrency bug caught by a value type ==
limit 50, 256 threads, no lock across check-then-charge
allowed more requests than the limit permits: true
torn counts refused by Decision's constructor: true
a message from this run: remaining cannot be negative, got -64Two lines in there are the lesson. remaining cannot be negative, got -3, which names the field and the value. And the last one, which is the same message arriving from a code path no test in this lesson covers.
The negative number in that last line differs on every run. That it is negative does not.
Decision.java — four fields, one consistent answer
public record Decision(boolean allowed, long remaining, String deniedBy, Duration retryAfter) {A record, so every component is final and the guarantee travels with the object. J4 covered the mechanics: final fields, one assignment, javac proving it. The design consequence is what matters here. A Decision handed to a logger, a header writer and a metrics counter is the same Decision in all three, so a check that ran once covers all three forever. Make one component mutable and the check covers only the instant it ran in.
public Decision {
Objects.requireNonNull(deniedBy, "deniedBy");The compact constructor, which runs before the fields are assigned. No caller can reach a Decision that skipped it, including a caller written next year who never read this file. That is the whole claim of A5. It is also the difference from a validate() method, which has to be called, and no compiler will tell you it was not.
requireNonNull returns its argument, so a check and an assignment can be one statement. Here it is the check alone, because a record's compact constructor assigns the fields for you.
if (remaining < 0) {
throw new IllegalArgumentException("remaining cannot be negative, got " + remaining);
}The message is part of the invariant, not decoration on top of it. `IllegalArgumentException: -3` names neither the field nor the type. This message names both the field and the value, so the person reading it at 1am has the whole fact in one line. contrast/ measures what the alternative costs.
Why refuse rather than clamp. remaining = Math.max(0L, remaining) also compiles, also stops the negative escaping, and reads as the considerate thing to do. It destroys the only evidence that a counter was charged twice for one request. The torn count becomes an ordinary "you have nothing left" denial and nobody ever finds out. when-not.md has the measurement.
if (allowed) {
if (!deniedBy.isEmpty()) {
throw new IllegalArgumentException("an allowed request was not denied by " + deniedBy);
}Cross-field, which is the kind of invariant a field-by-field check cannot express. Each of the four values is legal on its own. deniedBy = "burst" is a fine string and allowed = true is a fine boolean, and together they are nonsense: something both passed and was refused. A validate() per field would pass this. Only a check that sees all four at once catches it.
The bug it prevents is a caller reading deniedBy to build an alert. With this combination representable, an allowed request raises a "burst limit exceeded" page.
if (!retryAfter.isZero()) {
throw new IllegalArgumentException(
"an allowed request has nothing to wait for, got " + retryAfter);
}This one has a downstream cost with a name. A client that honours Retry-After sleeps for it. An allowed decision carrying two seconds means every successful request pauses. Throughput drops and no error is logged anywhere.
if (retryAfter.isZero() || retryAfter.isNegative()) {Both halves, and isZero() is the one that gets dropped. A denial with Duration.ZERO tells the caller to retry immediately, which produces a hot loop against a limiter that is already refusing. Writing isNegative() alone compiles and passes any test that only checks negatives. faded/GapTest.java asserts the zero case for this reason.
if (remaining != 0) {
throw new IllegalArgumentException(
"a denied request has nothing remaining, got " + remaining);
}A policy decision wearing an invariant's clothes, and worth knowing that about it. "A rule denies precisely when it has nothing left" is this problem's convention, quoted from corpus/rate-limiter/contract/Decision.java. It is true of this design and it is not a law of nature. when-not.md measures what happens when a requirement asks a denial to report a non-zero figure, because that is where a constructor-placed rule bites back.
public static Decision allowed(long remaining) {
return new Decision(true, remaining, "", Duration.ZERO);
}Two factories, and between them they make three of the four fields unspecifiable. A caller cannot pass deniedBy to allowed or a non-zero remaining to denied, so most of the invariant is enforced by the shape of the call rather than by a check inside it. The compact constructor stays anyway, because new Decision(...) is still public on a record and the concurrency path in Main goes through allowed.
Rule.java — four per-field invariants, and one that looks like a detail
Objects.requireNonNull(algorithm, "algorithm");One line, and no membership check anywhere. There is no value of type Algorithm that is not FIXED_WINDOW or TOKEN_BUCKET, so the set was closed before this constructor ran. Compare RuleByString below, which needs four lines and a second copy of the constant list to reach a weaker version of the same guarantee.
if (limit < 1) {
throw new IllegalArgumentException("rule " + name + ": limit must be at least 1, got " + limit);
}Every message in this class starts with the rule name. A limiter holds several rules per caller. limit must be at least 1, got 0 would leave you grepping a config file. rule hourly: ... does not.
A limit of zero is a configuration mistake, not a rule that denies everything. That reading is stated in the corpus contract, and it is the sort of thing an interviewer asks about. "Deny everything" is a different feature and belongs somewhere a reader can see it.
try {
Math.multiplyExact(limit, window.toNanos());
} catch (ArithmeticException overflow) {The invariant that looks like an implementation detail and is not. A token bucket carries fractional tokens by holding its balance in token-nanoseconds, so one token is windowNanos units. That representation is exact only while limit × window fits in a long. Past that bound the arithmetic drifts, and an allowance that erodes over a week is a bug nobody can reproduce.
Refusing the rule at construction converts an unreproducible drift into a startup failure with a message. Math.multiplyExact is doing the work: it throws on overflow, where limit * nanos would wrap silently. Writing the check against window.toSeconds() instead compiles and lets the overflowing rule through, which is one of the wrong answers faded/GapTest.java catches.
ClientKey.java — the one-invariant case, and why it is still a type
public record ClientKey(String value) {
public ClientKey {
Objects.requireNonNull(value, "value");
if (value.isBlank()) {isBlank(), not isEmpty(). A key of " " is a caller nobody can identify, and it reaches a map as a perfectly good key. isEmpty() compiles, passes a test written with "", and lets the whitespace key through.
The invariant here is thin and the type still pays. Everything in a rate limiter is keyed by this value, and a rule name is also a String. A method taking two bare strings is a call the compiler cannot check, and swapping the arguments produces a limiter that works and limits the wrong thing. lru-cache makes the opposite trade honestly: its problem.json calls A5 "the honest weakest tag on this problem", because one positive-capacity check is all its contract gave it a place to put. One invariant does not earn ceremony. This one earns a record and eight lines.
Algorithm.java and RuleByString.java — placement by type, not by if
Both files carry the same fact: which of two counting conventions a rule uses. One of them cannot be got wrong.
Write the typo against the enum and the build stops:
> javac -d out *.java
Typo.java:5: error: cannot find symbol
return new Rule("hourly", Algorithm.FIXED_WINDO, 100L, Duration.ofHours(1));
^
symbol: variable FIXED_WINDO
location: class Algorithm
1 errorWrite the same typo against the string and it compiles, because "fixed_windo" is a valid String. The best that placement can then do is refuse at runtime:
rule hourly: unknown algorithm "fixed_windo", expected one of [FIXED_WINDOW, TOKEN_BUCKET]That is a good message and it arrives late. Three further costs come with it:
private static final List<String> KNOWN = List.of("FIXED_WINDOW", "TOKEN_BUCKET");KNOWN is a second copy of the constant set, kept in step by hand. Add a sliding-window algorithm and forget this line, and the new rule is refused by a check that was meant to help. Forget the check entirely and the rule is accepted and never counted.
Matching is a question the enum never posed. "fixed_window" in lower case is refused, as the run above shows. Whether that is right is now a decision somebody has to make, defend and test. The enum has no such case to consider.
There is nothing to switch on exhaustively. switch over Algorithm with no default stops compiling when a third constant arrives, at the place a decision is owed. A switch over strings compiles forever and falls through.
This is what "invariant placement" means beyond constructors. Some invariants are placed in a type, where the compiler holds them for nothing.
The same trade appears wherever the corpus has a closed set. corpus/parking-lot/contract/VehicleType.java is three constants on one line, and MOTORBKE does not compile. corpus/vending-machine/contract/Coin.java says it outright in its javadoc: the enum is the accepted set, so insertCoin has no bad-coin failure mode to handle or to test.
Budget.java — an invariant across a collection
private final ClientKey key;
private final List<Rule> rules;
private Budget(ClientKey key, List<Rule> rules) {A private constructor, and it is the only writer of either field. So there is one place to look when a budget is wrong, and no caller can build one that skipped of. J4 covered the mechanism; what it buys here is that the duplicate-name check below has no way around it.
for (int i = 0; i < rules.size(); i++) {
Objects.requireNonNull(rules.get(i), "rule at index " + i + " for client " + key);
}
List<Rule> copy = List.copyOf(rules);The loop runs before List.copyOf, and that ordering is the whole point of the loop. List.copyOf already refuses a null element. It refuses it with no message at all, which the run above shows as (no message) for the unmodifiable case. This loop names the index and the client, so the output reads rule at index 1 for client acme. Reverse the two statements and the message is gone, because copyOf throws first.
List<Rule> copy = List.copyOf(rules);copyOf is what makes final on the field mean anything. final stops the reference being repointed and says nothing about the list. Store the caller's ArrayList and the caller can add a duplicate name a second after the check passed. The invariant would then hold for one instant rather than for the object's life, which is a different and much weaker promise.
The run shows the other half: budget.rules().add(hourly) throws UnsupportedOperationException, so rules() can hand the field out with no copy per call.
Set<String> seen = new HashSet<>();
for (Rule rule : copy) {
if (!seen.add(rule.name())) {Set.add returning false is the duplicate test, so the loop is one pass. The invariant is a property of the whole list rather than of any element, so no Rule constructor could hold it. The bug it prevents is stated in the message: a denial reporting hourly when two rules are called hourly explains nothing, and the operator reading it cannot tell which quota was hit.
This is the rule KeyBudget.of enforces in corpus/rate-limiter/reference/DECISION_LOG.md, for that reason.
public long remaining(long usedSoFar) {
long fewest = Long.MAX_VALUE;
for (Rule rule : rules) {
fewest = Math.min(fewest, rule.limit() - usedSoFar);
}No clamp, deliberately. Math.max(0L, rule.limit() - usedSoFar) here would look careful and would swallow the signal. A subtraction that goes negative means the counter was charged more times than requests were allowed. Letting it through to Decision is what turns that into a thrown exception naming the field and the value.
A key with no rules returns Long.MAX_VALUE, which is this problem's way of writing unlimited. That is a convention, so it is stated rather than inferred.
The last block of output, which nobody designed
Main.theTornCount runs 256 threads through a check-then-charge with the counter atomic and no lock held across the two steps. The counter loses nothing. The decision does: a thread checks while units remain, other threads charge, and by the time it charges the budget is gone.
Nothing in that method asserts anything about remaining. There is no test for it. The refusal comes from Decision's constructor, and the message names the field and the value:
remaining cannot be negative, got -64This is not a scenario invented for the lesson. It happened during the corpus's own authoring, and corpus/rate-limiter/reference/DECISION_LOG.md records it:
several of the observed failures on the first variant were not assertions at all but
IllegalArgumentException: remaining cannot be negative, got -3thrown byDecision's own compact constructor.
The log's own reading of it. Putting the check in the value type meant a torn count could not be reported quietly. The suite got that without needing a checker of its own.
That is the argument for placement at construction in its strongest form. The check was written to stop a nonsense header. It caught a concurrency bug in a different file, in a code path its author was not thinking about, years of code later in the general case. A validate() method could not have done it, because nobody would have called it there.
When not to
When not to put the invariant in the constructor
STANDARD v1.0's D5 level 3 reads "failure modes named in the code's structure — impossible states unrepresentable rather than merely checked". That sentence is what this lesson teaches toward, and it is also the sentence people over-read. Level 3 asks for the states that matter to be unrepresentable. It does not ask for every field to be interrogated on the way in.
There is no over-validated tag in the rubric, so nothing in the grader will tell you off for this. The bill arrives in three other places instead, and the third one is the expensive one.
1 · A check the type already made
Algorithm is an enum. There is no value of that type outside its constants, so a membership check against them is dead code. Here is that check, written by somebody being careful. Put it next to worked/src/Algorithm.java and it compiles: javac 21 with -Xlint:all prints nothing and exits 0.
public record NoisyRule(String name, Algorithm algorithm, long limit, Duration window) {
public NoisyRule {
Objects.requireNonNull(name, "name");
Objects.requireNonNull(algorithm, "algorithm");
Objects.requireNonNull(window, "window");
if (algorithm != Algorithm.FIXED_WINDOW && algorithm != Algorithm.TOKEN_BUCKET) {
throw new IllegalArgumentException("rule " + name + ": unknown algorithm " + algorithm);
}
if (name.length() < 0) {
throw new IllegalArgumentException("rule " + name + ": a name cannot have negative length");
}
if (window.toNanos() != window.toNanos()) {
throw new IllegalArgumentException("rule " + name + ": the window changed while we read it");
}
}
}Two of those three branches can never run. String.length() is never negative and Duration is immutable, so both conditions are constant false. javac says nothing about either, which is why they survive review.
The first branch is worse, because it can run, and the day it does it is wrong. Add a third constant to Algorithm and this is the real output:
NoisyRule[name=hourly, algorithm=FIXED_WINDOW, limit=100, window=PT1H]
threw java.lang.IllegalArgumentException
rule burst: unknown algorithm SLIDING_WINDOW
Rule[name=burst, algorithm=SLIDING_WINDOW, limit=5, window=PT1S]Rule accepts the new algorithm without being touched. NoisyRule refuses it, using the message that was meant to be protective. A membership check over a closed type is not neutral. It is a future bug with a helpful tone.
The corpus states the same restraint in corpus/vending-machine/contract/Coin.java:
The enum is the accepted set: there is no such thing as a coin the machine does not recognise, so
insertCoinhas no "bad coin" failure mode.
corpus/lru-cache/problem.json makes the honest version of the point about scale. It calls A5 "the honest weakest tag on this problem", because the only invariant its design has is a positive capacity, checked once in a constructor. One scalar check with no ceremony round it is the right answer there. Adding a validation layer to reach level 3 would have made that design worse.
2 · A rule that is not a property of the type
Three questions decide whether a rule belongs in a constructor. The interesting failures are the ones that fail exactly one.
Does it hold for every instance, or only for some callers? "remaining is never negative" holds for every decision. "Enterprise tenants may go 1000 into overdraft" does not. Put the second one in the constructor and it has no access to the tenant, so the rule has to be widened into a parameter or dropped. Both of those edits touch the type, every factory on it and every construction site.
Does it hold for the object's whole life, or only at one instant? A Slot in corpus/vending-machine/contract/Slot.java refuses a negative quantity, and that is a property of a snapshot. "This slot has stock" is not, and it is the machine's business rather than the value's.
Can it be decided from the arguments alone? A uniqueness check against a database cannot. A constructor that opens a connection is a much bigger problem than the invariant it was enforcing.
The concrete cost: a caller who only wanted to look
An operator console lets somebody type a rule field by field and underlines what is wrong as they go. Rule cannot hold that state, because it refuses to exist until all four fields are right. So a second type appears. This compiles next to worked/src/Rule.java, -Xlint:all clean:
public final class RuleForm {
private String name;
private Algorithm algorithm;
private Long limit;
private Duration window;
/** The same rules again, so the form can underline one field at a time. */
public List<String> problems() {
List<String> found = new ArrayList<>();
if (name == null || name.isBlank()) found.add("name is required");
if (algorithm == null) found.add("algorithm is required");
if (limit == null) found.add("limit is required");
else if (limit < 1L) found.add("limit must be at least 1");
if (window == null) found.add("window is required");
else if (window.isZero() || window.isNegative()) found.add("window must be positive");
return List.copyOf(found);
}
public boolean submittable() { return problems().isEmpty(); }
public Rule toRule() { return new Rule(name, algorithm, limit, window); }
}Nothing about that is unreasonable, and a real admin console needs it. The cost is that one rule set now exists twice, and the two copies drift. Real output, and note the last two lines:
empty form [name is required, algorithm is required, limit is required, window is required]
name typed [algorithm is required, limit is required, window is required]
all four typed []
submittable true
toRule() threw rule firehose: limit 10000000000 over PT1H is too large to count exactly in nanosecondssubmittable says yes. The constructor says no. The form's author copied three of Rule's four invariants and missed the overflow one, so the console offers a Save button that always fails. The operator has no way to tell what is wrong, because the form is the thing that was supposed to say.
The fix is not to drop the constructor check. It is to make RuleForm.problems() call one shared predicate that the constructor also calls, so the rule exists once. What this costs is the extra public surface, and it is a real cost worth naming out loud when an interviewer asks.
3 · An invariant that repairs instead of refusing
This is the one that measures worse than having no invariant at all, and contrast/ measures it.
contrast/b-normalising/Decision.java puts the checks in exactly the place b/ does. It differs in one respect: it clamps remaining to zero and substitutes a one-second wait, rather than throwing. That is the change a reviewer asks for after a negative Retry-After has caused an incident.
From node lessons/A5/contrast/measure.mjs:
| Scenario | a/ no invariant | a-validate/ method | b/ refuses | b-normalising/ repairs |
|---|---|---|---|---|
torn count, remaining = -3 | never detected, 7 calls | never detected, 7 calls | 2 calls | never detected, 7 calls |
| stale window boundary, via the responder | 6 calls | 3 calls | 2 calls | never detected |
| stale window boundary, via the caller | 5 calls | 3 calls | 2 calls | never detected |
| size | 114 normalised lines | 127 | 124 | 122 |
Read the audit lines, not the counts. In a/ the log records remaining=-3, which a human can find and reason about. In b-normalising/ it records remaining=0 and a response of 100% of quota used, which is what an honestly exhausted quota looks like. The evidence is gone.
b-normalising/ costs 8 more lines than a/ and detects less. It is the only one of the four designs where a torn count leaves no trace anywhere.
The same thing happens to the retry hint. The fallback wait is one second, so a caller holding a stale window boundary sleeps for a second nobody asked for and retries. No error, no log line, and the boundary is still stale.
4 · The clock
A validation pass over a type nobody asked you to validate is time. STANDARD v1.0 caps D2 at 0 when no main exists, on the grounds that "interviewers run it first", and D2 is 25% of the score against D5's 10%. Four unreachable checks and a form class are not worth a missing driver.
The corpus's own strongest A5 showcase is small. corpus/rate-limiter/contract/Decision.java is one compact constructor. ClientKey is one check. Rule is four. corpus/rate-limiter/problem.json calls A5 "strong here, and spread across four types rather than concentrated in one", and none of those four types is large.
The threshold
Put the rule in the constructor when all three of these hold.
- It holds for every instance of the type, not for some callers.
- It holds for the object's whole life, not at one instant.
- It can be decided from the constructor's arguments alone, with no I/O and no context.
Fail any one of the three and the rule belongs somewhere the caller can see it: a policy object, a service method, or a documented precondition. Tenant overdraft fails the first. Stock levels fail the second. A uniqueness check against a store fails the third.
Then, inside the constructor, refuse rather than repair. If you would not be willing to throw, the value is not an invariant. It is a default, and a default belongs in a named static factory where the call site says what was assumed.
And do not check what a type already closes. An enum, a sealed hierarchy or a record component that cannot be null needs a null check at most. A membership check over a closed set is a bug waiting for the set to grow.
The contrast pair
The measured set: one bad value, four designs, and the distance it travels
Four designs of the same rate limiter. All four answer identically while the inputs are honest, and BaseTest.java passes against all four. The comparison is between working designs.
a/puts the checks at the point of use. Each consumer validates what it reads.a-validate/puts the same rules in aDecision.validate()method, andLimitercalls it on the deny path.b/puts them inDecision's compact constructor. No consumer validates anything.b-normalising/puts them in the same constructor and has them repair the value instead of refusing it.
The instrument is not diff size. For an invariant the question is how far a bad value gets before anything notices, so Probe.java counts the calls and reports what the thing that noticed said.
The moment this measures, in an interviewer's words
Two threads hit the same key. Your check-then-charge is not under one lock, so one of them checks while 97 requests are counted and charges when 103 are. What does your API return for that request?
That is not a hypothetical. It is the bug the rate-limiter stress suite was built to catch, and corpus/rate-limiter/reference/DECISION_LOG.md records how it surfaced:
several of the observed failures on the first variant were not assertions at all but
IllegalArgumentException: remaining cannot be negative, got -3thrown byDecision's own compact constructor.
Nobody wrote a test for that. The value type refused the value.
The numbers
Run it yourself:
node lessons/A5/contrast/measure.mjsReal output, from exactly these directories:
a BaseTest 2/2 InvariantTest 0/2
a-validate BaseTest 2/2 InvariantTest 0/2
b BaseTest 2/2 InvariantTest 2/2
b-normalising BaseTest 2/2 InvariantTest 0/2BaseTest.java is the shared behaviour. InvariantTest.java is the suite that separates the four, and both of its assertions are about construction alone. No consumer appears in either, so a design that checks at the point of use cannot pass by being careful somewhere else.
| Scenario | a/ point of use | a-validate/ method | b/ constructor | b-normalising/ repairs |
|---|---|---|---|---|
torn count, remaining = -3 | never detected, 7 calls | never detected, 7 calls | 2 calls | never detected, 7 calls |
| stale boundary, through the responder | 6 calls | 3 calls | 2 calls | never detected |
| stale boundary, through the retrying caller | 5 calls | 3 calls | 2 calls | never detected |
| size | 114 normalised lines | 127 | 124 | 122 |
The two calls in b/ are Limiter.decide and Decision.allowed. The second one is the throw.
Scenario 1, the torn count, in full
a/, unedited:
scenario 1 torn count: checked at 97 used, charged at 103, limit 100
detected no
calls 7 [Limiter.decide, Decision.allowed, Limiter.audit, Responder.respond, Responder.status, Responder.headers, Responder.body]
outcome audit [rule=hourly allowed=true remaining=-3 retryAfter=PT0S] response [200 OK | X-RateLimit-Remaining: -3, Retry-After: 0 | 103% of quota used]Nothing threw. The customer got a 200, a header saying they have minus three requests left, and a usage figure of 103%. The audit line is already written. There is no exception, no alert and no test failure anywhere in the system.
b/, unedited:
scenario 1 torn count: checked at 97 used, charged at 103, limit 100
detected yes, after 2 call(s)
calls [Limiter.decide, Decision.allowed]
threw java.lang.IllegalArgumentException
message remaining cannot be negative, got -3
blamed Decision.<init>(Decision.java:15)Two calls, and the top frame is the constructor of the type that owns the rule. The audit line was never written, because the decision never existed.
That is the claim of A5 in one pair of outputs. The same wrong number, produced by the same bug, is a silent 200 in one design and a thrown exception in the other. Nothing in a/ is incompetent. Its consumers check what they use. The -3 slips through because printing a number cannot fail and dividing by a limit cannot fail, so no consumer had a reason to look.
a-validate/, which is the design most people already write
The rules in a-validate/Decision.validate() are character for character b/'s rules. The method is public, it is on the type that owns them, and Limiter.decide calls it. On the deny path.
scenario 2 stale window boundary, through the HTTP responder
detected yes, after 3 call(s)
calls [Limiter.decide, Decision.denied, Decision.validate]
message a denial must say when to come back, and it must be later than now, got PT-3S
blamed Decision.validate(Decision.java:19)That works. The message is the good one and the blame is in the right class, one call later than b/. Where the design fails is scenario 1:
scenario 1 torn count: checked at 97 used, charged at 103, limit 100
detected no
calls 7 [Limiter.decide, Decision.allowed, Limiter.audit, Responder.respond, Responder.status, Responder.headers, Responder.body]
outcome audit [rule=hourly allowed=true remaining=-3 retryAfter=PT0S] response [200 OK | X-RateLimit-Remaining: -3, Retry-After: 0 | 103% of quota used]Decision.validate is not in that call list. It exists, it is correct, and the allow path does not call it. Nobody decided to skip it. The author was thinking about the retry hint, wrote the call on the branch where the retry hint is set, and moved on. No compiler mentions the other branch.
Now the size: a-validate/ is 127 normalised lines against b/'s 124. It costs three lines more than putting the same rules in the constructor, and it misses the case a concurrency bug actually used. That is the whole argument against a validate() method, in two numbers from one command.
Scenario 2 and 3, and why the same bug has two messages in a/
The stale boundary produces a negative wait. Two consumers see it, and each one fails differently.
Through the HTTP responder, which does check:
detected yes, after 6 call(s)
threw java.lang.IllegalArgumentException
message Retry-After cannot be negative: PT-3S
blamed Responder.headers(Responder.java:26)Through the internal caller, which does not:
detected yes, after 5 call(s)
threw java.lang.IllegalArgumentException
message timeout value is negative
blamed java.base/java.lang.Thread.sleep(Thread.java:500)Same rule, same violation, two messages. One names a header and blames Responder. The other comes from java.lang.Thread and mentions neither rate limiting nor the rule that produced it. Neither names the limiter whose window boundary went stale, because neither consumer knows about it.
b/ reports both paths the same way, in two calls:
message a denial must say when to come back, and it must be later than now, got PT-3S
blamed Decision.<init>(Decision.java:18)The count is the cheaper half of this finding. The expensive half is where the blame lands. In a/ the stack trace points at the class that noticed, which is never the class that was wrong. Every one of those investigations starts in the wrong file.
The measurement that goes the wrong way
Here is the review comment that produces b-normalising/:
A negative
Retry-Aftertook the checkout service down last quarter. Do not make every caller handle it. Make the type tolerant.
It is a reasonable request, and the change is two lines: remaining = Math.max(0L, remaining) and a one-second fallback wait. The invariant stays exactly where b/ put it. Only the response to a violation changes, from refusing to repairing.
scenario 1 torn count: checked at 97 used, charged at 103, limit 100
detected no
calls 7
outcome audit [rule=hourly allowed=true remaining=0 retryAfter=PT0S] response [200 OK | X-RateLimit-Remaining: 0, Retry-After: 0 | 100% of quota used]Compare that audit line with a/'s. In a/ the log says remaining=-3, which is a number a human can find and reason about. Here it says remaining=0 and the response reads 100% of quota used, which is indistinguishable from a customer who has honestly spent their whole hourly quota.
b-normalising/ is the only one of the four where the torn count leaves no trace at all. Placing the check correctly and then softening it is worse than not placing it, and it costs 8 more lines than a/ to be worse.
Scenario 3 makes the same point louder. The fallback wait is one second, so the retrying caller sleeps for a second nobody asked for and then retries. No error, no log line, one second of latency per affected request, and the window boundary is still stale.
The alternatives, so the choice is a choice
Could a/ catch the torn count by checking in Responder? Yes, and it would then be caught at call 6 instead of never. That check has to be written in every consumer that reads remaining, and there are three in this tiny tree: the audit line, the header and the usage figure. The count of consumers is what grows, and none of them can be made to check by the compiler.
Is b/ free? No. It is 124 normalised lines against a/'s 114. Ten lines is the price, and when-not.md names the two occasions when it buys nothing. It is worth noticing that b/ is the second cheapest of the four designs, and the only one that catches everything.
Would calling validate() from every construction site fix a-validate/? Yes, and the construction sites are the problem. There are two in this tree. The corpus reference has three, in KeyBudget.java and twice in RateLimiter.java, and nothing checks that the number of validate() calls matches. b/ has one site by construction, because the constructor is the only way to make the object.
Could b/ log instead of throwing? That is b-normalising/ with a print statement, and the measurement above is the answer. A log line in a system that emits millions of them is not a detection. Throwing is what makes it one.
What this set does not show
The distances here are 2 against 7 in a tree of five small files. In a real service the consumer side is a request handler, a metrics exporter, a billing pipeline and a support console, and the equivalent scenario 1 number is not 7. It is however many calls happen between a torn subtraction and somebody noticing a support ticket about a 103% figure.
It also does not show a case where construction-time placement is wrong. That case exists, and it is when-not.md.
Worked source
The 7 files of the worked design
Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.
worked/src/Algorithm.java19 linesworked/src/Budget.java92 linesworked/src/ClientKey.java29 linesworked/src/Decision.java58 linesworked/src/Rule.java47 linesworked/src/RuleByString.java30 linesworked/src/Main.java195 lines
worked/src/Algorithm.java19 lines
/**
* How a rule counts. Two constants, and the set is closed.
*
* <p>This type is an invariant, placed by the compiler rather than by an {@code if}. There is no
* such thing as an unknown algorithm reaching {@link Rule}, so {@code Rule}'s constructor has no
* membership check for it and no "unknown algorithm" failure mode to test. Compare
* {@link RuleByString}, which carries the same information as text and pays for it in both
* places.
*
* <p>Adapted from {@code corpus/rate-limiter/contract/Algorithm.java}.
*/
public enum Algorithm {
/** {@code limit} requests per epoch-aligned window; the counter resets at each boundary. */
FIXED_WINDOW,
/** A bucket of {@code limit} tokens, refilling {@code limit} per window, continuously. */
TOKEN_BUCKET
}worked/src/Budget.java92 lines
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
/**
* Every rule one caller is held to. All of them must pass for a request to be allowed.
*
* <p>A class rather than a record, because the invariant spans the elements of a collection rather
* than sitting on a field: two rules on one caller may not share a name. A record's canonical
* constructor could hold that check too. What a record cannot do is refuse to publish the list it
* was handed, and this one has to, or the check is a formality.
*
* <p>The duplicate-name rule is {@code KeyBudget.of}'s, from
* {@code corpus/rate-limiter/reference/DECISION_LOG.md}: a denial naming a rule that matches two
* rules explains nothing.
*/
public final class Budget {
private final ClientKey key;
private final List<Rule> rules;
private Budget(ClientKey key, List<Rule> rules) {
this.key = key;
this.rules = rules;
}
/**
* The only way to make one. Every check runs before {@code new}, and the list is copied before
* it is stored.
*
* @throws IllegalArgumentException if two rules share a name
* @throws NullPointerException if the key, the list or any rule in it is null
*/
public static Budget of(ClientKey key, List<Rule> rules) {
Objects.requireNonNull(key, "key");
Objects.requireNonNull(rules, "rules");
// Before List.copyOf, which refuses a null element with no message at all. A bare
// NullPointerException does not say which of eight configured rules was missing.
for (int i = 0; i < rules.size(); i++) {
Objects.requireNonNull(rules.get(i), "rule at index " + i + " for client " + key);
}
List<Rule> copy = List.copyOf(rules);
Set<String> seen = new HashSet<>();
for (Rule rule : copy) {
if (!seen.add(rule.name())) {
throw new IllegalArgumentException(
"client " + key + " has two rules called " + rule.name()
+ "; a denial naming that rule would not say which one refused");
}
}
return new Budget(key, copy);
}
public ClientKey key() {
return key;
}
/** The rules, unmodifiable. Handed straight out: the field is already a copy. */
public List<Rule> rules() {
return rules;
}
/** The names of the rules that would refuse, given how many requests have been counted. */
public List<String> refusedBy(long usedSoFar) {
List<String> refused = new ArrayList<>();
for (Rule rule : rules) {
if (usedSoFar >= rule.limit()) {
refused.add(rule.name());
}
}
return List.copyOf(refused);
}
/**
* How many more requests the tightest rule would allow. A key with no rules is unlimited.
*
* <p>No clamp, on purpose. {@code Math.max(0L, ...)} here would look defensive and would erase
* the one signal that a counter was charged twice for one request. The subtraction is allowed
* to go negative so that {@link Decision} can refuse it and say which field and which value.
*/
public long remaining(long usedSoFar) {
long fewest = Long.MAX_VALUE;
for (Rule rule : rules) {
fewest = Math.min(fewest, rule.limit() - usedSoFar);
}
return fewest;
}
}worked/src/ClientKey.java29 lines
import java.util.Objects;
/**
* Who is asking: an API key, a tenant id, a user id.
*
* <p>One invariant, enforced once. "A caller must be identifiable" is a property of the key, so it
* is checked where keys are made rather than re-verified by every method that takes one.
*
* <p>From {@code corpus/rate-limiter/contract/ClientKey.java}.
*/
public record ClientKey(String value) {
public ClientKey {
Objects.requireNonNull(value, "value");
if (value.isBlank()) {
throw new IllegalArgumentException("a client key cannot be blank");
}
}
/** Reads better at a call site than the constructor: {@code ClientKey.of("acme")}. */
public static ClientKey of(String value) {
return new ClientKey(value);
}
@Override
public String toString() {
return value;
}
}worked/src/Decision.java58 lines
import java.time.Duration;
import java.util.Objects;
/**
* The answer to one request: allowed or denied, what is left, and — when denied — which rule said
* no and how long to wait.
*
* <p>The four fields are not independent, so the invariants are not per-field checks. An allowed
* decision carrying a retry hint, or a denial that names no rule, cannot be constructed at all.
* That is what makes a torn count unreportable rather than merely unlikely: a {@code remaining}
* assembled from two different reads of the same counter fails a check here instead of arriving at
* a customer as a header.
*
* <p>From {@code corpus/rate-limiter/contract/Decision.java}, whose own compact constructor caught
* a concurrency bug during the stress-suite work. See {@code reference/DECISION_LOG.md}.
*/
public record Decision(boolean allowed, long remaining, String deniedBy, Duration retryAfter) {
public Decision {
Objects.requireNonNull(deniedBy, "deniedBy");
Objects.requireNonNull(retryAfter, "retryAfter");
if (remaining < 0) {
throw new IllegalArgumentException("remaining cannot be negative, got " + remaining);
}
if (allowed) {
if (!deniedBy.isEmpty()) {
throw new IllegalArgumentException("an allowed request was not denied by " + deniedBy);
}
if (!retryAfter.isZero()) {
throw new IllegalArgumentException(
"an allowed request has nothing to wait for, got " + retryAfter);
}
} else {
if (deniedBy.isBlank()) {
throw new IllegalArgumentException("a denial must name the rule that refused");
}
if (retryAfter.isZero() || retryAfter.isNegative()) {
throw new IllegalArgumentException(
"a denial must say when to come back, and it must be later than now, got "
+ retryAfter);
}
if (remaining != 0) {
throw new IllegalArgumentException(
"a denied request has nothing remaining, got " + remaining);
}
}
}
/** Allowed, with {@code remaining} more to go. */
public static Decision allowed(long remaining) {
return new Decision(true, remaining, "", Duration.ZERO);
}
/** Denied by the rule called {@code ruleName}; come back in {@code retryAfter}. */
public static Decision denied(String ruleName, Duration retryAfter) {
return new Decision(false, 0L, ruleName, retryAfter);
}
}worked/src/Rule.java47 lines
import java.time.Duration;
import java.util.Objects;
/**
* One limit a caller is held to: {@code limit} requests per {@code window}, counted by
* {@code algorithm}, and called {@code name}.
*
* <p>Four invariants, all in the compact constructor, so no rule that exists is wrong. Every
* message names the rule, the field and the value, because the reader of that message is on call.
*
* <p>From {@code corpus/rate-limiter/contract/Rule.java}.
*/
public record Rule(String name, Algorithm algorithm, long limit, Duration window) {
public Rule {
Objects.requireNonNull(name, "name");
// The only check `algorithm` needs. Membership was settled by the enum.
Objects.requireNonNull(algorithm, "algorithm");
Objects.requireNonNull(window, "window");
if (name.isBlank()) {
throw new IllegalArgumentException("a rule needs a name so a denial can explain itself");
}
if (limit < 1) {
throw new IllegalArgumentException("rule " + name + ": limit must be at least 1, got " + limit);
}
if (window.isZero() || window.isNegative()) {
throw new IllegalArgumentException("rule " + name + ": window must be positive, got " + window);
}
try {
Math.multiplyExact(limit, window.toNanos());
} catch (ArithmeticException overflow) {
throw new IllegalArgumentException(
"rule " + name + ": limit " + limit + " over " + window
+ " is too large to count exactly in nanoseconds");
}
}
/** {@code limit} requests per epoch-aligned {@code window}, reset at each boundary. */
public static Rule fixedWindow(String name, long limit, Duration window) {
return new Rule(name, Algorithm.FIXED_WINDOW, limit, window);
}
/** A bucket of {@code limit} tokens, refilling {@code limit} per {@code window}. */
public static Rule tokenBucket(String name, long limit, Duration window) {
return new Rule(name, Algorithm.TOKEN_BUCKET, limit, window);
}
}worked/src/RuleByString.java30 lines
import java.time.Duration;
import java.util.List;
import java.util.Objects;
/**
* The same rule with the algorithm carried as text instead of as a type.
*
* <p>Here for one comparison, and it is the competent version of that design rather than a straw
* man: the membership check is present, it is in the constructor, and its message lists what was
* expected. What it cannot do is stop the typo being written, because {@code "fixed_windo"} is a
* perfectly good {@code String}. The check also has to answer a question the enum never posed —
* whether {@code "fixed_window"} in lower case is the same algorithm.
*
* <p>{@code KNOWN} is the price: a second list of the constants, kept in step by hand.
*/
public record RuleByString(String name, String algorithm, long limit, Duration window) {
/** The enum's constant set, written out again because a {@code String} has no constants. */
private static final List<String> KNOWN = List.of("FIXED_WINDOW", "TOKEN_BUCKET");
public RuleByString {
Objects.requireNonNull(name, "name");
Objects.requireNonNull(algorithm, "algorithm");
Objects.requireNonNull(window, "window");
if (!KNOWN.contains(algorithm)) {
throw new IllegalArgumentException(
"rule " + name + ": unknown algorithm \"" + algorithm + "\", expected one of " + KNOWN);
}
}
}worked/src/Main.java195 lines
import java.time.Duration;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicLong;
/**
* Triggers every invariant in this lesson and prints what it says.
*
* <p>Run it. The messages in {@code NOTES.md} are this program's output, unedited.
*/
public final class Main {
public static void main(String[] args) throws InterruptedException {
happyPath();
perFieldInvariants();
crossFieldInvariants();
theCollectionInvariant();
typeVersusCheck();
theTornCount();
}
// ---------------------------------------------------------------- happy path
private static void happyPath() {
System.out.println("== What a valid budget looks like ==");
Budget budget = Budget.of(
ClientKey.of("acme"),
List.of(
Rule.fixedWindow("hourly", 100L, Duration.ofHours(1)),
Rule.tokenBucket("burst", 5L, Duration.ofSeconds(1))));
System.out.println("rules " + names(budget.rules()));
System.out.println("remaining after 3 requests " + budget.remaining(3L));
System.out.println("refused after 5 requests " + budget.refusedBy(5L));
System.out.println("allowed(2) " + Decision.allowed(budget.remaining(3L)));
System.out.println("denied(\"burst\", 200ms) "
+ Decision.denied("burst", Duration.ofMillis(200)));
System.out.println();
}
// ------------------------------------------------- one field, one invariant
private static void perFieldInvariants() {
System.out.println("== One field at a time ==");
show("ClientKey.of(\" \")", () -> ClientKey.of(" "));
show("Rule.fixedWindow(\"hourly\", 0, 1h)",
() -> Rule.fixedWindow("hourly", 0L, Duration.ofHours(1)));
show("Rule.fixedWindow(\"hourly\", 100, PT0S)",
() -> Rule.fixedWindow("hourly", 100L, Duration.ZERO));
show("Rule.tokenBucket(\"firehose\", 10_000_000_000, 1h)",
() -> Rule.tokenBucket("firehose", 10_000_000_000L, Duration.ofHours(1)));
System.out.println();
}
// ------------------------------------ four fields, one consistent decision
private static void crossFieldInvariants() {
System.out.println("== Four fields that have to agree ==");
show("Decision.allowed(-3)", () -> Decision.allowed(-3L));
show("new Decision(true, 97, \"burst\", PT0S)",
() -> new Decision(true, 97L, "burst", Duration.ZERO));
show("new Decision(true, 97, \"\", PT2S)",
() -> new Decision(true, 97L, "", Duration.ofSeconds(2)));
show("Decision.denied(\"\", PT2S)", () -> Decision.denied("", Duration.ofSeconds(2)));
show("Decision.denied(\"burst\", PT0S)", () -> Decision.denied("burst", Duration.ZERO));
show("new Decision(false, 97, \"burst\", PT2S)",
() -> new Decision(false, 97L, "burst", Duration.ofSeconds(2)));
System.out.println();
}
// ------------------------------------- an invariant across a whole collection
private static void theCollectionInvariant() {
System.out.println("== An invariant that spans a collection ==");
Rule hourly = Rule.fixedWindow("hourly", 100L, Duration.ofHours(1));
Rule alsoHourly = Rule.tokenBucket("hourly", 5L, Duration.ofSeconds(1));
show("Budget.of(acme, [hourly, hourly])",
() -> Budget.of(ClientKey.of("acme"), List.of(hourly, alsoHourly)));
List<Rule> withAHole = new ArrayList<>();
withAHole.add(hourly);
withAHole.add(null);
show("Budget.of(acme, [hourly, null])",
() -> Budget.of(ClientKey.of("acme"), withAHole));
Budget budget = Budget.of(ClientKey.of("acme"), List.of(hourly));
show("budget.rules().add(hourly)", () -> budget.rules().add(hourly));
System.out.println();
}
// -------------------------------- the invariant a type holds without an if
private static void typeVersusCheck() {
System.out.println("== Closed type versus checked value ==");
show("Algorithm.valueOf(\"FIXED_WINDO\")", () -> Algorithm.valueOf("FIXED_WINDO"));
show("RuleByString(\"hourly\", \"fixed_windo\", ...)",
() -> new RuleByString("hourly", "fixed_windo", 100L, Duration.ofHours(1)));
show("RuleByString(\"hourly\", \"fixed_window\", ...)",
() -> new RuleByString("hourly", "fixed_window", 100L, Duration.ofHours(1)));
System.out.println("Rule(\"hourly\", Algorithm.FIXED_WINDOW, ...) built, and no typo was "
+ "reachable to check for");
System.out.println();
}
// ------------------------------------------ the bug nobody wrote a test for
/**
* Check-then-charge with no lock, which is the bug the rate-limiter stress suite was built to
* catch. Two threads pass the check while one unit is left, then both charge, so the counter
* ends above the limit and the subtraction goes negative.
*
* <p>Nothing here asserts anything about {@code remaining}. The only thing standing between a
* torn count and a customer is {@link Decision}'s constructor.
*/
private static void theTornCount() throws InterruptedException {
System.out.println("== A concurrency bug caught by a value type ==");
int limit = 50;
int threads = 256;
AtomicLong used = new AtomicLong();
AtomicLong allowed = new AtomicLong();
AtomicLong refused = new AtomicLong();
String[] oneMessage = {"none"};
CountDownLatch go = new CountDownLatch(1);
List<Thread> pool = new ArrayList<>();
for (int i = 0; i < threads; i++) {
Thread t = new Thread(() -> {
try {
go.await();
} catch (InterruptedException interrupted) {
Thread.currentThread().interrupt();
return;
}
// Check. The counter itself is atomic, so no update is lost — the missing
// thing is a lock held across the check AND the charge.
if (used.get() >= limit) {
return;
}
// The interval a real limiter spends evaluating its other rules. Nothing here
// is contrived: the bug is that this interval exists outside a lock.
for (int spin = 0; spin < 20_000; spin++) {
Thread.onSpinWait();
}
// Charge, unconditionally, on a decision that may already be stale.
long after = used.incrementAndGet();
allowed.incrementAndGet();
try {
Decision.allowed(limit - after);
} catch (IllegalArgumentException caught) {
refused.incrementAndGet();
synchronized (oneMessage) {
oneMessage[0] = caught.getMessage();
}
}
});
pool.add(t);
t.start();
}
go.countDown();
for (Thread t : pool) {
t.join();
}
System.out.println("limit " + limit + ", " + threads
+ " threads, no lock across check-then-charge");
System.out.println("allowed more requests than the limit permits: " + (allowed.get() > limit));
System.out.println("torn counts refused by Decision's constructor: " + (refused.get() > 0));
System.out.println("a message from this run: " + oneMessage[0]);
}
// ---------------------------------------------------------------- plumbing
private static void show(String call, Runnable attempt) {
try {
attempt.run();
System.out.println(pad(call) + "accepted");
} catch (RuntimeException thrown) {
System.out.println(pad(call) + thrown.getClass().getName());
String message = thrown.getMessage();
System.out.println(pad("") + " " + (message == null ? "(no message)" : message));
}
}
private static String pad(String s) {
return s + " ".repeat(Math.max(1, 46 - s.length()));
}
private static List<String> names(List<Rule> rules) {
return rules.stream().map(Rule::name).toList();
}
private Main() {}
}The faded stage is not here, on purpose
In the app, the third stage of a lesson hands you the worked design with a few lines
replaced by // GAP: markers, then compiles your completion and runs a JUnit suite
against it. That needs javac, and a static site has no compiler — so rather than show a
control that cannot work, this page stops at the worked source.
Run the app for the drill: it is the download in the header, and it works offline once unpacked.