S3 change index: stop re-walking the deployment bucket

Amadan discussion: carlos/platform #336. Branch s3-polling-336. Status: rev 3, 2026-10-21. Astra accepted rev 2 at spec level (round 2); rev 3 closes round 2's two cost gaps, marked (codex R2-N). Round 1 findings are marked (codex N); all were accepted.

0. Problem and evidence

Flagship S3 cost $211 for October by the 20th and runs at ~$16/day, up from ~$2/day in early September. S3 server access logs (2026-10-20 21:14Z to 2026-10-21 11:00Z, 5.5M requests, matching Cost Explorer) put nearly all of it on the deployment bucket, made by the box roles:

| Family (per day, whole fleet) | Count | ≈ /month | |---|---|---| | LIST apps/<acct>/<app>/instances/ | 1.17M | $175 | | LIST apps/<acct>/ (delimiter) | 0.49M | $73 | | LIST apps/<acct>/<app>/sidecars/ | 0.34M | $52 | | GET control/certs/* | 1.55M | $19 | | GET accounts/<sqid>/* | 1.41M | $17 | | GET apps/*/*/config-gen.json | 1.23M | $15 | | GET apps/*/*/channels/canary | 0.60M | $7 |

The cost scales with apps × boxes × passes, not with use: about $3 per app per month. The causes, all on main at 3d444a1b:

• provision.listAppSubtree (internal/provision/reconcile.go:2022) lists every account and every app in the bucket; knownAccounts (:1760) re-GETs every account.json.
• Every box runs that walk three times per full pass: provision.Reconcile and ReconcileSidecars under reconcileMu (internal/host/agent.go:1542,1570), then ListAllRecordsStrict in the moves pass (internal/host/movespass.go:1079). refreshOfflineView can add a fourth.
• Full passes fire on any change to the global control/serial (any tenant's console action, read every 2s by fastTick) and on the ungated 5–6 minute instancesLoop (agent.go:3358). Fitted: ~570 passes per box per day.
• The console's StartRunSweep (internal/console/runsweep.go:17) walks every app every 30s.
• configGenLoop (agent.go:1979) GETs each hosted app's config-gen.json every 3–4s; PassFilter (agent.go:2628) GETs every canary channel pointer on every 2s tick; the edge cert mirror (internal/edge/certsync.go:411) GETs every cert every 30s.

1. Rulings (Paul, 2026-10-21)

• R1. The bucket stays the store of record. No database, cache tier or DynamoDB in this work (weighed on #336: DynamoDB is ~20x cheaper per read but is a second required component and a large migration; a cache needs the same change signal this spec adds).
• R2. Fix the change detection: writers record which app changed in the bucket, readers re-read only what changed, a slow full walk remains as the backstop.
• R3. The backstop interval is 30 minutes (answer to §10 Q1).
• R4. Old CLIs writing straight to the bucket converge at the backstop until operators update; the release notes say so (answer to §10 Q2).

2. Goals and non-goals

Goals:

• Steady-state request rate independent of the number of apps when nothing changes; work proportional to what changed when something does.
• No loss of correctness: every reader converges to the bucket's state; the bound on staleness for writers that bypass the index is the backstop interval.
• Provider-neutral: plain S3 API (conditional PUT, conditional GET, ListObjectsV2), works on MinIO and DirStore.
• Target: flagship S3 below ~$100/month, roughly storage, litestream and a polling floor.

Non-goals (follow-ups, named so they are not lost): domains.Reconcile's flat List("apps/") (~60 pages every 5–6 min on the housekeeper box, ~$3 a month), console materialize/settle List("apps/"), the litestream data bucket, and the control/serial mechanism itself, which stays.

3. The change index

3.1 Object

One object per deployment bucket: control/changes.json.

{"schema": 1,
 "entries": {"apps/bab/shop": 41, "accounts/bab": 3,
             "control/certs": 977, "control/edges": 12}}

Each entry is a scope and a generation, a positive integer that only increases. The object is unsigned (like control/serial), carries no authority and is only ever a hint to re-read: a forged or rolled-back index can delay convergence until the backstop, never change what a reader believes about a record (the reader always re-reads the records themselves). Size is ~40 bytes per app; entries are not removed in v1.

3.2 Which writes bump which scope

A pure function ChangeScope(key) (scope string, ok bool) in internal/release:

| Key | Scope | |---|---| | apps/<a>/<b>/<rest> where the first segment of <rest> is not a data prefix | apps/<a>/<b> | | apps/<a>/<b>/{logs,errors,analytics,runs,metrics,schedule-status}/… | none | | accounts/<a>/… | accounts/<a> | | control/certs/… | control/certs | | control/edges/… | control/edges | | everything else (including control/changes.json, control/serial and control/edge-mesh-key*) | none |

The data-prefix list is a denylist on purpose: a missing exclusion costs an extra re-read, a missing inclusion costs staleness until the backstop. runs/ is excluded because run state that readers act on lives in the instance record (ActiveRun), which is in scope. The exact data-prefix set is fixed in the plan from the writer map (#336 thread) and pinned by a table test. Keys outside every scope keep the readers they have today (§5 for the mesh keys).

3.3 Write path

The bump lives inside the two concrete stores, not in a decorator (codex 3, 6, 11). S3Store and DirStore gain an opt-in EnableChangeIndex(); once enabled, each of their four mutation methods, Put, PutFrom, Delete and DeleteIfMatch, bumps the key's scope after the mutation succeeds. Because the hook is in the concrete type:

• every optional extension (ConditionalDeleter, PutStreamer, Opener, SizeLister, PageLister, BucketListDirs, ModLister) is untouched, and every mutation path, including release.DeleteIfMatch (internal/release/conditional_delete.go:29) and streaming PutFrom, bumps;
• callers that type-assert *release.S3Store, such as box publication (internal/host/boxpublish.go:259), still match;
• outer wrappers (NewPrefixStore, the hostops mutation boundary, internal/hostops/mutation_boundary.go:108,188) sit above the hook, so their writes bump, and the index write itself goes straight to the bucket from inside the store, never through the boundary's classifier (internal/hostops/mutation_classifier.go:47,168). That is deliberate: the index carries no authority, so the boundary has nothing to decide about it.

The bump:

1. Get control/changes.json (absent = empty, schema 1).
2. Set entries[scope] = old + 1 (or 1).
3. Put with If-Match on the ETag read, or create-only if absent.
4. On a precondition failure, retry from 1, at most 4 attempts with jitter, all inside a 2s budget detached from the caller's cancellation (the bumpSerial pattern, internal/console/serialbump.go:31).

Properties:

• Bump after write, never before. A reader that sees the new generation and re-lists is guaranteed (S3 strong read-after-write) to see the write. Bumping first would let a reader re-list before the write and record the new generation, missing the write until the backstop.
• Best effort. A failed bump is logged and never fails the write. The write is then visible at the next backstop walk, or sooner if anything else bumps the same scope.
• Coalescing (plan detail): a process may batch several scopes into one read-modify-write, provided each scope's bump still follows its write. Bursts (a purge deleting hundreds of keys under one app, run churn) are expected to coalesce to one bump per scope per batch; contention on the single object is otherwise the same class as control/serial today.

Every opener of the deployment store enables the index: the console (cmd/console/main.go), the box agent and edge (internal/host/agent.go, internal/edge/edge.go), the CLI's direct-bucket openStore() (cli.go:2065) and every other release.NewS3Store call site that opens the deployment bucket. A test walks the AST for release.NewS3Store/ NewS3StoreIn call sites and requires each to be listed as either "deployment, index enabled" or "other bucket" with a reason, so a new opener cannot silently skip the index.

IAM: every role that writes the deployment bucket needs s3:PutObject and s3:GetObject on control/changes.json. The plan checks the deployment-buckets and region-host module policies and the Tito deployment's equivalents; a denied bump is a failed bump (logged, covered by the backstop), never a failed write.

Writes that still bypass the index: binaries built before this change (old CLIs in direct-bucket mode, boxes mid-roll), and any tool writing the bucket directly. The backstop (§4.4) covers them.

3.4 Read path

Two new optional read extensions, implemented by both concrete stores:

• ConditionalGetter.GetIfChanged(ctx, key, etag) returns (body, etag, changed, err); S3 answers 304 Not Modified for an unchanged object. A 304 costs one GET ($0.40 per million), so a 2s poll is ~43k GETs per process per day.
• ETagLister.ListETags(ctx, prefix) returns each key with its ETag. S3 returns the ETag with every ListObjectsV2 entry; DirStore returns the same ETag its Get returns. ETags avoid the one-second LastModified resolution trap ClaimCache needs a settle window for.

The hostops mutation boundary and NewPrefixStore forward both read extensions (codex 6).

Capability fallback (codex 7). A reader uses the index only when its store answers both extensions and the index read succeeds. A store without them (the fleet store door, internal/edge/storedoor.go:149,431, and test fakes), a denied read, or any index error means "unknown", never "empty and unchanged": that pass walks as today. Customer fleet boxes therefore keep today's polling; a tenant-filtered index for the door is a follow-up, because exposing the global index would disclose other tenants' account and app names.

4. The record view (box agent and console)

4.1 State

A RecordView in internal/provision holds, for the whole deployment:

• per account: known/soft-deleted, from account.json, with the generation it was read at;
• per app: the instances/ and sidecars/ key listings with each key's ETag; the parsed record bodies; the trash marker; the instances manifest instances.json (ManifestKey, internal/provision/provision.go:321; seeds and update policy, reconcile.go:995) and the sidecars manifest sidecars.json (internal/provision/sidecar.go:122; placement, sidecar_reconcile.go:328), each through its existing parser and keeping its distinct missing and error semantics (codex 5); and the app's applied generation;
• complete and unreadable flags with today's meanings (strict consumers fail on an incomplete view exactly as they fail on a partial walk today).

It produces the same []Record / sidecar slices and the same known/readFailed results the walk produces today, so Reconcile, ReconcileSidecars, the moves pass, steeringLoop and the console sweeps consume it without changing their logic.

4.2 Refresh

The view keeps two generation maps (codex 4): observed (the latest index it has read) and applied (per scope, the generation its current contents reflect). Refresh(ctx):

1. Conditional GET of the index. Changed: update observed. Unchanged (304): keep observed.
2. For every scope where applied < observed, or that is new: re-read that scope. Step 2 runs on a 304 too, so a scope whose earlier re-read failed is retried on the next refresh. An app scope re-lists instances/ and sidecars/ with ListETags, GETs only keys that are new or whose ETag changed, and re-reads the trash marker and both manifests. An account scope re-reads account.json.
3. Set applied[scope] to the observed generation only for scopes re-read successfully. The view is incomplete while any scope has applied < observed.

4.3 Publication, snapshots and lock order

(codex 1, 2)

• One refresh lock. RecordView.mu serializes every mutation of the view: incremental Refresh and the backstop rebuild (§4.4) alike. A publication therefore always reflects reads that started after the previous publication's reads, so the view never moves backwards, and a slow backstop cannot publish over a newer incremental read. This is the same serialization the walk has today, where Reconcile walks inside reconcileMu (internal/host/agent.go:1529-1542,1570).
• Immutable snapshots. Each publication produces an immutable snapshot with a monotonically increasing epoch, swapped in atomically. Consumers read snapshots; they never hold mu.
• Reconcile and sidecars. Inside reconcileMu, the pass calls Refresh and then takes the current snapshot, so a pass's snapshot is never older than the previous pass's.
• Moves. Today the moves pass walks inside w.pass (internal/host/movespass.go:1061,1079). It keeps that shape, and acts only on live data: inside w.pass it calls Refresh and takes the current snapshot, but uses it only to decide whether there is any move work at all. When the snapshot has a record with a move (or one it cannot decode), the last walk found one, or the worker holds any move state of its own (a wake fence, the strict set, the hold or offline keep view unbuilt or naming a host, archive verdicts, a landing lease, an op journal or page outbox entry on disk), the pass walks the bucket and runs exactly as before the index; otherwise it skips the walk. A snapshot can be older than a walk a pass made while the view could not vouch (a bump that failed), and move steps have side effects in both directions, so they never act on it (final review R1, finding 1). The offline keep view is always read from the bucket. A move started by a write whose bump failed waits for the backstop rebuild. The pass never takes a copy handed over from the Reconcile leg.
• Lock order: reconcileMu → RecordView.mu, and w.pass → reconcileMu → RecordView.mu. RecordView.mu is a leaf: nothing is acquired while holding it. Move operations that take reconcileMu inside w.pass (internal/host/movesoffline.go:1065) keep their existing order, and nothing holds reconcileMu across the moves pass.

4.4 Backstop walk

A full strict walk (today's code path, with ListETags reuse for bodies) rebuilds the view every changeIndexBackstop (30 minutes, R3, jittered ±10%) per process, and at start. Under RecordView.mu it reads the index first, walks, publishes the rebuilt view, and sets observed and applied to the index generations read before the walk began, so a bump that lands during the walk triggers a re-read afterwards, never a skip. Holding mu for the walk blocks incremental refreshes for its duration, which is no worse than today, where every Reconcile pass walks inside reconcileMu.

The backstop bounds staleness for writers that bypass the index. Today those writers (box run/seed/move writes, direct-bucket CLI writes) rely on the 5-minute floor; with the index they converge in seconds, and only failures and old binaries wait for the backstop.

Removals are decided by the bucket's walk. The same writers mean absence in a snapshot is not the bucket's word: a record written without its bump is missing from a Complete snapshot until the next rebuild. So a Reconcile or ReconcileSidecars pass over a snapshot that reaches a removal candidate proved by absence (record gone, a sidecar gone or no longer placeable, the trash marker) runs the record walk once more over the live bucket (scanRecords, scanSidecars over freshStore) and decides every removal in that pass from what that walk read, by the walk's own rules: invalid shapes and empty channels protected before scope, hosts matched across every key (a host re-homed to another key is present), full sidecar eligibility (region, pool, placement from the record and the live sidecars manifest, against this box's inbound), and the live trash marker. A walk that cannot read cleanly keeps every row that pass, as the walk always has. A snapshot pass with no removal candidate reads nothing more. Over any store that is not a snapshot the pass's own walk already is the bucket's, and nothing is read twice (final review R1, findings 2 and 4, amadan #336).

4.5 What triggers a pass, and what it reads

• fastTick keeps reading control/serial every 2s as today and also polls the index (§3.4). The 5s clamp stays.
• A serial change triggers today's full pass, with the record walks replaced by Refresh. Its adopt and config-sync legs keep their current scope (hosted routes), because the serial is also bumped for things outside the index's scopes.
• An index-only change triggers a scoped pass (codex 10): Refresh, Reconcile and ReconcileSidecars over the snapshot, the moves pass, and then adopt (release.Pass, internal/release/adopt.go:682) and config sync (internal/appconfig/syncexec.go:174) restricted to hosted routes whose app scope moved. Changing one app re-reads that app only. A witness test asserts that an index bump for one app causes no read under any other app's prefix.
• instancesLoop's 5–6 minute floor stays, now as a Refresh (one conditional GET when nothing changed) followed by a scoped pass over whatever moved.
• The backstop (§4.4) ends with today's unrestricted full pass, so every leg is re-run over everything at least every 30 minutes.

Known limit (codex R2-10). Serial-triggered passes keep adopt and config sync over every hosted route, because the serial also signals changes outside the index's scopes and there is no inventory of those yet. That fan-out is bounded by the routes a box hosts, not by every app in the deployment, and runs at the serial's rate (about once a minute on flagship): roughly 0.35M GETs a day across the fleet, ~$4 a month. Scoping those passes needs the console to mark serial bumps whose effects the index fully covers; that is a follow-up, measured after rollout before it is designed.

4.6 Console sweeps

• Run sweep (30s): keeps its interval and reads the console's own RecordView after a Refresh. Run state the boxes write (SetRecordRun) is an instance-record write and bumps the app's scope once the boxes run this code. Minutes-stale is already safe here (KeepFor 24h, CAS on every change).
• Orphan-run housekeeping (every twentieth sweep, internal/console/runsweep.go:39,110,232) today lists runs/ for every app with an instance record. It now lists only apps with a run-start activity row (internal/console/apiruns.go:315) in the last 48 hours, the window in which a run's objects can still be live or awaiting cleanup, and does today's all-app sweep once a day as the backstop. Orphans are still found by time (a stray's newest object a day old), not by index movement, since runs/ is outside every scope (codex R2-1).
• Seed sweep (5 min): keeps its strict walk, because its snapshot deletes are proved by absence and must see records listed after the snapshot listing (seedsweep.go:126-131). It now skips the walk entirely when the snapshot listing is empty, since there is nothing to delete; stale-seed abandonment reads the view.

5. GET loops

Every gated read below also has a maximum successful-read age equal to the backstop interval, a read on first use, and a retry on error, independent of index movement (codex 9).

• configGenLoop: GETs an app's config-gen.json only when the app's scope generation moved, or when its last successful read is older than the backstop interval. genCache (agent.go:1641) stays as the ETag comparison.
• Canary pointers (fastMembers → PassFilter): canary routes stay members of every tick, but PassFilter reads a channel pointer only when its app's generation moved or its last successful read is older than the backstop. Direct-bucket promotes from new CLIs bump the app scope, so canaries keep adopting in seconds; old CLIs fall back to the backstop (R4).
• telemetryPass (internal/host/telemetry_pass.go:35): app and account telemetry.json reads are gated on their scope generations plus the age rule, and the account file is read once per pass, not once per app.
• Cert mirror (certsync.go:627): polls the index; when control/certs moves, ListETags and GET only new or changed certs; a full rebuild, the one that drops spent challenge tokens, runs at the backstop and whenever a key disappears from the listing. The boot refresh before the listeners bind is unchanged.
• Home map (internal/edge/homemap.go:320): only the hosts half is gated on control/edges. The mesh keys (control/edge-mesh-key and .next, internal/edgeproof/edgeproof.go:58) keep their independent 30s poll (two GETs per box per 30s), and RefreshAttempted is still recorded on every poll, unchanged ones included, so the five-minute refresh heartbeat (internal/lbhealth/lbhealth.go:36,174) holds (codex 8).

6. Provider boundary

Everything is core: conditional PUT and GET and ListObjectsV2 ETags are plain S3 API, supported by MinIO and implemented by DirStore. No AWS SDK outside internal/release's existing S3 client. A deployment that never arms the readers behaves exactly as today, and so does any store that lacks the read extensions (§3.4). TestDeliveredContractMinio gains coverage for GetIfChanged and ListETags.

7. Rollout

Writers ship first and always bump (cost: ~one extra GET and PUT per relevant write, ~$3/month). Readers are armed per process by CARLOS_CHANGE_INDEX=read (box host.env, console environment), off by default, so a mixed fleet behaves as today. Writers that bump never change any read path, so shipping them is safe with readers disarmed; this includes box publication, which keeps its concrete *release.S3Store (§3.3).

1. Check IAM (§3.3) on dev, flagship and Tito before the release.
2. Release with the writers and dormant readers. Roll dev boxes, dev console, flagship boxes, flagship console (roll order rule).
3. Arm dev (boxes then console). Check: passes still converge (instance create, delete, config set, promote, a run) within seconds; the backstop log line appears every ~30 minutes; request rate on dev's bucket drops (Cost Explorer daily, usage type by operation).
4. Arm flagship boxes, then the console. Measure Cost Explorer daily ListBucket/GetObject for three days against the 2026-10-19 baseline (2.26M LIST, 7.5M GET).
5. Disarm is removing the variable and restarting: readers fall back to walking, writers keep bumping harmlessly.

The census overlay for the touched packages is owed per the plan14 process (#280). Release notes tell operators to update the CLI (R4).

8. Testing

• Production-wired witnesses: the write hook is exercised through the real openers (console, agent, CLI direct mode) and through the final claim-enabled store handles (hostops boundary, prefix stores) against DirStore, not a fake (codex 6); box publication runs through the index-enabled opener (codex 11); the AST opener test from §3.3.
• Capability preservation: every optional extension the concrete stores implement today is still implemented with the index enabled, and every mutation method bumps (codex 3).
• Invariant simulation: random interleavings of writers (some bumping, some bypassing, some failing their bump), incremental refreshes, backstop walks and consumers, on DirStore. Invariants: (a) after a Refresh that observed generation g for a scope, every write to that scope that bumped to ≤ g is visible in the view; (b) after a backstop walk, the view equals a fresh strict walk; (c) published epochs only increase and no scope's contents ever revert to an older read; (d) a strict consumer never receives an incomplete view as complete; (e) a scope whose re-read failed is retried on the next refresh even when the index is unchanged. Named interleavings that must be in the seed set: the backstop lists an app before a record appears while an incremental refresh sees and publishes it (codex 2); a pass captures a snapshot, stalls, and another pass consumes a newer one before the first reaches w.pass (codex 1); an app refresh fails after the index moved and the next index read is a 304 (codex 4). One 3000-seed sweep per revision, niced, per the CPU budget. Mutation checks: bump before write; record generations for failed scopes; skip the before-walk index read in §4.4; publish the backstop outside mu; consume a handed-over snapshot in the moves pass. Each must fail the simulation.
• Scoped-pass witness: one app's bump causes no reads under any other app's prefix (codex 10).
• Gated-read ages: telemetry, config-gen, canary pointers and certs are re-read at the age bound with the index unchanged (codex 9); mesh-key rotation reaches the home map with control/edges unchanged, and the health heartbeat survives unchanged polls (codex 8).
• Fallback: a store without the read extensions, and a denied index read, both produce today's walk, never an empty view (codex 7).
• Table tests for ChangeScope; unit tests for GetIfChanged and ListETags on both stores, plus MinIO in the delivered-contract test.

9. Expected effect

| Family (per day) | Today | After (estimate) | |---|---|---| | Record walks (LIST) | ~2.0M | ~70k (backstop 48/day/process + changed apps) | | Index + serial polls (GET) | 0.13M | ~0.35M | | Record and manifest bodies (GET) | ~2M | changed only | | config-gen + canary + certs + accounts (GET) | ~4.8M | changed only + age-bound re-reads |

Expected flagship S3: ~$50–90/month (storage $16, transfer ~$25, litestream ~$26, requests ~$10–25), flat as apps are added.

10. Questions for Paul (answered 2026-10-21, see R3 and R4)

1. Backstop interval. 30 minutes bounds staleness for old binaries and failed bumps at ~$5/month. 15 minutes doubles that cost; 60 halves it. Recommendation: 30.
2. Old CLIs in direct-bucket mode (promote, env set, trash): their writes converge at the backstop (up to 30 minutes) instead of within seconds as today (configGenLoop's 3s poll, canary pointers read every tick) until operators update the CLI. Console and new-CLI writes are unaffected.

11. Review log

• Round 1 (Astra, bbae135c): reject, 3 P1 and 8 P2. All accepted: codex 1 (moves snapshot ordering, §4.3), 2 (backstop publication ordering, §4.3–4.4), 3 (capabilities, §3.3), 4 (304 retry, §4.2), 5 (manifests, §4.1), 6 (hostops order, §3.3–3.4), 7 (fleet door, §3.4), 8 (mesh keys and heartbeat, §5), 9 (telemetry age, §5), 10 (per-app fan-out, §4.5), 11 (box publication, §3.3, §7).
• Round 2 (Astra, ca129623): accept at spec level. Round 1 dispositions: ten resolved, 10 partly (serial-triggered fan-out). New: R2-1 (orphan housekeeping). Rev 3 closes R2-1 (§4.6) and records R2-10 as a measured known limit (§4.5).