面试官经常问的一致性哈希算法，原来这么简单

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

• 一致性哈希算法经典实用场景

• 一致性哈希算法通常不适合用于服务类负载均衡

• 面试应对之策

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

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

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

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

1.1 在分布式缓存领域上述算法的弊端

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

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

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

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

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

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

1.2 一致性哈希算法

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

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

扩容后的示例图：

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

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

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

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

• 顺时针选择节点
  可以使用TreeMap，一来具备排序功能，天然提供了相应的方法获取顺时针的一个元素。
  TreeMap 的 ceilingEntry()方法用于返回与大于或等于给定键元素(ele)的最小键元素链接的键值对。

• 虚拟节点如何生成分散的哈希值
  生成分散的哈希值，通常可以基于md5来实现。
  

  

2、一致性哈希算法被“滥用”

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

在Dubbo中为了实现客户端在服务调用时对服务提供者进行负载均衡，官方也提供了一致性哈希算法；在RocketMQ集群消费模式时消费队列的负载均衡机制竟然也实现了一致性哈希算法，但我觉得一致性哈希算法在这些领域完全无法发挥其他优势，比轮循、加权轮循、随机、加权随机算法等负载均衡算法相比，实现复杂，性能低下，运维管理复杂。

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

3、面试应对之策

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

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

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