runnerd_core/scheduler/priority.rs
1//! Which one pool goes first once memory or CPU keeps running out before its next job's runner fits (ADR 0096): how
2//! long each pool's next job waited, whether a barrier has served the pool (ADR 0098), what an empty slice would hold,
3//! the rule that picks a plan's one barrier, and which younger jobs may start behind it all the same (`Backfill`, ADR
4//! 0097). `plan` and `admission::simulate` both decide by it, so a replay shows what the daemon does. It does no I/O
5//! and reads no clock; the engine keeps the waits, and it never stops or clamps what already runs.
6
7use std::time::{Duration, SystemTime};
8
9use super::{Left, signed};
10use crate::api::Waiting;
11
12/// Once a pool's next job has waited this long for memory or CPU, no younger job starts until its runner fits: smaller
13/// jobs would otherwise take everything that frees up, and the room a large one needs would never gather. Long enough
14/// that a passing shortage puts up no barrier, whose cost is what stands idle behind it (ADR 0098).
15pub const PRIORITY_AFTER: Duration = Duration::from_secs(600);
16
17/// `PRIORITY_AFTER` for a pool a barrier has served, until its queue empties: its wait restarts with each job, so with
18/// the first limit a pool of many large jobs could run them only one at a time (ADR 0098).
19pub const SERVED_PRIORITY_AFTER: Duration = Duration::from_secs(120);
20
21/// What a job's runner lacks that a running job gives back.
22#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
23pub enum Scarce {
24 /// The slice's memory budget, or what the host's memory leaves it.
25 Memory,
26 /// The CPU budget.
27 Cpu,
28}
29
30/// Since when a job has waited for something scarce.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct Wait {
33 /// The job's ID: a wait counts for this job alone, so it cannot outlive it.
34 pub job: u64,
35 /// When a scheduling plan first held it.
36 pub since: SystemTime,
37}
38
39/// What a pool's next job has waited for, and whether a barrier has served the pool. Each clock runs from the first plan
40/// that held the job for it and goes on through a plan that holds it for the other, or for a slot.
41#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
42pub struct Waits {
43 /// Its wait for memory.
44 pub memory: Option<Wait>,
45 /// Its wait for CPU.
46 pub cpu: Option<Wait>,
47 /// The waiting job, if a plan's barrier was ever its own. Not only the last plan's: the plan that starts it has no
48 /// barrier, as it fits, and a start refused, or that failed preparing its caches, plans again. A failure that brings
49 /// a backoff clears this with the waits.
50 pub owner: Option<u64>,
51 /// Whether a runner of the pool started for a job that owned a barrier, since its queue last emptied: its next jobs
52 /// wait `SERVED_PRIORITY_AFTER`.
53 pub served: bool,
54}
55
56impl Waits {
57 /// Whether nothing is kept for the pool.
58 pub fn is_empty(&self) -> bool {
59 *self == Waits::default()
60 }
61
62 /// Starts the clock of `scarce` for `job`, unless one runs; whether it started.
63 pub fn note(&mut self, scarce: Scarce, job: u64, now: SystemTime) -> bool {
64 let wait = match scarce {
65 Scarce::Memory => &mut self.memory,
66 Scarce::Cpu => &mut self.cpu,
67 };
68 let started = wait.is_none();
69 wait.get_or_insert(Wait { job, since: now });
70 started
71 }
72
73 /// Drops what is kept for the jobs `queued` says are gone. The mark stays: a job taken elsewhere says nothing of the
74 /// jobs behind it.
75 pub fn retain(&mut self, queued: impl Fn(u64) -> bool) {
76 for wait in [&mut self.memory, &mut self.cpu] {
77 if wait.is_some_and(|wait| !queued(wait.job)) {
78 *wait = None;
79 }
80 }
81 self.owner = self.owner.filter(|job| queued(*job));
82 }
83
84 /// Notes that the plan's barrier is `job`'s, if this pool waits for it.
85 pub fn own(&mut self, job: u64) {
86 let waits = [self.memory, self.cpu];
87 if waits.iter().flatten().any(|wait| wait.job == job) {
88 self.owner = Some(job);
89 }
90 }
91
92 /// A runner of the pool is in its slot: its waits end, and if it came to a job that owned a barrier, the barrier has
93 /// served the pool. A proposed start, a deferred one or one that failed comes to nothing, so it does not count.
94 pub fn started(&mut self) {
95 self.served |= self.owner.is_some();
96 *self = Waits {
97 served: self.served,
98 ..Waits::default()
99 };
100 }
101
102 /// A listing that succeeded shows none of the pool's jobs queued: the next job to wait is a new contention.
103 pub fn emptied(&mut self) {
104 self.served = false;
105 }
106
107 /// How long a job of the pool waits before it may own a barrier.
108 fn limit(&self) -> Duration {
109 if self.served {
110 SERVED_PRIORITY_AFTER
111 } else {
112 PRIORITY_AFTER
113 }
114 }
115
116 /// When each wait reaches its limit, for a replay to look again then.
117 pub fn deadlines(&self) -> impl Iterator<Item = SystemTime> {
118 let limit = self.limit();
119 [self.memory, self.cpu]
120 .into_iter()
121 .flatten()
122 .map(move |wait| wait.since + limit)
123 }
124
125 /// When `job` first had waited long enough for either, if it has by `now`: a job that waited for CPU and now lacks
126 /// memory, or the other way round, keeps what it waited.
127 fn matured(&self, job: u64, now: SystemTime) -> Option<SystemTime> {
128 let limit = self.limit();
129 [self.memory, self.cpu]
130 .into_iter()
131 .flatten()
132 .filter(|wait| wait.job == job)
133 .map(|wait| wait.since + limit)
134 .filter(|reached| *reached <= now)
135 .min()
136 }
137}
138
139/// What the budgets would leave once every runner ended, the mirror, seed containers and shells still there; `None`,
140/// no such bound known. A job holds younger ones only for room that draining can give it.
141#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
142pub struct Drained {
143 /// The slice's memory.
144 pub memory: Option<i64>,
145 /// The CPU budget, in millicores.
146 pub cpu: Option<i64>,
147 /// What the host's memory leaves the slice for a job the host holds: by the larger margin while a runner runs,
148 /// whichever margin is in force (ADR 0102).
149 pub host: Option<i64>,
150 /// What it leaves for a job something else holds, by the plain margin: such a job's wait does not follow the margin,
151 /// so its barrier need not keep off it.
152 pub host_plain: Option<i64>,
153}
154
155impl Drained {
156 /// Whether a runner of `memory` and `cpu`, of a job `held` so, fits, every known bound counted.
157 fn holds(self, memory: u64, cpu: u64, held: Held) -> bool {
158 let fits = |room: Option<i64>, needs: u64| {
159 room.is_none_or(|room| room >= i64::try_from(needs).unwrap_or(i64::MAX))
160 };
161 let host = match held {
162 Held::ByHost => self.host,
163 Held::ByBudget => self.host_plain,
164 };
165 fits(self.memory, memory) && fits(host, memory) && fits(self.cpu, cpu)
166 }
167}
168
169/// What holds a job back, which says by which margin a drain serves it.
170#[derive(Debug, Clone, Copy, PartialEq, Eq)]
171pub enum Held {
172 /// What the host's memory leaves the slice.
173 ByHost,
174 /// The slice's memory budget, its high-water mark or the CPU budget.
175 ByBudget,
176}
177
178/// A job a plan held for something scarce, with a free slot for its runner.
179#[derive(Debug, Clone, Copy, PartialEq, Eq)]
180pub struct Short {
181 /// Its ID.
182 pub job: u64,
183 /// What it lacks first: memory before CPU, as `Waiting` says it.
184 pub scarce: Scarce,
185 /// Whether the host holds it.
186 pub held: Held,
187 /// What its runner takes of the memory budget.
188 pub memory: u64,
189 /// What its runner takes of the CPU budget, in millicores.
190 pub cpu: u64,
191}
192
193/// The one job a plan lets no younger job start before, whichever of memory and CPU it lacks: it drains towards both.
194#[derive(Debug, Clone, Copy, PartialEq, Eq)]
195pub struct Barrier {
196 /// The job's ID.
197 pub job: u64,
198 /// What it lacks now.
199 pub scarce: Scarce,
200 /// What its runner takes of the memory budget.
201 pub memory: u64,
202 /// What its runner takes of the CPU budget, in millicores.
203 pub cpu: u64,
204 /// When its wait reached its limit: from then on, what starts counts against the room it is owed.
205 pub since: SystemTime,
206}
207
208impl Barrier {
209 /// The barrier `short`, whose pool `waits`, puts up: the first of a plan's jobs that waited long enough and that
210 /// `drained` has room for. `None` from a demand draining could not serve, as a runner past the budget or a host
211 /// short because of programs outside the slice: younger jobs that fit go on. `drained` is `None` while a safety
212 /// interlock starts nothing, whose zeros say nothing of the room there is: the wait keeps its age meanwhile.
213 pub fn of(
214 short: Short,
215 waits: &Waits,
216 drained: Option<Drained>,
217 now: SystemTime,
218 ) -> Option<Barrier> {
219 let drained = drained?;
220 let since = waits.matured(short.job, now)?;
221 let holds = drained.holds(short.memory, short.cpu, short.held);
222 holds.then_some(Barrier {
223 job: short.job,
224 scarce: short.scarce,
225 memory: short.memory,
226 cpu: short.cpu,
227 since,
228 })
229 }
230
231 /// Why a younger job waits behind it.
232 pub fn reason(self) -> Waiting {
233 match self.scarce {
234 Scarce::Memory => Waiting::BehindMemory { job: self.job },
235 Scarce::Cpu => Waiting::BehindCpu { job: self.job },
236 }
237 }
238}
239
240/// What a runner may take at most: its profile's caps.
241#[derive(Debug, Clone, Copy, PartialEq, Eq)]
242pub(crate) struct Caps {
243 /// Memory.
244 pub(crate) memory: u64,
245 /// CPU, in millicores.
246 pub(crate) cpu: u64,
247}
248
249/// A runner as a backfill reads it, one in a slot or one the plan already started.
250#[derive(Debug, Clone, Copy)]
251pub(crate) struct Runner<'plan> {
252 /// Its profile.
253 pub(crate) profile: &'plan str,
254 /// When it started.
255 pub(crate) started_at: SystemTime,
256 /// How long its job usually keeps it; `None`, it ends now as far as a backfill knows: it runs no job yet, or one
257 /// with no estimate. That only makes the room come sooner, and less starts behind the barrier.
258 pub(crate) usual: Option<Duration>,
259 /// What it takes of the memory budget now.
260 pub(crate) memory: u64,
261 /// What it takes of the CPU budget now, in millicores.
262 pub(crate) cpu: u64,
263 /// What it could take.
264 pub(crate) caps: Caps,
265}
266
267impl Runner<'_> {
268 /// How long from `now` it usually ends: at once if that time has passed, or if it started in the future, as after
269 /// a clock went back: the room coming sooner is the side that starts less behind a barrier.
270 fn left_to_run(&self, now: SystemTime) -> Duration {
271 let Ok(ran) = now.duration_since(self.started_at) else {
272 return Duration::ZERO;
273 };
274 self.usual
275 .map_or(Duration::ZERO, |usual| usual.saturating_sub(ran))
276 }
277}
278
279/// A job older than a barrier's owner that the plan left waiting. It goes before the owner, so room it loses to a
280/// younger job comes back to the owner late.
281#[derive(Debug, Clone, Copy)]
282pub(crate) struct Older<'plan> {
283 /// Its pool's profile.
284 pub(crate) profile: &'plan str,
285 /// Whether that profile has a free slot, or will have one with no runner ending, as when it is preparing.
286 pub(crate) free_slot: bool,
287 /// What its runner takes of the memory budget.
288 pub(crate) memory: u64,
289 /// What its runner takes of the CPU budget, in millicores.
290 pub(crate) cpu: u64,
291}
292
293/// What a plan knows when a barrier goes up.
294#[derive(Debug, Clone, Copy)]
295pub(crate) struct Around<'plan> {
296 /// The budgets left.
297 pub(crate) left: Left,
298 /// How much more memory the pooled count could leave with no runner ending (`Budget::credit_room`).
299 pub(crate) credit_room: u64,
300 /// What a drain leaves.
301 pub(crate) drained: Drained,
302 /// The runners in slots, and those the plan started so far.
303 pub(crate) runners: &'plan [Runner<'plan>],
304 /// The jobs older than the owner it left waiting.
305 pub(crate) older: &'plan [Older<'plan>],
306}
307
308/// A younger job a plan would start, had it no barrier to wait behind.
309#[derive(Debug, Clone, Copy)]
310pub(crate) struct Candidate<'plan> {
311 /// Its pool's profile.
312 pub(crate) profile: &'plan str,
313 /// How many of that profile's slots are free.
314 pub(crate) free_slots: usize,
315 /// The largest usual run time of its pool's queued jobs, since GitHub may give the runner any of them; `None` if
316 /// any has no estimate (`admission::Predictor::longest_usual`).
317 pub(crate) usual: Option<Duration>,
318 /// Its profile's caps.
319 pub(crate) caps: Caps,
320}
321
322/// The room behind a barrier, as ADR 0097 bounds it. If each run takes what the plan read, everything started here has
323/// ended before the owner or any job older than it could start, so nothing they see changes and an owner that keeps the
324/// barrier starts no later than with no backfill. The plan reads p95s, so a run that ends early can bring the room while
325/// a job started here still runs, and that job can cost the owner what it has left. Whatever the run times do, what
326/// started since the barrier matured cannot take, even at its caps, what an empty slice has for the owner and the older
327/// jobs, nor the last free slot of its profile, so the owner fits once the older jobs and what ran before have ended.
328#[derive(Debug, Clone, Copy)]
329pub(crate) struct Backfill<'plan> {
330 /// The owner's profile.
331 profile: &'plan str,
332 /// How long from now until the running runners' usual ends let the owner or an older job start.
333 until: Duration,
334 /// What a drain leaves past the owner and the caps of what started since its barrier matured.
335 spare: Left,
336}
337
338/// The runners by how long each usually has left, soonest first.
339struct Ending<'plan>(Vec<(Duration, Runner<'plan>)>);
340
341impl Ending<'_> {
342 /// How long until their ends let a runner of `memory` and `cpu` fit `left`; `None` if none does.
343 fn room_in(&self, left: Left, memory: u64, cpu: u64) -> Option<Duration> {
344 if left.fits(memory, cpu) {
345 return Some(Duration::ZERO);
346 }
347 let mut room = left;
348 self.0.iter().find_map(|(left_to_run, runner)| {
349 room.give(runner.memory, runner.cpu);
350 room.fits(memory, cpu).then_some(*left_to_run)
351 })
352 }
353
354 /// How long until `older` could start, the budgets being `left`; `None` if no end lets it. Older jobs beside it may
355 /// well take that room first, so it may start later, never sooner.
356 fn start_of(&self, older: &Older<'_>, left: Left) -> Option<Duration> {
357 let room = self.room_in(left, older.memory, older.cpu)?;
358 let in_profile = |(_, runner): &&(Duration, Runner<'_>)| runner.profile == older.profile;
359 let slot = if older.free_slot {
360 Duration::ZERO
361 } else {
362 self.0.iter().find(in_profile)?.0
363 };
364 Some(room.max(slot))
365 }
366}
367
368impl<'plan> Backfill<'plan> {
369 /// What the `barrier` of a job of `profile` leaves room for, as things stand `around` it. `None` where nothing may
370 /// start behind it: the owner's room comes now, or no end of a running runner brings it, as when something other
371 /// than runners holds it.
372 pub(crate) fn behind(
373 barrier: Barrier,
374 profile: &'plan str,
375 around: Around<'_>,
376 now: SystemTime,
377 ) -> Option<Backfill<'plan>> {
378 let Around {
379 left,
380 credit_room,
381 drained,
382 runners,
383 older,
384 } = around;
385 // The room may come sooner than ends bring it: a credit can grow at any moment, and an end gives back at most
386 // what its runner counts. So the time found is the earliest the owner could start. The host's limit reads the
387 // plain count, which no credit moves.
388 let mut left = left;
389 left.memory = left
390 .memory
391 .map(|memory| memory.saturating_add(signed(credit_room)));
392 let mut ending: Vec<(Duration, Runner<'_>)> = runners
393 .iter()
394 .map(|runner| (runner.left_to_run(now), *runner))
395 .collect();
396 ending.sort_by_key(|(left_to_run, _)| *left_to_run);
397 let ending = Ending(ending);
398 let owner = ending.room_in(left, barrier.memory, barrier.cpu)?;
399 let starts = older.iter().filter_map(|job| ending.start_of(job, left));
400 let until = starts.fold(owner, Duration::min);
401 if until.is_zero() {
402 return None;
403 }
404 let mut spare = Left {
405 memory: drained.memory,
406 cpu: drained.cpu,
407 host: drained.host,
408 };
409 // An older job that matures takes the barrier, so its room is kept as the owner's is. One no drain serves never
410 // will, and must not stop everything behind the barrier.
411 let served = older.iter().filter(|job| spare.fits(job.memory, job.cpu));
412 let memory = served.clone().map(|job| job.memory).max().unwrap_or(0);
413 let cpu = served.map(|job| job.cpu).max().unwrap_or(0);
414 spare.take(barrier.memory.max(memory), barrier.cpu.max(cpu));
415 for runner in runners
416 .iter()
417 .filter(|runner| runner.started_at >= barrier.since)
418 {
419 spare.take(runner.caps.memory, runner.caps.cpu);
420 }
421 Some(Backfill {
422 profile,
423 until,
424 spare,
425 })
426 }
427
428 /// Whether `candidate`, which fits the budgets left and has a free slot, may start behind the barrier; if so, counts
429 /// its caps. It need not move the time found: a runner that usually ends by then gives back what it took.
430 pub(crate) fn admits(&mut self, candidate: Candidate<'_>) -> bool {
431 let caps = candidate.caps;
432 let admitted = candidate.usual.is_some_and(|usual| usual <= self.until)
433 && self.spare.fits(caps.memory, caps.cpu)
434 && (candidate.profile != self.profile || candidate.free_slots > 1);
435 if admitted {
436 self.spare.take(caps.memory, caps.cpu);
437 }
438 admitted
439 }
440}