大家好，我是浩然，网名“磊磊落落”。专注Golang、算法、DevOps、PostgreSQL及云原生，想学新技术，关注我就对了！
假定 N 为后台服务节点数，当前台携带关键字 key 发起请求时，我们通常将 key 进行 hash 后采用模运算（hash(key)%N）来将请求分发到不同的节点上。
对前台请求于后台无状态服务节点不敏感的场景而言，只要请求 key 具有一定的随机性，哪怕节点动态增删，该算法于后台而言已可以达到很好的负载均衡效果。
但对于分布式缓存，或者分布式数据库等场景而言，上述方式就不合适了。因后台节点的增删会引起几乎所有 key 的重新映射。这样，于分布式缓存而言，均发生 cache miss；于分布式数据库而言发生数据错乱，其影响是灾难性的。
而一致性哈希算法的目标是，当 K 个请求 key 发起请求时。后台增减节点，只会引起 K/N 的 key 发生重新映射。即一致性哈希算法，在后台节点稳定时，同一 key 的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将 K 个 key 映射到与之前相同的节点上。
1 一致性哈希算法原理
一致性哈希算法是将每个 Node 节点映射到同一个圆上。将各 Node 的 key 采用 hash 计算，可得到一个整数数组。将该数组排序后，首尾相连即是一个圆。如下图所示，Node 的 key 分布在圆的不同弧段上。同理，若有一请求 key，hash 后落入该圆的某一弧段（下图三角点所示），顺时针方向寻得离其最近的节点即为其服务节点（下图 Node2）。这样每个节点覆盖了圆上从上一节点到其本身的一段弧段区间。如某一节点失效，之前落入其弧段区间的请求即会顺时针移到与其相邻的节点（下图如 Node2 失效，之前落入 Node3 至 Node2 弧段的请求会落入 Node1）。而未落入失效弧段区间的节点则不受影响（之前落入 Node2 至 Node3 弧段的请求，当 Node2 失效后不受影响）。增加节点的场景与此类似，新的节点承载一段新区间，这样，落入失效节点至新节点弧段的请求会被新节点所承载。
在节点固定的情况下，为了增加节点在圆上分布的均匀性与分散性，可以设置节点的 replicas（副本数）。下图将 replicas 设置为 2，各节点承载的弧段范围已更加精细且于整体而言分布更加分散。所以适当调节 replicas 参数可以提高算法的均衡性。2 Golang 一致性哈希算法实现
本文的 hash 函数，是对 key 先做一次 md5Sum，然后采用 crc32 做 checkSum 得到一个正数。
package consistent_hashingimport ( "crypto/md5" "hash/crc32" "sort" "strconv" "sync")type Node struct { Id string Address string}type ConsistentHashing struct { mutex sync.RWMutex nodes map[int]Node replicas int}func NewConsistentHashing(nodes []Node, replicas int) *ConsistentHashing { ch := &ConsistentHashing{nodes: make(map[int]Node), replicas: replicas} for _, node := range nodes { ch.AddNode(node) } return ch}func (ch *ConsistentHashing) AddNode(node Node) { ch.mutex.Lock() defer ch.mutex.Unlock() for i := 0; i < ch.replicas; i++ { k := hash(node.Id + "_" + strconv.Itoa(i)) ch.nodes[k] = node }}func (ch *ConsistentHashing) RemoveNode(node Node) { ch.mutex.Lock() defer ch.mutex.Unlock() for i := 0; i < ch.replicas; i++ { k := hash(node.Id + "_" + strconv.Itoa(i)) delete(ch.nodes, k) }}func (ch *ConsistentHashing) GetNode(outerKey string) Node { key := hash(outerKey) nodeKey := ch.findNearestNodeKeyClockwise(key) return ch.nodes[nodeKey]}func (ch *ConsistentHashing) findNearestNodeKeyClockwise(key int) int { ch.mutex.RLock() sortKeys := sortKeys(ch.nodes) ch.mutex.RUnlock() for _, k := range sortKeys { if key <= k { return k } } return sortKeys[0]}func sortKeys(m map[int]Node) []int { var sortedKeys []int for k := range m { sortedKeys = append(sortedKeys, k) } sort.Ints(sortedKeys) return sortedKeys}func hash(key string) int { md5Chan := make(chan []byte, 1) md5Sum := md5.Sum([]byte(key)) md5Chan <- md5Sum[:] return int(crc32.ChecksumIEEE(<-md5Chan))}目录
3 均匀性分析
构建服务节点时，为模拟节点 key 在圆上的分布，简单采用 id（0，1，2）做初始 key，replicas 为 100。根据点间距等比例划分圆后得到其位置，彩色小圆点为其对应的节点（红绿蓝对应 0，1，2）；
三角点代表外部请求的三个字符串（10.10.10.10，10.10.20.11，10.10.30.12）hash 后按算法取到的服务节点；
使用 Python matplotlib 工具描点绘图如下。
从图可知，节点虽少（3 个），但扩大副本量后，key 的分布已具有一定的均匀性与分散性，外部 key 请求的最终落地节点于整体服务节点而言也是比较均匀的。
4 Golang 高可用集群代理代码
一致性哈希算法具有很广泛的使用场景。如做请求分流与负载均衡，分布式缓存，分布式存储等。如下代码调用 Golang 反向代理类库，结合上述一致性哈希算法，根据请求头标记做分发，数行代码，即可构建一个小巧高可用的代理服务器。
package mainimport ( "consistent_hashing" "net/http" "net/http/httputil" "net/url")func main() { nodes := []consistent_hashing.Node{ {"0", ""}, {"1", ""}, {"2", ""}, } ch := consistent_hashing.NewConsistentHashing(nodes, 100) http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) { sign := r.Header.Get("sign") node := ch.GetNode(sign) uri, _ := url.Parse(node.Address) httputil.NewSingleHostReverseProxy(uri) }) http.ListenAndServe(":8080", nil)}点击阅读原文，欢迎来我的博客获取更多有价值的文章！