You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cloudstack.apache.org by "bhouse-nexthop (via GitHub)" <gi...@apache.org> on 2026/09/09 23:50:03 UTC
[PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
bhouse-nexthop opened a new pull request, #14109:
URL: https://github.com/apache/cloudstack/pull/14109
### Description
This PR adds an opt-in VM allocation algorithm, `balancedweighted`, for `vm.allocation.algorithm`. Existing algorithms and the default are untouched.
**The problem.** The existing algorithms rank hosts on allocated capacity alone. Under a large overprovisioning factor that reads badly: allocation is measured against a total that has already been multiplied by the factor, so a host under real strain can still report a low percentage allocated and keep attracting new VMs. Anything allocation cannot see - guests using far more than they asked for, VMs the management server has lost track of - is invisible.
Concurrent deployments make it worse. Capacity is only charged once a VM starts, so every decision taken in the same moment reads the same figures, and strict ordering makes them all agree on one host.
**What it ranks on.** A blend, lower is better:
| Term | Source |
|---|---|
| CPU allocated | `op_host_capacity`, over the overprovisioned total |
| CPU utilisation | moving average of measured usage |
| Memory allocated | `op_host_capacity`, over the overprovisioned total |
| Memory utilisation | moving average of measured usage |
| VM count | VMs on the host |
| Recent starts | VMs started within the last few minutes |
Recent starts exist because a VM that started moments ago is invisible to both allocation lag and a moving average, while often working hardest.
A dominant-resource term is added on top of the weighted mean, taking the larger of allocated and measured per resource, so that a host nearly out of any one resource does not rank well on a good average.
Then two things happen that ranking alone does not do:
- hosts measurably too busy are held back, unless that would leave nowhere to deploy
- selection is random among the best few rather than strictly ordered, so simultaneous deployments do not all pick the same host
**Measured effect.** Simulation over a churning, heavily overprovisioned fleet where part of the real load is invisible to allocation, measuring how unevenly real load ends up distributed (max/mean across hosts, lower is better):
| Ranking | Load skew |
|---|---|
| allocation only | 1.84 - 2.01 |
| allocation only, plus the random spread | 1.65 - 2.08 |
| weighted | **1.27 - 1.40** |
The middle row is a control: it isolates what the scoring contributes from what the randomisation contributes.
**Utilisation figures** come from a moving average of what `StatsCollector` already polls but nothing used for placement. It is per management server and not persisted; every management server polls every host, so they converge. Until a server has samples, ranking falls back to allocation figures, and hosts that cannot be measured rank behind hosts that can rather than being assumed idle.
Note the utilisation terms are only meaningful as intended on KVM. `getCpuUtilization` reports a reservation figure on VMware and is scaled by core count on XenServer; this is documented on the collector.
All weights and thresholds are settings, most cluster scoped.
### Types of changes
- [ ] Breaking change (fix or feature that would cause existing functionality to change)
- [x] New feature (non-breaking change which adds functionality)
- [ ] Bug fix (non-breaking change which fixes an issue)
- [ ] Enhancement (improves an existing feature and functionality)
- [ ] Cleanup (Code refactoring and cleanup, that may add test cases)
- [ ] Build/CI
- [ ] Test (unit or integration test code)
### Feature/Enhancement Scale or Bug Severity
#### Feature/Enhancement Scale
- [x] Major
- [ ] Minor
### How Has This Been Tested?
Unit tests, 39 new cases:
- `WeightedHostScorerTest` - the scoring function: each term's direction, the dominant-resource term, unmeasured hosts, the utilisation gates, the selection spread.
- `WeightedHostScorerRankTest` - `rank()` end to end as the allocator calls it, with the capacity and VM-count queries mocked. Covers the overprovisioned denominator, a busy host ranking behind a quiet one at equal allocation, an over-threshold host never leading while a healthy one exists, unmeasured hosts ranking last, fallback to allocation when nothing is measured, and a host missing a capacity row.
- `HostLoadTrackerTest` - the moving average: first sample, a single spike not dominating, convergence, half-life, missed samples decaying by elapsed time rather than sample count, unchanged readings not folded twice, and a host that stops reporting becoming unusable.
- `WeightedPlacementDistributionTest` - the simulation above. Deterministic; the workload is fixed before any arm runs so all arms see identical VMs.
Full `mvn test` on `api`, `engine/schema` and `server`, checkstyle and license checks enabled: 0 failures.
#### How did you try to break this feature and the system with this change?
This went through two rounds of adversarial review. The defects found and fixed are worth listing, since they are the interesting part:
- **The allocated fraction was measured against the wrong total.** `op_host_capacity` stores totals raw and applies overprovisioning when they are read. Dividing by the stored total made the fraction reach 1 at the host's physical size, so on a cluster overcommitted ten times every host clamped to 1 and both the allocation term and the dominant-resource term went dead - on exactly the clusters this is for.
- **The utilisation threshold could be bypassed.** Held-back hosts were re-appended before the random spread was applied, so with one healthy host and a spread of three, two thirds of deployments picked an over-threshold host.
- **A host with no samples was treated as idle**, exempt from the thresholds and scoring well on the dominant term - so a host with broken statistics became a deployment magnet.
- **A host that stopped reporting kept vouching for itself.** `StatsCollector` hands back the previous entry when a poll fails, and that unchanged reading was folded again every interval.
- **The sampler ran on a `Timer`**, which dies permanently and silently on one escaping error, leaving placement quietly back on allocation alone. It also ran regardless of whether the algorithm was selected.
- **A negative weight** would have ranked the most loaded host first.
- **The simulation drew different random streams per arm**, so the arms were not seeing the same workload; and it bypassed `rank()`, which is why it caught none of the above. Both fixed, and the spread-only control arm added.
Other things checked: hosts missing a capacity row, all-zero weights, `podId`/`clusterId` being null, concurrent access to the shared average, and that the two per-ranking queries became one.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5693017622
This pull request has merge conflicts. Dear author, please fix the conflicts and sync your branch with the base branch.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "bhouse-nexthop (via GitHub)" <gi...@apache.org>.
bhouse-nexthop commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-6341233672
> is this similar to #10997 ?
No, this is vastly different. The primary difference I'd say is the fact that this looks at actual utilization numbers not just allocated numbers. With overprovisioning and the use of free page reporting you can have hosts with greatly varying utilization and this looks to even that out. Its got weighting knobs for each of the cpu and memory utilization vs allocation, with sane defaults. It also weights actual VM count as the agent can struggle with managing more smaller vms vs fewer larger vms so it helps balance those out as well.
In our environment we run mostly things like developer VMs and ephemeral runners for CI/CD tasks so we need overprovisioning as the allocations for those VMs are way different then the actual utilization (4x memory overcommit and 10x cpu overcommit).
With this balancing algorithm we went from daily OOM events and slow agent provisioning and destroy of VMs to zero of both events.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "DaanHoogland (via GitHub)" <gi...@apache.org>.
DaanHoogland commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5817203023
> @DaanHoogland this is a behavioural change on top of what you approved, so flagging it rather than assuming the approval carries — happy to split the gate into its own PR if you would rather keep this one to the scoring change.
Thanks @bhouse-nexthop , I lost context a bit (holiday) and as 82 files changed in the latest commit I would agree a new review is needed. I'll be busy when back next week I imagine so I can not promise much attention. Can you lobby for others to review?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "bhouse-nexthop (via GitHub)" <gi...@apache.org>.
bhouse-nexthop commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5932058055
> as 82 files changed in the latest commit I would agree a new review is needed
Thanks @DaanHoogland, and welcome back. The 82 files is a side effect of my force-push on 09-16, which rebased the branch onto `main`; GitHub's "changes since last review" view then includes everything that landed on `main` in between. The PR itself touches 17 files, and what is new since your approval is two commits:
- 01b6871715261713ff5911263742c493a68ca585 Hold back hosts with a backlog of VMs still starting (5 files, +226/−30)
- 02b9428ad4fb825749b1d3cafcaae3d6f45a8141 Rank each candidate host once, however many tags it carries (4 files, +76/−5)
So the re-review is about 300 lines, not 82 files. Reviewing those two commits individually is the quickest route.
@nvazquez @RosiKyu since Daan is short on time, would one of you be able to pick this up for 4.24? We've been running it in production.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "codecov[bot] (via GitHub)" <gi...@apache.org>.
codecov[bot] commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5610485283
## [Codecov](https://app.codecov.io/gh/apache/cloudstack/pull/14109?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:white_check_mark: All modified and coverable lines are covered by tests.
:white_check_mark: Project coverage is 3.52%. Comparing base ([`036493f`](https://app.codecov.io/gh/apache/cloudstack/commit/036493fd0149f8b3e639685be338ca5af2c6f1bd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`87c06e3`](https://app.codecov.io/gh/apache/cloudstack/commit/87c06e3ab3e9db688b83c71a32a54dbc078f3882?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
> :exclamation: There is a different number of reports uploaded between BASE (036493f) and HEAD (87c06e3). Click for more details.
>
> <details><summary>HEAD has 1 upload less than BASE</summary>
>
>| Flag | BASE (036493f) | HEAD (87c06e3) |
>|------|------|------|
>|unittests|1|0|
></details>
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #14109 +/- ##
=============================================
- Coverage 19.79% 3.52% -16.27%
=============================================
Files 6371 487 -5884
Lines 575954 41903 -534051
Branches 70521 7927 -62594
=============================================
- Hits 113997 1479 -112518
+ Misses 449530 40209 -409321
+ Partials 12427 215 -12212
```
| [Flag](https://app.codecov.io/gh/apache/cloudstack/pull/14109/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [uitests](https://app.codecov.io/gh/apache/cloudstack/pull/14109/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `3.52% <ø> (ø)` | |
| [unittests](https://app.codecov.io/gh/apache/cloudstack/pull/14109/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/cloudstack/pull/14109?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "blueorangutan (via GitHub)" <gi...@apache.org>.
blueorangutan commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5734331145
Packaging result [SF]: ✔️ el8 ✔️ el9 ✔️ el10 ✔️ debian ✔️ suse15. SL-JID 19286
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "DaanHoogland (via GitHub)" <gi...@apache.org>.
DaanHoogland commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5947909942
> Thanks @DaanHoogland, and welcome back.
thanks
> * [01b6871](https://github.com/apache/cloudstack/commit/01b6871715261713ff5911263742c493a68ca585) Hold back hosts with a backlog of VMs still starting (5 files, +226/−30)
> * [02b9428](https://github.com/apache/cloudstack/commit/02b9428ad4fb825749b1d3cafcaae3d6f45a8141) Rank each candidate host once, however many tags it carries (4 files, +76/−5)
changes look good
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "weizhouapache (via GitHub)" <gi...@apache.org>.
weizhouapache commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-6340202392
is this similar to #10997 ?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#discussion_r3977752471
##########
engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java:
##########
@@ -795,6 +802,44 @@ public Pair<List<Long>, Map<Long, Double>> listPodIdsInZoneByVmCount(long dataCe
}
}
+
+ @Override
+ public Map<Long, Pair<Long, Long>> countVmsByHost(long dcId, Long podId, Long clusterId, Date changedStateAfter) {
+ TransactionLegacy txn = TransactionLegacy.currentTxn();
+ Map<Long, Pair<Long, Long>> result = new HashMap<>();
+ String sql = COUNT_VMS_BY_HOST;
+ if (podId != null) {
+ sql = sql + " AND host.pod_id = ? ";
+ }
+ if (clusterId != null) {
+ sql = sql + " AND host.cluster_id = ? ";
+ }
+ sql = sql + COUNT_VMS_BY_HOST_PART2;
+ try {
+ PreparedStatement pstmt = txn.prepareAutoCloseStatement(sql);
+ int index = 1;
+ // a cut-off in the future counts nothing as recent, which is what a null asks for
+ long cutOff = changedStateAfter != null ? changedStateAfter.getTime() : Long.MAX_VALUE;
+ pstmt.setTimestamp(index++, new Timestamp(cutOff));
Review Comment:
Using `Long.MAX_VALUE` to represent a ‘future cut-off’ can overflow practical timestamp ranges in JDBC drivers and/or MySQL/MariaDB column types (often `TIMESTAMP` is limited), causing runtime failures if `changedStateAfter` is ever null. Prefer a safe sentinel within the DB-supported range (e.g., a far-future date that’s still representable for your schema), or adjust the SQL to avoid needing an extreme timestamp (e.g., make the ‘recent’ predicate conditional on the parameter being non-null).
##########
engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java:
##########
@@ -795,6 +802,44 @@ public Pair<List<Long>, Map<Long, Double>> listPodIdsInZoneByVmCount(long dataCe
}
}
+
+ @Override
+ public Map<Long, Pair<Long, Long>> countVmsByHost(long dcId, Long podId, Long clusterId, Date changedStateAfter) {
+ TransactionLegacy txn = TransactionLegacy.currentTxn();
+ Map<Long, Pair<Long, Long>> result = new HashMap<>();
+ String sql = COUNT_VMS_BY_HOST;
+ if (podId != null) {
+ sql = sql + " AND host.pod_id = ? ";
+ }
+ if (clusterId != null) {
+ sql = sql + " AND host.cluster_id = ? ";
+ }
+ sql = sql + COUNT_VMS_BY_HOST_PART2;
+ try {
+ PreparedStatement pstmt = txn.prepareAutoCloseStatement(sql);
+ int index = 1;
+ // a cut-off in the future counts nothing as recent, which is what a null asks for
+ long cutOff = changedStateAfter != null ? changedStateAfter.getTime() : Long.MAX_VALUE;
+ pstmt.setTimestamp(index++, new Timestamp(cutOff));
+ pstmt.setLong(index++, dcId);
+ if (podId != null) {
+ pstmt.setLong(index++, podId);
+ }
+ if (clusterId != null) {
+ pstmt.setLong(index++, clusterId);
+ }
+ ResultSet rs = pstmt.executeQuery();
+ while (rs.next()) {
+ result.put(rs.getLong(1), new Pair<>(rs.getLong(2), rs.getLong(3)));
+ }
+ return result;
+ } catch (SQLException e) {
+ throw new CloudRuntimeException("DB Exception on: " + sql, e);
+ } catch (Throwable e) {
+ throw new CloudRuntimeException("Caught: " + sql, e);
+ }
Review Comment:
Catching `Throwable` will also catch unrecoverable `Error`s (e.g., `OutOfMemoryError`) and can make failures harder to diagnose/handle correctly. It’s safer to catch `Exception` (or a narrower set of expected runtime exceptions) and let `Error`s propagate. If the intent is to wrap any unexpected runtime exception, consider `catch (RuntimeException e)` instead.
##########
server/src/main/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorer.java:
##########
@@ -0,0 +1,406 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+package com.cloud.agent.manager.allocator.impl;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Date;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.stream.Collectors;
+
+import javax.inject.Inject;
+
+import org.apache.cloudstack.framework.config.ConfigKey;
+import org.apache.cloudstack.framework.config.Configurable;
+
+import com.cloud.capacity.Capacity;
+import com.cloud.capacity.CapacityManager;
+import com.cloud.capacity.CapacityVO;
+import com.cloud.capacity.dao.CapacityDao;
+import com.cloud.dc.ClusterDetailsDao;
+import com.cloud.dc.ClusterDetailsVO;
+import com.cloud.host.Host;
+import com.cloud.host.HostScoringWeights;
+import com.cloud.utils.Pair;
+import com.cloud.utils.component.AdapterBase;
+import com.cloud.vm.VmDetailConstants;
+import com.cloud.vm.dao.VMInstanceDao;
+
+/**
+ * Ranks hosts on a blend of what has been allocated on them and what they are actually doing.
+ *
+ * Ordering purely by allocated capacity misreads a heavily overprovisioned cluster: allocation is
+ * measured against a total that has been multiplied by the overprovisioning factor, so hosts under
+ * real strain can still look close to empty and keep attracting new VMs. This blends allocation
+ * with measured utilisation, VM count, and how many VMs started on the host recently, since a VM
+ * that has just started is usually working harder than its long run average.
+ *
+ * Scores run from 0 (idle) upwards and lower is better. Hosts are then chosen from among the best
+ * rather than strictly in order - see {@link #applySelectionSpread}.
+ */
+public class WeightedHostScorer extends AdapterBase implements Configurable {
+
+ private static final String WEIGHT_DESCRIPTION_SUFFIX =
+ " Relative weight, only meaningful compared with the other host.weighted.* weights. Zero disables the term.";
+
+ public static final ConfigKey<Double> VmCountWeight = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.vm.count.weight", "1.0",
+ "How much the number of VMs already on a host counts against it, regardless of how busy they are."
+ + WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Double> RecentStartWeight = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.recent.start.weight", "2.0",
+ "How much VMs started recently on a host count against it. Guards against sending a burst of new "
+ + "VMs to one host, since neither allocation nor utilisation has caught up with them yet."
+ + WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Double> DominantResourceWeight = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.dominant.resource.weight", "1.0",
+ "How much a host's single most stressed resource counts against it, on top of the average across "
+ + "resources. Keeps a host that is fine on average but nearly out of one resource from ranking well."
+ + WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Integer> RecentStartWindow = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.weighted.recent.start.window", "300",
+ "Seconds for which a newly started VM counts as recently started.",
+ true, ConfigKey.Scope.Global);
+
+ public static final ConfigKey<Integer> ExpectedVmsPerHost = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.weighted.expected.vms.per.host", "50",
+ "Roughly how many VMs a host is expected to carry. Used only to bring VM counts onto the same "
+ + "0 to 1 scale as the other terms; it is not a limit and is never enforced.",
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Double> CpuUtilisationThreshold = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.cpu.utilisation.threshold", "0.85",
+ "Hosts whose measured CPU utilisation is above this fraction are held back from new VMs. "
+ + "Ignored if it would leave nowhere to deploy. Set to 1 to disable.",
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Double> MemoryUtilisationThreshold = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.memory.utilisation.threshold", "0.90",
+ "Hosts whose measured memory utilisation is above this fraction are held back from new VMs. "
+ + "Ignored if it would leave nowhere to deploy. Set to 1 to disable.",
+ true, ConfigKey.Scope.Cluster);
+
+ public static final ConfigKey<Integer> SelectionSpread = new ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.weighted.selection.spread", "3",
+ "How many of the best scoring hosts to choose between at random. Ranking strictly by score sends "
+ + "concurrent deployments to the same host, because they all read the same figures before any "
+ + "of them is accounted for. 1 restores strict ordering.",
+ true, ConfigKey.Scope.Cluster);
+
+ private static final Pair<Long, Long> NO_VMS = new Pair<>(0L, 0L);
+
+ @Inject
+ private CapacityDao capacityDao;
+
+ @Inject
+ private ClusterDetailsDao clusterDetailsDao;
+
+ @Inject
+ private VMInstanceDao vmInstanceDao;
+
+ @Inject
+ private HostLoadTracker hostLoadTracker;
+
+ protected Random random = new Random();
+
+ /**
+ * Orders hosts best first. Hosts absent from the capacity tables keep their original relative
+ * order at the end of the list rather than being dropped.
+ */
+ public List<Host> rank(long zoneId, Long podId, Long clusterId, List<? extends Host> hosts) {
+ if (hosts == null || hosts.size() <= 1) {
+ return hosts == null ? new ArrayList<>() : new ArrayList<>(hosts);
+ }
+
+ Map<Long, Double> scores = score(zoneId, podId, clusterId, hosts);
+
+ List<Host> unscored = new ArrayList<>();
+ List<Host> measured = new ArrayList<>();
+ List<Host> unmeasured = new ArrayList<>();
+ for (Host host : hosts) {
+ if (!scores.containsKey(host.getId())) {
+ unscored.add(host);
+ } else if (hostLoadTracker.getLoad(host.getId()).isUsable()) {
+ measured.add(host);
+ } else {
+ unmeasured.add(host);
+ }
+ }
+
+ Comparator<Host> byScore = Comparator.comparingDouble(h -> scores.get(h.getId()));
+ measured.sort(byScore);
+ unmeasured.sort(byScore);
+
+ List<Host> healthy = new ArrayList<>();
+ List<Host> tooBusy = new ArrayList<>();
+ partitionByUtilisation(clusterId, measured, healthy, tooBusy);
+
+ List<Host> result = new ArrayList<>();
+ if (healthy.isEmpty() && unmeasured.isEmpty()) {
+ logger.warn("Every candidate host is above its utilisation threshold, so the thresholds are being "
+ + "ignored for this deployment. The cluster is short of capacity.");
+ result.addAll(tooBusy);
+ applySelectionSpread(clusterId, result);
+ } else {
+ result.addAll(healthy);
+ // spread only over hosts known to be healthy, before anything else is appended,
+ // otherwise a busy or unmeasured host can be shuffled into the lead
+ applySelectionSpread(clusterId, result);
+ // a host we cannot measure is not assumed to be idle: it ranks behind every host we can
+ result.addAll(unmeasured);
+ result.addAll(tooBusy);
+ }
+
+ if (!tooBusy.isEmpty()) {
+ logger.debug("Holding back {} host(s) above their utilisation threshold: {}", tooBusy.size(), tooBusy);
+ }
+ logger.debug("Weighted host ranking: {}", () -> result.stream()
+ .filter(h -> scores.containsKey(h.getId()))
+ .map(h -> String.format("%s=%.4f", h.getName(), scores.get(h.getId())))
+ .collect(Collectors.joining(", ")));
+
+ result.addAll(unscored);
+ return result;
+ }
+
+ protected Map<Long, Double> score(long zoneId, Long podId, Long clusterId, List<? extends Host> hosts) {
+ List<CapacityVO> capacities = capacityDao.listHostCapacityByCapacityTypes(zoneId, clusterId,
+ List.of(Capacity.CAPACITY_TYPE_CPU, Capacity.CAPACITY_TYPE_MEMORY));
+ Map<Long, Pair<Long, Long>> vmCounts = vmInstanceDao.countVmsByHost(zoneId, podId, clusterId,
+ new Date(System.currentTimeMillis() - RecentStartWindow.value() * 1000L));
+
+ Map<Long, Double[]> allocated = allocatedFractions(capacities);
+
+ Weights weights = new Weights(clusterId);
+ Map<Long, Double> scores = new HashMap<>();
+ for (Host host : hosts) {
+ Double[] alloc = allocated.get(host.getId());
+ if (alloc == null) {
+ continue;
+ }
+ Pair<Long, Long> counts = vmCounts.getOrDefault(host.getId(), NO_VMS);
+ scores.put(host.getId(), scoreHost(weights, alloc[0], alloc[1], hostLoadTracker.getLoad(host.getId()),
+ counts.first(), counts.second()));
+ }
+ return scores;
+ }
+
+ /**
+ * Allocated CPU and memory as a fraction of what a host can hand out.
+ *
+ * op_host_capacity stores totals raw; overprovisioning is applied when they are read, so the
+ * cluster's ratio has to be applied here too. Without it the fraction reaches 1 at the host's
+ * physical size and every host on an overcommitted cluster clamps to 1, which is where this
+ * algorithm is most needed.
+ *
+ * Only hosts with both a CPU and a memory row are returned. A host missing one would otherwise
+ * score as if that resource were untouched, making it the most attractive host in the cluster.
+ */
+ protected Map<Long, Double[]> allocatedFractions(List<CapacityVO> capacities) {
+ Map<Long, Double[]> fractions = new HashMap<>();
+ Map<Long, Integer> seen = new HashMap<>();
+ for (CapacityVO capacity : capacities) {
+ long total = capacity.getTotalCapacity();
+ if (total <= 0) {
+ continue;
+ }
+ boolean isCpu = capacity.getCapacityType() == Capacity.CAPACITY_TYPE_CPU;
+ float overcommit = overcommitRatio(capacity.getClusterId(), isCpu);
+ double allocatable = total * overcommit;
+ double used = (double) (capacity.getUsedCapacity() + capacity.getReservedCapacity()) / allocatable;
+
+ Double[] entry = fractions.computeIfAbsent(capacity.getHostOrPoolId(), id -> new Double[] {0.0, 0.0});
+ entry[isCpu ? 0 : 1] = clamp(used);
+ seen.merge(capacity.getHostOrPoolId(), isCpu ? 1 : 2, Integer::sum);
+ }
+ fractions.keySet().removeIf(hostId -> seen.getOrDefault(hostId, 0) != 3);
+ return fractions;
+ }
+
+ /**
+ * The cluster's overprovisioning factor, defaulting to none if it cannot be read.
+ */
+ protected float overcommitRatio(Long clusterId, boolean forCpu) {
+ if (clusterId == null) {
+ return 1f;
+ }
+ String key = forCpu ? VmDetailConstants.CPU_OVER_COMMIT_RATIO : VmDetailConstants.MEMORY_OVER_COMMIT_RATIO;
+ ClusterDetailsVO detail = clusterDetailsDao.findDetail(clusterId, key);
+ if (detail == null || detail.getValue() == null) {
+ return 1f;
+ }
+ try {
+ float ratio = Float.parseFloat(detail.getValue());
+ return ratio > 0 ? ratio : 1f;
+ } catch (NumberFormatException e) {
+ logger.warn("Cluster {} has an unreadable {} of [{}], treating it as 1.", clusterId, key, detail.getValue());
+ return 1f;
+ }
+ }
+
+ /**
+ * The blend. Every term is a fraction of the host's capacity for that resource so the weights
+ * are directly comparable, and the dominant resource term is added on top of the weighted mean
+ * so that being nearly out of any one resource is penalised even when the average looks fine.
+ */
+ protected double scoreHostIn(Long clusterId, double cpuAllocated, double memoryAllocated, HostLoad load,
+ long vmCount, long recentStarts) {
+ return scoreHost(new Weights(clusterId), cpuAllocated, memoryAllocated, load, vmCount, recentStarts);
+ }
+
+ protected double scoreHost(Weights weights, double cpuAllocated, double memoryAllocated, HostLoad load,
+ long vmCount, long recentStarts) {
+ // a host with no usable load figures is ranked on allocation alone, and is placed behind
+ // every measured host by the caller rather than being assumed idle
+ double cpuUsedWeight = load.isUsable() ? weights.cpuUsed : 0;
+ double memoryUsedWeight = load.isUsable() ? weights.memoryUsed : 0;
+
+ double vmCountTerm = clamp(vmCount / weights.vmScale);
+ double recentStartTerm = clamp(recentStarts / weights.vmScale);
+
+ double weightSum = weights.cpuAllocated + cpuUsedWeight + weights.memoryAllocated + memoryUsedWeight
+ + weights.vmCount + weights.recentStart;
+
+ double mean = 0;
+ if (weightSum > 0) {
+ mean = (weights.cpuAllocated * cpuAllocated
+ + cpuUsedWeight * load.getCpuUtilisation()
+ + weights.memoryAllocated * memoryAllocated
+ + memoryUsedWeight * load.getMemoryUtilisation()
+ + weights.vmCount * vmCountTerm
+ + weights.recentStart * recentStartTerm) / weightSum;
+ }
+
+ if (weights.dominant <= 0) {
+ return mean;
+ }
+ return (mean + weights.dominant * dominantResource(cpuAllocated, memoryAllocated, load)) / (1 + weights.dominant);
+ }
+
+ /**
+ * The most stressed resource on the host. Allocation and utilisation are both considered for
+ * each resource and the larger is taken, because memory that has been reclaimed from idle
+ * guests can be taken back as soon as those guests get busy.
+ */
+ protected double dominantResource(double cpuAllocated, double memoryAllocated, HostLoad load) {
+ double cpu = load.isUsable() ? Math.max(cpuAllocated, load.getCpuUtilisation()) : cpuAllocated;
+ double memory = load.isUsable() ? Math.max(memoryAllocated, load.getMemoryUtilisation()) : memoryAllocated;
+ return Math.max(cpu, memory);
+ }
+
+ /**
+ * Splits measurably busy hosts out from the rest. Only hosts with load samples can be held
+ * back; a host that cannot be measured is dealt with by the caller.
+ */
+ protected void partitionByUtilisation(Long clusterId, List<Host> measured, List<Host> healthy, List<Host> tooBusy) {
+ double cpuThreshold = valueIn(CpuUtilisationThreshold, clusterId);
+ double memoryThreshold = valueIn(MemoryUtilisationThreshold, clusterId);
+
+ for (Host host : measured) {
+ HostLoad load = hostLoadTracker.getLoad(host.getId());
+ if (load.getCpuUtilisation() > cpuThreshold || load.getMemoryUtilisation() > memoryThreshold) {
+ tooBusy.add(host);
+ } else {
+ healthy.add(host);
+ }
+ }
+ }
+
+ /**
+ * Shuffles the best few hosts so that deployments made at the same moment do not all pick the
+ * same one. Capacity is only charged once a VM starts, so until then every concurrent decision
+ * sees the same figures and strict ordering makes them agree.
+ */
+ protected void applySelectionSpread(Long clusterId, List<Host> ranked) {
+ int spread = Math.min((int) valueIn(SelectionSpread, clusterId), ranked.size());
+ if (spread > 1) {
+ Collections.shuffle(ranked.subList(0, spread), random);
+ }
+ }
+
+ /**
+ * The weights for one ranking, read once rather than per host.
+ *
+ * A negative weight would invert the ranking and make the most loaded host the best, so they
+ * are floored at zero and the bad value is reported.
+ */
+ protected final class Weights {
+ private final double cpuAllocated;
+ private final double cpuUsed;
+ private final double memoryAllocated;
+ private final double memoryUsed;
+ private final double vmCount;
+ private final double recentStart;
+ private final double dominant;
+ private final double vmScale;
+
+ protected Weights(Long clusterId) {
+ cpuAllocated = nonNegative(HostScoringWeights.CpuAllocatedWeight, clusterId);
+ cpuUsed = nonNegative(HostScoringWeights.CpuUsedWeight, clusterId);
+ memoryAllocated = nonNegative(HostScoringWeights.MemoryAllocatedWeight, clusterId);
+ memoryUsed = nonNegative(HostScoringWeights.MemoryUsedWeight, clusterId);
+ vmCount = nonNegative(VmCountWeight, clusterId);
+ recentStart = nonNegative(RecentStartWeight, clusterId);
+ dominant = nonNegative(DominantResourceWeight, clusterId);
+ vmScale = Math.max(1, valueIn(ExpectedVmsPerHost, clusterId));
+ }
+
+ private double nonNegative(ConfigKey<Double> key, Long clusterId) {
+ double value = valueIn(key, clusterId);
+ if (value < 0) {
+ logger.warn("{} is set to {}, which would rank the most loaded host first. Treating it as 0.",
+ key.key(), value);
+ return 0;
+ }
+ return value;
+ }
+ }
+
+ private <T extends Number> double valueIn(ConfigKey<T> key, Long clusterId) {
+ T value = clusterId == null ? key.value() : key.valueIn(clusterId);
+ return value == null ? 0 : value.doubleValue();
+ }
+
+ private static double clamp(double value) {
+ if (Double.isNaN(value) || value < 0) {
+ return 0;
+ }
+ return Math.min(value, 1);
+ }
+
+ @Override
+ public String getConfigComponentName() {
+ return CapacityManager.class.getSimpleName();
+ }
+
+ @Override
+ public ConfigKey<?>[] getConfigKeys() {
+ return new ConfigKey<?>[] {HostScoringWeights.CpuAllocatedWeight, HostScoringWeights.CpuUsedWeight, HostScoringWeights.MemoryAllocatedWeight, HostScoringWeights.MemoryUsedWeight,
+ VmCountWeight, RecentStartWeight, DominantResourceWeight, RecentStartWindow, ExpectedVmsPerHost,
+ CpuUtilisationThreshold, MemoryUtilisationThreshold, SelectionSpread};
Review Comment:
This `getConfigKeys()` initializer is likely to violate typical Java/checkstyle line-length rules and is hard to scan during review. Consider formatting each entry on its own line (or at least one per line consistently) to improve readability and reduce style-check failures.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "bhouse-nexthop (via GitHub)" <gi...@apache.org>.
bhouse-nexthop commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5731044256
@rosikyu or @nvazquez I'd like this in 4.24, we're running it in production.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5620372740
This pull request has merge conflicts. Dear author, please fix the conflicts and sync your branch with the base branch.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "bhouse-nexthop (via GitHub)" <gi...@apache.org>.
bhouse-nexthop commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5618788660
Thanks for the review, and for the approval @DaanHoogland — agreed that this wants real-world testing; it is opt-in behind `vm.allocation.algorithm=balancedweighted` precisely so it can be trialled on one cluster.
On the Copilot comments:
**`Long.MAX_VALUE` timestamp — fixed, and it was worse than described.** `vm_instance.update_time` is a `TIMESTAMP` column, so the ceiling is 2038-01-19, not the `DATETIME` 9999-12-31. `new Timestamp(Long.MAX_VALUE)` is roughly year 292 million. Rather than hunt for a sentinel that is both "far future" and representable, the query now omits the predicate entirely when no cut-off is given — the recent-count becomes a constant `0` and no timestamp is bound.
**`catch (Throwable)` — changed to `catch (Exception)`.** Worth noting for context that this was copied from the neighbouring methods: `VMInstanceDaoImpl` has six other `catch (Throwable)` blocks, as does `CapacityDaoImpl`. I have only changed the one this PR adds, so as not to widen the diff. Happy to follow up with a separate cleanup across those files if that would be welcome.
**Config key array formatting — done**, one entry per line.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "bhouse-nexthop (via GitHub)" <gi...@apache.org>.
bhouse-nexthop commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5683015701
Pushed one more commit, and added a section to the description on the thundering herd, which the write-up had been treating as an implementation detail of the selection spread rather than as the problem it is.
**What prompted it.** The failure we actually see is not an allocation failure: a burst of deployments lands on one host and the VMs then sit in `Starting` for minutes instead of seconds, while that host works through a queue of starts its storage and agent command path cannot absorb.
Nothing in the algorithm saw that. Capacity is not charged until a VM reaches `Starting` — `CapacityManagerImpl.postStateTransitionEvent` calls `allocateVmCapacity` on that transition, which is after the allocator has returned — and the utilisation average is a sample interval and a half life behind, so a burst is over before either notices. The recent-start term is the closest thing to a guard and it cannot do the job:
- **It expires on a clock, and the load does not.** It counts VMs whose state changed within the window, so a VM stuck in `Starting` for ten minutes stops counting after five. The signal decays fastest on exactly the hosts that are worst off.
- **It is capped too low to act as a brake.** Its contribution is capped at `0.111` of the score, so a host with 200 VMs stuck in `Starting` ranks identically to one with 50.
So `host.weighted.starting.vms.threshold` (default 10, `0` disables) counts the VMs actually *in* `Starting` and gates on it rather than weighting it. It does not expire while the condition persists, it is read fresh on every ranking, and a gate cannot be outvoted by the other terms. It costs nothing — the per-host count query already filters on `vm.state`, so it is one more `SUM(IF(...))` in a query that was already being made, and the one-query-per-ranking property holds.
Worth being explicit that this is a brake and not a cure: a host taking minutes to start VMs is usually saturated on its storage path or agent command queue, and the allocator cannot make that faster, only stop adding to it. If the bottleneck is a shared primary storage pool rather than the host, per-host gating will not help.
**A defect found on the way.** The selection spread was applied to the healthy list only. Whenever no host was eligible, that list was empty, the shuffle was a no-op, and the held-back hosts were handed out in strict score order — so concurrent deployments agreed on one host in exactly the conditions that had caused the pile-up. Same class of defect as the "held-back hosts re-appended before the spread" one from the earlier review, in the other branch of the same `if`. The spread now applies to whichever tier leads, which removes the branch it was hiding in.
On the question that came up while writing this — what happens if every host trips a threshold — the answer is unchanged and now stated in the description: thresholds decide *preference*, never *eligibility*. Held-back hosts are moved down the list, never dropped, so no threshold can turn a deployment that would have succeeded into an `InsufficientServerCapacity` failure. Within the held-back group the order is by starting count, so the least backed up host is tried first.
Six new test cases (45 total). Full `mvn test` on `api`, `engine/schema` and `server`: 0 failures.
The three Copilot threads were addressed in the previous push; I have resolved them.
@DaanHoogland this is a behavioural change on top of what you approved, so flagging it rather than assuming the approval carries — happy to split the gate into its own PR if you would rather keep this one to the scoring change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "blueorangutan (via GitHub)" <gi...@apache.org>.
blueorangutan commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5733736138
@nvazquez a [SL] Jenkins job has been kicked to build packages. It will be bundled with no SystemVM templates. I'll keep you posted as I make progress.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add 'balancedweighted' VM allocation algorithm [cloudstack]
Posted by "nvazquez (via GitHub)" <gi...@apache.org>.
nvazquez commented on PR #14109:
URL: https://github.com/apache/cloudstack/pull/14109#issuecomment-5733730332
Thanks @bhouse-nexthop we will review it, it is included in the milestone
@blueorangutan package
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudstack.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org