Question:

Due to the different configurations of the machines, different traffic ratios need to be configured for different machines, and polling access is also required to avoid single point overheating

So a simple polling algorithm (1, 2, 3, 1, 2, 3, 1, 2, 2, 3, 2, 3) is not going to work.

Suppose there are three machines with 1, 2 and 4 cores respectively, corresponding to A, B and C, respectively corresponding to the weight of 1:2:4.

When machine A calls it once, machine B calls it twice, and machine C calls it four times, it is polling once. And can not be a single point of continuous access.

Implementation:

import lombok.AllArgsConstructor; import lombok.Getter; import lombok.NoArgsConstructor; import lombok.Setter; /** * @author chenwenxin * @since 2020-03-26 16:50 */ @Getter @Setter @NoArgsConstructor @AllArgsConstructor public class ServerNode { private String hostname; /** set weight */ private int weight; /** currentWeight */ private int currentWeight; public void selected(int total) { currentWeight -= total; } public void increaseCurrentWeight() { currentWeight += weight; } } import org.chenwenxin.algorithm.loadbalance.LoadBalance; import org.chenwenxin.algorithm.loadbalance.ServerNode; import java.util.ArrayList; import java.util.List; / * * * * load balancing - weighted polling algorithm @ author chenwenxin * @ since the 2020-03-26 hast judged * / public class WeightRoundRobinLoadBalance implements LoadBalance { @Override public ServerNode select(List<ServerNode> serverNodes) { ServerNode serverNodeSelected = null; int maxWeight = Integer.MIN_VALUE; int totalWeight = 0; For (ServerNode ServerNode: serverNodes) {/ / increase their respective currentWeight ServerNode. IncreaseCurrentWeight (); if (serverNode.getCurrentWeight() > maxWeight) { maxWeight = serverNode.getCurrentWeight(); serverNodeSelected = serverNode; } totalWeight += serverNode.getWeight(); } if (serverNodeSelected ! = null) {/ / the selected node, currentWeight need to minus the sum of all the weight serverNodeSelected. Selected (totalWeight); return serverNodeSelected; } // should not happen here return serverNodes.get(0); } / / test public static void main (String [] args) {WeightRoundRobinLoadBalance lb = new WeightRoundRobinLoadBalance (); List<ServerNode> servers = new ArrayList<>(); Add (new ServerNode("a", 1, 0)); servers.add(new ServerNode("b", 2, 0)); servers.add(new ServerNode("c", 4, 0)); for (int i = 0; i < 15; I++) {if (I % 7 = = 0) {System. Out. Println (the String. Format (" \ n the first % s round request = = = = = = : ", (I / 7) + 1)); } ServerNode selected = lb.select(servers); Println (string. format(" select machine: %s", I + 1, selection.gethostName ())); }}}Copy the code

Proof:

The whole algorithm can be simplified into two steps

  1. Each execution adds the current weight to the weight set by the node

  2. Select the node with the maximum weight and subtract the total weight.

So we only have to prove two things

  1. The number of executions per round is weighted, that is, executed proportionally.

  2. The next node after each execution is different from the last one, that is, smooth.

Proof weighting:

Assumptions:

  • There are n nodes

  • The ith node has a weight of Xi

  • The total weight is S, S=X1+X2+X3···+Xn

Proof:

Because: initial weight is [0, 0, 0···, 0]

Then: the weight after the first step is [X1, X2, X3···, Xn]

If: The JTH node has the largest weight

Then: the current weight is [X1, X2, Xj-S···, Xn]

Then: the current sum of weights is X1+X2+X3···+ xn-s = 0

Suppose: Node I is selected Mi times, and the current weight of node I is Wi

Let: node j has been selected Xj before t(t<S)

Then: the current weight of node J is Wj=t* xj-xj *S=Xj(t-s)

Because: t – S < 0

Is: Wj < 0

Since: S>0, when t<S, Wj, there must be a node weight >0, so node J can select Wj times at most.

Suppose: node J executes Xj-1 times when t(t<S)

Then: Wj=t*Xj-(Xj-1)*S = (t-s)Xj+S

Because: Xj < S

Then: there must be a time for Wj>0

To sum up: node J can only be executed Xj times in S times of execution

Therefore, it can be proved that the selection times of nodes are carried out according to the weighted value

Prove smoothness:

To prove smoothness, just show that the node is not always selected.

Assumptions:

  • The total weight is S

  • The current number of executions is t(S>t)

  • The node j can be selected continuously

  • It’s currently selected t times

  • t=Xj-1

Proof:

It can be obtained from above:

Wj=(Xj-1)*Xj-(Xj-1)S

=Xj*Xj-Xj-Xj*S+S

Then: After the first step is executed in the next execution

Wj=Xj*Xj-Xj*S+S

=(Xj-1)(Xj-S)+Xj

Therefore, we only need to prove that the weight of other nodes is greater than the current node

Because: Xj -s < 1

Then, Wj<1 after amplification

Therefore, there must be another node Wi=t*Xi>1

Therefore, it is proved that nodes are not selected continuously