* [RFC proxmox 2/3] resource-scheduling: add {topsis,pve_static}-variants with basic proptests
2026-03-06 8:20 [RFC proxmox 0/3] evaluate static scheduler variants Dominik Rusovac
2026-03-06 8:20 ` [RFC proxmox 1/3] resource-scheduling: add lab feature Dominik Rusovac
@ 2026-03-06 8:20 ` Dominik Rusovac
2026-03-06 8:20 ` [RFC proxmox 3/3] resource-scheduling: evaluate static scheduler variants Dominik Rusovac
2 siblings, 0 replies; 4+ messages in thread
From: Dominik Rusovac @ 2026-03-06 8:20 UTC (permalink / raw)
To: pve-devel
Add concrete variants to evaluate.
Proptest against current implementation, for the sake of a basic
proptest demo.
Signed-off-by: Dominik Rusovac <d.rusovac@proxmox.com>
---
Cargo.toml | 1 +
proxmox-resource-scheduling/Cargo.toml | 3 +
proxmox-resource-scheduling/src/pve_static.rs | 142 ++++++++++++++++-
proxmox-resource-scheduling/src/topsis.rs | 144 +++++++++++++++++-
4 files changed, 288 insertions(+), 2 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
index 1a6cc5d7..446aa65a 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -141,6 +141,7 @@ tracing-subscriber = "0.3.16"
url = "2.2"
walkdir = "2"
zstd = "0.13"
+proptest = "1.6.0"
# workspace dependencies
proxmox-access-control = { version = "1.3.0", path = "proxmox-access-control" }
diff --git a/proxmox-resource-scheduling/Cargo.toml b/proxmox-resource-scheduling/Cargo.toml
index 5060fae3..296ffc66 100644
--- a/proxmox-resource-scheduling/Cargo.toml
+++ b/proxmox-resource-scheduling/Cargo.toml
@@ -12,5 +12,8 @@ exclude.workspace = true
anyhow.workspace = true
serde = { workspace = true, features = [ "derive" ] }
+[dev-dependencies]
+proptest.workspace = true
+
[features]
lab = []
diff --git a/proxmox-resource-scheduling/src/pve_static.rs b/proxmox-resource-scheduling/src/pve_static.rs
index 0afbec05..23e49656 100644
--- a/proxmox-resource-scheduling/src/pve_static.rs
+++ b/proxmox-resource-scheduling/src/pve_static.rs
@@ -5,6 +5,7 @@ use crate::topsis;
#[derive(Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
+#[cfg_attr(feature = "lab", derive(Debug))]
/// Static usage information of a node.
pub struct StaticNodeUsage {
/// Hostname of the node.
@@ -45,6 +46,7 @@ fn add_cpu_usage(old: f64, max: f64, add: f64) -> f64 {
#[derive(Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
+#[cfg_attr(feature = "lab", derive(Debug))]
/// Static usage information of an HA resource.
pub struct StaticServiceUsage {
/// Number of assigned CPUs or CPU limit.
@@ -140,7 +142,10 @@ pub mod evaluate {
topsis::evaluate::{score_alternatives_with_variant, DispatchedTopsis},
};
- use super::{StaticNodeUsage, StaticServiceUsage, N_CRITERIA, PVE_HA_TOPSIS_CRITERIA};
+ use super::{
+ add_cpu_usage, PveTopsisAlternative, StaticNodeUsage, StaticServiceUsage, N_CRITERIA,
+ PVE_HA_TOPSIS_CRITERIA,
+ };
/// Dispatched parts of static resource scheduling
pub trait DispatchedStaticResourceScheduler {
@@ -152,6 +157,74 @@ pub mod evaluate {
) -> Vec<[f64; N_CRITERIA]>;
}
+ #[derive(Debug, PartialEq)]
+ pub enum StaticResourceScheduling {
+ Base,
+ RmsNTimesMoreMaxcpu(usize),
+ }
+
+ fn preprocess_with_rms<T: AsRef<StaticNodeUsage>>(
+ nodes: &[T],
+ service: &StaticServiceUsage,
+ bloat_maxcpu_by: Option<usize>,
+ ) -> Vec<[f64; N_CRITERIA]> {
+ let len = nodes.len();
+ let bf = bloat_maxcpu_by.unwrap_or(1);
+
+ nodes
+ .iter()
+ .enumerate()
+ .map(|(target_index, _)| {
+ let mut highest_cpu = 0.0;
+ let mut squares_cpu = 0.0;
+ let mut highest_mem = 0.0;
+ let mut squares_mem = 0.0;
+
+ for (index, node) in nodes.iter().enumerate() {
+ let node = node.as_ref();
+ let maxcpu = node.maxcpu * bf;
+ let new_cpu = if index == target_index {
+ add_cpu_usage(node.cpu, maxcpu as f64, service.maxcpu)
+ } else {
+ node.cpu
+ } / (maxcpu as f64);
+ highest_cpu = f64::max(highest_cpu, new_cpu);
+ squares_cpu += new_cpu.powi(2);
+
+ let new_mem = if index == target_index {
+ node.mem + service.maxmem
+ } else {
+ node.mem
+ } as f64
+ / node.maxmem as f64;
+ highest_mem = f64::max(highest_mem, new_mem);
+ squares_mem += new_mem.powi(2);
+ }
+
+ PveTopsisAlternative {
+ average_cpu: 1.0 + (squares_cpu / len as f64).sqrt(),
+ highest_cpu: 1.0 + highest_cpu,
+ average_memory: 1.0 + (squares_mem / len as f64).sqrt(),
+ highest_memory: 1.0 + highest_mem,
+ }
+ .into()
+ })
+ .collect::<Vec<_>>()
+ }
+
+ impl DispatchedStaticResourceScheduler for StaticResourceScheduling {
+ fn preprocess<T: AsRef<StaticNodeUsage>>(
+ &self,
+ nodes: &[T],
+ service: &StaticServiceUsage,
+ ) -> Vec<[f64; N_CRITERIA]> {
+ match self {
+ Self::Base => preprocess_with_rms(nodes, service, None),
+ Self::RmsNTimesMoreMaxcpu(n) => preprocess_with_rms(nodes, service, Some(*n)),
+ }
+ }
+ }
+
/// Score `nodes` using specific `topsis_variant` and `static_resource_scheduling_variant`.
///
/// Calls [`crate::topsis::score_nodes_to_start_service`] if `static_resource_scheduling_variant` is [`None`]
@@ -175,4 +248,71 @@ pub mod evaluate {
.unwrap_or_else(|err| panic!("scoring nodes to start service failed: {err}")),
}
}
+
+ #[cfg(test)]
+ mod base_variant_scores_like_present_rollout {
+ use crate::{
+ pve_static::{
+ evaluate::{score_nodes_to_start_service_with_variant, StaticResourceScheduling},
+ score_nodes_to_start_service,
+ },
+ topsis::evaluate::Topsis,
+ };
+
+ use super::super::{StaticNodeUsage, StaticServiceUsage};
+ use proptest::prelude::*;
+
+ const REPEAT_N_TIMES: u32 = 100;
+
+ const MIN_NODES: usize = 2;
+ const MAX_NODES: usize = 40;
+
+ const MAX_CPU: usize = 32;
+ const MAX_MEM: usize = 406;
+
+ fn node() -> impl Strategy<Value = StaticNodeUsage> {
+ (".*", 0.0..(MAX_CPU as f64), 0..MAX_MEM).prop_map(|(name, cpu, mem)| StaticNodeUsage {
+ name,
+ cpu,
+ maxcpu: MAX_CPU,
+ mem,
+ maxmem: MAX_MEM,
+ })
+ }
+
+ fn service() -> impl Strategy<Value = StaticServiceUsage> {
+ (0.0..(MAX_CPU as f64), 0..MAX_MEM)
+ .prop_map(|(maxcpu, maxmem)| StaticServiceUsage { maxcpu, maxmem })
+ }
+
+ fn nodes() -> impl Strategy<Value = Vec<StaticNodeUsage>> {
+ prop::collection::vec(node(), MIN_NODES..MAX_NODES)
+ }
+
+ fn test_case_err(err: impl ToString) -> TestCaseError {
+ TestCaseError::fail(err.to_string())
+ }
+
+ proptest! {
+ #![proptest_config(ProptestConfig {
+ failure_persistence: None,
+ cases: REPEAT_N_TIMES,
+ ..ProptestConfig::default()
+ })]
+
+ #[test]
+ fn shrink_different_winners(nodes in nodes(), service in service()) {
+ let lhs = score_nodes_to_start_service(&nodes, &service).map_err(test_case_err)?;
+ let rhs = score_nodes_to_start_service_with_variant(
+ &nodes,
+ &service,
+ None::<&Topsis>,
+ None::<&StaticResourceScheduling>,
+ );
+
+ assert_eq!(lhs, rhs);
+ }
+
+ }
+ }
}
diff --git a/proxmox-resource-scheduling/src/topsis.rs b/proxmox-resource-scheduling/src/topsis.rs
index f52ee27d..4a0c6b47 100644
--- a/proxmox-resource-scheduling/src/topsis.rs
+++ b/proxmox-resource-scheduling/src/topsis.rs
@@ -18,6 +18,7 @@ fn l2_norm(values: impl IntoIterator<Item = f64>) -> f64 {
}
/// A criterion that can be used when scoring with the TOPSIS algorithm.
+#[cfg_attr(feature = "lab", derive(Debug, Clone))]
pub struct Criterion {
/// Name of the criterion.
name: String,
@@ -48,6 +49,7 @@ impl Criterion {
}
/// A normalized array of `Criterion`.
+#[cfg_attr(feature = "lab", derive(Debug, Clone))]
pub struct Criteria<const N_CRITERIA: usize>([Criterion; N_CRITERIA]);
impl<const N: usize> Criteria<N> {
@@ -85,6 +87,7 @@ impl<const N: usize> Criteria<N> {
}
/// A normalized matrix used for scoring with the TOPSIS algorithm.
+#[cfg_attr(feature = "lab", derive(Clone))]
pub struct Matrix<const N_CRITERIA: usize>(Vec<[f64; N_CRITERIA]>);
impl<const N: usize> Matrix<N> {
@@ -248,7 +251,7 @@ macro_rules! criteria_struct {
#[cfg(feature = "lab")]
pub mod evaluate {
- use super::{score_alternatives, Criteria, IdealAlternatives, Matrix};
+ use super::{differences, l2_norm, score_alternatives, Criteria, IdealAlternatives, Matrix};
/// Dispatched parts of TOPSIS algorithm
pub trait DispatchedTopsis<const N: usize> {
@@ -265,6 +268,82 @@ pub mod evaluate {
) -> f64;
}
+ #[derive(Debug, PartialEq)]
+ pub enum Topsis {
+ Base,
+ MinMaxRelativeDistance,
+ }
+
+ impl<const N: usize> DispatchedTopsis<N> for Topsis {
+ fn normalize(&self, alternatives: &mut Matrix<N>) {
+ match self {
+ Self::Base => {
+ for n in 0..N {
+ let divisor = l2_norm(alternatives.fixed_criterion(n));
+
+ // If every alternative has zero value for the given criterion, keep it like that.
+ if divisor != 0.0 {
+ for value in alternatives.fixed_criterion_mut(n) {
+ *value /= divisor;
+ }
+ }
+ }
+ }
+ Self::MinMaxRelativeDistance => {
+ let m = alternatives.clone();
+
+ for n in 0..N {
+ let col = m.fixed_criterion(n);
+ let min = col
+ .clone()
+ .min_by(|a, b| a.total_cmp(b))
+ .expect("zero alternatives");
+ let max = col
+ .clone()
+ .max_by(|a, b| a.total_cmp(b))
+ .expect("zero alternatives");
+
+ match max - min {
+ 0.0 => {
+ // clamp values to unit interval
+ for value in alternatives.fixed_criterion_mut(n) {
+ *value = 0.0;
+ }
+ }
+ k => {
+ for value in alternatives.fixed_criterion_mut(n) {
+ *value = (*value - min) / k;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ #[allow(private_interfaces)]
+ fn distance(
+ &self,
+ alternative: &[f64; N],
+ criteria: &Criteria<N>,
+ ideals: &IdealAlternatives<N>,
+ ) -> f64 {
+ match self {
+ Self::Base | Self::MinMaxRelativeDistance => {
+ let distance_to_best =
+ l2_norm(criteria.weigh(differences(alternative, &ideals.best)));
+ let distance_to_worst =
+ l2_norm(criteria.weigh(differences(alternative, &ideals.worst)));
+
+ match distance_to_worst + distance_to_best {
+ 0.0 => 0.0,
+ k => distance_to_worst / k,
+ }
+ }
+ }
+ }
+ }
+
/// Score alternatives with specific dispatched `topsis_variant`.
///
/// Calls [`crate::topsis::score_alternatives`] if `topsis_variant` is [`None`]
@@ -292,4 +371,67 @@ pub mod evaluate {
.unwrap_or_else(|err| panic!("scoring alternatives failed: {err}")),
}
}
+
+ #[cfg(test)]
+ mod base_variant_scores_like_present_rollout {
+ use crate::topsis::{score_alternatives, Matrix};
+
+ use super::{
+ super::{Criteria, Criterion},
+ score_alternatives_with_variant, Topsis,
+ };
+
+ use proptest::{array::UniformArrayStrategy, prelude::*};
+
+ const REPEAT_N_TIMES: u32 = 100;
+ const N_CRITERIA: usize = 4;
+
+ const MIN_ALTERNATIVES: usize = 2;
+ const MAX_ALTERNATIVES: usize = 100;
+
+ const MIN_WEIGHT: f64 = -10.0;
+ const MAX_WEIGHT: f64 = 10.0;
+
+ fn criterion() -> impl Strategy<Value = Criterion> {
+ (".*", MIN_WEIGHT..MAX_WEIGHT).prop_map(|(s, w)| Criterion::new(s, w))
+ }
+
+ fn criteria() -> impl Strategy<Value = [Criterion; N_CRITERIA]> {
+ prop::collection::vec(criterion(), N_CRITERIA)
+ .prop_map(|v| unsafe { v.try_into().unwrap_unchecked() })
+ }
+
+ fn matrix() -> impl Strategy<Value = Vec<[f64; N_CRITERIA]>> {
+ prop::collection::vec(
+ UniformArrayStrategy::new(any::<f64>()),
+ MIN_ALTERNATIVES..MAX_ALTERNATIVES,
+ )
+ }
+
+ fn test_case_err(err: impl ToString) -> TestCaseError {
+ TestCaseError::fail(err.to_string())
+ }
+
+ proptest! {
+ #![proptest_config(ProptestConfig {
+ failure_persistence: None,
+ cases: REPEAT_N_TIMES,
+ ..ProptestConfig::default()
+ })]
+
+
+ #[test]
+ fn shrink_different_winners(cs in criteria(), matrix in matrix()) {
+ let criteria = Criteria::new(cs).map_err(test_case_err)?;
+
+ let lhs = Matrix::new(matrix.clone())
+ .and_then(|matrix| score_alternatives(&matrix, &criteria.clone()))
+ .map_err(test_case_err)?;
+ let rhs = score_alternatives_with_variant(Some(&Topsis::Base), matrix, &criteria);
+
+ assert_eq!(lhs, rhs);
+ }
+
+ }
+ }
}
--
2.47.3
^ permalink raw reply [flat|nested] 4+ messages in thread* [RFC proxmox 3/3] resource-scheduling: evaluate static scheduler variants
2026-03-06 8:20 [RFC proxmox 0/3] evaluate static scheduler variants Dominik Rusovac
2026-03-06 8:20 ` [RFC proxmox 1/3] resource-scheduling: add lab feature Dominik Rusovac
2026-03-06 8:20 ` [RFC proxmox 2/3] resource-scheduling: add {topsis,pve_static}-variants with basic proptests Dominik Rusovac
@ 2026-03-06 8:20 ` Dominik Rusovac
2 siblings, 0 replies; 4+ messages in thread
From: Dominik Rusovac @ 2026-03-06 8:20 UTC (permalink / raw)
To: pve-devel
This hacky diff was used to evaluate several variants of the static
scheduler. In particular, results of proptests were pretty printed and
compared in the command line.
Might come in handy for future experiments/evaluations.
Signed-off-by: Dominik Rusovac <d.rusovac@proxmox.com>
---
proxmox-resource-scheduling/src/pve_static.rs | 60 ++-
.../tests/pve_static.rs | 495 ++++++++++++++++++
2 files changed, 542 insertions(+), 13 deletions(-)
create mode 100644 proxmox-resource-scheduling/tests/pve_static.rs
diff --git a/proxmox-resource-scheduling/src/pve_static.rs b/proxmox-resource-scheduling/src/pve_static.rs
index 23e49656..f0c772c7 100644
--- a/proxmox-resource-scheduling/src/pve_static.rs
+++ b/proxmox-resource-scheduling/src/pve_static.rs
@@ -5,7 +5,7 @@ use crate::topsis;
#[derive(Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
-#[cfg_attr(feature = "lab", derive(Debug))]
+#[cfg_attr(feature = "lab", derive(Debug, PartialEq))]
/// Static usage information of a node.
pub struct StaticNodeUsage {
/// Hostname of the node.
@@ -249,6 +249,37 @@ pub mod evaluate {
}
}
+ pub fn imbalance(
+ target_index: usize,
+ nodes: &[StaticNodeUsage],
+ service: &StaticServiceUsage,
+ ) -> f64 {
+ let len = nodes.len();
+ let mut xs = vec![];
+
+ for (index, node) in nodes.iter().enumerate() {
+ let new_cpu = if index == target_index {
+ add_cpu_usage(node.cpu, node.maxcpu as f64, service.maxcpu)
+ } else {
+ node.cpu
+ } / (node.maxcpu as f64);
+
+ let new_mem = if index == target_index {
+ node.mem + service.maxmem
+ } else {
+ node.mem
+ } as f64
+ / node.maxmem as f64;
+
+ xs.push((new_cpu + new_mem) / 2.0);
+ }
+
+ let mean = xs.iter().sum::<f64>() / len as f64;
+ let sd = (xs.iter().map(|x| (x - mean).powi(2)).sum::<f64>() / len as f64).sqrt();
+
+ sd / mean
+ }
+
#[cfg(test)]
mod base_variant_scores_like_present_rollout {
use crate::{
@@ -270,23 +301,26 @@ pub mod evaluate {
const MAX_CPU: usize = 32;
const MAX_MEM: usize = 406;
- fn node() -> impl Strategy<Value = StaticNodeUsage> {
- (".*", 0.0..(MAX_CPU as f64), 0..MAX_MEM).prop_map(|(name, cpu, mem)| StaticNodeUsage {
- name,
- cpu,
- maxcpu: MAX_CPU,
- mem,
- maxmem: MAX_MEM,
- })
- }
-
fn service() -> impl Strategy<Value = StaticServiceUsage> {
- (0.0..(MAX_CPU as f64), 0..MAX_MEM)
+ (1.0..(MAX_CPU as f64), 1..MAX_MEM)
.prop_map(|(maxcpu, maxmem)| StaticServiceUsage { maxcpu, maxmem })
}
fn nodes() -> impl Strategy<Value = Vec<StaticNodeUsage>> {
- prop::collection::vec(node(), MIN_NODES..MAX_NODES)
+ prop::collection::vec((0.0..(MAX_CPU as f64), 0..MAX_MEM), MIN_NODES..MAX_NODES)
+ .prop_map(move |resources| {
+ resources
+ .into_iter()
+ .enumerate()
+ .map(|(i, (cpu, mem))| StaticNodeUsage {
+ name: format!("node{i}"),
+ cpu,
+ maxcpu: MAX_CPU,
+ mem,
+ maxmem: MAX_MEM,
+ })
+ .collect()
+ })
}
fn test_case_err(err: impl ToString) -> TestCaseError {
diff --git a/proxmox-resource-scheduling/tests/pve_static.rs b/proxmox-resource-scheduling/tests/pve_static.rs
new file mode 100644
index 00000000..92f6d17b
--- /dev/null
+++ b/proxmox-resource-scheduling/tests/pve_static.rs
@@ -0,0 +1,495 @@
+#[cfg(feature = "lab")]
+mod skewed {
+ //! This test compares several variants on skewed node stats
+ use proxmox_resource_scheduling::{
+ pve_static::{
+ evaluate::{
+ imbalance, score_nodes_to_start_service_with_variant, StaticResourceScheduling,
+ },
+ StaticNodeUsage, StaticServiceUsage,
+ },
+ topsis::evaluate::Topsis,
+ };
+ use std::{fmt::Debug, sync::LazyLock};
+
+ use proptest::prelude::*;
+
+ fn print_table(
+ input: &[impl Evaluate],
+ nodes: &[StaticNodeUsage],
+ service: &StaticServiceUsage,
+ ) {
+ let delim = " ";
+
+ let (result_names, results) = (
+ input.iter().map(|x| x.name()).collect::<Vec<_>>(),
+ input
+ .iter()
+ .map(|x| x.run(nodes, service))
+ .collect::<Vec<_>>(),
+ );
+
+ let (service_cpu, service_mem) = (service.maxcpu, service.maxmem);
+
+ eprintln!();
+ eprint!(
+ "{:<15}{delim}{:>10}{delim}{:>10}{delim}{:>10}{delim}{:>10}{delim}{:>10}",
+ "name",
+ format!("cpu+{service_cpu:.2}"),
+ "maxcpu",
+ format!("mem+{service_mem}"),
+ "maxmem",
+ "imbalance"
+ );
+ for x in &result_names {
+ eprint!("{delim}{:>10}", x.chars().take(10).collect::<String>());
+ }
+ eprintln!();
+
+ eprint!(
+ "{:-<15}{delim}{:->10}{delim}{:->10}{delim}{:->10}{delim}{:->10}{delim}{:->10}",
+ "", "", "", "", "", ""
+ );
+ for _ in result_names {
+ eprint!("{delim}{:->10}", "");
+ }
+ eprintln!();
+
+ let sorted_results = results
+ .iter()
+ .map(|result| {
+ let mut xs = result.to_vec();
+ xs.sort_by(|(_, a), (_, b)| b.total_cmp(a));
+ xs
+ })
+ .collect::<Vec<_>>();
+
+ let k = sorted_results.len();
+
+ nodes.iter().enumerate().for_each(|(i, n)| {
+ let pivot = &n.name;
+ let scores = sorted_results
+ .iter()
+ .filter_map(|result| result.iter().find(|(n, _)| n == pivot).map(|x| x.1))
+ .collect::<Vec<_>>();
+ let ranks = sorted_results
+ .iter()
+ .filter_map(|result| result.iter().position(|(n, _)| n == pivot).map(|x| x + 1))
+ .collect::<Vec<_>>();
+
+ if let Some(node) = nodes.iter().find(|n| n.name == *pivot) {
+ eprint!(
+ "{:<15}{delim}{:>10.2}{delim}{:>10}{delim}{:>10}{delim}{:>10}{delim}{:>10.2}",
+ node.name,
+ node.cpu,
+ node.maxcpu,
+ node.mem,
+ node.maxmem,
+ imbalance(i, nodes, service)
+ );
+ for j in 0..k {
+ let s = match ranks[j] {
+ 1 => format!("\x1B[30m\x1B[1;{}m{:.3}:1\x1B[0m", (41 + j) % 47, scores[j]),
+ n => format!("\x1B[37m\x1B[0;{}m{:.3}:{n}\x1B[0m", 37, scores[j]),
+ };
+ eprint!("{delim}{s:>26}");
+ }
+ eprintln!();
+ }
+ });
+ }
+
+ static NODES: LazyLock<[StaticNodeUsage; 4]> = LazyLock::new(|| {
+ [
+ StaticNodeUsage {
+ name: "node1".to_owned(),
+ cpu: 2.0 + 32.0,
+ maxcpu: 32,
+ mem: 2 + 8,
+ maxmem: 406,
+ },
+ StaticNodeUsage {
+ name: "node2".to_owned(),
+ cpu: 2.0,
+ maxcpu: 32,
+ mem: 400,
+ maxmem: 406,
+ },
+ StaticNodeUsage {
+ name: "node4".to_owned(),
+ cpu: 2.0 + 32.0,
+ maxcpu: 32,
+ mem: 32 + 8,
+ maxmem: 406,
+ },
+ StaticNodeUsage {
+ name: "node5".to_owned(),
+ cpu: 2.0 + 32.0,
+ maxcpu: 32,
+ mem: 2 + 8,
+ maxmem: 406,
+ },
+ ]
+ });
+
+ static SERVICE: StaticServiceUsage = StaticServiceUsage {
+ maxcpu: 32.0,
+ maxmem: 21,
+ };
+
+ trait Evaluate {
+ fn run(
+ &self,
+ nodes: &[StaticNodeUsage],
+ service: &StaticServiceUsage,
+ ) -> Vec<(String, f64)>;
+ fn name(&self) -> String;
+ }
+
+ #[derive(Clone, Debug)]
+ enum Candidate {
+ Base,
+ MinMax,
+ MoreMaxCpu(usize),
+ }
+
+ impl Evaluate for Candidate {
+ fn run(
+ &self,
+ nodes: &[StaticNodeUsage],
+ service: &StaticServiceUsage,
+ ) -> Vec<(String, f64)> {
+ match self {
+ Self::Base => score_nodes_to_start_service_with_variant(
+ nodes,
+ service,
+ None::<&Topsis>,
+ None::<&StaticResourceScheduling>,
+ ),
+ Self::MinMax => score_nodes_to_start_service_with_variant(
+ nodes,
+ service,
+ Some(&Topsis::MinMaxRelativeDistance),
+ Some(&StaticResourceScheduling::Base),
+ ),
+ Self::MoreMaxCpu(n) => score_nodes_to_start_service_with_variant(
+ nodes,
+ service,
+ None::<&Topsis>,
+ Some(&StaticResourceScheduling::RmsNTimesMoreMaxcpu(*n)),
+ ),
+ }
+ }
+
+ fn name(&self) -> String {
+ match self {
+ Candidate::Base => "base".to_owned(),
+ Candidate::MinMax => "minmax".to_owned(),
+ Candidate::MoreMaxCpu(n) => format!("{n}xmaxcpu"),
+ }
+ }
+ }
+
+ #[test]
+ fn comparison_single() {
+ print_table(
+ &[
+ Candidate::Base,
+ Candidate::MinMax,
+ Candidate::MoreMaxCpu(2),
+ Candidate::MoreMaxCpu(8),
+ Candidate::MoreMaxCpu(10),
+ Candidate::MoreMaxCpu(35),
+ ],
+ NODES.as_slice(),
+ &SERVICE,
+ );
+ }
+
+ const REPEAT_N_TIMES: u32 = 300;
+
+ const MIN_NODES: usize = 2;
+ const MAX_NODES: usize = 40;
+
+ const MAX_CPU: usize = 32;
+ const MAX_MEM: usize = 406;
+
+ fn service() -> impl Strategy<Value = StaticServiceUsage> {
+ (1.0..(MAX_CPU as f64), 1..MAX_MEM)
+ .prop_map(|(maxcpu, maxmem)| StaticServiceUsage { maxcpu, maxmem })
+ }
+
+ fn nodes() -> impl Strategy<Value = Vec<StaticNodeUsage>> {
+ prop::collection::vec((0.0..(MAX_CPU as f64), 0..MAX_MEM), MIN_NODES..MAX_NODES).prop_map(
+ move |resources| {
+ resources
+ .into_iter()
+ .enumerate()
+ .map(|(i, (cpu, mem))| StaticNodeUsage {
+ name: format!("node{i}"),
+ cpu,
+ maxcpu: MAX_CPU,
+ mem,
+ maxmem: MAX_MEM,
+ })
+ .collect()
+ },
+ )
+ }
+
+ proptest! {
+ #![proptest_config(ProptestConfig {
+ failure_persistence: None,
+ cases: REPEAT_N_TIMES,
+ ..ProptestConfig::default()
+ })]
+
+ //#[test]
+ fn minmax_is_not_last(nodes in nodes(), service in service()) {
+ let mut scores = vec![];
+
+ for c in [
+ Candidate::Base,
+ Candidate::MinMax,
+ Candidate::MoreMaxCpu(2),
+ Candidate::MoreMaxCpu(8),
+ Candidate::MoreMaxCpu(10),
+ Candidate::MoreMaxCpu(35),
+ ] {
+ let mut score = 0.0;
+
+ let mut result = c.run(&nodes, &service);
+ result.sort_by(|(_, x), (_, y)| y.total_cmp(x));
+
+ if let Some(node) = result
+ .first()
+ .and_then(|(winner, _)| nodes.iter().find(|n| n.name == *winner))
+ {
+ if let Some(imbalance) = nodes
+ .iter()
+ .position(|n| n == node)
+ .map(|i| imbalance(i, &nodes, &service))
+ {
+ score += imbalance;
+
+ if (node.cpu + service.maxcpu) > node.maxcpu as f64 {
+ score += 0.5;
+ }
+ if (node.mem + service.maxmem) > node.maxmem {
+ score += 1.0;
+ }
+
+ scores.push((c.name(), score, node, imbalance));
+ };
+ }
+
+ }
+
+ scores.sort_by(|(_, x,_,_), (_, y,_,_)| y.total_cmp(x));
+
+ if let Some((a, b,_,_)) = scores.first() {
+ dbg!(&scores);
+ if scores
+ .iter()
+ .any(|(_, x,_,_)| x != b) {
+ assert!(*a != Candidate::MinMax.name())
+ }
+ }
+ }
+
+
+ #[test]
+ fn comparison_multiple(nodes in nodes(), service in service()) {
+ print_table(
+ &[
+ Candidate::Base,
+ Candidate::MinMax,
+ Candidate::MoreMaxCpu(2),
+ Candidate::MoreMaxCpu(8),
+ Candidate::MoreMaxCpu(10),
+ Candidate::MoreMaxCpu(35),
+ ],
+ &nodes,
+ &service
+ );
+ }
+ }
+}
+
+#[cfg(feature = "lab")]
+#[allow(dead_code)]
+mod minmax_neq_35xcpu {
+ //! [`crate::skewed_stats::comparison`] suggests that "minmax" and "35xcpu" make similar
+ //! decisions on nodes with skewed stats.
+ //!
+ //! This proptest shrinks the search space to find cases where "minmax" and "35xcpu" do not
+ //! agree on a winner.
+ use proptest::prelude::*;
+ use proxmox_resource_scheduling::{
+ pve_static::{
+ evaluate::{
+ imbalance, score_nodes_to_start_service_with_variant, StaticResourceScheduling,
+ },
+ StaticNodeUsage, StaticServiceUsage,
+ },
+ topsis::evaluate::Topsis,
+ };
+
+ fn print_table(
+ input: &[(&str, &[(String, f64)])],
+ nodes: &[StaticNodeUsage],
+ service: &StaticServiceUsage,
+ ) {
+ let delim = " ";
+
+ let (result_names, results) = {
+ let (mut lhs, mut rhs) = (vec![], vec![]);
+ input.iter().for_each(|(l, r)| {
+ lhs.push(l);
+ rhs.push(r)
+ });
+ (lhs, rhs)
+ };
+
+ let (service_cpu, service_mem) = (service.maxcpu, service.maxmem);
+
+ eprintln!();
+ eprint!(
+ "{:<15}{delim}{:>10}{delim}{:>10}{delim}{:>10}",
+ "name",
+ format!("cpu+{service_cpu:.2}"),
+ format!("mem+{service_mem}"),
+ "imbalance"
+ );
+ for x in &result_names {
+ eprint!("{delim}{:>10}", x.chars().take(10).collect::<String>());
+ }
+ eprintln!();
+
+ eprint!(
+ "{:-<15}{delim}{:->10}{delim}{:->10}{delim}{:->10}",
+ "", "", "", ""
+ );
+ for _ in result_names {
+ eprint!("{delim}{:->10}", "");
+ }
+ eprintln!();
+
+ let sorted_results = results
+ .iter()
+ .map(|result| {
+ let mut xs = result.to_vec();
+ xs.sort_by(|(_, a), (_, b)| b.total_cmp(a));
+ xs
+ })
+ .collect::<Vec<_>>();
+
+ let k = sorted_results.len();
+
+ nodes.iter().enumerate().for_each(|(i, n)| {
+ let pivot = &n.name;
+ let scores = sorted_results
+ .iter()
+ .filter_map(|result| result.iter().find(|(n, _)| n == pivot).map(|x| x.1))
+ .collect::<Vec<_>>();
+ let ranks = sorted_results
+ .iter()
+ .filter_map(|result| result.iter().position(|(n, _)| n == pivot).map(|x| x + 1))
+ .collect::<Vec<_>>();
+
+ if let Some(node) = nodes.iter().find(|n| n.name == *pivot) {
+ eprint!(
+ "{:<15}{delim}{:>10.2}{delim}{:>10}{delim}{:>10.2}",
+ node.name,
+ node.cpu,
+ node.mem,
+ imbalance(i, nodes, service)
+ );
+ for i in 0..k {
+ let s = format!(
+ "\x1B[{}m{:.3}:{}\x1B[0m",
+ (31 + i) % 37,
+ scores[i],
+ ranks[i]
+ );
+ eprint!("{delim}{s:>19}");
+ }
+ eprintln!();
+ }
+ });
+ }
+
+ const REPEAT_N_TIMES: u32 = 100;
+
+ const MIN_NODES: usize = 2;
+ const MAX_NODES: usize = 40;
+
+ const MAX_CPU: usize = 32;
+ const MAX_MEM: usize = 406;
+
+ fn service() -> impl Strategy<Value = StaticServiceUsage> {
+ (0.0..(MAX_CPU as f64), 0..MAX_MEM)
+ .prop_map(|(maxcpu, maxmem)| StaticServiceUsage { maxcpu, maxmem })
+ }
+
+ fn nodes() -> impl Strategy<Value = Vec<StaticNodeUsage>> {
+ prop::collection::vec((0.0..(MAX_CPU as f64), 0..MAX_MEM), MIN_NODES..MAX_NODES).prop_map(
+ move |resources| {
+ resources
+ .into_iter()
+ .enumerate()
+ .map(|(i, (cpu, mem))| StaticNodeUsage {
+ name: format!("node{i}"),
+ cpu,
+ maxcpu: MAX_CPU,
+ mem,
+ maxmem: MAX_MEM,
+ })
+ .collect()
+ },
+ )
+ }
+
+ proptest! {
+ #![proptest_config(ProptestConfig {
+ failure_persistence: None,
+ cases: REPEAT_N_TIMES,
+ ..ProptestConfig::default()
+ })]
+
+ //#[test]
+ fn shrink_different_winners(nodes in nodes(), service in service()) {
+ let mut lhs = score_nodes_to_start_service_with_variant(
+ &nodes,
+ &service,
+ Some(&Topsis::MinMaxRelativeDistance),
+ Some(&StaticResourceScheduling::Base),
+ );
+
+ let mut rhs = score_nodes_to_start_service_with_variant(
+ &nodes,
+ &service,
+ None::<&Topsis>,
+ Some(&StaticResourceScheduling::RmsNTimesMoreMaxcpu(35)),
+ );
+
+ print_table(&[("minmax", &lhs), ("35xcpu", &rhs)], &nodes, &service);
+
+ lhs.sort_by(|(_, x), (_, y)| y.total_cmp(x));
+ rhs.sort_by(|(_, x), (_, y)| y.total_cmp(x));
+
+ if let Some((winner_lhs, winner_rhs)) = lhs
+ .first()
+ .and_then(|node| nodes.iter().find(|n| n.name == node.0))
+ .zip(
+ rhs.first()
+ .and_then(|node| nodes.iter().find(|n| n.name == node.0)),
+ )
+ {
+ assert_eq!(winner_lhs, winner_rhs);
+ }
+
+ }
+
+ }
+}
--
2.47.3
^ permalink raw reply [flat|nested] 4+ messages in thread