Skip to main content

rypipe_core/
budget.rs

1//! Memory-budget partitioning, accounting, and streaming-run statistics.
2//!
3//! [`BudgetPartition`] derives per-component limits from a [`MemoryBudget`]
4//! so that every simultaneously live, engine-controlled allocation stays
5//! within it; the unit tests prove the worst case. [`BudgetLedger`] charges
6//! the actual (capacity-accurate) live bytes at stage boundaries and tracks
7//! the peak. [`StreamStats`] summarizes a streaming run, including that peak.
8//!
9//! `BoundedExecutor` uses the ledger observationally: it records charges and
10//! reports the peak through [`StreamStats`] without changing sizing or
11//! enforcement. [`BudgetLedger::check`] is the enforcement backstop for
12//! adopters that want a hard error once live bytes exceed the budget.
13//!
14//! Engine-controlled memory: input chunk buffers, column builders, the batch
15//! accumulator, exported Arrow batches in flight, and the parallel reorder
16//! buffer. Out of scope: process baseline, caller-owned input slices, memory
17//! the consumer retains after `consume` returns, Python objects, and
18//! allocator retention (freed bytes the allocator keeps mapped).
19
20use crate::bounded::MemoryBudget;
21
22/// Per-component limits derived from a [`MemoryBudget`] so that every
23/// simultaneously live, engine-controlled allocation stays within it.
24///
25/// This is the documented envelope behind the executors' sizing heuristics:
26/// `BoundedExecutor` targets `budget / 64` batches (well under
27/// `batch_target`) and `ParallelStreamingExecutor` derives per-worker chunks
28/// of `budget / (32 × threads)` (well under the parallel partition's
29/// per-worker chunk). The fractions below are the bounds those heuristics
30/// may grow into, not the values they target.
31///
32/// Serial streaming keeps these components live at peak:
33///
34/// | component | bound |
35/// |---|---|
36/// | input chunk buffer | `max_chunk_bytes` |
37/// | one chunk builder (doubling growth) | `2 × max_chunk_bytes` |
38/// | batch accumulator (exact-capacity storage) | `2 × batch_target` |
39/// | exported batches in flight (channel + consumer-held) | `2 × batch_target` |
40///
41/// The fractions sum to 11/16 of the budget; the remainder covers row
42/// buffers, schema maps, and other small per-builder state, and provides
43/// slack for estimate error.
44#[derive(Clone, Copy, Debug)]
45pub struct BudgetPartition {
46    /// Total budget in bytes.
47    pub budget: usize,
48    /// Payload bytes at which the batch accumulator is flushed. Exported
49    /// batches are exact-sized, so each in-flight batch is ≤ this value
50    /// unless it is a flagged oversize batch.
51    pub batch_target: usize,
52    /// Maximum bytes of one input chunk; also bounds the reusable chunk
53    /// buffer on the seek-based path.
54    pub max_chunk_bytes: usize,
55    /// Finished batches allowed in flight (channel slot + consumer-held).
56    pub max_in_flight: usize,
57    /// Parallel reorder-buffer limit in bytes (0 for the serial partition).
58    pub reorder_limit: usize,
59}
60
61impl BudgetPartition {
62    /// Partition for the serial streaming executor.
63    pub fn serial(budget: MemoryBudget) -> Self {
64        let b = budget.bytes();
65        Self {
66            budget: b,
67            batch_target: (b / 8).max(1),
68            max_chunk_bytes: (b / 16).max(1),
69            max_in_flight: 2,
70            reorder_limit: 0,
71        }
72    }
73
74    /// Partition for the parallel streaming executor with `threads` workers.
75    ///
76    /// Live at peak: `threads` chunk builders (`2 × chunk` each), up to
77    /// `2 × threads` finished batches (`chunk` each), and the ordered-mode
78    /// reorder buffer (`budget / 2`). Per-worker chunk payload is therefore
79    /// `budget / (8 × threads)`.
80    pub fn parallel(budget: MemoryBudget, threads: usize) -> Self {
81        let b = budget.bytes();
82        let n = threads.max(1);
83        let chunk = (b / (8 * n)).max(1);
84        Self {
85            budget: b,
86            batch_target: chunk,
87            max_chunk_bytes: chunk,
88            max_in_flight: 2 * n,
89            reorder_limit: (b / 2).max(1),
90        }
91    }
92}
93
94/// Fixed structural overhead tolerated by the ledger check: empty-builder
95/// preallocation hints, column metadata, and schema maps. Independent of
96/// data size; negligible against realistic budgets (≥ 1 MiB) but dominant
97/// for toy budgets used in unit tests.
98pub const STRUCTURAL_ALLOWANCE: usize = 256 * 1024;
99
100/// Running account of engine-controlled live bytes, charged at stage
101/// boundaries with capacity-accurate values.
102#[derive(Debug, Default)]
103pub struct BudgetLedger {
104    budget: usize,
105    input: usize,
106    builders: usize,
107    in_flight: usize,
108    reorder: usize,
109    peak: usize,
110}
111
112impl BudgetLedger {
113    pub fn new(budget: MemoryBudget) -> Self {
114        Self {
115            budget: budget.bytes(),
116            ..Self::default()
117        }
118    }
119
120    fn live(&self) -> usize {
121        self.input + self.builders + self.in_flight + self.reorder
122    }
123
124    fn note(&mut self) {
125        self.peak = self.peak.max(self.live());
126    }
127
128    /// Set the input-buffer charge (chunk buffer or engine-owned input Vec).
129    pub fn set_input(&mut self, bytes: usize) {
130        self.input = bytes;
131        self.note();
132    }
133
134    /// Set the builders charge to the current combined capacity of the live
135    /// accumulator and chunk builder.
136    pub fn set_builders(&mut self, bytes: usize) {
137        self.builders = bytes;
138        self.note();
139    }
140
141    pub fn charge_in_flight(&mut self, bytes: usize) {
142        self.in_flight += bytes;
143        self.note();
144    }
145
146    pub fn release_in_flight(&mut self, bytes: usize) {
147        self.in_flight = self.in_flight.saturating_sub(bytes);
148    }
149
150    pub fn charge_reorder(&mut self, bytes: usize) {
151        self.reorder += bytes;
152        self.note();
153    }
154
155    pub fn release_reorder(&mut self, bytes: usize) {
156        self.reorder = self.reorder.saturating_sub(bytes);
157    }
158
159    /// Peak simultaneously live engine-controlled bytes observed so far.
160    pub fn peak(&self) -> usize {
161        self.peak
162    }
163
164    /// Enforcement backstop: error if live bytes exceed the budget by more
165    /// than `allowance` (e.g. [`STRUCTURAL_ALLOWANCE`], tolerated for
166    /// flagged oversize batches). Budget-derived sizing should keep live
167    /// bytes under the budget; exceeding it without an oversize record
168    /// indicates an accounting bug.
169    pub fn check(&self, allowance: usize) -> crate::Result<()> {
170        let live = self.live();
171        let limit = self.budget.saturating_add(allowance);
172        if live > limit {
173            return Err(crate::Error::Memory { used: live, limit });
174        }
175        Ok(())
176    }
177}
178
179/// Outcome of a streaming run, including memory-budget accounting data.
180#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
181pub struct StreamStats {
182    /// Batches delivered to the consumer.
183    pub batches: usize,
184    /// Total rows across all batches.
185    pub rows: usize,
186    /// Batches emitted alone because a single record exceeded the batch
187    /// target. These may exceed the budget; all other batches may not.
188    pub oversize_batches: usize,
189    /// Peak simultaneously live engine-controlled bytes (capacity-accurate).
190    pub peak_tracked_bytes: usize,
191}
192
193#[cfg(test)]
194mod tests {
195    use super::*;
196
197    #[test]
198    fn test_serial_partition_sums_within_budget() {
199        let budget = MemoryBudget::new(10 * 1024 * 1024);
200        let p = BudgetPartition::serial(budget);
201        let worst = p.max_chunk_bytes          // chunk buffer
202            + 2 * p.max_chunk_bytes            // chunk builder (doubling)
203            + 2 * p.batch_target               // accumulator
204            + 2 * p.batch_target; // in flight
205        assert!(
206            worst <= budget.bytes(),
207            "serial worst case {worst} exceeds {}",
208            budget.bytes()
209        );
210    }
211
212    #[test]
213    fn test_parallel_partition_sums_within_budget() {
214        for threads in [1, 4, 16] {
215            let budget = MemoryBudget::new(64 * 1024 * 1024);
216            let p = BudgetPartition::parallel(budget, threads);
217            let worst = threads * 2 * p.max_chunk_bytes // worker builders
218                + p.max_in_flight * p.batch_target      // finished batches
219                + p.reorder_limit;
220            assert!(
221                worst <= budget.bytes(),
222                "parallel worst case {worst} exceeds {} (threads {threads})",
223                budget.bytes()
224            );
225        }
226    }
227
228    #[test]
229    fn test_ledger_check_and_peak() {
230        let mut ledger = BudgetLedger::new(MemoryBudget::new(100));
231        ledger.set_input(40);
232        ledger.set_builders(50);
233        assert_eq!(ledger.peak(), 90);
234        assert!(ledger.check(0).is_ok());
235        ledger.charge_in_flight(20);
236        assert_eq!(ledger.peak(), 110);
237        assert!(ledger.check(0).is_err());
238        assert!(ledger.check(10).is_ok());
239        ledger.set_builders(0);
240        ledger.release_in_flight(20);
241        ledger.set_input(0);
242        assert_eq!(ledger.peak(), 110);
243    }
244}