架构师训练营 Week5 作业
发布于: 2020 年 07 月 08 日
一致性hash算法及java实现
一致性hash算法是分布式中一个常用且好用的分片算法、或者数据库分库分表算法。现在的互联网服务架构中,为避免单点故障、提升处理效率、横向扩展等原因,分布式系统已经成为了居家旅行必备的部署模式,所以也产出了几种数据分片的方法:
取模
划段
一致性hash
前两种有很大的一个问题就是需要固定的节点数,即节点数不能变,不能某一个节点挂了或者实时增加一个节点,变了分片规则就需要改变,需要迁移的数据也多。
那么一致性hash是怎么解决这个问题的呢?
一致性hash:对节点和数据,都做一次hash运算,然后比较节点和数据的hash值,数据值和节点最相近的节点作为处理节点。为了分布得更均匀,通过使用虚拟节点的方式,每个节点计算出n个hash值,均匀地放在hash环上这样数据就能比较均匀地分布到每个节点
通过学习做了一个简单的实现:
package me.lichun.homework.week5;import java.util.HashMap;import java.util.Map;import java.util.SortedMap;import java.util.TreeMap;/** * 一致性hash算法 * </br> * 重点:1.如何造一个hash环,2.如何在哈希环上映射服务器节点,3.如何找到对应的节点 * * @author: lichun * @date: 2020/7/8 */public class ConsistentHashingWithoutNode { //待添加入Hash环的服务器列表,10个服务节点 private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111", "192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111" }; //key表示服务器的hash值,value表示服务器 private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); //程序初始化,将所有的服务器放入sortedMap中 static { for (int i=0; i<servers.length; i++) { int hash = getHash(servers[i]); System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash); sortedMap.put(hash, servers[i]); } System.out.println(); } //得到应当路由到的结点 private static String getServer(String key) { //得到该key的hash值 int hash = getHash(key); //得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = sortedMap.tailMap(hash); if(subMap.isEmpty()){ //如果没有比该key的hash值大的,则从第一个node开始 Integer i = sortedMap.firstKey(); //返回对应的服务器 return sortedMap.get(i); }else{ //第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); //返回对应的服务器 return subMap.get(i); } } //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 private static 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 static void main(String[] args) { long node0Count = 0L; long node1Count = 0L; long node2Count = 0L; long node3Count = 0L; long node4Count = 0L; long node5Count = 0L; long node6Count = 0L; long node7Count = 0L; long node8Count = 0L; long node9Count = 0L; // 模拟100W的KV数据 Map<String, String> testMap = new HashMap<>(); for(int i=0; i< 1000000; i++) { testMap.put("key" + i, "value" + i); } for(Map.Entry<String, String> entry : testMap.entrySet()) { String mapStr = entry.getKey() + ":" + entry.getValue(); String nodeStr = getServer(mapStr); if (servers[0].equals(nodeStr)){ node0Count++; } if (servers[1].equals(nodeStr)){ node1Count++; } if (servers[2].equals(nodeStr)){ node2Count++; } if (servers[3].equals(nodeStr)){ node3Count++; } if (servers[4].equals(nodeStr)){ node4Count++; } if (servers[5].equals(nodeStr)){ node5Count++; } if (servers[6].equals(nodeStr)){ node6Count++; } if (servers[7].equals(nodeStr)){ node7Count++; } if (servers[8].equals(nodeStr)){ node8Count++; } if (servers[9].equals(nodeStr)){ node9Count++; } } System.out.println("[" + "服务节点" + servers[0] + "路由到的个数为:" + String.valueOf(node0Count) +"]"); System.out.println("[" + "服务节点" + servers[1] + "路由到的个数为:" + String.valueOf(node1Count) +"]"); System.out.println("[" + "服务节点" + servers[2] + "路由到的个数为:" + String.valueOf(node2Count) +"]"); System.out.println("[" + "服务节点" + servers[3] + "路由到的个数为:" + String.valueOf(node3Count) +"]"); System.out.println("[" + "服务节点" + servers[4] + "路由到的个数为:" + String.valueOf(node4Count) +"]"); System.out.println("[" + "服务节点" + servers[5] + "路由到的个数为:" + String.valueOf(node5Count) +"]"); System.out.println("[" + "服务节点" + servers[6] + "路由到的个数为:" + String.valueOf(node6Count) +"]"); System.out.println("[" + "服务节点" + servers[7] + "路由到的个数为:" + String.valueOf(node7Count) +"]"); System.out.println("[" + "服务节点" + servers[8] + "路由到的个数为:" + String.valueOf(node8Count) +"]"); System.out.println("[" + "服务节点" + servers[9] + "路由到的个数为:" + String.valueOf(node9Count) +"]"); }}
执行结果:
[192.168.0.0:111]加入集合中, 其Hash值为1767802393[192.168.0.1:111]加入集合中, 其Hash值为406441873[192.168.0.2:111]加入集合中, 其Hash值为800212117[192.168.0.3:111]加入集合中, 其Hash值为475180206[192.168.0.4:111]加入集合中, 其Hash值为514183420[192.168.0.5:111]加入集合中, 其Hash值为854676609[192.168.0.6:111]加入集合中, 其Hash值为995851316[192.168.0.7:111]加入集合中, 其Hash值为1193712218[192.168.0.8:111]加入集合中, 其Hash值为987443045[192.168.0.9:111]加入集合中, 其Hash值为441056192[服务节点192.168.0.0:111路由到的个数为:267494][服务节点192.168.0.1:111路由到的个数为:365524][服务节点192.168.0.2:111路由到的个数为:133545][服务节点192.168.0.3:111路由到的个数为:16077][服务节点192.168.0.4:111路由到的个数为:18135][服务节点192.168.0.5:111路由到的个数为:25427][服务节点192.168.0.6:111路由到的个数为:3796][服务节点192.168.0.7:111路由到的个数为:92054][服务节点192.168.0.8:111路由到的个数为:61949][服务节点192.168.0.9:111路由到的个数为:15999]
通过对比发现数据通过一致性hash算法,存在着负载不均衡的情况,这个怎么解决?需要我们后续在学习,再总结
划线
评论
复制
发布于: 2020 年 07 月 08 日 阅读数: 29
平淡人生
关注
还未添加个人签名 2018.11.05 加入
还未添加个人简介
评论