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