diff options
Diffstat (limited to 'container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java')
-rw-r--r-- | container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java | 105 |
1 files changed, 78 insertions, 27 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 6d8bb1dce3d..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 @@ -26,8 +26,9 @@ public class LoadBalancer { private static final long DEFAULT_LATENCY_DECAY_RATE = 1000; private static final long MIN_LATENCY_DECAY_RATE = 42; - private static final double INITIAL_QUERY_TIME = 0.001; - private static final double MIN_QUERY_TIME = 0.001; + private static final double LATENCY_DECAY_TIME = Duration.ofSeconds(5).toMillis()/1000.0; + private static final Duration INITIAL_QUERY_TIME = Duration.ofMillis(1); + private static final double MIN_QUERY_TIME = Duration.ofMillis(1).toMillis()/1000.0; private final List<GroupStatus> scoreboard; private final GroupScheduler scheduler; @@ -45,8 +46,8 @@ public class LoadBalancer { this.scheduler = switch (policy) { case ROUNDROBIN: yield new RoundRobinScheduler(scoreboard); case BEST_OF_RANDOM_2: yield new BestOfRandom2(new Random(), scoreboard); - case LATENCY_AMORTIZED_OVER_REQUESTS: yield new AdaptiveScheduler(new Random(), scoreboard); - case LATENCY_AMORTIZED_OVER_TIME: yield new AdaptiveScheduler(new Random(), scoreboard); // TODO Intentionally the same for now + case LATENCY_AMORTIZED_OVER_REQUESTS: yield new AdaptiveScheduler(AdaptiveScheduler.Type.REQUESTS, new Random(), scoreboard); + case LATENCY_AMORTIZED_OVER_TIME: yield new AdaptiveScheduler(AdaptiveScheduler.Type.TIME, new Random(), scoreboard); }; } @@ -80,7 +81,7 @@ public class LoadBalancer { * @param success was the query successful * @param searchTime query execution time, used for adaptive load balancing */ - public void releaseGroup(Group group, boolean success, Duration searchTime) { + public void releaseGroup(Group group, boolean success, RequestDuration searchTime) { synchronized (this) { for (GroupStatus sched : scoreboard) { if (sched.group.id() == group.id()) { @@ -93,50 +94,51 @@ public class LoadBalancer { static class GroupStatus { + interface Decayer { + void decay(RequestDuration duration); + double averageCost(); + } + + static class NoDecay implements Decayer { + public void decay(RequestDuration duration) {} + public double averageCost() { return MIN_QUERY_TIME; } + } + private final Group group; private int allocations = 0; - private long queries = 0; - private double averageSearchTime = INITIAL_QUERY_TIME; + private Decayer decayer; GroupStatus(Group group) { this.group = group; + this.decayer = new NoDecay(); + } + void setDecayer(Decayer decayer) { + this.decayer = decayer; } void allocate() { allocations++; } - void release(boolean success, Duration searchTime) { - double searchSeconds = searchTime.toMillis()/1000.0; + void release(boolean success, RequestDuration searchTime) { allocations--; if (allocations < 0) { log.warning("Double free of query target group detected"); allocations = 0; } if (success) { - searchSeconds = Math.max(searchSeconds, MIN_QUERY_TIME); - double decayRate = Math.min(queries + MIN_LATENCY_DECAY_RATE, DEFAULT_LATENCY_DECAY_RATE); - averageSearchTime = (searchSeconds + (decayRate - 1) * averageSearchTime) / decayRate; - queries++; + decayer.decay(searchTime); } } - Duration averageSearchTime() { - return Duration.ofNanos((long)(averageSearchTime*1000000000)); - } - - double averageSearchTimeInverse() { - return 1.0 / averageSearchTime; + double weight() { + return 1.0 / decayer.averageCost(); } int groupId() { return group.id(); } - void setQueryStatistics(long queries, Duration averageSearchTime) { - this.queries = queries; - this.averageSearchTime = averageSearchTime.toMillis()/1000.0; - } } private interface GroupScheduler { @@ -201,13 +203,62 @@ public class LoadBalancer { } static class AdaptiveScheduler implements GroupScheduler { - + enum Type {TIME, REQUESTS} private final Random random; private final List<GroupStatus> scoreboard; - public AdaptiveScheduler(Random random, List<GroupStatus> scoreboard) { + 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; + DecayByRequests() { + this(0, INITIAL_QUERY_TIME); + } + DecayByRequests(long initialQueries, Duration initialSearchTime) { + queries = initialQueries; + averageSearchTime = toDouble(initialSearchTime); + } + public void decay(RequestDuration duration) { + double searchTime = Math.max(toDouble(duration.duration()), MIN_QUERY_TIME); + double decayRate = Math.min(queries + MIN_LATENCY_DECAY_RATE, DEFAULT_LATENCY_DECAY_RATE); + queries++; + averageSearchTime = (searchTime + (decayRate - 1) * averageSearchTime) / decayRate; + } + public double averageCost() { return averageSearchTime; } + Duration averageSearchTime() { return fromDouble(averageSearchTime);} + } + + static class DecayByTime implements GroupStatus.Decayer { + private double averageSearchTime; + private RequestDuration prev; + DecayByTime() { + this(INITIAL_QUERY_TIME, RequestDuration.of(Duration.ZERO)); + } + DecayByTime(Duration initialSearchTime, RequestDuration start) { + averageSearchTime = toDouble(initialSearchTime); + prev = start; + } + public void decay(RequestDuration duration) { + double searchTime = Math.max(toDouble(duration.duration()), MIN_QUERY_TIME); + double decayRate = LATENCY_DECAY_TIME; + double sampleWeight = Math.min(decayRate/2, toDouble(duration.difference(prev))); + averageSearchTime = (sampleWeight*searchTime + (decayRate - sampleWeight) * averageSearchTime) / decayRate; + prev = duration; + } + public double averageCost() { return averageSearchTime; } + Duration averageSearchTime() { return fromDouble(averageSearchTime);} + } + + public AdaptiveScheduler(Type type, Random random, List<GroupStatus> scoreboard) { this.random = random; this.scoreboard = scoreboard; + for (GroupStatus gs : scoreboard) { + gs.setDecayer(type == Type.REQUESTS ? new DecayByRequests() : new DecayByTime()); + } } private Optional<GroupStatus> selectGroup(double needle, boolean requireCoverage, Set<Integer> rejected) { @@ -216,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++; } } @@ -228,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); } |