一致性哈希
https://segmentfault.com/a/1190000021199728
https://blog.csdn.net/suifeng629/article/details/81567777
一、传统哈希的问题
1. 节点减少的场景
在分布式多节点系统中，出现故障很常见。任何节点都可能在没有任何事先通知的情况下挂掉。
传统的哈希，当节点减少会导致键与节点的映射关系发生变化，这个变化对新的键来说并不会产生任何影响，但对于已有的键，将导致节点映射错误
2. 节点增加的场景
在分布式多节点系统中，需要对服务节点进行扩容，以应对突发流量。同样的，传统哈希，当节点增加会导致已有的键，映射节点错误。
3. 问题
对于分布式缓存这种系统而言，映射规则失效就意味着之前缓存的失效，若同一时刻出现大量的缓存失效，则可能出现“缓存雪崩”，这将导致灾难性的后果。
二、一致性哈希算法
在移除或者添加一个服务器时，能够尽可能小的改变已存在的服务请求与处理请求服务器之间的映射关系。
优点：
可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销
更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。
虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。
一致性哈希算法与哈希算法的关系：一致性哈希算法是在哈希算法基础上提出的，在动态变化的分布式环境中，哈希算法应该满足的几个条件：平衡性、单调性和分散性
- 平衡性：是指 hash 的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
- 单调性：是指在新增或者删减节点时，不影响系统正常运行。
- 分散性：是指数据应该分散地存放在分布式集群中的各个节点（节点自己可以有备份），不必每个节点都存储所有的数据
1. 原理
一致性哈希算法通过一致性哈希环的数据结构来实现。这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，因此这个环的整数分布范围是 [ 0, 2^32-1 ]。
假设我们有几个对象，通过求哈希值后放入哈希环上，然后给我们的物理服务器虚拟出一组虚拟服务器，将这些虚拟服务器通过求哈希值放到哈希环上，如果需要确定对象的服务器，则先确定对象的虚拟服务器，再由虚拟服务器确定物理服务器。
如何确定呢？确认对象的物理服务器，在哈希环上按照顺时针方向找到虚拟服务器，通过虚拟服务器找到物理服务器。
这样，在新增服务器后，只有少部分对象需要重新分配。服务器减少后，也只有少部分机器需要分配。解决了大量节点需要重分配的问题。
2. 代码实现
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
public class ConsistentHashingWithoutVirtualNode {
private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"};
private static List<String> realNodes = new LinkedList<String>();
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
private static final int VIRTUAL_NODES = 5;
static{
for(int i=0; i<servers.length; i++)
realNodes.add(servers[i]);
for (String str : realNodes){
for(int i=0; i<VIRTUAL_NODES; i++){
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = getHash(virtualNodeName);
System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
private static int getHash(String str){
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
private static String getServer(String key){
int hash = getHash(key);
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if(subMap.isEmpty()){
Integer i = virtualNodes.firstKey();
virtualNode = virtualNodes.get(i);
}else{
Integer i = subMap.firstKey();
virtualNode = subMap.get(i);
}
if(StringUtils.isNotBlank(virtualNode)){
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
return null;
}
public static void main(String[] args){
String[] keys = {"太阳", "月亮", "星星"};
for(int i=0; i<keys.length; i++)
System.out.println("[" + keys[i] + "]的hash值为" +
getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");
}
}
|