Line data Source code
1 : // Copyright 2011 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 sstable
6 :
7 : import (
8 : "fmt"
9 : "os"
10 : "sync"
11 :
12 : "github.com/cockroachdb/pebble/internal/base"
13 : "github.com/cockroachdb/pebble/internal/invariants"
14 : "github.com/cockroachdb/pebble/sstable/block"
15 : "github.com/cockroachdb/pebble/sstable/colblk"
16 : "github.com/cockroachdb/pebble/sstable/rowblk"
17 : )
18 :
19 : // dataBlockIterator extends the block.IndexBlockIterator interface with a
20 : // constraint that the implementing type be a pointer to a type I.
21 : //
22 : // DataBlockIterator requires that the type be a pointer to its type parameter,
23 : // D, to allow sstable iterators embed the block iterator within its struct. See
24 : // this example from the Go generics proposal:
25 : // https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#pointer-method-example
26 : type dataBlockIterator[D any] interface {
27 : block.DataBlockIterator
28 :
29 : *D // non-interface type constraint element
30 : }
31 :
32 : // indexBlockIterator extends the block.IndexBlockIterator interface with a
33 : // constraint that the implementing type be a pointer to a type I.
34 : //
35 : // indexBlockIterator requires that the type be a pointer to its type parameter,
36 : // I, to allow sstable iterators embed the block iterator within its struct. See
37 : // this example from the Go generics proposal:
38 : // https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#pointer-method-example
39 : type indexBlockIterator[I any] interface {
40 : block.IndexBlockIterator
41 :
42 : *I // non-interface type constraint element
43 : }
44 :
45 : // Iterator iterates over an entire table of data.
46 : type Iterator interface {
47 : base.InternalIterator
48 :
49 : // NextPrefix implements (base.InternalIterator).NextPrefix.
50 : NextPrefix(succKey []byte) *base.InternalKV
51 :
52 : // SetCloseHook sets a function that will be called when the iterator is
53 : // closed. This is used by the file cache to release the reference count on
54 : // the open sstable.Reader when the iterator is closed.
55 : SetCloseHook(func())
56 : }
57 :
58 : // Iterator positioning optimizations and singleLevelIterator and
59 : // twoLevelIterator:
60 : //
61 : // An iterator is absolute positioned using one of the Seek or First or Last
62 : // calls. After absolute positioning, there can be relative positioning done
63 : // by stepping using Prev or Next.
64 : //
65 : // We implement optimizations below where an absolute positioning call can in
66 : // some cases use the current position to do less work. To understand these,
67 : // we first define some terms. An iterator is bounds-exhausted if the bounds
68 : // (upper of lower) have been reached. An iterator is data-exhausted if it has
69 : // the reached the end of the data (forward or reverse) in the sstable. A
70 : // singleLevelIterator only knows a local-data-exhausted property since when
71 : // it is used as part of a twoLevelIterator, the twoLevelIterator can step to
72 : // the next lower-level index block.
73 : //
74 : // The bounds-exhausted property is tracked by
75 : // singleLevelIterator.exhaustedBounds being +1 (upper bound reached) or -1
76 : // (lower bound reached). The same field is reused by twoLevelIterator. Either
77 : // may notice the exhaustion of the bound and set it. Note that if
78 : // singleLevelIterator sets this property, it is not a local property (since
79 : // the bound has been reached regardless of whether this is in the context of
80 : // the twoLevelIterator or not).
81 : //
82 : // The data-exhausted property is tracked in a more subtle manner. We define
83 : // two predicates:
84 : // - partial-local-data-exhausted (PLDE):
85 : // i.data.IsDataInvalidated() || !i.data.Valid()
86 : // - partial-global-data-exhausted (PGDE):
87 : // i.index.IsDataInvalidated() || !i.index.Valid() || i.data.IsDataInvalidated() ||
88 : // !i.data.Valid()
89 : //
90 : // PLDE is defined for a singleLevelIterator. PGDE is defined for a
91 : // twoLevelIterator. Oddly, in our code below the singleLevelIterator does not
92 : // know when it is part of a twoLevelIterator so it does not know when its
93 : // property is local or global.
94 : //
95 : // Now to define data-exhausted:
96 : // - Prerequisite: we must know that the iterator has been positioned and
97 : // i.err is nil.
98 : // - bounds-exhausted must not be true:
99 : // If bounds-exhausted is true, we have incomplete knowledge of
100 : // data-exhausted since PLDE or PGDE could be true because we could have
101 : // chosen not to load index block or data block and figured out that the
102 : // bound is exhausted (due to block property filters filtering out index and
103 : // data blocks and going past the bound on the top level index block). Note
104 : // that if we tried to separate out the BPF case from others we could
105 : // develop more knowledge here.
106 : // - PGDE is true for twoLevelIterator. PLDE is true if it is a standalone
107 : // singleLevelIterator. !PLDE or !PGDE of course imply that data-exhausted
108 : // is not true.
109 : //
110 : // An implication of the above is that if we are going to somehow utilize
111 : // knowledge of data-exhausted in an optimization, we must not forget the
112 : // existing value of bounds-exhausted since by forgetting the latter we can
113 : // erroneously think that data-exhausted is true. Bug #2036 was due to this
114 : // forgetting.
115 : //
116 : // Now to the two categories of optimizations we currently have:
117 : // - Monotonic bounds optimization that reuse prior iterator position when
118 : // doing seek: These only work with !data-exhausted. We could choose to make
119 : // these work with data-exhausted but have not bothered because in the
120 : // context of a DB if data-exhausted were true, the DB would move to the
121 : // next file in the level. Note that this behavior of moving to the next
122 : // file is not necessarily true for L0 files, so there could be some benefit
123 : // in the future in this optimization. See the WARNING-data-exhausted
124 : // comments if trying to optimize this in the future.
125 : // - TrySeekUsingNext optimizations: these work regardless of exhaustion
126 : // state.
127 : //
128 : // Implementation detail: In the code PLDE only checks that
129 : // i.data.IsDataInvalidated(). This narrower check is safe, since this is a
130 : // subset of the set expressed by the OR expression. Also, it is not a
131 : // de-optimization since whenever we exhaust the iterator we explicitly call
132 : // i.data.Invalidate(). PGDE checks i.index.IsDataInvalidated() &&
133 : // i.data.IsDataInvalidated(). Again, this narrower check is safe, and not a
134 : // de-optimization since whenever we exhaust the iterator we explicitly call
135 : // i.index.Invalidate() and i.data.Invalidate(). The && is questionable -- for
136 : // now this is a bit of defensive code. We should seriously consider removing
137 : // it, since defensive code suggests we are not confident about our invariants
138 : // (and if we are not confident, we need more invariant assertions, not
139 : // defensive code).
140 : //
141 : // TODO(sumeer): remove the aforementioned defensive code.
142 :
143 : type (
144 : singleLevelIteratorRowBlocks = singleLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter]
145 : twoLevelIteratorRowBlocks = twoLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter]
146 : singleLevelIteratorColumnBlocks = singleLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter]
147 : twoLevelIteratorColumnBlocks = twoLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter]
148 : )
149 :
150 : var (
151 : singleLevelIterRowBlockPool sync.Pool // *singleLevelIteratorRowBlocks
152 : twoLevelIterRowBlockPool sync.Pool // *twoLevelIteratorRowBlocks
153 : singleLevelIterColumnBlockPool sync.Pool // *singleLevelIteratorColumnBlocks
154 : twoLevelIterColumnBlockPool sync.Pool // *singleLevelIteratorColumnBlocks
155 : )
156 :
157 1 : func init() {
158 1 : singleLevelIterRowBlockPool = sync.Pool{
159 1 : New: func() interface{} {
160 1 : i := &singleLevelIteratorRowBlocks{pool: &singleLevelIterRowBlockPool}
161 1 : if invariants.UseFinalizers {
162 1 : invariants.SetFinalizer(i, checkSingleLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter])
163 1 : }
164 1 : return i
165 : },
166 : }
167 1 : twoLevelIterRowBlockPool = sync.Pool{
168 1 : New: func() interface{} {
169 1 : i := &twoLevelIteratorRowBlocks{pool: &twoLevelIterRowBlockPool}
170 1 : if invariants.UseFinalizers {
171 1 : invariants.SetFinalizer(i, checkTwoLevelIterator[rowblk.IndexIter, *rowblk.IndexIter, rowblk.Iter, *rowblk.Iter])
172 1 : }
173 1 : return i
174 : },
175 : }
176 1 : singleLevelIterColumnBlockPool = sync.Pool{
177 1 : New: func() interface{} {
178 1 : i := &singleLevelIteratorColumnBlocks{
179 1 : pool: &singleLevelIterColumnBlockPool,
180 1 : }
181 1 : if invariants.UseFinalizers {
182 1 : invariants.SetFinalizer(i, checkSingleLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter])
183 1 : }
184 1 : return i
185 : },
186 : }
187 1 : twoLevelIterColumnBlockPool = sync.Pool{
188 1 : New: func() interface{} {
189 1 : i := &twoLevelIteratorColumnBlocks{
190 1 : pool: &twoLevelIterColumnBlockPool,
191 1 : }
192 1 : if invariants.UseFinalizers {
193 1 : invariants.SetFinalizer(i, checkTwoLevelIterator[colblk.IndexIter, *colblk.IndexIter, colblk.DataBlockIter, *colblk.DataBlockIter])
194 1 : }
195 1 : return i
196 : },
197 : }
198 : }
199 :
200 : func checkSingleLevelIterator[I any, PI indexBlockIterator[I], D any, PD dataBlockIterator[D]](
201 : obj interface{},
202 1 : ) {
203 1 : i := obj.(*singleLevelIterator[I, PI, D, PD])
204 1 : if h := PD(&i.data).Handle(); h.Valid() {
205 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %#v\n", h)
206 0 : os.Exit(1)
207 0 : }
208 1 : if h := PI(&i.index).Handle(); h.Valid() {
209 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %#v\n", h)
210 0 : os.Exit(1)
211 0 : }
212 : }
213 :
214 : func checkTwoLevelIterator[I any, PI indexBlockIterator[I], D any, PD dataBlockIterator[D]](
215 : obj interface{},
216 1 : ) {
217 1 : i := obj.(*twoLevelIterator[I, PI, D, PD])
218 1 : if h := PD(&i.secondLevel.data).Handle(); h.Valid() {
219 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.data.handle is not nil: %#v\n", h)
220 0 : os.Exit(1)
221 0 : }
222 1 : if h := PI(&i.secondLevel.index).Handle(); h.Valid() {
223 0 : fmt.Fprintf(os.Stderr, "singleLevelIterator.index.handle is not nil: %#v\n", h)
224 0 : os.Exit(1)
225 0 : }
226 : }
|
