Hands-on labs

Reading about a token bucket and writing one are different skills, and only one of them survives an interviewer asking “what happens when two requests hit the same key at once?”

These labs implement the primitives from 03-system-design-curriculum.md and 06-system-design-reference.md. The code lives in labs/, has no dependencies, and runs on Node’s built-in test runner.

cd labs
node --test          # or: npm test

Why these five

They were chosen because each one is (a) plausibly askable as a coding round — LRU cache and rate limiter show up by name in 02-coding-checklist.md § 13 — and (b) load-bearing in a design round. They earn their place twice.

How to use them

Do not read the source first. That converts a two-hour exercise into a twenty-minute one and teaches you almost nothing.

For each lab:

1. Read only the test file. It is the specification.
2. Delete the implementation (git checkout restores it) or write yours in a scratch file next to it.
3. Implement until the tests pass, on a timer, narrating out loud — the same discipline as 01-plan-8-weeks.md demands of every practice problem.
4. Then read the provided implementation and diff the reasoning, not the syntax. Where did it handle a case you missed?
5. Log it in 05-practice-log.md like any other problem.

The tests are deliberately more demanding than an interviewer would be. That is the point — an interviewer asks about one edge case, and you want to have already met all of them.

Lab 1 — LRU cache

File: labs/src/lru-cache.js · Tests: labs/test/lru-cache.test.js

The invariant: hashmap for O(1) lookup, doubly linked list for O(1) reorder. Neither structure can do both jobs alone, which is why the answer is a pair.

What the tests force you to get right

• Eviction order matches a naive reference implementation across a scripted sequence of mixed reads and writes. A subtle recency bug shows up immediately rather than passing by luck.
• capacity = 1, which exercises every pointer path at once and is where most first-pass implementations break.
• Updating an existing key refreshes recency and does not grow the cache.
• has() must not count as a use — a real distinction that trips people up.
• A randomised property test over 5,000 operations asserts the two internal structures never disagree and size never exceeds capacity.

The detail worth stealing: sentinel head and tail nodes. They remove every null check from the splice logic. Most first-pass LRU bugs are missing null guards at the ends of the list; sentinels make those states unrepresentable.

Say this in an interview: that get returning undefined is ambiguous if callers may store undefined, which is why real caches return a sentinel or a {hit, value} pair. Noticing an API flaw unprompted is an L5 signal.

Lab 2 — Rate limiters

File: labs/src/rate-limiter.js · Tests: labs/test/rate-limiter.test.js

Three algorithms, so the differences stop being abstract.

The test that matters most proves the fixed-window boundary burst rather than asserting it. Spend the full limit at 900 ms, spend it again at 1,100 ms, and you have achieved exactly 2× the intended rate 200 ms apart. The sliding-window test then shows the same traffic being suppressed.

Being able to say “fixed windows allow twice the limit across a boundary, here’s the traffic pattern that does it” is worth far more than naming five algorithms.

Other things the tests pin down

• Lazy refill from elapsed time, not a timer per bucket. A timer per key does not scale to millions of keys; lazy refill is O(1) per request with no background work.
• An idle bucket never accumulates more than capacity — the cap is what makes it a bucket.
• retryAfterMs is actually correct: waiting exactly that long is sufficient. A 429 without Retry-After forces clients to guess, and they guess badly.
• Over 60 simulated seconds the long-run rate converges on the refill rate plus one initial burst.
• KeyedRateLimiter sweeps idle buckets. A naive Map of key → bucket is an unbounded memory leak and therefore a denial-of-service vector: an attacker sends one request each from a million keys. This is the follow-up question after you present the happy path, and most candidates have not thought about it.

Time is injected, never read from Date.now(). A rate limiter whose tests depend on real sleeping is a rate limiter with flaky tests — and injecting the clock is exactly how you would make it testable in production.

Lab 3 — Consistent hash ring

File: labs/src/consistent-hash.js · Tests: labs/test/consistent-hash.test.js

This is the lab that converts a phrase you can recite into a number you can defend. The tests measure what the curriculum merely asserts.

Measured over 20,000 keys, five nodes, 200 virtual nodes each:

Run it yourself and watch the numbers come out; that is what makes the argument stick.

The lesson hiding behind the lesson. My first implementation produced a 33.7% imbalance even with 200 virtual nodes. The cause was not the ring — it was the hash. Ring labels are short and highly similar (a#0, a#1, b#0), and FNV-1a alone leaves such inputs correlated in the high bits, so the ring positions cluster and the arcs come out uneven. Adding MurmurHash3’s finalizer (fmix32, pure avalanche, no new entropy) took it from 33.7% to 7.4%.

So “use consistent hashing with virtual nodes” is only half the advice. The hash has to actually avalanche. There is a test that measures exactly this, and another that verifies a single flipped input bit changes about half the output bits.

Also tested: removing a node moves only that node’s keys and disturbs no others; getNodes(key, 3) returns three distinct physical machines, because with virtual nodes the next few ring positions are frequently the same machine and putting all replicas there defeats the purpose.

Lab 4 — Bloom filter

File: labs/src/bloom-filter.js · Tests: labs/test/bloom-filter.test.js

The asymmetry is the whole point. A negative answer is certain; a positive answer is probabilistic. For the web crawler in problem 3 that means the worst case is skipping a page you have not actually crawled — acceptable. If the error ran the other way the structure would be useless there.

Stating which direction the error goes, and why that is tolerable for this specific problem, is the interview signal. The structure is not the point.

What the tests establish

• Zero false negatives across 1,000 inserts — impossible by construction, so the test documents the guarantee.
• Observed false-positive rate stays within the target’s order of magnitude over 20,000 probes.
• ~9.6 bits per item at a 1% false-positive rate — over 20× smaller than storing the URLs.
• Overfilling 10× past the design capacity pushes the rate above 50%, i.e. makes it useless. This is why sizing for the real n matters, and it is a good thing to volunteer.
• Kirsch–Mitzenmacher: derive k hashes as h1 + i·h2 from two independent ones instead of computing k real hashes. A cheap extra half-step of depth.

Lab 5 — Idempotency and sagas

File: labs/src/idempotency.js · Tests: labs/test/idempotency.test.js

06-system-design-reference.md claims “exactly-once delivery does not exist; what exists is at-least-once plus idempotent processing.” This lab makes that claim executable.

The race most implementations get wrong. A naive check-then-insert has a window where a retry arriving while the first attempt is still running starts a second execution. The fix is to reserve the key before awaiting the operation, so the concurrent retry observes IN_FLIGHT and waits on the original promise instead.

There is a test that fires 25 simultaneous requests at one key and asserts exactly one execution and one shared result.

Design decisions the code makes explicit

• A failed operation clears the key so a retry can legitimately proceed. Whether failures should be cached is a genuine tradeoff — caching prevents retry storms but makes a transient error permanent. Say which you chose.
• Records expire on a TTL. Idempotency keys are not kept forever.
• Sagas compensate in reverse order, most-recent effect first.
• A step that never ran is never compensated.
• Compensation failures are reported, not swallowed. A failed rollback cannot be retried away; real systems park it for a human. Pretending the rollback worked is how money goes missing.

The final test combines both: a retried saga that does not double-charge. That is what “effectively exactly-once” actually means, and it is a much better answer than the phrase alone.

What these labs deliberately do not cover

• No networking, no persistence, no concurrency across processes. Everything is single-process and in-memory. Real distributed versions of these primitives are substantially harder, and building them is not the best use of eight weeks aimed at an interview.
• No consensus implementation. Writing Raft is a rewarding multi-week project and poor interview preparation. 10-distributed-systems-theory.md covers what you actually need to say about it.
• No benchmarks. The tests measure correctness and distribution, not throughput. Performance claims in an interview should come from the latency table in the reference, not from a microbenchmark on your laptop.