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 sstable
6 :
7 : import (
8 : "github.com/cockroachdb/pebble/internal/base"
9 : "github.com/cockroachdb/pebble/internal/invariants"
10 : "github.com/cockroachdb/pebble/internal/keyspan"
11 : "github.com/cockroachdb/pebble/internal/rangedel"
12 : "github.com/cockroachdb/pebble/internal/rangekey"
13 : )
14 :
15 : // fragmentBlockIter wraps a blockIter, implementing the
16 : // keyspan.FragmentIterator interface. It's used for reading range deletion and
17 : // range key blocks.
18 : //
19 : // Range deletions and range keys are fragmented before they're persisted to the
20 : // block. Overlapping fragments have identical bounds. The fragmentBlockIter
21 : // gathers all the fragments with identical bounds within a block and returns a
22 : // single keyspan.Span describing all the keys defined over the span.
23 : //
24 : // # Memory lifetime
25 : //
26 : // A Span returned by fragmentBlockIter is only guaranteed to be stable until
27 : // the next fragmentBlockIter iteration positioning method. A Span's Keys slice
28 : // may be reused, so the user must not assume it's stable.
29 : //
30 : // Blocks holding range deletions and range keys are configured to use a restart
31 : // interval of 1. This provides key stability. The caller may treat the various
32 : // byte slices (start, end, suffix, value) as stable for the lifetime of the
33 : // iterator.
34 : type fragmentBlockIter struct {
35 : blockIter blockIter
36 : keyBuf [2]keyspan.Key
37 : span keyspan.Span
38 : dir int8
39 : closeHook func(i keyspan.FragmentIterator) error
40 :
41 : // elideSameSeqnum, if true, returns only the first-occurring (in forward
42 : // order) Key for each sequence number.
43 : elideSameSeqnum bool
44 : }
45 :
46 1 : func (i *fragmentBlockIter) resetForReuse() fragmentBlockIter {
47 1 : return fragmentBlockIter{blockIter: i.blockIter.resetForReuse()}
48 1 : }
49 :
50 1 : func (i *fragmentBlockIter) decodeSpanKeys(kv *base.InternalKV, internalValue []byte) error {
51 1 : // TODO(jackson): The use of i.span.Keys to accumulate keys across multiple
52 1 : // calls to Decode is too confusing and subtle. Refactor to make it
53 1 : // explicit.
54 1 :
55 1 : // decode the contents of the fragment's value. This always includes at
56 1 : // least the end key: RANGEDELs store the end key directly as the value,
57 1 : // whereas the various range key kinds store are more complicated. The
58 1 : // details of the range key internal value format are documented within the
59 1 : // internal/rangekey package.
60 1 : var err error
61 1 : switch kv.Kind() {
62 1 : case base.InternalKeyKindRangeDelete:
63 1 : i.span = rangedel.Decode(kv.K, internalValue, i.span.Keys)
64 1 : case base.InternalKeyKindRangeKeySet, base.InternalKeyKindRangeKeyUnset, base.InternalKeyKindRangeKeyDelete:
65 1 : i.span, err = rangekey.Decode(kv.K, internalValue, i.span.Keys)
66 0 : default:
67 0 : i.span = keyspan.Span{}
68 0 : err = base.CorruptionErrorf("pebble: corrupt keyspan fragment of kind %d", kv.Kind())
69 : }
70 1 : return err
71 : }
72 :
73 1 : func (i *fragmentBlockIter) elideKeysOfSameSeqNum() {
74 1 : if invariants.Enabled {
75 1 : if !i.elideSameSeqnum || len(i.span.Keys) == 0 {
76 0 : panic("elideKeysOfSameSeqNum called when it should not be")
77 : }
78 : }
79 1 : lastSeqNum := i.span.Keys[0].SeqNum()
80 1 : k := 1
81 1 : for j := 1; j < len(i.span.Keys); j++ {
82 1 : if lastSeqNum != i.span.Keys[j].SeqNum() {
83 1 : lastSeqNum = i.span.Keys[j].SeqNum()
84 1 : i.span.Keys[k] = i.span.Keys[j]
85 1 : k++
86 1 : }
87 : }
88 1 : i.span.Keys = i.span.Keys[:k]
89 : }
90 :
91 : // gatherForward gathers internal keys with identical bounds. Keys defined over
92 : // spans of the keyspace are fragmented such that any overlapping key spans have
93 : // identical bounds. When these spans are persisted to a range deletion or range
94 : // key block, they may be persisted as multiple internal keys in order to encode
95 : // multiple sequence numbers or key kinds.
96 : //
97 : // gatherForward iterates forward, re-combining the fragmented internal keys to
98 : // reconstruct a keyspan.Span that holds all the keys defined over the span.
99 1 : func (i *fragmentBlockIter) gatherForward(kv *base.InternalKV) (*keyspan.Span, error) {
100 1 : i.span = keyspan.Span{}
101 1 : if kv == nil || !i.blockIter.valid() {
102 1 : return nil, nil
103 1 : }
104 : // Use the i.keyBuf array to back the Keys slice to prevent an allocation
105 : // when a span contains few keys.
106 1 : i.span.Keys = i.keyBuf[:0]
107 1 :
108 1 : // Decode the span's end key and individual keys from the value.
109 1 : internalValue := kv.V.InPlaceValue()
110 1 : if err := i.decodeSpanKeys(kv, internalValue); err != nil {
111 0 : return nil, err
112 0 : }
113 1 : prevEnd := i.span.End
114 1 :
115 1 : // There might exist additional internal keys with identical bounds encoded
116 1 : // within the block. Iterate forward, accumulating all the keys with
117 1 : // identical bounds to s.
118 1 : kv = i.blockIter.Next()
119 1 : for kv != nil && i.blockIter.cmp(kv.K.UserKey, i.span.Start) == 0 {
120 1 : internalValue = kv.InPlaceValue()
121 1 : if err := i.decodeSpanKeys(kv, internalValue); err != nil {
122 0 : return nil, err
123 0 : }
124 :
125 : // Since k indicates an equal start key, the encoded end key must
126 : // exactly equal the original end key from the first internal key.
127 : // Overlapping fragments are required to have exactly equal start and
128 : // end bounds.
129 1 : if i.blockIter.cmp(prevEnd, i.span.End) != 0 {
130 0 : i.span = keyspan.Span{}
131 0 : return nil, base.CorruptionErrorf("pebble: corrupt keyspan fragmentation")
132 0 : }
133 1 : kv = i.blockIter.Next()
134 : }
135 1 : if i.elideSameSeqnum && len(i.span.Keys) > 0 {
136 1 : i.elideKeysOfSameSeqNum()
137 1 : }
138 : // i.blockIter is positioned over the first internal key for the next span.
139 1 : return &i.span, nil
140 : }
141 :
142 : // gatherBackward gathers internal keys with identical bounds. Keys defined over
143 : // spans of the keyspace are fragmented such that any overlapping key spans have
144 : // identical bounds. When these spans are persisted to a range deletion or range
145 : // key block, they may be persisted as multiple internal keys in order to encode
146 : // multiple sequence numbers or key kinds.
147 : //
148 : // gatherBackward iterates backwards, re-combining the fragmented internal keys
149 : // to reconstruct a keyspan.Span that holds all the keys defined over the span.
150 1 : func (i *fragmentBlockIter) gatherBackward(kv *base.InternalKV) (*keyspan.Span, error) {
151 1 : i.span = keyspan.Span{}
152 1 : if kv == nil || !i.blockIter.valid() {
153 1 : return nil, nil
154 1 : }
155 : // Use the i.keyBuf array to back the Keys slice to prevent an allocation
156 : // when a span contains few keys.
157 1 : i.span.Keys = i.keyBuf[:0]
158 1 :
159 1 : // Decode the span's end key and individual keys from the value.
160 1 : internalValue := kv.V.InPlaceValue()
161 1 : if err := i.decodeSpanKeys(kv, internalValue); err != nil {
162 0 : return nil, err
163 0 : }
164 1 : prevEnd := i.span.End
165 1 :
166 1 : // There might exist additional internal keys with identical bounds encoded
167 1 : // within the block. Iterate backward, accumulating all the keys with
168 1 : // identical bounds to s.
169 1 : kv = i.blockIter.Prev()
170 1 : for kv != nil && i.blockIter.cmp(kv.K.UserKey, i.span.Start) == 0 {
171 1 : internalValue = kv.V.InPlaceValue()
172 1 : if err := i.decodeSpanKeys(kv, internalValue); err != nil {
173 0 : return nil, err
174 0 : }
175 :
176 : // Since k indicates an equal start key, the encoded end key must
177 : // exactly equal the original end key from the first internal key.
178 : // Overlapping fragments are required to have exactly equal start and
179 : // end bounds.
180 1 : if i.blockIter.cmp(prevEnd, i.span.End) != 0 {
181 0 : i.span = keyspan.Span{}
182 0 : return nil, base.CorruptionErrorf("pebble: corrupt keyspan fragmentation")
183 0 : }
184 1 : kv = i.blockIter.Prev()
185 : }
186 : // i.blockIter is positioned over the last internal key for the previous
187 : // span.
188 :
189 : // Backwards iteration encounters internal keys in the wrong order.
190 1 : keyspan.SortKeysByTrailer(&i.span.Keys)
191 1 :
192 1 : if i.elideSameSeqnum && len(i.span.Keys) > 0 {
193 1 : i.elideKeysOfSameSeqNum()
194 1 : }
195 1 : return &i.span, nil
196 : }
197 :
198 : // Close implements (keyspan.FragmentIterator).Close.
199 1 : func (i *fragmentBlockIter) Close() error {
200 1 : var err error
201 1 : if i.closeHook != nil {
202 0 : err = i.closeHook(i)
203 0 : }
204 1 : err = firstError(err, i.blockIter.Close())
205 1 : return err
206 : }
207 :
208 : // First implements (keyspan.FragmentIterator).First
209 1 : func (i *fragmentBlockIter) First() (*keyspan.Span, error) {
210 1 : i.dir = +1
211 1 : return i.gatherForward(i.blockIter.First())
212 1 : }
213 :
214 : // Last implements (keyspan.FragmentIterator).Last.
215 1 : func (i *fragmentBlockIter) Last() (*keyspan.Span, error) {
216 1 : i.dir = -1
217 1 : return i.gatherBackward(i.blockIter.Last())
218 1 : }
219 :
220 : // Next implements (keyspan.FragmentIterator).Next.
221 1 : func (i *fragmentBlockIter) Next() (*keyspan.Span, error) {
222 1 : switch {
223 1 : case i.dir == -1 && !i.span.Valid():
224 1 : // Switching directions.
225 1 : //
226 1 : // i.blockIter is exhausted, before the first key. Move onto the first.
227 1 : i.blockIter.First()
228 1 : i.dir = +1
229 1 : case i.dir == -1 && i.span.Valid():
230 1 : // Switching directions.
231 1 : //
232 1 : // i.blockIter is currently positioned over the last internal key for
233 1 : // the previous span. Next it once to move to the first internal key
234 1 : // that makes up the current span, and gatherForwaad to land on the
235 1 : // first internal key making up the next span.
236 1 : //
237 1 : // In the diagram below, if the last span returned to the user during
238 1 : // reverse iteration was [b,c), i.blockIter is currently positioned at
239 1 : // [a,b). The block iter must be positioned over [d,e) to gather the
240 1 : // next span's fragments.
241 1 : //
242 1 : // ... [a,b) [b,c) [b,c) [b,c) [d,e) ...
243 1 : // ^ ^
244 1 : // i.blockIter want
245 1 : if x, err := i.gatherForward(i.blockIter.Next()); err != nil {
246 0 : return nil, err
247 1 : } else if invariants.Enabled && !x.Valid() {
248 0 : panic("pebble: invariant violation: next entry unexpectedly invalid")
249 : }
250 1 : i.dir = +1
251 : }
252 : // We know that this blockIter has in-place values.
253 1 : return i.gatherForward(&i.blockIter.ikv)
254 : }
255 :
256 : // Prev implements (keyspan.FragmentIterator).Prev.
257 1 : func (i *fragmentBlockIter) Prev() (*keyspan.Span, error) {
258 1 : switch {
259 1 : case i.dir == +1 && !i.span.Valid():
260 1 : // Switching directions.
261 1 : //
262 1 : // i.blockIter is exhausted, after the last key. Move onto the last.
263 1 : i.blockIter.Last()
264 1 : i.dir = -1
265 1 : case i.dir == +1 && i.span.Valid():
266 1 : // Switching directions.
267 1 : //
268 1 : // i.blockIter is currently positioned over the first internal key for
269 1 : // the next span. Prev it once to move to the last internal key that
270 1 : // makes up the current span, and gatherBackward to land on the last
271 1 : // internal key making up the previous span.
272 1 : //
273 1 : // In the diagram below, if the last span returned to the user during
274 1 : // forward iteration was [b,c), i.blockIter is currently positioned at
275 1 : // [d,e). The block iter must be positioned over [a,b) to gather the
276 1 : // previous span's fragments.
277 1 : //
278 1 : // ... [a,b) [b,c) [b,c) [b,c) [d,e) ...
279 1 : // ^ ^
280 1 : // want i.blockIter
281 1 : if x, err := i.gatherBackward(i.blockIter.Prev()); err != nil {
282 0 : return nil, err
283 1 : } else if invariants.Enabled && !x.Valid() {
284 0 : panic("pebble: invariant violation: previous entry unexpectedly invalid")
285 : }
286 1 : i.dir = -1
287 : }
288 : // We know that this blockIter has in-place values.
289 1 : return i.gatherBackward(&i.blockIter.ikv)
290 : }
291 :
292 : // SeekGE implements (keyspan.FragmentIterator).SeekGE.
293 1 : func (i *fragmentBlockIter) SeekGE(k []byte) (*keyspan.Span, error) {
294 1 : if s, err := i.SeekLT(k); err != nil {
295 0 : return nil, err
296 1 : } else if s != nil && i.blockIter.cmp(k, s.End) < 0 {
297 1 : return s, nil
298 1 : }
299 : // TODO(jackson): If the above i.SeekLT(k) discovers a span but the span
300 : // doesn't meet the k < s.End comparison, then there's no need for the
301 : // SeekLT to gatherBackward.
302 1 : return i.Next()
303 : }
304 :
305 : // SeekLT implements (keyspan.FragmentIterator).SeekLT.
306 1 : func (i *fragmentBlockIter) SeekLT(k []byte) (*keyspan.Span, error) {
307 1 : i.dir = -1
308 1 : return i.gatherBackward(i.blockIter.SeekLT(k, base.SeekLTFlagsNone))
309 1 : }
310 :
311 : // String implements fmt.Stringer.
312 0 : func (i *fragmentBlockIter) String() string {
313 0 : return "fragment-block-iter"
314 0 : }
315 :
316 : // SetCloseHook implements sstable.FragmentIterator.
317 0 : func (i *fragmentBlockIter) SetCloseHook(fn func(i keyspan.FragmentIterator) error) {
318 0 : i.closeHook = fn
319 0 : }
320 :
321 : // WrapChildren implements FragmentIterator.
322 0 : func (i *fragmentBlockIter) WrapChildren(wrap keyspan.WrapFn) {}
|
