From a review of how the store manages keys once they leave the window. The serious one is #90; these are the rest, kept together so they are not lost.
1. Every filter runs K=3 at 12 bits/key, which is not the optimum
NewBloomSizedForKeys(count, 3) is used for segment indexes (indexmerge.go:192, segstore.go:3804), block sets (blockset.go:329), day filters (dayfilter.go:176) and key filters (segstore.go:929). Measured on real keys, 200k absent probes against a 120k-key filter:
| filter |
pages/probe |
false positives |
| scattered, 12 bits, k=3 (today) |
3 |
1.140% |
| blocked, 12 bits, k=3 |
1 |
1.071% |
| blocked, 12 bits, k=8 |
1 |
0.318% |
| blocked, 16 bits, k=8 |
1 |
0.060% |
Blocking every key's bits into one page makes a probe one page touch however many hash functions it uses, which in turn makes the hash count free, and the optimum is about 0.7 x bits per key. K=3 exists because the current layout scatters bits and each hash function costs a page. Cost of the change: it alters the bit layout in every .idx and .bset, so a format version bump and a rebuild. Measurements are in database/keytable_sim_test.go (TestKeyTableBloomSim).
2. The day filter allocates the bitmap its bound exists to prevent
dayfilter.go:176:
bloom := NewBloomSizedForKeys(keys, 3) // allocates keys*12/8
if DayFilterMaxBytes > 0 && bloom.NumBytes > DayFilterMaxBytes {
bloom = newBloomSized(DayFilterMaxBytes*8/BloomBitsPerKey, ...)
}The first line already allocates the ~648 MB the comment at dayfilter.go:70 says must never be held, on the pack path with every shard pinned, before the cap is applied. Compute the size, clamp, then allocate.
3. SetStore.build has no such bound at all
blockset.go:329 sizes its bloom from the summed key count with no cap, and holds bloom.Map live from there until blockset.go:402. A first pack over a long backlog hits exactly the spec 1.2 problem DayFilterMaxBytes was written to avoid.
4. SetStore is not independently safe against concurrent builds
closeFinishedGroups snapshots a group's sets under the mutex (blockset.go:476), releases it, builds the filter, then re-reads state to publish. If a set could join that group in the gap, the committed filter would definitively deny that set's keys. In-process this is closed by KVShard.packMu, whose comment names exactly this failure — but the guard lives in KVShard, not in SetStore, and SetStore.build's own overlap check at blockset.go:294 reads Newest() outside the mutex it takes at :442. There is also no directory or process lock anywhere in the package, so two processes over one database directory would defeat both packMu and the PID-qualified tmp name.
5. SetGroupBlocks is validated only at open
openDayFilter refuses a filter built under a different group size (dayfilter.go:275), which is right, but it runs once at open and the in-memory dayFilter does not retain the size it was built under. If the exported var changes after OpenSetStore, setGroup computes group numbers under the new size while findDayFilter matches on the bare integer, so a filter built over one block range can be consulted for another and answer a confident "not here".
6. ImportSegmentFile reports success after dropping the filters
segstore.go:3581: after break on an addSegmentKeys error, return s.writeManifest() overwrites the named err. The filters were dropped, which is the safe direction, but the caller is told the import succeeded and never learns the store is now walking.
Also worth knowing
ForEach holds a dedup set proportional to distinct keys (iterate.go:20), so export and consistency checks cannot run at the billion-key scale the design now targets. The comment says so and names the fix: the k-way merge in indexmerge.go already emits keys in order with no such set.
From a review of how the store manages keys once they leave the window. The serious one is #90; these are the rest, kept together so they are not lost.
1. Every filter runs K=3 at 12 bits/key, which is not the optimum
NewBloomSizedForKeys(count, 3)is used for segment indexes (indexmerge.go:192,segstore.go:3804), block sets (blockset.go:329), day filters (dayfilter.go:176) and key filters (segstore.go:929). Measured on real keys, 200k absent probes against a 120k-key filter:Blocking every key's bits into one page makes a probe one page touch however many hash functions it uses, which in turn makes the hash count free, and the optimum is about 0.7 x bits per key. K=3 exists because the current layout scatters bits and each hash function costs a page. Cost of the change: it alters the bit layout in every
.idxand.bset, so a format version bump and a rebuild. Measurements are indatabase/keytable_sim_test.go(TestKeyTableBloomSim).2. The day filter allocates the bitmap its bound exists to prevent
dayfilter.go:176:The first line already allocates the ~648 MB the comment at
dayfilter.go:70says must never be held, on the pack path with every shard pinned, before the cap is applied. Compute the size, clamp, then allocate.3.
SetStore.buildhas no such bound at allblockset.go:329sizes its bloom from the summed key count with no cap, and holdsbloom.Maplive from there untilblockset.go:402. A first pack over a long backlog hits exactly the spec 1.2 problemDayFilterMaxByteswas written to avoid.4.
SetStoreis not independently safe against concurrent buildscloseFinishedGroupssnapshots a group's sets under the mutex (blockset.go:476), releases it, builds the filter, then re-reads state to publish. If a set could join that group in the gap, the committed filter would definitively deny that set's keys. In-process this is closed byKVShard.packMu, whose comment names exactly this failure — but the guard lives inKVShard, not inSetStore, andSetStore.build's own overlap check atblockset.go:294readsNewest()outside the mutex it takes at:442. There is also no directory or process lock anywhere in the package, so two processes over one database directory would defeat bothpackMuand the PID-qualified tmp name.5.
SetGroupBlocksis validated only at openopenDayFilterrefuses a filter built under a different group size (dayfilter.go:275), which is right, but it runs once at open and the in-memorydayFilterdoes not retain the size it was built under. If the exported var changes afterOpenSetStore,setGroupcomputes group numbers under the new size whilefindDayFiltermatches on the bare integer, so a filter built over one block range can be consulted for another and answer a confident "not here".6.
ImportSegmentFilereports success after dropping the filterssegstore.go:3581: afterbreakon anaddSegmentKeyserror,return s.writeManifest()overwrites the namederr. The filters were dropped, which is the safe direction, but the caller is told the import succeeded and never learns the store is now walking.Also worth knowing
ForEachholds a dedup set proportional to distinct keys (iterate.go:20), so export and consistency checks cannot run at the billion-key scale the design now targets. The comment says so and names the fix: the k-way merge inindexmerge.goalready emits keys in order with no such set.