Documentation
¶
Overview ¶
Package chronicle is the extracted cascade engine of the chronicle substrate (docs/proposals/chronicle-substrate.md, @C03/@C04): a generic rollup cascade parameterised by a monoid, over a time-grain hierarchy.
The theorem (@C03): the rollup cascade in ts, cal, and bal is one construction — a monoid homomorphism over a grain hierarchy. ts folds (number, +, 0) and (min/max with identities); cal's dayparts fold (bitset, OR, ∅); bal folds (int64, +, 0). This package implements the construction once, parameterised: an associative combine with an identity, cascading upward on append, invalidating on correction.
Sequencing (@C §5): incumbents do not migrate onto this engine merely because it exists — cal's rollups are stress-verified on real hardware and migrate opportunistically or never; ts likewise when next touched for its own reasons. New consumers (bal, wave 4) ride the engine natively. The instantiation tests in this package prove the incumbent monoids are expressible, which is the extraction's correctness bar.
Index ¶
- func AssertRebuildOracle(t TestingT, ctx context.Context, o RebuildOracle)
- func MonthWindows(t time.Time) (time.Time, time.Time)
- func RunBucketStoreContract(t *testing.T, newStore func() BucketStore[int64])
- type BitsetOR
- type BucketKey
- type BucketStore
- type Engine
- func (e *Engine[T]) Append(v T, t time.Time)
- func (e *Engine[T]) AsOf(epoch, t time.Time) T
- func (e *Engine[T]) Bucket(level int, t time.Time) T
- func (e *Engine[T]) FoldRange(from, to time.Time) T
- func (e *Engine[T]) Invalidate(t time.Time)
- func (e *Engine[T]) Recompute(t time.Time, replay func(from, to time.Time, emit func(v T, at time.Time)))
- type Grain
- type Hierarchy
- type MaxFloat64
- type MemStore
- type MinFloat64
- type MinValue
- type Monoid
- type OracleResult
- type RebuildOracle
- type SealedError
- type Sealer
- type SumFloat64
- type SumInt64
- type TestingT
- type WindowFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AssertRebuildOracle ¶ added in v0.16.13
func AssertRebuildOracle(t TestingT, ctx context.Context, o RebuildOracle)
AssertRebuildOracle runs the oracle and fails the test on divergence — the test-side consumption form.
func MonthWindows ¶ added in v0.16.13
MonthWindows tiles time into UTC calendar months — bal's period shape.
func RunBucketStoreContract ¶ added in v0.16.13
func RunBucketStoreContract(t *testing.T, newStore func() BucketStore[int64])
RunBucketStoreContract exercises any BucketStore[int64] implementation against the behaviour the engine depends on. New stores (bal's SQL-plane store at wave 4; any Pebble-plane store) must pass this harness before the engine is trusted on them — the same contract-harness discipline as pkg/graph's store contract.
The int64 carrier is deliberate: the contract is about storage behaviour (presence, overwrite, deletion, ordered ranging, level isolation), not the monoid, and a comparable carrier keeps the assertions exact.
Types ¶
type BitsetOR ¶
type BitsetOR struct{}
BitsetOR is cal's daypart occupancy fold: (uint8 bitset, OR, 0). One byte summarises a day at 3-hour-daypart granularity (@cal codec §4).
type BucketKey ¶
BucketKey addresses one bucket: a hierarchy level and its grain-aligned start instant (UTC).
type BucketStore ¶
type BucketStore[T any] interface { Get(k BucketKey) (T, bool) Put(k BucketKey, v T) Delete(k BucketKey) // RangeLevel visits every existing bucket at the given level with // Start in the half-open window [from, to), in ascending Start // order. Returning false from fn stops the iteration. Required by // the prefix-fold read path (AsOf); implementations back it with an // ordered scan (SQL: ORDER BY start; Pebble: key iteration). RangeLevel(level int, from, to time.Time, fn func(k BucketKey, v T) bool) }
BucketStore is the storage seam. The engine is storage-agnostic: an in-memory store ships here for tests and small consumers; bal brings a SQL-plane store (wave 4, guard-locality obliged — @C04a), and any Pebble-plane store arrives with its consumer.
Get returns the bucket's folded value and whether it exists. Put overwrites. Delete removes (used by invalidation). Implementations must be safe for the engine's single-writer discipline; concurrent writers are the consumer's concern (bal serialises under its own transaction; @C04a).
type Engine ¶
type Engine[T any] struct { // contains filtered or unexported fields }
Engine is the monoid-parameterised cascade over one hierarchy and one store. Append folds a value into the finest bucket and cascades the combine upward through every coarser grain. Invalidate removes every bucket covering an instant so a later Recompute (or the consumer's re-fold) rebuilds them — corrections must not silently keep stale coarse folds (the ts correction rule, generalised).
func (*Engine[T]) Append ¶
Append folds v into the bucket containing t at every level of the hierarchy — the upward cascade. Because Combine is associative and every coarse bucket is an exact multiple of the fine grain, combining the increment directly into each level equals re-folding that level from its children: the homomorphism property, asserted by the engine's tests rather than trusted.
func (*Engine[T]) AsOf ¶ added in v0.16.13
AsOf folds everything from `epoch` up to (excluding) the finest bucket containing t plus that bucket itself — i.e. the cumulative value as of the end of t's finest bucket. Callers wanting strict "before t" semantics pass to=t truncated to grain 0 via FoldRange directly; AsOf is the common inclusive read (bal: balance as of a posting instant includes the instant's bucket).
func (*Engine[T]) Bucket ¶
Bucket returns the folded value for the bucket containing t at the given level, or the identity if the bucket does not exist.
func (*Engine[T]) FoldRange ¶ added in v0.16.13
FoldRange folds the half-open window [from, to) using the coarsest buckets that fit entirely inside it, descending to finer grains only at the ragged edges — the classic prefix/segment walk. This is @C03's cumulative read ("the fold of a prefix: the same monoid, chained across sealed checkpoints"): bal's balance-as-of is FoldRange from the epoch (or the last sealed checkpoint) to the as-of instant.
Correctness rests on the homomorphism: a coarse bucket equals the fold of its children, so substituting it for them changes nothing. The engine's tests assert FoldRange == the naive finest-grain fold.
Cost: O(levels × buckets-touched); for a hierarchy like 5m/hour/day an as-of over a year touches ~365 day buckets + edge partials rather than ~105k five-minute buckets.
func (*Engine[T]) Invalidate ¶
Invalidate removes every bucket, at every level, that covers t. A correction to underlying data makes every covering fold stale; the safe response is absence (forcing recompute), never a silently wrong value. Recompute rebuilds from a replay callback.
func (*Engine[T]) Recompute ¶
func (e *Engine[T]) Recompute(t time.Time, replay func(from, to time.Time, emit func(v T, at time.Time)))
Recompute rebuilds every bucket, at every level, inside the coarsest bucket containing t, by re-folding source values supplied by replay. replay must yield every (value, instant) pair within the half-open window [from, to) — the consumer owns the authoritative record (the journal, the event store) and therefore owns replay; the engine owns only the fold.
The whole coarsest window is cleared, not just the chain covering t: replay refills every fine bucket in the window via Append, so any bucket left standing would double-count its replayed values.
type Grain ¶
type Grain struct {
Name string // e.g. "5m", "hour", "day" — diagnostic only
Width time.Duration // bucket width; must be > 0
}
Grain is one level of the time hierarchy: a bucket width. Instants truncate onto grain-aligned bucket starts in UTC.
type Hierarchy ¶
type Hierarchy struct {
// contains filtered or unexported fields
}
Hierarchy is an ordered set of grains, finest first, each coarser grain an exact multiple of the previous. The multiple requirement is what makes the homomorphism exact: every coarse bucket is the fold of a whole number of fine buckets, so cascading combine loses nothing.
func NewHierarchy ¶
NewHierarchy validates and constructs a hierarchy. Grains must be ordered finest→coarsest, each width a positive exact multiple of the preceding width.
type MaxFloat64 ¶
type MaxFloat64 struct{}
MaxFloat64 is ts's maximum fold, same identity treatment.
func (MaxFloat64) Combine ¶
func (MaxFloat64) Combine(a, b MinValue) MinValue
func (MaxFloat64) Identity ¶
func (MaxFloat64) Identity() MinValue
type MemStore ¶
type MemStore[T any] struct { // contains filtered or unexported fields }
MemStore is the in-memory BucketStore: the test vehicle and the small-consumer default. Not safe for concurrent use — the engine's single-writer discipline is the consumer's to enforce (@C04a).
func NewMemStore ¶
NewMemStore constructs an empty in-memory store.
func (*MemStore[T]) RangeLevel ¶ added in v0.16.13
RangeLevel visits existing buckets at level with Start in [from, to), ascending. The map is unordered, so keys are collected and sorted — fine for the test/small-consumer role; durable stores use an ordered scan natively.
type MinFloat64 ¶
type MinFloat64 struct{}
func (MinFloat64) Combine ¶
func (MinFloat64) Combine(a, b MinValue) MinValue
func (MinFloat64) Identity ¶
func (MinFloat64) Identity() MinValue
type MinValue ¶
MinFloat64 is ts's minimum fold, with +Inf-free identity handling via a validity flag: the identity is "no value yet".
type Monoid ¶
type Monoid[T any] interface { // Identity returns the neutral element: Combine(Identity(), x) == x. Identity() T // Combine folds two values. Must be associative: // Combine(a, Combine(b, c)) == Combine(Combine(a, b), c). Combine(a, b T) T }
Monoid is the algebraic parameter of the cascade: an associative Combine with an Identity element. Associativity and identity are laws the implementation must satisfy — they are property-tested per instantiation in this package, not assumed.
type OracleResult ¶ added in v0.16.13
type OracleResult struct {
Name string
Equal bool
// FirstDivergence describes the first differing line when not equal:
// "line N: derived=... current=..." — enough to localise, not a full
// diff (fingerprints are available to the caller for that).
FirstDivergence string
Derived string
Current string
}
OracleResult reports one oracle's outcome.
func CheckAll ¶ added in v0.16.13
func CheckAll(ctx context.Context, oracles []RebuildOracle) ([]*OracleResult, error)
CheckAll runs a set of oracles, failing fast only on execution errors — divergences are results, not errors, so one broken invariant does not hide another's report.
type RebuildOracle ¶ added in v0.16.13
type RebuildOracle struct {
// Name identifies the oracle in reports, e.g. "cal.index",
// "graph.edges", "ts.rollups".
Name string
// Derive replays the authoritative record (journal, source table)
// into the canonical fingerprint of the state it implies.
Derive func(ctx context.Context) (string, error)
// Current serialises the live derived state into the same canonical
// form.
Current func(ctx context.Context) (string, error)
}
RebuildOracle names one derived-state invariant for one primitive.
func (RebuildOracle) Check ¶ added in v0.16.13
func (o RebuildOracle) Check(ctx context.Context) (*OracleResult, error)
Check runs one oracle.
type SealedError ¶ added in v0.16.13
SealedError reports a mutation refused because its span touches the sealed (immutable) past.
func (*SealedError) Error ¶ added in v0.16.13
func (e *SealedError) Error() string
type Sealer ¶ added in v0.16.13
type Sealer struct {
// contains filtered or unexported fields
}
Sealer manages a monotone seal frontier over a window tiling, and serialises frontier advance against guarded mutations. The zero frontier means nothing is sealed.
func (*Sealer) AdvanceTo ¶ added in v0.16.13
AdvanceTo advances the frontier to now (monotone: moving backward is a no-op). Sealing is a logical freeze — the frontier IS the seal; no per-window rewrite happens here (cal's model, kept: a physical cold move is a consumer/store concern).
func (*Sealer) Frontier ¶ added in v0.16.13
Frontier returns the current seal frontier. Windows ending at or before it are immutable.
func (*Sealer) Guard ¶ added in v0.16.13
Guard runs fn under the seal lock iff the span [from, to) touches no sealed window; otherwise it returns *SealedError and fn never runs. This is the lifted serialisation discipline: Guard and AdvanceTo are mutually exclusive, so the seal observes only fully-applied states and mutations never land in the immutable past.
fn runs WITH the lock held — it must be the consumer's short critical section (the index write, the bucket update), not long I/O. cal's hazard analysis applies verbatim: the one operation touching two planes must sit entirely inside the guard or the interleaving returns.
type SumFloat64 ¶
type SumFloat64 struct{}
SumFloat64 is ts's additive fold: (float64, +, 0).
func (SumFloat64) Combine ¶
func (SumFloat64) Combine(a, b float64) float64
func (SumFloat64) Identity ¶
func (SumFloat64) Identity() float64
type SumInt64 ¶
type SumInt64 struct{}
SumInt64 is bal's conservation fold: (int64, +, 0). Balance-as-of is this monoid chained across sealed checkpoints (@C03).
type TestingT ¶ added in v0.16.13
type TestingT interface {
Helper()
Fatalf(format string, args ...interface{})
Logf(format string, args ...interface{})
}
TestingT is the subset of *testing.T the assertion helper needs; an interface so the harness does not import testing (tooling links this package too).
type WindowFn ¶ added in v0.16.13
WindowFn maps an instant to the half-open window [start, end) containing it, in UTC. Windows must tile time: contiguous, non-overlapping, end(t) == start of the next window. cal instantiates UTC days; bal instantiates calendar months; fixed-width consumers use GrainWindows.
func GrainWindows ¶ added in v0.16.13
GrainWindows adapts a fixed-width Grain to a WindowFn.
Source Files