No first-class pattern for a multi-worker, time-scheduled work queue (FOR UPDATE SKIP LOCKED convoys under concurrency)

## The gap

CockroachDB has no *first-class* way to build a **multi-worker, time/expiry-scheduled work queue**: the pattern where rows carry a future `run_at`/`expires_at`, and a pool of workers each pull "the items due now" and process them. The idiom works, but only with an application-level sharding scheme layered on; there's no native primitive and no documented recommended pattern. Each available mechanism has a limitation for that shape:

1. **`SELECT ... FOR UPDATE SKIP LOCKED` (the SQL/Postgres idiom).** The natural choice, and what teams migrating from Postgres reach for. Under SERIALIZABLE it produces a WriteTooOld **retry convoy** under concurrency, plus a single-leaseholder **CPU peg** from tombstone scanning (Evidence A and B below). It works, but degrades badly at worker-pool concurrency without app-side key-partitioning.
2. **Changefeeds / CDC.** CRDB-native and scalable, but changefeeds emit **on row change**, not when a row's future `run_at` **arrives**. There's no "emit this row at time T." CDC pushes work to consumers as it's created or updated, but it doesn't map to a scheduler whose trigger is a wall-clock deadline stored in the row; bridging the two means running a separate scheduler that re-injects due items into the changefeed's path.
3. **Row-level TTL.** Time-based, but **delete-only** on a cron (`ttl_job_cron`): it evicts expired rows, it doesn't hand them to workers for processing. And it's a single background job, not a worker pool.

A scheduled queue needs two things: *(a)* fire on a stored future timestamp, and *(b)* distribute due items across N workers without them colliding. No single native mechanism does both. FUSL gives (a)+(b) but convoys; CDC gives scalable (b) but not (a); TTL gives (a) but only as deletion, not (b)-style dispatch.

## Why we're posting this

We hit this building an expiry-scheduled work queue and benchmarked the FUSL approach against Postgres, MariaDB, and CedarDB to understand whether the convoy is inherent to the pattern or specific to CRDB.

**What we found (key context):** it's not "Postgres good, CRDB bad." The convoy appears in every engine we tested whose active isolation forces read-set tracking or gap locks onto this workload: Postgres under SSI and CedarDB under OCC both convoy heavily. Where it runs clean (Postgres RC, MariaDB RC), it's because READ COMMITTED sheds that engine's default overhead. The CRDB-specific point is an **asymmetry**: on Postgres and MariaDB, dropping to RC removes the overhead and fixes it; on CRDB, SERIALIZABLE has no such overhead to shed, and RC instead adds durable-replicated-lock cost (~15× worse within CRDB). So the isolation lever that fixes the others isn't available on CRDB, which leaves app-side key-partitioning as the only lever we found.

**What we're asking:**
1. Is there a **recommended CRDB-native pattern** for a multi-worker, time-scheduled queue that we've missed? If FUSL is it, is a **bucketed index** (`(bucket, run_at, id)`, one bucket per worker) the sanctioned way to avoid the convoy?
2. Is the **tombstone-scan CPU cost** (Evidence B) expected, or a rough edge worth addressing?
3. Longer-term: is a **native scheduled-queue / scheduled-changefeed primitive** on the roadmap? This is a common Postgres-migration need.

We have a candidate app-side workaround (the bucketed index above), but it's a schema change the application team is reluctant to adopt, so there's no agreed path yet. That's much of why we're asking: a sanctioned CRDB pattern or a planned native primitive would change the calculus versus pushing app-side sharding.

## Environment

- CockroachDB **v25.4.10**, self-hosted, large multi-node cluster.
- Workload: a work-item queue drained by a worker pool (≈16–64 concurrent workers).
- Isolation: SERIALIZABLE (default). READ COMMITTED was **~15× worse** here. We attribute this to RC's replicated `FOR UPDATE` locks and retry backoff (per CRDB's own docs on RC locking reads), though we haven't profiled the exact split. See the cross-engine table.
- Self-contained reproduction available to share (Python + uv harness; `skip-locked` / `limit-n` / `hash-bucket` modes; single-node localhost + a large multi-node cluster).

## The schema

```sql
-- Minimal queue schema (what the PG / MariaDB / CedarDB benchmarks ran: one index)
CREATE TABLE queue (
id UUID NOT NULL DEFAULT gen_random_uuid() PRIMARY KEY,
run_at TIMESTAMPTZ, -- when this item is next due; NULL = not scheduled
state STRING, -- terminal states should clear run_at to NULL
payload JSONB,
INDEX queue_run_at_idx (run_at ASC) WHERE run_at IS NOT NULL
);

-- Index-heavy queue schema (mirrors the CRDB production table: five secondary indexes,
-- so every claim UPDATE writes through all of them — this is a large part of why the CRDB rows/s are lower
-- and part of why the churned-edge scan is expensive). Same drain query runs against both.
CREATE TABLE queue (
id UUID NOT NULL DEFAULT gen_random_uuid() PRIMARY KEY,
run_at TIMESTAMPTZ, -- the queue/schedule column; NULL = not scheduled
owner_id INT8 NOT NULL, -- stands in for an account/entity id
campaign_id INT8 NOT NULL, -- stands in for a grouping key with fan-out
state STRING NOT NULL,
created TIMESTAMPTZ NOT NULL DEFAULT now(),
payload JSONB,
INDEX queue_run_at_idx (run_at ASC) WHERE run_at IS NOT NULL,
INDEX queue_owner_state_idx (owner_id ASC, state ASC, created DESC) STORING (campaign_id, payload),
INDEX queue_state_pending_idx (state ASC) STORING (owner_id, campaign_id, created) WHERE state LIKE 'PENDING%',
INDEX queue_campaign_owner_state_idx (campaign_id ASC, owner_id ASC, created DESC) STORING (state, payload),
INDEX queue_created_idx (created ASC) USING HASH WITH (bucket_count = 6)
);
```

## The query

A generic queue schema: `queue(id PK, run_at TIMESTAMPTZ, ...)` with a single-column partial index `queue_run_at_idx (run_at ASC) WHERE run_at IS NOT NULL`. Workers claim the head of the queue and reschedule it (a lease) in one statement:

```sql
UPDATE queue SET run_at = now() + '1 hour'
WHERE id IN (
SELECT id FROM queue
WHERE run_at < now()
ORDER BY run_at ASC
FOR UPDATE SKIP LOCKED
LIMIT 1000
)
RETURNING id;
```

N workers run this concurrently to drain the queue head.

---

## Evidence A — SKIP LOCKED does not prevent a WriteTooOld retry convoy

**Observed:** with tens of concurrent workers, ~31% of executions fail with `40001` / `WriteTooOldError` on the `run_at` index key (`/Table/////0`), retrying up to tens of epochs each; individual statements stall for minutes; cluster p99 and one node's CPU spike; throughput collapses. (We call this pileup a "convoy" below: a lock/serialization convoy in the classic sense, where many workers serialize on the same hot keys and collective throughput collapses.)

**Mechanism (as we understand it):** a locking scan runs `SkipLocked` and `FailOnMoreRecent` together. `SkipLocked` skips rows with *active locks*, but once a peer worker commits its reschedule, the lock is gone and only the bumped committed MVCC version remains. The next scanner sees a committed version newer than its read timestamp → `FailOnMoreRecent` → `WriteTooOldError` → serializable restart (the `epo=` epoch bump). So `SKIP LOCKED` cannot skip a *committed newer version*, only a live lock; and all N workers `ORDER BY run_at ASC` onto the same leftmost keys, which makes collisions likely under concurrency.

### Cross-engine comparison

All rows/s below are single-node localhost, same harness, contention profile (many workers, reschedule-in-place so the queue stays deep). **Absolute numbers are not comparable across engines:** the CRDB schema mirrors our production table (five secondary indexes, so every UPDATE writes through all of them), while the PG/MariaDB/CedarDB schemas are minimal (one index). Compare *within* each engine, across isolation levels; the ratios and the retry behavior are the signal, not the absolute rows/s.

| Engine | Isolation | Rows/s (localhost) | Surfaced retries |
|---|---|---|---|
| **CockroachDB 25.4** | SERIALIZABLE (default) | 314 | dozens/round (WriteTooOld); trips our alert |
| CockroachDB 25.4 | READ COMMITTED | 21 (**~15× worse**) | 0 surfaced, but durable-lock + backoff cost |
| **Postgres 17** | READ COMMITTED (default) | 4,268 | **0** |
| Postgres 17 | REPEATABLE READ | 4,340 | 27,886 (cheap first-updater-wins) |
| Postgres 17 | SERIALIZABLE (SSI) | 76 | 35,897 (predicate-lock convoy) |
| **MariaDB 12** | READ COMMITTED | 3,206 | **0** |
| MariaDB 12 | REPEATABLE READ (default) | 220 | gap-lock deadlocks |
| **CedarDB** | SERIALIZABLE (OCC) | 329–2,024 | 21k–42k (OCC commit-time) |

Read this strictly within each engine (the absolute rows/s aren't cross-comparable; different schemas). In each engine, one isolation level convoys and another doesn't, and the pattern is the point:
- **Postgres**: SERIALIZABLE/SSI convoys via predicate-lock read-set tracking (76 rows/s, 35,897 retries); READ COMMITTED and even REPEATABLE READ run clean or cheap because RC sheds that tracking.
- **MariaDB**: REPEATABLE READ (default) convoys via next-key gap locks; READ COMMITTED disables them and runs clean.
- **CedarDB**: SERIALIZABLE OCC validates at commit, so every concurrent claim conflicts (21k–42k retries).
- **CRDB**: SERIALIZABLE convoys (WriteTooOld); and dropping to READ COMMITTED makes it **worse within CRDB** (314 → 21 rows/s), because RC here *adds* durable-replicated-lock cost rather than removing overhead.

That last point is the asymmetry that matters: on Postgres and MariaDB, READ COMMITTED is the lever that turns the convoy off; on CRDB it's not available as a fix (it costs more), which is what leaves app-side key-partitioning as the remaining lever.

---

## Evidence B — MVCC tombstone-scan CPU amplification at the churned index edge

**Observed:** during the convoy, the leaseholder for the hot `run_at`-index range burned **~13 CPU-cores on a single range at ~1.5 QPS**. Cost-per-scan rose ~40× (≈0.2 → ≈8 CPU-seconds per scan) while query volume fell to near-zero and bytes-read stayed ~0 (in-memory). CPU profiles (auto-captured) attribute **~91% of node CPU to the read-only scan path**: `executeReadOnlyBatch → batcheval.Scan → MVCCScanToBytes`, with `pebble … initMinRangeDelIters` / `keyspanIter.materializeSpan` / `truncatingIter.nextSpanWithinBounds` as the dominant leaves. Those are MVCC range/point tombstone iteration.

**Mechanism (hypothesis):** the reschedule (`SET run_at = now()+1h`) deletes the old index entry and inserts a new one, so the oldest-`run_at` edge accumulates a dense band of superseded versions and tombstones faster than GC collects them (short `gc.ttlseconds`, e.g. 600). Every `ORDER BY run_at ASC` scan must then iterate that garbage to reach the first live key: O(tombstones) CPU per scan, all concentrated on one leaseholder.

The retries in Evidence A are arguably working-as-intended, but a scan spending 90%+ of its CPU walking not-yet-GC'd tombstones at a hot index edge looks like a sharper edge worth CRL's read. Two questions:

1. Is the keyspan/range-del iteration cost expected here, or is there a known inefficiency in `initMinRangeDelIters` for a heavily churned prefix?
2. Are there knobs (GC cadence, a `gc.ttlseconds` floor, tombstone-aware scan skipping) that would blunt it?

---

## Scope

This is not a regression; the pattern behaves the same across recent versions on our repro. It's also distinct from the SKIP LOCKED row-skipping reports listed below. The point is the absence of a scalable native pattern for this workload shape.

## Evidence we can share on request

We have the following and are happy to provide it if useful, holding off on attaching until asked:
- A self-contained reproduction harness (single-node localhost + a large multi-node cluster; `skip-locked` / `limit-n` / `hash-bucket` modes) with the cross-engine numbers above.
- Node CPU pprof files showing the ~91% `MVCCScanToBytes` / `initMinRangeDelIters` attribution.
- Hot-range samples: ~13,000 ms CPU/s at ~1.5 QPS on the single hot range.

---

*Related (distinct from this): #167582 / #121917 / #143017 are about SKIP LOCKED skipping rows; #171222 is optimizer limit-pushdown. None cover the retry convoy, the tombstone-scan cost, or the missing scheduled-queue pattern.*

Jira issue: CRDB-65788

Start with the self-contained Python and uv reproduction harness, especially its skip-locked, limit-n, and hash-bucket modes, and review the documented FOR UPDATE SKIP LOCKED query and benchmark evidence. Done means establishing whether CockroachDB has a recommended native pattern, whether bucketed indexing is sanctioned, and whether the tombstone-scan behavior or a scheduled primitive needs follow-up.

Written by the indexing model from the issue text.