com.baidu.brpc.loadbalance

Class FairStrategy

java.lang.Object

com.baidu.brpc.loadbalance.FairStrategy

All Implemented Interfaces:

LoadBalanceStrategy

public class FairStrategy
extends Object
implements LoadBalanceStrategy

Fair load balance strategy aims to more reasonable distribution of traffic. The principle of traffic distribution is not the same as pv, but the distribution of traffic according to performance, the performance of the machine with multi-point traffic, the poor performance of the machine with less point traffic, the same machine traffic with the same performance, and finally the service performance of all nodes tends to balance, there will be no slow nodes to improve the overall performance of the service.

Algorithm overview: The fair load balancing policy dynamically adjusts the weight of each server and divides it by weight. Rpc client maintains a latency window record rpc time for each server, after processing a traffic, the server updates its own window. If the mean value of the service in the window > the overall mean of the service, reduce its own weight. On the contrary, increase its own weight. When the window is not full, the polling does not adjust the weight.

Since:

2018-09-03

Author:

wangjiayin

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FairStrategy.Node The weight tree node

Field Summary

Fields

Modifier and Type	Field and Description
protected CopyOnWriteArrayList<FairStrategy.Node>	treeContainer The binary tree used to save weight number for each node.

Fields inherited from interface com.baidu.brpc.loadbalance.LoadBalanceStrategy

LOAD_BALANCE_FAIR, LOAD_BALANCE_RANDOM, LOAD_BALANCE_ROUND_ROBIN, LOAD_BALANCE_WEIGHT

Constructor Summary

Constructors

Constructor and Description
FairStrategy()

Method Summary

Modifier and Type	Method and Description
protected int	calculateWeight(CommunicationClient instance, int timeout) Calculate the weight of a rpc server
void	destroy()
protected CommunicationClient	fairSelect(FairStrategy.Node root)
protected FairStrategy.Node	generateWeightTreeByLeafNodes(Queue<FairStrategy.Node> leafNodes) generate the tree by leaf nodes the leaf nodes are the real rpc servers the parent nodes used to calculate the sum of it's children's weight
protected long	getRandomLong()
void	init(RpcClient rpcClient)
void	markInvalidInstance(List<CommunicationClient> instances) Since the weight tree will update by a period of time, so if there's any invalid instance, the business should notify the fair strategy.
protected FairStrategy.Node	searchNode(FairStrategy.Node parent, int weight)
CommunicationClient	selectInstance(Request request, List<CommunicationClient> instances, Set<CommunicationClient> selectedInstances) select instance channel from total instances
protected void	updateWeightTree() Update weight of each node of the tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

treeContainer

protected CopyOnWriteArrayList<FairStrategy.Node> treeContainer

The binary tree used to save weight number for each node. We use a CopyOnWriteArrayList to safely lockless update the weight tree, The first element fo the CopyOnWriteArrayList is useful. The leaf elements of the weight tree are the real rpc servers, and the parent elements of the weight used to save the sum weight of its left and right child's weight. The root element's weight sum is the total sum of every leaf element's weight.

The weight tree can achieve time complexity at the O(logN) level, and 1000 servers require only 11 memory accesses.

Constructor Detail

FairStrategy

public FairStrategy()

Method Detail

init

public void init(RpcClient rpcClient)

Specified by:

init in interface LoadBalanceStrategy

selectInstance

public CommunicationClient selectInstance(Request request,
                                          List<CommunicationClient> instances,
                                          Set<CommunicationClient> selectedInstances)

Description copied from interface: LoadBalanceStrategy

select instance channel from total instances

Specified by:

selectInstance in interface LoadBalanceStrategy

Parameters:

request - request info

instances - total instances, often are all healthy instances

selectedInstances - instances which have been selected.

Returns:

the best instance channel

destroy

public void destroy()

Specified by:

destroy in interface LoadBalanceStrategy

markInvalidInstance

public void markInvalidInstance(List<CommunicationClient> instances)

Since the weight tree will update by a period of time, so if there's any invalid instance, the business should notify the fair strategy.

getRandomLong

protected long getRandomLong()

fairSelect

protected CommunicationClient fairSelect(FairStrategy.Node root)

searchNode

protected FairStrategy.Node searchNode(FairStrategy.Node parent,
                                       int weight)

updateWeightTree

protected void updateWeightTree()

Update weight of each node of the tree. By create a new tree and insert into the head of the treeContainer

calculateWeight

protected int calculateWeight(CommunicationClient instance,
                              int timeout)

Calculate the weight of a rpc server

Parameters:

instance - The instance of a rpc server

timeout - Read timeout in millis

Returns:

Weight num

generateWeightTreeByLeafNodes

protected FairStrategy.Node generateWeightTreeByLeafNodes(Queue<FairStrategy.Node> leafNodes)

generate the tree by leaf nodes the leaf nodes are the real rpc servers the parent nodes used to calculate the sum of it's children's weight

Parameters:

leafNodes - leaf nodes list

Returns:

the root node of the tree