You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by mz...@apache.org on 2019/03/18 20:54:50 UTC
[mesos] 03/16: Refactored and augmented `class ResourceQuantities`.
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit aa7b75fecd336b951fa8577ac5db26d3d0e28c1b
Author: Meng Zhu <mz...@mesosphere.io>
AuthorDate: Tue Feb 26 15:45:08 2019 -0800
Refactored and augmented `class ResourceQuantities`.
This patch removed the map interface of
`class ResourceQuantities`, added a few built-in
arithmetic operations. Now, absent resource items imply
there is no (zero) such resources.
Also added a to-do to add `class ResourceLimits` which
is similar but treats absent resource entries as having
infinite amount of such resource.
Also changed affected call sites and tests accordingly.
Review: https://reviews.apache.org/r/70062
---
src/common/resource_quantities.cpp | 105 +++++++++++++++++++++++---
src/common/resource_quantities.hpp | 49 ++++++------
src/master/allocator/sorter/drf/sorter.cpp | 15 +---
src/master/allocator/sorter/drf/sorter.hpp | 17 +----
src/master/allocator/sorter/random/sorter.cpp | 11 +--
src/master/allocator/sorter/random/sorter.hpp | 17 +----
src/tests/resource_quantities_tests.cpp | 33 +-------
7 files changed, 134 insertions(+), 113 deletions(-)
diff --git a/src/common/resource_quantities.cpp b/src/common/resource_quantities.cpp
index fbc19fb..bfd99b0 100644
--- a/src/common/resource_quantities.cpp
+++ b/src/common/resource_quantities.cpp
@@ -62,9 +62,10 @@ Try<ResourceQuantities> ResourceQuantities::fromString(const string& text)
return Error(
"Failed to parse '" + pair[1] + "' to quantity:"
" negative values are not allowed");
+ } else if (value->scalar().value() > 0) {
+ result.add(strings::trim(pair[0]), value->scalar());
}
-
- result[strings::trim(pair[0])] += value->scalar();
+ // Zero value is silently dropped.
}
return result;
@@ -79,7 +80,7 @@ ResourceQuantities ResourceQuantities::fromScalarResources(
foreach (const Resource& resource, resources) {
CHECK_EQ(Value::SCALAR, resource.type()) << " Resources: " << resources;
- result[resource.name()] += resource.scalar();
+ result.add(resource.name(), resource.scalar());
}
return result;
@@ -100,7 +101,7 @@ ResourceQuantities::ResourceQuantities(
// Use `auto` in place of `protobuf::MapPair<string, Value::Scalar>`
// below since `foreach` is a macro and cannot contain angle brackets.
foreach (auto&& quantity, quantities.quantities()) {
- (*this)[quantity.first] = quantity.second;
+ add(quantity.first, quantity.second);
}
}
@@ -121,7 +122,7 @@ ResourceQuantities::const_iterator ResourceQuantities::end()
}
-Option<Value::Scalar> ResourceQuantities::get(const string& name) const
+Value::Scalar ResourceQuantities::get(const string& name) const
{
// Don't bother binary searching since
// we don't expect a large number of elements.
@@ -134,19 +135,103 @@ Option<Value::Scalar> ResourceQuantities::get(const string& name) const
}
}
- return None();
+ return Value::Scalar();
}
-Value::Scalar& ResourceQuantities::operator[](const string& name)
+ResourceQuantities& ResourceQuantities::operator+=(
+ const ResourceQuantities& right)
{
+ size_t leftIndex = 0u;
+ size_t rightIndex = 0u;
+
+ // Since quantities are sorted in alphabetical order, we can walk them
+ // at the same time.
+ while (leftIndex < size() && rightIndex < right.size()) {
+ pair<string, Value::Scalar>& left_ = quantities.at(leftIndex);
+ const pair<string, Value::Scalar>& right_ = right.quantities.at(rightIndex);
+
+ if (left_.first < right_.first) {
+ // Item exists in the left but not in the right.
+ ++leftIndex;
+ } else if (left_.first > right_.first) {
+ // Item exists in the right but not in the left.
+ // Insert absent entries in the alphabetical order.
+ quantities.insert(quantities.begin() + leftIndex, right_);
+ ++leftIndex;
+ ++rightIndex;
+ } else {
+ // Item exists in both left and right.
+ left_.second += right_.second;
+ ++leftIndex;
+ ++rightIndex;
+ }
+ }
+
+ // Copy the remaining items in `right`.
+ while (rightIndex < right.size()) {
+ quantities.push_back(right.quantities.at(rightIndex));
+ ++rightIndex;
+ }
+
+ return *this;
+}
+
+
+ResourceQuantities& ResourceQuantities::operator-=(
+ const ResourceQuantities& right)
+{
+ size_t leftIndex = 0u;
+ size_t rightIndex = 0u;
+
+ // Since quantities are sorted in alphabetical order, we can walk them
+ // at the same time.
+ while (leftIndex < size() && rightIndex < right.size()) {
+ pair<string, Value::Scalar>& left_ = quantities.at(leftIndex);
+ const pair<string, Value::Scalar>& right_ = right.quantities.at(rightIndex);
+
+ if (left_.first < right_.first) {
+ // Item exists in the left but not in the right.
+ ++leftIndex;
+ } else if (left_.first > right_.first) {
+ // Item exists in the right but not in the left (i.e. 0), this
+ // would result in a negative entry, so skip it.
+ ++rightIndex;
+ } else {
+ // Item exists in both left and right.
+ if (left_.second <= right_.second) {
+ // Drop negative and zero entries.
+ quantities.erase(quantities.begin() + leftIndex);
+ ++rightIndex;
+ } else {
+ left_.second -= right_.second;
+ ++leftIndex;
+ ++rightIndex;
+ }
+ }
+ }
+
+ return *this;
+}
+
+
+void ResourceQuantities::add(const string& name, const Value::Scalar& scalar)
+{
+ CHECK_GE(scalar, Value::Scalar());
+
+ // Ignore adding zero.
+ if (scalar == Value::Scalar()) {
+ return;
+ }
+
// Find the location to insert while maintaining
// alphabetical ordering. Don't bother binary searching
// since we don't expect a large number of quantities.
auto it = quantities.begin();
for (; it != quantities.end(); ++it) {
if (it->first == name) {
- return it->second;
+ it->second += scalar;
+ return;
}
if (it->first > name) {
@@ -154,9 +239,7 @@ Value::Scalar& ResourceQuantities::operator[](const string& name)
}
}
- it = quantities.insert(it, std::make_pair(name, Value::Scalar()));
-
- return it->second;
+ it = quantities.insert(it, std::make_pair(name, scalar));
}
diff --git a/src/common/resource_quantities.hpp b/src/common/resource_quantities.hpp
index d775bb7..11e3f42 100644
--- a/src/common/resource_quantities.hpp
+++ b/src/common/resource_quantities.hpp
@@ -30,32 +30,23 @@ namespace mesos {
namespace internal {
-// An efficient collection of resource quantities.
+// An efficient collection of resource quantities. All values are guaranteed
+// to be positive and finite.
//
-// E.g. [("cpus", 4.5), ("gpus", 0), ("ports", 1000)]
+// E.g. [("cpus", 4.5), ("gpus", 0.1), ("ports", 1000)]
//
-// We provide map-like semantics: [] operator for inserting/retrieving values,
-// keys are unique, and iteration is sorted.
+// Absent resource entries imply there is no (zero) such resources.
//
-// Notes on handling negativity and arithmetic operations: during construction,
-// `Value::Scalar` arguments must be non-negative and finite. Invalid arguments
-// will result in an error where `Try` is returned. Once constructed, users can
-// use `[]` operator to mutate values directly. No member methods are provided
-// for arithmetic operations. Users should be mindful of producing negatives
-// when mutating the `Value::Scalar` directly.
+// TODO(mzhu): Add `class ResourceLimits` where absence means infinite amount
+// of such resources.
//
-// An alternative design for this class was to provide addition and
-// subtraction functions as opposed to a map interface. However, this
-// leads to some un-obvious semantics around presence of zero values
-// (will zero entries be automatically removed?) and handling of negatives
-// (will negatives trigger a crash? will they be converted to zero? Note
-// that Value::Scalar should be non-negative but there is currently no
-// enforcement of this by Value::Scalar arithmetic operations; we probably
-// want all Value::Scalar operations to go through the same negative
-// handling). To avoid the confusion, we provided a map like interface
-// which produces clear semantics: insertion works like maps, and the
-// user is responsible for performing arithmetic operations on the values
-// (using the already provided Value::Scalar arithmetic overloads).
+// Notes on handling negativity and arithmetic operations: values are guaranteed
+// to be positive. This is achieved by construction validation and no public
+// mutation interfaces. During construction, `Value::Scalar` arguments must be
+// non-negative and finite, and entries with zero quantities will be dropped
+// silently. Invalid arguments will result in an error where `Try`
+// is returned. For arithmetic operations, non-positive values are silently
+// dropped--this is consist with `class Resources`.
//
// Note for posterity, the status quo prior to this class
// was to use stripped-down `Resources` objects for storing
@@ -72,6 +63,7 @@ class ResourceQuantities
public:
// Parse an input string of semicolon separated "name:number" pairs.
// Duplicate names are allowed in the input and will be merged into one entry.
+ // Entries with zero values will be silently dropped.
//
// Example: "cpus:10;mem:1024;ports:3"
// "cpus:10; mem:1024; ports:3"
@@ -117,15 +109,16 @@ public:
size_t size() const { return quantities.size(); };
- // Returns the quantity scalar value if a quantity with the given name
- // exists (even if the quantity is zero), otherwise return `None()`.
- Option<Value::Scalar> get(const std::string& name) const;
+ // Returns the quantity scalar value if a quantity with the given name.
+ // If the given name is absent, return zero.
+ Value::Scalar get(const std::string& name) const;
- // Like std::map, returns a reference to the quantity with the given name.
- // If no quantity exists with the given name, a new entry will be created.
- Value::Scalar& operator[](const std::string& name);
+ ResourceQuantities& operator+=(const ResourceQuantities& quantities);
+ ResourceQuantities& operator-=(const ResourceQuantities& quantities);
private:
+ void add(const std::string& name, const Value::Scalar& scalar);
+
// List of name quantity pairs sorted by name.
// Arithmetic and comparison operations benefit from this sorting.
std::vector<std::pair<std::string, Value::Scalar>> quantities;
diff --git a/src/master/allocator/sorter/drf/sorter.cpp b/src/master/allocator/sorter/drf/sorter.cpp
index b128df0..43c9767 100644
--- a/src/master/allocator/sorter/drf/sorter.cpp
+++ b/src/master/allocator/sorter/drf/sorter.cpp
@@ -515,10 +515,7 @@ void DRFSorter::add(const SlaveID& slaveId, const Resources& resources)
(resources.nonShared() + newShared).createStrippedScalarQuantity();
total_.scalarQuantities += scalarQuantities;
-
- foreach (const Resource& resource, scalarQuantities) {
- total_.totals[resource.name()] += resource.scalar();
- }
+ total_.totals += ResourceQuantities::fromScalarResources(scalarQuantities);
// We have to recalculate all shares when the total resources
// change, but we put it off until `sort` is called so that if
@@ -548,13 +545,11 @@ void DRFSorter::remove(const SlaveID& slaveId, const Resources& resources)
const Resources scalarQuantities =
(resources.nonShared() + absentShared).createStrippedScalarQuantity();
- foreach (const Resource& resource, scalarQuantities) {
- total_.totals[resource.name()] -= resource.scalar();
- }
-
CHECK(total_.scalarQuantities.contains(scalarQuantities));
total_.scalarQuantities -= scalarQuantities;
+ total_.totals -= ResourceQuantities::fromScalarResources(scalarQuantities);
+
if (total_.resources[slaveId].empty()) {
total_.resources.erase(slaveId);
}
@@ -671,9 +666,7 @@ double DRFSorter::calculateShare(const Node* node) const
continue;
}
- Value::Scalar allocation =
- node->allocation.totals.get(resourceName)
- .getOrElse(Value::Scalar()); // Absent means zero.
+ Value::Scalar allocation = node->allocation.totals.get(resourceName);
share = std::max(share, allocation.value() / scalar.value());
}
diff --git a/src/master/allocator/sorter/drf/sorter.hpp b/src/master/allocator/sorter/drf/sorter.hpp
index e64c9ad..75f90f3 100644
--- a/src/master/allocator/sorter/drf/sorter.hpp
+++ b/src/master/allocator/sorter/drf/sorter.hpp
@@ -344,9 +344,7 @@ struct DRFSorter::Node
resources[slaveId] += toAdd;
scalarQuantities += quantitiesToAdd;
- foreach (const Resource& resource, quantitiesToAdd) {
- totals[resource.name()] += resource.scalar();
- }
+ totals += ResourceQuantities::fromScalarResources(quantitiesToAdd);
count++;
}
@@ -370,9 +368,7 @@ struct DRFSorter::Node
const Resources quantitiesToRemove =
(toRemove.nonShared() + sharedToRemove).createStrippedScalarQuantity();
- foreach (const Resource& resource, quantitiesToRemove) {
- totals[resource.name()] -= resource.scalar();
- }
+ totals -= ResourceQuantities::fromScalarResources(quantitiesToRemove);
CHECK(scalarQuantities.contains(quantitiesToRemove))
<< scalarQuantities << " does not contain " << quantitiesToRemove;
@@ -408,13 +404,8 @@ struct DRFSorter::Node
scalarQuantities -= oldAllocationQuantity;
scalarQuantities += newAllocationQuantity;
- foreach (const Resource& resource, oldAllocationQuantity) {
- totals[resource.name()] -= resource.scalar();
- }
-
- foreach (const Resource& resource, newAllocationQuantity) {
- totals[resource.name()] += resource.scalar();
- }
+ totals -= ResourceQuantities::fromScalarResources(oldAllocationQuantity);
+ totals += ResourceQuantities::fromScalarResources(newAllocationQuantity);
}
// We store the number of times this client has been chosen for
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
index f578ef1..6fcfc41 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -440,10 +440,7 @@ void RandomSorter::add(const SlaveID& slaveId, const Resources& resources)
(resources.nonShared() + newShared).createStrippedScalarQuantity();
total_.scalarQuantities += scalarQuantities;
-
- foreach (const Resource& resource, scalarQuantities) {
- total_.totals[resource.name()] += resource.scalar();
- }
+ total_.totals += ResourceQuantities::fromScalarResources(scalarQuantities);
}
}
@@ -467,13 +464,11 @@ void RandomSorter::remove(const SlaveID& slaveId, const Resources& resources)
const Resources scalarQuantities =
(resources.nonShared() + absentShared).createStrippedScalarQuantity();
- foreach (const Resource& resource, scalarQuantities) {
- total_.totals[resource.name()] -= resource.scalar();
- }
-
CHECK(total_.scalarQuantities.contains(scalarQuantities));
total_.scalarQuantities -= scalarQuantities;
+ total_.totals -= ResourceQuantities::fromScalarResources(scalarQuantities);
+
if (total_.resources[slaveId].empty()) {
total_.resources.erase(slaveId);
}
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
index 4f230ec..2031cb2 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -331,9 +331,7 @@ struct RandomSorter::Node
resources[slaveId] += toAdd;
scalarQuantities += quantitiesToAdd;
- foreach (const Resource& resource, quantitiesToAdd) {
- totals[resource.name()] += resource.scalar();
- }
+ totals += ResourceQuantities::fromScalarResources(quantitiesToAdd);
}
void subtract(const SlaveID& slaveId, const Resources& toRemove)
@@ -355,9 +353,7 @@ struct RandomSorter::Node
const Resources quantitiesToRemove =
(toRemove.nonShared() + sharedToRemove).createStrippedScalarQuantity();
- foreach (const Resource& resource, quantitiesToRemove) {
- totals[resource.name()] -= resource.scalar();
- }
+ totals -= ResourceQuantities::fromScalarResources(quantitiesToRemove);
CHECK(scalarQuantities.contains(quantitiesToRemove))
<< scalarQuantities << " does not contain " << quantitiesToRemove;
@@ -393,13 +389,8 @@ struct RandomSorter::Node
scalarQuantities -= oldAllocationQuantity;
scalarQuantities += newAllocationQuantity;
- foreach (const Resource& resource, oldAllocationQuantity) {
- totals[resource.name()] -= resource.scalar();
- }
-
- foreach (const Resource& resource, newAllocationQuantity) {
- totals[resource.name()] += resource.scalar();
- }
+ totals -= ResourceQuantities::fromScalarResources(oldAllocationQuantity);
+ totals += ResourceQuantities::fromScalarResources(newAllocationQuantity);
}
// We maintain multiple copies of each shared resource allocated
diff --git a/src/tests/resource_quantities_tests.cpp b/src/tests/resource_quantities_tests.cpp
index 6a1aa39..192f1ee 100644
--- a/src/tests/resource_quantities_tests.cpp
+++ b/src/tests/resource_quantities_tests.cpp
@@ -53,13 +53,6 @@ TEST(QuantitiesTest, FromStringValid)
EXPECT_EQ("cpus", resourceQuantities.begin()->first);
EXPECT_DOUBLE_EQ(3.14, resourceQuantities.begin()->second.value());
- // Zero value is retained.
- resourceQuantities =
- CHECK_NOTERROR(ResourceQuantities::fromString("cpus:0"));
- EXPECT_EQ(1u, resourceQuantities.size());
- EXPECT_EQ("cpus", resourceQuantities.begin()->first);
- EXPECT_DOUBLE_EQ(0, resourceQuantities.begin()->second.value());
-
// Whitespace is trimmed.
resourceQuantities =
CHECK_NOTERROR(ResourceQuantities::fromString(" cpus : 3.14 ; disk : 10 "));
@@ -71,6 +64,10 @@ TEST(QuantitiesTest, FromStringValid)
EXPECT_EQ("disk", it->first);
EXPECT_DOUBLE_EQ(10, it->second.value());
+ // Zero value.
+ resourceQuantities = CHECK_NOTERROR(ResourceQuantities::fromString("cpus:0"));
+ EXPECT_EQ(0u, resourceQuantities.size());
+
// Two resources.
resourceQuantities =
CHECK_NOTERROR(ResourceQuantities::fromString("cpus:10.5;ports:1"));
@@ -167,28 +164,6 @@ TEST(QuantitiesTest, FromScalarResources)
}
-TEST(QuantitiesTest, Insertion)
-{
- ResourceQuantities resourceQuantities =
- CHECK_NOTERROR(ResourceQuantities::fromString("cpus:10"));
-
- resourceQuantities["disk"] = Value::Scalar();
- resourceQuantities["alpha"] = Value::Scalar();
-
- auto it = resourceQuantities.begin();
- EXPECT_EQ("alpha", it->first);
- EXPECT_DOUBLE_EQ(0, it->second.value());
-
- ++it;
- EXPECT_EQ("cpus", it->first);
- EXPECT_DOUBLE_EQ(10, it->second.value());
-
- ++it;
- EXPECT_EQ("disk", it->first);
- EXPECT_DOUBLE_EQ(0, it->second.value());
-}
-
-
} // namespace tests {
} // namespace internal {
} // namespace mesos {