pub mod growth;
pub mod host;
pub mod pooled;
pub mod recent;
mod replay;
pub mod trace;
use std::collections::{BTreeMap, BTreeSet};
use std::time::Duration;
use crate::api::Spread;
use crate::api::{Basis, JobPeak};
use crate::config;
use crate::scheduler::Pool;
use crate::sizing::{GRANULE, History, Ran, spread};
use recent::{Ending, RECENT_RUNS, Recent};
pub use replay::{recorded, simulate};
use trace::{Hazard, OOMD_UNDER, Reading, RunId, RunTrace, STEP, THROTTLES_UNDER, Trace};
pub const UNPREDICTABLE_FOR: u64 = 7 * 24 * 3600 * 1000;
pub const OWN_RUNS: u64 = 2;
pub const HIGH_WATER: u64 = 90;
pub const CPU_GRANULE: u64 = 100;
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key {
pub repository: String,
pub workflow: Option<String>,
pub name: String,
}
impl Key {
pub fn of(run: &Ran) -> Key {
Key {
repository: run.repository.clone(),
workflow: run.workflow.clone(),
name: run.name.clone(),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Copies {
Alone,
Several,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Prediction {
pub memory: u64,
pub basis: Basis,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CpuPrediction {
pub cpu: u64,
pub basis: Basis,
}
#[derive(Debug, Clone, Default)]
struct Averages {
sorted: Vec<u64>,
succeeded: u64,
}
impl Averages {
fn add(&mut self, average: u64, succeeded: bool) {
let at = self.sorted.partition_point(|known| *known <= average);
self.sorted.insert(at, average);
self.succeeded += u64::from(succeeded);
}
fn runs(&self) -> u64 {
self.sorted.len() as u64
}
fn p95(&self) -> u64 {
spread(self.sorted.clone()).p95
}
fn max(&self) -> u64 {
self.sorted.last().copied().unwrap_or(0)
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct InProfile {
key: Key,
profile: String,
}
impl InProfile {
fn new(key: &Key, profile: &str) -> InProfile {
InProfile {
key: key.clone(),
profile: profile.to_owned(),
}
}
}
#[derive(Debug, Clone)]
pub struct Predictor {
margin: u32,
min_jobs: u32,
recent: Recent,
cpu_jobs: BTreeMap<InProfile, Averages>,
cpu_profiles: BTreeMap<String, Averages>,
}
impl Predictor {
pub fn new(rules: &config::Sizing) -> Predictor {
Predictor {
margin: rules.margin,
min_jobs: rules.min_jobs,
recent: Recent::new(RECENT_RUNS.max(u64::from(rules.min_jobs))),
cpu_jobs: BTreeMap::new(),
cpu_profiles: BTreeMap::new(),
}
}
pub fn read(
rules: &config::Sizing,
history: &History,
cap_of: impl Fn(&str) -> Option<u64>,
) -> Predictor {
let mut predictor = Predictor::new(rules);
predictor.read_until(history, u64::MAX, cap_of);
predictor
}
fn read_until(&mut self, history: &History, until: u64, cap_of: impl Fn(&str) -> Option<u64>) {
for (run, ending) in recent::rows(history) {
let cap = run
.memory_cap
.or_else(|| cap_of(&run.profile))
.unwrap_or(u64::MAX);
let at = recent::finished(run);
if at >= until {
break;
}
match ending {
Ending::Finished => self.learn(run, &run.profile, cap, at),
Ending::Cancelled => self.mark(run, &run.profile, cap, at),
}
}
}
pub fn learn(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
self.recent.read(run, profile, Ending::Finished, cap, at);
self.learn_cpu(run, profile);
}
pub fn learn_cpu(&mut self, run: &Ran, profile: &str) {
let Some(average) = run.cpu_average else {
return;
};
self.cpu_profiles
.entry(profile.to_owned())
.or_default()
.add(average, run.succeeded);
self.cpu_jobs
.entry(InProfile::new(&Key::of(run), profile))
.or_default()
.add(average, run.succeeded);
}
pub fn predict_cpu(&self, key: &Key, profile: &str, cap: u64) -> CpuPrediction {
let job = self.cpu_jobs.get(&InProfile::new(key, profile));
let min_jobs = u64::from(self.min_jobs);
let peers = self
.cpu_profiles
.get(profile)
.filter(|peers| peers.runs() >= min_jobs);
let (cpu, basis) = match (job.filter(|job| job.runs() > 0), peers) {
(Some(job), _) if job.runs() >= min_jobs => (
job.p95(),
Basis::Job {
runs: job.runs(),
peak: JobPeak::P95,
},
),
(Some(job), Some(_)) if job.succeeded >= OWN_RUNS => (
job.max(),
Basis::Job {
runs: job.runs(),
peak: JobPeak::Largest,
},
),
(Some(job), Some(peers)) => (
job.max().max(peers.p95()),
Basis::Profile { runs: peers.runs() },
),
(None, Some(peers)) => (peers.max(), Basis::ProfileMax { runs: peers.runs() }),
_ => (cap, Basis::Cap),
};
CpuPrediction {
cpu: cpu
.div_ceil(CPU_GRANULE)
.saturating_mul(CPU_GRANULE)
.clamp(CPU_GRANULE, cap.max(CPU_GRANULE)),
basis,
}
}
pub fn usual(&self, key: &Key, profile: &str) -> Option<Duration> {
self.recent.job(key, profile)?.usual()
}
pub fn longest_usual(
&self,
keys: impl IntoIterator<Item = Key>,
profile: &str,
) -> Option<Duration> {
let usual: Option<Vec<Duration>> = keys
.into_iter()
.map(|key| self.usual(&key, profile))
.collect();
usual?.into_iter().max()
}
pub fn mark(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
self.recent.read(run, profile, Ending::Cancelled, cap, at);
}
pub fn predict(
&self,
key: &Key,
profile: &str,
cap: u64,
now: u64,
copies: Copies,
) -> Prediction {
let job = self.recent.job(key, profile);
if let Some(hold) = job.and_then(|job| job.held(now, Some(UNPREDICTABLE_FOR))) {
return Prediction {
memory: cap,
basis: Basis::Unpredictable {
until: hold.at.saturating_add(UNPREDICTABLE_FOR) / 1000,
},
};
}
let min_jobs = u64::from(self.min_jobs);
let peers = self.recent.profile(profile);
let peers_runs = peers.len() as u64;
let overran = job.and_then(|job| {
job.overruns(now, UNPREDICTABLE_FOR)
.fold(None, |most: Option<(u64, u64)>, overrun| {
let until = overrun.at.saturating_add(UNPREDICTABLE_FOR);
Some(most.map_or((overrun.peak, until), |(peak, last)| {
(peak.max(overrun.peak), last.max(until))
}))
})
});
let (memory, basis) = match (job, peers_runs >= min_jobs) {
(Some(job), _) if job.runs() == 0 => (cap, Basis::Cap),
(Some(job), _) if let Some((peak, until)) = overran => (
self.with_margin(job.max().max(peak)),
Basis::Overran {
until: until / 1000,
},
),
(Some(job), _) if job.runs() >= min_jobs => (
self.with_margin(spread(job.peaks().to_vec()).p95),
Basis::Job {
runs: job.runs(),
peak: JobPeak::P95,
},
),
(Some(job), true) if job.succeeded() >= OWN_RUNS && copies == Copies::Alone => (
self.with_margin(job.max()),
Basis::Job {
runs: job.runs(),
peak: JobPeak::Largest,
},
),
(Some(job), true) => (
self.with_margin(job.max().max(spread(peers.to_vec()).p95)),
Basis::Profile { runs: peers_runs },
),
(None, true) => (
self.with_margin(peers.last().copied().unwrap_or(0)),
Basis::ProfileMax { runs: peers_runs },
),
_ => (cap, Basis::Cap),
};
Prediction {
memory: memory.min(cap),
basis,
}
}
fn with_margin(&self, peak: u64) -> u64 {
let memory = peak.saturating_add(peak.saturating_mul(u64::from(self.margin)) / 100);
memory
.div_ceil(GRANULE)
.saturating_mul(GRANULE)
.max(GRANULE)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Policy {
Caps,
Measured,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Barriers {
On,
Strict,
Off,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Arrivals {
AsQueued,
AfterNeeds,
}
#[derive(Debug, Clone, Copy)]
pub struct Replaying<'known> {
pub barriers: Barriers,
pub arrivals: Arrivals,
pub known: Option<&'known History>,
pub trace: Option<&'known Trace>,
pub most_credit: u64,
pub host_reserve: HostReserve,
pub credit_room: CreditRoom,
pub band: Band,
pub growth: Option<GrowthCount>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct GrowthCount {
pub growth: pooled::Growth,
pub brake: Brake,
pub guard: GuardHold,
}
impl GrowthCount {
pub const DAEMON: GrowthCount = GrowthCount {
growth: pooled::GROWTH,
brake: Brake::On,
guard: GuardHold::On,
};
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Brake {
On,
Off,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum GuardHold {
On,
Off,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HostReserve {
Plain,
Top2,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Band {
NoWaiterFits,
AnyWaiter,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CreditRoom {
Counted,
LeftOut,
}
impl From<Barriers> for Replaying<'_> {
fn from(barriers: Barriers) -> Self {
Replaying {
barriers,
arrivals: Arrivals::AsQueued,
known: None,
trace: None,
most_credit: 0,
host_reserve: HostReserve::Top2,
credit_room: CreditRoom::Counted,
band: Band::NoWaiterFits,
growth: None,
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct PoolReplay {
pub waits: Vec<u64>,
pub never_started: u64,
}
impl PoolReplay {
pub fn wait(&self) -> Spread {
spread(self.waits.clone())
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RunReplay {
pub took: u64,
pub profiles: BTreeSet<String>,
}
type RunKey = (String, u64, u32);
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Backfilled {
pub jobs: u64,
pub overran: u64,
pub most_overrun: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Replay {
pub jobs: u64,
pub never_started: u64,
pub wait: Spread,
pub mean_wait: u64,
pub most_running: u64,
pub worst_overlap: u64,
pub makespan: u64,
pub under_predicted: u64,
pub held_back: u64,
pub cpu_held: u64,
pub worst_cpu: u64,
pub pools: BTreeMap<Pool, PoolReplay>,
pub charged: u128,
pub capacity: u128,
pub barrier_for: u64,
pub withheld: u128,
pub runs: Vec<RunReplay>,
pub backfilled: Backfilled,
pub slice_waited: u64,
pub host_waited: u64,
pub hazard: Hazard,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Recorded {
pub pools: BTreeMap<Pool, PoolReplay>,
pub runs: Vec<RunReplay>,
pub host_waited: u64,
}
impl Recorded {
pub fn waited(&self) -> u64 {
self.pools.values().flat_map(|pool| &pool.waits).sum()
}
}
#[cfg(test)]
mod tests;