一致性哈希，原来这么多学问！-技术圈

面试中一致性哈希算法被问到的概率非常大，本文将从如下三个方面探探一致性哈希算法，让大家轻松应对面试，并且说出与众不同的答案。

1、一致性哈希算法经典使用场景

在数据库存储领域如果单表数据量很大，通常会采用分库分表，在缓存领域同样需要分库，下面以一个非常常见的Redis分库架构为例进行阐述。

将上述3个Redis节点称之为分片，每一个节点存储部分数据，需要使用负载均衡算法，将数据尽量分摊到各个节点，充分发挥分布式的优势，提升系统缓存访问的性能。

在分布缓存领域，对数据存在新增与查询，即数据通过路由算法存储在某一个节点后，查询时需要尽量路由到同一个节点，否则会出现查询未命中缓存的情况，这也是与分布式服务调用领域的负载算法一个不同点。

分布式缓存存储类领域的负载均衡算法通常会使用某一个字段当分片键，在进行负载之前先求出分片字段对应的 HashCode，然后与当前的节点数取模。即 hashcode(分片键) % 节点总数(分片总数)。

先哈希再取模实现起来简单高效，但在分布式缓存领域存在一个致命的痛点，对扩容、缩容不友好，会降低缓存的命中率。

因扩容引起的数据命中率问题示意图如下：

例如当前集群中由 3 个节点存储，现在向集群中写入 6 个数据，其分片键的 hashcode 为 1-6，数据的分布情况如上述所示。

但由于随着业务的急剧增长，3 台 redis 已经无法满足业务的需求，项目组决定对其进行扩容，从原先的 3 台扩容到 4 台，这个时候项目组尝试去缓存中查找 k1, k2, k3, k4, k5, k6 时会出现什么问题？

根据 hashcode 再取模的方式，由于数量从3台到4台，经路由算法路由后，k4 会尝试从 3.169 的机器去查找，但对应的数据却存储在 3.166 上，以上面 6 个key的命中来看，只有 50% 的命中率，扩容后带来缓存穿透，大量数据进入穿透到后台数据库。

面对上述问题第一种解决方案：成倍扩容。将原来的 3 个节点数量翻倍，新增加的第一台数据来源于第一台，以此类推，第 6 台的数据来源于第 3 台，这样 k6 经过新的负载均衡算法会落到第 6 台，避免了缓存穿透。

成倍扩容能有效解决扩容后带来的缓存穿透问题，但这样做会造成资源的浪费，有没有其他更好的方法呢？

一致性哈希算法闪亮登场。

一致性哈希算法的设计理念如下图所示：

首先将哈希值映射到 0 ~ 2 的 32 次方的一个圆中，然后将实际的物理节点的IP地址或取其可以表示一个节点的 hash 值，放入到 hash 环中。

然后对需要插入的数据先求哈希，再顺时针沿着哈希环，找到第一个实际节点，数据将存储到该实际节点上。

扩容后的示例图：

从中可以看到受影响的范围能控制在两个节点的 hashcode 之间的部分数据，比起先哈希再取模，其未命中率将会得到极大的影响。

但一致性哈希算法要得到较好的效果，取决于各个实体节点在哈希环的分布情况，是否能分散，例如如下分布则会大打折扣：

这种情况会造成数据分布不均衡，为了解决数据很可能分布不均匀的情况，对一致性哈希算法，提出了改进，引入了虚拟节点的，可以设置一个哈希环中存在多少个虚拟节点，然后将虚拟节点映射到实体节点，从而解决数据分布不均衡的问题。

这样通过为不同的的实际节点映射到多个虚拟节点，实现数据的均匀分布，并且扩容或缩容时并不会出现大面积的缓存穿透。

温馨提示：上述的映射只是一个理想状态，其核心思路是为每一个实体节点创建多个虚拟节点，并且核心虚拟节点的Hash值越分散越好。

大家可以思考一下，如何用JAVA来实现一致性哈希算法？

一致性哈希算法的两个关键：

顺时针选择节点
可以使用TreeMap，一来具备排序功能，天然提供了相应的方法获取顺时针的一个元素。TreeMap 的 ceilingEntry()方法用于返回与大于或等于给定键元素(ele)的最小键元素链接的键值对。
虚拟节点如何生成分散的哈希值
生成分散的哈希值，通常可以基于md5来实现。

一致性哈希算法在面对分布式缓存有着得天独厚的优势，因为它的产生就是为了解决分布式缓存扩容、缩容带来的缓存穿透问题。但现在一致性在分布式服务调用的负载算法竟然也提供了一致性哈希算法的实现。

在Dubbo中为了实现客户端在服务调用时对服务提供者进行负载均衡，官方也提供了一致性哈希算法；

在RocketMQ集群消费模式时消费队列的负载均衡机制竟然也实现了一致性哈希算法。

但我觉得一致性哈希算法在这些领域完全无法发挥其他优势，比轮循、加权轮循、随机、加权随机算法等负载均衡算法相比，实现复杂，性能低下，运维管理复杂。

因为在服务调用等负载均衡算法，多次服务调用之间关联性不太强，在服务端扩容、缩容后，对于客户端来说其实并不关心路由到哪台服务器，其关心的是能否返回一台服务器即可。

在面试过程中，遇到一致性哈希算的时候，尽量能从其使用场景：分布式缓存负载均衡，特别是突出扩容、缩容能有效避免缓存穿透的问题。同时需要阐述一致性哈希算法的缺陷以及其应对策略(虚拟节点)。

聊的差不多可以顺便提一下阅读过一致性哈希算法的源码：强调TreeMap与虚拟节点哈希值的生成方法。

最后可以尝试引导面试官聊聊现在一致性哈希算法有点被滥用的嫌疑，在轻松愉快的讨论中与面试交流技术，面试官好评度蹭蹭往上涨。

本文就介绍到这里了，麻烦点亮在看，点赞、转发、留言是对我最大的鼓励。


精彩热文TOP3

这篇文章出自好基友丁哥，他出版了《RocketMQ 技术内幕》一书，荣获 RocketMQ 官方社区优秀布道师，在 MQ 领域有着较大的影响力，他将他日均千亿级消息的 MQ 运维经验整理成了电子书，关注下方公众号回复 RMQPDF 即可免费获取。

下面是丁哥的个人微信号，有任何中间件有关的技术问题，可以撩他讨论。