summaryrefslogtreecommitdiffstats
path: root/container-search/src/main/java/com/yahoo/search/dispatch/LoadBalancer.java
diff options
context:
space:
mode:
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.java105
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);
}