Improve slave-preference function

scripts/master/master_utils.py

 # Copyright (c) 2012 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 import os
 import random
 import re
 import sys
 
 import buildbot
@@ skipping 637 matching lines @@
 
     # Choose our inner IRenderer and render it
     renderer = (self.present) if is_present else (self.absent)
     # Disable 'too many positional arguments' error | pylint: disable=E1121
     return IRenderable(renderer).getRenderingFor(build)
 
 
 class PreferredBuilderNextSlaveFunc(object):
   """
   This object, when used as a Builder's 'nextSlave' function, will choose
-  a slave builder whose 'preferred_builder' value is the same as the builder
-  name. If there is no such a builder, a builder is randomly chosen.
+  a slave whose 'preferred_builder' value is the same as the builder
+  name. If there is no such slave, a slave is randomly chosen that doesn't
+  prefer any builder if such a slave is available. If not, a slave is randomly
+  chosen with preference on slaves with higher capacity.
   """
 
+  def __init__(self, choice=random.choice):
+    # Allow overriding the choice function for testability.
+    self.choice = choice
+
   def __call__(self, builder, slave_builders):
     if not slave_builders:
       return None
 

[tandrii(chromium), 2016/10/21 10:39:16]

first, consider adding new functionality behind a switch.
second, how about this (as brainstormed offline):

prefs = collections.Counter(s.preferred_builder for s in slave_builders)
if builder in prefs:
  key = builder
elif None in prefs:
  key = None
else:
  key = prefs.most_common()[0]
return choice(s for s in slave_builders if s.preferred_builder == key)


# As discussed, last loop over all slaves_builders can be optimized by storing
randomly selected slave next to count of slave so far in prefs{}.

[Michael Achenbach, 2016/10/21 13:17:43]

Used the first simple method with minor modifications. I don't think more
optimization is necessary at that point.

Note that the semantics now change: a set of several sets of equally available
slaves is chosen now arbitrarily (not randomly) based on dictionary order. Only
the slave from the set will be chosen randomly. I don't think it matters and it
makes the algorithm faster.

+    # First choice: Slaves that prefer this builder.
     preferred_slaves = [
         s for s in slave_builders
         if s.slave.properties.getProperty('preferred_builder') == builder.name]
-    return random.choice(preferred_slaves or slave_builders)
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Second choice: Slaves that don't prefer any builders.
+    preferred_slaves = [
+        s for s in slave_builders
+        if not s.slave.properties.getProperty('preferred_builder')]
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Third choice: Slaves that prefer other builders but have largest
+    # capacity left.
+    preference_to_slaves = {}
+    largest_capacity = 0
+    for s in slave_builders:
+      # There should only be slaves with preference left, but lets be
+      # defensive.
+      preference = s.slave.properties.getProperty('preferred_builder')
+      if preference:
+        slaves = preference_to_slaves.setdefault(preference, [])
+        slaves.append(s)
+        largest_capacity = max(largest_capacity, len(slaves))
+    # Prefer list over set as each slave has only one preferred builder.
+    preferred_slaves = []
+    for preference, slaves in preference_to_slaves.iteritems():
+      if len(slaves) == largest_capacity:
+        preferred_slaves.extend(slaves)
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Last choice: Choose from all slaves. We should never reach here as all
+    # slaves should have been considered above.
+    log.err('Didn\'t get preferred slave for %s' % builder.name)
+    return self.choice(slave_builders)
 
 
 def SetMasterProcessName():
   """Sets the name of this process to the name of the master.  Linux only."""
 
   if sys.platform != 'linux2':
     return
 
   command_line.set_command_line("master: %s" % GetMastername())