Skip to main content

runnerd_core/
sizing.rs

1//! Right-sizing advice from the job history: the spread of each profile's and each job's sampled peaks, waits and
2//! slot use, and the `memory` and `slots` to set. Pure: the store reads the history, the daemon serves the result
3//! (`api::Sizing`). It never changes the config: a client applies advice through `PUT /v1/config`, which validates
4//! it like any other config, and under `[sizing] auto` the daemon applies what `auto::changes` picks the same way.
5
6use crate::admission::Key;
7use crate::admission::recent::Recent;
8use crate::api::{self, Advice, Peaks, Spread};
9use crate::config::{Admission, Config};
10use crate::observe::metrics::SAMPLE_INTERVAL;
11
12pub(crate) use crate::api::GRANULE;
13
14/// Without its container's `memory.events`, a peak at or above this share of its cap, in percent, likely met it.
15const AT_CAP: u64 = 95;
16
17/// Lowering a cap is advised once it saves at least this share of it, in percent.
18const WORTH_LOWERING: u64 = 10;
19
20/// Jobs that waited this long at p95, in seconds, or slots busy this share of the time, in percent, want more
21/// slots.
22const WAITED: u64 = 60;
23const BUSY: u32 = 50;
24
25/// One finished job of this daemon's runners, as sizing reads it. Times in milliseconds.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Ran {
28    /// `owner/name`.
29    pub repository: String,
30    /// The workflow's name, when known.
31    pub workflow: Option<String>,
32    /// The job's name.
33    pub name: String,
34    /// The profile its runner ran in.
35    pub profile: String,
36    /// Its container's memory cap, when recorded.
37    pub memory_cap: Option<u64>,
38    /// Its container's CPU cap, millicores, when recorded.
39    pub cpu_cap: Option<u64>,
40    /// Its sampled memory peak, bytes, as `measure` counts memory.
41    pub memory_peak: u64,
42    /// Its sampled CPU peak, millicores.
43    pub cpu_peak: u64,
44    /// Its CPU time over its run time, millicores; `None` when not recorded.
45    pub cpu_average: Option<u64>,
46    /// When it was queued.
47    pub queued_at: u64,
48    /// When it started; `None` for a job lost before.
49    pub started_at: Option<u64>,
50    /// When its runner's container started: before `queued_at`, it was a warm runner.
51    pub runner_started_at: u64,
52    /// When it finished, or was found lost.
53    pub finished_at: Option<u64>,
54    /// Whether the kernel killed a process in its container for memory.
55    pub oom_killed: bool,
56    /// Whether its container's memory, or a descendant's, reached a limit with nothing left to reclaim
57    /// (`memory.events` `oom`); `None` when its events were not recorded.
58    pub hit_cap: Option<bool>,
59    /// Whether its container's own limit failed reclaim (`memory.events.local` `oom`), not a descendant's; `None`
60    /// when not recorded, as before schema 14.
61    pub own_cap: Option<bool>,
62    /// What its sampled memory counts.
63    pub measure: Measure,
64    /// Whether it completed with success: a failed or lost run may have stopped before its heaviest step.
65    pub succeeded: bool,
66    /// Whether it completed with `failure` or `timed_out`: not lost, not cancelled.
67    pub failed: bool,
68    /// Its workflow run on GitHub: a re-run of its failed jobs has the same.
69    pub run_id: u64,
70    /// The branch it ran for, when known.
71    pub branch: Option<String>,
72    /// What measured admission reserved for it; `None` under caps or for an adopted runner.
73    pub reserved: Option<u64>,
74    /// How long of its wait it waited because the host's memory could not take its runner, in ms: no more slots
75    /// would have started it sooner.
76    pub host_waited: u64,
77    /// How much of its wait passed while no runnerd ran, in ms.
78    pub unseen: u64,
79    /// The periods of its CPU quota it had work in (`api::JobMetrics::cpu_periods`); `None` where the kernel kept no
80    /// figure, as in runs from before schema 17.
81    pub cpu_periods: Option<u64>,
82    /// Of those, the periods its quota throttled it in (`api::JobMetrics::cpu_throttled`).
83    pub cpu_throttled: Option<u64>,
84}
85
86/// A job's wait for a runner as sizing, insights and the history's figures count it: from when GitHub queued it, or
87/// from when the history holds every job if that came later (`history_kept`), as for a job queued before runnerd
88/// first ran, to when it started, less what of it passed while no runnerd ran (ADR 0081). A job's own page shows its
89/// whole wait, as GitHub's does; arrivals, as `simulate` and warm runners model them, go by `queued_at`.
90#[derive(Debug, Clone, Copy, PartialEq, Eq)]
91pub struct Wait {
92    /// When GitHub queued it, in ms.
93    pub queued_at: u64,
94    /// When it started, in ms.
95    pub started_at: u64,
96    /// How much of it passed while no runnerd ran, in ms.
97    pub unseen: u64,
98}
99
100impl Wait {
101    /// In ms, 0 at least, with the history holding every job since `kept_since` (ms).
102    pub fn counted(self, kept_since: u64) -> u64 {
103        self.started_at
104            .saturating_sub(self.queued_at.max(kept_since))
105            .saturating_sub(self.unseen)
106    }
107}
108
109/// What a run's sampled memory counts.
110#[derive(Debug, Clone, Copy, PartialEq, Eq)]
111pub enum Measure {
112    /// `memory.current` less `inactive_file`, as runners started before schema version 8 were sampled: page cache
113    /// read twice (`active_file`) counts, so peaks overstate what a job needs.
114    WithActiveFile,
115    /// `memory.current` less the file LRU lists (`active_file`, `inactive_file`): an estimate of what a job holds
116    /// without the page cache the kernel can drop.
117    WithoutPageCache,
118}
119
120/// What a run says about its container's memory cap (ADR 0070).
121#[derive(Debug, Clone, Copy, PartialEq, Eq)]
122pub enum Capped {
123    /// The container's own limit failed reclaim: it needed more than the cap.
124    Met,
125    /// Recorded without the local counter: by the reading before it, a kill or a limit hit in the container, or
126    /// without events a peak within `AT_CAP` percent of the cap. Holds and floors as `Met`, never raises a cap.
127    Assumed,
128    /// A process in it was killed for memory while its own limit held: the slice or the host ran out.
129    Killed,
130    /// None of those. A peak near the cap with no `oom` at it is clear: a JVM fills the room it has.
131    Clear,
132}
133
134impl Capped {
135    /// Whether it says the job needed its cap: `Met` or `Assumed`.
136    pub fn met(self) -> bool {
137        matches!(self, Capped::Met | Capped::Assumed)
138    }
139
140    /// Whether it puts its job on its cap: anything but `Clear`.
141    pub fn holds(self) -> bool {
142        self != Capped::Clear
143    }
144}
145
146impl Ran {
147    /// Its wait, once it started.
148    pub fn wait(&self) -> Option<Wait> {
149        Some(Wait {
150            queued_at: self.queued_at,
151            started_at: self.started_at?,
152            unseen: self.unseen,
153        })
154    }
155
156    /// What it says about its container's `cap`. A kill that only a descendant's own limit explains, the counters
157    /// showing a limit hit below the container and none at it, is a service container the job capped itself: clear.
158    /// A kill no sample saw an `oom` before, its last sample within `AT_CAP` percent of the cap, met it in the last
159    /// interval.
160    pub fn capped(&self, cap: u64) -> Capped {
161        match self.own_cap {
162            Some(true) => Capped::Met,
163            // No sample saw `oom` at any level and its last came near the cap: its own limit killed it before the
164            // next sample could count it.
165            Some(false)
166                if self.oom_killed
167                    && self.hit_cap == Some(false)
168                    && self.memory_peak.saturating_mul(100) >= cap.saturating_mul(AT_CAP) =>
169            {
170                Capped::Met
171            }
172            Some(false) if self.oom_killed && self.hit_cap != Some(true) => Capped::Killed,
173            None if self.oom_killed
174                || self.hit_cap.unwrap_or_else(|| {
175                    self.memory_peak.saturating_mul(100) >= cap.saturating_mul(AT_CAP)
176                }) =>
177            {
178                Capped::Assumed
179            }
180            Some(false) | None => Capped::Clear,
181        }
182    }
183}
184
185/// One runner container's time in a slot for a job. Times in milliseconds.
186#[derive(Debug, Clone, PartialEq, Eq)]
187pub struct Held {
188    /// Its profile.
189    pub profile: String,
190    /// When it started holding the slot for a job: its start, or when its job was queued if that came later, as for
191    /// a warm runner.
192    pub started_at: u64,
193    /// When it was removed; `None` while it runs.
194    pub removed_at: Option<u64>,
195}
196
197/// A profile's `cpus` as the daemon ran it from `at` (ms), by its `profile.changed` event: one when it started with
198/// the profile, and after each reload or restart that changed the profile's image, CPUs, memory or slots.
199#[derive(Debug, Clone, PartialEq, Eq)]
200pub struct CpusSet {
201    /// The profile.
202    pub profile: String,
203    /// Its `cpus` from then.
204    pub cpus: u32,
205    /// When, in milliseconds.
206    pub at: u64,
207}
208
209/// A profile's `memory` as the daemon ran it from `at` (ms), by its `profile.changed` event, as `CpusSet` has its
210/// `cpus`.
211#[derive(Debug, Clone, PartialEq, Eq)]
212pub struct MemorySet {
213    /// The profile.
214    pub profile: String,
215    /// Its `memory` from then, in bytes.
216    pub memory: u64,
217    /// When, in milliseconds.
218    pub at: u64,
219}
220
221/// What the store reads for sizing.
222#[derive(Debug, Clone, Default, PartialEq, Eq)]
223pub struct History {
224    /// Finished jobs with a recorded peak, cancelled ones left out.
225    pub jobs: Vec<Ran>,
226    /// Cancelled jobs, for what admission learns from how they ended: a kill for memory, a peak at the cap or past
227    /// what was reserved. Their peaks (0 when never sampled) are not read as a job's size.
228    pub cancelled: Vec<Ran>,
229    /// Runners that held a slot at some point after the history's start.
230    pub runners: Vec<Held>,
231    /// Auto sizing's changes, oldest first, from `CHANGES_READ` before now: what a revert reads (ADR 0070). Empty
232    /// where nothing reads them, as for admission.
233    pub changes: Vec<api::SizingChange>,
234    /// Each profile's `memory` as the daemon ran it, oldest first: since when a raise reads runs at it.
235    pub memory_set: Vec<MemorySet>,
236    /// From when, in ms, the history holds every job (`history_kept`): a wait before it, as of a job queued before
237    /// runnerd first ran, counts from then.
238    pub kept_since: u64,
239}
240
241/// What `advise` sizes against besides the history.
242#[derive(Debug, Clone, Copy)]
243pub struct Window {
244    /// The start asked for, in milliseconds, at most `now`.
245    pub since: u64,
246    /// Now, in milliseconds.
247    pub now: u64,
248    /// Seconds between two samples of a container.
249    pub sample_interval: u64,
250}
251
252impl Window {
253    /// The window `GET /v1/sizing` reads: from `since` (seconds), default 30 days before `now` (seconds), and
254    /// never after `now`.
255    pub fn new(since: Option<u64>, now: u64) -> Window {
256        Window {
257            since: since
258                .unwrap_or_else(|| now.saturating_sub(30 * 24 * 3600))
259                .min(now)
260                .saturating_mul(1000),
261            now: now.saturating_mul(1000),
262            sample_interval: SAMPLE_INTERVAL.as_secs(),
263        }
264    }
265}
266
267/// The advice for every profile of `config` from `history`, against the slice's `memory_max` as `config`'s
268/// admission policy budgets it. Peaks, and the memory advice, go by each job's sizing window over the history's last
269/// 30 days (`memory`, ADR 0070); `window.since` narrows only the waits, the busy share and the starts.
270pub fn advise(
271    config: &Config,
272    memory_max: Option<u64>,
273    history: &History,
274    window: Window,
275) -> api::Sizing {
276    let since = first_runner(history, window.since);
277    let caps = config.memory_caps().map_or(u64::MAX, |caps| caps.0);
278    let mirror = config.mirror_memory();
279    let rules = &config.sizing;
280    let recent = memory::windows(config, history, window.now);
281    let profiles = config
282        .profiles
283        .iter()
284        .map(|(name, profile)| {
285            let jobs: Vec<&Ran> = history
286                .jobs
287                .iter()
288                .filter(|job| job.profile == *name && job.queued_at >= window.since)
289                .collect();
290            let share = profile.memory.0.saturating_mul(u64::from(profile.slots));
291            let busy = busy(history, name, profile.slots, since, window.now);
292            let wait = waits(&jobs, history.kept_since);
293            let starts = starts(&jobs, history.kept_since);
294            let cap = profile.memory.0;
295            let took = memory::took(&history.memory_set, name, cap, window.now);
296            let sized = Sized {
297                cap,
298                cpus: u64::from(profile.cpus) * 1000,
299                slots: profile.slots,
300                share,
301                admission: config.host.admission,
302                room: memory_max.map(|max| match config.host.admission {
303                    // What the slice leaves this profile once the other profiles and the mirror took theirs.
304                    Admission::Caps => max.saturating_sub(caps.saturating_sub(share)),
305                    // Measured admission reserves predicted peaks, not caps: the config check only holds one
306                    // runner of each profile beside the mirror.
307                    Admission::Measured => max.saturating_sub(mirror),
308                }),
309                wants_slots: wait.p95 >= WAITED || busy >= BUSY,
310                min_jobs: rules.min_jobs,
311            };
312            let raises = Raises {
313                history,
314                recent: &recent,
315                profile: name,
316                cap,
317                took,
318                margin: rules.margin,
319            };
320            let memory = job_memory(&raises, &jobs, &sized, window.now, busy);
321            let peaks = memory::peaks(
322                recent.jobs_of(name).flat_map(|(_, runs)| runs.window()),
323                memory.on_cap,
324                sized.cpus,
325            );
326            let current = api::Resize {
327                memory: cap,
328                slots: profile.slots,
329                cpus: None,
330            };
331            let revert = memory::revert(config, history, name, current);
332            let advice = match &revert {
333                Some((_, to)) => Advice::Raise {
334                    memory: to.memory,
335                    slots: to.slots,
336                },
337                None => sized.advice(
338                    &peaks,
339                    Needs {
340                        raise: raises.need(None),
341                        floor: memory.floor.max(memory::revert_floor(history, name)),
342                    },
343                    sized.wants_slots,
344                ),
345            };
346            api::ProfileSizing {
347                name: name.clone(),
348                memory: cap,
349                cpus: profile.cpus,
350                slots: profile.slots,
351                advice,
352                revert: revert.map(|(revert, _)| revert),
353                peaks,
354                wait,
355                starts,
356                busy,
357                wants_slots: sized.wants_slots,
358                jobs: memory.jobs,
359            }
360        })
361        .collect();
362    api::Sizing {
363        since: since / 1000,
364        until: window.now / 1000,
365        margin: rules.margin,
366        sample_interval: window.sample_interval,
367        min_jobs: rules.min_jobs,
368        memory_max,
369        admission: config.host.admission.policy(),
370        profiles,
371        auto: config.sizing.auto,
372        changes: Vec::new(),
373        auto_plan: None,
374    }
375}
376
377/// What a raise of one profile reads (`memory::raise_need`).
378struct Raises<'history> {
379    history: &'history History,
380    recent: &'history Recent,
381    profile: &'history str,
382    /// Its `memory`.
383    cap: u64,
384    /// Since when it has had it, in ms.
385    took: u64,
386    margin: u32,
387}
388
389impl Raises<'_> {
390    /// What a raise needs from the job `key`, or from every job for `None`.
391    fn need(&self, key: Option<&Key>) -> u64 {
392        memory::raise_need(
393            self.history,
394            self.recent,
395            self.profile,
396            self.cap,
397            self.took,
398            self.margin,
399            key,
400        )
401    }
402}
403
404/// What a profile's jobs say about its `memory`.
405struct JobMemory {
406    /// Each job's sizing.
407    jobs: Vec<api::JobSizing>,
408    /// How many of them are on their cap.
409    on_cap: u64,
410    /// The largest of their floors.
411    floor: u64,
412}
413
414/// Each job of `raises.profile` with runs in its window: its peaks, waits and advice; `jobs` are the profile's runs
415/// since the window's start, for the waits.
416fn job_memory(raises: &Raises<'_>, jobs: &[&Ran], sized: &Sized, now: u64, busy: u32) -> JobMemory {
417    let mut on_cap = 0;
418    let mut floor = 0;
419    let sizings = raises
420        .recent
421        .jobs_of(raises.profile)
422        .filter(|(_, runs)| runs.runs() > 0)
423        .map(|(key, runs)| {
424            let held = memory::on_cap(runs, now);
425            on_cap += u64::from(held);
426            let peaks = memory::peaks(runs.window(), u64::from(held), sized.cpus);
427            let needs = Needs {
428                raise: raises.need(Some(key)),
429                floor: memory::floor(runs, raises.margin),
430            };
431            floor = floor.max(needs.floor);
432            let runs_of: Vec<&Ran> = jobs
433                .iter()
434                .copied()
435                .filter(|job| Key::of(job) == *key)
436                .collect();
437            let wait = waits(&runs_of, raises.history.kept_since);
438            api::JobSizing {
439                repository: key.repository.clone(),
440                workflow: key.workflow.clone(),
441                name: key.name.clone(),
442                advice: sized.advice(&peaks, needs, wait.p95 >= WAITED || busy >= BUSY),
443                peaks,
444                wait,
445            }
446        })
447        .collect();
448    JobMemory {
449        jobs: sizings,
450        on_cap,
451        floor,
452    }
453}
454
455/// Where a history read from `start` (ms) begins: at its first runner when that started later, as a new daemon's
456/// history does.
457fn first_runner(history: &History, start: u64) -> u64 {
458    history
459        .runners
460        .iter()
461        .map(|runner| runner.started_at)
462        .min()
463        .map_or(start, |first| first.max(start))
464}
465
466/// The percent of the time from `since` to `now` (ms) that the profile's runners held its `slots`.
467fn busy(history: &History, profile: &str, slots: u32, since: u64, now: u64) -> u32 {
468    let span = now.saturating_sub(since).max(1);
469    let held: u64 = history
470        .runners
471        .iter()
472        .filter(|runner| runner.profile == profile)
473        .map(|runner| {
474            let end = runner.removed_at.unwrap_or(now).min(now);
475            end.saturating_sub(runner.started_at.max(since))
476        })
477        .sum();
478    u32::try_from(
479        (held.saturating_mul(100) / span.saturating_mul(u64::from(slots).max(1))).min(100),
480    )
481    .unwrap_or(100)
482}
483
484/// A profile's limits and the rules advice follows.
485struct Sized {
486    cap: u64,
487    /// Its `cpus`, in millicores: CPU peaks are read only of runs at them.
488    cpus: u64,
489    slots: u32,
490    /// What its slots take of the budget now: `memory × slots`.
491    share: u64,
492    admission: Admission,
493    /// The memory the slice holds for it, as `admission` budgets it: all its slots at their caps under `caps`, one
494    /// runner under `measured`; `None` for an unlimited slice.
495    room: Option<u64>,
496    /// Whether its jobs waited for a slot at p95, or its slots were busy, enough to want more.
497    wants_slots: bool,
498    min_jobs: u32,
499}
500
501/// What a set of jobs' runs say its `memory` needs (`memory`, ADR 0070).
502#[derive(Debug, Clone, Copy)]
503struct Needs {
504    /// What a raise goes to: from runs that met the current cap since the profile took it; 0 without one.
505    raise: u64,
506    /// What a lowering stays at or above: every windowed run's need, and any revert's floor.
507    floor: u64,
508}
509
510impl Sized {
511    /// A raise toward `needs.raise` when it is above the cap; a lowering toward `needs.floor` when that saves a tenth
512    /// and no job is on its cap; else keep, with `needs.floor` as what the jobs need, above the cap or not.
513    fn advice(&self, peaks: &Peaks, needs: Needs, wants_slots: bool) -> Advice {
514        if peaks.jobs < u64::from(self.min_jobs) {
515            return Advice::TooFew { jobs: peaks.jobs };
516        }
517        if needs.raise > self.cap {
518            let need = needs.raise;
519            let fit = |memory: u64| u32::try_from(memory / need).unwrap_or(u32::MAX);
520            let slots = match (self.admission, self.room) {
521                (Admission::Caps, Some(room)) => fit(room).min(self.slots),
522                (Admission::Measured, Some(room)) if room < need => 0,
523                (_, _) => self.slots,
524            };
525            if slots == 0 {
526                return Advice::SliceTooSmall { memory: need };
527            }
528            return Advice::Raise {
529                memory: need,
530                slots,
531            };
532        }
533        let need = needs.floor.max(GRANULE);
534        // A job on its cap may have been held back or killed by it: no lowering until it ran clear of it again.
535        if peaks.on_cap == 0
536            && need <= self.cap
537            && self.cap - need >= self.cap * WORTH_LOWERING / 100
538        {
539            let fit = |memory: u64| u32::try_from(memory / need).unwrap_or(u32::MAX);
540            // Under measured admission slots are not bought with caps: the advice line says when more may help.
541            return Advice::Lower {
542                memory: need,
543                slots: if wants_slots && self.admission == Admission::Caps {
544                    fit(self.share).max(self.slots)
545                } else {
546                    self.slots
547                },
548            };
549        }
550        Advice::Keep { memory: need }
551    }
552}
553
554/// The [waits](Wait) of the jobs that started, in seconds, less what they waited for the host's memory.
555fn waits(jobs: &[&Ran], kept_since: u64) -> Spread {
556    spread(
557        jobs.iter()
558            .filter_map(|job| {
559                job.wait()
560                    .map(|wait| wait.counted(kept_since).saturating_sub(job.host_waited) / 1000)
561            })
562            .collect(),
563    )
564}
565
566/// The jobs that started on a warm runner and the others, and their median waits.
567fn starts(jobs: &[&Ran], kept_since: u64) -> api::Starts {
568    let (warm, cold): (Vec<&Ran>, Vec<&Ran>) = jobs
569        .iter()
570        .filter(|job| job.started_at.is_some())
571        .partition(|job| job.runner_started_at < job.queued_at);
572    let count = |jobs: &[&Ran]| u32::try_from(jobs.len()).unwrap_or(u32::MAX);
573    api::Starts {
574        warm: count(&warm),
575        warm_p50: waits(&warm, kept_since).p50,
576        cold: count(&cold),
577        cold_p50: waits(&cold, kept_since).p50,
578    }
579}
580
581/// Nearest-rank percentiles; all zero for no values.
582pub(crate) fn spread(mut values: Vec<u64>) -> Spread {
583    values.sort_unstable();
584    let rank = |percent: usize| {
585        let index = (values.len() * percent).div_ceil(100).saturating_sub(1);
586        values.get(index).copied().unwrap_or(0)
587    };
588    Spread {
589        p50: rank(50),
590        p95: rank(95),
591        p99: rank(99),
592        max: values.last().copied().unwrap_or(0),
593    }
594}
595
596pub mod auto;
597pub mod memory;
598
599#[cfg(test)]
600mod tests;