aurora-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jco...@apache.org
Subject aurora git commit: SlaUtil::percentile percentiles interpolation
Date Wed, 30 Nov 2016 22:45:26 GMT
Repository: aurora
Updated Branches:
  refs/heads/master 4e46fd892 -> 8bcad84dc


SlaUtil::percentile percentiles interpolation

Modification to SlaUtil::percentile to compute percentiles by interpolation

The calculation of mttX (median-time-to-X) depends on the computation of percentile values.
The
current implementation does not behave nicely with a small sample size. For instance, for
a given
sample set of  {50, 150}, 50-percentile is reported to be 50. Although, 100 seems a more appropriate
return value.

This patch uses Guava's Quantile for interpolation.

Reviewed at https://reviews.apache.org/r/54106/


Project: http://git-wip-us.apache.org/repos/asf/aurora/repo
Commit: http://git-wip-us.apache.org/repos/asf/aurora/commit/8bcad84d
Tree: http://git-wip-us.apache.org/repos/asf/aurora/tree/8bcad84d
Diff: http://git-wip-us.apache.org/repos/asf/aurora/diff/8bcad84d

Branch: refs/heads/master
Commit: 8bcad84dceb5e8531b47af5259cc79b5e73ed4a7
Parents: 4e46fd8
Author: Reza Motamedi <reza.motamedi@gmail.com>
Authored: Wed Nov 30 16:45:06 2016 -0600
Committer: Joshua Cohen <jcohen@apache.org>
Committed: Wed Nov 30 16:45:06 2016 -0600

----------------------------------------------------------------------
 .../aurora/scheduler/sla/SlaAlgorithm.java      |   2 +-
 .../apache/aurora/scheduler/sla/SlaUtil.java    |  32 ++--
 .../aurora/scheduler/sla/SlaAlgorithmTest.java  |  38 ++---
 .../aurora/scheduler/sla/SlaUtilTest.java       | 165 +++++++++++++++++++
 4 files changed, 207 insertions(+), 30 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/aurora/blob/8bcad84d/src/main/java/org/apache/aurora/scheduler/sla/SlaAlgorithm.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/aurora/scheduler/sla/SlaAlgorithm.java b/src/main/java/org/apache/aurora/scheduler/sla/SlaAlgorithm.java
index 263647e..5d8d5bd 100644
--- a/src/main/java/org/apache/aurora/scheduler/sla/SlaAlgorithm.java
+++ b/src/main/java/org/apache/aurora/scheduler/sla/SlaAlgorithm.java
@@ -176,7 +176,7 @@ interface SlaAlgorithm {
               event -> timeFrame.upperEndpoint() - event.getTimestamp(),
               TASK_TO_EVENT)).toList();
 
-      return (int) Math.floor((double) SlaUtil.percentile(uptimes, percentile) / 1000);
+      return (double) SlaUtil.percentile(uptimes, percentile) / 1000;
     }
   }
 

http://git-wip-us.apache.org/repos/asf/aurora/blob/8bcad84d/src/main/java/org/apache/aurora/scheduler/sla/SlaUtil.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/aurora/scheduler/sla/SlaUtil.java b/src/main/java/org/apache/aurora/scheduler/sla/SlaUtil.java
index 156b9c0..f6945aa 100644
--- a/src/main/java/org/apache/aurora/scheduler/sla/SlaUtil.java
+++ b/src/main/java/org/apache/aurora/scheduler/sla/SlaUtil.java
@@ -15,7 +15,7 @@ package org.apache.aurora.scheduler.sla;
 
 import java.util.List;
 
-import com.google.common.collect.Ordering;
+import com.google.common.math.Quantiles;
 
 /**
  * Utility methods for the SLA calculations.
@@ -27,22 +27,34 @@ final class SlaUtil {
   }
 
   /**
-   * Reports the percentile value from the given list ordered in a non-descending order.
-   * Example: [30, 60, 70, 90], the 75 percentile is 30 (i.e. 75% of elements are greater).
+   * Reports the percentile value from the continuous distribution described by a given list
of
+   * samples.
+   *
+   * Example: [30, 60, 70, 90], the 50 percentile is 65.0 (i.e. larger values cover 50% of
the PDF
+   * (Probability Density Function)).
+   * Example: [30, 60, 70, 90], the 75 percentile is 52.5 (i.e. larger values cover 75% of
the PDF).
+   * Example: [30, 60, 70, 90], the 90 percentile is 39.0 (i.e. larger values cover 85% of
the PDF).
+   * Example: [30, 60, 70, 90], the 99 percentile is 30.9 (i.e. larger values cover 95% of
the PDF).
    *
    * @param list List to calculate percentile for.
    * @param percentile Percentile value to apply.
    * @return Element at the given percentile.
    */
-  static Long percentile(List<Long> list, double percentile) {
+  static Number percentile(List<Long> list, double percentile) {
     if (list.isEmpty()) {
-      return 0L;
+      return 0.0;
+    }
+
+    // index should be a full integer. use quantile scale to allow reporting of percentile
values
+    // such as p99.9.
+    double percentileCopy = percentile;
+    int quantileScale = 100;
+    while ((percentileCopy - Math.floor(percentileCopy)) > 0) {
+      quantileScale *= 10;
+      percentileCopy *= 10;
     }
 
-    List<Long> sorted = Ordering.natural().immutableSortedCopy(list);
-    int total = sorted.size();
-    int percentileElements = (int) Math.floor(percentile / 100 * total);
-    int index = total - percentileElements - 1;
-    return index >= 0 && index < total ? sorted.get(index) : 0L;
+    return Quantiles.scale(quantileScale).index((int) Math.floor(quantileScale - percentileCopy))
+        .compute(list);
   }
 }

http://git-wip-us.apache.org/repos/asf/aurora/blob/8bcad84d/src/test/java/org/apache/aurora/scheduler/sla/SlaAlgorithmTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/aurora/scheduler/sla/SlaAlgorithmTest.java b/src/test/java/org/apache/aurora/scheduler/sla/SlaAlgorithmTest.java
index eca1bee..2e719ac 100644
--- a/src/test/java/org/apache/aurora/scheduler/sla/SlaAlgorithmTest.java
+++ b/src/test/java/org/apache/aurora/scheduler/sla/SlaAlgorithmTest.java
@@ -56,7 +56,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(100L, PENDING, 200L, ASSIGNED, 300L, RUNNING)),
             makeTask(ImmutableMap.of(200L, PENDING, 250L, ASSIGNED, 350L, STARTING))),
         Range.closedOpen(0L, 300L));
-    assertEquals(50L, actual);
+    assertEquals(75.0, actual);
   }
 
   @Test
@@ -67,7 +67,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(100L, PENDING, 200L, ASSIGNED, 300L, RUNNING)),
             makeTask(ImmutableMap.of(200L, PENDING, 250L, ASSIGNED, 350L, STARTING))),
         Range.closedOpen(0L, 300L));
-    assertEquals(100L, actual);
+    assertEquals(100.0, actual);
   }
 
   @Test
@@ -77,7 +77,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(50L, PENDING)),
             makeTask(ImmutableMap.of(100L, PENDING, 200L, ASSIGNED, 300L, KILLED))),
         Range.closedOpen(0L, 300L));
-    assertEquals(0L, actual);
+    assertEquals(0.0, actual);
   }
 
   @Test
@@ -87,7 +87,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(50L, PENDING)),
             makeTask(ImmutableMap.of(100L, PENDING, 200L, ASSIGNED))),
         Range.closedOpen(0L, 300L));
-    assertEquals(100L, actual);
+    assertEquals(100.0, actual);
   }
 
   @Test(expected = IllegalArgumentException.class)
@@ -117,7 +117,7 @@ public class SlaAlgorithmTest {
                 200L, RUNNING,
                 300L, KILLED))), // Ignored due to being terminal.
         Range.closedOpen(0L, 500L));
-    assertEquals(100L, actual);
+    assertEquals(150.0, actual);
   }
 
   @Test
@@ -140,7 +140,7 @@ public class SlaAlgorithmTest {
                 200L, RUNNING,
                 300L, KILLED))), // Ignored due to being terminal.
         Range.closedOpen(0L, 500L));
-    assertEquals(200L, actual);
+    assertEquals(200.0, actual);
   }
 
   @Test
@@ -151,7 +151,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(50L, PENDING, 100L, STARTING, 200L, RUNNING, 300L, KILLED)),
             makeTask(ImmutableMap.of(50L, PENDING, 100L, STARTING, 200L, KILLED))),
         Range.closedOpen(0L, 500L));
-    assertEquals(0L, actual);
+    assertEquals(0.0, actual);
   }
 
   @Test
@@ -168,7 +168,7 @@ public class SlaAlgorithmTest {
                 200L, RUNNING,
                 300L, KILLED))), // Ignored due to being terminal.
         Range.closedOpen(0L, 500L));
-    assertEquals(130L, actual);
+    assertEquals(215.0, actual);
   }
 
   @Test
@@ -180,7 +180,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(100L, PENDING, 200L, ASSIGNED, 300L, STARTING, 400L,
RUNNING)),
             makeTask(ImmutableMap.of(50L, PENDING, 100L, ASSIGNED, 150L, STARTING, 200L,
RUNNING))),
         Range.closedOpen(0L, 500L));
-    assertEquals(150L, actual);
+    assertEquals(150.0, actual);
   }
 
   @Test
@@ -190,7 +190,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(50L, PENDING)),
             makeTask(ImmutableMap.of(50L, PENDING, 100L, RUNNING, 200L, KILLED))),
         Range.closedOpen(0L, 500L));
-    assertEquals(0L, actual);
+    assertEquals(0.0, actual);
   }
 
   @Test
@@ -204,7 +204,7 @@ public class SlaAlgorithmTest {
             makeTask(ImmutableMap.of(100L, PENDING, 260L, ASSIGNED)),
             makeTask(ImmutableMap.of(100L, PENDING, 400L, ASSIGNED))),
         Range.closedOpen(200L, 300L));
-    assertEquals(100L, actual);
+    assertEquals(130.0, actual);
   }
 
   @Test
@@ -213,7 +213,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_50.getAlgorithm().calculate(
         makeUptimeTasks(100, now),
         Range.closed(0L, now));
-    assertEquals(50, actual);
+    assertEquals(50.5, actual);
   }
 
   @Test
@@ -222,7 +222,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_75.getAlgorithm().calculate(
         makeUptimeTasks(100, now),
         Range.closed(0L, now));
-    assertEquals(25, actual);
+    assertEquals(25.75, actual);
   }
 
   @Test
@@ -231,7 +231,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_90.getAlgorithm().calculate(
         makeUptimeTasks(100, now),
         Range.closed(0L, now));
-    assertEquals(10, actual);
+    assertEquals(10.9, actual);
   }
 
   @Test
@@ -240,7 +240,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_95.getAlgorithm().calculate(
         makeUptimeTasks(100, now),
         Range.closed(0L, now));
-    assertEquals(5, actual);
+    assertEquals(5.95, actual);
   }
 
   @Test
@@ -249,7 +249,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_99.getAlgorithm().calculate(
         makeUptimeTasks(100, now),
         Range.closed(0L, now));
-    assertEquals(1, actual);
+    assertEquals(1.99, actual);
   }
 
   @Test
@@ -258,7 +258,7 @@ public class SlaAlgorithmTest {
     Number actual = JOB_UPTIME_99.getAlgorithm().calculate(
         new LinkedList<IScheduledTask>(),
         Range.closed(0L, now));
-    assertEquals(0, actual);
+    assertEquals(0.0, actual);
   }
 
   @Test
@@ -267,7 +267,7 @@ public class SlaAlgorithmTest {
     Set<IScheduledTask> instances = makeUptimeTasks(100, now);
     instances.add(makeTask(ImmutableMap.of(now - 5000, RUNNING, now - 3000, KILLED)));
     Number actual = JOB_UPTIME_99.getAlgorithm().calculate(instances, Range.closed(0L, now));
-    assertEquals(1, actual);
+    assertEquals(1.99, actual);
   }
 
   @Test
@@ -276,7 +276,7 @@ public class SlaAlgorithmTest {
     Set<IScheduledTask> instances = makeUptimeTasks(100, now);
     instances.add(makeTask(ImmutableMap.of(now - 5000, RUNNING, now - 3000, RESTARTING)));
     Number actual = JOB_UPTIME_99.getAlgorithm().calculate(instances, Range.closed(0L, now));
-    assertEquals(1, actual);
+    assertEquals(1.99, actual);
   }
 
   @Test

http://git-wip-us.apache.org/repos/asf/aurora/blob/8bcad84d/src/test/java/org/apache/aurora/scheduler/sla/SlaUtilTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/aurora/scheduler/sla/SlaUtilTest.java b/src/test/java/org/apache/aurora/scheduler/sla/SlaUtilTest.java
new file mode 100644
index 0000000..a3f9928
--- /dev/null
+++ b/src/test/java/org/apache/aurora/scheduler/sla/SlaUtilTest.java
@@ -0,0 +1,165 @@
+/**
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.aurora.scheduler.sla;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertSame;
+
+public class SlaUtilTest {
+
+  private List<Long> samples;
+
+  @Test
+  public void testPercentileEmpty() {
+    samples = new LinkedList<>();
+    Number actual = SlaUtil.percentile(samples, 75);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(0.0, actual);
+  }
+
+  @Test
+  public void testPercentileSingleValue() {
+    samples = new LinkedList<>(Collections.singletonList(10L));
+    Number actual = SlaUtil.percentile(samples, 75);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(10.0, actual);
+  }
+
+  @Test
+  public void testPercentileConstant() {
+    samples = new LinkedList<>();
+    for (int i = 0; i < 100; i++) {
+      samples.add(10L);
+    }
+    Number actual = SlaUtil.percentile(samples, 75);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(10.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(10.0, actual);
+  }
+
+  @Test
+  public void testPercentileLinearEven() {
+    samples = new LinkedList<>();
+    for (int i = 0; i < 100; i += 4) {
+      samples.add((long) i);
+    }
+    samples.add(100L);
+
+    assertSame(samples.size() % 2, 0);
+
+    Number actual = SlaUtil.percentile(samples, 50);
+    assertEquals(50.0, actual);
+
+    actual = SlaUtil.percentile(samples, 75);
+    assertEquals(25.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(1.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(0.1, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(100.0, actual);
+  }
+
+  @Test
+  public void testPercentileLinearOdd() {
+    samples = new LinkedList<>();
+    for (int i = 0; i <= 100; i++) {
+      samples.add((long) i);
+    }
+
+    assertSame(samples.size() % 2, 1);
+
+    Number actual = SlaUtil.percentile(samples, 50);
+    assertEquals(50.0, actual);
+
+    actual = SlaUtil.percentile(samples, 75);
+    assertEquals(25.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(1.0, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(0.1, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(0.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(100.0, actual);
+  }
+
+  @Test
+  public void testPercentileInterpolate() {
+    samples = new LinkedList<>(Arrays.asList(30L, 70L, 90L, 60L));
+    Number actual = SlaUtil.percentile(samples, 75);
+    assertEquals(52.5, actual);
+
+    actual = SlaUtil.percentile(samples, 99);
+    assertEquals(30.9, actual);
+
+    actual = SlaUtil.percentile(samples, 99.9);
+    assertEquals(30.09, actual);
+
+    actual = SlaUtil.percentile(samples, 100);
+    assertEquals(30.0, actual);
+
+    actual = SlaUtil.percentile(samples, 0);
+    assertEquals(90.0, actual);
+  }
+}


Mime
View raw message