1.什么是一致性哈希

对于分布式存储，不同机器上存储不同对象的数据，那么该使用什么方式去找到目标缓存在哪个节点上呢？使用哈希函数建立从数据到服务器之间的映射关系是一种方式。
其次，一致性哈希可用于分布式集群缓存的负载均衡实现，比如 memcached 缓存集群，需要把缓存数据的 key 利用哈希函数散列，这样缓存数据能够均匀分布到各个分布式存储节点上，要实现这样的负载均衡一般可以用哈希算法来实现。

一句话概括一致性哈希：就是普通取模哈希算法的改良版，哈希函数计算方法不变，只不过是通过构建环状的Hash空间代替普通的线性Hash空间。

对于缓存集群内的每个存储服务器节点计算Hash值，可以用服务器的 IP 或主机名计算得到哈希值，计算得到的哈希值就是服务节点在Hash环上的位置。对每个需要存储的数据key同样也计算一次哈希值，计算之后的哈希也映射到环上，数据存储的位置是沿顺时针的方向找到的环上的第一个节点。

2.为什么使用一致性哈希

问题一和二要结合看，即就是普通hash面临扩展性和容错性问题

2.1 问题一：普通哈希的扩展性问题（新加节点）

如果采用普通的随机选择或顺序选择节点进行访问，假设第一次随机选取了节点 1 ，节点 1 从数据源获取到数据的同时缓存该数据；那第二次，只有 1/10 的可能性再次选择节点 1, 有 9/10 的概率选择了其他节点，如果选择了其他节点，就意味着需要再一次从数据源获取数据，一般来说，这个操作是很耗时的。这样做，一是缓存效率低，二是各个节点上存储着相同的数据，浪费了大量的存储空间。
想到就是采用hash函数，使用特定的算法去保证同一个对象能准确的访问同一个节点。
一致性hash解决扩展性问题是避免了移动大量节点的值，而是只面向移动数据的两个节点。

2.2 问题二：普通hash的容错性问题（节点下线）

简单hash函数面临缓存雪崩的问题，如下
一致性hash算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，节点之间的数据迁移只限于两个节点之间，不会造成全局的网络问题。
普通哈希算法当某一服务节点宕机下线，也会导致原来哈希映射的大面积失效，失效的映射触发数据迁移影响缓存服务性能，容错能力不足。一起来看下一致性哈希是如何提升容错能力的。

2.3 一致性哈希优化

一致性哈希面临数据倾斜和节点雪崩。
数据倾斜，即较少的服务节点哈希值聚集在一起，值都映射到了同一个节点上，如下图。

节点雪崩可以由数据倾斜和节点宕机引起，即过多的缓存数据集中到了一个节点上导致一个节点承受不了，崩了，然后又积累到下一个节点，连锁反应导致的整个缓存集群不可用。
为了避免上诉两个问题，采用虚拟节点进行一致性哈希的优化！

2.4 虚拟节点

虚拟节点，就是对原来单一的物理节点在哈希环上虚拟出几个它的分身节点，这些分身节点称为「虚拟节点」。
解决数据倾斜
打到分身节点上的数据实际上也是映射到分身对应的物理节点上，这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分，解决了数据倾斜问题。
解决节点雪崩
由于虚拟节点分散在哈希环各个部分，当某个节点宕机下线，他所存储的数据会被均匀分配给其他各个节点，避免对单一节点突发压力导致的节点雪崩问题。

3.代码实现

首先实现一致性哈希的思路如下：

一致性哈希算法将 key 映射到 2^32 的空间中，将这个数字首尾相连，形成一个环。
1.计算节点/机器(通常使用节点的名称、编号和 IP 地址)的哈希值，放置在环上。
2.计算 key 的哈希值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点/机器。

引入虚拟节点

需要加一个映射，即代码中需要一个map来记录哪些节点是本节点的虚拟节点。
假设 1 个真实节点对应 3 个虚拟节点，那么 peer1 对应的虚拟节点是 peer1-1、 peer1-2、 peer1-3（通常以添加编号的方式实现），其余节点也以相同的方式操作。
1.计算虚拟节点的 Hash 值，放置在环上。
2.计算 key 的 Hash 值，在环上顺时针寻找到应选取的虚拟节点，例如是 peer2-1，那么就对应真实节点 peer2。

package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

// Hash maps bytes to uint32
// 采取依赖注入的方式，允许用于替换成自定义的Hash函数
// 默认是crc32.ChecksumIEEE
type Hash func(data []byte) uint32

// Map constains all hashed keys
// 一致性哈希的主数据结构
type Map struct {
	// 哈希函数
	hash     Hash
	// 虚拟节点倍数
	// 即根据真实节点创建replicas个虚拟节点
	replicas int
	// 哈希环
	keys     []int // Sorted
	// 虚拟节点与真实节点的映射表
	// 键是虚拟节点的哈希值，值是真实节点的名称
	hashMap  map[int]string
}

// New creates a Map instance
// 构造函数，创建Map实例
// 支持自定义虚拟节点倍数和Hash函数
func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

// Add adds some keys to the hash.
// 允许可变长的参数keys（函数允许传入0或多个真实节点的名称）
func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		// 对每一个真实节点key，对应创建m.replicas个虚拟节点
		for i := 0; i < m.replicas; i++ {
			// 虚拟节点的名称是：strconv.Itoa(i)+key
			// m.hash()计算虚拟节点的哈希值
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			// 将节点哈希值添加到环上
			m.keys = append(m.keys, hash)
			// 增加虚拟节点和真实节点的映射关系
			m.hashMap[hash] = key
		}
	}
	// 对环上的哈希值排序（升序）
	sort.Ints(m.keys)
}

// Get gets the closest item in the hash to the provided key.
//
func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}

	// key是节点名称，通过其计算得到key的哈希值
	hash := int(m.hash([]byte(key)))
	// Binary search for appropriate replica.
	/*
		func Search(n int, f func(int) bool) int
		Search函数采用二分法搜索找到[0,n)区间内最小的满足f(i)==true的值i
	 */
	// idx是顺时针找到的第一个匹配的虚拟节点下标
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})

	// 因为是环，所以要取余
	// 返回虚拟节点在hashMap映射到的真实节点
	return m.hashMap[m.keys[idx%len(m.keys)]]
}

4.验证

说明引用下图

// 计算hash值的函数如下
hash := New(3, func(key []byte) uint32 {
	i, _ := strconv.Atoi(string(key))
	return uint32(i)
})
// 虚拟节点的哈希值计算如下
for _, key := range keys {
	// 对每一个真实节点key，对应创建m.replicas个虚拟节点
	for i := 0; i < m.replicas; i++ {
		// 虚拟节点的名称是：strconv.Itoa(i)+key
		// m.hash()计算虚拟节点的哈希值
		hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
		// 将节点哈希值添加到环上
		m.keys = append(m.keys, hash)
		// 增加虚拟节点和真实节点的映射关系
		m.hashMap[hash] = key
	}
}

测试代码如下

package consistenthash

import (
	"strconv"
	"testing"
)

func TestHashing(t *testing.T) {
	hash := New(3, func(key []byte) uint32 {
		i, _ := strconv.Atoi(string(key))
		return uint32(i)
	})

	// Given the above hash function, this will give replicas with "hashes":
	// 2, 4, 6, 12, 14, 16, 22, 24, 26
	hash.Add("6", "4", "2")

	// key是2，对应会映射到2；11会映射到11，11顺时针最近的是虚拟节点12，对应的也是2；
	// 23顺时针最近是24，对应真实节点是4；27对应顺时针最近是2；
	testCases := map[string]string{
		"2":  "2",
		"11": "2",
		"23": "4",
		"27": "2",
	}

	for k, v := range testCases {
		if hash.Get(k) != v {
			t.Errorf("Asking for %s, should have yielded %s", k, v)
		}
	}

	// Adds 8, 18, 28
	hash.Add("8")

	// 27 should now map to 8.
	testCases["27"] = "8"

	for k, v := range testCases {
		if hash.Get(k) != v {
			t.Errorf("Asking for %s, should have yielded %s", k, v)
		}
	}

}

5.总结

本节最重要的就是理解访问缓存面临的问题，即同一个key可能随机或顺序去访问节点导致效率低下，所以引出使用hash函数，但是传统hash函数面领着扩展性和容错性的问题，所以提出使用一致性哈希。
要明白一致性哈希是什么，它解决什么问题，它怎么解决扩展性和容错性的问题，然后它面临数据倾斜和节点雪崩又是怎么解决的（虚拟节点）。