mz_timely_util/
funded_spine.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Differential's fueled spine with optional exertion funded by its input.
11//!
12//! `arrange_core` calls `Trace::exert` once per operator activation, and
13//! every call that the exertion policy answers grants a fixed allowance of
14//! fuel, or a virtual introduction that rolls up the layers below it. Nothing
15//! in the stock spine ties the number of grants to the amount of input, so the
16//! optional consolidation it performs scales with how often its operator is
17//! scheduled. Enough idle turns between two published batches lift each batch
18//! into the largest layer on its own, and merge work per row approaches the
19//! size of the largest batch divided by the published batch size.
20//!
21//! This spine pays for policy-requested effort from two sources: credit that
22//! inserted updates accrue, and a bounded bank of allowances that each
23//! inserted batch tops up. `arrange_core` inserts batches as its input
24//! frontier advances, so the bank tracks upstream progress rather than
25//! scheduling, and a quiet input whose frontier advances still converges. An
26//! unfunded request that would start new work is declined and the spine stays
27//! quiet until the next insert. Once the input closes, exertion is unbounded
28//! again so the trace reaches the policy's reduced form.
29//!
30//! What funding bounds is the number of granted requests: one per
31//! `effort / 8` inserted updates from credit, about 125 at the cluster
32//! policy's effort of 1000, plus eight per inserted batch from a bank capped
33//! at 64. For small batches the bank is the bound. It does not bound the work
34//! a grant causes. A grant either
35//! applies one `effort` of fuel to the merges in progress or, with none in
36//! progress, introduces a virtual batch that can start a merge up into the
37//! largest layer, and a merge in progress always finishes, funded or not.
38//! Work still stops scaling with scheduling: an unfunded turn can only
39//! advance a merge already in progress, which must complete before anything
40//! else lands at its level, and every new merge a grant starts is paid for by
41//! input.
42//!
43//! NOTE: `spine_fueled` is a copy, not a dependency. Bumping
44//! differential-dataflow does not update it, so upstream fixes to its spine
45//! reach this one only when someone ports them. Review upstream's
46//! `spine_fueled.rs` changes on every bump. As this copy diverges, not every
47//! change will apply.
48//!
49//! `spine_fueled` is `trace/implementations/spine_fueled.rs` from
50//! differential-dataflow 0.25.1 with its crate-internal paths rewritten. The
51//! funding changes are its two funding fields and their constants, the
52//! `insert` path that funds them, and the `exert` path that spends them, so
53//! the diff against upstream stays reviewable. Everything else, including the
54//! `Trace` and `TraceReader` contracts, is upstream's.
55
56#[rustfmt::skip]
57#[allow(clippy::as_conversions, clippy::needless_pass_by_ref_mut)]
58pub mod spine_fueled;
59
60pub use spine_fueled::Spine;
61
62#[cfg(test)]
63mod tests;
mz_timely_util/funded_spine.rs

mz_timely_util/
funded_spine.rs
