一致性 hash 的 Java 代码实现
发布于: 2020 年 07 月 08 日
一致性hash算法是分布式中一个常用且好用的分片算法、或者数据库分库分表算法。现在的互联网服务架构中,为避免单点故障、提升处理效率、横向扩展等原因,分布式系统已经成为了居家旅行必备的部署模式,所以也产出了几种数据分片的方法:
1.取模,2.划段,3.一致性hash
前两种有很大的一个问题就是需要固定的节点数,即节点数不能变,不能某一个节点挂了或者实时增加一个节点,变了分片规则就需要改变,需要迁移的数据也多。
那么一致性hash是怎么解决这个问题的呢?
一致性hash:对节点和数据,都做一次hash运算,然后比较节点和数据的hash值,数据值和节点最相近的节点作为处理节点。为了分布得更均匀,通过使用虚拟节点的方式,每个节点计算出n个hash值,均匀地放在hash环上这样数据就能比较均匀地分布到每个节点。
package hash; import java.util.SortedMap; import java.util.TreeMap; /** * 不带虚拟节点的一致性Hash算法 * 重点:1.如何造一个hash环,2.如何在哈希环上映射服务器节点,3.如何找到对应的节点 */ public class ConsistentHashingWithoutVirtualNode { //待添加入Hash环的服务器列表 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" }; //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) { String[] keys = {"太阳", "月亮", "星星"}; for(int i=0; i<keys.length; i++) System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]"); } }
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 91
叶鹏
关注
还未添加个人签名 2018.09.25 加入
还未添加个人简介
评论