graphite-dev team mailing list archive

[Michael Leinartas <mleinartas@xxxxxxxxx>]

Michael Leinartas has proposed merging lp:~mleinartas/graphite/stdev into lp:graphite.

Requested reviews:
  graphite-dev (graphite-dev)

For more details, see:
https://code.launchpad.net/~mleinartas/graphite/stdev/+merge/94248

This is a rewrite of the standard deviation function. The previous version was very intolerant of missing values. In the best case, it would skew the result (average calculations would effectively treat the None as a zero) and in the worst (and most common) case it would crash (see https://bugs.launchpad.net/graphite/+bug/907586).

This version will tolerate nulls in a configurable manner using the optional parameter windowTolerance. If windowTolerance is set to 0.0, a standard deviation will not be output unless every point in the window size is present. This means that the beginning will be padded with Nones for the first n points, and any missing value will trigger another n points of Nones (until the None in the input falls out of the window).

I've set the default tolerance to 0.10 - up to 1 in 10 of the input values can be None for the standard deviation to still be calculated. My thought is that this will be accurate enough for most purposes and will be less surprising than the 0.0 case where users may be confused when they see a large gap in the graph due to a single value missing. Users who do care about the values being absolutely correct can set this tolerance to 0.0, others who care less about correctness and want to ensure a complete graph when data is sparse can up the tolerance.

I'd love some feedback on the tolerance thing - is 0.10 a good default? does it make sense to be 0 as intolerant and 1 as tolerant? should it be the inverse?
-- 
https://code.launchpad.net/~mleinartas/graphite/stdev/+merge/94248
Your team graphite-dev is requested to review the proposed merge of lp:~mleinartas/graphite/stdev into lp:graphite.

=== modified file 'webapp/graphite/render/functions.py'
--- webapp/graphite/render/functions.py	2012-02-21 08:14:23 +0000
+++ webapp/graphite/render/functions.py	2012-02-22 18:40:28 +0000
@@ -33,15 +33,15 @@
 #Utility functions
 def safeSum(values):
   safeValues = [v for v in values if v is not None]
-  if not safeValues: return None
-  return sum(safeValues)
+  if safeValues:
+    return sum(safeValues)
 
 def safeDiff(values):
   safeValues = [v for v in values if v is not None]
-  if not safeValues: return None
-  values = map(lambda x: x*-1, safeValues[1:])
-  values.insert(0, safeValues[0])
-  return sum(values)
+  if safeValues:
+    values = map(lambda x: x*-1, safeValues[1:])
+    values.insert(0, safeValues[0])
+    return sum(values)
 
 def safeLen(values):
   return len([v for v in values if v is not None])
@@ -52,7 +52,8 @@
   return float(a) / float(b)
 
 def safeMul(*factors):
-  if None in factors: return None
+  if None in factors:
+    return None
 
   factors = map(float, factors)
   product = reduce(lambda x,y: x*y, factors)
@@ -76,6 +77,11 @@
   if safeValues:
     return max(safeValues)
 
+def safeMap(function, values):
+  safeValues = [v for v in values if v is not None]
+  if safeValues:
+    return map(function, values)
+
 def lcm(a,b):
   if a == b: return a
   if a < b: (a,b) = (b,a) #ensure a > b
@@ -1290,62 +1296,70 @@
   return [ series for (sigma,series) in deviants ][:n] #return the n most deviant series
 
 
-# returns a two-element tuple
-# the first element is the std dev, the second is the new sum of squares
-def doStdDev(sumOfSquares, first, new, n, avg):
-   newSumOfSquares = sumOfSquares - (first * first) + (new * new)
-   return (math.sqrt((newSumOfSquares / float(n)) - (avg * avg)), newSumOfSquares)
-
-
-def stdev(requestContext, seriesList, time):
+def stdev(requestContext, seriesList, points, windowTolerance=0.1):
   """
   Takes one metric or a wildcard seriesList followed by an integer N.
   Draw the Standard Deviation of all metrics passed for the past N datapoints.
+  If the ratio of null points in the window is greater than windowTolerance,
+  skip the calculation. The default for windowTolerance is 0.1 (up to 10% of points
+  in the window can be missing). Note that if this is set to 0.0, it will cause large
+  gaps in the output anywhere a single point is missing.
 
   Example:
 
   .. code-block:: none
 
-    &target=stddev(server*.instance*.threads.busy,30)
+    &target=stdev(server*.instance*.threads.busy,30)
+    &target=stdev(server*.instance*.cpu.system,30,0.0)
 
   """
 
-  count = 0
-  for series in seriesList:
-    stddevs = TimeSeries("stddev(%s,%.1f)" % (series.name, float(time)), series.start, series.end, series.step, [])
-    stddevs.pathExpression = "stddev(%s,%.1f)" % (series.name, float(time))
-    avg = safeDiv(safeSum(series[:time]), time)
-    sumOfSquares = None
-
-    if avg is not None:
-      sumOfSquares = sum(map(lambda(x): x * x, [v for v in series[:time] if v is not None]))
-      (sd, sumOfSquares) = doStdDev(sumOfSquares, 0, 0, time, avg)
-      stddevs.append(sd)
-    else:
-      stddevs.append(None)
-
-    for (index, el) in enumerate(series[time:]):
-      if el is None:
-        continue
-
-      toDrop = series[index]
-      if toDrop is None:
-        toDrop = 0
-
-      s = safeSum([safeMul(time, avg), el, -toDrop])
-      avg = safeDiv(s, time)
-
-      if avg is not None and sumOfSquares is not None:
-        (sd, sumOfSquares) = doStdDev(sumOfSquares, toDrop, series[index+time], time, avg)
-        stddevs.append(sd)
-      else:
-        stddevs.append(None)
-
-    for i in range(0, time-1):
-      stddevs.insert(0, None)
-
-    seriesList[count] = stddevs
-    count = count + 1
+  # For this we take the standard deviation in terms of the moving average
+  # and the moving average of series squares.
+  for (seriesIndex,series) in enumerate(seriesList):
+    stddevSeries = TimeSeries("stddev(%s,%.1f)" % (series.name, float(points)), series.start, series.end, series.step, [])
+    stddevSeries.pathExpression = "stddev(%s,%.1f)" % (series.name, float(points))
+
+    validPoints = 0
+    currentSum = 0
+    currentSumOfSquares = 0
+    for (index, newValue) in enumerate(series):
+      # Mark whether we've reached our window size - dont drop points out otherwise
+      if index < points:
+        bootstrapping = True
+        droppedValue = None
+      else:
+        bootstrapping = False
+        droppedValue = series[index - points]
+
+      # Track non-None points in window
+      if not bootstrapping and droppedValue is not None:
+        validPoints -= 1
+      if newValue is not None:
+        validPoints += 1
+
+      # Remove the value that just dropped out of the window
+      if not bootstrapping and droppedValue is not None:
+        currentSum -= droppedValue
+        currentSumOfSquares -= droppedValue**2
+
+      # Add in the value that just popped in the window
+      if newValue is not None:
+        currentSum += newValue
+        currentSumOfSquares += newValue**2
+
+      if validPoints > 0 and \
+        float(validPoints)/points >= windowTolerance:
+
+        try:
+          deviation = math.sqrt(validPoints * currentSumOfSquares - currentSum**2)/validPoints
+        except ValueError:
+          deviation = None
+        stddevSeries.append(deviation)
+      else:
+        stddevSeries.append(None)
+
+    seriesList[seriesIndex] = stddevSeries
 
   return seriesList