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             :         "math"
       9             : 
      10             :         "github.com/cockroachdb/pebble/internal/base"
      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 :                 &testKeysSuffixIntervalCollector{},
      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)
      39           1 : }
      40             : 
      41             : // NewTestKeysMaskingFilter constructs a TestKeysMaskingFilter that implements
      42             : // pebble.BlockPropertyFilterMask for efficient range-key masking using the
      43             : // testkeys block property filter. The masking filter wraps a block interval
      44             : // filter, and modifies the configured interval when Pebble requests it.
      45           1 : func NewTestKeysMaskingFilter() TestKeysMaskingFilter {
      46           1 :         return TestKeysMaskingFilter{BlockIntervalFilter: NewTestKeysBlockPropertyFilter(0, math.MaxUint64)}
      47           1 : }
      48             : 
      49             : // TestKeysMaskingFilter implements BlockPropertyFilterMask and may be used to mask
      50             : // point keys with the testkeys-style suffixes (eg, @4) that are masked by range
      51             : // keys with testkeys-style suffixes.
      52             : type TestKeysMaskingFilter struct {
      53             :         *BlockIntervalFilter
      54             : }
      55             : 
      56             : // SetSuffix implements pebble.BlockPropertyFilterMask.
      57           1 : func (f TestKeysMaskingFilter) SetSuffix(suffix []byte) error {
      58           1 :         ts, err := testkeys.ParseSuffix(suffix)
      59           1 :         if err != nil {
      60           0 :                 return err
      61           0 :         }
      62           1 :         f.BlockIntervalFilter.SetInterval(uint64(ts), math.MaxUint64)
      63           1 :         return nil
      64             : }
      65             : 
      66             : // Intersects implements the BlockPropertyFilter interface.
      67           1 : func (f TestKeysMaskingFilter) Intersects(prop []byte) (bool, error) {
      68           1 :         return f.BlockIntervalFilter.Intersects(prop)
      69           1 : }
      70             : 
      71             : var _ DataBlockIntervalCollector = (*testKeysSuffixIntervalCollector)(nil)
      72             : 
      73             : // testKeysSuffixIntervalCollector maintains an interval over the timestamps in
      74             : // MVCC-like suffixes for keys (e.g. foo@123).
      75             : type testKeysSuffixIntervalCollector struct {
      76             :         initialized  bool
      77             :         lower, upper uint64
      78             : }
      79             : 
      80             : // Add implements DataBlockIntervalCollector by adding the timestamp(s) in the
      81             : // suffix(es) of this record to the current interval.
      82             : //
      83             : // Note that range sets and unsets may have multiple suffixes. Range key deletes
      84             : // do not have a suffix. All other point keys have a single suffix.
      85           1 : func (c *testKeysSuffixIntervalCollector) Add(key base.InternalKey, value []byte) error {
      86           1 :         i := testkeys.Comparer.Split(key.UserKey)
      87           1 :         if i == len(key.UserKey) {
      88           1 :                 c.initialized = true
      89           1 :                 c.lower, c.upper = 0, math.MaxUint64
      90           1 :                 return nil
      91           1 :         }
      92           1 :         ts, err := testkeys.ParseSuffix(key.UserKey[i:])
      93           1 :         if err != nil {
      94           0 :                 return err
      95           0 :         }
      96           1 :         uts := uint64(ts)
      97           1 :         if !c.initialized {
      98           1 :                 c.lower, c.upper = uts, uts+1
      99           1 :                 c.initialized = true
     100           1 :                 return nil
     101           1 :         }
     102           1 :         if uts < c.lower {
     103           1 :                 c.lower = uts
     104           1 :         }
     105           1 :         if uts >= c.upper {
     106           1 :                 c.upper = uts + 1
     107           1 :         }
     108           1 :         return nil
     109             : }
     110             : 
     111             : // FinishDataBlock implements DataBlockIntervalCollector.
     112           1 : func (c *testKeysSuffixIntervalCollector) FinishDataBlock() (lower, upper uint64, err error) {
     113           1 :         l, u := c.lower, c.upper
     114           1 :         c.lower, c.upper = 0, 0
     115           1 :         c.initialized = false
     116           1 :         return l, u, nil
     117           1 : }