一致性Hash 算法

1，介绍一致性hash算法（Consistent Hashing）及其在分布式缓存中的利用，以及对一致性hash算法原理的介绍。
2，简略的代码实现
3，发现有什么问题不便请指出下。。谢谢。。

一，背景

咱们通过一个问题思考引入。。

假如咱们有个网站，随着用户量的一直增长，日活量的一直晋升，导致 mysql 的数据读写压力飞速增长，对咱们的服务造成极大的压力。。

为了解决下面的窘境咱们引入了 redis 作为缓存机制，然而你会发现其实随着业务扩张，单台 redis 很快就无奈撑持起你零碎服务，那么为了解决这个问题，咱们会开始引入多台 redis 形成服务集群为网站提供缓存服务；

因为咱们不可能所有的 redis 服务都缓存所有数据，因为这样意义不大，咱们现实的是 每个 redis 服务提供一部分用户的缓存数据，而后依据不同的客户的申请读取不同 redis 的缓存数据；

在这个时候：很多人会想起 hash取模 法；

如上图：依据 Customer_id 取模失去值，依据值流入指定的redis服务中。如果 customer_id 是自增的，咱们每个 redis 服务外面的值的数量都是相对均匀的；

然而短期问题是解决了。。然而你有没有想过，当3个redis 服务无奈失常撑持，须要退出 第 4 个 redis 服务 或者资源过剩了，你心愿回收一个 redis 应用两个 redis 撑持服务了。。然而这个时候你会发现。。 取模的值一旦扭转。。之前缓存的数据就会产生错乱。。这样会有大量的申请穿过你的 redis 缓存服务，间接达到你的 mysql。。而且 redis 缓存服务也缓存着大量无用数据，结果有点可怕。。

为了解决上述问题。。。咱们引入 一致性Hash算法

二，算法简述

简略来说咱们把所有数据做一致性hash计算后的所有后果看作一个 hash 闭环，而闭环的大小为0~2^32，也就说所有的数据都会坐落在这个 hash 闭环；如下图：

0 和 2^32 在 hash 闭环中重合，这里为什么要这样做 大家能够思考下。。

下一步咱们把 redis 服务 的IP 也应用 雷同的 hash("redis服务IP") 办法进行求出 hash 值，这样咱们 redis服务 也会坐落在咱们的 hash闭环 中，他的作用 能够看做个桶，承接顺指针流入的数据；如下图：

接下来咱们把所有的数据key （即:Customer_id）应用雷同的 hash("key") 函数计算出对应的 hash 值；那么咱们的数据也会坐落于咱们 hash闭环 中，从此地位开始沿着 hash闭环 顺时针行走，遇到第一个 Redis服务 就是其定位所在的缓存服务器。。如下图：

比方：咱们有 A,B,C,D 4个数据，通过 hash() 函数计算后，坐落在 hash闭环上，顺时针运行后，A 数据会流入 Redis服务1中，B 和 C 数据会流入Redis服务2中，D数据则会流入 Redis服务3中；

兴许你会好奇，hash 取模 不也能够实现上述的吗？而且还能保证数据的相对平均。。

OK！那么我看他特有的劣势：

当咱们须要把 Redis服务3 从集群中剥离进去会产生怎么的状况，如下图：

咱们看出，当 Redis服务3 从集群中剥离进去后，原来要流入服务器 Redis服务3 的数据 D ，只能流入 Redis服务1 中，而 Redis服务2的数据将没有任何影响，也就是环境话说 当缓存服务器从集群中剥离进去或者增加缓存服务器到集群中都只会影响到顺流而下的下一个缓存服务器；

换句话说：一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具备较好的容错性和可扩展性。

三，虚构节点

如果你仔细浏览，你会发现如果依照下面的计划施行，咱们没有方法保障缓存数据可能均匀分布到每一个缓存服务器中。既然问题发现了，就必然会存在解决的计划。。

无妨咱们做一个大胆的假如，如果咱们 redis服务 十分多，数量极大，有限趋向于 2^32，那么咱们数据流入服务器的数量是不是就肯定会趋向于平均呢？（这里咱们不思考hash碰撞的问题哟）

答案是必定的，当然咱们缓存服务器的数量也不可能有这么多，这个阐明只是为了阐明当 缓存节点坐落在 hash闭环 上的数量越多，那么咱们数据分布就会趋向于平均。。然而咱们又没方法用于这么多实在的缓存服务节点，所以咱们引入了一个 虚构节点 的概念。。如下图：

咱们把 实在的Redis服务1节点 转换成2个虚构节点 散布在环上，当数据流入虚构节点时实际上也是流入Redis服务1。

其实 虚构节点 除了保障散布的平均，还有一个突出的作用：每一台缓存服务的性能不同 会导致提供服务的能力不同。通过虚构节点 咱们能够无效控制数据缓存的量。（nginx的一致性hash算法负载平衡就是这样实现的。。有趣味能够理解下）

四，代码实现

上面我提供下我实现的 一个简略的 一致性hash实现

package mainimport (    "errors"    "hash/crc32"    "sort"    "strconv"    "sync")type Hash func(data []byte) uint32type UInt32Slice []uint32func (s UInt32Slice) Len() int {    return len(s)}func (s UInt32Slice) Less(i, j int) bool {    return s[i] < s[j]}func (s UInt32Slice) Swap(i, j int)  {    s[i], s[j] = s[j], s[i]}type ConsistentHashBanlance struct {    mux sync.RWMutex    hash Hash    replicas int // 虚构节点数量，虚构节点越多 节点散布更趋势平均    keys UInt32Slice // 节点排序    hashMap map[uint32]string //节点哈希和Key的map,键是hash值，值是节点key}func NewConsistentHashBanlance(replicas int, fn Hash) *ConsistentHashBanlance {    m := &ConsistentHashBanlance{        replicas: replicas,        hash:     fn,        hashMap:  make(map[uint32]string),    }    if m.hash == nil {        //最多32位,保障是一个2^32-1环        m.hash = crc32.ChecksumIEEE    }    return m}// 验证是否为空func (c *ConsistentHashBanlance) IsEmpty() bool {    return len(c.keys) == 0}// Add 办法用来增加缓存节点，参数为节点key，比方应用IPfunc (c *ConsistentHashBanlance) Add(params ...string) error {    if len(params) == 0 {        return errors.New("param len 1 at least")    }    addr := params[0]    c.mux.Lock()    defer c.mux.Unlock()    // 联合 虚构节点数量 计算所有虚构节点的hash值，并存入m.keys中，同时在m.hashMap中保留哈希值和key的映射    for i := 0; i < c.replicas; i++ {        hash := c.hash([]byte(strconv.Itoa(i) + addr))        c.keys = append(c.keys, hash)        c.hashMap[hash] = addr    }    // 对所有虚构节点的哈希值进行排序，不便之后进行二分查找    sort.Sort(c.keys)    return nil}// Get 办法依据给定的对象获取最靠近它的那个节点func (c *ConsistentHashBanlance) Get(key string) (string, error) {    if c.IsEmpty() {        return "", errors.New("node is empty")    }    hash := c.hash([]byte(key))    // 通过二分查找获取最优节点，第一个"服务器hash"值大于"数据hash"值的就是最优"服务器节点"    idx := sort.Search(len(c.keys), func(i int) bool { return c.keys[i] >= hash })    // 如果查找后果 大于 服务器节点哈希数组的最大索引，示意此时该对象哈希值位于最初一个节点之后，那么放入第一个节点中    if idx == len(c.keys) {        idx = 0    }    c.mux.RLock()    defer c.mux.RUnlock()    return c.hashMap[c.keys[idx]], nil}

能够参考下。

参考链接：

  • 《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》: https://www.akamai.com/us/en/...
  • nginx一致性hash模块: http://tengine.taobao.org/doc...
  • 一致性HASH技术的窘境: https://www.pianshen.com/arti...