PostgreSQL TenantFair claim policy

TenantFair provides exact per-owner logical-run admission plus conditional bounded cross-partition rotation. It does not promise completion order, wall-clock latency, CPU or resource equality, strict round robin, dynamic- population fairness, weighted or preferred share, borrowing, reclaim, or unconditional starvation freedom.

Configuration and engine boundary

TenantFair is the sole PostgreSQL scheduler for required tenancy:

use Docket,
  backend: Docket.Postgres,
  repo: MyApp.Repo,
  tenant_mode: :required,
  claim_policy: [
    implementation: Docket.Postgres.ClaimPolicy.TenantFair,
    default_max_active_runs: 4
  ]

default_max_active_runs is a required integer in 1..2_147_483_647. It is a configured persisted field. After schema validation and before backend children start, every homogeneous TenantFair instance synchronizes the singleton policy row. First startup initializes it; changing the configured value updates it on the next deployment. Restarting with unchanged config is a no-op, so a runtime default change survives until the Elixir option changes. Per-scope overrides are durable runtime state and are never synchronized from application configuration. Independently deployed configurations sharing one domain are unsupported in v0.1.

Legacy remains the omitted-policy default only for tenant_mode: :none. It is tenant-blind and never creates admission markers. Required tenancy rejects Legacy and requires TenantFair with an explicit cap.

Docket.Postgres.RunStore.claim_due/3 remains the only admission entrypoint. It executes one prefix-local docket_tenant_fair_claim statement through the internal ClaimPolicy plan/decode/observe seam. TenantFair and Legacy both lock the singleton policy row and may proceed only in their own admission_mode, so the two engines cannot admit concurrently.

Fairness domain and authority

One fairness domain is one physical PostgreSQL database plus one resolved Docket schema. Prefix or search_path aliases that resolve to the same physical schema name the same domain; different schemas are different domains.

The owner scope is :tenantless or {:tenant, tenant_id}. Tenantless maps to the empty scope_key and is one ordinary partition, not a wildcard or separate scheduling class.

Schema V2 contains four authorities:

• docket_claim_policy: singleton engine mode, persisted default cap, and the domain-global scan_ring_position cursor;
• docket_claim_partitions: per-scope cap override, version, and outcome-backed admission_epoch;
• docket_claim_schedule: stable ring position and exact unfinished count for every partition; and
• docket_runs.tenant_admitted_at: durable logical-run admission identity.

The database, not application memory or telemetry, is authoritative. Every run-creation transaction atomically creates its owner partition; rollback leaves neither the run nor a new partition behind.

Sticky admission

tenant_admitted_at is internal and does not add a public run status. The derived states are:

• queued: healthy running, due, unclaimed, and unadmitted;
• admitted-ready: healthy running, due, unclaimed, and admitted;
• admitted-claimed: healthy running, claimed, and admitted; and
• inactive: future-scheduled, externally waiting, poisoned, or terminal, with no admission.

An admitted identity is a healthy running row with non-null tenant_admitted_at; its claim token may be present or absent. In TenantFair mode, normally:

live_claim_count(scope) <= admitted_run_count(scope) <= max_active_runs(scope)

Lowering a cap below the admitted count creates non-preemptive debt. Existing admissions are not revoked and remain eligible for reacquisition, but no queued run may be promoted until the admitted count falls below the new cap.

FIFO promotion

Promotion is the only null-to-non-null admission transition. Under partition authority, TenantFair freshly counts admitted healthy rows and may promote only when capacity remains. Promotion order is (wake_at, internal id) among due, healthy, unclaimed, unadmitted rows.

Already-admitted eligible work is served before promotion. A queued candidate must come from a contiguous locked and rechecked FIFO prefix. A locked or stale head may underfill a visit but cannot be bypassed, and no candidate cursor rotates around it. A permanently runnable admitted cohort may therefore keep later same-owner work queued; cross-partition rotation is not within-partition time slicing.

An admitted poison outcome releases its marker. An unadmitted poison candidate must be the authoritative FIFO head and requires a free admission slot.

Marker lifetime

The following retain the original marker:

• cooperative drain yield;
• generic immediate claim release;
• claim refresh and reacquisition;
• vehicle replacement; and
• expired-claim steal.

The following clear it atomically with the lifecycle change:

• future scheduling or external waiting;
• terminal completion, failure, or cancellation;
• interruption or another immediate unclaimed signal;
• host-incompatible abandon/backoff; and
• poison.

Waking a previously unadmitted run leaves it queued. Existing claim-token and checkpoint-sequence fences remain authoritative: a stale holder cannot clear a newer claim or admission, and transaction rollback persists neither side.

Authoritative unfinished ring

docket_claim_schedule has one immutable-position row per owner partition:

• scope_key is the primary and foreign key;
• ring_position is a positive, unique, monotonic identity;
• unfinished_count exactly counts committed nonterminal running or waiting rows for the scope; and
• the partial ring index contains exactly rows with unfinished_count > 0.

The count includes ready work, future timers, externally waiting work, live or expired claims, and poisoned running rows. The ring is therefore an authoritative superset of current eligibility, not a hint or cache. Dormant positions may yield unsuccessful inspections, but nonterminal work cannot be omitted.

A zero-count row remains to preserve its position. Transactional triggers maintain the counter. Scope and position are immutable; direct counter writes, underflow, truncation, or deleting a partition with unfinished work fail closed. There is no reconciliation path.

Bounded traversal and locking

The ratified logical-work budgets are:

One inspection creates at most one grant. One call is bounded by 32 grants, 512 exact-key run-lock attempts, and 256 outcomes or mutation inputs. Caller demand may lower those ceilings. These are logical-work bounds, not elapsed- time or query-plan guarantees.

One recursive keyset walk reads the next positive ring position after the durable cursor and wraps to the first. Filling demand stops immediately. Otherwise a qualifying call with a nonempty materialized ring consumes all S inspections, including repeated wrap when the ring has fewer than S positions. An empty ring produces no inspection and leaves the cursor unchanged.

Discovery reads schedule membership through MVCC. Each visit separately tries exact partition authority, so a partition-lock miss is a committed unsuccessful inspection. Run locking freezes no more than K structural IDs before using SKIP LOCKED; it cannot scan an unbounded locked prefix or substitute structural row K + 1. Every locked row is authoritatively rechecked before mutation, and one grant mutates at most Q rows.

Ready/expired class behavior remains portable: demand one honors its advisory preference with fallback; demand of at least two reserves an outcome for each nonempty class before filling remaining demand, and that reservation carries across partition grants. Poison consumes demand and Q but creates no claim token. Stable age/ID order applies within the choices left by partition rotation and class reservation.

The lock graph is:

admission: policy + scan cursor -> partition authority -> run rows
lifecycle: run row -> schedule counter
discovery: MVCC read of schedule ring; no schedule-row lock

Admission requires a writable Read Committed transaction. Unsupported transaction modes, engine conflict, or policy-cursor timeout fail closed before inspection. TenantFair preserves a lower caller lock_timeout; otherwise it caps its waits at 250 ms. A schema-version or validated startup-shape mismatch blocks startup. A partition-lock miss, or a visit with no surviving exact run lock or outcome, is an unsuccessful inspection that advances the cursor. An individual run-lock miss does not prevent another locked candidate in the same visit from producing a grant. Rollback persists no cursor, epoch, admission, or outcome work.

The one-statement rule is a client boundary, not a single-snapshot rule. After locking partition authority, the function's later Read Committed command gets a fresh snapshot for admitted count and mutation. Partition serialization plus that fresh recheck protects the final slot across concurrent callers.

Fixed-window fair-rotation contract

The theorem targets one low-volume partition t. A qualification window opens immediately before the first qualifying TenantFair scan after both of these facts commit:

1. t has positive unfinished_count and occupies the unfinished ring; and
2. an authoritative recheck would permit at least one outcome for t.

It closes at the database linearization point of t's first committed nonempty grant.

For one eligible window:

• P is the minimal fixed cohort consisting of t plus every partition that grants before t;
• C is the fixed, complete, duplicate-free cyclic set of positive unfinished_count positions and contains P;
• only t must remain continuously admissible; competitors may be intermittently eligible;
• no partition outside P grants before t; and
• policy, engine, schema/function identity, budgets, and the supplied L remain fixed.

A zero-to-positive or positive-to-zero ring change, cap or administrative policy change, engine/schema/function change, loss of target admissibility, error, or rollback makes the window ineligible. A positive-to-positive unfinished-count change does not change C. An ineligible event never turns a pending or failed window into a pass.

Target admissibility uses the production mutation rules:

• admitted-ready reacquisition and admitted expired steal are count-neutral and remain permitted at or above the cap;
• queued promotion requires the authoritative FIFO head and a fresh admitted count below the effective cap;
• admitted poison is permitted and releases its marker;
• queued poison must be the authoritative FIFO head and requires a free slot; and
• cap debt excludes queued promotion but not otherwise-valid admitted work.

Loss of partition authority, loss of every viable exact candidate lock, or a stale/empty mutation race does not redefine the population. It is a failed target inspection counted by L.

Units

• An inspection is one visit to the next positive ring position in durable cursor order. When H < S, a call may wrap and revisit a position. Lock skip, cap denial, dormancy, staleness, or empty recheck is unsuccessful.
• A grant is one committed acquisition of partition authority followed by 1..Q committed lease or poison outcomes. Zero outcomes is not a grant.
• An outcome is a committed admitted-ready lease, queued-promotion lease, expired admitted replacement lease, or poison.
• A qualifying call is a committed TenantFair statement that owns and advances the domain cursor. Failure before cursor authority, error, or rollback contributes no call, inspection, grant, outcome, cursor movement, or service epoch.

Let:

• A = |P|;
• H = |C|, where 1 <= A <= H;
• S = 32 inspections per unfilled qualifying call;
• Q = 8 outcomes per grant, further limited by remaining demand; and
• L >= 0 be the maximum consecutive complete target inspections that may fail before the next target inspection commits a grant.

L covers the complete outcome opportunity: partition-lock loss, loss of every exact candidate lock, and stale/empty mutation races all consume a failed target inspection. Finite lock hold time alone does not establish a numeric L.

Scheduler invariants

1. One durable circular cursor is serialized across every poller in the fairness domain.
2. Cursor movement is contiguous. Every inspected position advances it, including denial, staleness, emptiness, and lock skip.
3. Filling demand stops immediately; otherwise a nonempty qualifying call consumes its full S, including wrap.
4. Before the first target inspection and between consecutive target inspections, each competitor in P may receive at most one grant.
5. At most L consecutive target inspections fail; the next target inspection commits a grant.

admission_epoch is outcome-backed service evidence, not the scan cursor. It advances exactly once per committed nonempty grant, regardless of whether that grant returns one or Q outcomes, and never for cap rejection, staleness, emptiness, lock skip, error, or rollback. Cursor movement, epoch increment, and outcomes share one transaction.

Bounds

Count competitor work strictly after the window opens and strictly before the target grant:

competing grants   <= (L + 1) * (A - 1)
competing outcomes <= Q * (L + 1) * (A - 1)

Count qualifying calls through and including the target-grant call:

qualifying calls
  <= (L + 1) * ((A - 1) + ceil((H - A + 1) / S))

The smaller (L + 1) * ceil(H / S) expression is not a claim-call bound when a competitor can fill demand and end a call before the target is inspected.

These formulas bound logical admission units only. Continued polling means qualifying committed calls continue; it does not imply a millisecond, queue- wait, completion-time, throughput, CPU, memory, I/O, processing-time, or unconditional starvation guarantee.

Recovery boundary

Recovery and fair rotation are separate guarantees. Claim TTL permits another caller to steal an expired claim but does not revoke sticky admission. Expired steal, cooperative release, and reacquisition are count-neutral and may remain valid target opportunities at or above the cap.

These paths preserve claim fencing and retry opportunities. They do not establish L, a queue-wait bound, or wall-clock fairness. The theorem applies only when its qualification and complete-opportunity assumptions are independently proven.

Conditional separation from Legacy

The deterministic control uses ordinary ready work, demand one, and stable age/ID order. For N >= 2, seed one hot partition with N older rows, then one low-volume target row, and complete each outcome before the next call.

Legacy selects all N older rows first, so bypass is exactly N. On the equivalent two-partition TenantFair trace with L = 0, the hot partition gets at most one grant or Q outcomes before the target grant, independently of N.

This is separation on one eligible frozen trace, not global dominance for dynamic membership, other class/demand mixes, latency, or throughput.

Schema, migration, and administration

Schema version 2 installs the engine's policy and partition authority, stable unfinished ring, marker and partial indexes, lifecycle triggers, serialized cursor, and the sole six-argument claim function.

The stopped V1-to-V2 upgrade backfills tenant_admitted_at = claimed_at only for healthy claimed rows. Unclaimed rows remain queued; an over-cap tenant becomes debt rather than being trimmed. Fresh installs apply V1 and V2 in one host migration. Custom prefix, failed transactional upgrade, populated backfill, concurrent first partition creation, and rollback/down to V1 are release-gated.

The supported rollout is stopped and homogeneous:

1. stop every Docket dispatcher and run writer;
2. apply the generated transactional migration;
3. deploy one homogeneous application version and engine configuration; and
4. restart processing; TenantFair persists its configured default before starting dispatchers.

Startup requires schema version 2 plus the validated marker-column and sole six-argument function-signature shape. Claim traffic only reads and verifies the initialized active policy under its existing policy lock; it never initializes the default or switches engines. Online migration, mixed old binaries, readiness ledgers, activation ceremonies, and audited mode history are outside v0.1.0. A binary that predates the engine interlock cannot be made safe by new database code alone.

The public facade provides fetch_claim_policy_default, put_claim_policy_default, put_claim_policy_override, reset_claim_policy_override, and inspect_claim_policy. Writes accept an optional :expected_version CAS value; caps must be integers in 1..2_147_483_647. Effective inspection exposes token-free queued, admitted_ready, admitted_claimed, and debt counts. Configured-module forms use the runtime's Repo and prefix without exposing a storage context.

Observability and performance evidence

Production emits identity-free aggregate ClaimPolicy, run-store claim, attempt, poison, and bounded admission-release telemetry. Singleton policy- cursor contention is the only proven :policy_cursor contention phase. Tenant, scope, run, graph, cursor, and claim-token identity are forbidden as ordinary metric labels.

Production invokes the claim function with trace mode disabled and filters all inspection rows/internal columns before decoding public outcomes. Trusted direct inspection may explicitly enable the identity-bearing raw trace. Aggregate telemetry cannot reconstruct per-target bypass.

Timing percentiles, query plans, and the PostgreSQL scorecard may detect regressions but cannot satisfy fairness correctness. See the telemetry guide and benchmark guide for their operational contracts.

The scorecard runs its required-tenancy fairness scenario only with TenantFair. Claim ceiling and fast/slow scenarios run both registered policy variants.

Correctness evidence

The repository includes implementation-level evidence for:

• ring, cursor, class, budget, and epoch mechanics in tenant_fair_ring_test.exs;
• the demand-aware formulas and trace-oracle invariants in fair_rotation_oracle_test.exs;
• cap-two/cap-ten identities, FIFO, debt, steal, poison, interlock, and rollback in claim_policy_tenant_fair_test.exs;
• public-facade CAS/effective counts, engine selection, startup shape, and supervised admission in claim_policy_admin_test.exs, claim_policy_test.exs, backend_test.exs, and dispatcher_test.exs;
• marker lifecycle in run_store_test.exs;
• fresh/populated/prefix/rollback/concurrent-creation migration paths in migration_test.exs.

CI runs the ordinary, core-only, PostgreSQL 13, and PostgreSQL 17 test jobs. Timing, randomized soak, and scenario count remain regression evidence rather than proof of the fixed-window assumptions.