第五周·命题作业·一致性 hash

发布于: 2020 年 07 月 09 日
第五周·命题作业·一致性hash

一致性hash:对节点和数据,都做一次hash运算,然后比较节点和数据的hash值,数据值和节点最相近的节点作为处理节点。为了分布得更均匀,通过使用虚拟节点的方式,每个节点计算出n个hash值,均匀地放在hash环上这样数据就能比较均匀地分布到每个节点。

1.不使用虚拟节点

10个服务器节点。标准差测试结果104881.

class HashCircle {
SortedMap<Long,VirtualNode> hashTree;
List<String> serverList;
HashCircle() {
serverList = Arrays.asList("192.168.1.10","192.168.1.11","192.168.1.12","192.168.1.13","192.168.1.14"
,"192.168.1.15","192.168.1.16","192.168.1.17","192.168.1.18","192.168.1.19");
hashTree = new TreeMap<>();
List<Long> nodeCursorList = new ArrayList<>();
int index =0;
for (String serverIp :serverList) {
long hashValue = googleHash(serverIp);
nodeCursorList.add(hashValue);
hashTree.put(hashValue, new VirtualNode("node" + index++));
}
nodeCursorList = nodeCursorList.stream().sorted().collect(Collectors.toList());
int kvCount = 1000000;
for (int i = 0; i < kvCount; i++) {
long kvHashValue = googleHash(UUID.randomUUID().toString());
int hitCursor = 0;
for (int j = nodeCursorList.size() -1;j > -1;j-- ) {
if (kvHashValue > nodeCursorList.get(j)) {
if (j != nodeCursorList.size() - 1) {
hitCursor = j + 1;
}
break;
}
}
VirtualNode nodeCursor = hashTree.get(nodeCursorList.get(hitCursor));
nodeCursor.setHitTimes(nodeCursor.getHitTimes() + 1);
}
System.out.println(hashTree.size());
}
Double getStandardDeviation(){
double sum = 0d ;
for (Long key:hashTree.keySet()) {
VirtualNode nodeCursor = hashTree.get(key);
sum += Math.pow(nodeCursor.getHitTimes() - 100000,2);
}
return Math.sqrt(sum/10);
}
private int googleHash(String s){
HashFunction hashFunction = Hashing.murmur3_128(31);
return Math.abs(hashFunction.hashString(s, Charsets.UTF_8).hashCode());
}

2.使用虚拟节点

10个服务器

每台服务器100个虚拟节点:标准差测试结果8211

public class HashCircleWithVirtualNode {
SortedMap<Integer,VirtualNode> vnMap;
List<String> serverList;
int kvCount ;
public HashCircleWithVirtualNode(int kvCount) {
this.kvCount = kvCount;
buildTreeMap();
}
private String getVirtualNode(String key) {
int hashValue = googleHash(key);
SortedMap<Integer, VirtualNode> subMap = vnMap.tailMap(hashValue);
VirtualNode virtualNode;
if (subMap.isEmpty()) {
virtualNode = vnMap.get(vnMap.firstKey());
} else {
virtualNode = subMap.get(subMap.firstKey());
}
return virtualNode.getType().substring(0, virtualNode.getType().indexOf("#"));
}
public Map<String,Integer> getKvDistribution() {
Map<String, Integer> serverIpMap = new HashMap<>();
for (int i = 0; i < kvCount; i++) {
String key = RandomStringUtils.randomAlphabetic(6); //UUID.randomUUID().toString();
String ip = getVirtualNode(key);
if (serverIpMap.containsKey(ip)) {
serverIpMap.replace(ip, serverIpMap.get(ip) + 1);
} else {
serverIpMap.put(ip, 1);
}
}
return serverIpMap;
}
private void buildTreeMap() {
serverList = new ArrayList<>();
for(int i = 1;i<11;i++) {
for (int j = 1; j < 101; j++) {
serverList.add("192.168.1." + i + "#VN" + j);
}
}
vnMap = new TreeMap<>();
for (String serverIp :serverList) {
int hashValue = googleHash(serverIp);
vnMap.put(hashValue, new VirtualNode(serverIp));
}
}
private int googleHash(String s){
HashFunction hashFunction = Hashing.murmur3_32();
return Math.abs(hashFunction.hashString(s, Charsets.UTF_8).hashCode());
}
}

用户头像

刘璐

关注

还未添加个人签名 2018.03.29 加入

还未添加个人简介

评论

发布
暂无评论
第五周·命题作业·一致性hash