不得不说，如今这个以微服务高并发为主导的coder时代，掌握一致性hash的基本原理还是很有必要的。
一致性哈希的原理其实并不复杂，简单来说，就是：
为N台服务器生成互不相同的keyword（比如机器的hostname）；
将关键词用hash算法映射为数字，并使得该数字始终维持在一个范围，如1到2^32次方；
将hash后的数字正序排序，如此以来，N台服务器就会根据自身的keyword生成的数字，分布到一个数字形成的环上，如1到2^32次方首尾相连的环；
将需要存储的变量key同样使用hash算法计算，得到一个1到2^32次方范围内的数字；
对比变量key的数字，与N台服务器的数字值，找到第一个 >=变量key的hash数值 的服务器，即为需要存储到的机器。
此处仅是简单描述一致性哈希的实现步骤，方便后续的代码编写，如果对其原理尚有疑惑的小伙伴，可移步any搜索工具自行查找。
结构预定义：
// 定义一致性hash的方法类型，便于扩展其他hash算法， type HashFn func(data []byte) uint32 type ConsistentHashMap struct { hashFn HashFn // 一致性哈希函数，默认crc32 copyNum int // 机器节点的拷贝份数 vhosts []int // 哈希环上的虚拟节点列表 trueMap map[int]string // 虚拟节点与真实节点的映射map }初始化
func NewChash(copyNum int, fn HashFn) *ConsistentHashMap { m := &ConsistentHashMap{ copyNum: copyNum, hashFn: fn, trueMap: make(map[int]string), } if m.hashFn == nil { m.hashFn = crc32.ChecksumIEEE } return m }添加机器节点
func (c *ConsistentHashMap) AddChash(keys ...string) { for _, realHostKey := range keys { // 根据自定义的拷贝份数，将真实节点复制对应倍数 for i := 0; i < c.copyNum; i++ { // 真实key添加后缀以生成虚拟key节点 vhostKey := []string{strconv.Itoa(i), realHostKey} // 计算虚拟key的crc32值 vhostNum := int(c.hashFn([]byte(strings.Join(vhostKey, "")))) c.vhosts = append(c.vhosts, vhostNum) // 追加到虚拟节点数组 c.trueMap[vhostNum] = realHostKey // 保存虚拟节点到真实节点的映射关系 } } sort.Ints(c.vhosts) // 每次添加节点都要对虚拟节点执行排序 }获取 变量key 被映射到的真实机器节点
func (c *ConsistentHashMap) GetChash(sk string) string { if len(c.vhosts) == 0 { panic("none-c-host") } kNum := int(c.hashFn([]byte(sk))) // 二分查找第一个 >=kNum 的虚拟节点下标 // 即，kNum 在vhosts中的插入位置 L, R := 0, len(c.vhosts)-1 for L <= R { m := (L + R) / 2 if c.vhosts[m] >= kNum { R = m - 1 } else { L = m + 1 // if c.vhosts[m] < kNum } } // 插入到虚拟节点的下标：R+1 insertId := (R + 1) % len(c.vhosts) return c.trueMap[c.vhosts[insertId]] }这个简单版的一致性hash，大约60行代码左右，其中涉及几个小 trick，此处简略提一下：
将hash函数做了自定义扩展；其实默认使用crc32算法基本够用了，之所以自定义，一则是方便后续扩展，二则是为了测试时浅显易懂；
节点数做了虚拟化倍数扩展(代码中的copyNum)；之所以如此，是因为生产环境中的变量key经过hash计算得到的数字，不大可能如我们所愿，均匀分布到1到2^32次方范围内，既然变量key不可控，那就扩展节点数量，节点数量足够多的时候，变量key的分布就会被动变均匀；就和工作一样，如果改变不了他人的看法，那就努力提升自己的实力；
节点的虚拟化扩展方式，就是简单将索引下标添加到服务器keyword之前（代码中的AddChash方法），这个方式可以按实际情况或自己的心情随意定，上面的Demo如此定义是为了便于观察算法结果(参考文末的测试代码)；
获取经过一致性哈希的变量key对应的机器时(GetChash)，使用了二分查找，其实如果只是测试，直接遍历虚拟节点列表vhosts，找到第一个大于变量key的机器即可(vhosts已排序)，但实际应用时，是有性能问题的，假设虚拟化了100个节点，QPS是1万，直接遍历的代价是100万次循环，二分却可使其降到7万次，差距还是很明显的；
二分逻辑旨在获取变量key的hash数值在虚拟节点列表vhosts中的插入位置，但该位置存在溢出情况，即数值超过了vhosts中的所有值，此时的插入位置在列表末尾，下标值变为vhosts长度，超出了下标界限，因此采用了一个取余的小trick，以保证溢出时，下标insertId会取余变为0，保障一致性hash的正常运行。
测试代码如下：
func main() { // trick-1：自定义 hash 方法，专为测试和验证 使用； // 直接将下标id添加到机器key之前，并将其转换为数字，便于验证我们的算法结果 hash := NewChash(3, func(key []byte) uint32 { i, _ := strconv.Atoi(string(key)) return uint32(i) }) // 我们添加 2、4、6 这三台机器key，此时根据我们上面的自定义hash方法可推导出 // 环节点经拼接下标id后共产生：2, 4, 6, 12, 14, 16, 22, 24, 26 等虚拟节点 hash.AddChash("6", "4", "2") // 验证结论 testCases := map[string]string{ "2": "2", // 变量key如果为2，则实际映射到机器2 "11": "2", // 变量key如果为11，同样映射到机器2 "23": "4", // 23，映射到机器4 "27": "2", // 27，映射到机器2 } for k, v := range testCases { if hash.GetChash(k) != v { // 如果不符合我们的预期，则说明，一致性hash算法存在问题 fmt.Printf("Asking for %s, should have yielded %s\n", k, v) } } hash.AddChash("8") // 添加机器8，虚拟节点产生：8, 18, 28 testCases["27"] = "8" // 此时，变量key的27 就应当被映射到机器 8 for k, v := range testCases { if hash.GetChash(k) != v { fmt.Printf("Asking for %s, should have yielded %s\n", k, v) } } }注：本文代码参考了go公共库 groupcache 的部分源码go
赞收藏
分享
阅读 158更新于 11 月 2 日
后厂村村长
7 声望2 粉丝
Hello, Debug World
关注作者
