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