tempo_payload_builder/
budget.rs

1//! Budget helpers for deciding when to stop executing pool transactions.
2//!
3//! The builder can stop transaction execution, but it still has to finish
4//! non-interruptible finalization work like state hashing, state root updates,
5//! block assembly, and marshal persistence. These helpers learn the relation
6//! between tx execution cutoff time, total replayable build work, validation
7//! latency feedback, and the size-dependent cost of persisting large blocks
8//! through consensus.
9//!
10//! The decision model is:
11//! `leader_idle + predicted_builder_work + predicted_validator_work + 2 * marshal_persist >= budget`.
12//! Idle waiting only happens on the proposer. Builder work is projected from the
13//! current build, while validator work uses feedback from previously validated
14//! blocks when available and otherwise falls back to the builder projection.
15
16use std::time::Duration;
17
18#[cfg(test)]
19use tempo_payload_types::ValidationLatencyEstimator;
20use tempo_payload_types::{
21    MarshalPersistEstimator, ValidationLatencyEstimate, ValidationLatencyWorkload,
22};
23
24/// Fixed-point scale for build time multipliers.
25pub(crate) const BUILD_TIME_MULTIPLIER_SCALE: u64 = 1_000_000;
26#[cfg(test)]
27const DEFAULT_BUILD_TIME_MULTIPLIER_SCALED: u64 = 1_350_000;
28const MAX_BUILD_TIME_MULTIPLIER: u64 = 1_700_000;
29/// How quickly the multiplier decays when observed builds get cheaper.
30const BUILD_TIME_MULTIPLIER_DECAY: u64 = 8;
31
32/// Initial estimate of total replayable build work divided by work at tx cutoff.
33///
34/// For example, `1.35` means "when cutoff work is 100 ms, expect the completed
35/// replayable build work to be about 135 ms".
36pub const DEFAULT_BUILD_TIME_MULTIPLIER: f64 = 1.35;
37
38/// Converts a human-readable build-work multiplier into the fixed-point representation.
39pub(crate) fn scaled_build_time_multiplier(multiplier: f64) -> u64 {
40    assert!(
41        multiplier.is_finite() && multiplier >= 1.0,
42        "build time multiplier must be finite and >= 1.0"
43    );
44
45    (multiplier * BUILD_TIME_MULTIPLIER_SCALE as f64).round() as u64
46}
47
48fn scaled_duration(elapsed: Duration, multiplier: u64) -> Duration {
49    Duration::from_nanos(
50        (elapsed.as_nanos().saturating_mul(u128::from(multiplier))
51            / u128::from(BUILD_TIME_MULTIPLIER_SCALE))
52        .min(u128::from(u64::MAX)) as u64,
53    )
54}
55
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub(crate) struct PayloadBudgetDecision {
58    pub(crate) predicted_builder_work: Duration,
59    pub(crate) predicted_validator_work: Duration,
60    pub(crate) marshal_persist: Duration,
61    pub(crate) total_reserved: Duration,
62}
63
64/// Builds the shared proposer/validator budget decision for the current payload.
65///
66/// `elapsed` is wall-clock time spent in the builder so far. `idle_elapsed` is
67/// the proposer-only time spent waiting for more transactions, which is not
68/// replayed by validators and therefore counts once.
69/// `validation_latency` is an estimate of validator-side replay work from
70/// previously validated proposals. If no latency estimate is usable for the
71/// current workload, the validator reserve falls back to
72/// `predicted_builder_work`, which is the replayable proposer work projected
73/// from this build.
74/// `current_workload` describes the block currently being assembled.
75///
76/// The budget is not split into fixed leader/validator buckets. Instead, we
77/// charge proposer idle once, projected builder work once, learned validator
78/// work once capped at the conservative builder-work projection, and marshal
79/// persistence once for each side.
80pub(crate) fn payload_budget_decision(
81    elapsed: Duration,
82    idle_elapsed: Duration,
83    multiplier: u64,
84    marshal_persist: MarshalPersistEstimator,
85    block_size_bytes: usize,
86    validation_latency: Option<ValidationLatencyEstimate>,
87    current_workload: ValidationLatencyWorkload,
88) -> PayloadBudgetDecision {
89    let work_elapsed = elapsed.saturating_sub(idle_elapsed);
90    let predicted_builder_work = scaled_duration(work_elapsed, multiplier);
91    let validation_latency_estimate =
92        validation_latency.and_then(|estimate| estimate.estimate(current_workload));
93    let predicted_validator_work = validation_latency_estimate
94        .map(|estimate| estimate.min(predicted_builder_work))
95        .unwrap_or(predicted_builder_work);
96    let marshal_persist = marshal_persist.estimate(block_size_bytes);
97    let total_reserved = idle_elapsed
98        .saturating_add(predicted_builder_work)
99        .saturating_add(predicted_validator_work)
100        .saturating_add(marshal_persist)
101        .saturating_add(marshal_persist);
102    PayloadBudgetDecision {
103        predicted_builder_work,
104        predicted_validator_work,
105        marshal_persist,
106        total_reserved,
107    }
108}
109
110/// Computes the observed total-work to tx-cutoff-work multiplier.
111///
112/// `work_at_tx_cutoff` is measured when pool transaction execution stops.
113/// `total_work` is measured after finalization finishes. Their ratio captures
114/// `builder_finish` without needing a separate fixed reserve.
115pub(crate) fn observed_build_time_multiplier(
116    total_work: Duration,
117    work_at_tx_cutoff: Duration,
118) -> Option<u64> {
119    if work_at_tx_cutoff == Duration::ZERO {
120        return None;
121    }
122
123    let multiplier = total_work
124        .as_nanos()
125        .saturating_mul(u128::from(BUILD_TIME_MULTIPLIER_SCALE))
126        / work_at_tx_cutoff.as_nanos();
127    Some(multiplier.min(u128::from(MAX_BUILD_TIME_MULTIPLIER)) as u64)
128}
129
130/// Updates the multiplier, immediately rising but slowly decaying.
131pub(crate) fn decay_build_time_multiplier(current: u64, observed: u64) -> u64 {
132    if observed >= current {
133        observed
134    } else {
135        let decay = ((current - observed) / BUILD_TIME_MULTIPLIER_DECAY).max(1);
136        current.saturating_sub(decay).max(observed)
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143
144    fn validation_latency_estimate(
145        workload: ValidationLatencyWorkload,
146        elapsed: Duration,
147    ) -> Option<ValidationLatencyEstimate> {
148        let mut estimator = ValidationLatencyEstimator::default();
149        estimator.observe(1, workload, elapsed);
150        estimator.estimate()
151    }
152
153    #[test]
154    fn observed_build_multiplier_tracks_tail_cost() {
155        assert_eq!(
156            observed_build_time_multiplier(Duration::from_millis(135), Duration::from_millis(100)),
157            Some(DEFAULT_BUILD_TIME_MULTIPLIER_SCALED)
158        );
159        assert_eq!(
160            observed_build_time_multiplier(Duration::from_millis(100), Duration::from_millis(100)),
161            Some(1_000_000)
162        );
163        assert_eq!(
164            observed_build_time_multiplier(Duration::from_millis(250), Duration::from_millis(100)),
165            Some(MAX_BUILD_TIME_MULTIPLIER)
166        );
167        assert_eq!(decay_build_time_multiplier(1_500_000, 1_300_000), 1_475_000);
168    }
169
170    #[test]
171    fn payload_budget_accounts_for_leader_idle_once() {
172        let decision = payload_budget_decision(
173            Duration::from_millis(100),
174            Duration::ZERO,
175            1_350_000,
176            MarshalPersistEstimator::default(),
177            0,
178            None,
179            ValidationLatencyWorkload::default(),
180        );
181        assert_eq!(decision.predicted_builder_work, Duration::from_millis(135));
182        assert_eq!(
183            decision.predicted_validator_work,
184            Duration::from_millis(135)
185        );
186        assert_eq!(decision.total_reserved, Duration::from_millis(270));
187
188        let decision = payload_budget_decision(
189            Duration::from_millis(350),
190            Duration::from_millis(250),
191            1_350_000,
192            MarshalPersistEstimator::default(),
193            0,
194            None,
195            ValidationLatencyWorkload::default(),
196        );
197        assert_eq!(decision.predicted_builder_work, Duration::from_millis(135));
198        assert_eq!(
199            decision.predicted_validator_work,
200            Duration::from_millis(135)
201        );
202        assert_eq!(decision.total_reserved, Duration::from_millis(520));
203    }
204
205    #[test]
206    fn payload_budget_uses_validator_feedback_when_available() {
207        let workload = ValidationLatencyWorkload::new(100, 0);
208        let validation_latency = validation_latency_estimate(workload, Duration::from_millis(80));
209        let decision = payload_budget_decision(
210            Duration::from_millis(100),
211            Duration::ZERO,
212            1_350_000,
213            MarshalPersistEstimator::default(),
214            0,
215            validation_latency,
216            workload,
217        );
218
219        assert_eq!(decision.predicted_builder_work, Duration::from_millis(135));
220        assert_eq!(decision.predicted_validator_work, Duration::from_millis(80));
221        assert_eq!(decision.total_reserved, Duration::from_millis(215));
222    }
223
224    #[test]
225    fn payload_budget_caps_scaled_validator_feedback_at_builder_projection() {
226        let validation_latency = validation_latency_estimate(
227            ValidationLatencyWorkload::new(100, 10),
228            Duration::from_millis(100),
229        );
230        let decision = payload_budget_decision(
231            Duration::from_millis(100),
232            Duration::ZERO,
233            1_350_000,
234            MarshalPersistEstimator::default(),
235            0,
236            validation_latency,
237            ValidationLatencyWorkload::new(200, 10),
238        );
239
240        assert_eq!(
241            decision.predicted_validator_work,
242            Duration::from_millis(135)
243        );
244        assert_eq!(decision.total_reserved, Duration::from_millis(270));
245    }
246
247    #[test]
248    fn payload_budget_accounts_for_marshal_persist_twice() {
249        let marshal_persist = MarshalPersistEstimator::from_ns_per_byte(1_000);
250
251        let decision = payload_budget_decision(
252            Duration::from_millis(100),
253            Duration::ZERO,
254            1_350_000,
255            marshal_persist,
256            15_000,
257            None,
258            ValidationLatencyWorkload::default(),
259        );
260        assert_eq!(decision.marshal_persist, Duration::from_millis(15));
261        assert_eq!(decision.total_reserved, Duration::from_millis(300));
262
263        let decision = payload_budget_decision(
264            Duration::from_millis(100),
265            Duration::ZERO,
266            1_350_000,
267            marshal_persist,
268            14_999,
269            None,
270            ValidationLatencyWorkload::default(),
271        );
272        assert_eq!(decision.marshal_persist, Duration::from_micros(14_999));
273        assert_eq!(decision.total_reserved, Duration::from_micros(299_998));
274    }
275
276    #[test]
277    fn build_multiplier_scales_decimal_values() {
278        assert_eq!(
279            scaled_build_time_multiplier(DEFAULT_BUILD_TIME_MULTIPLIER),
280            DEFAULT_BUILD_TIME_MULTIPLIER_SCALED
281        );
282    }
283}
tempo_payload_builder/budget.rs

tempo_payload_builder/
budget.rs
