作业一:一致性 hash 实现

发布于: 2020 年 07 月 08 日

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

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

测试结果

package com.rudy.consistent;
import java.util.*;
public class ConsistentHash {
//物理节点
private ArrayList<Node> realNodes = new ArrayList<>();
//有序的虚拟节点,根据物理节点生成
private HashMap<Node, List<Integer>> realVirtualNodes = new HashMap<>();
private SortedMap<Integer, Node> sortedMap = new TreeMap<>();
//添加物理节点
public void addNode(Node node) {
realNodes.add(node);
List<Integer> virtualNodes = new ArrayList<>();
realVirtualNodes.put(node, virtualNodes);
//小于等于要求的个虚拟节点
for (int i = 0; i < node.getVirtualNums(); i++) {
String ip = node.ip + i;
int hashVaule = FNV1_32_HASH.getHash(ip);
if (!this.sortedMap.containsKey(hashVaule)) {
virtualNodes.add(hashVaule);
this.sortedMap.put(hashVaule, node);
}
}
}
//移除物理节点
public void removeNode(Node node) {
List<Integer> virtualNodes = this.realVirtualNodes.get(node);
if (realVirtualNodes != null) {
for (Integer hash : virtualNodes) {
this.sortedMap.remove(hash);
}
}
this.realVirtualNodes.remove(node);
this.realNodes.remove(node);
}
//获得物理节点
public Node getNode(String key) {
int hash = FNV1_32_HASH.getHash(key);
//得到大于该hash指的所有虚拟节点map
SortedMap<Integer, Node> subMap = sortedMap.tailMap(hash);
if (!subMap.isEmpty()) {
//取第一个key
Integer vhash = subMap.firstKey();
//返回对应的服务器
return subMap.get(vhash);
} else {
return sortedMap.get(sortedMap.firstKey());
}
}
/**
* 使用的是 FNV1_32_HASH
*/
public static long hash(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) {
hash = (hash ^ key.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 double StandardDeviation(int[] nums) {
if (nums == null || nums.length == 0) return 0;
long sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
long average = sum / nums.length;
int sum2 = 0;
for (int i = 0; i < nums.length; i++) {
sum2 += Math.pow(nums[i] - average, 2);
}
return Math.sqrt(sum2 / nums.length);
}
public static void main(String[] args) {
ConsistentHash ch = new ConsistentHash();
ch.addNode(new Node("192.168.1.10", 100));
ch.addNode(new Node("192.168.1.11", 100));
ch.addNode(new Node("192.168.1.12", 100));
ch.addNode(new Node("192.168.1.13", 100));
ch.addNode(new Node("192.168.1.14", 100));
ch.addNode(new Node("192.168.1.15", 100));
ch.addNode(new Node("192.168.1.16", 100));
ch.addNode(new Node("192.168.1.17", 100));
ch.addNode(new Node("192.168.1.18", 100));
ch.addNode(new Node("192.168.1.19", 100));
int[] chNums = new int[10];
for (int i = 0; i < 1000000; i++) {
String ip = ch.getNode("a" + i).getIp();
int num = Integer.valueOf(ip.substring(ip.length() - 1));
chNums[num]++;
}
for (int i = 0; i < chNums.length; i++) {
System.out.println("服务器" + i + ":" + chNums[i]);
}
System.out.println(ConsistentHash.StandardDeviation(chNums)/1000000);
}
}
//服务器节点
class Node {
//地址
String ip;
//对应的虚拟节点个数
int virtualNums;
public Node(String ip, int virtualNums) {
this.ip = ip;
this.virtualNums = virtualNums;
}
public String getIp() {
return ip;
}
public int getVirtualNums() {
return virtualNums;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return virtualNums == node.virtualNums &&
Objects.equals(ip, node.ip);
}
@Override
public int hashCode() {
return Objects.hash(ip, virtualNums);
}
}

用户头像

ruettiger

关注

还未添加个人签名 2018.05.30 加入

还未添加个人简介

评论

发布
暂无评论
作业一:一致性hash实现