专栏首页架构说使用虚拟节点改进的一致性哈希算法

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

1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 如何实现 连接:http://www.cnblogs.com/coser/archive/2011/11/27/2265134.html

分布式存储中的应用

1 直接取模

在分布式存储系统中,将数据分布至多个节点的方式之一是使用哈希算法。

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

2 致性哈希(Consistent Hashing)

“一致性” 这个定语的意义在于:当增删节点时,只影响到与变动节点相邻的一个或两个节点,散列表的其他部分与原来保持一致

某种程度上可以将其理解为:一致性哈希算法的哈希函数与节点数 N 无关。

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

上图左右分别表示增加一个 “节点 5” 前后的哈希表,哈希函数使用的是 md5 。md5 会根据 key 的值摘要出一个 128 bit 的哈希值(校验和),一般表示为一个 32 位的 16 进制数。这里我们取哈希值第一位的范围来将 key 映射到不同的节点,

可以看到在拆分了 “节点 4” 的 md5 首位范围后,只需要将 “节点 4” 原本数据的约一半移动到 “节点 5” 上去就可以了,其他三个节点并未受到影响。

3 负载均衡改进-虚拟节点

缺点:

问题在于,上面需要将 “节点 4” 的一半数据搬运到 “节点 5” 上,这个压力会比较大。

以一个节点存有 3TB 的数据、节点间网络为千兆网(但只允许搬运进程使用 25% 负载)来算,搬运完 1.5TB 的数据最少需要

(1.5TB * 1024GB/TB * 1024MB/GB) / (125MB/s * 0.25)

≈ 14h

另一方面,“节点 5” 直接分担走了 “节点 4” 数据的一半,

如果原来 4 个节点的负载是均衡的(md5 本身是一个很均匀的哈希函数),那么现在就变得不均衡了。(why?)

这两个问题有一个公共的解决方法:新增的 “节点 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% 的网络带宽来接收数据;新的哈希表也实现了负载均衡。当然一致性也得到了保证。

实现代码:

http://files.cnblogs.com/coser/ConsistentHashAlgorithm.rar

QA:数据存在在虚拟节点还是真实节点 ?

例如上图v000-v003 数据存储在节点1(redis)从中抽取v002s 数据应该是copy节点1中数据

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-04-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [LeetCode] Symmetric Tree

    1、题目名称 Symmetric Tree https://leetcode.com/problems/symmetric-tree/ 2、题目内容 Give...

    程序员小王
  • raft一致性算法简单解释

    在分布式环境中, 一致性是指数据在多个副本之间是否能够保持一致的特性。在一致性的需求下,当一个系统在数据一致的状态下执行更新操作之后, 应该能够保证系统的数据仍...

    程序员小王
  • leetcode538. 把二叉搜索树转换为累加树

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

    程序员小王
  • 7-2 其余的一些树-排序二叉树-霍夫曼树

    二叉排序树可以通过递归的方法来定义,它或者是空二叉树,或者是具有如下定义的二叉树:

    TeeyoHuang
  • 数据结构之二叉树解析

    可是,排序有快速排序,归并排序,查找有二分法,甚至直接遍历查找,我干啥要使用二叉树呢?

    Kevin_Zhang
  • 重温数据结构:理解 B 树、B+ 树特点及使用场景

    B 树就是常说的“B 减树(B- 树)”,又名平衡多路(即不止两个子树)查找树,它和平衡二叉树的不同有这么几点:

    张拭心 shixinzhang
  • 使用蒙特卡洛树搜索实现围棋落子算法

    上一节我们完成了最大最小搜索树,加上alhpa-beta剪枝算法实现了围棋落子走法。它存在一个问题是,树搜索的层次不高,尽管如此,围棋机器人下棋时还是要多次扫描...

    望月从良
  • 红黑树(二):删除操作

    构造上,节点会有三种可能:其一是删除节点的孩子都为Nil,其二是删除节点的一个孩子节点为Nil,其三是删除节点的两个孩子节点都不为Nil。而如果两个节点都不为N...

    每天学Java
  • 探索C#之虚拟桶分片

    蘑菇先生
  • Raft分布式一致性算法整理 顶 原

    CAP定理指出,在异步网络模型中,不存在一个系统可以同时满足上述3个属性。换句话说,分布式系统必须舍弃其中的一个属性。对于需要在分布式条件下运行的系统来说,如何...

    算法之名

扫码关注云+社区

领取腾讯云代金券