算法|面试时遇到一致性哈希算法这样回答会让面试官眼前一亮中间件|redis|java|分布式

做积极的人，越努力越幸运！
文章图片

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

一致性哈希算法经典实用场景
一致性哈希算法通常不适合用于服务类负载均衡
面试应对之策

1、一致性哈希算法经典使用场景在数据库存储领域如果单表数据量很大，通常会采用分库分表，在缓存领域同样需要分库，下面以一个非常常见的Redis分库架构为例进行阐述。

文章图片
将上述3个Redis节点称之为分片，每一个节点存储部分数据，需要使用负载均衡算法，将数据尽量分摊到各个节点，充分发挥分布式的优势，提升系统缓存访问的性能。在分布缓存领域，对数据存在新增与查询，即数据通过路由算法存储在某一个节点后，查询时需要尽量路由到同一个节点，否则会出现查询未命中缓存的情况，这也是与分布式服务调用领域的负载算法一个不同点。
分布式缓存存储类领域的负载均衡算法通常会使用某一个字段当分片键，在进行负载之前先求出分片字段对应的HashCode，然后与当前的节点数取模。即 hashcode(分片键) % 节点总数(分片总数)。
1.1 在分布式缓存领域上述算法的弊端先哈希再取模实现起来简单高效，但在分布式缓存领域存在一个致命的痛点，对扩容、缩容不友好，会降低缓存的命中率。
因扩容引起的数据命中率问题示意图如下：

文章图片

例如当前集群中由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台，数据原本存在于第3台，而第6台的数据来源于第3台，这样避免了缓存穿透。
成倍扩容能有效解决扩容后带来的缓存穿透问题，但这样做会造成资源的浪费，有没有其他更好的方法呢？
一致性哈希算法闪亮登场。
1.2 一致性哈希算法一致性哈希算法的设计理念如下图所示：

文章图片
首先将哈希值映射到 0 ~ 2的32次方的一个圆中，然后将实际的物理节点的IP地址获取其可以表示一个节点的hash值，放入到hash环中。然后对需要插入的数据先求哈希，再顺时针沿着哈希环，找到第一个实际节点，数据将存储到该实际节点上。
扩容后的示例图：

文章图片

从中可以看到受影响的范围能控制在两个节点的hashcode之间的部分数据，比起先哈希再取模，其未命中率将会得到极大的影响。但一致性哈希算法要得到较好的效果，取决于各个实体节点在哈希环的分布情况，是否能分散，例如如下分布则会大打折扣：

文章图片

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

文章图片

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

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

大家可以思考一下，如何用JAVA来实现一致性哈希算法？
一致性哈希算法的两个关键：

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

文章图片

2、一致性哈希算法被“滥用” 一致性哈希算法在面对分布式缓存有着得天独厚的优势，因为它的产生就是为了解决分布式缓存扩容、缩容带来的缓存穿透问题。但现在一致性在分布式服务调用的负载算法竟然也提供了一致性哈希算法的实现。
在Dubbo中为了实现客户端在服务调用时对服务提供者进行负载均衡，官方也提供了一致性哈希算法；在RocketMQ集群消费模式时消费队列的负载均衡机制竟然也实现了一致性哈希算法，但我觉得一致性哈希算法在这些领域完全无法发挥其他优势，比轮循、加权轮循、随机、加权随机算法等负载均衡算法相比，实现复杂，性能低下，运维管理复杂。
因为在服务调用等负载均衡算法，多次服务调用之间关联性不太强，在服务端扩容、缩容后，对于客户端来说其实并不关心路由到哪台服务器，其关心的是能否返回一台服务器即可。
3、面试应对之策在面试过程中，遇到一致性哈希算的时候，尽量能从其使用场景：分布式缓存负载均衡，特别是突出扩容、缩容能有效避免缓存穿透的问题。同时需要阐述一致性哈希算法的缺陷以及其应对策略(虚拟节点)。
聊的差不多可以顺便提一下阅读过一致性哈希算法的源码：强调TreeMap与虚拟节点哈希值的生成方法。
最后可以尝试引导面试官聊聊现在一致性哈希算法有点被滥用的嫌疑，在轻松愉快的讨论中与面试交流技术，面试官好评度蹭蹭往上涨。
这篇文章来自于我的好基友的公众号「中间件兴趣圈」，由《RocketMQ技术内幕》作者，RocketMQ社区优秀布道师维护，主打成体系分享JAVA主流中间件，打造完备的互联网架构体系，目前涵盖Java并发、微服务、消息、调度、数据异构等领域，未来继续关注监控、在线诊断等领域。
回复【RMQPDF】可以领取由阿里巴巴根据我RocketMQ专栏整理的电子书：