Documentation
¶
Overview ¶
Package dbformat provides the internal key format used by RocksDB.
This package implements the InternalKey encoding which consists of: - User key (arbitrary bytes) - 8-byte trailer: (sequence_number << 8) | value_type
The format is bit-compatible with RocksDB's db/dbformat.h.
Reference: RocksDB v10.7.5
- db/dbformat.h
- db/dbformat.cc
Index ¶
- Constants
- Variables
- func AppendInternalKey(dst []byte, key *ParsedInternalKey) []byte
- func BytewiseCompare(a, b []byte) int
- func CompareInternalKeys(a, b []byte) int
- func ExtractUserKey(internalKey []byte) []byte
- func IsExtendedValueType(t ValueType) bool
- func IsValueType(t ValueType) bool
- func PackSequenceAndType(seq SequenceNumber, t ValueType) uint64
- func UnpackSequenceAndType(packed uint64) (SequenceNumber, ValueType)
- func UpdateInternalKey(key *InternalKey, seq SequenceNumber, t ValueType)
- type InternalKey
- type InternalKeyComparator
- type ParsedInternalKey
- type SequenceNumber
- type UserKeyComparer
- type ValueType
Constants ¶
const NumInternalBytes = 8
NumInternalBytes is the size of the internal key trailer (sequence + type).
const ValueTypeForSeek = TypeValuePreferredSeqno
ValueTypeForSeek is used when seeking to find a specific user key. We seek to the key with the largest possible sequence number and value type. Reference: RocksDB v10.7.5 db/dbformat.cc line 28:
const ValueType kValueTypeForSeek = kTypeValuePreferredSeqno;
const ValueTypeForSeekForPrev = TypeDeletion
ValueTypeForSeekForPrev is similar but for reverse seeking.
Variables ¶
var ( // ErrCorruptedKey is returned when an internal key is malformed. ErrCorruptedKey = errors.New("dbformat: corrupted internal key") // ErrKeyTooSmall is returned when an internal key is smaller than the trailer. ErrKeyTooSmall = errors.New("dbformat: internal key too small") // ErrInvalidValueType is returned when the value type is not recognized. ErrInvalidValueType = errors.New("dbformat: invalid value type") )
var DefaultInternalKeyComparator = NewInternalKeyComparator(BytewiseCompare)
DefaultInternalKeyComparator is the default comparator using bytewise user key ordering.
Functions ¶
func AppendInternalKey ¶
func AppendInternalKey(dst []byte, key *ParsedInternalKey) []byte
AppendInternalKey appends the serialization of key to dst.
func BytewiseCompare ¶ added in v0.1.3
BytewiseCompare is the default user key comparer (lexicographic ordering).
func CompareInternalKeys ¶ added in v0.1.3
CompareInternalKeys is a convenience function using the default bytewise comparator. This is the most common case and maintains backward compatibility.
func ExtractUserKey ¶
ExtractUserKey returns the user key portion of an internal key. REQUIRES: len(internalKey) >= NumInternalBytes
func IsExtendedValueType ¶
IsExtendedValueType includes types from user operations plus range deletion.
func IsValueType ¶
IsValueType returns true if t is a valid inline value type (i.e., a type used in memtable skiplist and SST file datablock).
func PackSequenceAndType ¶
func PackSequenceAndType(seq SequenceNumber, t ValueType) uint64
PackSequenceAndType packs a sequence number and value type into a 64-bit value. The sequence number occupies the upper 56 bits, the type occupies the lower 8 bits.
func UnpackSequenceAndType ¶
func UnpackSequenceAndType(packed uint64) (SequenceNumber, ValueType)
UnpackSequenceAndType extracts the sequence number and value type from a packed 64-bit value.
func UpdateInternalKey ¶
func UpdateInternalKey(key *InternalKey, seq SequenceNumber, t ValueType)
UpdateInternalKey updates an internal key's sequence number and type in place. REQUIRES: the key must be valid and have space for the trailer.
Types ¶
type InternalKey ¶
type InternalKey []byte
InternalKey is an encoded internal key stored as a byte slice.
func NewInternalKey ¶
func NewInternalKey(userKey []byte, seq SequenceNumber, t ValueType) InternalKey
NewInternalKey creates a new internal key from user key, sequence, and type.
func (InternalKey) Parse ¶
func (k InternalKey) Parse() (*ParsedInternalKey, error)
Parse returns the parsed internal key.
func (InternalKey) Sequence ¶
func (k InternalKey) Sequence() SequenceNumber
Sequence returns the sequence number.
func (InternalKey) UserKey ¶
func (k InternalKey) UserKey() []byte
UserKey returns the user key portion.
func (InternalKey) Valid ¶
func (k InternalKey) Valid() bool
Valid returns true if this is a valid internal key.
type InternalKeyComparator ¶ added in v0.1.3
type InternalKeyComparator struct {
// contains filtered or unexported fields
}
InternalKeyComparator compares internal keys.
Internal key format: user_key + 8-byte trailer (sequence << 8 | type)
Comparison order (matching C++ RocksDB):
- User key (ascending, using the wrapped user comparator)
- Sequence number (descending - higher comes first)
- Value type (descending - higher comes first)
Since sequence and type are packed as (seq << 8 | type), comparing the packed trailer in descending order handles both.
Reference: RocksDB v10.7.5 db/dbformat.h InternalKeyComparator::Compare
func NewInternalKeyComparator ¶ added in v0.1.3
func NewInternalKeyComparator(userCompare UserKeyComparer) *InternalKeyComparator
NewInternalKeyComparator creates a new InternalKeyComparator with the given user key comparison function.
func (*InternalKeyComparator) Compare ¶ added in v0.1.3
func (c *InternalKeyComparator) Compare(a, b []byte) int
Compare compares two internal keys. Returns negative if a < b, positive if a > b, zero if equal.
func (*InternalKeyComparator) CompareUserKey ¶ added in v0.1.3
func (c *InternalKeyComparator) CompareUserKey(a, b []byte) int
CompareUserKey compares just the user key portion of two internal keys.
func (*InternalKeyComparator) UserCompare ¶ added in v0.1.3
func (c *InternalKeyComparator) UserCompare() UserKeyComparer
UserCompare returns the user key comparison function.
type ParsedInternalKey ¶
type ParsedInternalKey struct {
UserKey []byte
Sequence SequenceNumber
Type ValueType
}
ParsedInternalKey represents a parsed internal key.
func ParseInternalKey ¶
func ParseInternalKey(data []byte) (*ParsedInternalKey, error)
ParseInternalKey parses an internal key from data. Returns an error if the key is corrupted.
func (*ParsedInternalKey) DebugString ¶
func (p *ParsedInternalKey) DebugString() string
DebugString returns a debug string representation of the parsed internal key.
func (*ParsedInternalKey) EncodedLength ¶
func (p *ParsedInternalKey) EncodedLength() int
EncodedLength returns the length of the encoded internal key.
func (*ParsedInternalKey) String ¶
func (p *ParsedInternalKey) String() string
String returns a human-readable representation.
type SequenceNumber ¶
type SequenceNumber uint64
SequenceNumber is a 56-bit sequence number (stored in upper 56 bits of 64-bit trailer).
const DisableGlobalSequenceNumber SequenceNumber = ^SequenceNumber(0)
DisableGlobalSequenceNumber is a special value indicating no global sequence override.
const MaxSequenceNumber SequenceNumber = (1 << 56) - 1
MaxSequenceNumber is the maximum valid sequence number (2^56 - 1).
func ExtractSequenceNumber ¶
func ExtractSequenceNumber(internalKey []byte) SequenceNumber
ExtractSequenceNumber returns the sequence number from an internal key. REQUIRES: len(internalKey) >= NumInternalBytes
type UserKeyComparer ¶ added in v0.1.3
UserKeyComparer is a function that compares two user keys. Returns negative if a < b, positive if a > b, zero if equal.
type ValueType ¶
type ValueType uint8
ValueType represents the type of a key-value record. These values are embedded in the on-disk format and MUST NOT change.
const ( TypeDeletion ValueType = 0x00 TypeValue ValueType = 0x01 TypeMerge ValueType = 0x02 TypeLogData ValueType = 0x03 // WAL only TypeColumnFamilyDeletion ValueType = 0x04 // WAL only TypeColumnFamilyValue ValueType = 0x05 // WAL only TypeColumnFamilyMerge ValueType = 0x06 // WAL only TypeSingleDeletion ValueType = 0x07 TypeColumnFamilySingleDeletion ValueType = 0x08 // WAL only TypeBeginPrepareXID ValueType = 0x09 // WAL only TypeEndPrepareXID ValueType = 0x0A // WAL only TypeCommitXID ValueType = 0x0B // WAL only TypeRollbackXID ValueType = 0x0C // WAL only TypeNoop ValueType = 0x0D // WAL only TypeColumnFamilyRangeDeletion ValueType = 0x0E // WAL only TypeRangeDeletion ValueType = 0x0F // meta block TypeColumnFamilyBlobIndex ValueType = 0x10 // Blob DB only TypeBlobIndex ValueType = 0x11 // Blob DB only TypeBeginPersistedPrepareXID ValueType = 0x12 // WAL only TypeBeginUnprepareXID ValueType = 0x13 // WAL only TypeDeletionWithTimestamp ValueType = 0x14 TypeCommitXIDAndTimestamp ValueType = 0x15 // WAL only TypeWideColumnEntity ValueType = 0x16 TypeColumnFamilyWideColumnEntity ValueType = 0x17 // WAL only TypeValuePreferredSeqno ValueType = 0x18 TypeColumnFamilyValuePreferredSeqno ValueType = 0x19 // WAL only TypeMaxValid ValueType = 0x1A // Should be after the last valid type TypeMax ValueType = 0x7F // Not used for storing records )
Value types - these are embedded in the on-disk format and must match RocksDB exactly.
func ExtractValueType ¶
ExtractValueType returns the value type from an internal key. REQUIRES: len(internalKey) >= NumInternalBytes
Source Files