Fix last_devices to be quieter, and improve device affinity.

build/android/pylib/perf/setup.py

Index: build/android/pylib/perf/setup.py
diff --git a/build/android/pylib/perf/setup.py b/build/android/pylib/perf/setup.py
index 8e1fc28a7e651bef567b336e5593d8be64c75701..de870c2e4f9164739361801a56cf3b5c636bc393 100644
--- a/build/android/pylib/perf/setup.py
+++ b/build/android/pylib/perf/setup.py
@@ -6,6 +6,7 @@
 
 import json
 import fnmatch
+import hashlib
 import logging
 import os
 import shutil
@@ -18,18 +19,6 @@ from pylib.perf import test_runner
 from pylib.utils import test_environment
 
 
-def _GetAllDevices():
-  devices_path = os.path.join(os.environ.get('CHROMIUM_OUT_DIR', 'out'),
-                              device_list.LAST_DEVICES_FILENAME)
-  try:
-    devices = [device_utils.DeviceUtils(s)
-               for s in device_list.GetPersistentDeviceList(devices_path)]
-  except IOError as e:
-    logging.error('Unable to find %s [%s]', devices_path, e)
-    devices = device_utils.DeviceUtils.HealthyDevices()
-  return sorted(devices)
-
-
 def _GetStepsDictFromSingleStep(test_options):
   # Running a single command, build the tests structure.
   steps_dict = {
@@ -56,6 +45,80 @@ def _GetStepsDict(test_options):
       return steps
 
 
+def DistributeAffinities(devices):
+  """Create a mapping from device to affinity using a round-robin hash scheme.
+
+  Args:
+    devices: a list of device serials.
+
+  Returns: a dictionary mapping each of the given device serials to a list
+    of affinities (numbers between 0 and NUM_DEVICE_AFFINITIES-1) it should
+    run.
+
+  This function implements an algorithm to assign affinities to devices in a
+  relatively stable way while still maximizing the use of resources.
+
+  We begin with all affinities unassigned.  We cycle through the list of device
+  serials, and for each one we assign a yet-unassigned affinity.  We choose the
+  affinity to assign by hashing the device serial, so that changes in the set of
+  devices will produce minimal changes in the assignments.  We resolve
+  collisions by rehashing the hash that produced the collision (which will be
+  unique, since it is an md5 hash which we squish down).
+
+  Another way to think of this: each device corresponds to a random series of
+  affinities, then we cycle through the devices giving each device its first
+  available choice.  We expect the first few devices in the list to get their
+  first choice (so they will definitely be stable). Stability is only in danger
+  if a change to the device list produces a cascade of devices getting a
+  different choice than they had before.
+
+  The probability that a later choice is directly disrupted by an earlier change
+  is 1/A, since there are A different assignments to be chosen and hash
+  functions distribute uniformly.  However, there are transitive disruptions: a
+  change in the 1st choice might cause a change in the 2nd choice, which in turn
+  causes a change in the 3rd choice. Call the probability that a the n'th choice
+  is disrupted by changing i'th choice D(i,n) (assuming i < n).  We have the
+  relation:
+
+    D(i,n) = 1 - (1 - 1/A) product from j=i+1 to n-1 of { 1 - D(i,j) D(j,n) }
+                      ^^^                                     ^^^^^^^^^^^^^
+             Disrupted directly                         Transitive disruptions
+
+  From numerical solutions with A=8, the worst case D(1,8) = 26% (the
+  probability of a device added lexicographically first disrupting the last
+  device in the cycle).  The average probability of a choice being affected by a
+  change is 16%.
+  """
+  if not devices:
+    return {}
+  devices = sorted(devices)

[navabi, 2015/06/04 22:30:11]

You may want to not sort the devices. I know you want to avoid keeping
historical data (i.e. what were the devices or affinity assignment I had the
last build), but 'adb devices' gives you some free historical data.

I.e. If I have devices, [a, b, c] on the bot, and 'b' gets replaces with 'd',
you 'adb devices' will show [a, c, d]. You may want this, because it let's the
existing devices (i.e. a and c) get their first choices before d gets to choose.
That way d gets forced into being assigned to what test suites are left, which
are those that b had.

I know it's not as 'pure' of a solution as it relies on this adb devices
artifact, but just something to think about as we consider simpler solutions. 

[luqui, 2015/06/12 02:43:36]

I ran some monte carlo simulations and this turned out to be a very good
suggestion.  It took it down from 2.1 average reassignments per change to 1.36. 
Of course, if the history is ever lost we will have to pay that debt...  Will we
have to pay every time the host is rebooted? (I.e. do they come up randomly?)

+
+  device_cycle = []
+  while len(device_cycle) < test_runner.NUM_DEVICE_AFFINITIES:
+    device_cycle.extend(devices)
+  device_cycle = device_cycle[:test_runner.NUM_DEVICE_AFFINITIES]
+
+  affinity_to_device = {}
+
+  # Hash and rehash each device ID until we get a unique affinity.
+  for device in device_cycle:
+    cur_hash = device
+    while True:
+      cur_hash = hashlib.md5(cur_hash).hexdigest()
+      affinity = int(int(cur_hash, 16) % test_runner.NUM_DEVICE_AFFINITIES)
+      if affinity not in affinity_to_device:
+        affinity_to_device[affinity] = device
+        break
+
+  # Invert the dictionary we just built.
+  device_to_affinity = {}
+  for k, v in affinity_to_device.iteritems():
+    if v not in device_to_affinity:
+      device_to_affinity[v] = []
+    device_to_affinity[v].append(k)
+
+  return device_to_affinity
+
 def Setup(test_options):
   """Create and return the test runner factory and tests.
 
@@ -74,8 +137,9 @@ def Setup(test_options):
   # Before running the tests, kill any leftover server.
   test_environment.CleanupLeftoverProcesses()
 
-  # We want to keep device affinity, so return all devices ever seen.
-  all_devices = _GetAllDevices()
+  all_devices = [d.adb.GetDeviceSerial()
+                 for d in device_utils.DeviceUtils.HealthyDevices()]
+  affinity_map = DistributeAffinities(all_devices)
 
   steps_dict = _GetStepsDict(test_options)
   sorted_step_names = sorted(steps_dict['steps'].keys())
@@ -89,9 +153,9 @@ def Setup(test_options):
     with file(test_options.flaky_steps, 'r') as f:
       flaky_steps = json.load(f)
 
-  def TestRunnerFactory(device, shard_index):
+  def TestRunnerFactory(device, _):
+    affinities = affinity_map[device]
     return test_runner.TestRunner(
-        test_options, device, shard_index, len(all_devices),
-        steps_dict, flaky_steps)
+        test_options, device, affinities, steps_dict, flaky_steps)
 
   return (TestRunnerFactory, sorted_step_names, all_devices)