#18890

Committed 09 Nov 2023 09:46PM UTC coverage: 88.206% (-0.06%) from 88.264%

Build # #18890

Build Type

push

github

Committed by

web-flow

Commit Message

xds:Make Ring Hash LB a petiole policy (#10610)

* Update picker logic per A61 that it no longer pays attention to the first 2 elements, but rather takes the first ring element not in TF and uses that.
---------
Pulled in by rebase:
Eric Anderson  (android: Remove unneeded proguard rule 44723b6)
Terry Wilson (stub: Deprecate StreamObservers b5434e8)

Run Details

30334 of 34390 relevant lines covered (88.21%)

0.88 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.41

/../util/src/main/java/io/grpc/util/RoundRobinLoadBalancer.java

/*
 * Copyright 2016 The gRPC Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package io.grpc.util;

import static com.google.common.base.Preconditions.checkArgument;
import static io.grpc.ConnectivityState.CONNECTING;
import static io.grpc.ConnectivityState.IDLE;
import static io.grpc.ConnectivityState.READY;
import static io.grpc.ConnectivityState.TRANSIENT_FAILURE;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import io.grpc.ConnectivityState;
import io.grpc.EquivalentAddressGroup;
import io.grpc.Internal;
import io.grpc.LoadBalancer;
import io.grpc.NameResolver;
import io.grpc.Status;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
import javax.annotation.Nonnull;

/**
 * A {@link LoadBalancer} that provides round-robin load-balancing over the {@link
 * EquivalentAddressGroup}s from the {@link NameResolver}.
 */
@Internal
public class RoundRobinLoadBalancer extends MultiChildLoadBalancer {
  private final Random random;
  protected RoundRobinPicker currentPicker = new EmptyPicker(EMPTY_OK);

  public RoundRobinLoadBalancer(Helper helper) {
    super(helper);
    this.random = new Random();
  }

  @Override
  protected SubchannelPicker getSubchannelPicker(Map<Object, SubchannelPicker> childPickers) {
    throw new UnsupportedOperationException(); // local updateOverallBalancingState doesn't use this
  }

  private static final Status EMPTY_OK = Status.OK.withDescription("no subchannels ready");

  /**
   * Updates picker with the list of active subchannels (state == READY).
   */
  @Override
  protected void updateOverallBalancingState() {
    List<ChildLbState> activeList = getReadyChildren();
    if (activeList.isEmpty()) {
      // No READY subchannels

      // RRLB will request connection immediately on subchannel IDLE.
      boolean isConnecting = false;
      for (ChildLbState childLbState : getChildLbStates()) {
        ConnectivityState state = childLbState.getCurrentState();
        if (state == CONNECTING || state == IDLE) {
          isConnecting = true;
          break;
        }
      }

      if (isConnecting) {
        updateBalancingState(CONNECTING,  new EmptyPicker(Status.OK));
      } else {
        updateBalancingState(TRANSIENT_FAILURE, createReadyPicker(getChildLbStates()));
      }
    } else {
      updateBalancingState(READY, createReadyPicker(activeList));
    }
  }

  private void updateBalancingState(ConnectivityState state, RoundRobinPicker picker) {
    if (state != currentConnectivityState || !picker.isEquivalentTo(currentPicker)) {
      getHelper().updateBalancingState(state, picker);
      currentConnectivityState = state;
      currentPicker = picker;
    }
  }

  protected RoundRobinPicker createReadyPicker(Collection<ChildLbState> children) {
    // initialize the Picker to a random start index to ensure that a high frequency of Picker
    // churn does not skew subchannel selection.
    int startIndex = random.nextInt(children.size());

    List<SubchannelPicker> pickerList = new ArrayList<>();
    for (ChildLbState child : children) {
      SubchannelPicker picker = child.getCurrentPicker();
      pickerList.add(picker);
    }

    return new ReadyPicker(pickerList, startIndex);
  }

  public abstract static class RoundRobinPicker extends SubchannelPicker {
    public abstract boolean isEquivalentTo(RoundRobinPicker picker);
  }

  @VisibleForTesting
  static class ReadyPicker extends RoundRobinPicker {
    private static final AtomicIntegerFieldUpdater<ReadyPicker> indexUpdater =
        AtomicIntegerFieldUpdater.newUpdater(ReadyPicker.class, "index");

    private final List<SubchannelPicker> subchannelPickers; // non-empty
    @SuppressWarnings("unused")
    private volatile int index;

    public ReadyPicker(List<SubchannelPicker> list, int startIndex) {
      checkArgument(!list.isEmpty(), "empty list");
      this.subchannelPickers = list;
      this.index = startIndex - 1;
    }

    @Override
    public PickResult pickSubchannel(PickSubchannelArgs args) {
      return subchannelPickers.get(nextIndex()).pickSubchannel(args);
    }

    @Override
    public String toString() {
      return MoreObjects.toStringHelper(ReadyPicker.class)
          .add("subchannelPickers", subchannelPickers)
          .toString();
    }

    private int nextIndex() {
      int size = subchannelPickers.size();
      int i = indexUpdater.incrementAndGet(this);
      if (i >= size) {
        int oldi = i;
        i %= size;
        indexUpdater.compareAndSet(this, oldi, i);
      }
      return i;
    }

    @VisibleForTesting
    List<SubchannelPicker> getSubchannelPickers() {
      return subchannelPickers;
    }

    @Override
    public boolean isEquivalentTo(RoundRobinPicker picker) {
      if (!(picker instanceof ReadyPicker)) {
        return false;
      }
      ReadyPicker other = (ReadyPicker) picker;
      // the lists cannot contain duplicate subchannels
      return other == this
          || (subchannelPickers.size() == other.subchannelPickers.size() && new HashSet<>(
          subchannelPickers).containsAll(other.subchannelPickers));
    }
  }

  @VisibleForTesting
  static final class EmptyPicker extends RoundRobinPicker {

    private final Status status;

    EmptyPicker(@Nonnull Status status) {
      this.status = Preconditions.checkNotNull(status, "status");
    }

    @Override
    public PickResult pickSubchannel(PickSubchannelArgs args) {
      return status.isOk() ? PickResult.withNoResult() : PickResult.withError(status);
    }

    @Override
    public boolean isEquivalentTo(RoundRobinPicker picker) {
      return picker instanceof EmptyPicker && (Objects.equal(status, ((EmptyPicker) picker).status)
          || (status.isOk() && ((EmptyPicker) picker).status.isOk()));
    }

    @Override
    public String toString() {
      return MoreObjects.toStringHelper(EmptyPicker.class).add("status", status).toString();
    }
  }

  /**
   * A lighter weight Reference than AtomicReference.
   */
  @VisibleForTesting
  static final class Ref<T> {
    T value;

    Ref(T value) {
      this.value = value;
    }
  }
}

1	/*
2	* Copyright 2016 The gRPC Authors
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16
17	package io.grpc.util;
18
19	import static com.google.common.base.Preconditions.checkArgument;
20	import static io.grpc.ConnectivityState.CONNECTING;
21	import static io.grpc.ConnectivityState.IDLE;
22	import static io.grpc.ConnectivityState.READY;
23	import static io.grpc.ConnectivityState.TRANSIENT_FAILURE;
24
25	import com.google.common.annotations.VisibleForTesting;
26	import com.google.common.base.MoreObjects;
27	import com.google.common.base.Objects;
28	import com.google.common.base.Preconditions;
29	import io.grpc.ConnectivityState;
30	import io.grpc.EquivalentAddressGroup;
31	import io.grpc.Internal;
32	import io.grpc.LoadBalancer;
33	import io.grpc.NameResolver;
34	import io.grpc.Status;
35	import java.util.ArrayList;
36	import java.util.Collection;
37	import java.util.HashSet;
38	import java.util.List;
39	import java.util.Map;
40	import java.util.Random;
41	import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
42	import javax.annotation.Nonnull;
43
44	/**
45	* A {@link LoadBalancer} that provides round-robin load-balancing over the {@link
46	* EquivalentAddressGroup}s from the {@link NameResolver}.
47	*/
48	@Internal
49	public class RoundRobinLoadBalancer extends MultiChildLoadBalancer {
50	private final Random random;
51	protected RoundRobinPicker currentPicker = new EmptyPicker(EMPTY_OK);	1✔
52
53	public RoundRobinLoadBalancer(Helper helper) {
54	super(helper);	1✔
55	this.random = new Random();	1✔
56	}	1✔
57
58	@Override
59	protected SubchannelPicker getSubchannelPicker(Map<Object, SubchannelPicker> childPickers) {
60	throw new UnsupportedOperationException(); // local updateOverallBalancingState doesn't use this	×
61	}
62
63	private static final Status EMPTY_OK = Status.OK.withDescription("no subchannels ready");	1✔
64
65	/**
66	* Updates picker with the list of active subchannels (state == READY).
67	*/
68	@Override
69	protected void updateOverallBalancingState() {
70	List<ChildLbState> activeList = getReadyChildren();	1✔
71	if (activeList.isEmpty()) {	1✔
72	// No READY subchannels
73
74	// RRLB will request connection immediately on subchannel IDLE.
75	boolean isConnecting = false;	1✔
76	for (ChildLbState childLbState : getChildLbStates()) {	1✔
77	ConnectivityState state = childLbState.getCurrentState();	1✔
78	if (state == CONNECTING \|\| state == IDLE) {	1✔
79	isConnecting = true;	1✔
80	break;	1✔
81	}
82	}	1✔
83
84	if (isConnecting) {	1✔
85	updateBalancingState(CONNECTING, new EmptyPicker(Status.OK));	1✔
86	} else {
87	updateBalancingState(TRANSIENT_FAILURE, createReadyPicker(getChildLbStates()));	1✔
88	}
89	} else {	1✔
90	updateBalancingState(READY, createReadyPicker(activeList));	1✔
91	}
92	}	1✔
93
94	private void updateBalancingState(ConnectivityState state, RoundRobinPicker picker) {
95	if (state != currentConnectivityState \|\| !picker.isEquivalentTo(currentPicker)) {	1✔
96	getHelper().updateBalancingState(state, picker);	1✔
97	currentConnectivityState = state;	1✔
98	currentPicker = picker;	1✔
99	}
100	}	1✔
101
102	protected RoundRobinPicker createReadyPicker(Collection<ChildLbState> children) {
103	// initialize the Picker to a random start index to ensure that a high frequency of Picker
104	// churn does not skew subchannel selection.
105	int startIndex = random.nextInt(children.size());	1✔
106
107	List<SubchannelPicker> pickerList = new ArrayList<>();	1✔
108	for (ChildLbState child : children) {	1✔
109	SubchannelPicker picker = child.getCurrentPicker();	1✔
110	pickerList.add(picker);	1✔
111	}	1✔
112
113	return new ReadyPicker(pickerList, startIndex);	1✔
114	}
115
116	public abstract static class RoundRobinPicker extends SubchannelPicker {	1✔
117	public abstract boolean isEquivalentTo(RoundRobinPicker picker);
118	}
119
120	@VisibleForTesting
121	static class ReadyPicker extends RoundRobinPicker {
122	private static final AtomicIntegerFieldUpdater<ReadyPicker> indexUpdater =	1✔
123	AtomicIntegerFieldUpdater.newUpdater(ReadyPicker.class, "index");	1✔
124
125	private final List<SubchannelPicker> subchannelPickers; // non-empty
126	@SuppressWarnings("unused")
127	private volatile int index;
128
129	public ReadyPicker(List<SubchannelPicker> list, int startIndex) {	1✔
130	checkArgument(!list.isEmpty(), "empty list");	1✔
131	this.subchannelPickers = list;	1✔
132	this.index = startIndex - 1;	1✔
133	}	1✔
134
135	@Override
136	public PickResult pickSubchannel(PickSubchannelArgs args) {
137	return subchannelPickers.get(nextIndex()).pickSubchannel(args);	1✔
138	}
139
140	@Override
141	public String toString() {
142	return MoreObjects.toStringHelper(ReadyPicker.class)	×
143	.add("subchannelPickers", subchannelPickers)	×
144	.toString();	×
145	}
146
147	private int nextIndex() {
148	int size = subchannelPickers.size();	1✔
149	int i = indexUpdater.incrementAndGet(this);	1✔
150	if (i >= size) {	1✔
151	int oldi = i;	1✔
152	i %= size;	1✔
153	indexUpdater.compareAndSet(this, oldi, i);	1✔
154	}
155	return i;	1✔
156	}
157
158	@VisibleForTesting
159	List<SubchannelPicker> getSubchannelPickers() {
160	return subchannelPickers;	1✔
161	}
162
163	@Override
164	public boolean isEquivalentTo(RoundRobinPicker picker) {
165	if (!(picker instanceof ReadyPicker)) {	1✔
166	return false;	1✔
167	}
168	ReadyPicker other = (ReadyPicker) picker;	1✔
169	// the lists cannot contain duplicate subchannels
170	return other == this	1✔
171	\|\| (subchannelPickers.size() == other.subchannelPickers.size() && new HashSet<>(	1✔
172	subchannelPickers).containsAll(other.subchannelPickers));	1✔
173	}
174	}
175
176	@VisibleForTesting
177	static final class EmptyPicker extends RoundRobinPicker {
178
179	private final Status status;
180
181	EmptyPicker(@Nonnull Status status) {	1✔
182	this.status = Preconditions.checkNotNull(status, "status");	1✔
183	}	1✔
184
185	@Override
186	public PickResult pickSubchannel(PickSubchannelArgs args) {
187	return status.isOk() ? PickResult.withNoResult() : PickResult.withError(status);	1✔
188	}
189
190	@Override
191	public boolean isEquivalentTo(RoundRobinPicker picker) {
192	return picker instanceof EmptyPicker && (Objects.equal(status, ((EmptyPicker) picker).status)	1✔
193	\|\| (status.isOk() && ((EmptyPicker) picker).status.isOk()));	1✔
194	}
195
196	@Override
197	public String toString() {
198	return MoreObjects.toStringHelper(EmptyPicker.class).add("status", status).toString();	×
199	}
200	}
201
202	/**
203	* A lighter weight Reference than AtomicReference.
204	*/
205	@VisibleForTesting
206	static final class Ref<T> {
207	T value;
208
209	Ref(T value) {	×
210	this.value = value;	×
211	}	×
212	}
213	}

grpc / grpc-java / #18890

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous