# Toy backlog Each entry: the mechanism it's meant to teach, and the "aha" moment the demo should produce. Pick any order — they're independent. ## Data stores - [ ] **lsm-tree** — memtable + sorted SSTable segments + compaction. Aha: writes are always sequential appends; reads may need to check multiple segments; compaction merges and drops shadowed keys. - [x] **wal-kv** — a key-value store with a write-ahead log and crash recovery. Aha (sharpened once it was built): `kill -9` *cannot* fail as a durability test — with `fsync` off entirely it still recovers every record, because the bytes are in the kernel's page cache and the kernel isn't what died. See [`wal-kv/`](wal-kv/) and its [commentary](wal-kv/commentary.md) ([rendered](wal-kv/commentary.html)). - [ ] **btree-index** — a B-tree (or B+tree) built on top of a flat file, used as an index into a data file. Aha: point lookups are O(log n) node reads, not a full scan. - [ ] **inverted-index** — mini full-text search: tokenize, build postings lists, do a boolean AND/OR query. Aha: query time depends on postings list length, not corpus size. - [ ] **mvcc-store** — multi-version concurrency control: each write creates a new version tagged with a transaction id; readers see a consistent snapshot. Aha: a long-running reader doesn't block or see a concurrent writer's uncommitted change. ## Distributed systems - [ ] **raft-toy** — leader election + log replication among simulated nodes (in-process, not real network). Aha: kill the leader process/thread and watch a new one get elected within a few ticks. - [ ] **gossip-protocol** — nodes periodically exchange state with random peers until the cluster converges. Aha: inject a value at one node and watch it propagate to all nodes in O(log n) rounds. - [ ] **vector-clock-crdt** — a G-Counter or OR-Set CRDT with vector clocks, merged from multiple replicas. Aha: two replicas update concurrently offline, merge, and converge without a coordinator. - [ ] **consistent-hashing** — a hash ring with virtual nodes for request/key routing. Aha: adding/removing one node only reshuffles ~1/N of the keys, not all of them. - [ ] **two-phase-commit** — a coordinator + participants doing prepare/ commit/abort. Aha: one participant voting "no" aborts the whole transaction across all participants. - [ ] **quorum-replication** — N replicas, tunable W (write quorum) and R (read quorum), with read-repair on stale replicas. Aha: with W+R > N you always read the latest write even if some replicas are down or slow; drop W+R to N and show a stale read slip through. - [ ] **distributed-lock** — a Redlock-style lock across simulated independent lock servers, with a lease/TTL. Aha: a client that pauses past its lease loses the lock without knowing it, and a second client legitimately acquires it — classic distributed-lock-isn't-mutex gotcha. - [ ] **failure-detector** — heartbeats plus a phi-accrual (or simple timeout) detector deciding "is this node dead." Aha: a fixed timeout produces false positives under jitter; phi-accrual adapts and doesn't. - [ ] **unique-id-generator** — Snowflake-style IDs (timestamp + machine id + sequence, packed into 64 bits). Aha: IDs stay roughly sortable by time and collision-free across machines with zero coordination between them. ## Networking - [ ] **http-from-sockets** — a minimal HTTP/1.1 server built directly on raw TCP sockets (parse request line/headers, write response). Aha: curl hits it and gets a real response with zero framework code. - [ ] **tcp-proxy** — a forward proxy that shuffles bytes between client and upstream, with basic connection pooling. Aha: watch it multiplex many client connections onto few upstream connections. - [ ] **pubsub-broker** — an in-process pub/sub broker with topics and subscriber queues. Aha: one publish fans out to N subscribers independently, one slow subscriber doesn't block the others. - [x] **rate-limiter** — token bucket vs. sliding window log implementations side by side. Aha: burst behavior differs visibly between the two under the same request trace. See [`rate-limiter/`](rate-limiter/) and its [commentary](rate-limiter/commentary.md) ([rendered](rate-limiter/commentary.html)). ## Concurrency / runtimes - [ ] **mini-asyncio** — a single-threaded event loop with a task queue and coroutines driven by `send()`. Aha: two "sleeping" tasks interleave without threads. - [ ] **work-stealing-queue** — a thread pool where idle workers steal tasks from busy workers' deques. Aha: an uneven workload still finishes near optimal time because idle workers steal instead of sitting empty. - [ ] **green-threads** — cooperative scheduling of lightweight "threads" using generators, with a simple scheduler loop. Aha: thousands of green threads run on one OS thread. ## Compilers / interpreters - [ ] **tiny-interpreter** — tokenizer + recursive-descent parser + tree-walk evaluator for a tiny arithmetic/expression language. Aha: watch the same input go from tokens to an AST to a result, step by step. - [ ] **regex-engine** — Thompson's construction: regex -> NFA -> match. Aha: matching is a graph walk, not backtracking (until you also implement a backtracking version and compare pathological input times). - [ ] **bytecode-vm** — compile the tiny language above to a stack-based bytecode and run it on a small VM loop. Aha: same program, now runs as a dispatch loop over opcodes instead of walking a tree. ## OS-ish - [ ] **toy-filesystem** — inode table + block allocation over one big flat file, with a tiny CLI (`write`, `read`, `ls`, `rm`). Aha: deleting a file just frees blocks/inode, contents remain until overwritten. - [ ] **malloc-arena** — a simple free-list allocator (malloc/free) over a fixed byte array. Aha: watch fragmentation happen and get fixed by coalescing adjacent free blocks. - [ ] **process-scheduler** — simulate round-robin vs. priority vs. MLFQ scheduling over a fixed set of synthetic jobs. Aha: same jobs, different average wait time depending on scheduling policy. ## Security / crypto - [ ] **merkle-tree** — build a Merkle tree over a set of blocks, verify a single block with an inclusion proof. Aha: verifying one leaf only needs O(log n) hashes, not the whole dataset. - [ ] **jwt-from-scratch** — implement JWT signing/verification (HMAC) by hand, no library. Aha: tampering with the payload one byte invalidates the signature. - [ ] **toy-blockchain** — blocks with hash pointers + proof-of-work difficulty target. Aha: changing one historical block invalidates every block after it, and remining is visibly slow. ## Caching / probabilistic structures - [ ] **lru-cache** — a fixed-capacity cache with O(1) get/put via a hash map + doubly linked list. Aha: watch eviction order fall out of access order, not insertion order; compare against LFU on a Zipfian access trace to see when each policy wins. - [ ] **bloom-filter** — a probabilistic set membership filter (k hash functions over a bit array). Aha: false positives happen at a rate you can predict from the math, false negatives never happen; use it to skip SSTable segments that provably don't contain a key (ties back to `lsm-tree`). ## Observability / infra - [ ] **circuit-breaker** — closed/open/half-open state machine wrapping a flaky call. Aha: after N failures it stops calling the flaky dependency entirely, then probes and recovers. - [ ] **metrics-aggregator** — a StatsD-style counter/gauge/histogram aggregator with percentile estimation (e.g. t-digest or simple reservoir sampling). Aha: p50/p99 tracked in O(1) memory per bucket instead of storing every sample. - [ ] **load-balancer** — round-robin vs. least-connections vs. weighted, simulated against a set of backends with varying latency. Aha: same traffic, different tail latency depending on the balancing policy. ## Suggested starting order If you want a ramp rather than picking randomly: `wal-kv` → `lsm-tree` → `consistent-hashing` → `raft-toy` → `tiny-interpreter` → `mini-asyncio`. This goes single-node durability -> storage engine -> distributed routing -> distributed consensus -> language internals -> concurrency internals, each building intuition the next one leans on.