Hash 一致性虚拟节点算法

用户头像
李锦
关注
发布于: 2020 年 07 月 08 日

一致性哈希(Hash)算法解决了分布式环境下机器增加或者减少时,简单的取模运算无法获取较高命中率的问题。

 

通过虚拟节点的使用,一致性哈希算法可以均匀分担机器的负载,使得这一算法更具现实的意义。

 

一致性哈希算法通过哈希环的数据结构实现。环的起点是0,终点是2^32 - 1,并且起点与终点连接,哈希环中间的整数按逆时针(或者顺时针)分布,故哈希环的整数分布范围是[0, 2^32-1]。

 

在负载均衡中,首先为每一台机器计算一个哈希值,然后把这些哈希值放置在哈希环上。假设我们有3台Web服务器:s1、s2、s3,它们计算得到的哈希值分别为h1、h2、h3,如下图所示:

 

 

引入虚拟节点来解决负载不均衡的问题,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,作为虚拟节点来解决以下两种情况

 

  • 集群中如果有一台机器宕机,会导致该机器上的请求分配到临近的下一个机器上,那么该机器有可能导致负载过高而引起系统雪崩的情况。

  • 集群中增加一台机器,并不能够均衡原有所有机器的服务压力,只会分担临近机器的压力,所以不能做到分担整个集群的压力。

 



实现一致性Hash java 算法代码

 



public class ConsistentHash {
// 服务器列表
private List<String> servers = null;
// 服务器虚拟节点
private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
// 服务器访问统计
private TreeMap<String, Integer> serverVisit = new TreeMap<>();
// 虚拟节点个数
private int virtualFactor = 180;
public ConsistentHash(List<String> servers, int virtualFactor) {
this.servers = servers;
this.virtualFactor = virtualFactor;
this.servers.forEach(server -> this.addServer(server));
}
/**
* 获取字符串的hash值
*
* @param str
* @return
*/
public 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;
return hash;
}
/**
* 添加server节点
*
* @param server
*/
public void addServer(String server) {
if (!serverVisit.containsKey(server)) {
serverVisit.put(server, 0);
for (int i = 0; i < virtualFactor; i++) {
virtualNodes.put(getHash(server + "?VNODE=" + i), server);
}
}
}
/**
* 移除server节点
*
* @param server
*/
public void removeServer(String server) {
if (serverVisit.containsKey(server)) {
serverVisit.remove(server);
for (int i = 0; i < virtualFactor; i++) {
Object o = virtualNodes.remove(getHash(server + "?VNODE=" + i));
}
}
}
/**
* 模拟请求获取服务地址
*
* @param reqKey
* @return
*/
public String request(String reqKey) {
String server = null;
int reqHash = getHash(reqKey);
SortedMap<Integer, String> greaterMap = virtualNodes.tailMap(reqHash, true);
if (greaterMap.isEmpty()) {
// 如果没有比reqHash大的值,则返回第一个虚拟服务器节点
server = virtualNodes.get(virtualNodes.firstKey());
} else {
// greaterMap第一个值就是顺时针下离reqHash最近的虚拟服务器节点
server = greaterMap.get(greaterMap.firstKey());
}
// 记录访问次数
serverVisit.put(server, serverVisit.get(server) + 1);
return server;
}
/**
* 计算请求分布的标准差
*
* @return
*/
public double calcStd() {
Integer[] visitData = new Integer[serverVisit.size()];
serverVisit.values().toArray(visitData);
double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d);
double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
double std = Math.sqrt(avgStd);
return std;
}



由于日常工作不用代码,因此没有调试完成,后续再调试。

用户头像

李锦

关注

还未添加个人签名 2017.11.30 加入

还未添加个人简介

评论

发布
暂无评论
Hash 一致性虚拟节点算法