一致性哈希研究

一致性哈希是比较流行的web cache技术。

面试中常考一致性哈希这个问题,随手用 Python + 最简单的数据结构 实现了核心算法的逻辑。

# 一个已排序的服务器列表,我们需要把列表想象成环,其实只需要考虑一个特殊情况,就是环对接的地方,就是两头
# 其中是每个server的hash值
servers = [4, 7, 13, 19, 22, 27, 39, 44]

# 参数hv是一个cache的hash值,返回该cache对应server的hash值
def find_hole(hv):
    maxi = len(servers) - 1
    # 判断是不是在环对接的地方
    if hv <= servers[0] or hv > servers[maxi]:
        return servers[0]
    return find_hole_inside(hv, 0, maxi)

def find_hole_inside(hv, li, ri):
    if li >= (ri - 1):
        return servers[ri]
    mi = (li + ri) / 2
    if hv > servers[mi]:
        return find_hole_inside(hv, mi, ri)
    else:
        return find_hole_inside(hv, li, mi)

hvlist = [1, 8, 20, 26, 27, 40, 99] #测试数据列表
for hv in hvlist:
    print find_hole(hv)

拓展问题1:

在实际的实现中,servers这个集合需要支持高效的插入、删除,而且要有序,一个最好的办法就是使用二叉树(为了平衡,比如可以用红黑树)。这样既保证了查找的时候就像上面list数据结构的二分查找一样高效,也保证了高效的插入和自动有序。

拓展问题2:

关于如何做哈希。一致性哈希有个虚拟节点的概念,就是可能在环中有多个node代表同一台server。基本上用如下的方法就可以哈希出来了。

 import md5 #用md5

 topn = 50 #有一个上限的hash值,用来取模

 def my_hash(name, i):
     m1 = md5.new(name+str(i)) #md5的值是server的name和当前虚拟节点的index
     return int(m1.hexdigest(), 16) % topn

 server = {'name': 'zhoutall', 'replica': 4}
 for i in range(server['replica']):
     print my_hash(server['name'], i)
Tags : ,

3 thoughts on “一致性哈希研究”

  1. 赞。
    可以深入写下分布式系统是怎么实现一致性哈希的,比如dynamo好像每个节点都存整个环,但会存在一致性同步问题,所以有很多分布式一致性哈希实现,比如chord,每个节点都存部分数据。

  2. 我竟然找到同一个实验室,同一级的小伙伴~~~
    我最近也看了consistent hashing,Karger的论文好难懂=-=
    一般的实现都是红黑树,不过这样lookup就是log(C)了。也可以用一个辅助哈希表来管理cache node。
    我刚刚实现了一把红黑树的 https://github.com/SJTU-DDST/consistent-hash

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: