Line data Source code
1 : // Copyright 2018 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 rowblk
6 :
7 : import (
8 : "fmt"
9 : "os"
10 : "sync"
11 :
12 : "github.com/cockroachdb/pebble/internal/base"
13 : "github.com/cockroachdb/pebble/internal/invariants"
14 : "github.com/cockroachdb/pebble/internal/keyspan"
15 : "github.com/cockroachdb/pebble/internal/rangedel"
16 : "github.com/cockroachdb/pebble/internal/rangekey"
17 : "github.com/cockroachdb/pebble/sstable/block"
18 : )
19 :
20 : // fragmentIter wraps an Iter, implementing the keyspan.FragmentIterator
21 : // interface. It's used for reading range deletion and range key blocks.
22 : //
23 : // Range deletions and range keys are fragmented before they're persisted to the
24 : // block. Overlapping fragments have identical bounds. The fragmentIter gathers
25 : // all the fragments with identical bounds within a block and returns a single
26 : // keyspan.Span describing all the keys defined over the span.
27 : //
28 : // # Memory lifetime
29 : //
30 : // A Span returned by fragmentIter is only guaranteed to be stable until the
31 : // next fragmentIter iteration positioning method. A Span's Keys slice may be
32 : // reused, so the user must not assume it's stable.
33 : //
34 : // Blocks holding range deletions and range keys are configured to use a restart
35 : // interval of 1. This provides key stability. The caller may treat the various
36 : // byte slices (start, end, suffix, value) as stable for the lifetime of the
37 : // iterator.
38 : type fragmentIter struct {
39 : blockIter Iter
40 : keyBuf [2]keyspan.Key
41 : span keyspan.Span
42 : dir int8
43 :
44 : // elideSameSeqnum, if true, returns only the first-occurring (in forward
45 : // order) Key for each sequence number.
46 : elideSameSeqnum bool
47 : closeCheck invariants.CloseChecker
48 : }
49 :
50 : var _ keyspan.FragmentIterator = (*fragmentIter)(nil)
51 :
52 : var fragmentBlockIterPool = sync.Pool{
53 2 : New: func() interface{} {
54 2 : i := &fragmentIter{}
55 2 : // Note: this is a no-op if invariants are disabled or race is enabled.
56 2 : invariants.SetFinalizer(i, checkFragmentBlockIterator)
57 2 : return i
58 2 : },
59 : }
60 :
61 : // NewFragmentIter returns a new keyspan iterator that iterates over a block's
62 : // spans.
63 : func NewFragmentIter(
64 : cmp base.Compare,
65 : split base.Split,
66 : blockHandle block.BufferHandle,
67 : transforms block.FragmentIterTransforms,
68 2 : ) (keyspan.FragmentIterator, error) {
69 2 : i := fragmentBlockIterPool.Get().(*fragmentIter)
70 2 :
71 2 : // Use the i.keyBuf array to back the Keys slice to prevent an allocation
72 2 : // when the spans contain few keys.
73 2 : i.span.Keys = i.keyBuf[:0]
74 2 : i.elideSameSeqnum = transforms.ElideSameSeqNum
75 2 : i.closeCheck = invariants.CloseChecker{}
76 2 :
77 2 : if err := i.blockIter.InitHandle(cmp, split, blockHandle, block.IterTransforms{
78 2 : SyntheticSeqNum: transforms.SyntheticSeqNum,
79 2 : // It's okay for HideObsoletePoints to be false here, even for shared
80 2 : // ingested sstables. This is because rangedels do not apply to points in
81 2 : // the same sstable at the same sequence number anyway, so exposing obsolete
82 2 : // rangedels is harmless.
83 2 : HideObsoletePoints: false,
84 2 : }); err != nil {
85 0 : i.Close()
86 0 : return nil, err
87 0 : }
88 2 : return i, nil
89 : }
90 :
91 : // initSpan initializes the span with a single fragment.
92 : // Note that the span start and end keys and range key contents are aliased to
93 : // the key or value. This is ok because the range del/key block doesn't use
94 : // prefix compression (and we don't perform any transforms), so the key/value
95 : // will be pointing directly into the buffer data.
96 2 : func (i *fragmentIter) initSpan(ik base.InternalKey, internalValue []byte) error {
97 2 : var err error
98 2 : if ik.Kind() == base.InternalKeyKindRangeDelete {
99 2 : i.span = rangedel.Decode(ik, internalValue, i.span.Keys[:0])
100 2 : } else {
101 2 : i.span, err = rangekey.Decode(ik, internalValue, i.span.Keys[:0])
102 2 : }
103 2 : return err
104 : }
105 :
106 : // addToSpan adds a fragment to the existing span. The fragment must be for the
107 : // same start/end keys.
108 : func (i *fragmentIter) addToSpan(
109 : cmp base.Compare, ik base.InternalKey, internalValue []byte,
110 2 : ) error {
111 2 : var err error
112 2 : if ik.Kind() == base.InternalKeyKindRangeDelete {
113 2 : err = rangedel.DecodeIntoSpan(cmp, ik, internalValue, &i.span)
114 2 : } else {
115 2 : err = rangekey.DecodeIntoSpan(cmp, ik, internalValue, &i.span)
116 2 : }
117 2 : return err
118 : }
119 :
120 2 : func (i *fragmentIter) elideKeysOfSameSeqNum() {
121 2 : if invariants.Enabled {
122 2 : if !i.elideSameSeqnum || len(i.span.Keys) == 0 {
123 0 : panic("elideKeysOfSameSeqNum called when it should not be")
124 : }
125 : }
126 2 : lastSeqNum := i.span.Keys[0].SeqNum()
127 2 : k := 1
128 2 : for j := 1; j < len(i.span.Keys); j++ {
129 2 : if lastSeqNum != i.span.Keys[j].SeqNum() {
130 2 : lastSeqNum = i.span.Keys[j].SeqNum()
131 2 : i.span.Keys[k] = i.span.Keys[j]
132 2 : k++
133 2 : }
134 : }
135 2 : i.span.Keys = i.span.Keys[:k]
136 : }
137 :
138 : // gatherForward gathers internal keys with identical bounds. Keys defined over
139 : // spans of the keyspace are fragmented such that any overlapping key spans have
140 : // identical bounds. When these spans are persisted to a range deletion or range
141 : // key block, they may be persisted as multiple internal keys in order to encode
142 : // multiple sequence numbers or key kinds.
143 : //
144 : // gatherForward iterates forward, re-combining the fragmented internal keys to
145 : // reconstruct a keyspan.Span that holds all the keys defined over the span.
146 2 : func (i *fragmentIter) gatherForward(kv *base.InternalKV) (*keyspan.Span, error) {
147 2 : i.span = keyspan.Span{}
148 2 : if kv == nil || !i.blockIter.Valid() {
149 2 : return nil, nil
150 2 : }
151 : // Use the i.keyBuf array to back the Keys slice to prevent an allocation
152 : // when a span contains few keys.
153 2 : i.span.Keys = i.keyBuf[:0]
154 2 :
155 2 : // Decode the span's end key and individual keys from the value.
156 2 : if err := i.initSpan(kv.K, kv.InPlaceValue()); err != nil {
157 0 : return nil, err
158 0 : }
159 :
160 : // There might exist additional internal keys with identical bounds encoded
161 : // within the block. Iterate forward, accumulating all the keys with
162 : // identical bounds to s.
163 :
164 : // Overlapping fragments are required to have exactly equal start and
165 : // end bounds.
166 2 : for kv = i.blockIter.Next(); kv != nil && i.blockIter.cmp(kv.K.UserKey, i.span.Start) == 0; kv = i.blockIter.Next() {
167 2 : if err := i.addToSpan(i.blockIter.cmp, kv.K, kv.InPlaceValue()); err != nil {
168 0 : return nil, err
169 0 : }
170 : }
171 2 : if i.elideSameSeqnum && len(i.span.Keys) > 0 {
172 2 : i.elideKeysOfSameSeqNum()
173 2 : }
174 : // i.blockIter is positioned over the first internal key for the next span.
175 2 : return &i.span, nil
176 : }
177 :
178 : // gatherBackward gathers internal keys with identical bounds. Keys defined over
179 : // spans of the keyspace are fragmented such that any overlapping key spans have
180 : // identical bounds. When these spans are persisted to a range deletion or range
181 : // key block, they may be persisted as multiple internal keys in order to encode
182 : // multiple sequence numbers or key kinds.
183 : //
184 : // gatherBackward iterates backwards, re-combining the fragmented internal keys
185 : // to reconstruct a keyspan.Span that holds all the keys defined over the span.
186 2 : func (i *fragmentIter) gatherBackward(kv *base.InternalKV) (*keyspan.Span, error) {
187 2 : i.span = keyspan.Span{}
188 2 : if kv == nil || !i.blockIter.Valid() {
189 2 : return nil, nil
190 2 : }
191 :
192 : // Decode the span's end key and individual keys from the value.
193 2 : if err := i.initSpan(kv.K, kv.InPlaceValue()); err != nil {
194 0 : return nil, err
195 0 : }
196 :
197 : // There might exist additional internal keys with identical bounds encoded
198 : // within the block. Iterate backward, accumulating all the keys with
199 : // identical bounds to s.
200 : //
201 : // Overlapping fragments are required to have exactly equal start and
202 : // end bounds.
203 2 : for kv = i.blockIter.Prev(); kv != nil && i.blockIter.cmp(kv.K.UserKey, i.span.Start) == 0; kv = i.blockIter.Prev() {
204 2 : if err := i.addToSpan(i.blockIter.cmp, kv.K, kv.InPlaceValue()); err != nil {
205 0 : return nil, err
206 0 : }
207 : }
208 : // i.blockIter is positioned over the last internal key for the previous
209 : // span.
210 :
211 : // Backwards iteration encounters internal keys in the wrong order.
212 2 : keyspan.SortKeysByTrailer(&i.span.Keys)
213 2 :
214 2 : if i.elideSameSeqnum && len(i.span.Keys) > 0 {
215 2 : i.elideKeysOfSameSeqNum()
216 2 : }
217 2 : return &i.span, nil
218 : }
219 :
220 : // Close implements (keyspan.FragmentIterator).Close.
221 2 : func (i *fragmentIter) Close() {
222 2 : i.blockIter.Close()
223 2 : i.closeCheck.Close()
224 2 :
225 2 : if invariants.Sometimes(25) {
226 2 : // In invariants mode, sometimes don't add the object to the pool so that we
227 2 : // can check for double closes that take longer than the object stays in the
228 2 : // pool.
229 2 : return
230 2 : }
231 :
232 2 : *i = fragmentIter{
233 2 : blockIter: i.blockIter.ResetForReuse(),
234 2 : closeCheck: i.closeCheck,
235 2 : }
236 2 : fragmentBlockIterPool.Put(i)
237 : }
238 :
239 : // First implements (keyspan.FragmentIterator).First
240 2 : func (i *fragmentIter) First() (*keyspan.Span, error) {
241 2 : i.dir = +1
242 2 : return i.gatherForward(i.blockIter.First())
243 2 : }
244 :
245 : // Last implements (keyspan.FragmentIterator).Last.
246 2 : func (i *fragmentIter) Last() (*keyspan.Span, error) {
247 2 : i.dir = -1
248 2 : return i.gatherBackward(i.blockIter.Last())
249 2 : }
250 :
251 : // Next implements (keyspan.FragmentIterator).Next.
252 2 : func (i *fragmentIter) Next() (*keyspan.Span, error) {
253 2 : switch {
254 2 : case i.dir == -1 && !i.span.Valid():
255 2 : // Switching directions.
256 2 : //
257 2 : // i.blockIter is exhausted, before the first key. Move onto the first.
258 2 : i.blockIter.First()
259 2 : i.dir = +1
260 2 : case i.dir == -1 && i.span.Valid():
261 2 : // Switching directions.
262 2 : //
263 2 : // i.blockIter is currently positioned over the last internal key for
264 2 : // the previous span. Next it once to move to the first internal key
265 2 : // that makes up the current span, and gatherForwaad to land on the
266 2 : // first internal key making up the next span.
267 2 : //
268 2 : // In the diagram below, if the last span returned to the user during
269 2 : // reverse iteration was [b,c), i.blockIter is currently positioned at
270 2 : // [a,b). The block iter must be positioned over [d,e) to gather the
271 2 : // next span's fragments.
272 2 : //
273 2 : // ... [a,b) [b,c) [b,c) [b,c) [d,e) ...
274 2 : // ^ ^
275 2 : // i.blockIter want
276 2 : if x, err := i.gatherForward(i.blockIter.Next()); err != nil {
277 0 : return nil, err
278 2 : } else if invariants.Enabled && !x.Valid() {
279 0 : panic("pebble: invariant violation: next entry unexpectedly invalid")
280 : }
281 2 : i.dir = +1
282 : }
283 : // We know that this blockIter has in-place values.
284 2 : return i.gatherForward(i.blockIter.KV())
285 : }
286 :
287 : // Prev implements (keyspan.FragmentIterator).Prev.
288 2 : func (i *fragmentIter) Prev() (*keyspan.Span, error) {
289 2 : switch {
290 2 : case i.dir == +1 && !i.span.Valid():
291 2 : // Switching directions.
292 2 : //
293 2 : // i.blockIter is exhausted, after the last key. Move onto the last.
294 2 : i.blockIter.Last()
295 2 : i.dir = -1
296 2 : case i.dir == +1 && i.span.Valid():
297 2 : // Switching directions.
298 2 : //
299 2 : // i.blockIter is currently positioned over the first internal key for
300 2 : // the next span. Prev it once to move to the last internal key that
301 2 : // makes up the current span, and gatherBackward to land on the last
302 2 : // internal key making up the previous span.
303 2 : //
304 2 : // In the diagram below, if the last span returned to the user during
305 2 : // forward iteration was [b,c), i.blockIter is currently positioned at
306 2 : // [d,e). The block iter must be positioned over [a,b) to gather the
307 2 : // previous span's fragments.
308 2 : //
309 2 : // ... [a,b) [b,c) [b,c) [b,c) [d,e) ...
310 2 : // ^ ^
311 2 : // want i.blockIter
312 2 : if x, err := i.gatherBackward(i.blockIter.Prev()); err != nil {
313 0 : return nil, err
314 2 : } else if invariants.Enabled && !x.Valid() {
315 0 : panic("pebble: invariant violation: previous entry unexpectedly invalid")
316 : }
317 2 : i.dir = -1
318 : }
319 : // We know that this blockIter has in-place values.
320 2 : return i.gatherBackward(i.blockIter.KV())
321 : }
322 :
323 : // SeekGE implements (keyspan.FragmentIterator).SeekGE.
324 2 : func (i *fragmentIter) SeekGE(k []byte) (*keyspan.Span, error) {
325 2 : if s, err := i.SeekLT(k); err != nil {
326 0 : return nil, err
327 2 : } else if s != nil && i.blockIter.cmp(k, s.End) < 0 {
328 2 : return s, nil
329 2 : }
330 : // TODO(jackson): If the above i.SeekLT(k) discovers a span but the span
331 : // doesn't meet the k < s.End comparison, then there's no need for the
332 : // SeekLT to gatherBackward.
333 2 : return i.Next()
334 : }
335 :
336 : // SeekLT implements (keyspan.FragmentIterator).SeekLT.
337 2 : func (i *fragmentIter) SeekLT(k []byte) (*keyspan.Span, error) {
338 2 : i.dir = -1
339 2 : return i.gatherBackward(i.blockIter.SeekLT(k, base.SeekLTFlagsNone))
340 2 : }
341 :
342 : // String implements fmt.Stringer.
343 0 : func (i *fragmentIter) String() string {
344 0 : return "fragment-block-iter"
345 0 : }
346 :
347 : // WrapChildren implements FragmentIterator.
348 0 : func (i *fragmentIter) WrapChildren(wrap keyspan.WrapFn) {}
349 :
350 2 : func checkFragmentBlockIterator(obj interface{}) {
351 2 : i := obj.(*fragmentIter)
352 2 : if p := i.blockIter.Handle().Get(); p != nil {
353 0 : fmt.Fprintf(os.Stderr, "fragmentBlockIter.blockIter.handle is not nil: %p\n", p)
354 0 : os.Exit(1)
355 0 : }
356 : }
|
