compactionv2

package
v4.0.0-rc.2 Latest Latest
Warning

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

Go to latest
Published: Nov 4, 2026 License: AGPL-3.0 Imports: 11 Imported by: 0

Documentation

Overview

Package compactionv2 plans K-way compaction from sections with inclusive ordering-key bounds. CalculateRuns keeps physical objects intact while forming strict merge inputs. IsConverged treats touching-only object boundaries as a terminal fixed point. Plan batches P runs into ceil(P/K) tasks that each produce one output sequence.

Index

Constants

View Source
const (
	// DefaultSizeLevelBase is the default upper bound of level 0, in bytes of
	// uncompressed log data. Empirically, a fresh run is one object of about 6GiB. One
	// fresh run stays in level 0, and a merge of three or more moves up a
	// level.
	DefaultSizeLevelBase uint64 = 16 << 30

	// DefaultSizeLevelRatio is the default size ratio between levels. It
	// matches the default log merge fan-in (K) of 8. For levels 1 and above,
	// a merge of 8 runs from one level lands in the next level. Level 0 has
	// no lower bound, so this does not hold there.
	DefaultSizeLevelRatio uint64 = 8
)

Variables

View Source
var ResultRecordSchema = arrow.NewSchema([]arrow.Field{
	{Name: "path", Type: arrow.BinaryTypes.String, Nullable: false},
}, nil)

ResultRecordSchema is the Arrow schema of the record a compaction job emits to report its replacement index: exactly one row.

Functions

func BelowMinCompactionSize

func BelowMinCompactionSize(runs []Run, minSize uint64) bool

BelowMinCompactionSize reports whether the runs' total size is below minSize.

func CompactedIndexPath

func CompactedIndexPath(tenant string, r io.Reader) (string, error)

CompactedIndexPath returns the object-storage key for a compacted index object whose content is read from r, using the same content hash as ingestion object naming. Layout: indexes/tenants/<tenant>/<h2>/<hrest>.

func CompactedLogObjectPath

func CompactedLogObjectPath(tenant string, r io.Reader) (string, error)

CompactedLogObjectPath returns the object-storage key for a compacted log object whose content is read from r. Layout: objects/tenants/<tenant>/<h2>/<hrest>.

func IsConverged

func IsConverged[K any](sections []Section[K], compare CompareFunc[K]) bool

IsConverged reports whether a set of sections have no positive overlap. Touching bounds are considered converged because rewriting cannot remove their ambiguity. It does not mutate sections.

func Plan

func Plan(runs []Run, tenant string, k int) []*compactionv2pb.TaskSpec

Plan groups [runs] into ceil(P/K) task batches: runs [0..K) -> task 0, runs [K..2K) -> task 1, ... The output is deterministic for a given input.

Special cases:

  • len(runs) == 0 -> returns nil (no tasks).
  • k >= P -> returns a single TaskSpec containing all runs.

Types

type CompareFunc

type CompareFunc[K any] func(a, b K) int

CompareFunc compares two ordering keys.

type ResultArtifact

type ResultArtifact struct {
	Path string
}

ResultArtifact identifies the replacement index produced by a completed task. It is usable only when returned with a nil error. Its index and newly referenced log objects have been uploaded, but it has not been published to the ToC. The zero value is invalid.

func (*ResultArtifact) FromRecordBatch

func (a *ResultArtifact) FromRecordBatch(rec arrow.RecordBatch) error

FromRecordBatch decodes exactly one artifact with a non-null, nonempty path. The artifact does not borrow memory from rec. A failed decode clears the receiver.

func (ResultArtifact) ToRecordBatch

func (a ResultArtifact) ToRecordBatch(mem memory.Allocator) (arrow.RecordBatch, error)

ToRecordBatch encodes the artifact as a single-row record batch under ResultRecordSchema. The caller owns the returned record batch.

func (ResultArtifact) Validate

func (a ResultArtifact) Validate() error

Validate checks that the artifact identifies a replacement index.

type Run

type Run interface {
	// Sections returns the run's sections in sorted order.
	Sections() []*compactionv2pb.SectionRef
	// Size returns the sum of the run's sections' UncompressedSize.
	Size() uint64
}

Run is one strictly ordered sequence of sections.

func CalculateRuns

func CalculateRuns[K any](sections []Section[K], compare CompareFunc[K]) []Run

CalculateRuns groups sections into N disjoint, contiguous runs based on the Min and Max sort keys. Sections of the same object are treated as one indivisible unit and always land in the same run. It panics if a section has a nil Ref.

type Section

type Section[K any] struct {
	Ref      *compactionv2pb.SectionRef
	Min, Max K
}

Section associates a section reference with its inclusive ordering-key bounds.

type SizeLeveledStrategy

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

SizeLeveledStrategy groups runs into levels by their uncompressed size. Runs in the same level have a similar size, so merging them keeps write amplification low.

Level 0 holds runs below base. Level n, for n >= 1, holds runs in [base*ratio^(n-1), base*ratio^n). The top level has no upper size bound.

A level is full when it holds k runs, and a merge task holds at most k runs.

func NewSizeLeveledStrategy

func NewSizeLeveledStrategy(base, ratio uint64, k int) (*SizeLeveledStrategy, error)

NewSizeLeveledStrategy returns a strategy with the given level 0 bound, ratio between levels, and maximum runs per merge task k.

base must be greater than 0 and ratio must be at least 2. k must be at least 2, because with k of 1 a single run always needs compaction and compaction never stops.

func (*SizeLeveledStrategy) NeedsCompaction

func (s *SizeLeveledStrategy) NeedsCompaction(runs []Run) bool

NeedsCompaction reports whether any level holds at least k runs.

A window where every level holds fewer than k runs counts as converged, even if its runs overlap. Plan merges the k runs of a full level into one run, so each compaction reduces the number of runs and compaction stops.

func (*SizeLeveledStrategy) Plan

func (s *SizeLeveledStrategy) Plan(runs []Run, tenant string) (merges []*compactionv2pb.TaskSpec, unmerged []Run)

Plan splits each level into groups of at most k runs, so no group mixes levels. Each group of two or more runs becomes a merge task.

A run alone in its level, or left over after the split, has nothing to merge with. Plan returns it in unmerged instead of a task, so the caller can keep it without rewriting its data. Every run lands in exactly one merge task or in unmerged.

func (*SizeLeveledStrategy) RunsPerLevel

func (s *SizeLeveledStrategy) RunsPerLevel(runs []Run) []int

RunsPerLevel returns the number of runs in each level, from level 0 up to the highest level that holds a run.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL