From 81575e0b094f78b790fd18f70eb625bd99eafcbc Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Tue, 23 Aug 2022 06:42:28 +0200 Subject: Separate the notion of decaying cost from averageSearchTime, which is only needed for testing. --- .../com/yahoo/search/dispatch/LoadBalancer.java | 28 ++++++------- .../com/yahoo/search/dispatch/RequestDuration.java | 4 +- .../yahoo/search/dispatch/LoadBalancerTest.java | 48 +++++++++++----------- 3 files changed, 41 insertions(+), 39 deletions(-) diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java b/container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java index 8736f612fc1..04855bf24ed 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java @@ -96,12 +96,12 @@ public class LoadBalancer { interface Decayer { void decay(RequestDuration duration); - double averageSearchTime(); + double averageCost(); } static class NoDecay implements Decayer { public void decay(RequestDuration duration) {} - public double averageSearchTime() { return MIN_QUERY_TIME; } + public double averageCost() { return MIN_QUERY_TIME; } } private final Group group; @@ -131,12 +131,8 @@ public class LoadBalancer { } } - Duration averageSearchTime() { - return Duration.ofNanos((long)(decayer.averageSearchTime()*1_000_000_000)); - } - - double averageSearchTimeInverse() { - return 1.0 / decayer.averageSearchTime(); + double weight() { + return 1.0 / decayer.averageCost(); } int groupId() { @@ -214,6 +210,8 @@ public class LoadBalancer { private static double toDouble(Duration duration) { return duration.toNanos()/1_000_000_000.0; } + private static Duration fromDouble(double seconds) { return Duration.ofNanos((long)(seconds*1_000_000_000));} + static class DecayByRequests implements GroupStatus.Decayer { private long queries; private double averageSearchTime; @@ -230,7 +228,8 @@ public class LoadBalancer { queries++; averageSearchTime = (searchTime + (decayRate - 1) * averageSearchTime) / decayRate; } - public double averageSearchTime() { return averageSearchTime; } + public double averageCost() { return averageSearchTime; } + Duration averageSearchTime() { return fromDouble(averageSearchTime);} } static class DecayByTime implements GroupStatus.Decayer { @@ -244,13 +243,14 @@ public class LoadBalancer { prev = start; } public void decay(RequestDuration duration) { - double searchTime = Math.max(duration.duration().toMillis()/1000.0, MIN_QUERY_TIME); + double searchTime = Math.max(toDouble(duration.duration()), MIN_QUERY_TIME); double decayRate = LATENCY_DECAY_TIME; - double sampleWeight = Math.min(decayRate/2, toDouble(duration.timeSince(prev))); + double sampleWeight = Math.min(decayRate/2, toDouble(duration.difference(prev))); averageSearchTime = (sampleWeight*searchTime + (decayRate - sampleWeight) * averageSearchTime) / decayRate; prev = duration; } - public double averageSearchTime() { return averageSearchTime; } + public double averageCost() { return averageSearchTime; } + Duration averageSearchTime() { return fromDouble(averageSearchTime);} } public AdaptiveScheduler(Type type, Random random, List scoreboard) { @@ -267,7 +267,7 @@ public class LoadBalancer { for (GroupStatus gs : scoreboard) { if (rejected == null || !rejected.contains(gs.group.id())) { if (!requireCoverage || gs.group.hasSufficientCoverage()) { - sum += gs.averageSearchTimeInverse(); + sum += gs.weight(); n++; } } @@ -279,7 +279,7 @@ public class LoadBalancer { for (GroupStatus gs : scoreboard) { if (rejected == null || !rejected.contains(gs.group.id())) { if (!requireCoverage || gs.group.hasSufficientCoverage()) { - accum += gs.averageSearchTimeInverse(); + accum += gs.weight(); if (needle < accum / sum) { return Optional.of(gs); } diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/RequestDuration.java b/container-search/src/main/java/com/yahoo/search/dispatch/RequestDuration.java index ad6b7f4a40c..1206277a103 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/RequestDuration.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/RequestDuration.java @@ -5,6 +5,8 @@ import java.time.Duration; import java.time.Instant; /** + * Contains start and and time. Exposes a duration, and lets you measure the time difference between 2 requests. + * It does use System.nanoTime to get a steady clock. * * @author baldersheim */ @@ -29,7 +31,7 @@ class RequestDuration { Duration duration() { return Duration.ofNanos(endTime - startTime); } - Duration timeSince(RequestDuration prev) { + Duration difference(RequestDuration prev) { return Duration.ofNanos(Math.abs(endTime - prev.endTime)); } static RequestDuration of(Duration duration) { diff --git a/container-search/src/test/java/com/yahoo/search/dispatch/LoadBalancerTest.java b/container-search/src/test/java/com/yahoo/search/dispatch/LoadBalancerTest.java index 283c2bc743a..ddf4fae5cba 100644 --- a/container-search/src/test/java/com/yahoo/search/dispatch/LoadBalancerTest.java +++ b/container-search/src/test/java/com/yahoo/search/dispatch/LoadBalancerTest.java @@ -90,29 +90,30 @@ public class LoadBalancerTest { @Test void requireCorrectAverageSearchTimeDecay() { + AdaptiveScheduler.DecayByRequests decayer = new AdaptiveScheduler.DecayByRequests(0, Duration.ofSeconds(1)); GroupStatus gs = newGroupStatus(1); - gs.setDecayer(new AdaptiveScheduler.DecayByRequests(0, Duration.ofSeconds(1))); + gs.setDecayer(decayer); updateSearchTime(gs, RequestDuration.of(Duration.ofSeconds(1))); - assertEquals(Duration.ofSeconds(1), gs.averageSearchTime()); + assertEquals(Duration.ofSeconds(1), decayer.averageSearchTime()); updateSearchTime(gs, RequestDuration.of(Duration.ofSeconds(2))); - assertEquals(Duration.ofNanos(1023255813), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(1023255813), decayer.averageSearchTime()); updateSearchTime(gs, RequestDuration.of(Duration.ofSeconds(2))); - assertEquals(Duration.ofNanos(1045454545), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(1045454545), decayer.averageSearchTime()); updateSearchTime(gs, RequestDuration.of(Duration.ofMillis(100))); updateSearchTime(gs, RequestDuration.of(Duration.ofMillis(100))); updateSearchTime(gs, RequestDuration.of(Duration.ofMillis(100))); updateSearchTime(gs, RequestDuration.of(Duration.ofMillis(100))); - assertEquals(Duration.ofNanos(966666666), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(966666666), decayer.averageSearchTime()); for (int i = 0; i < 10000; i++) { updateSearchTime(gs, RequestDuration.of(Duration.ofSeconds(1))); } - assertEquals(Duration.ofNanos(999999812), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(999999812), decayer.averageSearchTime()); updateSearchTime(gs, RequestDuration.of(Duration.ofMillis(100))); - assertEquals(Duration.ofNanos(999099812), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(999099812), decayer.averageSearchTime()); for (int i = 0; i < 10000; i++) { updateSearchTime(gs, RequestDuration.of(Duration.ZERO)); } - assertEquals(Duration.ofNanos(1045087), gs.averageSearchTime()); + assertEquals(Duration.ofNanos(1045087), decayer.averageSearchTime()); } @Test @@ -193,16 +194,12 @@ public class LoadBalancerTest { assertEquals(0, allocate(sched.takeNextGroup(null).get()).groupId()); } - private static Duration from_s(double seconds) { - return Duration.ofNanos((long)(seconds * 1_000_000_000)); - } - private static int countRequestsToReach90p(Duration timeBetweenSample, Duration searchTime) { double p90 = 0.9*searchTime.toMillis()/1000.0; GroupStatus.Decayer decayer = new AdaptiveScheduler.DecayByTime(Duration.ofMillis(1), RequestDuration.of(Instant.EPOCH, Duration.ZERO)); int requests = 0; Instant start = Instant.EPOCH; - for (; decayer.averageSearchTime() < p90;) { + while (decayer.averageCost() < p90) { decayer.decay(RequestDuration.of(start, searchTime)); start = start.plus(timeBetweenSample); requests++; @@ -213,21 +210,21 @@ public class LoadBalancerTest { @Test public void requireDecayByTimeToDependOnlyOnTime() { GroupStatus.Decayer decayer = new AdaptiveScheduler.DecayByTime(Duration.ofMillis(2), RequestDuration.of(Instant.EPOCH, Duration.ZERO)); - assertEquals(0.002, decayer.averageSearchTime(), delta); + assertEquals(0.002, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(1000), Duration.ofMillis(10))); - assertEquals(0.003616, decayer.averageSearchTime(), delta); + assertEquals(0.003616, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(2000), Duration.ofMillis(10))); - assertEquals(0.0048928, decayer.averageSearchTime(), delta); + assertEquals(0.0048928, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(3000), Duration.ofMillis(10))); - assertEquals(0.00591424, decayer.averageSearchTime(), delta); + assertEquals(0.00591424, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(3100), Duration.ofMillis(10))); - assertEquals(0.0059959552, decayer.averageSearchTime(), delta); + assertEquals(0.0059959552, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(3100), Duration.ofMillis(10))); - assertEquals(0.0059959552, decayer.averageSearchTime(), delta); + assertEquals(0.0059959552, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(3000), Duration.ofMillis(10))); - assertEquals(0.006076036096, decayer.averageSearchTime(), delta); + assertEquals(0.006076036096, decayer.averageCost(), delta); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(5000), Duration.ofMillis(10))); - assertEquals(0.0076456216576000005, decayer.averageSearchTime(), delta); + assertEquals(0.0076456216576000005, decayer.averageCost(), delta); assertEquals(110, countRequestsToReach90p(Duration.ofMillis(100), Duration.ofMillis(10))); assertEquals(55, countRequestsToReach90p(Duration.ofMillis(200), Duration.ofMillis(10))); assertEquals(11, countRequestsToReach90p(Duration.ofMillis(1000), Duration.ofMillis(10))); @@ -235,10 +232,13 @@ public class LoadBalancerTest { @Test public void requireDecayByTimeToNotJumpTooFar() { - GroupStatus.Decayer decayer = new AdaptiveScheduler.DecayByTime(Duration.ofMillis(2), RequestDuration.of(Instant.EPOCH, Duration.ZERO)); - assertEquals(0.002, decayer.averageSearchTime(), delta); + AdaptiveScheduler.DecayByTime decayer = new AdaptiveScheduler.DecayByTime(Duration.ofMillis(2), RequestDuration.of(Instant.EPOCH, Duration.ZERO)); + assertEquals(0.002, decayer.averageCost(), delta); + assertEquals(Duration.ofMillis(2), decayer.averageSearchTime()); decayer.decay(RequestDuration.of(Instant.ofEpochMilli(10000), Duration.ofMillis(10))); - assertEquals(0.006, decayer.averageSearchTime(), delta); // Capped at 50% sampleWeight + assertEquals(0.006, decayer.averageCost(), delta); // Capped at 50% sampleWeight + assertEquals(Duration.ofMillis(6), decayer.averageSearchTime()); + } private static void updateSearchTime(GroupStatus gs, RequestDuration time) { -- cgit v1.2.3