架构师训练营第 1 期第 5 周作业

用户头像
业哥
关注
发布于: 2020 年 10 月 20 日
架构师训练营第 1 期第 5 周作业



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

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



解:上面2个题通过java语言来实现如下:

先上类图:

  • 上面类图中,先定义了一致性hash算法的接口类,需要实现5个方法:

  1. 添加服务节点

  2. 移除服务节点

  3. 根据kv的key值活得命中的服务器节点

  4. fnv1_32_hash的hashcode算法的实现

  5. 获取服务节点存储kv值的个数的标准差

  • 定义一个抽象类AbstractHash,实现共同方法fnv1_32_hash();

  • 最后实现2种一致性hash算法的实现类

  1. 常用的一致性hash算法

  2. 加入虚拟服务器节点的一致性hash算法

  • 最后有一个main主程序进行测试



接着上代码如下:

接口类Hash:

package org.yege.algorithm.hash;
/**
* Hash算法接口
*/
public interface Hash {
/**
* 添加服务器节点
* @param nodeName
*/
public void addServerNode(String nodeName);
/**
* 移除服务器节点
* @param nodeName
*/
public void removeServerNode(String nodeName);
/**
* 根据key值获取命中的服务器节点名称
* @param key
* @return
*/
public String getServerNodeByKey(String key);
/**
* fnv1_32_hash算法
* @param str
* @return
*/
public Integer fnv1_32_hash(String str);
/**
* 计算服务器节点命中的标准差
* @return
*/
public double getStandardDeviation();
}

抽象类AbstractHash:

package org.yege.algorithm.hash;
public abstract class AbstractHash implements Hash {
/**
* 使用FNV1_32_HASH算法
*/
public Integer fnv1_32_hash(String str) {
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;
}
}



实现类1:一致性hash算法(不带虚拟节点)

package org.yege.algorithm.hash;
import java.util.*;
/**
* 一致性hash算法(不带虚拟节点)
*/
public class ConsistentHash extends AbstractHash{
private SortedMap<Integer,String> sortedMap=new TreeMap<Integer, String>();//真实服务器hash值和真实服务器对应关系的Map
private Map<String,Long> serverNodeHasKeys=new HashMap<String, Long>();//真实服务器存储key的个数计数器
public void addServerNode(String nodeName) {
int serverNodeHashCode=fnv1_32_hash(nodeName);
sortedMap.put(serverNodeHashCode,nodeName);
}
public void removeServerNode(String nodeName) {
int serverNodeHashCode=fnv1_32_hash(nodeName);
if(sortedMap.containsKey(serverNodeHashCode)){
sortedMap.remove(serverNodeHashCode);
serverNodeHasKeys.remove(nodeName);
}
}
public String getServerNodeByKey(String key) {
//得到该key的hash值
int hash = fnv1_32_hash(key);
//得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(subMap.isEmpty()){
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
String serverNode=sortedMap.get(i);
if(serverNodeHasKeys.containsKey(serverNode)){
Long l=serverNodeHasKeys.get(serverNode);
serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
}else {
serverNodeHasKeys.put(serverNode,Long.valueOf(1));
}
return serverNode;
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
String serverNode=subMap.get(i);
if(serverNodeHasKeys.containsKey(serverNode)){
Long l=serverNodeHasKeys.get(serverNode);
serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
}else {
serverNodeHasKeys.put(serverNode,Long.valueOf(1));
}
return serverNode;
}
}
/**
* 计算服务器节点命中的标准差
* @return
*/
public double getStandardDeviation(){
Set<String> servers=serverNodeHasKeys.keySet();
for(String serverNode:servers){
System.out.println("服务节点【"+serverNode+"】存储keys数量:"+serverNodeHasKeys.get(serverNode));
}
Collection<Long> longs =serverNodeHasKeys.values();
Long[] array= new Long[longs.size()];
longs.toArray(array);
int sum = 0;
for(int i=0;i<array.length;i++){
sum += array[i]; //求出数组的总和
}
double average = sum/array.length; //求出数组的平均数
int total=0;
for(int i=0;i<array.length;i++){
total += (array[i]-average)*(array[i]-average); //求出方差,如果要计算方差的话这一步就可以了
}
double standardDeviation = Math.sqrt(total/array.length); //求出标准差
return standardDeviation;
}
}



实现类2:一致性hash算法(带虚拟节点)

package org.yege.algorithm.hash;
import java.util.*;
/**
* 一致性hash算法(加入虚拟节点)
*/
public class ConsistentAndVirtualNodeHash extends AbstractHash{
private SortedMap<Integer,String> sortedMap=new TreeMap<Integer, String>();//虚拟服务器hash值和虚拟服务器对应关系的Map
private Map<String,Long> serverNodeHasKeys=new HashMap<String, Long>();//真实服务器存储key的个数计数器
public static int VIRTUAL_NODES=150;//虚拟节点个数
private String separator="$$";//真实服务器和虚拟服务器字分隔符,通过这个分隔符可以快速从虚拟服务器得到真实服务器节点
public void addServerNode(String nodeName) {
for(int i=1;i<=VIRTUAL_NODES;i++){
//$$为真实服务器与虚拟服务器的分隔符,得到虚拟服务器名称,可以快速获取真实服务器名称
int serverNodeHashCode=fnv1_32_hash(nodeName+separator+i);
sortedMap.put(serverNodeHashCode,nodeName);
}
}
public void removeServerNode(String nodeName) {
for(int i=1;i<=VIRTUAL_NODES;i++){
int serverNodeHashCode=fnv1_32_hash(nodeName+separator+i);
if(sortedMap.containsKey(serverNodeHashCode)){
sortedMap.remove(serverNodeHashCode);
}
}
serverNodeHasKeys.remove(nodeName);
}
public String getServerNodeByKey(String key) {
//得到该key的hash值
int hash = fnv1_32_hash(key);
//得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(subMap.isEmpty()){
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
String virtualServerNode=sortedMap.get(i);//这里获取的是虚拟节点
String serverNode=virtualServerNode.split(separator)[0];//得到真实节点
if(serverNodeHasKeys.containsKey(serverNode)){
Long l=serverNodeHasKeys.get(serverNode);
serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
}else {
serverNodeHasKeys.put(serverNode,Long.valueOf(1));
}
return serverNode;//返回真实节点
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
String virtualServerNode=subMap.get(i);//这里获取的是虚拟节点
String serverNode=virtualServerNode.split(separator)[0];//得到真实节点
if(serverNodeHasKeys.containsKey(serverNode)){
Long l=serverNodeHasKeys.get(serverNode);
serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
}else {
serverNodeHasKeys.put(serverNode,Long.valueOf(1));
}
return virtualServerNode.split(separator)[0];
}
}
/**
* 计算服务器节点命中的标准差
* @return
*/
public double getStandardDeviation(){
Set<String> servers=serverNodeHasKeys.keySet();
for(String serverNode:servers){
System.out.println("服务节点【"+serverNode+"】存储keys数量:"+serverNodeHasKeys.get(serverNode));
}
Collection<Long> longs =serverNodeHasKeys.values();
Long[] array= new Long[longs.size()];
longs.toArray(array);
int sum = 0;
for(int i=0;i<array.length;i++){
sum += array[i]; //求出数组的总和
}
double average = sum/array.length; //求出数组的平均数
int total=0;
for(int i=0;i<array.length;i++){
total += (array[i]-average)*(array[i]-average); //求出方差,如果要计算方差的话这一步就可以了
}
double standardDeviation = Math.sqrt(total/array.length); //求出标准差
return standardDeviation;
}
}



测试主程序:

package org.yege.algorithm.hash;
/**
* 主程序
*/
public class HashMain {
public static void main(String[] args) {
String[] serverNodes=new String[]{
"192.168.1.1"
,"192.168.1.2"
,"192.168.1.3"
,"192.168.1.4"
,"192.168.1.5"
,"192.168.1.6"
,"192.168.1.7"
,"192.168.1.8"
,"192.168.1.9"
,"192.168.1.10"};
System.out.println("1.【一致性hash算法_不加入虚拟节点】100万kv数据量测试情况:");
Hash hash=new ConsistentHash();
for(String serverNode:serverNodes){
hash.addServerNode(serverNode);
}
for(int key=1;key<=1000000;key++){
hash.getServerNodeByKey(Integer.toString(key));
}
double sd=hash.getStandardDeviation();
System.out.println("标准差:"+sd);
System.out.println("--------------------------------------------");
System.out.println("2.【一致性hash算法_加入虚拟节点】100万kv数据量测试情况:");
Hash hash1=new ConsistentAndVirtualNodeHash();
for(String serverNode:serverNodes){
hash1.addServerNode(serverNode);
}
for(int key=1;key<=1000000;key++){
hash1.getServerNodeByKey(Integer.toString(key));
}
double sd1=hash1.getStandardDeviation();
System.out.println("标准差:"+sd1);
}
}



最后测试结果:



最终结论:

根据测试结果,在同样数据量级(100w)下KV 数据在服务器上分布数量的标准差方面加了虚拟节点的一致性hash算法会更小,表示其在存储负载均衡性方面更好。



用户头像

业哥

关注

架构即未来! 2018.02.19 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 1 期第 5 周作业