Skip to main content

Module chunk

differential_dataflow::trace

Module chunk 

Source
Expand description

Sorted, consolidated runs of updates, and operators over sequences of them.

A Chunk is a consolidated, sorted run of (data, time, diff) updates. A sequence of chunks is also expected to be consolidated and sorted.

The Chunk trait exposes whole-chunk operations, so that the implementor can internally divert to their best implementations, with amortized overhead. Each operation is invoked as if “streaming”, providing input and output queues. An implementor is expected to drain as much as possible of the inputs, and any chunk written to the output is “committed” and likely to be shipped onward.

§Wiring a Chunk into an arrangement

Implementing Chunk for a type C is the only bespoke code needed; three aliases then expand into a full trace:

These are the Batcher / Builder / Spine to hand to arrange_core, along with a chunker that forms C from the input stream — typically ContainerChunker<C>. Trace maintenance needs only Chunk; cursor-driven consumption of the arrangement additionally asks C for the NavigableChunk capability. Everything else here (ChunkBatch, ChunkMerger, ChunkBatchMerger, ChunkBatchCursor, ChunkBatchBuilder) is machinery those aliases expand to and is not named directly. The vec module is a worked Chunk that re-exports the three aliases specialized to its layout, and the chunks example stands one up.

§Bounded footprint

There is a TARGET associated constant that signals the intended chunk size. The constant should be chosen large enough to amortize overheads, but small enough that per-chunk work does not “stall” the system when invoked. The implementor is trusted to make a reasonable choice here.

The Chunk::settle method “settles” sequences of chunks, and is called as chunks are no longer expected to be needed in the near future. The implementor should ensure the chunks are “graded”, in that the sequence of chunks are all at most TARGET in size, any two in order sum to strictly more than TARGET. This is also an opportunity to compress data, or spill to disk or cloud storage.

The active (un-settled) chunk set is kept small from both sides. Every producer settles its committed output as it goes (see Chunk::settle), rather than building a whole sequence and settling at the end. And every walk over a whole chunk sequence reads only resident metadata — len and bounds — never a chunk body: the straddle cursor seeks by galloping the chunks’ bounds from a hint and opens only the chunk(s) a query touches. Implementors must therefore keep len and bounds cheap even when a chunk’s body is paged out.

Modules§

vec
A worked Chunk: Vec<((K, V), T, R)> behind an Rc.

Structs§

ChunkBatch
A batch is a Chunk sequence plus a Description.
ChunkBatchBuilder
A Builder that collects a chunk sequence into a ChunkBatch.
ChunkBatchCursor
A cursor over a ChunkBatch, merging the per-chunk cursors.
ChunkBatchMerger
The resumable Batch::Merger for ChunkBatch: merges two batches and advances their times to the compaction frontier, a fuel-bounded step at a time.
ChunkMerger
A merge-batcher Merger over chains of Chunks.

Traits§

Chunk
A non-empty, bounded, consolidated, sorted sequence of (data, time, diff).
NavigableChunk
The navigation capability: a Chunk whose contents can be read by cursor.

Functions§

is_graded
Whether chunks satisfy the Chunk::TARGET grading invariant: every chunk at most TARGET, and every adjacent pair summing to more than TARGET (so no two neighbours could be combined into one legal chunk — a maximal packing).
merge_chains
Merge two full chains of chunks into one, to completion, appending to out.
pack
Maximal-packing driver an implementor’s Chunk::settle may delegate to.
settle_all
Settle input to completion into a fresh graded Vec (see Chunk::settle).

Type Aliases§

ChunkBatcher
A merge-batcher Merger over chains of Chunks.
ChunkBuilder
A reference-counted ChunkBatch builder over chunks of type C.
ChunkSpine
A spine of Rc-shared ChunkBatches of type C: the trace type for arrange.