manifest

package
v0.2.16 Latest Latest
Warning

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

 Go to latest Published: Nov 12, 2026 License: BSD-3-Clause Imports: 39 Imported by: 0

Documentation

Index

Constants

View Source 
const NumLevels = 7

NumLevels is the number of levels a Version contains.

View Source 
const RetainedFileTrackingBytes = 192

Variables

View Source 
var EndScanCursor = ScanCursor{Level: NumLevels}

EndScanCursor is a cursor that is past all files in the LSM.

Functions

func CheckOrdering 

func CheckOrdering(comparer *base.Comparer, 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 ExtendKeyRange 

func ExtendKeyRange(
	ucmp Compare, bounds base.UserKeyBounds, iters ...iter.Seq[*TableMetadata],
) base.UserKeyBounds

ExtendKeyRange returns the narrowest UserKeyBounds that encompass the provided bounds and the bounds of all the TableMetadata in iters.

func KeyRange 

func KeyRange(ucmp Compare, iters ...iter.Seq[*TableMetadata]) base.UserKeyBounds

KeyRange returns the narrowest UserKeyBounds that encompass the bounds of all the TableMetadata in iters.

func MakeRetainedFileIndex added in v0.2.15 

func MakeRetainedFileIndex(
	tables []*TableMetadata, blobs []BlobFileMetadata,
) Result[RetainedFileIndex]

MakeRetainedFileIndex is consumed by immutable ingested flushables; versions instead update their cloned index directly from the actual native edit.

func RetainedFileIndexBudget added in v0.2.15 

func RetainedFileIndexBudget(index *RetainedFileIndex, annotation uint64) Result[uint64]

RetainedFileIndexBudget is a conservative O(1) bound for the indexed native graph, not file payload/dataset bytes. Each nonempty B-tree node contains at least one item. Point, range, disjoint L0 sublevels and membership/blob trees therefore have at most five nodes per indexed file. Metadata/region endpoint storage is conservatively counted three times; all actual key lengths and reference capacities were recorded when the original immutable item entered.

func RetainedFileIndexContains added in v0.2.15 

func RetainedFileIndexContains(index *RetainedFileIndex, blob bool, number base.DiskFileNum) bool

func RetainedLevelSliceItems added in v0.2.6 

func RetainedLevelSliceItems(
	slice LevelSlice, annotationBytes uint64,
) iter.Seq[RetainedVersionItem]

RetainedLevelSliceItems also covers ingested files still in a flushable queue.

func RetainedVersionBudget added in v0.2.15 

func RetainedVersionBudget(version *Version, annotation uint64) Result[uint64]

func RetainedVersionContains added in v0.2.15 

func RetainedVersionContains(version *Version, blob bool, number base.DiskFileNum) bool

func RetainedVersionItems added in v0.2.6 

func RetainedVersionItems(v *Version, annotationBytes uint64) iter.Seq[RetainedVersionItem]

RetainedVersionItems visits the immutable graph without building a file list. The caller owns a version reference and must stop the sequence before releasing it.

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
	// ReferencedBackingValueSize is the sum of the length of the uncompressed
	// values in all blob files in the set that are still referenced by live
	// backing tables (i.e., in the latest version). Note that this may
	// overcount values when virtual sstables with the same backing are present,
	// as each virtual sstable contributes the full backing table's value size.
	ReferencedBackingValueSize 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 BlobFileAnnotationIdx 

type BlobFileAnnotationIdx int

BlobFileAnnotationIdx is an index associated with a specific blob file annotator. Blob file annotators should have distinct BlobFileAnnotationIdx values.

func NewBlobAnnotationIdx 

func NewBlobAnnotationIdx() BlobFileAnnotationIdx

NewBlobAnnotationIdx generates a unique BlobFileAnnotationIdx that can be used with blob file annotators. It should be called during global initialization.

type BlobFileAnnotator 

type BlobFileAnnotator[T any] struct {
	// contains filtered or unexported fields
}

A BlobFileAnnotator defines a computation over a version's set of blob files.

func MakeBlobFileAnnotator 

func MakeBlobFileAnnotator[T any](
	idx BlobFileAnnotationIdx, funcs BlobFileAnnotatorFuncs[T],
) BlobFileAnnotator[T]

func (*BlobFileAnnotator[T]) Annotation 

func (a *BlobFileAnnotator[T]) Annotation(blobFiles *BlobFileSet) T

Annotation calculates the annotation defined by this BlobFileAnnotator for all blob files in the given set.

type BlobFileAnnotatorFuncs 

type BlobFileAnnotatorFuncs[T any] struct {
	// Merge combines two values src and dst into dst.
	Merge func(dst *T, src T)

	// BlobFile computes the annotation for a blob file in a tree. Returns the
	// value and a bool flag indicating whether 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.
	BlobFile func(BlobFileMetadata) (_ T, cacheOK bool)
}

BlobFileAnnotatorFuncs groups the functions that define a blob file annotator.

type BlobFileMetadata 

type BlobFileMetadata struct {
	// FileID is a stable identifier for referencing a blob file containing
	// values. It is the same domain as the BlobReference.FileID. Blob
	// references use the FileID to look up the physical blob file containing
	// referenced values.
	FileID base.BlobFileID
	// Physical is the metadata for the physical blob file.
	//
	// If the blob file has been replaced, Physical.FileNum ≠ FileID. Physical
	// is always non-nil.
	Physical *PhysicalBlobFile
}

BlobFileMetadata encapsulates a blob file ID used to identify a particular blob file, and a reference-counted physical blob file. Different Versions may contain different BlobFileMetadata with the same FileID, but if so they necessarily point to different PhysicalBlobFiles.

See the BlobFileSet documentation for more details.

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().

func (BlobFileMetadata) Ref 

func (m BlobFileMetadata) Ref()

Ref increments the reference count for the physical blob file.

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.

func (BlobFileMetadata) Unref 

func (m BlobFileMetadata) Unref(of ObsoleteFilesSet)

Unref decrements the reference count for the physical blob file. If the reference count reaches zero, the blob file is added to the provided obsolete files set.

type BlobFileSet 

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

BlobFileSet contains a set of blob files that are referenced by a version. It's used to maintain reference counts on blob files still in-use by some referenced version.

It's backed by a copy-on-write B-Tree of BlobFileMetadata keyed by FileID. A version edit that adds or deletes m blob files updates m⋅log(n) nodes in the B-Tree.

Initially a BlobFileMetadata has a FileID that matches the DiskFileNum of the backing physical blob file. However a blob file may be replaced without replacing the referencing TableMetadatas, which is recorded in the BlobFileSet by replacing the old BlobFileMetadata with a different PhysicalBlobFile.

func MakeBlobFileSet 

func MakeBlobFileSet(entries []BlobFileMetadata) BlobFileSet

MakeBlobFileSet creates a BlobFileSet from the given blob files.

func (*BlobFileSet) All 

func (s *BlobFileSet) All() iter.Seq[BlobFileMetadata]

All returns an iterator over all the blob files in the set.

func (*BlobFileSet) Count 

func (s *BlobFileSet) Count() int

Count returns the number of blob files in the set.

func (*BlobFileSet) Lookup 

func (s *BlobFileSet) Lookup(fileID base.BlobFileID) (base.ObjectInfo, bool)

Lookup returns the physical blob file backing the given file ID. It returns false for the second return value if the FileID is not present in the set.

func (*BlobFileSet) LookupPhysical 

func (s *BlobFileSet) LookupPhysical(fileID base.BlobFileID) (*PhysicalBlobFile, bool)

LookupPhysical returns the *PhysicalBlobFile backing the given file ID. It returns false for the second return value if the FileID is not present in the set.

type BlobReference 

type BlobReference struct {
	// FileID identifies the referenced blob file. FileID is stable. If a blob
	// file is rewritten and a blob reference is preserved during a compaction,
	// the new sstable's BlobReference will preserve the same FileID.
	FileID base.BlobFileID
	// 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.
	ValueSize uint64
	// BackingValueSize is the sum of the lengths of the uncompressed values within the
	// blob file for which there exists a reference in the backing sstable. For non-virtual
	// sstables, this is the same as ValueSize.
	BackingValueSize uint64
	// EstimatedPhysicalSize is 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.
	EstimatedPhysicalSize uint64
}

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

func MakeBlobReference 

func MakeBlobReference(
	fileID base.BlobFileID, valueSize uint64, backingValueSize uint64, phys *PhysicalBlobFile,
) BlobReference

MakeBlobReference creates a BlobReference from the given file ID, value size, and physical 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) BlobFileIDByID 

func (br *BlobReferences) BlobFileIDByID(i base.BlobReferenceID) base.BlobFileID

BlobFileIDByID returns the BlobFileID for the identified BlobReference.

func (*BlobReferences) IDByBlobFileID 

func (br *BlobReferences) IDByBlobFileID(fileID base.BlobFileID) (base.BlobReferenceID, bool)

IDByBlobFileID returns the reference ID for the given BlobFileID. If the blob file ID is not found, the second return value is false. IDByBlobFileID is linear in the length of the BlobReferences slice.

type BlobRewriteHeuristic 

type BlobRewriteHeuristic struct {
	// CurrentTime returns the current time.
	CurrentTime func() time.Time
	// MinimumAge is the minimum age of a blob file that is considered for
	// rewrite and replacement.
	//
	// TODO(jackson): Support updating this at runtime. Lowering the value is
	// simple: pop from the recentlyCreated heap and push to the candidates
	// heap. Raising the value is more complex: we would need to iterate over
	// all the blob files in the candidates heap.
	MinimumAge time.Duration
}

BlobRewriteHeuristic configures the heuristic used to determine which blob files should be rewritten and replaced in order to reduce value-separation induced space amplification.

The heuristic divides blob files into three categories:

1. Fully referenced: Blob files that are fully referenced by live tables. 2. Recently created: Blob files with garbage that were recently created. 3. Eligible: Blob files with garbage that are old.

Files in the first category (fully referenced) should never be rewritten, because rewriting them has no impact on space amplification.

Among files that are not fully referenced, the heuristic separates files into files that were recently created (less than MinimumAgeSecs seconds old) and files that are old and eligible for rewrite. We defer rewriting recently created files under the assumption that their references may be removed through ordinary compactions. The threshold for what is considered recent is the MinimumAgeSecs field.

type BlobRewriteHeuristicStats 

type BlobRewriteHeuristicStats struct {
	CountFilesFullyReferenced int
	CountFilesTooRecent       int
	CountFilesEligible        int
	NextEligible              BlobFileMetadata
	NextEligibleLivePct       float64
	NextRewrite               BlobFileMetadata
	NextRewriteLivePct        float64
}

BlobRewriteHeuristicStats records statistics about the blob rewrite heuristic.

func (BlobRewriteHeuristicStats) String 

func (s BlobRewriteHeuristicStats) String() string

String implements fmt.Stringer.

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.BlobFileID]*PhysicalBlobFile
		// 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 is keyed by blob file ID and points to the physical blob file.
		Deleted map[base.BlobFileID]*PhysicalBlobFile
	}

	// AddedFileBacking is a map to support lookup so that we can populate the
	// TableBacking of virtual sstables during manifest replay.
	AddedFileBacking   map[base.DiskFileNum]*TableBacking
	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
}

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.

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) SafeFormat 

func (s CompactionState) SafeFormat(w redact.SafePrinter, _ rune)

SafeFormat implements redact.SafeFormatter.

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, h BlobRewriteHeuristic)

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) ReferencingTables 

func (s *CurrentBlobFileSet) ReferencingTables(fileID base.BlobFileID) []*TableMetadata

ReferencingTables returns a slice containing the set of tables that reference the blob file with the provided file ID. The returned slice is sorted by table number.

func (*CurrentBlobFileSet) ReplacementCandidate 

func (s *CurrentBlobFileSet) ReplacementCandidate() (BlobFileMetadata, bool)

ReplacementCandidate returns the next blob file that should be rewritten. If there are no candidates, the second return value is false. Successive calls to ReplacementCandidate may (but are not guaranteed to) return the same blob file until the blob file is replaced.

func (*CurrentBlobFileSet) Stats 

func (s *CurrentBlobFileSet) Stats() (AggregateBlobFileStats, BlobRewriteHeuristicStats)

Stats returns the cumulative stats across all blob files in the set and the stats for the rewrite heaps.

func (*CurrentBlobFileSet) String 

func (s *CurrentBlobFileSet) String() string

String implements fmt.Stringer.

type DeletedBlobFileEntry 

type DeletedBlobFileEntry struct {
	FileID  base.BlobFileID
	FileNum base.DiskFileNum
}

DeletedBlobFileEntry holds the state for a blob file deletion. The blob file ID may still be in-use with a different physical blob file.

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 ExciseOpEntry 

type ExciseOpEntry struct {
	Bounds base.UserKeyBounds
	SeqNum base.SeqNum
}

ExciseOpEntry holds the bounds and sequence number for an excise operation.

type InternalKey 

type InternalKey = base.InternalKey

InternalKey exports the base.InternalKey type.

type InternalKeyBounds 

type InternalKeyBounds = base.InternalKeyBounds

InternalKeyBounds exports the base.InternalKeyBounds type.

type KeyType 

type KeyType int8

KeyType denotes the type of keys: point, range, or both. 

const (
	// KeyTypePointAndRange indicates the joined keyspace of point and range
	// keys.
	KeyTypePointAndRange KeyType = iota
	// KeyTypePoint indicates the point keyspace. This key type includes point
	// keys and RANGEDELs.
	KeyTypePoint
	// KeyTypeRange indicates the range key (eg, RANGEKEYSET, RANGEKEYUNSET,
	// RANGEKEYDEL) keyspace.
	KeyTypeRange
)

func (KeyType) String 

func (kt KeyType) String() string

String implements fmt.Stringer.

type L0Compaction 

type L0Compaction struct {
	Bounds    base.UserKeyBounds
	IsIntraL0 bool
}

L0Compaction describes an active compaction with inputs from L0.

type L0CompactionFiles 

type L0CompactionFiles struct {
	Files []*TableMetadata

	FilesIncluded map[base.TableNum]struct{}
	// 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) SubLevelOf 

func (o *L0Organizer) SubLevelOf(f *TableMetadata) int

SubLevelOf returns the sublevel of the given L0 file.

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 LevelIterator 

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

LevelIterator iterates over a set of tables' 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) Current 

func (i *LevelIterator) Current() *TableMetadata

func (*LevelIterator) Filter 

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

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

func (*LevelIterator) First 

func (i *LevelIterator) First() *TableMetadata

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

func (*LevelIterator) Last 

func (i *LevelIterator) Last() *TableMetadata

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

func (*LevelIterator) Next 

func (i *LevelIterator) Next() *TableMetadata

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

func (*LevelIterator) PeekNext 

func (i *LevelIterator) PeekNext() *TableMetadata

PeekNext returns the next table without advancing the iterator.

func (*LevelIterator) Prev 

func (i *LevelIterator) Prev() *TableMetadata

Prev moves the iterator the previous table and returns it.

func (*LevelIterator) SeekGE 

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

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

More specifically, userKey is less than the table'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 tables 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 table with a smallest key (of the desired type) that is less than the given user key. This is the last table 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 tables to be sorted by user keys and non-overlapping.

func (LevelIterator) String 

func (i LevelIterator) String() string

func (*LevelIterator) Take 

func (i *LevelIterator) Take() LevelTable

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

type LevelMetadata 

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

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

func MakeLevelMetadata 

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

MakeLevelMetadata creates a LevelMetadata with the given tables.

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 tables in the level.

func (*LevelMetadata) Empty 

func (lm *LevelMetadata) Empty() bool

Empty indicates whether there are any tables in the level.

func (*LevelMetadata) EstimatedReferenceSize 

func (lm *LevelMetadata) EstimatedReferenceSize() uint64

EstimatedReferenceSize returns an estimate of the physical size of all the 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 table in the level. If it exists, returns a LevelSlice that contains just that table; 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 tables 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.

func (*LevelMetadata) VirtualTables 

func (lm *LevelMetadata) VirtualTables() metrics.CountAndSize

VirtualTables returns the count and total size of the virtual tables in the level.

type LevelSlice 

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

LevelSlice contains a slice of the tables 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 tables.

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

func NewLevelSliceKeySorted 

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

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

func NewLevelSliceSeqSorted 

func NewLevelSliceSeqSorted(tables []*TableMetadata) LevelSlice

NewLevelSliceSeqSorted constructs a LevelSlice over the provided tables, 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(tables []*TableMetadata) LevelSlice

NewLevelSliceSpecificOrder constructs a LevelSlice over the provided tables, ordering the tables 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 tables in the slice.

func (*LevelSlice) Empty 

func (ls *LevelSlice) Empty() bool

Empty indicates whether the slice contains any tables.

func (LevelSlice) HasOverlap 

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

HasOverlap is equivalent to ls.Overlaps(cmp, bounds).Len() > 0 but is more efficient.

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 tables 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 tables 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 tables 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 LevelTable 

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

LevelTable holds a table's metadata along with its position within a level of the LSM.

func (LevelTable) Slice 

func (lf LevelTable) Slice() LevelSlice

Slice constructs a LevelSlice containing only this table.

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 {
	TableBackings []*TableBacking
	BlobFiles     []*PhysicalBlobFile
}

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

func (*ObsoleteFiles) AddBacking 

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

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

func (*ObsoleteFiles) AddBlob 

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

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 TableBacking to the list of obsolete
	// files.
	AddBacking(*TableBacking)
	// AddBlob appends the provided BlobFileMetadata to the list of obsolete
	// files.
	AddBlob(*PhysicalBlobFile)
}

ObsoleteFilesSet accumulates files that now have zero references.

type PhysicalBlobFile 

type PhysicalBlobFile struct {
	// FileNum is an ID that uniquely identifies the blob file.
	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
}

PhysicalBlobFile is metadata describing a physical blob value file.

func ParsePhysicalBlobFileDebug 

func ParsePhysicalBlobFileDebug(s string) (_ *PhysicalBlobFile, err error)

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

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

func (*PhysicalBlobFile) FileInfo 

func (m *PhysicalBlobFile) FileInfo() (base.FileType, base.DiskFileNum)

FileInfo returns the type and file number of the blob file.

func (*PhysicalBlobFile) PopulateProperties 

func (m *PhysicalBlobFile) PopulateProperties(props *blob.FileProperties)

PopulateProperties populates the bob file properties. Can be called at most once for a TableBacking.

func (*PhysicalBlobFile) Properties 

func (m *PhysicalBlobFile) Properties() (_ *blob.FileProperties, ok bool)

Properties returns the blob file properties if they have been populated, or nil and ok=false if they were not.

The caller must not modify the returned stats.

func (*PhysicalBlobFile) Ref 

func (m *PhysicalBlobFile) Ref()

Ref increments the reference count for the blob file. This is the exported version of ref() for use by ingestedFlushable entries.

func (*PhysicalBlobFile) SafeFormat 

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

SafeFormat implements redact.SafeFormatter.

func (*PhysicalBlobFile) String 

func (m *PhysicalBlobFile) String() string

String implements fmt.Stringer.

func (*PhysicalBlobFile) Unref 

func (m *PhysicalBlobFile) Unref(of ObsoleteFilesSet)

Unref decrements the reference count for the blob file. If the reference count reaches zero, the blob file is added to the provided obsolete files set. This is the exported version of unref() for use by ingestedFlushable entries.

func (*PhysicalBlobFile) UserKeyBounds 

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

UserKeyBounds returns the user key bounds of the blob file, if known.

type PickFileAnnotatorFuncs 

type PickFileAnnotatorFuncs 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
}

type RangeKeyKinds 

type RangeKeyKinds uint8

RangeKeyKinds describes which kinds of range keys may be present in a table. 

const (
	// NoRangeKeys indicates that the table contains no range keys.
	NoRangeKeys RangeKeyKinds = iota
	// OnlyRangeKeyUnsetAndDelete indicates that the table contains range keys,
	// but only of the RANGEKEYUNSET and RANGEKEYDELETE kinds (no
	// RANGEKEYSETs).
	OnlyRangeKeyUnsetAndDelete
	// AnyRangeKeys indicates that the table may contain range keys of any
	// kind, including RANGEKEYSETs. This is the default when we don't know
	// for sure (e.g. older manifests, external/virtual tables).
	AnyRangeKeys
)

func (RangeKeyKinds) String 

func (r RangeKeyKinds) String() string

String implements fmt.Stringer.

type RetainedFileIndex added in v0.2.15 

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

RetainedFileIndex is immutable alongside its version/ingested flushable. Its scalar COW entries add no table/backing references. Ordinary version edits maintain the summary and membership in O(changed files * tree height).

type RetainedVersionItem added in v0.2.6 

type RetainedVersionItem struct {
	FileNum      base.DiskFileNum
	Blob         bool
	FileBytes    uint64
	WorkingBytes uint64
}

RetainedVersionItem is one bounded accounting observation. FileBytes are baseline storage, not extra retention until that exact backing becomes a zombie.

func RetainedBlobItem added in v0.2.6 

func RetainedBlobItem(file *PhysicalBlobFile) RetainedVersionItem

RetainedBlobItem projects the actual immutable physical blob metadata.

type ScanCursor 

type ScanCursor struct {
	// Level is the LSM level (0 to NumLevels). When Level=NumLevels, the cursor
	// is at the end and the scan is complete.
	Level int
	// Key is an inclusive lower bound for Smallest.UserKey for tables on Level.
	Key []byte
	// SeqNum is an inclusive lower bound for SeqNums.High for tables on Level
	// with Smallest.UserKey equaling Key. Used to break ties within L0, and also
	// used to position a cursor immediately after a given file.
	SeqNum base.SeqNum
}

ScanCursor represents a position in an LSM scan. The scan proceeds level-by-level, and within each level files are ordered by their smallest user key. For L0, we break ties using SeqNums.High since files can overlap.

A cursor can be thought of as a boundary between two files in a version (ordered by level, then by Smallest.UserKey, then by SeqNums.High). A file is either "before" or "after" the cursor.

func MakeScanCursor 

func MakeScanCursor(f *TableMetadata, level int) ScanCursor

MakeScanCursor returns a cursor that points exactly at the given file. This is used when comparing whether a candidate file is at or after a boundary position in the scan.

func MakeScanCursorAfterFile 

func MakeScanCursorAfterFile(f *TableMetadata, level int) ScanCursor

MakeScanCursorAfterFile returns a cursor that is immediately after the given file. This is used to advance the scan position past a file that has just been processed.

The cursor is positioned such that the file would be considered "before" the cursor (i.e., cursor.Compare(MakeScanCursor(f, level)) > 0).

func (*ScanCursor) AtEnd 

func (c *ScanCursor) AtEnd() bool

AtEnd returns true if the cursor is after all files in the LSM.

func (ScanCursor) Compare 

func (c ScanCursor) Compare(keyCmp base.Compare, other ScanCursor) int

Compare compares two cursors. Returns -1 if c < other, 0 if c == other, 1 if c > other.

func (*ScanCursor) FileIsAfterCursor 

func (c *ScanCursor) FileIsAfterCursor(cmp base.Compare, f *TableMetadata, level int) bool

FileIsAfterCursor returns true if the given file is strictly after the cursor position. This is useful for skipping files that have already been processed.

func (*ScanCursor) FirstExternalFileInLevelIter 

func (c *ScanCursor) FirstExternalFileInLevelIter(
	cmp base.Compare,
	objProvider objstorage.Provider,
	it LevelIterator,
	endBound base.UserKeyBoundary,
) *TableMetadata

FirstExternalFileInLevelIter finds the first external file after the cursor but which starts before the endBound. It is assumed that the iterator corresponds to cursor.Level.

func (*ScanCursor) NextExternalFile 

func (c *ScanCursor) NextExternalFile(
	cmp base.Compare, objProvider objstorage.Provider, bounds base.UserKeyBounds, v *Version,
) (_ *TableMetadata, level int)

NextExternalFile returns the first external file after the cursor, returning the file and the level. If no such file exists, returns nil fileMetadata.

func (*ScanCursor) NextExternalFileOnLevel 

func (c *ScanCursor) NextExternalFileOnLevel(
	cmp base.Compare, objProvider objstorage.Provider, endBound base.UserKeyBoundary, v *Version,
) *TableMetadata

NextExternalFileOnLevel returns the first external file on c.Level which is after c and with Smallest.UserKey within the end bound.

func (*ScanCursor) String 

func (c *ScanCursor) String() string

String implements fmt.Stringer.

type TableAnnotationIdx 

type TableAnnotationIdx int

TableAnnotationIdx is an index associated with a specific annotator. Table annotators should have distinct TableAnnotationIdx values.

func NewTableAnnotationIdx 

func NewTableAnnotationIdx() TableAnnotationIdx

NewTableAnnotationIdx generates a unique AnnotationIdx that can be used with a table annotator. It should be called during global initialization.

type TableAnnotator 

type TableAnnotator[T any] struct {
	// contains filtered or unexported fields
}

A TableAnnotator 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 MakePickFileAnnotator 

func MakePickFileAnnotator(
	idx TableAnnotationIdx, funcs PickFileAnnotatorFuncs,
) TableAnnotator[*TableMetadata]

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

func MakeTableAnnotator 

func MakeTableAnnotator[T any](
	idx TableAnnotationIdx, funcs TableAnnotatorFuncs[T],
) TableAnnotator[T]

func (*TableAnnotator[T]) LevelAnnotation 

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

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

func (*TableAnnotator[T]) LevelRangeAnnotation 

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

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

func (*TableAnnotator[T]) MultiLevelAnnotation 

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

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

func (*TableAnnotator[T]) VersionRangeAnnotation 

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

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

type TableAnnotatorFuncs 

type TableAnnotatorFuncs[T any] struct {
	// Merge combines two values src and dst into dst.
	Merge func(dst *T, src T)

	// Table computes the annotation for a table in a tree. Returns the value and
	// a bool flag indicating whether 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.
	Table func(*TableMetadata) (_ T, cacheOK bool)

	// PartialOverlap computes the annotation for a table that only partially
	// overlaps the given bounds. PartialOverlap is optional and only used with
	// range annotation functionality.
	//
	// PartialOverlap results are never cached.
	PartialOverlap func(*TableMetadata, base.UserKeyBounds) T
}

TableAnnotatorFuncs groups the functions that define a table annotator.

type TableBacking 

type TableBacking struct {
	DiskFileNum base.DiskFileNum
	Size        uint64

	// ReferencedBlobValueSizeTotal is the the sum of the length of uncompressed
	// values in all blob files for which there exists a reference in the backing
	// table.
	ReferencedBlobValueSizeTotal uint64
	// contains filtered or unexported fields
}

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

See the comment above the TableMetadata type for sstable terminology.

func (*TableBacking) IsUnused 

func (b *TableBacking) IsUnused() bool

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

func (*TableBacking) MustHaveRefs 

func (b *TableBacking) MustHaveRefs()

MustHaveRefs asserts that the backing has a positive refcount.

func (*TableBacking) PopulateProperties 

func (b *TableBacking) PopulateProperties(props *sstable.Properties) *TableBackingProperties

PopulateProperties populates the table stats. Can be called at most once for a TableBacking.

func (*TableBacking) Properties 

func (b *TableBacking) Properties() (_ *TableBackingProperties, ok bool)

Properties returns the backing properties if they have been populated, or nil and ok=false if they were not.

The caller must not modify the returned stats.

func (*TableBacking) Ref 

func (b *TableBacking) Ref()

Ref increments the backing's ref count.

func (*TableBacking) Unref 

func (b *TableBacking) Unref() int32

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

type TableBackingProperties 

type TableBackingProperties struct {
	// The number of entries in this table.
	NumEntries uint64
	// Total raw key size.
	RawKeySize uint64
	// Total raw value size. If values are separated, this includes the size of
	// the separated value, NOT the value handle.
	RawValueSize uint64
	// Total raw key size of point deletion tombstones. This value is comparable
	// to RawKeySize.
	RawPointTombstoneKeySize uint64
	// Sum of the raw value sizes carried by point deletion tombstones
	// containing size estimates. See the DeleteSized key kind. This value is
	// comparable to Raw{Key,Value}Size.
	RawPointTombstoneValueSize uint64
	// The number of point deletion entries ("tombstones") in this table that
	// carry a size hint indicating the size of the value the tombstone deletes.
	NumSizedDeletions uint64
	// The number of deletion entries in this table, including both point and
	// range deletions.
	NumDeletions uint64
	// The number of range deletions in this table.
	NumRangeDeletions uint64
	// The number of RANGEKEYDELs in this table.
	NumRangeKeyDels uint64
	// The number of RANGEKEYSETs in this table.
	NumRangeKeySets uint64
	// Total size of value blocks and value index block.
	ValueBlocksSize uint64

	// TombstoneDenseBlocksRatio is the fraction of data blocks in this table that
	// are tombstone-dense. See sstableCommonProperties.NumTombstoneDenseBlocks for
	// more details.
	TombstoneDenseBlocksRatio float64

	CompressionStats block.CompressionStats

	// ValueSeparationMinSize is the minimum value size for which values were
	// separated when writing the table. This value is 0 if the policy used
	// does not write blob files.
	ValueSeparationMinSize uint64
	// ValueSeparationBySuffixDisabled indicates if disabled applying special
	// value separation rules by KV suffix when writing the table. Note that
	// if value separation was disabled, this field is not meaningful.
	ValueSeparationBySuffixDisabled bool
}

TableBackingProperties are properties of the physical backing; they are directly derived from the sstable.Properties of the physical table.

These properties are held in memory for all tables; the size should be minimized.

func (*TableBackingProperties) NumPointDeletions 

func (p *TableBackingProperties) NumPointDeletions() uint64

NumPointDeletions is the number of point deletions in the sstable. For virtual sstables, this is an estimate.

type TableInfo 

type TableInfo struct {
	// FileNum is the internal DB identifier for the table.
	FileNum base.FileNum
	// Size is the size of the table in bytes. If the table is physical, this is
	// the same with the backing size. If the table is virtual, this is an
	// estimation of how much data the virtual table references.
	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
	// contains filtered or unexported fields
}

TableInfo contains the common information for table related events.

func (*TableInfo) GetBlobReferenceFiles 

func (t *TableInfo) GetBlobReferenceFiles() []base.BlobFileID

GetBlobReferenceFiles returns the list of blob file numbers referenced by the table.

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

	// TableBacking is the physical file that backs either physical or virtual
	// sstables.
	TableBacking *TableBacking

	// 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 == TableBacking.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 == TableBacking.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
	// SeqNums holds the 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 SeqNums.Low or
	// SeqNums.High within virtual sstable bounds.
	SeqNums base.SeqNumRange

	// 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 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

	// 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
	// HasPointKeys tracks whether the table (possibly) contains point keys
	// (including RANGEDELs). If a table contains only range deletions,
	// HasPointsKeys is still true.
	//
	// For virtual tables, it can be true even if no point keys are visible in the
	// virtual table.
	HasPointKeys bool
	// HasRangeKeys tracks whether the table (possibly) contains any range keys.
	//
	// For virtual tables, it can be true even if no range keys are visible in the
	// virtual table.
	//
	// Equivalent to RangeKeyKinds != NoRangeKeys; kept as a separate convenience
	// field for symmetry with HasPointKeys.
	HasRangeKeys bool
	// RangeKeyKinds describes which kinds of range keys may be present in the
	// table. In some cases (older manifests, external/virtual tables) we don't
	// have full information; in those cases AnyRangeKeys is used as a defensive
	// default whenever the table is known to have range keys.
	RangeKeyKinds RangeKeyKinds
	// 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 TableBacking. 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 TableBacking 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 TableBacking.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 *TableBacking)

AttachVirtualBacking attaches an existing TableBacking 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, kinds RangeKeyKinds, 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 kinds describe which range key kinds are (potentially) present in the new bounds; the resulting RangeKeyKinds field is the maximum of the existing and new values, so a later call cannot downgrade an existing AnyRangeKeys. Callers without precise information should pass AnyRangeKeys defensively. 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) FileInfo 

func (m *TableMetadata) FileInfo() (base.FileType, base.DiskFileNum)

ObjectInfo implements the base.ObjectInfo interface.

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 TableBacking which is required by a physical sstable TableMetadata.

Ensure that the state required by TableBacking, 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 TableBacking.

func (*TableMetadata) InitVirtualBacking 

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

InitVirtualBacking creates a new TableBacking 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) PopulateStats 

func (m *TableMetadata) PopulateStats(stats *TableStats)

PopulateStats populates the table stats. Can be called at most once for a 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 TableBacking.

func (*TableMetadata) ScaleStatistic 

func (m *TableMetadata) ScaleStatistic(value uint64) uint64

ScaleStatistic scales the given value by the table-size:backing-size ratio if the table is virtual. Returns the unchanged value when the table is not virtual.

The scaling rounds up so any non-zero value stays non-zero.

func (*TableMetadata) ScaleStatisticFloat 

func (m *TableMetadata) ScaleStatisticFloat(value float64) float64

ScaleStatisticFloat scales the given value by the table-size:backing-size ratio if the table is virtual. Returns the unchanged value when the table is not virtual.

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) Stats 

func (m *TableMetadata) Stats() (_ *TableStats, ok bool)

Stats returns the table statistics if they have been populated, or nil and ok=false if they were not.

The caller must not modify the returned stats.

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 the table's sequence number range is a single integer.

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 the table's backing file becomes obsolete, it's 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 {
	// 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
}

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

	// BlobFiles holds the set of physical blob files that are referenced by the
	// version. The BlobFileSet is responsible for maintaining reference counts
	// on physical blob files so that they remain on storage until they're no
	// longer referenced by any version.
	BlobFiles BlobFileSet

	// RangeKeySetRegions tracks regions that may contain range-key-sets. The
	// property is the number of tables with RangeKeyKinds=AnyRangeKeys whose
	// range-key bounds overlap the region.
	RangeKeySetRegions regiontree.T[[]byte, int]

	// The callback to invoke when the last reference to a version is
	// removed. Will be called with list.mu held.
	Deleted func(obsolete ObsoleteFiles)
	// 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 NewVersionWithFiles 

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

NewVersionWithFiles constructs a new Version with the provided files. The per-level B-Trees are built using the canonical comparators (`btreeCmpSeqNum` for L0, `btreeCmpSmallestKey` for L1+); tree iteration reflects that order regardless of the order of `files`. 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) AllTables 

func (v *Version) AllTables() iter.Seq2[Layer, *TableMetadata]

AllTables returns an iterator over all tables in the version.

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) Comparer 

func (v *Version) Comparer() *base.Comparer

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) DebugStringFormatKey 

func (v *Version) DebugStringFormatKey(fmtKey base.FormatKey) string

DebugStringFormatKey is like DebugString but allows overriding key formatting with the provided FormatKey.

func (*Version) HasOverlap 

func (v *Version) HasOverlap(level int, bounds base.UserKeyBounds) bool

HasOverlap is equivalent to len(v.Overlaps(level, bounds)) > 0 but more efficient.

func (*Version) MaxReadAmp 

func (v *Version) MaxReadAmp() int

MaxReadAmp returns the number of non-empty sublevels and levels in the Version. This is the maximum number of sstables that a point read must consult.

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) ReadLoanPinnedBytes added in v0.2.5 

func (v *Version) ReadLoanPinnedBytes(ctx context.Context, annotationBytes uint64) (uint64, error)

ReadLoanPinnedBytes counts the immutable version graph retained by a read loan, not SSTable/file payload sizes or the process heap. Shared nodes may be conservatively counted more than once. Current engine annotation payloads have the fixed maximum supplied by their actual package's typed definitions.

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. They're
	// also allowed to contain sequence numbers less than or equal to 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 TableBacking 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 TableBacking which is required by these virtual
	// sstables.
	//
	// INVARIANT: The TableBacking 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 TableBacking as the physical sstable in NewFiles. A
	// file must be present in CreatedBackingTables in exactly one version edit.
	// The physical sstable associated with the TableBacking must also not be
	// present in NewFiles.
	CreatedBackingTables []*TableBacking
	// RemovedBackingTables is used to remove the TableBacking 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 physical blob files that became unused during
	// the version edit.
	//
	// A physical blob file may become unused if the corresponding BlobFileID
	// becomes unreferenced during the version edit. In this case the BlobFileID
	// is not referenced by any sstable in the resulting Version.
	//
	// A physical blob file may also become unused if it is being replaced by a
	// new physical blob file. In this case NewBlobFiles must contain a
	// BlobFileMetadata with the same BlobFileID.
	//
	// While replaying a MANIFEST, the values are nil. Otherwise the values must
	// not be nil.
	DeletedBlobFiles map[DeletedBlobFileEntry]*PhysicalBlobFile

	// ExciseBoundsRecord holds excise operations as a slice of entries.
	ExciseBoundsRecord []ExciseOpEntry
}

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 TableBacking for virtual sstables and the responsibility is left to the caller. However, the Decode step will populate the NewTableEntry.BackingFileNum in VersionEdit.NewTables.

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 false.

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 false.

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 *TableBacking, placement base.Placement)

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, level int)

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

func (*VirtualBackings) All 

func (bv *VirtualBackings) All() iter.Seq[*TableBacking]

All returns an iterator over all backings, 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) Get 

func (bv *VirtualBackings) Get(n base.DiskFileNum) (_ *TableBacking, 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(backing base.DiskFileNum, table base.TableNum)

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) ReplacementCandidate 

func (bv *VirtualBackings) ReplacementCandidate() (
	referencedDataFraction float64,
	backing *TableBacking,
	tables [NumLevels][]*TableMetadata,
)

ReplacementCandidate returns the backing with the lowest ratio of data referenced by virtual tables to total size, along with the list of virtual tables that use the backing. If there are no backings in the set, nil is returned.

func (*VirtualBackings) Stats 

func (bv *VirtualBackings) Stats() metrics.CountAndSizeByPlacement

Stats returns the number and total size of all the virtual backings, broken down by placement.

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() []*TableBacking

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 (TableBacking.Size - virtualizedSize) / useCount. The intuition is that if TableBacking.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.
⌂ 换网址