Design a multi-tenant distributed delay queue and webhook/payment retry timer service supporting 100M pending delayed jobs (delays from 1 second to 30 days), 50K schedules/sec, < 500 ms firing jitter, at-least-once idempotent dispatch, and zero job loss on node failure.
From patterns to decisions.
Partition jobs by `hash(job_id)` into Raft/replicated RocksDB WAL shards, load only the next 15-minute window into a leader-elected Hierarchical Time Wheel, and dispatch via an idempotent worker queue.
Separating 30-Day Disk Storage from 15-Minute RAM Wheels.
Assume 1 KB average job payload: 100M * 1 KB = 100 GB total pending state. At 50K schedules/sec, 15 minutes of near-term jobs is 50K * 900s = 45M lightweight (fire_at_ms, job_id) pointers (~1.4 GB across 16 shards = ~90 MB/shard).
Distant jobs stay compressed on SSD in RocksDB keyed by fire_at_bucket || job_id.
15-Minute Lookahead Sizing
1.Stage Objective: Size 100M pending jobs and justify why only a bounded lookahead window belongs in RAM.
2.Level (Foundation): Assume 1 KB average job payload: `100M * 1 KB = 100 GB` total pending state. At 50K schedules/sec, 15 minutes of near-term jobs is `50K * 90
3.Operational Invariant: 100 GB of 30-day payloads stay on disk while ~90 MB/shard of pointers run in RAM Time Wheels.
Caption: 100 GB of 30-day payloads stay on disk while ~90 MB/shard of pointers run in RAM Time Wheels.
Partitioned RocksDB Shards with Raft Leader Leases.
Partition into 32 virtual shards replicated across 3 nodes via Raft (or Kafka + standby). Only the active Raft leader for a shard runs the RAM Time Wheel and dispatches timers.
On leader failure, the newly elected leader scans [last_acked_cursor, now + 15m] from RocksDB into a fresh Time Wheel in < 2 seconds.
Raft-Replicated Timer Shards
1.Stage Objective: Achieve zero job loss and < 10s failover without split-brain double-firing.
2.Level (Foundation): Partition into 32 virtual shards replicated across 3 nodes via Raft (or Kafka + standby). Only the active Raft leader for a shard runs the R
3.Operational Invariant: Leader leases ensure one active Time Wheel per shard while RocksDB replication preserves durability.
Caption: Leader leases ensure one active Time Wheel per shard while RocksDB replication preserves durability.
Streaming Near-Term Buckets into the Hierarchical Time Wheel.
Maintain a loaded_horizon_ms watermark. Every 5 seconds, a background loader scans RocksDB [loaded_horizon_ms, now + 15m] and inserts pointers into the Time Wheel. Jobs arriving with fire_at <= now + 15m insert into BOTH RocksDB and the RAM Time Wheel immediately.
class ShardScheduler:
def __init__(self, wal_store, time_wheel, dispatch_queue) -> None:
self.wal = wal_store
self.wheel = time_wheel
self.dispatch_queue = dispatch_queue
self.horizon_ms = 0
def schedule(self, job_id: str, fire_at_ms: int, payload: bytes, now_ms: int) -> None:
if not job_id:
raise ValueError('job_id is required')
self.wal.put_idempotent(fire_at_ms, job_id, payload)
if fire_at_ms <= self.horizon_ms or fire_at_ms <= now_ms + 900_000:
self.wheel.add_task(fire_at_ms, job_id)
def cancel(self, job_id: str, fire_at_ms: int) -> bool:
removed = self.wal.mark_cancelled(fire_at_ms, job_id)
self.wheel.cancel_task(job_id)
return removedDual-Write Lookahead & Cancel
1.Stage Objective: Implement safe lookahead loading, O(1) cancellation, and bounded-error dispatch.
2.Level (Intermediate): Maintain a `loaded_horizon_ms` watermark. Every 5 seconds, a background loader scans RocksDB `[loaded_horizon_ms, now + 15m]` and inserts po
3.Operational Invariant: Near-term jobs enter both RocksDB and RAM immediately; cancellations tombstone WAL and unlink O(1).
Caption: Near-term jobs enter both RocksDB and RAM immediately; cancellations tombstone WAL and unlink O(1).
Two-Phase ACK, Lease Timeouts & Idempotency Keys.
When a bucket fires, move jobs to IN_FLIGHT with a 30-second visibility lease and push (job_id, attempt_no, idempotency_key) to the Worker Pool. Workers call the downstream webhook/payment API with Idempotency-Key.
If the worker ACKs, tombstone the job in RocksDB; if the 30s lease expires, reschedule with exponential backoff + jitter.
Visibility-Lease Dispatch Flow
1.Stage Objective: Guarantee every due job executes at least once without losing jobs if a worker crashes mid-flight.
2.Level (Intermediate): When a bucket fires, move jobs to `IN_FLIGHT` with a 30-second visibility lease and push `(job_id, attempt_no, idempotency_key)` to the Work
3.Operational Invariant: 30-second worker leases and idempotency keys ensure crash-safe at-least-once execution.
Caption: 30-second worker leases and idempotency keys ensure crash-safe at-least-once execution.
Self-Scheduling Exponential Backoff & Dead-Letter Queues.
When attempt k fails with a retryable 5xx/429, the worker re-enqueues job_id into the same Delay Queue with delay = min(max_delay, base * 2^k) + uniform_jitter. After max_retries (e.g., 8 attempts) or a permanent 4xx error, route the payload + failure trace to a Dead-Letter Queue (DLQ) for operator replay.
Retry Loop & DLQ Sink
1.Stage Objective: Feed failed attempts back into the delay queue cleanly without blocking healthy partitions.
2.Level (Advanced): When attempt `k` fails with a retryable 5xx/429, the worker re-enqueues `job_id` into the same Delay Queue with `delay = min(max_delay, base
3.Operational Invariant: Failed jobs self-schedule into the delay queue with jittered backoff until ACK or DLQ.
Caption: Failed jobs self-schedule into the delay queue with jittered backoff until ACK or DLQ.
Handling Midnight-UTC Cron Spikes & Hot Tenant Shards.
If 5M billing jobs all schedule for 00:00:00 UTC, a single second bucket will spike. Mitigate by (1) adding deterministic sub-second/minute jitter on non-strict schedules, (2) enforcing per-tenant token-bucket dispatch limits so one noisy tenant cannot starve others, and (3) capping per-tick worker queue depth.
Per-Tenant Dispatch Shaper
1.Stage Objective: Prevent millions of jobs scheduled for `00:00:00 UTC` from overwhelming downstream workers.
2.Level (Advanced): If 5M billing jobs all schedule for `00:00:00 UTC`, a single second bucket will spike. Mitigate by (1) adding deterministic sub-second/minut
3.Operational Invariant: Per-tenant token buckets and deterministic jitter smooth midnight-UTC firing spikes.
Caption: Per-tenant token buckets and deterministic jitter smooth midnight-UTC firing spikes.
Measuring Firing Jitter, Lookahead Lag & Zombie Leases.
Track firing_jitter_ms = actual_dispatch_ms - fire_at_ms (p99 < 500 ms), lookahead_watermark_lag, dlq_ingress_rate, and raft_commit_latency. Run synthetic canary timers every second per shard to verify end-to-end firing SLA.
Jitter & Canary Telemetry
1.Stage Objective: Alert on < 500 ms jitter violations and Raft replication lag before timers drift.
2.Level (Advanced): Track `firing_jitter_ms = actual_dispatch_ms - fire_at_ms` (p99 < 500 ms), `lookahead_watermark_lag`, `dlq_ingress_rate`, and `raft_commit_l
3.Operational Invariant: Per-shard synthetic canary timers continuously validate the < 500 ms firing jitter SLO.
Caption: Per-shard synthetic canary timers continuously validate the < 500 ms firing jitter SLO.
Practice: Make the trade-off yourself.
Why does the scheduler keep only a 15-minute lookahead window in the RAM Time Wheel instead of all 100M 30-day jobs?