写点什么

架构师训练营第 5 周作业

用户头像
Bruce Xiong
关注
发布于: 2020 年 07 月 06 日

命题

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

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



一致性Hash算法应用

一致性Hash算法主要是解决分布式场景中增加或者移除一台服务器时,对原有的服务器和服务资源之间的映射关系产生的影响最小。

一致性Hash算法原理

将整个哈希输出空间设置为一个环形区域。例如,该环形区域用数字0-2^32-1表示,沿顺时针方向值不断增大,0与2^32重合。整个哈希空间环如下:



接下来,我们将服务器进行Hash。可以使用服务器的编号或者ip等作为输入,得到一个输出值,映射在输出空间的环形区域上。

对于用户数据,同样进行Hash操作,映射在环形区域上。然后,让该值沿着顺时针方向移动,遇到的第一个服务器就是它分配的服务器。

例如有A、B、C、D四个数据对象,经过一致性哈希计算后,在环空间上的位置如下:





标准差

10个物量服务器分布情况【不均衡】

服务器:192.168.10.9,缓存数量3090

服务器:192.168.10.8,缓存数量13454

服务器:192.168.10.10,缓存数量144421

服务器:192.168.10.1,缓存数量2489

服务器:192.168.10.3,缓存数量24123

服务器:192.168.10.2,缓存数量114136

服务器:192.168.10.5,缓存数量112850

服务器:192.168.10.4,缓存数量342722

服务器:192.168.10.7,缓存数量228415

服务器:192.168.10.6,缓存数量14301

服务器数:10,结点数:10,标准差:108274.81092710345

10(物理)*100(虚拟)个节点分布情况

服务器:192.168.10.9,缓存数量81755

服务器:192.168.10.8,缓存数量123924

服务器:192.168.10.10,缓存数量98287

服务器:192.168.10.1,缓存数量91434

服务器:192.168.10.3,缓存数量106013

服务器:192.168.10.2,缓存数量109691

服务器:192.168.10.5,缓存数量102253

服务器:192.168.10.4,缓存数量119259

服务器:192.168.10.7,缓存数量90672

服务器:192.168.10.6,缓存数量76713

服务器数:10,结点数:100,标准差:14549.574629520961

通过计算每个服务器分配100-2000【每50个递增】个虚拟节点之间的标准差,120是最小值

10个服务器,每个服务器结点数:1200,标准差:1156.6812439043006

10个服务器,每个服务器结点数:1150,标准差:1257.7124870176012

10个服务器,每个服务器结点数:1250,标准差:1435.5613884470424

10个服务器,每个服务器结点数:1100,标准差:1509.881154263474

10个服务器,每个服务器结点数:1750,标准差:1866.6071091689328

10个服务器,每个服务器结点数:1700,标准差:1978.5044604448078

10个服务器,每个服务器结点数:1300,标准差:2032.681849183487

10个服务器,每个服务器结点数:1650,标准差:2064.112472710729

10个服务器,每个服务器结点数:1500,标准差:2080.7437372247455

10个服务器,每个服务器结点数:1850,标准差:2092.7501762035527

10个服务器,每个服务器结点数:1400,标准差:2099.094399973474

10个服务器,每个服务器结点数:1450,标准差:2165.7329706129517

10个服务器,每个服务器结点数:2000,标准差:2168.5971732896824

10个服务器,每个服务器结点数:1800,标准差:2251.5710737171944

10个服务器,每个服务器结点数:1900,标准差:2302.9775291999704

10个服务器,每个服务器结点数:1050,标准差:2307.9699521440916

10个服务器,每个服务器结点数:1350,标准差:2333.239229054749

10个服务器,每个服务器结点数:1000,标准差:2397.1952152463514

10个服务器,每个服务器结点数:1950,标准差:2410.568128056123

10个服务器,每个服务器结点数:1550,标准差:2505.3358457500262

10个服务器,每个服务器结点数:1600,标准差:2506.2980070215112

10个服务器,每个服务器结点数:950,标准差:3067.9444095354793

10个服务器,每个服务器结点数:900,标准差:3593.6678338433007

10个服务器,每个服务器结点数:850,标准差:4091.722412383323

10个服务器,每个服务器结点数:600,标准差:4093.7243556448693

10个服务器,每个服务器结点数:800,标准差:4322.946020944513

10个服务器,每个服务器结点数:700,标准差:4334.997820068656

10个服务器,每个服务器结点数:650,标准差:4364.490565919464

10个服务器,每个服务器结点数:750,标准差:4479.528981935489

10个服务器,每个服务器结点数:450,标准差:4498.305269765493

10个服务器,每个服务器结点数:550,标准差:4631.106314910077

10个服务器,每个服务器结点数:350,标准差:4956.882215667425

10个服务器,每个服务器结点数:500,标准差:4957.698831111063

10个服务器,每个服务器结点数:400,标准差:4988.6829825115165

10个服务器,每个服务器结点数:300,标准差:5178.060631162984

10个服务器,每个服务器结点数:250,标准差:5716.913459201564

10个服务器,每个服务器结点数:200,标准差:6676.696930369088

10个服务器,每个服务器结点数:150,标准差:7801.216719204767

10个服务器,每个服务器结点数:100,标准差:14549.574629520961

通过计算每个服务器分配1200-5000【每50个递增】个虚拟节点之间的标准差,4250是最小值

10个服务器,每个服务器结点数:4250,标准差:962.6680113102335

10个服务器,每个服务器结点数:4600,标准差:1055.0244073006083

10个服务器,每个服务器结点数:4300,标准差:1058.9868271135388

10个服务器,每个服务器结点数:3900,标准差:1080.0532857225148

10个服务器,每个服务器结点数:4450,标准差:1081.8706484603417

10个服务器,每个服务器结点数:4700,标准差:1132.8640253799217

10个服务器,每个服务器结点数:4900,标准差:1144.0028409055635

10个服务器,每个服务器结点数:3950,标准差:1155.4426424535318

10个服务器,每个服务器结点数:1200,标准差:1156.6812439043006



5000以后标准差未见明显示提升,反而还有所降低

10个服务器,每个服务器结点数:10000,标准差:1068.097795147991

10个服务器,每个服务器结点数:9950,标准差:1097.273666867113

10个服务器,每个服务器结点数:5250,标准差:1099.5312182925957

10个服务器,每个服务器结点数:9850,标准差:1102.4272765130586

10个服务器,每个服务器结点数:9900,标准差:1113.5159181619274

10个服务器,每个服务器结点数:5150,标准差:1115.6875458657769

10个服务器,每个服务器结点数:5350,标准差:1116.734211887502

10个服务器,每个服务器结点数:9800,标准差:1124.4185608571215

10个服务器,每个服务器结点数:5200,标准差:1128.8103029295933

10个服务器,每个服务器结点数:5400,标准差:1130.2348870920594

10个服务器,每个服务器结点数:5300,标准差:1146.7122132427123

10个服务器,每个服务器结点数:5100,标准差:1152.3828790814275

10个服务器,每个服务器结点数:5050,标准差:1163.9304532488186

10个服务器,每个服务器结点数:5000,标准差:1168.9286120204263



代码

package com.architect.practise5;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {

/**
* 虚拟节点
*/
private SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
public static ConsistentHash build(String[] servers, int virtual_nodes) {
return new ConsistentHash(servers,virtual_nodes);
}
private ConsistentHash(String[] servers, int virtual_nodes) {
for(String server : servers) {
for(int i=0;i<virtual_nodes;i++) {
String virtualNode = server+":"+i;
virtualNodes.put(getHash(virtualNode), virtualNode);
}
}
}
/**
* 使用FNV1_32_HASH算法计算hash值
* @param str
* @return
*/
private 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) {
int keyHash = getHash(key);
// 得到大于该Hash值的节点
SortedMap<Integer, String> tailMap = virtualNodes.tailMap(keyHash);
int nodeKey = 0;
if(!tailMap.isEmpty()) {
nodeKey = tailMap.firstKey();
}else {
nodeKey = virtualNodes.firstKey();
}
String virtualNode = virtualNodes.get(nodeKey);
return virtualNode.substring(0,virtualNode.indexOf(":"));
}

public static double StandardDiviation(Integer[] x) {
int m=x.length;
Integer sum=0;
for(int i=0;i<m;i++){//求和
sum+=x[i];
}
double dAve=sum/m;//求平均值
double dVar=0;
for(int i=0;i<m;i++){//求方差
dVar+=(x[i]-dAve)*(x[i]-dAve);
}
return Math.sqrt(dVar/m);
}


public static double test(int virtual_nodes,int serverNum ) {
//服务器被选中次数
Map<String,Integer> ServerCounter = new HashMap<String, Integer>();
String[] servers = new String[serverNum];
for(int i=1;i<=servers.length;i++) {
String node = "192.168.10."+i;
servers[i-1] = node;
ServerCounter.put(node, 0);
}

ConsistentHash hash = ConsistentHash.build(servers, virtual_nodes);
for(int i =0;i<= 1000000;i++) {
String server = hash.getServer(String.valueOf(i));
int count = ServerCounter.get(server);
ServerCounter.put(server, count+1);
}
Integer[] Counter = new Integer[serverNum];
int index =0;
for (Entry<String, Integer> entry : ServerCounter.entrySet()) {
//System.out.println("服务器:"+entry.getKey()+",缓存数量"+entry.getValue());
Counter[index] = entry.getValue();
index++;
}
double sd = ConsistentHash.StandardDiviation(Counter);

return sd;
}

public static void main(String[] args) {
SortedMap<Double, Integer> standardDiv = new TreeMap<Double, Integer>();
for(int j=1200;j<= 5000;j+=50) {
standardDiv.put(test(j,10),j);
}
standardDiv.forEach((key,value) -> {
System.out.println("10个服务器,每个服务器结点数:" + value + ",标准差:"+key);
});
}
}




用户头像

Bruce Xiong

关注

熊大 2017.10.18 加入

还未添加个人简介

评论

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