一致性 Hash 常用于缓解分布式缓存系统扩缩容节点时造成的缓存大量失效的问题。一致性 Hash 与其说是一种 Hash 算法，其实更像是一种负载均衡策略。

GroupCache 是 golang 官方提供的一个分布式缓存库，其中包含了一个简单的一致性 Hash 的实现。其代码在 github.com/golang/groupcache/consistenthash。本文将会基于 GroupCache 的一致性 Hash 实现，深入剖析一致性 Hash 的原理。

本文会着重探讨以下几点内容：

1. 传统的 Hash 式负载均衡在集群扩缩容时面临的缓存失效问题。
2. 一致性 Hash 的原理。
3. Golang 的开源库 GroupCache 如何实现一致性 Hash。

集群扩缩容导致缓存的问题

我们先看下传统的 Hash 式负载均衡，当集群扩缩容时会遇到哪些问题。

假设我们有三台缓存服务器，每台服务器用于缓存一部分用户的信息。最常见的 Hash 式负载均衡做法是：对于指定用户，我们可以对其用户名或者其他唯一信息计算 hash 值，然后将该 hash 值对 3 取余，得到该用户对应的缓存服务器。如下图所示:

而当我们需要对集群进行扩容或者缩容时，增加或者减少部分服务器节点，将会带来大面积的缓存失效。

例如需要扩容一台服务器，即由 3 台缓存服务器增加为 4 台，那么之前 hash(username) % 3 这种策略，将变更为 hash(username) % 4。整个负载均衡的策略发生了彻底的变化，对于任何一个用户都会面临Hash失效的风险。

而一旦缓存集体失效，所有请求无法命中缓存，直接打到后端服务上，系统很有可能发生崩溃。

一致性 Hash 的原理

针对以上问题，如果使用一致性 Hash 作为缓存系统的负载均衡策略，可以有效缓解集群扩缩容带来的缓存失效问题。

相比于直接对 hash 取模得到目标 Server 的做法，一致性 Hash 采用 有序 Hash 环 的方式选择目标缓存 Server。如下图所示：

对于该有序 Hash 环，环中的每个节点对应于一台缓存 Server，同时每个节点也包含一个整数值。各节点按照该整数值从小到大依次排列。

对于指定用户来说，我们依然首先出计算用户名的 hash 值。接着，在 Hash 环中按照值大小顺序，从小到大依次寻找，找到 第一个大于等于该 hash 值的节点，将其作为目标缓存 Server。

例如，我们 hash 环中的三个节点 Node-A...