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 : )
15 :
16 : // getIter is an internal iterator used to perform gets. It iterates through
17 : // the values for a particular key, level by level. It is not a general purpose
18 : // internalIterator, but specialized for Get operations so that it loads data
19 : // lazily.
20 : type getIter struct {
21 : comparer *Comparer
22 : newIters tableNewIters
23 : snapshot uint64
24 : iterOpts IterOptions
25 : key []byte
26 : prefix []byte
27 : iter internalIterator
28 : level int
29 : batch *Batch
30 : mem flushableList
31 : l0 []manifest.LevelSlice
32 : version *version
33 : iterKV *base.InternalKV
34 : // tombstoned and tombstonedSeqNum track whether the key has been deleted by
35 : // a range delete tombstone. The first visible (at getIter.snapshot) range
36 : // deletion encounterd transitions tombstoned to true. The tombstonedSeqNum
37 : // field is updated to hold the sequence number of the tombstone.
38 : tombstoned bool
39 : tombstonedSeqNum uint64
40 : err error
41 : }
42 :
43 : // TODO(sumeer): CockroachDB code doesn't use getIter, but, for completeness,
44 : // make this implement InternalIteratorWithStats.
45 :
46 : // getIter implements the base.InternalIterator interface.
47 : var _ base.InternalIterator = (*getIter)(nil)
48 :
49 0 : func (g *getIter) String() string {
50 0 : return fmt.Sprintf("len(l0)=%d, len(mem)=%d, level=%d", len(g.l0), len(g.mem), g.level)
51 0 : }
52 :
53 0 : func (g *getIter) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
54 0 : panic("pebble: SeekGE unimplemented")
55 : }
56 :
57 0 : func (g *getIter) SeekPrefixGE(prefix, key []byte, flags base.SeekGEFlags) *base.InternalKV {
58 0 : return g.SeekPrefixGEStrict(prefix, key, flags)
59 0 : }
60 :
61 0 : func (g *getIter) SeekPrefixGEStrict(prefix, key []byte, flags base.SeekGEFlags) *base.InternalKV {
62 0 : panic("pebble: SeekPrefixGE unimplemented")
63 : }
64 :
65 0 : func (g *getIter) SeekLT(key []byte, flags base.SeekLTFlags) *base.InternalKV {
66 0 : panic("pebble: SeekLT unimplemented")
67 : }
68 :
69 1 : func (g *getIter) First() *base.InternalKV {
70 1 : return g.Next()
71 1 : }
72 :
73 0 : func (g *getIter) Last() *base.InternalKV {
74 0 : panic("pebble: Last unimplemented")
75 : }
76 :
77 1 : func (g *getIter) Next() *base.InternalKV {
78 1 : // If g.iter != nil, we're already iterating through a level. Next. Note
79 1 : // that it's possible the next key within the level is still relevant (eg,
80 1 : // MERGE keys written in the presence of an LSM snapshot).
81 1 : //
82 1 : // NB: We can't perform this Next below, in the for loop, because when we
83 1 : // open an iterator into the next level, we need to seek to the key.
84 1 : if g.iter != nil {
85 1 : g.iterKV = g.iter.Next()
86 1 : if err := g.iter.Error(); err != nil {
87 0 : g.err = err
88 0 : return nil
89 0 : }
90 : }
91 :
92 : // This for loop finds the next internal key in the LSM that is equal to
93 : // g.key, visible at g.snapshot and not shadowed by a range deletion. If it
94 : // exhausts a level, it initializes iterators for the next level.
95 1 : for {
96 1 : if g.iter != nil {
97 1 : if g.iterKV != nil {
98 1 : // Check if the current KV pair is deleted by a range deletion.
99 1 : if g.tombstoned && g.tombstonedSeqNum > g.iterKV.SeqNum() {
100 1 : // We have a range tombstone covering this key. Rather than
101 1 : // return a point or range deletion here, we return nil and
102 1 : // close our internal iterator stopping iteration.
103 1 : g.err = g.iter.Close()
104 1 : g.iter = nil
105 1 : return nil
106 1 : }
107 :
108 : // Is this the correct user key?
109 1 : if g.comparer.Equal(g.key, g.iterKV.K.UserKey) {
110 1 : // If the KV pair is not visible at the get's snapshot,
111 1 : // Next. The level may still contain older keys with the
112 1 : // same user key that are visible.
113 1 : if !g.iterKV.Visible(g.snapshot, base.InternalKeySeqNumMax) {
114 1 : g.iterKV = g.iter.Next()
115 1 : continue
116 : }
117 1 : return g.iterKV
118 : }
119 : }
120 : // We've advanced the iterator passed the desired key. Move on to the
121 : // next memtable / level.
122 1 : g.err = g.iter.Close()
123 1 : g.iter = nil
124 1 : if g.err != nil {
125 1 : return nil
126 1 : }
127 : }
128 : // g.iter == nil; we need to initialize the next iterator.
129 1 : if !g.initializeNextIterator() {
130 1 : return nil
131 1 : }
132 1 : g.iterKV = g.iter.SeekPrefixGE(g.prefix, g.key, base.SeekGEFlagsNone)
133 : }
134 : }
135 :
136 0 : func (g *getIter) Prev() *base.InternalKV {
137 0 : panic("pebble: Prev unimplemented")
138 : }
139 :
140 0 : func (g *getIter) NextPrefix([]byte) *base.InternalKV {
141 0 : panic("pebble: NextPrefix unimplemented")
142 : }
143 :
144 1 : func (g *getIter) Error() error {
145 1 : return g.err
146 1 : }
147 :
148 1 : func (g *getIter) Close() error {
149 1 : if g.iter != nil {
150 1 : if err := g.iter.Close(); err != nil && g.err == nil {
151 0 : g.err = err
152 0 : }
153 1 : g.iter = nil
154 : }
155 1 : return g.err
156 : }
157 :
158 0 : func (g *getIter) SetBounds(lower, upper []byte) {
159 0 : panic("pebble: SetBounds unimplemented")
160 : }
161 :
162 0 : func (g *getIter) SetContext(_ context.Context) {}
163 :
164 1 : func (g *getIter) initializeNextIterator() (ok bool) {
165 1 : // A batch's keys shadow all other keys, so we visit the batch first.
166 1 : if g.batch != nil {
167 1 : if g.batch.index == nil {
168 0 : g.err = ErrNotIndexed
169 0 : g.iterKV = nil
170 0 : return false
171 0 : }
172 1 : g.iter = g.batch.newInternalIter(nil)
173 1 : if !g.maybeSetTombstone(g.batch.newRangeDelIter(nil,
174 1 : // Get always reads the entirety of the batch's history, so no
175 1 : // batch keys should be filtered.
176 1 : base.InternalKeySeqNumMax,
177 1 : )) {
178 0 : return false
179 0 : }
180 1 : g.batch = nil
181 1 : return true
182 : }
183 :
184 : // If we're trying to initialize the next level of the iterator stack but
185 : // have a tombstone from a previous level, it is guaranteed to delete keys
186 : // in lower levels. This key is deleted.
187 1 : if g.tombstoned {
188 1 : return false
189 1 : }
190 :
191 : // Create iterators from memtables from newest to oldest.
192 1 : if n := len(g.mem); n > 0 {
193 1 : m := g.mem[n-1]
194 1 : g.iter = m.newIter(nil)
195 1 : if !g.maybeSetTombstone(m.newRangeDelIter(nil)) {
196 0 : return false
197 0 : }
198 1 : g.mem = g.mem[:n-1]
199 1 : return true
200 : }
201 :
202 : // Visit each sublevel of L0 individually, so that we only need to read
203 : // at most one file per sublevel.
204 1 : if g.level == 0 {
205 1 : // Create iterators from L0 from newest to oldest.
206 1 : if n := len(g.l0); n > 0 {
207 1 : files := g.l0[n-1].Iter()
208 1 : g.l0 = g.l0[:n-1]
209 1 :
210 1 : iter, rangeDelIter, err := g.getSSTableIterators(files, manifest.L0Sublevel(n))
211 1 : if err != nil {
212 1 : g.err = firstError(g.err, err)
213 1 : return false
214 1 : }
215 1 : if !g.maybeSetTombstone(rangeDelIter) {
216 0 : return false
217 0 : }
218 1 : g.iter = iter
219 1 : return true
220 : }
221 : // We've exhausted all the sublevels of L0. Progress to L1.
222 1 : g.level++
223 : }
224 1 : for g.level < numLevels {
225 1 : if g.version.Levels[g.level].Empty() {
226 1 : g.level++
227 1 : continue
228 : }
229 : // Open the next level of the LSM.
230 1 : iter, rangeDelIter, err := g.getSSTableIterators(g.version.Levels[g.level].Iter(), manifest.Level(g.level))
231 1 : if err != nil {
232 0 : g.err = firstError(g.err, err)
233 0 : return false
234 0 : }
235 1 : if !g.maybeSetTombstone(rangeDelIter) {
236 0 : return false
237 0 : }
238 1 : g.level++
239 1 : g.iter = iter
240 1 : return true
241 : }
242 : // We've exhausted all levels of the LSM.
243 1 : return false
244 : }
245 :
246 : // getSSTableIterators returns a point iterator and a range deletion iterator
247 : // for the sstable in files that overlaps with the key g.key. Pebble does not
248 : // split user keys across adjacent sstables within a level, ensuring that at
249 : // most one sstable overlaps g.key.
250 : func (g *getIter) getSSTableIterators(
251 : files manifest.LevelIterator, level manifest.Level,
252 1 : ) (internalIterator, keyspan.FragmentIterator, error) {
253 1 : files = files.Filter(manifest.KeyTypePoint)
254 1 : m := files.SeekGE(g.comparer.Compare, g.key)
255 1 : if m == nil {
256 1 : return emptyIter, nil, nil
257 1 : }
258 : // m is now positioned at the file containing the first point key ≥ `g.key`.
259 : // Does it exist and possibly contain point keys with the user key 'g.key'?
260 1 : if m == nil || !m.HasPointKeys || g.comparer.Compare(m.SmallestPointKey.UserKey, g.key) > 0 {
261 1 : return emptyIter, nil, nil
262 1 : }
263 : // m may possibly contain point (or range deletion) keys relevant to g.key.
264 1 : g.iterOpts.level = level
265 1 : iters, err := g.newIters(context.Background(), m, &g.iterOpts, internalIterOpts{}, iterPointKeys|iterRangeDeletions)
266 1 : if err != nil {
267 1 : return emptyIter, nil, err
268 1 : }
269 1 : return iters.Point(), iters.RangeDeletion(), nil
270 : }
271 :
272 : // maybeSetTombstone updates g.tombstoned[SeqNum] to reflect the presence of a
273 : // range deletion covering g.key, if there are any. It returns true if
274 : // successful, or false if an error occurred and the caller should abort
275 : // iteration.
276 1 : func (g *getIter) maybeSetTombstone(rangeDelIter keyspan.FragmentIterator) (ok bool) {
277 1 : if rangeDelIter == nil {
278 1 : // Nothing to do.
279 1 : return true
280 1 : }
281 : // Find the range deletion that covers the sought key, if any.
282 1 : t, err := keyspan.Get(g.comparer.Compare, rangeDelIter, g.key)
283 1 : if err != nil {
284 0 : g.err = firstError(g.err, err)
285 0 : return false
286 0 : }
287 : // Find the most recent visible range deletion's sequence number. We only
288 : // care about the most recent range deletion that's visible because it's the
289 : // "most powerful."
290 1 : g.tombstonedSeqNum, g.tombstoned = t.LargestVisibleSeqNum(g.snapshot)
291 1 : if g.err = firstError(g.err, rangeDelIter.Close()); g.err != nil {
292 0 : return false
293 0 : }
294 1 : return true
295 : }
|
