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 : "strconv"
11 :
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 1 : func NewTestKeysBlockPropertyCollector() BlockPropertyCollector {
24 1 : return NewBlockIntervalCollector(
25 1 : testKeysBlockPropertyName,
26 1 : &testKeysSuffixIntervalMapper{},
27 1 : nil)
28 1 : }
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 1 : func NewTestKeysBlockPropertyFilter(filterMin, filterMax uint64) *BlockIntervalFilter {
39 1 : return NewBlockIntervalFilter(testKeysBlockPropertyName, filterMin, filterMax, testKeysBlockIntervalSyntheticReplacer{})
40 1 : }
41 :
42 : var _ BlockIntervalSuffixReplacer = testKeysBlockIntervalSyntheticReplacer{}
43 :
44 : type testKeysBlockIntervalSyntheticReplacer struct{}
45 :
46 : // ApplySuffixReplacement implements BlockIntervalSyntheticReplacer.
47 : func (sr testKeysBlockIntervalSyntheticReplacer) ApplySuffixReplacement(
48 : interval BlockInterval, newSuffix []byte,
49 1 : ) (BlockInterval, error) {
50 1 : decoded, err := testkeys.ParseSuffix(newSuffix)
51 1 : if err != nil {
52 0 : return BlockInterval{}, err
53 0 : }
54 : // The testKeysSuffixIntervalMapper below maps keys with no suffix to
55 : // [0, MaxUint64); ignore that.
56 1 : if interval.Upper != math.MaxUint64 && uint64(decoded) < interval.Upper {
57 0 : panic(fmt.Sprintf("the synthetic suffix %d is less than the property upper bound %d", decoded, interval.Upper))
58 : }
59 1 : return BlockInterval{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 1 : func (f TestKeysMaskingFilter) SyntheticSuffixIntersects(prop []byte, suffix []byte) (bool, error) {
94 1 : return f.BlockIntervalFilter.SyntheticSuffixIntersects(prop, suffix)
95 1 : }
96 :
97 : // testKeysSuffixIntervalMapper maps keys to intervals according to the
98 : // timestamps in MVCC-like suffixes for keys (e.g. "foo@123" -> 123).
99 : type testKeysSuffixIntervalMapper struct {
100 : ignorePoints bool
101 : ignoreRangeKeys bool
102 : }
103 :
104 : var _ IntervalMapper = &testKeysSuffixIntervalMapper{}
105 :
106 : // MapPointKey is part of the IntervalMapper interface.
107 : func (c *testKeysSuffixIntervalMapper) MapPointKey(
108 : key InternalKey, value []byte,
109 1 : ) (BlockInterval, error) {
110 1 : if c.ignorePoints {
111 0 : return BlockInterval{}, nil
112 0 : }
113 1 : n := testkeys.Comparer.Split(key.UserKey)
114 1 : return testKeysSuffixToInterval(key.UserKey[n:]), nil
115 : }
116 :
117 : // MapRangeKeys is part of the IntervalMapper interface.
118 1 : func (c *testKeysSuffixIntervalMapper) MapRangeKeys(span Span) (BlockInterval, error) {
119 1 : if c.ignoreRangeKeys {
120 0 : return BlockInterval{}, nil
121 0 : }
122 1 : var result BlockInterval
123 1 : for _, k := range span.Keys {
124 1 : if len(k.Suffix) > 0 {
125 1 : result.UnionWith(testKeysSuffixToInterval(k.Suffix))
126 1 : }
127 : }
128 1 : return result, nil
129 : }
130 :
131 1 : func testKeysSuffixToInterval(suffix []byte) BlockInterval {
132 1 : if len(suffix) == 0 {
133 1 : return BlockInterval{0, math.MaxUint64}
134 1 : }
135 1 : n, err := testkeys.ParseSuffix(suffix)
136 1 : if err != nil {
137 0 : panic(err)
138 : }
139 1 : return BlockInterval{uint64(n), uint64(n) + 1}
140 : }
141 :
142 : type MaxTestKeysSuffixProperty struct{}
143 :
144 : // Name is part of the MaxTestKeysSuffixProperty interface.
145 0 : func (testprop MaxTestKeysSuffixProperty) Name() string {
146 0 : return `pebble.internal.testkeys.suffixes`
147 0 : }
148 :
149 : // Extract is part of the MaxTestKeysSuffixProperty interface used to extract the
150 : // latest suffix from the block property.
151 : func (testprop MaxTestKeysSuffixProperty) Extract(
152 : dst []byte, encodedProperty []byte,
153 0 : ) (suffix []byte, ok bool, err error) {
154 0 : if len(encodedProperty) <= 1 {
155 0 : return nil, false, nil
156 0 : }
157 : // First byte is shortID, skip it and decode interval from remainder.
158 0 : interval, err := DecodeBlockInterval(encodedProperty[1:])
159 0 : if err != nil {
160 0 : return nil, false, err
161 0 : } else if interval.IsEmpty() {
162 0 : return nil, false, nil
163 0 : }
164 0 : dst = append(dst, '@')
165 0 : dst = strconv.AppendUint(dst, (interval.Upper - 1), 10)
166 0 : return dst, true, nil
167 : }
|
