第五周作业 - 一致性 hash 实现

发布于: 2020 年 07 月 08 日

作业

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

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

代码

package interview.hash;
import java.util.*;
public class ConsistentHash {
//一致性hash简单实现
//1 确定区间值
//2 节点散列到区间值(物理节点+虚拟节点,虚拟节点解决数据倾斜不均匀(1 本身节点散列不均匀;2 添加删除节点不均匀))
//3 元素散列到区间值
//4 顺时针获取下一个节点位置
//虚拟节点的个数,经验:物理节点个位数时,每个物理节点160个虚拟节点时,数据会分散很平均
//上述实现原理中, 元素散列比节点散列频繁的多,即读多写少, 使用链表维护区间值圆环效率不高,二叉树查找非常适合,使用TreeMap-红黑树,按照key排序,查找效率高
//物理节点数
private List<String> nodes = null;
//所有节点(虚拟+物理)
private SortedMap<Long,String> allVirutualNodes = null;
private int virtual = 100;
public ConsistentHash(String []nodeNames){
this.nodes= new ArrayList<>(Arrays.asList(nodeNames));
this.refreshHashCircle();
}
/**
* 刷新hash Circle
*/
public void refreshHashCircle(){
if(allVirutualNodes ==null){
allVirutualNodes = new TreeMap<>();
}else{
allVirutualNodes.clear();
}
for(String node:nodes){
for(int i=0;i<virtual;i++){
String nn = "pn"+node+"&&vn"+i;
long hash = HashUtil.getHash(nn);
allVirutualNodes.put(hash,node);
}
}
}
/**
* 添加节点
* @param nodeName
*/
public void addNode(String nodeName){
nodes.add(nodeName);
this.refreshHashCircle();
}
/**
* 删除节点
* @param nodeName
*/
public void removeNode(String nodeName) {
Iterator<String> iterator = nodes.iterator();
while(iterator.hasNext()){
String sss = iterator.next();
if(sss.equals(nodeName))
iterator.remove();
}
this.refreshHashCircle();
}
/**
* 获取节点
* @param key
* @return
*/
public String getNode(String key){
long hash = HashUtil.getHash(key);
SortedMap<Long,String> subMap = allVirutualNodes.tailMap(hash);
if(subMap==null||subMap.isEmpty()){
return allVirutualNodes.get(allVirutualNodes.firstKey());
}
String s = subMap.get(subMap.firstKey());
return s;
}
}

package interview.hash;
public class HashUtil {
/**
* FNV1_32_HASH算法
* @param value
* @return
*/
public static int getHash(String value){
final int p = 16777619;
int result = (int) 2166136261L;
for (int i = 0; i < value.length(); i++) {
result = (result ^ value.charAt(i)) * p;
}
result += result << 13;
result ^= result >> 7;
result += result << 3;
result ^= result >> 17;
result += result << 5;
return Math.abs(result);
}
}

package interview.hash;
import java.util.*;
public class Test {
public static void main(String []args){
Map<String, Integer> hitMap = new HashMap<>();
List<String> nodes = new ArrayList<>();
int countNode = 10;
for (int i = 0; i < countNode; i++) {
String node = "192.168.1." + i+8080;
nodes.add(node);
hitMap.put(node,0);
}
ConsistentHash consistentHash = new ConsistentHash(nodes);
long startTime = System.currentTimeMillis();
int countKV = 1000000;
for (int i = 0; i < countKV; i++) {
String uuid = UUID.randomUUID().toString();
String node = consistentHash.getNode(uuid);
int count = hitMap.get(node);
hitMap.put(node, ++count);
}
for (Map.Entry<String, Integer> entry : hitMap.entrySet()) {
System.out.println(entry.toString());
}
System.out.println("--------------------------------------------------------");
long spentTime = System.currentTimeMillis() - startTime;
System.out.println(String.format("spent %s ms", spentTime));
int averageHit = countKV / countNode;
double temp = hitMap.values().stream().map(value -> Math.pow((value - averageHit), 2)).reduce(0.0, (s, e) -> s = s + e);
double standardDeviation = Math.sqrt(temp/countNode);
System.out.println("方差:standardDeviation: " + standardDeviation);
}
}

测试结果:

192.168.1.68080=91903

192.168.1.08080=108726

192.168.1.58080=98863

192.168.1.78080=90922

192.168.1.48080=92488

192.168.1.18080=110332

192.168.1.28080=98565

192.168.1.38080=87911

192.168.1.98080=107800

192.168.1.88080=112490

--------------------------------------------------------

spent 4614 ms

方差:standardDeviation: 8681.19203796345

用户头像

netbanner

关注

还未添加个人签名 2017.10.17 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业 - 一致性 hash 实现