一致哈希

用户头像
王鹏飞
关注
发布于: 2020 年 07 月 07 日
一致哈希
一致Hash的实现方式

一致哈希将每个对象映射到圆环边上的一个点,系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时,需要用一致哈希算法计算得到对象对应圆环边上位置,沿着圆环边上查找直到遇到某个节点机器,这台机器即为对象应该保存的位置。 当删除一台节点机器时,这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时,这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

一致哈希在互联网分布式缓存中非常有用的几个特性

冗余少,负载均衡,过渡平滑,存储均衡,关键词单调

应用实例(Java)

java 代码实现一致性hash算法,测试100万KV 数据,10个服务器节点的情况下,计算这些KV数据在服务器分布数量的标准差,以评估算法的存储负载不均衡性。

/**
*
* hash 环
*
*/
public class HashHoop {
/**
* 环上节点数据数量 : (2^31)-1
*/
final static private Integer hoopSize = Integer.MAX_VALUE;
/**
* 真实节点
*/
List<Node> realNodes;
/**
* 虚拟节点数量
*/
SortedMap<Long, Node> virtualNodes = new TreeMap<>();
/**
* 虚拟节点数量
*/
private int virtualNodeSize;
/**
* 初始化Hash环
* @param realNodes
* @param virtualNodeSize
*/
public HashHoop(List<Node> realNodes,int virtualNodeSize){
this.realNodes = realNodes;
this.virtualNodeSize = virtualNodeSize;
constructVirtualNodes();
}
/**
* 使用HashMap的散列码取值方式 借鉴 xxl-job 的代码
* @param value
* @return
*/
public Long getKeyHashCode(String value){
// md5 byte
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("MD5 not supported", e);
}
md5.reset();
byte[] keyBytes;
try {
keyBytes = value.getBytes("UTF-8");
} catch (UnsupportedEncodingException e) {
throw new RuntimeException("Unknown string :" + value, e);
}
md5.update(keyBytes);
byte[] digest = md5.digest();
// hash code, Truncate to 32-bits
long hashCode = ((long) (digest[3] & 0xFF) << 24)
| ((long) (digest[2] & 0xFF) << 16)
| ((long) (digest[1] & 0xFF) << 8)
| (digest[0] & 0xFF);
long truncateHashCode = hashCode & 0xffffffffL;
return truncateHashCode > hoopSize?truncateHashCode%hoopSize:truncateHashCode;
}
/**
* 构建虚拟节点
*/
private void constructVirtualNodes(){
/**
* 遍历每一个真实节点
*/
for (int i = 0; i < realNodes.size(); i++) {
String ip = realNodes.get(i).getIp();
for (int j = 0; j < virtualNodeSize; j++) {
String virtualIp = ip+"."+j;
Long key = getKeyHashCode(virtualIp);
virtualNodes.put(key,realNodes.get(i));
}
}
}
/**
* 跟进key获取一个最近的NODE节点
* @return
*/
public Node getKeyNode(String key){
Long hashCode = getKeyHashCode(key);
Node node;
if(!virtualNodes.containsKey(hashCode)){
SortedMap<Long, Node> tailMap = virtualNodes.tailMap(hashCode);
if(!tailMap.isEmpty()) {
node = tailMap.get(tailMap.firstKey());
}else{
node = virtualNodes.get(virtualNodes.firstKey());
}
}else{
node = virtualNodes.get(hashCode);
}
/**
* 增加命中个数
*/
node.incrementAndGet();
return node;
}
/**
* 清空虚拟节点
*/
public void cleanVirtualNodes() {
virtualNodes.clear();
}
/**
* 节点类
*/
static class Node {
/**
* 节点ip地址
*/
private String ip;
/**
* 命中计数器
*/
private AtomicInteger counter = new AtomicInteger(0);
public Node(String ip){
this.ip = ip;
}
public String getIp() {
return ip;
}
public void incrementAndGet(){
counter.incrementAndGet();
}
public int getCounter(){
return counter.get();
}
public void cleanCounter() {
counter.set(0);
}
}
}

测试用例

public class HashHoopTest {
static int keySize = 1000000;
static int nodeSize = 10;
static List<String> keyList = new ArrayList<>(keySize);
static List<HashHoop.Node> nodes = new ArrayList<>(nodeSize);
static{
for (int i = 0; i < nodeSize; i++) {
HashHoop.Node node = new HashHoop.Node("127.0.0."+i);
nodes.add(node);
}
for (int i = 0; i < keySize; i++) {
String key = DigestUtils.md5Hex(""+i);
keyList.add(key);
}
}
public static List<HashHoop.Node> getNodes() {
return nodes;
}
/**
* 平均值
* @param hashHoop
* @return
*/
public static long average(HashHoop hashHoop){
long sum = 0;
/**
* key集合遍历查找Node节点
*/
keyList.stream().forEach(key->hashHoop.getKeyNode(key));
for (int i = 0; i < nodeSize; i++) {
sum += nodes.get(i).getCounter();
System.out.println(nodes.get(i).getIp()+"分配KEY数量:"+nodes.get(i).getCounter());
}
return sum / nodeSize;
}
/**
* 标准差计算
* @param hashHoop
*/
public static void standardDeviation(HashHoop hashHoop){
long average = average(hashHoop);
long deviation = 0;
for (int i = 0; i < nodeSize; i++) {
int counter = nodes.get(i).getCounter();
deviation += Math.pow(counter - average,2);
}
System.out.println("平均值:"+average);
double sqrt = Math.sqrt(Double.valueOf(deviation / keySize));
System.out.println("标准差:"+sqrt);
nodes.stream().forEach(node ->node.cleanCounter());
System.out.println("Hash环上单个NODE节点虚拟节点数量 = " + hashHoop.virtualNodes.size()/nodeSize);
hashHoop.cleanVirtualNodes();
System.out.println("--------------------------------------------");
}
public static void main(String[] args) {
HashHoop hashHoop = new HashHoop(HashHoopTest.getNodes(),10);
HashHoopTest.standardDeviation(hashHoop);
HashHoop hashHoop2 = new HashHoop(HashHoopTest.getNodes(),50);
HashHoopTest.standardDeviation(hashHoop2);
HashHoop hashHoop3 = new HashHoop(HashHoopTest.getNodes(),100);
HashHoopTest.standardDeviation(hashHoop3);
HashHoop hashHoop4 = new HashHoop(HashHoopTest.getNodes(),150);
HashHoopTest.standardDeviation(hashHoop4);
HashHoop hashHoop5 = new HashHoop(HashHoopTest.getNodes(),200);
HashHoopTest.standardDeviation(hashHoop5);
HashHoop hashHoop6 = new HashHoop(HashHoopTest.getNodes(),250);
HashHoopTest.standardDeviation(hashHoop6);
HashHoop hashHoop7 = new HashHoop(HashHoopTest.getNodes(),300);
HashHoopTest.standardDeviation(hashHoop7);
HashHoop hashHoop8 = new HashHoop(HashHoopTest.getNodes(),400);
HashHoopTest.standardDeviation(hashHoop8);
HashHoop hashHoop9 = new HashHoop(HashHoopTest.getNodes(),800);
HashHoopTest.standardDeviation(hashHoop9);
HashHoop hashHoop10 = new HashHoop(HashHoopTest.getNodes(),1000);
HashHoopTest.standardDeviation(hashHoop10);
HashHoop hashHoop11 = new HashHoop(HashHoopTest.getNodes(),1500);
HashHoopTest.standardDeviation(hashHoop11);
HashHoop hashHoop12 = new HashHoop(HashHoopTest.getNodes(),2000);
HashHoopTest.standardDeviation(hashHoop12);
HashHoop hashHoop13 = new HashHoop(HashHoopTest.getNodes(),2500);
HashHoopTest.standardDeviation(hashHoop13);
HashHoop hashHoop14 = new HashHoop(HashHoopTest.getNodes(),3000);
HashHoopTest.standardDeviation(hashHoop14);
HashHoop hashHoop15 = new HashHoop(HashHoopTest.getNodes(),4000);
HashHoopTest.standardDeviation(hashHoop15);
HashHoop hashHoop16 = new HashHoop(HashHoopTest.getNodes(),5000);
HashHoopTest.standardDeviation(hashHoop16);
HashHoop hashHoop17 = new HashHoop(HashHoopTest.getNodes(),6000);
HashHoopTest.standardDeviation(hashHoop17);
HashHoop hashHoop18 = new HashHoop(HashHoopTest.getNodes(),10000);
HashHoopTest.standardDeviation(hashHoop18);
HashHoop hashHoop19 = new HashHoop(HashHoopTest.getNodes(),20000);
HashHoopTest.standardDeviation(hashHoop19);
}
}

输出结果:

127.0.0.0分配KEY数量:141125
127.0.0.1分配KEY数量:77641
127.0.0.2分配KEY数量:104462
127.0.0.3分配KEY数量:39402
127.0.0.4分配KEY数量:149200
127.0.0.5分配KEY数量:89326
127.0.0.6分配KEY数量:117044
127.0.0.7分配KEY数量:72907
127.0.0.8分配KEY数量:116147
127.0.0.9分配KEY数量:92746
平均值:100000
标准差:98.76740352970711

###### Hash环上单个NODE节点虚拟节点数量 = 10

127.0.0.0分配KEY数量:120295
127.0.0.1分配KEY数量:97681
127.0.0.2分配KEY数量:108186
127.0.0.3分配KEY数量:91186
127.0.0.4分配KEY数量:101720
127.0.0.5分配KEY数量:103941
127.0.0.6分配KEY数量:105702
127.0.0.7分配KEY数量:99307
127.0.0.8分配KEY数量:84174
127.0.0.9分配KEY数量:87808
平均值:100000
标准差:31.811947441173732

Hash环上单个NODE节点虚拟节点数量 = 50
--------------------------------------------

127.0.0.0分配KEY数量:121694
127.0.0.1分配KEY数量:105614
127.0.0.2分配KEY数量:104313
127.0.0.3分配KEY数量:98937
127.0.0.4分配KEY数量:95370
127.0.0.5分配KEY数量:96687
127.0.0.6分配KEY数量:89168
127.0.0.7分配KEY数量:95432
127.0.0.8分配KEY数量:98569
127.0.0.9分配KEY数量:94216
平均值:100000
标准差:26.962937525425527

Hash环上单个NODE节点虚拟节点数量 = 100
--------------------------------------------

127.0.0.0分配KEY数量:120371
127.0.0.1分配KEY数量:93826
127.0.0.2分配KEY数量:107440
127.0.0.3分配KEY数量:97381
127.0.0.4分配KEY数量:97180
127.0.0.5分配KEY数量:103809
127.0.0.6分配KEY数量:94609
127.0.0.7分配KEY数量:94630
127.0.0.8分配KEY数量:97632
127.0.0.9分配KEY数量:93122
平均值:100000
标准差:25.45584412271571

Hash环上单个NODE节点虚拟节点数量 = 150
--------------------------------------------

127.0.0.0分配KEY数量:108738
127.0.0.1分配KEY数量:98449
127.0.0.2分配KEY数量:101241
127.0.0.3分配KEY数量:104618
127.0.0.4分配KEY数量:94029
127.0.0.5分配KEY数量:105536
127.0.0.6分配KEY数量:101061
127.0.0.7分配KEY数量:97512
127.0.0.8分配KEY数量:94730
127.0.0.9分配KEY数量:94086
平均值:100000
标准差:15.394804318340652

Hash环上单个NODE节点虚拟节点数量 = 200
--------------------------------------------

127.0.0.0分配KEY数量:103858
127.0.0.1分配KEY数量:101208
127.0.0.2分配KEY数量:93974
127.0.0.3分配KEY数量:98829
127.0.0.4分配KEY数量:97283
127.0.0.5分配KEY数量:104005
127.0.0.6分配KEY数量:100487
127.0.0.7分配KEY数量:105778
127.0.0.8分配KEY数量:99679
127.0.0.9分配KEY数量:94899
平均值:100000
标准差:11.704699910719626

Hash环上单个NODE节点虚拟节点数量 = 250
--------------------------------------------

127.0.0.0分配KEY数量:99023
127.0.0.1分配KEY数量:100131
127.0.0.2分配KEY数量:104517
127.0.0.3分配KEY数量:101558
127.0.0.4分配KEY数量:97920
127.0.0.5分配KEY数量:104116
127.0.0.6分配KEY数量:99918
127.0.0.7分配KEY数量:99310
127.0.0.8分配KEY数量:97203
127.0.0.9分配KEY数量:96304
平均值:100000
标准差:8.18535277187245

Hash环上单个NODE节点虚拟节点数量 = 300
--------------------------------------------

127.0.0.0分配KEY数量:96202
127.0.0.1分配KEY数量:102863
127.0.0.2分配KEY数量:104250
127.0.0.3分配KEY数量:97786
127.0.0.4分配KEY数量:92200
127.0.0.5分配KEY数量:108342
127.0.0.6分配KEY数量:98033
127.0.0.7分配KEY数量:96841
127.0.0.8分配KEY数量:103379
127.0.0.9分配KEY数量:100104
平均值:100000
标准差:14.177446878757825

Hash环上单个NODE节点虚拟节点数量 = 400
--------------------------------------------

127.0.0.0分配KEY数量:94633
127.0.0.1分配KEY数量:99120
127.0.0.2分配KEY数量:105431
127.0.0.3分配KEY数量:92272
127.0.0.4分配KEY数量:96467
127.0.0.5分配KEY数量:100561
127.0.0.6分配KEY数量:101344
127.0.0.7分配KEY数量:103069
127.0.0.8分配KEY数量:104589
127.0.0.9分配KEY数量:102514
平均值:100000
标准差:13.038404810405298

Hash环上单个NODE节点虚拟节点数量 = 800
--------------------------------------------

127.0.0.0分配KEY数量:92340
127.0.0.1分配KEY数量:96464
127.0.0.2分配KEY数量:102144
127.0.0.3分配KEY数量:96956
127.0.0.4分配KEY数量:98458
127.0.0.5分配KEY数量:99034
127.0.0.6分配KEY数量:106667
127.0.0.7分配KEY数量:103118
127.0.0.8分配KEY数量:103775
127.0.0.9分配KEY数量:101044
平均值:100000
标准差:12.529964086141668

Hash环上单个NODE节点虚拟节点数量 = 1000
--------------------------------------------

127.0.0.0分配KEY数量:95805
127.0.0.1分配KEY数量:100205
127.0.0.2分配KEY数量:99596
127.0.0.3分配KEY数量:97006
127.0.0.4分配KEY数量:96140
127.0.0.5分配KEY数量:101440
127.0.0.6分配KEY数量:102942
127.0.0.7分配KEY数量:103330
127.0.0.8分配KEY数量:102518
127.0.0.9分配KEY数量:101018
平均值:100000
标准差:8.366600265340756

Hash环上单个NODE节点虚拟节点数量 = 1500
--------------------------------------------

127.0.0.0分配KEY数量:97863
127.0.0.1分配KEY数量:99000
127.0.0.2分配KEY数量:100414
127.0.0.3分配KEY数量:95832
127.0.0.4分配KEY数量:99524
127.0.0.5分配KEY数量:99485
127.0.0.6分配KEY数量:103827
127.0.0.7分配KEY数量:103904
127.0.0.8分配KEY数量:100984
127.0.0.9分配KEY数量:99167
平均值:100000
标准差:7.416198487095663

Hash环上单个NODE节点虚拟节点数量 = 1999
--------------------------------------------

127.0.0.0分配KEY数量:98910
127.0.0.1分配KEY数量:97507
127.0.0.2分配KEY数量:101462
127.0.0.3分配KEY数量:96531
127.0.0.4分配KEY数量:99710
127.0.0.5分配KEY数量:98873
127.0.0.6分配KEY数量:102404
127.0.0.7分配KEY数量:103315
127.0.0.8分配KEY数量:103511
127.0.0.9分配KEY数量:97777
平均值:100000
标准差:7.483314773547883

Hash环上单个NODE节点虚拟节点数量 = 2499
--------------------------------------------

127.0.0.0分配KEY数量:98656
127.0.0.1分配KEY数量:97473
127.0.0.2分配KEY数量:100894
127.0.0.3分配KEY数量:97844
127.0.0.4分配KEY数量:98564
127.0.0.5分配KEY数量:98353
127.0.0.6分配KEY数量:102978
127.0.0.7分配KEY数量:103991
127.0.0.8分配KEY数量:102844
127.0.0.9分配KEY数量:98403
平均值:100000
标准差:7.280109889280518

Hash环上单个NODE节点虚拟节点数量 = 2999
--------------------------------------------

127.0.0.0分配KEY数量:98580
127.0.0.1分配KEY数量:99114
127.0.0.2分配KEY数量:100538
127.0.0.3分配KEY数量:98451
127.0.0.4分配KEY数量:99889
127.0.0.5分配KEY数量:97336
127.0.0.6分配KEY数量:102568
127.0.0.7分配KEY数量:102403
127.0.0.8分配KEY数量:103717
127.0.0.9分配KEY数量:97404
平均值:100000
标准差:6.708203932499369

Hash环上单个NODE节点虚拟节点数量 = 3999
--------------------------------------------

127.0.0.0分配KEY数量:97525
127.0.0.1分配KEY数量:100191
127.0.0.2分配KEY数量:100284
127.0.0.3分配KEY数量:97420
127.0.0.4分配KEY数量:100041
127.0.0.5分配KEY数量:98076
127.0.0.6分配KEY数量:103928
127.0.0.7分配KEY数量:103534
127.0.0.8分配KEY数量:101713
127.0.0.9分配KEY数量:97288
平均值:100000
标准差:7.3484692283495345

Hash环上单个NODE节点虚拟节点数量 = 4999
--------------------------------------------

127.0.0.0分配KEY数量:96725
127.0.0.1分配KEY数量:100410
127.0.0.2分配KEY数量:101926
127.0.0.3分配KEY数量:96919
127.0.0.4分配KEY数量:100816
127.0.0.5分配KEY数量:98944
127.0.0.6分配KEY数量:102739
127.0.0.7分配KEY数量:101814
127.0.0.8分配KEY数量:102444
127.0.0.9分配KEY数量:97263
平均值:100000
标准差:7.0710678118654755

Hash环上单个NODE节点虚拟节点数量 = 5999
--------------------------------------------

127.0.0.0分配KEY数量:99748
127.0.0.1分配KEY数量:100050
127.0.0.2分配KEY数量:99580
127.0.0.3分配KEY数量:99728
127.0.0.4分配KEY数量:99997
127.0.0.5分配KEY数量:97555
127.0.0.6分配KEY数量:103172
127.0.0.7分配KEY数量:100651
127.0.0.8分配KEY数量:100517
127.0.0.9分配KEY数量:99002
平均值:100000
标准差:4.242640687119285

Hash环上单个NODE节点虚拟节点数量 = 9999
--------------------------------------------

127.0.0.0分配KEY数量:100361
127.0.0.1分配KEY数量:99724
127.0.0.2分配KEY数量:100058
127.0.0.3分配KEY数量:99854
127.0.0.4分配KEY数量:100400
127.0.0.5分配KEY数量:98707
127.0.0.6分配KEY数量:100139
127.0.0.7分配KEY数量:101495
127.0.0.8分配KEY数量:98692
127.0.0.9分配KEY数量:100570
平均值:100000
标准差:2.449489742783178

Hash环上单个NODE节点虚拟节点数量 = 19998
--------------------------------------------
总结

标准差随着虚拟节点的增加而逐渐下降。算法中的 getKeyHashCode 方法借鉴 xxl-job中的源码实现,在虚拟节点设置到 10000 时出现了 一个hashCode值冲突,20000 时增加为2 。虽然标准差的值逐步降低但是同样业务产生了两个疑问 1.虚拟机节点的个数应如何界定?2.有没有一个比较通用的hashCode算法?

发布于: 2020 年 07 月 07 日 阅读数: 44
用户头像

王鹏飞

关注

还未添加个人签名 2019.06.11 加入

还未添加个人简介

评论

发布
暂无评论
一致哈希