rangekeystack

Documentation

Index

• type Buffers
  • func (bufs *Buffers) PrepareForReuse()
• type UserIteratorConfig
  • func (ui *UserIteratorConfig) AddLevel(iter keyspan.FragmentIterator)
  • func (ui *UserIteratorConfig) Init(comparer *base.Comparer, snapshot base.SeqNum, lower, upper []byte, ...) keyspan.FragmentIterator
  • func (ui *UserIteratorConfig) NewLevelIter() *keyspanimpl.LevelIter
  • func (ui *UserIteratorConfig) SetBounds(lower, upper []byte)
  • func (ui *UserIteratorConfig) ShouldDefragment(suffixCmp base.CompareRangeSuffixes, a, b *keyspan.Span) bool
  • func (ui *UserIteratorConfig) Transform(suffixCmp base.CompareRangeSuffixes, s keyspan.Span, dst *keyspan.Span) error

Types

type Buffers

type Buffers struct {
	// contains filtered or unexported fields
}

Buffers holds various buffers used for range key iteration. They're exposed so that they may be pooled and reused between iterators.

func (*Buffers) PrepareForReuse

func (bufs *Buffers) PrepareForReuse()

PrepareForReuse discards any excessively large buffers.

type UserIteratorConfig

type UserIteratorConfig struct {
	// contains filtered or unexported fields
}

UserIteratorConfig holds state for constructing the range key iterator stack for user iteration. The range key iterator must merge range key spans across the levels of the LSM. This merging is performed by a keyspanimpl.MergingIter on-the-fly. The UserIteratorConfig implements keyspan.Transformer, evaluating range-key semantics and shadowing, so the spans returned by a MergingIter are fully resolved.

The MergingIter is wrapped by a BoundedIter, which elides spans that are outside the iterator bounds (or the current prefix's bounds, during prefix iteration mode).

To provide determinisim during iteration, the BoundedIter is wrapped by a DefragmentingIter that defragments abutting spans with identical user-observable state.

At the top-level an InterleavingIter interleaves range keys with point keys and performs truncation to iterator bounds.

Below is an abbreviated diagram illustrating the mechanics of a SeekGE.

               InterleavingIter.SeekGE
                       │
            DefragmentingIter.SeekGE
                       │
               BoundedIter.SeekGE
                       │
      ╭────────────────┴───────────────╮
      │                                ├── defragmentBwd*
MergingIter.SeekGE                     │
      │                                ╰── defragmentFwd
      ╰─╶╶ per level╶╶ ─╮
                        │
                        │
                        ├── <?>.SeekLT
                        │
                        ╰── <?>.Next

func (*UserIteratorConfig) AddLevel

func (ui *UserIteratorConfig) AddLevel(iter keyspan.FragmentIterator)

AddLevel adds a new level to the bottom of the iterator stack. AddLevel must be called after Init and before any other method on the iterator.

func (*UserIteratorConfig) Init

func (ui *UserIteratorConfig) Init(
	comparer *base.Comparer,
	snapshot base.SeqNum,
	lower, upper []byte,
	hasPrefix *bool,
	prefix *[]byte,
	internalKeys bool,
	bufs *Buffers,
	iters ...keyspan.FragmentIterator,
) keyspan.FragmentIterator

Init initializes the range key iterator stack for user iteration. The resulting fragment iterator applies range key semantics, defragments spans according to their user-observable state and, if !internalKeys, removes all Keys other than RangeKeySets describing the current state of range keys. The resulting spans contain Keys sorted by suffix (unless internalKeys is true, in which case they remain sorted by trailer descending).

The snapshot sequence number parameter determines which keys are visible. Any keys not visible at the provided snapshot are ignored.

func (*UserIteratorConfig) NewLevelIter

func (ui *UserIteratorConfig) NewLevelIter() *keyspanimpl.LevelIter

NewLevelIter returns a pointer to a newly allocated or reused keyspanimpl.LevelIter. The caller is responsible for calling Init() on this instance.

func (*UserIteratorConfig) SetBounds

func (ui *UserIteratorConfig) SetBounds(lower, upper []byte)

SetBounds propagates bounds to the iterator stack. The fragment iterator interface ordinarily doesn't enforce bounds, so this is exposed as an explicit method on the user iterator config.

func (*UserIteratorConfig) ShouldDefragment

func (ui *UserIteratorConfig) ShouldDefragment(
	suffixCmp base.CompareRangeSuffixes, a, b *keyspan.Span,
) bool

ShouldDefragment implements the DefragmentMethod interface and configures a DefragmentingIter to defragment spans of range keys if their user-visible state is identical. This defragmenting method assumes the provided spans have already been transformed through (UserIterationConfig).Transform, so all RangeKeySets are user-visible sets and are already in Suffix order. This defragmenter checks for equality between set suffixes and values (ignoring sequence numbers). It's intended for use during user iteration, when the wrapped keyspan iterator is merging spans across all levels of the LSM.

func (*UserIteratorConfig) Transform

func (ui *UserIteratorConfig) Transform(
	suffixCmp base.CompareRangeSuffixes, s keyspan.Span, dst *keyspan.Span,
) error

Transform implements the keyspan.Transformer interface for use with a keyspanimpl.MergingIter. It transforms spans by resolving range keys at the provided snapshot sequence number. Shadowing of keys is resolved (eg, removal of unset keys, removal of keys overwritten by a set at the same suffix, etc) and then non-RangeKeySet keys are removed. The resulting transformed spans only contain RangeKeySets describing the state visible at the provided sequence number, and hold their Keys sorted by Suffix (except if internalKeys is true, then keys remain sorted by trailer.