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/testkeys"
      12             : )
      13             : 
      14             : // Code in this file contains utils for testing. It implements interval block
      15             : // property collectors and filters on the suffixes of keys in the format used
      16             : // by the testkeys package (eg, 'key@5').
      17             : 
      18             : const testKeysBlockPropertyName = `pebble.internal.testkeys.suffixes`
      19             : 
      20             : // NewTestKeysBlockPropertyCollector constructs a sstable property collector
      21             : // over testkey suffixes.
      22           1 : func NewTestKeysBlockPropertyCollector() BlockPropertyCollector {
      23           1 :         return NewBlockIntervalCollector(
      24           1 :                 testKeysBlockPropertyName,
      25           1 :                 &testKeysSuffixIntervalMapper{},
      26           1 :                 nil)
      27           1 : }
      28             : 
      29             : // NewTestKeysBlockPropertyFilter constructs a new block-property filter that excludes
      30             : // blocks containing exclusively suffixed keys where all the suffixes fall
      31             : // outside of the range [filterMin, filterMax).
      32             : //
      33             : // The filter only filters based on data derived from the key. The iteration
      34             : // results of this block property filter are deterministic for unsuffixed keys
      35             : // and keys with suffixes within the range [filterMin, filterMax). For keys with
      36             : // suffixes outside the range, iteration is nondeterministic.
      37           1 : func NewTestKeysBlockPropertyFilter(filterMin, filterMax uint64) *BlockIntervalFilter {
      38           1 :         return NewBlockIntervalFilter(testKeysBlockPropertyName, filterMin, filterMax, testKeysBlockIntervalSyntheticReplacer{})
      39           1 : }
      40             : 
      41             : var _ BlockIntervalSuffixReplacer = testKeysBlockIntervalSyntheticReplacer{}
      42             : 
      43             : type testKeysBlockIntervalSyntheticReplacer struct{}
      44             : 
      45             : // ApplySuffixReplacement implements BlockIntervalSyntheticReplacer.
      46             : func (sr testKeysBlockIntervalSyntheticReplacer) ApplySuffixReplacement(
      47             :         interval BlockInterval, newSuffix []byte,
      48           1 : ) (BlockInterval, error) {
      49           1 :         decoded, err := testkeys.ParseSuffix(newSuffix)
      50           1 :         if err != nil {
      51           0 :                 return BlockInterval{}, err
      52           0 :         }
      53             :         // The testKeysSuffixIntervalMapper below maps keys with no suffix to
      54             :         // [0, MaxUint64); ignore that.
      55           1 :         if interval.Upper != math.MaxUint64 && uint64(decoded) < interval.Upper {
      56           0 :                 panic(fmt.Sprintf("the synthetic suffix %d is less than the property upper bound %d", decoded, interval.Upper))
      57             :         }
      58           1 :         return BlockInterval{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           1 : func NewTestKeysMaskingFilter() TestKeysMaskingFilter {
      66           1 :         return TestKeysMaskingFilter{BlockIntervalFilter: NewTestKeysBlockPropertyFilter(0, math.MaxUint64)}
      67           1 : }
      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           1 : func (f TestKeysMaskingFilter) SetSuffix(suffix []byte) error {
      78           1 :         ts, err := testkeys.ParseSuffix(suffix)
      79           1 :         if err != nil {
      80           0 :                 return err
      81           0 :         }
      82           1 :         f.BlockIntervalFilter.SetInterval(uint64(ts), math.MaxUint64)
      83           1 :         return nil
      84             : }
      85             : 
      86             : // Intersects implements the BlockPropertyFilter interface.
      87           1 : func (f TestKeysMaskingFilter) Intersects(prop []byte) (bool, error) {
      88           1 :         return f.BlockIntervalFilter.Intersects(prop)
      89           1 : }
      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             : // testKeysSuffixIntervalMapper maps keys to intervals according to the
      97             : // timestamps in MVCC-like suffixes for keys (e.g. "foo@123" -> 123).
      98             : type testKeysSuffixIntervalMapper struct {
      99             :         ignorePoints    bool
     100             :         ignoreRangeKeys bool
     101             : }
     102             : 
     103             : var _ IntervalMapper = &testKeysSuffixIntervalMapper{}
     104             : 
     105             : // MapPointKey is part of the IntervalMapper interface.
     106             : func (c *testKeysSuffixIntervalMapper) MapPointKey(
     107             :         key InternalKey, value []byte,
     108           1 : ) (BlockInterval, error) {
     109           1 :         if c.ignorePoints {
     110           1 :                 return BlockInterval{}, nil
     111           1 :         }
     112           1 :         n := testkeys.Comparer.Split(key.UserKey)
     113           1 :         return testKeysSuffixToInterval(key.UserKey[n:]), nil
     114             : }
     115             : 
     116             : // MapRangeKeys is part of the IntervalMapper interface.
     117           1 : func (c *testKeysSuffixIntervalMapper) MapRangeKeys(span Span) (BlockInterval, error) {
     118           1 :         if c.ignoreRangeKeys {
     119           1 :                 return BlockInterval{}, nil
     120           1 :         }
     121           1 :         var result BlockInterval
     122           1 :         for _, k := range span.Keys {
     123           1 :                 if len(k.Suffix) > 0 {
     124           1 :                         result.UnionWith(testKeysSuffixToInterval(k.Suffix))
     125           1 :                 }
     126             :         }
     127           1 :         return result, nil
     128             : }
     129             : 
     130           1 : func testKeysSuffixToInterval(suffix []byte) BlockInterval {
     131           1 :         if len(suffix) == 0 {
     132           1 :                 return BlockInterval{0, math.MaxUint64}
     133           1 :         }
     134           1 :         n, err := testkeys.ParseSuffix(suffix)
     135           1 :         if err != nil {
     136           0 :                 panic(err)
     137             :         }
     138           1 :         return BlockInterval{uint64(n), uint64(n) + 1}
     139             : }