Measure and fix the API's read path: bloom residency, and the 14-pread binary search behind every filter hit

[PaulSnow]

What was measured

CPU profile of a validator under 500 tx/s, 30 s, from Accumulate soak 20260902T041031Z:

item	share
syscall.Syscall6 (flat)	18.45%
— of which pread	16.5% of total CPU
— of which segment.bloomTest → os.File.ReadAt	71.8% of the preads
segment.lookup (the binary search)	18.6% of the preads
segment.readValue (the actual record)	8.9% of the preads
Bloom.Test itself	1.17%

One CPU-second in six is pread. The cost of a read is finding the record, not returning it.

The cost structure, per segment

segment.lookup (segstore.go:339) calls bloomTest first, then binary-searches the index. Reading the code rather than inferring it:

• bloomTest (segstore.go:289) already does the minimal thing — ByteMask computes a byte offset and it reads one byte, short-circuiting at the first clear bit. It does not read the whole filter.
• K is 3 (segstore.go:3693, NewBloomSizedForKeys(count, 3)). BloomBitsPerKey = 12 is bits of space per key, not bits set — the two are separate, and the doc comment says so: "~1% false positives at capacity with k=3".
• The binary search does one pread per probe (segstore.go:357), log₂(count) of them. The "one borrow for the whole binary search" is the file handle, not the reads.

outcome	preads	what it buys
filter says no	1–3	skips a merged segment — 20 blocks of records
filter says maybe	1–3 + ~14 + 1	the record, or nothing

At SealLimit = 12,500 records a segment, log₂(12,500) ≈ 14.

Two consequences worth stating plainly:

1. Skipping is cheap and the filter is doing its job. 1–3 syscalls to rule out 20 blocks is a good trade.
2. Being wrong about it is not. A false positive costs ~15 preads for nothing. At ~1% over a 40-segment walk that is ~0.4 wasted searches per read — roughly the cost of all 40 skips combined.

The validator is being handled elsewhere

Accumulate is adding a read cache for the records its executor reads every block — account URLs, the messages and transactions behind synthetic delivery, anchor chain elements (accumulatenetwork/accumulate#4186). Those are write-once and have strong locality, so a bounded cache removes the store lookup entirely for the protocol path. This issue is not about that path.

The API is a different problem

API reads — an explorer walking history, a client proving an old account state — have none of that locality: arbitrary keys, arbitrary depth, no working set to cache. They are exactly the reads that walk many segments and pay the costs above, and no amount of caching in the executor helps them.

Proposal: measure it outside the protocol first

A standalone benchmark against a synthetic store, with no Accumulate, no consensus and no network — so the read path can be changed and measured without a 20-minute soak per attempt.

Fixture. Build a store of S segments × 12,500 records at realistic value sizes, for S spanning what a chain reaches (10, 100, 1,000, 10,000 segments). Report build time and on-disk size so the fixture is reproducible.

Workloads, each as its own benchmark:

• HitInWindow — a key in the newest 2N segments (what the validator does)
• HitDeep — a key uniformly at random across all S (what an explorer does)
• Miss — a key that is in no segment (the pure walk cost, and the false-positive rate falls out of it)

Variants to compare against the baseline:

• filters resident for the newest 2N only (loadBloom on entry to the window, freeBloom on exit — both already exist)
• filters resident for all S (the unbounded case Roll the key filter over a window of blocks instead of all history #56 is about, as the upper bound on what residency buys)
• index resident or mmapped, to attack the ~14 preads behind a filter hit
• mmap the index file so probes are page faults rather than syscalls

Metrics per lookup, not just wall time: pread count, bytes read, resident bytes, and the filter's observed false-positive rate. Wall time on a warm page cache will flatter everything; the syscall count is what the profile actually caught.

What it should decide

• Whether bloom residency for the 2N window is worth it. Sizing suggests it is cheap: 40 segments × ~18.3 KB × 8 shards ≈ 6 MB per partition engine, bounded by N rather than by chain age — which is the bound Roll the key filter over a window of blocks instead of all history #56 asks for. (18.3 KB is derived from nKeys × BloomBitsPerKey / 8; the benchmark should report the real figure.)
• Whether the ~14-pread binary search is worth attacking, and at what memory cost. An index is far larger than a filter, so "keep the index resident too" is not obviously affordable the way the filter is — this is the question the benchmark exists to answer rather than guess at.
• Whether the false-positive rate justifies a larger k or more bits per key, given a false positive costs ~15 preads and a skip costs 1–3.

Related: #56 (resident bloom memory and open-time scan growing without bound), #33 (a seal costs six fsyncs), accumulatenetwork/accumulate#4186.

[PaulSnow]

Measured

The benchmark this issue asked for is in database/readpath_test.go — a synthetic store, no Accumulate, no consensus, -load to run it. It counts read syscalls from /proc/self/io rather than inferring them, and reports per lookup.

Segments of 12,500 records, 200-byte values, 2,000 lookups a case:

segments	variant	HitInWindow	HitDeep	Miss
10	window-resident	4,285 ns / 16.6	4,282 ns / 16.6	428 ns / 0.0
10	all-resident	4,484 ns / 16.6	4,221 ns / 16.6	420 ns / 0.0
100	window-resident	6,675 ns / 21.0	20,681 ns / 58.4	42,921 ns / 111.0
100	all-resident	3,887 ns / 14.2	5,293 ns / 17.1	5,222 ns / 10.8
1,000	window-resident	6,734 ns / 21.3	1,053,743 ns / 689.8	2,706,442 ns / 1,377.0
1,000	all-resident	3,520 ns / 14.8	60,640 ns / 81.4	99,018 ns / 138.0

(ns per lookup / preads per lookup.)

What it says

The window is fine. Everything below it is not, and it degrades with the segment count.

• HitInWindow is flat — 6.7 µs at 100 segments and at 1,000. The window's filters are resident, so a validator's read does not care how long the chain is. That is the design working.
• HitDeep goes 4.3 µs → 20.7 µs → 1.05 ms as segments go 10 → 100 → 1,000. Preads go 16.6 → 58 → 690.
• Miss is worse: 2.7 ms and 1,377 preads at 1,000 segments. A miss walks every segment, and each cold filter costs its 1–3 syscalls.

Residency is the whole difference. At 1,000 segments, making every filter resident takes a miss from 2.71 ms to 99 µs — 27× faster, 1,377 preads to 138 — and a deep hit from 1.05 ms to 61 µs, 17× faster. At 10 segments the two are identical, which is the control: with nothing to walk, residency buys nothing.

So the 71.8%-of-preads figure in the profile is history segments' filters being fetched to be tested, and it is a direct consequence of the residency rule added in #64: filters resident for the active tier, cold for history. That rule was right about memory and wrong about this.

What it costs to fix

Filters are 12 bits a key, so at 12,500 records a segment:

segments	resident filters
100	1.9 MB
1,000	18.8 MB
10,000	187.5 MB

18.8 MB at 1,000 segments is nothing against 27× on every miss. 187 MB at 10,000 is the growth #64 exists to prevent — which is why the answer is neither of the two variants measured here.

Proposal

A residency budget, not a tier rule. Keep filters resident until a byte budget is reached, newest first, and let the oldest go cold beyond it. That keeps what #64 guaranteed — resident memory bounded, not growing with chain age — while removing the syscalls for the segments anything actually reads. At a 64 MB budget that is ~3,400 segments of filters, far past any working set, and a store larger than that degrades gradually from its oldest end rather than all at once.

Two details the measurement suggests:

• The budget belongs to the store, not the tier. loadBloom/freeBloom already exist and are called at the tier boundary; the change is to call them from a budget instead, and to load on access rather than only on entry to the window.
• mmap is the other shape of this and worth measuring before choosing: the probe becomes a page fault and the page cache decides residency. It would also attack the ~14 preads behind a filter hit, which residency does not touch — at 1,000 segments the all-resident miss still costs 138 preads, and those are binary searches.

Not in this issue

The false-positive rate is not the problem: 0.31% of lookups at 1,000 segments walked for nothing, against a design point of ~1%. The filters are sized correctly (#54); it is what a walk costs that hurts.