【go项目-geecache】动手写分布式缓存 - day4 - 一致性哈希(hash)

收获

1. 学会了什么是一致性哈希
2. 学会如何实现一致性哈希

分布式哈希是什么？

一致性哈希（Consistent Hashing）是一种常用的哈希算法，主要用于解决分布式系统中的负载均衡问题。它的主要思想是将数据和节点映射到一个虚拟环形空间中，通过一致的哈希函数将数据均匀地分布在环上，然后根据节点在环上的位置将数据映射到相应的节点上，从而实现负载均衡。

最终达到的效果就是每个请求都会落在同一个节点上，提高了缓存效率，但是去缺点就是

分布式哈希实现

结构体实现

package consistenthash  
import (  "hash/crc32"  "sort"  "strconv"  
)  
type Hash func(data []byte) uint32  
type Map struct {  hash     Hash  replicas int  keys     []int // Sorted  hashMap  map[int]string  
}

• hash：表示哈希函数，为一个 Hash 类型的函数变量。
• replicas：表示每个键值对在哈希表中的副本数量。
• keys：表示哈希表中所有键的有序数组。
• hashMap：表示哈希表，为一个从 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  
}

这里如果hash函数为空，那么默认调用32位的CRC校验值

实现add函数

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() ： 用于向哈希表中添加一个或多个键值对。该方法接受一个或多个 string 类型的键作为参数，并将这些键映射到哈希表中的位置。

实现Get函数

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

• Get() : 传入字符串，得到哈希值字符串
• 首先判断是否存在key
• 用哈希函数计算哈希值
• 二分查找找到第一个匹配的虚拟节点的下标 idx，从 m.keys 中获取到对应的哈希值
• 通过hashmap映射得到真实节点

实现代码和测试代码

consistenthash.go

package consistenthash
import ("hash/crc32""sort""strconv")
type Hash func(data []byte) uint32
type Map struct {hash     Hashreplicas intkeys     []int // SortedhashMap  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}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)]]}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)}

test_consistenthash

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