The Tiered Fair Queue

Ductor runs work on behalf of many tenants at once. If delivery were naive FIFO, a single tenant enqueuing a million tasks could starve everyone else. The tiered fair queue is the scheduling plane that prevents that: a Redis-backed queue that delivers work fairly across tenants while keeping enqueue and dequeue atomic.

What it delivers

The queue is the durable cross-node transport for two kinds of work:

• Step tasks — the units a Step Worker picks up and executes.
• Coordinator wakeups — the signals that tell a Coordinator "this run has something to do; tick it."

Work items are scoped by a pool (the partition) and a tenant. That scoping is what makes fair scheduling possible.

Fairness across tenants

The unfair-queue failure mode is simple: one tenant with many partitions crowds out a tenant with few. Ductor's fair scan fixes this with a two-tier pointer walk instead of a single global cursor:

1. Pick the single earliest-due tenant from a tenant-level sorted set.
2. Within that tenant, pick its earliest-due partitions.
3. Join partition metadata in one batched read.

Because selection goes tenant first, then partition, a tenant is scheduled based on its own earliest work regardless of how many partitions it holds. Pointer sets are maintained on every enqueue, so even a tenant whose only work is currently rate-limited or backlogged stays visible to the scheduler — it isn't silently forgotten.

Tiers and weighted sampling

"Tiered" refers to the backlog kind of an item — roughly, whether it's fresh work or continuing work:

When the scheduler draws from the backlog it uses a weighted reservoir shuffle: continuations are sampled roughly ten times as often as fresh starts. The effect is that work already in progress tends to finish rather than being buried under a flood of new arrivals — latency for in-flight runs stays bounded even under load.

Atomicity via Lua

Every state transition on the queue is a single Redis Lua script. Redis runs a script atomically on its single thread, so each script bundles all of its reads and writes into one indivisible step — there is no window for a partial update.

The core scripts:

• enqueue.lua — checks the idempotency key, evaluates GCRA rate limiting, handles debounce/singleton semantics, then atomically writes the item, sets the idempotency key with a TTL, adds it to the ready or backlog sorted set, and updates the fairness pointers. It returns a status code (enqueued, already-exists, throttled, backlog-full, and so on).
• peek.lua + check_and_lease.lua — the modern dequeue path: peek the earliest ready item, then atomically validate concurrency limits and lease it to a worker. (An older single-script dequeue_atomic.lua still exists but is deprecated.)
• Lease and recovery scripts (extend_lease.lua, partition_recover.lua, partition_requeue.lua), dead-letter scripts (move_to_dlq.lua, nack_or_dlq.lua, retry_from_dlq.lua), and backlog promotion (backlog_promote.lua).

Rate limiting uses GCRA (a token-bucket variant) per partition, evaluated before any state mutation — a throttled item either returns untouched or parks in the backlog at its retry time. Concurrency ceilings (per pool, per tenant, or custom) are enforced at lease time, not enqueue time, so an item is admitted only when there's actually capacity to run it.

SyncMatch: the zero-latency fast path

Going through Redis is the durable path, but it isn't always the fast path. When a worker is co-located with the coordinator in the same process, SyncMatch delivers a step task directly through an in-process buffered Go channel — no Redis round-trip.

The dispatcher tries SyncMatch first (unless the step explicitly prefers the tiered queue) and falls back to the durable queue on a miss — no registered channel, or a full buffer. Every attempt is metered (hit, miss_no_channel, miss_buffer_full) so you can see how often the fast path is taken. This is what makes the synchronous "trigger and wait" call path low-latency without sacrificing the durability guarantee: if SyncMatch misses, the task still lands on the durable queue.

Wakeups and the dedup boundary

Coordinator wakeups ride the queue on a dedicated system partition. There are two flavors:

• An immediate step-complete wakeup, whose queue item ID is a random UUID — deliberately not deduplicated, because the coordinator's optimistic-lock tick is the real dedup boundary (a redundant wakeup just produces a no-op tick).
• A timer wakeup fired at a future time, whose item ID is a deterministic logical-timer key, carrying the run ID, a reason, and a requeue count.

Where to go next

• Coordinator & Step Workers — what consumes these tasks.
• Optimistic Locking — why redundant wakeups are cheap.
• Data Flow — where the queue sits in the overall system.