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;