From: Dominik Rusovac <d.rusovac@proxmox.com>
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 [thread overview]
Message-ID: <20261112094437.1951271-9-d.rusovac@proxmox.com> (raw)
In-Reply-To: <20261112094437.1951271-1-d.rusovac@proxmox.com>
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 <d.rusovac@proxmox.com>
---
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<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<prop::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 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<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))
+ })
+ })
+ })
+ }
+
+ /// 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<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(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
next prev parent reply other threads:[~2026-11-12 9:46 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-12 9:44 [RFC PATCH-SERIES cluster/ha-manager/manager/proxmox{,-perl-rs} v2 00/19] fix #7993: implement weighted crs load balancing Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 01/19] resource-scheduling: fix typos Dominik Rusovac
2026-11-19 12:27 ` Daniel Kral
2026-11-12 9:44 ` [PATCH proxmox v2 02/19] resource-scheduling: scheduler: refine score_* docs Dominik Rusovac
2026-11-19 12:27 ` Daniel Kral
2026-11-19 12:47 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 03/19] resource-scheduling: scheduler: abstract post-migration stats logic Dominik Rusovac
2026-11-19 12:28 ` Daniel Kral
2026-11-19 12:47 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 04/19] fix #7993: resource-scheduling: node: add weighted node load Dominik Rusovac
2026-11-19 12:28 ` Daniel Kral
2026-11-19 12:50 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 05/19] resource-scheduling: scheduler: make imbalance with candidate public Dominik Rusovac
2026-11-19 12:41 ` Daniel Kral
2026-11-19 12:52 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 06/19] fix #7993: resource-scheduling: scheduler: add weights Dominik Rusovac
2026-11-19 12:40 ` Daniel Kral
2026-11-19 13:52 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH proxmox v2 07/19] workspace,resource-scheduling: add proptest as dev-dependency Dominik Rusovac
2026-11-12 9:44 ` Dominik Rusovac [this message]
2026-11-12 9:44 ` [PATCH proxmox-perl-rs v2 09/19] fix #7993: pve-rs: resource-scheduling: add scheduler options Dominik Rusovac
2026-11-19 12:45 ` Daniel Kral
2026-11-19 13:28 ` Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-cluster v2 10/19] fix #7993: datacenter config: ad ha-{cpu,mem}-weight crs options Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-manager v2 11/19] ui: form: crs options: make fine-tuning options advanced Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-manager v2 12/19] fix #7993: ui: form: crs options: add weights Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 13/19] manager: remove obsolete argument Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 14/19] manager: rename update_crs_scheduler_mod to update_crs_settings Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 15/19] manager: factor out crs option update helper Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 16/19] manager: log changes to crs settings Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 17/19] sim: hardware: allow changing datacenter settings at runtime Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 18/19] fix #7993: manager,usage: use weights for static and dynamic mode Dominik Rusovac
2026-11-12 9:44 ` [PATCH pve-ha-manager v2 19/19] test: add automatic rebalancing test cases with weights Dominik Rusovac
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261112094437.1951271-9-d.rusovac@proxmox.com \
--to=d.rusovac@proxmox.com \
--cc=pve-devel@lists.proxmox.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox