Building toil, and letting detsim find the bugs in it

toil is a small job queue: a server, a client library with a worker pool, a cli, a dashboard, wal-backed, priority queues, visibility timeouts, dead letter queue, all of it. but thats not really why i built it. i built it to be the first real test of a question i kept avoiding while working on detsim: does this thing actually catch bugs in code i didnt write specifically to be caught, or does it only ever catch bugs in code i wrote knowing exactly how the harness works?

so the rule for toil was: build it like a real job queue first, wire detsim in second, dont go back and simplify anything just to make it easier to test.

the wal

append-only log, length-prefixed, crc32-checksummed per record. every state transition (enqueue, lease, ack, nack, timeout-requeue, dead-letter, revive, purge) is a record before its applied to memory. restart replays the log. standard stuff. the one design choice worth mentioning: the wal is written against a Backend interface (WriteAt/ReadAt/Sync), not directly against *os.File. *os.File already satisfies it as-is, same method signatures. that one interface is the entire reason detsim could plug in later without touching a single line of the actual wal logic, i just had to pass detsim.FaultyStorage in instead of a real file. same production code path, different backend.

seed 2

first real crash-safety test: enqueue/lease/ack a bunch of jobs through a FaultyStorage-backed wal with torn writes, byte corruption, and dropped syncs all turned on, then simulate a hard crash (fresh wal instance over the same backend, trusted length re-derived from what the backend actually reports as durable) and check the recovered state. ran it for 3000 seeds.

seed 1 immediately failed my first assertion, which was "an acked job must never come back after recovery." turned out that assertion was just wrong. Ack() returns success as soon as the in-process apply happens, before anything confirms the ack record itself survived the write path. if the ack is the specific record that gets torn or dropped, the job correctly comes back as pending on recovery. thats not corruption, thats at-least-once delivery, the exact same guarantee sqs, faktory, and sidekiq all document instead of promising exactly-once. i was asserting a guarantee i never actually built. fixed the test, not the store.

fixed that, reran. seed 2, new failure: store: replay: EOF. this one wasnt my assertion being wrong, this was a real bug.

traced it by hand, walking the wal frame by frame outside the normal replay path, printing offset/length/checksum at each step. found a record at offset 239 with length=0, wantSum=0. crc32 of zero bytes is zero, so that trivially checksums as a valid empty record. replay tried to decode it as a real event and hit eof immediately, since nothing this codebase writes is ever actually zero bytes.

the real question was how a run of unwritten zero bytes ends up sitting in the middle of an otherwise valid log. traced it back to wal.Append: it advances the wal's own offset counter unconditionally after every write, trusting that Sync() returning nil means the bytes are actually durable. FaultyStorage.Sync() can silently drop a pending write and still return nil, thats the entire point of SkipSyncRate, its modeling the real failure class behind actual production incidents where fsync lied about persisting something. so: write gets dropped, offset already advanced past it regardless, next write lands past a gap that was never actually written, and writeCommitted's grow-and-zero-fill behavior leaves that gap as literal zero bytes forever.

the fix is in wal.Sync: after a backend confirms a sync, if it can also report how many bytes are actually durable, i added an optional Sizer interface for exactly this, the wal's offset gets pulled back down to match reality instead of trusting what it believed it had written. next append lands where the data actually ends. real files dont need this, a genuine short write from *os.File already returns an error, it cant silently lie the way this synthetic backend does on purpose. also added a cheap defense-in-depth check in replay itself: reject a zero-length record outright, since it can only ever be a hole, never a real event.

reran all 3000 seeds after the fix. clean.

TestReplayIsDeterministic is the other half of this, separate from the crash test: replay the exact same fault-injected log twice, through two independent store instances, and the recovered state has to match exactly both times. proves recovery is a pure function of whats actually on disk, not of anything about how or when the crashed process happened to run.

the rewrite tool has a real edge, and i found it honestly instead of routing around it

detsim has a second testing mode, detsim-test, that source-rewrites a package's goroutines and channels to run through its deterministic scheduler instead of making you write against the kernel directly. toil's client worker pool, real goroutines, a sync.WaitGroup, a select/time.After poll loop, is exactly the shape of code that path is for. figured id point it at that and get a second detsim story for free.

first attempt failed because my poll loop's select had return directly inside a case, select { case <-ctx.Done(): return; ... }, and the rewriter explicitly refuses to touch a select shaped like that (a return inside a rewritten select's closure would only exit the closure, not the real function, silently wrong instead of a compile error, so it bails out instead of risking that). fair, and an easy fix, moved the decision into a plain bool returned from the select (sleepOrDone in client/pool.go) instead of returning from inside the case itself.

second attempt failed for a completely different reason, and this one i couldnt fix from toil's side: ctx.Done() returns a channel created deep inside the standard library's context package, code the rewriter never parses, so it has no way to retroactively route that specific channel through the scheduler. go vet on the rewritten overlay caught it immediately, type <-chan struct{} of ctx.Done() does not match *rt.Chan[T]. thats a real, honest boundary of what source rewriting can reach, not a bug in either project. context.Context is genuinely opaque to it. so the worker pool today is exercised by go test -race and reading the code, not by the rewrite path, and i wrote that straight into toil's readme instead of quietly not mentioning i tried.

one more, found by just running the thing

after all the seeded testing passed, i actually started the server and hit it with curl by hand instead of trusting the test suite alone. enqueued a job, leased it, and the response was {"job":{...}} with no lease_id field at all. json's omitempty was dropping it, because the very first lease issued by a fresh store gets leaseID=0, the counter starts at zero, and omitempty treats the zero value as absent regardless of whether its actually meaningful. functionally it happened to still work by coincidence (a client unmarshaling into a zero-valued struct field lands on the right number anyway), but it's exactly the kind of fragile-by-accident behavior i didnt want sitting in the wire format. fixed by starting the lease counter at 1 instead of 0, so 0 unambiguously means "no lease" everywhere it appears, and reran the whole enqueue/lease/ack round trip through the actual running server and the actual cli afterward to confirm.

what this actually proved

the thing i was checking wasnt "can detsim catch bugs," i already knew that from working on it directly. it was "does it catch bugs in code that wasnt written with detsim in mind," and the honest answer is yes, immediately, on the second seed of the first real test i wrote against it. and just as importantly, it also caught a wrong assumption in my own test before it caught anything in the code, which is arguably the more useful failure mode, since a test asserting the wrong thing is worse than no test at all.

code's public, toil on github if you want to look at the wal fix directly, its in wal/wal.go and store/crash_sim_test.go.