Golang实现一致性Hash算法
什么是一致性Hash算法
一致性Hash算法是使用取模的方法,一致性Hash算法是对2^32取模,什么意思呢?简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下:
圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1
我们把这个由2的32次方个点组成的圆环称为hash环。
假设我们有3台缓存服务器,服务器A、服务器B、服务器C,那么,在生产环境中,这三台服务器肯定有自己的IP地址,我们使用它们各自的IP地址进行哈希计算,使用哈希后的结果对2^32取模,可以使用如下公式示意
hash(服务器A的IP地址) % 2^32
通过上述公式算出的结果一定是一个0到2^32-1之间的一个整数,我们就用算出的这个整数,代表服务器A,既然这个整数肯定处于0到2^32-1之间,那么,上图中的hash环上必定有一个点与这个整数对应,而我们刚才已经说明,使用这个整数代表服务器A,那么,服务器A就可以映射到这个环上,用下图示意
同理,服务器B与服务器C也可以通过相同的方法映射到上图中的hash环中。所以现在的hash环:
这样我们的服务器就映射到了hash环上,现在我们同理也就可以把我们需要访问的对象也放在hash环上。
假设我们现在需要分别在三个服务器上放缓存的文件,我们就使用文件的名字作为计算hash的key:
hash(文件名) % 2^32
这样也能计算一个值,也就能映射到对应的hash环上。现在我们的hash环就变成了这个样子:
计算出来了文件的hash值,下一步就是觉得那个服务器存储这个对象了。这里规定是:从计算出来的位置开始向顺时针方向遇到的第一个服务器,进行存储。所以这里文件就会存储在服务器B上。
这就是一致性hash算法。
优点
这里我们假设,我们的服务器B突然失效了,我们上面例子中的文件就会存储到服务器c中,这样就算是缓存失效。但是这里服务器失效的是A,就对上面例子中的文件不会有任何的影响。使用一致性哈希算法时,服务器的数量如果发生改变,并不是所有缓存都会失效,而是只有部分缓存会失效,前端的缓存仍然能分担整个系统的压力,而不至于所有压力都在同一时间集中到后端服务器上。这就是一致性哈希算法所体现出的优点。
hash环的偏斜
理想情况下我们的3个服务器是如上图所示,均匀的分布在hash环上,但是理想往往和现实差距很大:
实际上映射中,服务器可能会被映射成这样:
这种情况下缓存的对象很有可能大部分集中缓存在某一台服务器。这就很难受了。这就是hash环的偏斜。那么,我们应该怎样防止hash环的偏斜呢?
虚拟节点
虚拟节点就是来解决hash环偏斜的问题的。顾名思义就是在hash环上创建每个服务器的副本,是”实际节点”(实际的物理服务器)在hash环上的复制品,一个实际节点可以对应多个虚拟节点,创建副本后的hash环就变成了这样:
这样就解决了偏移问题。虚拟节点越多,hash环上的节点就越多,缓存被均匀分布的概率就越大。
Golang中实现hash环
package hash
import (
"errors"
"hash/crc32"
"sort"
"strconv"
"sync"
)
//声明新切片类型
type units []uint32
//返回切片长度
func (x units) Len() int {
return len(x)
}
//比对两个数大小
func (x units) Less(i, j int) bool {
return x[i] < x[j]
}
//切片中两个值的交换
func (x units) Swap(i, j int) {
x[i], x[j] = x[j], x[i]
}
//创建结构体保存一致性hash信息
type ConsistentHash struct {
//hash环,key为哈希值,值存放节点的信息
circle map[uint32]string
//已经排序的节点hash切片
sortedHashes units
//虚拟节点个数,用来增加hash的平衡性
VirtualNode int
//map 读写锁
sync.RWMutex
}
//创建一致性hash算法结构体,设置默认节点数量
func NewConsistent(nodeNum int) *ConsistentHash {
return &ConsistentHash{
//初始化变量
circle: make(map[uint32]string),
//设置虚拟节点个数
VirtualNode: nodeNum,
}
}
//自动生成key值
func (c *ConsistentHash) generateKey(element string, index int) string {
//副本key生成逻辑
return element + strconv.Itoa(index)
}
//获取hash位置 计算key 在hash环中对应的位置
func (c *ConsistentHash) hashKey(key string) uint32 {
//当长度不够填充
if len(key) < 64 {
//声明一个数组长度为64
var tmpList [64]byte
//拷贝数据到数组中
copy(tmpList[:], key)
//使用IEEE 多项式返回数据的CRC-32校验和
return crc32.ChecksumIEEE(tmpList[:len(key)])
}
return crc32.ChecksumIEEE([]byte(key))
}
//更新排序,方便查找 因为后面我们使用的是sort.Search进行查找 sort.Search使用的是二分法进行查找,所以这里需要排序
func (c *ConsistentHash) updateSortedHashes() {
hashes := c.sortedHashes[:0]
//判断切片容量,是否过大,如果过大则重置
if cap(c.sortedHashes)/(c.VirtualNode*4) > len(c.circle) {
hashes = nil
}
//添加hashes
for k := range c.circle {
hashes = append(hashes, k)
}
//对所有节点hash值进行排序,
//方便之后进行二分查找
sort.Sort(hashes)
//重新赋值
c.sortedHashes = hashes
}
//向hash环中添加节点
func (c *ConsistentHash) Add(element string) {
//加锁
c.Lock()
//解锁
defer c.Unlock()
c.add(element)
}
//添加节点
func (c *ConsistentHash) add(element string) {
//循环虚拟节点,设置副本
for i := 0; i < c.VirtualNode; i++ {
//根据生成的节点添加到hash环中
c.circle[c.hashKey(c.generateKey(element, i))] = element
}
//更新排序
c.updateSortedHashes()
}
//删除节点
func (c *ConsistentHash) remove(element string) {
for i := 0; i < c.VirtualNode; i++ {
delete(c.circle, c.hashKey(c.generateKey(element, i)))
}
c.updateSortedHashes()
}
//删除一个节点
func (c *ConsistentHash) Remove(element string) {
c.Lock()
defer c.Unlock()
c.remove(element)
}
//顺时针查找最近的节点
func (c *ConsistentHash) search(key uint32) int {
//查找算法
f := func(x int) bool {
return c.sortedHashes[x] > key
}
//使用"二分查找"算法来搜索指定切片满足条件的最小值
i := sort.Search(len(c.sortedHashes), f)
//如果超出范围则设置i=0
if i >= len(c.sortedHashes) {
i = 0
}
return i
}
//根据数据标示获取最近的服务器节点信息
func (c *ConsistentHash) Get(name string) (string, error) {
//添加锁
c.RLock()
//解锁
defer c.RUnlock()
//如果为零则返回错误
if len(c.circle) == 0 {
return "", errors.New("hash环没有数据")
}
//计算hash值
key := c.hashKey(name)
i := c.search(key)
return c.circle[c.sortedHashes[i]], nil
}
这样就很简单的实现了golong的一致性hash。
这里提一下,为什么是2^32呢?因为这个算法的出现就算为了解决分布式问题,所以在分布式中基本上存储的就算服务器的ip,IPv4的地址是4组8位2进制数组成,所以用2^32可以保证每个IP地址会有唯一的映射。
参考连接:https://www.cnblogs.com/williamjie/p/9477852.html
本文使用CC BY-NC-SA 3.0 中国大陆协议许可
本文链接:https://myxy99.cn/posts/golang/6a0c048e.html