写点什么

架构师训练营第五周作业

用户头像
李日盛
关注
发布于: 2020 年 11 月 22 日
架构师训练营第五周作业

问题:



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

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



解答:

一致性hash,主要解决的是在分布式的场景下面,数据路由的问题。通常的来说,由于最初版本的一致性hash在节点增加后容易导致大面积的缓存不命中,业界实际采用基于虚拟节点的改进型实现。本文基于虚拟节点实现。测试通过10个节点,每个节点生成150个虚拟节点,通过写入100W条数据,计算每个节点存储的数据量,计算不同的节点的标准差,评估实际数据的分散效果。执行结果如下截图:





本文采用的节点hash散列算法是FNV1_32_HASH,具有计算快速的特点,具体的实现类如下:


package week4;

/**
* @Description: hash code 算法集合
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class HashCodeGen {

public static int hash(String str){
return fnv32Hash(str);
}

/***
* 基于FNV1_32_HASH
* @param str
* @return
*/
private static int fnv32Hash(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;
}

/***
* 使用java默认hashCode方法
* @param str
* @return
*/
private static int defaultHash(String str){
return str.hashCode();
}

}




其中,一致性hash的实现关键在于,通过计算待写入数据的key值的hash code,在一个环形的队列里面顺时针查找离自己最近的虚拟节点。这里就涉及到一个对虚拟节点的hash code值排序和查找这样的一个实现需求。本文采用基于TreeMap的红黑树实现,实现快速查找,关键的类实现如下:

package week4;

import java.util.*;

/**
* @Description: 一致性哈希+虚拟节点实现
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class ConsistentHashingServer {

private List<ServerNode> realNodes;
private SortedMap<Integer,VirtualNode> virtualNodes = new TreeMap<>();
private final int virtualSize = 150;

public ConsistentHashingServer(){
this.realNodes = new LinkedList<>();
}

/***
* 获取key 要对应的存放服务器
* @param key
* @return
*/
public ServerNode getServer(String key){
//顺时针查找
int keyHashCode = HashCodeGen.hash(key);
SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(keyHashCode);
VirtualNode target;
if(subMap.isEmpty()){
//没有找到对应的值,取第一台服务器
int i = virtualNodes.firstKey();
target = virtualNodes.get(i);
}else{
int i = subMap.firstKey();
target = subMap.get(i);
}
// System.out.println(String.format("key:%s hash:%d -> virtual:%s",key,keyHashCode,target.getName()));
return target.getRealNode();
}

public void addServer(String serverName){
ServerNode<String,String> serverNode = new ServerNode<>(serverName,virtualSize);
realNodes.add(serverNode);
for(VirtualNode node:serverNode.getVirtualNodes()){
int hashCode = HashCodeGen.hash(node.getName());
virtualNodes.put(hashCode,node);
// System.out.println(String.format("虚拟节点[%s]被添加,hash值:%d",node.getName(),hashCode));
}
}

public List<Integer> getRealServerKeySizes(){
List<Integer> nodeKeySizes = new ArrayList<>(realNodes.size());
for(ServerNode n:realNodes){
nodeKeySizes.add(n.getKeySize());
System.out.println(String.format("node[%s],key size:%d",n.getNodeName(),n.getKeySize()));
}
return nodeKeySizes;
}

public void removeServer(String serverName){
throw new UnsupportedOperationException();
}

}


核心代码在这里:

/***
* 获取key 要对应的存放服务器
* @param key
* @return
*/
public ServerNode getServer(String key){
//顺时针查找
int keyHashCode = HashCodeGen.hash(key);
SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(keyHashCode);
VirtualNode target;
if(subMap.isEmpty()){
//没有找到对应的值,取第一台服务器
int i = virtualNodes.firstKey();
target = virtualNodes.get(i);
}else{
int i = subMap.firstKey();
target = subMap.get(i);
}
// System.out.println(String.format("key:%s hash:%d -> virtual:%s",key,keyHashCode,target.getName()));
return target.getRealNode();
}

服务节点实现类:

package week4;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
* @Description: 实际保存数据的服务节点
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class ServerNode<K,V>{

private String nodeName;
private int virtualSize;
private List<VirtualNode> virtualNodes;
private Map<K,V> keyMap = new HashMap<>();

public ServerNode(String nodeName,int virtualSize){
this.nodeName = nodeName;
this.virtualSize = virtualSize;
virtualNodes = new ArrayList<>(virtualSize);

for (int i=0;i<virtualSize;i++){
VirtualNode n = new VirtualNode(nodeName+"_"+i,this);
virtualNodes.add(n);
}
}

public List<VirtualNode> getVirtualNodes() {
return this.virtualNodes;
}

public void add(K key,V value){
this.keyMap.put(key,value);
}

public V get(K key){
return this.keyMap.get(key);
}

public int getKeySize() {
return keyMap.size();
}

public String getNodeName(){
return nodeName;
}
}


虚拟节点:

package week4;

/**
* @Description: 虚拟节点
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class VirtualNode{

private String name;
private ServerNode realNode;

public VirtualNode(String name,ServerNode realNode){
this.name = name;
this.realNode = realNode;
}

public ServerNode getRealNode() {
return this.realNode;
}

public String getName(){
return name;
}
}


辅助类,计算标准差

package week4;

/**
* @Description: 计算标准差
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class MathHelper {

private int[] numbers;

public MathHelper(int[] numbers){
this.numbers = numbers;
}

/***
* 计算标准差
*
* @return
*/
public double countStandardDeviation(){
return Math.sqrt(countVariance());
}

/***
* 计算方差
* 计算公式:方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
* @return
*/
public double countVariance(){
double var = 0;
double ave = countAverage();
for(int i=0;i<numbers.length;i++){
var += (numbers[i] - ave) * (numbers[i] - ave);
}
return var / numbers.length;
}

/***
* 计算平均值
* @return
*/
public double countAverage(){
return countSum() / numbers.length;
}

/***
* 计算总数
* @return
*/
public double countSum(){
double sum = 0;
for(int n:numbers) {
sum += n;
}
return sum;
}

}


辅助类,生成随机字符串

package week4;

import java.util.Random;

/**
* @Description: 随机生成器
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class RandomHelper {

private static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

public static String randString(int len){
StringBuffer sb = new StringBuffer();
Random random = new Random();
for (int i = 0; i < len; i++) {
sb.append(ALLCHAR.charAt(random.nextInt(ALLCHAR.length())));
}
return sb.toString();
}
}


最终代码的运行和测试类:

package week4;

import java.util.List;

/**
* @Description: TODO
* @Author: easonlee
* @CreateDate 2020/11/21
*/
public class ConsistentHashingDemo {

public static void main(String[] args) {
//创建一致性hash对象
ConsistentHashingServer server = new ConsistentHashingServer();
//增加服务器
server.addServer("192.168.1.21:8080");
server.addServer("192.168.1.22:8080");
server.addServer("192.168.1.23:8080");
server.addServer("192.168.1.24:8080");
server.addServer("192.168.1.25:8080");
server.addServer("192.168.1.26:8080");
server.addServer("192.168.1.27:8080");
server.addServer("192.168.1.28:8080");
server.addServer("192.168.1.29:8080");
server.addServer("192.168.1.30:8080");

//添加测试数据
int dataSize=1000000;
int[] keyHashDatas = new int[dataSize];
for(int i=0;i< dataSize;i++){
String key = RandomHelper.randString(10);
String value = RandomHelper.randString(12);
ServerNode serverNode = server.getServer(key);
serverNode.add(key,value);
keyHashDatas[i] = HashCodeGen.hash(key);
}
//打印并计算标准差
List<Integer> nodeKeySizes = server.getRealServerKeySizes();
MathHelper storeHelper = new MathHelper(nodeKeySizes.stream().mapToInt(k->k).toArray());

System.out.println("存储标准差:"+storeHelper.countStandardDeviation());

MathHelper keyHelper = new MathHelper(keyHashDatas);
System.out.println("原始数据标准差:"+keyHelper.countStandardDeviation());

}
}




从执行结果来看,本次的实现的效果不算太好,各个节点不算太均衡(标准差在5000左右),核心还是在于hash算法的选择。时间关系,没有尝试其他的hash算法,后续可以继续尝试不同的hash算法对结果的影响。从输入结果来看,就是输入的结果集为一个随机的结果集,如果要做横向比较,应该是采用用一套数据集,才能评估不同的hash算法实现的优劣。

发布于: 2020 年 11 月 22 日阅读数: 19
用户头像

李日盛

关注

好架构=低成本+可实现 2018.01.22 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
虚拟节点个数会显著影响标准差,可以修改看看
2020 年 11 月 29 日 11:03
回复
没有更多了
架构师训练营第五周作业