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