写点什么

极客时间架构师培训 1 期 - 第 5 周作业

用户头像
Kaven
关注
发布于: 2020 年 10 月 25 日
  1. 用你熟悉的编程语言实现一致性 hash 算法。

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


如下为源码,还请老师指正


/** * CacheNode.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
/** * <p> * ClassName: CacheNode * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class CacheNode {
private String name; // 节点Name
private String ip; // 节点IP
private String port; // 端口
private Long numCache; // Cache存储数量
public CacheNode(String strName, String strIp, String StrPort) { name = strName; ip = strIp; port = StrPort; numCache = 0L; }
public void addNumCache(){ numCache++; return; }

public Long getNumCache(){ return numCache; }
public String getNodeCacheKey() { return this.name + "-" + this.ip + "-" + this.port; }
@Override public String toString() { return "CacheNode{" + "name='" + name + '\'' + ", ip='" + ip + '\'' + ", port='" + port + '\'' + ", numCache=" + numCache + '}'; }}
复制代码


/** * HashUtils.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.io.UnsupportedEncodingException;import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;
/** * <p> * ClassName: HashUtils * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class HashUtils { public static Long hash(String nodeName, int number) { byte[] digest = md5(nodeName); return (((long) (digest[3 + number * 4] & 0xFF) << 24) | ((long) (digest[2 + number * 4] & 0xFF) << 16) | ((long) (digest[1 + number * 4] & 0xFF) << 8) | (digest[number * 4] & 0xFF)) & 0xFFFFFFFFL; }
/** * md5加密 * * @param str * @return */ public static byte[] md5(String str) { try { MessageDigest md = MessageDigest.getInstance("MD5"); md.reset(); md.update(str.getBytes("UTF-8")); return md.digest(); } catch (NoSuchAlgorithmException e) { e.printStackTrace(); return null; } catch (UnsupportedEncodingException e) { e.printStackTrace(); return null; } }

public static double standardDeviation(Long[] x) { int m = x.length; double 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); }}
复制代码


/** * ConsistentHashLoadBalance.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.io.UnsupportedEncodingException;import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;import java.util.LinkedList;import java.util.Map;import java.util.TreeMap;
/** * <p> * ClassName: ConsistentHashLoadBalance * </p> * <p> * Description: Hash算法 * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class ConsistentHashLoadBalance {
//虚拟节点 private TreeMap<Long, CacheNode> virtualNodes = new TreeMap<>();
//真实节点 private LinkedList<CacheNode> nodes;
//每个真实节点对应的虚拟节点数 private final int replicCnt;
public ConsistentHashLoadBalance(LinkedList<CacheNode> nodes, int replicCnt){ this.nodes = nodes; this.replicCnt = replicCnt; initalization(); }
/** * 初始化哈希环 * 循环计算每个node名称的哈希值,将其放入treeMap */ private void initalization(){ for (CacheNode node: nodes) { for (int i = 0; i < replicCnt/4; i++) { String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i); for (int j = 0; j < 4; j++) { virtualNodes.put(HashUtils.hash(virtualNodeName, j), node); } } } }
private String getNodeNameByIndex(String nodeName, int index){ return new StringBuffer(nodeName) .append("&&") .append(index) .toString(); } /** * 根据资源key选择返回相应的节点名称 * @param key * @return 节点名称 */ public CacheNode selectNode(String key){ Long hashOfKey = HashUtils.hash(key, 0); if (!virtualNodes.containsKey(hashOfKey)) { Map.Entry<Long, CacheNode> entry = virtualNodes.ceilingEntry(hashOfKey); if (entry != null) { return entry.getValue(); } else { return nodes.getFirst(); } } else { return virtualNodes.get(hashOfKey); } }
public void addNode(CacheNode node){ nodes.add(node); for (int i = 0; i < replicCnt/4; i++) { String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i); for (int j = 0; j < 4; j++) { virtualNodes.put(HashUtils.hash(virtualNodeName, j), node); } } }
public void removeNode(CacheNode node){ nodes.remove(node); for (int i = 0; i < replicCnt/4; i++) { String virtualNodeName = getNodeNameByIndex(node.getNodeCacheKey(), i); for (int j = 0; j < 4; j++) { virtualNodes.remove(HashUtils.hash(virtualNodeName, j), node); } } }
public void printTreeNode(){ if (virtualNodes != null && ! virtualNodes.isEmpty()){ virtualNodes.forEach((hashKey, node) -> System.out.println( new StringBuffer(node.toString()) .append(" ==> ") .append(hashKey) ) ); } else { System.out.println("Cycle is Empty"); }
}

}
复制代码


/** * ConsistentHashLoadBalanceMain.java * Created at 2020-10-25 * Created by LiKai * Copyright (C) 2020 SAIC VOLKSWAGEN, All rights reserved. */package com.hash;
import java.util.HashMap;import java.util.LinkedList;
/** * <p> * ClassName: ConsistentHashLoadBalanceMain * </p> * <p> * Description: TODO * </p> * <p> * Author: LiKai * </p> * <p> * Date: 2020-10-25 * </p> */public class ConsistentHashLoadBalanceMain { public static void main(String[] args){ LinkedList<CacheNode> nodes = new LinkedList<>(); nodes.add(new CacheNode("node1", "192.168.13.1", "8080")); nodes.add(new CacheNode("node1", "192.168.13.2", "8080")); nodes.add(new CacheNode("node1", "192.168.13.3", "8080")); nodes.add(new CacheNode("node1", "192.168.13.4", "8080"));
ConsistentHashLoadBalance consistentHash = new ConsistentHashLoadBalance(nodes, 150); System.out.print("初始化后缓存信息:"); consistentHash.printTreeNode(); long startTime=System.currentTimeMillis(); //100W数据加入测试 for (int n = 0; n < 1000000; n++) {
String key = String.format("%f", Math.random());// key 选择 CacheNode keyHash = consistentHash.selectNode(key); //找到加++ keyHash.addNumCache(); } System.out.print("测试数据入缓存后信息:"); consistentHash.printTreeNode(); long endTime=System.currentTimeMillis(); double std = 0; double avg =100000; Long[] ccArray = new Long[nodes.size()]; for (int i = 0; i < nodes.size(); i++) { CacheNode node = nodes.get(i); ccArray[i] = node.getNumCache(); //System.out.println(" 节点:" + i +" 缓存个数: " + (node.GetNumCache()) ); }
System.out.println(" 节点个数:" + nodes.size() +" 100万次查找算法程序运行时间: " + (endTime - startTime ) + "ms" +" 标准差:" + HashUtils.standardDeviation(ccArray));
}
}
复制代码


用户头像

Kaven

关注

还未添加个人签名 2019.04.13 加入

还未添加个人简介

评论

发布
暂无评论
极客时间架构师培训 1 期 - 第 5 周作业