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(suffixCmp base.CompareRangeSuffixes, keys []keyspan.Key, dst *[]keyspan.Key)
• func CoalesceInto(suffixCmp base.CompareRangeSuffixes, dst []keyspan.Key, snapshot base.SeqNum, ...) []keyspan.Key
• func Decode(ik base.InternalKey, v []byte, keysBuf []keyspan.Key) (keyspan.Span, error)
• func DecodeEndKey(kind base.InternalKeyKind, data []byte) (endKey, value []byte, _ error)
• func DecodeIntoSpan(cmp base.Compare, ik base.InternalKey, v []byte, s *keyspan.Span) error
• 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
• type Encoder
  • func (e *Encoder) Encode(s keyspan.Span) error
• type ForeignSSTTransformer
  • func (f *ForeignSSTTransformer) Transform(suffixCmp base.CompareRangeSuffixes, s keyspan.Span, dst *keyspan.Span) error
• type SuffixValue

Functions

func Coalesce

func Coalesce(suffixCmp base.CompareRangeSuffixes, keys []keyspan.Key, dst *[]keyspan.Key)

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.

The resulting dst Keys slice is sorted by InternalKeyTrailer.

func CoalesceInto

func CoalesceInto(
	suffixCmp base.CompareRangeSuffixes, dst []keyspan.Key, snapshot base.SeqNum, keys []keyspan.Key,
) []keyspan.Key

CoalesceInto is a variant of Coalesce which outputs the results into dst without sorting them.

func Decode

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

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

func DecodeEndKey

func DecodeEndKey(kind base.InternalKeyKind, data []byte) (endKey, value []byte, _ error)

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 DecodeIntoSpan

func DecodeIntoSpan(cmp base.Compare, ik base.InternalKey, v []byte, s *keyspan.Span) error

DecodeIntoSpan decodes an internal key pair encoding range key(s) and appends them to the given span. The start and end keys must match those in the span.

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.

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 ForeignSSTTransformer

type ForeignSSTTransformer struct {
	Equal  base.Equal
	SeqNum base.SeqNum
	// contains filtered or unexported fields
}

ForeignSSTTransformer implements a keyspan.Transformer for range keys in shared ingested sstables. It is largely similar to the Transform function implemented in UserIteratorConfig in that it calls coalesce to remove range keys shadowed by other range keys, but also retains the range key that does the shadowing. In addition, it elides RangeKey unsets/dels in L6 as they are inapplicable when reading from a different Pebble instance. Finally, it returns keys sorted in trailer order, not suffix order, as that's what the rest of the iterator stack expects.

func (*ForeignSSTTransformer) Transform

func (f *ForeignSSTTransformer) Transform(
	suffixCmp base.CompareRangeSuffixes, s keyspan.Span, dst *keyspan.Span,
) error

Transform implements the Transformer interface.

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.