[mesos] branch 1.10.x updated: Fixed performance of tracking resource totals in allocator's roles tree.
This is an automated email from the ASF dual-hosted git repository.
asekretenko pushed a commit to branch 1.10.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
The following commit(s) were added to refs/heads/1.10.x by this push:
new 1ff2fcd Fixed performance of tracking resource totals in allocator's
roles tree.
1ff2fcd is described below
commit 1ff2fcd90eabd98786531748869b8596120f7dfe
Author: Andrei Sekretenko
AuthorDate: Wed May 13 18:15:13 2020 +0200
Fixed performance of tracking resource totals in allocator's roles tree.
Before this patch, the roles tree was tracking total resources
offered/allocated to a role as a single `Resources` objects.
In the case when each agent has a limited number of unique resources
(for example, a single persistent voulme), this resulted in poor
asymptotic complexity of allocation versus the number of agents
(O(N^2)) that was clearly observable in
`HierarchicalAllocations_BENCHMARK_Test.PersistentVolumes`.
In addition, the role tree code was violating the convention that
`Resources` belonging to different agents should never be added.
This patch implements per-agent tracking of `Resources` in the roles
tree, thus improving the performance of allocation (and getting rid of
the potentially problematic O(N^2) asymptotic) in the case of many
agents with a limited number of unique resources each.
Review: https://reviews.apache.org/r/72508
---
src/master/allocator/mesos/hierarchical.cpp | 139
src/master/allocator/mesos/hierarchical.hpp | 69 ++
2 files changed, 152 insertions(+), 56 deletions(-)
diff --git a/src/master/allocator/mesos/hierarchical.cpp
b/src/master/allocator/mesos/hierarchical.cpp
index 5fe9ffc..9e50799 100644
--- a/src/master/allocator/mesos/hierarchical.cpp
+++ b/src/master/allocator/mesos/hierarchical.cpp
@@ -202,6 +202,46 @@ static hashmap>
unpackFrameworkOfferFilters(
}
+void ScalarResourceTotals::add(
+const SlaveID& slaveID,
+const Resources& resources)
+{
+ if (resources.scalars().empty()) {
+// In this case, we avoid adding an entry to `scalars` to maintain the
+// invariant that `scalars` doesn't track agents with empty resources.
+return;
+ }
+
+ scalarsTotal -= ResourceQuantities::fromScalarResources(scalars[slaveID]);
+ scalars.at(slaveID) += resources.scalars();
+ scalarsTotal += ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+}
+
+
+void ScalarResourceTotals::subtract(
+const SlaveID& slaveID,
+const Resources& resources)
+{
+ if (resources.scalars().empty()) {
+// `scalars` does not track agents with empty resources, thus subtracting
+// empty resources from an agent is valid regardless of whether its
+// resources are tracked in `scalars`.
+return;
+ }
+
+ CHECK_CONTAINS(scalars, slaveID);
+ CHECK_CONTAINS(scalars.at(slaveID), resources.scalars());
+
+ scalarsTotal -= ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+ scalars.at(slaveID) -= resources.scalars();
+ scalarsTotal += ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+
+ if (scalars.at(slaveID).empty()) {
+scalars.erase(slaveID);
+ }
+}
+
+
Role::Role(const string& _role, Role* _parent)
: role(_role),
basename(strings::split(role, "/").back()),
@@ -315,10 +355,10 @@ bool RoleTree::tryRemove(const std::string& role)
break;
}
-CHECK(current->allocatedScalars_.empty())
+CHECK(current->allocatedUnreservedNonRevocable.empty())
<< "An empty role " << current->role
<< " has non-empty allocated scalar resources: "
- << current->allocatedScalars_;
+ << current->allocatedUnreservedNonRevocable.quantities();
Role* parent = CHECK_NOTNULL(current->parent);
@@ -328,9 +368,17 @@ bool RoleTree::tryRemove(const std::string& role)
(*metrics)->removeRole(current->role);
}
-CHECK(current->offeredOrAllocatedScalars_.empty())
- << " role: " << role
- << " offeredOrAllocated: " << current->offeredOrAllocatedScalars_;
+CHECK(current->offeredOrAllocatedUnreservedNonRevocable.empty())
+ << "An empty role " << current->role
+ << " has non-empty offered or allocated"
+ << " unreserved non-revocable scalar resources: "
+ << current->offeredOrAllocatedUnreservedNonRevocable.quantities();
+
+CHECK(current->offeredOrAllocatedReserved.empty())
+ << "An empty role " << current->role
+ << " has non-empty offered or allocated reserved scalar resources: "
+ << current->offeredOrAllocatedReserved.quantities();
+
roles_.erase(current->role);
current = parent;
@@ -385,28 +433,32 @@ void RoleTree::untrackReservations(const Resources&
resources)
}
-void RoleTree::trackAllocated(const Resources& resources_)
+void RoleTree::trackAllocated(
+const SlaveID& slaveId,
+const Resources& resources_)
{
foreachpair (
[mesos] branch master updated: Fixed performance of tracking resource totals in allocator's roles tree.
This is an automated email from the ASF dual-hosted git repository.
asekretenko pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git
The following commit(s) were added to refs/heads/master by this push:
new dcb5585 Fixed performance of tracking resource totals in allocator's
roles tree.
dcb5585 is described below
commit dcb558597767aba9bcdcbc23e1a0a2674f653161
Author: Andrei Sekretenko
AuthorDate: Wed May 13 18:15:13 2020 +0200
Fixed performance of tracking resource totals in allocator's roles tree.
Before this patch, the roles tree was tracking total resources
offered/allocated to a role as a single `Resources` objects.
In the case when each agent has a limited number of unique resources
(for example, a single persistent voulme), this resulted in poor
asymptotic complexity of allocation versus the number of agents
(O(N^2)) that was clearly observable in
`HierarchicalAllocations_BENCHMARK_Test.PersistentVolumes`.
In addition, the role tree code was violating the convention that
`Resources` belonging to different agents should never be added.
This patch implements per-agent tracking of `Resources` in the roles
tree, thus improving the performance of allocation (and getting rid of
the potentially problematic O(N^2) asymptotic) in the case of many
agents with a limited number of unique resources each.
Review: https://reviews.apache.org/r/72508
---
src/master/allocator/mesos/hierarchical.cpp | 139
src/master/allocator/mesos/hierarchical.hpp | 69 ++
2 files changed, 152 insertions(+), 56 deletions(-)
diff --git a/src/master/allocator/mesos/hierarchical.cpp
b/src/master/allocator/mesos/hierarchical.cpp
index 5fe9ffc..9e50799 100644
--- a/src/master/allocator/mesos/hierarchical.cpp
+++ b/src/master/allocator/mesos/hierarchical.cpp
@@ -202,6 +202,46 @@ static hashmap>
unpackFrameworkOfferFilters(
}
+void ScalarResourceTotals::add(
+const SlaveID& slaveID,
+const Resources& resources)
+{
+ if (resources.scalars().empty()) {
+// In this case, we avoid adding an entry to `scalars` to maintain the
+// invariant that `scalars` doesn't track agents with empty resources.
+return;
+ }
+
+ scalarsTotal -= ResourceQuantities::fromScalarResources(scalars[slaveID]);
+ scalars.at(slaveID) += resources.scalars();
+ scalarsTotal += ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+}
+
+
+void ScalarResourceTotals::subtract(
+const SlaveID& slaveID,
+const Resources& resources)
+{
+ if (resources.scalars().empty()) {
+// `scalars` does not track agents with empty resources, thus subtracting
+// empty resources from an agent is valid regardless of whether its
+// resources are tracked in `scalars`.
+return;
+ }
+
+ CHECK_CONTAINS(scalars, slaveID);
+ CHECK_CONTAINS(scalars.at(slaveID), resources.scalars());
+
+ scalarsTotal -= ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+ scalars.at(slaveID) -= resources.scalars();
+ scalarsTotal += ResourceQuantities::fromScalarResources(scalars.at(slaveID));
+
+ if (scalars.at(slaveID).empty()) {
+scalars.erase(slaveID);
+ }
+}
+
+
Role::Role(const string& _role, Role* _parent)
: role(_role),
basename(strings::split(role, "/").back()),
@@ -315,10 +355,10 @@ bool RoleTree::tryRemove(const std::string& role)
break;
}
-CHECK(current->allocatedScalars_.empty())
+CHECK(current->allocatedUnreservedNonRevocable.empty())
<< "An empty role " << current->role
<< " has non-empty allocated scalar resources: "
- << current->allocatedScalars_;
+ << current->allocatedUnreservedNonRevocable.quantities();
Role* parent = CHECK_NOTNULL(current->parent);
@@ -328,9 +368,17 @@ bool RoleTree::tryRemove(const std::string& role)
(*metrics)->removeRole(current->role);
}
-CHECK(current->offeredOrAllocatedScalars_.empty())
- << " role: " << role
- << " offeredOrAllocated: " << current->offeredOrAllocatedScalars_;
+CHECK(current->offeredOrAllocatedUnreservedNonRevocable.empty())
+ << "An empty role " << current->role
+ << " has non-empty offered or allocated"
+ << " unreserved non-revocable scalar resources: "
+ << current->offeredOrAllocatedUnreservedNonRevocable.quantities();
+
+CHECK(current->offeredOrAllocatedReserved.empty())
+ << "An empty role " << current->role
+ << " has non-empty offered or allocated reserved scalar resources: "
+ << current->offeredOrAllocatedReserved.quantities();
+
roles_.erase(current->role);
current = parent;
@@ -385,28 +433,32 @@ void RoleTree::untrackReservations(const Resources&
resources)
}
-void RoleTree::trackAllocated(const Resources& resources_)
+void RoleTree::trackAllocated(
+const SlaveID& slaveId,
+const Resources& resources_)
{
foreachpair (
