文档章节

一致性哈希算法

haoran_10
 haoran_10
发布于 2016/07/15 16:40
字数 2531
阅读 26
收藏 1
点赞 0
评论 0

前记:由于在学习redis 集群时使用到了 twemproxy方案,twemproxy是以一致性哈希算法为原理进行代理多个孤立的redis 节点集成集群。所以很有必要学习下一致性哈希算法。

 

一、什么是一致性哈希

  •  一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot spot)问题。
  • 初衷和CARP(Common Access Redundancy Protocol共用地址冗余协议)十分类似。
  • 一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT(Distributed Hash Table,分布式哈希表)可以在P2P环境中真正得到应用。

 

二、普通哈希算法的缺点

假如有N个redis节点(单机,孤立的),我们在这些N个redis节点前面做一个代理,转发客户端的读和写,使用hash算法分配到后面的redis节点中。

一般情况,我们是这样使用 hash(object_x) %N = object_x_key,当N个节点没有任何问题时,一切运行良好。。。突然,有一天!

  • 有一台redis抽风出现故障,不可用了,此时hash(object_x)%(N-1)=object_x_key_1 。再也找不回熟悉的味道。。。哦,错了,熟悉的节点。
  • 内存不够了,运维哥哥说加一台机器,此时hash(object_x)%(N+1)=object_x_key_2。也找不到熟悉的节点了。
  • 运维哥哥发现有几台机器内存使用率很高,还有几台内存使用率很低,完全浪费。怎么回事,不是说好了做彼此的天使,有困难一起扛吗?

 

 

三、一致性哈希算法怎么解决普通哈希算法遗留的问题

 

看看一致性哈希算法的如何映射数据的。

(1)、环形Hash空间

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中,即0~(2^32)-1的数字空间中(数据量不够,2^64也行)。现在我们可以将这些数字头尾相连,想象成一个闭合的环形。

如下图所示:



 

(2)、把缓存数据映射到哈希环上

假如有四个缓存数据需要映射,通过hash函数计算出的hash值key 在环上的分布。

hash(object1)=key1
hash(object2)=key2
hash(object3)=key3
hash(object4)=key4

 

 如下图所示:



 

(3)、把缓存节点服务器映射到哈希环上

假设我们有三台缓存服务器节点,命名为:Cache A,Cache B,Cache C 通过hash函数计算出的hash值key 在环上的分布。

hash(CacheA) = keyA;
hash(CacheB) = keyB;
hash(CacheC) = keyC;

 如下图所示:



 

说到这里,顺便提一下 节点cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者唯一机器名作为 hash输入。

 

(4)、把缓存数据映射到缓存节点服务器上

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从缓存对象的 key 值出发,直到遇见一个 节点cache ,那么就将该对象存储在这个 节点cache 上,因为缓存对象和 节点cache 的 hash 值是固定的,因此这个 缓存cache 必然是唯一和确定的。

 

那么根据上面的方法,对象 object1 将被存储到 节点cache A 上; object2 和object3 对应到 节点cache C ; object4 对应到 节点cache B ;

 

图和(3)、【把缓存节点服务器映射到哈希环上】共用,上图所示。

 

 

说了那么多,还没说怎么解决问题,下面来看

(1)、移除一个缓存节点

假设节点CacheB挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 节点cache B 逆时针遍历直到下一个 cache ( cache A )之间的对象,也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可 。

 

如下图所示:



 

 

(2)、新增一个缓存节点

假设添加一台新的节点 cache D 的情况,假设在这个环形 hash 空间中, 节点cache D 被映射在对象 object2 和object3 之间。

这时受影响的将仅是那些沿 节点cache D 逆时针遍历直到下一个节点cache ( 节点cache B )之间的对象(它们是本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

 

因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上 。

 

如下图所示:

 



 

(3)、平衡分配数据

 在【(1)、移除一个缓存节点】中,移除了节点CacheB,结果object4也转移到CacheC,这时节点CacheA只有object1,而节点CacheC有,object2,object3,object4,分布不平衡。

为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念。
 

它可以如下定义:

“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

 

 

仍以仅部署 节点cache A 和节点 cache C 的情况为例,在【(1)、移除一个缓存节点】 中我们已经看到,节点 cache 分布并不均匀。

现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点:

节点 cache A1,节点 cache A2 代表了节点cache A ; 

节点cache C1, 节点cache C2 代表了 节点 cache C ;假设一种比较理想的情况。

 

如下图:

 



 

 

 

此时,对象到“虚拟节点”的映射关系为:

objec1->节点cache A2 ; objec2->节点cache A1 ; objec3->节点cache C1 ; objec4->节点cache C2 ;

因此对象 object1 和 object2 都被映射到了节点 cache A 上,而 object3 和 object4 映射到了 节点cache C 上;平衡性有了很大提高。

 

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系 。

如下图所示:



 

 

 

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。

例如假设 节点cache A 的 IP 地址为192.168.11.1 。
引入“虚拟节点”前,计算节点 cache A 的 hash 值:
Hash(“192.168.11.1”);
引入“虚拟节点”后,计算“虚拟节”点 中节点cache A1 和节点 cache A2 的 hash 值:
Hash(“192.168.11.1#1”);  // 节点cache A1
Hash(“192.168.11.1#2”);  // 节点cache A2

 

 

 

 

四、一致性哈希算法优点总结

(1)、单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 

  (2)、平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

  (3)、分散性(Spread)

在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

  (4)、负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

 

五、一致性哈希算法局限性

(1)、某个单个节点出现故障时,该节点下的数据全部不可用

在【三、(1)、移除一个缓存节点】时,节点CacheB的key是转移到了CacheC,但是事实上数据已经丢失了。

这个也不是该算法所能解决的范畴,只能通过主从模式对该节点进行做从节点,一旦主节出现故障时,从节点能自动接替主节点,从而该节点下的数据不至于丢失。

 

(2)、增加节点时,该节点下的数据没有重新分配到其他节点

 在【三、(2)、新增一个缓存节点】时,新增节点CacheD时,处于节点CacheB和CacheD之间的数据,本来属于CacheC的,确没有转移到CacheD上,只有key转移到了CacheD上,那么这些数据也丢失了。

这个算法也解决不了,只能通过一些特殊的办法,转移数据。最好能做到新增一个节点时,数据自动分配,那就完美了。

 

六、小结

一致性哈希算法解决了一些问题,但是又引出了一些新的问题,这些问题至少从算法的角度不能轻易解决。不知道能不能通过数据冗余的办法or算法解决掉吗?

 

© 著作权归作者所有

共有 人打赏支持
haoran_10
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员

暂无文章

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
5
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
1
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
165
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部