[RFC proxmox 2/3] resource-scheduling: add {topsis,pve_static}-variants with basic proptests

[Dominik Rusovac <d.rusovac@proxmox.com>]

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