关于算法:不会一致性hash算法劝你简历别写搞过负载均衡

大家好，我是小富~

集体公众号：程序员内点事，欢送学习交换

这两天看到技术群里，有小伙伴在探讨一致性 hash 算法的问题，正愁没啥写的题目就来了，那就简略介绍下它的原理。下边咱们以分布式缓存中经典场景举例，面试中也是常常提及的一些话题，看看什么是一致性 hash 算法以及它有那些过人之处。

构建场景

如果咱们有三台缓存服务器编号node0、node1、node2，当初有 3000 万个key，心愿能够将这些个 key 平均的缓存到三台机器上，你会想到什么计划呢？

咱们可能首先想到的计划，是取模算法hash（key）% N，对 key 进行 hash 运算后取模，N 是机器的数量。key 进行 hash 后的后果对 3 取模，失去的后果肯定是 0、1 或者 2，正好对应服务器node0、node1、node2，存取数据间接找对应的服务器即可，简略粗犷，齐全能够解决上述的问题。

hash 的问题

取模算法尽管应用简略，但对机器数量取模，在集群扩容和膨胀时却有肯定的局限性，因为在生产环境中依据业务量的大小，调整服务器数量是常有的事；而服务器数量 N 发生变化后 hash（key）% N 计算的后果也会随之变动。

比方：一个服务器节点挂了，计算公式从 hash（key）% 3 变成了hash（key）% 2，后果会发生变化，此时想要拜访一个 key，这个 key 的缓存地位大概率会产生扭转，那么之前缓存 key 的数据也会失去作用与意义。

大量缓存在同一时间生效，造成缓存的雪崩，进而导致整个缓存零碎的不可用，这基本上是不能承受的，为了解决优化上述情况，一致性 hash 算法应运而生~

那么，一致性哈希算法又是如何解决上述问题的？

一致性 hash

一致性 hash 算法实质上也是一种取模算法，不过，不同于上边按服务器数量取模，一致性 hash 是对固定值 2^32 取模。

IPv4 的地址是 4 组 8 位 2 进制数组成，所以用 2^32 能够保障每个 IP 地址会有惟一的映射

hash 环

咱们能够将这 2^32 个值形象成一个圆环⭕️（不得意圆的，本人想个形态，好了解就行），圆环的正上方的点代表 0，顺时针排列，以此类推，1、2、3、4、5、6……直到 2^32-1，而这个由 2 的 32 次方个点组成的圆环统称为hash 环。

那么这个 hash 环和一致性 hash 算法又有什么关系嘞？咱们还是以上边的场景为例，三台缓存服务器编号node0、node1、node2，3000 万个key。

服务器映射到 hash 环

这个时候计算公式就从 hash（key）% N 变成了hash（服务器 ip）% 2^32，应用服务器 IP 地址进行 hash 计算，用哈希后的后果对 2^32 取模，后果肯定是一个 0 到 2^32- 1 之间的整数，而这个整数映射在 hash 环上的地位代表了一个服务器，顺次将node0、node1、node2 三个缓存服务器映射到 hash 环上。

对象 key 映射到 hash 环

接着在将须要缓存的 key 对象也映射到 hash 环上，hash（key）% 2^32，服务器节点和要缓存的 key 对象都映射到了 hash 环，那对象 key 具体应该缓存到哪个服务器上呢？

对象 key 映射到服务器

从缓存对象 key 的地位开始，沿顺时针方向遇到的第一个服务器，便是以后对象将要缓存到的服务器。

因为被缓存对象与服务器 hash 后的值是固定的，所以，在服务器不变的条件下，对象 key 必定会被缓存到固定的服务器上。依据上边的规定，下图中的映射关系：

• key-1 -> node-1
• key-3 -> node-2
• key-4 -> node-2
• key-5 -> node-2
• key-2 -> node-0

如果想要拜访某个 key，只有应用雷同的计算形式，即可得悉这个 key 被缓存在哪个服务器上了。

一致性 hash 的劣势

咱们简略理解了一致性 hash 的原理，那它又是如何优化集群中增加节点和缩减节点，一般取模算法导致的缓存服务，大面积不可用的问题呢？

先来看看扩容的场景，如果业务量激增，零碎须要进行扩容减少一台服务器 node-4，刚好node-4 被映射到 node-1 和node-2之间，沿顺时针方向对象映射节点，发现本来缓存在 node-2 上的对象 key-4、key-5 被从新映射到了 node-4 上，而整个扩容过程中受影响的只有 node-4 和node-1节点之间的一小部分数据。

反之，如果 node-1 节点宕机，沿顺时针方向对象映射节点，缓存在 node-1 上的对象 key-1 被从新映射到了 node-4 上，此时受影响的数据只有 node-0 和node-1之间的一小部分数据。

从上边的两种状况发现，当集群中服务器的数量产生扭转时，一致性 hash 算只会影响少部分的数据，保障了缓存零碎整体还能够对外提供服务的。

数据偏斜问题

前边为了便于了解原理，画图中的 node 节点都很理想化的绝对均匀分布，但现实和理论的场景往往差异很大，就比方办了个健身年卡的我，只去过健身房两次，还只是洗了个澡。

在服务器节点数量太少的状况下，很容易因为节点散布不平均而造成 数据歪斜 问题，如下图被缓存的对象大部分缓存在 node-4 服务器上，导致其余节点资源节约，零碎压力大部分集中在 node-4 节点上，这样的集群是十分不衰弱的。

解决数据歪斜的方法也简略，咱们就要想方法让节点映射到 hash 环上时，绝对散布平均一点。

一致性 Hash 算法引入了一个 虚构节点 机制，即对每个服务器节点计算出多个 hash 值，它们都会映射到 hash 环上，映射到这些虚构节点的对象 key，最终会缓存在实在的节点上。

虚构节点的 hash 计算通常能够采纳，对应节点的 IP 地址加数字编号后缀 hash（10.24.23.227#1) 的形式，举个例子，node- 1 节点 IP 为 10.24.23.227，失常计算 node-1 的 hash 值。

• hash（10.24.23.227#1）% 2^32

假如咱们给 node- 1 设置三个虚构节点，node-1#1、node-1#2、node-1#3，对它们进行 hash 后取模。

• hash（10.24.23.227#1）% 2^32
• hash（10.24.23.227#2）% 2^32
• hash（10.24.23.227#3）% 2^32

下图退出虚构节点后，原有节点在 hash 环上散布的就绝对平均了，其余节点压力失去了摊派。

但须要留神一点，调配的虚构节点个数越多，映射在 hash 环上才会越趋于平均，节点太少的话很难看出成果

引入虚构节点的同时也减少了新的问题，要做虚构节点和实在节点间的映射，对象 key-> 虚构节点 -> 理论节点 之间的转换。

一致性 hash 的利用场景

一致性 hash 在分布式系统中应该是实现负载平衡的首选算法，它的实现比拟灵便，既能够在客户端实现，也能够在中间件上实现，比方日常应用较多的缓存中间件 memcached 和redis集群都有用到它。

memcached 的集群比拟非凡，严格来说它只能算是 伪集群，因为它的服务器之间不能通信，申请的散发路由齐全靠客户端来的计算出缓存对象应该落在哪个服务器上，而它的路由算法用的就是一致性 hash。

还有 redis 集群中 hash 槽的概念，尽管实现不尽相同，但思维万变不离其宗，看完本篇的一致性 hash，你再去了解 redis 槽位就轻松多了。

其它的利用场景还有很多：

• RPC框架 Dubbo 用来抉择服务提供者
• 分布式关系数据库分库分表：数据与节点的映射关系
• LVS负载平衡调度器
• …………………

总结

简略的论述了下一致性 hash，如果有不对的中央大家能够留言斧正，任何技术都不会美中不足，一致性 Hash 算法也是有一些潜在隐患的，如果 Hash 环上的节点数量十分宏大或者更新频繁时，检索性能会比拟低下，而且整个分布式缓存须要一个路由服务来做负载平衡，一旦路由服务挂了，整个缓存也就不可用了，还要思考做高可用。

不过话说回来，只有是能解决问题的都是好技术，有点副作用还是能够忍耐的。