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