一致性哈希

普通hash算法

普通的hash算法在分布式应用中的不足

在分布式的存储系统中，要将数据存储到具体的节点上，如果我们采用普通的hash算法进行路由，将数据映射到具体的节点上，如key%N，key是数据的哈希值，N是服务器节点数。

如果有一个节点加入或退出这个集群，也就意味着几乎缓存值对应的节点都发生了改变。即几乎所有的缓存值都失效了。节点在接收到对应的请求时，均需要重新去数据源获取数据，容易引起 缓存雪崩。

一致性哈希

一致性哈希原理

哈希算法是对节点的数量进行取模运算，而一致性哈希是对2^32进行取模运算。一致性哈希将整个哈希值空间组成一个虚拟的圆环，也就是哈希环。

计算节点/机器(通常使用节点的名称、编号和 IP 地址)的哈希值，放置在环上。
计算 key 的哈希值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点/机器。

一致性哈希原理

在一致性哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是会寻址到此节点和前一节点之间的数据。

一致性哈希数据倾斜

在一致性哈希算法中，如果节点太少，容易因为节点分布不均匀造成数据访问的冷热不均，也就是说大多数访问请求都会集中少量几个节点上。

数据倾斜

通过引入虚拟节点解决分布不均匀的问题。对每一个服务器节点计算多个哈希值，每个计算结果位置上都放置一个虚拟节点，并将虚拟节点映射到实际节点。比如，可以在主机名后面增加编号，分别计算Node-A-01、Node-A-02、Node-B-01、Node-B-02、Node-C-01、Node-C-02的哈希值，于是形成6个虚拟节点。

虚拟节点

增加了节点后，节点在哈希环上的分布就相对均匀了。如果有访问请求寻址到Node-A-01这个虚拟节点，将被重定位到节点A。

参考：

一致性哈希算法详解

实现

字段

type Map struct {
	hash     Hash           // hash函数，crc32哈希
	replicas int            // 虚拟节点倍数
	keys     []int          // 哈希环，环中元素是已经排序的
	hashMap  map[int]string // 虚拟节点和真实节点的映射关系
}

虚拟节点和真实节点的倍数关系
虚拟节点和真实节点的映射关系

方法

Add添加缓存节点
- 虚拟节点名称为序号+key名称
- 循环replicas次，计算虚拟节点的哈希值，进行类型转换
- 添加到哈希环中
- 维护虚拟节点到真实节点之间的映射
- 最后对哈希环排序
Get选择缓存节点
- 校验数据有效性
- 计算key的哈希值
- 顺时针找到哈希环上的第一个匹配的虚拟节点的下标
- 通过hashMap定位到真实的缓存节点

package consistenthash

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

// Hash hash函数类型
type Hash func(data []byte) uint32

type Map struct {
	hash     Hash           // hash函数，crc32哈希
	replicas int            // 虚拟节点倍数
	keys     []int          // 哈希环，环中元素是已经排序的
	hashMap  map[int]string // 虚拟节点和真实节点的映射关系
}

// New 创建一个Map实例
func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string), // 初始化map函数，map必须要进行初始化
	}

	// 默认用crc32
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

// Add 可以一次性添加多个缓存服务器
func (m *Map) Add(keys ...string) {
	for _, key := range keys {

		// 虚拟节点名称为序号+key名称
		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
		}
	}
	// 对哈希环进行排序
	sort.Ints(m.keys)
}

// Get 选择缓存节点函数
func (m *Map) Get(key string) string {
	// 校验数据有效性
	if len(m.keys) == 0 {
		return ""
	}

	// 计算key的哈希值
	hash := int(m.hash([]byte(key)))
	// 顺时针找到哈希环上的第一个匹配的虚拟节点的下标
	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)]]
}