内容简介：还没关注？快动动手指！
还没关注？
快动动手指！
聊技术、论职场！
为IT人打造一个“有温度”的 狸猫技术窝
当我们在做数据库分库分表或者是分布式缓存时，不可避免的都会遇到一个问题:
如何将数据均匀的分散到各个节点中，并且尽量的在加减节点时能使受影响的数据最少。
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 后加上编号来生成哈希值。 这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。
END
作者：crossover Jie
来源：
https://crossoverjie.top/2018/01/08/Consistent-Hash/
本文版权归作者所有
为您推荐：
长按下图二维码，即刻关注【 狸猫技术窝 】
阿里、京东、美团、字节跳动
顶尖技术专家 坐镇
为IT人打造一个 “有温度” 的技术窝！
以上所述就是小编给大家介绍的《大白话聊聊面试中常问的一致性 Hash 算法！》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 大白话 Laravel 中间件
- 大白话讲梯度下降法（一）
- 大白话讲梯度下降法（二）
- 大白话理解和初步使用vuex
- JAVA-大白话探索JVM-类加载过程（二）
- JAVA-大白话探索JVM-运行时内存（三）
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Python高性能编程
【美】 戈雷利克 （Micha Gorelick）、【美】 欧日沃尔德（Ian Ozsvald） / 人民邮电出版社 / 2017-7-1 / 79
本书共有12章，围绕如何进行代码优化和加快实际应用的运行速度进行详细讲解。本书主要包含以下主题：计算机内部结构的背景知识、列表和元组、字典和集合、迭代器和生成器、矩阵和矢量计算、并发、集群和工作队列等。最后，通过一系列真实案例展现了在应用场景中需要注意的问题。 本书适合初级和中级Python程序员、有一定Python语言基础想要得到进阶和提高的读者阅读。一起来看看 《Python高性能编程》 这本书的介绍吧!
