Module trace

An append-only collection of compactable update batches. The Spine below is a fork of Differential Dataflow’s Spine with minimal modifications. The original Spine code is designed for incremental (via “fuel“ing) synchronous merge of in-memory batches. Persist doesn’t want compaction to block incoming writes and, in fact, may in the future elect to push the work of compaction onto another machine entirely via RPC. As a result, we abuse the Spine code as follows:

• The normal Spine works in terms of Batch impls. A Batch is added to the Spine. As progress is made, the Spine will merge two batches together by: constructing a Batch::Merger, giving it bits of fuel to incrementally perform the merge (which spreads out the work, keeping latencies even), and then once it’s done fueling extracting the new single output Batch and discarding the inputs.
• Persist instead represents a batch of blob data with a HollowBatch pointer which contains the normal Batch metadata plus the keys necessary to retrieve the updates.
• SpineBatch wraps HollowBatch and has a FuelingMerge companion (analogous to Batch::Merger) that allows us to represent a merge as it is fueling. Normally, this would represent real incremental compaction progress, but in persist, it’s simply a bookkeeping mechanism. Once fully fueled, the FuelingMerge is turned into a fueled SpineBatch, which to the Spine is indistinguishable from a merged batch. At this point, it is eligible for asynchronous compaction and a FueledMergeReq is generated.
• At any later point, this request may be answered via Trace::apply_merge_res_checked or Trace::apply_merge_res_unchecked. This internally replaces theSpineBatch, which has no effect on the structure of Spine but replaces the metadata in persist’s state to point at the new batch.
• SpineBatch is explictly allowed to accumulate a list of HollowBatchs. This decouples compaction from Spine progress and also allows us to reduce write amplification by merging N batches at once where N can be greater than 2.

Structs

ActiveCompaction

FlatTrace

This is a “flattened” representation of a Trace. Goals:

FueledMergeReq

FueledMergeRes

FuelingMerge

IdFuelingMerge

IdHollowBatch

MergeState 🔒

Describes the state of a layer.

Spine 🔒

An append-only collection of update batches.

SpineBatch 🔒

SpineId

SpineMetrics 🔒

ThinMerge

ThinSpineBatch

Trace

An append-only collection of compactable update batches.

Enums

ApplyMergeResult

CompactionInput

SpineLog 🔒

A log of what transitively happened during a Spine operation: e.g. FueledMergeReqs were generated.

Constants

BATCHES_PER_LEVEL 🔒

The maximum number of batches per level in the spine. In practice, we probably want a larger max and a configurable soft cap, but using a stack-friendly data structure and keeping this number low makes this safer during the initial rollout.

Functions

id_range

Creates a SpineId that covers the range of ids in the set.