You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@aurora.apache.org by jc...@apache.org on 2016/11/30 22:45:26 UTC
aurora git commit: SlaUtil::percentile percentiles interpolation
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 <re...@gmail.com>
Authored: Wed Nov 30 16:45:06 2016 -0600
Committer: Joshua Cohen <jc...@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);
+ }
+}