Normalize the weights instead of using raw values

The weight system is being used by the scheduler and the cells code.
Currently this system is using the raw values instead of normalizing them.
This makes difficult to properly use multipliers for establishing the
relative importance between two wheighers (one big magnitude could
shade a smaller one). This change introduces weight normalization so
that:

- From an operator point of view we can prioritize the weighers that
  we are applying. The only way to do this is being sure that all the
  weighers will give a value in a known range, so that it is
  not needed to artificially use a huge multiplier to prioritize a
  weigher.

- From a weigher developer point of view, somebody willing to implement
  one has to care about 1) returning a list of values, 2) setting the
  minimum and maximum values where the weights can range, if they are
  needed and they are significant for the weighing. For a weigher
  developer there are two use cases:

    Case 1: Use of a percentage instead of absolute values (for example, %
    of free RAM). If we compare two nodes focusing on the percentage of free
    ram, the maximum value for the weigher is 100. If we have two nodes one
    with 2048 total/1024 free, and the second one 1024 total/512 free they
    will get both the same weight, since they have the same % of free RAM
    (that is, the 50%).

    Case 2: Use of absolute values. In this case, the maximum of the weigher
    will be the maximum of the values in the list (in the case above, 1024)
    or the maximum value that the magnitude could take (in the case above,
    2048). How this maximum is set, is a decision of the developer. He may
    let the operator choose the behaviour of the weigher though.

- From the point of view of the scheduler we ensure that it is using
  normalized values, and not leveraging the normalization mechanism to the
  weighers.

Changes introduced this commit:

1) it introduces weight normalization so that we can apply multipliers
   easily. All the weights for an object will be normalized between 0.0 and
   1.0 before being sumed up, so that the final weight for a host will be:

    weight = w1_multiplier * norm(w1) + w2_multiplier * norm(w2) + ...

2) weights.BaseWeigher has been changed into an ABC so that we enforce
   that all weighers have the expected methods.

3) weights.BaseWeigher.weigh_objects() does no longer sum up the
   computer weighs to the object, but it rather returns a list that will be
   then normalized and added to the existing weight by BaseWeightHandler

4) Adapt the existing weighers to the above changes. Namely
    - New 'offset_weight_multiplier' for the cell weigher
      nova.cells.weights.weight_offset.WeightOffsetWeigher
    - Changed the name of the existing multiplier methods.

5) unittests for all of the introduced changes.

Implements blueprint normalize-scheduler-weights

DocImpact: Now weights for an object are normalized before suming them
up. This means that each weigher will take a maximum value of 1. This
may have an impact for operators that are using more than one weigher
(currently there is only one weigher: RAMWeiger) and for operators using
cells (where we have several weighers). It is needed to review then the
multipliers used and adjust them properly in case they have been
modified.

Docimpact: There is a new configuration option 'offset_weight_multiplier'
in nova.cells.weights.weight_offset.WeightOffsetWeigher

Change-Id: I81bf90898d3cb81541f4390596823cc00106eb20

1 files changed, 87 insertions, 14 deletions

diff --git a/nova/weights.py b/nova/weights.py
index da5c93a7ad..c8ee1cd355 100644
--- a/nova/weights.py
+++ b/nova/weights.py
@@ -17,9 +17,40 @@
 Pluggable Weighing support
 """
 
+import abc
+
 from nova import loadables
 
 
+def normalize(weight_list, minval=None, maxval=None):
+    """Normalize the values in a list between 0 and 1.0.
+
+    The normalization is made regarding the lower and upper values present in
+    weight_list. If the minval and/or maxval parameters are set, these values
+    will be used instead of the minimum and maximum from the list.
+
+    If all the values are equal, they are normalized to 0.
+    """
+
+    if not weight_list:
+        return ()
+
+    if maxval is None:
+        maxval = max(weight_list)
+
+    if minval is None:
+        minval = min(weight_list)
+
+    maxval = float(maxval)
+    minval = float(minval)
+
+    if minval == maxval:
+        return [0] * len(weight_list)
+
+    range_ = maxval - minval
+    return ((i - minval) / range_ for i in weight_list)
+
+
 class WeighedObject(object):
     """Object with weight information."""
     def __init__(self, obj, weight):
@@ -31,26 +62,59 @@ class WeighedObject(object):
 
 
 class BaseWeigher(object):
-    """Base class for pluggable weighers."""
-    def _weight_multiplier(self):
-        """How weighted this weigher should be.  Normally this would
-        be overridden in a subclass based on a config value.
+    """Base class for pluggable weighers.
+
+    The attributes maxval and minval can be specified to set up the maximum
+    and minimum values for the weighed objects. These values will then be
+    taken into account in the normalization step, instead of taking the values
+    from the calculated weights.
+    """
+
+    __metaclass__ = abc.ABCMeta
+
+    minval = None
+    maxval = None
+
+    def weight_multiplier(self):
+        """How weighted this weigher should be.
+
+        Override this method in a subclass, so that the returned value is
+        read from a configuration option to permit operators specify a
+        multiplier for the weigher.
         """
         return 1.0
 
+    @abc.abstractmethod
     def _weigh_object(self, obj, weight_properties):
-        """Override in a subclass to specify a weight for a specific
-        object.
-        """
-        return 0.0
+        """Weigh an specific object."""
 
     def weigh_objects(self, weighed_obj_list, weight_properties):
-        """Weigh multiple objects.  Override in a subclass if you need
-        need access to all objects in order to manipulate weights.
+        """Weigh multiple objects.
+
+        Override in a subclass if you need access to all objects in order
+        to calculate weights. Do not modify the weight of an object here,
+        just return a list of weights.
         """
+        # Calculate the weights
+        weights = []
         for obj in weighed_obj_list:
-            obj.weight += (self._weight_multiplier() *
-                           self._weigh_object(obj.obj, weight_properties))
+            weight = self._weigh_object(obj.obj, weight_properties)
+
+            # Record the min and max values if they are None. If they anything
+            # but none we assume that the weigher has set them
+            if self.minval is None:
+                self.minval = weight
+            if self.maxval is None:
+                self.maxval = weight
+
+            if weight < self.minval:
+                self.minval = weight
+            elif weight > self.maxval:
+                self.maxval = weight
+
+            weights.append(weight)
+
+        return weights
 
 
 class BaseWeightHandler(loadables.BaseLoader):
@@ -58,7 +122,7 @@ class BaseWeightHandler(loadables.BaseLoader):
 
     def get_weighed_objects(self, weigher_classes, obj_list,
             weighing_properties):
-        """Return a sorted (highest score first) list of WeighedObjects."""
+        """Return a sorted (descending), normalized list of WeighedObjects."""
 
         if not obj_list:
             return []
@@ -66,6 +130,15 @@ class BaseWeightHandler(loadables.BaseLoader):
         weighed_objs = [self.object_class(obj, 0.0) for obj in obj_list]
         for weigher_cls in weigher_classes:
             weigher = weigher_cls()
-            weigher.weigh_objects(weighed_objs, weighing_properties)
+            weights = weigher.weigh_objects(weighed_objs, weighing_properties)
+
+            # Normalize the weights
+            weights = normalize(weights,
+                                minval=weigher.minval,
+                                maxval=weigher.maxval)
+
+            for i, weight in enumerate(weights):
+                obj = weighed_objs[i]
+                obj.weight += weigher.weight_multiplier() * weight
 
         return sorted(weighed_objs, key=lambda x: x.weight, reverse=True)