From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68]) by lore.proxmox.com (Postfix) with ESMTPS id 6113E1FF13E for ; Fri, 06 Mar 2026 09:19:56 +0100 (CET) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id D388F19F19; Fri, 6 Mar 2026 09:21:02 +0100 (CET) From: Dominik Rusovac To: pve-devel@lists.proxmox.com Subject: [RFC proxmox 2/3] resource-scheduling: add {topsis,pve_static}-variants with basic proptests Date: Fri, 6 Mar 2026 09:20:45 +0100 Message-ID: <20260306082046.34311-3-d.rusovac@proxmox.com> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260306082046.34311-1-d.rusovac@proxmox.com> References: <20260306082046.34311-1-d.rusovac@proxmox.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Bm-Milter-Handled: 55990f41-d878-4baa-be0a-ee34c49e34d2 X-Bm-Transport-Timestamp: 1772785224220 X-SPAM-LEVEL: Spam detection results: 0 AWL 0.272 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DMARC_MISSING 0.1 Missing DMARC policy KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment RCVD_IN_MSPIKE_H2 0.001 Average reputation (+2) SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record Message-ID-Hash: CJQ77NZSSQLVTO5YTKP6CWFJHGQWX3K2 X-Message-ID-Hash: CJQ77NZSSQLVTO5YTKP6CWFJHGQWX3K2 X-MailFrom: d.rusovac@proxmox.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; loop; banned-address; emergency; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.10 Precedence: list List-Id: Proxmox VE development discussion List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: Add concrete variants to evaluate. Proptest against current implementation, for the sake of a basic proptest demo. Signed-off-by: Dominik Rusovac --- 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>( + nodes: &[T], + service: &StaticServiceUsage, + bloat_maxcpu_by: Option, + ) -> 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::>() + } + + impl DispatchedStaticResourceScheduler for StaticResourceScheduling { + fn preprocess>( + &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 { + (".*", 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 { + (0.0..(MAX_CPU as f64), 0..MAX_MEM) + .prop_map(|(maxcpu, maxmem)| StaticServiceUsage { maxcpu, maxmem }) + } + + fn nodes() -> impl Strategy> { + 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) -> 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([Criterion; N_CRITERIA]); impl Criteria { @@ -85,6 +87,7 @@ impl Criteria { } /// A normalized matrix used for scoring with the TOPSIS algorithm. +#[cfg_attr(feature = "lab", derive(Clone))] pub struct Matrix(Vec<[f64; N_CRITERIA]>); impl Matrix { @@ -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 { @@ -265,6 +268,82 @@ pub mod evaluate { ) -> f64; } + #[derive(Debug, PartialEq)] + pub enum Topsis { + Base, + MinMaxRelativeDistance, + } + + impl DispatchedTopsis for Topsis { + fn normalize(&self, alternatives: &mut Matrix) { + 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, + ideals: &IdealAlternatives, + ) -> 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 { + (".*", MIN_WEIGHT..MAX_WEIGHT).prop_map(|(s, w)| Criterion::new(s, w)) + } + + fn criteria() -> impl Strategy { + prop::collection::vec(criterion(), N_CRITERIA) + .prop_map(|v| unsafe { v.try_into().unwrap_unchecked() }) + } + + fn matrix() -> impl Strategy> { + prop::collection::vec( + UniformArrayStrategy::new(any::()), + 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