manifest

package
v0.0.0-...-74fe3af Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 18, 2025 License: BSD-3-Clause Imports: 28 Imported by: 0

Documentation

Index

Constants

View Source 
const NumLevels = 7

NumLevels is the number of levels a Version contains.

Variables

View Source 
var NumFilesAnnotator = SumAnnotator(func(f *TableMetadata) (uint64, bool) {
	return 1, true
})

NumFilesAnnotator is an Annotator which computes an annotation value equal to the number of files included in the annotation. Particularly, it can be used to efficiently calculate the number of files in a given key range using range annotations.

Functions

func CheckOrdering 

func CheckOrdering(cmp Compare, format base.FormatKey, level Layer, files LevelIterator) error

CheckOrdering checks that the files are consistent with respect to seqnums (for level 0 files -- see detailed comment below) and increasing and non- overlapping internal key ranges (for non-level 0 files).

func SortBySeqNum 

func SortBySeqNum(files []*TableMetadata)

SortBySeqNum sorts the specified files by increasing sequence number.

func SortBySmallest 

func SortBySmallest(files []*TableMetadata, cmp Compare)

SortBySmallest sorts the specified files by smallest key using the supplied comparison function to order user keys.

Types

type AggregateBlobFileStats 

type AggregateBlobFileStats struct {
	// Count is the number of blob files in the set.
	Count uint64
	// PhysicalSize is the sum of the size of all blob files in the set.  This
	// is the size of the blob files on physical storage. Data within blob files
	// is compressed, so this value may be less than ValueSize.
	PhysicalSize uint64
	// ValueSize is the sum of the length of the uncompressed values in all blob
	// files in the set.
	ValueSize uint64
	// ReferencedValueSize is the sum of the length of the uncompressed values
	// in all blob files in the set that are still referenced by live tables
	// (i.e., in the latest version).
	ReferencedValueSize uint64
	// ReferencesCount is the total number of tracked references in live tables
	// (i.e., in the latest version). When virtual sstables are present, this
	// count is per-virtual sstable (not per backing physical sstable).
	ReferencesCount uint64
}

AggregateBlobFileStats records cumulative stats across blob files.

func (AggregateBlobFileStats) String 

func (s AggregateBlobFileStats) String() string

String implements fmt.Stringer.

type AnnotationAggregator 

type AnnotationAggregator[T any] interface {
	// Zero returns the zero value of an annotation. This value is returned
	// when a LevelMetadata is empty. The dst argument, if non-nil, is an
	// obsolete value previously returned by this Annotator and may be
	// overwritten and reused to avoid a memory allocation.
	Zero(dst *T) *T

	// Accumulate computes the annotation for a single file in a level's
	// metadata. It merges the file's value into dst and returns a bool flag
	// indicating whether or not the value is stable and okay to cache as an
	// annotation. If the file's value may change over the life of the file,
	// the annotator must return false.
	//
	// Implementations may modify dst and return it to avoid an allocation.
	Accumulate(f *TableMetadata, dst *T) (v *T, cacheOK bool)

	// Merge combines two values src and dst, returning the result.
	// Implementations may modify dst and return it to avoid an allocation.
	Merge(src *T, dst *T) *T
}

An AnnotationAggregator defines how an annotation should be accumulated from a single TableMetadata and merged with other annotated values.

type Annotator 

type Annotator[T any] struct {
	Aggregator AnnotationAggregator[T]
}

An Annotator defines a computation over a level's TableMetadata. If the computation is stable and uses inputs that are fixed for the lifetime of a TableMetadata, the LevelMetadata's internal data structures are annotated with the intermediary computations. This allows the computation to be computed incrementally as edits are applied to a level.

func SumAnnotator 

func SumAnnotator(accumulate func(f *TableMetadata) (v uint64, cacheOK bool)) *Annotator[uint64]

SumAnnotator takes a function that computes a uint64 value from a single TableMetadata and returns an Annotator that sums together the values across files.

func (*Annotator[T]) InvalidateLevelAnnotation 

func (a *Annotator[T]) InvalidateLevelAnnotation(lm LevelMetadata)

InvalidateLevelAnnotation clears any cached annotations defined by Annotator. A pointer to the Annotator is used as the key for pre-calculated values, so the same Annotator must be used to clear the appropriate cached annotation. Calls to InvalidateLevelAnnotation are *not* concurrent-safe with any other calls to Annotator methods for the same Annotator (concurrent calls from other annotators are fine). Any calls to this function must have some externally-guaranteed mutual exclusion.

func (*Annotator[T]) LevelAnnotation 

func (a *Annotator[T]) LevelAnnotation(lm LevelMetadata) *T

LevelAnnotation calculates the annotation defined by this Annotator for all files in the given LevelMetadata. A pointer to the Annotator is used as the key for pre-calculated values, so the same Annotator must be used to avoid duplicate computation.

func (*Annotator[T]) LevelRangeAnnotation 

func (a *Annotator[T]) LevelRangeAnnotation(lm LevelMetadata, bounds base.UserKeyBounds) *T

LevelRangeAnnotation calculates the annotation defined by this Annotator for the files within LevelMetadata which are within the range [lowerBound, upperBound). A pointer to the Annotator is used as the key for pre-calculated values, so the same Annotator must be used to avoid duplicate computation.

func (*Annotator[T]) MultiLevelAnnotation 

func (a *Annotator[T]) MultiLevelAnnotation(lms []LevelMetadata) *T

MultiLevelAnnotation calculates the annotation defined by this Annotator for all files across the given levels. A pointer to the Annotator is used as the key for pre-calculated values, so the same Annotator must be used to avoid duplicate computation.

func (*Annotator[T]) VersionRangeAnnotation 

func (a *Annotator[T]) VersionRangeAnnotation(v *Version, bounds base.UserKeyBounds) *T

VersionRangeAnnotation calculates the annotation defined by this Annotator for all files within the given Version which are within the range defined by bounds.

type BlobFileMetadata 

type BlobFileMetadata struct {
	// FileNum is the file number.
	FileNum base.DiskFileNum
	// Size is the size of the file, in bytes.
	Size uint64
	// ValueSize is the sum of the length of the uncompressed values stored in
	// this blob file.
	ValueSize uint64
	// File creation time in seconds since the epoch (1970-01-01 00:00:00
	// UTC).
	CreationTime uint64
	// contains filtered or unexported fields
}

BlobFileMetadata is metadata describing a blob value file.

func ParseBlobFileMetadataDebug 

func ParseBlobFileMetadataDebug(s string) (_ *BlobFileMetadata, err error)

ParseBlobFileMetadataDebug parses a BlobFileMetadata from its string representation. This function is intended for use in tests. It's the inverse of BlobFileMetadata.String().

In production code paths, the BlobFileMetadata is serialized in a binary format within a version edit under the tag tagNewBlobFile.

func (*BlobFileMetadata) SafeFormat 

func (m *BlobFileMetadata) SafeFormat(w redact.SafePrinter, _ rune)

SafeFormat implements redact.SafeFormatter.

func (*BlobFileMetadata) String 

func (m *BlobFileMetadata) String() string

String implements fmt.Stringer.

type BlobReference 

type BlobReference struct {
	// FileNum identifies the referenced blob file.
	FileNum base.DiskFileNum
	// ValueSize is the sum of the lengths of the uncompressed values within the
	// blob file for which there exists a reference in the sstable. Note that if
	// any of the referencing tables are virtualized tables, the ValueSize may
	// be approximate.
	//
	// INVARIANT: ValueSize <= Metadata.ValueSize
	ValueSize uint64

	// Metadata is the metadata for the blob file. It is non-nil for blob
	// references contained within active Versions. It is expected to initially
	// be nil when decoding a version edit as a part of manfiest replay. When
	// the version edit is accumulated into a bulk version edit, the metadata
	// is populated.
	Metadata *BlobFileMetadata
}

A BlobReference describes a sstable's reference to a blob value file.

func (*BlobReference) EstimatedPhysicalSize 

func (br *BlobReference) EstimatedPhysicalSize() uint64

EstimatedPhysicalSize returns an estimate of the physical size of the blob reference, in bytes. It's calculated by scaling the blob file's physical size according to the ValueSize of the blob reference relative to the total ValueSize of the blob file.

type BlobReferenceDepth 

type BlobReferenceDepth int

BlobReferenceDepth is a statistic maintained per-sstable, indicating an upper bound on the number of blob files that a reader scanning the table would need to keep open if they only open and close referenced blob files once. In other words, it's the stack depth of blob files referenced by a sstable. If a flush or compaction rewrites an sstable's values to a new blob file, the resulting sstable has a blob reference depth of 1. When a compaction reuses blob references, the max blob reference depth of the files in each level is used, and then the depth is summed, and assigned to the output. This is a loose upper bound (assuming worst case distribution of keys in all inputs) but avoids tracking key spans for references and using key comparisons.

Because the blob reference depth is the size of the working set of blob files referenced by the table, it cannot exceed the count of distinct blob file references.

Example: Consider a compaction of file f0 from L0 and files f1, f2, f3 from L1, where the former has blob reference depth of 1 and files f1, f2, f3 all happen to have a blob-reference-depth of 1. Say we produce many output files, one of which is f4. We are assuming here that the blobs referenced by f0 whose keys happened to be written to f4 are spread all across the key span of f4. Say keys from f1 and f2 also made their way to f4. Then we will first have keys that refer to blobs referenced by f1,f0 and at some point once we move past the keys of f1, we will have keys that refer to blobs referenced by f2,f0. In some sense, we have a working set of 2 blob files at any point in time, and this is similar to the idea of level stack depth for reads -- hence we adopt the depth terminology. We want to keep this stack depth in check, since locality is important, while allowing it to be higher than 1, since otherwise we will need to rewrite blob files in every compaction (defeating the write amp benefit we are looking for). Similar to the level depth, this simplistic analysis does not take into account distribution of keys involved in the compaction and which of them have blob references. Also the locality is actually better than in this analysis because more of the keys will be from the lower level.

type BlobReferences 

type BlobReferences []BlobReference

BlobReferences is a slice of BlobReference. The order of the slice is significant and should be maintained. In practice, a sstable's BlobReferences are ordered by earliest appearance within the sstable. The ordering is persisted to the manifest.

func (*BlobReferences) FileNumByID 

func (br *BlobReferences) FileNumByID(i blob.ReferenceID) base.DiskFileNum

FileNumByID returns the FileNum for the identified BlobReference.

func (*BlobReferences) IDByFileNum 

func (br *BlobReferences) IDByFileNum(fileNum base.DiskFileNum) (blob.ReferenceID, bool)

IDByFileNum returns the reference ID for the given FileNum. If the file number is not found, the second return value is false. IDByFileNum is linear in the length of the BlobReferences slice.

type BulkVersionEdit 

type BulkVersionEdit struct {
	AddedTables   [NumLevels]map[base.FileNum]*TableMetadata
	DeletedTables [NumLevels]map[base.FileNum]*TableMetadata

	BlobFiles struct {
		// Added holds the metadata of all new blob files introduced within the
		// aggregated version edit, keyed by file number.
		Added map[base.DiskFileNum]*BlobFileMetadata
		// Deleted holds a list of all blob files that became unreferenced by
		// any sstables, making them obsolete within the resulting version (a
		// zombie if still referenced by previous versions). Deleted file
		// numbers must not exist in Added.
		Deleted map[base.DiskFileNum]*BlobFileMetadata
		// DeletedReferences holds metadata of blob files referenced by tables
		// deleted in the accumulated version edits. This is used during replay
		// to populate the *BlobFileMetadata pointers of new blob references,
		// making use of the invariant that new blob references must correspond
		// to a file introduced in VersionEdit.AddedBlobFiles or a file
		// referenced by a deleted sstable.
		DeletedReferences map[base.DiskFileNum]*BlobFileMetadata
	}

	// AddedFileBacking is a map to support lookup so that we can populate the
	// FileBacking of virtual sstables during manifest replay.
	AddedFileBacking   map[base.DiskFileNum]*FileBacking
	RemovedFileBacking []base.DiskFileNum

	// AllAddedTables maps table number to table metadata for all added sstables
	// from accumulated version edits. AllAddedTables is only populated if set to
	// non-nil by a caller. It must be set to non-nil when replaying version edits
	// read from a MANIFEST (as opposed to VersionEdits constructed in-memory).
	// While replaying a MANIFEST file, VersionEdit.DeletedFiles map entries have
	// nil values, because the on-disk deletion record encodes only the file
	// number. Accumulate uses AllAddedTables to correctly populate the
	// BulkVersionEdit's Deleted field with non-nil *TableMetadata.
	AllAddedTables map[base.FileNum]*TableMetadata

	// MarkedForCompactionCountDiff holds the aggregated count of files
	// marked for compaction added or removed.
	MarkedForCompactionCountDiff int
}

BulkVersionEdit summarizes the files added and deleted from a set of version edits.

INVARIANTS: No file can be added to a level more than once. This is true globally, and also true for all of the calls to Accumulate for a single bulk version edit.

No file can be removed from a level more than once. This is true globally, and also true for all of the calls to Accumulate for a single bulk version edit.

A sstable file must not be added and removed from a given level in the same version edit, and a blob file must not be both added and deleted in the same version edit.

A file that is being removed from a level must have been added to that level before (in a prior version edit). Note that a given file can be deleted from a level and added to another level in a single version edit

func (*BulkVersionEdit) Accumulate 

func (b *BulkVersionEdit) Accumulate(ve *VersionEdit) error

Accumulate adds the file addition and deletions in the specified version edit to the bulk edit's internal state.

INVARIANTS: (1) If a table is added to a given level in a call to Accumulate and then removed from that level in a subsequent call, the file will not be present in the resulting BulkVersionEdit.Deleted for that level. (2) If a new table is added and it includes a reference to a blob file, that blob file must either appear in BlobFiles.Added, or the blob file must be referenced by a table deleted in the same bulk version edit.

After accumulation of version edits, the bulk version edit may have information about a file which has been deleted from a level, but it may not have information about the same file added to the same level. The add could've occurred as part of a previous bulk version edit. In this case, the deleted file must be present in BulkVersionEdit.Deleted, at the end of the accumulation, because we need to decrease the refcount of the deleted file in Apply.

func (*BulkVersionEdit) Apply 

func (b *BulkVersionEdit) Apply(curr *Version, readCompactionRate int64) (*Version, error)

Apply applies the delta b to the current version to produce a new version. The ordering of tables within the new version is consistent with respect to the comparer.

Apply updates the backing refcounts (Ref/Unref) as files are installed into the levels.

curr may be nil, which is equivalent to a pointer to a zero version.

Not that L0SublevelFiles is not initialized in the returned version; it is the caller's responsibility to set it using L0Organizer.PerformUpdate().

type CompactionState 

type CompactionState uint8

CompactionState is the compaction state of a file.

The following shows the valid state transitions: 

NotCompacting --> Compacting --> Compacted
      ^               |
      |               |
      +-------<-------+

Input files to a compaction transition to Compacting when a compaction is picked. A file that has finished compacting typically transitions into the Compacted state, at which point it is effectively obsolete ("zombied") and will eventually be removed from the LSM. A file that has been move-compacted will transition from Compacting back into the NotCompacting state, signaling that the file may be selected for a subsequent compaction. A failed compaction will result in all input tables transitioning from Compacting to NotCompacting.

This state is in-memory only. It is not persisted to the manifest. 

const (
	CompactionStateNotCompacting CompactionState = iota
	CompactionStateCompacting
	CompactionStateCompacted
)

CompactionStates.

func (CompactionState) String 

func (s CompactionState) String() string

String implements fmt.Stringer.

type Compare 

type Compare = base.Compare

Compare exports the base.Compare type.

type CurrentBlobFileSet 

type CurrentBlobFileSet struct {
	// contains filtered or unexported fields
}

CurrentBlobFileSet describes the set of blob files that are currently live in the latest Version. CurrentBlobFileSet is not thread-safe. In practice its use is protected by the versionSet logLock.

func (*CurrentBlobFileSet) ApplyAndUpdateVersionEdit 

func (s *CurrentBlobFileSet) ApplyAndUpdateVersionEdit(ve *VersionEdit) error

ApplyAndUpdateVersionEdit applies a version edit to the current blob file set, updating its internal tracking of extant blob file references. If after applying the version edit a blob file has no more references, the version edit is modified to record the blob file removal.

func (*CurrentBlobFileSet) Init 

func (s *CurrentBlobFileSet) Init(bve *BulkVersionEdit)

Init initializes the CurrentBlobFileSet with the state of the provided BulkVersionEdit. This is used after replaying a manifest.

func (*CurrentBlobFileSet) Metadatas 

func (s *CurrentBlobFileSet) Metadatas() []*BlobFileMetadata

Metadatas returns a slice of all blob file metadata in the set, sorted by file number for determinism.

func (*CurrentBlobFileSet) Stats 

func (s *CurrentBlobFileSet) Stats() AggregateBlobFileStats

Stats returns the cumulative stats across all blob files in the set.

type DeletedTableEntry 

type DeletedTableEntry struct {
	Level   int
	FileNum base.FileNum
}

DeletedTableEntry holds the state for a sstable deletion from a level. The table itself might still be referenced by another level.

type FileBacking 

type FileBacking struct {
	DiskFileNum base.DiskFileNum
	Size        uint64
	// contains filtered or unexported fields
}

FileBacking either backs a single physical sstable, or one or more virtual sstables.

See the comment above the TableMetadata type for sstable terminology.

func (*FileBacking) IsUnused 

func (b *FileBacking) IsUnused() bool

IsUnused returns if the backing is not being used by any tables in a version or btree.

func (*FileBacking) MustHaveRefs 

func (b *FileBacking) MustHaveRefs()

MustHaveRefs asserts that the backing has a positive refcount.

func (*FileBacking) Ref 

func (b *FileBacking) Ref()

Ref increments the backing's ref count.

func (*FileBacking) Unref 

func (b *FileBacking) Unref() int32

Unref decrements the backing's ref count (and returns the new count).

type InternalKey 

type InternalKey = base.InternalKey

InternalKey exports the base.InternalKey type.

func KeyRange 

func KeyRange(ucmp Compare, iters ...iter.Seq[*TableMetadata]) (smallest, largest InternalKey)

KeyRange returns the minimum smallest and maximum largest internalKey for all the TableMetadata in iters.

type InternalKeyBounds 

type InternalKeyBounds struct {
	// contains filtered or unexported fields
}

InternalKeyBounds represents set of keys (smallest, largest) used for the in-memory and on-disk partial DBs that make up a pebble DB.

It consists of the smallest, largest keys and their respective trailers. The keys are represented as a single string; their individual representations are given by the userKeySeparatorIdx as:

  • smallest: [0, userKeySeparatorIdx)
  • largest: [userKeySeparatorIdx, len(userKeyData))

This format allows us to save a couple of bytes that will add up proportionally to the amount of sstables we have.

func (*InternalKeyBounds) Largest 

func (ikr *InternalKeyBounds) Largest() InternalKey

func (*InternalKeyBounds) LargestUserKey 

func (ikr *InternalKeyBounds) LargestUserKey() []byte

func (*InternalKeyBounds) SetInternalKeyBounds 

func (ikr *InternalKeyBounds) SetInternalKeyBounds(smallest, largest InternalKey)

func (*InternalKeyBounds) SetLargest 

func (ikr *InternalKeyBounds) SetLargest(ik InternalKey)

func (*InternalKeyBounds) SetSmallest 

func (ikr *InternalKeyBounds) SetSmallest(ik InternalKey)

func (*InternalKeyBounds) Smallest 

func (ikr *InternalKeyBounds) Smallest() InternalKey

func (*InternalKeyBounds) SmallestUserKey 

func (ikr *InternalKeyBounds) SmallestUserKey() []byte

type KeyType 

type KeyType int8

KeyType is used to specify the type of keys we're looking for in LevelIterator positioning operations. Files not containing any keys of the desired type are skipped. 

const (
	// KeyTypePointAndRange denotes a search among the entire keyspace, including
	// both point keys and range keys. No sstables are skipped.
	KeyTypePointAndRange KeyType = iota
	// KeyTypePoint denotes a search among the point keyspace. SSTables with no
	// point keys will be skipped. Note that the point keyspace includes rangedels.
	KeyTypePoint
	// KeyTypeRange denotes a search among the range keyspace. SSTables with no
	// range keys will be skipped.
	KeyTypeRange
)

type L0Compaction 

type L0Compaction struct {
	Smallest  InternalKey
	Largest   InternalKey
	IsIntraL0 bool
}

L0Compaction describes an active compaction with inputs from L0.

type L0CompactionFiles 

type L0CompactionFiles struct {
	Files []*TableMetadata

	FilesIncluded bitSet
	// contains filtered or unexported fields
}

L0CompactionFiles represents a candidate set of L0 files for compaction. Also referred to as "lcf". Contains state information useful for generating the compaction (such as Files), as well as for picking between candidate compactions (eg. fileBytes and seedIntervalStackDepthReduction).

func (*L0CompactionFiles) Clone 

func (l *L0CompactionFiles) Clone() *L0CompactionFiles

Clone allocates a new L0CompactionFiles, with the same underlying data. Note that the two fileMetadata slices contain values that point to the same underlying fileMetadata object. This is safe because these objects are read only.

func (*L0CompactionFiles) String 

func (l *L0CompactionFiles) String() string

String merely prints the starting address of the first file, if it exists.

type L0Organizer 

type L0Organizer struct {
	// contains filtered or unexported fields
}

L0Organizer keeps track of L0 state, including the subdivision into sublevels.

It is designed to be used as a singleton (per DB) which gets updated as the version changes. It is used to initialize L0-related Version fields.

The level 0 sstables are organized in a series of sublevels. Similar to the seqnum invariant in normal levels, there is no internal key in a lower sublevel table that has both the same user key and a higher sequence number. Within a sublevel, tables are sorted by their internal key range and any two tables at the same sublevel do not overlap. Unlike the normal levels, sublevel n contains older tables (lower sequence numbers) than sublevel n+1 (this is because the number of sublevels is variable).

func NewL0Organizer 

func NewL0Organizer(comparer *base.Comparer, flushSplitBytes int64) *L0Organizer

NewL0Organizer creates the L0 organizer. The L0 organizer is responsible for maintaining the current L0 state and is kept in-sync with the current Version.

flushSplitBytes denotes the target number of bytes per sublevel in each flush split interval (i.e. range between two flush split keys) in L0 sstables. When set to zero, only a single sstable is generated by each flush. When set to a non-zero value, flushes are split at points to meet L0's TargetFileSize, any grandparent-related overlap options, and at boundary keys of L0 flush split intervals (which are targeted to contain around FlushSplitBytes bytes in each sublevel between pairs of boundary keys). Splitting sstables during flush allows increased compaction flexibility and concurrency when those tables are compacted to lower levels.

func (L0Organizer) Check 

func (s L0Organizer) Check()

Check performs sanity checks on l0Sublevels in invariants mode.

func (L0Organizer) ExtendL0ForBaseCompactionTo 

func (s L0Organizer) ExtendL0ForBaseCompactionTo(
	smallest, largest InternalKey, candidate *L0CompactionFiles,
) bool

ExtendL0ForBaseCompactionTo extends the specified base compaction candidate L0CompactionFiles to optionally cover more files in L0 without "touching" any of the passed-in keys (i.e. the smallest/largest bounds are exclusive), as including any user keys for those internal keys could require choosing more files in LBase which is undesirable. Unbounded start/end keys are indicated by passing in the InvalidInternalKey.

func (L0Organizer) FlushSplitKeys 

func (s L0Organizer) FlushSplitKeys() [][]byte

FlushSplitKeys returns a slice of user keys to split flushes at. Used by flushes to avoid writing sstables that straddle these split keys. These should be interpreted as the keys to start the next sstable (not the last key to include in the prev sstable). These are user keys so that range tombstones can be properly truncated (untruncated range tombstones are not permitted for L0 files).

func (L0Organizer) InUseKeyRanges 

func (s L0Organizer) InUseKeyRanges(smallest, largest []byte) []base.UserKeyBounds

InUseKeyRanges returns the merged table bounds of L0 files overlapping the provided user key range. The returned key ranges are sorted and nonoverlapping.

func (L0Organizer) InitCompactingFileInfo 

func (s L0Organizer) InitCompactingFileInfo(inProgress []L0Compaction)

InitCompactingFileInfo initializes internal flags relating to compacting files. Must be called after sublevel initialization.

Requires DB.mu *and* the manifest lock to be held.

func (L0Organizer) MaxDepthAfterOngoingCompactions 

func (s L0Organizer) MaxDepthAfterOngoingCompactions() int

MaxDepthAfterOngoingCompactions returns an estimate of maximum depth of sublevels after all ongoing compactions run to completion. Used by compaction picker to decide compaction score for L0. There is no scoring for intra-L0 compactions -- they only run if L0 score is high but we're unable to pick an L0 -> Lbase compaction.

func (*L0Organizer) PerformUpdate 

func (o *L0Organizer) PerformUpdate(prepared L0PreparedUpdate, newVersion *Version)

PerformUpdate applies an update the L0 organizer which was previously prepared using PrepareUpdate.

Sets newVersion.L0SublevelFiles (which is immutable once set).

This method cannot be called concurrently with any other methods.

func (L0Organizer) PickBaseCompaction 

func (s L0Organizer) PickBaseCompaction(
	logger base.Logger,
	minCompactionDepth int,
	baseFiles LevelSlice,
	baseLevel int,
	problemSpans *problemspans.ByLevel,
) *L0CompactionFiles

PickBaseCompaction picks a base compaction based on the above specified heuristics, for the specified Lbase files and a minimum depth of overlapping files that can be selected for compaction. Returns nil if no compaction is possible.

func (L0Organizer) PickIntraL0Compaction 

func (s L0Organizer) PickIntraL0Compaction(
	earliestUnflushedSeqNum base.SeqNum, minCompactionDepth int, problemSpans *problemspans.ByLevel,
) *L0CompactionFiles

PickIntraL0Compaction picks an intra-L0 compaction for files in this sublevel. This method is only called when a base compaction cannot be chosen. See comment above [PickBaseCompaction] for heuristics involved in this selection.

func (*L0Organizer) PrepareUpdate 

func (o *L0Organizer) PrepareUpdate(bve *BulkVersionEdit, newVersion *Version) L0PreparedUpdate

PrepareUpdate is the first step in the two-step process to update the L0Organizer. This first step performs as much work as it can without modifying the L0Organizer.

This method can be called concurrently with other methods (other than PerformUpdate). It allows doing most of the update work outside an important lock.

func (L0Organizer) ReadAmplification 

func (s L0Organizer) ReadAmplification() int

ReadAmplification returns the contribution of l0Sublevels to the read amplification for any particular point key. It is the maximum height of any tracked fileInterval. This is always less than or equal to the number of sublevels.

func (*L0Organizer) ResetForTesting 

func (o *L0Organizer) ResetForTesting(v *Version)

ResetForTesting reinitializes the L0Organizer to reflect the given version. Sets v.L0SublevelFiles.

func (L0Organizer) String 

func (s L0Organizer) String() string

String produces a string containing useful debug information. Useful in test code and debugging.

func (L0Organizer) UpdateStateForStartedCompaction 

func (s L0Organizer) UpdateStateForStartedCompaction(inputs []LevelSlice, isBase bool) error

UpdateStateForStartedCompaction updates internal l0Sublevels state for a recently started compaction. isBase specifies if this is a base compaction; if false, this is assumed to be an intra-L0 compaction. The specified compaction must be involving L0 SSTables. It's assumed that the Compacting and IsIntraL0Compacting fields are already set on all [TableMetadata]s passed in.

type L0PreparedUpdate 

type L0PreparedUpdate struct {
	// contains filtered or unexported fields
}

L0PreparedUpdate is returned by L0Organizer.PrepareUpdate(), to be passed to PerformUpdate().

type Layer 

type Layer struct {
	// contains filtered or unexported fields
}

Layer represents a section of the logical sstable hierarchy. It can represent:

  • a level L1 through L6, or
  • the entire L0 level, or
  • a specific L0 sublevel, or
  • the layer of flushable ingests (which is conceptually above the LSM).

func FlushableIngestsLayer 

func FlushableIngestsLayer() Layer

FlushableIngestsLayer returns a Layer that represents the flushable ingests layer (which is logically above L0).

func L0Sublevel 

func L0Sublevel(sublevel int) Layer

L0Sublevel returns a Layer that represents a specific L0 sublevel.

func Level 

func Level(level int) Layer

Level returns a Layer that represents an entire level (L0 through L6).

func (Layer) IsFlushableIngests 

func (l Layer) IsFlushableIngests() bool

IsFlushableIngests returns true if the layer represents flushable ingests.

func (Layer) IsL0Sublevel 

func (l Layer) IsL0Sublevel() bool

IsL0Sublevel returns true if the layer represents an L0 sublevel.

func (Layer) IsSet 

func (l Layer) IsSet() bool

IsSet returns true if l has been initialized.

func (Layer) Level 

func (l Layer) Level() int

Level returns the level for the layer. Must not be called if the layer represents flushable ingests.

func (Layer) SafeFormat 

func (l Layer) SafeFormat(s redact.SafePrinter, verb rune)

SafeFormat implements redact.SafeFormatter.

func (Layer) String 

func (l Layer) String() string

func (Layer) Sublevel 

func (l Layer) Sublevel() int

Sublevel returns the L0 sublevel. Can only be called if the layer represents an L0 sublevel.

type LevelFile 

type LevelFile struct {
	*TableMetadata
	// contains filtered or unexported fields
}

LevelFile holds a file's metadata along with its position within a level of the LSM.

func (LevelFile) Slice 

func (lf LevelFile) Slice() LevelSlice

Slice constructs a LevelSlice containing only this file.

type LevelIterator 

type LevelIterator struct {
	// contains filtered or unexported fields
}

LevelIterator iterates over a set of files' metadata. Its zero value is an empty iterator.

func (*LevelIterator) Clone 

func (i *LevelIterator) Clone() LevelIterator

Clone copies the iterator, returning an independent iterator at the same position.

func (*LevelIterator) Filter 

func (i *LevelIterator) Filter(keyType KeyType) LevelIterator

Filter clones the iterator and sets the desired KeyType as the key to filter files on.

func (*LevelIterator) First 

func (i *LevelIterator) First() *TableMetadata

First seeks to the first file in the iterator and returns it.

func (*LevelIterator) Last 

func (i *LevelIterator) Last() *TableMetadata

Last seeks to the last file in the iterator and returns it.

func (*LevelIterator) Next 

func (i *LevelIterator) Next() *TableMetadata

Next advances the iterator to the next file and returns it.

func (*LevelIterator) Prev 

func (i *LevelIterator) Prev() *TableMetadata

Prev moves the iterator the previous file and returns it.

func (*LevelIterator) SeekGE 

func (i *LevelIterator) SeekGE(cmp Compare, userKey []byte) *TableMetadata

SeekGE seeks to the first file with a largest key (of the desired type) that is an upper bound for the given user key. This is the first file that could contain a user key that is greater than or equal to userKey.

More specifically, userKey is less than the file's largest.UserKey or they are equal and largest is not an exclusive sentinel.

The iterator must have been constructed from L1+ or from a single sublevel of L0, because it requires the underlying files to be sorted by user keys and non-overlapping.

func (*LevelIterator) SeekLT 

func (i *LevelIterator) SeekLT(cmp Compare, userKey []byte) *TableMetadata

SeekLT seeks to the last file with a smallest key (of the desired type) that is less than the given user key. This is the last file that could contain a key less than userKey.

The iterator must have been constructed from L1+ or from a single sublevel of L0, because it requires the underlying files to be sorted by user keys and non-overlapping.

func (LevelIterator) String 

func (i LevelIterator) String() string

func (*LevelIterator) Take 

func (i *LevelIterator) Take() LevelFile

Take constructs a LevelFile containing the file at the iterator's current position. Take panics if the iterator is not currently positioned over a file.

type LevelMetadata 

type LevelMetadata struct {

	// NumVirtual is the number of virtual sstables in the level.
	NumVirtual uint64
	// VirtualTableSize is the size of the virtual sstables in the level.
	VirtualTableSize uint64
	// contains filtered or unexported fields
}

LevelMetadata contains metadata for all of the files within a level of the LSM.

func MakeLevelMetadata 

func MakeLevelMetadata(cmp Compare, level int, files []*TableMetadata) LevelMetadata

MakeLevelMetadata creates a LevelMetadata with the given files.

func (*LevelMetadata) AggregateSize 

func (lm *LevelMetadata) AggregateSize() uint64

AggregateSize returns the aggregate size estimate of all sstables within the level, plus an estimate of the physical size of values stored externally in blob files. This quantity is equal to TableSize() + EstimatedReferenceSize().

func (*LevelMetadata) All 

func (lm *LevelMetadata) All() iter.Seq[*TableMetadata]

All returns an iterator over all files in the level.

func (*LevelMetadata) Empty 

func (lm *LevelMetadata) Empty() bool

Empty indicates whether there are any files in the level.

func (*LevelMetadata) EstimatedReferenceSize 

func (lm *LevelMetadata) EstimatedReferenceSize() uint64

EstimatedReferenceSize returns an estimate of the physical size of all the file's blob references in the table. This sum, added to TableSize(), yields AggregateSize().

func (*LevelMetadata) Find 

func (lm *LevelMetadata) Find(cmp base.Compare, m *TableMetadata) LevelSlice

Find finds the provided file in the level. If it exists, returns a LevelSlice that contains just that file; otherwise, returns an empty LevelSlice.

func (*LevelMetadata) Iter 

func (lm *LevelMetadata) Iter() LevelIterator

Iter constructs a LevelIterator over the entire level.

func (*LevelMetadata) Len 

func (lm *LevelMetadata) Len() int

Len returns the number of files within the level.

func (*LevelMetadata) Slice 

func (lm *LevelMetadata) Slice() LevelSlice

Slice constructs a slice containing the entire level.

func (*LevelMetadata) TableSize 

func (lm *LevelMetadata) TableSize() uint64

TableSize returns the cumulative size of all sstables within the level. This quantity does NOT include the size of values stored externally in blob files.

type LevelSlice 

type LevelSlice struct {
	// contains filtered or unexported fields
}

LevelSlice contains a slice of the files within a level of the LSM. A LevelSlice is immutable once created, but may be used to construct a mutable LevelIterator over the slice's files.

LevelSlices should be constructed through one of the existing constructors, not manually initialized.

func NewLevelSliceKeySorted 

func NewLevelSliceKeySorted(cmp base.Compare, files []*TableMetadata) LevelSlice

NewLevelSliceKeySorted constructs a LevelSlice over the provided files, sorted by the files smallest keys. TODO(jackson): Can we improve this interface or avoid needing to export a slice constructor like this?

func NewLevelSliceSeqSorted 

func NewLevelSliceSeqSorted(files []*TableMetadata) LevelSlice

NewLevelSliceSeqSorted constructs a LevelSlice over the provided files, sorted by the L0 sequence number sort order. TODO(jackson): Can we improve this interface or avoid needing to export a slice constructor like this?

func NewLevelSliceSpecificOrder 

func NewLevelSliceSpecificOrder(files []*TableMetadata) LevelSlice

NewLevelSliceSpecificOrder constructs a LevelSlice over the provided files, ordering the files by their order in the provided slice. It's used in tests. TODO(jackson): Update tests to avoid requiring this and remove it.

func (*LevelSlice) AggregateSizeSum 

func (ls *LevelSlice) AggregateSizeSum() uint64

AggregateSizeSum sums the size of all sstables in the slice, inclusive of the estimated physical size of tables' blob references. Its runtime is linear in the length of the slice.

func (LevelSlice) All 

func (ls LevelSlice) All() iter.Seq[*TableMetadata]

All returns an iterator over all files in the slice.

func (*LevelSlice) Empty 

func (ls *LevelSlice) Empty() bool

Empty indicates whether the slice contains any files.

func (*LevelSlice) Iter 

func (ls *LevelSlice) Iter() LevelIterator

Iter constructs a LevelIterator that iterates over the slice.

func (*LevelSlice) Len 

func (ls *LevelSlice) Len() int

Len returns the number of files in the slice. Its runtime is constant.

func (*LevelSlice) NumVirtual 

func (ls *LevelSlice) NumVirtual() uint64

NumVirtual returns the number of virtual sstables in the level. Its runtime is linear in the length of the slice.

func (LevelSlice) Overlaps 

func (ls LevelSlice) Overlaps(cmp Compare, bounds base.UserKeyBounds) LevelSlice

Overlaps returns a new LevelSlice that reflects the portion of files with boundaries that overlap with the provided bounds.

func (LevelSlice) Reslice 

func (ls LevelSlice) Reslice(resliceFunc func(start, end *LevelIterator)) LevelSlice

Reslice constructs a new slice backed by the same underlying level, with new start and end positions. Reslice invokes the provided function, passing two LevelIterators: one positioned to i's inclusive start and one positioned to i's inclusive end. The resliceFunc may move either iterator forward or backwards, including beyond the callee's original bounds to capture additional files from the underlying level. Reslice constructs and returns a new LevelSlice with the final bounds of the iterators after calling resliceFunc.

func (LevelSlice) String 

func (ls LevelSlice) String() string

String implements fmt.Stringer.

func (*LevelSlice) TableSizeSum 

func (ls *LevelSlice) TableSizeSum() uint64

TableSizeSum sums the size of all sstables in the slice. Its runtime is linear in the length of the slice.

func (*LevelSlice) VirtualTableSizeSum 

func (ls *LevelSlice) VirtualTableSizeSum() uint64

VirtualTableSizeSum returns the sum of the sizes of the virtual sstables in the level.

type NewTableEntry 

type NewTableEntry struct {
	Level int
	Meta  *TableMetadata
	// BackingFileNum is only set during manifest replay, and only for virtual
	// sstables.
	BackingFileNum base.DiskFileNum
}

NewTableEntry holds the state for a new sstable or one moved from a different level.

type ObsoleteFiles 

type ObsoleteFiles struct {
	FileBackings []*FileBacking
	BlobFiles    []*BlobFileMetadata
}

ObsoleteFiles holds a set of files that are no longer referenced by any referenced Version.

func (*ObsoleteFiles) AddBacking 

func (of *ObsoleteFiles) AddBacking(fb *FileBacking)

AddBacking appends the provided FileBacking to the list of obsolete files.

func (*ObsoleteFiles) AddBlob 

func (of *ObsoleteFiles) AddBlob(bm *BlobFileMetadata)

AddBlob appends the provided BlobFileMetadata to the list of obsolete files.

func (*ObsoleteFiles) Count 

func (of *ObsoleteFiles) Count() int

Count returns the number of files in the ObsoleteFiles.

type ObsoleteFilesSet 

type ObsoleteFilesSet interface {
	// AddBacking appends the provided FileBacking to the list of obsolete
	// files.
	AddBacking(*FileBacking)
	// AddBlob appends the provided BlobFileMetadata to the list of obsolete
	// files.
	AddBlob(*BlobFileMetadata)
}

ObsoleteFilesSet accumulates files that now have zero references.

type PartialOverlapAnnotationAggregator 

type PartialOverlapAnnotationAggregator[T any] interface {
	AnnotationAggregator[T]
	AccumulatePartialOverlap(f *TableMetadata, dst *T, bounds base.UserKeyBounds) *T
}

A PartialOverlapAnnotationAggregator is an extension of AnnotationAggregator that allows for custom accumulation of range annotations for files that only partially overlap with the range.

type PickFileAggregator 

type PickFileAggregator struct {
	// Filter takes a TableMetadata and returns whether it is eligible to be
	// picked by this PickFileAggregator. The second return value indicates
	// whether this eligibility is stable and thus cacheable.
	Filter func(f *TableMetadata) (eligible bool, cacheOK bool)
	// Compare compares two instances of TableMetadata and returns true if the
	// first one should be picked over the second one. It may assume that both
	// arguments are non-nil.
	Compare func(f1 *TableMetadata, f2 *TableMetadata) bool
}

PickFileAggregator implements the AnnotationAggregator interface. It defines an aggregator that picks a single file from a set of eligible files.

func (PickFileAggregator) Accumulate 

func (fa PickFileAggregator) Accumulate(
	f *TableMetadata, dst *TableMetadata,
) (v *TableMetadata, cacheOK bool)

Accumulate implements AnnotationAggregator.Accumulate, accumulating a single file as long as it is eligible to be picked.

func (PickFileAggregator) Merge 

func (fa PickFileAggregator) Merge(src *TableMetadata, dst *TableMetadata) *TableMetadata

Merge implements AnnotationAggregator.Merge by picking a single file based on the output of PickFileAggregator.Compare.

func (PickFileAggregator) Zero 

func (fa PickFileAggregator) Zero(dst *TableMetadata) *TableMetadata

Zero implements AnnotationAggregator.Zero, returning nil as the zero value.

type SumAggregator 

type SumAggregator struct {
	AccumulateFunc               func(f *TableMetadata) (v uint64, cacheOK bool)
	AccumulatePartialOverlapFunc func(f *TableMetadata, bounds base.UserKeyBounds) uint64
}

SumAggregator defines an Aggregator which sums together a uint64 value across files.

func (SumAggregator) Accumulate 

func (sa SumAggregator) Accumulate(f *TableMetadata, dst *uint64) (v *uint64, cacheOK bool)

Accumulate implements AnnotationAggregator.Accumulate, accumulating a single file's uint64 value.

func (SumAggregator) AccumulatePartialOverlap 

func (sa SumAggregator) AccumulatePartialOverlap(
	f *TableMetadata, dst *uint64, bounds base.UserKeyBounds,
) *uint64

AccumulatePartialOverlap implements PartialOverlapAnnotationAggregator.AccumulatePartialOverlap, accumulating a single file's uint64 value for a file which only partially overlaps with the range defined by bounds.

func (SumAggregator) Merge 

func (sa SumAggregator) Merge(src *uint64, dst *uint64) *uint64

Merge implements AnnotationAggregator.Merge by summing two uint64 values.

func (SumAggregator) Zero 

func (sa SumAggregator) Zero(dst *uint64) *uint64

Zero implements AnnotationAggregator.Zero, returning a new uint64 set to 0.

type TableInfo 

type TableInfo struct {
	// FileNum is the internal DB identifier for the table.
	FileNum base.FileNum
	// Size is the size of the file in bytes.
	Size uint64
	// Smallest is the smallest internal key in the table.
	Smallest InternalKey
	// Largest is the largest internal key in the table.
	Largest InternalKey
	// SmallestSeqNum is the smallest sequence number in the table.
	SmallestSeqNum base.SeqNum
	// LargestSeqNum is the largest sequence number in the table.
	LargestSeqNum base.SeqNum
}

TableInfo contains the common information for table related events.

type TableMetadata 

type TableMetadata struct {
	// AllowedSeeks is used to determine if a file should be picked for
	// a read triggered compaction. It is decremented when read sampling
	// in pebble.Iterator after every after every positioning operation
	// that returns a user key (eg. Next, Prev, SeekGE, SeekLT, etc).
	AllowedSeeks atomic.Int64

	// FileBacking is the state which backs either a physical or virtual
	// sstables.
	FileBacking *FileBacking

	// InitAllowedSeeks is the inital value of allowed seeks. This is used
	// to re-set allowed seeks on a file once it hits 0.
	InitAllowedSeeks int64
	// TableNum is the table number, unique across the lifetime of a DB.
	//
	// INVARIANT: when !TableMetadata.Virtual, TableNum == FileBacking.DiskFileNum.
	TableNum base.TableNum
	// Size is the size of the file, in bytes. Size is an approximate value for
	// virtual sstables.
	//
	// INVARIANTS:
	// - When !TableMetadata.Virtual, Size == FileBacking.Size.
	// - Size should be non-zero. Size 0 virtual sstables must not be created.
	Size uint64
	// File creation time in seconds since the epoch (1970-01-01 00:00:00
	// UTC). For ingested sstables, this corresponds to the time the file was
	// ingested. For virtual sstables, this corresponds to the wall clock time
	// when the TableMetadata for the virtual sstable was first created.
	CreationTime int64
	// LargestSeqNumAbsolute is an upper bound for the largest sequence number
	// in the table. This upper bound is guaranteed to be higher than any
	// sequence number any of the table's keys have held at any point in time
	// while the database has been open. Specifically, if the table contains
	// keys that have had their sequence numbers zeroed during a compaction,
	// LargestSeqNumAbsolute will be at least as high as the pre-zeroing
	// sequence number. LargestSeqNumAbsolute is NOT durably persisted, so after
	// a database restart it takes on the value of LargestSeqNum.
	LargestSeqNumAbsolute base.SeqNum
	// Lower and upper bounds for the smallest and largest sequence numbers in
	// the table, across both point and range keys. For physical sstables, these
	// values are tight bounds. For virtual sstables, there is no guarantee that
	// there will be keys with SmallestSeqNum or LargestSeqNum within virtual
	// sstable bounds.
	SmallestSeqNum base.SeqNum
	LargestSeqNum  base.SeqNum
	// PointKeyBounds.Smallest() and PointKeyBounds.Largest() are the inclusive bounds for the
	// internal point keys stored in the table. This includes RANGEDELs, which
	// alter point keys.
	// NB: these field should be set using ExtendPointKeyBounds. They are left
	// exported for reads as an optimization.
	PointKeyBounds InternalKeyBounds
	// RangeKeyBounds.Smallest() and RangeKeyBounds.Largest() are the inclusive bounds for the
	// internal range keys stored in the table.
	// NB: these field should be set using ExtendRangeKeyBounds. They are left
	// exported for reads as an optimization.
	RangeKeyBounds *InternalKeyBounds
	// BlobReferences is a list of blob files containing values that are
	// referenced by this sstable.
	BlobReferences BlobReferences
	// BlobReferenceDepth is the stack depth of blob files referenced by this
	// sstable. See the comment on the BlobReferenceDepth type for more details.
	//
	// INVARIANT: BlobReferenceDepth == 0 iff len(BlobReferences) == 0
	// INVARIANT: BlobReferenceDepth <= len(BlobReferences)
	BlobReferenceDepth BlobReferenceDepth

	// Stats describe table statistics. Protected by DB.mu.
	//
	// For virtual sstables, set stats upon virtual sstable creation as
	// asynchronous computation of stats is not currently supported.
	//
	// TODO(bananabrick): To support manifest replay for virtual sstables, we
	// probably need to compute virtual sstable stats asynchronously. Otherwise,
	// we'd have to write virtual sstable stats to the version edit.
	Stats TableStats

	// For L0 files only. Protected by DB.mu. Used to generate L0 sublevels and
	// pick L0 compactions. Only accurate for the most recent Version.
	// TODO(radu): this is very hacky and fragile. This information should live
	// inside l0Sublevels.
	SubLevel int
	L0Index  int

	// IsIntraL0Compacting is set to True if this file is part of an intra-L0
	// compaction. When it's true, IsCompacting must also return true. If
	// Compacting is true and IsIntraL0Compacting is false for an L0 file, the
	// file must be part of a compaction to Lbase.
	IsIntraL0Compacting bool
	CompactionState     CompactionState
	// True if compaction of this file has been explicitly requested.
	// Previously, RocksDB and earlier versions of Pebble allowed this
	// flag to be set by a user table property collector. Some earlier
	// versions of Pebble respected this flag, while other more recent
	// versions ignored this flag.
	//
	// More recently this flag has been repurposed to facilitate the
	// compaction of 'atomic compaction units'. Files marked for
	// compaction are compacted in a rewrite compaction at the lowest
	// possible compaction priority.
	//
	// NB: A count of files marked for compaction is maintained on
	// Version, and compaction picking reads cached annotations
	// determined by this field.
	//
	// Protected by DB.mu.
	MarkedForCompaction bool
	// HasPointKeys tracks whether the table contains point keys (including
	// RANGEDELs). If a table contains only range deletions, HasPointsKeys is
	// still true.
	HasPointKeys bool
	// HasRangeKeys tracks whether the table contains any range keys.
	HasRangeKeys bool
	// Virtual is true if the TableMetadata belongs to a virtual sstable.
	Virtual bool

	// VirtualParams are set only when Virtual is true.
	VirtualParams *virtual.VirtualReaderParams

	// SyntheticPrefix is used to prepend a prefix to all keys and/or override all
	// suffixes in a table; used for some virtual tables.
	SyntheticPrefixAndSuffix sstable.SyntheticPrefixAndSuffix
	// contains filtered or unexported fields
}

TableMetadata is maintained for leveled-ssts, i.e., they belong to a level of some version. TableMetadata does not contain the actual level of the sst, since such leveled-ssts can move across levels in different versions, while sharing the same TableMetadata. There are two kinds of leveled-ssts, physical and virtual. Underlying both leveled-ssts is a backing-sst, for which the only state is FileBacking. A backing-sst is level-less. It is possible for a backing-sst to be referred to by a physical sst in one version and by one or more virtual ssts in one or more versions. A backing-sst becomes obsolete and can be deleted once it is no longer required by any physical or virtual sst in any version.

We maintain some invariants:

  1. Each physical and virtual sst will have a unique TableMetadata.TableNum, and there will be exactly one TableMetadata associated with the TableNum.

  2. Within a version, a backing-sst is either only referred to by one physical sst or one or more virtual ssts.

  3. Once a backing-sst is referred to by a virtual sst in the latest version, it cannot go back to being referred to by a physical sst in any future version.

Once a physical sst is no longer needed by any version, we will no longer maintain the table metadata associated with it. We will still maintain the FileBacking associated with the physical sst if the backing sst is required by any virtual ssts in any version.

When using these fields in the context of a Virtual Table, These fields have additional invariants imposed on them, and/or slightly varying meanings:

  • boundTypeSmallest and boundTypeLargest (and their counterparts {Point,Range}KeyBounds.{Smallest(), Largest()}) remain tight bounds that represent a key at that exact bound. We make the effort to determine the next smallest or largest key in an sstable after virtualizing it, to maintain this tightness. If the largest is a sentinel key (IsExclusiveSentinel()), it could mean that a rangedel or range key ends at that user key, or has been truncated to that user key.
  • One invariant is that if a rangedel or range key is truncated on its upper bound, the virtual sstable *must* have a rangedel or range key sentinel key as its upper bound. This is because truncation yields an exclusive upper bound for the rangedel/rangekey, and if there are any points at that exclusive upper bound within the same virtual sstable, those could get uncovered by this truncation. We enforce this invariant in calls to keyspan.Truncate.
  • Size is an estimate of the size of the virtualized portion of this sstable. The underlying file's size is stored in FileBacking.Size, though it could also be estimated or could correspond to just the referenced portion of a file (eg. if the file originated on another node).
  • Size must be > 0.
  • SmallestSeqNum and LargestSeqNum are loose bounds for virtual sstables. This means that all keys in the virtual sstable must have seqnums within [SmallestSeqNum, LargestSeqNum], however there's no guarantee that there's a key with a seqnum at either of the bounds. Calculating tight seqnum bounds would be too expensive and deliver little value.
  • Note: These properties do not apply to external sstables, whose bounds are loose rather than tight, as we do not open them on ingest.

func ParseTableMetadataDebug 

func ParseTableMetadataDebug(s string) (_ *TableMetadata, err error)

ParseTableMetadataDebug parses a TableMetadata from its DebugString representation.

func (*TableMetadata) AttachVirtualBacking 

func (m *TableMetadata) AttachVirtualBacking(backing *FileBacking)

AttachVirtualBacking attaches an existing FileBacking for a virtual table.

The Smallest/Largest bounds must already be set to their final values.

func (*TableMetadata) ContainedWithinSpan 

func (m *TableMetadata) ContainedWithinSpan(cmp Compare, start, end []byte) bool

ContainedWithinSpan returns true if the file key range completely overlaps with the given range ("end" is assumed to exclusive).

func (*TableMetadata) ContainsKeyType 

func (m *TableMetadata) ContainsKeyType(kt KeyType) bool

ContainsKeyType returns whether or not the file contains keys of the provided type.

func (*TableMetadata) DebugString 

func (m *TableMetadata) DebugString(format base.FormatKey, verbose bool) string

DebugString returns a verbose representation of TableMetadata, typically for use in tests and debugging, returning the file number and the point, range and overall bounds for the table.

func (*TableMetadata) EstimatedReferenceSize 

func (m *TableMetadata) EstimatedReferenceSize() uint64

EstimatedReferenceSize returns the estimated physical size of all the file's blob references in the table. This sum, added to the sstable's size, yields an approximation of the overall size of the data represented by the table.

EstimatedReferenceSize is an estimate, but it's guaranteed to be stable over the lifetime of the table. This is necessary to correctly maintain incrementally-updated metrics.

func (*TableMetadata) ExtendPointKeyBounds 

func (m *TableMetadata) ExtendPointKeyBounds(
	cmp Compare, smallest, largest InternalKey,
) *TableMetadata

ExtendPointKeyBounds attempts to extend the lower and upper point key bounds and overall table bounds with the given smallest and largest keys. The smallest and largest bounds may not be extended if the table already has a bound that is smaller or larger, respectively. The receiver is returned. NB: calling this method should be preferred to manually setting the bounds by manipulating the fields directly, to maintain certain invariants.

func (*TableMetadata) ExtendRangeKeyBounds 

func (m *TableMetadata) ExtendRangeKeyBounds(
	cmp Compare, smallest, largest InternalKey,
) *TableMetadata

ExtendRangeKeyBounds attempts to extend the lower and upper range key bounds and overall table bounds with the given smallest and largest keys. The smallest and largest bounds may not be extended if the table already has a bound that is smaller or larger, respectively. The receiver is returned. NB: calling this method should be preferred to manually setting the bounds by manipulating the fields directly, to maintain certain invariants.

func (*TableMetadata) FragmentIterTransforms 

func (m *TableMetadata) FragmentIterTransforms() sstable.FragmentIterTransforms

FragmentIterTransforms returns an sstable.FragmentIterTransforms populated according to the file.

func (*TableMetadata) InitPhysicalBacking 

func (m *TableMetadata) InitPhysicalBacking()

InitPhysicalBacking allocates and sets the FileBacking which is required by a physical sstable TableMetadata.

Ensure that the state required by FileBacking, such as the TableNum, is already set on the TableMetadata before InitPhysicalBacking is called. Calling InitPhysicalBacking only after the relevant state has been set in the TableMetadata is not necessary in tests which don't rely on FileBacking.

func (*TableMetadata) InitVirtualBacking 

func (m *TableMetadata) InitVirtualBacking(fileNum base.DiskFileNum, size uint64)

InitVirtualBacking creates a new FileBacking for a virtual table.

The Smallest/Largest bounds must already be set to their final values.

func (*TableMetadata) InternalKeyBounds 

func (m *TableMetadata) InternalKeyBounds() (InternalKey, InternalKey)

InternalKeyBounds returns the set of overall table bounds.

func (*TableMetadata) IsCompacting 

func (m *TableMetadata) IsCompacting() bool

IsCompacting returns true if this file's compaction state is CompactionStateCompacting. Protected by DB.mu.

func (*TableMetadata) IterTransforms 

func (m *TableMetadata) IterTransforms() sstable.IterTransforms

IterTransforms returns an sstable.IterTransforms populated according to the file.

func (*TableMetadata) Largest 

func (m *TableMetadata) Largest() InternalKey

Largest returns the largest key based on the bound type of boundTypeLargest.

func (*TableMetadata) LargestBound 

func (m *TableMetadata) LargestBound(kt KeyType) (InternalKey, bool)

LargestBound returns the file's largest bound of the key type. It returns a false second return value if the file does not contain any keys of the key type.

func (*TableMetadata) Overlaps 

func (m *TableMetadata) Overlaps(cmp Compare, bounds *base.UserKeyBounds) bool

Overlaps returns true if the file key range overlaps with the given user key bounds.

func (*TableMetadata) PhysicalMeta 

func (m *TableMetadata) PhysicalMeta() *TableMetadata

func (*TableMetadata) Ref 

func (m *TableMetadata) Ref()

Ref increments the table's ref count. If this is the table's first reference, Ref will increment the reference of the table's FileBacking and referenced blob files.

func (*TableMetadata) SetCompactionState 

func (m *TableMetadata) SetCompactionState(to CompactionState)

SetCompactionState transitions this file's compaction state to the given state. Protected by DB.mu.

func (*TableMetadata) Smallest 

func (m *TableMetadata) Smallest() InternalKey

Smallest returns the smallest key based on the bound type of boundTypeSmallest.

func (*TableMetadata) SmallestBound 

func (m *TableMetadata) SmallestBound(kt KeyType) (InternalKey, bool)

SmallestBound returns the file's smallest bound of the key type. It returns a false second return value if the file does not contain any keys of the key type.

func (*TableMetadata) StatsMarkValid 

func (m *TableMetadata) StatsMarkValid()

StatsMarkValid marks the TableStats as valid. The caller must hold DB.mu while populating TableStats and calling StatsMarkValud. Once stats are populated, they must not be mutated.

func (*TableMetadata) StatsValid 

func (m *TableMetadata) StatsValid() bool

StatsValid returns true if the table stats have been populated. If StatValid returns true, the Stats field may be read (with or without holding the database mutex).

func (*TableMetadata) String 

func (m *TableMetadata) String() string

String implements fmt.Stringer, printing the file number and the overall table bounds.

func (*TableMetadata) SyntheticSeqNum 

func (m *TableMetadata) SyntheticSeqNum() sstable.SyntheticSeqNum

SyntheticSeqNum returns a SyntheticSeqNum which is set when SmallestSeqNum equals LargestSeqNum.

func (*TableMetadata) TableInfo 

func (m *TableMetadata) TableInfo() TableInfo

TableInfo returns a subset of the TableMetadata state formatted as a TableInfo.

func (*TableMetadata) Unref 

func (m *TableMetadata) Unref(obsoleteFiles ObsoleteFilesSet)

Unref decrements the table's reference count. If the count reaches zero, the table releases its references on associated files. If any referenced files become obsolete, they're inserted into the provided ObsoleteFiles.

func (*TableMetadata) UserKeyBounds 

func (m *TableMetadata) UserKeyBounds() base.UserKeyBounds

UserKeyBounds returns the user key bounds that correspond to m.Smallest and Largest. Because we do not allow split user keys, the user key bounds of files within a level do not overlap.

func (*TableMetadata) UserKeyBoundsByType 

func (m *TableMetadata) UserKeyBoundsByType(keyType KeyType) base.UserKeyBounds

UserKeyBoundsByType returns the user key bounds for the given key types. Note that the returned bounds are invalid when requesting KeyTypePoint but HasPointKeys is false, or when requesting KeyTypeRange and HasRangeKeys is false.

func (*TableMetadata) Validate 

func (m *TableMetadata) Validate(cmp Compare, formatKey base.FormatKey) error

Validate validates the metadata for consistency with itself, returning an error if inconsistent.

func (*TableMetadata) ValidateVirtual 

func (m *TableMetadata) ValidateVirtual(createdFrom *TableMetadata)

ValidateVirtual should be called once the TableMetadata for a virtual sstable is created to verify that the fields of the virtual sstable are sound.

func (*TableMetadata) VirtualMeta 

func (m *TableMetadata) VirtualMeta() *TableMetadata

type TableStats 

type TableStats struct {
	// The total number of entries in the table.
	NumEntries uint64
	// The number of point and range deletion entries in the table.
	NumDeletions uint64
	// NumRangeKeySets is the total number of range key sets in the table.
	//
	// NB: If there's a chance that the sstable contains any range key sets,
	// then NumRangeKeySets must be > 0.
	NumRangeKeySets uint64
	// Estimate of the total disk space that may be dropped by this table's
	// point deletions by compacting them.
	PointDeletionsBytesEstimate uint64
	// Estimate of the total disk space that may be dropped by this table's
	// range deletions by compacting them. This estimate is at data-block
	// granularity and is not updated if compactions beneath the table reduce
	// the amount of reclaimable disk space. It also does not account for
	// overlapping data in L0 and ignores L0 sublevels, but the error that
	// introduces is expected to be small. Similarly, multiple overlapping
	// RANGEDELs can in different levels can count the same data to be deleted
	// multiple times.
	//
	// Tables in the bottommost level of the LSM may have a nonzero estimate if
	// snapshots or move compactions prevented the elision of their range
	// tombstones. A table in the bottommost level that was ingested into L6
	// will have a zero estimate, because the file's sequence numbers indicate
	// that the tombstone cannot drop any data contained within the file itself.
	RangeDeletionsBytesEstimate uint64
	// Total size of value blocks and value index block.
	ValueBlocksSize uint64
	// CompressionType is the compression type of the table.
	CompressionType block.Compression
	// TombstoneDenseBlocksRatio is the ratio of data blocks in this table that
	// fulfills at least one of the following:
	// 1. The block contains at least options.Experimental.NumDeletionsThreshold
	//    point tombstones.
	// 2. The ratio of the uncompressed size of point tombstones to the
	//    uncompressed size of the block is at least
	//    options.Experimental.DeletionSizeRatioThreshold.
	// This statistic is used to determine eligibility for a tombstone density
	// compaction.
	TombstoneDenseBlocksRatio float64
}

TableStats contains statistics on a table used for compaction heuristics, and export via Metrics.

type Version 

type Version struct {

	// L0SublevelFiles contains the L0 sublevels.
	L0SublevelFiles []LevelSlice

	Levels [NumLevels]LevelMetadata

	// RangeKeyLevels holds a subset of the same files as Levels that contain range
	// keys (i.e. fileMeta.HasRangeKeys == true). The memory amplification of this
	// duplication should be minimal, as range keys are expected to be rare.
	RangeKeyLevels [NumLevels]LevelMetadata

	// The callback to invoke when the last reference to a version is
	// removed. Will be called with list.mu held.
	Deleted func(obsolete ObsoleteFiles)

	// Stats holds aggregated stats about the version maintained from
	// version to version.
	Stats struct {
		// MarkedForCompaction records the count of files marked for
		// compaction within the version.
		MarkedForCompaction int
	}
	// contains filtered or unexported fields
}

Version is a collection of table metadata for on-disk tables at various levels. In-memory DBs are written to level-0 tables, and compactions migrate data from level N to level N+1. The tables map internal keys (which are a user key, a delete or set bit, and a sequence number) to user values.

The tables at level 0 are sorted by largest sequence number. Due to file ingestion, there may be overlap in the ranges of sequence numbers contain in level 0 sstables. In particular, it is valid for one level 0 sstable to have the seqnum range [1,100] while an adjacent sstable has the seqnum range [50,50]. This occurs when the [50,50] table was ingested and given a global seqnum. The ingestion code will have ensured that the [50,50] sstable will not have any keys that overlap with the [1,100] in the seqnum range [1,49]. The range of internal keys [fileMetadata.smallest, fileMetadata.largest] in each level 0 table may overlap.

The tables at any non-0 level are sorted by their internal key range and any two tables at the same non-0 level do not overlap.

The internal key ranges of two tables at different levels X and Y may overlap, for any X != Y.

Finally, for every internal key in a table at level X, there is no internal key in a higher level table that has both the same user key and a higher sequence number.

func NewInitialVersion 

func NewInitialVersion(comparer *base.Comparer) *Version

NewInitialVersion creates a version with no files. The L0Organizer should be freshly created.

func NewVersionForTesting 

func NewVersionForTesting(
	comparer *base.Comparer, l0Organizer *L0Organizer, files [7][]*TableMetadata,
) *Version

NewVersionForTesting constructs a new Version with the provided files. It requires the provided files are already well-ordered. The L0Organizer should be freshly created.

func ParseVersionDebug 

func ParseVersionDebug(
	comparer *base.Comparer, l0Organizer *L0Organizer, s string,
) (*Version, error)

ParseVersionDebug parses a Version from its DebugString output.

func (*Version) AllLevelsAndSublevels 

func (v *Version) AllLevelsAndSublevels() iter.Seq2[Layer, LevelSlice]

AllLevelsAndSublevels returns an iterator that produces a Layer, LevelSlice pair for each L0 sublevel (from top to bottom) and each level below L0.

func (*Version) CalculateInuseKeyRanges 

func (v *Version) CalculateInuseKeyRanges(
	l0Organizer *L0Organizer, level, maxLevel int, smallest, largest []byte,
) []base.UserKeyBounds

CalculateInuseKeyRanges examines table metadata in levels [level, maxLevel] within bounds [smallest,largest], returning an ordered slice of key ranges that include all keys that exist within levels [level, maxLevel] and within [smallest,largest].

func (*Version) CheckOrdering 

func (v *Version) CheckOrdering() error

CheckOrdering checks that the files are consistent with respect to increasing file numbers (for level 0 files) and increasing and non- overlapping internal key ranges (for level non-0 files).

func (*Version) Contains 

func (v *Version) Contains(level int, m *TableMetadata) bool

Contains returns a boolean indicating whether the provided file exists in the version at the given level. If level is non-zero then Contains binary searches among the files. If level is zero, Contains scans the entire level.

func (*Version) DebugString 

func (v *Version) DebugString() string

DebugString returns an alternative format to String() which includes sequence number and kind information for the sstable boundaries.

func (*Version) Next 

func (v *Version) Next() *Version

Next returns the next version in the list of versions.

func (*Version) Overlaps 

func (v *Version) Overlaps(level int, bounds base.UserKeyBounds) LevelSlice

Overlaps returns all elements of v.files[level] whose user key range intersects the given bounds. If level is non-zero then the user key bounds of v.files[level] are assumed to not overlap (although they may touch). If level is zero then that assumption cannot be made, and the given bounds are expanded to the union of those matching bounds so far and the computation is repeated until the bounds stabilize. The returned files are a subsequence of the input files, i.e., the ordering is not changed.

func (*Version) Ref 

func (v *Version) Ref()

Ref increments the version refcount.

func (*Version) Refs 

func (v *Version) Refs() int32

Refs returns the number of references to the version.

func (*Version) String 

func (v *Version) String() string

String implements fmt.Stringer, printing the TableMetadata for each level in the Version.

func (*Version) Unref 

func (v *Version) Unref()

Unref decrements the version refcount. If the last reference to the version was removed, the version is removed from the list of versions and the Deleted callback is invoked. Requires that the VersionList mutex is NOT locked.

func (*Version) UnrefLocked 

func (v *Version) UnrefLocked()

UnrefLocked decrements the version refcount. If the last reference to the version was removed, the version is removed from the list of versions and the Deleted callback is invoked. Requires that the VersionList mutex is already locked.

type VersionEdit 

type VersionEdit struct {
	// ComparerName is the value of Options.Comparer.Name. This is only set in
	// the first VersionEdit in a manifest (either when the DB is created, or
	// when a new manifest is created) and is used to verify that the comparer
	// specified at Open matches the comparer that was previously used.
	ComparerName string

	// MinUnflushedLogNum is the smallest WAL log file number corresponding to
	// mutations that have not been flushed to an sstable.
	//
	// This is an optional field, and 0 represents it is not set.
	MinUnflushedLogNum base.DiskFileNum

	// ObsoletePrevLogNum is a historic artifact from LevelDB that is not used by
	// Pebble, RocksDB, or even LevelDB. Its use in LevelDB was deprecated in
	// 6/2011. We keep it around purely for informational purposes when
	// displaying MANIFEST contents.
	ObsoletePrevLogNum uint64

	// The next file number. A single counter is used to assign file numbers
	// for the WAL, MANIFEST, sstable, and OPTIONS files.
	NextFileNum uint64

	// LastSeqNum is an upper bound on the sequence numbers that have been
	// assigned in flushed WALs. Unflushed WALs (that will be replayed during
	// recovery) may contain sequence numbers greater than this value.
	LastSeqNum base.SeqNum

	// A file num may be present in both deleted files and new files when it
	// is moved from a lower level to a higher level (when the compaction
	// found that there was no overlapping file at the higher level).
	DeletedTables map[DeletedTableEntry]*TableMetadata
	NewTables     []NewTableEntry
	// CreatedBackingTables can be used to preserve the FileBacking associated
	// with a physical sstable. This is useful when virtual sstables in the
	// latest version are reconstructed during manifest replay, and we also need
	// to reconstruct the FileBacking which is required by these virtual
	// sstables.
	//
	// INVARIANT: The FileBacking associated with a physical sstable must only
	// be added as a backing file in the same version edit where the physical
	// sstable is first virtualized. This means that the physical sstable must
	// be present in DeletedFiles and that there must be at least one virtual
	// sstable with the same FileBacking as the physical sstable in NewFiles. A
	// file must be present in CreatedBackingTables in exactly one version edit.
	// The physical sstable associated with the FileBacking must also not be
	// present in NewFiles.
	CreatedBackingTables []*FileBacking
	// RemovedBackingTables is used to remove the FileBacking associated with a
	// virtual sstable. Note that a backing sstable can be removed as soon as
	// there are no virtual sstables in the latest version which are using the
	// backing sstable, but the backing sstable doesn't necessarily have to be
	// removed atomically with the version edit which removes the last virtual
	// sstable associated with the backing sstable. The removal can happen in a
	// future version edit.
	//
	// INVARIANT: A file must only be added to RemovedBackingTables if it was
	// added to CreateBackingTables in a prior version edit. The same version
	// edit also cannot have the same file present in both CreateBackingTables
	// and RemovedBackingTables. A file must be present in RemovedBackingTables
	// in exactly one version edit.
	RemovedBackingTables []base.DiskFileNum
	// NewBlobFiles holds the metadata for all new blob files introduced within
	// the version edit.
	NewBlobFiles []*BlobFileMetadata
	// DeletedBlobFiles holds all blob files that became unreferenced during the
	// version edit. These blob files must not be referenced by any sstable in
	// the resulting Version.
	//
	// While replaying a MANIFEST, the values are nil. Otherwise the values must
	// not be nil.
	DeletedBlobFiles map[base.DiskFileNum]*BlobFileMetadata
}

VersionEdit holds the state for an edit to a Version along with other on-disk state (log numbers, next file number, and the last sequence number).

func ParseVersionEditDebug 

func ParseVersionEditDebug(s string) (_ *VersionEdit, err error)

ParseVersionEditDebug parses a VersionEdit from its DebugString implementation.

It doesn't recognize all fields; this implementation can be filled in as needed.

func (*VersionEdit) DebugString 

func (v *VersionEdit) DebugString(fmtKey base.FormatKey) string

DebugString is a more verbose version of String(). Use this in tests.

func (*VersionEdit) Decode 

func (v *VersionEdit) Decode(r io.Reader) error

Decode decodes an edit from the specified reader.

Note that the Decode step will not set the FileBacking for virtual sstables and the responsibility is left to the caller. However, the Decode step will populate the NewFileEntry.BackingFileNum in VersionEdit.NewFiles.

func (*VersionEdit) Encode 

func (v *VersionEdit) Encode(w io.Writer) error

Encode encodes an edit to the specified writer.

func (*VersionEdit) String 

func (v *VersionEdit) String() string

String implements fmt.Stringer for a VersionEdit.

type VersionList 

type VersionList struct {
	// contains filtered or unexported fields
}

VersionList holds a list of versions. The versions are ordered from oldest to newest.

func (*VersionList) Back 

func (l *VersionList) Back() *Version

Back returns the newest version in the list. Note that this version is only valid if Empty() returns true.

func (*VersionList) Empty 

func (l *VersionList) Empty() bool

Empty returns true if the list is empty, and false otherwise.

func (*VersionList) Front 

func (l *VersionList) Front() *Version

Front returns the oldest version in the list. Note that this version is only valid if Empty() returns true.

func (*VersionList) Init 

func (l *VersionList) Init(mu *sync.Mutex)

Init initializes the version list.

func (*VersionList) PushBack 

func (l *VersionList) PushBack(v *Version)

PushBack adds a new version to the back of the list. This new version becomes the "newest" version in the list.

func (*VersionList) Remove 

func (l *VersionList) Remove(v *Version)

Remove removes the specified version from the list.

type VirtualBackings 

type VirtualBackings struct {
	// contains filtered or unexported fields
}

VirtualBackings maintains information about the set of backings that support virtual tables in the latest version.

The VirtualBackings set internally maintains for each backing the number of virtual tables that use that backing and the sum of their virtual sizes. When a backing is added to the set, it initially is not associated with any tables. AddTable/RemoveTable are used to maintain the set of tables that are associated with a backing. Finally, a backing can only be removed from the set when it is no longer in use.

-- Protection API --

VirtualBackings exposes a Protect/Unprotect API. This is used to allow external file ingestions to reuse existing virtual backings. Because ingestions can run in parallel with other operations like compactions, it is possible for a backing to "go away" in-between the time the ingestion decides to use it and the time the ingestion installs a new version. The protection API solves this problem by keeping backings alive, even if they become otherwise unused by any tables.

Backing protection achieves two goals:

  • it must prevent the removal of the backing from the latest version, where removal means becoming part of a VersionEdit.RemovedBackingTables. This is achieved by treating the backing as "in use", preventing Unused() from reporting it.
  • it must prevent the backing from becoming obsolete (i.e. reaching a ref count of 0). To achieve this, VirtualBackings takes a ref on each backing when it is added; this ref must be released after the backing is removed (when it is ok for the backing to be reported as obsolete).

For example, say we have virtual table T1 with backing B1 and an ingestion tries to reuse the file. This is what will usually happen (the happy case):

  • latest version is V1 and it contains T1(B1).
  • ingestion request comes for another virtual portion of B1. Ingestion process finds B1 and calls Protect(B1).
  • ingestion completes, installs version V2 which has T1(B1) and a new T2(B1), and calls Unprotect(B1).

In this path, the Protect/Unprotect calls do nothing. But here is what could happen (the corner case):

  • latest version is V1 and it contains T1(B1).
  • ingestion request comes for another virtual portion of B1. Ingestion process finds B1 and calls Protect(B1).
  • compaction completes and installs version V2 which no longer has T1. But because B1 is protected, V2 still has B1.
  • ingestion completes, installs version V3 which has a new T2(B1) and calls Unprotect(B1).

If instead the ingestion fails to complete, the last step becomes:

  • ingestion fails, calls Unprotect(B1). B1 is now Unused() and the next version (applied by whatever next operation is) will remove B1.

func MakeVirtualBackings 

func MakeVirtualBackings() VirtualBackings

MakeVirtualBackings returns empty initialized VirtualBackings.

func (*VirtualBackings) AddAndRef 

func (bv *VirtualBackings) AddAndRef(backing *FileBacking)

AddAndRef adds a new backing to the set and takes a reference on it. Another backing for the same DiskFileNum must not exist.

The added backing is unused until it is associated with a table via AddTable or protected via Protect.

func (*VirtualBackings) AddTable 

func (bv *VirtualBackings) AddTable(m *TableMetadata)

AddTable is used when a new table is using an exiting backing. The backing must be in the set already.

func (*VirtualBackings) Backings 

func (bv *VirtualBackings) Backings() []*FileBacking

Backings returns all backings in the set, in unspecified order.

func (*VirtualBackings) DiskFileNums 

func (bv *VirtualBackings) DiskFileNums() []base.DiskFileNum

DiskFileNums returns disk file nums of all the backing in the set, in sorted order.

func (*VirtualBackings) ForEach 

func (bv *VirtualBackings) ForEach(fn func(backing *FileBacking))

ForEach calls fn on each backing, in unspecified order.

func (*VirtualBackings) Get 

func (bv *VirtualBackings) Get(n base.DiskFileNum) (_ *FileBacking, ok bool)

Get returns the backing with the given DiskFileNum, if it is in the set.

func (*VirtualBackings) Protect 

func (bv *VirtualBackings) Protect(n base.DiskFileNum)

Protect prevents a backing from being reported as unused until a corresponding Unprotect call is made. The backing must be in the set.

Multiple Protect calls can be made for the same backing; each must have a corresponding Unprotect call before the backing can become unused.

func (*VirtualBackings) Remove 

func (bv *VirtualBackings) Remove(n base.DiskFileNum)

Remove removes a backing. The backing must not be in use; normally backings are removed once they are reported by Unused().

It is up to the caller to release the reference took by AddAndRef.

func (*VirtualBackings) RemoveTable 

func (bv *VirtualBackings) RemoveTable(m *TableMetadata)

RemoveTable is used when a table using a backing is removed. The backing is not removed from the set, even if it becomes unused.

func (*VirtualBackings) Stats 

func (bv *VirtualBackings) Stats() (count int, totalSize uint64)

Stats returns the number and total size of all the virtual backings.

func (*VirtualBackings) String 

func (bv *VirtualBackings) String() string

func (*VirtualBackings) Unprotect 

func (bv *VirtualBackings) Unprotect(n base.DiskFileNum)

Unprotect reverses a Protect call.

func (*VirtualBackings) Unused 

func (bv *VirtualBackings) Unused() []*FileBacking

Unused returns all backings that are and no longer used by the latest version and are not protected, in DiskFileNum order.

func (*VirtualBackings) Usage 

func (bv *VirtualBackings) Usage(n base.DiskFileNum) (useCount int, virtualizedSize uint64)

Usage returns information about the usage of a backing, specifically:

  • useCount: the number of virtual tables that use this backing;
  • virtualizedSize: the sum of sizes of virtual tables that use the backing.

During compaction picking, we compensate a virtual sstable file size by (FileBacking.Size - virtualizedSize) / useCount. The intuition is that if FileBacking.Size - virtualizedSize is high, then the space amplification due to virtual sstables is high, and we should pick the virtual sstable with a higher priority.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.
⌂ 换网址