util: Deliver addresses in a random order in MultiChildLb
This should often not matter much, but in b/412468630 it was cleary
visible that child creation order can skew load for the first batch of
RPCs. This doesn't solve all the cases, as further-away backends will
still be less likely chosen initially and it is ignorant of the LB
policy. But this doesn't impact correctness, is easy, and is one fewer
cases to worry about.
diff --git a/util/src/main/java/io/grpc/util/MultiChildLoadBalancer.java b/util/src/main/java/io/grpc/util/MultiChildLoadBalancer.java
index ed33834..2a93ef9 100644
--- a/util/src/main/java/io/grpc/util/MultiChildLoadBalancer.java
+++ b/util/src/main/java/io/grpc/util/MultiChildLoadBalancer.java
@@ -24,7 +24,9 @@
import static io.grpc.ConnectivityState.TRANSIENT_FAILURE;
import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Iterables;
import com.google.common.collect.Maps;
+import com.google.common.primitives.UnsignedInts;
import io.grpc.Attributes;
import io.grpc.ConnectivityState;
import io.grpc.EquivalentAddressGroup;
@@ -40,6 +42,7 @@
import java.util.HashSet;
import java.util.List;
import java.util.Map;
+import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.annotation.Nullable;
@@ -52,6 +55,7 @@
public abstract class MultiChildLoadBalancer extends LoadBalancer {
private static final Logger logger = Logger.getLogger(MultiChildLoadBalancer.class.getName());
+ private static final int OFFSET_SEED = new Random().nextInt();
// Modify by replacing the list to release memory when no longer used.
private List<ChildLbState> childLbStates = new ArrayList<>(0);
private final Helper helper;
@@ -168,9 +172,15 @@
childLbState = createChildLbState(entry.getKey());
}
newChildLbStates.add(childLbState);
- if (entry.getValue() != null) {
+ }
+ // Use a random start position for child updates to weakly "shuffle" connection creation order.
+ // The network will often add noise to the creation order, but this avoids giving earlier
+ // children a consistent head start.
+ for (ChildLbState childLbState : offsetIterable(newChildLbStates, OFFSET_SEED)) {
+ ResolvedAddresses addresses = newChildAddresses.get(childLbState.getKey());
+ if (addresses != null) {
// update child LB
- Status newStatus = childLbState.lb.acceptResolvedAddresses(entry.getValue());
+ Status newStatus = childLbState.lb.acceptResolvedAddresses(addresses);
if (!newStatus.isOk()) {
status = newStatus;
}
@@ -188,6 +198,19 @@
return status;
}
+ @VisibleForTesting
+ static <T> Iterable<T> offsetIterable(Collection<T> c, int seed) {
+ int pos;
+ if (c.isEmpty()) {
+ pos = 0;
+ } else {
+ pos = UnsignedInts.remainder(seed, c.size());
+ }
+ return Iterables.concat(
+ Iterables.skip(c, pos),
+ Iterables.limit(c, pos));
+ }
+
@Nullable
protected static ConnectivityState aggregateState(
@Nullable ConnectivityState overallState, ConnectivityState childState) {
diff --git a/util/src/test/java/io/grpc/util/MultiChildLoadBalancerTest.java b/util/src/test/java/io/grpc/util/MultiChildLoadBalancerTest.java
index c128364..14dc851 100644
--- a/util/src/test/java/io/grpc/util/MultiChildLoadBalancerTest.java
+++ b/util/src/test/java/io/grpc/util/MultiChildLoadBalancerTest.java
@@ -264,6 +264,42 @@
.testEquals();
}
+ @Test
+ public void offsetIterable_positive() {
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1, 2, 3, 4), 9))
+ .containsExactly(2, 3, 4, 1)
+ .inOrder();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1, 2, 3, 4, 5), 9))
+ .containsExactly(5, 1, 2, 3, 4)
+ .inOrder();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1, 2, 3), 3))
+ .containsExactly(1, 2, 3)
+ .inOrder();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1, 2, 3), 0))
+ .containsExactly(1, 2, 3)
+ .inOrder();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1), 123))
+ .containsExactly(1)
+ .inOrder();
+ }
+
+ @Test
+ public void offsetIterable_negative() {
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(1, 2, 3, 4), -1))
+ .containsExactly(4, 1, 2, 3)
+ .inOrder();
+ }
+
+ @Test
+ public void offsetIterable_empty() {
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(), 1))
+ .isEmpty();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(), 0))
+ .isEmpty();
+ assertThat(MultiChildLoadBalancer.offsetIterable(Arrays.asList(), -1))
+ .isEmpty();
+ }
+
private String addressesOnlyString(EquivalentAddressGroup eag) {
if (eag == null) {
return null;
