一致性 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 取余，得到该用户对应的缓存服务器。如下图所示:

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

hash(username) % 3hash(username) % 4

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

一致性 Hash 的原理

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

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

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

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

Node-ANode-BNode-CNode-CNode-C

缓存失效的缓解

以上就是正常情况下一致性 Hash 的使用，接下来我们看下，一致性 Hash 是如何应对集群的扩缩容的。

New-Node

Node-BNewNodeNode-CNewNode
Node-ANode-BNewNodeNode-BNode-CNode-C

一致性 Hash 利用有序 Hash 环，巧妙的缓解了集群扩缩容造成的缓存失效问题。注意，这里说的是 “缓解”，缓存失效问题无法完全避免，但是可以将其影响降到最低。

hash(ip:port)

数据倾斜与虚拟节点

以上介绍了一致性 hash 的基本过程，这么看来，一致性 hash 作为缓解缓存失效的手段，的确是行之有效的。

Node-ANode-BNode-B(Node-A, Node-B]Node-Ahash < Node-Ahash > Node-B
Node-ANode-BNode-ANode-B

对于此类问题，我们可以引入虚拟节点的概念，或者说是副本节点。每个真实的缓存 Server 在 Hash 环上都对应多个虚拟节点。如下图所示：

V-Node-ANode-A
GroupCache 的一致性 Hash 实现

GroupCache 提供了一个简单的一致性 hash 的实现。其代码在 github.com/golang/groupcache/consistenthash。

我们先看下它的使用方法：

import (
	"fmt"
	"github.com/golang/groupcache/consistenthash"
)

func main() {
	// 构造一个 consistenthash 对象，每个节点在 Hash 环上都一共有三个虚拟节点。
	hash := consistenthash.New(3, nil)

	// 添加节点
	hash.Add(
		"127.0.0.1:8080",
		"127.0.0.1:8081",
		"127.0.0.1:8082",
	)

	// 根据 key 获取其对应的节点
	node := hash.Get("cyhone.com")

	fmt.Println(node)
}

consistenthash 对外提供了三个函数：

New(replicas int, fn Hash)replicasfnAddGet

Add 函数

我们先看下其 Add 函数的实现。Add 函数用于向 Hash 环上添加节点。其源码如下：

func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		for i := 0; i < m.replicas; i++ {
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			m.keys = append(m.keys, hash)
			m.hashMap[hash] = key
		}
	}

	// 排序，这个动作非常重要，因为只有这样，才能构造一个有序的 Hash 环
	sort.Ints(m.keys)
}

在 Add 函数里面涉及两个重要的属性:

[]intmap[int]stringkeys
["Node-A", "Node-B"]Node-A0Node-A1Node-A
keys

Get 函数

接下来我们分析下 Get 函数的使用，Get 函数用于给指定 key 分配对应节点。其源码如下：

func (m *Map) Get(key string) string {
	if m.IsEmpty() {
		return ""
	}

	hash := int(m.hash([]byte(key)))

	// Binary search for appropriate replica.
	// 二分查找
	idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })

	// Means we have cycled back to the first replica.
	// 如果没有找到，则使用首元素
	if idx == len(m.keys) {
		idx = 0
	}

	return m.hashMap[m.keys[idx]]
}
sort.Searchkeyskeys
hashMap[keys[idx]]

以上就是 Groupcache 对一致性 Hash 的实现了。这个实现简单有效，可以帮助我们快速理解一致性 Hash 的原理。