[PATCH proxmox 05/15] resource-scheduling: scheduler: proptest weights

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

Introduce proptests with constants to control scheduler proptests and
functions implementing useful proptest strategies.

Use per-method `mod`s to make deliberate testing easier, e.g., executing
`cargo test bruteforce` to run bruteforce (prop)tests only.

For each method (bruteforce, TOPSIS), respectively, add proptests:
- test_weight_scale_invariance: test that only weight ratio matters, not
  their absolute magnitudes; and
- test_zero_cpu_weight_discards_cpu_load: cpu weight of 0 discards CPU
  load (symmetric test discarding memory usage is omitted).

Signed-off-by: Dominik Rusovac <d.rusovac@proxmox.com>
---
 proxmox-resource-scheduling/src/scheduler.rs | 343 +++++++++++++++++++
 1 file changed, 343 insertions(+)

diff --git a/proxmox-resource-scheduling/src/scheduler.rs b/proxmox-resource-scheduling/src/scheduler.rs
index 0690385d..3c4c8d87 100644
--- a/proxmox-resource-scheduling/src/scheduler.rs
+++ b/proxmox-resource-scheduling/src/scheduler.rs
@@ -429,6 +429,27 @@ impl Scheduler {
 mod tests {
     use super::*;
 
+    use proptest::prelude::*;
+    use std::ops::Range;
+
+    const MIN_NODES: usize = 3;
+    const MAX_NODES: usize = 36;
+
+    const MIN_CPU: usize = 2;
+    const MIN_MEM: usize = 2;
+    const MAX_CPU: usize = 128;
+    const MAX_MEM: usize = 256;
+
+    const MIN_WEIGHT: usize = 1;
+    const MAX_WEIGHT: usize = 1_000;
+
+    const MIN_CONSTANT: usize = 1;
+    const MAX_CONSTANT: usize = 1_000;
+
+    const REPEAT_PROPTEST_N_TIMES: u32 = 256; // proptest's default
+
+    const EPSILON: f64 = 1e-9;
+
     #[test]
     fn test_scored_migration_order() {
         let migration1 = ScoredMigration::new(
@@ -528,4 +549,326 @@ mod tests {
         assert_eq!(heap.pop(), Some(Reverse(migration2)));
         assert_eq!(heap.pop(), Some(Reverse(migration3)));
     }
+
+    /// Strategy to generate `n` random nodes with stats bound by `max_cpu` and `max_mem`.
+    pub fn nodes_strategy(
+        n: usize,
+        max_cpu: usize,
+        max_mem: usize,
+    ) -> impl Strategy<Value = Vec<NodeUsage>> {
+        prop::collection::vec((0..max_cpu + 1, 0..max_mem + 1), n).prop_map(
+            move |computational_resources| {
+                computational_resources
+                    .into_iter()
+                    .enumerate()
+                    .map(|(i, (cpu, mem))| NodeUsage {
+                        name: format!("node{i}"),
+                        stats: NodeStats {
+                            cpu: cpu as f64,
+                            maxcpu: max_cpu,
+                            mem,
+                            maxmem: max_mem,
+                        },
+                    })
+                    .collect()
+            },
+        )
+    }
+
+    /// Strategy to generate a random number in `n_range` of migration candidates between `nodes`.
+    /// Resource stats are bound by `max_cpu` and `max_mem`.
+    fn candidates_strategy(
+        n_range: impl Into<proptest::collection::SizeRange>,
+        max_cpu: usize,
+        max_mem: usize,
+        nodes: Vec<NodeUsage>,
+    ) -> impl Strategy<Value = Vec<MigrationCandidate>> {
+        let k = nodes.len();
+
+        prop::collection::vec((0..max_cpu, 0..max_mem, 0..k, 0..k), n_range).prop_map(
+            move |computational_resources| {
+                computational_resources
+                    .into_iter()
+                    .enumerate()
+                    .map(
+                        |(i, (cpu, mem, source_idx, target_idx))| MigrationCandidate {
+                            migration: Migration {
+                                sid: format!("vm:10{i}"),
+                                source_node: nodes[source_idx].name.clone(),
+                                target_node: nodes[target_idx].name.clone(),
+                            },
+                            stats: ResourceStats {
+                                cpu: cpu as f64,
+                                maxcpu: max_cpu as f64,
+                                mem,
+                                maxmem: max_mem,
+                            },
+                        },
+                    )
+                    .filter(|candidate| {
+                        candidate.migration.source_node != candidate.migration.target_node
+                    })
+                    .collect()
+            },
+        )
+    }
+
+    /// Strategy to generate:
+    /// - a random number n in `n_nodes_range` of nodes
+    /// - a random number between 1 and n * (n - 1) of migration candidates between the generated
+    ///   nodes
+    ///
+    /// The stats of nodes and migration candidates are bound by random numbers in `cpu_range` and
+    /// `mem_range`, respectively.
+    fn scenario_strategy(
+        cpu_range: Range<usize>,
+        mem_range: Range<usize>,
+        n_nodes_range: Range<usize>,
+    ) -> impl Strategy<Value = (Vec<NodeUsage>, Vec<MigrationCandidate>)> {
+        (cpu_range, mem_range).prop_flat_map(move |(max_cpu, max_mem)| {
+            n_nodes_range
+                .clone()
+                .prop_filter("cluster size must be odd", |n| n % 2 == 1)
+                .prop_flat_map(move |n_nodes| {
+                    nodes_strategy(n_nodes, max_cpu, max_mem).prop_flat_map(move |nodes| {
+                        let max_candidates = n_nodes * (n_nodes - 1);
+
+                        candidates_strategy(1..=max_candidates, max_cpu, max_mem, nodes.clone())
+                            .prop_map(move |candidates| (nodes.clone(), candidates))
+                    })
+                })
+        })
+    }
+
+    mod bruteforce {
+        use super::*;
+
+        mod weights {
+            use super::*;
+
+            proptest! {
+                #![proptest_config(ProptestConfig {
+                    cases: REPEAT_PROPTEST_N_TIMES,
+                    ..ProptestConfig::default()
+                })]
+
+                /// Test that the achievable scores are completely unaffected by uniformly scaling
+                /// both weights; only the weights' ratio matters.
+                #[test]
+                fn test_weight_scale_invariance(
+                    cpu_weight in MIN_WEIGHT..MAX_WEIGHT,
+                    mem_weight in MIN_WEIGHT..MAX_WEIGHT,
+                    k in MIN_CONSTANT..MAX_CONSTANT,
+                    (nodes, candidates) in
+                        scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES)
+                ) {
+                    let scheduler = Scheduler::from_nodes(nodes);
+                    let n = candidates.len();
+
+                    scheduler
+                        .score_best_balancing_migration_candidates(
+                            candidates.clone(),
+                            n,
+                            cpu_weight,
+                            mem_weight,
+                        )
+                        .iter()
+                        .zip(
+                            scheduler
+                                .score_best_balancing_migration_candidates(
+                                    candidates.clone(),
+                                    n,
+                                    k * cpu_weight,
+                                    k * mem_weight,
+                                )
+                                .iter(),
+                        )
+                        .for_each(|(lhs, rhs)| {
+                            assert!(
+                                (lhs.score - rhs.score).abs() < EPSILON,
+                                "equally ranked migrations {:?} and {:?} must have the same score",
+                                lhs,
+                                rhs,
+                            );
+                        });
+                }
+
+                /// Test that with a `cpu_weight` of 0 the score for each scored migration should
+                /// match an imbalance computed directly from [`NodeStats::mem_load()`] alone.
+                #[test]
+                fn test_zero_cpu_weight_discards_cpu_load(
+                    mem_weight in MIN_WEIGHT..MAX_WEIGHT,
+                    (nodes, candidates) in
+                        scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES)
+                ) {
+                    let cpu_weight = 0;
+
+                    Scheduler::from_nodes(nodes.clone())
+                        .score_best_balancing_migration_candidates(
+                            candidates.clone(),
+                            candidates.len(),
+                            cpu_weight,
+                            mem_weight,
+                        )
+                        .iter()
+                        .filter_map(|scored_migration| {
+                            candidates
+                                .iter()
+                                .find(|c| c.migration.sid == scored_migration.migration.sid)
+                                .map(|c| (scored_migration, c))
+                        })
+                        .for_each(|(scored_migration, candidate)| {
+                            let reference_imbalance = calculate_node_imbalance(&nodes, |node| {
+                                node_stats_after_migration(candidate, node).mem_load()
+                            });
+
+                            assert!(
+                                (scored_migration.score - reference_imbalance).abs() < EPSILON
+                            );
+                        })
+                }
+            }
+        }
+    }
+
+    mod topsis {
+        use super::*;
+
+        /// Strategy producing two scenarios using [`super::scenario_strategy`] that are identical
+        /// in every memory-related field and in topology but have varying CPU fields.
+        #[allow(clippy::type_complexity)]
+        fn two_scenarios_with_varying_cpu_stats_strategy(
+            cpu_range: Range<usize>,
+            mem_range: Range<usize>,
+            n_nodes_range: Range<usize>,
+        ) -> impl Strategy<
+            Value = (
+                (Vec<NodeUsage>, Vec<MigrationCandidate>),
+                (Vec<NodeUsage>, Vec<MigrationCandidate>),
+            ),
+        > {
+            let max_possible_nodes = n_nodes_range.end - 1; // Range<T> is exclusive
+            let max_possible_candidates = max_possible_nodes * (max_possible_nodes - 1);
+            let cpu_pool_bound = cpu_range.end;
+
+            (
+                scenario_strategy(cpu_range, mem_range, n_nodes_range),
+                prop::collection::vec(0usize..cpu_pool_bound + 1, max_possible_nodes),
+                prop::collection::vec(0usize..cpu_pool_bound, max_possible_candidates),
+            )
+                .prop_map(
+                    move |((nodes, candidates), alt_node_cpu_pool, alt_candidate_cpu_pool)| {
+                        let mut alt_nodes = nodes.clone();
+                        alt_nodes.iter_mut().zip(alt_node_cpu_pool.iter()).for_each(
+                            |(node, &cpu)| {
+                                node.stats.cpu = cpu as f64;
+                            },
+                        );
+
+                        let mut alt_candidates = candidates.clone();
+                        alt_candidates
+                            .iter_mut()
+                            .zip(alt_candidate_cpu_pool.iter())
+                            .for_each(|(candidate, &cpu)| {
+                                candidate.stats.cpu = cpu as f64;
+                            });
+
+                        ((nodes, candidates), (alt_nodes, alt_candidates))
+                    },
+                )
+        }
+
+        proptest! {
+            #![proptest_config(ProptestConfig {
+                cases: REPEAT_PROPTEST_N_TIMES,
+                ..ProptestConfig::default()
+            })]
+
+            /// Test that the achievable scores are completely unaffected by uniformly scaling both
+            /// weights; only the weights' ratio matters.
+            #[test]
+            fn test_weight_scale_invariance(
+                cpu_weight in MIN_WEIGHT..MAX_WEIGHT,
+                mem_weight in MIN_WEIGHT..MAX_WEIGHT,
+                k in MIN_CONSTANT..MAX_CONSTANT,
+                (nodes, candidates) in
+                    scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES)
+            ) {
+                let scheduler = Scheduler::from_nodes(nodes);
+                let n = candidates.len();
+
+                scheduler
+                    .score_best_balancing_migration_candidates_topsis(
+                        &candidates,
+                        n,
+                        cpu_weight,
+                        mem_weight,
+                    )
+                    .unwrap_or_else(|err| panic!("topsis failed with: {err}"))
+                    .iter()
+                    .zip(
+                        scheduler
+                            .score_best_balancing_migration_candidates_topsis(
+                                &candidates,
+                                n,
+                                k * cpu_weight,
+                                k * mem_weight,
+                            )
+                            .unwrap_or_else(|err| panic!("topsis failed with: {err}"))
+                            .iter(),
+                    )
+                    .for_each(|(lhs, rhs)| {
+                        assert!(
+                            (lhs.score - rhs.score).abs() < EPSILON,
+                            "equally ranked migrations {:?} and {:?} must have the same score",
+                            lhs,
+                            rhs,
+                        );
+                    });
+            }
+
+            /// Test that varying CPU stats between two otherwise identical scenarios do not change
+            /// the achievable scores if CPU weight is 0.
+            #[test]
+            fn test_zero_cpu_weight_discards_cpu_load(
+                mem_weight in MIN_WEIGHT..MAX_WEIGHT,
+                ((nodes_a, candidates_a), (nodes_b, candidates_b)) in
+                    two_scenarios_with_varying_cpu_stats_strategy(
+                        MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES
+                    ),
+            ) {
+                let cpu_weight = 0;
+                let n = candidates_a.len();
+
+                Scheduler::from_nodes(nodes_a)
+                    .score_best_balancing_migration_candidates_topsis(
+                        &candidates_a,
+                        n,
+                        cpu_weight,
+                        mem_weight,
+                    )
+                    .unwrap_or_else(|err| panic!("topsis failed with: {err}"))
+                    .iter()
+                    .zip(
+                        Scheduler::from_nodes(nodes_b)
+                            .score_best_balancing_migration_candidates_topsis(
+                                &candidates_b,
+                                n,
+                                cpu_weight,
+                                mem_weight,
+                            )
+                            .unwrap_or_else(|err| panic!("topsis failed with: {err}"))
+                            .iter(),
+                    )
+                    .for_each(|(a, b)| {
+                        assert!(
+                            (a.score - b.score).abs() < EPSILON,
+                            "equally ranked migrations {:?} and {:?} must have the same score",
+                            a,
+                            b,
+                        );
+                    });
+            }
+        }
+    }
 }
-- 
2.47.3