Skip to content

perf(storage): index shard ownership so startup is linear in shards - #209

Merged
jsam merged 1 commit into
mainfrom
fm/il-r03
Oct 3, 2026
Merged

jsam merged 1 commit into
mainfrom
fm/il-r03

Conversation

@jsam

@jsam jsam commented Oct 3, 2026 •

Copy link
Copy Markdown
Contributor

Startup assigned each persist shard to its knowledge graph by trying every known KG name as a prefix, so it cost O(KGs × shards). This replaces that scan with ShardOwners, an index built once from the KG names. A lookup probes the shard key's : positions in a hash set, so its cost no longer depends on the KG count:

  • Canonical names (no :): one probe at the first :.
  • Legacy stored names containing :, such as user next to user:42: probing right to left gives longest-prefix ownership. This path is behind a flag set when the index is built and runs only when such a name exists.

Ownership semantics are unchanged. A unit test checks the index exhaustively against the old scan, over every shard key on {a,b,:} up to length 6 against 56 legacy and canonical name sets.

Also:

  • Drop cleanup (delete_kg_files, at startup and at runtime) builds the index once instead of scanning per shard.
  • save_knowledge_graph used to flush by the raw prefix "{name}:", so user also flushed user:42's shards. It now flushes only shards the KG owns, counting live and tombstoned KGs.
  • New integration test: canonical, ambiguous legacy, stale-metadata and orphan names, plus KG and relation tombstones. It asserts the exact loaded KG → relation → count map, the same map after a restart, and that the tombstones are cleared.
  • New benches/startup_benchmarks.rs (harness = false) sweeps KGs × shards. It runs on tmpfs because per-shard fsyncs hide CPU cost on disk.

Measurements

Same host, release bench, tmpfs. Median of 3 opens after one warm-up open.

kgs × shards/kg before after µs/shard before → after
4000 × 1 882 ms 797 ms 221 → 199
8000 × 1 2004 ms 1814 ms 251 → 227
16000 × 1 5091 ms 3178 ms 318 → 199
16000 × 1, legacy names 5087 ms 3341 ms 318 → 209

Per-shard cost is now flat as the KG count grows. Peak RSS at 16k KGs: 79.6 MB before, 81.1 MB after, within noise. The remaining ~200 µs per KG is eager per-KG setup, which lazy activation (R02) removes, so #135 stays open.

Hot path

Startup and drop cleanup only. No query, write or delta path changes and no locks are added, so warm Q/W/D are expected to be unchanged. The P00 perf gate was not run locally because the host was too loaded to give a verdict; it runs at the release checkpoint.

Verification

  • cargo fmt --check: clean.
  • cargo clippy -p inputlayer --all-targets --all-features -D warnings: clean.
  • cargo test -p inputlayer --all-features: 3655 passed, 0 failed.
  • 01_knowledge_graph snapshot specs: 8 passed, 0 failed. No .iql.out changed.
  • Mutation check: forcing the canonical path breaks 6 integration tests and 2 unit tests.

Tracker: #199

Startup assigned each persist shard to its KG by trying every known KG
name as a prefix, O(KGs x shards). `ShardOwners` indexes the names once
and probes the shard key's `:` positions instead: one hash probe for
canonical names, a right-to-left longest-prefix probe only when a stored
legacy KG name contains `:`. Ownership semantics are unchanged; an
exhaustive test checks the index against the old scan.

Drop cleanup uses the same index, and `save_knowledge_graph` no longer
flushes a longer legacy KG's shards through a raw `{name}:` prefix.

`benches/startup_benchmarks.rs` sweeps KGs x shards: at 16,000 KGs startup
drops from 5.09 s to 3.18 s and per-shard cost stays flat (~200 us).

Part of #135; lazy activation and eviction remain (R02).
@jsam
jsam changed the base branch from fm/il-rc1 to main October 3, 2026 20:37
@jsam
jsam marked this pull request as ready for review October 3, 2026 20:37
@jsam jsam closed this Oct 3, 2026
@jsam jsam reopened this Oct 3, 2026
@jsam
jsam merged commit 4dd8fe9 into main Oct 3, 2026
13 checks passed
@jsam
jsam deleted the fm/il-r03 branch October 3, 2026 20:52
jsam added a commit that referenced this pull request Oct 4, 2026
…ry request (#249)

The release-checkpoint performance gate fails on main: cheap_query serial
p50 is 1.110x the approved baseline e732cd5 on the 32-vCPU runner
(115 -> 126 us). Concurrent latency and throughput did not move. Bisected
to #214 (per-connection request pipelining), made worse by #222.

Cause: the pipeline runs requests in a `FuturesUnordered`. Its `poll_next`
wakes its own task and returns `Pending` after any poll that polled every
future in the set. With one request in flight, which is every serial
client, that happens on each request's first poll. The connection task
wakes itself, tokio schedules that as a yield, and a yield wakes an idle
worker to take the task. Each request therefore costs one more context
switch (4.0 -> 5.0 per query) and a hand-off of the connection task to
another core. #222 added no work per query but made the hand-off dearer:
user cycles per query rose 15% at the same instruction count.

Fix: keep one never-woken future in the set. After the pipeline's first
poll it is never polled again, so no poll reaches every future and the
forced yield no longer fires. The yield after futures that wake
themselves still applies. Pipelining, ordering, deadlines, cancellation
and the credential fence are unchanged. Nothing is added per request: no
lock, atomic or allocation. Each connection gets one more set node.

Bisect (cheap_query, `?edge(1, Y)`, serial). Server counters per query
from perf stat. Ratios are against e732cd5, from an interleaved probe
with one pinned server per commit, 40 rounds:

| commit | PR | user instr/query | ctx switches/query | p50 ratio |
|---|---|---|---|---|
| e732cd5 | baseline | 1.282M | 4.0 | 1.000 |
| d75ce6e | #208 atomic programs | 1.279M | 4.0 | 0.993 |
| 4578fe6 | #215 notification stream | 1.271M | 4.0 | 0.991 |
| 71a4d24 | #216 online backup | 1.275M | 4.0 | 1.016 |
| 2f621c5 | #200 first-update latency | 1.272M | 4.0 | 1.009 |
| e96df5c | #207 | 1.279M | 4.0 | 0.998 |
| 4dd8fe9 | #209 shard index | 1.272M | 4.0 | 0.987 |
| 277c7f0 | #206 | 1.274M | 4.0 | 1.008 |
| 3554c98 | #214 pipelining, deadlines | 1.296M | 5.0 | 1.020 |
| 3492a59 | #213 | 1.294M | 5.0 | 1.030 |
| 2ba9a5a | #212 provenance | 1.297M | 5.0 | 1.029 |
| 9ed61b4 | #204 key expiry | 1.297M | 5.0 | 1.027 |
| be35ee3 | #221 | 1.297M | 5.0 | 1.013 |
| c98a590 | #222 bounded streaming | 1.298M | 5.0 | 1.047 |
| a6fd628 | #219 wildcard fix | 1.297M | 5.0 | 1.061 |
| b7f7ad6 | #220 WAL durability | 1.300M | 5.0 | 1.056 |
| de54807 | #223 shared standing eval | 1.299M | 5.0 | 1.071 |
| 55ec34d | #225 checkpoint-1 fixes | 1.300M | 5.0 | 1.045 |
| 23712b8 | main | 1.300M | 5.0 | 1.064 |
| this change | | 1.300M | 4.0 | 1.033 |

Confirming A/Bs with the gate's own fixture (fresh pinned servers each
round, 40 rounds, ratio [95% interval]):

- #214 vs its parent 277c7f0: 1.039 [1.027..1.049]
- #222 vs its parent be35ee3: 1.025 [1.006..1.044]
- A/A 3554c98: 1.010 [1.002..1.025]
- e732cd5 -> main: 1.048 [1.028..1.066]
- main -> this change: 0.978 [0.958..0.989]
- e732cd5 -> this change: 1.021 [1.009..1.044], PASS (budget 1.05)

User cycles per query (perf stat, same instruction count): e732cd5 958K,
be35ee3 1053K, c98a590 1206K, this change 1006K.

Full gate, all fixtures, 20 rounds, servers pinned to CPUs 2-15:

- main -> this change: no metric worse. Every required metric is PASS, or
  INCONCLUSIVE with an interval that includes 1.0. cheap_query p50 0.979
  [0.953..1.007].
- e732cd5 -> this change: cheap_query p50 1.029 [1.019..1.072],
  INCONCLUSIVE on a busy host (load average up to 22); bound_query p50
  1.022, PASS. The insert and delta metrics improved since the baseline.

The shared host is about 4x slower per query than the CI runner, so the
same hand-off is a smaller share of each query here than there.

The remaining ~1.7% of user instructions per query since #214 is the
pipeline's own per-request bookkeeping: the boxed request future (one
4-8 KiB allocation), its set node, the request control and the in-flight
maps.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant