Skip to content

Commit ee6e275

Browse files
committed
feat(loadbalancer): add the opt-in adaptive scoring strategy for divide (#8300)
1 parent a6104b9 commit ee6e275

7 files changed

Lines changed: 779 additions & 5 deletions

File tree

‎shenyu-common/src/main/java/org/apache/shenyu/common/enums/LoadBalanceEnum.java‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,14 @@ public enum LoadBalanceEnum {
5050
/**
5151
* shortest response load balance enum.
5252
*/
53-
SHORTEST_RESPONSE(6, "shortestResponse", true);
53+
SHORTEST_RESPONSE(6, "shortestResponse", true),
54+
55+
/**
56+
* adaptive scoring load balance enum (#8300): opt-in score-based selection on top
57+
* of the p2c pairing, using per-upstream latency, in-flight work and classified
58+
* outcomes.
59+
*/
60+
ADAPTIVE(7, "adaptive", true);
5461

5562
private final int code;
5663

Lines changed: 197 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,197 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one or more
3+
* contributor license agreements. See the NOTICE file distributed with
4+
* this work for additional information regarding copyright ownership.
5+
* The ASF licenses this file to You under the Apache License, Version 2.0
6+
* (the "License"); you may not use this file except in compliance with
7+
* the License. You may obtain a copy of the License at
8+
*
9+
* http://www.apache.org/licenses/LICENSE-2.0
10+
*
11+
* Unless required by applicable law or agreed to in writing, software
12+
* distributed under the License is distributed on an "AS IS" BASIS,
13+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14+
* See the License for the specific language governing permissions and
15+
* limitations under the License.
16+
*/
17+
18+
package org.apache.shenyu.loadbalancer.spi;
19+
20+
import org.apache.shenyu.common.enums.LoadBalanceEnum;
21+
import org.apache.shenyu.loadbalancer.entity.LoadBalanceData;
22+
import org.apache.shenyu.loadbalancer.entity.Upstream;
23+
import org.apache.shenyu.loadbalancer.entity.UpstreamIdentity;
24+
import org.apache.shenyu.spi.ExtensionLoader;
25+
import org.apache.shenyu.spi.Join;
26+
27+
import java.util.List;
28+
import java.util.Objects;
29+
import java.util.OptionalLong;
30+
import java.util.Random;
31+
32+
/**
33+
* Adaptive scoring load balance impl (#8300).
34+
*
35+
* <p>Selection keeps the p2c pairing (two random candidates compared in O(1), no
36+
* full-list sort) but compares per-upstream adaptive scores instead of the raw
37+
* {@code (sqrt(lag)+1) * inflight} product: a smoothed per-attempt latency (with a
38+
* synthetic floor for failed attempts, so fast failures stay unattractive), the
39+
* in-flight count, and the warm-up adjusted configured weight. While a candidate is
40+
* still cold (fewer than {@value AdaptiveUpstreamStats#MIN_SAMPLES} latency samples)
41+
* the pair is compared with the p2c load formula, so cold start, restarts and
42+
* discovery churn behave exactly like today. Idle nodes keep the p2c forced
43+
* exploration so a slow node is never starved permanently.</p>
44+
*
45+
* <p>The feedback is a single hook: the divide plugin measures each attempt with its
46+
* own start time and calls {@link #feedback(Upstream, long, AdaptiveOutcome)}, so
47+
* overlapping attempts never share a timestamp, and the classified outcome keeps
48+
* client-caused 4xx results neutral. Health, canary partitioning, breaker admission,
49+
* sticky affinity and draining/ready gating all happen before this selector sees the
50+
* candidate list, so the adaptive comparison only ranks already eligible targets.</p>
51+
*/
52+
@Join
53+
public class AdaptiveLoadBalancer extends AbstractLoadBalancer {
54+
55+
/**
56+
* maximum tolerance of idle time, mirroring the p2c exploration.
57+
*/
58+
private static final int FORCE_GAP = 3 * 1000;
59+
60+
/**
61+
* pick times for the healthy-candidate redraw.
62+
*/
63+
private static final int PICK_TIMES = 3;
64+
65+
private final Random random = new Random();
66+
67+
/**
68+
* p2c load formula reused as the cold-start comparison, so the fallback scale is
69+
* the same for both candidates of a pair.
70+
*/
71+
private final P2cLoadBalancer coldStartComparison = new P2cLoadBalancer();
72+
73+
private final AdaptiveUpstreamStats stats = new AdaptiveUpstreamStats();
74+
75+
/**
76+
* The feedback statistics of this selector; visible for tests.
77+
*
78+
* @return the stats registry
79+
*/
80+
AdaptiveUpstreamStats stats() {
81+
return stats;
82+
}
83+
84+
@Override
85+
public Upstream select(final List<Upstream> upstreamList, final LoadBalanceData data) {
86+
Upstream picked = super.select(upstreamList, data);
87+
// AbstractLoadBalancer short-circuits a singleton candidate list before doSelect
88+
// runs, so the in-flight reservation made here pairs the completion decrement in
89+
// the divide plugin (same accounting fix as the p2c selector, #7974).
90+
if (Objects.nonNull(picked) && upstreamList.size() == 1) {
91+
picked.setLastPicked(System.currentTimeMillis());
92+
picked.getInflight().incrementAndGet();
93+
}
94+
return picked;
95+
}
96+
97+
@Override
98+
protected Upstream doSelect(final List<Upstream> upstreamList, final LoadBalanceData data) {
99+
long now = System.currentTimeMillis();
100+
stats.pruneIfNeeded(now);
101+
Upstream[] upstreams = pickTwoUpstreams(upstreamList);
102+
Upstream picked;
103+
Upstream unpicked;
104+
if (compare(upstreams[0], upstreams[1]) > 0) {
105+
picked = upstreams[1];
106+
unpicked = upstreams[0];
107+
} else {
108+
picked = upstreams[0];
109+
unpicked = upstreams[1];
110+
}
111+
// If the loser is not selected once in the forceGap period, it is forced to be
112+
// selected once, mirroring the p2c exploration.
113+
if ((now - unpicked.getLastPicked()) > FORCE_GAP) {
114+
unpicked.setLastPicked(now);
115+
picked = unpicked;
116+
}
117+
118+
if (picked != unpicked) {
119+
picked.setLastPicked(now);
120+
}
121+
picked.getInflight().incrementAndGet();
122+
return picked;
123+
}
124+
125+
/**
126+
* Compare two candidates: adaptive scores when both are warm, the p2c load formula
127+
* for a cold pair (the scales must never be mixed inside one comparison).
128+
*
129+
* @param first the first candidate
130+
* @param second the second candidate
131+
* @return negative/zero/positive following the first candidate's advantage
132+
*/
133+
private long compare(final Upstream first, final Upstream second) {
134+
if (stats.bothAdaptive(first.identity(), second.identity())) {
135+
return Long.compare(score(first), score(second));
136+
}
137+
return Long.compare(coldStartComparison.load(first), coldStartComparison.load(second));
138+
}
139+
140+
private long score(final Upstream upstream) {
141+
OptionalLong adaptive = stats.score(upstream.identity(), upstream.getInflight().get(), getWeight(upstream));
142+
// bothAdaptive already guaranteed warm statistics; the fallback keeps the
143+
// comparison total if a concurrent prune removed the entry between the checks
144+
return adaptive.orElseGet(() -> coldStartComparison.load(upstream));
145+
}
146+
147+
/**
148+
* Feed back one classified attempt. Called by the divide plugin's completion
149+
* trigger with the attempt's own start time, so the measurement is per attempt.
150+
* Resolves the registered adaptive selector, so the feedback always lands on the
151+
* same instance that performs the selections.
152+
*
153+
* @param upstream the upstream that served the attempt
154+
* @param elapsedMillis the measured attempt latency
155+
* @param outcome the classified outcome
156+
*/
157+
public static void feedback(final Upstream upstream, final long elapsedMillis, final AdaptiveOutcome outcome) {
158+
LoadBalancer join = ExtensionLoader.getExtensionLoader(LoadBalancer.class)
159+
.getJoin(LoadBalanceEnum.ADAPTIVE.getName());
160+
if (join instanceof AdaptiveLoadBalancer) {
161+
((AdaptiveLoadBalancer) join).onFeedback(upstream, elapsedMillis, outcome);
162+
}
163+
}
164+
165+
/**
166+
* Feed back one classified attempt into this instance's statistics.
167+
*
168+
* @param upstream the upstream that served the attempt
169+
* @param elapsedMillis the measured attempt latency
170+
* @param outcome the classified outcome
171+
*/
172+
void onFeedback(final Upstream upstream, final long elapsedMillis, final AdaptiveOutcome outcome) {
173+
if (Objects.isNull(upstream) || Objects.isNull(outcome)) {
174+
return;
175+
}
176+
UpstreamIdentity identity = upstream.identity();
177+
stats.record(identity, elapsedMillis, outcome, System.currentTimeMillis());
178+
}
179+
180+
private Upstream[] pickTwoUpstreams(final List<Upstream> upstreamList) {
181+
Upstream[] upstreams = new Upstream[2];
182+
for (int i = 0; i < PICK_TIMES; i++) {
183+
int a = random.nextInt(upstreamList.size());
184+
int b = random.nextInt(upstreamList.size() - 1);
185+
// prevent random nodes from being the same.
186+
if (b >= a) {
187+
b += 1;
188+
}
189+
upstreams[0] = upstreamList.get(a);
190+
upstreams[1] = upstreamList.get(b);
191+
if (upstreams[0].isHealthy() && upstreams[1].isHealthy()) {
192+
break;
193+
}
194+
}
195+
return upstreams;
196+
}
197+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one or more
3+
* contributor license agreements. See the NOTICE file distributed with
4+
* this work for additional information regarding copyright ownership.
5+
* The ASF licenses this file to You under the Apache License, Version 2.0
6+
* (the "License"); you may not use this file except in compliance with
7+
* the License. You may obtain a copy of the License at
8+
*
9+
* http://www.apache.org/licenses/LICENSE-2.0
10+
*
11+
* Unless required by applicable law or agreed to in writing, software
12+
* distributed under the License is distributed on an "AS IS" BASIS,
13+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14+
* See the License for the specific language governing permissions and
15+
* limitations under the License.
16+
*/
17+
18+
package org.apache.shenyu.loadbalancer.spi;
19+
20+
/**
21+
* Classified outcome of one transport attempt, fed back into the adaptive scoring.
22+
*
23+
* <p>The classes keep upstream failures distinct from client-caused results: a fast
24+
* 5xx penalizes the serving node, while a 4xx (application or authentication
25+
* rejection) is neutral — it must never make a node look better or worse, and a
26+
* downstream cancellation says nothing about the upstream at all.</p>
27+
*/
28+
public enum AdaptiveOutcome {
29+
30+
/**
31+
* The attempt completed with a successful response class.
32+
*/
33+
SUCCESS,
34+
35+
/**
36+
* The upstream answered with a client-error class (4xx): neutral, no latency is
37+
* recorded and no penalty is applied.
38+
*/
39+
CLIENT_ERROR,
40+
41+
/**
42+
* The upstream answered with a server-error class (5xx): the latency is real but
43+
* the fast failure must not look attractive, so a penalty is applied.
44+
*/
45+
SERVER_ERROR,
46+
47+
/**
48+
* The attempt failed on the transport (connection, timeout, cancellation of the
49+
* write): no latency is observable, a penalty is applied.
50+
*/
51+
TRANSPORT_ERROR
52+
}

0 commit comments

Comments
 (0)