Line data Source code
1 : // Copyright 2011 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 base // import "github.com/cockroachdb/pebble/internal/base"
6 :
7 : import (
8 : "cmp"
9 : "encoding/binary"
10 : "fmt"
11 : "strconv"
12 : "strings"
13 : )
14 :
15 : const (
16 : // SeqNumZero is the zero sequence number, set by compactions if they can
17 : // guarantee there are no keys underneath an internal key.
18 : SeqNumZero = uint64(0)
19 : // SeqNumStart is the first sequence number assigned to a key. Sequence
20 : // numbers 1-9 are reserved for potential future use.
21 : SeqNumStart = uint64(10)
22 : )
23 :
24 : // InternalKeyKind enumerates the kind of key: a deletion tombstone, a set
25 : // value, a merged value, etc.
26 : type InternalKeyKind uint8
27 :
28 : // These constants are part of the file format, and should not be changed.
29 : const (
30 : InternalKeyKindDelete InternalKeyKind = 0
31 : InternalKeyKindSet InternalKeyKind = 1
32 : InternalKeyKindMerge InternalKeyKind = 2
33 : InternalKeyKindLogData InternalKeyKind = 3
34 : //InternalKeyKindColumnFamilyDeletion InternalKeyKind = 4
35 : //InternalKeyKindColumnFamilyValue InternalKeyKind = 5
36 : //InternalKeyKindColumnFamilyMerge InternalKeyKind = 6
37 :
38 : // InternalKeyKindSingleDelete (SINGLEDEL) is a performance optimization
39 : // solely for compactions (to reduce write amp and space amp). Readers other
40 : // than compactions should treat SINGLEDEL as equivalent to a DEL.
41 : // Historically, it was simpler for readers other than compactions to treat
42 : // SINGLEDEL as equivalent to DEL, but as of the introduction of
43 : // InternalKeyKindSSTableInternalObsoleteBit, this is also necessary for
44 : // correctness.
45 : InternalKeyKindSingleDelete InternalKeyKind = 7
46 : //InternalKeyKindColumnFamilySingleDelete InternalKeyKind = 8
47 : //InternalKeyKindBeginPrepareXID InternalKeyKind = 9
48 : //InternalKeyKindEndPrepareXID InternalKeyKind = 10
49 : //InternalKeyKindCommitXID InternalKeyKind = 11
50 : //InternalKeyKindRollbackXID InternalKeyKind = 12
51 : //InternalKeyKindNoop InternalKeyKind = 13
52 : //InternalKeyKindColumnFamilyRangeDelete InternalKeyKind = 14
53 : InternalKeyKindRangeDelete InternalKeyKind = 15
54 : //InternalKeyKindColumnFamilyBlobIndex InternalKeyKind = 16
55 : //InternalKeyKindBlobIndex InternalKeyKind = 17
56 :
57 : // InternalKeyKindSeparator is a key used for separator / successor keys
58 : // written to sstable block indexes.
59 : //
60 : // NOTE: the RocksDB value has been repurposed. This was done to ensure that
61 : // keys written to block indexes with value "17" (when 17 happened to be the
62 : // max value, and InternalKeyKindMax was therefore set to 17), remain stable
63 : // when new key kinds are supported in Pebble.
64 : InternalKeyKindSeparator InternalKeyKind = 17
65 :
66 : // InternalKeyKindSetWithDelete keys are SET keys that have met with a
67 : // DELETE or SINGLEDEL key in a prior compaction. This key kind is
68 : // specific to Pebble. See
69 : // https://github.com/cockroachdb/pebble/issues/1255.
70 : InternalKeyKindSetWithDelete InternalKeyKind = 18
71 :
72 : // InternalKeyKindRangeKeyDelete removes all range keys within a key range.
73 : // See the internal/rangekey package for more details.
74 : InternalKeyKindRangeKeyDelete InternalKeyKind = 19
75 : // InternalKeyKindRangeKeySet and InternalKeyKindRangeUnset represent
76 : // keys that set and unset values associated with ranges of key
77 : // space. See the internal/rangekey package for more details.
78 : InternalKeyKindRangeKeyUnset InternalKeyKind = 20
79 : InternalKeyKindRangeKeySet InternalKeyKind = 21
80 :
81 : // InternalKeyKindIngestSST is used to distinguish a batch that corresponds to
82 : // the WAL entry for ingested sstables that are added to the flushable
83 : // queue. This InternalKeyKind cannot appear, amongst other key kinds in a
84 : // batch, or in an sstable.
85 : InternalKeyKindIngestSST InternalKeyKind = 22
86 :
87 : // InternalKeyKindDeleteSized keys behave identically to
88 : // InternalKeyKindDelete keys, except that they hold an associated uint64
89 : // value indicating the (len(key)+len(value)) of the shadowed entry the
90 : // tombstone is expected to delete. This value is used to inform compaction
91 : // heuristics, but is not required to be accurate for correctness.
92 : InternalKeyKindDeleteSized InternalKeyKind = 23
93 :
94 : // This maximum value isn't part of the file format. Future extensions may
95 : // increase this value.
96 : //
97 : // When constructing an internal key to pass to DB.Seek{GE,LE},
98 : // internalKeyComparer sorts decreasing by kind (after sorting increasing by
99 : // user key and decreasing by sequence number). Thus, use InternalKeyKindMax,
100 : // which sorts 'less than or equal to' any other valid internalKeyKind, when
101 : // searching for any kind of internal key formed by a certain user key and
102 : // seqNum.
103 : InternalKeyKindMax InternalKeyKind = 23
104 :
105 : // Internal to the sstable format. Not exposed by any sstable iterator.
106 : // Declared here to prevent definition of valid key kinds that set this bit.
107 : InternalKeyKindSSTableInternalObsoleteBit InternalKeyKind = 64
108 : InternalKeyKindSSTableInternalObsoleteMask InternalKeyKind = 191
109 :
110 : // InternalKeyZeroSeqnumMaxTrailer is the largest trailer with a
111 : // zero sequence number.
112 : InternalKeyZeroSeqnumMaxTrailer = uint64(255)
113 :
114 : // A marker for an invalid key.
115 : InternalKeyKindInvalid InternalKeyKind = InternalKeyKindSSTableInternalObsoleteMask
116 :
117 : // InternalKeySeqNumBatch is a bit that is set on batch sequence numbers
118 : // which prevents those entries from being excluded from iteration.
119 : InternalKeySeqNumBatch = uint64(1 << 55)
120 :
121 : // InternalKeySeqNumMax is the largest valid sequence number.
122 : InternalKeySeqNumMax = uint64(1<<56 - 1)
123 :
124 : // InternalKeyRangeDeleteSentinel is the marker for a range delete sentinel
125 : // key. This sequence number and kind are used for the upper stable boundary
126 : // when a range deletion tombstone is the largest key in an sstable. This is
127 : // necessary because sstable boundaries are inclusive, while the end key of a
128 : // range deletion tombstone is exclusive.
129 : InternalKeyRangeDeleteSentinel = (InternalKeySeqNumMax << 8) | uint64(InternalKeyKindRangeDelete)
130 :
131 : // InternalKeyBoundaryRangeKey is the marker for a range key boundary. This
132 : // sequence number and kind are used during interleaved range key and point
133 : // iteration to allow an iterator to stop at range key start keys where
134 : // there exists no point key.
135 : InternalKeyBoundaryRangeKey = (InternalKeySeqNumMax << 8) | uint64(InternalKeyKindRangeKeySet)
136 : )
137 :
138 : // Assert InternalKeyKindSSTableInternalObsoleteBit > InternalKeyKindMax
139 : const _ = uint(InternalKeyKindSSTableInternalObsoleteBit - InternalKeyKindMax - 1)
140 :
141 : var internalKeyKindNames = []string{
142 : InternalKeyKindDelete: "DEL",
143 : InternalKeyKindSet: "SET",
144 : InternalKeyKindMerge: "MERGE",
145 : InternalKeyKindLogData: "LOGDATA",
146 : InternalKeyKindSingleDelete: "SINGLEDEL",
147 : InternalKeyKindRangeDelete: "RANGEDEL",
148 : InternalKeyKindSeparator: "SEPARATOR",
149 : InternalKeyKindSetWithDelete: "SETWITHDEL",
150 : InternalKeyKindRangeKeySet: "RANGEKEYSET",
151 : InternalKeyKindRangeKeyUnset: "RANGEKEYUNSET",
152 : InternalKeyKindRangeKeyDelete: "RANGEKEYDEL",
153 : InternalKeyKindIngestSST: "INGESTSST",
154 : InternalKeyKindDeleteSized: "DELSIZED",
155 : InternalKeyKindInvalid: "INVALID",
156 : }
157 :
158 2 : func (k InternalKeyKind) String() string {
159 2 : if int(k) < len(internalKeyKindNames) {
160 2 : return internalKeyKindNames[k]
161 2 : }
162 0 : return fmt.Sprintf("UNKNOWN:%d", k)
163 : }
164 :
165 : // InternalKey is a key used for the in-memory and on-disk partial DBs that
166 : // make up a pebble DB.
167 : //
168 : // It consists of the user key (as given by the code that uses package pebble)
169 : // followed by 8-bytes of metadata:
170 : // - 1 byte for the type of internal key: delete or set,
171 : // - 7 bytes for a uint56 sequence number, in little-endian format.
172 : type InternalKey struct {
173 : UserKey []byte
174 : Trailer uint64
175 : }
176 :
177 : // InvalidInternalKey is an invalid internal key for which Valid() will return
178 : // false.
179 : var InvalidInternalKey = MakeInternalKey(nil, 0, InternalKeyKindInvalid)
180 :
181 : // MakeInternalKey constructs an internal key from a specified user key,
182 : // sequence number and kind.
183 2 : func MakeInternalKey(userKey []byte, seqNum uint64, kind InternalKeyKind) InternalKey {
184 2 : return InternalKey{
185 2 : UserKey: userKey,
186 2 : Trailer: (seqNum << 8) | uint64(kind),
187 2 : }
188 2 : }
189 :
190 : // MakeTrailer constructs an internal key trailer from the specified sequence
191 : // number and kind.
192 2 : func MakeTrailer(seqNum uint64, kind InternalKeyKind) uint64 {
193 2 : return (seqNum << 8) | uint64(kind)
194 2 : }
195 :
196 : // MakeSearchKey constructs an internal key that is appropriate for searching
197 : // for a the specified user key. The search key contain the maximal sequence
198 : // number and kind ensuring that it sorts before any other internal keys for
199 : // the same user key.
200 2 : func MakeSearchKey(userKey []byte) InternalKey {
201 2 : return InternalKey{
202 2 : UserKey: userKey,
203 2 : Trailer: (InternalKeySeqNumMax << 8) | uint64(InternalKeyKindMax),
204 2 : }
205 2 : }
206 :
207 : // MakeRangeDeleteSentinelKey constructs an internal key that is a range
208 : // deletion sentinel key, used as the upper boundary for an sstable when a
209 : // range deletion is the largest key in an sstable.
210 2 : func MakeRangeDeleteSentinelKey(userKey []byte) InternalKey {
211 2 : return InternalKey{
212 2 : UserKey: userKey,
213 2 : Trailer: InternalKeyRangeDeleteSentinel,
214 2 : }
215 2 : }
216 :
217 : // MakeExclusiveSentinelKey constructs an internal key that is an
218 : // exclusive sentinel key, used as the upper boundary for an sstable
219 : // when a ranged key is the largest key in an sstable.
220 2 : func MakeExclusiveSentinelKey(kind InternalKeyKind, userKey []byte) InternalKey {
221 2 : return InternalKey{
222 2 : UserKey: userKey,
223 2 : Trailer: (InternalKeySeqNumMax << 8) | uint64(kind),
224 2 : }
225 2 : }
226 :
227 : var kindsMap = map[string]InternalKeyKind{
228 : "DEL": InternalKeyKindDelete,
229 : "SINGLEDEL": InternalKeyKindSingleDelete,
230 : "RANGEDEL": InternalKeyKindRangeDelete,
231 : "LOGDATA": InternalKeyKindLogData,
232 : "SET": InternalKeyKindSet,
233 : "MERGE": InternalKeyKindMerge,
234 : "INVALID": InternalKeyKindInvalid,
235 : "SEPARATOR": InternalKeyKindSeparator,
236 : "SETWITHDEL": InternalKeyKindSetWithDelete,
237 : "RANGEKEYSET": InternalKeyKindRangeKeySet,
238 : "RANGEKEYUNSET": InternalKeyKindRangeKeyUnset,
239 : "RANGEKEYDEL": InternalKeyKindRangeKeyDelete,
240 : "INGESTSST": InternalKeyKindIngestSST,
241 : "DELSIZED": InternalKeyKindDeleteSized,
242 : }
243 :
244 : // ParseInternalKey parses the string representation of an internal key. The
245 : // format is <user-key>.<kind>.<seq-num>. If the seq-num starts with a "b" it
246 : // is marked as a batch-seq-num (i.e. the InternalKeySeqNumBatch bit is set).
247 1 : func ParseInternalKey(s string) InternalKey {
248 1 : x := strings.Split(s, ".")
249 1 : ukey := x[0]
250 1 : kind, ok := kindsMap[x[1]]
251 1 : if !ok {
252 0 : panic(fmt.Sprintf("unknown kind: %q", x[1]))
253 : }
254 1 : j := 0
255 1 : if x[2][0] == 'b' {
256 1 : j = 1
257 1 : }
258 1 : seqNum, _ := strconv.ParseUint(x[2][j:], 10, 64)
259 1 : if x[2][0] == 'b' {
260 1 : seqNum |= InternalKeySeqNumBatch
261 1 : }
262 1 : return MakeInternalKey([]byte(ukey), seqNum, kind)
263 : }
264 :
265 : // ParseKind parses the string representation of an internal key kind.
266 1 : func ParseKind(s string) InternalKeyKind {
267 1 : kind, ok := kindsMap[s]
268 1 : if !ok {
269 0 : panic(fmt.Sprintf("unknown kind: %q", s))
270 : }
271 1 : return kind
272 : }
273 :
274 : // InternalTrailerLen is the number of bytes used to encode InternalKey.Trailer.
275 : const InternalTrailerLen = 8
276 :
277 : // DecodeInternalKey decodes an encoded internal key. See InternalKey.Encode().
278 2 : func DecodeInternalKey(encodedKey []byte) InternalKey {
279 2 : n := len(encodedKey) - InternalTrailerLen
280 2 : var trailer uint64
281 2 : if n >= 0 {
282 2 : trailer = binary.LittleEndian.Uint64(encodedKey[n:])
283 2 : encodedKey = encodedKey[:n:n]
284 2 : } else {
285 2 : trailer = uint64(InternalKeyKindInvalid)
286 2 : encodedKey = nil
287 2 : }
288 2 : return InternalKey{
289 2 : UserKey: encodedKey,
290 2 : Trailer: trailer,
291 2 : }
292 : }
293 :
294 : // InternalCompare compares two internal keys using the specified comparison
295 : // function. For equal user keys, internal keys compare in descending sequence
296 : // number order. For equal user keys and sequence numbers, internal keys
297 : // compare in descending kind order (this may happen in practice among range
298 : // keys).
299 2 : func InternalCompare(userCmp Compare, a, b InternalKey) int {
300 2 : if x := userCmp(a.UserKey, b.UserKey); x != 0 {
301 2 : return x
302 2 : }
303 : // Reverse order for trailer comparison.
304 2 : return cmp.Compare(b.Trailer, a.Trailer)
305 : }
306 :
307 : // Encode encodes the receiver into the buffer. The buffer must be large enough
308 : // to hold the encoded data. See InternalKey.Size().
309 2 : func (k InternalKey) Encode(buf []byte) {
310 2 : i := copy(buf, k.UserKey)
311 2 : binary.LittleEndian.PutUint64(buf[i:], k.Trailer)
312 2 : }
313 :
314 : // EncodeTrailer returns the trailer encoded to an 8-byte array.
315 2 : func (k InternalKey) EncodeTrailer() [8]byte {
316 2 : var buf [8]byte
317 2 : binary.LittleEndian.PutUint64(buf[:], k.Trailer)
318 2 : return buf
319 2 : }
320 :
321 : // Separator returns a separator key such that k <= x && x < other, where less
322 : // than is consistent with the Compare function. The buf parameter may be used
323 : // to store the returned InternalKey.UserKey, though it is valid to pass a
324 : // nil. See the Separator type for details on separator keys.
325 : func (k InternalKey) Separator(
326 : cmp Compare, sep Separator, buf []byte, other InternalKey,
327 2 : ) InternalKey {
328 2 : buf = sep(buf, k.UserKey, other.UserKey)
329 2 : if len(buf) <= len(k.UserKey) && cmp(k.UserKey, buf) < 0 {
330 2 : // The separator user key is physically shorter than k.UserKey (if it is
331 2 : // longer, we'll continue to use "k"), but logically after. Tack on the max
332 2 : // sequence number to the shortened user key. Note that we could tack on
333 2 : // any sequence number and kind here to create a valid separator key. We
334 2 : // use the max sequence number to match the behavior of LevelDB and
335 2 : // RocksDB.
336 2 : return MakeInternalKey(buf, InternalKeySeqNumMax, InternalKeyKindSeparator)
337 2 : }
338 2 : return k
339 : }
340 :
341 : // Successor returns a successor key such that k <= x. A simple implementation
342 : // may return k unchanged. The buf parameter may be used to store the returned
343 : // InternalKey.UserKey, though it is valid to pass a nil.
344 2 : func (k InternalKey) Successor(cmp Compare, succ Successor, buf []byte) InternalKey {
345 2 : buf = succ(buf, k.UserKey)
346 2 : if len(buf) <= len(k.UserKey) && cmp(k.UserKey, buf) < 0 {
347 2 : // The successor user key is physically shorter that k.UserKey (if it is
348 2 : // longer, we'll continue to use "k"), but logically after. Tack on the max
349 2 : // sequence number to the shortened user key. Note that we could tack on
350 2 : // any sequence number and kind here to create a valid separator key. We
351 2 : // use the max sequence number to match the behavior of LevelDB and
352 2 : // RocksDB.
353 2 : return MakeInternalKey(buf, InternalKeySeqNumMax, InternalKeyKindSeparator)
354 2 : }
355 2 : return k
356 : }
357 :
358 : // Size returns the encoded size of the key.
359 2 : func (k InternalKey) Size() int {
360 2 : return len(k.UserKey) + 8
361 2 : }
362 :
363 : // SetSeqNum sets the sequence number component of the key.
364 2 : func (k *InternalKey) SetSeqNum(seqNum uint64) {
365 2 : k.Trailer = (seqNum << 8) | (k.Trailer & 0xff)
366 2 : }
367 :
368 : // SeqNum returns the sequence number component of the key.
369 2 : func (k InternalKey) SeqNum() uint64 {
370 2 : return k.Trailer >> 8
371 2 : }
372 :
373 : // Visible returns true if the key is visible at the specified snapshot
374 : // sequence number.
375 2 : func (k InternalKey) Visible(snapshot, batchSnapshot uint64) bool {
376 2 : return Visible(k.SeqNum(), snapshot, batchSnapshot)
377 2 : }
378 :
379 : // Visible returns true if a key with the provided sequence number is visible at
380 : // the specified snapshot sequence numbers.
381 2 : func Visible(seqNum uint64, snapshot, batchSnapshot uint64) bool {
382 2 : // There are two snapshot sequence numbers, one for committed keys and one
383 2 : // for batch keys. If a seqNum is less than `snapshot`, then seqNum
384 2 : // corresponds to a committed key that is visible. If seqNum has its batch
385 2 : // bit set, then seqNum corresponds to an uncommitted batch key. Its
386 2 : // visible if its snapshot is less than batchSnapshot.
387 2 : //
388 2 : // There's one complication. The maximal sequence number
389 2 : // (`InternalKeySeqNumMax`) is used across Pebble for exclusive sentinel
390 2 : // keys and other purposes. The maximal sequence number has its batch bit
391 2 : // set, but it can never be < `batchSnapshot`, since there is no expressible
392 2 : // larger snapshot. We dictate that the maximal sequence number is always
393 2 : // visible.
394 2 : return seqNum < snapshot ||
395 2 : ((seqNum&InternalKeySeqNumBatch) != 0 && seqNum < batchSnapshot) ||
396 2 : seqNum == InternalKeySeqNumMax
397 2 : }
398 :
399 : // SetKind sets the kind component of the key.
400 2 : func (k *InternalKey) SetKind(kind InternalKeyKind) {
401 2 : k.Trailer = (k.Trailer &^ 0xff) | uint64(kind)
402 2 : }
403 :
404 : // Kind returns the kind component of the key.
405 2 : func (k InternalKey) Kind() InternalKeyKind {
406 2 : return TrailerKind(k.Trailer)
407 2 : }
408 :
409 : // TrailerKind returns the key kind of the key trailer.
410 2 : func TrailerKind(trailer uint64) InternalKeyKind {
411 2 : return InternalKeyKind(trailer & 0xff)
412 2 : }
413 :
414 : // Valid returns true if the key has a valid kind.
415 1 : func (k InternalKey) Valid() bool {
416 1 : return k.Kind() <= InternalKeyKindMax
417 1 : }
418 :
419 : // Clone clones the storage for the UserKey component of the key.
420 2 : func (k InternalKey) Clone() InternalKey {
421 2 : if len(k.UserKey) == 0 {
422 1 : return k
423 1 : }
424 2 : return InternalKey{
425 2 : UserKey: append([]byte(nil), k.UserKey...),
426 2 : Trailer: k.Trailer,
427 2 : }
428 : }
429 :
430 : // CopyFrom converts this InternalKey into a clone of the passed-in InternalKey,
431 : // reusing any space already used for the current UserKey.
432 1 : func (k *InternalKey) CopyFrom(k2 InternalKey) {
433 1 : k.UserKey = append(k.UserKey[:0], k2.UserKey...)
434 1 : k.Trailer = k2.Trailer
435 1 : }
436 :
437 : // String returns a string representation of the key.
438 2 : func (k InternalKey) String() string {
439 2 : return fmt.Sprintf("%s#%d,%d", FormatBytes(k.UserKey), k.SeqNum(), k.Kind())
440 2 : }
441 :
442 : // Pretty returns a formatter for the key.
443 2 : func (k InternalKey) Pretty(f FormatKey) fmt.Formatter {
444 2 : return prettyInternalKey{k, f}
445 2 : }
446 :
447 : // IsExclusiveSentinel returns whether this internal key excludes point keys
448 : // with the same user key if used as an end boundary. See the comment on
449 : // InternalKeyRangeDeletionSentinel.
450 2 : func (k InternalKey) IsExclusiveSentinel() bool {
451 2 : switch kind := k.Kind(); kind {
452 2 : case InternalKeyKindRangeDelete:
453 2 : return k.Trailer == InternalKeyRangeDeleteSentinel
454 2 : case InternalKeyKindRangeKeyDelete, InternalKeyKindRangeKeyUnset, InternalKeyKindRangeKeySet:
455 2 : return (k.Trailer >> 8) == InternalKeySeqNumMax
456 2 : default:
457 2 : return false
458 : }
459 : }
460 :
461 : type prettyInternalKey struct {
462 : InternalKey
463 : formatKey FormatKey
464 : }
465 :
466 2 : func (k prettyInternalKey) Format(s fmt.State, c rune) {
467 2 : if seqNum := k.SeqNum(); seqNum == InternalKeySeqNumMax {
468 2 : fmt.Fprintf(s, "%s#inf,%s", k.formatKey(k.UserKey), k.Kind())
469 2 : } else {
470 2 : fmt.Fprintf(s, "%s#%d,%s", k.formatKey(k.UserKey), k.SeqNum(), k.Kind())
471 2 : }
472 : }
473 :
474 : // ParsePrettyInternalKey parses the pretty string representation of an
475 : // internal key. The format is <user-key>#<seq-num>,<kind>.
476 1 : func ParsePrettyInternalKey(s string) InternalKey {
477 1 : x := strings.FieldsFunc(s, func(c rune) bool { return c == '#' || c == ',' })
478 1 : ukey := x[0]
479 1 : kind, ok := kindsMap[x[2]]
480 1 : if !ok {
481 0 : panic(fmt.Sprintf("unknown kind: %q", x[2]))
482 : }
483 1 : var seqNum uint64
484 1 : if x[1] == "max" || x[1] == "inf" {
485 1 : seqNum = InternalKeySeqNumMax
486 1 : } else {
487 1 : seqNum, _ = strconv.ParseUint(x[1], 10, 64)
488 1 : }
489 1 : return MakeInternalKey([]byte(ukey), seqNum, kind)
490 : }
|
