专栏首页Java3y什么是一致性Hash算法?

什么是一致性Hash算法?

本文公众号来源:crossoverJie 作者:crossoverJie 当时我就是看这篇文章学习什么是一致性Hash算法的,觉得写得非常不错,分享一下

当我们在做数据库分库分表或者是分布式缓存时,不可避免的都会遇到一个问题:

如何将数据均匀的分散到各个节点中,并且尽量的在加减节点时能使受影响的数据最少。

Hash 取模

随机放置就不说了,会带来很多问题。通常最容易想到的方案就是 hash取模了。

可以将传入的 Key 按照 index=hash(key)%N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法,N 就是节点的数量。

这样可以满足数据的均匀分配,但是这个算法的容错性和扩展性都较差。

比如增加或删除了一个节点时,所有的 Key 都需要重新计算,显然这样成本较高,为此需要一个算法满足分布均匀同时也要有良好的容错性和拓展性。

一致 Hash 算法

一致 Hash 算法是将所有的哈希值构成了一个环,其范围在 0~2^32-1。如下图:

之后将各个节点散列到这个环上,可以用节点的 IP、hostname 这样的唯一性字段作为 Key 进行 hash(key),散列之后如下:

之后需要将数据定位到对应的节点上,使用同样的 hash函数 将 Key 也映射到这个环上。

这样按照顺时针方向就可以把 k1 定位到 N1节点,k2 定位到 N3节点,k3 定位到 N2节点

容错性

这时假设 N1 宕机了:

依然根据顺时针方向,k2 和 k3 保持不变,只有 k1 被重新映射到了 N3。这样就很好的保证了容错性,当一个节点宕机时只会影响到少少部分的数据。

拓展性

当新增一个节点时:

在 N2 和 N3 之间新增了一个节点 N4 ,这时会发现受印象的数据只有 k3,其余数据也是保持不变,所以这样也很好的保证了拓展性。

虚拟节点

到目前为止该算法依然也有点问题:

当节点较少时会出现数据分布不均匀的情况:

这样会导致大部分数据都在 N1 节点,只有少量的数据在 N2 节点。

为了解决这个问题,一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash,生成多个节点放置在环上称为虚拟节点:

计算时可以在 IP 后加上编号来生成哈希值。

这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。

更多资料

这篇写得比较简洁,如果觉得还没看够的同学可以看看下面这篇:

  • https://zhuanlan.zhihu.com/p/34985026

本文的作者还写了一篇Hash算法的实际应用,有兴趣的同学也可以前往学习学习:

本文分享自微信公众号 - Java3y(java3y)

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

原始发表时间:2019-05-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Map集合、散列表、红黑树介绍

    Java3y
  • 二叉树就这么简单

    一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

    Java3y
  • DOM编程

    什么是DOM? DOM(Document Object Model)文档对象模型,是语言和平台的中立接口。。 允许程序和脚本动态地访问和更新文档的内容。 为什么...

    Java3y
  • 【算法专栏】二叉树的下一个节点

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    ConardLi
  • JavaScript 技术篇-js只获取本节点text文本,不包含子节点

    innerText 和 textContent 都是获取所有节点的 firstChild.nodeValue 是获取本节点的text文本,不包含子节点的。

    小蓝枣
  • 详解 NoSQL 数据库的分布式算法

    系统的可扩展性是推动NoSQL运动发展的的主要理由,包含了分布式系统协调,故障转移,资源管理和许多其他特性。这么讲使得NoSQL听起来像是一个大筐,什么都能塞进...

    CSDN技术头条
  • 吹弹牛皮之Unity AI决策-行为树

    行为树。小菜最早接触到这个内容的身影是在一款捕鱼游戏的机器人模拟上,模拟玩家登录游戏,进入大厅,发射子弹,退出游戏等过程中的行为。由于最近工作的需要,小...

    用户7698595
  • 数据结构与算法笔记(四)

    二叉查找树支持快速插入、删除、查找操作,各个操作时间跟树的高度成正比,理想情况下,时间复杂度为 O(logn)。但是,在极端的情况下,二叉树会退化成链表(比如按...

    WriteOnRead
  • 浅谈多路查找树(B树)

    曾今我不知道多叉树有上面用,所以对于多叉树并没有过多的关注,或者说,基本没关注。 直到我了解到了多路查找树(B树),我知道,是我浅薄了。

    看、未来
  • 拥抱STL -树的导览

    树,一种十分基础的数据结构。 本篇将重点讲一些树的基础知识,作为下一篇《走进STL - 红黑树》的支持。

    看、未来

扫码关注云+社区

领取腾讯云代金券