Line data Source code
1 : // Copyright 2024 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 rangekeystack
6 :
7 : import (
8 : "bytes"
9 :
10 : "github.com/cockroachdb/pebble/internal/base"
11 : "github.com/cockroachdb/pebble/internal/invariants"
12 : "github.com/cockroachdb/pebble/internal/keyspan"
13 : "github.com/cockroachdb/pebble/internal/keyspan/keyspanimpl"
14 : "github.com/cockroachdb/pebble/internal/manifest"
15 : "github.com/cockroachdb/pebble/internal/rangekey"
16 : )
17 :
18 : // UserIteratorConfig holds state for constructing the range key iterator stack
19 : // for user iteration. The range key iterator must merge range key spans across
20 : // the levels of the LSM. This merging is performed by a keyspanimpl.MergingIter
21 : // on-the-fly. The UserIteratorConfig implements keyspan.Transformer, evaluating
22 : // range-key semantics and shadowing, so the spans returned by a MergingIter are
23 : // fully resolved.
24 : //
25 : // The MergingIter is wrapped by a BoundedIter, which elides spans that are
26 : // outside the iterator bounds (or the current prefix's bounds, during prefix
27 : // iteration mode).
28 : //
29 : // To provide determinisim during iteration, the BoundedIter is wrapped by a
30 : // DefragmentingIter that defragments abutting spans with identical
31 : // user-observable state.
32 : //
33 : // At the top-level an InterleavingIter interleaves range keys with point keys
34 : // and performs truncation to iterator bounds.
35 : //
36 : // Below is an abbreviated diagram illustrating the mechanics of a SeekGE.
37 : //
38 : // InterleavingIter.SeekGE
39 : // │
40 : // DefragmentingIter.SeekGE
41 : // │
42 : // BoundedIter.SeekGE
43 : // │
44 : // ╭────────────────┴───────────────╮
45 : // │ ├── defragmentBwd*
46 : // MergingIter.SeekGE │
47 : // │ ╰── defragmentFwd
48 : // ╰─╶╶ per level╶╶ ─╮
49 : // │
50 : // │
51 : // ├── <?>.SeekLT
52 : // │
53 : // ╰── <?>.Next
54 : type UserIteratorConfig struct {
55 : snapshot base.SeqNum
56 : comparer *base.Comparer
57 : miter keyspanimpl.MergingIter
58 : biter keyspan.BoundedIter
59 : diter keyspan.DefragmentingIter
60 : liters [manifest.NumLevels]keyspanimpl.LevelIter
61 : litersUsed int
62 : internalKeys bool
63 : bufs *Buffers
64 : }
65 :
66 : // Buffers holds various buffers used for range key iteration. They're exposed
67 : // so that they may be pooled and reused between iterators.
68 : type Buffers struct {
69 : merging keyspanimpl.MergingBuffers
70 : defragmenting keyspan.DefragmentingBuffers
71 : sortBuf []keyspan.Key
72 : }
73 :
74 : // PrepareForReuse discards any excessively large buffers.
75 1 : func (bufs *Buffers) PrepareForReuse() {
76 1 : bufs.merging.PrepareForReuse()
77 1 : bufs.defragmenting.PrepareForReuse()
78 1 : }
79 :
80 : // Init initializes the range key iterator stack for user iteration. The
81 : // resulting fragment iterator applies range key semantics, defragments spans
82 : // according to their user-observable state and, if !internalKeys, removes all
83 : // Keys other than RangeKeySets describing the current state of range keys. The
84 : // resulting spans contain Keys sorted by suffix (unless internalKeys is true,
85 : // in which case they remain sorted by trailer descending).
86 : //
87 : // The snapshot sequence number parameter determines which keys are visible. Any
88 : // keys not visible at the provided snapshot are ignored.
89 : func (ui *UserIteratorConfig) Init(
90 : comparer *base.Comparer,
91 : snapshot base.SeqNum,
92 : lower, upper []byte,
93 : hasPrefix *bool,
94 : prefix *[]byte,
95 : internalKeys bool,
96 : bufs *Buffers,
97 : iters ...keyspan.FragmentIterator,
98 1 : ) keyspan.FragmentIterator {
99 1 : ui.snapshot = snapshot
100 1 : ui.comparer = comparer
101 1 : ui.internalKeys = internalKeys
102 1 : ui.miter.Init(comparer, ui, &bufs.merging, iters...)
103 1 : ui.biter.Init(comparer.Compare, comparer.Split, &ui.miter, lower, upper, hasPrefix, prefix)
104 1 : if internalKeys {
105 1 : ui.diter.Init(comparer, &ui.biter, keyspan.DefragmentInternal, keyspan.StaticDefragmentReducer, &bufs.defragmenting)
106 1 : } else {
107 1 : ui.diter.Init(comparer, &ui.biter, ui, keyspan.StaticDefragmentReducer, &bufs.defragmenting)
108 1 : }
109 1 : ui.litersUsed = 0
110 1 : ui.bufs = bufs
111 1 : return &ui.diter
112 : }
113 :
114 : // AddLevel adds a new level to the bottom of the iterator stack. AddLevel
115 : // must be called after Init and before any other method on the iterator.
116 1 : func (ui *UserIteratorConfig) AddLevel(iter keyspan.FragmentIterator) {
117 1 : ui.miter.AddLevel(iter)
118 1 : }
119 :
120 : // NewLevelIter returns a pointer to a newly allocated or reused
121 : // keyspanimpl.LevelIter. The caller is responsible for calling Init() on this
122 : // instance.
123 1 : func (ui *UserIteratorConfig) NewLevelIter() *keyspanimpl.LevelIter {
124 1 : if ui.litersUsed >= len(ui.liters) {
125 1 : return &keyspanimpl.LevelIter{}
126 1 : }
127 1 : ui.litersUsed++
128 1 : return &ui.liters[ui.litersUsed-1]
129 : }
130 :
131 : // SetBounds propagates bounds to the iterator stack. The fragment iterator
132 : // interface ordinarily doesn't enforce bounds, so this is exposed as an
133 : // explicit method on the user iterator config.
134 1 : func (ui *UserIteratorConfig) SetBounds(lower, upper []byte) {
135 1 : ui.biter.SetBounds(lower, upper)
136 1 : }
137 :
138 : // Transform implements the keyspan.Transformer interface for use with a
139 : // keyspanimpl.MergingIter. It transforms spans by resolving range keys at the
140 : // provided snapshot sequence number. Shadowing of keys is resolved (eg, removal
141 : // of unset keys, removal of keys overwritten by a set at the same suffix, etc)
142 : // and then non-RangeKeySet keys are removed. The resulting transformed spans
143 : // only contain RangeKeySets describing the state visible at the provided
144 : // sequence number, and hold their Keys sorted by Suffix (except if internalKeys
145 : // is true, then keys remain sorted by trailer.
146 : func (ui *UserIteratorConfig) Transform(
147 : suffixCmp base.CompareSuffixes, s keyspan.Span, dst *keyspan.Span,
148 1 : ) error {
149 1 : // Apply shadowing of keys.
150 1 : dst.Start = s.Start
151 1 : dst.End = s.End
152 1 : ui.bufs.sortBuf = rangekey.CoalesceInto(suffixCmp, ui.bufs.sortBuf[:0], ui.snapshot, s.Keys)
153 1 : if ui.internalKeys {
154 1 : if s.KeysOrder != keyspan.ByTrailerDesc {
155 0 : panic("unexpected key ordering in UserIteratorTransform with internalKeys = true")
156 : }
157 1 : dst.Keys = ui.bufs.sortBuf
158 1 : keyspan.SortKeysByTrailer(dst.Keys)
159 1 : return nil
160 : }
161 : // During user iteration over range keys, unsets and deletes don't matter. This
162 : // step helps logical defragmentation during iteration.
163 1 : keys := ui.bufs.sortBuf
164 1 : dst.Keys = dst.Keys[:0]
165 1 : for i := range keys {
166 1 : switch keys[i].Kind() {
167 1 : case base.InternalKeyKindRangeKeySet:
168 1 : if invariants.Enabled && len(dst.Keys) > 0 && suffixCmp(dst.Keys[len(dst.Keys)-1].Suffix, keys[i].Suffix) > 0 {
169 0 : panic("pebble: keys unexpectedly not in ascending suffix order")
170 : }
171 1 : dst.Keys = append(dst.Keys, keys[i])
172 1 : case base.InternalKeyKindRangeKeyUnset:
173 1 : if invariants.Enabled && len(dst.Keys) > 0 && suffixCmp(dst.Keys[len(dst.Keys)-1].Suffix, keys[i].Suffix) > 0 {
174 0 : panic("pebble: keys unexpectedly not in ascending suffix order")
175 : }
176 : // Skip.
177 1 : continue
178 1 : case base.InternalKeyKindRangeKeyDelete:
179 1 : // Skip.
180 1 : continue
181 0 : default:
182 0 : return base.CorruptionErrorf("pebble: unrecognized range key kind %s", keys[i].Kind())
183 : }
184 : }
185 : // coalesce results in dst.Keys being sorted by Suffix.
186 1 : dst.KeysOrder = keyspan.BySuffixAsc
187 1 : return nil
188 : }
189 :
190 : // ShouldDefragment implements the DefragmentMethod interface and configures a
191 : // DefragmentingIter to defragment spans of range keys if their user-visible
192 : // state is identical. This defragmenting method assumes the provided spans have
193 : // already been transformed through (UserIterationConfig).Transform, so all
194 : // RangeKeySets are user-visible sets and are already in Suffix order. This
195 : // defragmenter checks for equality between set suffixes and values (ignoring
196 : // sequence numbers). It's intended for use during user iteration, when the
197 : // wrapped keyspan iterator is merging spans across all levels of the LSM.
198 : func (ui *UserIteratorConfig) ShouldDefragment(
199 : suffixCmp base.CompareSuffixes, a, b *keyspan.Span,
200 1 : ) bool {
201 1 : // This method is not called with internalKeys = true.
202 1 : if ui.internalKeys {
203 0 : panic("unexpected call to ShouldDefragment with internalKeys = true")
204 : }
205 : // This implementation must only be used on spans that have transformed by
206 : // ui.Transform. The transform applies shadowing, removes all keys besides
207 : // the resulting Sets and sorts the keys by suffix. Since shadowing has been
208 : // applied, each Set must set a unique suffix. If the two spans are
209 : // equivalent, they must have the same number of range key sets.
210 1 : if len(a.Keys) != len(b.Keys) || len(a.Keys) == 0 {
211 1 : return false
212 1 : }
213 1 : if a.KeysOrder != keyspan.BySuffixAsc || b.KeysOrder != keyspan.BySuffixAsc {
214 0 : panic("pebble: range key span's keys unexpectedly not in ascending suffix order")
215 : }
216 :
217 1 : ret := true
218 1 : for i := range a.Keys {
219 1 : if invariants.Enabled {
220 1 : if a.Keys[i].Kind() != base.InternalKeyKindRangeKeySet ||
221 1 : b.Keys[i].Kind() != base.InternalKeyKindRangeKeySet {
222 0 : panic("pebble: unexpected non-RangeKeySet during defragmentation")
223 : }
224 1 : if i > 0 && (suffixCmp(a.Keys[i].Suffix, a.Keys[i-1].Suffix) < 0 ||
225 1 : suffixCmp(b.Keys[i].Suffix, b.Keys[i-1].Suffix) < 0) {
226 0 : panic("pebble: range keys not ordered by suffix during defragmentation")
227 : }
228 : }
229 1 : if suffixCmp(a.Keys[i].Suffix, b.Keys[i].Suffix) != 0 {
230 1 : ret = false
231 1 : break
232 : }
233 1 : if !bytes.Equal(a.Keys[i].Value, b.Keys[i].Value) {
234 1 : ret = false
235 1 : break
236 : }
237 : }
238 1 : return ret
239 : }
|
