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 1 : ) *LevelIter {
94 1 : l := &LevelIter{}
95 1 : l.Init(opts, cmp, newIter, files, level, keyType)
96 1 : return l
97 1 : }
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 1 : ) {
108 1 : l.err = nil
109 1 : l.level = level
110 1 : l.tableOpts = opts
111 1 : l.cmp = cmp
112 1 : l.iterFile = nil
113 1 : l.newIter = newIter
114 1 : switch keyType {
115 1 : case manifest.KeyTypePoint:
116 1 : l.keyType = keyType
117 1 : l.files = files.Filter(keyType)
118 1 : case manifest.KeyTypeRange:
119 1 : l.keyType = keyType
120 1 : l.files = files.Filter(keyType)
121 0 : default:
122 0 : panic(fmt.Sprintf("unsupported key type: %v", keyType))
123 : }
124 : }
125 :
126 : type loadFileReturnIndicator int8
127 :
128 : const (
129 : noFileLoaded loadFileReturnIndicator = iota
130 : fileAlreadyLoaded
131 : newFileLoaded
132 : )
133 :
134 1 : func (l *LevelIter) loadFile(file *manifest.FileMetadata, dir int) loadFileReturnIndicator {
135 1 : indicator := noFileLoaded
136 1 : if l.iterFile == file {
137 1 : if l.err != nil {
138 0 : return noFileLoaded
139 0 : }
140 1 : if l.iter != nil {
141 1 : // We are already at the file, but we would need to check for bounds.
142 1 : // Set indicator accordingly.
143 1 : indicator = fileAlreadyLoaded
144 1 : }
145 : // We were already at file, but don't have an iterator, probably because the file was
146 : // beyond the iteration bounds. It may still be, but it is also possible that the bounds
147 : // have changed. We handle that below.
148 : }
149 :
150 : // Note that LevelIter.Close() can be called multiple times.
151 1 : if indicator != fileAlreadyLoaded {
152 1 : if err := l.Close(); err != nil {
153 0 : return noFileLoaded
154 0 : }
155 : }
156 :
157 1 : l.iterFile = file
158 1 : if file == nil {
159 1 : return noFileLoaded
160 1 : }
161 1 : if indicator != fileAlreadyLoaded {
162 1 : l.iter, l.err = l.newIter(file, l.tableOpts)
163 1 : if l.wrapFn != nil {
164 0 : l.iter = l.wrapFn(l.iter)
165 0 : }
166 1 : l.iter = keyspan.MaybeAssert(l.iter, l.cmp)
167 1 : indicator = newFileLoaded
168 : }
169 1 : if l.err != nil {
170 0 : return noFileLoaded
171 0 : }
172 1 : return indicator
173 : }
174 :
175 : // SeekGE implements keyspan.FragmentIterator.
176 1 : func (l *LevelIter) SeekGE(key []byte) (*keyspan.Span, error) {
177 1 : l.dir = +1
178 1 : l.straddle = keyspan.Span{}
179 1 : l.straddleDir = 0
180 1 : l.err = nil // clear cached iteration error
181 1 :
182 1 : f := l.files.SeekGE(l.cmp, key)
183 1 : if f != nil && l.keyType == manifest.KeyTypeRange && l.cmp(key, f.SmallestRangeKey.UserKey) < 0 {
184 1 : // Peek at the previous file.
185 1 : prevFile := l.files.Prev()
186 1 : l.files.Next()
187 1 : if prevFile != nil {
188 1 : // We could unconditionally return an empty span between the seek key and
189 1 : // f.SmallestRangeKey, however if this span is to the left of all range
190 1 : // keys on this level, it could lead to inconsistent behaviour in relative
191 1 : // positioning operations. Consider this example, with a b-c range key:
192 1 : //
193 1 : // SeekGE(a) -> a-b:{}
194 1 : // Next() -> b-c{(#5,RANGEKEYSET,@4,foo)}
195 1 : // Prev() -> nil
196 1 : //
197 1 : // Iterators higher up in the iterator stack rely on this sort of relative
198 1 : // positioning consistency.
199 1 : //
200 1 : // TODO(bilal): Investigate ways to be able to return straddle spans in
201 1 : // cases similar to the above, while still retaining correctness.
202 1 : // Return a straddling key instead of loading the file.
203 1 : l.iterFile = f
204 1 : if l.err = l.Close(); l.err != nil {
205 0 : return l.verify(nil, l.err)
206 0 : }
207 1 : l.straddleDir = +1
208 1 : l.straddle = keyspan.Span{
209 1 : Start: prevFile.LargestRangeKey.UserKey,
210 1 : End: f.SmallestRangeKey.UserKey,
211 1 : Keys: nil,
212 1 : }
213 1 : return l.verify(&l.straddle, nil)
214 : }
215 : }
216 1 : loadFileIndicator := l.loadFile(f, +1)
217 1 : if loadFileIndicator == noFileLoaded {
218 1 : return l.verify(nil, l.err)
219 1 : }
220 1 : if span, err := l.iter.SeekGE(key); err != nil {
221 0 : return l.verify(nil, err)
222 1 : } else if span != nil {
223 1 : return l.verify(span, nil)
224 1 : }
225 1 : return l.skipEmptyFileForward()
226 : }
227 :
228 : // SeekLT implements keyspan.FragmentIterator.
229 1 : func (l *LevelIter) SeekLT(key []byte) (*keyspan.Span, error) {
230 1 : l.dir = -1
231 1 : l.straddle = keyspan.Span{}
232 1 : l.straddleDir = 0
233 1 : l.err = nil // clear cached iteration error
234 1 :
235 1 : f := l.files.SeekLT(l.cmp, key)
236 1 : if f != nil && l.keyType == manifest.KeyTypeRange && l.cmp(f.LargestRangeKey.UserKey, key) < 0 {
237 1 : // Peek at the next file.
238 1 : nextFile := l.files.Next()
239 1 : l.files.Prev()
240 1 : if nextFile != nil {
241 1 : // We could unconditionally return an empty span between f.LargestRangeKey
242 1 : // and the seek key, however if this span is to the right of all range keys
243 1 : // on this level, it could lead to inconsistent behaviour in relative
244 1 : // positioning operations. Consider this example, with a b-c range key:
245 1 : //
246 1 : // SeekLT(d) -> c-d:{}
247 1 : // Prev() -> b-c{(#5,RANGEKEYSET,@4,foo)}
248 1 : // Next() -> nil
249 1 : //
250 1 : // Iterators higher up in the iterator stack rely on this sort of relative
251 1 : // positioning consistency.
252 1 : //
253 1 : // TODO(bilal): Investigate ways to be able to return straddle spans in
254 1 : // cases similar to the above, while still retaining correctness.
255 1 : // Return a straddling key instead of loading the file.
256 1 : l.iterFile = f
257 1 : if l.err = l.Close(); l.err != nil {
258 0 : return l.verify(nil, l.err)
259 0 : }
260 1 : l.straddleDir = -1
261 1 : l.straddle = keyspan.Span{
262 1 : Start: f.LargestRangeKey.UserKey,
263 1 : End: nextFile.SmallestRangeKey.UserKey,
264 1 : Keys: nil,
265 1 : }
266 1 : return l.verify(&l.straddle, nil)
267 : }
268 : }
269 1 : if l.loadFile(f, -1) == noFileLoaded {
270 1 : return l.verify(nil, l.err)
271 1 : }
272 1 : if span, err := l.iter.SeekLT(key); err != nil {
273 0 : return l.verify(nil, err)
274 1 : } else if span != nil {
275 1 : return l.verify(span, nil)
276 1 : }
277 1 : return l.skipEmptyFileBackward()
278 : }
279 :
280 : // First implements keyspan.FragmentIterator.
281 1 : func (l *LevelIter) First() (*keyspan.Span, error) {
282 1 : l.dir = +1
283 1 : l.straddle = keyspan.Span{}
284 1 : l.straddleDir = 0
285 1 : l.err = nil // clear cached iteration error
286 1 :
287 1 : if l.loadFile(l.files.First(), +1) == noFileLoaded {
288 1 : return l.verify(nil, l.err)
289 1 : }
290 1 : if span, err := l.iter.First(); err != nil {
291 0 : return l.verify(nil, err)
292 1 : } else if span != nil {
293 1 : return l.verify(span, nil)
294 1 : }
295 1 : return l.skipEmptyFileForward()
296 : }
297 :
298 : // Last implements keyspan.FragmentIterator.
299 1 : func (l *LevelIter) Last() (*keyspan.Span, error) {
300 1 : l.dir = -1
301 1 : l.straddle = keyspan.Span{}
302 1 : l.straddleDir = 0
303 1 : l.err = nil // clear cached iteration error
304 1 :
305 1 : if l.loadFile(l.files.Last(), -1) == noFileLoaded {
306 1 : return l.verify(nil, l.err)
307 1 : }
308 1 : if span, err := l.iter.Last(); err != nil {
309 0 : return l.verify(nil, err)
310 1 : } else if span != nil {
311 1 : return l.verify(span, nil)
312 1 : }
313 1 : return l.skipEmptyFileBackward()
314 : }
315 :
316 : // Next implements keyspan.FragmentIterator.
317 1 : func (l *LevelIter) Next() (*keyspan.Span, error) {
318 1 : if l.err != nil || (l.iter == nil && l.iterFile == nil && l.dir > 0) {
319 0 : return l.verify(nil, l.err)
320 0 : }
321 1 : if l.iter == nil && l.iterFile == nil {
322 1 : // l.dir <= 0
323 1 : return l.First()
324 1 : }
325 1 : l.dir = +1
326 1 :
327 1 : if l.iter != nil {
328 1 : if span, err := l.iter.Next(); err != nil {
329 0 : return l.verify(nil, err)
330 1 : } else if span != nil {
331 1 : return l.verify(span, nil)
332 1 : }
333 : }
334 1 : return l.skipEmptyFileForward()
335 : }
336 :
337 : // Prev implements keyspan.FragmentIterator.
338 1 : func (l *LevelIter) Prev() (*keyspan.Span, error) {
339 1 : if l.err != nil || (l.iter == nil && l.iterFile == nil && l.dir < 0) {
340 0 : return l.verify(nil, l.err)
341 0 : }
342 1 : if l.iter == nil && l.iterFile == nil {
343 1 : // l.dir >= 0
344 1 : return l.Last()
345 1 : }
346 1 : l.dir = -1
347 1 :
348 1 : if l.iter != nil {
349 1 : if span, err := l.iter.Prev(); err != nil {
350 0 : return nil, err
351 1 : } else if span != nil {
352 1 : return l.verify(span, nil)
353 1 : }
354 : }
355 1 : return l.skipEmptyFileBackward()
356 : }
357 :
358 1 : func (l *LevelIter) skipEmptyFileForward() (*keyspan.Span, error) {
359 1 : if l.straddleDir == 0 && l.keyType == manifest.KeyTypeRange &&
360 1 : l.iterFile != nil && l.iter != nil {
361 1 : // We were at a file that had spans. Check if the next file that has
362 1 : // spans is not directly adjacent to the current file i.e. there is a
363 1 : // gap in the span keyspace between the two files. In that case, synthesize
364 1 : // a "straddle span" in l.straddle and return that.
365 1 : //
366 1 : // Straddle spans are not created in rangedel mode.
367 1 : if l.err = l.Close(); l.err != nil {
368 0 : return l.verify(nil, l.err)
369 0 : }
370 1 : startKey := l.iterFile.LargestRangeKey.UserKey
371 1 : // Resetting l.iterFile without loading the file into l.iter is okay and
372 1 : // does not change the logic in loadFile() as long as l.iter is also nil;
373 1 : // which it should be due to the Close() call above.
374 1 : l.iterFile = l.files.Next()
375 1 : if l.iterFile == nil {
376 1 : return l.verify(nil, nil)
377 1 : }
378 1 : endKey := l.iterFile.SmallestRangeKey.UserKey
379 1 : if l.cmp(startKey, endKey) < 0 {
380 1 : // There is a gap between the two files. Synthesize a straddling span
381 1 : // to avoid unnecessarily loading the next file.
382 1 : l.straddle = keyspan.Span{
383 1 : Start: startKey,
384 1 : End: endKey,
385 1 : }
386 1 : l.straddleDir = +1
387 1 : return l.verify(&l.straddle, nil)
388 1 : }
389 1 : } else if l.straddleDir < 0 {
390 1 : // We were at a straddle key, but are now changing directions. l.iterFile
391 1 : // was already moved backward by skipEmptyFileBackward, so advance it
392 1 : // forward.
393 1 : l.iterFile = l.files.Next()
394 1 : }
395 1 : l.straddle = keyspan.Span{}
396 1 : l.straddleDir = 0
397 1 : var span *keyspan.Span
398 1 : for span.Empty() {
399 1 : fileToLoad := l.iterFile
400 1 : if l.keyType == manifest.KeyTypePoint {
401 1 : // We haven't iterated to the next file yet if we're in point key
402 1 : // (rangedel) mode.
403 1 : fileToLoad = l.files.Next()
404 1 : }
405 1 : if l.loadFile(fileToLoad, +1) == noFileLoaded {
406 1 : return l.verify(nil, l.err)
407 1 : }
408 1 : span, l.err = l.iter.First()
409 1 : if l.err != nil {
410 0 : return l.verify(nil, l.err)
411 0 : }
412 : // In rangedel mode, we can expect to get empty files that we'd need to
413 : // skip over, but not in range key mode.
414 1 : if l.keyType == manifest.KeyTypeRange {
415 1 : break
416 : }
417 : }
418 1 : return l.verify(span, l.err)
419 : }
420 :
421 1 : func (l *LevelIter) skipEmptyFileBackward() (*keyspan.Span, error) {
422 1 : // We were at a file that had spans. Check if the previous file that has
423 1 : // spans is not directly adjacent to the current file i.e. there is a
424 1 : // gap in the span keyspace between the two files. In that case, synthesize
425 1 : // a "straddle span" in l.straddle and return that.
426 1 : //
427 1 : // Straddle spans are not created in rangedel mode.
428 1 : if l.straddleDir == 0 && l.keyType == manifest.KeyTypeRange &&
429 1 : l.iterFile != nil && l.iter != nil {
430 1 : if l.err = l.Close(); l.err != nil {
431 0 : return l.verify(nil, l.err)
432 0 : }
433 1 : endKey := l.iterFile.SmallestRangeKey.UserKey
434 1 : // Resetting l.iterFile without loading the file into l.iter is okay and
435 1 : // does not change the logic in loadFile() as long as l.iter is also nil;
436 1 : // which it should be due to the Close() call above.
437 1 : l.iterFile = l.files.Prev()
438 1 : if l.iterFile == nil {
439 1 : return l.verify(nil, nil)
440 1 : }
441 1 : startKey := l.iterFile.LargestRangeKey.UserKey
442 1 : if l.cmp(startKey, endKey) < 0 {
443 1 : // There is a gap between the two files. Synthesize a straddling span
444 1 : // to avoid unnecessarily loading the next file.
445 1 : l.straddle = keyspan.Span{
446 1 : Start: startKey,
447 1 : End: endKey,
448 1 : }
449 1 : l.straddleDir = -1
450 1 : return l.verify(&l.straddle, nil)
451 1 : }
452 1 : } else if l.straddleDir > 0 {
453 1 : // We were at a straddle key, but are now changing directions. l.iterFile
454 1 : // was already advanced forward by skipEmptyFileForward, so move it
455 1 : // backward.
456 1 : l.iterFile = l.files.Prev()
457 1 : }
458 1 : l.straddle = keyspan.Span{}
459 1 : l.straddleDir = 0
460 1 : var span *keyspan.Span
461 1 : for span.Empty() {
462 1 : fileToLoad := l.iterFile
463 1 : if l.keyType == manifest.KeyTypePoint {
464 1 : fileToLoad = l.files.Prev()
465 1 : }
466 1 : if l.loadFile(fileToLoad, -1) == noFileLoaded {
467 1 : return l.verify(nil, l.err)
468 1 : }
469 1 : span, l.err = l.iter.Last()
470 1 : if l.err != nil {
471 0 : return l.verify(span, l.err)
472 0 : }
473 : // In rangedel mode, we can expect to get empty files that we'd need to
474 : // skip over, but not in range key mode as the filter on the FileMetadata
475 : // should guarantee we always get a non-empty file.
476 1 : if l.keyType == manifest.KeyTypeRange {
477 1 : break
478 : }
479 : }
480 1 : return l.verify(span, l.err)
481 : }
482 :
483 : // verify is invoked whenever a span is returned from an iterator positioning
484 : // method to a caller. During invariant builds, it asserts invariants to the
485 : // caller.
486 1 : func (l *LevelIter) verify(s *keyspan.Span, err error) (*keyspan.Span, error) {
487 1 : // NB: Do not add any logic outside the invariants.Enabled conditional to
488 1 : // ensure that verify is always compiled away in production builds.
489 1 : if invariants.Enabled {
490 1 : if err != l.err {
491 0 : panic(errors.AssertionFailedf("LevelIter.err (%v) != returned error (%v)", l.err, err))
492 : }
493 1 : if err != nil && s != nil {
494 0 : panic(errors.AssertionFailedf("non-nil error returned alongside non-nil span"))
495 : }
496 1 : if f := l.files.Current(); f != l.iterFile {
497 0 : panic(fmt.Sprintf("LevelIter.files.Current (%s) and l.iterFile (%s) diverged",
498 0 : f, l.iterFile))
499 : }
500 : }
501 1 : return s, err
502 : }
503 :
504 : // Error implements keyspan.FragmentIterator.
505 0 : func (l *LevelIter) Error() error {
506 0 : return l.err
507 0 : }
508 :
509 : // Close implements keyspan.FragmentIterator.
510 1 : func (l *LevelIter) Close() error {
511 1 : if l.iter != nil {
512 1 : l.err = l.iter.Close()
513 1 : l.iter = nil
514 1 : }
515 1 : return l.err
516 : }
517 :
518 : // String implements keyspan.FragmentIterator.
519 0 : func (l *LevelIter) String() string {
520 0 : if l.iterFile != nil {
521 0 : return fmt.Sprintf("%s: fileNum=%s", l.level, l.iterFile.FileNum)
522 0 : }
523 0 : return fmt.Sprintf("%s: fileNum=<nil>", l.level)
524 : }
525 :
526 : // WrapChildren implements FragmentIterator.
527 0 : func (l *LevelIter) WrapChildren(wrap keyspan.WrapFn) {
528 0 : l.iter = wrap(l.iter)
529 0 : l.wrapFn = wrap
530 0 : }
|
