Line data    Source code

       1             : // Copyright 2022 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 sstable
       6             : 
       7             : import (
       8             :         "fmt"
       9             :         "math"
      10             : 
      11             :         "github.com/cockroachdb/pebble/internal/base"
      12             :         "github.com/cockroachdb/pebble/internal/testkeys"
      13             : )
      14             : 
      15             : // Code in this file contains utils for testing. It implements interval block
      16             : // property collectors and filters on the suffixes of keys in the format used
      17             : // by the testkeys package (eg, 'key@5').
      18             : 
      19             : const testKeysBlockPropertyName = `pebble.internal.testkeys.suffixes`
      20             : 
      21             : // NewTestKeysBlockPropertyCollector constructs a sstable property collector
      22             : // over testkey suffixes.
      23           2 : func NewTestKeysBlockPropertyCollector() BlockPropertyCollector {
      24           2 :         return NewBlockIntervalCollector(
      25           2 :                 testKeysBlockPropertyName,
      26           2 :                 &testKeysSuffixIntervalCollector{},
      27           2 :                 nil)
      28           2 : }
      29             : 
      30             : // NewTestKeysBlockPropertyFilter constructs a new block-property filter that excludes
      31             : // blocks containing exclusively suffixed keys where all the suffixes fall
      32             : // outside of the range [filterMin, filterMax).
      33             : //
      34             : // The filter only filters based on data derived from the key. The iteration
      35             : // results of this block property filter are deterministic for unsuffixed keys
      36             : // and keys with suffixes within the range [filterMin, filterMax). For keys with
      37             : // suffixes outside the range, iteration is nondeterministic.
      38           2 : func NewTestKeysBlockPropertyFilter(filterMin, filterMax uint64) *BlockIntervalFilter {
      39           2 :         return NewBlockIntervalFilter(testKeysBlockPropertyName, filterMin, filterMax, testKeysBlockIntervalSyntheticReplacer{})
      40           2 : }
      41             : 
      42             : var _ BlockIntervalSyntheticReplacer = testKeysBlockIntervalSyntheticReplacer{}
      43             : 
      44             : type testKeysBlockIntervalSyntheticReplacer struct{}
      45             : 
      46             : // AdjustIntervalWithSyntheticSuffix implements BlockIntervalSyntheticReplacer.
      47             : func (sr testKeysBlockIntervalSyntheticReplacer) AdjustIntervalWithSyntheticSuffix(
      48             :         lower uint64, upper uint64, suffix []byte,
      49           1 : ) (adjustedLower uint64, adjustedUpper uint64, err error) {
      50           1 :         decoded, err := testkeys.ParseSuffix(suffix)
      51           1 :         if err != nil {
      52           0 :                 return 0, 0, err
      53           0 :         }
      54             :         // The testKeysSuffixIntervalCollector below maps keys with no suffix to MaxUint64; ignore it.
      55           1 :         if upper != math.MaxUint64 && uint64(decoded) < upper {
      56           0 :                 panic(fmt.Sprintf("the synthetic suffix %d is less than the property upper bound %d", decoded, upper))
      57             :         }
      58           1 :         return uint64(decoded), uint64(decoded) + 1, nil
      59             : }
      60             : 
      61             : // NewTestKeysMaskingFilter constructs a TestKeysMaskingFilter that implements
      62             : // pebble.BlockPropertyFilterMask for efficient range-key masking using the
      63             : // testkeys block property filter. The masking filter wraps a block interval
      64             : // filter, and modifies the configured interval when Pebble requests it.
      65           2 : func NewTestKeysMaskingFilter() TestKeysMaskingFilter {
      66           2 :         return TestKeysMaskingFilter{BlockIntervalFilter: NewTestKeysBlockPropertyFilter(0, math.MaxUint64)}
      67           2 : }
      68             : 
      69             : // TestKeysMaskingFilter implements BlockPropertyFilterMask and may be used to mask
      70             : // point keys with the testkeys-style suffixes (eg, @4) that are masked by range
      71             : // keys with testkeys-style suffixes.
      72             : type TestKeysMaskingFilter struct {
      73             :         *BlockIntervalFilter
      74             : }
      75             : 
      76             : // SetSuffix implements pebble.BlockPropertyFilterMask.
      77           2 : func (f TestKeysMaskingFilter) SetSuffix(suffix []byte) error {
      78           2 :         ts, err := testkeys.ParseSuffix(suffix)
      79           2 :         if err != nil {
      80           0 :                 return err
      81           0 :         }
      82           2 :         f.BlockIntervalFilter.SetInterval(uint64(ts), math.MaxUint64)
      83           2 :         return nil
      84             : }
      85             : 
      86             : // Intersects implements the BlockPropertyFilter interface.
      87           2 : func (f TestKeysMaskingFilter) Intersects(prop []byte) (bool, error) {
      88           2 :         return f.BlockIntervalFilter.Intersects(prop)
      89           2 : }
      90             : 
      91             : // SyntheticSuffixIntersects implements the BlockPropertyFilter interface.
      92           1 : func (f TestKeysMaskingFilter) SyntheticSuffixIntersects(prop []byte, suffix []byte) (bool, error) {
      93           1 :         return f.BlockIntervalFilter.SyntheticSuffixIntersects(prop, suffix)
      94           1 : }
      95             : 
      96             : var _ DataBlockIntervalCollector = (*testKeysSuffixIntervalCollector)(nil)
      97             : 
      98             : // testKeysSuffixIntervalCollector maintains an interval over the timestamps in
      99             : // MVCC-like suffixes for keys (e.g. foo@123).
     100             : type testKeysSuffixIntervalCollector struct {
     101             :         initialized  bool
     102             :         lower, upper uint64
     103             : }
     104             : 
     105             : // Add implements DataBlockIntervalCollector by adding the timestamp(s) in the
     106             : // suffix(es) of this record to the current interval.
     107             : //
     108             : // Note that range sets and unsets may have multiple suffixes. Range key deletes
     109             : // do not have a suffix. All other point keys have a single suffix.
     110           2 : func (c *testKeysSuffixIntervalCollector) Add(key base.InternalKey, value []byte) error {
     111           2 :         i := testkeys.Comparer.Split(key.UserKey)
     112           2 :         if i == len(key.UserKey) {
     113           2 :                 c.initialized = true
     114           2 :                 c.lower, c.upper = 0, math.MaxUint64
     115           2 :                 return nil
     116           2 :         }
     117           2 :         ts, err := testkeys.ParseSuffix(key.UserKey[i:])
     118           2 :         if err != nil {
     119           0 :                 return err
     120           0 :         }
     121           2 :         uts := uint64(ts)
     122           2 :         if !c.initialized {
     123           2 :                 c.lower, c.upper = uts, uts+1
     124           2 :                 c.initialized = true
     125           2 :                 return nil
     126           2 :         }
     127           2 :         if uts < c.lower {
     128           2 :                 c.lower = uts
     129           2 :         }
     130           2 :         if uts >= c.upper {
     131           2 :                 c.upper = uts + 1
     132           2 :         }
     133           2 :         return nil
     134             : }
     135             : 
     136             : // FinishDataBlock implements DataBlockIntervalCollector.
     137           2 : func (c *testKeysSuffixIntervalCollector) FinishDataBlock() (lower, upper uint64, err error) {
     138           2 :         l, u := c.lower, c.upper
     139           2 :         c.lower, c.upper = 0, 0
     140           2 :         c.initialized = false
     141           2 :         return l, u, nil
     142           2 : }