Unify master maintenance scheduling (WAL merge / compaction / index / repair)

Goal

Replace the eleven independent scheduling, sweep and discovery loops in lance-context-master with one model: a single leader planner over a per-table demand table, per-(table, kind) scores with priority classes and aging, executor capacity published as (slots per kind, bytes), and one typed failure ledger. The merge-crate fence (target-locks, merge-executions, version barriers, progress watchdog) is not changed; it stays the correctness boundary.

Success criteria:

One place answers "what runs next on table X and why" (GET /api/v1/scheduler/demand?target=).
Scheduling decisions are pure functions of (demand, executors, fence state, ledger, policy, now) and unit-tested without etcd.
Global scheduling env knobs ≤ 12 (today ≈ 71); per-table behaviour from one policy document (today six allowlists).
No planner cycle issues a full prefix scan; one etcd txn per placement (today a 7-key snapshot per candidate plus a running/ page scan per claim).
Starvation cases covered by tests: continuous merger vs prepared compaction, low-count WAL tails, legacy RPCs holding merge slots, alphabet-late tables.

Why now

Metric	Today
Independent scheduling/discovery loops	11
Pacing mechanisms	4 (tokio interval, sleep, etcd `next_batch_ms` cursors, k8s Job lifecycle)
Failure/backoff systems	5
Admission surfaces	3 (5 semaphores, drain gate, 7 etcd ownership keys)
etcd key families	27
Scheduling env knobs	≈ 71
Per-table allowlists	6
PRs 2026-09-30 → 10-08 fixing this layer	~35 of 50

Queue keys are UUIDv7 (generate_id()), so order is approximately enqueue time; what is missing is any priority dimension.

Design highlights

Full design: docs/design/unified-maintenance-scheduler.md. Backlog with file:line references: docs/design/scheduler-improvement-backlog.md.

Scale fit. Tens to low hundreds of active tables, 3–6 masters, tasks lasting seconds to hours. This is a multi-table storage-engine background scheduler (RocksDB column families, ClickHouse MergeTree, Pebble, Hudi table services), not a cluster scheduler. A single leader with a full in-memory view is sufficient; optimistic multi-claimer (what claim_next is today) and Omega-style shared state are rejected.
Demand table per table (pending_generations, pending_bytes, oldest_pending_ms, fragment_count, index_stale, missing_fragments), fed by per-shard watermarks (sealed_through_seq, idempotent under loss/duplication) from writer flush and merge release, reconciled by the existing stats scan, which may lower a watermark only with a newer observed revision. Replaces merge sweep, wal-tail sweep, resident discovery, catch-up admission and the merge-requests loop.
Scores and classes. merge_score = max(gens/min, bytes/min) × age_boost; classes Recovery > Critical merge (≥256 gens) > Commit-ready (generalises fix: give prepared compaction the next merge admission turn #324) > Normal merge > Compact/Index > Tail. Class order alone starves, so two hard bounds apply across classes: max_consecutive_turns[kind] per table and max_turn_wait_secs[kind] promoting to class 1.
One write-turn holder per table = the existing merge-crate lock. Preparation (compaction/index) runs outside the turn, concurrently with the holder and with each other; the planner must never re-serialise merge behind preparation (fix: prepare compaction files without blocking WAL merges #308, Prepare key indexes outside table write ownership #327). Dependencies become demand post-conditions, not task DAG edges.
Executors (resident master, worker, catch-up Job, legacy worker RPC) publish leased heartbeats with slots[kind]; bytes_free is a sample only. Each assignment carries reserved_bytes, headroom = bytes_total − Σ reserved over live assignments (rebuilt from etcd on failover), and executors still enforce the local memory budget. Placements are rate-limited per executor (TiKV PD store-limit). k8s Jobs become an executor type, not a separate controller. Isolating legacy RPCs bounds blast radius only; stall detection stays on the execution's actual read/encode/commit progress.
Typed errors with stable codes replace message-text classification (fix: retry stale maintenance preparations without one-hour cooldown #328 matches on the store_base.rs: path; a path move or Lance wrapper change breaks it, line renumbering does not).
Proportional backpressure: per-table backlog_class so writers slow before the 4096-generation 503 cliff.
Single-leader risks (hot spot, split brain on lease expiry, stale state, thundering herd) and their mitigations are listed in design §5.

Plan

P0 — no behaviour change
- Design doc + backlog doc (docs: design for a unified maintenance scheduler #334, docs: scheduler improvement backlog and migration order #335)
- Extract eligibility() pure function from claim_next, unit tests, skip-reason logging (refactor(master): extract claim eligibility into a pure module #336)
- Stable MaintenanceErrorCode; classify by code in merge/failure.rs (fix(merge): classify stale preparations by a stable error code #338)
- Metrics: schedule_to_bind_seconds, turn_wait_seconds{kind}, commit-ready served/expired, resident pool depth (feat(master): expose scheduling backlog and fairness metrics #339)
- Slow-but-alive index build e2e test (Prepare key indexes outside table write ownership #327 + Report actual merge work, phases, and no-progress state #330 + fix: retry stale maintenance preparations without one-hour cooldown #328 interaction) (test(master): slow-but-alive preparation outlives the idle timeout #340)
- /merge-progress: single-revision read, typed response (fix(master): read merge progress at one etcd revision with a typed response #341)
- Operator runbook (docs: operator runbook for maintenance scheduling #342)
P1 — demand table + shadow planner (every existing loop keeps running unchanged; shadow places nothing and removes nothing)
- P1 data model spec (docs: P1 data model for the unified scheduler #343)
- TableDemand::fold pure function with permutation/idempotency tests (feat(master): pure demand fold over per-shard watermarks #344)
- Writers publish per-shard demand-events watermarks on every flush (feat: publish per-shard demand watermarks on every writer flush #345, detached in fix(server): detach demand publish from the flush and merge-request path #351)
- Executors publish merged_through in the merge-crate release txn (feat: publish merged watermarks in the maintenance release transaction #350)
- Stats scanner additionally writes demand-events (source scan) (feat(master): stats scan publishes scan-sourced demand for every shard #356)
- Fold is a per-dimension join ordered by generation; rebuild-equals-fold property test (fix(merge): demand fold orders by generation, carries age, refuses newer schema #359, replaced fix(merge): make demand folding a per-dimension join #352 after review rounds 3–4)
- Merged watermarks published after release, one put per shard (fix(master): publish merged watermarks after release, one shard per put #357)
- Leader election + planner folds demand-events/ into P/demand/; GET /scheduler/demand (feat(master): leader-elected planner folds demand events into a cache #361)
- Leader election; planner logs intended placements; GET /scheduler/demand
- Executor heartbeats; headroom from durable reserved_bytes (feat(master): executor heartbeats and headroom from durable reservations #362)
- Scores + classes + oldest-first class 1; shadow placements; scheduler_shadow_disagreements_total (feat(master): score merge demand and record shadow placements #363)
P2 — planner owns MergeWal for mode: planner tables, switched per table only once every master runs a policy-aware binary; legacy workers become an executor kind; delete resident-only pool (Reserve resident WAL task capacity beyond legacy merge RPCs #331), wal-tail sweep, resident discovery for migrated tables
P3 — Compact / IndexId / Repair / Retire; catch-up Jobs as executor type
P4 — cleanup: delete pool pollers, multi-key claim, cursor loops, allowlists, ~55 env knobs, 15 etcd key families; split task_store.rs

Mixed-version rule for every phase: old masters ignore unknown key families and keep honouring target-locks/merge-executions; no key family is deleted while any binary reads it.

Open questions before P1

Production table count and hot-table fraction.
Generation size distribution (bytes/rows).
p99 compaction and index-build duration on the largest tables.
Can the rollout server coalesce generations under critical backlog, or must backpressure stay read-side?

PRs

#334 design · #335 backlog · #336 eligibility module · #337 review fixes · #338 error code · #339 metrics · #340 watchdog test · #341 merge-progress · #342 runbook · #343 P1 spec · #344 demand fold · #345 writer demand events · #347 #348 #349 review-2 fixes · #350 merged watermarks in release · #351 #352 #353 #354 #355 review-3 fixes · #356 scan demand · #357 #358 #359 #360 review-4 fixes · #355 real-IO watchdog test · #361 #362 #363 P1.5–1.7 planner · #364 #365 review-5 fixes · #366 review-6 fixes · #367 #368 review-7 fixes + canary runbook · #371 failover + isolation tests

PRs:

docs: design for a unified maintenance scheduler #334 design doc
docs: scheduler improvement backlog and migration order #335 improvement backlog

docs: design for a unified maintenance scheduler (#334)

docs: scheduler improvement backlog and migration order (#335)

docs: fold production review into the scheduler design (#337)

Production review folded in via #337 — thanks, all six points were accepted:

One write-turn holder per table, not one assignment; preparation runs concurrently (never re-serialise merge behind compaction/index).
Hard fairness bounds: max_consecutive_turns[kind] across classes and max_turn_wait_secs[kind] promoting to class 1.
Demand as per-shard watermarks, idempotent under loss/duplication; snapshots lower a watermark only with a newer observed revision.
Assignments carry reserved_bytes; headroom computed from live assignments, rebuilt on failover; executor keeps the local budget check.
Shadow phase keeps every existing loop running; per-table switch only on a homogeneous fleet.
Isolating legacy RPCs bounds blast radius only; stall detection stays on actual read/encode/commit progress.

Factual fixes: generate_id() is UUIDv7 (approx. FIFO, no priority); failure.rs tolerates any line/column digits — path/wrapper changes are the fragility.

PRs so far: #334 design · #335 backlog · #336 P0.1 eligibility pure module (CI running) · #337 review fixes.

refactor(master): extract claim eligibility into a pure module (#336)

feat(master): expose scheduling backlog and fairness metrics (#339)

fix(merge): classify stale preparations by a stable error code (#338)

docs: operator runbook for maintenance scheduling (#342)

test(master): slow-but-alive preparation outlives the idle timeout (#340

docs: P1 data model for the unified scheduler (#343)

P0 status: #336 #338 #339 #340 #342 merged; #341 (merge-progress single-revision) in CI with auto-merge.

P1 data model spec merged as #343 (docs/design/scheduler-p1-data-model.md): per-shard watermarks with epoch rule, durable assignment reservations, leader key, read-only policy schema, shadow-disagreement metric, and the five tests P1 must land with. Code for P1 starts from this schema.

fix(master): read merge progress at one etcd revision with a typed re…

feat(master): pure demand fold over per-shard watermarks (#344)

feat: publish per-shard demand watermarks on every writer flush (#345)

feat(master): stats scan publishes scan-sourced demand for every shard (

feat(master): leader-elected planner folds demand events into a cache (…

feat(master): executor heartbeats and headroom from durable reservati…

P1 shadow phase is code-complete pending #363:

feat(master): leader-elected planner folds demand events into a cache #361 leader + demand cache + GET /scheduler/demand (merged)
feat(master): executor heartbeats and headroom from durable reservations #362 executor heartbeats + headroom from durable reservations + GET /scheduler/executors (merged)
feat(master): score merge demand and record shadow placements #363 scoring/classes (class 1 oldest-first), shadow placements, scheduler_shadow_disagreements_total (CI)

All behind PLANNER_ENABLED (default off). Nothing is placed or removed; a source-level test enforces that no executor path reads assignments.

What has to happen before P2 can start, and none of it is code:

Enable PLANNER_ENABLED=1 on staging with real writers and watch scheduler_shadow_disagreements_total for at least a week. The design says this must approach zero; today we have no idea what it will read.
Answer the open questions from the issue body: production table count / hot fraction, generation size distribution, p99 compaction and index duration. These set critical_generations, max_turn_wait_secs and expected_bytes, which are all defaults right now.
A policy document per table (P/policies/) does not exist yet; P2's per-table mode: planner switch needs it, and the fleet must be homogeneous before any table flips.

Spec §7 tests landed: 1, 2 (#359), 3, 4 (#362), 5, 6 (#363). Not yet: 7 (scan with equal epoch and lower sealed — covered by a_lower_value_from_any_source_changes_nothing in #359 but not named as such), 8 (backpressure bounds — no backpressure code exists yet).

feat(master): score merge demand and record shadow placements (#363)

Fifth production review round, with real numbers: 13,405 tables, 354 with pending, 318 generic. My design assumed tens-to-hundreds of active tables; that was off by two orders of magnitude and the next three findings follow from it. All six fixed in #364:

#	Finding	Fix
1 [P1]	Full prefix read exceeds the 4 MiB etcd client cap at ~27k shard records	Every planner read paged at one revision; reconcile detached from the leader loop so it cannot starve keepalive
2 [P1]	Scan never read merged → lost completion event leaves a merged shard pending forever; first contact reads gen 1001 as 1001 pending	Scan reads the base MemWAL index's merged watermark per shard and publishes it
3	`generic:generic:<name>`	Fixed; `entry.name` already carried the prefix
4	1-byte reservations	Unknown bytes reserve the full per-pass cost; counted
5	"disagreement ≈ 0" is not a gate	Split into `discovery_miss` / `placement_gap` / `phantom_task` / `agree`, each a precise question, documented as observations not a takeover criterion
6	Age after merging past the kept entries wrong/unknown; keepalive starvation	Times map bounded by cap only, filtered by merged on read, answer carries Exact/Upper; only Exact promotes. Keepalive via #1

Test at production shape: 13,405 × 2 shards; asserts the unpaged read fails (not vacuous), paged read returns all, leader holds its lease through a full pass.

Agreed with the recommendation: no P2 takeover, no removal of babysitting loops, until a shadow run at real table count, shard count and size distribution has been read. The design doc's scale assumptions (§2) are wrong and I will correct them in a follow-up.

fix: demand pipeline at production scale (#364)

docs: correct the scheduler design's table-count assumption (#365)

Sixth production review round — five findings, all confirmed, fixed in #366 (CI):

#	Finding	Fix
1 [P1]	Paging bounded keys, not bytes; 512×8 with full time maps → 5.6 MB, fails and loops on the same page	Adaptive pages: halve on >1 MiB or a message-size error, grow back; still one revision
2 [P1]	Cache writes bounded by op count only; 100×20-shard records ≈ 2.7 MB > etcd's 1.5 MiB request cap	Chunk by ops and bytes (768 KiB/txn)
3 [P2]	Long-lived tail never promotes: early timestamps pin the bounded map, Upper bounds excluded from promotion	I had the direction wrong. An Upper bound on flush time is a floor on wait — exactly what "waited ≥ max_turn_wait" needs. Promotion uses the floor from either bound; score aging stays exact-only
4 [P2]	Comparison conflated queued/running, skipped unplaceable tables, wrote zeros on failure	Separate paged sets; per-due-table outcomes `discovery_miss / queued_only / running / placement_gap / phantom_task`; skip-and-count on read failure
5 [P2]	Byte estimate capped at 2×max_bytes; a whole generation is read first	`2 × max(max_bytes, largest generation seen)`; whole local budget when unknown

Scale tests at the reviewer's exact shapes, both asserting the unbounded operation fails so they cannot pass vacuously.

Still true: shard distribution per table in production is unmeasured; the 8/20-shard shapes are test fixtures. Until a shadow run at real shape has been read, no P2, no babysitting-loop removal. That position has not changed across rounds 5 and 6 and I do not expect it to change from code alone.

fix(master): page by bytes, chunk writes by bytes, promote on wait fl…

docs: shadow planner canary runbook (#368)

Seventh production review round: #366 independently verified (8/20-shard paging, byte-chunked writes, 23-hour tail promotion), and a single-master shadow canary in production is cleared. Not cleared: takeover or removing any recovery mechanism.

Three remaining items:

GET /scheduler/demand list mode was still an unpaged read → fix(master): page the demand listing; stop treating average size as max #367: paged, bounded summary (limit ≤ 2000, include_idle, totals); full record only for ?target=.
Byte estimate treated the average generation size as the max → fix(master): page the demand listing; stop treating average size as max #367: every shadow reservation is the whole local budget until per-generation sizes exist; spec now says the shadow capacity model answers "can one unit fit", not parallelism, and placement_gap must not be read as such.
Real-traffic observation → docs: shadow planner canary runbook #368 (merged): canary runbook — enable on one master, what to watch in what order, what each comparison outcome means and does not, what the canary cannot tell you, disable, widen. Explicit that it changes no merge behaviour and that P2 does not follow from canary data alone.

Still open as test gaps: leader-failover rebuild equivalence and sustained concurrent progress isolation.

fix(master): page the demand listing; stop treating average size as m…

test(master): leader failover rebuild and sustained watchdog isolation (

Both remaining test gaps closed in #371 (merged):

Leader failover (spec test 4): old leader aborted without release, lease expires, its token refused; new leader rebuilds identical demand cache, identical shadow placements, identical executor totals, and keeps a durable Bound reservation. Mutation-checked both ways.
Sustained concurrent isolation: four real index builds over several idle windows (two alive at different rates, one frozen from start, one frozen midway). Frozen builds cancelled within the idle window measured from their own last progress; alive builds unaffected. A shared-progress-counter mutation fails it.

Spec §7: tests 1–8 now all landed except 8 (backpressure), which has no code yet. Nothing of mine is open. The canary (docs/operations/shadow-planner-canary.md) is the next step.

Navigation Menu

Repository navigation

Unify master maintenance scheduling (WAL merge / compaction / index / repair) #333

Goal

Why now

Design highlights

Plan

Open questions before P1

PRs

19 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Unify master maintenance scheduling (WAL merge / compaction / index / repair) #333

Description

Goal

Why now

Design highlights

Plan

Open questions before P1

PRs

Activity

beinan commented on Oct 8, 2026

beinan commented on Oct 8, 2026

beinan commented on Oct 8, 2026

19 remaining items

beinan commented on Oct 8, 2026

beinan commented on Oct 9, 2026

beinan commented on Oct 9, 2026

beinan commented on Oct 9, 2026

beinan commented on Oct 9, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions