Line data Source code
1 : // Copyright 2018 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 pebble
6 :
7 : import (
8 : "context"
9 : "fmt"
10 :
11 : "github.com/cockroachdb/pebble/internal/base"
12 : "github.com/cockroachdb/pebble/internal/keyspan"
13 : "github.com/cockroachdb/pebble/internal/manifest"
14 : "github.com/cockroachdb/pebble/sstable"
15 : )
16 :
17 : // getIter is an internal iterator used to perform gets. It iterates through
18 : // the values for a particular key, level by level. It is not a general purpose
19 : // internalIterator, but specialized for Get operations so that it loads data
20 : // lazily.
21 : type getIter struct {
22 : logger Logger
23 : comparer *Comparer
24 : newIters tableNewIters
25 : snapshot uint64
26 : key []byte
27 : iter internalIterator
28 : rangeDelIter keyspan.FragmentIterator
29 : tombstone *keyspan.Span
30 : levelIter levelIter
31 : level int
32 : batch *Batch
33 : mem flushableList
34 : l0 []manifest.LevelSlice
35 : version *version
36 : iterKey *InternalKey
37 : iterValue base.LazyValue
38 : err error
39 : }
40 :
41 : // TODO(sumeer): CockroachDB code doesn't use getIter, but, for completeness,
42 : // make this implement InternalIteratorWithStats.
43 :
44 : // getIter implements the base.InternalIterator interface.
45 : var _ base.InternalIterator = (*getIter)(nil)
46 :
47 0 : func (g *getIter) String() string {
48 0 : return fmt.Sprintf("len(l0)=%d, len(mem)=%d, level=%d", len(g.l0), len(g.mem), g.level)
49 0 : }
50 :
51 0 : func (g *getIter) SeekGE(key []byte, flags base.SeekGEFlags) (*InternalKey, base.LazyValue) {
52 0 : panic("pebble: SeekGE unimplemented")
53 : }
54 :
55 : func (g *getIter) SeekPrefixGE(
56 : prefix, key []byte, flags base.SeekGEFlags,
57 0 : ) (*base.InternalKey, base.LazyValue) {
58 0 : panic("pebble: SeekPrefixGE unimplemented")
59 : }
60 :
61 0 : func (g *getIter) SeekLT(key []byte, flags base.SeekLTFlags) (*InternalKey, base.LazyValue) {
62 0 : panic("pebble: SeekLT unimplemented")
63 : }
64 :
65 1 : func (g *getIter) First() (*InternalKey, base.LazyValue) {
66 1 : return g.Next()
67 1 : }
68 :
69 0 : func (g *getIter) Last() (*InternalKey, base.LazyValue) {
70 0 : panic("pebble: Last unimplemented")
71 : }
72 :
73 1 : func (g *getIter) Next() (*InternalKey, base.LazyValue) {
74 1 : if g.iter != nil {
75 1 : g.iterKey, g.iterValue = g.iter.Next()
76 1 : if err := g.iter.Error(); err != nil {
77 0 : g.err = err
78 0 : return nil, base.LazyValue{}
79 0 : }
80 : }
81 :
82 1 : for {
83 1 : if g.iter != nil {
84 1 : // We have to check rangeDelIter on each iteration because a single
85 1 : // user-key can be spread across multiple tables in a level. A range
86 1 : // tombstone will appear in the table corresponding to its start
87 1 : // key. Every call to levelIter.Next() potentially switches to a new
88 1 : // table and thus reinitializes rangeDelIter.
89 1 : if g.rangeDelIter != nil {
90 1 : g.tombstone, g.err = keyspan.Get(g.comparer.Compare, g.rangeDelIter, g.key)
91 1 : g.err = firstError(g.err, g.rangeDelIter.Close())
92 1 : if g.err != nil {
93 0 : return nil, base.LazyValue{}
94 0 : }
95 1 : g.rangeDelIter = nil
96 : }
97 :
98 1 : if g.iterKey != nil {
99 1 : key := g.iterKey
100 1 : if g.tombstone != nil && g.tombstone.CoversAt(g.snapshot, key.SeqNum()) {
101 1 : // We have a range tombstone covering this key. Rather than return a
102 1 : // point or range deletion here, we return false and close our
103 1 : // internal iterator which will make Valid() return false,
104 1 : // effectively stopping iteration.
105 1 : g.err = g.iter.Close()
106 1 : g.iter = nil
107 1 : return nil, base.LazyValue{}
108 1 : }
109 1 : if g.comparer.Equal(g.key, key.UserKey) {
110 1 : if !key.Visible(g.snapshot, base.InternalKeySeqNumMax) {
111 1 : g.iterKey, g.iterValue = g.iter.Next()
112 1 : continue
113 : }
114 1 : return g.iterKey, g.iterValue
115 : }
116 : }
117 : // We've advanced the iterator passed the desired key. Move on to the
118 : // next memtable / level.
119 1 : g.err = g.iter.Close()
120 1 : g.iter = nil
121 1 : if g.err != nil {
122 0 : return nil, base.LazyValue{}
123 0 : }
124 : }
125 :
126 : // Create an iterator from the batch.
127 1 : if g.batch != nil {
128 1 : if g.batch.index == nil {
129 0 : g.err = ErrNotIndexed
130 0 : g.iterKey, g.iterValue = nil, base.LazyValue{}
131 0 : return nil, base.LazyValue{}
132 0 : }
133 1 : g.iter = g.batch.newInternalIter(nil)
134 1 : g.rangeDelIter = g.batch.newRangeDelIter(
135 1 : nil,
136 1 : // Get always reads the entirety of the batch's history, so no
137 1 : // batch keys should be filtered.
138 1 : base.InternalKeySeqNumMax,
139 1 : )
140 1 : g.iterKey, g.iterValue = g.iter.SeekGE(g.key, base.SeekGEFlagsNone)
141 1 : if err := g.iter.Error(); err != nil {
142 0 : g.err = err
143 0 : return nil, base.LazyValue{}
144 0 : }
145 1 : g.batch = nil
146 1 : continue
147 : }
148 :
149 : // If we have a tombstone from a previous level it is guaranteed to delete
150 : // keys in lower levels.
151 1 : if g.tombstone != nil && g.tombstone.VisibleAt(g.snapshot) {
152 1 : return nil, base.LazyValue{}
153 1 : }
154 :
155 : // Create iterators from memtables from newest to oldest.
156 1 : if n := len(g.mem); n > 0 {
157 1 : m := g.mem[n-1]
158 1 : g.iter = m.newIter(nil)
159 1 : g.rangeDelIter = m.newRangeDelIter(nil)
160 1 : g.mem = g.mem[:n-1]
161 1 : g.iterKey, g.iterValue = g.iter.SeekGE(g.key, base.SeekGEFlagsNone)
162 1 : if err := g.iter.Error(); err != nil {
163 0 : g.err = err
164 0 : return nil, base.LazyValue{}
165 0 : }
166 1 : continue
167 : }
168 :
169 1 : if g.level == 0 {
170 1 : // Create iterators from L0 from newest to oldest.
171 1 : if n := len(g.l0); n > 0 {
172 1 : files := g.l0[n-1].Iter()
173 1 : g.l0 = g.l0[:n-1]
174 1 : iterOpts := IterOptions{
175 1 : // TODO(sumeer): replace with a parameter provided by the caller.
176 1 : CategoryAndQoS: sstable.CategoryAndQoS{
177 1 : Category: "pebble-get",
178 1 : QoSLevel: sstable.LatencySensitiveQoSLevel,
179 1 : },
180 1 : logger: g.logger,
181 1 : snapshotForHideObsoletePoints: g.snapshot}
182 1 : g.levelIter.init(context.Background(), iterOpts, g.comparer, g.newIters,
183 1 : files, manifest.L0Sublevel(n), internalIterOpts{})
184 1 : g.levelIter.initRangeDel(&g.rangeDelIter)
185 1 : bc := levelIterBoundaryContext{}
186 1 : g.levelIter.initBoundaryContext(&bc)
187 1 : g.iter = &g.levelIter
188 1 :
189 1 : // Compute the key prefix for bloom filtering if split function is
190 1 : // specified, or use the user key as default.
191 1 : prefix := g.key
192 1 : if g.comparer.Split != nil {
193 1 : prefix = g.key[:g.comparer.Split(g.key)]
194 1 : }
195 1 : g.iterKey, g.iterValue = g.iter.SeekPrefixGE(prefix, g.key, base.SeekGEFlagsNone)
196 1 : if err := g.iter.Error(); err != nil {
197 0 : g.err = err
198 0 : return nil, base.LazyValue{}
199 0 : }
200 :
201 1 : if bc.isSyntheticIterBoundsKey || bc.isIgnorableBoundaryKey {
202 1 : g.iterKey = nil
203 1 : g.iterValue = base.LazyValue{}
204 1 : }
205 1 : continue
206 : }
207 1 : g.level++
208 : }
209 :
210 1 : if g.level >= numLevels {
211 1 : return nil, base.LazyValue{}
212 1 : }
213 1 : if g.version.Levels[g.level].Empty() {
214 1 : g.level++
215 1 : continue
216 : }
217 :
218 1 : iterOpts := IterOptions{
219 1 : // TODO(sumeer): replace with a parameter provided by the caller.
220 1 : CategoryAndQoS: sstable.CategoryAndQoS{
221 1 : Category: "pebble-get",
222 1 : QoSLevel: sstable.LatencySensitiveQoSLevel,
223 1 : }, logger: g.logger, snapshotForHideObsoletePoints: g.snapshot}
224 1 : g.levelIter.init(context.Background(), iterOpts, g.comparer, g.newIters,
225 1 : g.version.Levels[g.level].Iter(), manifest.Level(g.level), internalIterOpts{})
226 1 : g.levelIter.initRangeDel(&g.rangeDelIter)
227 1 : bc := levelIterBoundaryContext{}
228 1 : g.levelIter.initBoundaryContext(&bc)
229 1 : g.level++
230 1 : g.iter = &g.levelIter
231 1 :
232 1 : // Compute the key prefix for bloom filtering if split function is
233 1 : // specified, or use the user key as default.
234 1 : prefix := g.key
235 1 : if g.comparer.Split != nil {
236 1 : prefix = g.key[:g.comparer.Split(g.key)]
237 1 : }
238 1 : g.iterKey, g.iterValue = g.iter.SeekPrefixGE(prefix, g.key, base.SeekGEFlagsNone)
239 1 : if err := g.iter.Error(); err != nil {
240 0 : g.err = err
241 0 : return nil, base.LazyValue{}
242 0 : }
243 1 : if bc.isSyntheticIterBoundsKey || bc.isIgnorableBoundaryKey {
244 1 : g.iterKey = nil
245 1 : g.iterValue = base.LazyValue{}
246 1 : }
247 : }
248 : }
249 :
250 0 : func (g *getIter) Prev() (*InternalKey, base.LazyValue) {
251 0 : panic("pebble: Prev unimplemented")
252 : }
253 :
254 0 : func (g *getIter) NextPrefix([]byte) (*InternalKey, base.LazyValue) {
255 0 : panic("pebble: NextPrefix unimplemented")
256 : }
257 :
258 0 : func (g *getIter) Valid() bool {
259 0 : return g.iterKey != nil && g.err == nil
260 0 : }
261 :
262 1 : func (g *getIter) Error() error {
263 1 : return g.err
264 1 : }
265 :
266 1 : func (g *getIter) Close() error {
267 1 : if g.iter != nil {
268 1 : if err := g.iter.Close(); err != nil && g.err == nil {
269 0 : g.err = err
270 0 : }
271 1 : g.iter = nil
272 : }
273 1 : return g.err
274 : }
275 :
276 0 : func (g *getIter) SetBounds(lower, upper []byte) {
277 0 : panic("pebble: SetBounds unimplemented")
278 : }
279 :
280 0 : func (g *getIter) SetContext(_ context.Context) {}
|
