0%

一致性哈希算法

在分布式系统中,常常需要使用到缓存,通常缓存一般都是使用集群的方式进行部署,访问缓存的时候一般是对对象的HASH值对集群中机器个个数取余。

比如有三台redis节点,hash值对3取余之后只能是0,1,2三个数通过取余求出来的结果决定到哪台机器上取缓存。

普通的Hash算法

普通的hash算法无法解决redis节点增加和删除的问题。假如增加了一个节点,那么原本对象的hash值则需要对4进行取余,取余结果可能有0,1,2,3。

这个时候,原有的对象的取余则会多个4,但是机器4上却缺少这个对象的缓存。

代码实现:

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
/**
* 单位对象
*/
public class Obj {
public Obj(String name) {
this.name = name;
}

private String name;

@Override
public String toString() {
return "Obj{" +
"name='" + name + '\'' +
'}';
}

@Override
public int hashCode() {
return Math.abs(super.hashCode());
}
}

/**
* 服务器节点,用于存储Obj对象
*/
public class Node {
Map<Integer, Obj> node = new HashMap<>();
public Node(String address) {
this.address = address;
}
/**
* 服务器地址
*/
private String address;
public String getAddress() {
return address;
}
public Obj getObj(Obj obj) {
return node.get(obj.hashCode());
}
public void putObj(Obj obj) {
node.put(obj.hashCode(), obj);
}
/**
* 预防出现负值
*
*/
@Override
public int hashCode() {
return Math.abs(super.hashCode());
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return address.equals(node.address);
}
}


/**
* hash 列表
* 用于存储服务器节点
*/
public class NodeArray {

List<Node> nodes = new ArrayList();
public void addNode(Node node) {
size++;
nodes.add(node);
}
public void removeNode(Node node) {
nodes.remove(node);
}
Obj get(Obj obj) {
int index = obj.hashCode() % nodes.size();
Node node = nodes.get(index);
System.out.print(node.getAddress() + " ");
return node.getObj(obj);
}
void put(Obj obj) {
int index = obj.hashCode() % nodes.size();
nodes.get(index).putObj(obj);
}

}

在正常不增加节点的情况下,执行结果是正常的,都能够寻找到对应的机器

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
    public static void main(String[] args) {
NodeArray nodeArray = new NodeArray();
// 所有节点
Node[] nodes = { new Node("192.168.0.1"),new Node("192.168.0.2"),new Node("192.168.0.3")};
for (Node node : nodes) {
nodeArray.addNode(node);
}
// 所有对象
Obj[] objs = {new Obj("1"),new Obj("2"),new Obj("3"), new Obj("4"),new Obj("5")};
for (Obj obj : objs) {
nodeArray.put(obj);
}
for (Obj obj : objs) {
System.out.println(nodeArray.get(obj));
}

// 强行增加节点
nodeArray.addNode(new Node("192.168.1.4"));
System.out.println("========== after =============");
for (Obj obj : objs) {
System.out.println(nodeArray.get(obj));
}

// 强行删除节点
nodeArray.addNode(new Node("192.168.1.4"));
System.out.println("========== after =============");
for (Obj obj : objs) {
System.out.println(nodeArray.get(obj));
}

}

执行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
192.168.0.1   Obj{name='1'}
192.168.0.3 Obj{name='2'}
192.168.0.2 Obj{name='3'}
192.168.0.2 Obj{name='4'}
192.168.0.2 Obj{name='5'}
========== after =============
192.168.1.4 null
192.168.0.1 null
192.168.0.3 null
192.168.0.3 null
192.168.0.3 null
========== after =============
192.168.0.1 Obj{name='1'}
192.168.0.3 Obj{name='2'}
192.168.0.2 Obj{name='3'}
192.168.0.2 Obj{name='4'}
192.168.0.2 Obj{name='5'}

从结果中可以看到,数据初始化完毕之后,第一次加载数据正常,新增一个节点之后就到别的机器上寻找缓存,删除新增的节点之后又恢复正常。

一致性Hash算法

一致性Hash算法在普通的Hash算法基础之上,修改了取余的方式。

由于机器会变化,索性就不对机器数取余,找个中立的值2的32次方。

将我们的缓存节点通过Hash的方式取余之后分布在炒鸡大的一个手动构造的圆环中。每个缓存数据根据自己的值到Hash环上顺时针寻找离自己最近的服务器。

这样即使中间少了一台服务器,也能够从这个服务器之后继续往后寻找一个新的可用的服务器节点。

我们将NodeArray改造一下:

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

public class NodeArray {
TreeMap<Integer, Node> nodes = new TreeMap<>();
public void addNode(Node node) {
nodes.put(node.hashCode(), node);
}
public void removeNode(Node node) {
nodes.remove(node.hashCode());
}
Obj get(Obj obj) {
Node node;
node = nodes.get(obj.hashCode());
if (node != null) {
System.out.print(node.getAddress() + " ");
return node.getObj(obj);
}
// 找到比给定 key 大的集合
SortedMap<Integer, Node> tailMap = nodes.tailMap(obj.hashCode());
// 找到最小的节点
int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
node = nodes.get(nodeHashcode);
System.out.print(node.getAddress() + " ");
return node.getObj(obj);
}
void put(Obj obj) {
int objHashcode = obj.hashCode();
Node node = nodes.get(objHashcode);
if (node != null) {
node.putObj(obj);
return;
}

// 找到比给定 key 大的集合
SortedMap<Integer, Node> tailMap = nodes.tailMap(objHashcode);
// 找到最小的节点
int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
nodes.get(nodeHashcode).putObj(obj);
}
}

运行结果为:

1
2
3
4
5
6
7
8
9
10
11
12

192.168.0.3 Obj{name='1'}
192.168.0.2 Obj{name='2'}
192.168.0.1 Obj{name='3'}
192.168.0.3 Obj{name='4'}
192.168.0.3 Obj{name='5'}
========== after =============
192.168.0.3 Obj{name='1'}
192.168.0.2 Obj{name='2'}
192.168.0.1 Obj{name='3'}
192.168.0.3 Obj{name='4'}
192.168.0.3 Obj{name='5'}

一致性Hash算法的问题

一致性Hash由于Hash之后可能定位到相近的地址段中导致负载不均的问题,因此我们需要引入虚拟节点来解决这个问题
其工作原理是:将一个物理节点拆分为多个虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式可以有效的解决地址分配不均衡的问题。

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

public class NodeArray {
/**
* 虚拟节点
*/
SortedMap<Integer, Node> virtualNodes = new TreeMap<>();

/**
* 虚拟节点数
*/
final int VIRTUAL_NODES = 5;
public void addNode(Node node) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
Node virtualNode = new Node(node.getAddress() + "&&VN" + i);
virtualNode.node = node.node;
int hash = HashUtils.getHash(virtualNode.getAddress());
System.out.println("虚拟节点[" + virtualNode + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNode);
}
}
public void removeNode(Node node) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
Node virtualNode = new Node(node.getAddress() + "&&VN" + i);
int hash = HashUtils.getHash(virtualNode.getAddress());
System.out.println("虚拟节点[" + virtualNode + "]被删除, hash值为" + hash);
virtualNodes.remove(hash);
}
}
Obj get(Obj obj) {
Node node;
node = virtualNodes.get(obj.hashCode());
if (node != null) {
System.out.print(node.getAddress() + " ");
return node.getObj(obj);
}
// 找到比给定 key 大的集合
SortedMap<Integer, Node> tailMap = virtualNodes.tailMap(obj.hashCode());
// 找到最小的节点
int nodeHashcode = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
node = virtualNodes.get(nodeHashcode);
System.out.print(node.getAddress() + " ");
return node.getObj(obj);
}
void put(Obj obj) {
int objHashcode = obj.hashCode();
Node node = virtualNodes.get(objHashcode);
if (node != null) {
node.putObj(obj);
return;
}

// 找到比给定 key 大的集合
SortedMap<Integer, Node> tailMap = virtualNodes.tailMap(objHashcode);
// 找到最小的节点
int nodeHashcode = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
virtualNodes.get(nodeHashcode).putObj(obj);
}
}

执行结果:

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

虚拟节点[Node{address='192.168.0.1&&VN0'}]被添加, hash值为675967561
虚拟节点[Node{address='192.168.0.1&&VN1'}]被添加, hash值为281940379
虚拟节点[Node{address='192.168.0.1&&VN2'}]被添加, hash值为533000324
虚拟节点[Node{address='192.168.0.1&&VN3'}]被添加, hash值为662119032
虚拟节点[Node{address='192.168.0.1&&VN4'}]被添加, hash值为194906877
虚拟节点[Node{address='192.168.0.2&&VN0'}]被添加, hash值为99777120
虚拟节点[Node{address='192.168.0.2&&VN1'}]被添加, hash值为1792088293
虚拟节点[Node{address='192.168.0.2&&VN2'}]被添加, hash值为1807865840
虚拟节点[Node{address='192.168.0.2&&VN3'}]被添加, hash值为1517366624
虚拟节点[Node{address='192.168.0.2&&VN4'}]被添加, hash值为1408334810
虚拟节点[Node{address='192.168.0.3&&VN0'}]被添加, hash值为2003205714
虚拟节点[Node{address='192.168.0.3&&VN1'}]被添加, hash值为51298955
虚拟节点[Node{address='192.168.0.3&&VN2'}]被添加, hash值为1514128021
虚拟节点[Node{address='192.168.0.3&&VN3'}]被添加, hash值为963993841
虚拟节点[Node{address='192.168.0.3&&VN4'}]被添加, hash值为192869356
192.168.0.2&&VN4 Obj{name='1'}
192.168.0.2&&VN4 Obj{name='2'}
192.168.0.3&&VN3 Obj{name='3'}
192.168.0.2&&VN4 Obj{name='4'}
192.168.0.2&&VN4 Obj{name='5'}
虚拟节点[Node{address='192.168.1.4&&VN0'}]被添加, hash值为1646480332
虚拟节点[Node{address='192.168.1.4&&VN1'}]被添加, hash值为870978208
虚拟节点[Node{address='192.168.1.4&&VN2'}]被添加, hash值为1782522189
虚拟节点[Node{address='192.168.1.4&&VN3'}]被添加, hash值为859295554
虚拟节点[Node{address='192.168.1.4&&VN4'}]被添加, hash值为103010354
========== after =============
192.168.0.2&&VN4 Obj{name='1'}
192.168.0.2&&VN4 Obj{name='2'}
192.168.0.3&&VN3 Obj{name='3'}
192.168.0.2&&VN4 Obj{name='4'}
192.168.0.2&&VN4 Obj{name='5'}