写点什么

第五周作业

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



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

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



Hash算法接口

public interface HashAlgorithm {
public int getHash(String v);
}

FNV-1a hash算法实现,参考网上的位移部分修正

public class FNV1A32HashAlgorithm implements HashAlgorithm{
private static final long FNV_32_INIT = 2166136261L;
private static final long FNV_32_PRIME = 16777619;
public int getHash(String v) {
int hash = (int)FNV_32_INIT;
int len = v.length();
for (int i = 0; i < len; i++) {
hash ^= v.charAt(i);
hash *= FNV_32_PRIME;
}
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环实现

public class HashRing {
private HashAlgorithm ha;
private int vns;
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
public HashRing() {
this(200, new FNV1A32HashAlgorithm());
}
public HashRing(int vns) {
this(vns, new FNV1A32HashAlgorithm());
}
public HashRing(int vns, HashAlgorithm ha ) {
this.vns = vns;
this.ha = ha;
}
public void addServer(String server) {
for(int i=0; i<vns; i++){
String virtualNodeName = server + "##" + i;
int hash = ha.getHash(virtualNodeName);
virtualNodes.put(hash, virtualNodeName);
}
}
public int getHash(String data) {
return ha.getHash(data);
}
public String getServer(String data) {
int hash = ha.getHash(data);
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if(subMap.isEmpty()){
Integer i = virtualNodes.firstKey();
virtualNode = virtualNodes.get(i);
}else{
Integer i = subMap.firstKey();
virtualNode = subMap.get(i);
}
if(virtualNode.length() > 0){
return virtualNode.substring(0, virtualNode.indexOf("##"));
}
return null;
}

}

多次测试结果250个虚拟节点最佳,我感觉hash算法的修正还是有点问题的

datacount:1000000 server:10 virtualNode:20 avgDiff:18804

datacount:1000000 server:10 virtualNode:40 avgDiff:9945

datacount:1000000 server:10 virtualNode:50 avgDiff:11548

datacount:1000000 server:10 virtualNode:80 avgDiff:7348

datacount:1000000 server:10 virtualNode:100 avgDiff:6231

datacount:1000000 server:10 virtualNode:150 avgDiff:4056

datacount:1000000 server:10 virtualNode:200 avgDiff:4864

datacount:1000000 server:10 virtualNode:250 avgDiff:3344

datacount:1000000 server:10 virtualNode:300 avgDiff:4167



用户头像

数字

关注

还未添加个人签名 2018.10.06 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业