一致性哈希(Consistent Hashing)

在实现分库分表的时候,需要全面考虑以下的问题:
1、持久化服务负载多台的情况下,确保分库分表键对应的目标库表一致;
2、根据分库分表键能均匀分配数据;
3、涉及到变更库表数量的时候产生的变动最小。


方案一:hash(分库键)%库数 + hash(分表键)%表数

这是我最开始想到的方案,它能很快的解决问题1,问题2也能勉强满足,但遇到问题3就需要将所有的数据重新导出再导入一遍,这个性能消耗让人无法接受。

方案二:一致性hash(分裤键) + 一致性hash(分表键)

由于方案一不能完全满足所有的问题,所以引入了一致性hash。

分布式解决方案中,为了负载均衡,提供了很多不同场景使用的算法,其中有轮循、哈希、最少连接等,而最快速最常用的就是哈希算法。但根据N取模的hash算法,会随着N变化而产生覆灭式的颠簸,所以一致性哈希算法(Consistent Hashing Algorithm)由此产生,来解决这些问题。

解决问题1:

一致性hash算法的原理:

将N固定为了2^32,即[0, 2^32-1],将这些点按顺时针组成一个虚拟圆环,然后将服务器hash值模除2^32后,得到服务器在这虚拟圆环上的位置。同理,将数据的hash值也模除2^32后,得到圆环上的位置,并顺时针找到第一个对应的服务器节点,即该数据对应这个数据库节点。如此分布式情况下,只要用于hash的key一致,对应的服务器也一定是一致的。

解决问题2:

如上图,如果服务器节点太少,容易导致数据分配不均匀,可能会集中在某一块而分配到一个服务器上,这个可以虚拟服务器节点,服务器节点越多则被分配到的数据越平均

解决问题3:

当新增或者删除服务器节点的时候,只会影响该服务器节点逆时针到下一个服务器节点之间的数据,并且只要把这部分数据迁移到这些数据顺时针的第一个服务器节点即可

java代码:

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/**
* 需要做一致性hash的节点 接口
*/
public interface ConsistentHashNode {
String hashString();
}

/**
* 数据库表节点,实现了hash算法
*/
public class TableNode implements ConsistentHashNode {
private String tableName; // 表名
private int index; // 表下标

public TableNode(String tableName, int index) {
this.tableName = tableName;
this.index = index;
}

public String getTableName() {
return tableName;
}

public void setTableName(String tableName) {
this.tableName = tableName;
}

public int getIndex() {
return index;
}

public void setIndex(int index) {
this.index = index;
}

@Override
public String hashString() {
return "" + index;
}
}

/**
* 一致性hash算法
*/
public class ConsistentHash<T extends ConsistentHashNode> {
/**
* 通过treemap天然实现一致性hash的圆环
*/
protected final SortedMap<Integer, T> circle = new TreeMap<>();
/**
* 自定义hash方法,我是用md5,这里抽象出来,方便控制
*/
protected HashFunction hashFunction;
/**
* 备份数,用于新增虚拟节点
* 越大越负载均衡
*/
protected int replicas = 1;

public ConsistentHash() {
}

public ConsistentHash(HashFunction hashFunction, int replicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.replicas = replicas;

for (T node : nodes) {
add(node);
}
}

/**
* 初始化表节点,以及虚拟节点
*/
public void add(T node) {
for (int i = 1; i <= replicas; i++) {
int hasCode = replicasHashCode(node, i);
circle.put(hasCode, node);
}
}

public void remove(ConsistentHashNode node) {
for (int i = 0; i < replicas; i++) {
int hasCode = replicasHashCode(node, i);
circle.remove(hasCode);
}
}

public boolean contains(ConsistentHashNode node) {
for (int i = 0; i < replicas; i++) {
int hasCode = replicasHashCode(node, i);
if (circle.containsKey(hasCode)) {
return true;
}
}
return false;
}

/**
* 获取key对应的顺时针及比keyhash值大的数据库表节点,若未找到,取circle第一个节点
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}

private int replicasHashCode(ConsistentHashNode node, int replaceNo) {
return hashFunction.hash(node.hashString() + "-" + replaceNo);
}

public Collection<T> getAll() {
return circle.values();
}

public int getReplicas() {
return replicas;
}

public void setReplicas(int replicas) {
this.replicas = replicas;
}

public HashFunction getHashFunction() {
return hashFunction;
}

public void setHashFunction(HashFunction hashFunction) {
this.hashFunction = hashFunction;
}

public void clear() {
circle.clear();
}
}

显示 Gitment 评论