task-queue

A distributed task queue in Python guaranteeing effectively-once execution under worker failure, proven with a real chaos test — not a demo of the concept, an actual harness that kills real OS processes and checks the invariant held.

The number

658 random worker kills, 6,000 tasks, 0 duplicate executions, 0 lost tasks.

That's from an actual run (chaos/headline_run_result.json), not a claim. Reproduce it with python3 chaos/chaos_harness.py.

What this is

Multiple worker processes pull tasks from a shared, persistent queue. Workers die — hard SIGKILL, no cleanup, mid-task — constantly and at random. No task is ever lost, and no task's side effect ever runs twice, even though the workers killing them have no idea they're about to die.

Exactly-once delivery is impossible to guarantee over a network or across process crashes — that's a real distributed-systems fact, not a limitation of this implementation specifically. What's achievable, and what this queue does, is at-least-once delivery of a task to a worker, plus an idempotent side effect, which composes to the same practical guarantee. The build log documents finding this out the hard way: the first version got the first half right and the second half wrong, which produced a real bug (duplicate executions), and the fix for that bug had its own bug (a phantom-completion race), which needed its own fix. See docs/BUILD_LOG.md.

Architecture

• Lease-based claiming (src/phase3_lease.py): a worker claiming a task gets exclusive ownership for a time-limited lease. If it dies before acking, the lease expires and another worker reclaims the task. SQLite's atomic UPDATE ... WHERE is the concurrency primitive — a claim only succeeds if the row still matches the expected pre-claim state.
• Idempotent side effects (chaos/chaos_harness.py): the queue-level idempotency key prevents duplicate enqueue, but that's a different problem from duplicate execution after a crash mid-processing. Execution idempotency needed its own mechanism: write-durable-then-atomically-claim via os.link(), not os.rename() (which silently overwrites on POSIX instead of failing on conflict).
• Dead-letter queue with exponential backoff: tasks that fail repeatedly stop retrying immediately and back off, then move to a dead state after max_attempts.
• Persistence: SQLite in WAL mode, synchronous=FULL. Survives a real process restart — tested by actually closing the connection and reopening a fresh one against the same file, not by mocking anything.

Honest results, not just the win

The chaos test passing cleanly is the headline, but two things are worth stating as plainly as the pass:

It took two real bugs to get here. The first version had 14 duplicate executions out of 2000 tasks. The fix for that had 1 silently-swallowed task out of 2000. Both are documented in docs/BUILD_LOG.md with what I thought was wrong versus what actually was.

Throughput goes down as worker count goes up, from 856 tasks/sec at 1 worker to 280 tasks/sec at 16 workers (bench/results.json). This isn't a correctness problem — the chaos invariant holds at every worker count — but it's a real architectural ceiling: SQLite allows exactly one writer at a time even in WAL mode, so more workers past a small number means more lock contention, not more parallelism. Fixing it means sharding across multiple SQLite files or moving to a database with real concurrent-write support (Postgres). That's future work, not a hidden problem.

Run it yourself

pip install -r requirements.txt  # stdlib only, this is here for completeness

# unit tests, each phase
python3 tests/test_phase1.py   # in-memory queue
python3 tests/test_phase2.py   # persistence across restart
python3 tests/test_phase3.py   # leases, real multi-process concurrency, backoff, dead-letter

# the actual proof
python3 chaos/chaos_harness.py

# throughput/latency at 1, 4, 16 workers
python3 bench/benchmark.py

Build order

Followed deliberately in this sequence — each phase had to pass its own tests before the next started:

1. In-memory queue: enqueue/dequeue/ack (src/phase1_inmemory.py)
2. SQLite persistence, survives restart (src/phase2_persistent.py)
3. Multi-worker leases, idempotency keys, backoff, dead-letter (src/phase3_lease.py)
4. Chaos harness: real process kills, real verification (chaos/chaos_harness.py)
5. Benchmark: throughput and latency at 1/4/16 workers (bench/benchmark.py)

What's not here

No network layer — this is single-machine, multi-process, not multi-host. The concurrency primitive (SQLite's atomic UPDATE...WHERE) doesn't generalize to multiple machines without a different coordination mechanism (a real distributed lock, or a database that supports it natively). That's a deliberate scope cut, not an oversight — the interesting engineering here is the failure-mode reasoning, and adding a network layer would mostly add plumbing without adding to that.