[RFC PATCH-SERIES cluster/ha-manager/manager/proxmox{,-perl-rs} 00/15] fix #7993: implement weighted auto rebalancing

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

Let users express a preference for prioritizing CPU load balancing over memory
usage balancing, or vice versa, by means of weights.

Tested basic functionality in virtualized 3-node cluster. Added property tests, unit 
tests and tests to document efficacy of weighted auto reblalancing.

Will follow this up with a separate series updating CRS docs accordingly, once
this one is considered.

# TL;DR
This series enables weighting CPU load against memory usage when computing node
load. The node load becomes the weighted arithmetic mean of both (see Details).
Only the weight ratio matters, and equal weights reproduce the old plain mean.
This addresses cases where the load balancer didn't act because a blended load
imbalance looked fine even though the cluster was rather imbalanced in CPU load
or memory usage alone.

## Bruteforce
- a higher weight on a resource steers migrations toward balancing that
  resource; this is a tendency, not a guarantee
- a migration that leaves the variance of both resources higher can still look
  better balanced, because CPU and memory deviations can cancel out (negative
  covariance); weights don't disable this
- load imbalance values computed with different weights, and the thresholds
  they are compared against, aren't directly comparable

## TOPSIS
- only the average CPU and average memory criterion weights are exposed
- the weights of the highest CPU and highest memory criteria are fixed at twice
  those of the respective average criteria, which keeps the ratio from [0]

# Details
A weight is any non-negative integer. Weights are blended into the computation
of node loads. The load of a node is currently the arithmetic mean [1] of the
node's CPU load `cpu(node)` and memory usage `mem(node)`:

(F1)       (cpu(node) + mem(node)) / 2

This series replaces F1 with the weighted arithmetic mean [2]:

(F2)       (cpu(node) * cpu_w + mem(node) * mem_w) / (cpu_w + mem_w)

`cpu_w` controls how much `cpu(node)` contributes to F2, analogously, `mem_w`
controls how much `mem(node)` contributes to F2; the higher the weight, the
more that resource dominates the result of F2.

NOTE:
- a weight of 0 means no contribution to F2;
- only the weights' ratio matters, not their absolute magnitude; and
- F2 reduces exactly to the plain arithmetic mean F1 whenever `cpu_w` and
  `mem_w` are equal (not just when both equal 1).

Let `X` be the population of loads according to F2 with weights `cpu_w` and
`mem_w` of all nodes in a cluster consisting of `n` nodes. Since weights
`cpu_w` and `mem_w` affect the result of F2, they also shape how sensitively
the load imbalance computation:

(F3)       coefficient_of_variation(X) / sqrt(n - 1)

reacts to CPU load changes relative to memory usage changes. Accordingly, this
series enables users to control how much a given change in CPU load or memory
usage moves the imbalance metric by means of weights. This is to address: "In
our case CRS has not moved any VM around because the imbalance percentage is
low (7%). Eventhough the cluster is very imbalance [sic] CPU wise, or memory
wise alone." [3]

Weights of course also factor into the load balancer's decision, the 'how'
depends on which method is used.

## Bruteforce Method
The higher the weight of a computational resource, the more the search will
tend to prioritize balancing out that resource, e.g., a much greater 'cpu_w'
than 'mem_w' will steer migrations toward evening out CPU load, even at the
cost of leaving memory usage less balanced. This is a general tendency, not a
guarantee. The following deep(er) dive into the load imbalance formula gives
more insights.

Recall F3. Note that

(F4)       coefficient_of_variation(X) := standard_deviation(X) / mean(X)

(F5)       standard_deviation(X) := sqrt(variance(X))

Hence, `variance(X)` is the part of F3 that captures how dispersed the node
loads are. Define `C := [cpu(x) | x in cluster]` and `M := [mem(x) | x in cluster]`.
In fact, one can derive that `variance(X)` can be rewritten as:

(F6)       (cpu_t + mem_t + cov_t) / (cpu_w + mem_w)^2
           where
                 cpu_t := cpu_w^2 * variance(C)
                 mem_t := mem_w^2 * variance(M)
                 cov_t := 2 * cpu_w * mem_w * covariance(M,C)

F6 dissects how the weights shape the variance part of the load imbalance.

`cpu_t` and `mem_t` relate to the respective resource's dispersion weighted by
the square of its weight (note that doubling a weight roughly quadruples that
term's pull on the total). Note that `variance(C)` as part of `cpu_t` and
`variance(M)` as part of `mem_t` are each an average of squared deviations [5],
so they can never be negative, and neither can the squared weights; hence
`cpu_t` and `mem_t` can only ever add to `variance(X)`, never subtract from it.
They are also where each weight acts on its own resource's dispersion, and this
is the mechanism behind letting users express a preference for balancing one
computational resource over the other. Because `cpu_t` scales with `cpu_w^2`
and `mem_t` scales with `mem_w^2`, raising `cpu_w` relative to `mem_w` makes
`variance(C)`'s own dispersion count for a disproportionately larger share of
the numerator of F6, which steers the bruteforce method toward candidates that
keep CPU load tight, even at the cost of leaving memory usage more spread out.
This is the sense in which a higher `cpu_w` means "prioritize balancing CPU
load": not that memory usage is ignored, but that `mem_t`'s pull on the
numerator shrinks relative to `cpu_t`'s as the weight ratio skews toward CPU
load.

`cov_t` is the only one of the three terms that can be negative, which makes it
the only lever capable of pulling `variance(X)` below what the two resources'
own dispersions would otherwise force it to be. A rebalancing migration
can exploit this by arranging `cpu(·)` and `mem(·)` to deviate from their means
in opposite directions across nodes. A node that ends up above-average on
`mem(·)` tends to end up below-average on `cpu(·)`, and vice versa. Averaged
into F2 per node, those two errors partially cancel out, so `variance(X)` (and
hence the reported load imbalance) can come out looking well-balanced even when
neither `variance(C)` nor `variance(M)` individually is. One caveat that
follows directly: weighting a resource more heavily increases its pull on
`variance(X)`, but it doesn't disable `cov_t`. A candidate with a sufficiently
favorable (negative) covariance can still beat one that's honestly better on
the heavily-weighted resource's own dispersion. In short, weighting changes how
much a resource's balance matters to the outcome, but it does not make bruteforce
immune to the cancellation mechanism described above.

Besides `variance(X)`, the weights also enter `mean(X)`, the denominator of F4.
By definition, `mean(X)` is the plain (unweighted) arithmetic mean over the
nodes of the weighted node loads, that is, the sum of the loads according to F2
divided by the number of nodes `n`. The weights act across the two resources
within each node, not across nodes. In fact, `mean(X)` can be rewritten as the
weighted arithmetic mean of the two resources' mean loads:

(F7)       (cpu_w * mean(C) + mem_w * mean(M)) / (cpu_w + mem_w)

The result of F7 lies between `mean(C)` and `mean(M)` and moves toward the mean
of the more heavily weighted resource. Scaling both weights by the same factor
leaves it unchanged.

Note that a single rebalancing migration only redistributes computational
resources between nodes, it never changes the cluster-wide total CPU load or
memory usage. Hence, for nodes of equal capacity (homogeneous cluster),
`mean(C)`, `mean(M)` and thus `mean(X)` are the same constant for every
migration candidate at fixed weights: the mean scales the load imbalance (F3)
but does not influence which candidate has the lowest one, which is why the
weights' steering effect on the ranking is dissected by F6. Two caveats follow:

- Different weights: Both `variance(X)` (F6) and `mean(X)` (F7) change with the
  choice of weights, so the same state of the cluster yields different load
  imbalance values for different weights, in particular if `mean(C)` and
  `mean(M)` or `variance(C)` and `variance(M)` differ considerably. Values
  computed with different weights, and thresholds they are compared against, are
  therefore not directly comparable.
- Nodes of different capacity (heterogeneous cluster): The same amount of a
  resource corresponds to a different fraction of the capacity of different
  nodes, so migrating it to different targets can change the sum of node loads.
  Then `mean(C)`, `mean(M)` and `mean(X)` can differ between migration
  candidates, and the mean influences which candidate has the lowest load
  imbalance in addition to `variance(X)`. F6 remains valid but in this case only
  explains the variance part of the ranking.

## TOPSIS Method
Weights have always been part of the TOPSIS [4] method, weighing the criteria
of the decision process. Previously, all of these weights were fixed. This
series exposes customizable weights for average CPU and average memory only.
The weights of highest CPU and highest memory are not independently
configurable; each is derived as twice as much as its average counterpart, that
is, the weight of highest CPU/memory is twice as much as the weight of average
CPU/memory. This makes it possible for users to prioritize balancing a specific
computational resource while also preserving the ratio between a resource's two
criteria, as introduced in [0]. Unlike for the bruteforce method, TOPSIS'
per-resource criteria never combine CPU load and memory usage into a single
quantity, so there is no known cancellation-style lever to be aware of here.


[0] https://lore.proxmox.com/all/20221110143800.98047-3-f.ebner@proxmox.com/
[1] https://en.wikipedia.org/wiki/Arithmetic_mean
[2] https://en.wikipedia.org/wiki/Weighted_arithmetic_mean
[3] https://bugzilla.proxmox.com/show_bug.cgi?id=7993
[4] https://en.wikipedia.org/wiki/TOPSIS
[5] https://en.wikipedia.org/wiki/Variance


proxmox:

Dominik Rusovac (5):
  resource-scheduling: scheduler: fix typos
  resource-scheduling: scheduler: abstract post-migration stats logic
  fix #7993: resource-scheduling: lift to weighted load balancing
  workspace,resource-scheduling: add proptest crate
  resource-scheduling: scheduler: proptest weights

 Cargo.toml                                    |   1 +
 proxmox-resource-scheduling/Cargo.toml        |   3 +
 proxmox-resource-scheduling/src/node.rs       |  27 +-
 proxmox-resource-scheduling/src/pve_static.rs |   3 +-
 proxmox-resource-scheduling/src/scheduler.rs  | 620 +++++++++++++++---
 proxmox-resource-scheduling/src/topsis.rs     |   2 +-
 .../tests/scheduler.rs                        | 136 +++-
 7 files changed, 685 insertions(+), 107 deletions(-)


proxmox-perl-rs:

Dominik Rusovac (1):
  fix #7993: pve-rs: resource-scheduling: add weights to pve bindings

 .../resource_scheduling/pve_dynamic.rs        | 27 +++++++++++++++----
 .../resource_scheduling/pve_static.rs         | 25 +++++++++++++----
 pve-rs/test/resource_scheduling.pl            |  3 ++-
 3 files changed, 44 insertions(+), 11 deletions(-)


pve-manager:

Dominik Rusovac (2):
  fix #7993: ui: form: crs options: add weights
  ui: form: crs options: make options advanced

 www/manager6/form/CRSOptions.js | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)


pve-ha-manager:

Dominik Rusovac (6):
  manager: remove obsolete argument
  fix #7993: manager,usage: implement weighted auto rebalancing
  sim: hardware: enable datacenter config changes at runtime
  manager: log changes to crs settings
  test: add auto rebalance with weights test cases
  manager: rename update_crs_scheduler_mode

 src/PVE/HA/Manager.pm                         | 140 ++++++++++++++----
 src/PVE/HA/Sim/Hardware.pm                    |  62 ++++++++
 src/PVE/HA/Usage.pm                           |  21 ++-
 src/PVE/HA/Usage/Basic.pm                     |  14 +-
 src/PVE/HA/Usage/Dynamic.pm                   |  27 ++--
 src/PVE/HA/Usage/Static.pm                    |  27 ++--
 .../log.expect                                |  13 +-
 .../README                                    |   5 +
 .../cmdlist                                   |   6 +
 .../datacenter.cfg                            |   6 +
 .../dynamic_service_stats                     |   8 +
 .../hardware_status                           |   5 +
 .../log.expect                                |  62 ++++++++
 .../manager_status                            |   1 +
 .../service_config                            |   8 +
 .../static_service_stats                      |   8 +
 .../README                                    |   4 +
 .../cmdlist                                   |   8 +
 .../datacenter.cfg                            |   6 +
 .../dynamic_service_stats                     |   8 +
 .../hardware_status                           |   5 +
 .../log.expect                                |  66 +++++++++
 .../manager_status                            |   1 +
 .../service_config                            |   8 +
 .../static_service_stats                      |   8 +
 .../README                                    |   5 +
 .../cmdlist                                   |   6 +
 .../datacenter.cfg                            |   6 +
 .../dynamic_service_stats                     |   8 +
 .../hardware_status                           |   5 +
 .../log.expect                                |  62 ++++++++
 .../manager_status                            |   1 +
 .../service_config                            |   8 +
 .../static_service_stats                      |   8 +
 34 files changed, 566 insertions(+), 70 deletions(-)
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/README
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/cmdlist
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/datacenter.cfg
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/dynamic_service_stats
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/hardware_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/log.expect
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/manager_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/service_config
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-cpu-bias/static_service_stats
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/README
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/cmdlist
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/datacenter.cfg
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/dynamic_service_stats
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/hardware_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/log.expect
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/manager_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/service_config
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-increasing-bias/static_service_stats
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/README
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/cmdlist
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/datacenter.cfg
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/dynamic_service_stats
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/hardware_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/log.expect
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/manager_status
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/service_config
 create mode 100644 src/test/test-crs-dynamic-auto-rebalance-with-mem-bias/static_service_stats


pve-cluster:

Dominik Rusovac (1):
  fix #7993: datacenter config: add ha-auto-rebalance-{cpu,mem}-weight

 src/PVE/DataCenterConfig.pm | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)


Summary over all repositories:
  46 files changed, 1340 insertions(+), 188 deletions(-)

-- 
Generated by murpp 0.11.0