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 keyspanimpl
6 :
7 : import (
8 : "fmt"
9 :
10 : "github.com/cockroachdb/errors"
11 : "github.com/cockroachdb/pebble/internal/base"
12 : "github.com/cockroachdb/pebble/internal/invariants"
13 : "github.com/cockroachdb/pebble/internal/keyspan"
14 : "github.com/cockroachdb/pebble/internal/manifest"
15 : )
16 :
17 : // TableNewSpanIter creates a new iterator for range key spans for the given
18 : // file.
19 : type TableNewSpanIter func(
20 : file *manifest.FileMetadata, iterOptions keyspan.SpanIterOptions,
21 : ) (keyspan.FragmentIterator, error)
22 :
23 : // LevelIter provides a merged view of spans from sstables in a level.
24 : // It takes advantage of level invariants to only have one sstable span block
25 : // open at one time, opened using the newIter function passed in.
26 : type LevelIter struct {
27 : cmp base.Compare
28 : // Denotes the kind of key the level iterator should read. If the key type
29 : // is KeyTypePoint, the level iterator will read range tombstones (which
30 : // only affect point keys). If the key type is KeyTypeRange, the level
31 : // iterator will read range keys. It is invalid to configure an iterator
32 : // with the KeyTypePointAndRange key type.
33 : //
34 : // If key type is KeyTypePoint, no straddle spans are emitted between files,
35 : // and point key bounds are used to find files instead of range key bounds.
36 : //
37 : // TODO(bilal): Straddle spans can safely be produced in rangedel mode once
38 : // we can guarantee that we will never read sstables in a level that split
39 : // user keys across them. This might be guaranteed in a future release, but
40 : // as of CockroachDB 22.2 it is not guaranteed, so to be safe disable it when
41 : // keyType == KeyTypePoint
42 : keyType manifest.KeyType
43 : // The LSM level this LevelIter is initialized for. Used in logging.
44 : level manifest.Level
45 : // The below fields are used to fill in gaps between adjacent files' range
46 : // key spaces. This is an optimization to avoid unnecessarily loading files
47 : // in cases where range keys are sparse and rare. dir is set by every
48 : // positioning operation, straddleDir is set to dir whenever a straddling
49 : // Span is synthesized and the last positioning operation returned a
50 : // synthesized straddle span.
51 : //
52 : // Note that when a straddle span is initialized, iterFile is modified to
53 : // point to the next file in the straddleDir direction. A change of direction
54 : // on a straddle key therefore necessitates the value of iterFile to be
55 : // reverted.
56 : dir int
57 : straddle keyspan.Span
58 : straddleDir int
59 : // The iter for the current file (iterFile). It is nil under any of the
60 : // following conditions:
61 : // - files.Current() == nil
62 : // - err != nil
63 : // - straddleDir != 0, in which case iterFile is not nil and points to the
64 : // next file (in the straddleDir direction).
65 : // - some other constraint, like the bounds in opts, caused the file at index to not
66 : // be relevant to the iteration.
67 : iter keyspan.FragmentIterator
68 : wrapFn keyspan.WrapFn
69 : // iterFile holds the current file.
70 : // INVARIANT: iterFile = files.Current()
71 : iterFile *manifest.FileMetadata
72 : newIter TableNewSpanIter
73 : files manifest.LevelIterator
74 : err error
75 :
76 : // The options that were passed in.
77 : tableOpts keyspan.SpanIterOptions
78 :
79 : // TODO(bilal): Add InternalIteratorStats.
80 : }
81 :
82 : // LevelIter implements the keyspan.FragmentIterator interface.
83 : var _ keyspan.FragmentIterator = (*LevelIter)(nil)
84 :
85 : // NewLevelIter returns a LevelIter.
86 : func NewLevelIter(
87 : opts keyspan.SpanIterOptions,
88 : cmp base.Compare,
89 : newIter TableNewSpanIter,
90 : files manifest.LevelIterator,
91 : level manifest.Level,
92 : keyType manifest.KeyType,
93 2 : ) *LevelIter {
94 2 : l := &LevelIter{}
95 2 : l.Init(opts, cmp, newIter, files, level, keyType)
96 2 : return l
97 2 : }
98 :
99 : // Init initializes a LevelIter.
100 : func (l *LevelIter) Init(
101 : opts keyspan.SpanIterOptions,
102 : cmp base.Compare,
103 : newIter TableNewSpanIter,
104 : files manifest.LevelIterator,
105 : level manifest.Level,
106 : keyType manifest.KeyType,
107 2 : ) {
108 2 : l.err = nil
109 2 : l.level = level
110 2 : l.tableOpts = opts
111 2 : l.cmp = cmp
112 2 : l.iterFile = nil
113 2 : l.newIter = newIter
114 2 : switch keyType {
115 2 : case manifest.KeyTypePoint:
116 2 : l.keyType = keyType
117 2 : l.files = files.Filter(keyType)
118 2 : case manifest.KeyTypeRange:
119 2 : l.keyType = keyType
120 2 : l.files = files.Filter(keyType)
121 0 : default:
122 0 : panic(fmt.Sprintf("unsupported key type: %v", keyType))
123 : }
124 : }
125 :
126 2 : func (l *LevelIter) findFileGE(key []byte) *manifest.FileMetadata {
127 2 : // Find the earliest file whose largest key is >= key.
128 2 : //
129 2 : // If the earliest file has its largest key == key and that largest key is a
130 2 : // range deletion sentinel, we know that we manufactured this sentinel to convert
131 2 : // the exclusive range deletion end key into an inclusive key (reminder: [start, end)#seqnum
132 2 : // is the form of a range deletion sentinel which can contribute a largest key = end#sentinel).
133 2 : // In this case we don't return this as the earliest file since there is nothing actually
134 2 : // equal to key in it.
135 2 :
136 2 : m := l.files.SeekGE(l.cmp, key)
137 2 : for m != nil {
138 2 : largestKey := m.LargestRangeKey
139 2 : if l.keyType == manifest.KeyTypePoint {
140 2 : largestKey = m.LargestPointKey
141 2 : }
142 2 : if !largestKey.IsExclusiveSentinel() || l.cmp(largestKey.UserKey, key) != 0 {
143 2 : break
144 : }
145 0 : m = l.files.Next()
146 : }
147 2 : return m
148 : }
149 :
150 2 : func (l *LevelIter) findFileLT(key []byte) *manifest.FileMetadata {
151 2 : // Find the last file whose smallest key is < key.
152 2 : return l.files.SeekLT(l.cmp, key)
153 2 : }
154 :
155 : type loadFileReturnIndicator int8
156 :
157 : const (
158 : noFileLoaded loadFileReturnIndicator = iota
159 : fileAlreadyLoaded
160 : newFileLoaded
161 : )
162 :
163 2 : func (l *LevelIter) loadFile(file *manifest.FileMetadata, dir int) loadFileReturnIndicator {
164 2 : indicator := noFileLoaded
165 2 : if l.iterFile == file {
166 2 : if l.err != nil {
167 0 : return noFileLoaded
168 0 : }
169 2 : if l.iter != nil {
170 2 : // We are already at the file, but we would need to check for bounds.
171 2 : // Set indicator accordingly.
172 2 : indicator = fileAlreadyLoaded
173 2 : }
174 : // We were already at file, but don't have an iterator, probably because the file was
175 : // beyond the iteration bounds. It may still be, but it is also possible that the bounds
176 : // have changed. We handle that below.
177 : }
178 :
179 : // Note that LevelIter.Close() can be called multiple times.
180 2 : if indicator != fileAlreadyLoaded {
181 2 : if err := l.Close(); err != nil {
182 0 : return noFileLoaded
183 0 : }
184 : }
185 :
186 2 : l.iterFile = file
187 2 : if file == nil {
188 2 : return noFileLoaded
189 2 : }
190 2 : if indicator != fileAlreadyLoaded {
191 2 : l.iter, l.err = l.newIter(file, l.tableOpts)
192 2 : if l.wrapFn != nil {
193 0 : l.iter = l.wrapFn(l.iter)
194 0 : }
195 2 : l.iter = keyspan.MaybeAssert(l.iter, l.cmp)
196 2 : indicator = newFileLoaded
197 : }
198 2 : if l.err != nil {
199 1 : return noFileLoaded
200 1 : }
201 2 : return indicator
202 : }
203 :
204 : // SeekGE implements keyspan.FragmentIterator.
205 2 : func (l *LevelIter) SeekGE(key []byte) (*keyspan.Span, error) {
206 2 : l.dir = +1
207 2 : l.straddle = keyspan.Span{}
208 2 : l.straddleDir = 0
209 2 : l.err = nil // clear cached iteration error
210 2 :
211 2 : f := l.findFileGE(key)
212 2 : if f != nil && l.keyType == manifest.KeyTypeRange && l.cmp(key, f.SmallestRangeKey.UserKey) < 0 {
213 2 : // Peek at the previous file.
214 2 : prevFile := l.files.Prev()
215 2 : l.files.Next()
216 2 : if prevFile != nil {
217 2 : // We could unconditionally return an empty span between the seek key and
218 2 : // f.SmallestRangeKey, however if this span is to the left of all range
219 2 : // keys on this level, it could lead to inconsistent behaviour in relative
220 2 : // positioning operations. Consider this example, with a b-c range key:
221 2 : //
222 2 : // SeekGE(a) -> a-b:{}
223 2 : // Next() -> b-c{(#5,RANGEKEYSET,@4,foo)}
224 2 : // Prev() -> nil
225 2 : //
226 2 : // Iterators higher up in the iterator stack rely on this sort of relative
227 2 : // positioning consistency.
228 2 : //
229 2 : // TODO(bilal): Investigate ways to be able to return straddle spans in
230 2 : // cases similar to the above, while still retaining correctness.
231 2 : // Return a straddling key instead of loading the file.
232 2 : l.iterFile = f
233 2 : if l.err = l.Close(); l.err != nil {
234 0 : return l.verify(nil, l.err)
235 0 : }
236 2 : l.straddleDir = +1
237 2 : l.straddle = keyspan.Span{
238 2 : Start: prevFile.LargestRangeKey.UserKey,
239 2 : End: f.SmallestRangeKey.UserKey,
240 2 : Keys: nil,
241 2 : }
242 2 : return l.verify(&l.straddle, nil)
243 : }
244 : }
245 2 : loadFileIndicator := l.loadFile(f, +1)
246 2 : if loadFileIndicator == noFileLoaded {
247 2 : return l.verify(nil, l.err)
248 2 : }
249 2 : if span, err := l.iter.SeekGE(key); err != nil {
250 0 : return l.verify(nil, err)
251 2 : } else if span != nil {
252 2 : return l.verify(span, nil)
253 2 : }
254 2 : return l.skipEmptyFileForward()
255 : }
256 :
257 : // SeekLT implements keyspan.FragmentIterator.
258 2 : func (l *LevelIter) SeekLT(key []byte) (*keyspan.Span, error) {
259 2 : l.dir = -1
260 2 : l.straddle = keyspan.Span{}
261 2 : l.straddleDir = 0
262 2 : l.err = nil // clear cached iteration error
263 2 :
264 2 : f := l.findFileLT(key)
265 2 : if f != nil && l.keyType == manifest.KeyTypeRange && l.cmp(f.LargestRangeKey.UserKey, key) < 0 {
266 2 : // Peek at the next file.
267 2 : nextFile := l.files.Next()
268 2 : l.files.Prev()
269 2 : if nextFile != nil {
270 2 : // We could unconditionally return an empty span between f.LargestRangeKey
271 2 : // and the seek key, however if this span is to the right of all range keys
272 2 : // on this level, it could lead to inconsistent behaviour in relative
273 2 : // positioning operations. Consider this example, with a b-c range key:
274 2 : //
275 2 : // SeekLT(d) -> c-d:{}
276 2 : // Prev() -> b-c{(#5,RANGEKEYSET,@4,foo)}
277 2 : // Next() -> nil
278 2 : //
279 2 : // Iterators higher up in the iterator stack rely on this sort of relative
280 2 : // positioning consistency.
281 2 : //
282 2 : // TODO(bilal): Investigate ways to be able to return straddle spans in
283 2 : // cases similar to the above, while still retaining correctness.
284 2 : // Return a straddling key instead of loading the file.
285 2 : l.iterFile = f
286 2 : if l.err = l.Close(); l.err != nil {
287 0 : return l.verify(nil, l.err)
288 0 : }
289 2 : l.straddleDir = -1
290 2 : l.straddle = keyspan.Span{
291 2 : Start: f.LargestRangeKey.UserKey,
292 2 : End: nextFile.SmallestRangeKey.UserKey,
293 2 : Keys: nil,
294 2 : }
295 2 : return l.verify(&l.straddle, nil)
296 : }
297 : }
298 2 : if l.loadFile(f, -1) == noFileLoaded {
299 2 : return l.verify(nil, l.err)
300 2 : }
301 2 : if span, err := l.iter.SeekLT(key); err != nil {
302 0 : return l.verify(nil, err)
303 2 : } else if span != nil {
304 2 : return l.verify(span, nil)
305 2 : }
306 2 : return l.skipEmptyFileBackward()
307 : }
308 :
309 : // First implements keyspan.FragmentIterator.
310 2 : func (l *LevelIter) First() (*keyspan.Span, error) {
311 2 : l.dir = +1
312 2 : l.straddle = keyspan.Span{}
313 2 : l.straddleDir = 0
314 2 : l.err = nil // clear cached iteration error
315 2 :
316 2 : if l.loadFile(l.files.First(), +1) == noFileLoaded {
317 2 : return l.verify(nil, l.err)
318 2 : }
319 2 : if span, err := l.iter.First(); err != nil {
320 0 : return l.verify(nil, err)
321 2 : } else if span != nil {
322 2 : return l.verify(span, nil)
323 2 : }
324 2 : return l.skipEmptyFileForward()
325 : }
326 :
327 : // Last implements keyspan.FragmentIterator.
328 2 : func (l *LevelIter) Last() (*keyspan.Span, error) {
329 2 : l.dir = -1
330 2 : l.straddle = keyspan.Span{}
331 2 : l.straddleDir = 0
332 2 : l.err = nil // clear cached iteration error
333 2 :
334 2 : if l.loadFile(l.files.Last(), -1) == noFileLoaded {
335 2 : return l.verify(nil, l.err)
336 2 : }
337 2 : if span, err := l.iter.Last(); err != nil {
338 0 : return l.verify(nil, err)
339 2 : } else if span != nil {
340 2 : return l.verify(span, nil)
341 2 : }
342 2 : return l.skipEmptyFileBackward()
343 : }
344 :
345 : // Next implements keyspan.FragmentIterator.
346 2 : func (l *LevelIter) Next() (*keyspan.Span, error) {
347 2 : if l.err != nil || (l.iter == nil && l.iterFile == nil && l.dir > 0) {
348 1 : return l.verify(nil, l.err)
349 1 : }
350 2 : if l.iter == nil && l.iterFile == nil {
351 2 : // l.dir <= 0
352 2 : return l.First()
353 2 : }
354 2 : l.dir = +1
355 2 :
356 2 : if l.iter != nil {
357 2 : if span, err := l.iter.Next(); err != nil {
358 0 : return l.verify(nil, err)
359 2 : } else if span != nil {
360 2 : return l.verify(span, nil)
361 2 : }
362 : }
363 2 : return l.skipEmptyFileForward()
364 : }
365 :
366 : // Prev implements keyspan.FragmentIterator.
367 2 : func (l *LevelIter) Prev() (*keyspan.Span, error) {
368 2 : if l.err != nil || (l.iter == nil && l.iterFile == nil && l.dir < 0) {
369 1 : return l.verify(nil, l.err)
370 1 : }
371 2 : if l.iter == nil && l.iterFile == nil {
372 2 : // l.dir >= 0
373 2 : return l.Last()
374 2 : }
375 2 : l.dir = -1
376 2 :
377 2 : if l.iter != nil {
378 2 : if span, err := l.iter.Prev(); err != nil {
379 0 : return nil, err
380 2 : } else if span != nil {
381 2 : return l.verify(span, nil)
382 2 : }
383 : }
384 2 : return l.skipEmptyFileBackward()
385 : }
386 :
387 2 : func (l *LevelIter) skipEmptyFileForward() (*keyspan.Span, error) {
388 2 : if l.straddleDir == 0 && l.keyType == manifest.KeyTypeRange &&
389 2 : l.iterFile != nil && l.iter != nil {
390 2 : // We were at a file that had spans. Check if the next file that has
391 2 : // spans is not directly adjacent to the current file i.e. there is a
392 2 : // gap in the span keyspace between the two files. In that case, synthesize
393 2 : // a "straddle span" in l.straddle and return that.
394 2 : //
395 2 : // Straddle spans are not created in rangedel mode.
396 2 : if l.err = l.Close(); l.err != nil {
397 0 : return l.verify(nil, l.err)
398 0 : }
399 2 : startKey := l.iterFile.LargestRangeKey.UserKey
400 2 : // Resetting l.iterFile without loading the file into l.iter is okay and
401 2 : // does not change the logic in loadFile() as long as l.iter is also nil;
402 2 : // which it should be due to the Close() call above.
403 2 : l.iterFile = l.files.Next()
404 2 : if l.iterFile == nil {
405 2 : return l.verify(nil, nil)
406 2 : }
407 2 : endKey := l.iterFile.SmallestRangeKey.UserKey
408 2 : if l.cmp(startKey, endKey) < 0 {
409 2 : // There is a gap between the two files. Synthesize a straddling span
410 2 : // to avoid unnecessarily loading the next file.
411 2 : l.straddle = keyspan.Span{
412 2 : Start: startKey,
413 2 : End: endKey,
414 2 : }
415 2 : l.straddleDir = +1
416 2 : return l.verify(&l.straddle, nil)
417 2 : }
418 2 : } else if l.straddleDir < 0 {
419 2 : // We were at a straddle key, but are now changing directions. l.iterFile
420 2 : // was already moved backward by skipEmptyFileBackward, so advance it
421 2 : // forward.
422 2 : l.iterFile = l.files.Next()
423 2 : }
424 2 : l.straddle = keyspan.Span{}
425 2 : l.straddleDir = 0
426 2 : var span *keyspan.Span
427 2 : for span.Empty() {
428 2 : fileToLoad := l.iterFile
429 2 : if l.keyType == manifest.KeyTypePoint {
430 2 : // We haven't iterated to the next file yet if we're in point key
431 2 : // (rangedel) mode.
432 2 : fileToLoad = l.files.Next()
433 2 : }
434 2 : if l.loadFile(fileToLoad, +1) == noFileLoaded {
435 2 : return l.verify(nil, l.err)
436 2 : }
437 2 : span, l.err = l.iter.First()
438 2 : if l.err != nil {
439 0 : return l.verify(nil, l.err)
440 0 : }
441 : // In rangedel mode, we can expect to get empty files that we'd need to
442 : // skip over, but not in range key mode.
443 2 : if l.keyType == manifest.KeyTypeRange {
444 2 : break
445 : }
446 : }
447 2 : return l.verify(span, l.err)
448 : }
449 :
450 2 : func (l *LevelIter) skipEmptyFileBackward() (*keyspan.Span, error) {
451 2 : // We were at a file that had spans. Check if the previous file that has
452 2 : // spans is not directly adjacent to the current file i.e. there is a
453 2 : // gap in the span keyspace between the two files. In that case, synthesize
454 2 : // a "straddle span" in l.straddle and return that.
455 2 : //
456 2 : // Straddle spans are not created in rangedel mode.
457 2 : if l.straddleDir == 0 && l.keyType == manifest.KeyTypeRange &&
458 2 : l.iterFile != nil && l.iter != nil {
459 2 : if l.err = l.Close(); l.err != nil {
460 0 : return l.verify(nil, l.err)
461 0 : }
462 2 : endKey := l.iterFile.SmallestRangeKey.UserKey
463 2 : // Resetting l.iterFile without loading the file into l.iter is okay and
464 2 : // does not change the logic in loadFile() as long as l.iter is also nil;
465 2 : // which it should be due to the Close() call above.
466 2 : l.iterFile = l.files.Prev()
467 2 : if l.iterFile == nil {
468 2 : return l.verify(nil, nil)
469 2 : }
470 2 : startKey := l.iterFile.LargestRangeKey.UserKey
471 2 : if l.cmp(startKey, endKey) < 0 {
472 2 : // There is a gap between the two files. Synthesize a straddling span
473 2 : // to avoid unnecessarily loading the next file.
474 2 : l.straddle = keyspan.Span{
475 2 : Start: startKey,
476 2 : End: endKey,
477 2 : }
478 2 : l.straddleDir = -1
479 2 : return l.verify(&l.straddle, nil)
480 2 : }
481 2 : } else if l.straddleDir > 0 {
482 2 : // We were at a straddle key, but are now changing directions. l.iterFile
483 2 : // was already advanced forward by skipEmptyFileForward, so move it
484 2 : // backward.
485 2 : l.iterFile = l.files.Prev()
486 2 : }
487 2 : l.straddle = keyspan.Span{}
488 2 : l.straddleDir = 0
489 2 : var span *keyspan.Span
490 2 : for span.Empty() {
491 2 : fileToLoad := l.iterFile
492 2 : if l.keyType == manifest.KeyTypePoint {
493 2 : fileToLoad = l.files.Prev()
494 2 : }
495 2 : if l.loadFile(fileToLoad, -1) == noFileLoaded {
496 2 : return l.verify(nil, l.err)
497 2 : }
498 2 : span, l.err = l.iter.Last()
499 2 : if l.err != nil {
500 0 : return l.verify(span, l.err)
501 0 : }
502 : // In rangedel mode, we can expect to get empty files that we'd need to
503 : // skip over, but not in range key mode as the filter on the FileMetadata
504 : // should guarantee we always get a non-empty file.
505 2 : if l.keyType == manifest.KeyTypeRange {
506 2 : break
507 : }
508 : }
509 2 : return l.verify(span, l.err)
510 : }
511 :
512 : // verify is invoked whenever a span is returned from an iterator positioning
513 : // method to a caller. During invariant builds, it asserts invariants to the
514 : // caller.
515 2 : func (l *LevelIter) verify(s *keyspan.Span, err error) (*keyspan.Span, error) {
516 2 : // NB: Do not add any logic outside the invariants.Enabled conditional to
517 2 : // ensure that verify is always compiled away in production builds.
518 2 : if invariants.Enabled {
519 2 : if err != l.err {
520 0 : panic(errors.AssertionFailedf("LevelIter.err (%v) != returned error (%v)", l.err, err))
521 : }
522 2 : if err != nil && s != nil {
523 0 : panic(errors.AssertionFailedf("non-nil error returned alongside non-nil span"))
524 : }
525 2 : if f := l.files.Current(); f != l.iterFile {
526 0 : panic(fmt.Sprintf("LevelIter.files.Current (%s) and l.iterFile (%s) diverged",
527 0 : f, l.iterFile))
528 : }
529 : }
530 2 : return s, err
531 : }
532 :
533 : // Error implements keyspan.FragmentIterator.
534 0 : func (l *LevelIter) Error() error {
535 0 : return l.err
536 0 : }
537 :
538 : // Close implements keyspan.FragmentIterator.
539 2 : func (l *LevelIter) Close() error {
540 2 : if l.iter != nil {
541 2 : l.err = l.iter.Close()
542 2 : l.iter = nil
543 2 : }
544 2 : return l.err
545 : }
546 :
547 : // String implements keyspan.FragmentIterator.
548 0 : func (l *LevelIter) String() string {
549 0 : if l.iterFile != nil {
550 0 : return fmt.Sprintf("%s: fileNum=%s", l.level, l.iterFile.FileNum)
551 0 : }
552 0 : return fmt.Sprintf("%s: fileNum=<nil>", l.level)
553 : }
554 :
555 : // WrapChildren implements FragmentIterator.
556 0 : func (l *LevelIter) WrapChildren(wrap keyspan.WrapFn) {
557 0 : l.iter = wrap(l.iter)
558 0 : l.wrapFn = wrap
559 0 : }
|
