一致性 Hash 算法详述
区块链哈希算法竞猜游戏开发 V 对接 hkkf5566，娱乐平台定制，游戏俱乐部零碎开发
算法原理
一致性哈希算法在 1997 年由麻省理工学院提出，是一种非凡的哈希算法，在移除或者增加一个服务器时，可能尽可能小地扭转已存在的服务申请与解决申请服务器之间的映射关系；
一致性哈希解决了简略哈希算法在分布式哈希表（Distributed Hash Table，DHT）中存在的动静伸缩等问题；
一致性 hash 算法实质上也是一种取模算法；
哈希是一种通过对数据进行压缩, 从而提高效率的一种解决办法，但因为哈希函数无限，数据增大等缘故，哈希抵触成为数据无效压缩的一个难题。
不过，不同于上边按服务器数量取模，一致性 hash 是对固定值 2^32 取模；
IPv4 的地址是 4 组 8 位 2 进制数组成，所以用 2^32 能够保障每个 IP 地址会有惟一的映射；
① hash 环
咱们能够将这 2^32 个值形象成一个圆环 ⭕️，圆环的正上方的点代表 0，顺时针排列，以此类推：1、2、3…直到 2^32-1，而这个由 2 的 32 次方个点组成的圆环统称为 hash 环；
② 服务器映射到 hash 环
在对服务器进行映射时，应用 hash（服务器 ip）% 2^32，即：
应用服务器 IP 地址进行 hash 计算，用哈希后的后果对 2^32 取模，后果肯定是一个 0 到 2^32- 1 之间的整数；
而这个整数映射在 hash 环上的地位代表了一个服务器，顺次将 node0、node1、node2 三个缓存服务器映射到 hash 环上；
③ 对象 key 映射到服务器
在对对应的 Key 映射到具体的服务器时，须要首先计算 Key 的 Hash 值：hash（key）% 2^32；
注：此处的 Hash 函数能够和之前计算服务器映射至 Hash 环的函数不同，只有保障取值范畴和 Hash 环的范畴雷同即可（即：2^32）；
将 Key 映射至服务器遵循上面的逻辑：
从缓存对象 key 的地位开始，沿顺时针方向遇到的第一个服务器，便是以后对象将要缓存到的服务器；
假如咱们有 “semlinker”、”kakuqo”、”lolo”、”fer” 四个对象，别离简写为 o1、o2、o3 和 o4；
首先，应用哈希函数计算这个对象的 hash 值，值的范畴是 [0, 2^32-1]：
图中对象的映射关系如下：
hash(o1) = k1; hash(o2) = k2;
hash(o3) = k3; hash(o4) = k4;
同时 3 台缓存服务器，别离为 CS1、CS2 和 CS3：
则可知，各对象和服务器的映射关系如下：
K1 => CS1
K4 => CS3
K2 => CS2
K3 => CS1
即：
以上便是一致性 Hash 的工作原理；
能够看到，一致性 Hash 就是：将本来单个点的 Hash 映射，转变为了在一个环上的某个片段上的映射！
上面咱们来看几种服务器扩缩容的场景；
服务器扩缩容场景
① 服务器缩小
假如 CS3 服务器呈现故障导致服务下线，这时本来存储于 CS3 服务器的对象 o4，须要被重新分配至 CS2 服务器，其它对象仍存储在原有的机器上：
此时受影响的数据只有 CS2 和 CS3 服务器之间的局部数据！
② 服务器减少
如果业务量激增，咱们须要减少一台服务器 CS4，通过同样的 hash 运算，该服务器最终落于 t1 和 t2 服务器之间，具体如下图所示：
此时，只有 t1 和 t2 服务器之间的局部对象须要重新分配；
在以上示例中只有 o3 对象须要重新分配，即它被从新到 CS4 服务器；
在后面咱们曾经说过：如果应用简略的取模办法，当新增加服务器时可能会导致大部分缓存生效，而应用一致性哈希算法后，这种状况失去了较大的改善，因为只有少部分对象须要重新分配！
数据偏斜 & 服务器性能均衡问题
引出问题
在下面给出的例子中，各个服务器简直是均匀被均摊到 Hash 环上；
然而在理论场景中很难选取到一个 Hash 函数这么完满的将各个服务器散列到 Hash 环上；
此时，在服务器节点数量太少的状况下，很容易因为节点散布不平均而造成数据歪斜问题；
如下图被缓存的对象大部分缓存在 node- 4 服务器上，导致其余节点资源节约，零碎压力大部分集中在 node- 4 节点上，这样的集群是十分不衰弱的：
同时，还有另一个问题：
在下面新增服务器 CS4 时，CS4 只分担了 CS1 服务器的负载，服务器 CS2 和 CS3 并没有因为 CS4 服务器的退出而缩小负载压力；如果 CS4 服务器的性能与原有服务器的性能统一甚至可能更高，那么这种后果并不是咱们所冀望的；
虚构节点
针对下面的问题，咱们能够通过：引入虚构节点来解决负载不平衡的问题：
行将每台物理服务器虚构为一组虚构服务器，将虚构服务器搁置到哈希环上，如果要确定对象的服务器，需先确定对象的虚构服务器，再由虚构服务器确定物理服务器；
如下图所示：
在图中：o1 和 o2 示意对象，v1 ~ v6 示意虚构服务器，s1 ~ s3 示意理论的物理服务器；
虚构节点的计算
虚构节点的 hash 计算通常能够采纳：对应节点的 IP 地址加数字编号后缀 hash（10.24.23.227#1) 的形式；
举个例子，node-1 节点 IP 为 10.24.23.227，失常计算 node- 1 的 hash 值：
hash（10.24.23.227#1）% 2^32
假如咱们给 node-1 设置三个虚构节点，node-1#1、node-1#2、node-1#3，对它们进行 hash 后取模：
hash（10.24.23.227#1）% 2^32
hash（10.24.23.227#2）% 2^32
hash（10.24.23.227#3）% 2^32
留神：
调配的虚构节点个数越多，映射在 hash 环上才会越趋于平均，节点太少的话很难看出成果；
引入虚构节点的同时也减少了新的问题，要做虚构节点和实在节点间的映射，对象 key-> 虚构节点 -> 理论节点之间的转换；
应用场景
一致性 hash 在分布式系统中应该是实现负载平衡的首选算法，它的实现比拟灵便，既能够在客户端实现，也能够在中间件上实现，比方日常应用较多的缓存中间件 memcached 和 redis 集群都有用到它；
memcached 的集群比拟非凡，严格来说它只能算是伪集群，因为它的服务器之间不能通信，申请的散发路由齐全靠客户端来的计算出缓存对象应该落在哪个服务器上，而它的路由算法用的就是一致性 hash；
还有 redis 集群中 hash 槽的概念，尽管实现不尽相同，但思维万变不离其宗，看完本篇的一致性 hash，你再去了解 redis 槽位就轻松多了；
其它的利用场景还有很多：
RPC 框架 Dubbo 用来抉择服务提供者
分布式关系数据库分库分表：数据与节点的映射关系
LVS 负载平衡调度器
……
一致性 Hash 算法实现
上面咱们依据下面的讲述，应用 Golang 实现一个一致性 Hash 算法，这个算法具备一些上面的性能个性：
一致性 Hash 外围算法；
反对自定义 Hash 算法；
反对自定义虚构节点个数；
具体源代码见：
https://github.com/JasonkayZK…
上面开始实现吧！
构造体、谬误以及常量定义
① 构造体定义
首先定义每一台缓存服务器的数据结构：
core/host.go
type Host struct {
// the host id: ip:port
Name string
// the load bound of the host
LoadBound int64
}
其中：
Name：缓存服务器的 Ip 地址 + 端口，如：127.0.0.1:8000
LoadBound：缓存服务器以后解决的“申请”缓存数，这个字段在后文含有负载边界值的一致性 Hash 中会用到；
其次，定义一致性 Hash 的构造：
core/algorithm.go
// Consistent is an implementation of consistent-hashing-algorithm
type Consistent struct {
// the number of replicas
replicaNum int
// the total loads of all replicas
totalLoad int64
// the hash function for keys
hashFunc func(key string) uint64
// the map of virtual nodes to hosts
hostMap map[string]*Host
// the map of hashed virtual nodes to host name
replicaHostMap map[uint64]string
// the hash ring
sortedHostsHashSet []uint64
// the hash ring lock
sync.RWMutex
}
其中：
replicaNum：示意每个实在的缓存服务器在 Hash 环中存在的虚构节点数；
totalLoad：所有物理服务器对应的总缓存“申请”数（这个字段在后文含有负载边界值的一致性 Hash 中会用到）；
hashFunc：计算 Hash 环映射以及 Key 映射的散列函数；
hostMap：物理服务器名称对应的 Host 构造体映射；
replicaHostMap：Hash 环中虚构节点对应实在缓存服务器名称的映射；
sortedHostsHashSet：Hash 环；
sync.RWMutex：操作 Hash 环时用到的读写锁；
大略的构造如上所示，上面咱们来看一些常量和谬误的定义；
② 常量和谬误定义
常量的定义如下：
core/algorithm.go
const (
// The format of the host replica name
hostReplicaFormat = %s%d
)
var (
// the default number of replicas
defaultReplicaNum = 10
// the load bound factor
// ref: https://research.googleblog.c…
loadBoundFactor = 0.25
// the default Hash function for keys
defaultHashFunc = func(key string) uint64 {
out := sha512.Sum512([]byte(key))
return binary.LittleEndian.Uint64(out[:])
}
)
别离示意：
defaultReplicaNum：默认状况下，每个实在的物理服务器在 Hash 环中虚构节点的个数；
loadBoundFactor：负载边界因数（这个字段在后文含有负载边界值的一致性 Hash 中会用到）；
defaultHashFunc：默认的散列函数，这里用到的是 SHA512 算法，并取的是 unsigned int64，这一点和下面介绍的 0~2^32- 1 有所区别！
hostReplicaFormat：虚构节点名称格局，这里的虚构节点的格局为：%s%d，和上文提到的 10.24.23.227#1 的格局有所区别，然而情理是一样的！
还有一些谬误的定义：
core/error.go
var (
ErrHostAlreadyExists = errors.New(“host already exists”)
ErrHostNotFound = errors.New(“host not found”)
)
别离示意服务器曾经注册，以及缓存服务器未找到；
上面来看具体的办法实现！
注册 / 登记缓存服务器
① 注册缓存服务器
注册缓存服务器的代码如下：
core/algorithm.go
func (c *Consistent) RegisterHost(hostName string) error {
c.Lock()
defer c.Unlock()
if _, ok := c.hostMap[hostName]; ok {
return ErrHostAlreadyExists
}
c.hostMap[hostName] = &Host{
Name: hostName,
LoadBound: 0,
}
for i := 0; i < c.replicaNum; i++ {
hashedIdx := c.hashFunc(fmt.Sprintf(hostReplicaFormat, hostName, i))
c.replicaHostMap[hashedIdx] = hostName
c.sortedHostsHashSet = append(c.sortedHostsHashSet, hashedIdx)
}
// sort hashes in ascending order
sort.Slice(c.sortedHostsHashSet, func(i int, j int) bool {
if c.sortedHostsHashSet[i] < c.sortedHostsHashSet[j] {
return true
}
return false
})
return nil
}