Repository: mesos
Updated Branches:
  refs/heads/master 3f3a3bd7b -> fba310812


Improve DRF sorter performance by bypassing `Resources`.

Currently in `DRFSorter::calculateShare()` (which is called very
frequently), the use of `Resources::get<Scalar>()` is expensive
as it needs to loop over the `Resource` objects and do string
comparison on the `Resource::name` strings.

This patch avoids using `Resources::get<Scalar>()` in
`DRFSorter::calaculateShare()` in favor of maintaining
a map of resource names to scalars.

Note that we had to maintain both this new map and the
previously added `strippedScalarQuantities` since the
latter stores resource roles.

Review: https://reviews.apache.org/r/43665/


Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/fba31081
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/fba31081
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/fba31081

Branch: refs/heads/master
Commit: fba3108123442c78d4cee6047e2b1d64aab5a37a
Parents: 3f3a3bd
Author: Dario Rexin <dre...@apple.com>
Authored: Thu Sep 22 16:00:03 2016 -0700
Committer: Benjamin Mahler <bmah...@apache.org>
Committed: Thu Sep 22 19:47:32 2016 -0700

----------------------------------------------------------------------
 src/master/allocator/sorter/drf/sorter.cpp | 99 ++++++++++++++-----------
 src/master/allocator/sorter/drf/sorter.hpp | 23 +++++-
 src/master/allocator/sorter/sorter.hpp     |  2 +-
 3 files changed, 76 insertions(+), 48 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos/blob/fba31081/src/master/allocator/sorter/drf/sorter.cpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/drf/sorter.cpp 
b/src/master/allocator/sorter/drf/sorter.cpp
index 1a880ac..790c932 100644
--- a/src/master/allocator/sorter/drf/sorter.cpp
+++ b/src/master/allocator/sorter/drf/sorter.cpp
@@ -21,6 +21,7 @@
 
 #include <mesos/mesos.hpp>
 #include <mesos/resources.hpp>
+#include <mesos/values.hpp>
 
 #include <process/pid.hpp>
 
@@ -167,10 +168,16 @@ void DRFSorter::allocated(
       return !allocations[name].resources[slaveId].contains(resource);
     });
 
-  allocations[name].resources[slaveId] += resources;
-  allocations[name].scalarQuantities +=
+  const Resources scalarQuantities =
     (resources.nonShared() + newShared).createStrippedScalarQuantity();
 
+  allocations[name].resources[slaveId] += resources;
+  allocations[name].scalarQuantities += scalarQuantities;
+
+  foreach (const Resource& resource, scalarQuantities) {
+    allocations[name].totals[resource.name()] += resource.scalar();
+  }
+
   // If the total resources have changed, we're going to
   // recalculate all the shares, so don't bother just
   // updating this client.
@@ -207,6 +214,14 @@ void DRFSorter::update(
   allocations[name].scalarQuantities -= oldAllocationQuantity;
   allocations[name].scalarQuantities += newAllocationQuantity;
 
+  foreach (const Resource& resource, oldAllocationQuantity) {
+    allocations[name].totals[resource.name()] -= resource.scalar();
+  }
+
+  foreach (const Resource& resource, newAllocationQuantity) {
+    allocations[name].totals[resource.name()] += resource.scalar();
+  }
+
   // Just assume the total has changed, per the TODO above.
   dirty = true;
 }
@@ -283,11 +298,15 @@ void DRFSorter::unallocated(
       return !allocations[name].resources[slaveId].contains(resource);
     });
 
-  const Resources resourcesQuantity =
+  const Resources scalarQuantities =
     (resources.nonShared() + absentShared).createStrippedScalarQuantity();
 
-  CHECK(allocations[name].scalarQuantities.contains(resourcesQuantity));
-  allocations[name].scalarQuantities -= resourcesQuantity;
+  foreach (const Resource& resource, scalarQuantities) {
+    allocations[name].totals[resource.name()] -= resource.scalar();
+  }
+
+  CHECK(allocations[name].scalarQuantities.contains(scalarQuantities));
+  allocations[name].scalarQuantities -= scalarQuantities;
 
   if (allocations[name].resources[slaveId].empty()) {
     allocations[name].resources.erase(slaveId);
@@ -310,9 +329,16 @@ void DRFSorter::add(const SlaveID& slaveId, const 
Resources& resources)
       });
 
     total_.resources[slaveId] += resources;
-    total_.scalarQuantities +=
+
+    const Resources scalarQuantities =
       (resources.nonShared() + newShared).createStrippedScalarQuantity();
 
+    total_.scalarQuantities += scalarQuantities;
+
+    foreach (const Resource& resource, scalarQuantities) {
+      total_.totals[resource.name()] += resource.scalar();
+    }
+
     // We have to recalculate all shares when the total resources
     // change, but we put it off until sort is called so that if
     // something else changes before the next allocation we don't
@@ -337,11 +363,15 @@ void DRFSorter::remove(const SlaveID& slaveId, const 
Resources& resources)
         return !total_.resources[slaveId].contains(resource);
       });
 
-    const Resources resourcesQuantity =
+    const Resources scalarQuantities =
       (resources.nonShared() + absentShared).createStrippedScalarQuantity();
 
-    CHECK(total_.scalarQuantities.contains(resourcesQuantity));
-    total_.scalarQuantities -= resourcesQuantity;
+    foreach (const Resource& resource, scalarQuantities) {
+      total_.totals[resource.name()] -= resource.scalar();
+    }
+
+    CHECK(total_.scalarQuantities.contains(scalarQuantities));
+    total_.scalarQuantities -= scalarQuantities;
 
     if (total_.resources[slaveId].empty()) {
       total_.resources.erase(slaveId);
@@ -386,7 +416,7 @@ vector<string> DRFSorter::sort()
 }
 
 
-bool DRFSorter::contains(const string& name)
+bool DRFSorter::contains(const string& name) const
 {
   return allocations.contains(name);
 }
@@ -415,56 +445,35 @@ void DRFSorter::update(const string& name)
 }
 
 
-double DRFSorter::calculateShare(const string& name)
+double DRFSorter::calculateShare(const string& name) const
 {
+  CHECK(contains(name));
+
   double share = 0.0;
 
   // TODO(benh): This implementation of "dominant resource fairness"
   // currently does not take into account resources that are not
   // scalars.
 
-  foreach (const string& scalar, total_.scalarQuantities.names()) {
+  foreachpair (const string& resourceName,
+               const Value::Scalar& scalar,
+               total_.totals) {
     // Filter out the resources excluded from fair sharing.
     if (fairnessExcludeResourceNames.isSome() &&
-        fairnessExcludeResourceNames->count(scalar) > 0) {
+        fairnessExcludeResourceNames->count(resourceName) > 0) {
       continue;
     }
 
-    // We collect the scalar accumulated total value from the
-    // `Resources` object.
-    //
-    // NOTE: Although in principle scalar resources may be spread
-    // across multiple `Resource` objects (e.g., persistent volumes),
-    // we currently strip persistence and reservation metadata from
-    // the resources in `scalarQuantities`.
-    Option<Value::Scalar> __total =
-      total_.scalarQuantities.get<Value::Scalar>(scalar);
-
-    CHECK_SOME(__total);
-    const double _total = __total.get().value();
-
-    if (_total > 0.0) {
-      double allocation = 0.0;
-
-      // We collect the scalar accumulated allocation value from the
-      // `Resources` object.
-      //
-      // NOTE: Although in principle scalar resources may be spread
-      // across multiple `Resource` objects (e.g., persistent volumes),
-      // we currently strip persistence and reservation metadata from
-      // the resources in `scalarQuantities`.
-      Option<Value::Scalar> _allocation =
-        allocations[name].scalarQuantities.get<Value::Scalar>(scalar);
-
-      if (_allocation.isSome()) {
-        allocation = _allocation.get().value();
-      }
-
-      share = std::max(share, allocation / _total);
+    if (scalar.value() > 0.0 &&
+        allocations.at(name).totals.contains(resourceName)) {
+      const double allocation =
+        allocations.at(name).totals.at(resourceName).value();
+
+      share = std::max(share, allocation / scalar.value());
     }
   }
 
-  return share / weights[name];
+  return share / weights.at(name);
 }
 
 

http://git-wip-us.apache.org/repos/asf/mesos/blob/fba31081/src/master/allocator/sorter/drf/sorter.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/drf/sorter.hpp 
b/src/master/allocator/sorter/drf/sorter.hpp
index 82154c1..5bed53a 100644
--- a/src/master/allocator/sorter/drf/sorter.hpp
+++ b/src/master/allocator/sorter/drf/sorter.hpp
@@ -23,6 +23,7 @@
 
 #include <mesos/mesos.hpp>
 #include <mesos/resources.hpp>
+#include <mesos/values.hpp>
 
 #include <stout/hashmap.hpp>
 #include <stout/option.hpp>
@@ -120,7 +121,7 @@ public:
 
   virtual std::vector<std::string> sort();
 
-  virtual bool contains(const std::string& name);
+  virtual bool contains(const std::string& name) const;
 
   virtual int count();
 
@@ -130,7 +131,7 @@ private:
   void update(const std::string& name);
 
   // Returns the dominant resource share for the client.
-  double calculateShare(const std::string& name);
+  double calculateShare(const std::string& name) const;
 
   // Resources (by name) that will be excluded from fair sharing.
   Option<std::set<std::string>> fairnessExcludeResourceNames;
@@ -168,6 +169,15 @@ private:
     // omitted because sharedness inherently refers to the identities of
     // resources and not quantities.
     Resources scalarQuantities;
+
+    // We also store a map version of `scalarQuantities`, mapping
+    // the `Resource::name` to aggregated scalar. This improves the
+    // performance of calculating shares. See MESOS-4694.
+    //
+    // TODO(bmahler): Ideally we do not store `scalarQuantities`
+    // redundantly here, investigate performance improvements to
+    // `Resources` to make this unnecessary.
+    hashmap<std::string, Value::Scalar> totals;
   } total_;
 
   // Allocation for a client.
@@ -182,6 +192,15 @@ private:
     // about dynamic reservations, persistent volumes and sharedness of
     // the corresponding resource. See notes above.
     Resources scalarQuantities;
+
+    // We also store a map version of `scalarQuantities`, mapping
+    // the `Resource::name` to aggregated scalar. This improves the
+    // performance of calculating shares. See MESOS-4694.
+    //
+    // TODO(bmahler): Ideally we do not store `scalarQuantities`
+    // redundantly here, investigate performance improvements to
+    // `Resources` to make this unnecessary.
+    hashmap<std::string, Value::Scalar> totals;
   };
 
   // Maps client names to the resources they have been allocated.

http://git-wip-us.apache.org/repos/asf/mesos/blob/fba31081/src/master/allocator/sorter/sorter.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/sorter.hpp 
b/src/master/allocator/sorter/sorter.hpp
index 1d85b5d..737b13f 100644
--- a/src/master/allocator/sorter/sorter.hpp
+++ b/src/master/allocator/sorter/sorter.hpp
@@ -134,7 +134,7 @@ public:
 
   // Returns true if this Sorter contains the specified client,
   // either active or deactivated.
-  virtual bool contains(const std::string& client) = 0;
+  virtual bool contains(const std::string& client) const = 0;
 
   // Returns the number of clients this Sorter contains,
   // either active or deactivated.

Reply via email to