前言
现在有一个场景：一个客户端去访问服务端，只能一直访问一台机器，因为有一些用户数据就存在该服务器上面，如果访问其他服务器的话，这个用户数据就丢了，如何用算法来解决这个问题？
一致性哈希环算法
base
这里的环结构是我们想象的、抽象出来的，最朴素的想法，就是给一个请求，用哈希函数等操作去计算出它对应到的服务器位置，然后分配即可。
客户端如何映射到哈希环上的节点呢?
比如有一个userId =1去请求：
计算了哈希值后落在了P1与P4之间，哈希环处理规则就是找到比它大的最近的那个节点，这里的哈希环是一个有序环，依次递增：P1< P2< P3< P4，那么比userId =1大的最近的就是P1，那么就会分配给P1这个服务器。
在Java中有哪个数据结构是可以满足这个需求的呢？完成自动排序（比如一个数字进到集合中后，该结构能够将新来的和之前的集合元素进行排序，这里采用的是TreeMap）
变种：穿插虚拟节点分担请求压力
思考一个问题：如果在某个高峰时间，所有的请求都打到了P1-P4这个区域，那么将会全部击中P1这台服务器，P1承受很大流量，可能导致宕机，同时其他服务器可能比较空闲，这样并不合理，我们可以采用很多的虚拟节点，就可以在原有基础之上，中间穿插许多的虚拟节点，类似孙悟空拔了一根汗毛做分身，这样就可以把刚刚那一大堆流量给分散到不同服务器上，使得压力分散的很均匀、散列：
一致性哈希环的数据结构实现：TreeMap
TreeMap的底层采用的是红黑树，
这里的红黑树会对插入的数据完成自动排序，在TreeMap的api中有一个tailMap() 函数，输入一个fromKey，输出的是一个SortedMap有序Map：
1
2
| SortedMap<Integer,String> subMap = virtualNodes.tailMap(2);
Integer nodeIndex = subMap.firstKey();
|
能够得到2、3、4、5这几个索引的数据，String是它对应的value。
简单来说：能够通过tailMap() 找到2右边的子树（也就是大于等于2的子树），再用firstKey()拿到比他大的第一个元素。
这样就对应到了我们的一致性哈希环，可以拿到它最近的比他大的服务器节点
考虑边界：如果请求计算出比P4还要大，那么就直接返回P1即可（环状）
代码
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
public class ConsistentHash {
private static TreeMap<Integer,String> virtualNodes = new TreeMap();
private static final int VIRTUAL_NODES = 160;
static {
for(String ip: ServerIps.LIST) {
for(int i = 0; i < VIRTUAL_NODES; i++) {
int hash = getHash(ip+"VN"+i);
virtualNodes.put(hash,ip);
}
}
}
public static String getServer(String clientInfo) {
int hash = getHash(clientInfo);
SortedMap<Integer,String> subMap = virtualNodes.tailMap(hash);
Integer nodeIndex = subMap.firstKey();
if (nodeIndex == null) {
nodeIndex = virtualNodes.firstKey();
}
return virtualNodes.get(nodeIndex);
}
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;
}
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
System.out.println(getServer("userId" + i));
}
}
}
public class ConsistentHash {
private static TreeMap<Integer,String> virtualNodes = new TreeMap();
private static final int VIRTUAL_NODES = 160;
static {
for(String ip: ServerIps.LIST) {
for(int i = 0; i < VIRTUAL_NODES; i++) {
int hash = getHash(ip+"VN"+i);
virtualNodes.put(hash,ip);
}
}
}
public static String getServer(String clientInfo) {
int hash = getHash(clientInfo);
SortedMap<Integer,String> subMap = virtualNodes.tailMap(hash);
Integer nodeIndex = subMap.firstKey();
if (nodeIndex == null) {
nodeIndex = virtualNodes.firstKey();
}
return virtualNodes.get(nodeIndex);
}
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;
}
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
System.out.println(getServer("userId" + i));
}
}
}
|
可以看出运行结果是相对比较散列的，对于服务器来说压力就比较小了。
这里还要测试保证一下：对于同一个userId，每次去请求，都会到达同一个服务器上，这样才合理（每次运行，结果都一致即可）。
