一致性哈希算法学习及JAVA代码实现分析

简介:

1,对于待存储的海量数据,如何将它们分配到各个机器中去?---数据分片与路由

当数据量很大时,通过改善单机硬件资源的纵向扩充方式来存储数据变得越来越不适用,而通过增加机器数目来获得水平横向扩展的方式则越来越流行。因此,就有个问题,如何将这些海量的数据分配到各个机器中?数据分布到各个机器存储之后,又如何进行查找?这里主要记录一致性Hash算法如何将数据分配到各个机器中去。

 

2,衡量一致性哈希算法好处的四个标准:

①平衡性:平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。②单调性:单调性是指如果已经有一些数据通过哈希分配到了相应的机器上,又有新的机器加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的机器中去,而不会被映射到旧的机器集合中的其他机器上。

这里再解释一下:就是原有的数据要么还是呆在它所在的机器上不动,要么被迁移到新的机器上,而不会迁移到旧的其他机器上。

③分散性④负载参考这里

 

3,一致性哈希的原理:

由于一般的哈希函数返回一个int(32bit)型的hashCode。因此,可以将该哈希函数能够返回的hashCode表示成一个范围为0---(2^32)-1 环。

将机器的标识(如:IP地址)作为哈希函数的Key映射到环上。如:

hash(Node1) =Key1      hash(Node2) = Key2,借用一张图如下:

 

 

 同样,数据也通过相同的哈希函数映射到环上。这样,按照顺时针方向,数据存放在它所在的顺时针方向上的那个机器上。这就是一致性哈希算法分配数据的方式!

 

4,JAVA实现一致性哈希算法的代码分析:

设计哈希函数

这里采用了MD5算法,主要是用来保证平衡性,即能够将机器均衡地映射到环上。貌似用Jdk中String类的hashCode并不能很好的保证平衡性。

复制代码
 1 import java.security.MessageDigest;
 2 import java.security.NoSuchAlgorithmException;
 3 
 4 /*
 5  * 实现一致性哈希算法中使用的哈希函数,使用MD5算法来保证一致性哈希的平衡性
 6  */
 7 public class HashFunction {
 8     private MessageDigest md5 = null;
 9 
10     public long hash(String key) {
11         if (md5 == null) {
12             try {
13                 md5 = MessageDigest.getInstance("MD5");
14             } catch (NoSuchAlgorithmException e) {
15                 throw new IllegalStateException("no md5 algrithm found");
16             }
17         }
18 
19         md5.reset();
20         md5.update(key.getBytes());
21         byte[] bKey = md5.digest();
22         //具体的哈希函数实现细节--每个字节 & 0xFF 再移位
23         long result = ((long) (bKey[3] & 0xFF) << 24)
24                 | ((long) (bKey[2] & 0xFF) << 16
25                         | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF));
26         return result & 0xffffffffL;
27     }
28 }
复制代码

 

实现一致性哈希算法:

为什么要引入虚拟机器节点?它的作用是什么?

引入虚拟机器节点,其目的就是为了解决数据分配不均衡的问题。因为,在将实际的物理机器映射到环上时,有可能大部分机器都映射到环上的某一个部分(比如左半圆上),而通过引入虚拟机器节点,在进行机器hash映射时,不是映射具体机器,而是映射虚拟机器,并保证虚拟机器对应的物理机器是均衡的---每台实际的机器对应着相等数目的Virtual nodes。如下图:

 

 

如何解决集群中添加或者删除机器上需要迁移大量数据的问题?

假设采用传统的哈希取模法,设有K台物理机,H(key)=hash(key) mod K 即可实现数据分片。但当K变化时(如新增一台机器),所有已经映射好的数据都需要重新再映射。H(key)=hash(key) mod (K+1)。

一致性哈希采用的做法如下:引入一个环的概念,如上面的第一个图。先将机器映射到这个环上,再将数据也通过相同的哈希函数映射到这个环上,数据存储在它顺时针走向的那台机器上。以环为中介,实现了数据与机器数目之间的解藕。这样,当机器的数目变化时,只会影响到增加或删除的那台机器所在的环的邻接机器的数据存储,而其他机器上的数据不受影响。

 

在具体JAVA实现代码中,定义了一个TreeMap<k, V>用来保存虚拟机器节点到实际的物理机器的映射。机器以字符串形式来标识,故hash函数的参数为String

复制代码
1 for (int i = 0; i < numberOfReplicas; i++)
2             // 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
3             /*
4              * 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
5              * 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
6              */
7             circle.put(hashFunction.hash(node.toString() + i), node);
复制代码

 

而对于 数据的存储而言,逻辑上是按顺时针方向存储在虚拟机器节点中,虚拟机器节点通过TreeMap知道它实际需要将数据存储在哪台物理机器上。此外,TreeMap中的Key是有序的,而环也是顺时针有序的,这样才能当数据被映射到两台虚拟机器之间的弧上时,通过TreeMap的 tailMap()来寻找顺时针方向上的下一台虚拟机。

1     if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
2             SortedMap<Long, T> tailMap = circle.tailMap(hash);
3             hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
4         }

 

 完整代码:

复制代码
 1 import java.util.Collection;
 2 import java.util.HashSet;
 3 import java.util.Iterator;
 4 import java.util.Set;
 5 import java.util.SortedMap;
 6 import java.util.SortedSet;
 7 import java.util.TreeMap;
 8 import java.util.TreeSet;
 9 
10 public class ConsistentHash<T> {
11     private final HashFunction hashFunction;
12     private final int numberOfReplicas;// 节点的复制因子,实际节点个数 * numberOfReplicas =
13                                         // 虚拟节点个数
14     private final SortedMap<Long, T> circle = new TreeMap<Long, T>();// 存储虚拟节点的hash值到真实节点的映射
15 
16     public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
17             Collection<T> nodes) {
18         this.hashFunction = hashFunction;
19         this.numberOfReplicas = numberOfReplicas;
20         for (T node : nodes)
21             add(node);
22     }
23 
24     public void add(T node) {
25         for (int i = 0; i < numberOfReplicas; i++)
26             // 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
27             /*
28              * 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
29              * 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
30              */
31             circle.put(hashFunction.hash(node.toString() + i), node);
32     }
33 
34     public void remove(T node) {
35         for (int i = 0; i < numberOfReplicas; i++)
36             circle.remove(hashFunction.hash(node.toString() + i));
37     }
38 
39     /*
40      * 获得一个最近的顺时针节点,根据给定的key 取Hash
41      * 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点
42      * 再从实际节点中取得 数据
43      */
44     public T get(Object key) {
45         if (circle.isEmpty())
46             return null;
47         long hash = hashFunction.hash((String) key);// node 用String来表示,获得node在哈希环中的hashCode
48         if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
49             SortedMap<Long, T> tailMap = circle.tailMap(hash);
50             hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
51         }
52         return circle.get(hash);
53     }
54 
55     public long getSize() {
56         return circle.size();
57     }
58     
59     /*
60      * 查看MD5算法生成的hashCode值---表示整个哈希环中各个虚拟节点位置
61      */
62     public void testBalance(){
63         Set<Long> sets  = circle.keySet();//获得TreeMap中所有的Key
64         SortedSet<Long> sortedSets= new TreeSet<Long>(sets);//将获得的Key集合排序
65         for(Long hashCode : sortedSets){
66             System.out.println(hashCode);
67         }
68         
69         System.out.println("----each location 's distance are follows: ----");
70         /*
71          * 查看用MD5算法生成的long hashCode 相邻两个hashCode的差值
72          */
73         Iterator<Long> it = sortedSets.iterator();
74         Iterator<Long> it2 = sortedSets.iterator();
75         if(it2.hasNext())
76             it2.next();
77         long keyPre, keyAfter;
78         while(it.hasNext() && it2.hasNext()){
79             keyPre = it.next();
80             keyAfter = it2.next();
81             System.out.println(keyAfter - keyPre);
82         }
83     }
84     
85     public static void main(String[] args) {
86         Set<String> nodes = new HashSet<String>();
87         nodes.add("A");
88         nodes.add("B");
89         nodes.add("C");
90         
91         ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 2, nodes);
92         consistentHash.add("D");
93         
94         System.out.println("hash circle size: " + consistentHash.getSize());
95         System.out.println("location of each node are follows: ");
96         consistentHash.testBalance();
97     }
98     
99 }
复制代码

 

 

参考资料:五分钟理解一致性哈希算法(consistent hashing)

 一致性hash算法 - consistent hashing

一致性哈希算法介绍,及java实现

本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/,如需转载请自行联系原作者


 

目录
打赏
0
0
0
0
56
分享
相关文章
银行流水生成器在线制作,银行转账p图在线生成,java实现最牛的生成器【仅供学习用途】
本资料探讨银行系统核心技术,涵盖交易记录生成、电子回单加密验真及基于Java的财务管理系统开发。主要内容包括:交易记录实体类设计(不可变性与数字签名)
Java 大视界 -- Java 大数据在智能教育学习社区用户互动分析与社区活跃度提升中的应用(274)
本文系统阐述 Java 大数据技术在智能教育学习社区中的深度应用,涵盖数据采集架构、核心分析算法、活跃度提升策略及前沿技术探索,为教育数字化转型提供完整技术解决方案。
java 入门学习视频_2025 最新 java 入门零基础学习视频教程
《Java 21 入门实操指南(2025年版)》提供了Java最新特性的开发指导。首先介绍了JDK 21和IntelliJ IDEA 2025.1的环境配置,包括环境变量设置和预览功能启用。重点讲解了Java 21三大核心特性:虚拟线程简化高并发编程,Record模式优化数据解构,字符串模板提升字符串拼接可读性。最后通过图书管理系统案例,展示如何运用Record定义实体类、使用Stream API进行数据操作,以及结合字符串模板实现控制台交互。该指南完整呈现了从环境搭建到实际项目开发的Java 21全流程实
38 1
Java 从入门到实战完整学习路径与项目实战指南
本文详细介绍了“Java从入门到实战”的学习路径与应用实例,涵盖基础、进阶、框架工具及项目实战四个阶段。内容包括环境搭建、语法基础、面向对象编程,数据结构与算法、多线程并发、JVM原理,以及Spring框架等核心技术。通过学生管理系统、文件下载器和博客系统等实例,帮助读者将理论应用于实践。最后,提供全链路电商系统的开发方案,涉及前后端技术栈与分布式架构。附代码资源链接,助力成为合格的Java开发者。
44 4
|
15天前
|
银行转账p图软件,对公转账截图生成器,java版开发银行模拟器【仅供学习参考】
这是一套简单的银行账户管理系统代码,包含`BankAccount`和`BankSystem`两个核心类。`BankAccount`负责单个账户的管理
银行流水生成器在线制作,银行转账p图在线生成,java实现最牛的生成器【仅供学习用途】
本示例展示了一个基于Java的银行交易记录管理系统基础架构,涵盖交易记录生成、数字签名加密及账本存储功能。核心内容包括:1) TransactionRecord类
Java 基础知识超详细整理总结及学习要点解析
本文全面总结了Java基础知识,涵盖语言特性、语法基础、面向对象编程、集合框架、异常处理等核心内容。文章详细解析了Java的面向对象特性(如类与对象、构造方法、方法重载)、集合框架(如ArrayList、HashMap)、异常分类及处理,并深入探讨JVM内存模型、字符串比较、BigDecimal使用等重要知识点。此外,还提供了实际应用示例,帮助开发者更好地理解和掌握Java编程。代码资源可从文末链接获取。
106 4
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问