IT评测·应用市场-qidao123.com技术社区

标题: golang分布式缓存项目 Day4 一致性哈希 [打印本页]

---

作者: 南七星之家    时间: 2024-11-13 13:37
标题: golang分布式缓存项目 Day4 一致性哈希
注：该项目原作者：https://geektutu.com/post/geecache-day1.html。本文旨在记录本人做该项目时的一些疑惑解答以及部分的测试样例以便于本人复习
为什么使用一致性哈希

我该访问谁

对于分布式缓存来说，当一个节点吸收到请求，如果该节点并没有存储缓存值，那么它面临的困难是，从谁那获取数据？自己，还是节点1, 2, 3, 4… 。假设包括自己在内一共有 10 个节点，当一个节点吸收到请求时，随机选择一个节点，由该节点从数据源获取数据。
假设第一次随机选取了节点 1 ，节点 1 从数据源获取到数据的同时缓存该数据；那第二次，只有 1/10 的可能性再次选择节点 1, 有 9/10 的概率选择了其他节点，如果选择了其他节点，就意味着须要再一次从数据源获取数据，一般来说，这个操纵是很耗时的。这样做，一是缓存服从低，二是各个节点上存储着雷同的数据，浪费了大量的存储空间。
那有什么办法，对于给定的 key，每一次都选择同一个节点呢？使用 hash 算法也能够做到这一点。那把 key 的每一个字符的 ASCII 码加起来，再除以 10 取余数可以吗？当然可以，这可以以为是自界说的 hash 算法。
在这里插入图片描述

从上面的图可以看到，任意一个节点任意时刻请求查找键 Tom 对应的值，都会分配给节点 2，有效地解决了上述的标题。
节点数量变化了怎么办？

简单求取 Hash 值解决了缓存性能的标题，但是没有思量节点数量变化的场景。假设，移除了此中一台节点，只剩下 9 个，那么之前 hash(key) % 10 变成了 hash(key) % 9，也就意味着险些缓存值对应的节点都发生了改变。即险些全部的缓存值都失效了。节点在吸收到对应的请求时，均须要重新去数据源获取数据，容易引起 缓存雪崩。
那如何解决这个标题呢？一致性哈希算法可以。
算法原理

步骤

一致性哈希算法将 key 映射到 2^32 的空间中，将这个数字首尾相连，形成一个环。

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

PS：下面的图片是哈希环。此中key11, key2…在环上的位置是由其哈希值（由一个特殊函数算法）决定的，每一个key所用的节点是在环上顺时间取到的第一个节点peer

环上有 peer2，peer4，peer6 三个节点，key11，key2，key27 均映射到 peer2，key23 映射到 peer4。此时，如果新增节点/机器 peer8，假设它新增位置如图所示，那么只有 key27 从 peer2 调整到 peer8，其余的映射均没有发生改变。
也就是说，一致性哈希算法，在新增/删除节点时，只须要重新定位该节点附近的一小部分数据，而不须要重新定位全部的节点，这就解决了上述的标题
数据倾斜标题

如果服务器的节点过少，容易引起 key 的倾斜。例如上面例子中的 peer2，peer4，peer6 分布在环的上半部分，下半部分是空的。那么映射到环下半部分的 key 都会被分配给 peer2，key 过度向 peer2 倾斜，缓存节点间负载不均。
为相识决这个标题，引入了假造节点的概念，一个真实节点对应多个假造节点。
假设 1 个真实节点对应 3 个假造节点，那么 peer1 对应的假造节点是 peer1-1、 peer1-2、 peer1-3（通常以添加编号的方式实现），其余节点也以雷同的方式操纵。

• 第一步，计算假造节点的 Hash 值，放置在环上。
  
• 第二步，计算 key 的 Hash 值，在环上顺时针寻找到应选取的假造节点，例如是 peer2-1，那么就对应真实节点 peer2。
  

假造节点扩充了节点的数量，解决了节点较少的情况下数据容易倾斜的标题。而且代价非常小，只须要增长一个字典(map)维护真实节点与假造节点的映射关系即可。
Go语言实现

我们在 geecache 目录下新建 package consistenthash，用来实现一致性哈希算法。

1. package consistenthash
3. import (
4.         "hash/crc32"
5.         "sort"
6.         "strconv"
7. )
9. // Hash maps bytes to uint32
10. type HashFunc func(data []byte) uint32
12. // Map constains all hashed keys
13. type Map struct {
14.         hashFunc     HashFunc
15.         replicas int
16.         keys     []int // Sorted
17.         hashMap  map[int]string
18. }
20. // New creates a Map instance
21. func New(replicas int, fn HashFunc) *Map {
22.         m := &Map{
23.                 replicas: replicas,
24.                 hashFunc:     fn,
25.                 hashMap:  make(map[int]string),
26.         }
27.         if m.hash == nil {
28.                 m.hashFunc = crc32.ChecksumIEEE//如果没有输入哈希函数，则使用默认哈希函数crc32.ChecksumIEEE
29.         }
30.         return m
31. }

复制代码

• 界说了函数范例 Hash，采取依赖注入的方式，答应用于替换成自界说的 Hash 函数，也方便测试时替换，默以为
  crc32.ChecksumIEEE 算法。
  
• Map 是一致性哈希算法的主数据布局，包罗 4 个成员变量：Hash 函数 hash；假造节点倍数 replicas；哈希环
  keys；假造节点与真实节点的映射表 hashMap，键是假造节点的哈希值，值是真实节点的名称。
  
• 构造函数 New() 答应自界说假造节点倍数和 Hash 函数。
  

接下来，实现添加真实节点/机器的 Add() 方法。

1. // Add adds some keys to the hash.
2. func (m *Map) Add(keys ...string) {
3.         for _, key := range keys {
4.                 for i := 0; i < m.replicas; i++ {
5.                         hash := int(m.hashFunc([]byte(strconv.Itoa(i) + key)))//strconv.Itoa()函数用于将整数转换为字符串
6.                         m.keys = append(m.keys, hash)
7.                         m.hashMap[hash] = key
8.                 }
9.         }
10.         sort.Ints(m.keys)
11. }

复制代码

• Add 函数答应传入 0 或 多个真实节点的名称。
  
• 对每一个真实节点 key，对应创建 m.replicas 个假造节点，假造节点的名称是：strconv.Itoa(i) + key，即通过添加编号的方式区分不同假造节点.
  
• 使用 m.hash() 计算假造节点的哈希值，使用 append(m.keys, hash) 添加到环上。
  
• 在 hashMap 中增长假造节点和真实节点的映射关系。
  
• 最后一步，环上的哈希值排序。
  

最后一步，实现选择节点的 Get() 方法。

1. // Get gets the closest item in the hash to the provided key.
2. func (m *Map) Get(key string) string {
3.         if len(m.keys) == 0 {
4.                 return ""
5.         }
7.         hash := int(m.hashFunc([]byte(key)))
8.         // Binary search for appropriate replica.
9.         idx := sort.Search(len(m.keys), func(i int) bool {
10.                 return m.keys[i] >= hash
11.         })
13.         return m.hashMap[m.keys[idx%len(m.keys)]]
14. }

复制代码

• 选择节点就非常简单了，第一步，计算 key 的哈希值。
  
• 第二步，顺时针找到第一个匹配的假造节点的下标 idx，从 m.keys 中获取到对应的哈希值。如果 idx == len(m.keys)，阐明应选择 m.keys[0]，因为 m.keys 是一个环状布局，所以用取余数的方式来处理这种情况。
  
• 第三步，通过 hashMap 映射得到真实的节点。
  

sort.Search函数的用法：
函数署名

1. func Search(n int, f func(int) bool) int

复制代码

参数
n：表示要搜索的集合的大小，通常是切片的长度。
f：是一个函数，它接受一个整数参数 i，并返回一个布尔值。这个函数界说了搜索的条件。
工作原理
sort.Search 会找到并返回 [0, n) 范围内，使得 f(i) 为 true 的最小索引 i。如果不存在这样的索引，Search 返回 n。Search 要求 f 对于输入范围 [0, n) 的某些（可能为空）前缀为 false，然后对（可能为空）余数为 true；Search 返回第一个 true 的索引。
常见用途
sort.Search 常用于在排序的、可索引的数据布局（例如数组或切片）中查找值 x 的索引 i。在这种情况下，参数 f（通常是闭包）捕获要搜索的值，以及数据布局的索引和排序方式。
示例代码

1. package main
3. import (
4.     "fmt"
5.     "sort"
6. )
8. func main() {
9.     data := []int{1, 2, 3, 5, 10}
10.     target := 4
11.     index := sort.Search(len(data), func(i int) bool {
12.         return data[i] >= target
13.     })
14.     if index < len(data) && data[index] == target {
15.         // target is present at data[index]
16.         fmt.Printf("找到了不小于 %d 的元素，索引为 %d，值为 %d\n", target, index, data[index])
17.     } else {
18.         // target is not present in data,
19.         // but index is the index where it would be inserted.
20.         fmt.Printf("没有找到不小于 %d 的元素，索引为 %d\n", target, index)
21.     }
22. }

复制代码

至此，整个一致性哈希算法就实现完成了。
测试

1. package consistenthash
3. import (
4.         "strconv"
5.         "testing"
6. )
8. func TestHashing(t *testing.T) {
9.         hash := New(3, func(key []byte) uint32 {
10.                 i, _ := strconv.Atoi(string(key))
11.                 return uint32(i)
12.         })
14.         // Given the above hash function, this will give replicas with "hashes":
15.         // 2, 4, 6, 12, 14, 16, 22, 24, 26
16.         hash.Add("6", "4", "2")
18.         testCases := map[string]string{
19.                 "2":  "2",
20.                 "11": "2",
21.                 "23": "4",
22.                 "27": "2",
23.         }
25.         for k, v := range testCases {
26.                 if hash.Get(k) != v {
27.                         t.Errorf("Asking for %s, should have yielded %s", k, v)
28.                 }
29.         }
31.         // Adds 8, 18, 28
32.         hash.Add("8")
34.         // 27 should now map to 8.
35.         testCases["27"] = "8"
37.         for k, v := range testCases {
38.                 if hash.Get(k) != v {
39.                         t.Errorf("Asking for %s, should have yielded %s", k, v)
40.                 }
41.         }
43. }

复制代码

如果要举行测试，那么我们须要明确地知道每一个传入的 key 的哈希值，那使用默认的 crc32.ChecksumIEEE 算法显然达不到目标。所以在这里使用了自界说的 Hash 算法。自界说的 Hash 算法只处理数字，传入字符串表示的数字，返回对应的数字即可。

• 一开始，有 2/4/6 三个真实节点，对应的假造节点的哈希值是 02/12/22、04/14/24、06/16/26。
  
• 那么用例 2/11/23/27 选择的假造节点分别是 02/12/24/02，也就是真实节点 2/2/4/2。
  
• 添加一个真实节点 8，对应假造节点的哈希值是 08/18/28，此时，用例 27 对应的假造节点从 02 变动为 28，即真实节点 8。
  

PS：为什么2/4/6 三个真实节点，对应的假造节点的哈希值是 02/12/22、04/14/24、06/16/26？
：因为我们将节点值先转换为string范例， 再转换成[]byte范例。在转换成string范例后加上i = 0, 1, 2后，是直接在数据前相加的，也就是"0" + “2” = “02”, “1” + “2” = “12”, “2” + “2” = “22”…

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4