文档章节

分布式缓存的一致性hash算法

Nob
 Nob
发布于 2014/10/18 10:08
字数 1256
阅读 4190
收藏 8

基本场景

比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;


常规取余的hash算法

hash(key) % N

对于N台缓存服务器构成的集群缓存,依次编号为0 - (N-1)先对要存储的key进行hash取值,然后用hash值对N取余,得到一个在缓存服务器编号区间的一个数字,则将当前key存到这台服务器。

弊端:

随着系统访问压力的增长,缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式,在增加机器节点的这一时刻,大量的缓存命不中,缓存数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机。


设计分布式cache系统时,一致性hash算法可以帮我们解决哪些问题?

分布式缓存设计核心点:在设计分布式cache系统的时候,我们需要让key的分布均衡,并且在增加cache server后,cache的迁移做到最少。

这里提到的一致性hash算法ketama的做法是:选择具体的机器节点不在只依赖需要缓存数据的key的hash本身了,而是机器节点本身也进行了hash运算。


一致性哈希算法情景描述(转载)

1、 hash机器节点

首先求出机器节点的hash值(怎么算机器节点的hash?ip可以作为hash的参数吧。。当然还有其他的方法了),然后将其分布到0~2^32的一个圆环上(顺时针分布)。如下图所示:

集群中有机器:A , B, C, D, E五台机器,通过一定的hash算法我们将其分布到如上图所示的环上。


2、访问方式

如果有一个写入缓存的请求,其中Key值为K,计算器hash值Hash(K), Hash(K) 对应于图 – 1环中的某一个点,如果该点对应没有映射到具体的某一个机器节点,那么顺时针查找,直到第一次找到有映射机器的节点,该节点就是确定的目标节点,如果超过了2^32仍然找不到节点,则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间,那么命中的机器节点应该是B节点(如上图 )。


3、增加节点的处理

如上图 – 1,在原有集群的基础上欲增加一台机器F,增加过程如下:

计算机器节点的Hash值,将机器映射到环中的一个节点,如下图:

增加机器节点F之后,访问策略不改变,依然按照(2)中的方式访问,此时缓存命不中的情况依然不可避免,不能命中的数据是hash(K)在增加节点以前落在C~F之间的数据。尽管依然存在节点增加带来的命中问题,但是比较传统的 hash取模的方式,一致性hash已经将不命中的数据降到了最低。

 

Consistent Hashing最大限度地抑制了hash键的重新分布。另外要取得比较好的负载均衡的效果,往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能均匀的分布在圆环上。因为使用一般的hash方法,服务器的映射地点的分布非常不均匀。使用虚拟节点的思想,为每个物理节点(服务器)在圆上分配100~200个点。这样就能抑制分布不均匀,最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上,就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。


下面有一个图描述了需要为每台物理服务器增加的虚拟节点。

x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale),y轴是实际物理服务器数,可以看出,当物理服务器的数量很小时,需要更大的虚拟节点,反之则需要更少的节点,从图上可以看出,在物理服务器有10台时,差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。

[参考文献]

http://blog.csdn.net/kongqz/article/details/6695417  memcache的一致性hash算法使用

http://blog.csdn.net/sparkliang/article/details/5279393 

© 著作权归作者所有

Nob

Nob

粉丝 19
博文 87
码字总数 58773
作品 0
东城
个人站长
私信 提问
一致性Hash在负载均衡中的炫技

作者:不洗碗工作室 - Marklux 出处:Marklux's Pub 版权归作者所有,转载请注明出处 简介 一致性Hash是一种特殊的Hash算法,由于其均衡性、持久性的映射特点,被广泛的应用于负载均衡领域,...

不洗碗工作室
2018/09/05
0
0
[算法] 从 Memcached 分布式应用看一致性哈希散列函数的选择

一致性哈希算法来源于 P2P 网络的路由算法,目前主流的 P2P 软件就是利用我们所熟知的 DHT (Distributed Hash Table,分布式哈希表) 来定位整个分布式网络的信息,另外此算法在目前火热的云计...

长平狐
2012/11/19
713
0
一致性Hash算法在Redis分布式中的使用

由于redis是单点,但是项目中不可避免的会使用多台Redis缓存服务器,那么怎么把缓存的Key均匀的映射到多台Redis服务器上,且随着缓存服务器的增加或减少时做到最小化的减少缓存Key的命中率呢...

edeis2011
2016/05/11
287
0
一致性(连续性)hash算法(Consistent hashing)

一致性(连续性)hash算法(Consistent hashing) Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not s......

程序员诗人
2017/08/22
0
0
一致性Hash算法(Consistent Hash)

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted...

陶邦仁
2015/04/01
2.6K
5

没有更多内容

加载失败,请刷新页面

加载更多

IDEA ----Lombok工具 (用于简化 javaBean 的编写)

Lombok是一个可以通过简单的注解形式来帮助我们简化消除一些必须有但显得很臃肿的Java代码的工具,通过使用对应的注解,可以在编译源码的时候生成对应的方法。 1. 在项目中的pom.xml确定版本...

安然_oschina
36分钟前
6
0
RPA开发教程丨RPA+NLP邮件智能分析

RPA+NLP邮件项目背景 随着公司规模的不断扩大,公司商务邮箱里面的邮件也越来越多,而业务人员在繁忙的工作期,必须加班加点投入其中,由此,对邮件进行智能分析自动处理,变成了一种迫切需求...

UiBot
39分钟前
7
0
【百度AI语音合成】会员到访门店语音提醒

每次会员到访都需要。会员自主结账或找导购才能被发现。或者需要一个人员站在门口,并且对会员都全部了解,才能对会员到访进行更好服务的接待。 小帅为了免去这些操作呢。就想到了百度AI。语...

小帅帅丶
40分钟前
7
0
markdown语言使用

md基础入门 标题 使用一级标题hello world! Hello World! 其他类型的标题展示 一级标题 二级标题 三级标题 四级标题 五级标题 ######六级标题 ##段落换行 换行时有两种 末尾空2个空格 用一个...

writeademo
46分钟前
11
0
nginx启动无反应,看了logs下面的error.log后发现could not build server_names_hash错误

could not build server_names_hash, you should increase server_names_hash_bucket_size: 32 应该是说你的server_names配置太多了,超过了默认的32个字符 要加大 在http段里面添加 server...

yoblue
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部