写点什么

架构师训练营 -W5-20200708

用户头像
丁亚宁
关注
发布于: 2020 年 07 月 08 日
架构师训练营 -W5-20200708

一、一致性 hash 算法



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

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



1、一致性hash算法介绍

直接引用知乎上介绍的比较详细的说明:

https://zhuanlan.zhihu.com/p/98030096



简单说,一致性hash算法通过一个叫作一致性hash环的数据结构实现。这个环的起点是0,终点是2^32 - 1,并且起点与终点连接,环的中间的整数按逆时针分布,故这个环的整数分布范围是[0, 2^32-1]。



一致性hash算法解决了分布式环境下机器增加或者减少时,简单的取模运算无法获取较高命中率的问题。通过虚拟节点的使用,一致性hash算法可以均匀分担机器的负载,使得这一算法更具现实的意义。



正因如此,一致性hash算法被广泛应用于分布式系统中。



2、java代码实现

package hash;

import org.apache.commons.lang3.StringUtils;

import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;



public class ConsistentHashWithVirtualNode {
//待添加入Hash环的服务器列表
private static String[] servers = {"192.168.0.0", "192.168.0.1", "192.168.0.2",
"192.168.0.3", "192.168.0.4", "192.168.0.5", "192.168.0.6", "192.168.0.7",
"192.168.0.8", "192.168.0.9"};

//真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
private static List<String> realNodes = new LinkedList<>();

//虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

//虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
private static final int VIRTUAL_NODES = 1000;

static{
//先把原始的服务器添加到真实结点列表中
for(int i=0; i<servers.length; i++) {
realNodes.add(servers[i]);
}
//再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
for (String str : realNodes){
for(int i=0; i<VIRTUAL_NODES; i++){
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = getHash(virtualNodeName);
// System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
// System.out.println();
}

//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
private static int getHash(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;
}

//得到应当路由到的结点
public String getServer(String key){
//得到该key的hash值
int hash = getHash(key);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);

String virtualNode;
if(subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = virtualNodes.firstKey();
//返回对应的服务器
virtualNode = virtualNodes.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
virtualNode = subMap.get(i);
}

//virtualNode虚拟节点名称要截取一下
if(StringUtils.isNotBlank(virtualNode)){
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}

return null;
}

}



package hash;

import java.util.HashMap;
import java.util.Map;

public class ConsistentHashTest {
//标准方差
public static double getstd(Map<String,Integer> objectnodes){
double sum = 0;
int cnt = 0;
for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){
sum += entry.getValue();
cnt++;
}
double average = sum/cnt;
int total = 0;
for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){
total += (entry.getValue() - average) *(entry.getValue() - average);
}
double standardDeviation = Math.sqrt(total/cnt);

return standardDeviation;
}

public static void main(String[] args) {

Map<String, Integer> objectNodes = new HashMap<>();

ConsistentHashWithVirtualNode nodes = new ConsistentHashWithVirtualNode();

for (int i = 1; i <= 1000000; i++) {
String nodeIp = nodes.getServer(Integer.toString(i));
Integer count = objectNodes.getOrDefault(nodeIp, 0);
objectNodes.put(nodeIp, count + 1);
}

for(Map.Entry<String, Integer> entry : objectNodes.entrySet()){
long percent = (100 * entry.getValue() / 1000000);
System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
}

//计算标准方差
System.out.println("标准方差为:"+getstd(objectNodes));
}

}



测试结果:

10台服务器,每台100个虚拟节点,数据分布不是很均匀:



10台服务器,每台1000个虚拟节点,数据分布比较均匀:



从运行结果可以看出,当虚拟节点增加到一定量后,测试时为1000,整个数据呈均匀分布状态,标准方差为4195,达到了比较理想的分布式缓存要求。



发布于: 2020 年 07 月 08 日阅读数: 40
用户头像

丁亚宁

关注

死亡骑士带你勇闯多多 2018.03.27 加入

人不狠话挺多

评论

发布
暂无评论
架构师训练营 -W5-20200708