Skip to content

Latest commit

 

History

History
191 lines (146 loc) · 5.18 KB

02.4.consistent_hash.md

File metadata and controls

191 lines (146 loc) · 5.18 KB
Raw
title date category
4. 一致性哈希
2023-10-10
golang

https://github.com/dreamjz/golang-notes/tree/main/books/7-days-golang/GeeCache/day4-consistent-hash

DAY4-CONSISTENT-HASH
│  go.mod
│  go.work
│  main.go
│  
└─geecache
    │  byteview.go
    │  cache.go
    │  geecache.go
    │  geecache_test.go
    │  go.mod
    │  http.go
    │
    ├─consistenthash
    │      consistenthash.go
    │      consistenthash_test.go
    │
    └─lru
            lru.go
            lru_test.go

1. 一致性哈希(Consistent Hash)

1.1 为何需要一致性哈希

当一个节点收到请求，但是当前节点未存储缓存值，此时节点需要决定向哪一个节点发送请求：

  • 若随机选取，那么下一次不一定能够再次选取到已经有缓存的节点，再次需要访问数据库，效率低下
  • 若实现简单的哈希算法，例如将key的 ASCII 之和除以节点数的余数作为选择的节点编号。但是，当节点数量发生变化时，所有的缓存失效，引发缓存雪崩（缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。常因为缓存服务器宕机，或缓存设置了相同的过期时间引起）

2. 一致性哈希算法

2.1 基本步骤

一致性哈希算法将 key 映射到 $2^{32}$ 的空间中，将数组首位相连成环。

  1. 计算节点/机器（通常为节点名、编号、IP）的哈希值，放到环上
  2. 计算 key 的哈希值，放到环上，顺时针找到的第一个节点就是应该选取的节点/机器

一致性哈希添加节点 consistent hashing add peer

如上图所示，当新增节点peer8时，只有key27的映射会发生改变。

所以，使用一致性哈希算法，只有在新增/删除节点时，会导致一小部分数据需要重新定位，不会导致所有的缓存失效从而引起缓存雪崩。

2.2 数据倾斜

若节点过少，容易导致数据倾斜。例如上图中，节点2，4，6均分布在环的一侧，导致大量数据被分配到peer2上，导致负载不均。

通过引入虚拟节点可以解决数据倾斜问题：

  1. 计算虚拟节点哈希值，放在环上
  2. 建立虚拟节点和真实节点的映射
  3. 计算key的哈希值，顺时针寻找虚拟节点，并映射到真实节点

虚拟节点扩充了节点数量，解决了数据倾斜问题，且代价较小，只需维护虚拟/真实节点映射即可。

2.3 实现

// Hash maps bytes to uint32
type Hash func(data []byte) uint32

// Map contains all hashed keys
type Map struct {
	hash     Hash
	replicas int
	keys     []int
	hashMap  map[int]string
}

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
}

  • Map：一致性哈希算法主数据结构

    1. hash：哈希函数
    2. replicas：虚拟节点倍数
    3. keys：哈希环
    4. hashMap：虚拟/真实节点映射表，key 为虚拟节点哈希值，value 为真实节点名称

  • New：可定义节点倍数和哈希函数，默认哈希函数使用crc32.ChecksumIEEE

    // Add adds keys to the 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
		}
	}
	sort.Ints(m.keys)
}

  • Add：添加节点，可以传入多个真实节点名

  • 对于每个真实节点，创建m.replicas个虚拟节点，虚拟节点按照strconv.Itoa(i) + key 的形式编号

  • 计算虚拟节点的哈希值，并添加至虚拟/真实节点映射

  • 哈希环上的数据按照升序排序

// 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 ""
	}

	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
	})

	return m.hashMap[m.keys[idx%len(m.keys)]]
}
  1. 计算key的哈希值
  2. 顺时针寻找匹配的虚拟节点，若索引为len(keys)，则选择keys[0]，因为m.keys为环状结构所以使用模运算
  3. 通过hashMap获取真实节点

3. 测试

func TestHash(t *testing.T) {
	hash := New(3, func(data []byte) uint32 {
		i, _ := strconv.Atoi(string(data))
		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")

	tests := map[string]string{
		"2":  "2",
		"11": "2",
		"23": "4",
		"27": "2",
	}

	for k, v := range tests {
		if got := hash.Get(k); got != v {
			t.Errorf("Get(%q) = %v, want: %v", k, got, v)
		}
	}

	// 8, 18, 28
	hash.Add("8")
	tests["27"] = "8"

	for k, v := range tests {
		if got := hash.Get(k); got != v {
			t.Errorf("Get(%q) = %v, want: %v", k, got, v)
		}
	}
}

测试时使用了简单的哈希算法进行测试。

Reference

  1. https://geektutu.com/post/geecache-day4.html