Skip to main content

runnerd_core/
admission.rs

1//! Admission by measured peaks: a job's memory peak and average CPU predicted from the job history (`Predictor`),
2//! and the history replayed through admission by caps and by predictions, with or without a CPU budget
3//! (`simulate`), to show what each would have done with the same jobs, with the barrier `scheduler::plan` puts up for
4//! a starved job or without, and with jobs arriving when they did or after what they followed, or as they really ran
5//! (`trace`); what the host's memory leaves runners (`host`); and what all that runs counts for in the budget (`pooled`,
6//! ADR 0099), with the growth count's brake (`growth`). A job's memory and usual run time go by its last runs (`recent`,
7//! ADR 0070, 0097). Pure: no I/O, no clock.
8
9pub mod growth;
10pub mod host;
11pub mod pooled;
12pub mod recent;
13mod replay;
14pub mod trace;
15
16use std::collections::{BTreeMap, BTreeSet};
17use std::time::Duration;
18
19use crate::api::Spread;
20use crate::api::{Basis, JobPeak};
21use crate::config;
22use crate::scheduler::Pool;
23use crate::sizing::{GRANULE, History, Ran, spread};
24use recent::{Ending, RECENT_RUNS, Recent};
25pub use replay::{recorded, simulate};
26use trace::{Hazard, OOMD_UNDER, Reading, RunId, RunTrace, STEP, THROTTLES_UNDER, Trace};
27
28/// For at most this long after a run at its cap or killed for memory, in milliseconds, its job is admitted at its
29/// cap: 7 days, or until `recent::CLEAN_RUNS` clear runs. After a run past what it reserved, its job reserves its
30/// largest peak for at most as long, or until the run leaves its window.
31pub const UNPREDICTABLE_FOR: u64 = 7 * 24 * 3600 * 1000;
32
33/// From this many successful runs of its own, fewer than `[sizing] min_jobs` runs, a job reserves its own largest
34/// peak while no other copy of it is queued or running; otherwise the larger of that and its profile's p95.
35pub const OWN_RUNS: u64 = 2;
36
37/// While the slice uses this percent of its `MemoryMax` or more, measured admission starts nothing.
38pub const HIGH_WATER: u64 = 90;
39
40/// CPU predictions round up to this many millicores: a tenth of a CPU.
41pub const CPU_GRANULE: u64 = 100;
42
43/// A job as admission tells jobs apart: its repository, workflow and name.
44#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
45pub struct Key {
46    /// `owner/name`.
47    pub repository: String,
48    /// The workflow's name, when known.
49    pub workflow: Option<String>,
50    /// The job's name in the workflow.
51    pub name: String,
52}
53
54impl Key {
55    /// A finished run's key.
56    pub fn of(run: &Ran) -> Key {
57        Key {
58            repository: run.repository.clone(),
59            workflow: run.workflow.clone(),
60            name: run.name.clone(),
61        }
62    }
63}
64
65/// Whether other copies of a job may run beside the one predicted: queued with it, or running. A few light runs
66/// say little about a burst of copies, after a cache was invalidated, so only one copy at a time goes by them.
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68pub enum Copies {
69    /// No other copy is queued or running.
70    Alone,
71    /// Another copy is queued or running.
72    Several,
73}
74
75/// The memory admission reserves for a job, at most its cap, and what it goes by.
76#[derive(Debug, Clone, Copy, PartialEq, Eq)]
77pub struct Prediction {
78    /// Bytes.
79    pub memory: u64,
80    /// Why that much.
81    pub basis: Basis,
82}
83
84/// The CPU a runner reserves for a job, in millicores, at most its profile's `cpus`, and what it goes by.
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86pub struct CpuPrediction {
87    /// Millicores.
88    pub cpu: u64,
89    /// Why that much: `Basis::Job`, `Profile`, `ProfileMax` or `Cap`.
90    pub basis: Basis,
91}
92
93/// The CPU averages of a set of runs, sorted, and how many of those runs succeeded.
94#[derive(Debug, Clone, Default)]
95struct Averages {
96    sorted: Vec<u64>,
97    succeeded: u64,
98}
99
100impl Averages {
101    fn add(&mut self, average: u64, succeeded: bool) {
102        let at = self.sorted.partition_point(|known| *known <= average);
103        self.sorted.insert(at, average);
104        self.succeeded += u64::from(succeeded);
105    }
106
107    fn runs(&self) -> u64 {
108        self.sorted.len() as u64
109    }
110
111    fn p95(&self) -> u64 {
112        spread(self.sorted.clone()).p95
113    }
114
115    fn max(&self) -> u64 {
116        self.sorted.last().copied().unwrap_or(0)
117    }
118}
119
120/// A job in one profile, as the predictor keeps its CPU averages.
121#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
122struct InProfile {
123    key: Key,
124    profile: String,
125}
126
127impl InProfile {
128    fn new(key: &Key, profile: &str) -> InProfile {
129        InProfile {
130            key: key.clone(),
131            profile: profile.to_owned(),
132        }
133    }
134}
135
136/// Predicts a job's peak from the runs it learned.
137#[derive(Debug, Clone)]
138pub struct Predictor {
139    margin: u32,
140    min_jobs: u32,
141    /// Each job's last runs, by job and the profile it ran in (ADR 0070).
142    recent: Recent,
143    /// The CPU averages of the runs that have one, apart from the peaks: a run whose peak says nothing of its
144    /// memory still says what CPU it used, and must not make its job known to memory predictions.
145    cpu_jobs: BTreeMap<InProfile, Averages>,
146    cpu_profiles: BTreeMap<String, Averages>,
147}
148
149impl Predictor {
150    /// A predictor that knows no run yet, with `[sizing]`'s margin and minimum runs.
151    pub fn new(rules: &config::Sizing) -> Predictor {
152        Predictor {
153            margin: rules.margin,
154            min_jobs: rules.min_jobs,
155            recent: Recent::new(RECENT_RUNS.max(u64::from(rules.min_jobs))),
156            cpu_jobs: BTreeMap::new(),
157            cpu_profiles: BTreeMap::new(),
158        }
159    }
160
161    /// A predictor that learned every row of `history`, in the order they finished, each under the cap its
162    /// container had, else `cap_of(profile)`: what the daemon reads every minute, and again after a restart.
163    pub fn read(
164        rules: &config::Sizing,
165        history: &History,
166        cap_of: impl Fn(&str) -> Option<u64>,
167    ) -> Predictor {
168        let mut predictor = Predictor::new(rules);
169        predictor.read_until(history, u64::MAX, cap_of);
170        predictor
171    }
172
173    /// Learns the rows of `history` that ended before `until` (ms), in the order they finished, as `read` does.
174    fn read_until(&mut self, history: &History, until: u64, cap_of: impl Fn(&str) -> Option<u64>) {
175        for (run, ending) in recent::rows(history) {
176            let cap = run
177                .memory_cap
178                .or_else(|| cap_of(&run.profile))
179                .unwrap_or(u64::MAX);
180            let at = recent::finished(run);
181            if at >= until {
182                break;
183            }
184            match ending {
185                Ending::Finished => self.learn(run, &run.profile, cap, at),
186                Ending::Cancelled => self.mark(run, &run.profile, cap, at),
187            }
188        }
189    }
190
191    /// Learns a finished run of `profile` that ended at `at` (ms), having run under `cap`: its peak, how it ended,
192    /// and its CPU. Runs must come in the order they finished (`recent::Recent::read`).
193    pub fn learn(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
194        self.recent.read(run, profile, Ending::Finished, cap, at);
195        self.learn_cpu(run, profile);
196    }
197
198    /// Learns the CPU a finished run of `profile` used, without its peak.
199    pub fn learn_cpu(&mut self, run: &Ran, profile: &str) {
200        let Some(average) = run.cpu_average else {
201            return;
202        };
203        self.cpu_profiles
204            .entry(profile.to_owned())
205            .or_default()
206            .add(average, run.succeeded);
207        self.cpu_jobs
208            .entry(InProfile::new(&Key::of(run), profile))
209            .or_default()
210            .add(average, run.succeeded);
211    }
212
213    /// The CPU to reserve for a run of `key` in `profile`, whose `cpus` are `cap` millicores: the job's average
214    /// CPU (its CPU time over its run time), by the same fallbacks as memory without the margin. CPU is shared, not
215    /// a kill limit, so neither a run at its cap nor copies of the job beside it change it.
216    pub fn predict_cpu(&self, key: &Key, profile: &str, cap: u64) -> CpuPrediction {
217        let job = self.cpu_jobs.get(&InProfile::new(key, profile));
218        let min_jobs = u64::from(self.min_jobs);
219        let peers = self
220            .cpu_profiles
221            .get(profile)
222            .filter(|peers| peers.runs() >= min_jobs);
223        let (cpu, basis) = match (job.filter(|job| job.runs() > 0), peers) {
224            (Some(job), _) if job.runs() >= min_jobs => (
225                job.p95(),
226                Basis::Job {
227                    runs: job.runs(),
228                    peak: JobPeak::P95,
229                },
230            ),
231            (Some(job), Some(_)) if job.succeeded >= OWN_RUNS => (
232                job.max(),
233                Basis::Job {
234                    runs: job.runs(),
235                    peak: JobPeak::Largest,
236                },
237            ),
238            (Some(job), Some(peers)) => (
239                job.max().max(peers.p95()),
240                Basis::Profile { runs: peers.runs() },
241            ),
242            (None, Some(peers)) => (peers.max(), Basis::ProfileMax { runs: peers.runs() }),
243            _ => (cap, Basis::Cap),
244        };
245        CpuPrediction {
246            cpu: cpu
247                .div_ceil(CPU_GRANULE)
248                .saturating_mul(CPU_GRANULE)
249                .clamp(CPU_GRANULE, cap.max(CPU_GRANULE)),
250            basis,
251        }
252    }
253
254    /// How long a run of `key` in `profile` usually keeps its runner, if its runs say (`recent::JobRuns::usual`).
255    pub fn usual(&self, key: &Key, profile: &str) -> Option<Duration> {
256        self.recent.job(key, profile)?.usual()
257    }
258
259    /// The longest `usual` of `keys`, the queued jobs of a pool in `profile`, since GitHub may give its runner any of
260    /// them; `None` if any has none, or there is none.
261    pub fn longest_usual(
262        &self,
263        keys: impl IntoIterator<Item = Key>,
264        profile: &str,
265    ) -> Option<Duration> {
266        let usual: Option<Vec<Duration>> = keys
267            .into_iter()
268            .map(|key| self.usual(&key, profile))
269            .collect();
270        usual?.into_iter().max()
271    }
272
273    /// Learns a cancelled run of `profile`: how it ended, and its peak only when it met its cap. A run that met
274    /// its cap or was killed for memory holds its job in that profile at its cap (`Ran::capped`), a peak past what
275    /// it reserved makes it reserve its largest peak while that run is in its window.
276    pub fn mark(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
277        self.recent.read(run, profile, Ending::Cancelled, cap, at);
278    }
279
280    /// The memory to reserve for a run of `key` in `profile`, whose cap is `cap`, at `now` (ms), with `copies`
281    /// of it beside.
282    pub fn predict(
283        &self,
284        key: &Key,
285        profile: &str,
286        cap: u64,
287        now: u64,
288        copies: Copies,
289    ) -> Prediction {
290        let job = self.recent.job(key, profile);
291        if let Some(hold) = job.and_then(|job| job.held(now, Some(UNPREDICTABLE_FOR))) {
292            return Prediction {
293                memory: cap,
294                basis: Basis::Unpredictable {
295                    until: hold.at.saturating_add(UNPREDICTABLE_FOR) / 1000,
296                },
297            };
298        }
299        let min_jobs = u64::from(self.min_jobs);
300        let peers = self.recent.profile(profile);
301        let peers_runs = peers.len() as u64;
302        let overran = job.and_then(|job| {
303            job.overruns(now, UNPREDICTABLE_FOR)
304                .fold(None, |most: Option<(u64, u64)>, overrun| {
305                    let until = overrun.at.saturating_add(UNPREDICTABLE_FOR);
306                    Some(most.map_or((overrun.peak, until), |(peak, last)| {
307                        (peak.max(overrun.peak), last.max(until))
308                    }))
309                })
310        });
311        let (memory, basis) = match (job, peers_runs >= min_jobs) {
312            // Seen only cancelled, so its peaks say nothing.
313            (Some(job), _) if job.runs() == 0 => (cap, Basis::Cap),
314            (Some(job), _) if let Some((peak, until)) = overran => (
315                self.with_margin(job.max().max(peak)),
316                Basis::Overran {
317                    until: until / 1000,
318                },
319            ),
320            (Some(job), _) if job.runs() >= min_jobs => (
321                self.with_margin(spread(job.peaks().to_vec()).p95),
322                Basis::Job {
323                    runs: job.runs(),
324                    peak: JobPeak::P95,
325                },
326            ),
327            (Some(job), true) if job.succeeded() >= OWN_RUNS && copies == Copies::Alone => (
328                self.with_margin(job.max()),
329                Basis::Job {
330                    runs: job.runs(),
331                    peak: JobPeak::Largest,
332                },
333            ),
334            (Some(job), true) => (
335                self.with_margin(job.max().max(spread(peers.to_vec()).p95)),
336                Basis::Profile { runs: peers_runs },
337            ),
338            // A job never seen may be the profile's heaviest.
339            (None, true) => (
340                self.with_margin(peers.last().copied().unwrap_or(0)),
341                Basis::ProfileMax { runs: peers_runs },
342            ),
343            _ => (cap, Basis::Cap),
344        };
345        Prediction {
346            memory: memory.min(cap),
347            basis,
348        }
349    }
350    /// `peak` plus the margin, rounded up to 256M.
351    fn with_margin(&self, peak: u64) -> u64 {
352        let memory = peak.saturating_add(peak.saturating_mul(u64::from(self.margin)) / 100);
353        memory
354            .div_ceil(GRANULE)
355            .saturating_mul(GRANULE)
356            .max(GRANULE)
357    }
358}
359
360/// How a replay admits a queued job.
361#[derive(Debug, Clone, Copy, PartialEq, Eq)]
362pub enum Policy {
363    /// When a slot is free and the caps of the running jobs and its own fit the budget: what runnerd does now.
364    Caps,
365    /// As the daemon admits: when a slot is free, the running jobs (each at the larger of its prediction and its
366    /// peak) and the largest prediction among the repository's waiting jobs fit the budget, and the running jobs'
367    /// peaks are under `HIGH_WATER` percent of it. A started job then reserves its own prediction.
368    Measured,
369}
370
371/// Whether a replay puts up the barrier `scheduler::plan` does for a starved job (ADR 0096).
372#[derive(Debug, Clone, Copy, PartialEq, Eq)]
373pub enum Barriers {
374    /// As the daemon runs: a barrier, and the younger jobs `priority::Backfill` lets start behind it (ADR 0097).
375    On,
376    /// A barrier nothing younger starts behind: what to compare with.
377    Strict,
378    /// A job that does not fit lets every later one past, however long it waited: what to compare with.
379    Off,
380}
381
382/// When a replay's jobs arrive.
383#[derive(Debug, Clone, Copy, PartialEq, Eq)]
384pub enum Arrivals {
385    /// When they were queued, whatever the replay did to the jobs before them.
386    AsQueued,
387    /// A job that queued after another of its run attempt ended follows it: it arrives as long after the replayed end
388    /// of the last such job as it did after the real one. The history does not keep a job's `needs`, so this reads them
389    /// from the times. A job that follows one never started does not arrive.
390    AfterNeeds,
391}
392
393/// How a replay goes.
394#[derive(Debug, Clone, Copy)]
395pub struct Replaying<'known> {
396    /// The barrier for a starved job.
397    pub barriers: Barriers,
398    /// When jobs arrive.
399    pub arrivals: Arrivals,
400    /// The history to know from the start, as the daemon does by the time these jobs queue: its rows that ended before
401    /// the first job arrives. `None`, the replay knows only the runs it finishes.
402    pub known: Option<&'known History>,
403    /// How the jobs really ran. With it each job uses what its samples say from its replayed start, is known only when
404    /// the daemon could name it, and the host's memory bounds what starts. `None`, each holds its peak for its whole run.
405    pub trace: Option<&'known Trace>,
406    /// The most the pooled count may take off the plain one (`pooled::Snapshot::most`); read only with a `trace`.
407    pub most_credit: u64,
408    /// What the host's limit reads of what runs.
409    pub host_reserve: HostReserve,
410    /// Whether `Backfill` expects what the credit may still give, as the daemon does.
411    pub credit_room: CreditRoom,
412    /// What holds the host's larger margin up.
413    pub band: Band,
414    /// With a `trace` and measured admission, count by the growth count instead of `most_credit` and `host_reserve`.
415    pub growth: Option<GrowthCount>,
416}
417
418/// How a replay counts by the growth count (`pooled::Snapshot::growth`).
419#[derive(Debug, Clone, Copy, PartialEq, Eq)]
420pub struct GrowthCount {
421    /// How the count counts; its `hold` is the brake's to set.
422    pub growth: pooled::Growth,
423    /// Whether `growth::Growth` rests the count once what runs grows past the room it kept.
424    pub brake: Brake,
425    /// Whether a look below the guard's line rests it for `growth::GUARD_HOLD`; only with `Brake::On`.
426    pub guard: GuardHold,
427}
428
429impl GrowthCount {
430    /// The daemon's: `pooled::GROWTH`, its brake and its guard's hold (ADR 0130).
431    pub const DAEMON: GrowthCount = GrowthCount {
432        growth: pooled::GROWTH,
433        brake: Brake::On,
434        guard: GuardHold::On,
435    };
436}
437
438/// Whether a replay's growth count has its brake.
439#[derive(Debug, Clone, Copy, PartialEq, Eq)]
440pub enum Brake {
441    /// As the daemon has it.
442    On,
443    /// To show what the brake costs and what it guards against.
444    Off,
445}
446
447/// Whether a replay's brake holds the growth count back for `growth::GUARD_HOLD` after a look below the guard's line.
448#[derive(Debug, Clone, Copy, PartialEq, Eq)]
449pub enum GuardHold {
450    /// As the daemon has it.
451    On,
452    /// The guard reads each plan alone, as the density study had it.
453    Off,
454}
455
456/// What the host's limit reads of what runs in a replay (ADR 0108).
457#[derive(Debug, Clone, Copy, PartialEq, Eq)]
458pub enum HostReserve {
459    /// Every runner's take: the plain count, as before 0108.
460    Plain,
461    /// As the daemon does: eligible runners at their use, with room kept for the two largest growths
462    /// (`pooled::Count::hosted`).
463    Top2,
464}
465
466/// What holds up the host's larger margin in a replay.
467#[derive(Debug, Clone, Copy, PartialEq, Eq)]
468pub enum Band {
469    /// As the daemon does: jobs wait for the host and none fits the plain margin (`host::short`).
470    NoWaiterFits,
471    /// To show what that gives (ADR 0102): any job that waits for the host.
472    AnyWaiter,
473}
474
475/// Whether a replay's `Backfill` reads `Budget::credit_room`.
476#[derive(Debug, Clone, Copy, PartialEq, Eq)]
477pub enum CreditRoom {
478    /// As the daemon does.
479    Counted,
480    /// To show what that keeps: an owner may then start before the time its younger jobs were held to.
481    LeftOut,
482}
483
484impl From<Barriers> for Replaying<'_> {
485    fn from(barriers: Barriers) -> Self {
486        Replaying {
487            barriers,
488            arrivals: Arrivals::AsQueued,
489            known: None,
490            trace: None,
491            most_credit: 0,
492            host_reserve: HostReserve::Top2,
493            credit_room: CreditRoom::Counted,
494            band: Band::NoWaiterFits,
495            growth: None,
496        }
497    }
498}
499
500/// What a replay did with one pool's jobs.
501#[derive(Debug, Clone, Default, PartialEq, Eq)]
502pub struct PoolReplay {
503    /// Seconds from queued to started, of each job that started.
504    pub waits: Vec<u64>,
505    /// The jobs the replay never started.
506    pub never_started: u64,
507}
508
509impl PoolReplay {
510    /// The spread of `waits`.
511    pub fn wait(&self) -> Spread {
512        spread(self.waits.clone())
513    }
514}
515
516/// What a replay did with one attempt of a workflow run: the closest fact it has to a pull request's checks finishing.
517#[derive(Debug, Clone, Default, PartialEq, Eq)]
518pub struct RunReplay {
519    /// Seconds from its first job's arrival to its last job's end.
520    pub took: u64,
521    /// The profiles its jobs ran in.
522    pub profiles: BTreeSet<String>,
523}
524
525/// A run attempt as a replay tells them apart.
526type RunKey = (String, u64, u32);
527
528/// The jobs a replay started behind a barrier (ADR 0097).
529#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
530pub struct Backfilled {
531    /// How many.
532    pub jobs: u64,
533    /// Of those, how many ran past the usual run time they passed by.
534    pub overran: u64,
535    /// The furthest one did, in seconds.
536    pub most_overrun: u64,
537}
538
539/// What a replay did with the history's jobs.
540#[derive(Debug, Clone, PartialEq, Eq)]
541pub struct Replay {
542    /// The jobs replayed: finished ones of a configured profile.
543    pub jobs: u64,
544    /// Of those, the ones the policy never started: more than the budget holds.
545    pub never_started: u64,
546    /// Seconds from queued to started.
547    pub wait: Spread,
548    /// The mean of those, in seconds.
549    pub mean_wait: u64,
550    /// The most jobs that ran at once.
551    pub most_running: u64,
552    /// The most memory, in bytes, the running jobs' peaks and the mirror add up to at one moment: as if every
553    /// running job peaked at once, which is more than the slice ever holds. Not a bound on the daemon, which can
554    /// overlap more: it sees what jobs use, less than their peaks while they warm up, and the replay leaves out
555    /// start latency, seeds, shells and cancelled jobs.
556    pub worst_overlap: u64,
557    /// Seconds from the first job queued to the last one finished.
558    pub makespan: u64,
559    /// Jobs whose peak was above what admission reserved for them when they ended.
560    pub under_predicted: u64,
561    /// How many times the high-water mark held a job back that the predictions had room for.
562    pub held_back: u64,
563    /// How many times the CPU budget held a job back that memory and its slots had room for.
564    pub cpu_held: u64,
565    /// The most CPU, in millicores, the running jobs' averages add up to at one moment.
566    pub worst_cpu: u64,
567    /// By pool, the jobs that ran in it.
568    pub pools: BTreeMap<Pool, PoolReplay>,
569    /// What the running jobs took of the budget over the replay, in byte-milliseconds.
570    pub charged: u128,
571    /// The budget over the replay, in byte-milliseconds; 0 without one. `charged` over it is the busy share.
572    pub capacity: u128,
573    /// How long a barrier stood, in milliseconds.
574    pub barrier_for: u64,
575    /// What the budget had free while a barrier stood, in byte-milliseconds: at most what the barrier cost, as some of
576    /// it no younger job could have used.
577    pub withheld: u128,
578    /// By run attempt, what the replay did with those whose jobs started.
579    pub runs: Vec<RunReplay>,
580    /// What started behind a barrier.
581    pub backfilled: Backfilled,
582    /// How long jobs waited, added up, for the slice's budget, in ms; only with a trace.
583    pub slice_waited: u64,
584    /// How long jobs the slice's budget had room for waited for the host's memory, added up, in ms; only with a trace.
585    pub host_waited: u64,
586    /// What the replay found of a pooled count's risks; only with a trace.
587    pub hazard: Hazard,
588}
589
590/// What the jobs a replay runs did as they really ran, to read its figures against.
591#[derive(Debug, Clone, Default, PartialEq, Eq)]
592pub struct Recorded {
593    /// By pool, the seconds each job waited from queued to its runner's start, less what passed while no runnerd ran;
594    /// a job a warm runner took waited none.
595    pub pools: BTreeMap<Pool, PoolReplay>,
596    /// By run attempt, from its first job's queueing to its last job's end.
597    pub runs: Vec<RunReplay>,
598    /// How long the jobs waited for the host's memory alone, added up, in ms.
599    pub host_waited: u64,
600}
601
602impl Recorded {
603    /// Every job's wait added up, in seconds.
604    pub fn waited(&self) -> u64 {
605        self.pools.values().flat_map(|pool| &pool.waits).sum()
606    }
607}
608
609#[cfg(test)]
610mod tests;