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