# The Tiered Fair Queue (/docs/concepts/tiered-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 [#what-it-delivers]

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

* **Step tasks** — the units a [Step Worker](/docs/concepts/coordinator-workers)
  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 [#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 [#tiers-and-weighted-sampling]

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

| Kind                                       | Weight |
| ------------------------------------------ | ------ |
| `Continue` (in-flight run making progress) | 10     |
| `Start` (a fresh run)                      | 1      |
| `LatencyCanary`                            | 1      |

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 [#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 [#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.

```mermaid
flowchart TD
    A["Dispatcher"] --> B{"SyncMatch<br/>channel ready?"}
    B -->|hit| C["In-process Go channel"]
    B -->|miss| D["Durable tiered queue"]
```

## Wakeups and the dedup boundary [#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.

<Callout title="Why not dedup wakeups?">
  It's tempting to dedup wakeups to save ticks. Ductor deliberately doesn't:
  making the tick itself idempotent (via `record_version`) is safer than trying
  to suppress wakeups, because a *missed* wakeup stalls a run while a *redundant*
  wakeup costs almost nothing. See
  [Optimistic Locking](/docs/concepts/optimistic-locking).
</Callout>

## Where to go next [#where-to-go-next]

* [Coordinator & Step Workers](/docs/concepts/coordinator-workers) — what consumes these tasks.
* [Optimistic Locking](/docs/concepts/optimistic-locking) — why redundant wakeups are cheap.
* [Data Flow](/docs/architecture/data-flow) — where the queue sits in the overall system.