动手写分布式缓存 - GeeCache第四天 一致性哈希(hash) | 极客兔兔

[geektutu]

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

7天用 Go语言/golang 从零实现分布式缓存 GeeCache 教程(7 days implement golang distributed cache from scratch tutorial)，动手写分布式缓存，参照 groupcache 的实现。本文介绍了一致性哈希(consistent hashing)的原理、实现以及相关测试用例，一致性哈希为什么能避免缓存雪崩，虚拟节点为什么能解决数据倾斜的问题。

[xiaoxfan]

妙啊

[FWangZil]

开始感受到基础不够扎实对我造成的伤害了

[walkmiao]

return m.hashMap[m.keys[idx%len(m.keys)]] 这个idx不是一定小于len(m.keys)吗 那么idx%len(m.keys)不就等于idx吗

[geektutu]

正文中写了，idx 可能等于 len(m.keys)，key 比 m.keys 都大的时候。

[kkBill]

@walkmiao return m.hashMap[m.keys[idx%len(m.keys)]] 这个idx不是一定小于len(m.keys)吗 那么idx%len(m.keys)不就等于idx吗

sort.Search(...)函数点进去看一下就知道了，Search returns the first true index. If there is no such index, Search returns n.

[walkmiao]

好的谢谢 lch 邮箱：372815340@qq.com 签名由 网易邮箱大师 定制 在2020年04月18日 14:08，Jinyong Mao 写道： @walkmiao return m.hashMap[m.keys[idx%len(m.keys)]] 这个idx不是一定小于len(m.keys)吗 那么idx%len(m.keys)不就等于idx吗 sort.Search(...)函数点进去看一下就知道了，Search returns the first true index. If there is no such index, Search returns n. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[ghost]

通俗易懂！hashring这里要不要考虑加上mutex ？

[zhaozong]

是否应该加上删除节点的操作，这样当节点退出的时候，可以把缓存分摊给其他节点

[ghost]

对，我也这么想。但是那样就更复杂了，估计要第八天

[man-fish]

@zhaozong 是否应该加上删除节点的操作，这样当节点退出的时候，可以把缓存分摊给其他节点

删除只需要删除掉节点对应的虚拟节点和映射关系，至于均摊给其他节点，那是删除之后自然会发生的

// Remove use to remove a key and its virtual keys on the ring and map
func (m *Map) Remove(key string) {
    for i := 0; i < m.replicas; i++ {
        hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
        idx := sort.SearchInts(m.keys, hash)
        m.keys = append(m.keys[:idx], m.keys[idx+1:]...)
        delete(m.hashmap, hash)
    }
}

[shiluoye]

我觉得hash函数的选择和哈希倾斜也会有很大的关系吧，如果hash函数选择有问题，就算增加再多的虚拟节点，节点也有可能分布在哈希环的某一小段，不知道一般业界是选择什么样的哈希函数的，有没有相关参考资料

[geektutu]

@shiluoye 一般来说，哈希函数考虑两个点：一个是碰撞率，一个是性能。比如 CRC、MD5、SHA1。

对于缓存来说，hash 之后再根据节点数量取模，因此 hash 函数的碰撞率影响并不大，而是模的大小，也就是节点的数量比较关键，这也是引入虚拟节点的原因，但是缓存对性能比较敏感。

而对于需要完整性校验的场合，碰撞率比较关键，而性能就比较次要了。一般使用 256位的 SHA1 算法，MD5 已经不再推荐了。CRC 即循环冗余校验，编码简单，性能高，但安全性就很差了。作为缓存的 hash 算法还是很合适的。

[wanboyan]

sort.Search 好像不能保证返回第一个大于hash的key值

[geektutu]

@wanboyan 举个例子？

[hzylyq]

有点看不懂了

[FinaLone]

如果在32位的系统上， uint32强转成int，运行是否会异常？ 这里强转成int是为了使用sort.Ints函数吗？

[geektutu]

@FinaLone 这里是没关系的，即使转换成负数，并不影响后面的逻辑。使用 int 的确是方便使用各种函数。包括 sort.Ints sort.Search 等。

[boyl]

这里当节点数量变化后（新增节点/删除节点），只是简单的通过回调函数去加载一次数据吗，不考虑迁移变化节点的缓存吗，是否会同时造成缓存雪崩

[wilgx0]

子曰：温故而知新

[callmePicacho]

@boyl 这里当节点数量变化后（新增节点/删除节点），只是简单的通过回调函数去加载一次数据吗，不考虑迁移变化节点的缓存吗，是否会同时造成缓存雪崩

雪崩是全部失效，用分布式一致性算法后只有部分失效

[whitebluepants]

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

对于这段代码，sort.Search是在[0,len(m.keys))的范围二分查找最小满足的索引, 也就是idx的结果要么为-1，要么为[0,len(m.keys))之间. 那后面return语句中, idx没有必要除余len(m.keys)了吧

[z-learner]

@whitebluepants

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

对于这段代码，sort.Search是在[0,len(m.keys))的范围二分查找最小满足的索引, 也就是idx的结果要么为-1，要么为[0,len(m.keys))之间. 那后面return语句中, idx没有必要除余len(m.keys)了吧

sort.Search是在[0,len(m.keys)]的范围

nums := []int{1,2,3,4,5,6}
    target := 7
    idx := sort.Search(len(nums), func(i int) bool {
        return nums[i] >= target
    })

    log.Printf("Len(nums) : %d, idx : %d\n", len(nums), idx)
    // 2021/05/25 18:45:03 Len(nums) : 6, idx : 6

[yuanyb]

改成了基于写时复制的并发读写的形式，添加了 Remove 操作（来自评论区）

type Hash func(data []byte)uint32

type Map struct {
    sync.Mutex
    // 哈希函数
    hash Hash
    // 虚拟节点倍数
    replicas int

    // 原子地存取 keys 和 hashMap
    values atomic.Value // values
}

type values struct {
    // 哈希环
    keys []int
    // 虚拟节点与真实节点的映射
    hashMap map[int]string
}

func NewMap(replicas int, hashFunc Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash: hashFunc,
    }
    m.values.Store(&values{
        hashMap: make(map[int]string),
    })
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

// 添加节点
func (m *Map) Add(keys ...string) {
    m.Lock()
    defer m.Unlock()
    newValues := m.loadValues()
    for _, key := range keys {
        // 对每个 key(节点) 创建 m.replicas 个虚拟节点
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            newValues.keys = append(newValues.keys, hash)
            newValues.hashMap[hash] = key
        }
    }
    sort.Ints(newValues.keys)
    m.values.Store(newValues)
}

func (m *Map) Get(key string) string {
    values := m.loadValues()
    if len(values.keys) == 0 {
        return ""
    }
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(values.keys), func(i int) bool {
        return values.keys[i] >= hash
    })
    // 如果 idx == len(m.keys)，说明应选择 m.keys[0]，
    // 因为 m.keys 是一个环状结构，用取余数的方式来处理这种情况
    return values.hashMap[values.keys[idx % len(values.keys)]]
}

func (m *Map) Remove(key string) {
    m.Lock()
    defer m.Unlock()
    newValues := m.loadValues()

    for i := 0; i < m.replicas; i++ {
        hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
        idx := sort.SearchInts(newValues.keys, hash)
        if newValues.keys[idx] != hash {
            return
        }
        newValues.keys = append(newValues.keys[:idx], newValues.keys[idx+1:]...)
        delete(newValues.hashMap, hash)
    }

    m.values.Store(newValues)
}

func (m *Map) loadValues() *values {
    return m.values.Load().(*values)
}

func (m *Map) copyValues() *values {
    oldValues := m.loadValues()
    newValues := &values{
        keys:    make([]int, len(oldValues.keys)),
        hashMap: make(map[int]string),
    }
    copy(newValues.keys, oldValues.keys)
    for k, v := range oldValues.hashMap {
        newValues.hashMap[k] = v
    }
    return newValues
}

[spiritbird]

开始感受到基础不够扎实对我造成的伤害了

[shuifa]

idx := sort.Search(len(m.keys), func(i int) bool {
return m.keys[i] >= （hash % m.keys[len(m.keys)-1]) // 这里要取模，否则大于虚拟节点最大值的key都会跑到索引为0的虚拟节点了
})

[lidongyooo]

@oushuifa

idx := sort.Search(len(m.keys), func(i int) bool {
return m.keys[i] >= （hash % m.keys[len(m.keys)-1]) // 这里要取模，否则大于虚拟节点最大值的key都会跑到索引为0的虚拟节点了
})

你的担忧是多余的：

• CRC32 计算 HASH 值并不依赖输入值大小，来决定返回值大小；所以我们可以将其 HASH 值视为分布均匀的
• 大于最大值时顺时针查找节点索引到 0 号节点，符合一致性哈希查找原则
• 况且你这样如果 m.keys[len(m.keys)-1] 正好是一个较小哈希值，此时索引到前半部分的几率大大增加，而后半部分几乎不会被索引到；反而破坏了原本的均衡性。

想解决均衡性问题，正确的姿势就是加大虚拟节点数值

[lihangfu]

节点的hash值会不会出现碰撞啊

[demoManito]

@boyl 这里当节点数量变化后（新增节点/删除节点），只是简单的通过回调函数去加载一次数据吗，不考虑迁移变化节点的缓存吗，是否会同时造成缓存雪崩

这就是demo，要考虑的太多了，岂是这几十来行能写完的？

[driftingboy]

@yuanyb

add 和 remove 是不是都应该改成copyvules

[voidspiral]

@demoManito

@boyl 这里当节点数量变化后（新增节点/删除节点），只是简单的通过回调函数去加载一次数据吗，不考虑迁移变化节点的缓存吗，是否会同时造成缓存雪崩

这就是demo，要考虑的太多了，岂是这几十来行能写完的？

毕竟是copy的groupcache的实现，这个作者已经较好的讲解了基本的功能了。这种细节就靠自己去看其他人的一致性哈希实现了

[018429]

源码的测试文件的TestConsistency函数

func TestConsistency(t *testing.T) {
    hash1 := New(1, nil)
    hash2 := New(1, nil)

    hash1.Add("Bill", "Bob", "Bonny")
    hash2.Add("Bob", "Bonny", "Bill")

    if hash1.Get("Ben") != hash2.Get("Ben") {
        t.Errorf("Fetching 'Ben' from both hashes should be the same")
    }

    hash2.Add("Becky", "Ben", "Bobby")

    if hash1.Get("Ben") != hash2.Get("Ben") ||
        hash1.Get("Bob") != hash2.Get("Bob") ||
        hash1.Get("Bonny") != hash2.Get("Bonny") {
        t.Errorf("Direct matches should always return the same entry")
    }

}

我不理解为什么这里的哈希值相等，hash2的环相比hash1的环多了三个节点，而源码里面的Add函数没有把字符串自身的哈希值加入环上，所以不存在直接匹配这回事，查找Ben和查找任意一个字符串"anystring"是同样的效果，所以在两个不一样的列表查找任意的整数，对应的虚拟节点绝对存在不相等的情况，所以这句英文Direct matches should always return the same entry表达的含义我以为作者是下意识的以为环上存在字符串本事的哈希映射？

[taka250]

@whitebluepants

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

对于这段代码，sort.Search是在[0,len(m.keys))的范围二分查找最小满足的索引, 也就是idx的结果要么为-1，要么为[0,len(m.keys))之间. 那后面return语句中, idx没有必要除余len(m.keys)了吧

返回值没有-1

[taka250]

@018429 源码的测试文件的TestConsistency函数

func TestConsistency(t *testing.T) {
  hash1 := New(1, nil)
  hash2 := New(1, nil)

  hash1.Add("Bill", "Bob", "Bonny")
  hash2.Add("Bob", "Bonny", "Bill")

  if hash1.Get("Ben") != hash2.Get("Ben") {
      t.Errorf("Fetching 'Ben' from both hashes should be the same")
  }

  hash2.Add("Becky", "Ben", "Bobby")

  if hash1.Get("Ben") != hash2.Get("Ben") ||
      hash1.Get("Bob") != hash2.Get("Bob") ||
      hash1.Get("Bonny") != hash2.Get("Bonny") {
      t.Errorf("Direct matches should always return the same entry")
  }

}

我不理解为什么这里的哈希值相等，hash2的环相比hash1的环多了三个节点，而源码里面的Add函数没有把字符串自身的哈希值加入环上，所以不存在直接匹配这回事，查找Ben和查找任意一个字符串"anystring"是同样的效果，所以在两个不一样的列表查找任意的整数，对应的虚拟节点绝对存在不相等的情况，所以这句英文Direct matches should always return the same entry表达的含义我以为作者是下意识的以为环上存在字符串本事的哈希映射？

因为get中对参数的加密算法是相同的，对传入的参数进行计算后去hashmap表找对应的节点，返回的节点也应该是相同的。（节点和他的虚拟节点的哈希值在所有的环中都是相同的，因为算法相同）

[Dong-Guan-Saohuang-Dadui]

@z-learner

@whitebluepants

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

对于这段代码，sort.Search是在[0,len(m.keys))的范围二分查找最小满足的索引, 也就是idx的结果要么为-1，要么为[0,len(m.keys))之间. 那后面return语句中, idx没有必要除余len(m.keys)了吧

sort.Search是在[0,len(m.keys)]的范围

nums := []int{1,2,3,4,5,6}
  target := 7
  idx := sort.Search(len(nums), func(i int) bool {
      return nums[i] >= target
  })

  log.Printf("Len(nums) : %d, idx : %d\n", len(nums), idx)
  // 2021/05/25 18:45:03 Len(nums) : 6, idx : 6

Search函数采用二分法搜索找到[0, n)区间内最小的满足f(i)==true的值i。也就是说，Search函数希望f在输入位于区间[0, n)的前面某部分（可以为空）时返回假，而在输入位于剩余至结尾的部分（可以为空）时返回真；Search函数会返回满足f(i)==true的最小值i。如果没有该值，函数会返回n 所以如果没有一个节点的hash大于key hash时就会返回n，idx返回0

[linyerun]

如果一致性哈希算法算出来的Hash值一样怎么办，这样HashMap之前的值因为这个会被覆盖掉了

[jiengup]

@linyerun 如果一致性哈希算法算出来的Hash值一样怎么办，这样HashMap之前的值因为这个会被覆盖掉了

你说的这个叫做哈希冲突，hash算法是这样的，一般我们认为只要哈希空间很大，例如项目中的哈希空间差不多是2^32这么大，而key的数量级与之有差距的话，是比较难发生冲突的。而如果不是这样，就要考虑哈希冲突的问题，经典的解决办法一般有两个：

• 如果算出来的哈希值已经有对应的key了，那么我们可以将原来的key进行一些变化重新做一次哈希，或者是做原来的key的哈希的哈希，从而调整原来key的位置，然后将新key放到冲突哈希值的位置。
• 采用bucket的方式，将所有的哈希值对应一个bucket，将每个算出来相同哈希值的key都放入桶中，这种bucket的实现方式可以是将桶里的所有key值用一个链表组织起来，查找的时候顺着链表找就好了 以上的两种解决哈希冲突的方式可能会在插入和查找的时候造成一定的性能损失，学术界目前也有很多针对哈希冲突的研究，特别是近几年比较火的learned hash，如果你感兴趣可以了解

[GuiQuQu]

关于节点的增加和删除，在节点增加的场景下，因为原来的内容还保存在其他节点中，因此可以直接向哈希环上添加虚拟节点。当节点减少时，进行删除操作，把这个节点对应的虚拟节点哈希值删除掉，在重新排序，如果有原本保存在这个内容访问缓存，根据一致性哈希算法，会自动找到第一个哈希值大于key的哈希值的虚拟节点，然后会发现内容不存在，从数据源获取之后在返回。

[blight19]

@jiengup

@linyerun 如果一致性哈希算法算出来的Hash值一样怎么办，这样HashMap之前的值因为这个会被覆盖掉了

你说的这个叫做哈希冲突，hash算法是这样的，一般我们认为只要哈希空间很大，例如项目中的哈希空间差不多是2^32这么大，而key的数量级与之有差距的话，是比较难发生冲突的。而如果不是这样，就要考虑哈希冲突的问题，经典的解决办法一般有两个：

• 如果算出来的哈希值已经有对应的key了，那么我们可以将原来的key进行一些变化重新做一次哈希，或者是做原来的key的哈希的哈希，从而调整原来key的位置，然后将新key放到冲突哈希值的位置。
• 采用bucket的方式，将所有的哈希值对应一个bucket，将每个算出来相同哈希值的key都放入桶中，这种bucket的实现方式可以是将桶里的所有key值用一个链表组织起来，查找的时候顺着链表找就好了 以上的两种解决哈希冲突的方式可能会在插入和查找的时候造成一定的性能损失，学术界目前也有很多针对哈希冲突的研究，特别是近几年比较火的learned hash，如果你感兴趣可以了解

不是，你理解错了。他应该想问的是在计算虚拟节点哈希值时候产生这个问题，这里我觉得确实是个bug，虽然概率比较小，但是这个可能存在。这里使用哈希值然后做排序是一个比较简单的方法。这里可以将一个比较大范围的数字，比如0-16384平均分给每个虚拟节点。这样也有助于请求的均衡。

[ForeverCzz]

uint32转int不会出锅吗, 比较大的值会不会全塞到第一个节点

[zzzzzzyang]

你给出的代码很全面，但是我不明白你这里为什么同时使用了原子操作和锁，是否只需要其中一个即可？ 时间有点久远了，不知道你还不会不会回复:)

@yuanyb 改成了基于写时复制的并发读写的形式，添加了 Remove 操作（来自评论区）

type Hash func(data []byte)uint32

type Map struct {
  sync.Mutex
  // 哈希函数
  hash Hash
  // 虚拟节点倍数
  replicas int

  // 原子地存取 keys 和 hashMap
  values atomic.Value // values
}

type values struct {
  // 哈希环
  keys []int
  // 虚拟节点与真实节点的映射
  hashMap map[int]string
}

func NewMap(replicas int, hashFunc Hash) *Map {
  m := &Map{
      replicas: replicas,
      hash: hashFunc,
  }
  m.values.Store(&values{
      hashMap: make(map[int]string),
  })
  if m.hash == nil {
      m.hash = crc32.ChecksumIEEE
  }
  return m
}

// 添加节点
func (m *Map) Add(keys ...string) {
  m.Lock()
  defer m.Unlock()
  newValues := m.loadValues()
  for _, key := range keys {
      // 对每个 key(节点) 创建 m.replicas 个虚拟节点
      for i := 0; i < m.replicas; i++ {
          hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
          newValues.keys = append(newValues.keys, hash)
          newValues.hashMap[hash] = key
      }
  }
  sort.Ints(newValues.keys)
  m.values.Store(newValues)
}

func (m *Map) Get(key string) string {
    values := m.loadValues()
  if len(values.keys) == 0 {
      return ""
  }
  hash := int(m.hash([]byte(key)))
  idx := sort.Search(len(values.keys), func(i int) bool {
      return values.keys[i] >= hash
  })
  // 如果 idx == len(m.keys)，说明应选择 m.keys[0]，
  // 因为 m.keys 是一个环状结构，用取余数的方式来处理这种情况
  return values.hashMap[values.keys[idx % len(values.keys)]]
}

func (m *Map) Remove(key string) {
  m.Lock()
  defer m.Unlock()
  newValues := m.loadValues()

  for i := 0; i < m.replicas; i++ {
      hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
      idx := sort.SearchInts(newValues.keys, hash)
      if newValues.keys[idx] != hash {
          return
      }
      newValues.keys = append(newValues.keys[:idx], newValues.keys[idx+1:]...)
      delete(newValues.hashMap, hash)
  }

  m.values.Store(newValues)
}

func (m *Map) loadValues() *values {
    return m.values.Load().(*values)
}

func (m *Map) copyValues() *values {
  oldValues := m.loadValues()
  newValues := &values{
      keys:    make([]int, len(oldValues.keys)),
      hashMap: make(map[int]string),
  }
  copy(newValues.keys, oldValues.keys)
  for k, v := range oldValues.hashMap {
      newValues.hashMap[k] = v
  }
  return newValues
}

[pdxrlj]

大佬这个Add的时候hash不是加i了吗 hash := int(m.hash([]byte(strconv.Itoa(i) + key))) m.keys = append(m.keys, hash) 然后在Get的时候这个key不需要加i能找到吗 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 })

[ReReniao]

@pdxrlj 大佬这个Add的时候hash不是加i了吗 hash := int(m.hash([]byte(strconv.Itoa(i) + key))) m.keys = append(m.keys, hash) 然后在Get的时候这个key不需要加i能找到吗 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 })

找的是环上第一个大于等于hash值的结点，找不到则返回切片长度，例如11，会找到12,12是一个虚拟结点，对应的真实结点是2（通过m.hashMap确定映射关系），再从真实结点得到缓存值