Line data    Source code

       1             : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : package block
       6             : 
       7             : import (
       8             :         "bytes"
       9             :         "fmt"
      10             :         "unsafe"
      11             : 
      12             :         "github.com/cockroachdb/pebble/internal/base"
      13             : )
      14             : 
      15             : // IterTransforms allow on-the-fly transformation of data at iteration time.
      16             : //
      17             : // These transformations could in principle be implemented as block transforms
      18             : // (at least for non-virtual sstables), but applying them during iteration is
      19             : // preferable.
      20             : type IterTransforms struct {
      21             :         // SyntheticSeqNum, if set, overrides the sequence number in all keys. It is
      22             :         // set if the sstable was ingested or it is foreign.
      23             :         SyntheticSeqNum SyntheticSeqNum
      24             :         // HideObsoletePoints, if true, skips over obsolete points during iteration.
      25             :         // This is the norm when the sstable is foreign or the largest sequence number
      26             :         // of the sstable is below the one we are reading.
      27             :         HideObsoletePoints bool
      28             : 
      29             :         SyntheticPrefixAndSuffix SyntheticPrefixAndSuffix
      30             : }
      31             : 
      32             : // NoTransforms is the default value for IterTransforms.
      33             : var NoTransforms = IterTransforms{}
      34             : 
      35             : // NoTransforms returns true if there are no transforms enabled.
      36           1 : func (t *IterTransforms) NoTransforms() bool {
      37           1 :         return t.SyntheticSeqNum == 0 &&
      38           1 :                 !t.HideObsoletePoints &&
      39           1 :                 t.SyntheticPrefixAndSuffix.IsUnset()
      40           1 : }
      41             : 
      42           1 : func (t *IterTransforms) HasSyntheticPrefix() bool {
      43           1 :         return t.SyntheticPrefixAndSuffix.HasPrefix()
      44           1 : }
      45             : 
      46           1 : func (t *IterTransforms) SyntheticPrefix() []byte {
      47           1 :         return t.SyntheticPrefixAndSuffix.Prefix()
      48           1 : }
      49             : 
      50           1 : func (t *IterTransforms) HasSyntheticSuffix() bool {
      51           1 :         return t.SyntheticPrefixAndSuffix.HasSuffix()
      52           1 : }
      53             : 
      54           1 : func (t *IterTransforms) SyntheticSuffix() []byte {
      55           1 :         return t.SyntheticPrefixAndSuffix.Suffix()
      56           1 : }
      57             : 
      58             : // FragmentIterTransforms allow on-the-fly transformation of range deletion or
      59             : // range key data at iteration time.
      60             : type FragmentIterTransforms struct {
      61             :         SyntheticSeqNum          SyntheticSeqNum
      62             :         SyntheticPrefixAndSuffix SyntheticPrefixAndSuffix
      63             : }
      64             : 
      65             : // NoTransforms returns true if there are no transforms enabled.
      66           1 : func (t *FragmentIterTransforms) NoTransforms() bool {
      67           1 :         // NoTransforms returns true if there are no transforms enabled.
      68           1 :         return t.SyntheticSeqNum == 0 && t.SyntheticPrefixAndSuffix.IsUnset()
      69           1 : }
      70             : 
      71           1 : func (t *FragmentIterTransforms) HasSyntheticPrefix() bool {
      72           1 :         return t.SyntheticPrefixAndSuffix.HasPrefix()
      73           1 : }
      74             : 
      75           1 : func (t *FragmentIterTransforms) SyntheticPrefix() []byte {
      76           1 :         return t.SyntheticPrefixAndSuffix.Prefix()
      77           1 : }
      78             : 
      79           1 : func (t *FragmentIterTransforms) HasSyntheticSuffix() bool {
      80           1 :         return t.SyntheticPrefixAndSuffix.HasSuffix()
      81           1 : }
      82             : 
      83           1 : func (t *FragmentIterTransforms) SyntheticSuffix() []byte {
      84           1 :         return t.SyntheticPrefixAndSuffix.Suffix()
      85           1 : }
      86             : 
      87             : // NoFragmentTransforms is the default value for IterTransforms.
      88             : var NoFragmentTransforms = FragmentIterTransforms{}
      89             : 
      90             : // SyntheticSeqNum is used to override all sequence numbers in a table. It is
      91             : // set to a non-zero value when the table was created externally and ingested
      92             : // whole.
      93             : type SyntheticSeqNum base.SeqNum
      94             : 
      95             : // NoSyntheticSeqNum is the default zero value for SyntheticSeqNum, which
      96             : // disables overriding the sequence number.
      97             : const NoSyntheticSeqNum SyntheticSeqNum = 0
      98             : 
      99             : // SyntheticSuffix will replace every suffix of every point key surfaced during
     100             : // block iteration. A synthetic suffix can be used if:
     101             : //  1. no two keys in the sst share the same prefix; and
     102             : //  2. pebble.Compare(prefix + replacementSuffix, prefix + originalSuffix) < 0,
     103             : //     for all keys in the backing sst which have a suffix (i.e. originalSuffix
     104             : //     is not empty).
     105             : //
     106             : // Range dels are not supported when synthetic suffix is used.
     107             : //
     108             : // For range keys, the synthetic suffix applies to the suffix that is part of
     109             : // RangeKeySet - if it is non-empty, it is replaced with the SyntheticSuffix.
     110             : // RangeKeyUnset keys are not supported when a synthetic suffix is used.
     111             : type SyntheticSuffix []byte
     112             : 
     113             : // IsSet returns true if the synthetic suffix is not empty.
     114           1 : func (ss SyntheticSuffix) IsSet() bool {
     115           1 :         return len(ss) > 0
     116           1 : }
     117             : 
     118             : // SyntheticPrefix represents a byte slice that is implicitly prepended to every
     119             : // key in a file being read or accessed by a reader. Note that since the byte
     120             : // slice is prepended to every KV rather than replacing a byte prefix, the
     121             : // result of prepending the synthetic prefix must be a full, valid key while the
     122             : // partial key physically stored within the sstable need not be a valid key
     123             : // according to user key semantics.
     124             : //
     125             : // Note that elsewhere we use the language of 'prefix' to describe the user key
     126             : // portion of a MVCC key, as defined by the Comparer's base.Split method. The
     127             : // SyntheticPrefix is related only in that it's a byte prefix that is
     128             : // incorporated into the logical MVCC prefix.
     129             : //
     130             : // The table's bloom filters are constructed only on the partial keys physically
     131             : // stored in the table, but interactions with the file including seeks and
     132             : // reads will all behave as if the file had been constructed from keys that
     133             : // include the synthetic prefix. Note that all Compare operations will act on a
     134             : // partial key (before any prepending), so the Comparer must support comparing
     135             : // these partial keys.
     136             : //
     137             : // The synthetic prefix will never modify key metadata stored in the key suffix.
     138             : //
     139             : // NB: Since this transformation currently only applies to point keys, a block
     140             : // with range keys cannot be iterated over with a synthetic prefix.
     141             : type SyntheticPrefix []byte
     142             : 
     143             : // IsSet returns true if the synthetic prefix is not enpty.
     144           1 : func (sp SyntheticPrefix) IsSet() bool {
     145           1 :         return len(sp) > 0
     146           1 : }
     147             : 
     148             : // Apply prepends the synthetic prefix to a key.
     149           1 : func (sp SyntheticPrefix) Apply(key []byte) []byte {
     150           1 :         res := make([]byte, 0, len(sp)+len(key))
     151           1 :         res = append(res, sp...)
     152           1 :         res = append(res, key...)
     153           1 :         return res
     154           1 : }
     155             : 
     156             : // Invert removes the synthetic prefix from a key.
     157           1 : func (sp SyntheticPrefix) Invert(key []byte) []byte {
     158           1 :         res, ok := bytes.CutPrefix(key, sp)
     159           1 :         if !ok {
     160           0 :                 panic(fmt.Sprintf("unexpected prefix: %s", key))
     161             :         }
     162           1 :         return res
     163             : }
     164             : 
     165             : // SyntheticPrefixAndSuffix is a more compact way of representing both a
     166             : // synthetic prefix and a synthetic suffix. See SyntheticPrefix and
     167             : // SyntheticSuffix.
     168             : //
     169             : // The zero value is valid, representing no synthetic prefix or suffix.
     170             : type SyntheticPrefixAndSuffix struct {
     171             :         prefixLen uint32
     172             :         suffixLen uint32
     173             :         // buf is either nil (iff prefixLen=suffixLen=0) or a pointer to a buffer
     174             :         // containing the prefix followed by the suffix.
     175             :         buf unsafe.Pointer
     176             : }
     177             : 
     178             : // MakeSyntheticPrefixAndSuffix returns a SyntheticPrefixAndSuffix with the
     179             : // given prefix and suffix.
     180             : func MakeSyntheticPrefixAndSuffix(
     181             :         prefix SyntheticPrefix, suffix SyntheticSuffix,
     182           1 : ) SyntheticPrefixAndSuffix {
     183           1 :         if !prefix.IsSet() && !suffix.IsSet() {
     184           1 :                 return SyntheticPrefixAndSuffix{}
     185           1 :         }
     186           1 :         buf := make([]byte, len(prefix)+len(suffix))
     187           1 :         copy(buf, prefix)
     188           1 :         copy(buf[len(prefix):], suffix)
     189           1 :         return SyntheticPrefixAndSuffix{
     190           1 :                 prefixLen: uint32(len(prefix)),
     191           1 :                 suffixLen: uint32(len(suffix)),
     192           1 :                 buf:       unsafe.Pointer(&buf[0]),
     193           1 :         }
     194             : }
     195             : 
     196             : // IsUnset returns true if HasPrefix() and HasSuffix() both return false.
     197           1 : func (ps SyntheticPrefixAndSuffix) IsUnset() bool {
     198           1 :         return ps.buf == nil
     199           1 : }
     200             : 
     201             : // HasPrefix returns true if ps contains a non-empty synthetic prefix.
     202           1 : func (ps SyntheticPrefixAndSuffix) HasPrefix() bool {
     203           1 :         return ps.prefixLen != 0
     204           1 : }
     205             : 
     206             : // PrefixLen returns the length of the synthetic prefix, or 0 if it is not set.
     207           1 : func (ps SyntheticPrefixAndSuffix) PrefixLen() uint32 {
     208           1 :         return ps.prefixLen
     209           1 : }
     210             : 
     211             : // Prefix returns the synthetic prefix.
     212           1 : func (ps SyntheticPrefixAndSuffix) Prefix() SyntheticPrefix {
     213           1 :         if ps.prefixLen == 0 {
     214           1 :                 return nil
     215           1 :         }
     216           1 :         return unsafe.Slice((*byte)(ps.buf), ps.prefixLen)
     217             : }
     218             : 
     219             : // HasSuffix returns true if ps contains a non-empty synthetic suffix.
     220           1 : func (ps SyntheticPrefixAndSuffix) HasSuffix() bool {
     221           1 :         return ps.suffixLen != 0
     222           1 : }
     223             : 
     224             : // SuffixLen returns the length of the synthetic prefix, or 0 if it is not set.
     225           1 : func (ps SyntheticPrefixAndSuffix) SuffixLen() uint32 {
     226           1 :         return ps.suffixLen
     227           1 : }
     228             : 
     229             : // Suffix returns the synthetic suffix.
     230           1 : func (ps SyntheticPrefixAndSuffix) Suffix() SyntheticSuffix {
     231           1 :         if ps.suffixLen == 0 {
     232           1 :                 return nil
     233           1 :         }
     234           1 :         return unsafe.Slice((*byte)(unsafe.Pointer(uintptr(ps.buf)+uintptr(ps.prefixLen))), ps.suffixLen)
     235             : }
     236             : 
     237             : // RemoveSuffix returns a SyntheticPrefixAndSuffix that has the same prefix as
     238             : // the receiver but no suffix.
     239           1 : func (ps SyntheticPrefixAndSuffix) RemoveSuffix() SyntheticPrefixAndSuffix {
     240           1 :         if ps.prefixLen == 0 {
     241           1 :                 return SyntheticPrefixAndSuffix{}
     242           1 :         }
     243           1 :         return SyntheticPrefixAndSuffix{
     244           1 :                 prefixLen: ps.prefixLen,
     245           1 :                 suffixLen: 0,
     246           1 :                 buf:       ps.buf,
     247           1 :         }
     248             : }