一致性哈希分片与取余分片扩容指南
假设有10个分片节点,1000万的数据量,主键从100万开始自增。下面是分别以一致性哈希和取余分片的结果
- 一致性哈希分片
执行PartitionByMurmurHash的main方法,按上述假设会得到以下结果
index bucket ratio
0 1001836 0.1001836
1 1038892 0.1038892
2 927886 0.0927886
3 972728 0.0972728
4 1086100 0.10861
5 908616 0.0908616
6 1024269 0.1024269
7 1018029 0.1018029
8 995581 0.0995581
9 1026063 0.1026063
第一列是分片节点的编号,第二列是hash到每个节点的数据量,第三列是每个hash到每个节点的数据量与总数据量的比值。第三列的和是1.0,第十五列的和是10000000。
如果数据量相当少,会发现一致性哈希的分布不够均匀,而只要数据量在10000以上一致性哈希的分布比率就能保持在0.1左右,数据越多分布越均匀,每个节点的数据量越接近。
现在假设增加二个新节点,对0号节点执行rehash,会出现以下结果
index bucket ratio
0 853804 0.8522392886660092
1 0 0.0
2 0 0.0
3 0 0.0
4 0 0.0
5 0 0.0
6 0 0.0
7 0 0.0
8 0 0.0
9 0 0.0
10 70075 0.06994657808264028
11 77957 0.07781413325135052
第一第二列的意义与上一组列表一样,第三列是hash到当前节点上的数据量与原0号节点总数据量的比值。
从以上列表可以看到,原0号节点有1001836数据,rehash之后大部分数据仍然hash到0号上面,少量数据hash到了10、11号两个新节点,其它旧节点没有得到原来0号上的数据。其实不管增加多少节点,数据的rehash结果都会呈现这个规律:已有节点的数据发生rehash时只有两个可能的去处,要么是rehash之前的节点,要么是新增加的节点,这也是一致性哈希的意义所在。
采用这种该片方式,可以保证数据在rehash时尽可能的少迁移数据。
- 取余分片
模仿一致性哈希的main方法实现一段取余分片的测试代码,初始节点数、数据量、id起始值、扩容数与前面一样,会得到以下结果
index bucket ratio
0 1000000 0.1
1 1000000 0.1
2 1000000 0.1
3 1000000 0.1
4 1000000 0.1
5 1000000 0.1
6 1000000 0.1
7 1000000 0.1
8 1000000 0.1
9 1000000 0.1
0.9999999999999999 10000000
1000000 1000000
index bucket ratio
0 166667 0.166667
1 0 0.0
2 166667 0.166667
3 0 0.0
4 166667 0.166667
5 0 0.0
6 166666 0.166666
7 0 0.0
8 166666 0.166666
9 0 0.0
10 166667 0.166667
11 0 0.0
星号行上面的内容是10个节点的哈希结果,星号行下面是0号节点rehash的结果,这个结果非常明显的显示出取余分片会均匀的把数据hash到每个节点,但是发生rehash时会把原节点中的数据再次平均分配,而且rehash结果会因为初始节点数和扩容节点数的不同而变化。
取余分片的rehash数据迁移量比一致性哈希的要大的多。在按原节点数的2倍扩容时取余迁移量最低,为总数据量的1/2。随着调整初始节点和扩容节点的奇偶性以及二者的倍数关系,会得到不同的结果。有兴趣的同学可以自行试验,此处不再赘述。
评论区