golang 实现基于虚拟节点的一致性 hash 算法

发布于: 2020 年 07 月 08 日
golang实现基于虚拟节点的一致性hash算法

问题:实现一个基于虚拟节点的一致性hash cache集群,共10个节点。存放100万个KV, 计算数据分布情况。

解决方案:

三个关键问题:

  1. 如何给10个节点(每个节点对应N个虚拟节点)找到对应的槽位;

  2. 如何快速定位用户key对应的节点cache实例;

  3. 如何判断数据分布情况;

  1. 如何给10个节点(每个节点对应N个虚拟节点)找到对应的槽位;

对每个节点在2^(32-1)上hash出N个数字,对应的数字代表占有的槽位;

同时将所有已经占用的槽位放到map中,方便快速获取cache实例;

  1. 如何快速定位用户key对应的节点cache实例;

每个用户key用同样的方法去做hash, 得到一个数userKey;

遍历已经占有的槽位, 寻找最小的大于等于userKey的数字;

  1. 如何判断数据分布情况;

计算标准差;

关键数据结构:

// 客户端接口
// 这样cache可以是多种实现
type CacheClient interface {
Put(key, value string) error
Get(key string) (string, error)
Delete(key string) error
}
// CacheProxy cache代理
// 通过数字来快速获取CacheProxy中的某个实例
type CacheProxy struct {
// 物理槽位与CacheClient实例的映射
slot2Client map[int]CacheClient
// 物理槽位数量, 对应redis实例数量
realSlot int
// 每个物理槽位对应的虚拟槽位数量
virtualSlot int
// 虚拟槽位与实际槽位的映射
slotMap map[int]int
}
func (proxy *CacheProxy) Put(key, value string) error {
// TODO
}
func (proxy *CacheProxy) Delete(key string) error {
// TODO
}
// 根据字符串key生成一个数字,范围[0, 2^32 -1]
func hash(key string) int (
// TODO
)

原型代码:https://github.com/ToWorld/go-hashcache

发布于: 2020 年 07 月 08 日 阅读数: 23
用户头像

朱月俊

关注

还未添加个人签名 2017.11.06 加入

还未添加个人简介

评论

发布
暂无评论
golang实现基于虚拟节点的一致性hash算法