From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from gate001.proxmox.com (gate001.proxmox.com [IPv6:2a0f:8001:1:32::40]) by lore.proxmox.com (Postfix) with ESMTPS id E08E21FF0B6 for ; Thu, 12 Nov 2026 10:46:46 +0100 (CET) Received: from gate001.proxmox.com (localhost.localdomain [127.0.0.1]) by gate001.proxmox.com (Proxmox) with ESMTP id E0405216BE; Thu, 12 Nov 2026 10:45:32 +0100 (CET) From: Dominik Rusovac To: pve-devel@lists.proxmox.com Subject: [PATCH proxmox v2 08/19] resource-scheduling: scheduler: add property tests for weights Date: Thu, 12 Nov 2026 10:44:26 +0100 Message-ID: <20261112094437.1951271-9-d.rusovac@proxmox.com> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261112094437.1951271-1-d.rusovac@proxmox.com> References: <20261112094437.1951271-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: 1794476685716 X-SPAM-LEVEL: Spam detection results: 0 AWL 0.034 Adjusted score from AWL reputation of From: address DMARC_MISSING 0.1 Missing DMARC policy KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment (newer systems) RCVD_IN_DNSWL_MED -2.3 Sender listed at https://www.dnswl.org/, medium trust 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: 27G6NVA5TUDSPHVG3DCYYQDR6ZYSD77A X-Message-ID-Hash: 27G6NVA5TUDSPHVG3DCYYQDR6ZYSD77A 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: only the ratio of the weights should matter, and a weight of 0 should make the results independent of the respective resource, for any cluster. add property tests that check this on randomly generated clusters and migration candidates, namely that: - for the bruteforce method, uniformly scaling both weights changes neither the number of scored migrations nor the imbalance at each rank, which is compared instead of the migrations themselves, as migrations with nearly equal imbalance may swap places due to rounding - for the bruteforce method, with a CPU weight of 0, the imbalance of each scored migration equals the imbalance computed from the memory load of the nodes alone - for the TOPSIS method, uniformly scaling both weights does not change the node scores for starting a resource - for the TOPSIS method, with a CPU weight of 0, two clusters that only differ in CPU usage result in the same ranked migrations and the same node scores for starting a resource for the TOPSIS method, scale invariance is checked on the node scores for starting a resource. ranked migrations only carry the resulting imbalance, so a swap of two migrations with nearly equal TOPSIS scores due to rounding cannot be told apart from an actual ranking change the tests are grouped in per-method modules, so that, for example, `cargo test bruteforce` runs only the tests of the bruteforce method Signed-off-by: Dominik Rusovac --- Notes: changes since v1: * adapt to weights being a field of Scheduler * compare the imbalance of scored migrations instead of the removed score * check TOPSIS scale invariance on the node scores for starting a resource * check that a TOPSIS CPU weight of 0 results in exactly equal ranked migrations and node scores for starting a resource * reword commit proxmox-resource-scheduling/src/scheduler.rs | 325 +++++++++++++++++++ 1 file changed, 325 insertions(+) diff --git a/proxmox-resource-scheduling/src/scheduler.rs b/proxmox-resource-scheduling/src/scheduler.rs index 75929a14..ce0262c6 100644 --- a/proxmox-resource-scheduling/src/scheduler.rs +++ b/proxmox-resource-scheduling/src/scheduler.rs @@ -425,6 +425,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 PROPTEST_CASES: u32 = 256; // proptest's default + + const EPSILON: f64 = 1e-9; + #[test] fn test_scored_migration_order() { let migration1 = ScoredMigration::new( @@ -471,4 +492,308 @@ mod tests { assert_eq!(heap.pop(), Some(Reverse(migration2))); assert_eq!(heap.pop(), Some(Reverse(migration3))); } + + fn weights(cpu_weight: usize, mem_weight: usize) -> NodeStatsWeights { + let mut weights = NodeStatsWeights::default(); + weights.cpu_weight = cpu_weight as f64; + weights.mem_weight = mem_weight as f64; + + weights + } + + /// Strategy to generate `n` random nodes with stats bound by `max_cpu` and `max_mem`. + fn nodes_strategy( + n: usize, + max_cpu: usize, + max_mem: usize, + ) -> impl Strategy> { + 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, + max_cpu: usize, + max_mem: usize, + nodes: Vec, + ) -> impl Strategy> { + 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 odd number n in `n_nodes_range` of nodes + /// - up to n * (n - 1) 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, + mem_range: Range, + n_nodes_range: Range, + ) -> impl Strategy, Vec)> { + (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)) + }) + }) + }) + } + + /// Strategy to generate two scenarios with [`scenario_strategy`], which are identical in + /// topology and in every memory-related field, but differ in their CPU usage. + #[allow(clippy::type_complexity)] + fn two_scenarios_with_varying_cpu_usage_strategy( + cpu_range: Range, + mem_range: Range, + n_nodes_range: Range, + ) -> impl Strategy< + Value = ( + (Vec, Vec), + (Vec, Vec), + ), + > { + let max_possible_nodes = n_nodes_range.end - 1; // Range 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(0..cpu_pool_bound + 1, max_possible_nodes), + prop::collection::vec(0..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) + .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) + .for_each(|(candidate, cpu)| candidate.stats.cpu = cpu as f64); + + ((nodes, candidates), (alt_nodes, alt_candidates)) + }, + ) + } + + mod bruteforce { + use super::*; + + proptest! { + #![proptest_config(ProptestConfig::with_cases(PROPTEST_CASES))] + + /// Test that uniformly scaling both weights does not change the scored migrations; + /// only the ratio of the weights 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 n = candidates.len(); + + let scored = Scheduler::from_nodes(nodes.clone()) + .with_weights(weights(cpu_weight, mem_weight)) + .score_best_balancing_migration_candidates(candidates.clone(), n); + let scaled = Scheduler::from_nodes(nodes) + .with_weights(weights(k * cpu_weight, k * mem_weight)) + .score_best_balancing_migration_candidates(candidates, n); + + prop_assert_eq!(scored.len(), scaled.len()); + + // compare by rank, as near-equal imbalances may swap places due to rounding + for (lhs, rhs) in scored.iter().zip(scaled.iter()) { + prop_assert!( + (lhs.imbalance - rhs.imbalance).abs() < EPSILON, + "equally ranked migrations {:?} and {:?} must have the same imbalance", + lhs, + rhs, + ); + } + } + + /// Test that with a CPU weight of 0, the imbalance of each scored migration matches + /// the imbalance computed 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 n = candidates.len(); + + let scored = Scheduler::from_nodes(nodes.clone()) + .with_weights(weights(0, mem_weight)) + .score_best_balancing_migration_candidates(candidates.clone(), n); + + prop_assert_eq!(scored.len(), n); + + for scored_migration in scored { + let candidate = candidates + .iter() + .find(|candidate| candidate.migration == scored_migration.migration) + .expect("scored migration must be one of the candidates"); + + let reference_imbalance = calculate_node_imbalance(&nodes, |node| { + node_stats_after_migration(candidate, node).mem_load() + }); + + prop_assert!( + (scored_migration.imbalance - reference_imbalance).abs() < EPSILON, + "migration {:?} must have imbalance {}", + scored_migration, + reference_imbalance, + ); + } + } + } + } + + mod topsis { + use super::*; + + proptest! { + #![proptest_config(ProptestConfig::with_cases(PROPTEST_CASES))] + + /// Test that uniformly scaling both weights does not change the node scores to start + /// a resource; only the ratio of the weights matters. + /// + /// The node scores are compared instead of the ranked migrations, because the latter + /// only expose the imbalance, so near-equal TOPSIS scores that swap places due to + /// rounding could not be told apart from an actual change in the ranking. + #[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.clone()) + .with_weights(weights(cpu_weight, mem_weight)); + let scaled_scheduler = Scheduler::from_nodes(nodes) + .with_weights(weights(k * cpu_weight, k * mem_weight)); + + // use the stats of the generated candidates as resources to start + for candidate in candidates { + let scores = scheduler + .score_nodes_to_start_resource(candidate.stats) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")); + let scaled_scores = scaled_scheduler + .score_nodes_to_start_resource(candidate.stats) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")); + + for ((node, score), (scaled_node, scaled_score)) in + scores.iter().zip(scaled_scores.iter()) + { + prop_assert_eq!(node, scaled_node); + prop_assert!( + (score - scaled_score).abs() < EPSILON, + "node {} must have the same score, got {} and {}", + node, + score, + scaled_score, + ); + } + } + } + + /// Test that with a CPU weight of 0, varying the CPU usage between two otherwise + /// identical scenarios changes neither the ranked migrations nor the node scores to + /// start a resource. + #[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_usage_strategy( + MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES + ), + ) { + let n = candidates_a.len(); + + let scheduler_a = + Scheduler::from_nodes(nodes_a).with_weights(weights(0, mem_weight)); + let scheduler_b = + Scheduler::from_nodes(nodes_b).with_weights(weights(0, mem_weight)); + + // a CPU weight of 0 zeroes out every CPU criterion, so the results are identical + prop_assert_eq!( + scheduler_a + .score_best_balancing_migration_candidates_topsis(&candidates_a, n) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")), + scheduler_b + .score_best_balancing_migration_candidates_topsis(&candidates_b, n) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")), + ); + + for candidate in candidates_a { + prop_assert_eq!( + scheduler_a + .score_nodes_to_start_resource(candidate.stats) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")), + scheduler_b + .score_nodes_to_start_resource(candidate.stats) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")), + ); + } + } + } + } } -- 2.47.3