Line data Source code
1 : // Copyright 2021 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 keyspan
6 :
7 : import (
8 : "fmt"
9 :
10 : "github.com/cockroachdb/pebble/internal/base"
11 : "github.com/cockroachdb/pebble/internal/invariants"
12 : )
13 :
14 : // A SpanMask may be used to configure an interleaving iterator to skip point
15 : // keys that fall within the bounds of some spans.
16 : type SpanMask interface {
17 : // SpanChanged is invoked by an interleaving iterator whenever the current
18 : // span changes. As the iterator passes into or out of a Span, it invokes
19 : // SpanChanged, passing the new Span. When the iterator passes out of a
20 : // span's boundaries and is no longer covered by any span, SpanChanged is
21 : // invoked with a nil span.
22 : //
23 : // SpanChanged is invoked before SkipPoint, and callers may use SpanChanged
24 : // to recalculate state used by SkipPoint for masking.
25 : //
26 : // SpanChanged may be invoked consecutively with identical spans under some
27 : // circumstances, such as repeatedly absolutely positioning an iterator to
28 : // positions covered by the same span, or while changing directions.
29 : SpanChanged(*Span)
30 : // SkipPoint is invoked by the interleaving iterator whenever the iterator
31 : // encounters a point key covered by a Span. If SkipPoint returns true, the
32 : // interleaving iterator skips the point key and all larger keys with the
33 : // same prefix. This is used during range key iteration to skip over point
34 : // keys 'masked' by range keys.
35 : SkipPoint(userKey []byte) bool
36 : }
37 :
38 : // InterleavingIter combines an iterator over point keys with an iterator over
39 : // key spans.
40 : //
41 : // Throughout Pebble, some keys apply at single discrete points within the user
42 : // keyspace. Other keys apply over continuous spans of the user key space.
43 : // Internally, iterators over point keys adhere to the base.InternalIterator
44 : // interface, and iterators over spans adhere to the keyspan.FragmentIterator
45 : // interface. The InterleavingIterator wraps a point iterator and span iterator,
46 : // providing access to all the elements of both iterators.
47 : //
48 : // The InterleavingIterator implements the point base.InternalIterator
49 : // interface. After any of the iterator's methods return a key, a caller may
50 : // call Span to retrieve the span covering the returned key, if any. A span is
51 : // considered to 'cover' a returned key if the span's [start, end) bounds
52 : // include the key's user key.
53 : //
54 : // In addition to tracking the current covering span, InterleavingIter returns a
55 : // special InternalKey at span start boundaries. Start boundaries are surfaced
56 : // as a synthetic span marker: an InternalKey with the boundary as the user key,
57 : // the infinite sequence number and a key kind selected from an arbitrary key
58 : // the infinite sequence number and an arbitrary contained key's kind. Since
59 : // which of the Span's key's kind is surfaced is undefined, the caller should
60 : // not use the InternalKey's kind. The caller should only rely on the `Span`
61 : // method for retrieving information about spanning keys. The interleaved
62 : // synthetic keys have the infinite sequence number so that they're interleaved
63 : // before any point keys with the same user key when iterating forward and after
64 : // when iterating backward.
65 : //
66 : // Interleaving the synthetic start key boundaries at the maximum sequence
67 : // number provides an opportunity for the higher-level, public Iterator to
68 : // observe the Span, even if no live points keys exist within the boudns of the
69 : // Span.
70 : //
71 : // When returning a synthetic marker key for a start boundary, InterleavingIter
72 : // will truncate the span's start bound to the SeekGE or SeekPrefixGE search
73 : // key. For example, a SeekGE("d") that finds a span [a, z) may return a
74 : // synthetic span marker key `d#72057594037927935,21`.
75 : //
76 : // If bounds have been applied to the iterator through SetBounds,
77 : // InterleavingIter will truncate the bounds of spans returned through Span to
78 : // the set bounds. The bounds returned through Span are not truncated by a
79 : // SeekGE or SeekPrefixGE search key. Consider, for example SetBounds('c', 'e'),
80 : // with an iterator containing the Span [a,z):
81 : //
82 : // First() = `c#72057594037927935,21` Span() = [c,e)
83 : // SeekGE('d') = `d#72057594037927935,21` Span() = [c,e)
84 : //
85 : // InterleavedIter does not interleave synthetic markers for spans that do not
86 : // contain any keys.
87 : //
88 : // # SpanMask
89 : //
90 : // InterelavingIter takes a SpanMask parameter that may be used to configure the
91 : // behavior of the iterator. See the documentation on the SpanMask type.
92 : //
93 : // All spans containing keys are exposed during iteration.
94 : type InterleavingIter struct {
95 : cmp base.Compare
96 : comparer *base.Comparer
97 : pointIter base.InternalIterator
98 : keyspanIter FragmentIterator
99 : mask SpanMask
100 :
101 : // lower and upper hold the iteration bounds set through SetBounds.
102 : lower, upper []byte
103 : // keyBuf is used to copy SeekGE or SeekPrefixGE arguments when they're used
104 : // to truncate a span. The byte slices backing a SeekGE/SeekPrefixGE search
105 : // keys can come directly from the end user, so they're copied into keyBuf
106 : // to ensure key stability.
107 : keyBuf []byte
108 : // nextPrefixBuf is used during SeekPrefixGE calls to store the truncated
109 : // upper bound of the returned spans. SeekPrefixGE truncates the returned
110 : // spans to an upper bound of the seeked prefix's immediate successor.
111 : nextPrefixBuf []byte
112 : pointKey *base.InternalKey
113 : pointVal base.LazyValue
114 : // prefix records the iterator's current prefix if the iterator is in prefix
115 : // mode. During prefix mode, Pebble will truncate spans to the next prefix.
116 : // If the iterator subsequently leaves prefix mode, the existing span cached
117 : // in i.span must be invalidated because its bounds do not reflect the
118 : // original span's true bounds.
119 : prefix []byte
120 : // span holds the span at the keyspanIter's current position. If the span is
121 : // wholly contained within the iterator bounds, this span is directly
122 : // returned to the iterator consumer through Span(). If either bound needed
123 : // to be truncated to the iterator bounds, then truncated is set to true and
124 : // Span() must return a pointer to truncatedSpan.
125 : span *Span
126 : // spanMarker holds the synthetic key that is returned when the iterator
127 : // passes over a key span's start bound.
128 : spanMarker base.InternalKey
129 : // truncated indicates whether or not the span at the current position
130 : // needed to be truncated. If it did, truncatedSpan holds the truncated
131 : // span that should be returned.
132 : truncatedSpan Span
133 : truncated bool
134 :
135 : // Keeping all of the bools/uint8s together reduces the sizeof the struct.
136 :
137 : // pos encodes the current position of the iterator: exhausted, on the point
138 : // key, on a keyspan start, or on a keyspan end.
139 : pos interleavePos
140 : // withinSpan indicates whether the iterator is currently positioned within
141 : // the bounds of the current span (i.span). withinSpan must be updated
142 : // whenever the interleaving iterator's position enters or exits the bounds
143 : // of a span.
144 : withinSpan bool
145 : // spanMarkerTruncated is set by SeekGE/SeekPrefixGE calls that truncate a
146 : // span's start bound marker to the search key. It's returned to false on
147 : // the next repositioning of the keyspan iterator.
148 : spanMarkerTruncated bool
149 : // maskSpanChangedCalled records whether or not the last call to
150 : // SpanMask.SpanChanged provided the current span (i.span) or not.
151 : maskSpanChangedCalled bool
152 : // dir indicates the direction of iteration: forward (+1) or backward (-1)
153 : dir int8
154 : }
155 :
156 : // interleavePos indicates the iterator's current position. Note that both
157 : // keyspanStart and keyspanEnd positions correspond to their user key boundaries
158 : // with maximal sequence numbers. This means in the forward direction
159 : // posKeyspanStart and posKeyspanEnd are always interleaved before a posPointKey
160 : // with the same user key.
161 : type interleavePos int8
162 :
163 : const (
164 : posUninitialized interleavePos = iota
165 : posExhausted
166 : posPointKey
167 : posKeyspanStart
168 : posKeyspanEnd
169 : )
170 :
171 : // Assert that *InterleavingIter implements the InternalIterator interface.
172 : var _ base.InternalIterator = &InterleavingIter{}
173 :
174 : // InterleavingIterOpts holds options configuring the behavior of a
175 : // InterleavingIter.
176 : type InterleavingIterOpts struct {
177 : Mask SpanMask
178 : LowerBound, UpperBound []byte
179 : }
180 :
181 : // Init initializes the InterleavingIter to interleave point keys from pointIter
182 : // with key spans from keyspanIter.
183 : //
184 : // The point iterator must already have the bounds provided on opts. Init does
185 : // not propagate the bounds down the iterator stack.
186 : func (i *InterleavingIter) Init(
187 : comparer *base.Comparer,
188 : pointIter base.InternalIterator,
189 : keyspanIter FragmentIterator,
190 : opts InterleavingIterOpts,
191 1 : ) {
192 1 : *i = InterleavingIter{
193 1 : cmp: comparer.Compare,
194 1 : comparer: comparer,
195 1 : pointIter: pointIter,
196 1 : keyspanIter: keyspanIter,
197 1 : mask: opts.Mask,
198 1 : lower: opts.LowerBound,
199 1 : upper: opts.UpperBound,
200 1 : }
201 1 : }
202 :
203 : // InitSeekGE may be called after Init but before any positioning method.
204 : // InitSeekGE initializes the current position of the point iterator and then
205 : // performs a SeekGE on the keyspan iterator using the provided key. InitSeekGE
206 : // returns whichever point or keyspan key is smaller. After InitSeekGE, the
207 : // iterator is positioned and may be repositioned using relative positioning
208 : // methods.
209 : //
210 : // This method is used specifically for lazily constructing combined iterators.
211 : // It allows for seeding the iterator with the current position of the point
212 : // iterator.
213 : func (i *InterleavingIter) InitSeekGE(
214 : prefix, key []byte, pointKey *base.InternalKey, pointValue base.LazyValue,
215 1 : ) (*base.InternalKey, base.LazyValue) {
216 1 : i.dir = +1
217 1 : i.clearMask()
218 1 : i.prefix = prefix
219 1 : i.pointKey, i.pointVal = pointKey, pointValue
220 1 : // NB: This keyspanSeekGE call will truncate the span to the seek key if
221 1 : // necessary. This truncation is important for cases where a switch to
222 1 : // combined iteration is made during a user-initiated SeekGE.
223 1 : i.keyspanSeekGE(key, prefix)
224 1 : i.computeSmallestPos()
225 1 : return i.yieldPosition(key, i.nextPos)
226 1 : }
227 :
228 : // InitSeekLT may be called after Init but before any positioning method.
229 : // InitSeekLT initializes the current position of the point iterator and then
230 : // performs a SeekLT on the keyspan iterator using the provided key. InitSeekLT
231 : // returns whichever point or keyspan key is larger. After InitSeekLT, the
232 : // iterator is positioned and may be repositioned using relative positioning
233 : // methods.
234 : //
235 : // This method is used specifically for lazily constructing combined iterators.
236 : // It allows for seeding the iterator with the current position of the point
237 : // iterator.
238 : func (i *InterleavingIter) InitSeekLT(
239 : key []byte, pointKey *base.InternalKey, pointValue base.LazyValue,
240 1 : ) (*base.InternalKey, base.LazyValue) {
241 1 : i.dir = -1
242 1 : i.clearMask()
243 1 : i.pointKey, i.pointVal = pointKey, pointValue
244 1 : i.keyspanSeekLT(key)
245 1 : i.computeLargestPos()
246 1 : return i.yieldPosition(i.lower, i.prevPos)
247 1 : }
248 :
249 : // SeekGE implements (base.InternalIterator).SeekGE.
250 : //
251 : // If there exists a span with a start key ≤ the first matching point key,
252 : // SeekGE will return a synthetic span marker key for the span. If this span's
253 : // start key is less than key, the returned marker will be truncated to key.
254 : // Note that this search-key truncation of the marker's key is not applied to
255 : // the span returned by Span.
256 : //
257 : // NB: In accordance with the base.InternalIterator contract:
258 : //
259 : // i.lower ≤ key
260 : func (i *InterleavingIter) SeekGE(
261 : key []byte, flags base.SeekGEFlags,
262 1 : ) (*base.InternalKey, base.LazyValue) {
263 1 : i.clearMask()
264 1 : i.disablePrefixMode()
265 1 : i.pointKey, i.pointVal = i.pointIter.SeekGE(key, flags)
266 1 :
267 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
268 1 : // already positioned at a span, we might be able to avoid the seek if the
269 1 : // seek key falls within the existing span's bounds.
270 1 : if i.span != nil && i.cmp(key, i.span.End) < 0 && i.cmp(key, i.span.Start) >= 0 {
271 1 : // We're seeking within the existing span's bounds. We still might need
272 1 : // truncate the span to the iterator's bounds.
273 1 : i.checkForwardBound()
274 1 : i.savedKeyspan()
275 1 : } else {
276 1 : i.keyspanSeekGE(key, nil /* prefix */)
277 1 : }
278 :
279 1 : i.dir = +1
280 1 : i.computeSmallestPos()
281 1 : return i.yieldPosition(key, i.nextPos)
282 : }
283 :
284 : // SeekPrefixGE implements (base.InternalIterator).SeekPrefixGE.
285 : //
286 : // If there exists a span with a start key ≤ the first matching point key,
287 : // SeekPrefixGE will return a synthetic span marker key for the span. If this
288 : // span's start key is less than key, the returned marker will be truncated to
289 : // key. Note that this search-key truncation of the marker's key is not applied
290 : // to the span returned by Span.
291 : //
292 : // NB: In accordance with the base.InternalIterator contract:
293 : //
294 : // i.lower ≤ key
295 : func (i *InterleavingIter) SeekPrefixGE(
296 : prefix, key []byte, flags base.SeekGEFlags,
297 1 : ) (*base.InternalKey, base.LazyValue) {
298 1 : i.clearMask()
299 1 : i.prefix = prefix
300 1 : i.pointKey, i.pointVal = i.pointIter.SeekPrefixGE(prefix, key, flags)
301 1 :
302 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
303 1 : // already positioned at a span, we might be able to avoid the seek if the
304 1 : // entire seek prefix key falls within the existing span's bounds.
305 1 : //
306 1 : // During a SeekPrefixGE, Pebble defragments range keys within the bounds of
307 1 : // the prefix. For example, a SeekPrefixGE('c', 'c@8') must defragment the
308 1 : // any overlapping range keys within the bounds of [c,c\00).
309 1 : //
310 1 : // If range keys are fragmented within a prefix (eg, because a version
311 1 : // within a prefix was chosen as an sstable boundary), then it's possible
312 1 : // the seek key falls into the current i.span, but the current i.span does
313 1 : // not wholly cover the seek prefix.
314 1 : //
315 1 : // For example, a SeekPrefixGE('d@5') may only defragment a range key to
316 1 : // the bounds of [c@2,e). A subsequent SeekPrefixGE('c@0') must re-seek the
317 1 : // keyspan iterator, because although 'c@0' is contained within [c@2,e), the
318 1 : // full span of the prefix is not.
319 1 : //
320 1 : // Similarly, a SeekPrefixGE('a@3') may only defragment a range key to the
321 1 : // bounds [a,c@8). A subsequent SeekPrefixGE('c@10') must re-seek the
322 1 : // keyspan iterator, because although 'c@10' is contained within [a,c@8),
323 1 : // the full span of the prefix is not.
324 1 : seekKeyspanIter := true
325 1 : if i.span != nil && i.cmp(prefix, i.span.Start) >= 0 {
326 1 : if ei := i.comparer.Split(i.span.End); i.cmp(prefix, i.span.End[:ei]) < 0 {
327 1 : // We're seeking within the existing span's bounds. We still might need
328 1 : // truncate the span to the iterator's bounds.
329 1 : i.checkForwardBound()
330 1 : i.savedKeyspan()
331 1 : seekKeyspanIter = false
332 1 : }
333 : }
334 1 : if seekKeyspanIter {
335 1 : i.keyspanSeekGE(key, prefix)
336 1 : }
337 :
338 1 : i.dir = +1
339 1 : i.computeSmallestPos()
340 1 : return i.yieldPosition(key, i.nextPos)
341 : }
342 :
343 : // SeekLT implements (base.InternalIterator).SeekLT.
344 : func (i *InterleavingIter) SeekLT(
345 : key []byte, flags base.SeekLTFlags,
346 1 : ) (*base.InternalKey, base.LazyValue) {
347 1 : i.clearMask()
348 1 : i.disablePrefixMode()
349 1 : i.pointKey, i.pointVal = i.pointIter.SeekLT(key, flags)
350 1 :
351 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
352 1 : // already positioned at a span, we might be able to avoid the seek if the
353 1 : // seek key falls within the existing span's bounds.
354 1 : if i.span != nil && i.cmp(key, i.span.Start) > 0 && i.cmp(key, i.span.End) < 0 {
355 1 : // We're seeking within the existing span's bounds. We still might need
356 1 : // truncate the span to the iterator's bounds.
357 1 : i.checkBackwardBound()
358 1 : // The span's start key is still not guaranteed to be less than key,
359 1 : // because of the bounds enforcement. Consider the following example:
360 1 : //
361 1 : // Bounds are set to [d,e). The user performs a SeekLT(d). The
362 1 : // FragmentIterator.SeekLT lands on a span [b,f). This span has a start
363 1 : // key less than d, as expected. Above, checkBackwardBound truncates the
364 1 : // span to match the iterator's current bounds, modifying the span to
365 1 : // [d,e), which does not overlap the search space of [-∞, d).
366 1 : //
367 1 : // This problem is a consequence of the SeekLT's exclusive search key
368 1 : // and the fact that we don't perform bounds truncation at every leaf
369 1 : // iterator.
370 1 : if i.span != nil && i.truncated && i.cmp(i.truncatedSpan.Start, key) >= 0 {
371 1 : i.span = nil
372 1 : }
373 1 : i.savedKeyspan()
374 1 : } else {
375 1 : i.keyspanSeekLT(key)
376 1 : }
377 :
378 1 : i.dir = -1
379 1 : i.computeLargestPos()
380 1 : return i.yieldPosition(i.lower, i.prevPos)
381 : }
382 :
383 : // First implements (base.InternalIterator).First.
384 1 : func (i *InterleavingIter) First() (*base.InternalKey, base.LazyValue) {
385 1 : i.clearMask()
386 1 : i.disablePrefixMode()
387 1 : i.pointKey, i.pointVal = i.pointIter.First()
388 1 : i.span = i.keyspanIter.First()
389 1 : i.checkForwardBound()
390 1 : i.savedKeyspan()
391 1 : i.dir = +1
392 1 : i.computeSmallestPos()
393 1 : return i.yieldPosition(i.lower, i.nextPos)
394 1 : }
395 :
396 : // Last implements (base.InternalIterator).Last.
397 1 : func (i *InterleavingIter) Last() (*base.InternalKey, base.LazyValue) {
398 1 : i.clearMask()
399 1 : i.disablePrefixMode()
400 1 : i.pointKey, i.pointVal = i.pointIter.Last()
401 1 : i.span = i.keyspanIter.Last()
402 1 : i.checkBackwardBound()
403 1 : i.savedKeyspan()
404 1 : i.dir = -1
405 1 : i.computeLargestPos()
406 1 : return i.yieldPosition(i.lower, i.prevPos)
407 1 : }
408 :
409 : // Next implements (base.InternalIterator).Next.
410 1 : func (i *InterleavingIter) Next() (*base.InternalKey, base.LazyValue) {
411 1 : if i.dir == -1 {
412 1 : // Switching directions.
413 1 : i.dir = +1
414 1 :
415 1 : if i.mask != nil {
416 1 : // Clear the mask while we reposition the point iterator. While
417 1 : // switching directions, we may move the point iterator outside of
418 1 : // i.span's bounds.
419 1 : i.clearMask()
420 1 : }
421 :
422 : // When switching directions, iterator state corresponding to the
423 : // current iterator position (as indicated by i.pos) is already correct.
424 : // However any state that has yet to be interleaved describes a position
425 : // behind the current iterator position and needs to be updated to
426 : // describe the position ahead of the current iterator position.
427 1 : switch i.pos {
428 0 : case posExhausted:
429 : // Nothing to do. The below nextPos call will move both the point
430 : // key and span to their next positions and return
431 : // MIN(point,s.Start).
432 1 : case posPointKey:
433 1 : // If we're currently on a point key, the below nextPos will
434 1 : // correctly Next the point key iterator to the next point key.
435 1 : // Do we need to move the span forwards? If the current span lies
436 1 : // entirely behind the current key (!i.withinSpan), then we
437 1 : // need to move it to the first span in the forward direction.
438 1 : if !i.withinSpan {
439 1 : i.span = i.keyspanIter.Next()
440 1 : i.checkForwardBound()
441 1 : i.savedKeyspan()
442 1 : }
443 1 : case posKeyspanStart:
444 1 : i.withinSpan = true
445 1 : // Since we're positioned on a Span, the pointIter is positioned
446 1 : // entirely behind the current iterator position. Reposition it
447 1 : // ahead of the current iterator position.
448 1 : i.pointKey, i.pointVal = i.pointIter.Next()
449 0 : case posKeyspanEnd:
450 0 : // Since we're positioned on a Span, the pointIter is positioned
451 0 : // entirely behind of the current iterator position. Reposition it
452 0 : // ahead the current iterator position.
453 0 : i.pointKey, i.pointVal = i.pointIter.Next()
454 : }
455 : // Fallthrough to calling i.nextPos.
456 : }
457 1 : i.nextPos()
458 1 : return i.yieldPosition(i.lower, i.nextPos)
459 : }
460 :
461 : // NextPrefix implements (base.InternalIterator).NextPrefix.
462 1 : func (i *InterleavingIter) NextPrefix(succKey []byte) (*base.InternalKey, base.LazyValue) {
463 1 : if i.dir == -1 {
464 0 : panic("pebble: cannot switch directions with NextPrefix")
465 : }
466 :
467 1 : switch i.pos {
468 0 : case posExhausted:
469 0 : return nil, base.LazyValue{}
470 1 : case posPointKey:
471 1 : i.pointKey, i.pointVal = i.pointIter.NextPrefix(succKey)
472 1 : if i.withinSpan {
473 1 : if i.pointKey == nil || i.cmp(i.span.End, i.pointKey.UserKey) <= 0 {
474 1 : i.pos = posKeyspanEnd
475 1 : } else {
476 1 : i.pos = posPointKey
477 1 : }
478 1 : } else {
479 1 : i.computeSmallestPos()
480 1 : }
481 0 : case posKeyspanStart, posKeyspanEnd:
482 0 : i.nextPos()
483 : }
484 1 : return i.yieldPosition(i.lower, i.nextPos)
485 : }
486 :
487 : // Prev implements (base.InternalIterator).Prev.
488 1 : func (i *InterleavingIter) Prev() (*base.InternalKey, base.LazyValue) {
489 1 : if i.dir == +1 {
490 1 : // Switching directions.
491 1 : i.dir = -1
492 1 :
493 1 : if i.mask != nil {
494 1 : // Clear the mask while we reposition the point iterator. While
495 1 : // switching directions, we may move the point iterator outside of
496 1 : // i.span's bounds.
497 1 : i.clearMask()
498 1 : }
499 :
500 : // When switching directions, iterator state corresponding to the
501 : // current iterator position (as indicated by i.pos) is already correct.
502 : // However any state that has yet to be interleaved describes a position
503 : // ahead of the current iterator position and needs to be updated to
504 : // describe the position behind the current iterator position.
505 1 : switch i.pos {
506 0 : case posExhausted:
507 : // Nothing to do. The below prevPos call will move both the point
508 : // key and span to previous positions and return MAX(point, s.End).
509 1 : case posPointKey:
510 1 : // If we're currently on a point key, the point iterator is in the
511 1 : // right place and the call to prevPos will correctly Prev the point
512 1 : // key iterator to the previous point key. Do we need to move the
513 1 : // span backwards? If the current span lies entirely ahead of the
514 1 : // current key (!i.withinSpan), then we need to move it to the first
515 1 : // span in the reverse direction.
516 1 : if !i.withinSpan {
517 1 : i.span = i.keyspanIter.Prev()
518 1 : i.checkBackwardBound()
519 1 : i.savedKeyspan()
520 1 : }
521 1 : case posKeyspanStart:
522 1 : // Since we're positioned on a Span, the pointIter is positioned
523 1 : // entirely ahead of the current iterator position. Reposition it
524 1 : // behind the current iterator position.
525 1 : i.pointKey, i.pointVal = i.pointIter.Prev()
526 1 : // Without considering truncation of spans to seek keys, the keyspan
527 1 : // iterator is already in the right place. But consider span [a, z)
528 1 : // and this sequence of iterator calls:
529 1 : //
530 1 : // SeekGE('c') = c.RANGEKEYSET#72057594037927935
531 1 : // Prev() = a.RANGEKEYSET#72057594037927935
532 1 : //
533 1 : // If the current span's start key was last surfaced truncated due
534 1 : // to a SeekGE or SeekPrefixGE call, then it's still relevant in the
535 1 : // reverse direction with an untruncated start key.
536 1 : if i.spanMarkerTruncated {
537 0 : // When we fallthrough to calling prevPos, we want to move to
538 0 : // MAX(point, span.Start). We cheat here by claiming we're
539 0 : // currently on the end boundary, so that we'll move on to the
540 0 : // untruncated start key if necessary.
541 0 : i.pos = posKeyspanEnd
542 0 : }
543 0 : case posKeyspanEnd:
544 0 : // Since we're positioned on a Span, the pointIter is positioned
545 0 : // entirely ahead of the current iterator position. Reposition it
546 0 : // behind the current iterator position.
547 0 : i.pointKey, i.pointVal = i.pointIter.Prev()
548 : }
549 :
550 1 : if i.spanMarkerTruncated {
551 1 : // Save the keyspan again to clear truncation.
552 1 : i.savedKeyspan()
553 1 : }
554 : // Fallthrough to calling i.prevPos.
555 : }
556 1 : i.prevPos()
557 1 : return i.yieldPosition(i.lower, i.prevPos)
558 : }
559 :
560 : // computeSmallestPos sets i.{pos,withinSpan} to:
561 : //
562 : // MIN(i.pointKey, i.span.Start)
563 1 : func (i *InterleavingIter) computeSmallestPos() {
564 1 : if i.span != nil && (i.pointKey == nil || i.cmp(i.startKey(), i.pointKey.UserKey) <= 0) {
565 1 : i.withinSpan = true
566 1 : i.pos = posKeyspanStart
567 1 : return
568 1 : }
569 1 : i.withinSpan = false
570 1 : if i.pointKey != nil {
571 1 : i.pos = posPointKey
572 1 : return
573 1 : }
574 1 : i.pos = posExhausted
575 : }
576 :
577 : // computeLargestPos sets i.{pos,withinSpan} to:
578 : //
579 : // MAX(i.pointKey, i.span.End)
580 1 : func (i *InterleavingIter) computeLargestPos() {
581 1 : if i.span != nil && (i.pointKey == nil || i.cmp(i.span.End, i.pointKey.UserKey) > 0) {
582 1 : i.withinSpan = true
583 1 : i.pos = posKeyspanEnd
584 1 : return
585 1 : }
586 1 : i.withinSpan = false
587 1 : if i.pointKey != nil {
588 1 : i.pos = posPointKey
589 1 : return
590 1 : }
591 1 : i.pos = posExhausted
592 : }
593 :
594 : // nextPos advances the iterator one position in the forward direction.
595 1 : func (i *InterleavingIter) nextPos() {
596 1 : switch i.pos {
597 0 : case posExhausted:
598 0 : i.pointKey, i.pointVal = i.pointIter.Next()
599 0 : i.span = i.keyspanIter.Next()
600 0 : i.checkForwardBound()
601 0 : i.savedKeyspan()
602 0 : i.computeSmallestPos()
603 1 : case posPointKey:
604 1 : i.pointKey, i.pointVal = i.pointIter.Next()
605 1 : // If we're not currently within the span, we want to chose the
606 1 : // MIN(pointKey,span.Start), which is exactly the calculation performed
607 1 : // by computeSmallestPos.
608 1 : if !i.withinSpan {
609 1 : i.computeSmallestPos()
610 1 : return
611 1 : }
612 : // i.withinSpan=true
613 : // Since we previously were within the span, we want to choose the
614 : // MIN(pointKey,span.End).
615 1 : switch {
616 0 : case i.span == nil:
617 0 : panic("i.withinSpan=true and i.span=nil")
618 1 : case i.pointKey == nil:
619 1 : // Since i.withinSpan=true, we step onto the end boundary of the
620 1 : // keyspan.
621 1 : i.pos = posKeyspanEnd
622 1 : default:
623 1 : // i.withinSpan && i.pointKey != nil && i.span != nil
624 1 : if i.cmp(i.span.End, i.pointKey.UserKey) <= 0 {
625 1 : i.pos = posKeyspanEnd
626 1 : } else {
627 1 : i.pos = posPointKey
628 1 : }
629 : }
630 1 : case posKeyspanStart:
631 1 : // Either a point key or the span's end key comes next.
632 1 : if i.pointKey != nil && i.cmp(i.pointKey.UserKey, i.span.End) < 0 {
633 1 : i.pos = posPointKey
634 1 : } else {
635 1 : i.pos = posKeyspanEnd
636 1 : }
637 1 : case posKeyspanEnd:
638 1 : i.span = i.keyspanIter.Next()
639 1 : i.checkForwardBound()
640 1 : i.savedKeyspan()
641 1 : i.computeSmallestPos()
642 0 : default:
643 0 : panic(fmt.Sprintf("unexpected pos=%d\n", i.pos))
644 : }
645 : }
646 :
647 : // prevPos advances the iterator one position in the reverse direction.
648 1 : func (i *InterleavingIter) prevPos() {
649 1 : switch i.pos {
650 0 : case posExhausted:
651 0 : i.pointKey, i.pointVal = i.pointIter.Prev()
652 0 : i.span = i.keyspanIter.Prev()
653 0 : i.checkBackwardBound()
654 0 : i.savedKeyspan()
655 0 : i.computeLargestPos()
656 1 : case posPointKey:
657 1 : i.pointKey, i.pointVal = i.pointIter.Prev()
658 1 : // If we're not currently covered by the span, we want to chose the
659 1 : // MAX(pointKey,span.End), which is exactly the calculation performed
660 1 : // by computeLargestPos.
661 1 : if !i.withinSpan {
662 1 : i.computeLargestPos()
663 1 : return
664 1 : }
665 1 : switch {
666 0 : case i.span == nil:
667 0 : panic("withinSpan=true, but i.span == nil")
668 1 : case i.pointKey == nil:
669 1 : i.pos = posKeyspanEnd
670 1 : default:
671 1 : // i.withinSpan && i.pointKey != nil && i.span != nil
672 1 : if i.cmp(i.span.Start, i.pointKey.UserKey) > 0 {
673 1 : i.pos = posKeyspanStart
674 1 : } else {
675 1 : i.pos = posPointKey
676 1 : }
677 : }
678 1 : case posKeyspanStart:
679 1 : i.span = i.keyspanIter.Prev()
680 1 : i.checkBackwardBound()
681 1 : i.savedKeyspan()
682 1 : i.computeLargestPos()
683 1 : case posKeyspanEnd:
684 1 : // Either a point key or the span's start key is previous.
685 1 : if i.pointKey != nil && i.cmp(i.pointKey.UserKey, i.span.Start) >= 0 {
686 1 : i.pos = posPointKey
687 1 : } else {
688 1 : i.pos = posKeyspanStart
689 1 : }
690 0 : default:
691 0 : panic(fmt.Sprintf("unexpected pos=%d\n", i.pos))
692 : }
693 : }
694 :
695 : func (i *InterleavingIter) yieldPosition(
696 : lowerBound []byte, advance func(),
697 1 : ) (*base.InternalKey, base.LazyValue) {
698 1 : // This loop returns the first visible position in the current iteration
699 1 : // direction. Some positions are not visible and skipped. For example, if
700 1 : // masking is enabled and the iterator is positioned over a masked point
701 1 : // key, this loop skips the position. If a span's start key should be
702 1 : // interleaved next, but the span is empty, the loop continues to the next
703 1 : // key. Currently, span end keys are also always skipped, and are used only
704 1 : // for maintaining internal state.
705 1 : for {
706 1 : switch i.pos {
707 1 : case posExhausted:
708 1 : return i.yieldNil()
709 1 : case posPointKey:
710 1 : if i.pointKey == nil {
711 0 : panic("i.pointKey is nil")
712 : }
713 :
714 1 : if i.mask != nil {
715 1 : i.maybeUpdateMask()
716 1 : if i.withinSpan && i.mask.SkipPoint(i.pointKey.UserKey) {
717 1 : // The span covers the point key. If a SkipPoint hook is
718 1 : // configured, ask it if we should skip this point key.
719 1 : if i.prefix != nil {
720 1 : // During prefix-iteration node, once a point is masked,
721 1 : // all subsequent keys with the same prefix must also be
722 1 : // masked according to the key ordering. We can stop and
723 1 : // return nil.
724 1 : //
725 1 : // NB: The above is not just an optimization. During
726 1 : // prefix-iteration mode, the internal iterator contract
727 1 : // prohibits us from Next-ing beyond the first key
728 1 : // beyond the iteration prefix. If we didn't already
729 1 : // stop early, we would need to check if this masked
730 1 : // point is already beyond the prefix.
731 1 : return i.yieldNil()
732 1 : }
733 : // TODO(jackson): If we thread a base.Comparer through to
734 : // InterleavingIter so that we have access to
735 : // ImmediateSuccessor, we could use NextPrefix. We'd need to
736 : // tweak the SpanMask interface slightly.
737 :
738 : // Advance beyond the masked point key.
739 1 : advance()
740 1 : continue
741 : }
742 : }
743 1 : return i.yieldPointKey()
744 1 : case posKeyspanEnd:
745 1 : // Don't interleave end keys; just advance.
746 1 : advance()
747 1 : continue
748 1 : case posKeyspanStart:
749 1 : // Don't interleave an empty span.
750 1 : if i.span.Empty() {
751 1 : advance()
752 1 : continue
753 : }
754 1 : return i.yieldSyntheticSpanMarker(lowerBound)
755 0 : default:
756 0 : panic(fmt.Sprintf("unexpected interleavePos=%d", i.pos))
757 : }
758 : }
759 : }
760 :
761 : // keyspanSeekGE seeks the keyspan iterator to the first span covering a key ≥ k.
762 1 : func (i *InterleavingIter) keyspanSeekGE(k []byte, prefix []byte) {
763 1 : i.span = i.keyspanIter.SeekGE(k)
764 1 : i.checkForwardBound()
765 1 : i.savedKeyspan()
766 1 : }
767 :
768 : // keyspanSeekLT seeks the keyspan iterator to the last span covering a key < k.
769 1 : func (i *InterleavingIter) keyspanSeekLT(k []byte) {
770 1 : i.span = i.keyspanIter.SeekLT(k)
771 1 : i.checkBackwardBound()
772 1 : // The current span's start key is not guaranteed to be less than key,
773 1 : // because of the bounds enforcement. Consider the following example:
774 1 : //
775 1 : // Bounds are set to [d,e). The user performs a SeekLT(d). The
776 1 : // FragmentIterator.SeekLT lands on a span [b,f). This span has a start key
777 1 : // less than d, as expected. Above, checkBackwardBound truncates the span to
778 1 : // match the iterator's current bounds, modifying the span to [d,e), which
779 1 : // does not overlap the search space of [-∞, d).
780 1 : //
781 1 : // This problem is a consequence of the SeekLT's exclusive search key and
782 1 : // the fact that we don't perform bounds truncation at every leaf iterator.
783 1 : if i.span != nil && i.truncated && i.cmp(i.truncatedSpan.Start, k) >= 0 {
784 1 : i.span = nil
785 1 : }
786 1 : i.savedKeyspan()
787 : }
788 :
789 1 : func (i *InterleavingIter) checkForwardBound() {
790 1 : i.truncated = false
791 1 : i.truncatedSpan = Span{}
792 1 : if i.span == nil {
793 1 : return
794 1 : }
795 : // Check the upper bound if we have one.
796 1 : if i.upper != nil && i.cmp(i.span.Start, i.upper) >= 0 {
797 0 : i.span = nil
798 0 : return
799 0 : }
800 :
801 : // TODO(jackson): The key comparisons below truncate bounds whenever the
802 : // keyspan iterator is repositioned. We could perform this lazily, and do it
803 : // the first time the user actually asks for this span's bounds in
804 : // SpanBounds. This would reduce work in the case where there's no span
805 : // covering the point and the keyspan iterator is non-empty.
806 :
807 : // NB: These truncations don't require setting `keyspanMarkerTruncated`:
808 : // That flag only applies to truncated span marker keys.
809 1 : if i.lower != nil && i.cmp(i.span.Start, i.lower) < 0 {
810 1 : i.truncated = true
811 1 : i.truncatedSpan = *i.span
812 1 : i.truncatedSpan.Start = i.lower
813 1 : }
814 1 : if i.upper != nil && i.cmp(i.upper, i.span.End) < 0 {
815 1 : if !i.truncated {
816 1 : i.truncated = true
817 1 : i.truncatedSpan = *i.span
818 1 : }
819 1 : i.truncatedSpan.End = i.upper
820 : }
821 : // If this is a part of a SeekPrefixGE call, we may also need to truncate to
822 : // the prefix's bounds.
823 1 : if i.prefix != nil {
824 1 : if !i.truncated {
825 1 : i.truncated = true
826 1 : i.truncatedSpan = *i.span
827 1 : }
828 1 : if i.cmp(i.prefix, i.truncatedSpan.Start) > 0 {
829 1 : i.truncatedSpan.Start = i.prefix
830 1 : }
831 1 : i.nextPrefixBuf = i.comparer.ImmediateSuccessor(i.nextPrefixBuf[:0], i.prefix)
832 1 : if i.truncated && i.cmp(i.nextPrefixBuf, i.truncatedSpan.End) < 0 {
833 1 : i.truncatedSpan.End = i.nextPrefixBuf
834 1 : }
835 : }
836 :
837 1 : if i.truncated && i.comparer.Equal(i.truncatedSpan.Start, i.truncatedSpan.End) {
838 1 : i.span = nil
839 1 : }
840 : }
841 :
842 1 : func (i *InterleavingIter) checkBackwardBound() {
843 1 : i.truncated = false
844 1 : i.truncatedSpan = Span{}
845 1 : if i.span == nil {
846 1 : return
847 1 : }
848 : // Check the lower bound if we have one.
849 1 : if i.lower != nil && i.cmp(i.span.End, i.lower) <= 0 {
850 0 : i.span = nil
851 0 : return
852 0 : }
853 :
854 : // TODO(jackson): The key comparisons below truncate bounds whenever the
855 : // keyspan iterator is repositioned. We could perform this lazily, and do it
856 : // the first time the user actually asks for this span's bounds in
857 : // SpanBounds. This would reduce work in the case where there's no span
858 : // covering the point and the keyspan iterator is non-empty.
859 :
860 : // NB: These truncations don't require setting `keyspanMarkerTruncated`:
861 : // That flag only applies to truncated span marker keys.
862 1 : if i.lower != nil && i.cmp(i.span.Start, i.lower) < 0 {
863 1 : i.truncated = true
864 1 : i.truncatedSpan = *i.span
865 1 : i.truncatedSpan.Start = i.lower
866 1 : }
867 1 : if i.upper != nil && i.cmp(i.upper, i.span.End) < 0 {
868 1 : if !i.truncated {
869 1 : i.truncated = true
870 1 : i.truncatedSpan = *i.span
871 1 : }
872 1 : i.truncatedSpan.End = i.upper
873 : }
874 1 : if i.truncated && i.comparer.Equal(i.truncatedSpan.Start, i.truncatedSpan.End) {
875 1 : i.span = nil
876 1 : }
877 : }
878 :
879 1 : func (i *InterleavingIter) yieldNil() (*base.InternalKey, base.LazyValue) {
880 1 : i.withinSpan = false
881 1 : i.clearMask()
882 1 : return i.verify(nil, base.LazyValue{})
883 1 : }
884 :
885 1 : func (i *InterleavingIter) yieldPointKey() (*base.InternalKey, base.LazyValue) {
886 1 : return i.verify(i.pointKey, i.pointVal)
887 1 : }
888 :
889 : func (i *InterleavingIter) yieldSyntheticSpanMarker(
890 : lowerBound []byte,
891 1 : ) (*base.InternalKey, base.LazyValue) {
892 1 : i.spanMarker.UserKey = i.startKey()
893 1 : i.spanMarker.Trailer = base.MakeTrailer(base.InternalKeySeqNumMax, i.span.Keys[0].Kind())
894 1 :
895 1 : // Truncate the key we return to our lower bound if we have one. Note that
896 1 : // we use the lowerBound function parameter, not i.lower. The lowerBound
897 1 : // argument is guaranteed to be ≥ i.lower. It may be equal to the SetBounds
898 1 : // lower bound, or it could come from a SeekGE or SeekPrefixGE search key.
899 1 : if lowerBound != nil && i.cmp(lowerBound, i.startKey()) > 0 {
900 1 : // Truncating to the lower bound may violate the upper bound if
901 1 : // lowerBound == i.upper. For example, a SeekGE(k) uses k as a lower
902 1 : // bound for truncating a span. The span a-z will be truncated to [k,
903 1 : // z). If i.upper == k, we'd mistakenly try to return a span [k, k), an
904 1 : // invariant violation.
905 1 : if i.comparer.Equal(lowerBound, i.upper) {
906 1 : return i.yieldNil()
907 1 : }
908 :
909 : // If the lowerBound argument came from a SeekGE or SeekPrefixGE
910 : // call, and it may be backed by a user-provided byte slice that is not
911 : // guaranteed to be stable.
912 : //
913 : // If the lowerBound argument is the lower bound set by SetBounds,
914 : // Pebble owns the slice's memory. However, consider two successive
915 : // calls to SetBounds(). The second may overwrite the lower bound.
916 : // Although the external contract requires a seek after a SetBounds,
917 : // Pebble's tests don't always. For this reason and to simplify
918 : // reasoning around lifetimes, always copy the bound into keyBuf when
919 : // truncating.
920 1 : i.keyBuf = append(i.keyBuf[:0], lowerBound...)
921 1 : i.spanMarker.UserKey = i.keyBuf
922 1 : i.spanMarkerTruncated = true
923 : }
924 1 : i.maybeUpdateMask()
925 1 : return i.verify(&i.spanMarker, base.LazyValue{})
926 : }
927 :
928 1 : func (i *InterleavingIter) disablePrefixMode() {
929 1 : if i.prefix != nil {
930 1 : i.prefix = nil
931 1 : // Clear the existing span. It may not hold the true end bound of the
932 1 : // underlying span.
933 1 : i.span = nil
934 1 : }
935 : }
936 :
937 : func (i *InterleavingIter) verify(
938 : k *base.InternalKey, v base.LazyValue,
939 1 : ) (*base.InternalKey, base.LazyValue) {
940 1 : // Wrap the entire function body in the invariants build tag, so that
941 1 : // production builds elide this entire function.
942 1 : if invariants.Enabled {
943 0 : switch {
944 0 : case i.dir == -1 && i.spanMarkerTruncated:
945 0 : panic("pebble: invariant violation: truncated span key in reverse iteration")
946 0 : case k != nil && i.lower != nil && i.cmp(k.UserKey, i.lower) < 0:
947 0 : panic("pebble: invariant violation: key < lower bound")
948 0 : case k != nil && i.upper != nil && i.cmp(k.UserKey, i.upper) >= 0:
949 0 : panic("pebble: invariant violation: key ≥ upper bound")
950 : }
951 : }
952 1 : return k, v
953 : }
954 :
955 1 : func (i *InterleavingIter) savedKeyspan() {
956 1 : i.spanMarkerTruncated = false
957 1 : i.maskSpanChangedCalled = false
958 1 : }
959 :
960 : // updateMask updates the current mask, if a mask is configured and the mask
961 : // hasn't been updated with the current keyspan yet.
962 1 : func (i *InterleavingIter) maybeUpdateMask() {
963 1 : switch {
964 1 : case i.mask == nil, i.maskSpanChangedCalled:
965 1 : return
966 1 : case !i.withinSpan || i.span.Empty():
967 1 : i.clearMask()
968 1 : case i.truncated:
969 1 : i.mask.SpanChanged(&i.truncatedSpan)
970 1 : i.maskSpanChangedCalled = true
971 1 : default:
972 1 : i.mask.SpanChanged(i.span)
973 1 : i.maskSpanChangedCalled = true
974 : }
975 : }
976 :
977 : // clearMask clears the current mask, if a mask is configured and no mask should
978 : // be active.
979 1 : func (i *InterleavingIter) clearMask() {
980 1 : if i.mask != nil {
981 1 : i.maskSpanChangedCalled = false
982 1 : i.mask.SpanChanged(nil)
983 1 : }
984 : }
985 :
986 1 : func (i *InterleavingIter) startKey() []byte {
987 1 : if i.truncated {
988 1 : return i.truncatedSpan.Start
989 1 : }
990 1 : return i.span.Start
991 : }
992 :
993 : // Span returns the span covering the last key returned, if any. A span key is
994 : // considered to 'cover' a key if the key falls within the span's user key
995 : // bounds. The returned span is owned by the InterleavingIter. The caller is
996 : // responsible for copying if stability is required.
997 : //
998 : // Span will never return an invalid or empty span.
999 1 : func (i *InterleavingIter) Span() *Span {
1000 1 : if !i.withinSpan || len(i.span.Keys) == 0 {
1001 1 : return nil
1002 1 : } else if i.truncated {
1003 1 : return &i.truncatedSpan
1004 1 : }
1005 1 : return i.span
1006 : }
1007 :
1008 : // SetBounds implements (base.InternalIterator).SetBounds.
1009 1 : func (i *InterleavingIter) SetBounds(lower, upper []byte) {
1010 1 : i.lower, i.upper = lower, upper
1011 1 : i.pointIter.SetBounds(lower, upper)
1012 1 : i.Invalidate()
1013 1 : }
1014 :
1015 : // Invalidate invalidates the interleaving iterator's current position, clearing
1016 : // its state. This prevents optimizations such as reusing the current span on
1017 : // seek.
1018 1 : func (i *InterleavingIter) Invalidate() {
1019 1 : i.span = nil
1020 1 : i.pointKey = nil
1021 1 : i.pointVal = base.LazyValue{}
1022 1 : }
1023 :
1024 : // Error implements (base.InternalIterator).Error.
1025 1 : func (i *InterleavingIter) Error() error {
1026 1 : return firstError(i.pointIter.Error(), i.keyspanIter.Error())
1027 1 : }
1028 :
1029 : // Close implements (base.InternalIterator).Close.
1030 1 : func (i *InterleavingIter) Close() error {
1031 1 : perr := i.pointIter.Close()
1032 1 : rerr := i.keyspanIter.Close()
1033 1 : return firstError(perr, rerr)
1034 1 : }
1035 :
1036 : // String implements (base.InternalIterator).String.
1037 0 : func (i *InterleavingIter) String() string {
1038 0 : return fmt.Sprintf("keyspan-interleaving(%q)", i.pointIter.String())
1039 0 : }
1040 :
1041 1 : func firstError(err0, err1 error) error {
1042 1 : if err0 != nil {
1043 0 : return err0
1044 0 : }
1045 1 : return err1
1046 : }
|
