cockroachdb / cockroachdb/pebble
db: consider reworking rangedel, mergingIter and levelIter interactions
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
Currently, there's an intricate coordination dance performed between `mergingIter` and `levelIter` in order to make range deletions work. This dance has several complexities that make it fragile and difficult to grok. The introduction of range-key masking and "truthful" block-property filters also forces us into some [awkward contortions](https://github.com/cockroachdb/pebble/blob/1a45921accf7c4422d7214a8e6315c374d0725c6/level_iter.go#L126-L135) to deal with the fact that a file's point iterator and range deletion iterator may become exhausted at different times.
I suspect we could significantly clean things up by using the `keyspan.InterleavingIter` within the `levelIter` implementation. It would work something like:
- If a file has range deletions, the `levelIter` initializes a `keyspan.InterleavingIter` with the file's point iterator and rangedel iterator. It configures the `InterleavingIter` to interleave both start and end boundaries of range deletions.
- The `levelIter` keeps a file open until it exhausts the `InterleavingIter`. Since range deletions' start/end boundaries are interleaved, this ensures that we don't prematurely close the range deletion iterator during iteration. We can remove the code that manufactures "ignorable boundary keys." The interleaving iterator handles interleaving the rangedel end boundary if necessary.
- The merging iterator no longer keeps a direct handle on a file's range deletion iterator. Instead, every `mergingIterLevel` has a `getRangeDel() *keyspan.Span` func that returns the range deletion covering that level's iterator's current position, if any. When a `levelIter` is setup, this is set to `levelIter.Span` which in turn calls `InterelavingIter.Span`.
- The `filteredIter` interface and related tracking within the sstable iterator is removed. It's no longer necessary because range deletions are unconditionally interleaved, which ensures we never miss a range deletion due to block-property filters excluding point keys that exist beyond the smallest/largest range deletion bound.
- The merging iterator iteration is adjusted to skip over range deletion boundaries that are interleaved and rise to the top of the heap, much like the existing code skips over the "ignorable boundary keys".
- The mechanisms of applying range deletions also change. The `mergingIterLevel` no longer buffers a tombstone. It instead calls `getRangeDel()` which accesses the `InterleavingIter`'s buffered tombstone instead. We remove `mergingIter.init[Min,Max]RangeDelIters`, because the `InterleavingIter` is transparently ensuring the range deletion iterators are appropriately positioned.
The memtable and indexed batch levels will also have to be adjusted to make use of a `keyspan.InterleavingIter`.
Jira issue: PEBBLE-82
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.