Apache Mesos
sorter.hpp
Go to the documentation of this file.
1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 
17 #ifndef __MASTER_ALLOCATOR_MESOS_SORTER_RANDOM_SORTER_HPP__
18 #define __MASTER_ALLOCATOR_MESOS_SORTER_RANDOM_SORTER_HPP__
19 
20 #include <algorithm>
21 #include <random>
22 #include <set>
23 #include <string>
24 #include <vector>
25 
26 #include <mesos/mesos.hpp>
27 #include <mesos/resources.hpp>
29 #include <mesos/values.hpp>
30 
31 #include <stout/check.hpp>
32 #include <stout/hashmap.hpp>
33 #include <stout/hashset.hpp>
34 #include <stout/option.hpp>
35 
37 
38 
39 namespace mesos {
40 namespace internal {
41 namespace master {
42 namespace allocator {
43 
44 class RandomSorter : public Sorter
45 {
46 public:
47  RandomSorter();
48 
49  explicit RandomSorter(
50  const process::UPID& allocator,
51  const std::string& metricsPrefix);
52 
53  ~RandomSorter() override;
54 
55  void initialize(
56  const Option<std::set<std::string>>& fairnessExcludeResourceNames)
57  override;
58 
59  void add(const std::string& clientPath) override;
60 
61  void remove(const std::string& clientPath) override;
62 
63  void activate(const std::string& clientPath) override;
64 
65  void deactivate(const std::string& clientPath) override;
66 
67  void updateWeight(const std::string& path, double weight) override;
68 
69  void allocated(
70  const std::string& clientPath,
71  const SlaveID& slaveId,
72  const Resources& resources) override;
73 
74  void update(
75  const std::string& clientPath,
76  const SlaveID& slaveId,
77  const Resources& oldAllocation,
78  const Resources& newAllocation) override;
79 
80  void unallocated(
81  const std::string& clientPath,
82  const SlaveID& slaveId,
83  const Resources& resources) override;
84 
86  const std::string& clientPath) const override;
87 
89  const std::string& clientPath) const override;
91  const override;
92 
94  const std::string& clientPath,
95  const SlaveID& slaveId) const override;
96 
97  // NOTE: addSlave/removeSlave is a no-op for this sorter.
98  void addSlave(
99  const SlaveID& slaveId,
100  const ResourceQuantities& scalarQuantities) override {};
101 
102  void removeSlave(const SlaveID& slaveId) override {};
103 
104  // This will perform a weighted random shuffle on each call.
105  //
106  // TODO(bmahler): Unlike the DRF sorter, the allocator ideally would
107  // not call `sort()` for every agent, but rather loop through a single
108  // weighted shuffle before re-shuffling..
109  std::vector<std::string> sort() override;
110 
111  bool contains(const std::string& clientPath) const override;
112 
113  size_t count() const override;
114 
115 private:
116  // A node in the sorter's tree.
117  struct Node;
118 
119  // Returns the weight associated with the node. If no weight has
120  // been configured for the node's path, the default weight (1.0) is
121  // returned.
122  double getWeight(const Node* node) const;
123 
124  // Get active internal nodes -- internal nodes that have at least
125  // one active leaf descendant.
126  hashset<Node*> activeInternalNodes() const;
127 
128  // Returns the client associated with the given path. Returns
129  // nullptr if the path is not found or if the path identifies an
130  // internal node in the tree (not a client).
131  Node* find(const std::string& clientPath) const;
132 
133  // Sorting related info are kept in memory to avoid recalculations.
134  struct SortInfo
135  {
136  public:
137  SortInfo(const RandomSorter* sorter_) : dirty(true), sorter(sorter_) {}
138 
139  // Returns a pair of vectors which are active clients and
140  // their corresponding relative weights.
141  std::pair<std::vector<std::string>, std::vector<double>>
142  getClientsAndWeights();
143 
144  // A dirty bit indicates whether the info is up-to-date
145  // and requires recalculation.
146  bool dirty;
147 
148  private:
149  void updateRelativeWeights();
150 
151  std::vector<std::string> clients;
152 
153  // Relative weights of the `clients` above.
154  // Relative weight denotes the weight of an active leaf node relative to
155  // other active leaf nodes given their configured weights. The number here
156  // stands for the probability of a given node being shuffled to the 1st in
157  // all the nodes in a random shuffle. Intuitively, the sum of all relative
158  // weights should be one.
159  std::vector<double> weights;
160 
161  const RandomSorter* sorter;
162  } sortInfo;
163 
164  // Used for random number generation.
165  std::mt19937 generator;
166 
167  // The root node in the sorter tree.
168  Node* root;
169 
170  // To speed lookups, we keep a map from client paths to the leaf
171  // node associated with that client. There is an entry in this map
172  // for every leaf node in the client tree (except for the root when
173  // the tree is empty). Paths in this map do NOT contain the trailing
174  // "." label we use for leaf nodes.
176 
177  // Weights associated with role paths. Setting the weight for a path
178  // influences the sampling probability of all nodes in the subtree
179  // rooted at that path. This hashmap might include weights for paths
180  // that are not currently in the sorter tree.
182 };
183 
184 
185 // Represents a node in the sorter's tree. The structure of the tree
186 // reflects the hierarchical relationships between the clients of the
187 // sorter. Some (but not all) nodes correspond to sorter clients; some
188 // nodes only exist to represent the structure of the sorter
189 // tree. Clients are always associated with leaf nodes.
190 //
191 // For example, if there are two sorter clients "a/b" and "c/d", the
192 // tree will contain five nodes: the root node, internal nodes for "a"
193 // and "c", and leaf nodes for the clients "a/b" and "c/d".
195 {
196  // Indicates whether a node is an active leaf node, an inactive leaf
197  // node, or an internal node. Sorter clients always correspond to
198  // leaf nodes, and only leaf nodes can be activated or deactivated.
199  // The root node is always an "internal" node.
200  enum Kind
201  {
204  INTERNAL
205  };
206 
207  Node(const std::string& _name, Kind _kind, Node* _parent)
208  : name(_name), kind(_kind), parent(_parent)
209  {
210  // Compute the node's path. Three cases:
211  //
212  // (1) If the root node, use the empty string
213  // (2) If a child of the root node, use the child's name
214  // (3) Otherwise, use the parent's name, "/", and the child's name.
215  if (parent == nullptr) {
216  path = "";
217  } else if (parent->parent == nullptr) {
218  path = name;
219  } else {
220  path = strings::join("/", parent->path, name);
221  }
222  }
223 
225  {
226  foreach (Node* child, children) {
227  delete child;
228  }
229  }
230 
231  // The label of the edge from this node's parent to the
232  // node. "Implicit" leaf nodes are always named ".".
233  //
234  // TODO(neilc): Consider naming implicit leaf nodes in a clearer
235  // way, e.g., by making `name` an Option?
236  std::string name;
237 
238  // Complete path from root to node. This includes the trailing "."
239  // label for virtual leaf nodes.
240  std::string path;
241 
242  // Cached weight of the node, access this through `getWeight()`.
243  // The value is cached by `getWeight()` and updated by
244  // `updateWeight()`. Marked mutable since the caching writes
245  // to this are logically const.
247 
249 
251 
252  // Pointers to the child nodes. `children` is only non-empty if
253  // `kind` is INTERNAL_NODE.
254  //
255  // All inactive leaves are stored at the end of the vector; that
256  // is, each `children` vector consists of zero or more active leaves
257  // and internal nodes, followed by zero or more inactive leaves. This
258  // means that code that only wants to iterate over active children
259  // can stop when the first inactive leaf is observed.
260  std::vector<Node*> children;
261 
262  // If this node represents a sorter client, this returns the path of
263  // that client. Unlike the `path` field, this does NOT include the
264  // trailing "." label for virtual leaf nodes.
265  //
266  // For example, if the sorter contains two clients "a" and "a/b",
267  // the tree will contain four nodes: the root node, "a", "a/."
268  // (virtual leaf), and "a/b". The `clientPath()` of "a/." is "a",
269  // because that is the name of the client associated with that
270  // virtual leaf node.
271  const std::string& clientPath() const
272  {
273  if (name == ".") {
274  CHECK(kind == ACTIVE_LEAF || kind == INACTIVE_LEAF);
275  return CHECK_NOTNULL(parent)->path;
276  }
277 
278  return path;
279  }
280 
281  bool isLeaf() const
282  {
283  if (kind == ACTIVE_LEAF || kind == INACTIVE_LEAF) {
284  CHECK(children.empty());
285  return true;
286  }
287 
288  return false;
289  }
290 
291  void removeChild(const Node* child)
292  {
293  // Sanity check: ensure we are removing an extant node.
294  auto it = std::find(children.begin(), children.end(), child);
295  CHECK(it != children.end());
296 
297  children.erase(it);
298  }
299 
300  void addChild(Node* child)
301  {
302  // Sanity check: don't allow duplicates to be inserted.
303  auto it = std::find(children.begin(), children.end(), child);
304  CHECK(it == children.end());
305 
306  // If we're inserting an inactive leaf, place it at the end of the
307  // `children` vector; otherwise, place it at the beginning. This
308  // maintains ordering invariant above.
309  if (child->kind == INACTIVE_LEAF) {
310  children.push_back(child);
311  } else {
312  children.insert(children.begin(), child);
313  }
314  }
315 
316  // Allocation for a node.
317  struct Allocation
318  {
320 
321  void add(const SlaveID& slaveId, const Resources& toAdd)
322  {
323  // Add shared resources to the allocated quantities when the same
324  // resources don't already exist in the allocation.
325  const Resources sharedToAdd = toAdd.shared()
326  .filter([this, slaveId](const Resource& resource) {
327  return !resources[slaveId].contains(resource);
328  });
329 
330  const ResourceQuantities quantitiesToAdd =
332  (toAdd.nonShared() + sharedToAdd).scalars());
333 
334  resources[slaveId] += toAdd;
335  totals += quantitiesToAdd;
336  }
337 
338  void subtract(const SlaveID& slaveId, const Resources& toRemove)
339  {
340  CHECK(resources.contains(slaveId))
341  << "Resources " << resources << " does not contain " << slaveId;
342  CHECK(resources.at(slaveId).contains(toRemove))
343  << "Resources " << resources.at(slaveId) << " at agent " << slaveId
344  << " does not contain " << toRemove;
345 
346  resources[slaveId] -= toRemove;
347 
348  // Remove shared resources from the allocated quantities when there
349  // are no instances of same resources left in the allocation.
350  const Resources sharedToRemove = toRemove.shared()
351  .filter([this, slaveId](const Resource& resource) {
352  return !resources[slaveId].contains(resource);
353  });
354 
355  const ResourceQuantities quantitiesToRemove =
357  (toRemove.nonShared() + sharedToRemove).scalars());
358 
359  CHECK(totals.contains(quantitiesToRemove))
360  << totals << " does not contain " << quantitiesToRemove;
361 
362  totals -= quantitiesToRemove;
363 
364  if (resources.at(slaveId).empty()) {
365  resources.erase(slaveId);
366  }
367  }
368 
369  void update(
370  const SlaveID& slaveId,
371  const Resources& oldAllocation,
372  const Resources& newAllocation)
373  {
374  const ResourceQuantities oldAllocationQuantities =
376  const ResourceQuantities newAllocationQuantities =
378 
379  CHECK(resources.contains(slaveId))
380  << "Resources " << resources << " does not contain " << slaveId;
381  CHECK(resources[slaveId].contains(oldAllocation))
382  << "Resources " << resources[slaveId] << " at agent " << slaveId
383  << " does not contain " << oldAllocation;
384 
385  CHECK(totals.contains(oldAllocationQuantities))
386  << totals << " does not contain " << oldAllocationQuantities;
387 
388  resources[slaveId] -= oldAllocation;
389  resources[slaveId] += newAllocation;
390 
391  // It is possible that allocations can be updated to empty.
392  // See MESOS-9015 and MESOS-9975.
393  if (resources.at(slaveId).empty()) {
394  resources.erase(slaveId);
395  }
396 
397  totals -= oldAllocationQuantities;
398  totals += newAllocationQuantities;
399  }
400 
401  // We maintain multiple copies of each shared resource allocated
402  // to a client, where the number of copies represents the number
403  // of times this shared resource has been allocated to (and has
404  // not been recovered from) a specific client.
406 
407  // We keep the aggregated scalar resource quantities to speed
408  // up share calculation. Note, resources shared count are ignored.
409  // Because sharedness inherently refers to the identities of resources
410  // and not quantities.
412  } allocation;
413 };
414 
415 } // namespace allocator {
416 } // namespace master {
417 } // namespace internal {
418 } // namespace mesos {
419 
420 #endif // __MASTER_ALLOCATOR_MESOS_SORTER_RANDOM_SORTER_HPP__
const hashmap< SlaveID, Resources > & allocation(const std::string &clientPath) const override
Definition: path.hpp:29
Definition: option.hpp:29
void updateWeight(const std::string &path, double weight) override
Definition: master.hpp:27
std::stringstream & join(std::stringstream &stream, const std::string &separator, T &&...args)
Definition: strings.hpp:307
Definition: hashset.hpp:53
Definition: resource_quantities.hpp:63
void removeSlave(const SlaveID &slaveId) override
Definition: sorter.hpp:102
bool isLeaf() const
Definition: sorter.hpp:281
Resources filter(const lambda::function< bool(const Resource &)> &predicate) const
Definition: resources.hpp:83
void initialize(const Option< std::set< std::string >> &fairnessExcludeResourceNames) override
const std::string & clientPath() const
Definition: sorter.hpp:271
Definition: hashmap.hpp:38
const char * kind()
void unallocated(const std::string &clientPath, const SlaveID &slaveId, const Resources &resources) override
void activate(const std::string &clientPath) override
An "untyped" PID, used to encapsulate the process ID for lower-layer abstractions (eg...
Definition: pid.hpp:39
static ResourceQuantities fromScalarResources(const Resources &resources)
void allocated(const std::string &clientPath, const SlaveID &slaveId, const Resources &resources) override
void removeChild(const Node *child)
Definition: sorter.hpp:291
bool contains(const std::string &clientPath) const override
void addChild(Node *child)
Definition: sorter.hpp:300
Option< double > weight
Definition: sorter.hpp:246
void update(const SlaveID &slaveId, const Resources &oldAllocation, const Resources &newAllocation)
Definition: sorter.hpp:369
std::vector< Node * > children
Definition: sorter.hpp:260
Definition: agent.hpp:25
void deactivate(const std::string &clientPath) override
std::vector< std::string > sort() override
std::string name
Definition: sorter.hpp:236
Resources scalars() const
const ResourceQuantities & allocationScalarQuantities() const override
void add(const std::string &clientPath) override
Resources shared() const
Definition: attributes.hpp:24
Node(const std::string &_name, Kind _kind, Node *_parent)
Definition: sorter.hpp:207
void subtract(const SlaveID &slaveId, const Resources &toRemove)
Definition: sorter.hpp:338
Resources nonShared() const
std::set< pid_t > children(pid_t, const std::list< Process > &, bool)
Definition: os.hpp:216
hashmap< SlaveID, Resources > resources
Definition: sorter.hpp:405
std::string path
Definition: sorter.hpp:240
ResourceQuantities totals
Definition: sorter.hpp:411
constexpr const char * name
Definition: shell.hpp:43
Try< std::list< std::string > > find(const std::string &directory, const std::string &pattern)
Definition: find.hpp:37
void addSlave(const SlaveID &slaveId, const ResourceQuantities &scalarQuantities) override
Definition: sorter.hpp:98
void add(const SlaveID &slaveId, const Resources &toAdd)
Definition: sorter.hpp:321
void update(const std::string &clientPath, const SlaveID &slaveId, const Resources &oldAllocation, const Resources &newAllocation) override