您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

分布式原理:一致性哈希算法简介

时间:2019-10-22 13:33:02  来源:  作者:

一致性哈希算法

普通的哈希算法使用取余操作:hash(o) mod n,其中 n 代表机器的数量。如果在集群中新增加一个节点时,计算公式会变为:hash(o) mod (n+1);在集群中删除一个机器时,计算公式变为:hash(o) mod (n-1)。所以当集群中机器数量有所变化时,几乎所有的 Object 的哈希值都会改变。一致性哈希可以保证当从集群中删除一台机器时,仅仅保存在该机器上的 Object 的值会变化;当集群中增加一台机器时,也仅仅是非常小的一部分 Object 的哈希值会发生改变。

一致性哈希算法的实现原理其实很简单,它也是使用取模的方式,只是刚才描述的取模法是对机器的数量进行取模,而一致性哈希算法是对2^32取模,hash(o) mod 2^32 什么意思呢?我们慢慢聊。

其将整个哈希值空间组织成一个虚拟的圆环,比如某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),那么整个哈希空间环看起来就像下图所示:

分布式原理:一致性哈希算法简介

 

将机器映射到环中

一致性哈希算法是数据分布的方式,而数据最终是需要存到机器中的,所以我们首先需要将机器映射到环中。假设我们有四台机器 Node1、Node2、Node3 以及 Node4,我们使用机器名或者 ip 计算这些机器的哈希值,然后分别映射到环中去,看起来就像下面一样:

分布式原理:一致性哈希算法简介

 

将数据映射到环中

我们使用相同的哈希函数计算需要存储数据的哈希值,假设现在我们有四份数据 data1、data2、data3 以及 data4,我们需要将这些数据映射到环中去,这样看起来像下面图一样:

分布式原理:一致性哈希算法简介

 

在这个哈希环中,数据存储的机器是按照顺时针方向遇到的第一个节点就是这个数据存储的节点,所以图中:

  • 数据 data2 存储在节点 Node1 上;
  • 数据 data3 存储在节点 Node4 上;
  • 数据 data1 存储在节点 Node2 上;
  • 数据 data4 存储在节点 Node3 上。

添加节点在分布式环境中,添加或减少节点是很常见的操作。现在我们往上面的哈希环添加一个节点 Node5,同样使用相同的哈希函数计算这个节点在哈希环的位置,假设计算的结果如下:

 

分布式原理:一致性哈希算法简介

 

添加节点 Node5 之后,原本存储在 Node4 上的数据 data3 就转移到 Node5 了,其他数据分配不变。相比于普通的哈希添加节点会导致大量映射失效,一致性哈希可以很好的处理这种情况。如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

删除节点

如果哈希环中有节点出现故障,需要从哈希空间中移除,那么影响的数据也是有限的。假设节点 Node1 出现故障需要移除,新的哈希空间的数据映射如下:

 

分布式原理:一致性哈希算法简介

 

Node1 节点移走之后,数据 data2 就转移到 Node4 节点上了。所以如果从环中删除节点,受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

虚拟节点

上述最基本的一致性哈希算法有很明显缺点,随机分布方式使得难均匀的分布哈希值域;尤其在动态增加节点后,即使原先的分布均匀也很难保证继续均匀 即hash环的偏斜。由此带来另一个较为严重的缺点,当一个节异常时,该节点的压力全部转移到相邻的一个节点,当加入一个新节点时,只能为一个相邻节点分摊压力。

为此一个改进方法是引入虚拟节点(virtual node),虚拟节点是实际节点在哈希空间的复制品( replica ),一实际个节点(机器)对应了若干个虚拟节点,这个对应个数也成为复制个数,虚拟节点在哈希空间中以哈希值排列。

为了表述方便,假设我们有2个节点,4份数据,在引入虚拟节点之前节点和数据分布如下:

 

分布式原理:一致性哈希算法简介

 

可以看见节点 Node2 管理的数据有 data1、data3 和 data4;而节点 Node1 仅仅只管理数据 data2。这就造成了数据分布不均匀的情况。如果我们通过引入虚拟节点,并且假定复制个数为3,则哈希之后的情况如下:

 

分布式原理:一致性哈希算法简介

 

其中 Node1_1、Node1_2 和 Node1_3 是 Node1 虚拟出来的节点;同理Node2_1、Node2_2 和 Node2_3 是 Node2 虚拟出来的节点。通过添加虚拟节点之后,各个节点管理的数据已经比较均匀了。



Tags:哈希算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
哈希 Hash 算法介绍哈希算法也叫散列算法, 不过英文单词都是 Hash, 简单一句话概括, 就是可以把任意长度的输入信息通过算法变换成固定长度的输出信息, 输出信息也就是哈希...【详细内容】
2021-08-17  Tags: 哈希算法  点击:(72)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  Tags: 哈希算法  点击:(147)  评论:(0)  加入收藏
一、介绍及原理1.1 简介哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算,得到一个固定长度的输出摘要。比如Java字符串的hashCode()就是哈希算法,输出是...【详细内容】
2020-11-12  Tags: 哈希算法  点击:(199)  评论:(0)  加入收藏
哈希函数,想必大家都不陌生。通过哈希函数我们可以将数据映射成一个数字(哈希值),然后可用于将数据打乱。例如,在HashMap中则是通过哈希函数使得每个桶中的数据尽量均匀。那一致...【详细内容】
2020-07-07  Tags: 哈希算法  点击:(71)  评论:(0)  加入收藏
最近,区块链的概念是火爆了,就在最近,腾讯公司与中国信通院发表白皮书,将主导中国区块链发票。可以预见的是,在未来一段时间,区块链还会继续火爆下去,如果掌握了区块链的技术,不敢说...【详细内容】
2019-11-01  Tags: 哈希算法  点击:(78)  评论:(0)  加入收藏
一致性哈希算法普通的哈希算法使用取余操作:hash(o) mod n,其中 n 代表机器的数量。如果在集群中新增加一个节点时,计算公式会变为:hash(o) mod (n+1);在集群中删除一个机器时,计...【详细内容】
2019-10-22  Tags: 哈希算法  点击:(102)  评论:(0)  加入收藏
暴雪公司的魔兽、星际等游戏都一样一个非常大的MPQ文件,该文件存储了游戏中的大部分数据,想要把这些文字找出来,简单的办法是从数组头开始,一个个字符串读过去,比较每一个,直到找...【详细内容】
2019-10-09  Tags: 哈希算法  点击:(136)  评论:(0)  加入收藏
话说前几天有一次,某大厂的二面。然后呢,烟哥那天刚好有事,所以去不了。于是就约了一场视频面试了!...【详细内容】
2019-09-03  Tags: 哈希算法  点击:(186)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条