[shenyu] branch master updated: Optimize random algorithm. (#3911)

[xiaoyu]

This is an automated email from the ASF dual-hosted git repository.

xiaoyu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/shenyu.git


The following commit(s) were added to refs/heads/master by this push:
     new 461a99076 Optimize random algorithm. (#3911)
461a99076 is described below

commit 461a99076768296685dacb6b5bbe89dae7f62562
Author: DamonXue(Fibonacci) <damonx...@gmail.com>
AuthorDate: Sun Sep 4 11:27:11 2022 +0800

    Optimize random algorithm. (#3911)
    
    * optimize random algorithm.
    
    * optimize random algorithm + 1.
---
 .../loadbalancer/spi/RandomLoadBalancer.java       | 27 +++++++++++++++-------
 1 file changed, 19 insertions(+), 8 deletions(-)

diff --git 
a/shenyu-loadbalancer/src/main/java/org/apache/shenyu/loadbalancer/spi/RandomLoadBalancer.java
 
b/shenyu-loadbalancer/src/main/java/org/apache/shenyu/loadbalancer/spi/RandomLoadBalancer.java
index ca1f2547a..eabb89994 100644
--- 
a/shenyu-loadbalancer/src/main/java/org/apache/shenyu/loadbalancer/spi/RandomLoadBalancer.java
+++ 
b/shenyu-loadbalancer/src/main/java/org/apache/shenyu/loadbalancer/spi/RandomLoadBalancer.java
@@ -17,11 +17,10 @@
 
 package org.apache.shenyu.loadbalancer.spi;
 
-import org.apache.shenyu.loadbalancer.entity.Upstream;
-import org.apache.shenyu.spi.Join;
-
 import java.security.SecureRandom;
 import java.util.List;
+import org.apache.shenyu.loadbalancer.entity.Upstream;
+import org.apache.shenyu.spi.Join;
 
 /**
  * random algorithm impl.
@@ -42,8 +41,12 @@ public class RandomLoadBalancer extends AbstractLoadBalancer 
{
         weights[0] = firstUpstreamWeight;
         // init the totalWeight
         int totalWeight = firstUpstreamWeight;
+        int halfLengthTotalWeight = 0;
         for (int i = 1; i < length; i++) {
             int currentUpstreamWeight = getWeight(upstreamList.get(i));
+            if (i <= (length + 1) / 2) {
+                halfLengthTotalWeight = totalWeight;
+            }
             weights[i] = currentUpstreamWeight;
             totalWeight += currentUpstreamWeight;
             if (sameWeight && currentUpstreamWeight != firstUpstreamWeight) {
@@ -52,19 +55,27 @@ public class RandomLoadBalancer extends 
AbstractLoadBalancer {
             }
         }
         if (totalWeight > 0 && !sameWeight) {
-            return random(totalWeight, weights, upstreamList);
+            return random(totalWeight, halfLengthTotalWeight, weights, 
upstreamList);
         }
         return random(upstreamList);
     }
 
-    private Upstream random(final int totalWeight, final int[] weights, final 
List<Upstream> upstreamList) {
+    private Upstream random(final int totalWeight, final int 
halfLengthTotalWeight, final int[] weights, final List<Upstream> upstreamList) {
         // If the weights are not the same and the weights are greater than 0, 
then random by the total number of weights.
         int offset = RANDOM.nextInt(totalWeight);
+        int index = 0;
+        int end = weights.length;
+        if (offset >= halfLengthTotalWeight) {
+            index = (weights.length + 1) / 2;
+            offset -= halfLengthTotalWeight;
+        } else {
+            end = (weights.length + 1) / 2;
+        }
         // Determine which segment the random value falls on
-        for (int i = 0; i < weights.length; i++) {
-            offset -= weights[i];
+        for (; index < end; index++) {
+            offset -= weights[index];
             if (offset < 0) {
-                return upstreamList.get(i);
+                return upstreamList.get(index);
             }
         }
         return random(upstreamList);