文档章节

使用虚拟节点改进的一致性哈希算法

lionets
 lionets
发布于 2014/07/07 20:25
字数 1195
阅读 5117
收藏 16

##分布式存储中的应用

在分布式存储系统中,将数据分布至多个节点的方式之一是使用哈希算法。假设初始节点数为 N,则传统的对 N 取模的映射方式存在一个问题在于:当节点增删,即 N 值变化时,整个哈希表(Hash Table)需要重新映射,这便意味着大部分数据需要在节点之间移动。

因此现在普遍使用的是被称为一致性哈希(Consistent Hashing)的一类算法。“一致性” 这个定语的意义在于:当增删节点时,只影响到与变动节点相邻的一个或两个节点,散列表的其他部分与原来保持一致。某种程度上可以将其理解为:一致性哈希算法的哈希函数与节点数 N 无关。

其他地方对一致性哈希配图的时候,都会选择一个圆环来解释,但我个人感觉哈希表更加直观:

一致性哈希

上图左右分别表示增加一个 “节点 5” 前后的哈希表,哈希函数使用的是 md5 。md5 会根据 key 的值摘要出一个 128 bit 的哈希值(校验和),一般表示为一个 32 位的 16 进制数。这里我们取哈希值第一位的范围来将 key 映射到不同的节点,可以看到在拆分了 “节点 4” 的 md5 首位范围后,只需要将 “节点 4” 原本数据的约一半移动到 “节点 5” 上去就可以了,其他三个节点并未受到影响。 <br /> ##负载均衡改进

但这里其实仍有改进的空间。

问题在于,上面需要将 “节点 4” 的一半数据搬运到 “节点 5” 上,这个压力会比较大。以一个节点存有 3TB 的数据、节点间网络为千兆网(但只允许搬运进程使用 25% 负载)来算,搬运完 1.5TB 的数据最少需要 (1.5TB * 1024GB/TB * 1024MB/GB) / (125MB/s * 0.25) ≈ 14h;另一方面,“节点 5” 直接分担走了 “节点 4” 数据的一半,如果原来 4 个节点的负载是均衡的(md5 本身是一个很均匀的哈希函数),那么现在就变得不均衡了。

这两个问题有一个公共的解决方法:新增的 “节点 5” 不只从 “节点 4” 搬运数据,而从所有其他节点(或子集)处搬运数据,同时还要继续保持哈希一致性。

这种想法的一个实现方式就是,使用虚拟节点(virtual nodes)。上面 md5 哈希表实际可以分为两段:

  1. 通过 md5 将 key 哈希出一个 32 位的 16 进制哈希值
  2. 将这个哈希值映射到某个物理节点

当使用虚拟节点时,我们保持第一段不变,但会在第二段将哈希值映射到物理节点的过程中再插入一个虚拟节点中间件,从而将过程变为:

  1. 通过 md5 将 key 哈希出一个 32 位的 16 进制哈希值
  2. 将这个哈希值映射到一个虚拟节点
  3. 将这个虚拟节点映射到一个物理节点

新哈希表的关键之处在于虚拟节点的数量比物理节点数多得多,甚至很多时候会将虚拟节点的数量设置为 “尽可能多”。这样新哈希表的前两段就固定不变了,当增删物理节点时,只是对虚拟节点进行必要的重新分配的过程。

改进的一致性哈希

上图中我们依 md5 值的首位划分了 16 个虚拟节点,然后将它们映射到 4 个物理节点。(实际应用中,即使你当下只有 10 个物理节点,也大可以按 md5 的前三位划分出 4096 个虚拟节点)当我们增加物理 “节点 5” 的时候,就从节点 1、2、3 处各拿一个虚拟节点放到 “节点 5” 中。这个过程,“节点 5” 既可以使用 100% 的网络带宽来接收数据;新的哈希表也实现了负载均衡。当然一致性也得到了保证。

这种使用虚拟节点的一致性哈希算法我看到国内有人管它叫分布式一致性哈希(Distributed Consistent Hashing),但这个 “分布式” 叫法显得有些不合适,因为这种改进只涉及到算法的实现而与哈希过程发生的位置无关,并且 google 上也找不到这种叫法。所以一般就称改进的一致性哈希(Improved Consistent Hashing)好了。或者,使用虚拟节点的一致性哈希。

© 著作权归作者所有

共有 人打赏支持
lionets
粉丝 91
博文 99
码字总数 133263
作品 0
朝阳
程序员
私信 提问
加载中

评论(6)

hyhlinux
hyhlinux

引用来自“comeby”的评论


楼主的文章很通俗易懂,哈希方法很适合用来提高缓存系统命率。
但我对负载均衡还有一个问题不明白:假如有一个请求量很大的请求key,压力大到能导致一台机器宕机时,应该怎么做负载均衡,同时能保证缓存命中率。
例如:大家都用百度查找刘德华,假如百度服务器采取了类似hash的方式来做负载均衡以提高命中率,这些请求会被负载到一台物理机上,而单台物理机承载不了这么多请求,宕机了,然后这些请求又被负载到系统中另一台物理机,这台物理机也会因为无法承载如此大的压力宕机。最后整个服务集群就都宕掉了。
楼主知不知道这个问题怎么解决呢?
h(key) 保证了每次在同一台机器s1,但是对于热点key, 会导致增加s1的压力,所以这个时候,采用权重随机,保证热点key可以分散到其他服务器。
lionets
lionets

引用来自“一叶舟troy”的评论

可以转载不
ok
一叶舟troy
一叶舟troy
描述:
从节点 1、2、3 处各拿一个虚拟节点放到 “节点 5”

这个过程中是从真实的主机上根据范围来迁移数据呀?这个是不适要自己写个程序来控制,因为虚节点不不存储数据
迁移过程中如果发生修改了怎么办》
一叶舟troy
一叶舟troy
可以转载不
lionets
lionets

引用来自“comeby”的评论


楼主的文章很通俗易懂,哈希方法很适合用来提高缓存系统命率。
但我对负载均衡还有一个问题不明白:假如有一个请求量很大的请求key,压力大到能导致一台机器宕机时,应该怎么做负载均衡,同时能保证缓存命中率。
例如:大家都用百度查找刘德华,假如百度服务器采取了类似hash的方式来做负载均衡以提高命中率,这些请求会被负载到一台物理机上,而单台物理机承载不了这么多请求,宕机了,然后这些请求又被负载到系统中另一台物理机,这台物理机也会因为无法承载如此大的压力宕机。最后整个服务集群就都宕掉了。
楼主知不知道这个问题怎么解决呢?
单一对象请求能强到宕机程度的时候,一般可以预先做针对性优化,比如各种缓存。单节点实在承受不起的时候,也有通过分布于各地的机房各自分担区域请求的做法。这样单一对象分布于多个物理节点的时候,会有额外的方法保证数据一致性。
c
comeby

楼主的文章很通俗易懂,哈希方法很适合用来提高缓存系统命率。
但我对负载均衡还有一个问题不明白:假如有一个请求量很大的请求key,压力大到能导致一台机器宕机时,应该怎么做负载均衡,同时能保证缓存命中率。
例如:大家都用百度查找刘德华,假如百度服务器采取了类似hash的方式来做负载均衡以提高命中率,这些请求会被负载到一台物理机上,而单台物理机承载不了这么多请求,宕机了,然后这些请求又被负载到系统中另一台物理机,这台物理机也会因为无法承载如此大的压力宕机。最后整个服务集群就都宕掉了。
楼主知不知道这个问题怎么解决呢?
查找--深入理解一致性哈希算法

注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法...

珩翊
06/26
0
0
Cassandra的一致性哈希(Consistent Hashing)和虚拟节点(Virtual Nodes)的关系

本文原文出处: http://blog.csdn.net/bluishglc/article/details/52847591 严禁任何形式的转载,否则将委托CSDN官方维护权益! 一致性哈希所要解决的问题 一般的哈希算法存在的问题是:当“模...

bluishglc
2016/10/18
0
0
Consistent Hashing算法

前几天看了一下Memcached,看到Memcached的分布式算法时,知道了一种Consistent Hashing的哈希算法,上网搜了一下,大致了解了一下这个算法,做下记录。 数据均衡分布技术在分布式存储系统中...

xumaojun
04/08
0
0
一致性哈希算法及其在分布式系统中的应用

摘要 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及...

abing_hu
2013/09/01
0
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

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 教程:在 Confluence 中导航

当你对 Confluence 有所了解后,你会发现 Confluence 使用起来非常简单。这个教程主要是针对你使用的 Confluence 界面进行一些说明,同时向你展示在那里可以进行一些通用的任务和操作。 空间...

honeymose
今天
2
0
sed, awk 练习

1. sed打印某行到某行之间的内容 2. sed 转换大小写 将单词首字母转化大写 将所有小写转化大写 3. sed 在某一行最后面添加一个数字 4. 删除某行到最后一行 解析: {:a;N;$!ba;d} :a : 是...

Fc丶
今天
2
0
babel6升级到7,jest-babel报错:Requires Babel "^7.0.0-0", but was loaded with "6.26.3".

自从将前端环境更新到babel7,jest-babel之前是基于babel6的,执行时候就会报:Requires Babel "^7.0.0-0", but was loaded with "6.26.3". 很烦,因为连续帮好几台电脑修复这个问题,所以记...

曾建凯
今天
1
0
探索802.11ax

802.11ax承诺在真实条件下改善峰值性能和最差情况。 如何改善今天的Wi-Fi? 在决定如何改进当前版本以外的Wi-Fi时,802.11ac,IEEE和Wi-Fi联盟调查了Wi-Fi部署和行为,以确定更广泛使用的障碍...

linuxprobe16
今天
2
0
使用linux将64G的SDCARD格式化为FAT32

一、命令如下: sudo fdisk -lsudo mkfs.vfat /dev/sda -Isudo fdisk /dev/sda Welcome to fdisk (util-linux 2.29.2). Changes will remain in memory only, until you decide to wri......

mbzhong
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部