cockroachdb / cockroachdb/pebble

compaction: use bloom filters to elide point tombstones earlier

Open
#2,245 2 comments 0 reactions 0 assignees View on GitHub
A-storage C-performance T-storage
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.