2020-07-04- 第五周作业

发布于: 2020 年 07 月 08 日

作业

答:

1 一致性hash算法实现

一致性hash算法步骤

(1)使用hash算法计算出10个物理服务器结点对应的虚拟节点hashcode,并将这些虚拟节点尽量均匀分布在hash环上。

(2)同样使用hash算法,计算KV数据中键的hashcode,并其映射到hash环上。

(3)从数据映射hash环的位置开始顺时针查找,找到一个虚拟节点,要求该节点的hashcode大于等于KV数据中键的hashcode。

(4)找到该虚拟节点对应的物理服务器节点,并将该KV数据存储到该物理节点上。

一致性hash算法实现(JAVA)

代码清单1:ConsistencyHash.java

一致性算法实现类,构造方法有三个输入:hashcode算法,物理节点列表,每个物理节点的虚拟节点个数。包括了添加和删除物理节点方法,以及getNode通过KV中键的值获需要存储的物理节点对象。

package demo.algorithm;
import demo.hash.HashMethod;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* 一致性hash算法
* @param <T>
*/
public class ConsistencyHash<T> {
private Collection nodes;
private HashMethod hashMethod;
private int virtualNodesCount;
/**
* hash环上的虚拟节点
*/
private SortedMap<Integer, T> hashRing = new TreeMap<>();
/**
* 构造方法
* @param hashMethod hash算法
* @param nodes 物理节点集合
* @param virtualNodesCount 单个物理节点在hash环上的虚拟节点个数
*/
public ConsistencyHash(HashMethod hashMethod, Collection<T> nodes, int virtualNodesCount){
this.hashMethod = hashMethod;
this.virtualNodesCount = virtualNodesCount;
for(T n : nodes) {
addNode(n);
}
}
/**
* 添加节点
* @param node 节点对象
*/
public void addNode(T node) {
for(int i = 0; i < virtualNodesCount; i++) {
hashRing.put(hashMethod.hash(i + "#" +node.toString() + "#" + i), node);
}
}
/**
* 删除节点
* @param node 待删除结点
*/
public void removeNode(T node) {
for (int i = 0; i < virtualNodesCount; i++) {
hashRing.remove(hashMethod.hash(node.toString() + i));
}
}
/**
* 获取物理节点
* @param key 键
* @return
*/
public T getNode(Object key) {
int hash = hashMethod.hash(key);
for(int c : hashRing.keySet()) {
if(hash <= c) {
return hashRing.get(c);
}
}
return hashRing.get(hashRing.firstKey());
}
}

代码清单2:Md5HashMethod.java

使用MD5算法计算出对象的hashcode,因hashcode可能为负数,使用了Integer.MAX_VALUE进行与操作去除符号。

package demo.hash;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class Md5HashMethod implements HashMethod {
@Override
public int hash(Object obj) {
byte[] secretBytes = null;
try {
secretBytes = MessageDigest.getInstance("md5").digest(
obj.toString().getBytes());
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("没有这个md5算法!");
}
String md5code = new BigInteger(1, secretBytes).toString(16);
return md5code.hashCode() & Integer.MAX_VALUE;
}
}

代码清单3:Node.java

package demo.node;
public class Node {
String nodeName;
public Node(String nodeName) {
this.nodeName = nodeName;
}
public String toString() {
return this.nodeName;
}
}

2 测试算法的负载均衡性

代码清单4:Main.java

Main.main方法使用Md5Hash算法计算hashcode,resMap记录每个节点上存储的KV个数。使用10个物理节点,每个物理节点有80个虚拟节点。最终打印出每个物理节点上存储的KV个数,并计算样本的标准差。

package demo;
import demo.algorithm.ConsistencyHash;
import demo.hash.HashMethod;
import demo.hash.Md5HashMethod;
import demo.hash.NormalHashMethod;
import demo.node.Node;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
HashMethod hashMethod = new Md5HashMethod();
Map<Node, Integer> resMap = new LinkedHashMap<>();
List<Node> nodes = new ArrayList<>();
for(int i = 0; i < 10; i++) {
String nodeName = i + "NODE" + i;
Node n = new Node(nodeName);
nodes.add(n);
resMap.put(n, 0);
}
ConsistencyHash<Node> consistencyHash = new ConsistencyHash(hashMethod, nodes, 80);
IntStream.range(0, 1000000).forEach(idx -> {
Node n = consistencyHash.getNode(idx);
resMap.put(n, resMap.get(n) + 1);
});
// 计算标准差
int avg = 100000;
int temp = 0;
for(Node n: resMap.keySet()) {
System.out.println(n.toString() + " : " + resMap.get(n));
temp += (resMap.get(n) - avg) * (resMap.get(n) - avg);
}
int s = temp / 10;
System.out.println("方差:" + s);
System.out.println("标准差:" + Math.sqrt(s));
}
}

实验结果

0NODE0 : 101213
1NODE1 : 92116
2NODE2 : 104745
3NODE3 : 102025
4NODE4 : 103392
5NODE5 : 90734
6NODE6 : 99023
7NODE7 : 97158
8NODE8 : 104955
9NODE9 : 104639
方差:24271273
标准差:4926.588373306623

一致性hash算法最重要的核心就是要保证虚拟节点hashCode的均衡性。只要虚拟机结点在hash环上是均匀分布的,那就可以保证这些KV数据就能均匀分布在这10个服务器节点上,其标准差就会很小。

而影响算法均衡性的一个最主要因素就是hash函数。hash函数的主要作用就是将虚拟节点和KV数据的key值尽量均匀分布在hash环上,注意是尽量均匀分布。实际上由于hash函数的不均衡性,以及KV数据的随机性,想要将hashCode均匀分布是较难的。

根据不同的场景hash函数也有所不同,主要的有:直接定址法、数字分析法、折叠法、平方取中法、减去法、基数转换法、除留余数法、随机数法、字符串数值hash法、旋转法等。

除了需要构造hash函数外,hash冲突也是需要解决的一个问题,尽可能的将hash冲突减少到最低。

用户头像

路易斯李李李

关注

还未添加个人签名 2020.05.11 加入

还未添加个人简介

评论

发布
暂无评论
2020-07-04-第五周作业