use super::estimator::Stats;
use super::sampler::{best_of_d, AliasTable, Rng};
#[derive(Debug, Clone)]
pub struct Candidate {
pub stats: Stats,
pub in_flight: u32,
pub price_per_hour: f64,
pub local: bool,
}
#[derive(Debug, Clone, Copy)]
pub struct Weights {
pub latency: f64,
pub price: f64,
pub retry: f64,
pub unmeasured_ms: f64,
pub mesh_hop_ms: f64,
pub candidates_per_choice: usize,
pub weighting_exponent: f64,
pub queue_convexity: f64,
pub fleet_prior_weight: f64,
pub explore_floor: f64,
}
impl Default for Weights {
fn default() -> Self {
Weights {
latency: 1.0,
price: 0.0,
retry: 2.0,
unmeasured_ms: 250.0,
mesh_hop_ms: 250.0,
candidates_per_choice: 4,
weighting_exponent: 2.0,
queue_convexity: 1.0,
fleet_prior_weight: FLEET_PRIOR_WEIGHT,
explore_floor: EXPLORE_FLOOR,
}
}
}
pub const FLEET_PRIOR_WEIGHT: f64 = 1.0;
pub const EXPLORE_FLOOR: f64 = 0.005;
fn unmeasured_ms(candidate_local: bool, w: &Weights) -> f64 {
if candidate_local {
w.unmeasured_ms
} else {
w.unmeasured_ms + w.mesh_hop_ms
}
}
fn standard_normal(rng: &mut Rng) -> f64 {
let u1 = rng.next_f64().max(f64::MIN_POSITIVE);
let u2 = rng.next_f64();
(-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos()
}
pub fn sample_service_ms(stats: &Stats, local: bool, w: &Weights, rng: &mut Rng) -> f64 {
let n = stats.weight();
match (stats.median_service_ms(), n >= 1.0) {
(Some(median), true) => {
let sd = stats.log_sd().unwrap_or(0.5).max(0.05);
let spread = sd / n.sqrt();
(median.ln() + standard_normal(rng) * spread).exp()
}
_ => (unmeasured_ms(local, w).ln() + standard_normal(rng) * 0.8).exp(),
}
}
pub fn cost(candidate: &Candidate, sampled_service_ms: f64, w: &Weights) -> f64 {
let queue = (1.0 + candidate.in_flight as f64).powf(w.queue_convexity);
let completion = sampled_service_ms * queue;
let failure = 1.0 - candidate.stats.success_rate() * candidate.stats.trust();
let price = candidate.price_per_hour * sampled_service_ms / 3_600_000.0;
w.latency * completion + w.price * price + w.retry * failure * completion
}
pub fn with_fleet_prior(candidates: &[Candidate], w: &Weights) -> Vec<Candidate> {
if w.fleet_prior_weight <= 0.0 {
return candidates.to_vec();
}
let mut pool = [Stats::new(), Stats::new()];
for c in candidates {
pool[usize::from(c.local)].merge(&c.stats);
}
candidates
.iter()
.map(|c| {
let others = pool[usize::from(c.local)].service_without(&c.stats);
Candidate {
stats: c
.stats
.with_service_prior(&others, w.fleet_prior_weight - c.stats.weight()),
..c.clone()
}
})
.collect()
}
pub fn choose(
candidates: &[Candidate],
table: &AliasTable,
rng: &mut Rng,
d: usize,
w: &Weights,
) -> Option<usize> {
if candidates.is_empty() || table.is_empty() {
return None;
}
if w.explore_floor > 0.0 && rng.next_f64() < w.explore_floor {
let i = (rng.next_f64() * candidates.len() as f64) as usize;
return Some(i.min(candidates.len() - 1));
}
let sampled = std::cell::RefCell::new(Rng::seeded((rng.next_f64() * u64::MAX as f64) as u64));
let chosen = best_of_d(table, rng, d, |i| {
let c = &candidates[i];
let s = sample_service_ms(&c.stats, c.local, w, &mut sampled.borrow_mut());
cost(c, s, w)
});
chosen.filter(|i| *i < candidates.len())
}
pub fn table_weight(candidate: &Candidate, w: &Weights) -> f64 {
let service = candidate
.stats
.expected_service_ms()
.unwrap_or_else(|| unmeasured_ms(candidate.local, w));
let queue = (1.0 + candidate.in_flight as f64).powf(w.queue_convexity);
let completion = service * queue;
if completion <= 0.0 {
return 0.0;
}
let rate = 1.0 / completion;
rate.powf(w.weighting_exponent)
}
#[cfg(test)]
mod tests {
use super::*;
fn measured(median_ms: f64, n: usize, ok: bool) -> Stats {
let mut s = Stats::new();
for _ in 0..n {
s.observe(median_ms, ok);
}
s
}
fn candidate(median_ms: f64, n: usize, in_flight: u32) -> Candidate {
Candidate {
stats: measured(median_ms, n, true),
in_flight,
price_per_hour: 3.6,
local: false,
}
}
#[test]
fn an_unmeasured_local_worker_is_preferred_over_an_unmeasured_peer() {
let w = Weights::default();
let unmeasured = |local: bool| Candidate {
stats: Stats::new(),
in_flight: 0,
price_per_hour: 3.6,
local,
};
let local = unmeasured(true);
let peer = unmeasured(false);
assert!(
table_weight(&local, &w) > table_weight(&peer, &w),
"an unmeasured local worker must be drawn more often than an unmeasured peer: \
local {} vs peer {}",
table_weight(&local, &w),
table_weight(&peer, &w)
);
let ratio = table_weight(&local, &w) / table_weight(&peer, &w);
assert!(
(3.5..4.5).contains(&ratio),
"an unmeasured local worker should be drawn ~4x as often as an \
unmeasured peer (inverse-completion squared), got {ratio:.2}x"
);
let mut rng = Rng::seeded(7);
let mut local_wins = 0;
for _ in 0..500 {
let l = sample_service_ms(&local.stats, true, &w, &mut rng);
let p = sample_service_ms(&peer.stats, false, &w, &mut rng);
if l < p {
local_wins += 1;
}
}
assert!(
(300..480).contains(&local_wins),
"the local prior must win most draws but not all of them, got \
{local_wins}/500"
);
}
#[test]
fn measurements_still_override_the_local_prior() {
let w = Weights::default();
let fast_peer = Candidate {
stats: measured(2.0, 200, true),
in_flight: 0,
price_per_hour: 3.6,
local: false,
};
let cold_local = Candidate {
stats: Stats::new(),
in_flight: 0,
price_per_hour: 3.6,
local: true,
};
assert!(
table_weight(&fast_peer, &w) > table_weight(&cold_local, &w),
"a peer measured at 2ms must outrank a local worker merely assumed \
at {}ms",
w.unmeasured_ms
);
}
#[test]
fn a_well_measured_worker_is_sampled_close_to_what_it_measured() {
let w = Weights::default();
let mut rng = Rng::seeded(1);
let stats = measured(50.0, 200, true);
let draws: Vec<f64> = (0..500)
.map(|_| sample_service_ms(&stats, false, &w, &mut rng))
.collect();
let mean = draws.iter().sum::<f64>() / draws.len() as f64;
assert!(
(mean - 50.0).abs() < 10.0,
"200 observations should pin it near 50 ms, got {mean:.1}"
);
}
#[test]
fn a_barely_measured_worker_is_sampled_widely() {
let w = Weights::default();
let spread = |n: usize| {
let stats = measured(50.0, n, true);
let mut rng = Rng::seeded(7);
let draws: Vec<f64> = (0..2000)
.map(|_| sample_service_ms(&stats, false, &w, &mut rng))
.collect();
let mean = draws.iter().sum::<f64>() / draws.len() as f64;
let var = draws.iter().map(|d| (d - mean).powi(2)).sum::<f64>() / draws.len() as f64;
var.sqrt()
};
assert!(
spread(2) > spread(200) * 3.0,
"little evidence must sample widely: {:.1} vs {:.1}",
spread(2),
spread(200)
);
}
#[test]
fn queueing_counts_against_a_worker() {
let w = Weights::default();
let idle = candidate(30.0, 50, 0);
let busy = candidate(10.0, 50, 4);
assert!(
cost(&busy, 10.0, &w) > cost(&idle, 30.0, &w),
"four queued at 10 ms is worse than idle at 30 ms"
);
}
#[test]
fn failure_and_price_move_the_cost_the_way_they_should() {
let w = Weights::default();
let mut flaky = candidate(50.0, 0, 0);
for _ in 0..20 {
flaky.stats.observe(50.0, false);
}
let solid = candidate(50.0, 20, 0);
assert!(
cost(&flaky, 50.0, &w) > cost(&solid, 50.0, &w),
"a worker that keeps failing costs more than one that does not"
);
let priced = Weights {
price: 1e6,
..Weights::default()
};
let cheap = Candidate {
price_per_hour: 1.0,
..candidate(50.0, 20, 0)
};
let dear = Candidate {
price_per_hour: 100.0,
..candidate(50.0, 20, 0)
};
assert!(cost(&dear, 50.0, &priced) > cost(&cheap, 50.0, &priced));
}
#[test]
fn the_table_weights_a_fast_idle_worker_above_a_slow_busy_one() {
let w = Weights::default();
assert!(
table_weight(&candidate(10.0, 20, 0), &w) > table_weight(&candidate(10.0, 20, 4), &w)
);
assert!(
table_weight(&candidate(10.0, 20, 0), &w) > table_weight(&candidate(100.0, 20, 0), &w)
);
assert!(table_weight(&candidate(0.0, 0, 0), &w) > 0.0);
}
#[test]
fn weighting_exponent_controls_how_sharply_load_concentrates() {
let slow_share = |exponent: f64| {
let w = Weights {
weighting_exponent: exponent,
..Weights::default()
};
let fast = candidate(254.0, 50, 0);
let slow = candidate(1000.0, 50, 0);
let weights: Vec<f64> = std::iter::repeat_n(&fast, 4)
.chain(std::iter::repeat_n(&slow, 9))
.map(|c| table_weight(c, &w))
.collect();
let total: f64 = weights.iter().sum();
weights[4..].iter().sum::<f64>() / total
};
let linear = slow_share(1.0);
let squared = slow_share(2.0);
assert!(
(linear - 0.36).abs() < 0.01,
"linear weighting should match the measured 36% slow-end share, got {linear:.3}"
);
assert!(
squared < linear,
"a higher exponent must concentrate load more, not less: linear {linear:.3}, squared {squared:.3}"
);
assert!(
squared < 0.15,
"squared weighting should land close to the ~13% measured after squaring, got {squared:.3}"
);
}
#[test]
fn convex_queue_term_punishes_a_full_queue_harder_than_linear() {
let linear = Weights {
queue_convexity: 1.0,
..Weights::default()
};
let convex = Weights {
queue_convexity: 2.0,
..Weights::default()
};
let idle = candidate(50.0, 50, 0);
let busy = candidate(50.0, 50, 4);
let weight_ratio = |w: &Weights| table_weight(&busy, w) / table_weight(&idle, w);
assert!(
weight_ratio(&convex) < weight_ratio(&linear),
"convex queueing should shrink a busy worker's table share more: linear {:.5}, convex {:.5}",
weight_ratio(&linear),
weight_ratio(&convex)
);
let cost_ratio = |w: &Weights| cost(&busy, 50.0, w) / cost(&idle, 50.0, w);
assert!(
cost_ratio(&convex) > cost_ratio(&linear),
"convex queueing should cost a busy worker relatively more: linear {:.3}, convex {:.3}",
cost_ratio(&linear),
cost_ratio(&convex)
);
}
#[test]
fn an_unmeasured_worker_borrows_its_siblings_evidence() {
let w = Weights::default();
let local = |median: f64, n: usize| Candidate {
local: true,
..candidate(median, n, 0)
};
let fleet = vec![
local(4.0, 30),
local(4.0, 30),
local(4.0, 30),
local(0.0, 0),
];
let view = with_fleet_prior(&fleet, &w);
let cold = &view[3];
assert!(
(cold.stats.weight() - 1.0).abs() < 1e-9,
"topped up to one observation"
);
let median = cold.stats.median_service_ms().expect("now has an estimate");
assert!(
(median - 4.0).abs() < 1e-6,
"reads as its siblings, got {median}"
);
let ratio = table_weight(&view[3], &w) / table_weight(&view[0], &w);
assert!(
(0.9..1.1).contains(&ratio),
"drawn about as often as a measured sibling, got {ratio:.2}x"
);
let mixed = vec![local(4.0, 30), local(400.0, 3), local(0.0, 0)];
let view = with_fleet_prior(&mixed, &w);
assert_eq!(view[0].stats, mixed[0].stats);
assert_eq!(view[1].stats, mixed[1].stats);
assert_eq!(view[2].stats.success_rate(), mixed[2].stats.success_rate());
let peer = Candidate {
local: false,
..candidate(0.0, 0, 0)
};
let view = with_fleet_prior(&[local(4.0, 30), peer.clone()], &w);
assert_eq!(
view[1].stats, peer.stats,
"a peer has no peers to borrow from here"
);
let cold_broker = vec![local(0.0, 0), peer];
let view = with_fleet_prior(&cold_broker, &w);
assert_eq!(view[0].stats, cold_broker[0].stats);
assert_eq!(view[1].stats, cold_broker[1].stats);
let off = Weights {
fleet_prior_weight: 0.0,
..Weights::default()
};
assert_eq!(with_fleet_prior(&fleet, &off)[3].stats, fleet[3].stats);
}
}
#[cfg(test)]
mod regret_tests {
use super::*;
struct Fleet {
truth_ms: Vec<f64>,
stats: Vec<Stats>,
in_flight: Vec<u32>,
}
impl Fleet {
fn new(truth_ms: Vec<f64>) -> Self {
let n = truth_ms.len();
Fleet {
truth_ms,
stats: vec![Stats::new(); n],
in_flight: vec![0; n],
}
}
fn candidates(&self) -> Vec<Candidate> {
(0..self.truth_ms.len())
.map(|i| Candidate {
stats: self.stats[i],
in_flight: self.in_flight[i],
price_per_hour: 3.6,
local: false,
})
.collect()
}
fn run(&mut self, i: usize, rng: &mut Rng) -> f64 {
let noise = 0.75 + rng.next_f64() * 0.5;
let took = self.truth_ms[i] * noise;
self.stats[i].decay(0.98);
self.stats[i].observe(took, true);
took
}
fn decision_view(&self) -> Vec<Candidate> {
with_fleet_prior(&self.candidates(), &Weights::default())
}
}
fn run_policy(truth: Vec<f64>, tasks: usize, seed: u64, d: usize) -> f64 {
let mut fleet = Fleet::new(truth);
let mut rng = Rng::seeded(seed);
let w = Weights::default();
let mut total = 0.0;
for t in 0..tasks {
let cands = fleet.decision_view();
let weights: Vec<f64> = cands.iter().map(|c| table_weight(c, &w)).collect();
let table = AliasTable::build(&weights).expect("a fleet");
let i = choose(&cands, &table, &mut rng, d, &w).expect("a choice");
total += fleet.run(i, &mut rng);
let _ = t;
}
total
}
fn run_round_robin(truth: Vec<f64>, tasks: usize, seed: u64) -> f64 {
let mut fleet = Fleet::new(truth);
let mut rng = Rng::seeded(seed);
let n = fleet.truth_ms.len();
(0..tasks).map(|t| fleet.run(t % n, &mut rng)).sum()
}
fn run_oracle(truth: Vec<f64>, tasks: usize, seed: u64) -> f64 {
let best = truth
.iter()
.enumerate()
.min_by(|a, b| a.1.partial_cmp(b.1).unwrap())
.map(|(i, _)| i)
.unwrap();
let mut fleet = Fleet::new(truth);
let mut rng = Rng::seeded(seed);
(0..tasks).map(|_| fleet.run(best, &mut rng)).sum()
}
fn mesh() -> Vec<f64> {
let mut t = vec![254.0; 4];
t.extend(std::iter::repeat_n(1000.0, 9));
t
}
fn queueing_mesh() -> Vec<f64> {
let mut t = vec![150.0, 280.0, 290.0, 300.0];
t.extend(std::iter::repeat_n(1000.0, 9));
t
}
struct Completion {
at: f64,
worker: usize,
client: usize,
service: f64,
observed: f64,
}
#[derive(Debug, Clone, Copy, PartialEq)]
enum Observation {
Service,
RoundTrip,
PerSlot,
}
impl PartialEq for Completion {
fn eq(&self, other: &Self) -> bool {
self.at == other.at
}
}
impl Eq for Completion {}
impl PartialOrd for Completion {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Completion {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.at.partial_cmp(&self.at).unwrap()
}
}
struct QueueingFleet {
truth_ms: Vec<f64>,
stats: Vec<Stats>,
in_flight: Vec<u32>,
visible_in_flight: Vec<u32>,
available_at: Vec<f64>,
staleness: usize,
decisions_since_refresh: usize,
cold_ms: f64,
observation: Observation,
served: Vec<usize>,
completed: Vec<usize>,
warming: Vec<usize>,
skip_first_observation: bool,
round_robin: bool,
}
impl QueueingFleet {
fn new(truth_ms: Vec<f64>) -> Self {
Self::with_staleness(truth_ms, 0)
}
fn with_staleness(truth_ms: Vec<f64>, staleness: usize) -> Self {
let n = truth_ms.len();
QueueingFleet {
truth_ms,
stats: vec![Stats::new(); n],
in_flight: vec![0; n],
visible_in_flight: vec![0; n],
available_at: vec![0.0; n],
staleness,
decisions_since_refresh: 0,
cold_ms: 0.0,
observation: Observation::Service,
served: vec![0; n],
completed: vec![0; n],
warming: vec![0; n],
round_robin: false,
skip_first_observation: true,
}
}
fn candidates(&self) -> Vec<Candidate> {
(0..self.truth_ms.len())
.map(|i| Candidate {
stats: self.stats[i],
in_flight: self.visible_in_flight[i],
price_per_hour: 3.6,
local: false,
})
.collect()
}
fn refresh_visibility(&mut self) {
if self.decisions_since_refresh == 0 {
self.visible_in_flight.copy_from_slice(&self.in_flight);
}
self.decisions_since_refresh += 1;
if self.decisions_since_refresh > self.staleness {
self.decisions_since_refresh = 0;
}
}
fn dispatch(
&mut self,
now: f64,
client: usize,
rng: &mut Rng,
d: usize,
w: &Weights,
) -> Completion {
self.refresh_visibility();
let cands = with_fleet_prior(&self.candidates(), w);
let weights: Vec<f64> = cands.iter().map(|c| table_weight(c, w)).collect();
let table = AliasTable::build(&weights).expect("a fleet");
let i = match self.round_robin {
true => self.served.iter().sum::<usize>() % self.truth_ms.len(),
false => choose(&cands, &table, rng, d, w).expect("a choice"),
};
let ahead = self.in_flight[i];
self.in_flight[i] += 1;
if self.completed[i] == 0 {
self.warming[i] += 1;
}
let noise = 0.75 + rng.next_f64() * 0.5;
let cold = if self.served[i] == 0 {
self.cold_ms
} else {
0.0
};
self.served[i] += 1;
let service = self.truth_ms[i] * noise + cold;
let start = self.available_at[i].max(now);
let at = start + service;
self.available_at[i] = at;
let observed = match self.observation {
Observation::Service => service,
Observation::RoundTrip => at - now,
Observation::PerSlot => (at - now) / (1.0 + ahead as f64),
};
Completion {
at,
worker: i,
client,
service,
observed,
}
}
fn complete(&mut self, c: &Completion) {
self.in_flight[c.worker] = self.in_flight[c.worker].saturating_sub(1);
self.completed[c.worker] += 1;
if self.skip_first_observation && self.warming[c.worker] > 0 {
self.warming[c.worker] -= 1;
self.stats[c.worker].observe_outcome(true);
return;
}
self.stats[c.worker].decay(0.98);
self.stats[c.worker].observe(c.observed, true);
}
}
fn run_policy_concurrent(
truth: Vec<f64>,
requests: usize,
concurrency: usize,
seed: u64,
d: usize,
w: &Weights,
) -> Vec<f64> {
run_policy_concurrent_with_staleness(truth, requests, concurrency, seed, d, w, 0)
}
#[allow(clippy::too_many_arguments)]
fn run_policy_concurrent_with_staleness(
truth: Vec<f64>,
requests: usize,
concurrency: usize,
seed: u64,
d: usize,
w: &Weights,
staleness: usize,
) -> Vec<f64> {
let fleet = QueueingFleet::with_staleness(truth, staleness);
run_fleet(fleet, requests, concurrency, seed, d, w).0
}
fn run_fleet(
mut fleet: QueueingFleet,
requests: usize,
concurrency: usize,
seed: u64,
d: usize,
w: &Weights,
) -> (Vec<f64>, Vec<usize>) {
use std::collections::BinaryHeap;
let mut rng = Rng::seeded(seed);
let mut heap: BinaryHeap<Completion> = BinaryHeap::new();
let mut latencies = Vec::with_capacity(requests);
let mut submitted_at = vec![0.0f64; concurrency];
let mut dispatched = 0usize;
let clients = concurrency.min(requests);
for client in 0..clients {
heap.push(fleet.dispatch(0.0, client, &mut rng, d, w));
dispatched += 1;
}
while let Some(c) = heap.pop() {
fleet.complete(&c);
latencies.push(c.at - submitted_at[c.client]);
if dispatched < requests {
submitted_at[c.client] = c.at;
heap.push(fleet.dispatch(c.at, c.client, &mut rng, d, w));
dispatched += 1;
}
}
(latencies, fleet.served)
}
fn run_oracle_concurrent(
truth: Vec<f64>,
requests: usize,
concurrency: usize,
seed: u64,
) -> Vec<f64> {
let best_ms = truth.iter().cloned().fold(f64::INFINITY, f64::min);
let mut rng = Rng::seeded(seed);
let mut latencies = Vec::with_capacity(requests);
let mut submitted_at = vec![0.0f64; concurrency];
let mut available_at = 0.0f64;
let mut dispatched = 0usize;
let mut completions: std::collections::BinaryHeap<Completion> =
std::collections::BinaryHeap::new();
let mut dispatch_to_best = |now: f64, client: usize, rng: &mut Rng| -> Completion {
let noise = 0.75 + rng.next_f64() * 0.5;
let service = best_ms * noise;
let start = available_at.max(now);
let at = start + service;
available_at = at;
Completion {
at,
worker: 0,
client,
service,
observed: service,
}
};
let clients = concurrency.min(requests);
for client in 0..clients {
completions.push(dispatch_to_best(0.0, client, &mut rng));
dispatched += 1;
}
while let Some(c) = completions.pop() {
latencies.push(c.at - submitted_at[c.client]);
if dispatched < requests {
submitted_at[c.client] = c.at;
completions.push(dispatch_to_best(c.at, c.client, &mut rng));
dispatched += 1;
}
}
latencies
}
#[derive(Debug, Clone, Copy, PartialEq)]
struct TailStats {
mean: f64,
p50: f64,
p90: f64,
p99: f64,
max: f64,
}
impl std::fmt::Display for TailStats {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"mean {:.0} p50 {:.0} p90 {:.0} p99 {:.0} max {:.0}",
self.mean, self.p50, self.p90, self.p99, self.max
)
}
}
fn tail_stats(values: &[f64]) -> TailStats {
assert!(!values.is_empty(), "no samples to summarise");
let mut sorted = values.to_vec();
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
let n = sorted.len();
let at = |p: f64| {
let rank = ((p * n as f64).ceil() as usize).clamp(1, n);
sorted[rank - 1]
};
TailStats {
mean: sorted.iter().sum::<f64>() / n as f64,
p50: at(0.50),
p90: at(0.90),
p99: at(0.99),
max: sorted[n - 1],
}
}
#[test]
fn the_policy_beats_round_robin_by_a_wide_margin() {
let tasks = 3_000;
let policy = run_policy(mesh(), tasks, 11, 2);
let rr = run_round_robin(mesh(), tasks, 11);
let oracle = run_oracle(mesh(), tasks, 11);
let policy_regret = policy - oracle;
let rr_regret = rr - oracle;
println!(
" per task: oracle {:.0} ms, policy {:.0} ms, round-robin {:.0} ms",
oracle / tasks as f64,
policy / tasks as f64,
rr / tasks as f64
);
assert!(
policy_regret * 3.0 < rr_regret,
"policy regret {policy_regret:.0} ms vs round-robin {rr_regret:.0} ms"
);
}
#[test]
fn regret_per_task_shrinks_as_it_learns() {
let oracle_per_task = |tasks: usize| run_oracle(mesh(), tasks, 3) / tasks as f64;
let policy_per_task = |tasks: usize| run_policy(mesh(), tasks, 3, 2) / tasks as f64;
let early = policy_per_task(300) - oracle_per_task(300);
let late = policy_per_task(6_000) - oracle_per_task(6_000);
println!(" regret per task: early {early:.1} ms, late {late:.1} ms");
assert!(
late < early * 0.6,
"should keep improving: early {early:.1} ms, late {late:.1} ms"
);
}
fn rediscovery(seed: u64, w: &Weights, after_decisions: usize) -> (usize, usize) {
let mut fleet = Fleet::new(mesh());
let mut rng = Rng::seeded(seed);
let dispatch = |fleet: &mut Fleet, rng: &mut Rng| -> usize {
let cands = fleet.decision_view();
let weights: Vec<f64> = cands.iter().map(|c| table_weight(c, w)).collect();
let table = AliasTable::build(&weights).expect("a fleet");
let i = choose(&cands, &table, rng, 2, w).expect("a choice");
fleet.run(i, rng);
i
};
for _ in 0..1_500 {
dispatch(&mut fleet, &mut rng);
}
let before: usize = (0..300)
.map(|_| usize::from(dispatch(&mut fleet, &mut rng) == 12))
.sum();
fleet.truth_ms[12] = 20.0;
for _ in 0..after_decisions {
dispatch(&mut fleet, &mut rng);
}
let after: usize = (0..300)
.map(|_| usize::from(dispatch(&mut fleet, &mut rng) == 12))
.sum();
(before, after)
}
#[test]
fn it_notices_a_slow_worker_that_becomes_fast() {
let w = Weights::default();
let mut failed = Vec::new();
for seed in 1..=40u64 {
let (before, after) = rediscovery(seed, &w, 4_000);
if !(before < 30 && after > 150) {
failed.push((seed, before, after));
}
}
println!(" seeds that failed: {failed:?}");
assert!(
failed.len() <= 1,
"it must find a worker that improves, not write it off: (seed, before, after) {failed:?}"
);
}
#[test]
fn it_follows_the_mesh_when_conditions_change() {
let mut fleet = Fleet::new(mesh());
let mut rng = Rng::seeded(21);
let w = Weights::default();
let dispatch = |fleet: &mut Fleet, rng: &mut Rng| -> usize {
let cands = fleet.decision_view();
let weights: Vec<f64> = cands.iter().map(|c| table_weight(c, &w)).collect();
let table = AliasTable::build(&weights).expect("a fleet");
let i = choose(&cands, &table, rng, 2, &w).expect("a choice");
fleet.run(i, rng);
i
};
for _ in 0..1_500 {
dispatch(&mut fleet, &mut rng);
}
let before: usize = (0..300)
.map(|_| usize::from(dispatch(&mut fleet, &mut rng) < 4))
.sum();
for truth in fleet.truth_ms.iter_mut().take(4) {
*truth = 2_000.0;
}
for _ in 0..1_500 {
dispatch(&mut fleet, &mut rng);
}
let after: usize = (0..300)
.map(|_| usize::from(dispatch(&mut fleet, &mut rng) < 4))
.sum();
println!(" share on the formerly-fast workers: {before}/300 → {after}/300");
assert!(before > 200, "it found the fast ones: {before}/300");
assert!(
after < 90,
"it moved off them once they slowed: {after}/300"
);
}
#[test]
fn tail_stats_uses_nearest_rank_percentiles() {
let values: Vec<f64> = (1..=100).rev().map(|v| v as f64).collect();
let s = tail_stats(&values);
assert_eq!(s.p50, 50.0);
assert_eq!(s.p90, 90.0);
assert_eq!(s.p99, 99.0);
assert_eq!(s.max, 100.0);
assert!((s.mean - 50.5).abs() < 1e-9);
}
#[test]
fn stale_visibility_lets_a_burst_pile_onto_one_worker() {
let w = Weights {
explore_floor: 0.0,
..Weights::default()
};
let burst = 8;
let seeds = 30u64;
let max_share = |staleness: usize| -> f64 {
let mut total = 0.0;
for seed in 0..seeds {
let mut fleet = QueueingFleet::with_staleness(vec![100.0, 100.0], staleness);
for stats in fleet.stats.iter_mut().take(2) {
for _ in 0..50 {
stats.observe(100.0, true);
}
}
let mut rng = Rng::seeded(seed);
let mut landed = [0usize; 2];
for _ in 0..burst {
let c = fleet.dispatch(0.0, 0, &mut rng, 4, &w);
landed[c.worker] += 1;
}
total += *landed.iter().max().unwrap() as f64 / burst as f64;
}
total / seeds as f64
};
let fresh = max_share(0);
let stale = max_share(burst);
println!(" max share on one worker: fresh {fresh:.2}, stale {stale:.2}");
assert!(
stale > fresh + 0.1,
"a stale-for-the-whole-burst router should concentrate load more: fresh {fresh:.2}, stale {stale:.2}"
);
}
#[test]
fn adaptive_routing_keeps_the_tail_within_bounds_of_the_oracle() {
let requests = 20_000;
let concurrency = 4;
let w = Weights::default();
let mut latencies = Vec::new();
let mut oracle = Vec::new();
for seed in [1u64, 2, 3, 4, 5] {
latencies.extend(run_policy_concurrent(
queueing_mesh(),
requests,
concurrency,
seed,
w.candidates_per_choice,
&w,
));
oracle.extend(run_oracle_concurrent(
queueing_mesh(),
requests,
concurrency,
seed,
));
}
let stats = tail_stats(&latencies);
let o = tail_stats(&oracle);
println!(" chosen point tail: {stats}, oracle: {o}");
assert!(
stats.p99 < o.p99 * 2.5,
"p99 should stay within 2.5x the oracle's, got {:.0} vs oracle {:.0}",
stats.p99,
o.p99
);
assert!(
stats.max < o.max * 3.5,
"max should not run away either, got {:.0} vs oracle {:.0}",
stats.max,
o.max
);
}
#[test]
fn sharper_weighting_does_not_regain_its_edge_under_realistic_staleness() {
let requests = 20_000;
let concurrency = 4;
let d = 4;
let staleness = 8;
let seeds = [1u64, 2, 3, 4, 5];
let run = |w: &Weights| -> TailStats {
let mut latencies = Vec::new();
for &seed in &seeds {
latencies.extend(run_policy_concurrent_with_staleness(
queueing_mesh(),
requests,
concurrency,
seed,
d,
w,
staleness,
));
}
tail_stats(&latencies)
};
let default = run(&Weights::default());
let sharper = run(&Weights {
weighting_exponent: 3.0,
..Weights::default()
});
let convex = run(&Weights {
queue_convexity: 2.0,
..Weights::default()
});
println!(
" under staleness={staleness}: default {default}, sharper-exponent {sharper}, convex-queue {convex}"
);
assert!(
sharper.p99 >= default.p99 * 0.95,
"exponent 3.0 should no longer clearly beat the default under staleness: default p99 {:.0}, sharper p99 {:.0}",
default.p99,
sharper.p99
);
assert!(
convex.p99 >= default.p99 * 0.95,
"convex queueing should no longer clearly beat the default under staleness: default p99 {:.0}, convex p99 {:.0}",
default.p99,
convex.p99
);
}
#[test]
fn defaults_document_the_chosen_operating_point() {
let w = Weights::default();
assert_eq!(w.candidates_per_choice, 4);
assert!((w.weighting_exponent - 2.0).abs() < f64::EPSILON);
assert!((w.queue_convexity - 1.0).abs() < f64::EPSILON);
assert!((w.explore_floor - 0.005).abs() < f64::EPSILON);
}
#[test]
fn identical_workers_under_concurrency_get_an_even_split() {
let cases: [(f64, usize, usize, usize); 3] = [
(4.0, 4, 6, 600), (120.0, 4, 8, 240), (20.0, 8, 8, 800), ];
let split =
|service: f64, n: usize, conc: usize, requests: usize, seed: u64, fixed: bool| {
let mut fleet = fleet_of(vec![service; n], 500.0, Observation::RoundTrip);
fleet.skip_first_observation = fixed;
let w = Weights {
fleet_prior_weight: if fixed { FLEET_PRIOR_WEIGHT } else { 0.0 },
..Weights::default()
};
let (_, served) =
run_fleet(fleet, requests, conc, seed, w.candidates_per_choice, &w);
let total = served.iter().sum::<usize>() as f64;
served
.iter()
.map(|&x| x as f64 / total)
.collect::<Vec<f64>>()
};
let worst = |shares: &[f64]| {
shares
.iter()
.map(|x| (x - 1.0 / shares.len() as f64).abs())
.fold(0.0, f64::max)
};
let mut starved_before = 0;
for (service, n, conc, requests) in cases {
for seed in 1..=8u64 {
let now = split(service, n, conc, requests, seed, true);
assert!(
worst(&now) <= 0.05,
"{n} identical {service} ms workers at concurrency {conc}, seed {seed}: \
split {now:.3?} is more than 5 points off uniform"
);
if worst(&split(service, n, conc, requests, seed, false)) > 0.05 {
starved_before += 1;
}
}
}
assert!(
starved_before > 0,
"without the fleet prior and the warm-up exclusion these runs should \
reproduce the uneven staging split; if they no longer do, this test \
has stopped testing #438"
);
}
fn fleet_of(truth: Vec<f64>, cold_ms: f64, obs: Observation) -> QueueingFleet {
let mut f = QueueingFleet::new(truth);
f.cold_ms = cold_ms;
f.observation = obs;
f
}
fn run_many(
make: impl Fn() -> QueueingFleet,
requests: usize,
concurrency: usize,
seeds: &[u64],
w: &Weights,
) -> (TailStats, Vec<f64>) {
let mut lat = Vec::new();
let mut served: Vec<usize> = Vec::new();
for &seed in seeds {
let (l, s) = run_fleet(
make(),
requests,
concurrency,
seed,
w.candidates_per_choice,
w,
);
lat.extend(l);
if served.is_empty() {
served = vec![0; s.len()];
}
for (a, b) in served.iter_mut().zip(s) {
*a += b;
}
}
let total = served.iter().sum::<usize>().max(1) as f64;
(
tail_stats(&lat),
served.iter().map(|&x| x as f64 / total).collect(),
)
}
#[test]
#[ignore = "measurement, not a regression: run manually, see doc comment"]
fn sweep_homogeneous_concentration() {
let seeds = [1u64, 2, 3, 4, 5, 6, 7, 8];
let cases: [(&str, Vec<f64>, usize, usize); 4] = [
("light: 4 x 4 ms, c=6", vec![4.0; 4], 6, 600),
("heavy: 4 x 120 ms, c=8", vec![120.0; 4], 8, 240),
("mixed: queueing_mesh, c=4", queueing_mesh(), 4, 2_000),
(
"mixed: queueing_mesh, c=4, long",
queueing_mesh(),
4,
20_000,
),
];
let variants = [
("before #438", false, 0.0),
("fleet prior only", false, FLEET_PRIOR_WEIGHT),
("warm-up skip only", true, 0.0),
("#438", true, FLEET_PRIOR_WEIGHT),
];
for (label, truth, conc, requests) in cases {
println!("\n {label}");
for cold in [0.0, 500.0] {
let make = |round_robin: bool, skip: bool| {
let mut f = fleet_of(truth.clone(), cold, Observation::RoundTrip);
f.round_robin = round_robin;
f.skip_first_observation = skip;
f
};
let (rr, _) = run_many(
|| make(true, false),
requests,
conc,
&seeds,
&Weights::default(),
);
println!(" cold {cold:>3} {:<18} {rr}", "round-robin");
for (name, skip, prior) in variants {
let w = Weights {
fleet_prior_weight: prior,
..Weights::default()
};
let (st, split) = run_many(|| make(false, skip), requests, conc, &seeds, &w);
let dev = split
.iter()
.map(|x| (x - 1.0 / split.len() as f64).abs())
.fold(0.0, f64::max);
println!(" cold {cold:>3} {name:<18} {st} split off by {dev:.3}");
}
}
}
}
#[test]
#[ignore = "measurement, not a regression: run manually, see doc comment"]
fn sweep_d_exponent_and_queue_convexity() {
let requests = 20_000;
let concurrency = 4;
let seeds = [1u64, 2, 3, 4, 5];
let mut oracle = Vec::new();
for &seed in &seeds {
oracle.extend(run_oracle_concurrent(
queueing_mesh(),
requests,
concurrency,
seed,
));
}
let o = tail_stats(&oracle);
println!("\n oracle (always the fastest worker, still queued): {o}");
println!(
"\n {:>2} | {:>4} | {:>6} | {:>6} | {:>6} | {:>6} | {:>6} | {:>6}",
"d", "exp", "queue", "mean", "p50", "p90", "p99", "max"
);
for &d in &[2usize, 3, 4, 8] {
for &exponent in &[1.0f64, 1.5, 2.0, 3.0] {
for &queue_convexity in &[1.0f64, 2.0] {
let w = Weights {
weighting_exponent: exponent,
queue_convexity,
..Weights::default()
};
let mut latencies = Vec::new();
for &seed in &seeds {
latencies.extend(run_policy_concurrent(
queueing_mesh(),
requests,
concurrency,
seed,
d,
&w,
));
}
let s = tail_stats(&latencies);
let queue_label = if queue_convexity == 1.0 {
"linear"
} else {
"convex"
};
println!(
" {:>2} | {:>4} | {:>6} | {:>6.0} | {:>6.0} | {:>6.0} | {:>6.0} | {:>6.0}",
d, exponent, queue_label, s.mean, s.p50, s.p90, s.p99, s.max
);
}
}
}
}
#[test]
#[ignore = "measurement, not a regression: run manually, see doc comment"]
fn sweep_staleness_against_exponent_and_queue_convexity() {
let requests = 20_000;
let concurrency = 4;
let d = 4; let seeds = [1u64, 2, 3, 4, 5];
let mut oracle = Vec::new();
for &seed in &seeds {
oracle.extend(run_oracle_concurrent(
queueing_mesh(),
requests,
concurrency,
seed,
));
}
let o = tail_stats(&oracle);
println!("\n oracle (always the fastest worker, still queued): {o}");
println!(
"\n {:>5} | {:>4} | {:>6} | {:>6} | {:>6} | {:>6} | {:>6} | {:>6}",
"stale", "exp", "queue", "mean", "p50", "p90", "p99", "max"
);
for &staleness in &[0usize, 1, 2, 4, 8, 16] {
for &exponent in &[1.0f64, 1.5, 2.0, 3.0] {
for &queue_convexity in &[1.0f64, 2.0] {
let w = Weights {
weighting_exponent: exponent,
queue_convexity,
..Weights::default()
};
let mut latencies = Vec::new();
for &seed in &seeds {
latencies.extend(run_policy_concurrent_with_staleness(
queueing_mesh(),
requests,
concurrency,
seed,
d,
&w,
staleness,
));
}
let s = tail_stats(&latencies);
let queue_label = if queue_convexity == 1.0 {
"linear"
} else {
"convex"
};
println!(
" {:>5} | {:>4} | {:>6} | {:>6.0} | {:>6.0} | {:>6.0} | {:>6.0} | {:>6.0}",
staleness, exponent, queue_label, s.mean, s.p50, s.p90, s.p99, s.max
);
}
}
}
}
}