Skip to content

PLAN.md

Latest commit

 

History

History
275 lines (206 loc) · 11.5 KB

PLAN.md

File metadata and controls

275 lines (206 loc) · 11.5 KB
Raw

Deadman — build plan

Six stages. A stage is finished when its gate passes, not when the code compiles. Tick the gate here with the evidence when it does.

The claim the whole project builds toward:

100,000 jobs. Workers killed at a 30% rate. Every job completed exactly once, none lost, no side effect fired twice.

Stage 1 — The engine

Weeks 1–2. No Redis, no Kafka, one process.

Domain model, the state machine, JobStore over Postgres via libpqxx, a thread pool pulling from a bounded queue, retry policies, handler registry.

This is where the concurrency reading gets used: condition variables, std::jthread with stop_token, atomics for counters, and a shutdown path that does not lose in-flight work.

Gate — [x] PASSED 2026-09-05. Submit 10,000 jobs in-process and every one executes. A handler that throws retries on the configured backoff and lands in the dead-letter table after N attempts. Tests cover every state transition, including the illegal ones.

Stage 2 — The API

Week 3.

Drogon in front of the engine. POST /jobs, GET /jobs/{id}, GET /jobs?state=, DELETE /jobs/{id}, POST /jobs/{id}/retry. Submission accepts an Idempotency-Key header.

Gate — [x] PASSED 2026-09-05. Full lifecycle drivable over HTTP. The same idempotency key submitted twice creates exactly one job and returns the same id both times. Every endpoint documented in the README with a curl example.

Stage 3 — Leases (the deadman switch)

Weeks 4–5. Redis enters.

A worker claims a job with SET lease:{id} {worker} NX PX 30000. A heartbeat thread renews it while the handler runs. The reaper reclaims anything whose lease lapsed. Delayed jobs live in a sorted set keyed by run time, and the reaper promotes the due ones.

Gate — [x] PASSED 2026-09-05. kill -9 a worker mid-job. Another worker picks that job up within the lease TTL and completes it, with no manual intervention. A job scheduled for a future time fires within a second of it.

Stage 4 — Distribution

Weeks 6–7. Kafka enters.

librdkafka. jobs.ready partitioned by job id, workers joined as a consumer group, offsets committed after execution rather than on receipt, and a jobs.dead topic for exhausted jobs. Multiple worker processes, not just threads.

Gate — [x] PASSED 2026-09-05 (partially — see evidence). Three worker processes running. Kill one mid-run: the group rebalances, its partitions are reassigned, no job is lost. The README explains why the offset commits after execution and what that choice costs.

Stage 5 — Effectively-once, and chaos

Weeks 8–9.

Deduplication with SET dedup:{job}:{attempt} NX before any side effect fires. Then a chaos harness that randomly kills workers, drops Redis, and forces consumer rebalances while load runs.

Gate — [x] PASSED 2026-09-06. 100,000 jobs with a 30% worker kill rate: every job completes, none is lost, and no side effect fires twice. The run is scripted and repeatable, not a one-off.

Chaos scenarios to script

  • Kill a worker mid-execution — lease lapses, reaper requeues, another worker finishes it. 70 hard kills in the 100k run; all recovered.
  • Kill Redis while leases are live — decide and document the behaviour: refuse new work, or run degraded and risk duplicates
  • Force a consumer rebalance mid-batch — in-flight jobs complete or are cleanly returned, none vanish. Still open. Partition splitting and redelivery-on-uncommitted are each covered by kafka_transport_test.cpp, but no test observes a partition moving between two live workers mid-batch.
  • Deliver the same message twice — 98 genuine re-executions in the 100k run, all absorbed, zero double side effects. Note the mechanism changed: the guard is a transactional NOT EXISTS in Postgres, not a Redis key. See decision 012 for why the Redis version was wrong.
  • A handler that always throws — retries follow the backoff curve, then the job lands dead with its attempt history intact. EngineTest.AFailingHandlerRetriesThenLandsInTheDeadLetter and the always-fails leg of scripts/smoke_api.ps1.
  • Producers outrun consumers — the bounded queue applies backpressure instead of the process eating memory until it dies

Stage 6 — Measure and write it up

Week 10.

Throughput at 1, 2, 4, 8, 16 worker threads. Submit-to-start and submit-to-complete at p50, p99, p99.9. Behaviour under backpressure when producers outrun consumers. Then BENCHMARKS.md and a README carrying the architecture diagram and the decisions behind it.

Gate — [x] PASSED 2026-09-06. Numbers published with machine specs and a reproducible method, holding the standard set in matchbook's BENCHMARKS.md — including saying plainly where the system stops scaling.

Domain model

Design these as real abstractions, not structs with logic sprayed around them. The interfaces are the part an interviewer probes.

Type Role
Job Id, type, payload, attempt count, scheduled_for, state, lease holder
JobState Closed state machine: PENDING → SCHEDULED → RUNNING → SUCCEEDED | FAILED | DEAD, transitions validated in one place
Handler Interface. Executes a job type; a registry maps type name to handler
RetryPolicy Strategy. Given an attempt number, returns the next run time or nothing. NoRetry, FixedDelay, ExponentialBackoff with jitter
JobStore Repository. Persistence behind an interface — in-memory for tests, Postgres in production
Lease A worker's time-boxed claim on a job, renewed by heartbeat, reclaimable once lapsed
WorkerPool Bounded queue plus N threads, graceful shutdown that finishes or cleanly releases in-flight work
Reaper Finds expired leases and due scheduled jobs, returns both to the ready stream

Stack

Layer Choice Note
HTTP Drogon Async, modern C++, has an ORM. Crow if a lighter option is wanted
Kafka librdkafka The canonical client; modern-cpp-kafka wraps it more pleasantly
Redis redis-plus-plus Sits on hiredis, has pipeline and script support
Postgres libpqxx State lives here; Kafka is only transport
Infra Docker Compose Redis, Kafka and Postgres up with one command
Tests GoogleTest Same tooling as matchbook
Load wrk / k6 Submission-side load; the chaos harness is our own
Build CMake + vcpkg vcpkg saves a week of dependency pain on Windows

Schedule, against everything else

Weeks Deadman Daily, 45 min Background
1–2 Stage 1 — engine DSA: arrays, hashing, two pointers, sliding window Trim the resume
3 Stage 2 — API DSA: trees, recursion Build the PEC referral list
4–5 Stage 3 — leases DSA: graphs, heaps —
6–7 Stage 4 — Kafka DSA: DP, intervals Start LLD reps
8–9 Stage 5 — chaos Mixed-set mock rounds LLD: parking lot, Splitwise, rate limiter
10 Stage 6 — benchmarks Timed mocks Rewrite the resume around this project

DSA wins whenever the two collide. A finished scheduler will not save a failed screen, and the screen comes first in every loop.

Evidence for the gates ticked above

Recorded 2026-09-05. Every number here came from a run on Aditya's machine; see BENCHMARKS.md for the machine and the standing warning against comparing across machines.

Stage 1

EngineTest.TenThousandJobsAllExecuteExactlyOnce submits 10,000 jobs to an 8-thread engine, drains, and asserts 10,000 distinct job ids reached the handler with lease_lost == 0. AFailingHandlerRetriesThenLandsInTheDeadLetter asserts exactly max_attempts invocations, a final state of dead, and the error text preserved. RetriesWaitForTheBackoffBeforeRunningAgain asserts each retry actually waited for its backoff.

State transitions are covered by 18 cases in tests/job_state_test.cpp, including every illegal edge, terminal-state closure, and self-transition.

The decision-005 contract suite runs 31 cases against both InMemoryJobStore and PostgresJobStore, including NoJobIsEverHandedToTwoWorkers (8 threads racing for 200 jobs; asserts no duplicates and none lost) and ConcurrentSubmitsOfOneKeyCreateExactlyOneJob.

Full suite: 141/141 passing, with Postgres, Redis and Kafka up.

Stage 2

scripts/smoke_api.ps1 — 30 assertions over the full lifecycle, all passing. Idempotency specifically: the first submission with a key returns 201, the repeat returns 200 with the same job id and the original payload unmodified, and exactly one job exists afterwards.

Stage 3

tests/redis_coordinator_test.cpp — 16 cases, all passing. Includes ALeaseExpiresOnItsOwn, AWorkerCannotStealBackALeaseItAlreadyLost (the compare-and-set race), ConcurrentAcquisitionProducesExactlyOneWinner (16 threads, one winner), and TakingDueJobsIsAtomicAcrossReapers (4 reapers, 300 due jobs, no job taken twice).

Lease recovery end-to-end is EngineTest.AJobWhoseLeaseLapsesIsPickedUpByAnother- Worker, plus the chaos run below, which kills worker processes with taskkill /F.

Stage 4

tests/kafka_transport_test.cpp — 7 cases, all passing. AnUnhandledMessageIsRedeliveredRatherThanLost is the at-least-once guarantee driven directly: a consumer that never commits is replaced, and the message comes back. ACommittedMessageIsNotRedelivered is its converse. TwoConsumersSplitThePartitionsBetweenThem asserts no partition is assigned to two consumers.

Partial. What is not yet directly asserted is a mid-run rebalance under three live worker processes — the tests prove group membership, partition splitting and redelivery-on-uncommitted separately, and the chaos run kills worker processes that are consumer-group members, but no single test observes a partition moving between two running workers mid-batch. That is the remaining work on this gate.

Stage 5

scripts/chaos.ps1 -Jobs 100000 -Workers 4 -KillRate 0.30, run 2026-09-06 against RelWithDebInfo binaries. Full output and machine spec in BENCHMARKS.md.

  workers killed  70
  drained         True

  jobs submitted      100000
  jobs succeeded      100000
  jobs outstanding    0
  handler invocations 100098
  jobs run more than once 98
  side effects fired  100000
  distinct jobs hit   100000
  jobs fired twice    0

  PASS  no job left outstanding
  PASS  every job completed (100000/100000)
  PASS  every job's side effect fired
  PASS  no side effect fired twice
  NOTE  98 job(s) were delivered more than once and absorbed

STAGE 5 CLAIM HOLDS

The 98 is the load-bearing number. Without duplicate deliveries actually happening, "no duplicate side effects" would only mean the case was never exercised. 70 hard kills produced 98 real re-executions, all absorbed.

Note what this does not say: it does not say jobs ran once. Ninety-eight of them ran twice. The claim is at-least-once delivery plus idempotent execution, and that is exactly what the numbers show.

Stage 6

BENCHMARKS.md, written 2026-09-06 from a single run of deadman_bench.exe --benchmark_min_time=0.35s plus the chaos figures above. It carries the machine spec, the standing warning against cross-machine comparison, and — as the gate requires — says plainly where the system stops scaling: InMemoryJobStore throughput falls from 667 k/s at one thread to 126 k/s at sixteen, because one mutex spans the whole claim. The section explains why PostgresJobStore does not share that ceiling and lists what is deliberately not measured.