关于一致性哈希算法:一致性Hash算法golang简单实现

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 main

import (
    "errors"
    "hash/crc32"
    "sort"
    "strconv"
    "sync"
)

type Hash func(data []byte) uint32

type UInt32Slice []uint32

func (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，比方应用 IP
func (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…

关于一致性哈希算法:一致性Hash算法golang简单实现

一致性 Hash 算法

一，背景

二，算法简述

三，虚构节点

四，代码实现

参考链接：