写点什么

架构师训练营第五周作业

用户头像
丁乐洪
关注
发布于: 2020 年 11 月 21 日

1 一致性 hash 算法

参考网上,hash 算法没有深究

public class ConsistencyHash {
private TreeMap<Long, NodeDefine> nodes; // 虚拟节点
private List<NodeDefine> shards; // 真实机器节点
private final int NODE_NUM = 150; // 每个机器节点关联的虚拟节点个数
public ConsistencyHash(List<NodeDefine> shards) { super(); this.shards = shards; init(); }
private void init() { // 初始化一致性hash环 nodes = new TreeMap<Long, NodeDefine>(); for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点 final NodeDefine shardInfo = shards.get(i);
for (int n = 0; n < NODE_NUM; n++) // 一个真实机器节点关联NODE_NUM个虚拟节点 nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo);
} }
public NodeDefine getShardInfo(String key) { SortedMap<Long, NodeDefine> tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点 if (tail.size() == 0) { return nodes.get(nodes.firstKey()); } return tail.get(tail.firstKey()); // 返回该虚拟节点对应的真实机器节点的信息 } }
复制代码

关键是这个 TreeMap


2 测试

测试一下负载的均衡性

 public static void main(String[] args) {        List<NodeDefine> shards = new ArrayList<>();        for (int i=1;i<=10;i++){            NodeDefine nodeDefine1 = new NodeDefine("node"+i);            shards.add(nodeDefine1);        }
for (int i=50;i<200;i+=10){ calSD(shards,i); }
}
private static void calSD(List<NodeDefine> shards, int virNum) { ConsistencyHash hashGeneroTools = new ConsistencyHash(shards,virNum);
NodeDefine nodeDefine = hashGeneroTools.getShardInfo("test003");
Map<NodeDefine,Integer> hits = new HashMap<>();
for (int i=0;i<10000000;i++){ nodeDefine = hashGeneroTools.getShardInfo("test"+i); if (i%100000 ==0) { //System.out.println(nodeDefine); }
hits.put(nodeDefine, hits.get(nodeDefine)==null?1:hits.get(nodeDefine)+1); }

Integer[] nums = hits.values().toArray(new Integer[0]); double sd = calculateSD(nums);
System.out.println(virNum +"->" +sd); }

public static double calculateSD(Integer numArray[]) { double sum = 0.0, standardDeviation = 0.0; int length = numArray.length;
for(double num : numArray) { sum += num; }
double avg = sum/length;
for(double num: numArray) { standardDeviation += Math.pow(num - avg, 2); }
return Math.sqrt(standardDeviation/length-1); }
复制代码


方差:50->16118.15430500651460->16659.85493334200570->11781.38368783565280->7230.94148780087990->7634.385829914545100->7226.703660729419110->5370.755775493799120->8509.62398699261130->5219.742733123922140->5433.480541973073150->5587.672436261333160->4252.703399015737170->3883.7512021240495180->4519.301848737258190->5608.920876603627
复制代码

从我这边测试结果,虚拟节点数大于 80,结果接近


3 第五周心得

编程是架构师的基本功,有技术才能说服他人。

用户头像

丁乐洪

关注

还未添加个人签名 2018.10.11 加入

还未添加个人简介

评论

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