java- 分布式- 一致性哈希算法(1)
2023-09-27 14:26:36 时间
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。 因此,引入了一致性哈希算法:
把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。 如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:
for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点
SortedMap Long, S tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点
* 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。 因此,引入了一致性哈希算法:
把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。 如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:
图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。
for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点
SortedMap Long, S tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点
* 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
相关文章
- Java算法面试题(史上最强、持续更新、吐血推荐)
- Java 解析json数据
- Java基础篇(03):流程控制语句,和算法应用
- LeetCode 算法题详解 JAVA 版 开始刷题啦~
- Java核心技术卷I基础知识3.5 运算符
- 备战金九银十!【Java 面试小抄】涵盖当下最时新热门技术点,学完 offer 得拿到手软~
- Java面试题全集(上)
- Java面试第三季
- C/C++/Java代码 朴素的(暴力法)模式匹配算法 KMP算法 数据结构
- java学习笔记(3)
- (Java实习生)每日10道面试题打卡——JVM篇 (二)
- java 实现 DES加密 解密算法
- java中奖观众(Hash,Random)
- 分治算法实现经典归并排序java实现
- Java集合篇:Hashtable原理详解(JDK1.8)
- 华为OD机试 - 整数编码(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -新学校选址(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -最短木板长度(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 比赛评分(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -快递运输(Java) | 机试题+算法思路+考点+代码解析 【2023】
- Java 中最常见的 5 个错误
- java线:辛格尔顿隐藏ThreadLocal实现线程数据共享
- Java数据结构与算法 day12 图
- JAVA获取CLASSPATH路径--转
- 十几年老Java咳血推荐,你薪资涨一波没毛病!小AD以为我端午都干嘛去了?
- 深入JAVA注解之属性注解
- Java排序算法(一)冒泡排序