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