一致性哈希算法 JAVA 版简单验证

发布于: 20 小时前

  • 用熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

public class ConsistentHash {
//模拟 10个物理物理节点 ip
private Set<String> realIPNodes = new TreeSet<String>() {{
add("192.168.1.1");
add("192.168.1.2");
add("192.168.1.3");
add("192.168.1.4");
add("192.168.1.5");
add("192.168.1.6");
add("192.168.1.7");
add("192.168.1.8");
add("192.168.1.9");
add("192.168.1.10");
}
};
private final int copies = 100000; // 复制倍数
private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 -> 物理节点
private static Long FNVHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for (int idx = 0, num = key.length(); idx < num; ++idx) {
hash = (hash ^ key.charAt(idx)) * 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 ConsistentHash() {
for (String nodeIp : realIPNodes) {
addPhysicalNode(nodeIp);
}
}
// 添加物理节点
public void addPhysicalNode(String nodeIp) {
for (int idx = 0; idx < copies; ++idx) {
long hash = FNVHash(nodeIp + "#" + idx);
virtualNodes.put(hash, nodeIp);
}
}
// 查找对象映射的节点
public String getObjectNode(String object) {
long hash = FNVHash(object);
SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
return virtualNodes.get(key);
}
// 统计对象与节点的映射关系
public void dumpObjectNodeMap(int objectMin, int objectMax) {
// 统计
Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
for (int object = objectMin; object <= objectMax; ++object) {
String nodeIp = getObjectNode(Integer.toString(object));
Integer count = objectNodeMap.get(nodeIp);
objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
}
double totalCount = objectMax - objectMin + 1;
for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
double percent = (100 * entry.getValue() / totalCount);
System.out.println("IP=" + entry.getKey() + ": 命中率=" + percent + "%");
}
}
public static void main(String[] args) {
ConsistentHash ch = new ConsistentHash();
ch.dumpObjectNodeMap( 0, 1000000);
}
}

运行

结果:

用户头像

王胜贤

关注

还未添加个人签名 2018.04.28 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希算法JAVA版简单验证