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 : "context"
9 : "fmt"
10 :
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 : "github.com/cockroachdb/pebble/internal/treeprinter"
16 : )
17 :
18 : // TableNewSpanIter creates a new iterator for range key spans for the given
19 : // file.
20 : type TableNewSpanIter func(
21 : ctx context.Context, file *manifest.FileMetadata, iterOptions keyspan.SpanIterOptions,
22 : ) (keyspan.FragmentIterator, error)
23 :
24 : // LevelIter provides a merged view of spans from sstables in an L1+ level or an
25 : // L0 sublevel.
26 : //
27 : // LevelIter takes advantage of level invariants to only have one sstable span
28 : // block open at one time, opened using the newIter function passed in.
29 : //
30 : // A LevelIter is configured with a key type that is either KeyTypePoint
31 : // (corresponding to range dels) or KeyTypeRange (corresponding to range keys).
32 : // The key type decides which bounds we use for the files (and which files we
33 : // filter out).
34 : //
35 : // LevelIter supports emitting "straddling spans": these are empty spans that
36 : // cover the gaps between the keyspaces of adjacent files. This is an
37 : // optimization to avoid unnecessarily loading files in cases where spans are
38 : // very sparse (in the context of merging spans from multiple levels). We
39 : // currently produce straddling spans only in range key mode.
40 : //
41 : // TODO(radu): investigate enabling straddling spans for rangedel mode.
42 : type LevelIter struct {
43 : cmp base.Compare
44 : keyType manifest.KeyType
45 : // The LSM level this LevelIter is initialized for.
46 : level manifest.Layer
47 : // newIter creates a range del iterator if keyType is KeyTypePoint or a range
48 : // key iterator if keyType is KeyTypeRange.
49 : newIter TableNewSpanIter
50 : // ctx is passed to TableNewSpanIter.
51 : ctx context.Context
52 :
53 : // The options that were passed in.
54 : tableOpts keyspan.SpanIterOptions
55 :
56 : files manifest.LevelIterator
57 :
58 : // file always corresponds to the current position of LevelIter.files.
59 : file *manifest.FileMetadata
60 : pos levelIterPos
61 : // fileIter is the iterator for LevelIter.file when pos is atFile; it is nil
62 : // otherwise.
63 : fileIter keyspan.FragmentIterator
64 :
65 : // lastIter retains the last opened iterator, in case that the next time we
66 : // need an iterator it is for the same file. When fileIter is not nil,
67 : // fileIter is the same with lastIter and file is the same with lastIterFile.
68 : lastIter keyspan.FragmentIterator
69 : lastIterFile *manifest.FileMetadata
70 :
71 : wrapFn keyspan.WrapFn
72 : straddleSpan keyspan.Span
73 :
74 : // TODO(bilal): Add InternalIteratorStats.
75 : }
76 :
77 : // LevelIter implements the keyspan.FragmentIterator interface.
78 : var _ keyspan.FragmentIterator = (*LevelIter)(nil)
79 :
80 : // NewLevelIter returns a LevelIter.
81 : //
82 : // newIter must create a range del iterator for the given file if keyType is
83 : // KeyTypePoint or a range key iterator if keyType is KeyTypeRange.
84 : func NewLevelIter(
85 : ctx context.Context,
86 : opts keyspan.SpanIterOptions,
87 : cmp base.Compare,
88 : newIter TableNewSpanIter,
89 : files manifest.LevelIterator,
90 : level manifest.Layer,
91 : keyType manifest.KeyType,
92 1 : ) *LevelIter {
93 1 : l := &LevelIter{}
94 1 : l.Init(ctx, opts, cmp, newIter, files, level, keyType)
95 1 : return l
96 1 : }
97 :
98 : // Init initializes a LevelIter.
99 : //
100 : // newIter must create a range del iterator for the given file if keyType is
101 : // KeyTypePoint or a range key iterator if keyType is KeyTypeRange.
102 : func (l *LevelIter) Init(
103 : ctx context.Context,
104 : opts keyspan.SpanIterOptions,
105 : cmp base.Compare,
106 : newIter TableNewSpanIter,
107 : files manifest.LevelIterator,
108 : level manifest.Layer,
109 : keyType manifest.KeyType,
110 1 : ) {
111 1 : if keyType != manifest.KeyTypePoint && keyType != manifest.KeyTypeRange {
112 0 : panic("keyType must be point or range")
113 : }
114 1 : *l = LevelIter{
115 1 : cmp: cmp,
116 1 : keyType: keyType,
117 1 : level: level,
118 1 : newIter: newIter,
119 1 : ctx: ctx,
120 1 : tableOpts: opts,
121 1 : files: files.Filter(keyType),
122 1 : }
123 1 : l.setPosAfterFile(nil)
124 : }
125 :
126 : // levelIterPos narrows down the position of the iterator in relation to the file:
127 : //
128 : // - atFile: the iterator is currently positioned inside LevelIter.file.
129 : //
130 : // - beforeFile: the iterator is currently positioned right before
131 : // LevelIter.file. If .file is not the first file, this position corresponds
132 : // to a straddle span.
133 : //
134 : // - afterFile: the iterator is currently positioned right after
135 : // LevelIter.file. If .file is not the last file, this position corresponds
136 : // to a straddle span.
137 : //
138 : // Example:
139 : //
140 : // beforeFile atFile afterFile
141 : // | | |
142 : // v v v
143 : // ..--- .files.Prev() ------- .file ------- .files.Next() ---...
144 : //
145 : // Note that each straddle position can be represented in two different ways
146 : // (either after one file, or before the other file). We use the one which makes
147 : // it easier to keep l.file in sync with the l.files iterator (which depends on
148 : // the iteration direction).
149 : //
150 : // When file is nil, it should be considered a sentinel either before or after
151 : // all the files. When file is nil and pos is afterFile, we are positioned
152 : // after the imaginary start sentinel, i.e. before the first file:
153 : //
154 : // afterFile
155 : // |
156 : // v
157 : // .file=nil ------- .files.First() ---...
158 : //
159 : // When file is nil and pos is beforeFile, we are positioned after the
160 : // imaginary end sentinel, i.e. after the last file:
161 : //
162 : //
163 : // beforeFile
164 : // |
165 : // v
166 : // ...--- .files.Last() ------- .file=nil
167 : //
168 : // Note that when straddle spans are not emitted, the position is always
169 : // `atFile` unless the iterator is exhausted.
170 : type levelIterPos uint8
171 :
172 : const (
173 : atFile levelIterPos = iota
174 : beforeFile
175 : afterFile
176 : )
177 :
178 : // SeekGE implements keyspan.FragmentIterator.
179 1 : func (l *LevelIter) SeekGE(key []byte) (*keyspan.Span, error) {
180 1 : file := l.files.SeekGE(l.cmp, key)
181 1 : if file == nil {
182 1 : l.setPosBeforeFile(nil)
183 1 : return nil, nil
184 1 : }
185 1 : if l.straddleSpansEnabled() && l.cmp(key, file.SmallestRangeKey.UserKey) < 0 {
186 1 : // Peek at the previous file.
187 1 : if prevFile := l.files.Prev(); 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 : // SeekGE(a) -> a-b:{}
193 1 : // Next() -> b-c{(#5,RANGEKEYSET,@4,foo)}
194 1 : // Prev() -> nil
195 1 : // Iterators higher up in the iterator stack rely on this sort
196 1 : // of relative positioning consistency.
197 1 : //
198 1 : // TODO(bilal): Investigate ways to be able to return straddle spans in
199 1 : // cases similar to the above, while still retaining correctness.
200 1 : // Return a straddling key instead of loading the file.
201 1 : l.setPosAfterFile(prevFile)
202 1 : return l.makeStraddleSpan(prevFile, file), nil
203 1 : }
204 : // Return the iterator to file.
205 1 : l.files.Next()
206 : }
207 :
208 1 : if err := l.setPosAtFile(file); err != nil {
209 1 : return nil, err
210 1 : }
211 1 : if span, err := l.fileIter.SeekGE(key); span != nil || err != nil {
212 1 : return span, err
213 1 : }
214 1 : return l.moveToNextFile()
215 : }
216 :
217 : // SeekLT implements keyspan.FragmentIterator.
218 1 : func (l *LevelIter) SeekLT(key []byte) (*keyspan.Span, error) {
219 1 : file := l.files.SeekLT(l.cmp, key)
220 1 : if file == nil {
221 1 : l.setPosAfterFile(nil)
222 1 : return nil, nil
223 1 : }
224 1 : if l.straddleSpansEnabled() && l.cmp(file.LargestRangeKey.UserKey, key) < 0 {
225 1 : // Peek at the next file.
226 1 : if nextFile := l.files.Next(); nextFile != nil {
227 1 : // We could unconditionally return an empty span between f.LargestRangeKey
228 1 : // and the seek key, however if this span is to the right of all range keys
229 1 : // on this level, it could lead to inconsistent behaviour in relative
230 1 : // positioning operations. Consider this example, with a b-c range key:
231 1 : // SeekLT(d) -> c-d:{}
232 1 : // Prev() -> b-c{(#5,RANGEKEYSET,@4,foo)}
233 1 : // Next() -> nil
234 1 : // Iterators higher up in the iterator stack rely on this sort of relative
235 1 : // positioning consistency.
236 1 : //
237 1 : // TODO(bilal): Investigate ways to be able to return straddle spans in
238 1 : // cases similar to the above, while still retaining correctness.
239 1 : // Return a straddling key instead of loading the file.
240 1 : l.setPosBeforeFile(nextFile)
241 1 : return l.makeStraddleSpan(file, nextFile), nil
242 1 : }
243 : // Return the iterator to file.
244 1 : l.files.Prev()
245 : }
246 1 : if err := l.setPosAtFile(file); err != nil {
247 1 : return nil, err
248 1 : }
249 1 : if span, err := l.fileIter.SeekLT(key); span != nil || err != nil {
250 1 : return span, err
251 1 : }
252 1 : return l.moveToPrevFile()
253 : }
254 :
255 : // First implements keyspan.FragmentIterator.
256 1 : func (l *LevelIter) First() (*keyspan.Span, error) {
257 1 : file := l.files.First()
258 1 : if file == nil {
259 1 : l.setPosBeforeFile(nil)
260 1 : return nil, nil
261 1 : }
262 1 : if err := l.setPosAtFile(file); err != nil {
263 1 : return nil, err
264 1 : }
265 1 : if span, err := l.fileIter.First(); span != nil || err != nil {
266 1 : return span, err
267 1 : }
268 1 : return l.moveToNextFile()
269 : }
270 :
271 : // Last implements keyspan.FragmentIterator.
272 1 : func (l *LevelIter) Last() (*keyspan.Span, error) {
273 1 : file := l.files.Last()
274 1 : if file == nil {
275 0 : l.setPosAfterFile(nil)
276 0 : return nil, nil
277 0 : }
278 1 : if err := l.setPosAtFile(file); err != nil {
279 1 : return nil, err
280 1 : }
281 1 : if span, err := l.fileIter.Last(); span != nil || err != nil {
282 1 : return span, err
283 1 : }
284 1 : return l.moveToPrevFile()
285 : }
286 :
287 : // Next implements keyspan.FragmentIterator.
288 1 : func (l *LevelIter) Next() (*keyspan.Span, error) {
289 1 : if l.file == nil {
290 1 : if l.pos == afterFile {
291 1 : return l.First()
292 1 : }
293 : // Iterator is exhausted.
294 1 : return nil, nil
295 : }
296 1 : switch l.pos {
297 1 : case atFile:
298 1 : if span, err := l.fileIter.Next(); span != nil || err != nil {
299 1 : return span, err
300 1 : }
301 1 : case beforeFile:
302 1 : // We were positioned on a straddle span before l.file; now we can advance to the file.
303 1 : if err := l.setPosAtFile(l.file); err != nil {
304 0 : return nil, err
305 0 : }
306 1 : if span, err := l.fileIter.First(); span != nil || err != nil {
307 1 : return span, err
308 1 : }
309 1 : case afterFile:
310 : // We were positioned on a straddle span after l.file. Move to the next file.
311 : }
312 1 : return l.moveToNextFile()
313 : }
314 :
315 : // Prev implements keyspan.FragmentIterator.
316 1 : func (l *LevelIter) Prev() (*keyspan.Span, error) {
317 1 : if l.file == nil {
318 1 : if l.pos == beforeFile {
319 1 : return l.Last()
320 1 : }
321 : // Iterator is exhausted.
322 1 : return nil, nil
323 : }
324 1 : switch l.pos {
325 1 : case atFile:
326 1 : if span, err := l.fileIter.Prev(); span != nil || err != nil {
327 1 : return span, err
328 1 : }
329 1 : case afterFile:
330 1 : // We were positioned on a straddle span after l.file; now we can advance
331 1 : // (backwards) to the file.
332 1 : if err := l.setPosAtFile(l.file); err != nil {
333 0 : return nil, err
334 0 : }
335 1 : if span, err := l.fileIter.Last(); span != nil || err != nil {
336 1 : return span, err
337 1 : }
338 1 : case beforeFile:
339 : // We were positioned on a straddle span before l.file. Move to the previous file.
340 : }
341 1 : return l.moveToPrevFile()
342 : }
343 :
344 1 : func (l *LevelIter) moveToNextFile() (*keyspan.Span, error) {
345 1 : if invariants.Enabled && l.pos == beforeFile {
346 0 : panic("moveToNextFile with beforeFile pos")
347 : }
348 1 : for {
349 1 : nextFile := l.files.Next()
350 1 : if nextFile == nil {
351 1 : l.setPosBeforeFile(nil)
352 1 : return nil, nil
353 1 : }
354 : // Emit a straddle span, if necessary.
355 1 : if l.pos == atFile && nextFile != nil && l.needStraddleSpan(l.file, nextFile) {
356 1 : span := l.makeStraddleSpan(l.file, nextFile)
357 1 : l.setPosBeforeFile(nextFile)
358 1 : return span, nil
359 1 : }
360 1 : if err := l.setPosAtFile(nextFile); err != nil {
361 0 : return nil, err
362 0 : }
363 1 : if span, err := l.fileIter.First(); span != nil || err != nil {
364 1 : return span, err
365 1 : }
366 : // The file had no spans; continue.
367 : }
368 : }
369 :
370 1 : func (l *LevelIter) moveToPrevFile() (*keyspan.Span, error) {
371 1 : if invariants.Enabled && l.pos == afterFile {
372 0 : panic("eofBackward with afterFile pos")
373 : }
374 1 : for {
375 1 : prevFile := l.files.Prev()
376 1 : if prevFile == nil {
377 1 : l.setPosAfterFile(nil)
378 1 : return nil, nil
379 1 : }
380 : // Emit a straddle span, if necessary.
381 1 : if l.pos == atFile && l.file != nil && l.needStraddleSpan(prevFile, l.file) {
382 1 : span := l.makeStraddleSpan(prevFile, l.file)
383 1 : l.setPosAfterFile(prevFile)
384 1 : return span, nil
385 1 : }
386 1 : if err := l.setPosAtFile(prevFile); err != nil {
387 0 : return nil, err
388 0 : }
389 1 : if span, err := l.fileIter.Last(); span != nil || err != nil {
390 1 : return span, err
391 1 : }
392 : // The file had no spans; continue.
393 : }
394 : }
395 :
396 : // SetContext is part of the FragmentIterator interface.
397 0 : func (l *LevelIter) SetContext(ctx context.Context) {
398 0 : l.ctx = ctx
399 0 : if l.lastIter != nil {
400 0 : l.lastIter.SetContext(ctx)
401 0 : }
402 : }
403 :
404 : // Close implements keyspan.FragmentIterator.
405 1 : func (l *LevelIter) Close() {
406 1 : l.file = nil
407 1 : l.fileIter = nil
408 1 : if l.lastIter != nil {
409 1 : l.lastIter.Close()
410 1 : l.lastIter = nil
411 1 : l.lastIterFile = nil
412 1 : }
413 : }
414 :
415 : // String implements keyspan.FragmentIterator.
416 1 : func (l *LevelIter) String() string {
417 1 : if l.file != nil {
418 1 : return fmt.Sprintf("%s: fileNum=%s", l.level, l.file.FileNum)
419 1 : }
420 0 : return fmt.Sprintf("%s: fileNum=<nil>", l.level)
421 : }
422 :
423 : // WrapChildren implements FragmentIterator.
424 0 : func (l *LevelIter) WrapChildren(wrap keyspan.WrapFn) {
425 0 : if l.fileIter != nil {
426 0 : l.fileIter = wrap(l.fileIter)
427 0 : }
428 0 : l.wrapFn = wrap
429 : }
430 :
431 : // DebugTree is part of the FragmentIterator interface.
432 0 : func (l *LevelIter) DebugTree(tp treeprinter.Node) {
433 0 : n := tp.Childf("%T(%p) %s", l, l, l.level)
434 0 : if l.fileIter != nil {
435 0 : l.fileIter.DebugTree(n)
436 0 : }
437 : }
438 :
439 1 : func (l *LevelIter) setPosBeforeFile(f *manifest.FileMetadata) {
440 1 : l.setPosInternal(f, beforeFile)
441 1 : }
442 :
443 1 : func (l *LevelIter) setPosAfterFile(f *manifest.FileMetadata) {
444 1 : l.setPosInternal(f, afterFile)
445 1 : }
446 :
447 : // setPosAtFile sets the current position and opens an iterator for the file (if
448 : // necessary).
449 1 : func (l *LevelIter) setPosAtFile(f *manifest.FileMetadata) error {
450 1 : l.setPosInternal(f, atFile)
451 1 : // See if the last iterator was for the same file; if not, close it and open a
452 1 : // new one.
453 1 : if l.lastIter == nil || l.lastIterFile != f {
454 1 : if l.lastIter != nil {
455 1 : l.lastIter.Close()
456 1 : l.lastIter = nil
457 1 : l.lastIterFile = nil
458 1 : }
459 1 : iter, err := l.newIter(l.ctx, l.file, l.tableOpts)
460 1 : if err != nil {
461 1 : return err
462 1 : }
463 1 : iter = keyspan.MaybeAssert(iter, l.cmp)
464 1 : if l.wrapFn != nil {
465 0 : iter = l.wrapFn(iter)
466 0 : }
467 1 : l.lastIter = iter
468 1 : l.lastIterFile = f
469 : }
470 1 : l.fileIter = l.lastIter
471 1 : return nil
472 : }
473 :
474 : // setPos sets l.file and l.pos (and closes the iteris for the new file).
475 1 : func (l *LevelIter) setPosInternal(f *manifest.FileMetadata, pos levelIterPos) {
476 1 : l.file = f
477 1 : l.fileIter = nil
478 1 : l.pos = pos
479 1 : }
480 :
481 1 : func (l *LevelIter) straddleSpansEnabled() bool {
482 1 : return l.keyType == manifest.KeyTypeRange
483 1 : }
484 :
485 : // needStraddleSpan returns true if straddle spans are enabled and there is a
486 : // gap between the bounds of the files. file and nextFile are assumed to be
487 : // consecutive files in the level, in the order they appear in the level.
488 1 : func (l *LevelIter) needStraddleSpan(file, nextFile *manifest.FileMetadata) bool {
489 1 : // We directly use range key bounds because that is the current condition for
490 1 : // straddleSpansEnabled.
491 1 : return l.straddleSpansEnabled() && l.cmp(file.LargestRangeKey.UserKey, nextFile.SmallestRangeKey.UserKey) < 0
492 1 : }
493 :
494 : // makeStraddleSpan returns a straddle span that covers the gap between file and
495 : // nextFile.
496 1 : func (l *LevelIter) makeStraddleSpan(file, nextFile *manifest.FileMetadata) *keyspan.Span {
497 1 : l.straddleSpan = keyspan.Span{
498 1 : Start: file.LargestRangeKey.UserKey,
499 1 : End: nextFile.SmallestRangeKey.UserKey,
500 1 : Keys: nil,
501 1 : }
502 1 : return &l.straddleSpan
503 1 : }
|
