From 3a3330ccd0106e355f7d8a26dbf1b15db5ab9f7b Mon Sep 17 00:00:00 2001 From: Jon Bratseth Date: Fri, 2 Jul 2021 11:22:56 +0200 Subject: Enable top-k optimization only if balanced and non-sparse --- .../search/dispatch/InterleavedSearchInvoker.java | 12 ++-- .../com/yahoo/search/dispatch/InvokerFactory.java | 2 +- .../yahoo/search/dispatch/searchcluster/Group.java | 15 +++-- .../dispatch/InterleavedSearchInvokerTest.java | 70 ++++++++++++++-------- 4 files changed, 64 insertions(+), 35 deletions(-) (limited to 'container-search') diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/InterleavedSearchInvoker.java b/container-search/src/main/java/com/yahoo/search/dispatch/InterleavedSearchInvoker.java index adf7368faa2..fb04c8299e9 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/InterleavedSearchInvoker.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/InterleavedSearchInvoker.java @@ -3,6 +3,7 @@ package com.yahoo.search.dispatch; import com.yahoo.search.Query; import com.yahoo.search.Result; +import com.yahoo.search.dispatch.searchcluster.Group; import com.yahoo.search.dispatch.searchcluster.SearchCluster; import com.yahoo.search.result.Coverage; import com.yahoo.search.result.ErrorMessage; @@ -41,9 +42,9 @@ public class InterleavedSearchInvoker extends SearchInvoker implements ResponseM private final Set invokers; private final SearchCluster searchCluster; + private final Group group; private final LinkedBlockingQueue availableForProcessing; private final Set alreadyFailedNodes; - private final boolean isContentWellBalanced; private Query query; private boolean adaptiveTimeoutCalculated = false; @@ -60,14 +61,17 @@ public class InterleavedSearchInvoker extends SearchInvoker implements ResponseM private boolean timedOut = false; private boolean degradedByMatchPhase = false; - public InterleavedSearchInvoker(Collection invokers, boolean isContentWellBalanced, SearchCluster searchCluster, Set alreadyFailedNodes) { + public InterleavedSearchInvoker(Collection invokers, + SearchCluster searchCluster, + Group group, + Set alreadyFailedNodes) { super(Optional.empty()); this.invokers = Collections.newSetFromMap(new IdentityHashMap<>()); this.invokers.addAll(invokers); this.searchCluster = searchCluster; + this.group = group; this.availableForProcessing = newQueue(); this.alreadyFailedNodes = alreadyFailedNodes; - this.isContentWellBalanced = isContentWellBalanced; } /** @@ -85,7 +89,7 @@ public class InterleavedSearchInvoker extends SearchInvoker implements ResponseM int originalOffset = query.getOffset(); int neededHits = originalHits + originalOffset; int q = neededHits; - if (isContentWellBalanced) { + if (group.isBalanced() && !group.isSparse()) { Double topkProbabilityOverrride = query.properties().getDouble(Dispatcher.topKProbability); q = (topkProbabilityOverrride != null) ? searchCluster.estimateHitsToFetch(neededHits, invokers.size(), topkProbabilityOverrride) diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/InvokerFactory.java b/container-search/src/main/java/com/yahoo/search/dispatch/InvokerFactory.java index bd66ca88622..e602afadcfb 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/InvokerFactory.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/InvokerFactory.java @@ -89,7 +89,7 @@ public abstract class InvokerFactory { if (invokers.size() == 1 && failed == null) { return Optional.of(invokers.get(0)); } else { - return Optional.of(new InterleavedSearchInvoker(invokers, group.isBalanced(), searchCluster, failed)); + return Optional.of(new InterleavedSearchInvoker(invokers, searchCluster, group, failed)); } } diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/searchcluster/Group.java b/container-search/src/main/java/com/yahoo/search/dispatch/searchcluster/Group.java index 7be5cde0b14..727fb64faef 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/searchcluster/Group.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/searchcluster/Group.java @@ -61,7 +61,7 @@ public class Group { return (int) nodes.stream().filter(node -> node.isWorking() == Boolean.TRUE).count(); } - void aggregateNodeValues() { + public void aggregateNodeValues() { long activeDocs = nodes.stream().filter(node -> node.isWorking() == Boolean.TRUE).mapToLong(Node::getActiveDocuments).sum(); activeDocuments.set(activeDocs); isBlockingWrites.set(nodes.stream().anyMatch(Node::isBlockingWrites)); @@ -69,13 +69,13 @@ public class Group { if (numWorkingNodes > 0) { long average = activeDocs / numWorkingNodes; long skew = nodes.stream().filter(node -> node.isWorking() == Boolean.TRUE).mapToLong(node -> Math.abs(node.getActiveDocuments() - average)).sum(); - boolean skewIsLow = skew <= activeDocs * maxContentSkew; - if (!isBalanced.get() || skewIsLow != isBalanced.get()) { + boolean balanced = skew <= activeDocs * maxContentSkew; + if (!isBalanced.get() || balanced != isBalanced.get()) { if (!isSparse()) - log.info("Content is " + (skewIsLow ? "" : "not ") + "well balanced. Current deviation = " + + log.info("Content is " + (balanced ? "" : "not ") + "well balanced. Current deviation = " + skew * 100 / activeDocs + " %. activeDocs = " + activeDocs + ", skew = " + skew + ", average = " + average); - isBalanced.set(skewIsLow); + isBalanced.set(balanced); } } else { isBalanced.set(true); @@ -92,7 +92,10 @@ public class Group { public boolean isBalanced() { return isBalanced.get(); } /** Returns whether this group has too few documents per node to expect it to be balanced */ - public boolean isSparse() { return activeDocuments.get() / nodes.size() < minDocsPerNodeToRequireLowSkew; } + public boolean isSparse() { + if (nodes.isEmpty()) return false; + return activeDocuments.get() / nodes.size() < minDocsPerNodeToRequireLowSkew; + } public boolean fullCoverageStatusChanged(boolean hasFullCoverageNow) { boolean previousState = hasFullCoverage.getAndSet(hasFullCoverageNow); diff --git a/container-search/src/test/java/com/yahoo/search/dispatch/InterleavedSearchInvokerTest.java b/container-search/src/test/java/com/yahoo/search/dispatch/InterleavedSearchInvokerTest.java index 730aa0800e7..21a15165ab3 100644 --- a/container-search/src/test/java/com/yahoo/search/dispatch/InterleavedSearchInvokerTest.java +++ b/container-search/src/test/java/com/yahoo/search/dispatch/InterleavedSearchInvokerTest.java @@ -7,6 +7,8 @@ import com.yahoo.prelude.fastsearch.FastHit; import com.yahoo.prelude.fastsearch.GroupingListHit; import com.yahoo.search.Query; import com.yahoo.search.Result; +import com.yahoo.search.dispatch.searchcluster.Group; +import com.yahoo.search.dispatch.searchcluster.Node; import com.yahoo.search.dispatch.searchcluster.SearchCluster; import com.yahoo.search.result.Coverage; import com.yahoo.search.result.DefaultErrorHit; @@ -53,7 +55,7 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatAdaptiveTimeoutsAreNotUsedWithFullCoverageRequirement() throws IOException { SearchCluster cluster = new MockSearchCluster("!", createDispatchConfig(100.0), 1, 3); - SearchInvoker invoker = createInterleavedInvoker(cluster, 3); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 3); expectedEvents.add(new Event(5000, 100, 0)); expectedEvents.add(new Event(4900, 100, 1)); @@ -67,7 +69,7 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatTimeoutsAreNotMarkedAsAdaptive() throws IOException { SearchCluster cluster = new MockSearchCluster("!", createDispatchConfig(100.0), 1, 3); - SearchInvoker invoker = createInterleavedInvoker(cluster, 3); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 3); expectedEvents.add(new Event(5000, 300, 0)); expectedEvents.add(new Event(4700, 300, 1)); @@ -85,7 +87,7 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatAdaptiveTimeoutDecreasesTimeoutWhenCoverageIsReached() throws IOException { SearchCluster cluster = new MockSearchCluster("!", createDispatchConfig(50.0), 1, 4); - SearchInvoker invoker = createInterleavedInvoker(cluster, 4); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 4); expectedEvents.add(new Event(5000, 100, 0)); expectedEvents.add(new Event(4900, 100, 1)); @@ -106,7 +108,7 @@ public class InterleavedSearchInvokerTest { SearchCluster cluster = new MockSearchCluster("!", 1, 2); invokers.add(new MockInvoker(0, createCoverage(50155, 50155, 50155, 1, 1, 0))); invokers.add(new MockInvoker(1, createCoverage(49845, 49845, 49845, 1, 1, 0))); - SearchInvoker invoker = createInterleavedInvoker(cluster, 0); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 0); expectedEvents.add(new Event(null, 100, 0)); expectedEvents.add(new Event(null, 200, 1)); @@ -127,7 +129,7 @@ public class InterleavedSearchInvokerTest { SearchCluster cluster = new MockSearchCluster("!", 1, 2); invokers.add(new MockInvoker(0, createCoverage(10101, 50155, 50155, 1, 1, DEGRADED_BY_MATCH_PHASE))); invokers.add(new MockInvoker(1, createCoverage(13319, 49845, 49845, 1, 1, DEGRADED_BY_MATCH_PHASE))); - SearchInvoker invoker = createInterleavedInvoker(cluster, 0); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 0); expectedEvents.add(new Event(null, 100, 0)); expectedEvents.add(new Event(null, 200, 1)); @@ -149,7 +151,7 @@ public class InterleavedSearchInvokerTest { SearchCluster cluster = new MockSearchCluster("!", 1, 2); invokers.add(new MockInvoker(0, createCoverage(5000, 50155, 50155, 1, 1, DEGRADED_BY_TIMEOUT))); invokers.add(new MockInvoker(1, createCoverage(4900, 49845, 49845, 1, 1, DEGRADED_BY_TIMEOUT))); - SearchInvoker invoker = createInterleavedInvoker(cluster, 0); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()),0); expectedEvents.add(new Event(null, 100, 0)); expectedEvents.add(new Event(null, 200, 1)); @@ -171,7 +173,7 @@ public class InterleavedSearchInvokerTest { SearchCluster cluster = new MockSearchCluster("!", 1, 2); invokers.add(new MockInvoker(0, createCoverage(50155, 50155, 50155, 1, 1, 0))); invokers.add(new MockInvoker(1, createCoverage(49845, 49845, 49845, 1, 1, 0))); - SearchInvoker invoker = createInterleavedInvoker(cluster, 0); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 0); expectedEvents.add(new Event(null, 100, 0)); expectedEvents.add(null); @@ -205,8 +207,8 @@ public class InterleavedSearchInvokerTest { private static final List A5Aux = Arrays.asList(-1.0,11.0,8.5,7.5,-7.0,3.0,2.0); private static final List B5Aux = Arrays.asList(9.0,8.0,-3.0,7.0,6.0,1.0, -1.0); - private void validateThatTopKProbabilityOverrideTakesEffect(Double topKProbability, int expectedK, boolean isContentWellBalanced) throws IOException { - InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, isContentWellBalanced); + private void validateThatTopKProbabilityOverrideTakesEffect(Double topKProbability, int expectedK, Group group) throws IOException { + InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, group); query.setHits(8); query.properties().set(Dispatcher.topKProbability, topKProbability); SearchInvoker [] invokers = invoker.invokers().toArray(new SearchInvoker[0]); @@ -228,17 +230,37 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatTopKProbabilityOverrideTakesEffect() throws IOException { - validateThatTopKProbabilityOverrideTakesEffect(null, 8, true); - validateThatTopKProbabilityOverrideTakesEffect(0.8, 7, true); + validateThatTopKProbabilityOverrideTakesEffect(null, 8, new Group(0, List.of())); + validateThatTopKProbabilityOverrideTakesEffect(0.8, 7, new Group(0, List.of())); } + @Test public void requireThatTopKProbabilityOverrideIsDisabledOnContentSkew() throws IOException { - validateThatTopKProbabilityOverrideTakesEffect(0.8, 8, false); + Node node0 = new Node(0, "host0", 0); + Node node1 = new Node(1, "host1", 0); + Group group = new Group(0, List.of(node0, node1)); + + node0.setActiveDocuments(1000000); + node1.setActiveDocuments(1100000); + group.aggregateNodeValues(); + validateThatTopKProbabilityOverrideTakesEffect(0.8, 8, group); + } + + @Test + public void requireThatTopKProbabilityOverrideIsDisabledOnLittleContent() throws IOException { + Node node0 = new Node(0, "host0", 0); + Node node1 = new Node(1, "host1", 0); + Group group = new Group(0, List.of(node0, node1)); + + node0.setActiveDocuments(10); + node1.setActiveDocuments(10); + group.aggregateNodeValues(); + validateThatTopKProbabilityOverrideTakesEffect(0.8, 8, group); } @Test public void requireThatMergeOfConcreteHitsObeySorting() throws IOException { - InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, true); + InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, new Group(0, List.of())); query.setHits(12); Result result = invoker.search(query, null); assertEquals(10, result.hits().size()); @@ -247,7 +269,7 @@ public class InterleavedSearchInvokerTest { assertEquals(0, result.getQuery().getOffset()); assertEquals(12, result.getQuery().getHits()); - invoker = createInterLeavedTestInvoker(B5, A5, true); + invoker = createInterLeavedTestInvoker(B5, A5, new Group(0, List.of())); result = invoker.search(query, null); assertEquals(10, result.hits().size()); assertEquals(11.0, result.hits().get(0).getRelevance().getScore(), DELTA); @@ -258,7 +280,7 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatMergeOfConcreteHitsObeyOffset() throws IOException { - InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, true); + InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5, B5, new Group(0, List.of())); query.setHits(3); query.setOffset(5); Result result = invoker.search(query, null); @@ -268,7 +290,7 @@ public class InterleavedSearchInvokerTest { assertEquals(0, result.getQuery().getOffset()); assertEquals(3, result.getQuery().getHits()); - invoker = createInterLeavedTestInvoker(B5, A5, true); + invoker = createInterLeavedTestInvoker(B5, A5, new Group(0, List.of())); query.setOffset(5); result = invoker.search(query, null); assertEquals(3, result.hits().size()); @@ -280,7 +302,7 @@ public class InterleavedSearchInvokerTest { @Test public void requireThatMergeOfConcreteHitsObeyOffsetWithAuxilliaryStuff() throws IOException { - InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5Aux, B5Aux, true); + InterleavedSearchInvoker invoker = createInterLeavedTestInvoker(A5Aux, B5Aux, new Group(0, List.of())); query.setHits(3); query.setOffset(5); Result result = invoker.search(query, null); @@ -291,7 +313,7 @@ public class InterleavedSearchInvokerTest { assertEquals(0, result.getQuery().getOffset()); assertEquals(3, result.getQuery().getHits()); - invoker = createInterLeavedTestInvoker(B5Aux, A5Aux, true); + invoker = createInterLeavedTestInvoker(B5Aux, A5Aux, new Group(0, List.of())); query.setOffset(5); result = invoker.search(query, null); assertEquals(7, result.hits().size()); @@ -302,13 +324,12 @@ public class InterleavedSearchInvokerTest { assertEquals(3, result.getQuery().getHits()); } - private static InterleavedSearchInvoker createInterLeavedTestInvoker(List a, List b, - boolean isContentWellBalanced) { + private static InterleavedSearchInvoker createInterLeavedTestInvoker(List a, List b, Group group) { SearchCluster cluster = new MockSearchCluster("!", 1, 2); List invokers = new ArrayList<>(); invokers.add(createInvoker(a, 0)); invokers.add(createInvoker(b, 1)); - InterleavedSearchInvoker invoker = new InterleavedSearchInvoker(invokers, isContentWellBalanced, cluster, Collections.emptySet()); + InterleavedSearchInvoker invoker = new InterleavedSearchInvoker(invokers, cluster, group, Collections.emptySet()); invoker.responseAvailable(invokers.get(0)); invoker.responseAvailable(invokers.get(1)); return invoker; @@ -336,7 +357,7 @@ public class InterleavedSearchInvokerTest { Coverage errorCoverage = new Coverage(0, 0, 0); errorCoverage.setNodesTried(1); invokers.add(new SearchErrorInvoker(ErrorMessage.createBackendCommunicationError("node is down"), errorCoverage)); - SearchInvoker invoker = createInterleavedInvoker(cluster, 0); + SearchInvoker invoker = createInterleavedInvoker(cluster, new Group(0, List.of()), 0); expectedEvents.add(new Event(null, 1, 1)); expectedEvents.add(new Event(null, 100, 0)); @@ -354,12 +375,13 @@ public class InterleavedSearchInvokerTest { assertThat(cov.isDegradedByTimeout(), is(true)); } - private InterleavedSearchInvoker createInterleavedInvoker(SearchCluster searchCluster, int numInvokers) { + private InterleavedSearchInvoker createInterleavedInvoker(SearchCluster searchCluster, Group group, int numInvokers) { for (int i = 0; i < numInvokers; i++) { invokers.add(new MockInvoker(i)); } - return new InterleavedSearchInvoker(invokers, false, searchCluster, null) { + return new InterleavedSearchInvoker(invokers, searchCluster, group,null) { + @Override protected long currentTime() { return clock.millis(); -- cgit v1.2.3