架构师训练营第 5 周作业

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

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



测试结果输出如下：

虚拟节点数 10050 的标准差 5.792715732327589

虚拟节点数 200 的标准差 6.036923425424944

虚拟节点数 9050 的标准差 6.200358412579424

虚拟节点数 250 的标准差 6.306962642808167

虚拟节点数 2050 的标准差 6.6332495807108

虚拟节点数 7050 的标准差 7.0710678118654755

虚拟节点数 400 的标准差 7.118052168020874

虚拟节点数 450 的标准差 7.195677714974301

虚拟节点数 3050 的标准差 7.211102550927978

虚拟节点数 500 的标准差 7.453559924999299

虚拟节点数 350 的标准差 7.745966692414834

虚拟节点数 8050 的标准差 7.859884081701064

虚拟节点数 300 的标准差 8.04155872120988

虚拟节点数 550 的标准差 8.246211251235321

虚拟节点数 4050 的标准差 8.628119403696523

虚拟节点数 6050 的标准差 8.781293248212995

虚拟节点数 950 的标准差 8.94427190999916

虚拟节点数 30050 的标准差 8.96908269804914

虚拟节点数 5050 的标准差 9.055385138137417

虚拟节点数 100050 的标准差 9.899494936611665

虚拟节点数 40050 的标准差 10.011104945120804

虚拟节点数 1050 的标准差 10.044346115546242

虚拟节点数 50050 的标准差 10.055402085998905

虚拟节点数 750 的标准差 10.099504938362077

虚拟节点数 60050 的标准差 10.16530045465127

虚拟节点数 850 的标准差 10.913803695829934

虚拟节点数 20050 的标准差 11.15546702045434

虚拟节点数 90050 的标准差 11.88836966675134

虚拟节点数 150 的标准差 12.54325848148452

虚拟节点数 70050 的标准差 12.631530214330944

虚拟节点数 650 的标准差 13.824294235551815

虚拟节点数 80050 的标准差 13.888444437333106

虚拟节点数 100 的标准差 15.726834816113932

虚拟节点数 50 的标准差 16.766368453279053



代码如下：

package com.jk.test.hash;



import java.util.ArrayList;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;



public class UniformityHash {



private int nodeCount;

private int virtualNum;

List<String> serviceIpList = new ArrayList<String>();

List<String> virtualIpList = new ArrayList<String>();

TreeMap<Integer,String> serviceMap = new TreeMap<Integer,String>();

public UniformityHash(int defualNodeCount,int virtualNum , List<String> serviceIpList){

this.nodeCount = defualNodeCount;

this.virtualNum = virtualNum;

this.serviceIpList = serviceIpList;

init();

}

/**

* 初始化数据

*/

private void init()

{

if(null == serviceIpList || serviceIpList.size()==0)

{

serviceIpList = new ArrayList<String>();

String serviceIp = "192.168.0.";

for(int i=0;i<nodeCount;i++)

{

serviceIpList.add(serviceIp+(i+1));

}

}

for(String serviceIp:serviceIpList)

{

serviceMap.put(this.getHash(serviceIp), serviceIp);

for(int i=0;i<virtualNum;i++)

{

String virtualIp = serviceIp+"virtual"+i;

serviceMap.put(this.getHash(virtualIp), virtualIp);

}

}

}

/**

* 获取对应的服务器

* @param str

* @return

*/

public String getServiceIp(String str)

{

int hash = this.getHash(str);

SortedMap<Integer,String> map = serviceMap.tailMap(hash);

if(map.isEmpty())

{

return serviceMap.get(serviceMap.firstKey());

}

String virtualIp = map.get(map.firstKey());

int end = virtualIp.indexOf("virtual");

String returnStr = end> 0 ?virtualIp.substring(0, virtualIp.indexOf("virtual")):virtualIp;

if(returnStr.contains("virtual"))

{

System.out.print(returnStr);

}

return returnStr;

}



public static void main(String[] args) {

// 测试key数

int allKeyCount = 1000;

// 默认节点数

int nodeCount = 10;

// 标准差的计算

TreeMap<Double,String> standardDeviationMap = new TreeMap<Double,String>();

int virtualNum = 0;

// 测试10万虚拟节点一下的标准差

int maxvirtualNum = 100000;

while(virtualNum<maxvirtualNum)

{

// 如果节点数超过10000，一次加10000来算

if(virtualNum>10000)

{

virtualNum+= 10000;

}

// 如果节点数超过1000，一次加1000来算

else if(virtualNum>1000)

{

virtualNum+= 1000;

}

else if(virtualNum>500)

{

virtualNum+= 100;

}

// 如果节点数小于500，一次加50来算

else

{

virtualNum+= 50;

}

LinkedHashMap<String,Integer> distribution = getDistribution(allKeyCount, nodeCount, virtualNum);

double standardDeviation = standardDeviation(allKeyCount, nodeCount, virtualNum, distribution);

String virtualNumStr = standardDeviationMap.get(standardDeviation);

if(null == virtualNumStr)

virtualNumStr = "";

virtualNumStr +=" "+virtualNum;

standardDeviationMap.put(standardDeviation,virtualNumStr);

}

for( Double s : standardDeviationMap.keySet())

{

System.out.println(String.format("虚拟节点数 %s 的标准差 %s", standardDeviationMap.get(s),s));

}

System.out.println("");

}

/**

* 获取各个服务器的key数量分布

* @param allCount

* @param nodeCount

* @param virtualNum

* @return

*/

public static LinkedHashMap<String,Integer> getDistribution(int allCount,int nodeCount,int virtualNum)

{

LinkedHashMap<String,Integer> distribution = new LinkedHashMap<String,Integer>();

List<String> serviceIpList = new ArrayList<String>();

for(int i=1;i<nodeCount+1;i++)

{

String serviceIp = "192.168.0."+i;

serviceIpList.add(serviceIp);

distribution.put(serviceIp, 0);

}

UniformityHash un = new UniformityHash(nodeCount,virtualNum,serviceIpList);

String key = "懒得看聚少离多222";

for(int i=0;i<allCount;i++)

{

String s = key+i;

String serviceIp = un.getServiceIp(s);

try

{

distribution.put(serviceIp, distribution.get(serviceIp)+1);

}

catch(Exception e)

{

e.printStackTrace();

}

//System.out.println(String.format("字符串: %s 对应的服务器是：%s",s,serviceIp));

}

/* for(String s : distribution.keySet())

{

System.out.println(String.format("服务器 %s 数量 %s", s, distribution.get(s)));

}*/

return distribution;

}

/**

* 计算标准差

* @param allCount

* @param nodeCount

* @param virtualNum

* @param distribution

* @return

*/

private static double standardDeviation(int allCount,int nodeCount,int virtualNum,LinkedHashMap<String,Integer> distribution)

{

double sum = 0;

// 平均数

double avgValue = allCount/nodeCount;

for(String key :distribution.keySet())

{

sum += Math.pow(distribution.get(key)-avgValue, 2);

}

return Math.sqrt(sum/(distribution.size()-1));

}

private final static int p = 16777619;

/**

* 使用FNV132HASH

* @param str

* @return

*/

private int getHash(String str)

{

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)

return hash;

return Math.abs(hash);

}

}