如何写一个RPC框架（六）：负载均衡

在后续一段时间里， 我会写一系列文章来讲述如何实现一个RPC框架（我已经实现了一个示例框架， 代码在我的github上）。 这是系列第六篇文章， 主要讲述了RPC中负载均衡这一块的内容。

常见的LB策略

常见的LB策略有很多：

1. RoundRobin (RR)： 一个列表中轮着来
2. WeightedRoundRobin (WRR)： 带权重的RR
3. LocalFirst：本地服务优先
4. Random：随机选择
5. ConsistentHash： 一致性哈希

这些策略中，除了最后一个，别的都很好理解。 下面主要来说一下一致性哈希负载均衡的原理和实现吧。

一致性哈希负载均衡

一致性哈希算法

首先，我们需要去了解什么是一致性哈希算法。网上有很多关于一致性哈希的文章， 在这里我推荐一篇写的比较细致且容易理解的：一致性哈希算法

为什么要用一致性哈希来做负载均衡

假设我们根据userid来做hash，在服务器数量发生变动时，只有少数用户的请求会发送到新的机器上， 这样可以最大程度的利用服务器的本地缓存。

简单实现

一致性哈希算法在我看来只有两个注意点：

1. 如何找到某一个hash值在环中的下一个节点
2. 如何实现虚拟节点的replica

这两个问题比较好解决：

1. 对于第一个问题， 可以利用treemap来实现
2. 对于第二个问题， 我们只需要对某一个物理节点的key做多次的【修改key，再hash，再存入treemap中】即可

对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
1public interface HashFunction<T> {

2    int hash(T t);

3}

4

5public class ConsistentHash<T> {

6

7    private final HashFunction hashFunction;

8    private final int numberOfReplicas;

9    private final SortedMap<Integer, T> circle = new TreeMap<>();

10

11    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,

12            Collection<T> nodes) {

13        this.hashFunction = hashFunction;

14        this.numberOfReplicas = numberOfReplicas;

15

16        for (T node : nodes) {

17            add(node);

18        }

19    }

20

21    public void add(T node) {

22        for (int i = 0; i <numberOfReplicas; i++) {

23            circle.put(hashFunction.hash(node.toString() + i), node);

24        }

25    }

26

27    public void remove(T node) {

28        for (int i = 0; i <numberOfReplicas; i++) {

29            circle.remove(hashFunction.hash(node.toString() + i));

30        }

31    }

32

33    public T get(Object key) {

34        if (circle.isEmpty()) {

35            return null;

36        }

37        int hash = hashFunction.hash(key);

38        if (!circle.containsKey(hash)) {

39            SortedMap<Integer, T> tailMap = circle.tailMap(hash);

40            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();

41        }

42        return circle.get(hash);

43    }

44}

45