架构师训练营 - 作业 - 第五周
发布于: 2020 年 10 月 25 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
一致性Hash算法实现
package love.luke.architect.demo;import java.util.LinkedList;import java.util.List;import java.util.TreeMap;import java.util.UUID;import java.util.Map.Entry;import lombok.extern.slf4j.Slf4j;@Slf4jpublic class ConsistentHashRouter { /** * 虚拟节点的放大比例,真实节点数:虚拟节点数 = 1:virtualTime */ private int virtualTimes; /** * 真实节点的IP清单列表,真实节点的位置餐宿格式为ip:prot */ private String[] serversIp; /** * 由serversIps 真实节点的IP清单列表转换而来的List, 后续便于增删 */ private List<String> realNodes; /** * 虚拟节点构成的哈希环,使用TreeMap,后续查找节点方便 */ private TreeMap<Integer, String> virtualNodes; public ConsistentHashRouter(int virtualTimes, String[] serversIp) { if (null == serversIp || serversIp.length == 0) throw new IllegalArgumentException("输入服务器清单不能为空"); this.serversIp= serversIp; this.virtualTimes = virtualTimes; realNodes = new LinkedList<String>(); for(String ip : serversIp ) { realNodes.add(ip); } //为每个固定节点,生成哈希环上的虚拟节点 virtualNodes = new TreeMap<Integer, String>(); for(String realNode : realNodes) { for (int i=0; i<virtualTimes; i++) { // 采用随机UUID的hash为虚拟节点位置 int key = getHash(UUID.randomUUID().toString()); virtualNodes.put(key, realNode); } } } /** * 计算输入字符串对应的hash值 * @param str * @return 哈希值 */ private int getHash(String str) { // 先暂时使用内置的Hash算法,后续可以更换算法以达到更好的效果 return str.hashCode(); } /** * 根据传入的Key,得到对应的实际服务节点 * @param key * @return */ public synchronized String getServer(String key) { // 计算查询Key的hash int hashOfKey = getHash(key); // 在哈希环上向后找到大于查询Key的hash 的最近的一个虚拟节点 Entry<Integer, String> entry = virtualNodes.ceilingEntry(hashOfKey); // 因为是哈希环,所以当向后上找不到比当前查询Key hash大的节点,则循环返回第一个虚拟节点 if (null == entry) { entry = virtualNodes.firstEntry(); } return entry.getValue(); } /** * 增加实际真实节点 * @param newServerIp */ public synchronized void addServer(String newServerIp) { realNodes.add(newServerIp); for (int i=0; i<virtualTimes; i++) { int key = getHash(UUID.randomUUID().toString()); virtualNodes.put(key, newServerIp); } }}
测试用例
import static org.junit.Assert.*;import java.util.HashMap;import java.util.UUID;import java.util.Map.Entry;import love.luke.architect.demo.ConsistentHashRouter;import org.junit.Test;public class ConsistentHashRouterTest { @Test public void test() { final int TEST_CASE_AMOUNT = 1000000; String seversIp[] = { "10.0.0.0", "10.0.0.1", "10.0.0.2", "10.0.0.3", "10.0.0.4", "10.0.0.5", "10.0.0.6", "10.0.0.7", "10.0.0.8", "10.0.0.9" }; // 10个实体服务器,每个服务器对应100个虚拟节点 ConsistentHashRouter router = new ConsistentHashRouter(10, seversIp); // 计数器,统计每个真实Server被命中的次数 HashMap<String, Long> counterMap = new HashMap<>(); // 随机生成100万个UUID作为key进行测试,记录分实际存储节点被命中选取出来的数量 for (int i = 0; i < TEST_CASE_AMOUNT; i++) { String key = UUID.randomUUID().toString(); String ip = router.getServer(key); Long counter = counterMap.get(ip); if (counter == null) counterMap.put(ip, 1L); else counterMap.put(ip, counter + 1); } // 计算10个实际节点被命中次数的方差 long sum = 0; double average = 0; for (Entry<String, Long> counterEntry : counterMap.entrySet()) { System.out.println(counterEntry.getKey() + " :" + counterEntry.getValue()); sum = sum + counterEntry.getValue(); } average = sum / counterMap.keySet().size() ; System.out.println("average:" + average); double deviation = 0; for (Entry<String, Long> counterEntry : counterMap.entrySet()) { deviation = deviation + Math.pow(counterEntry.getValue() - average, 2); } System.out.println("Standard Deviation:" + Math.sqrt(deviation/counterMap.keySet().size())); }}
测试结果
当 实际节点:虚拟节点 = 1:10, 测试结果如下
10.0.0.8 :10695410.0.0.7 :5314310.0.0.9 :10601810.0.0.4 :8517910.0.0.3 :10944210.0.0.6 :10004710.0.0.5 :8772410.0.0.0 :15159110.0.0.2 :12880110.0.0.1 :71101Standard Deviation:26581.8542656452
当 实际节点:虚拟节点 = 1:100, 测试结果如下。 标准差明显变小,数据分布更加均匀了
10.0.0.8 :10617610.0.0.7 :10455310.0.0.9 :8119010.0.0.4 :9923810.0.0.3 :9370310.0.0.6 :11249110.0.0.5 :10302510.0.0.0 :9141210.0.0.2 :10129310.0.0.1 :106919average:100000.0Standard Deviation:8610.433194677256
划线
评论
复制
发布于: 2020 年 10 月 25 日 阅读数: 20
Max2@12
关注
还未添加个人签名 2018.12.13 加入
还未添加个人简介
评论