Module chunk 

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:

• ChunkBatcher<Chu, C> — the merge batcher.
• ChunkBuilder<C> — the batch builder.
• ChunkSpine<C> — the trace, a spine of Rc-shared batches.

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>. These aliases use ChunkBatch, ChunkMerger, ChunkBatchMerger, and ChunkBatchBuilder for batch formation and trace maintenance. The vec module provides a worked implementation and specializes the aliases for its chunk type. The chunks example builds an arrangement from it.

Reading chunks through cursors is an optional capability provided by the cursor module.

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.

Producers settle their committed output as they go, keeping the active, unsettled chunk set small. Implementors must keep len cheap even when a chunk’s body is paged out.

Re-exports

pub use cursor::ChunkBatchCursor;

pub use cursor::NavigableChunk;

Modules

cursor

Cursor navigation over chunks and chunk batches.

vec

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

Structs

ChunkBatch

A batch: an ordered Chunk sequence whose concatenation is its updates.

ChunkBatchBuilder

A Builder that collects a chunk sequence into a ChunkBatch.

ChunkBatchMerger

The resumable SpineBatch::Merger for ChunkBatch: merges two updates 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).

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 ChunkBatch builder over chunks of type C, emitting Rc-shared updates.

ChunkSpine

A spine of Rc-shared ChunkBatchs of type C: the trace type for arrange.