Java一个简单的一致性hash算法(带虚拟节点)
程序员文章站
2024-03-19 21:27:22
...
最近由于项目需要实现一个负载均衡的功能。考虑到以往的技术应用,准备参考Mycat的一致性hash算法,实现此功能。查阅网上资料和Mycat一致性hash算法的源码后,编写了一个简单的实现算法。
具体实现如下:
缓存实现参考:https://blog.csdn.net/weixin_35971547/article/details/89427914
import com.gccp.translate.getway.cache.LocalCache;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.common.hash.Hashing;
import org.apache.commons.lang3.StringUtils;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
import java.util.stream.IntStream;
/**
* @author hilbert.xu
* @date 2019/4/20
*/
@Component
public class ConsistentHash {
/**
* 虚拟节点数
*/
private static final int virtualNodeNum = 160;
/**
* 获取服务
*
* @param key 客户端请求ip
*/
@SuppressWarnings("unchecked")
public static String getServer(String key) {
// 本地缓存,监听的可用服务 缓存实现参考:https://blog.csdn.net/weixin_35971547/article/details/89427914
Object value = LocalCache.getInstance().getValue("servers");
Set<String> servers = Objects.isNull(value) ? Sets.newHashSet() : (Set<String>) value;
// 添加虚拟节点
SortedMap<Integer, String> virtualNodes = Maps.newTreeMap();
servers.stream().map(StringBuilder::new)
.forEach(ips -> IntStream.range(0, virtualNodeNum)
.mapToObj(i -> ips.append("&&VN").append(i).toString()).forEach(virtualNodeName -> {
int hash = getHash(virtualNodeName);
virtualNodes.put(hash, virtualNodeName);
}));
// 得到带路由的结点的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.isNotBlank(virtualNode)) {
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
return null;
}
/**
* 使用FNV1_32_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;
}
}
实现比较简单,Hash计算算法网上查阅得到,基本可以满足需求。没有原理介绍,网上相关资料很多,有需求的童鞋可以自行查阅。欢迎大家讨论学习,希望对您有所帮助。
精进技术,与其死磕到底。
上一篇: Nessus安装**与使用