use std::collections::{HashMap, HashSet};
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
use std::time::Duration;
use tokio::time::Instant;
use tokio_util::sync::CancellationToken;
use crate::durable::stream::DurableStream;
#[derive(Clone, Debug, PartialEq, Eq)]
#[must_use = "an eviction policy changes nothing until a task is declared with it"]
pub struct EvictionPolicy {
ttl: Duration,
allow_capacity_eviction: bool,
priority: i32,
}
impl EvictionPolicy {
pub fn ttl(ttl: Duration) -> Self {
Self {
ttl,
..Self::default()
}
}
pub fn allow_capacity_eviction(mut self, yes: bool) -> Self {
self.allow_capacity_eviction = yes;
self
}
pub fn priority(mut self, priority: i32) -> Self {
self.priority = priority;
self
}
pub(crate) fn has_ttl(&self) -> bool {
self.ttl > Duration::ZERO
}
}
impl Default for EvictionPolicy {
fn default() -> Self {
Self {
ttl: Duration::from_secs(15 * 60),
allow_capacity_eviction: true,
priority: 0,
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Config {
pub(crate) interval: Duration,
pub(crate) reserve_slots: usize,
pub(crate) min_wait_for_capacity: Duration,
}
pub(crate) const CONFIG: Config = Config {
interval: Duration::from_secs(1),
reserve_slots: 0,
min_wait_for_capacity: Duration::from_secs(10),
};
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Candidate {
pub(crate) task_id: String,
pub(crate) invocation_count: i32,
pub(crate) reason: String,
}
struct Record {
invocation_count: i32,
policy: Option<EvictionPolicy>,
waiting_since: Option<Instant>,
waits: usize,
wait: (&'static str, String),
evicting: bool,
}
#[derive(Default)]
pub(crate) struct EvictionBook {
runs: Mutex<HashMap<String, Record>>,
}
impl EvictionBook {
fn lock(&self) -> MutexGuard<'_, HashMap<String, Record>> {
self.runs.lock().unwrap_or_else(PoisonError::into_inner)
}
pub(crate) fn register(
&self,
task_id: &str,
invocation_count: i32,
policy: Option<EvictionPolicy>,
) {
self.lock().insert(
task_id.to_string(),
Record {
invocation_count,
policy,
waiting_since: None,
waits: 0,
wait: ("wait", String::new()),
evicting: false,
},
);
}
#[cfg(test)]
fn unregister(&self, task_id: &str) {
self.lock().remove(task_id);
}
pub(crate) fn take_on(
self: &Arc<Self>,
task_id: &str,
invocation_count: i32,
policy: Option<EvictionPolicy>,
) -> RunRegistration {
self.register(task_id, invocation_count, policy);
RunRegistration {
book: Arc::clone(self),
task_id: task_id.to_string(),
invocation_count,
}
}
pub(crate) fn unregister_matching(&self, task_id: &str, invocation_count: i32) {
let mut runs = self.lock();
if runs
.get(task_id)
.is_some_and(|record| record.invocation_count == invocation_count)
{
runs.remove(task_id);
}
}
pub(crate) fn mark_waiting(
self: &Arc<Self>,
task_id: &str,
kind: &'static str,
resource: &str,
) -> WaitingGuard {
self.mark_waiting_at(task_id, kind, resource, Instant::now())
}
pub(crate) fn mark_waiting_at(
self: &Arc<Self>,
task_id: &str,
kind: &'static str,
resource: &str,
at: Instant,
) -> WaitingGuard {
let mut invocation_count = 0;
if let Some(record) = self.lock().get_mut(task_id) {
invocation_count = record.invocation_count;
record.waits += 1;
if record.waits == 1 {
record.waiting_since = Some(at);
record.wait = (kind, resource.to_string());
}
}
WaitingGuard {
book: Arc::clone(self),
task_id: task_id.to_string(),
invocation_count,
}
}
fn left_wait(&self, task_id: &str, invocation_count: i32) {
if let Some(record) = self
.lock()
.get_mut(task_id)
.filter(|record| record.invocation_count == invocation_count)
{
record.waits = record.waits.saturating_sub(1);
if record.waits == 0 {
record.waiting_since = None;
}
}
}
pub(crate) fn begin_eviction(&self, task_id: &str) -> bool {
match self.lock().get_mut(task_id) {
Some(record) => {
record.evicting = true;
true
}
None => false,
}
}
pub(crate) fn abandon_eviction(&self, task_id: &str) {
if let Some(record) = self.lock().get_mut(task_id) {
record.evicting = false;
}
}
pub(crate) fn candidate(
&self,
now: Instant,
durable_slots: usize,
config: Config,
) -> Option<Candidate> {
let runs = self.lock();
let waiting = runs
.iter()
.filter(|(_, record)| record.waiting_since.is_some());
let mut eligible = Vec::new();
let mut waiting_count = 0_usize;
for (task_id, record) in waiting {
waiting_count += 1;
if record.evicting {
continue;
}
let Some(policy) = &record.policy else {
continue;
};
let waited = now.saturating_duration_since(
record.waiting_since.expect("filtered to the waiting runs"),
);
eligible.push((task_id.as_str(), record, policy, waited));
}
let by_ttl = eligible
.iter()
.copied()
.filter(|(_, _, policy, waited)| policy.has_ttl() && *waited >= policy.ttl);
if let Some((task_id, record, policy, _)) = pick(by_ttl) {
return Some(Candidate {
task_id: task_id.to_string(),
invocation_count: record.invocation_count,
reason: format!(
"wait TTL ({:?}) exceeded while waiting on {}",
policy.ttl,
waited_on(record)
),
});
}
if !under_pressure(durable_slots, config.reserve_slots, waiting_count) {
return None;
}
let by_capacity = eligible.iter().copied().filter(|(_, _, policy, waited)| {
policy.allow_capacity_eviction && *waited >= config.min_wait_for_capacity
});
let (task_id, record, _, _) = pick(by_capacity)?;
Some(Candidate {
task_id: task_id.to_string(),
invocation_count: record.invocation_count,
reason: format!("worker at capacity while waiting on {}", waited_on(record)),
})
}
}
fn waited_on(record: &Record) -> String {
let (kind, resource) = &record.wait;
format!("{kind}({resource})")
}
fn pick<'a>(
candidates: impl Iterator<Item = (&'a str, &'a Record, &'a EvictionPolicy, Duration)>,
) -> Option<(&'a str, &'a Record, &'a EvictionPolicy, Duration)> {
candidates.min_by(|left, right| {
let (_, _, left_policy, left_waited) = left;
let (_, _, right_policy, right_waited) = right;
left_policy
.priority
.cmp(&right_policy.priority)
.then(right_waited.cmp(left_waited))
})
}
fn under_pressure(durable_slots: usize, reserve_slots: usize, waiting: usize) -> bool {
let available = durable_slots.saturating_sub(reserve_slots);
durable_slots > 0 && available > 0 && waiting >= available
}
pub(crate) struct WaitingGuard {
book: Arc<EvictionBook>,
task_id: String,
invocation_count: i32,
}
impl Drop for WaitingGuard {
fn drop(&mut self) {
self.book.left_wait(&self.task_id, self.invocation_count);
}
}
pub(crate) struct RunRegistration {
book: Arc<EvictionBook>,
task_id: String,
invocation_count: i32,
}
impl Drop for RunRegistration {
fn drop(&mut self) {
self.book
.unregister_matching(&self.task_id, self.invocation_count);
}
}
pub(crate) async fn run(
book: Arc<EvictionBook>,
stream: DurableStream,
cancel: impl Fn(&str) + Send + 'static,
durable_slots: usize,
config: Config,
stop: CancellationToken,
) {
let mut ticker = tokio::time::interval(config.interval);
ticker.set_missed_tick_behavior(tokio::time::MissedTickBehavior::Delay);
loop {
tokio::select! {
() = stop.cancelled() => return,
_ = ticker.tick() => {}
}
let mut tried: HashSet<String> = HashSet::new();
while let Some(candidate) = book.candidate(Instant::now(), durable_slots, config) {
if !tried.insert(candidate.task_id.clone()) {
break;
}
if !book.begin_eviction(&candidate.task_id) {
continue;
}
tracing::info!(
task_run_external_id = %candidate.task_id,
invocation_count = candidate.invocation_count,
reason = %candidate.reason,
"handing a waiting durable run back to the engine",
);
match stream
.send_evict(
&candidate.task_id,
candidate.invocation_count,
Some(candidate.reason.clone()),
)
.await
{
Ok(()) => {
book.unregister_matching(&candidate.task_id, candidate.invocation_count);
cancel(&candidate.task_id);
}
Err(error) => {
book.abandon_eviction(&candidate.task_id);
tracing::warn!(
task_run_external_id = %candidate.task_id,
invocation_count = candidate.invocation_count,
%error,
"the engine did not acknowledge an eviction; leaving the run alone",
);
break;
}
}
}
}
}
pub(crate) const EVICTION_FEATURE: &str = "durable eviction";
pub(crate) fn supported(engine_version: &str) -> bool {
!matches!(
crate::version::ensure_feature(
EVICTION_FEATURE,
crate::version::EVICTION_MIN_ENGINE_VERSION,
engine_version,
),
Err(crate::Error::UnsupportedFeature { .. })
)
}
#[cfg(test)]
mod tests {
use super::*;
fn at(base: Instant, secs: u64) -> Instant {
base + Duration::from_secs(secs)
}
struct Held {
book: Arc<EvictionBook>,
_waits: Vec<WaitingGuard>,
}
impl std::ops::Deref for Held {
type Target = Arc<EvictionBook>;
fn deref(&self) -> &Arc<EvictionBook> {
&self.book
}
}
fn book(base: Instant, runs: &[(&str, EvictionPolicy, Option<u64>)]) -> Held {
let book = Arc::new(EvictionBook::default());
let mut waits = Vec::new();
for (id, policy, waiting_since) in runs {
book.register(id, 1, Some(policy.clone()));
if let Some(offset) = waiting_since {
waits.push(book.mark_waiting_at(id, "user_event", "approve", at(base, *offset)));
}
}
Held {
book,
_waits: waits,
}
}
#[test]
fn nothing_is_evicted_while_nothing_is_waiting() {
let base = Instant::now();
let book = book(
base,
&[("run-1", EvictionPolicy::ttl(Duration::from_secs(1)), None)],
);
assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
}
#[test]
fn a_wait_past_its_ttl_is_evicted_and_the_reason_says_what_it_was_waiting_on() {
let base = Instant::now();
let book = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(30)),
Some(0),
)],
);
assert!(
book.candidate(at(base, 29), 1000, CONFIG).is_none(),
"a second short of the TTL is not yet due",
);
let chosen = book
.candidate(at(base, 30), 1000, CONFIG)
.expect("past the TTL");
assert_eq!(chosen.task_id, "run-1");
assert_eq!(chosen.invocation_count, 1);
assert!(chosen.reason.contains("TTL"), "{}", chosen.reason);
assert!(chosen.reason.contains("user_event"), "{}", chosen.reason);
assert!(chosen.reason.contains("approve"), "{}", chosen.reason);
}
#[test]
fn the_clock_starts_at_the_wait_and_not_at_the_registration() {
let base = Instant::now();
let book = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(30)),
Some(3600),
)],
);
assert!(book.candidate(at(base, 3629), 1000, CONFIG).is_none());
assert!(book.candidate(at(base, 3630), 1000, CONFIG).is_some());
}
#[test]
fn a_zero_ttl_is_never_evicted_on_time() {
let base = Instant::now();
let book = book(
base,
&[("run-1", EvictionPolicy::ttl(Duration::ZERO), Some(0))],
);
assert!(book.candidate(at(base, 86_400), 1000, CONFIG).is_none());
}
#[test]
fn capacity_pressure_needs_every_slot_waiting_and_a_wait_past_the_floor() {
let base = Instant::now();
let long = EvictionPolicy::ttl(Duration::from_secs(3600));
let book = book(
base,
&[("run-1", long.clone(), Some(0)), ("run-2", long, Some(5))],
);
assert!(
book.candidate(at(base, 60), 3, CONFIG).is_none(),
"three slots and two waiting is not pressure",
);
let chosen = book
.candidate(at(base, 11), 2, CONFIG)
.expect("two slots, two waiting");
assert_eq!(
chosen.task_id, "run-1",
"the only one past the ten-second floor",
);
assert!(chosen.reason.contains("capacity"), "{}", chosen.reason);
assert!(
book.candidate(at(base, 9), 2, CONFIG).is_none(),
"neither has waited the floor out yet",
);
}
#[test]
fn a_run_that_forbids_capacity_eviction_is_never_chosen_for_it() {
let base = Instant::now();
let forbidden = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(3600)).allow_capacity_eviction(false),
Some(0),
)],
);
assert!(forbidden.candidate(at(base, 600), 1, CONFIG).is_none());
let allowed = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(3600)),
Some(0),
)],
);
assert_eq!(
allowed
.candidate(at(base, 600), 1, CONFIG)
.expect("allowed, and long past the floor")
.task_id,
"run-1",
);
}
#[test]
fn a_run_that_forbids_capacity_eviction_still_answers_to_its_ttl() {
let base = Instant::now();
let book = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(30)).allow_capacity_eviction(false),
Some(0),
)],
);
let chosen = book.candidate(at(base, 30), 1000, CONFIG).expect("due");
assert!(chosen.reason.contains("TTL"), "{}", chosen.reason);
}
#[test]
fn the_lowest_priority_goes_first_and_ties_break_on_the_longest_wait() {
let base = Instant::now();
let ttl = Duration::from_secs(10);
let book = book(
base,
&[
("high", EvictionPolicy::ttl(ttl).priority(5), Some(0)),
("low", EvictionPolicy::ttl(ttl).priority(1), Some(5)),
("low-older", EvictionPolicy::ttl(ttl).priority(1), Some(2)),
],
);
let chosen = book
.candidate(at(base, 60), 1000, CONFIG)
.expect("all three are past the TTL");
assert_eq!(chosen.task_id, "low-older");
}
#[test]
fn nested_waits_count_once_and_date_from_the_outer_one() {
let base = Instant::now();
let book = Arc::new(EvictionBook::default());
book.register(
"run-1",
1,
Some(EvictionPolicy::ttl(Duration::from_secs(10))),
);
let outer = book.mark_waiting_at("run-1", "spawn_child", "child", at(base, 0));
let inner = book.mark_waiting_at("run-1", "sleep", "sleep:5000ms", at(base, 5));
drop(inner);
let chosen = book
.candidate(at(base, 10), 1000, CONFIG)
.expect("ten seconds since the outer wait began");
assert_eq!(chosen.task_id, "run-1");
assert!(
chosen.reason.contains("spawn_child"),
"the outer wait is the one named: {}",
chosen.reason,
);
drop(outer);
assert!(
book.candidate(at(base, 600), 1000, CONFIG).is_none(),
"no longer waiting",
);
}
#[test]
fn a_run_that_goes_back_to_work_starts_its_clock_over() {
let base = Instant::now();
let book = Arc::new(EvictionBook::default());
book.register(
"run-1",
1,
Some(EvictionPolicy::ttl(Duration::from_secs(10))),
);
drop(book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0)));
let second = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 100));
assert!(
book.candidate(at(base, 109), 1000, CONFIG).is_none(),
"nine seconds into the second wait, not a hundred and nine",
);
assert!(book.candidate(at(base, 110), 1000, CONFIG).is_some());
drop(second);
}
#[test]
fn a_run_with_no_policy_is_never_a_candidate() {
let base = Instant::now();
let book = Arc::new(EvictionBook::default());
book.register("run-1", 1, None);
let _waiting = book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0));
assert!(book.candidate(at(base, 86_400), 1, CONFIG).is_none());
}
#[test]
fn a_run_with_no_policy_still_counts_towards_capacity_pressure() {
let base = Instant::now();
let book = Arc::new(EvictionBook::default());
book.register("no-policy", 1, None);
book.register(
"policy",
1,
Some(EvictionPolicy::ttl(Duration::from_secs(3600))),
);
let _one = book.mark_waiting_at("no-policy", "user_event", "approve", at(base, 0));
let _two = book.mark_waiting_at("policy", "user_event", "approve", at(base, 0));
assert!(
book.candidate(at(base, 60), 3, CONFIG).is_none(),
"three slots, two waiting",
);
assert_eq!(
book.candidate(at(base, 60), 2, CONFIG)
.expect("two slots, two waiting")
.task_id,
"policy",
"the one without a policy is counted but never chosen",
);
}
#[test]
fn a_run_already_being_handed_back_is_not_chosen_twice() {
let base = Instant::now();
let book = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(10)),
Some(0),
)],
);
assert!(book.candidate(at(base, 60), 1000, CONFIG).is_some());
assert!(book.begin_eviction("run-1"));
assert!(book.candidate(at(base, 60), 1000, CONFIG).is_none());
book.abandon_eviction("run-1");
assert!(book.candidate(at(base, 60), 1000, CONFIG).is_some());
assert!(
!book.begin_eviction("gone"),
"a run that is no longer on the books cannot be handed back",
);
}
#[test]
fn a_late_guard_from_an_evicted_attempt_leaves_the_next_one_alone() {
let base = Instant::now();
let book = Arc::new(EvictionBook::default());
book.register(
"run-1",
1,
Some(EvictionPolicy::ttl(Duration::from_secs(10))),
);
let stale = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 0));
book.unregister("run-1");
book.register(
"run-1",
2,
Some(EvictionPolicy::ttl(Duration::from_secs(10))),
);
let fresh = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 100));
drop(stale);
let chosen = book
.candidate(at(base, 110), 1000, CONFIG)
.expect("the second attempt is still waiting");
assert_eq!(chosen.invocation_count, 2);
drop(fresh);
assert!(book.candidate(at(base, 600), 1000, CONFIG).is_none());
}
#[test]
fn an_unregistered_run_leaves_nothing_behind() {
let base = Instant::now();
let book = book(
base,
&[(
"run-1",
EvictionPolicy::ttl(Duration::from_secs(1)),
Some(0),
)],
);
book.unregister("run-1");
assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
let guard = book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0));
drop(guard);
assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
}
#[test]
fn a_worker_with_no_durable_slots_is_never_under_pressure() {
assert!(!under_pressure(0, 0, 10));
assert!(!under_pressure(2, 2, 10));
assert!(!under_pressure(2, 3, 10));
assert!(under_pressure(2, 0, 2));
assert!(!under_pressure(2, 0, 1));
assert!(under_pressure(2, 1, 1));
}
#[test]
fn the_defaults_are_the_official_go_sdks() {
let policy = EvictionPolicy::default();
assert_eq!(policy.ttl, Duration::from_secs(15 * 60));
assert!(policy.allow_capacity_eviction);
assert_eq!(policy.priority, 0);
assert_eq!(EvictionPolicy::ttl(Duration::from_secs(1)).priority, 0);
}
#[test]
fn eviction_is_supported_from_the_version_the_official_sdks_gate_on() {
assert!(!supported("v0.79.0"));
assert!(supported(crate::version::MIN_ENGINE_VERSION));
assert!(supported("v0.107.0"));
assert!(supported("not a version"));
}
}