架构师训练营:第五周作业 - 一致性 hash 实现

用户头像
zcj
关注
发布于: 2020 年 07 月 08 日

作业:手动实现一致性 hash 算法



分布式一致性 hash 算法原理

  1. 有一个有序的环型hash表,hash表上记录着 服务器节点的hash值与节点的映射。

  2. 为了使服务器的节点均匀的分布在 hash环上, 在hash环上增加了一些服务器的虚拟节点,虚拟节点被访问时指向真实的节点。

  3. 当有数据存入时,存在数据的hash值对应最近的下一个节点上。如果是末尾且没有服务器节点则存在第一个服务器节点上。

  4. 当有数据访问时,按照存入的逻辑查询服务器节点访问。

  5. 当一个服务器从 hash 环删除时,仅该节点记录的数据丢失。后来的数据按照存入逻辑,存入最近节点的服务器上。

  6. 当一个新服务器节点插入到 hash 环上时。新节点与上一个服务器节点间的数据会丢失。



计算在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

编写测试用例测试这个算法,测试 100万KV 数据,10个服务器节点的情况下,计算这些KV数



实现过程

刚开始拿到这个题目时,感觉应该比较难,虽然分布式的一致性哈希算法到处有有讲解,但是却从来没有想过自己手动去编码实现。许多事情听起来觉得听懂了就会了,但是真正动手做的时候却发现不是那么简单,脑子里面连怎么做的步骤都没有个大概。

这次也是训练营作业要求去做,做的时候才发现自己眼高手低。学东西一点也没有把知识落地过。也庆幸这次作业让我认识到自己的缺点。让我明白以后该怎么去学东西。



一开始自己是没有想法的。不知道怎么去实现。虽然知道大概原理。所以还是看看大佬博客,看到一篇代码很简单的。看完后总结了几个实现分布式一致性算法的要点:

算法设计要点:



  1. 需要一个排序的hash表

  2. 找到一个hash算法,计算数据的hash值

  3. hash表访问一个key最近的下一个节点,末尾hash访问hash表的第一个节点,这样就构成hash环。



使用java语言

排序hash表使用TreeMap ,hash算法在网上搜了一下,找到一个java实现的hash算法大全类。直接拿过来用。

再往后就是编写代码了,直接上代码:



//一致性hash类。
public class ConsistentHash {
//构造hash环
public static ConsistentHashMap build(List serverNode, int virtualNodeCount,HashAlgorithm hashAlgorithm) {
ConsistentHashMap consistentHash =new ConsistentHashMap(serverNode,virtualNodeCount,hashAlgorithm);
consistentHash.initNode();
return consistentHash;
}
static class ConsistentHashMap{
/**
* 有序hash表
*/
private TreeMap<Long,String> nodeMap;
/**
* 虚拟节点数
*/
private int virtualNodeCount;
/**
* 真实的服务器
*/
private List<String> serverNode;
/**
* 使用的hash算法
*/
private HashAlgorithm hashAlgorithm;
private ConsistentHashMap(List serverNode, int virtualNodeCount, HashAlgorithm hashAlgorithm) {
this.nodeMap = new TreeMap<>();
this.serverNode=serverNode;
this.virtualNodeCount=virtualNodeCount;
this.hashAlgorithm=hashAlgorithm;
}
private void initNode() {
for (String realServer : serverNode) {
for(int i=0;i<virtualNodeCount; i++){
String virtualName = new StringBuilder(realServer).append("#vtal").append(i).toString();
nodeMap.put(hash(virtualName), virtualName);
// System.out.println("虚拟节点 : "+virtualName + "在hash环的 "+ hash(virtualName) +" 上" );
}
}
}
public String getServerNode(String key) {
long hash = hash(key);
//获取hash值对应的节点
if( nodeMap.get(hash) != null){
return getRealName(nodeMap.get(hash));
}
//获取hash值最近的节点
if ( nodeMap.higherKey(hash) != null) {
return getRealName(nodeMap.get(nodeMap.higherKey(hash)));
}
//获取首节点
if( nodeMap.firstEntry() != null){
return getRealName(nodeMap.firstEntry().getValue());
}
return null;
}
private String getRealName(String virtualNodeName) {
return virtualNodeName !=null ? virtualNodeName.substring(0,virtualNodeName.lastIndexOf("#")) : null;
}
public void addServerNode(String node) {
if (serverNode.contains(node)) {
return ;
}
serverNode.add(node);
for(int i=0;i<virtualNodeCount; i++){
String virtualName = new StringBuilder(node).append("#vtal").append(i).toString();
nodeMap.put(hash(virtualName), virtualName);
// System.out.println("虚拟节点 : "+virtualName + "在hash环的 "+ hash(virtualName) +" 上" );
}
}
public void removeServerNode(String node) {
if(!serverNode.contains(node)){
return ;
}
serverNode.remove(node);
for(int i=0;i<virtualNodeCount; i++){
String virtualName = new StringBuilder(node).append("#vtal").append(i).toString();
nodeMap.remove(hash(virtualName));
}
}
private long hash(String key) {
return hashAlgorithm.hash(key);
}
}
}



//算法接口
public interface HashAlgorithm {
int hash(String key);
}
//算法类网上找的。
//博客地址:https://www.cnblogs.com/lzl2016/p/6648259.html
public class HashAlgorithms {...}



//测试类
public class TestMain {
public static void main(String[] args) {
//测试一百万个key
int totalKeyCount=100_0000;
//真实服务器节点数
int serverCount=10;
//虚拟节点从每个服务器100个开始
int startVirtualNodeCount=100;
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::FNVHash1,"FNVHash1");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::APHash,"APHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::ELFHash,"ELFHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::DJBHash,"DJBHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::JSHash,"JSHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::RSHash,"RSHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::SDBMHash,"SDBMHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::bernstein,"bernstein");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::oneByOneHash,"oneByOneHash");
System.out.println("==============分隔==============");
testFive( totalKeyCount, serverCount, startVirtualNodeCount, HashAlgorithms::java,"java");
testOneByOneHash();
}
//进一步测试了FNH1 和 oneByone算法
public static void testOneByOneHash() {
int totalKeyCount=100_0000;
int serverCount=10;
int startVirtualNodeCount=200;
int count=40;
while(count-->0) {
test(totalKeyCount, serverCount, startVirtualNodeCount += 20, HashAlgorithms::oneByOneHash, "oneByOneHash");
}
System.out.println("==============分隔==============");
int count1=40;
startVirtualNodeCount=200;
while(count1-->0) {
test(totalKeyCount, serverCount, startVirtualNodeCount += 20, HashAlgorithms::FNVHash1, "FNVHash1");
}
}
//每次加20个虚拟节点,到200个为止
public static void testFive(int totalKeyCount, int serverCount, int virtualNodeCount,HashAlgorithm hashAlgorithm,String algorrithmName){
do{
test( totalKeyCount, serverCount, virtualNodeCount, hashAlgorithm,algorrithmName);
}while((virtualNodeCount+=20)<=200);
}
public static void test(int totalKeyCount, int serverCount, int virtualNodeCount,HashAlgorithm hashAlgorithm,String algorrithmName) {
List<String> ipList = new ArrayList<>();
Map<String, Integer> serverHodeCountMap = new HashMap<>(serverCount);
for (int i = 0; i < serverCount; i++) {
ipList.add("192.168.10." + i);
serverHodeCountMap.put("192.168.10." + i, 0);
}
ConsistentHash.ConsistentHashMap constMap = ConsistentHash.build(ipList, virtualNodeCount,hashAlgorithm);
String temp = null;
for (int j = 0; j < totalKeyCount; j++) {
temp = "testkey" + j;
String serverNode = constMap.getServerNode(temp);
// System.out.println("key : " + temp + " 被放到服务器 " + serverNode + " 中");
serverHodeCountMap.put(serverNode, serverHodeCountMap.get(serverNode) + 1);
}
double sd = calculate(serverHodeCountMap, totalKeyCount);
System.out.println(serverCount + " 个服务器,每个服务器 " + virtualNodeCount +
" 个虚拟节点,测试" + totalKeyCount + " 个key " + ",使用 "+algorrithmName+" 算法,标准差为:" + sd);
}
//计算标准差
public static double calculate(Map<String, Integer> serverHoldCountMap ,Integer totalCount) {
float average = totalCount/1.00f / serverHoldCountMap.size();
float sumAbs=0f;
for (String key : serverHoldCountMap.keySet()) {
float abs = Math.abs(average - serverHoldCountMap.get(key));
sumAbs=sumAbs+(abs*abs);
}
double sd = Math.sqrt(sumAbs/serverHoldCountMap.size());
return sd;
}
}



测试结果

10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:7827.245236991109
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:7099.085574917378
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:8407.645568171865
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:10131.300015299123
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:8603.725704600303
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:8979.737635365524
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:67049.62222115796
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:64940.375360787686
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:64940.375360787686
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:64940.375360787686
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:64940.375360787686
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 APHash 算法,标准差为:64940.375360787686
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267992.5395976537
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267989.17709489685
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267989.17709489685
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267989.17709489685
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267989.17709489685
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 ELFHash 算法,标准差为:267989.17709489685
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:267989.48277870903
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:161183.69187979284
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:161183.69187979284
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:161183.69187979284
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:161183.69187979284
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 DJBHash 算法,标准差为:161183.69187979284
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:132226.51691699363
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:94827.32298235568
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:94827.32298235568
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:94827.32298235568
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:94827.32298235568
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 JSHash 算法,标准差为:94827.32298235568
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:72489.25680402579
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:60751.637607557546
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:30929.108102239225
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:20667.90826377938
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:14537.00711976162
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 RSHash 算法,标准差为:19730.376174822417
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:61024.46774860064
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:39616.98221722599
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:39577.49016802354
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:39540.59706175414
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:39512.08017809237
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 SDBMHash 算法,标准差为:39480.806476058715
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.55811084248
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.54486071508
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.54486071508
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.54486071508
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.54486071508
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 bernstein 算法,标准差为:154564.54486071508
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:10297.258275871302
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:9278.562819747463
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:9603.46937309637
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:9576.96820502188
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:8341.963318068474
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:6953.414700706409
==============分隔==============
10 个服务器,每个服务器 100 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:154447.9991712421
10 个服务器,每个服务器 120 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:178426.9784085355
10 个服务器,每个服务器 140 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:178426.9784085355
10 个服务器,每个服务器 160 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:178426.9784085355
10 个服务器,每个服务器 180 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:178426.9784085355
10 个服务器,每个服务器 200 个虚拟节点,测试1000000 个key ,使用 java 算法,标准差为:178426.9784085355
==============进一步测试了FNH1 和 oneByone ==============
10 个服务器,每个服务器 220 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:6647.218365602262
10 个服务器,每个服务器 240 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:7060.639631081592
10 个服务器,每个服务器 260 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:5204.911910878031
10 个服务器,每个服务器 280 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4229.263765716203
10 个服务器,每个服务器 300 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3894.359639273189
10 个服务器,每个服务器 320 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3409.753803429215
10 个服务器,每个服务器 340 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4094.8197762538953
10 个服务器,每个服务器 360 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3763.944340714937
10 个服务器,每个服务器 380 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4245.543074802092
10 个服务器,每个服务器 400 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4066.4906246049554
10 个服务器,每个服务器 420 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4226.439163172706
10 个服务器,每个服务器 440 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3895.0177149789706
10 个服务器,每个服务器 460 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4233.9409537687225
10 个服务器,每个服务器 480 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4194.46015596763
10 个服务器,每个服务器 500 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4034.7909487357583
10 个服务器,每个服务器 520 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4361.705400413925
10 个服务器,每个服务器 540 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4174.968742397959
10 个服务器,每个服务器 560 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:4165.408023231337
10 个服务器,每个服务器 580 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3415.390753632738
10 个服务器,每个服务器 600 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3191.8088915221724
10 个服务器,每个服务器 620 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3004.5019553995967
10 个服务器,每个服务器 640 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:3099.8590290527727
10 个服务器,每个服务器 660 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2468.2902989721447
10 个服务器,每个服务器 680 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2067.7751328420604
10 个服务器,每个服务器 700 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2090.249985049635
10 个服务器,每个服务器 720 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2188.9753310624587
10 个服务器,每个服务器 740 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2185.621879465888
10 个服务器,每个服务器 760 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2255.019068655518
10 个服务器,每个服务器 780 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2505.3752213989824
10 个服务器,每个服务器 800 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2176.6651097493154
10 个服务器,每个服务器 820 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2488.7052858866195
10 个服务器,每个服务器 840 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2389.849053810721
10 个服务器,每个服务器 860 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:1843.2668689042289
10 个服务器,每个服务器 880 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2037.948171568649
10 个服务器,每个服务器 900 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2015.8584399704262
10 个服务器,每个服务器 920 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:1838.2526349770317
10 个服务器,每个服务器 940 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2099.445045720416
10 个服务器,每个服务器 960 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2201.576480615652
10 个服务器,每个服务器 980 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2115.3256250516138
10 个服务器,每个服务器 1000 个虚拟节点,测试1000000 个key ,使用 oneByOneHash 算法,标准差为:2331.829539224512
==============分隔==============
10 个服务器,每个服务器 220 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:7181.890001942385
10 个服务器,每个服务器 240 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:6296.052096353715
10 个服务器,每个服务器 260 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4785.64582893469
10 个服务器,每个服务器 280 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:5079.123152671138
10 个服务器,每个服务器 300 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4880.028893357087
10 个服务器,每个服务器 320 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4342.532671149406
10 个服务器,每个服务器 340 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4346.437391703693
10 个服务器,每个服务器 360 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4876.869487693924
10 个服务器,每个服务器 380 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4011.071427935434
10 个服务器,每个服务器 400 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3739.066594753295
10 个服务器,每个服务器 420 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3656.793130599542
10 个服务器,每个服务器 440 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3536.7230595566853
10 个服务器,每个服务器 460 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2912.687762188045
10 个服务器,每个服务器 480 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3105.5063999290037
10 个服务器,每个服务器 500 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3463.148278662062
10 个服务器,每个服务器 520 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2970.870747777493
10 个服务器,每个服务器 540 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3166.0535371342035
10 个服务器,每个服务器 560 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3915.715004951203
10 个服务器,每个服务器 580 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3311.018725407635
10 个服务器,每个服务器 600 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4274.6148364501805
10 个服务器,每个服务器 620 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4227.956007339717
10 个服务器,每个服务器 640 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4031.2467054250105
10 个服务器,每个服务器 660 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3488.077980779673
10 个服务器,每个服务器 680 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3719.4554708989326
10 个服务器,每个服务器 700 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:4043.8486618566726
10 个服务器,每个服务器 720 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3885.8138143765973
10 个服务器,每个服务器 740 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3534.083473830238
10 个服务器,每个服务器 760 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3637.8468906758567
10 个服务器,每个服务器 780 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3217.7350729977757
10 个服务器,每个服务器 800 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3137.4983665334394
10 个服务器,每个服务器 820 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3145.792427990124
10 个服务器,每个服务器 840 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3384.599533179664
10 个服务器,每个服务器 860 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3044.0
10 个服务器,每个服务器 880 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2831.604315578008
10 个服务器,每个服务器 900 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2585.5683127699413
10 个服务器,每个服务器 920 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2366.119925109461
10 个服务器,每个服务器 940 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2438.5143017829523
10 个服务器,每个服务器 960 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:2979.574466261919
10 个服务器,每个服务器 980 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3264.744094105999
10 个服务器,每个服务器 1000 个虚拟节点,测试1000000 个key ,使用 FNVHash1 算法,标准差为:3468.0595438948276




从测试结果总结:

  1. hash选择非常重要,有的hash算法标准差为几万,而且也不随虚拟节点增加变化。有可能这些算法设计的目的是解决hash冲突的,不是注重均匀散列分布的。或者是我使用的方式不对。

  2. FNV1Hash 算法 和 oneByone 算法表现突出,进一步测试发现 oneByone 方差更小。在不考虑算法的执行效率前提下 oneByone算法是很好的选择。



用户头像

zcj

关注

还未添加个人签名 2019.10.12 加入

精神小伙

评论

发布
暂无评论
架构师训练营:第五周作业-一致性 hash实现