rangekey

Documentation

Overview

Package rangekey provides facilities for encoding, decoding and merging range keys.

Range keys map a span of keyspan `[start, end)`, at an optional suffix, to a value.

Encoding

Unlike other Pebble keys, range keys encode several fields of information: start key, end key, suffix and value. Internally within Pebble and its sstables, all keys including range keys are represented as a key-value tuple. Range keys map to internal key-value tuples by mapping the start key to the key and encoding the remainder of the fields in the value.

## `RANGEKEYSET`

A `RANGEKEYSET` represents one more range keys set over a single region of user key space. Each represented range key must have a unique suffix. A `RANGEKEYSET` encapsulates a start key, an end key and a set of SuffixValue pairs.

A `RANGEKEYSET` key's user key holds the start key. Its value is a varstring end key, followed by a set of SuffixValue pairs. A `RANGEKEYSET` may have multiple SuffixValue pairs if the keyspan was set at multiple unique suffix values.

## `RANGEKEYUNSET`

A `RANGEKEYUNSET` represents the removal of range keys at specific suffixes over a single region of user key space. A `RANGEKEYUNSET` encapsulates a start key, an end key and a set of suffixes.

A `RANGEKEYUNSET` key's user key holds the start key. Its value is a varstring end key, followed by a set of suffixes. A `RANGEKEYUNSET` may have multiple suffixes if the keyspan was unset at multiple unique suffixes.

## `RANGEKEYDEL`

A `RANGEKEYDEL` represents the removal of all range keys over a single region of user key space, regardless of suffix. A `RANGEKEYDEL` encapsulates a start key and an end key. The end key is stored in the value, without any varstring length prefixing.

Index

• func Coalesce(cmp base.Compare, keys []keyspan.Key, dst *[]keyspan.Key) error
• func Decode(ik base.InternalKey, v []byte, keysDst []keyspan.Key) (keyspan.Span, error)
• func DecodeEndKey(kind base.InternalKeyKind, data []byte) (endKey, value []byte, ok bool)
• func Encode(s *keyspan.Span, emit func(k base.InternalKey, v []byte) error) error
• func EncodeSetValue(dst []byte, endKey []byte, suffixValues []SuffixValue) int
• func EncodeUnsetValue(dst []byte, endKey []byte, suffixes [][]byte) int
• func EncodedSetValueLen(endKey []byte, suffixValues []SuffixValue) int
• func EncodedUnsetValueLen(endKey []byte, suffixes [][]byte) int
• func IsRangeKey(kind base.InternalKeyKind) bool
• func SortBySuffix(cmp base.Compare, keys []keyspan.Key)
• type Encoder
  • func (e *Encoder) Encode(s *keyspan.Span) error
• type SuffixValue
• type UserIteratorConfig
  • func (ui *UserIteratorConfig) AddLevel(iter keyspan.FragmentIterator)
  • func (ui *UserIteratorConfig) Init(cmp base.Compare, snapshot uint64, levelIters ...keyspan.FragmentIterator) keyspan.FragmentIterator
  • func (ui *UserIteratorConfig) ShouldDefragment(cmp base.Compare, a, b *keyspan.Span) bool
  • func (ui *UserIteratorConfig) Transform(cmp base.Compare, s keyspan.Span, dst *keyspan.Span) error

Functions

func Coalesce

func Coalesce(cmp base.Compare, keys []keyspan.Key, dst *[]keyspan.Key) error

Coalesce imposes range key semantics and coalesces range keys with the same bounds. Coalesce drops any keys shadowed by more recent sets, unsets or deletes. Coalesce modifies the provided span's Keys slice, reslicing the slice to remove dropped keys.

Coalescence has subtle behavior with respect to sequence numbers. Coalesce depends on a keyspan.Span's Keys being sorted in sequence number descending order. The first key has the largest sequence number. The returned coalesced span includes only the largest sequence number. All other sequence numbers are forgotten. When a compaction constructs output range keys from a coalesced span, it produces at most one RANGEKEYSET, one RANGEKEYUNSET and one RANGEKEYDEL. Each one of these keys adopt the largest sequence number.

This has the potentially surprising effect of 'promoting' a key to a higher sequence number. This is okay, because:

• There are no other overlapping keys within the coalesced span of sequence numbers (otherwise they would be in the compaction, due to the LSM invariant).
• Range key sequence numbers are never compared to point key sequence numbers. Range keys and point keys have parallel existences.
• Compactions only coalesce within snapshot stripes.

Additionally, internal range keys at the same sequence number have subtle mechanics:

• RANGEKEYSETs shadow RANGEKEYUNSETs of the same suffix.
• RANGEKEYDELs only apply to keys at lower sequence numbers.

This is required for ingestion. Ingested sstables are assigned a single sequence number for the file, at which all of the file's keys are visible. The RANGEKEYSET, RANGEKEYUNSET and RANGEKEYDEL key kinds are ordered such that among keys with equal sequence numbers (thus ordered by their kinds) the keys do not affect one another. Ingested sstables are expected to be consistent with respect to the set/unset suffixes: A given suffix should be set or unset but not both.

func Decode

func Decode(ik base.InternalKey, v []byte, keysDst []keyspan.Key) (keyspan.Span, error)

Decode takes an internal key pair encoding range key(s) and returns a decoded keyspan containing the keys. If keysDst is provided, keys will be appended to keysDst.

func DecodeEndKey

func DecodeEndKey(kind base.InternalKeyKind, data []byte) (endKey, value []byte, ok bool)

DecodeEndKey reads the end key from the beginning of a range key (RANGEKEYSET, RANGEKEYUNSET or RANGEKEYDEL)'s physical encoded value. Both sets and unsets encode the range key, plus additional data in the value.

func Encode

func Encode(s *keyspan.Span, emit func(k base.InternalKey, v []byte) error) error

Encode takes a Span containing only range keys. It invokes the provided closure with the encoded internal keys that represent the Span's state. The keys and values passed to emit are only valid until the closure returns. If emit returns an error, Encode stops and returns the error.

func EncodeSetValue

func EncodeSetValue(dst []byte, endKey []byte, suffixValues []SuffixValue) int

EncodeSetValue encodes a RangeKeySet's value into dst. The length of dst must be greater than or equal to EncodedSetValueLen. EncodeSetValue returns the number of bytes written, which should always equal the EncodedSetValueLen with the same arguments.

func EncodeUnsetValue

func EncodeUnsetValue(dst []byte, endKey []byte, suffixes [][]byte) int

EncodeUnsetValue encodes a RangeKeyUnset's value into dst. The length of dst must be greater than or equal to EncodedUnsetValueLen. EncodeUnsetValue returns the number of bytes written, which should always equal the EncodedUnsetValueLen with the same arguments.

func EncodedSetValueLen

func EncodedSetValueLen(endKey []byte, suffixValues []SuffixValue) int

EncodedSetValueLen precomputes the length of a RangeKeySet's value when encoded. It may be used to construct a buffer of the appropriate size before encoding.

func EncodedUnsetValueLen

func EncodedUnsetValueLen(endKey []byte, suffixes [][]byte) int

EncodedUnsetValueLen precomputes the length of a RangeKeyUnset's value when encoded. It may be used to construct a buffer of the appropriate size before encoding.

func IsRangeKey

func IsRangeKey(kind base.InternalKeyKind) bool

IsRangeKey returns true if the given key kind is one of the range key kinds.

func SortBySuffix

func SortBySuffix(cmp base.Compare, keys []keyspan.Key)

SortBySuffix sorts the provided keys by suffix.

Types

type Encoder

type Encoder struct {
	Emit func(base.InternalKey, []byte) error
	// contains filtered or unexported fields
}

An Encoder encodes range keys into their on-disk InternalKey format. An Encoder holds internal buffers, reused between Emit calls.

func (*Encoder) Encode

func (e *Encoder) Encode(s *keyspan.Span) error

Encode takes a Span containing only range keys. It invokes the Encoder's Emit closure with the encoded internal keys that represent the Span's state. The keys and values passed to emit are only valid until the closure returns. If Emit returns an error, Encode stops and returns the error.

The encoded key-value pair passed to Emit is only valid until the closure completes.

type SuffixValue

type SuffixValue struct {
	Suffix []byte
	Value  []byte
}

SuffixValue represents a tuple of a suffix and a corresponding value. A physical RANGEKEYSET key may contain many logical RangeKeySets, each represented with a separate SuffixValue tuple.

type UserIteratorConfig

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

UserIteratorConfig holds state for constructing the range key iterator stack for user iteration.

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(
	cmp base.Compare, snapshot uint64, levelIters ...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 removes all Keys other than RangeKeySets describing the current state of range keys.

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

func (*UserIteratorConfig) ShouldDefragment

func (ui *UserIteratorConfig) ShouldDefragment(cmp base.Compare, 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. 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.

This implementation is stateful, and must not be used on multiple DefragmentingIters concurrently.

func (*UserIteratorConfig) Transform

func (ui *UserIteratorConfig) Transform(cmp base.Compare, s keyspan.Span, dst *keyspan.Span) error

Transform implements the keyspan.Transformer interface for use with a keyspan.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.