Skip to main content

levels.go

levels.go - Overview​

This file defines the levelsController which manages the levels of the LSM tree in BadgerDB. It handles table management, compaction, and data dropping based on prefixes.

Detailed Documentation​

type levelsController​

type levelsController struct {
	nextFileID atomic.Uint64
	l0stallsMs atomic.Int64

	// The following are initialized once and const.
	levels []*levelHandler
	kv     *DB

	cstatus compactStatus
}
  • Purpose: levelsController manages the different levels within the LSM tree, handling compaction, table management, and prefix dropping.
  • Fields:
    • nextFileID: Atomic counter for generating unique file IDs.
    • l0stallsMs: Atomic counter to track L0 stalls in milliseconds.
    • levels: Slice of levelHandler structs, one for each level.
    • kv: Pointer to the DB struct.
    • cstatus: compactStatus struct for managing compaction status.

func revertToManifest​

func revertToManifest(kv *DB, mf *Manifest, idMap map[uint64]struct{}) error
  • Purpose: Checks the existence of table files against the manifest and removes any table files not referenced in the manifest.
  • Parameters:
    • kv: Pointer to the DB struct.
    • mf: Pointer to the Manifest struct.
    • idMap: A map containing the IDs of the table files present in the directory.
  • Returns: An error if any table file listed in the manifest is missing or if removing extraneous files fails. Returns nil on success.

func newLevelsController​

func newLevelsController(db *DB, mf *Manifest) (*levelsController, error)
  • Purpose: Creates a new levelsController and initializes its fields, including loading existing tables from the manifest.
  • Parameters:
    • db: Pointer to the DB struct.
    • mf: Pointer to the Manifest struct.
  • Returns: A pointer to the new levelsController and an error, if any.

func closeAllTables​

func closeAllTables(tables [][]*table.Table)
  • Purpose: Closes all tables in the given slice of slices. Errors during close are ignored.
  • Parameters:
    • tables: A slice of slices containing pointers to table.Table structs.

func (s *levelsController) cleanupLevels​

func (s *levelsController) cleanupLevels() error
  • Purpose: Closes all level handlers.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: An error, if any.

func (s *levelsController) dropTree​

func (s *levelsController) dropTree() (int, error)
  • Purpose: Removes all tables from all levels by creating a manifest change set and decrementing the reference count of the tables, leading to their deletion.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: The number of tables dropped and an error, if any.

func (s *levelsController) dropPrefixes​

func (s *levelsController) dropPrefixes(prefixes [][]byte) error
  • Purpose: Drops keys with specified prefixes from the LSM tree, compacting L0->L1 and Li->Li levels.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • prefixes: A slice of byte slices representing the prefixes to drop.
  • Returns: An error, if any.

func (s *levelsController) startCompact​

func (s *levelsController) startCompact(lc *z.Closer)
  • Purpose: Starts the compaction process by launching multiple compactor goroutines.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • lc: A z.Closer used to manage the lifecycle of the compactor goroutines.

type targets​

type targets struct {
	baseLevel int
	targetSz  []int64
	fileSz    []int64
}
  • Purpose: targets holds the target sizes for each level in the LSM tree.
  • Fields:
    • baseLevel: The base level for compaction.
    • targetSz: Slice of target sizes for each level.
    • fileSz: Slice of file sizes for each level.

func (s *levelsController) levelTargets​

func (s *levelsController) levelTargets() targets
  • Purpose: Calculates the target sizes for each level in the LSM tree based on the size of the last level.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: A targets struct containing target sizes and file sizes for each level.

func (s *levelsController) runCompactor​

func (s *levelsController) runCompactor(id int, lc *z.Closer)
  • Purpose: Runs a compactor goroutine, picking compaction levels and running compactions in a loop.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • id: The ID of the compactor.
    • lc: A z.Closer used to signal when the compactor should exit.

type compactionPriority​

type compactionPriority struct {
	level        int
	score        float64
	adjusted     float64
	dropPrefixes [][]byte
	t            targets
}
  • Purpose: compactionPriority represents the priority of compacting a specific level.
  • Fields:
    • level: The level to compact.
    • score: The initial score for the level.
    • adjusted: The adjusted score after considering other levels.
    • dropPrefixes: Prefixes to drop during compaction.
    • t: targets for the level.

func (s *levelsController) lastLevel​

func (s *levelsController) lastLevel() *levelHandler
  • Purpose: Returns a pointer to the last level handler.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: A pointer to the last levelHandler.

func (s *levelsController) pickCompactLevels​

func (s *levelsController) pickCompactLevels(priosBuffer []compactionPriority) (prios []compactionPriority)
  • Purpose: Determines which level to compact based on the size and target size of each level.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • priosBuffer: A buffer to store compaction priorities, can be nil.
  • Returns: A slice of compactionPriority structs, sorted by adjusted score.

func (s *levelsController) checkOverlap​

func (s *levelsController) checkOverlap(tables []*table.Table, lev int) bool
  • Purpose: Checks if the given tables overlap with any level from the given level onwards.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • tables: A slice of table.Table pointers.
    • lev: The starting level to check for overlap.
  • Returns: true if there is any overlap, false otherwise.

func (s *levelsController) subcompact​

func (s *levelsController) subcompact(it y.Iterator, kr keyRange, cd compactDef,
	inflightBuilders *y.Throttle, res chan<- *table.Table)
  • Purpose: Runs a single sub-compaction over the specified key range.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • it: An iterator for the key range.
    • kr: The key range to compact.
    • cd: The compaction definition.
    • inflightBuilders: A throttle to limit the number of concurrent table builders.
    • res: A channel to send the resulting tables.

func (s *levelsController) compactBuildTables​

func (s *levelsController) compactBuildTables(
	lev int, cd compactDef) ([]*table.Table, func() error, error)
  • Purpose: Merges topTables and botTables to form a list of new tables.
  • Parameters:
    • lev: Level number.
    • cd: Compaction definition.
  • Returns: A slice of new tables, a function to decrement refs on these tables, and an error.

func buildChangeSet​

func buildChangeSet(cd *compactDef, newTables []*table.Table) pb.ManifestChangeSet
  • Purpose: Builds a manifest change set for the given compaction definition and new tables.
  • Parameters:
    • cd: Pointer to a compactDef struct.
    • newTables: A slice of table.Table pointers representing the new tables created during compaction.
  • Returns: A pb.ManifestChangeSet struct containing the changes to be applied to the manifest.

func hasAnyPrefixes​

func hasAnyPrefixes(s []byte, listOfPrefixes [][]byte) bool
  • Purpose: Checks if the given byte slice has any of the prefixes in the list.
  • Parameters:
    • s: The byte slice to check.
    • listOfPrefixes: A list of prefixes.
  • Returns: True if s has any of the prefixes.

func containsPrefix​

func containsPrefix(table *table.Table, prefix []byte) bool
  • Purpose: Determines if the table contains any key with the given prefix.
  • Parameters:
    • table: Pointer to the table.Table struct.
    • prefix: The prefix to check for.
  • Returns: true if the table contains the prefix, false otherwise.

func containsAnyPrefixes​

func containsAnyPrefixes(table *table.Table, listOfPrefixes [][]byte) bool
  • Purpose: Checks if the table contains any of the given prefixes.
  • Parameters:
    • table: Pointer to the table.Table struct.
    • listOfPrefixes: Slice of byte slices representing the prefixes.
  • Returns: True if table contains any of the prefixes

type compactDef​

type compactDef struct {
	compactorId int
	t           targets
	p           compactionPriority
	thisLevel   *levelHandler
	nextLevel   *levelHandler

	top []*table.Table
	bot []*table.Table

	thisRange keyRange
	nextRange keyRange
	splits    []keyRange

	thisSize int64

	dropPrefixes [][]byte
}
  • Purpose: compactDef defines a compaction operation.
  • Fields:
    • compactorId: ID of the compactor performing the compaction.
    • t: targets struct.
    • p: compactionPriority struct.
    • thisLevel: Pointer to the levelHandler for the level being compacted.
    • nextLevel: Pointer to the levelHandler for the next level.
    • top: Tables from the current level being compacted.
    • bot: Tables from the next level being compacted.
    • thisRange: Key range of the current level.
    • nextRange: Key range of the next level.
    • splits: Key ranges for sub-compactions.
    • thisSize: Size of the current level.
    • dropPrefixes: Prefixes to drop during compaction.

func (s *levelsController) addSplits​

func (s *levelsController) addSplits(cd *compactDef)
  • Purpose: Adds splits to the compaction definition based on the bottom tables.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • cd: Pointer to the compactDef struct.

func (cd *compactDef) lockLevels​

func (cd *compactDef) lockLevels()
  • Purpose: Acquires read locks on the thisLevel and nextLevel.
  • Parameters:
    • cd: Pointer to the compactDef struct.

func (cd *compactDef) unlockLevels​

func (cd *compactDef) unlockLevels()
  • Purpose: Releases read locks on the thisLevel and nextLevel.
  • Parameters:
    • cd: Pointer to the compactDef struct.

func (cd *compactDef) allTables​

func (cd *compactDef) allTables() []*table.Table
  • Purpose: Returns a slice containing all top and bottom tables.
  • Parameters:
    • cd: Pointer to the compactDef struct.
  • Returns: A slice of table.Table pointers.

func (s *levelsController) fillTablesL0ToL0​

func (s *levelsController) fillTablesL0ToL0(cd *compactDef) bool
  • Purpose: Fills the compactDef with tables for an L0 to L0 compaction.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • cd: Pointer to the compactDef struct.
  • Returns: true if tables were successfully filled, false otherwise.

func (s *levelsController) fillTablesL0ToLbase​

func (s *levelsController) fillTablesL0ToLbase(cd *compactDef) bool
  • Purpose: Fills the compactDef with tables for an L0 to Lbase compaction.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • cd: Pointer to the compactDef struct.
  • Returns: true if tables were successfully filled, false otherwise.

func (s *levelsController) fillTablesL0​

func (s *levelsController) fillTablesL0(cd *compactDef) bool
  • Purpose: Tries to fill tables for L0 compaction, first attempting L0ToLbase, then L0ToL0.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • cd: Pointer to the compactDef struct.
  • Returns: true if tables were successfully filled, false otherwise.

func (s *levelsController) sortByStaleDataSize​

func (s *levelsController) sortByStaleDataSize(tables []*table.Table, cd *compactDef)
  • Purpose: Sorts the given tables based on the amount of stale data they contain.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • tables: Slice of table.Table pointers.
    • cd: Pointer to the compactDef struct.

func (s *levelsController) sortByHeuristic​

func (s *levelsController) sortByHeuristic(tables []*table.Table, cd *compactDef)
  • Purpose: Sorts tables in increasing order of MaxVersion, so we compact older tables first.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • tables: Slice of table.Table pointers.
    • cd: Pointer to the compactDef struct.

func (s *levelsController) fillMaxLevelTables​

func (s *levelsController) fillMaxLevelTables(tables []*table.Table, cd *compactDef) bool
  • Purpose: Fills tables for compaction at the max level.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • tables: Tables at max level.
    • cd: Compaction definition.
  • Returns: True if able to fill tables.

func (s *levelsController) fillTables​

func (s *levelsController) fillTables(cd *compactDef) bool
  • Purpose: Fills the compactDef with tables to be compacted from thisLevel to nextLevel.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • cd: Pointer to the compactDef struct.
  • Returns: true if the tables were filled successfully, false otherwise.

func (s *levelsController) runCompactDef​

func (s *levelsController) runCompactDef(id, l int, cd compactDef) (err error)
  • Purpose: Executes a compaction defined by the given compactDef.
  • Parameters:
    • id: The ID of the compactor running the compaction.
    • l: The level being compacted.
    • cd: The compaction definition.
  • Returns: An error, if any.

func tablesToString​

func tablesToString(tables []*table.Table) []string
  • Purpose: Converts a slice of tables to a slice of strings, representing their IDs.
  • Parameters:
    • tables: Slice of table.Table pointers.
  • Returns: A slice of strings containing the formatted table IDs.

var errFillTables​

var errFillTables = errors.New("Unable to fill tables")
  • Purpose: Error returned when unable to fill tables for compaction.

func (s *levelsController) doCompact​

func (s *levelsController) doCompact(id int, p compactionPriority) error
  • Purpose: Performs a compaction operation for a given level.
  • Parameters:
    • id: The ID of the compactor.
    • p: The compaction priority.
  • Returns: An error, if any.

func (s *levelsController) addLevel0Table​

func (s *levelsController) addLevel0Table(t *table.Table) error
  • Purpose: Adds a table to level 0.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • t: Pointer to the table.Table struct.
  • Returns: An error, if any.

func (s *levelsController) close​

func (s *levelsController) close() error
  • Purpose: Closes the levels controller, cleaning up all levels.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: An error, if any.

func (s *levelsController) get​

func (s *levelsController) get(key []byte, maxVs y.ValueStruct, startLevel int) (
	y.ValueStruct, error)
  • Purpose: Searches for a given key in all levels of the LSM tree.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • key: The key to search for.
    • maxVs: Maximum value struct.
    • startLevel: The level to start searching from.
  • Returns: A y.ValueStruct and an error, if any.

func appendIteratorsReversed​

func appendIteratorsReversed(out []y.Iterator, th []*table.Table, opt int) []y.Iterator
  • Purpose: Appends iterators for the given tables in reversed order.
  • Parameters:
    • out: Slice to append the iterators to.
    • th: Slice of table.Table pointers.
    • opt: Iterator option.
  • Returns: The slice with appended iterators.

func (s *levelsController) appendIterators​

func (s *levelsController) appendIterators(
	iters []y.Iterator, opt *IteratorOptions) []y.Iterator
  • Purpose: Appends iterators for all levels to the given slice of iterators.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • iters: The slice of iterators to append to.
    • opt: Iterator options.
  • Returns: The slice of iterators with the new iterators appended.

type TableInfo​

type TableInfo struct {
	ID               uint64
	Level            int
	Left             []byte
	Right            []byte
	KeyCount         uint32 // Number of keys in the table
	OnDiskSize       uint32
	StaleDataSize    uint32
	UncompressedSize uint32
	MaxVersion       uint64
	IndexSz          int
	BloomFilterSize  int
}
  • Purpose: TableInfo represents information about a table.
  • Fields:
    • ID: Table ID.
    • Level: Level of table.
    • Left: Smallest key in table.
    • Right: Largest key in table.
    • KeyCount: Number of keys in the table.
    • OnDiskSize: On disk size.
    • StaleDataSize: Stale data size.
    • UncompressedSize: Uncompressed size.
    • MaxVersion: Max version.
    • IndexSz: Index size.
    • BloomFilterSize: Bloom filter size.

func (s *levelsController) getTableInfo​

func (s *levelsController) getTableInfo() (result []TableInfo)
  • Purpose: Retrieves information about all tables in the LSM tree.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: A slice of TableInfo structs.

type LevelInfo​

type LevelInfo struct {
	Level          int
	NumTables      int
	Size           int64
	TargetSize     int64
	TargetFileSize int64
	IsBaseLevel    bool
	Score          float64
	Adjusted       float64
	StaleDatSize   int64
}
  • Purpose: LevelInfo stores statistics about each level in LSM tree.
  • Fields:
    • Level: level number.
    • NumTables: number of tables.
    • Size: Total size.
    • TargetSize: Target Size of this level.
    • TargetFileSize: Max table file size.
    • IsBaseLevel: indicates base level.
    • Score: compaction score.
    • Adjusted: Adjusted compaction score.
    • StaleDatSize: Stale Data Size of this level.

func (s *levelsController) getLevelInfo​

func (s *levelsController) getLevelInfo() []LevelInfo
  • Purpose: Retrieves information about each level in the LSM tree.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: A slice of LevelInfo structs.

func (s *levelsController) verifyChecksum​

func (s *levelsController) verifyChecksum() error
  • Purpose: Verifies checksum for all tables on all levels.
  • Parameters:
    • s: Pointer to the levelsController struct.
  • Returns: An error, if any.

func (s *levelsController) keySplits​

func (s *levelsController) keySplits(numPerTable int, prefix []byte) []string
  • Purpose: Returns the sorted list of splits for all the levels and tables based on the block offsets.
  • Parameters:
    • s: Pointer to the levelsController struct.
    • numPerTable: Number of key splits per table.
    • prefix: A byte array.
  • Returns: A slice of strings.

Getting Started Relevance​