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
- Variables
- func BelowMinCompactionSize(runs []Run, minSize uint64) bool
- func CompactedIndexPath(tenant string, r io.Reader) (string, error)
- func CompactedLogObjectPath(tenant string, r io.Reader) (string, error)
- func IsConverged[K any](sections []Section[K], compare CompareFunc[K]) bool
- func Plan(runs []Run, tenant string, k int) []*compactionv2pb.TaskSpec
- type CompareFunc
- type ResultArtifact
- type Run
- type Section
- type SizeLeveledStrategy
Constants ¶
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 ¶
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 ¶
BelowMinCompactionSize reports whether the runs' total size is below minSize.
func CompactedIndexPath ¶
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 ¶
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 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.