哈希彩竞猜娱乐游戏俱乐部系统开发详情

一致性 Hash 算法详述

区块链哈希算法竞猜游戏开发，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/consistent-hashing-demo

下面开始实现吧！

结构体、错误以及常量定义

① 结构体定义

首先定义每一台缓存服务器的数据结构：

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.com/2017/04/consistent-hashing-with-bounded-loads.html

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

}