分布式缓存一致性 hash 算法实现

用户头像
考尔菲德
关注
发布于: 2020 年 07 月 07 日

1、首先自己需要提供一个hash算法,保证数据足够的分散,Hash算法如下:

// 需要保证Hash算法的分散
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;
}



2、需要构造hash环,然后由真实节点生成虚拟节点,如下代码:

public ConsistentHash(List<String> serverIps, Integer vnCount) {

this.vnCount = vnCount;
for (String ip : serverIps) {
realNodes.add(ip);
for (int i = 0; i < vnCount; i++) {
// 生成虚拟节点ip用于生成虚拟节点hash
String vnIp = ip + "&&VN" + i;
// 根据虚拟节点ip生成hash值
int vnHash = getHash(vnIp);
// 对应的Hash作为键,将虚拟节点信息作为value,插入到Hash缓存
hashAndServerIpMap.put(vnHash, vnIp);
}
}
}



3、对于提供的健值进行hash计算和路由,确定去哪一台服务器上获取数据,提供方法根据健值返回对应真实服务器的ip,代码如下:

// 根据数据的健值,计算hash值,然后通过空间环查询服务器ip,然后通过服务器ip查找对应的缓存
public String getServer(String key) {
// 结算健值对应的Hash值
Integer hash = getHash(key);
// 获取hash后面的节点数据
SortedMap<Integer, String> tailMap = hashAndServerIpMap.tailMap(hash);
Integer nodeHash;
// 如果该tailMap为空,则表示hash值大于列表中的最大值,则需要去第一个节点;
if (CollectionUtils.isEmpty(tailMap)) {
nodeHash = hashAndServerIpMap.firstKey();
} else {
// 否则就去tailMap中的第一个key值,就是对应的虚拟节点的ip
nodeHash = tailMap.firstKey();
}
String vnIp = hashAndServerIpMap.get(nodeHash);
return vnIp.substring(0, vnIp.indexOf("&&"));
}



4、测试代码如下:

public static void main(String[] args) {
Map<String, Integer> serverCountMap = new HashMap<>();
List<String> serverIps = new ArrayList<>();
Integer dataCount = 1000000;
Integer vnCount = 1000;
Integer server = 10;
for (int i = 0; i < server; i++) {
StringBuilder sb = new StringBuilder();
sb.append("127.0.0.1:");
sb.append(i);
sb.append(i);
sb.append(i);
sb.append(i);
String serverIp = sb.toString();
serverIps.add(serverIp);
serverCountMap.put(serverIp, Integer.valueOf(0));
}
ConsistentHash ch = new ConsistentHash(serverIps, vnCount);
for (int i = 0; i < dataCount; i++) {
String serverIp = ch.getServer(String.valueOf(i));
Integer serverCount = serverCountMap.get(serverIp);
serverCountMap.put(serverIp, serverCount + 1);
}
double sd = getSD(serverCountMap.values(), dataCount/server);
System.out.println("sd: " + String.valueOf(sd));
}
// 计算方差
public static double getSD(Collection<Integer> serverCount, Integer average) {
Integer vnCount = serverCount.size();
double varianceSum = 0d;
for (Integer value : serverCount) {
varianceSum = varianceSum + Math.pow((value - average), 2);
}
double variance = varianceSum / vnCount;
return Math.sqrt(variance);
}



用户头像

考尔菲德

关注

还未添加个人签名 2018.04.19 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
标准差可以打印出来看下,同时调整虚拟节点个数和哈希方法,看看变化
2020 年 07 月 13 日 22:33
回复
没有更多了
分布式缓存一致性hash算法实现