写点什么

第五周作业

用户头像
jizhi7
关注
发布于: 2020 年 11 月 23 日
  1. 用你熟悉的编程语言实现一致性 hash 算法。

算法接口:

public interface ConsistencyHash {
/** * 设置虚拟节点数量 * @param num */ void setVirtualNodeNum(int num);
/** * 添加服务器节点 * @param service */ void addService(String service);
/** * 批量添加 * @param services */ void addServices(String[] services);

/** * 获取顺时针最近的服务器节点 * @param key * @return */ String getService(Object key);
}
复制代码


算法的具体实现:

public class ConsistencyHashImpl implements ConsistencyHash {
private TreeMap<Integer, String> hashServices = new TreeMap<>();
private int virtualNodeNum = 0;
public static final String VIRTUAL_NODE_SEG = "V";
@Override public void setVirtualNodeNum(int num) { this.virtualNodeNum = num; }
@Override public void addService(String service) { int hashcode = getHash(service); hashServices.put(hashcode, service);
addVirtualNode(service); }
private void addVirtualNode(String service) { for (int i = 0; i < virtualNodeNum; i++) { int hashcode = getHash(service + VIRTUAL_NODE_SEG + i);
hashServices.put(hashcode, service); } }
@Override public void addServices(String[] services) { Stream.of(services).forEach(this::addService); }
@Override @Nullable public String getService(Object key) { if(hashServices.isEmpty()) { return null; } int hashcode = getHash(key);
String service = "";
// 大于hashcode的数据,顺时针取第一个 SortedMap sortedMap = hashServices.tailMap(hashcode); if (sortedMap != null && !sortedMap.isEmpty()) { service = hashServices.get(sortedMap.firstKey()); } else { service = hashServices.get(hashServices.firstKey()); } if(service.contains(VIRTUAL_NODE_SEG)) { service = service.split(VIRTUAL_NODE_SEG)[0]; } return service; }
private int getHash(Object obj){ String str = obj.toString(); 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; }
}
复制代码


测试类:

public class Test {
public static void main(String[] args) {
// 服务器节点 String[] services = {"127.0.0.1:8080", "127.0.0.2:8080", "127.0.0.3:8080", "127.0.0.4:8080", "127.0.0.5:8080", "127.0.0.6:8080", "127.0.0.7:8080", "127.0.0.8:8080", "127.0.0.9:8080", "127.0.0.10:8080"};
// 记录每个服务器存储的数量 Map<String, Integer> count = new HashMap<>();
// 一致性hash算法 ConsistencyHash consistencyHash = new ConsistencyHashImpl(); consistencyHash.setVirtualNodeNum(150); consistencyHash.addServices(services);
// 随机数key, Random random = new Random(); for (int i = 0; i < 1000000; i++) { int data = random.nextInt(); String service = consistencyHash.getService(data);
if (count.containsKey(service)) { count.put(service, (count.get(service) + 1)); } else { count.put(service, 1); } }
System.out.println(count); }
}
复制代码


执行结果:


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

标准差计算:

//标准差σ=sqrt(s^2)    public static double standardDiviation(int[] x) {        int m=x.length;        double sum=0;        for(int i=0;i<m;i++){//求和            sum+=x[i];        }        double dAve=sum/m;//求平均值        double dVar=0;        for(int i=0;i<m;i++){//求方差            dVar+=(x[i]-dAve)*(x[i]-dAve);        }        // 平均方差开平方        return Math.sqrt(dVar/m);    }
复制代码


当虚拟节点为 150 时,标准差为:4358.570338998787

当虚拟节点为 1500 时,标准差为:2757.541114834011

当虚拟节点为 15000 时,标准差为:993.5307745611104

当虚拟节点为 150000 时,标准差为:263.4145022583229


用户头像

jizhi7

关注

还未添加个人签名 2018.09.08 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业