一致性 Hash 原理及 GroupCache 源码分析 | 编程沉思录

chenyahui commented 3 years ago

https://www.cyhone.com/articles/consistent-hash-of-groupcache/

一致性 Hash 常用于缓解分布式缓存系统扩缩容节点时造成的缓存大量失效的问题。一致性 Hash 与其说是一种 Hash 算法，其实更像是一种负载均衡策略。 GroupCache 是 golang 官方提供的一个分布式缓存库，其中包含了一个简单的一致性 Hash 的实现。其代码在 github.com/golang/groupcache/consistenthash。本文将会基于 GroupCac

rtrdust commented 2 years ago

有点疑惑，使用二分侦测能找到第一个大于等于这个hash值的项吗？比如hashList里有5 6 7 8 9，这时来了个请求，请求的hash值是1，这时使用二分，找到的应该是7，就会返回结果，实际应该选5吧

chenyahui commented 2 years ago

@rtrdust 有点疑惑，使用二分侦测能找到第一个大于等于这个hash值的项吗？比如hashList里有5 6 7 8 9，这时来了个请求，请求的hash值是1，这时使用二分，找到的应该是7，就会返回结果，实际应该选5吧

sort.Search并非是"找到第一个大于等于这个hash值的项"，而是找到满足条件的最小值。文章里面的意思是，可以通过sort.Search 找到环中第一个大于该hash值的元素。不过这个描述确实容易引起误解，我修改下~

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true,

具体见文档：https://pkg.go.dev/sort#Search

chenyahui / chenyahui.github.io

一致性 Hash 原理及 GroupCache 源码分析 | 编程沉思录 #58