This is an automated email from the ASF dual-hosted git repository.
RosiKyu pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/cloudstack.git
The following commit(s) were added to refs/heads/main by this push:
new 6caa33e4ddb Add 'balancedweighted' VM allocation algorithm (#14109)
6caa33e4ddb is described below
commit 6caa33e4ddbcb5884c8986ee90df5abfe6b11847
Author: Brad House - Nexthop <[email protected]>
AuthorDate: Thu Nov 12 10:45:09 2026 -0500
Add 'balancedweighted' VM allocation algorithm (#14109)
* Add a DAO method to count VMs per host
Counts VMs occupying each host in a zone, pod or cluster, optionally only
those that changed state recently. One query for the whole scope rather
than one per host.
Signed-off-by: Brad House <[email protected]>
* Track a moving average of real host utilisation
StatsCollector already polls CPU and memory utilisation for every host,
but it keeps only the newest sample and nothing uses it for placement.
- fold those samples into an exponentially weighted moving average
- weight by elapsed time, so a missed poll decays correctly instead of
over-weighting the previous value
- report nothing usable until a host has been sampled, so callers can
fall back to allocation figures
Two settings: host.load.sample.interval and host.load.half.life.
Signed-off-by: Brad House <[email protected]>
* Add 'balancedweighted' VM allocation algorithm
Opt-in via vm.allocation.algorithm. Existing algorithms and the default
are untouched.
Allocated capacity alone is a poor ranking under heavy overprovisioning:
it is measured against a total already multiplied by the overprovisioning
factor, so a host under real strain still reports a low percentage and
keeps being chosen. Anything allocation cannot see - VMs the scheduler
has lost track of, guests using more than they asked for - is invisible.
Ranks on a blend, lower is better:
| term | source |
|---------------------|-------------------------------------------|
| CPU allocated | op_host_capacity, over the inflated total |
| CPU utilisation | moving average of real usage |
| memory allocated | op_host_capacity, over the inflated total |
| memory utilisation | moving average of real usage |
| VM count | VMs on the host |
| recent starts | VMs started within the last few minutes |
A dominant resource term is added on top so a host nearly out of any one
resource does not rank well on a good average. 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:
capacity is only charged once a VM starts, so concurrent deployments all
read the same figures and strict ordering makes them agree on one host.
All weights and thresholds are settings, most cluster scoped.
Signed-off-by: Brad House <[email protected]>
* Fix three defects found in review of the weighted scoring
Allocated fraction was measured against the wrong total. op_host_capacity
stores totals raw and overprovisioning is applied when they are read, so
dividing by the stored total made the fraction reach 1 at the host's
physical size. On a cluster overcommitted 10 times every host clamped to
1, killing both the allocation term and the dominant resource term - on
exactly the clusters this algorithm is for.
- apply the cluster ratio to the denominator
- drop hosts missing a CPU or memory capacity row instead of scoring the
missing resource as untouched, which made them rank first
Utilisation thresholds could be bypassed. Held-back hosts were appended
before the random spread was applied, so the spread could shuffle a busy
host into the lead. With 1 healthy host and a spread of 3, two thirds of
deployments picked an over-threshold host.
- spread over healthy hosts only, before anything else is appended
A host with no load samples was treated as idle. It was exempt from the
thresholds and its dominant resource term fell back to allocation, so a
host with broken stats outranked every measured host and collected the
deployments.
- rank hosts we cannot measure behind every host we can
- when nothing can be measured, ranking falls back to allocation as before
Signed-off-by: Brad House <[email protected]>
* Address the rest of the weighted scoring review
Utilisation average
- a host whose agent stops reporting kept vouching for itself forever:
StatsCollector hands back the previous entry when a poll fails, and
that unchanged reading was folded again every minute. Detect the
repeat, and expire an average that stops being updated
- sample on a scheduled executor catching Throwable, not a Timer, which
dies permanently and silently on one escaping error
- only collect when an algorithm that reads the figures is selected
- read the half life once per sample rather than inside the map update
- document what getCpuUtilization means per hypervisor: it is what this
assumes on KVM, a reservation figure on VMware, and scaled by core
count on XenServer
Scoring
- a negative weight would rank the most loaded host first; floor at
zero and say so
- zeroing all six terms no longer discards the dominant resource term
- read weights once per ranking instead of once per host
Queries
- one query per ranking instead of two, returning both counts
- count Stopping VMs, which still hold their host
- correct the doc: every host in scope is returned, including empty ones
Tests
- cover rank() end to end, which is where the defects were: the
capacity denominator, the thresholds, the spread and the ordering of
measured against unmeasured hosts
- the distribution simulation drew different random streams per arm, so
the arms saw different workloads. Fix the workload up front and add
an allocation-only-plus-spread control, which shows the scoring and
not the spread is what evens out real load
Signed-off-by: Brad House <[email protected]>
* Address review feedback on the weighted allocation algorithm
vm_instance.update_time is a TIMESTAMP column, so there is no date that
reliably means "never" - anything past 2038 is out of range. Counting
with no cut-off used Long.MAX_VALUE, which is roughly year 292 million.
The query now leaves the timestamp out entirely in that case rather than
binding an impossible one.
Also catch Exception rather than Throwable in the new query, and put the
config key array one entry per line.
Signed-off-by: Brad House <[email protected]>
* Hold back hosts with a backlog of VMs still starting
The symptom this addresses is a burst of deployments all landing on one
host and then sitting 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, 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 counts VMs whose
state changed within a window, so a VM stuck in Starting for ten minutes
stops counting after five - the signal decays fastest on the hosts that
are worst off - and its contribution is capped at 0.111 of the score, so
a host with 200 VMs stuck in Starting ranks the same as one with 50.
Count the VMs actually in Starting instead, and use it as a gate rather
than a weight. It does not expire while the condition persists, it is
read fresh on every ranking rather than sampled, and a gate cannot be
outvoted by the other terms. It costs nothing: the per-host VM count
query already filters on vm.state, so it is one more aggregate in a
query that was already being made.
Held-back hosts are still never dropped, only moved down the list, so
this cannot turn a deployment that would have succeeded into an
InsufficientServerCapacity failure. Within the held-back group the order
is by starting count, so if every host is backed up the least backed up
one is tried first.
Also fix a hole in the selection spread. It was applied to the healthy
list only, so 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 - concurrent deployments agreeing on one host in exactly the
conditions that caused the pile-up. The spread now applies to whichever
tier leads, which also removes the special-cased branch it was hiding
in. The "short of capacity" warning stays narrow: hosts merely being
unmeasured, as they all are on a freshly started management server, is
not a capacity problem and must not warn on every deployment.
Signed-off-by: Brad House <[email protected]>
* Rank each candidate host once, however many tags it carries
listAllUpAndEnabledNonHAHosts joins host_tags to filter out hosts whose
tags are rules, and the join carries no DISTINCT, so a host comes back
once per non-rule tag it holds. That path is taken whenever a VM has no
host tag to filter the candidate list by, which in practice means system
VMs: a virtual router deploying onto a twelve host cluster where three
hosts carry a second tag is handed fifteen candidates.
An allocator that walks the list and takes the first host that fits is
indifferent to a repeat, which is why this has gone unnoticed. The
weighted ranking is not. Scores are keyed by host, so a repeat changes no
score, but the selection spread shuffles the leading few entries and the
caller takes whichever ends up first - so a host holding two of the three
slots draws two thirds of the deployments rather than one third.
Collapse the repeats in the DAO, where the join creates them and every
caller benefits, and again in the scorer, so ranking cannot be skewed by
whatever a future caller hands it.
Signed-off-by: Brad House <[email protected]>
* Let WeightedHostScorer implement HostScoringWeights
The four shared weights are then inherited like the scorer's own keys
instead of being qualified with the interface name. The scorer's own
description suffix is renamed so it no longer hides the interface's.
Signed-off-by: Brad House <[email protected]>
---------
Signed-off-by: Brad House <[email protected]>
---
PendingReleaseNotes | 28 ++
.../com/cloud/deploy/DeploymentClusterPlanner.java | 7 +-
.../java/com/cloud/deploy/DeploymentPlanner.java | 2 +-
.../java/com/cloud/host/HostScoringWeights.java | 57 +++
.../main/java/com/cloud/host/dao/HostDaoImpl.java | 10 +-
.../main/java/com/cloud/vm/dao/VMInstanceDao.java | 13 +
.../java/com/cloud/vm/dao/VMInstanceDaoImpl.java | 56 +++
.../java/com/cloud/host/dao/HostDaoImplTest.java | 27 ++
.../manager/allocator/impl/FirstFitAllocator.java | 5 +
.../agent/manager/allocator/impl/HostLoad.java | 60 +++
.../manager/allocator/impl/HostLoadTracker.java | 260 +++++++++++
.../manager/allocator/impl/WeightedHostScorer.java | 513 +++++++++++++++++++++
.../spring-server-allocator-context.xml | 6 +
.../allocator/impl/HostLoadTrackerTest.java | 182 ++++++++
.../allocator/impl/WeightedHostScorerRankTest.java | 339 ++++++++++++++
.../allocator/impl/WeightedHostScorerTest.java | 175 +++++++
.../impl/WeightedPlacementDistributionTest.java | 319 +++++++++++++
17 files changed, 2055 insertions(+), 4 deletions(-)
diff --git a/PendingReleaseNotes b/PendingReleaseNotes
index c9afb25f7ed..823a13bd6ae 100644
--- a/PendingReleaseNotes
+++ b/PendingReleaseNotes
@@ -91,3 +91,31 @@ example.ver.1 > example.ver.2:
no device-mapper multipath configuration is required. A new
Storage.StoragePoolType.NVMeTCP + MultipathNVMeOFAdapterBase /
NVMeTCPAdapter on the KVM side back the new pool type.
+
+ * New VM allocation algorithm 'balancedweighted' for
vm.allocation.algorithm. Existing
+ algorithms and the default are unchanged; the new one is opt-in.
+
+ 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 and
+ keep attracting new VMs. Concurrent deployments make it worse, since they
all read the same
+ figures before any of them is accounted for.
+
+ 'balancedweighted' ranks hosts on a blend of allocated CPU and memory,
measured CPU and
+ memory utilisation, VM count, and how many VMs started on the host
recently. It holds back
+ hosts that are measurably too busy, and chooses at random from among the
best scoring hosts
+ so that simultaneous deployments do not all pick the same one.
+
+ It also holds back hosts that already have
host.weighted.starting.vms.threshold VMs sitting
+ in the Starting state, so that a burst of deployments does not queue up
behind itself on one
+ host. This is the only signal that reacts within a single deployment:
capacity is not charged
+ until a VM reaches Starting and a utilisation average is a sample interval
behind, so neither
+ notices a burst until it is over. Set the threshold to 0 to disable it.
+
+ Held-back hosts are never excluded, only moved to the back of the list, so
no threshold can
+ turn a deployment that would have succeeded into an
InsufficientServerCapacity failure.
+
+ Tuned with the host.weighted.* settings, most of which are cluster scoped.
Measured
+ utilisation comes from a moving average configured with
host.load.sample.interval and
+ host.load.half.life. Until a management server has collected samples,
ranking falls back to
+ allocation figures alone.
diff --git a/api/src/main/java/com/cloud/deploy/DeploymentClusterPlanner.java
b/api/src/main/java/com/cloud/deploy/DeploymentClusterPlanner.java
index 9471c3d5c84..5bf7dffbbf9 100644
--- a/api/src/main/java/com/cloud/deploy/DeploymentClusterPlanner.java
+++ b/api/src/main/java/com/cloud/deploy/DeploymentClusterPlanner.java
@@ -62,11 +62,14 @@ public interface DeploymentClusterPlanner extends
DeploymentPlanner {
"vm.allocation.algorithm",
"Advanced",
"random",
- "Order in which hosts within a cluster will be considered for VM
allocation. The value can be 'random', 'firstfit', 'userdispersing', or
'firstfitleastconsumed'.",
+ "Order in which hosts within a cluster will be considered for VM
allocation. The value can be 'random', "
+ + "'firstfit', 'userdispersing', 'firstfitleastconsumed',
or 'balancedweighted'. 'balancedweighted' "
+ + "ranks hosts on a blend of allocated capacity, measured
utilisation, VM count and how many VMs "
+ + "started recently, and is tuned with the host.weighted.*
settings.",
true,
ConfigKey.Scope.Global, null, null, null, null, null,
ConfigKey.Kind.Select,
- "random,firstfit,userdispersing,firstfitleastconsumed");
+
"random,firstfit,userdispersing,firstfitleastconsumed,balancedweighted");
/**
* This is called to determine list of possible clusters where a virtual
diff --git a/api/src/main/java/com/cloud/deploy/DeploymentPlanner.java
b/api/src/main/java/com/cloud/deploy/DeploymentPlanner.java
index 22d796d4a77..2d2964916ee 100644
--- a/api/src/main/java/com/cloud/deploy/DeploymentPlanner.java
+++ b/api/src/main/java/com/cloud/deploy/DeploymentPlanner.java
@@ -70,7 +70,7 @@ public interface DeploymentPlanner extends Adapter {
boolean canHandle(VirtualMachineProfile vm, DeploymentPlan plan,
ExcludeList avoid);
public enum AllocationAlgorithm {
- random, firstfit, userdispersing, firstfitleastconsumed;
+ random, firstfit, userdispersing, firstfitleastconsumed,
balancedweighted;
}
public enum PlannerResourceUsage {
diff --git a/api/src/main/java/com/cloud/host/HostScoringWeights.java
b/api/src/main/java/com/cloud/host/HostScoringWeights.java
new file mode 100644
index 00000000000..886487aeedf
--- /dev/null
+++ b/api/src/main/java/com/cloud/host/HostScoringWeights.java
@@ -0,0 +1,57 @@
+// 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.host;
+
+import org.apache.cloudstack.framework.config.ConfigKey;
+
+/**
+ * How much each signal counts when ranking hosts by how loaded they are.
+ *
+ * Shared by initial placement and by rebalancing on purpose. If the two
weighted these differently
+ * they would disagree about which host is the better one, and rebalancing
could move VMs off hosts
+ * that placement had just chosen, only for placement to put them back.
+ *
+ * Weights are relative to each other; only their ratios matter, and zero
disables a term. Terms that
+ * only make sense for one of the two - how many VMs a host carries, how many
started recently - stay
+ * with whichever uses them.
+ */
+public interface HostScoringWeights {
+
+ String WEIGHT_DESCRIPTION_SUFFIX = " Relative weight, only meaningful
compared with the other "
+ + "host.weighted.* weights. Zero disables the term. Used by both
the 'balancedweighted' "
+ + "allocation algorithm and the 'weighted' DRS algorithm.";
+
+ ConfigKey<Double> CpuAllocatedWeight = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.cpu.allocated.weight", "1.0",
+ "How much CPU allocated on a host counts against it." +
WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ ConfigKey<Double> CpuUsedWeight = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.cpu.used.weight", "2.0",
+ "How much measured CPU utilisation counts against a host." +
WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ ConfigKey<Double> MemoryAllocatedWeight = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.memory.allocated.weight", "1.0",
+ "How much memory allocated on a host counts against it." +
WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+
+ ConfigKey<Double> MemoryUsedWeight = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Double.class, "host.weighted.memory.used.weight", "2.0",
+ "How much measured memory utilisation counts against a host." +
WEIGHT_DESCRIPTION_SUFFIX,
+ true, ConfigKey.Scope.Cluster);
+}
diff --git a/engine/schema/src/main/java/com/cloud/host/dao/HostDaoImpl.java
b/engine/schema/src/main/java/com/cloud/host/dao/HostDaoImpl.java
index 15727d9d8e6..64a7d75dfd8 100644
--- a/engine/schema/src/main/java/com/cloud/host/dao/HostDaoImpl.java
+++ b/engine/schema/src/main/java/com/cloud/host/dao/HostDaoImpl.java
@@ -24,6 +24,7 @@ import java.util.Arrays;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
@@ -935,7 +936,14 @@ public class HostDaoImpl extends GenericDaoBase<HostVO,
Long> implements HostDao
sc.setParameters("status", Status.Up);
sc.setParameters("resourceState", ResourceState.Enabled);
- return listBy(sc);
+ // The tag join carries no DISTINCT, so a host comes back once per
non-rule tag it holds.
+ // Callers read this as a set of candidate hosts, so collapse the
repeats here rather than
+ // leave each of them to cope with the same host arriving more than
once.
+ Map<Long, HostVO> distinctHosts = new LinkedHashMap<>();
+ for (HostVO host : listBy(sc)) {
+ distinctHosts.putIfAbsent(host.getId(), host);
+ }
+ return new ArrayList<>(distinctHosts.values());
}
@Override
diff --git a/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDao.java
b/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDao.java
index 4316a483954..b41bc4f8fce 100755
--- a/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDao.java
+++ b/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDao.java
@@ -25,6 +25,7 @@ import java.util.Set;
import com.cloud.hypervisor.Hypervisor;
import com.cloud.utils.Pair;
+import com.cloud.utils.Ternary;
import com.cloud.utils.db.GenericDao;
import com.cloud.utils.fsm.StateDao;
import com.cloud.vm.VMInstanceVO;
@@ -131,6 +132,18 @@ public interface VMInstanceDao extends
GenericDao<VMInstanceVO, Long>, StateDao<
List<Long> listHostIdsByVmCount(long dcId, Long podId, Long clusterId,
long accountId);
+ /**
+ * Counts the VMs occupying each host in a zone, pod or cluster, in one
query.
+ *
+ * @param changedStateAfter
+ * cut-off for the second count: VMs whose state last changed
after this. Approximates
+ * the VMs still working through their startup load, which neither
allocation nor a
+ * utilisation average has caught up with yet.
+ * @return host id to {total VMs, VMs that changed state recently, VMs
still in Starting}. Every
+ * host in scope appears, including hosts with no VMs.
+ */
+ Map<Long, Ternary<Long, Long, Long>> countVmsByHost(long dcId, Long podId,
Long clusterId, Date changedStateAfter);
+
Long countRunningAndStartingByAccount(long accountId);
Long countByZoneAndState(long zoneId, State state);
diff --git
a/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java
b/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java
index 761b9b51511..ad81d785f05 100755
--- a/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java
+++ b/engine/schema/src/main/java/com/cloud/vm/dao/VMInstanceDaoImpl.java
@@ -18,6 +18,7 @@ package com.cloud.vm.dao;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
+import java.sql.Timestamp;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Collection;
@@ -45,6 +46,7 @@ import com.cloud.storage.dao.VolumeDao;
import com.cloud.tags.dao.ResourceTagDao;
import com.cloud.utils.DateUtil;
import com.cloud.utils.Pair;
+import com.cloud.utils.Ternary;
import com.cloud.utils.db.Attribute;
import com.cloud.utils.db.DB;
import com.cloud.utils.db.Filter;
@@ -156,6 +158,21 @@ public class VMInstanceDaoImpl extends
GenericDaoBase<VMInstanceVO, Long> implem
private static final String COUNT_VMS_BASED_ON_VGPU_TYPES2 =
"GROUP BY gpu_card.name, vgpu_profile.name";
+ // %s is the "changed state recently" test, or a constant 0 when no
cut-off is given. It is not
+ // a bound parameter because there is no timestamp that reliably means
"never" - update_time is
+ // a TIMESTAMP column, so anything past 2038 is out of range.
+ //
+ // The third count is VMs still in Starting. Unlike the
recent-state-change count it does not
+ // expire on a clock: a VM that has been starting for ten minutes still
counts, which is the
+ // case that matters, since a host that is struggling is exactly the one
whose VMs take longest
+ // to leave Starting.
+ private static final String COUNT_VMS_BY_HOST = "SELECT host.id,
COUNT(vm.id), SUM(IF(%s, 1, 0)), " +
+ "SUM(IF(vm.state = 'Starting', 1, 0)) " +
+ "FROM `cloud`.`host` host LEFT JOIN `cloud`.`vm_instance` vm " +
+ "ON vm.host_id = host.id AND vm.state IN ('Running', 'Starting',
'Stopping', 'Migrating') " +
+ "AND vm.removed IS NULL WHERE host.type = 'Routing' AND
host.removed IS NULL AND host.data_center_id = ? ";
+ private static final String COUNT_VMS_BY_HOST_PART2 = " GROUP BY host.id ";
+
private static final String UPDATE_SYSTEM_VM_TEMPLATE_ID_FOR_HYPERVISOR =
"UPDATE `cloud`.`vm_instance` SET vm_template_id = ? WHERE type <> 'User' AND
hypervisor_type = ? AND removed is NULL";
private static final String COUNT_VMS_BY_ZONE_AND_STATE_AND_HOST_TAG =
"SELECT COUNT(1) FROM vm_instance vi JOIN service_offering so ON
vi.service_offering_id=so.id " +
@@ -801,6 +818,45 @@ public class VMInstanceDaoImpl extends
GenericDaoBase<VMInstanceVO, Long> implem
}
}
+
+ @Override
+ public Map<Long, Ternary<Long, Long, Long>> countVmsByHost(long dcId, Long
podId, Long clusterId, Date changedStateAfter) {
+ TransactionLegacy txn = TransactionLegacy.currentTxn();
+ Map<Long, Ternary<Long, Long, Long>> result = new HashMap<>();
+ String sql = String.format(COUNT_VMS_BY_HOST, changedStateAfter !=
null ? "vm.update_time > ?" : "0");
+ 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;
+ if (changedStateAfter != null) {
+ pstmt.setTimestamp(index++, new
Timestamp(changedStateAfter.getTime()));
+ }
+ 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()) {
+ // SUM over no rows is NULL, which getLong reports as 0 -
correct for an empty host
+ result.put(rs.getLong(1), new Ternary<>(rs.getLong(2),
rs.getLong(3), rs.getLong(4)));
+ }
+ return result;
+ } catch (SQLException e) {
+ throw new CloudRuntimeException("DB Exception on: " + sql, e);
+ } catch (Exception e) {
+ throw new CloudRuntimeException("Caught: " + sql, e);
+ }
+ }
+
@Override
public List<Long> listHostIdsByVmCount(long dcId, Long podId, Long
clusterId, long accountId) {
TransactionLegacy txn = TransactionLegacy.currentTxn();
diff --git
a/engine/schema/src/test/java/com/cloud/host/dao/HostDaoImplTest.java
b/engine/schema/src/test/java/com/cloud/host/dao/HostDaoImplTest.java
index c76eedb01e9..a6a0af14062 100644
--- a/engine/schema/src/test/java/com/cloud/host/dao/HostDaoImplTest.java
+++ b/engine/schema/src/test/java/com/cloud/host/dao/HostDaoImplTest.java
@@ -39,6 +39,7 @@ import org.mockito.junit.MockitoJUnitRunner;
import com.cloud.cpu.CPU;
import com.cloud.host.Host;
+import com.cloud.host.HostTagVO;
import com.cloud.host.HostVO;
import com.cloud.host.Status;
import com.cloud.hypervisor.Hypervisor;
@@ -60,6 +61,32 @@ public class HostDaoImplTest {
@Mock
private SearchCriteria<HostVO> mockSearchCriteria;
+ @Test
+ public void testListAllUpAndEnabledNonHAHostsCollapsesRepeatedHosts() {
+ // the host_tags join carries no DISTINCT, so a host comes back once
per non-rule tag it
+ // holds. Callers read the result as a set of candidate hosts.
+ SearchBuilder<HostTagVO> tagSearchBuilder = mock(SearchBuilder.class);
+ when(tagSearchBuilder.entity()).thenReturn(mock(HostTagVO.class));
+ HostTagsDao hostTagsDao = mock(HostTagsDao.class);
+ when(hostTagsDao.createSearchBuilder()).thenReturn(tagSearchBuilder);
+ hostDao._hostTagsDao = hostTagsDao;
+
+ when(mockSearchBuilder.entity()).thenReturn(mock(HostVO.class));
+ when(mockSearchBuilder.create()).thenReturn(mockSearchCriteria);
+ doReturn(mockSearchBuilder).when(hostDao).createSearchBuilder();
+
+ HostVO twoTags = mock(HostVO.class);
+ when(twoTags.getId()).thenReturn(1L);
+ HostVO oneTag = mock(HostVO.class);
+ when(oneTag.getId()).thenReturn(2L);
+ doReturn(Arrays.asList(twoTags, twoTags,
oneTag)).when(hostDao).listBy(any(SearchCriteria.class));
+
+ List<HostVO> hosts =
hostDao.listAllUpAndEnabledNonHAHosts(Host.Type.Routing, 3L, 2L, 1L, null);
+
+ assertEquals(2, hosts.size());
+ assertEquals(Arrays.asList(1L, 2L),
hosts.stream().map(HostVO::getId).collect(Collectors.toList()));
+ }
+
@Test
public void testCountUpAndEnabledHostsInZone() {
long testZoneId = 100L;
diff --git
a/server/src/main/java/com/cloud/agent/manager/allocator/impl/FirstFitAllocator.java
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/FirstFitAllocator.java
index 4bc34d8a5c6..6a5669d1797 100644
---
a/server/src/main/java/com/cloud/agent/manager/allocator/impl/FirstFitAllocator.java
+++
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/FirstFitAllocator.java
@@ -16,6 +16,7 @@
// under the License.
package com.cloud.agent.manager.allocator.impl;
+import static
com.cloud.deploy.DeploymentPlanner.AllocationAlgorithm.balancedweighted;
import static
com.cloud.deploy.DeploymentPlanner.AllocationAlgorithm.firstfitleastconsumed;
import static com.cloud.deploy.DeploymentPlanner.AllocationAlgorithm.random;
import static
com.cloud.deploy.DeploymentPlanner.AllocationAlgorithm.userdispersing;
@@ -95,6 +96,8 @@ public class FirstFitAllocator extends BaseAllocator {
CapacityDao _capacityDao;
@Inject
VMInstanceDetailsDao vmInstanceDetailsDao;
+ @Inject
+ WeightedHostScorer weightedHostScorer;
boolean _checkHvm = true;
@@ -209,6 +212,8 @@ public class FirstFitAllocator extends BaseAllocator {
hosts = reorderHostsByNumberOfVms(plan, hosts, account);
} else if
(firstfitleastconsumed.toString().equals(vmAllocationAlgorithm)) {
hosts = reorderHostsByCapacity(plan, hosts);
+ } else if (balancedweighted.toString().equals(vmAllocationAlgorithm)) {
+ hosts = weightedHostScorer.rank(plan.getDataCenterId(),
plan.getPodId(), plan.getClusterId(), hosts);
}
logger.debug("FirstFitAllocator has {} hosts to check for allocation
{}.", hosts.size(), hosts);
diff --git
a/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoad.java
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoad.java
new file mode 100644
index 00000000000..2e3d14ba838
--- /dev/null
+++ b/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoad.java
@@ -0,0 +1,60 @@
+// 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;
+
+/**
+ * Smoothed view of what a host is actually doing, as opposed to what has been
allocated on it.
+ * Fractions are of the host's real capacity and ignore overprovisioning.
+ */
+public class HostLoad {
+
+ public static final HostLoad UNKNOWN = new HostLoad(0, 0, 0);
+
+ private final double cpuUtilisation;
+ private final double memoryUtilisation;
+ private final long samples;
+
+ public HostLoad(double cpuUtilisation, double memoryUtilisation, long
samples) {
+ this.cpuUtilisation = cpuUtilisation;
+ this.memoryUtilisation = memoryUtilisation;
+ this.samples = samples;
+ }
+
+ public double getCpuUtilisation() {
+ return cpuUtilisation;
+ }
+
+ public double getMemoryUtilisation() {
+ return memoryUtilisation;
+ }
+
+ public long getSamples() {
+ return samples;
+ }
+
+ /**
+ * False until enough has been observed to rank on. Callers fall back to
allocation figures.
+ */
+ public boolean isUsable() {
+ return samples > 0;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("HostLoad[cpu=%.3f, memory=%.3f, samples=%d]",
cpuUtilisation, memoryUtilisation, samples);
+ }
+}
diff --git
a/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoadTracker.java
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoadTracker.java
new file mode 100644
index 00000000000..4543af9b8b1
--- /dev/null
+++
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/HostLoadTracker.java
@@ -0,0 +1,260 @@
+// 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.Map;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.Executors;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+
+import javax.inject.Inject;
+
+import org.apache.cloudstack.framework.config.ConfigKey;
+import org.apache.cloudstack.framework.config.Configurable;
+import org.apache.cloudstack.managed.context.ManagedContextRunnable;
+
+import com.cloud.host.HostStats;
+import com.cloud.host.HostVO;
+import com.cloud.host.Status;
+import com.cloud.host.dao.HostDao;
+import com.cloud.server.StatsCollector;
+import com.cloud.deploy.DeploymentClusterPlanner;
+import com.cloud.deploy.DeploymentPlanner.AllocationAlgorithm;
+import com.cloud.utils.component.ManagerBase;
+import com.cloud.utils.concurrency.NamedThreadFactory;
+
+/**
+ * Keeps a smoothed view of how hard each host is actually working.
+ *
+ * StatsCollector already polls every host, but it keeps only the newest
sample and nothing uses it
+ * for placement. A single sample is too noisy to rank on: a host can look
idle moments before a
+ * batch of VMs starts work. This folds those samples into an exponentially
weighted moving average
+ * so ranking reflects a trend rather than an instant.
+ *
+ * The average is per management server and is not persisted. Every management
server polls every
+ * host, so all of them converge on the same picture, and a restarted server
simply reports nothing
+ * usable until it has sampled - callers then fall back to allocation figures.
+ *
+ * What getCpuUtilization means depends on the hypervisor, and only KVM
reports what this class
+ * assumes:
+ *
+ * <ul>
+ * <li>KVM reports busy time as a percentage of the host's cores, which is
what is wanted.</li>
+ * <li>VMware reports the share of CPU that is reserved rather than the
share that is busy, so
+ * the CPU term becomes a second allocation signal there rather than a
load signal.</li>
+ * <li>XenServer sums per-core averages without dividing by core count, so
the value ranges up to
+ * the number of cores and is under-reported here by roughly that
factor.</li>
+ * </ul>
+ *
+ * Memory is taken as used over total and is sound everywhere.
+ */
+public class HostLoadTracker extends ManagerBase implements Configurable {
+
+ public static final ConfigKey<Integer> HostLoadSampleInterval = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.load.sample.interval", "60",
+ "Seconds between samples of host CPU and memory utilisation, for
placement algorithms that " +
+ "consider actual load. Should not be shorter than
host.stats.interval.",
+ false, ConfigKey.Scope.Global);
+
+ public static final ConfigKey<Integer> HostLoadStaleAfter = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.load.stale.after", "600",
+ "Seconds after which a host's utilisation average is considered
out of date and stops being used " +
+ "for placement. A host whose agent stops reporting would
otherwise keep vouching for itself " +
+ "with figures that never change.",
+ true, ConfigKey.Scope.Global);
+
+ public static final ConfigKey<Integer> HostLoadHalfLife = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.load.half.life", "300",
+ "Half life in seconds of the moving average of host utilisation.
Larger values react more " +
+ "slowly and are less affected by short spikes or by guests
periodically releasing memory.",
+ true, ConfigKey.Scope.Global);
+
+ @Inject
+ private HostDao hostDao;
+
+ @Inject
+ private StatsCollector statsCollector;
+
+ private final Map<Long, Sample> samples = new ConcurrentHashMap<>();
+
+ private ScheduledExecutorService executor;
+
+ @Override
+ public boolean start() {
+ int interval = Math.max(1, HostLoadSampleInterval.value());
+ executor = Executors.newSingleThreadScheduledExecutor(
+ new NamedThreadFactory("HostLoadTracker"));
+ // catch Throwable: an escaping error would cancel all future runs,
and the failure would be
+ // silent - placement would quietly go back to ranking on allocation
alone
+ executor.scheduleWithFixedDelay(new ManagedContextRunnable() {
+ @Override
+ protected void runInContext() {
+ try {
+ sampleAllHosts();
+ } catch (Throwable t) {
+ logger.warn("Unable to sample host load", t);
+ }
+ }
+ }, interval, interval, TimeUnit.SECONDS);
+ return true;
+ }
+
+ @Override
+ public boolean stop() {
+ if (executor != null) {
+ executor.shutdownNow();
+ }
+ return true;
+ }
+
+ protected void sampleAllHosts() {
+ if (!isInUse()) {
+ samples.clear();
+ return;
+ }
+ for (HostVO host :
hostDao.listByType(com.cloud.host.Host.Type.Routing)) {
+ if (host.getStatus() != Status.Up) {
+ samples.remove(host.getId());
+ continue;
+ }
+ record(host.getId(), statsCollector.getHostStats(host.getId()));
+ }
+ }
+
+ /**
+ * Only the placement algorithms that read these figures pay for
collecting them.
+ */
+ protected boolean isInUse() {
+ return AllocationAlgorithm.balancedweighted.toString()
+
.equals(DeploymentClusterPlanner.VmAllocationAlgorithm.value());
+ }
+
+ protected void record(long hostId, HostStats stats) {
+ record(hostId, stats, System.currentTimeMillis());
+ }
+
+ protected void record(long hostId, HostStats stats, long now) {
+ if (stats == null) {
+ return;
+ }
+ double totalMemory = stats.getTotalMemoryKBs();
+ if (totalMemory <= 0) {
+ return;
+ }
+
+ Sample previous = samples.get(hostId);
+ if (previous != null && previous.isSameReadingAs(stats)) {
+ // StatsCollector keeps the previous entry when a poll fails, so
an unchanged object is
+ // a reading we have already folded, not a fresh measurement
+ return;
+ }
+
+ // getCpuUtilization is a percentage of the host's real cores. That
holds for KVM; see the
+ // class javadoc for what it means on other hypervisors.
+ double cpu = clamp(stats.getCpuUtilization() / 100.0);
+ double memory = clamp((totalMemory - stats.getFreeMemoryKBs()) /
totalMemory);
+ int halfLife = HostLoadHalfLife.value();
+
+ samples.compute(hostId, (id, current) -> current == null
+ ? new Sample(cpu, memory, now, stats)
+ : current.fold(cpu, memory, now, halfLife, stats));
+ }
+
+ public HostLoad getLoad(long hostId) {
+ return getLoad(hostId, System.currentTimeMillis());
+ }
+
+ protected HostLoad getLoad(long hostId, long now) {
+ Sample sample = samples.get(hostId);
+ if (sample == null) {
+ return HostLoad.UNKNOWN;
+ }
+ long staleAfter = Math.max(1, HostLoadStaleAfter.value()) * 1000L;
+ if (now - sample.updatedAt > staleAfter) {
+ // the host has stopped reporting; stop letting its last known
figures speak for it
+ return HostLoad.UNKNOWN;
+ }
+ return sample.toHostLoad();
+ }
+
+ protected void clear() {
+ samples.clear();
+ }
+
+ private static double clamp(double value) {
+ if (Double.isNaN(value) || value < 0) {
+ return 0;
+ }
+ return Math.min(value, 1);
+ }
+
+ @Override
+ public String getConfigComponentName() {
+ return HostLoadTracker.class.getSimpleName();
+ }
+
+ @Override
+ public ConfigKey<?>[] getConfigKeys() {
+ return new ConfigKey<?>[] {HostLoadSampleInterval, HostLoadHalfLife,
HostLoadStaleAfter};
+ }
+
+ /**
+ * One host's running average. Weighting is by elapsed time rather than by
sample count, so a
+ * missed poll decays the old value by the right amount instead of
over-weighting it.
+ */
+ private static final class Sample {
+ private final double cpu;
+ private final double memory;
+ private final long updatedAt;
+ private final long count;
+ private final HostStats reading;
+
+ private Sample(double cpu, double memory, long updatedAt, HostStats
reading) {
+ this(cpu, memory, updatedAt, 1, reading);
+ }
+
+ private Sample(double cpu, double memory, long updatedAt, long count,
HostStats reading) {
+ this.cpu = cpu;
+ this.memory = memory;
+ this.updatedAt = updatedAt;
+ this.count = count;
+ this.reading = reading;
+ }
+
+ private boolean isSameReadingAs(HostStats stats) {
+ return reading == stats;
+ }
+
+ private Sample fold(double newCpu, double newMemory, long now, int
halfLifeSeconds, HostStats reading) {
+ double alpha = alpha(now - updatedAt, halfLifeSeconds);
+ return new Sample(cpu + alpha * (newCpu - cpu), memory + alpha *
(newMemory - memory), now,
+ count + 1, reading);
+ }
+
+ private static double alpha(long elapsedMillis, int halfLifeSeconds) {
+ if (halfLifeSeconds <= 0 || elapsedMillis <= 0) {
+ return 1;
+ }
+ return 1 - Math.exp(-(elapsedMillis / 1000.0) * Math.log(2) /
halfLifeSeconds);
+ }
+
+ private HostLoad toHostLoad() {
+ return new HostLoad(cpu, memory, count);
+ }
+ }
+}
diff --git
a/server/src/main/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorer.java
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorer.java
new file mode 100644
index 00000000000..581c2052ffc
--- /dev/null
+++
b/server/src/main/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorer.java
@@ -0,0 +1,513 @@
+// 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.LinkedHashMap;
+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.Ternary;
+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,
HostScoringWeights {
+
+ private static final String ALLOCATOR_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."
+ + ALLOCATOR_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."
+ + ALLOCATOR_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."
+ + ALLOCATOR_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);
+
+ public static final ConfigKey<Integer> StartingVmsThreshold = new
ConfigKey<>(ConfigKey.CATEGORY_ADVANCED,
+ Integer.class, "host.weighted.starting.vms.threshold", "10",
+ "Hosts with at least this many VMs still in the Starting state are
held back from new VMs, so "
+ + "that a burst of deployments does not queue up behind
itself on one host. Unlike the "
+ + "utilisation thresholds this reacts within a single
deployment rather than waiting for a "
+ + "load sample. Ignored if it would leave nowhere to
deploy. Set to 0 to disable.",
+ true, ConfigKey.Scope.Cluster);
+
+ private static final Ternary<Long, Long, Long> NO_VMS = new Ternary<>(0L,
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) {
+ List<Host> candidates = distinctHosts(hosts);
+ if (candidates.size() <= 1) {
+ return candidates;
+ }
+
+ Map<Long, Ternary<Long, Long, Long>> vmCounts = countVmsByHost(zoneId,
podId, clusterId);
+ Map<Long, Double> scores = score(zoneId, clusterId, candidates,
vmCounts);
+
+ List<Host> unscored = new ArrayList<>();
+ List<Host> measured = new ArrayList<>();
+ List<Host> unmeasured = new ArrayList<>();
+ for (Host host : candidates) {
+ 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);
+
+ // held back for having too many VMs still starting. Taken out of
healthy, so a host that is
+ // fine on resources but already working through a queue of starts
stops attracting more.
+ List<Host> backedUp = new ArrayList<>();
+ partitionByStartingVms(clusterId, healthy, vmCounts, backedUp);
+
+ // Tiers, best first. Nothing is ever dropped: a tier is only reached
when every better tier
+ // is empty, so holding a host back can never turn a deployment that
would have succeeded
+ // into an InsufficientServerCapacity failure.
+ //
+ // healthy - no known problem
+ // backedUp - fine on resources, momentarily queueing starts;
clears on its own
+ // unmeasured - unknown, and not assumed to be idle
+ // tooBusy - measurably over a resource threshold
+ List<List<Host>> tiers = List.of(healthy, backedUp, unmeasured,
tooBusy);
+ List<Host> result = new ArrayList<>();
+ for (List<Host> tier : tiers) {
+ // the spread belongs on whichever tier deployments will actually
draw from, which is
+ // the first non-empty one. Applying it only to healthy left
concurrent deployments in
+ // strict score order - and so agreeing on one host - whenever
healthy was empty.
+ if (result.isEmpty()) {
+ applySelectionSpread(clusterId, tier);
+ }
+ result.addAll(tier);
+ }
+
+ // only when a held-back host actually has to be used. Hosts merely
being unmeasured, as
+ // they all are on a freshly started management server, is not a
capacity problem.
+ if (healthy.isEmpty() && unmeasured.isEmpty() && !(backedUp.isEmpty()
&& tooBusy.isEmpty())) {
+ logger.warn("No candidate host is within its utilisation
thresholds and clear of the starting VM "
+ + "threshold, so they are being ignored for this
deployment. The cluster is short of capacity.");
+ }
+ if (!tooBusy.isEmpty()) {
+ logger.debug("Holding back {} host(s) above their utilisation
threshold: {}", tooBusy.size(), tooBusy);
+ }
+ if (!backedUp.isEmpty()) {
+ logger.debug("Holding back {} host(s) with too many VMs still
starting: {}", backedUp.size(), backedUp);
+ }
+ 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;
+ }
+
+ /**
+ * The candidate list can hold the same host twice.
listAllUpAndEnabledNonHAHosts joins host_tags
+ * without collapsing the rows, so a host carrying two tags arrives once
per tag, and that path is
+ * taken whenever a VM has no host tag to filter on - system VMs, most
commonly. Ranking is a set
+ * operation: a repeat is harmless to the score, which is keyed by host,
but it costs a slot in
+ * the selection spread and would bias the shuffle towards whichever host
happens to be repeated.
+ */
+ protected List<Host> distinctHosts(List<? extends Host> hosts) {
+ if (hosts == null) {
+ return new ArrayList<>();
+ }
+ Map<Long, Host> distinct = new LinkedHashMap<>();
+ for (Host host : hosts) {
+ distinct.putIfAbsent(host.getId(), host);
+ }
+ return new ArrayList<>(distinct.values());
+ }
+
+ protected Map<Long, Ternary<Long, Long, Long>> countVmsByHost(long zoneId,
Long podId, Long clusterId) {
+ return vmInstanceDao.countVmsByHost(zoneId, podId, clusterId,
+ new Date(System.currentTimeMillis() -
RecentStartWindow.value() * 1000L));
+ }
+
+ protected Map<Long, Double> score(long zoneId, Long podId, Long clusterId,
List<? extends Host> hosts) {
+ return score(zoneId, clusterId, hosts, countVmsByHost(zoneId, podId,
clusterId));
+ }
+
+ protected Map<Long, Double> score(long zoneId, Long clusterId, List<?
extends Host> hosts,
+ Map<Long, Ternary<Long, Long, Long>> vmCounts) {
+ List<CapacityVO> capacities =
capacityDao.listHostCapacityByCapacityTypes(zoneId, clusterId,
+ List.of(Capacity.CAPACITY_TYPE_CPU,
Capacity.CAPACITY_TYPE_MEMORY));
+
+ 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;
+ }
+ Ternary<Long, 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);
+ }
+ }
+ }
+
+ /**
+ * Moves hosts with too many VMs still in Starting out of {@code healthy}
and into
+ * {@code backedUp}, least backed up first.
+ *
+ * This is the one signal in the algorithm that reacts inside a single
deployment. Allocation is
+ * not charged until a VM reaches Starting, and a utilisation average is a
sample interval and a
+ * half life behind, so neither notices a burst of deployments until it is
over. The count of
+ * VMs in Starting is read fresh on every ranking, and a host that is
struggling holds that count
+ * up for as long as it struggles - which is the point, since a host whose
VMs take minutes
+ * rather than seconds to start is precisely the one that should stop
being chosen.
+ *
+ * The fallback order within the held-back group is by starting count
rather than by score: if
+ * every host ends up here, the least backed up one is the least bad place
to add another.
+ */
+ protected void partitionByStartingVms(Long clusterId, List<Host> healthy,
+ Map<Long, Ternary<Long, Long, Long>> vmCounts, List<Host>
backedUp) {
+ int threshold = startingVmsThreshold(clusterId);
+ if (threshold <= 0) {
+ return;
+ }
+ healthy.removeIf(host -> {
+ if (startingVms(vmCounts, host) >= threshold) {
+ backedUp.add(host);
+ return true;
+ }
+ return false;
+ });
+ backedUp.sort(Comparator.comparingLong(h -> startingVms(vmCounts, h)));
+ }
+
+ protected int startingVmsThreshold(Long clusterId) {
+ return (int) valueIn(StartingVmsThreshold, clusterId);
+ }
+
+ private static long startingVms(Map<Long, Ternary<Long, Long, Long>>
vmCounts, Host host) {
+ return vmCounts.getOrDefault(host.getId(), NO_VMS).third();
+ }
+
+ /**
+ * 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. Every host
in a ranking is then
+ * scored with the same values even if a setting changes part way through,
and a bad value is
+ * reported once per ranking rather than once 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(CpuAllocatedWeight, clusterId);
+ cpuUsed = nonNegative(CpuUsedWeight, clusterId);
+ memoryAllocated = nonNegative(MemoryAllocatedWeight, clusterId);
+ memoryUsed = nonNegative(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<?>[] {
+ CpuAllocatedWeight,
+ CpuUsedWeight,
+ MemoryAllocatedWeight,
+ MemoryUsedWeight,
+ VmCountWeight,
+ RecentStartWeight,
+ DominantResourceWeight,
+ RecentStartWindow,
+ ExpectedVmsPerHost,
+ CpuUtilisationThreshold,
+ MemoryUtilisationThreshold,
+ SelectionSpread,
+ StartingVmsThreshold
+ };
+ }
+}
diff --git
a/server/src/main/resources/META-INF/cloudstack/server-allocator/spring-server-allocator-context.xml
b/server/src/main/resources/META-INF/cloudstack/server-allocator/spring-server-allocator-context.xml
index 28b96b8d194..69aea2cf845 100644
---
a/server/src/main/resources/META-INF/cloudstack/server-allocator/spring-server-allocator-context.xml
+++
b/server/src/main/resources/META-INF/cloudstack/server-allocator/spring-server-allocator-context.xml
@@ -31,6 +31,12 @@
<property name="name" value="Balance" />
</bean>
+ <bean id="hostLoadTracker"
+ class="com.cloud.agent.manager.allocator.impl.HostLoadTracker" />
+
+ <bean id="weightedHostScorer"
+ class="com.cloud.agent.manager.allocator.impl.WeightedHostScorer" />
+
<bean id="firstFitAllocator"
class="com.cloud.agent.manager.allocator.impl.FirstFitAllocator" />
diff --git
a/server/src/test/java/com/cloud/agent/manager/allocator/impl/HostLoadTrackerTest.java
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/HostLoadTrackerTest.java
new file mode 100644
index 00000000000..0be9b1310f0
--- /dev/null
+++
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/HostLoadTrackerTest.java
@@ -0,0 +1,182 @@
+// 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 org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InjectMocks;
+import org.mockito.Mockito;
+import org.mockito.junit.MockitoJUnitRunner;
+
+import com.cloud.host.HostStats;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+@RunWith(MockitoJUnitRunner.class)
+public class HostLoadTrackerTest {
+
+ private static final long HOST_ID = 1L;
+ private static final long HALF_LIFE_MS = 300 * 1000L;
+
+ @InjectMocks
+ private HostLoadTracker tracker = new HostLoadTracker();
+
+ private long now;
+
+ @Before
+ public void setUp() {
+ tracker.clear();
+ now = 1_000_000L;
+ }
+
+ private HostStats stats(double cpuPercent, double usedMemoryFraction) {
+ HostStats stats = Mockito.mock(HostStats.class);
+
Mockito.lenient().when(stats.getCpuUtilization()).thenReturn(cpuPercent);
+ Mockito.lenient().when(stats.getTotalMemoryKBs()).thenReturn(1000.0);
+ Mockito.lenient().when(stats.getFreeMemoryKBs()).thenReturn(1000.0 *
(1 - usedMemoryFraction));
+ return stats;
+ }
+
+ private void sample(double cpuPercent, double usedMemoryFraction, long
advanceMs) {
+ now += advanceMs;
+ tracker.record(HOST_ID, stats(cpuPercent, usedMemoryFraction), now);
+ }
+
+ private HostLoad load() {
+ return tracker.getLoad(HOST_ID, now);
+ }
+
+ @Test
+ public void testUnknownHostIsNotUsable() {
+ assertFalse(tracker.getLoad(999L, now).isUsable());
+ }
+
+ @Test
+ public void testFirstSampleIsTakenAsIs() {
+ sample(40, 0.6, 0);
+
+ HostLoad load = load();
+ assertTrue(load.isUsable());
+ assertEquals(0.40, load.getCpuUtilisation(), 1e-6);
+ assertEquals(0.60, load.getMemoryUtilisation(), 1e-6);
+ }
+
+ @Test
+ public void testSingleSpikeDoesNotDominateTheAverage() {
+ sample(10, 0.1, 0);
+ sample(100, 0.1, 60 * 1000L);
+
+ // one sample a fifth of a half life in should move the average part
of the way, not all of it
+ double cpu = load().getCpuUtilisation();
+ assertTrue("a single spike must not take over the average: " + cpu,
cpu < 0.30);
+ assertTrue("but it must move it: " + cpu, cpu > 0.10);
+ }
+
+ @Test
+ public void testSustainedLoadConvergesOnTheNewValue() {
+ sample(10, 0.1, 0);
+ for (int i = 0; i < 40; i++) {
+ sample(90, 0.9, 60 * 1000L);
+ }
+
+ HostLoad load = load();
+ assertEquals(0.90, load.getCpuUtilisation(), 0.01);
+ assertEquals(0.90, load.getMemoryUtilisation(), 0.01);
+ }
+
+ @Test
+ public void testHalfLifeMovesAverageHalfWay() {
+ sample(0, 0, 0);
+ sample(100, 1.0, HALF_LIFE_MS);
+
+ assertEquals(0.5, load().getCpuUtilisation(), 0.01);
+ }
+
+ @Test
+ public void testMissedSamplesDecayByElapsedTimeNotSampleCount() {
+ sample(0, 0, 0);
+ sample(100, 1.0, 4 * HALF_LIFE_MS);
+
+ // four half lives of catching up in one sample, so almost all the way
there
+ assertTrue(load().getCpuUtilisation() > 0.9);
+ }
+
+ @Test
+ public void testNullStatsAreIgnored() {
+ tracker.record(HOST_ID, null, now);
+ assertFalse(load().isUsable());
+ }
+
+ @Test
+ public void testHostReportingNoMemoryIsIgnored() {
+ HostStats broken = Mockito.mock(HostStats.class);
+ Mockito.lenient().when(broken.getTotalMemoryKBs()).thenReturn(0.0);
+
+ tracker.record(HOST_ID, broken, now);
+
+ assertFalse(load().isUsable());
+ }
+
+ @Test
+ public void testUnchangedReadingIsNotFoldedAgain() {
+ // StatsCollector keeps the previous entry when a poll fails, so the
same object comes back
+ HostStats reading = stats(10, 0.1);
+ tracker.record(HOST_ID, reading, now);
+ // stay inside the staleness window so this tests folding, not expiry
+ for (int i = 0; i < 5; i++) {
+ now += 60 * 1000L;
+ tracker.record(HOST_ID, reading, now);
+ }
+
+ assertEquals("re-reading one measurement must not count as six", 1,
load().getSamples());
+ }
+
+ @Test
+ public void testAHostThatStopsReportingBecomesUnusable() {
+ HostStats reading = stats(10, 0.1);
+ tracker.record(HOST_ID, reading, now);
+ assertTrue(load().isUsable());
+
+ // the agent stops updating; StatsCollector keeps handing back the
same stale entry
+ for (int i = 0; i < 20; i++) {
+ now += 60 * 1000L;
+ tracker.record(HOST_ID, reading, now);
+ }
+
+ assertFalse("a host that stopped reporting must not keep vouching for
itself", load().isUsable());
+ }
+
+ @Test
+ public void testFreshReadingsKeepAHostUsable() {
+ for (int i = 0; i < 20; i++) {
+ sample(10 + i, 0.1, 60 * 1000L);
+ }
+ assertTrue(load().isUsable());
+ }
+
+ @Test
+ public void testOutOfRangeValuesAreClamped() {
+ sample(250, 2.0, 0);
+
+ HostLoad load = load();
+ assertEquals(1.0, load.getCpuUtilisation(), 1e-6);
+ assertEquals(1.0, load.getMemoryUtilisation(), 1e-6);
+ }
+}
diff --git
a/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerRankTest.java
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerRankTest.java
new file mode 100644
index 00000000000..a597f3922c4
--- /dev/null
+++
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerRankTest.java
@@ -0,0 +1,339 @@
+// 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.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InjectMocks;
+import org.mockito.Mock;
+import org.mockito.Mockito;
+import org.mockito.junit.MockitoJUnitRunner;
+import org.springframework.test.util.ReflectionTestUtils;
+
+import com.cloud.capacity.Capacity;
+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.utils.Ternary;
+import com.cloud.vm.dao.VMInstanceDao;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * Exercises rank() as the allocator calls it, rather than the scoring
function alone, so the
+ * capacity denominator, the utilisation thresholds and the random spread are
all covered.
+ */
+@RunWith(MockitoJUnitRunner.class)
+public class WeightedHostScorerRankTest {
+
+ private static final long ZONE = 1L;
+ private static final long CLUSTER = 7L;
+ private static final long CORES = 192L * 2400L;
+ private static final long MEMORY = 1_132_000L * 1024L * 1024L;
+ private static final int CPU_OVERCOMMIT = 10;
+ private static final int MEMORY_OVERCOMMIT = 4;
+
+ @Mock
+ private CapacityDao capacityDao;
+
+ @Mock
+ private VMInstanceDao vmInstanceDao;
+
+ @Mock
+ private ClusterDetailsDao clusterDetailsDao;
+
+ @Mock
+ private HostLoadTracker hostLoadTracker;
+
+ @InjectMocks
+ private WeightedHostScorer scorer = new WeightedHostScorer();
+
+
+ private final List<CapacityVO> capacities = new ArrayList<>();
+ private final Map<Long, Ternary<Long, Long, Long>> vmCounts = new
HashMap<>();
+ private final Map<Long, Host> hosts = new HashMap<>();
+
+ @Before
+ public void setUp() {
+ scorer.random = new Random(1L);
+
Mockito.lenient().when(clusterDetailsDao.findDetail(Mockito.eq(CLUSTER),
Mockito.contains("cpu")))
+ .thenReturn(new ClusterDetailsVO(CLUSTER,
"cpuOvercommitRatio", String.valueOf(CPU_OVERCOMMIT)));
+
Mockito.lenient().when(clusterDetailsDao.findDetail(Mockito.eq(CLUSTER),
Mockito.contains("memory")))
+ .thenReturn(new ClusterDetailsVO(CLUSTER,
"memoryOvercommitRatio", String.valueOf(MEMORY_OVERCOMMIT)));
+
Mockito.lenient().when(capacityDao.listHostCapacityByCapacityTypes(Mockito.eq(ZONE),
Mockito.eq(CLUSTER), Mockito.any()))
+ .thenReturn(capacities);
+ Mockito.lenient().when(vmInstanceDao.countVmsByHost(Mockito.eq(ZONE),
Mockito.any(), Mockito.eq(CLUSTER), Mockito.any()))
+ .thenReturn(vmCounts);
+ }
+
+ private CapacityVO capacity(long hostId, short type, long used, long
total) {
+ CapacityVO capacity = new CapacityVO(hostId, ZONE, 1L, CLUSTER, used,
total, type);
+ capacity.setReservedCapacity(0L);
+ return capacity;
+ }
+
+ /** Registers a host with a share of its allocatable CPU and memory
already committed. */
+ private Host host(long id, String name, double cpuAllocatedFraction,
double memoryAllocatedFraction,
+ HostLoad load, long vms) {
+ return host(id, name, cpuAllocatedFraction, memoryAllocatedFraction,
load, vms, 0L);
+ }
+
+ /** As above, with a number of VMs left sitting in Starting on the host. */
+ private Host host(long id, String name, double cpuAllocatedFraction,
double memoryAllocatedFraction,
+ HostLoad load, long vms, long startingVms) {
+ Host host = Mockito.mock(Host.class);
+ Mockito.lenient().when(host.getId()).thenReturn(id);
+ Mockito.lenient().when(host.getName()).thenReturn(name);
+ capacities.add(capacity(id, Capacity.CAPACITY_TYPE_CPU,
+ (long) (CORES * CPU_OVERCOMMIT * cpuAllocatedFraction),
CORES));
+ capacities.add(capacity(id, Capacity.CAPACITY_TYPE_MEMORY,
+ (long) (MEMORY * MEMORY_OVERCOMMIT * memoryAllocatedFraction),
MEMORY));
+ vmCounts.put(id, new Ternary<>(vms, 0L, startingVms));
+ Mockito.lenient().when(hostLoadTracker.getLoad(id)).thenReturn(load);
+ hosts.put(id, host);
+ return host;
+ }
+
+ private List<String> rankedNames(List<? extends Host> input) {
+ return scorer.rank(ZONE, 1L, CLUSTER,
input).stream().map(Host::getName).collect(Collectors.toList());
+ }
+
+ @Test
+ public void testAllocationIsMeasuredAgainstTheOvercommittedTotal() {
+ // both hosts are well past their physical CPU, which is normal at a
factor of 10.
+ // if the denominator ignored the factor both would clamp to 1.0 and
rank equal.
+ Host light = host(1L, "light", 0.20, 0.20, new HostLoad(0.1, 0.1, 5),
20);
+ Host heavy = host(2L, "heavy", 0.80, 0.20, new HostLoad(0.1, 0.1, 5),
20);
+
+ Map<Long, Double> scores = scorer.score(ZONE, 1L, CLUSTER,
Arrays.asList(light, heavy));
+
+ assertTrue("hosts past their physical size must still be
distinguishable",
+ scores.get(heavy.getId()) > scores.get(light.getId()));
+ }
+
+ @Test
+ public void testARepeatedHostIsRankedOnce() {
+ // listAllUpAndEnabledNonHAHosts returns a host once per tag it
carries, so the same host
+ // reaches the allocator more than once whenever a VM has no tag to
filter the list by.
+ // A repeat would take an extra slot in the selection spread and bias
the shuffle to it.
+ Host light = host(1L, "light", 0.10, 0.10, new HostLoad(0.10, 0.10,
10), 10);
+ Host middle = host(2L, "middle", 0.40, 0.40, new HostLoad(0.40, 0.40,
10), 40);
+ Host heavy = host(3L, "heavy", 0.70, 0.70, new HostLoad(0.70, 0.60,
10), 70);
+
+ List<String> ranked = rankedNames(Arrays.asList(middle, light, middle,
heavy, light));
+
+ assertEquals("each host must be offered exactly once", 3,
ranked.size());
+ assertEquals("no host may appear twice", new HashSet<>(ranked).size(),
ranked.size());
+ assertTrue("no host may be dropped",
ranked.containsAll(Arrays.asList("light", "middle", "heavy")));
+ }
+
+ @Test
+ public void testBusyHostRanksBehindQuietOneAtEqualAllocation() {
+ Host quiet = host(1L, "quiet", 0.30, 0.30, new HostLoad(0.05, 0.05,
10), 30);
+ Host busy = host(2L, "busy", 0.30, 0.30, new HostLoad(0.70, 0.30, 10),
30);
+
+ assertEquals("quiet", rankedNames(Arrays.asList(busy, quiet)).get(0));
+ }
+
+ @Test
+ public void testHostOverThresholdIsNotChosenWhileAHealthyOneExists() {
+ // one healthy host and five over threshold: the spread must not
shuffle a busy host in front
+ List<Host> input = new ArrayList<>();
+ input.add(host(1L, "healthy", 0.30, 0.30, new HostLoad(0.50, 0.50,
10), 30));
+ for (long id = 2; id <= 6; id++) {
+ input.add(host(id, "busy" + id, 0.30, 0.30, new HostLoad(0.95,
0.50, 10), 30));
+ }
+
+ for (int attempt = 0; attempt < 50; attempt++) {
+ assertEquals("the only healthy host must always lead", "healthy",
rankedNames(input).get(0));
+ }
+ }
+
+ @Test
+ public void testUnmeasuredHostRanksBehindEveryMeasuredHost() {
+ // a host whose stats have stopped must not look idle and collect the
deployments
+ Host measured = host(1L, "measured", 0.60, 0.60, new HostLoad(0.40,
0.40, 10), 60);
+ Host unmeasured = host(2L, "unmeasured", 0.05, 0.05, HostLoad.UNKNOWN,
2);
+
+ List<String> ranked = rankedNames(Arrays.asList(unmeasured, measured));
+
+ assertEquals("measured", ranked.get(0));
+ assertEquals("unmeasured", ranked.get(1));
+ }
+
+ @Test
+ public void testRankingFallsBackToAllocationWhenNothingIsMeasured() {
+ Host light = host(1L, "light", 0.10, 0.10, HostLoad.UNKNOWN, 5);
+ Host heavy = host(2L, "heavy", 0.90, 0.90, HostLoad.UNKNOWN, 90);
+
+ assertEquals("light", rankedNames(Arrays.asList(heavy, light)).get(0));
+ }
+
+ @Test
+ public void testEveryHostIsStillOfferedWhenTheWholeClusterIsBusy() {
+ List<Host> input = Arrays.asList(
+ host(1L, "a", 0.30, 0.30, new HostLoad(0.95, 0.50, 10), 30),
+ host(2L, "b", 0.40, 0.30, new HostLoad(0.97, 0.50, 10), 40));
+
+ List<String> ranked = rankedNames(input);
+
+ assertEquals("deployment must remain possible", 2, ranked.size());
+ }
+
+ @Test
+ public void testSpreadVariesTheLeadAmongHealthyHosts() {
+ List<Host> input = Arrays.asList(
+ host(1L, "a", 0.30, 0.30, new HostLoad(0.10, 0.10, 10), 30),
+ host(2L, "b", 0.31, 0.30, new HostLoad(0.10, 0.10, 10), 30),
+ host(3L, "c", 0.32, 0.30, new HostLoad(0.10, 0.10, 10), 30),
+ host(4L, "d", 0.90, 0.30, new HostLoad(0.10, 0.10, 10), 90));
+
+ Set<String> leaders = new HashSet<>();
+ for (int attempt = 0; attempt < 200; attempt++) {
+ leaders.add(rankedNames(input).get(0));
+ }
+
+ assertTrue("concurrent deployments must not all pick one host",
leaders.size() > 1);
+ assertFalse("the clearly worst host must never lead",
leaders.contains("d"));
+ }
+
+ @Test
+ public void testHostMissingACapacityRowIsNotRankedFirst() {
+ Host complete = host(1L, "complete", 0.60, 0.60, new HostLoad(0.40,
0.40, 10), 60);
+ Host partial = Mockito.mock(Host.class);
+ Mockito.lenient().when(partial.getId()).thenReturn(2L);
+ Mockito.lenient().when(partial.getName()).thenReturn("partial");
+ // only a CPU row: memory must not be treated as untouched
+ capacities.add(capacity(2L, Capacity.CAPACITY_TYPE_CPU, 0L, CORES));
+
+ List<String> ranked = rankedNames(Arrays.asList(partial, complete));
+
+ assertEquals("complete", ranked.get(0));
+ assertEquals("partial", ranked.get(1));
+ }
+
+ @Test
+ public void testHostWithTooManyVmsStartingIsHeldBack() {
+ // the emptiest host in the cluster by every other measure, but
already working through a
+ // queue of starts: the next deployment must not join that queue
+ Host queueing = host(1L, "queueing", 0.05, 0.05, new HostLoad(0.05,
0.05, 10), 5, 12);
+ Host busier = host(2L, "busier", 0.60, 0.60, new HostLoad(0.50, 0.50,
10), 60, 0);
+
+ List<String> ranked = rankedNames(Arrays.asList(queueing, busier));
+
+ assertEquals("busier", ranked.get(0));
+ assertEquals("queueing", ranked.get(1));
+ }
+
+ @Test
+ public void testHostBelowTheStartingThresholdIsNotHeldBack() {
+ Host starting = host(1L, "starting", 0.05, 0.05, new HostLoad(0.05,
0.05, 10), 5, 9);
+ Host busier = host(2L, "busier", 0.60, 0.60, new HostLoad(0.50, 0.50,
10), 60, 0);
+
+ assertEquals("nine starts is under the default threshold of ten",
+ "starting", rankedNames(Arrays.asList(starting,
busier)).get(0));
+ }
+
+ @Test
+ public void testEveryHostBackedUpStillDeploys() {
+ // nothing is eligible, but a deployment must still be placed rather
than failing. The
+ // held-back group is ordered by starting count rather than by score,
so the most backed up
+ // host stays last even though it is the cheapest on every other
measure.
+ Host worst = host(1L, "worst", 0.10, 0.10, new HostLoad(0.10, 0.10,
10), 10, 40);
+ Host least = host(2L, "least", 0.80, 0.80, new HostLoad(0.60, 0.60,
10), 80, 11);
+ Host middle = host(3L, "middle", 0.10, 0.10, new HostLoad(0.10, 0.10,
10), 10, 20);
+ Host nearly = host(4L, "nearly", 0.10, 0.10, new HostLoad(0.10, 0.10,
10), 10, 25);
+
+ List<Host> input = Arrays.asList(worst, least, middle, nearly);
+
+ for (int attempt = 0; attempt < 200; attempt++) {
+ List<String> ranked = rankedNames(input);
+ assertEquals("every host must still be offered", 4, ranked.size());
+ assertEquals("the most backed up host must stay last", "worst",
ranked.get(3));
+ assertFalse("the most backed up host must never lead",
"worst".equals(ranked.get(0)));
+ }
+ }
+
+ @Test
+ public void testStartingThresholdOfZeroDisablesTheGate() {
+ scorer = new WeightedHostScorer() {
+ @Override
+ protected int startingVmsThreshold(Long clusterId) {
+ return 0;
+ }
+ };
+ ReflectionTestUtils.setField(scorer, "capacityDao", capacityDao);
+ ReflectionTestUtils.setField(scorer, "clusterDetailsDao",
clusterDetailsDao);
+ ReflectionTestUtils.setField(scorer, "vmInstanceDao", vmInstanceDao);
+ ReflectionTestUtils.setField(scorer, "hostLoadTracker",
hostLoadTracker);
+ scorer.random = new Random(1L);
+
+ Host queueing = host(1L, "queueing", 0.05, 0.05, new HostLoad(0.05,
0.05, 10), 5, 50);
+ Host busier = host(2L, "busier", 0.60, 0.60, new HostLoad(0.50, 0.50,
10), 60, 0);
+
+ assertEquals("with the gate disabled only the score matters",
+ "queueing", rankedNames(Arrays.asList(queueing,
busier)).get(0));
+ }
+
+ @Test
+ public void testSpreadStillAppliesWhenNoHostIsEligible() {
+ // regression: the spread used to be applied to the healthy list only.
With every host held
+ // back, healthy was empty, the shuffle was a no-op and concurrent
deployments fell through
+ // in strict score order - agreeing on one host in exactly the
conditions that created the
+ // pile-up in the first place.
+ List<Host> input = Arrays.asList(
+ host(1L, "a", 0.30, 0.30, new HostLoad(0.10, 0.10, 10), 30,
20),
+ host(2L, "b", 0.31, 0.30, new HostLoad(0.10, 0.10, 10), 30,
20),
+ host(3L, "c", 0.32, 0.30, new HostLoad(0.10, 0.10, 10), 30,
20));
+
+ Set<String> leaders = new HashSet<>();
+ for (int attempt = 0; attempt < 200; attempt++) {
+ leaders.add(rankedNames(input).get(0));
+ }
+
+ assertTrue("held-back hosts must still be spread over, not handed out
in strict order",
+ leaders.size() > 1);
+ }
+
+ @Test
+ public void testUnmeasuredHostIsPreferredOverAResourceSaturatedOne() {
+ // regression for the same branch: with healthy empty but an
unmeasured host present, the
+ // ordering between the remaining tiers must still hold
+ Host saturated = host(1L, "saturated", 0.95, 0.95, new HostLoad(0.99,
0.99, 10), 95);
+ Host unknown = host(2L, "unknown", 0.10, 0.10, HostLoad.UNKNOWN, 10);
+
+ List<String> ranked = rankedNames(Arrays.asList(saturated, unknown));
+
+ assertEquals("unknown", ranked.get(0));
+ assertEquals("saturated", ranked.get(1));
+ }
+}
diff --git
a/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerTest.java
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerTest.java
new file mode 100644
index 00000000000..d5097d79d21
--- /dev/null
+++
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedHostScorerTest.java
@@ -0,0 +1,175 @@
+// 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.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InjectMocks;
+import org.mockito.Mock;
+import org.mockito.Mockito;
+import org.mockito.junit.MockitoJUnitRunner;
+
+import com.cloud.host.Host;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+
+@RunWith(MockitoJUnitRunner.class)
+public class WeightedHostScorerTest {
+
+ private static final HostLoad IDLE = new HostLoad(0.0, 0.0, 10);
+
+ @Mock
+ private HostLoadTracker hostLoadTracker;
+
+ @InjectMocks
+ private WeightedHostScorer scorer = new WeightedHostScorer();
+
+ private long nextHostId;
+
+ @Before
+ public void setUp() {
+ nextHostId = 1;
+ }
+
+ private Host host(String name) {
+ Host host = Mockito.mock(Host.class);
+ Mockito.lenient().when(host.getId()).thenReturn(nextHostId++);
+ Mockito.lenient().when(host.getName()).thenReturn(name);
+ return host;
+ }
+
+ private double score(double cpuAllocated, double memAllocated, HostLoad
load, long vms, long recentStarts) {
+ return scorer.scoreHostIn(null, cpuAllocated, memAllocated, load, vms,
recentStarts);
+ }
+
+ @Test
+ public void testIdleHostScoresZero() {
+ assertEquals(0.0, score(0, 0, IDLE, 0, 0), 1e-9);
+ }
+
+ @Test
+ public void testMoreAllocationScoresHigher() {
+ assertTrue(score(0.5, 0.5, IDLE, 0, 0) > score(0.1, 0.1, IDLE, 0, 0));
+ }
+
+ @Test
+ public void testBusyHostScoresHigherThanIdleHostWithSameAllocation() {
+ HostLoad busy = new HostLoad(0.9, 0.5, 10);
+ assertTrue("measured load must separate hosts that look identical by
allocation",
+ score(0.05, 0.05, busy, 20, 0) > score(0.05, 0.05, IDLE, 20,
0));
+ }
+
+ @Test
+ public void testUtilisationIgnoredUntilThereAreSamples() {
+ // a host with no samples must not be treated as idle, it must rank on
allocation alone
+ double noSamples = score(0.4, 0.4, HostLoad.UNKNOWN, 10, 0);
+ double idleSamples = score(0.4, 0.4, IDLE, 10, 0);
+ assertTrue("a host with no load samples should not outrank a
measurably idle one",
+ noSamples >= idleSamples);
+ }
+
+ @Test
+ public void testDominantResourcePenalisesLopsidedHost() {
+ // same mean across resources, but one host is nearly out of memory
+ double balanced = score(0.5, 0.5, IDLE, 0, 0);
+ double lopsided = score(0.05, 0.95, IDLE, 0, 0);
+ assertTrue("a host nearly out of one resource must not rank as well as
an evenly loaded one",
+ lopsided > balanced);
+ }
+
+ @Test
+ public void testDominantResourceUsesUtilisationWhenHigherThanAllocation() {
+ HostLoad reclaimedButBusy = new HostLoad(0.95, 0.95, 10);
+ assertTrue(score(0.05, 0.05, reclaimedButBusy, 0, 0) > score(0.05,
0.05, IDLE, 0, 0));
+ }
+
+ @Test
+ public void testVmCountPenalisesHost() {
+ assertTrue(score(0.1, 0.1, IDLE, 120, 0) > score(0.1, 0.1, IDLE, 5,
0));
+ }
+
+ @Test
+ public void testRecentStartsPenaliseHost() {
+ assertTrue("VMs that just started are not yet visible in allocation or
utilisation",
+ score(0.1, 0.1, IDLE, 20, 20) > score(0.1, 0.1, IDLE, 20, 0));
+ }
+
+ @Test
+ public void testScoreStaysWithinUnitRange() {
+ assertTrue(score(1, 1, new HostLoad(1, 1, 10), 1000, 1000) <= 1.0);
+ assertTrue(score(0, 0, IDLE, 0, 0) >= 0.0);
+ }
+
+ @Test
+ public void testBusyHostIsHeldBackByThreshold() {
+ Host quiet = host("quiet");
+ Host busy = host("busy");
+ Mockito.when(hostLoadTracker.getLoad(quiet.getId())).thenReturn(new
HostLoad(0.10, 0.10, 10));
+ Mockito.when(hostLoadTracker.getLoad(busy.getId())).thenReturn(new
HostLoad(0.99, 0.10, 10));
+
+ List<Host> healthy = new ArrayList<>();
+ List<Host> tooBusy = new ArrayList<>();
+ scorer.partitionByUtilisation(null, new ArrayList<>(List.of(quiet,
busy)), healthy, tooBusy);
+
+ assertEquals(1, healthy.size());
+ assertSame(quiet, healthy.get(0));
+ assertSame("host over the CPU threshold must be held back", busy,
tooBusy.get(0));
+ }
+
+ @Test
+ public void testThresholdIsIgnoredWhenEveryHostIsBusy() {
+ Host a = host("a");
+ Host b = host("b");
+
Mockito.when(hostLoadTracker.getLoad(Mockito.anyLong())).thenReturn(new
HostLoad(0.99, 0.99, 10));
+
+ List<Host> healthy = new ArrayList<>();
+ List<Host> tooBusy = new ArrayList<>();
+ scorer.partitionByUtilisation(null, new ArrayList<>(List.of(a, b)),
healthy, tooBusy);
+
+ assertEquals("both hosts are over threshold", 2, tooBusy.size());
+ assertTrue(healthy.isEmpty());
+ }
+
+ @Test
+ public void testSelectionSpreadVariesTheChosenHost() {
+ Set<String> chosen = new HashSet<>();
+ List<Host> hosts = List.of(host("a"), host("b"), host("c"), host("d"),
host("e"));
+ for (int i = 0; i < 200; i++) {
+ List<Host> ranked = new ArrayList<>(hosts);
+ scorer.applySelectionSpread(null, ranked);
+ chosen.add(ranked.get(0).getName());
+ }
+ assertNotEquals("strict ordering sends every concurrent deployment to
the same host", 1, chosen.size());
+ assertTrue("only the best scoring hosts should be candidates",
chosen.size() <= 3);
+ }
+
+ @Test
+ public void testSelectionSpreadLeavesShortListsAlone() {
+ List<Host> ranked = new ArrayList<>(List.of(host("only")));
+ scorer.applySelectionSpread(null, ranked);
+ assertEquals(1, ranked.size());
+ }
+}
diff --git
a/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedPlacementDistributionTest.java
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedPlacementDistributionTest.java
new file mode 100644
index 00000000000..22fa6c56583
--- /dev/null
+++
b/server/src/test/java/com/cloud/agent/manager/allocator/impl/WeightedPlacementDistributionTest.java
@@ -0,0 +1,319 @@
+// 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.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Random;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertTrue;
+
+/**
+ * Simulates placement over a churning, heavily overprovisioned fleet.
+ *
+ * This is the regression fixture for the failure the weighted scoring exists
to prevent. Ranking
+ * hosts on allocated capacity alone is blind to what a host is really doing,
and under a large
+ * overprovisioning factor the gap between the two can be enormous: a host can
report a few percent
+ * allocated while its cores are saturated. Anything the scheduler is not told
about - VMs it has
+ * lost track of, guests using far more than their share - is invisible, so
the emptiest looking
+ * host keeps being chosen no matter how hard it is working.
+ *
+ * Three things are modelled that a single-shot unit test cannot show:
+ *
+ * - deployments arrive in concurrent batches and every decision in a batch
reads the same figures,
+ * because capacity is only charged once a VM starts
+ * - real load that allocation cannot account for
+ * - VMs are short lived and their lifetimes vary, so hosts empty unevenly
+ *
+ * Deterministic: fixed seeds, no wall clock.
+ */
+public class WeightedPlacementDistributionTest {
+
+ private static final int HOSTS = 9;
+ private static final int CORES_PER_HOST = 192;
+ private static final int MEMORY_MB_PER_HOST = 1_132_000;
+ private static final int CPU_OVERCOMMIT = 10;
+ private static final int MEMORY_OVERCOMMIT = 4;
+
+ private static final int VM_CORES = 4;
+ private static final int VM_MEMORY_MB = 8_192;
+
+ private static final int BATCHES = 300;
+ private static final int VMS_PER_BATCH = 8;
+ private static final int SPREAD = 3;
+
+ /** Share of VMs that peg their cores for their whole life, as build
runners do. */
+ private static final double BUSY_FRACTION = 0.35;
+
+ /**
+ * Cores in use on some hosts that allocation knows nothing about. Stands
in for anything the
+ * scheduler cannot see - VMs it believes are gone, or guests far
exceeding their request.
+ */
+ private static final int UNACCOUNTED_CORES = 60;
+
+ private static final class SimHost {
+ final long id;
+ final double unaccountedCores;
+ int vms;
+ int recentStarts;
+ double busyCores;
+ double memoryMb;
+
+ SimHost(long id, double unaccountedCores) {
+ this.id = id;
+ this.unaccountedCores = unaccountedCores;
+ }
+
+ /** What the capacity tables would report: uniform per VM, against an
inflated total. */
+ double cpuAllocated() {
+ return (double) vms * VM_CORES / (CORES_PER_HOST * CPU_OVERCOMMIT);
+ }
+
+ double memoryAllocated() {
+ return (double) vms * VM_MEMORY_MB / ((double) MEMORY_MB_PER_HOST
* MEMORY_OVERCOMMIT);
+ }
+
+ /** What the host is really doing, including what allocation cannot
see. */
+ double realCores() {
+ return busyCores + unaccountedCores;
+ }
+
+ HostLoad load() {
+ return new HostLoad(Math.min(1, realCores() / CORES_PER_HOST),
+ Math.min(1, memoryMb / MEMORY_MB_PER_HOST), 10);
+ }
+ }
+
+ /** Frozen figures for one batch, so every decision in the batch sees the
same thing. */
+ private static final class HostView {
+ final SimHost host;
+ final double cpuAllocated;
+ final double memoryAllocated;
+ final HostLoad load;
+ final int vms;
+ final int recentStarts;
+
+ HostView(SimHost host) {
+ this.host = host;
+ this.cpuAllocated = host.cpuAllocated();
+ this.memoryAllocated = host.memoryAllocated();
+ this.load = host.load();
+ this.vms = host.vms;
+ this.recentStarts = host.recentStarts;
+ }
+ }
+
+ private interface Placement {
+ SimHost choose(List<HostView> snapshot, Random random);
+ }
+
+ /** What firstfitleastconsumed does today: strictly the lowest allocated
fraction. */
+ private static final Placement LEAST_ALLOCATED = (snapshot, random) ->
+ snapshot.stream().min(Comparator.comparingDouble(v ->
v.cpuAllocated)).orElseThrow().host;
+
+ /**
+ * Allocation-only ranking with the same random spread as the weighted
arm. Isolates what the
+ * scoring contributes from what the spread alone contributes.
+ */
+ private static final Placement LEAST_ALLOCATED_WITH_SPREAD = (snapshot,
random) -> {
+ List<HostView> ranked = new ArrayList<>(snapshot);
+ ranked.sort(Comparator.comparingDouble(v -> v.cpuAllocated));
+ return ranked.get(random.nextInt(Math.min(SPREAD,
ranked.size()))).host;
+ };
+
+ private Placement weighted() {
+ WeightedHostScorer scorer = new WeightedHostScorer();
+ return (snapshot, random) -> {
+ List<HostView> ranked = new ArrayList<>(snapshot);
+ ranked.sort(Comparator.comparingDouble(v ->
+ scorer.scoreHostIn(null, v.cpuAllocated,
v.memoryAllocated, v.load, v.vms, v.recentStarts)));
+ return ranked.get(random.nextInt(Math.min(SPREAD,
ranked.size()))).host;
+ };
+ }
+
+ private static final class Result {
+ final double[] vmCounts;
+ final double[] realCores;
+
+ Result(double[] vmCounts, double[] realCores) {
+ this.vmCounts = vmCounts;
+ this.realCores = realCores;
+ }
+
+ double vmSkew() {
+ return max(vmCounts) / mean(vmCounts);
+ }
+
+ double loadSkew() {
+ return max(realCores) / mean(realCores);
+ }
+ }
+
+ /** The VMs to be placed, fixed before any arm runs so all arms see the
same workload. */
+ private List<int[]> workload(long seed) {
+ Random random = new Random(seed);
+ List<int[]> vms = new ArrayList<>();
+ for (int i = 0; i < BATCHES * VMS_PER_BATCH; i++) {
+ vms.add(new int[] {random.nextDouble() < BUSY_FRACTION ? 1 : 0, 10
+ random.nextInt(50)});
+ }
+ return vms;
+ }
+
+ private Result run(Placement placement, long seed) {
+ List<int[]> workload = workload(seed);
+ // a separate stream for placement decisions, so arms that consult it
differently still see
+ // the same workload
+ Random random = new Random(seed ^ 0x5DEECE66DL);
+ int next = 0;
+ List<SimHost> hosts = new ArrayList<>();
+ for (int i = 0; i < HOSTS; i++) {
+ // a third of the fleet carries load the scheduler cannot account
for
+ hosts.add(new SimHost(i + 1, i % 3 == 0 ? UNACCOUNTED_CORES : 0));
+ }
+ List<int[]> live = new ArrayList<>(); // {hostIndex, busy,
batchesLeft}
+
+ for (int batch = 0; batch < BATCHES; batch++) {
+ live.removeIf(vm -> {
+ if (--vm[2] > 0) {
+ return false;
+ }
+ SimHost host = hosts.get(vm[0]);
+ host.vms--;
+ host.memoryMb -= VM_MEMORY_MB;
+ if (vm[1] == 1) {
+ host.busyCores -= VM_CORES;
+ }
+ return true;
+ });
+
+ hosts.forEach(h -> h.recentStarts = 0);
+
+ List<HostView> snapshot = new ArrayList<>();
+ for (SimHost host : hosts) {
+ snapshot.add(new HostView(host));
+ }
+
+ for (int i = 0; i < VMS_PER_BATCH; i++) {
+ SimHost chosen = placement.choose(snapshot, random);
+ int[] vm = workload.get(next++);
+ boolean busy = vm[0] == 1;
+ chosen.vms++;
+ chosen.recentStarts++;
+ chosen.memoryMb += VM_MEMORY_MB;
+ if (busy) {
+ chosen.busyCores += VM_CORES;
+ }
+ // lifetimes vary, so hosts do not empty in the order they
filled
+ live.add(new int[] {hosts.indexOf(chosen), vm[0], vm[1]});
+ }
+ }
+
+ return new Result(hosts.stream().mapToDouble(h -> h.vms).toArray(),
+ hosts.stream().mapToDouble(SimHost::realCores).toArray());
+ }
+
+ private static double max(double[] values) {
+ return Arrays.stream(values).max().orElse(0);
+ }
+
+ private static double mean(double[] values) {
+ return Arrays.stream(values).average().orElse(0);
+ }
+
+ @Test
+ public void testAllocationOnlyOrderingPilesRealLoadOntoTheBusiestHosts() {
+ Result result = run(LEAST_ALLOCATED, 42L);
+
+ assertTrue(String.format("expected allocation-only ranking to be blind
to real load, "
+ + "got cores %s (max/mean %.2f)",
Arrays.toString(result.realCores), result.loadSkew()),
+ result.loadSkew() > 1.4);
+ }
+
+ @Test
+ public void testWeightedScoringKeepsRealLoadEven() {
+ Result result = run(weighted(), 42L);
+
+ // a third of the fleet carries a fixed handicap the scheduler can
only stop adding to, not
+ // remove, so some residual skew is expected. Measured across seeds:
allocation-only ranking
+ // lands at 1.84 to 2.01, weighted at 1.27 to 1.40.
+ assertTrue(String.format("real load should be spread, got cores %s
(max/mean %.2f)",
+ Arrays.toString(result.realCores), result.loadSkew()),
+ result.loadSkew() < 1.5);
+ }
+
+ @Test
+ public void testWeightedScoringBeatsAllocationOnlyOnEverySeed() {
+ for (long seed : new long[] {1L, 7L, 42L, 99L, 12345L}) {
+ double baseline = run(LEAST_ALLOCATED, seed).loadSkew();
+ double improved = run(weighted(), seed).loadSkew();
+ assertTrue(String.format("seed %d: weighted %.2f should beat
allocation-only %.2f",
+ seed, improved, baseline),
+ improved < baseline);
+ }
+ }
+
+ @Test
+ public void testTheScoringNotJustTheSpreadIsWhatEvensOutRealLoad() {
+ // the control: same random spread, ranking still blind to real load.
If the spread alone
+ // were doing the work, this arm would do as well as the weighted one.
+ for (long seed : new long[] {1L, 42L, 12345L}) {
+ double spreadOnly = run(LEAST_ALLOCATED_WITH_SPREAD,
seed).loadSkew();
+ double weighted = run(weighted(), seed).loadSkew();
+ assertTrue(String.format("seed %d: weighted %.2f should beat
spread-only %.2f",
+ seed, weighted, spreadOnly),
+ weighted < spreadOnly);
+ }
+ }
+
+ @Test
+ public void testWeightedScoringGivesFewerVmsToHostsCarryingHiddenLoad() {
+ Result result = run(weighted(), 42L);
+
+ // hosts 0, 3 and 6 carry load that allocation cannot see, so they
should get fewer VMs.
+ // uneven VM counts are the right answer here - it is real load that
should come out even.
+ double withHiddenLoad = mean(new double[] {result.vmCounts[0],
result.vmCounts[3], result.vmCounts[6]});
+ double withoutHiddenLoad = mean(new double[] {result.vmCounts[1],
result.vmCounts[2], result.vmCounts[4],
+ result.vmCounts[5], result.vmCounts[7], result.vmCounts[8]});
+
+ assertTrue(String.format("hosts with hidden load should take fewer
VMs: %.1f vs %.1f (counts %s)",
+ withHiddenLoad, withoutHiddenLoad,
Arrays.toString(result.vmCounts)),
+ withHiddenLoad < withoutHiddenLoad * 0.75);
+ assertTrue("no host should be left completely unused: " +
Arrays.toString(result.vmCounts),
+ min(result.vmCounts) > 0);
+ }
+
+ @Test
+ public void testAllocationOnlyOrderingIgnoresHiddenLoadEntirely() {
+ Result result = run(LEAST_ALLOCATED, 42L);
+
+ double withHiddenLoad = mean(new double[] {result.vmCounts[0],
result.vmCounts[3], result.vmCounts[6]});
+ double withoutHiddenLoad = mean(new double[] {result.vmCounts[1],
result.vmCounts[2], result.vmCounts[4],
+ result.vmCounts[5], result.vmCounts[7], result.vmCounts[8]});
+
+ assertTrue(String.format("allocation-only ranking should treat loaded
and idle hosts alike, got %.1f vs %.1f",
+ withHiddenLoad, withoutHiddenLoad),
+ withHiddenLoad > withoutHiddenLoad * 0.9);
+ }
+
+ private static double min(double[] values) {
+ return Arrays.stream(values).min().orElse(0);
+ }
+}
