Skip to content

compaction: integrate range keys #1686

@jbowens

Description

@jbowens

Range keys (#1339) need to be read and written during compactions. Like range deletions, range keys exist separately from point keys and are surfaced through the keyspan.FragmentIterator interface. Here's a sketch of the anticipated integration.

  1. When constructing a compaction input iterator, a keyspan.LevelIter is created for each input level that contains at least 1 file with range keys.
  2. The individual levels' range key keyspan.LevelIters are wrapped in a keyspan.MergingIter. The MergingIter is configured with a special keyspan.Transform. The Transform is configured with the slice of open snapshots. It partitions a Span's Keys into snapshot stripes, calling rangekey.Coalesce on the Keys of each stripe. We may want to refactor rangekey.Coalesce's interface to only take an input []Keys slice and output *[]Keys pointer. The rangekey.Coalesce calls performs shadowing, dropping unnecessary keys. This Transform is also likely where we should examine in-use key ranges (eg, elideRangeTombstone) to determine whether or not to drop RangeKeyUnset and RangeKeyDelete keys that exist in the last snapshot stripe.
  3. The MergingIter is then wrapped in a keyspan.DefragmentingIter configured with the DefragmentInternal defragmenting method. The defragmenting iterator will ensure the fragments persisted to disk are only as fine-grained as required.
  4. Finally, the keyspan.DefragmentingIter is wrapped with a keyspan.InterleavingIter to interleave range keys into the main compaction loop. This is similar to what was done for range deletions in compaction: use InterleavingIter to interleave rangedels #1659.
  5. When the main compaction loop encounters a RANGEKEYSET, RANGEKEYUNSET or RANGEKEYDELETE, it retrieves the span from the interleaving iterator and adds it to a keyspan.Fragmenter (separate from c.rangeDelFrag). All the truncation logic mirrors range deletions. Range keys should be added to the output sstable using Writer.AddRangeKey (not the Writer.RangeKey{Set,Unset,Delete} methods). Future work may consider removing the keyspan.Fragmenter, but I think it should be deferred for now, and we should track as close to possible to the current handling of range deletions.

Metadata

Metadata

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions