cockroachdb / cockroachdb/pebble
compaction: use bloom filters to elide point tombstones earlier
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
It seems feasible to develop a heuristic that sometimes uses lower-level files' bloom filters to elide point tombstones earlier if the bloom filters indicate a key is not present. When successful in proving a tombstone is no longer needed, it would prevent the write amplification of writing them to disk + the CPU overhead of nexting through the tombstones during reads. A heuristic could enable this for a compaction only if the inputs have many point tombstones according to their sstable properties and the compaction overlaps sufficiently few files in lower levels.
Bloom filters are defined over prefixes only, so this does not seem beneficial in regions of the keyspace with many versions of the same key. This might be able to be addressed by restricting this optimization to compactions overlapping a keyspan (eg, the lock table, the raft log) or with a heuristic consulting a sstable property on lower-levelled sstables containing the number of unique prefixes within sstable (to compare versus the total entries, to get a sense of the number of duplicates).
Jira issue: PEBBLE-155
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.