sort_governor/plan/
planner.rs

1//! The pure in-memory-vs-external decision. No I/O, no state —
2//! given a [`SortSpec`], a [`SorterSnapshot`], and a [`SorterConfig`] it
3//! returns a [`SortPlan`]. This is the heart of the Sorter and is the only
4//! place the two budgets (memory and file descriptors) are reconciled.
5
6use crate::config::SorterConfig;
7use crate::plan::kind::SortPlan;
8use crate::snapshot::SorterSnapshot;
9use crate::spec::SortSpec;
10
11/// Chooses how a sort runs. Stateless; every input is explicit so the
12/// decision is exhaustively unit-testable.
13pub struct SortPlanner;
14
15impl SortPlanner {
16    /// Decide whether `spec` sorts in memory or spills, and with what run
17    /// buffer and fan-in if it spills.
18    ///
19    /// A sort stays in memory only when it both fits under the configured
20    /// ceiling *and* the budget has the headroom to hold it. Otherwise it
21    /// spills, with the fan-in rationed from the global file-descriptor
22    /// headroom (so concurrent sorts cannot collectively exhaust the fd
23    /// table) and the run buffer sized *against* that fan-in to keep the
24    /// merge-pass depth bounded.
25    #[must_use]
26    pub fn plan(spec: &SortSpec, snap: &SorterSnapshot, cfg: &SorterConfig) -> SortPlan {
27        let available = snap.available_memory_bytes();
28        if spec.estimated_bytes() <= cfg.in_memory_ceiling_bytes()
29            && available >= spec.estimated_bytes()
30        {
31            return SortPlan::InMemory;
32        }
33        let max_fan_in = Self::ration_fan_in(snap, cfg);
34        let run_buffer_bytes = Self::size_run_buffer(spec, snap, cfg, max_fan_in);
35        SortPlan::External {
36            run_buffer_bytes,
37            max_fan_in,
38        }
39    }
40
41    /// Share the available file descriptors across the sorts in flight,
42    /// floored at 2 (a merge needs at least two inputs) and capped at the
43    /// configured ceiling. `fd_headroom` is already net of the safety
44    /// margin (the actor carves the margin out when it sizes the fd
45    /// semaphore), so the margin is not subtracted again here.
46    fn ration_fan_in(snap: &SorterSnapshot, cfg: &SorterConfig) -> u32 {
47        let share = snap.fd_headroom() / snap.active_external_sorts().saturating_add(1);
48        share.clamp(2, cfg.max_fan_in())
49    }
50
51    /// Pick a run buffer so the run count stays within `max_fan_in²` — at
52    /// most a two-pass cascade — without requesting more memory than is
53    /// available. Under fd pressure (small fan-in) this raises the buffer
54    /// rather than letting the run count explode; the cascade merge remains
55    /// correct for any run count, so this only bounds pass depth.
56    fn size_run_buffer(
57        spec: &SortSpec,
58        snap: &SorterSnapshot,
59        cfg: &SorterConfig,
60        max_fan_in: u32,
61    ) -> usize {
62        let fan = u64::from(max_fan_in);
63        let two_pass_target = spec
64            .estimated_bytes()
65            .div_ceil(fan.saturating_mul(fan).max(1));
66        let mem_cap = snap
67            .available_memory_bytes()
68            .max(cfg.min_run_buffer_bytes());
69        let buffer = two_pass_target
70            .clamp(cfg.min_run_buffer_bytes(), cfg.max_run_buffer_bytes())
71            .min(mem_cap);
72        usize::try_from(buffer).unwrap_or(usize::MAX)
73    }
74}
sort_governor/plan/planner.rs

sort_governor/plan/
planner.rs
