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