架构师训练营第五周作业

发布于: 2020 年 07 月 07 日

1.作业内容:

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

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

2.Hash算法

背景: 分布式缓存中为了把数据缓存在不同的机器中,采用hash算法计算数据缓存在哪台机器上。

简单求余法:

hash(名称) ->得到hash值 ,取模机器总数 -> 得到余数 。

hash(名称) % 机器总数 = 余数 (0,1,2 为机器编号)

如:有3台机器 , 6 %3 = 0 ,此时存储为机器编号为0 的服务器。

问题:随着业务的增长,原有的3台服务器无法处理业务,需要增加服务器,这时取模的机器总数发生变化,hash(名称)%机器总数 得到的余数都会发生变化,导致用户的请求穿透缓存,有可能造成雪崩效应。

2.1 简单一致性hash:

简单求余法的问题是由于分母发生了变化,导致求余变化很大。解决这个问题方法:

  • 构造一个Hash环,这个环有一个范围:[0,2^32-1]

  • 服务器分布在hash环上

  • 顺时针选择找到最近的服务器节点

2.2带虚拟节点的一致性hash

简单一致性hash存在问题:有可能存在hash倾斜,特别是在节点较少的时候,导致节点分布数据不均。

究其原因主要是服务器节点太少,此时可以在每个服务器节点上增加虚拟节点,这样数据会更加均匀分布

3.带虚拟节点的一致性hash实现java版本

3.1 java代码

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
/**
* 一致性hash
*/
public class ConsistentHash {
//默认虚拟节点为100个
private int virtualCount = 150;
//虚拟机节点map
private SortedMap<Integer, String> virtualNodeMap;
//物理节点集合
private List<String> physicalNodes;
//访问物理节点map
HashMap<String, Integer> visitPhysicalNodeMap;
/**
* 默认
*/
public ConsistentHash() {
this(150);
}
/**
* 虚拟节点个数
*
* @param virtualCount
*/
public ConsistentHash(int virtualCount) {
virtualNodeMap = new TreeMap<>();
physicalNodes = new ArrayList<>();
this.virtualCount = virtualCount;
visitPhysicalNodeMap = new HashMap<>();
}
/**
* 增加物理节点
*
* @param nodeName
*/
public void addPhysicalNode(String nodeName) {
if (!physicalNodes.contains(nodeName)) {
physicalNodes.add(nodeName);
for (int i = 0; i < virtualCount; i++) {
Integer hasKey = hash(String.format("%s#%d", nodeName, i));
virtualNodeMap.put(hasKey, nodeName);
}
visitPhysicalNodeMap.put(nodeName, 0);
}
}
/**
* 删除物理节点
*
* @param nodeName
*/
public void removePhysicalNode(String nodeName) {
if (physicalNodes.contains(nodeName)) {
physicalNodes.remove(nodeName);
for (int i = 0; i < virtualCount; i++) {
Integer hasKey = hash(String.format("%s#%d", nodeName, i));
virtualNodeMap.remove(hasKey);
}
visitPhysicalNodeMap.remove(nodeName);
}
}
/**
* 根据查找key值,计算hash值,找到虚拟机节点map对应的物理节点
*
* @param key
* @return
*/
public String findPhysicalNode(String key) {
if (key != null && !key.trim().equals("")) {
SortedMap<Integer, String> sortedMap = virtualNodeMap.tailMap(hash(key));
String node = virtualNodeMap.get(sortedMap.isEmpty() ? virtualNodeMap.firstKey() : sortedMap.firstKey());
//每次查询到物理节点,统计结果+1
visitPhysicalNodeMap.put(node, visitPhysicalNodeMap.get(node) + 1);
return node;
} else
return key;
}
/**
* 计算标准差
* 计算标准差 = (每个样本 - 平均值)的平方之和 / (服务器节点数) ,所得结果,再取平方
* sqrt(((x1-x)^2 +(x2-x)^2 +......(xn-x)^2)/n )
*
* @param keyCount
* @return
*/
public long calculateStdDeviation(int keyCount) {
long average = keyCount / physicalNodes.size();
AtomicLong variance = new AtomicLong();
visitPhysicalNodeMap.forEach((k, v) -> {
variance.addAndGet((long) Math.pow((v - average), 2));
System.out.println(String.format("服务器【%s】访问次数 %d", k, v));
});
return Math.round(Math.sqrt(variance.get() / physicalNodes.size()));
}
/**
* 清空所有数据集
*/
public void clear() {
virtualNodeMap.clear();
physicalNodes.clear();
visitPhysicalNodeMap.clear();
}
/**
* 改进的32位FNV算法1
*
* @param data
* @return
*/
private Integer hash(String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
}

3.2 测试

public static void main(String[] args){
long start = System.currentTimeMillis();
ConsistentHash consistentHash = new ConsistentHash(200);
consistentHash.addPhysicalNode("192.168.10.1:200");
consistentHash.addPhysicalNode("192.168.10.2:200");
consistentHash.addPhysicalNode("192.168.10.3:200");
consistentHash.addPhysicalNode("192.168.10.4:200");
consistentHash.addPhysicalNode("192.168.10.5:200");
consistentHash.addPhysicalNode("192.168.10.6:200");
consistentHash.addPhysicalNode("192.168.10.7:200");
consistentHash.addPhysicalNode("192.168.10.8:200");
consistentHash.addPhysicalNode("192.168.10.9:200");
consistentHash.addPhysicalNode("192.168.10.10:200");
int count = 100 * 10000;
Random random = new Random();
for (int j = 0; j < count; j++) {
String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
StringBuilder builder = new StringBuilder(20);
for (int i = 0; i < 20; i++) {
int index = random.nextInt(62);
builder.append(str.charAt(index));
}
consistentHash.findPhysicalNode(builder.toString());
}
long end = System.currentTimeMillis();
System.out.println(String.format("耗时%d毫秒",end-start));
System.out.println(String.format("方差:%d",consistentHash.calculateStdDeviation(count)));
}

测试结果

服务器【192.168.10.3:200】访问次数 126141

服务器【192.168.10.8:200】访问次数 97350

服务器【192.168.10.10:200】访问次数 89805

服务器【192.168.10.4:200】访问次数 95551

服务器【192.168.10.1:200】访问次数 107829

服务器【192.168.10.2:200】访问次数 107829

服务器【192.168.10.5:200】访问次数 93207

服务器【192.168.10.6:200】访问次数 101394

服务器【192.168.10.7:200】访问次数 87768

服务器【192.168.10.9:200】访问次数 93126

虚拟节点数为100,耗时785毫秒,标准差 10870

服务器【192.168.10.3:200】访问次数 111825

服务器【192.168.10.8:200】访问次数 99247

服务器【192.168.10.10:200】访问次数 91439

服务器【192.168.10.4:200】访问次数 108092

服务器【192.168.10.1:200】访问次数 90069

服务器【192.168.10.2:200】访问次数 96686

服务器【192.168.10.5:200】访问次数 102422

服务器【192.168.10.6:200】访问次数 113257

服务器【192.168.10.7:200】访问次数 91410

服务器【192.168.10.9:200】访问次数 95553

虚拟节点数为150,耗时810毫秒,标准差 8148

服务器【192.168.10.3:200】访问次数 98071

服务器【192.168.10.8:200】访问次数 104672

服务器【192.168.10.10:200】访问次数 88723

服务器【192.168.10.4:200】访问次数 104110

服务器【192.168.10.1:200】访问次数 107501

服务器【192.168.10.2:200】访问次数 95459

服务器【192.168.10.5:200】访问次数 96658

服务器【192.168.10.6:200】访问次数 103252

服务器【192.168.10.7:200】访问次数 97112

服务器【192.168.10.9:200】访问次数 104442

虚拟节点数为200,耗时843毫秒,标准差 5443

服务器【192.168.10.3:200】访问次数 102557

服务器【192.168.10.8:200】访问次数 102260

服务器【192.168.10.10:200】访问次数 91153

服务器【192.168.10.4:200】访问次数 100059

服务器【192.168.10.1:200】访问次数 108038

服务器【192.168.10.2:200】访问次数 95165

服务器【192.168.10.5:200】访问次数 93560

服务器【192.168.10.6:200】访问次数 99982

服务器【192.168.10.7:200】访问次数 98598

服务器【192.168.10.9:200】访问次数 108628

虚拟节点数为250,耗时886毫秒,标准差 5439

服务器【192.168.10.3:200】访问次数 105785

服务器【192.168.10.8:200】访问次数 103633

服务器【192.168.10.10:200】访问次数 90542

服务器【192.168.10.4:200】访问次数 99422

服务器【192.168.10.1:200】访问次数 102858

服务器【192.168.10.2:200】访问次数 103862

服务器【192.168.10.5:200】访问次数 93047

服务器【192.168.10.6:200】访问次数 94685

服务器【192.168.10.7:200】访问次数 98349

服务器【192.168.10.9:200】访问次数 107817

虚拟节点数为300,耗时921毫秒,标准差 5477

服务器【192.168.10.3:200】访问次数 102463

服务器【192.168.10.8:200】访问次数 97554

服务器【192.168.10.10:200】访问次数 94648

服务器【192.168.10.4:200】访问次数 101188

服务器【192.168.10.1:200】访问次数 101373

服务器【192.168.10.2:200】访问次数 102278

服务器【192.168.10.5:200】访问次数 100418

服务器【192.168.10.6:200】访问次数 96870

服务器【192.168.10.7:200】访问次数 96980

服务器【192.168.10.9:200】访问次数 106228

虚拟节点数为350,耗时961毫秒,标准差 3272

4.总结

根据测试的结果,分析虚拟节点数、耗时和标准差得到在虚拟节点数为200比较合适。

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

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

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