架构师训练营第 5 周作业

关注
发布于: 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);
		});	
			
		
		
	}
}
﻿
﻿
发布于: 2020 年 07 月 06 日阅读数: 56
Bruce Xiong

关注
熊大 2017.10.18 加入
还未添加个人简介
发布
暂无评论
创作场景

架构师训练营第 5 周作业

命题

一致性Hash算法应用

一致性Hash算法原理

标准差

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

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

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

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

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

代码

Bruce Xiong

评论
