您的位置 首页 java

一致性hash算法及java实现

典型的应用场景是: 有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,每台机器负责1/N的服务。

常用的算法是对 hash 结果取余数 (hash() mod N ):对机器编号从0到N-1,按照自定义的 hash()算法,对每个请求的hash()值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将当掉的服务器从算法从去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。

一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法,常用于负载均衡。Memcached client也选择这种算法,解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作,解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server,命中率会急剧下降)。

简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0 – (2^32)-1(即哈希值是一个32位无符号整形)

以下是自己总结的:

不带虚拟节点的一致性hash算法流程

1、定义一个服务器列表信息;

2、将服务器列表计算出hash值,并添加到map中(或者redis中);

3、计算出key值得hash值;

4、在map中取出大于此hash值得列表;

5、如果有则顺时针取出离 node 最近节点的服务器;

6、如果没有则取出map中第一个节点即可;

7、完毕;

代码如下:

//待添加入Hash环的服务器列表
private static String[] servers = { "192.168.0.1:8080", "192.168.0.2:8080",
 "192.168.0.3:8080", "192.168.0.4:8080", "192.168.0.5:8080" };
 
//key表示服务器的hash值,value表示服务器
private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
 
//程序初始化,将所有的服务器放入sortedMap中
static {
 for (int i=0; i<servers.length; i++) {
 int hash = getHash(servers[i]);
 System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
 sortedMap.put(hash, servers[i]);
 }
 System.out.println();
}
 
//得到应当路由到的结点
private static String getServer(String key) {
 //得到该key的hash值
 int hash = getHash(key);
 //得到大于该Hash值的所有Map
 SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
 if(subMap.isEmpty()){
 //如果没有比该key的hash值大的,则从第一个node开始
 Integer i = sortedMap.firstKey();
 //返回对应的服务器
 return sortedMap.get(i);
 }else{
 //第一个Key就是顺时针过去离node最近的那个结点
 Integer i = subMap.firstKey();
 //返回对应的服务器
 return subMap.get(i);
 }
}
 
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写 hashCode 的方法,最终效果没区别
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) {
 String[] keys = {"香蕉", "菠萝", "蜂蜜"};
 for(int i=0; i<keys.length; i++)
 System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])
 + ", 被路由到结点[" + getServer(keys[i]) + "]");
}
 

带虚拟接待的一致性hash算法流程

1、先把原始的服务器添加到真实结点列表中;

2、再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高;

3、得到该key的hash值;

4、得到大于该Hash值的所有Map;

5、如果没有比该key的hash值大的,则从第一个node开始;

6、如果有则第一个Key就是顺时针过去离node最近的那个结点

7、返回对应的服务器;

8、virtualNode虚拟节点名称要截取一下;

9、结束

代码如下:

//待添加入Hash环的服务器列表
private static String[] servers = {"192.168.0.1:8080", "192.168.0.2:8080", "192.168.0.3:8080",
 "192.168.0.4:8080", "192.168.0.5:8080"};
 
//真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
private static List<String> realNodes = new LinkedList<String>();
 
//虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
 
//虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
private static final int VIRTUAL_NODES = 5;
 
static{
 //先把原始的服务器添加到真实结点列表中
 for(int i=0; i<servers.length; i++)
 realNodes.add(servers[i]);
 
 //再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
 for (String str : realNodes){
 for(int i=0; i<VIRTUAL_NODES; i++){
 String virtualNodeName = str + "&&VN" + String.valueOf(i);
 int hash = getHash(virtualNodeName);
 System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
 virtualNodes.put(hash, virtualNodeName);
 }
 }
 System.out.println();
}
 
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
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;
}
 
//得到应当路由到的结点
private static String getServer(String key){
 //得到该key的hash值
 int hash = getHash(key);
 // 得到大于该Hash值的所有Map
 SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
 String virtualNode;
 if(subMap.isEmpty()){
 //如果没有比该key的hash值大的,则从第一个node开始
 Integer i = virtualNodes.firstKey();
 //返回对应的服务器
 virtualNode = virtualNodes.get(i);
 }else{
 //第一个Key就是顺时针过去离node最近的那个结点
 Integer i = subMap.firstKey();
 //返回对应的服务器
 virtualNode = subMap.get(i);
 }
 //virtualNode虚拟节点名称要截取一下
 if(!StringUtils.isEmpty(virtualNode)){
 return virtualNode.substring(0, virtualNode.indexOf("&&"));
 }
 return null;
}
 
public static void main(String[] args){
 String[] keys = {"香蕉", "菠萝", "蜂蜜"};
 for(int i=0; i<keys.length; i++)
 System.out.println("[" + keys[i] + "]的hash值为" +
 getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");
}
 

如有疑问,请留言,我会一一解答。

文章来源:智云一二三科技

文章标题:一致性hash算法及java实现

文章地址:https://www.zhihuclub.com/186935.shtml

关于作者: 智云科技

热门文章

评论已关闭

6条评论

  1. 3 Impaired pancreatic exocrine and endocrine function interact with alterations in the digestive tract to promote pancreatic cancer cachexia

  2. Understanding your semen parameters is the first step to managing any issues with fertility

  3. Flushing caused by pancreatic cell tumors, such as a VIPoma, often will present with other concomitant symptoms, such as watery diarrhea, dehydration, low potassium, and achlorhydria

网站地图