compaction.go
compaction.go - Overview
This file defines the compaction process and associated data structures for BadgerDB. It manages key ranges, compaction status, and ensures that compactions do not overlap.
Detailed Documentation
type keyRange
type keyRange struct {
left []byte
right []byte
inf bool
size int64
}
Represents a range of keys, defined by a left boundary, a right boundary, and a flag indicating whether the range is infinite.
left: The left boundary of the key range (inclusive).right: The right boundary of the key range (inclusive).inf: A boolean indicating whether the range is infinite.size: Size of the key range, used for key splits.
func (r keyRange) isEmpty() bool
func (r keyRange) isEmpty() bool
Checks if the keyRange is empty.
Returns:
bool: Returns true if the keyRange is empty, false otherwise.
var infRange keyRange
var infRange = keyRange{inf: true}
Represents an infinite key range.
func (r keyRange) String() string
func (r keyRange) String() string
Returns a string representation of the keyRange.
Returns:
string: String representation of the keyRange.
func (r keyRange) equals(dst keyRange) bool
func (r keyRange) equals(dst keyRange) bool
Checks if the keyRange is equal to another keyRange.
Parameters:
dst: The keyRange to compare with.
Returns:
bool: Returns true if the keyRanges are equal, false otherwise.
func (r *keyRange) extend(kr keyRange)
func (r *keyRange) extend(kr keyRange)
Extends the keyRange to include another keyRange.
Parameters:
kr: The keyRange to extend with.
func (r keyRange) overlapsWith(dst keyRange) bool
func (r keyRange) overlapsWith(dst keyRange) bool
Checks if the keyRange overlaps with another keyRange.
Parameters:
dst: The keyRange to check for overlap with.
Returns:
bool: Returns true if the keyRanges overlap, false otherwise.
func getKeyRange(tables ...*table.Table) keyRange
func getKeyRange(tables ...*table.Table) keyRange
Returns the smallest and the biggest key range in the list of tables.
Parameters:
tables: A variadic list of*table.Table
Returns:
keyRange: The key range representing the smallest and biggest keys in the tables.
type levelCompactStatus
type levelCompactStatus struct {
ranges []keyRange
delSize int64
}
Represents the compaction status of a level.
ranges: A slice of keyRanges that are currently being compacted in this level.delSize: The total size of deleted keys in this level.
func (lcs *levelCompactStatus) debug() string
func (lcs *levelCompactStatus) debug() string
Returns a debug string representing the key ranges of the level compact status.
Returns:
string: Debug string of key ranges.
func (lcs *levelCompactStatus) overlapsWith(dst keyRange) bool
func (lcs *levelCompactStatus) overlapsWith(dst keyRange) bool
Checks if the levelCompactStatus overlaps with a keyRange.
Parameters:
dst: The keyRange to check for overlap with.
Returns:
bool: Returns true if any of the keyRanges in the levelCompactStatus overlap with the input keyRange, false otherwise.
func (lcs *levelCompactStatus) remove(dst keyRange) bool
func (lcs *levelCompactStatus) remove(dst keyRange) bool
Removes a keyRange from the levelCompactStatus.
Parameters:
dst: The keyRange to remove.
Returns:
bool: Returns true if the keyRange was found and removed, false otherwise.
type compactStatus
type compactStatus struct {
sync.RWMutex
levels []*levelCompactStatus
tables map[uint64]struct{}
}
Represents the overall compaction status.
sync.RWMutex: A mutex to protect concurrent access to the compaction status.levels: A slice of levelCompactStatus, one for each level.tables: A map of table IDs that are currently being compacted.
func (cs *compactStatus) overlapsWith(level int, this keyRange) bool
func (cs *compactStatus) overlapsWith(level int, this keyRange) bool
Checks if a keyRange overlaps with the compaction status of a given level.
Parameters:
level: The level to check.this: The keyRange to check for overlap with.
Returns:
bool: Returns true if the keyRange overlaps with the compaction status of the level, false otherwise.
func (cs *compactStatus) delSize(l int) int64
func (cs *compactStatus) delSize(l int) int64
Returns the delete size of a given level.
Parameters:
l: The level to get the delete size from.
Returns:
int64: The delete size of the level.
type thisAndNextLevelRLocked
type thisAndNextLevelRLocked struct{}
Represents a read lock on the current and next level during compaction. It's an empty struct used for signaling.
func (cs *compactStatus) compareAndAdd(_ thisAndNextLevelRLocked, cd compactDef) bool
func (cs *compactStatus) compareAndAdd(_ thisAndNextLevelRLocked, cd compactDef) bool
Atomically checks if a compaction can be run and adds it to the compaction status.
Parameters:
_: An empty struct,thisAndNextLevelRLocked, used for signaling.cd: The compaction definition (compactDef) to add.
Returns:
bool: Returns true if the compaction was successfully added, false otherwise (if there was an overlap).
func (cs *compactStatus) delete(cd compactDef)
func (cs *compactStatus) delete(cd compactDef)
Deletes a compaction from the compaction status.
Parameters:
cd: The compaction definition (compactDef) to delete.
Code Examples
None.