当前访客身份:游客 [ 登录  | 注册加入尚学堂]
启用新域名sxt.cn
新闻资讯

一致性哈希学习

我来了! 发表于 2年前  | 评论(0 )| 阅读次数(834 )|   2 人收藏此文章,   我要收藏
摘要 一致性哈希学习
一致性哈希在分布式系统中被很多的使用,比如说memcached就是使用一致性哈希来做的。学习一下这个一致性哈希算法。

下面这篇博客利用图解的形式,将一致性哈希算法讲述的非常清楚:

博客:http://blog.codinglabs.org/articles/consistent-hashing.html

参考代码,下面我列出了java和c#的两个代码实现,可以通过读代码更深刻的去理解一下这个算法。 代码:

根据上述文章和代码,仿照着写了一个粗略版本的一致性哈希算法。


publicdelegateintHashFunction(stringval);
 
publicclassConsistentHash<T>whereT :class
{
    //this value used for generate virtual nodes
    privateint_replica;
    //Hash fuction used to calculate hash code base on a string
    privateHashFunction getHashCode;
    //image this as a big circle which store the node
    privateSortedDictionary<int, T> circle =newSortedDictionary<int, T>();
 
    publicConsistentHash(HashFunction hashFunc, ICollection<T> nodes,intreplicaNum = 100)
    {
        _replica = replicaNum;
        getHashCode = hashFunc;
        Init(nodes);
    }
 
    publicvoidAdd(T node)
    {
        for(inti = 0; i < _replica; i++)
        {
            inthash = getHashCode(node.GetHashCode().ToString() + i);
            circle[hash] = node;
        }
    }
 
    publicvoidRemove(T node)
    {
        for(inti = 0; i < _replica; i++)
        {
            inthash = getHashCode(node.GetHashCode().ToString() + i);
            circle.Remove(hash);
        }
    }
 
    publicT GetNode(objectkey)
    {
        if(key ==null)
            returnnull;
        inthashcode = getHashCode(key.GetHashCode().ToString());
        intfirstNode = GetFirst(circle.Keys.ToArray() , hashcode);
        returncircle[firstNode];
    }
 
    /// <summary>
    /// use binary search to search the first value in keys array
    /// which bigger than hashcode
    /// if not exist return first key in keys array
    /// </summary>
    /// <param name="keys">key array</param>
    /// <param name="hashcode"></param>
    /// <returns></returns>
    privateintGetFirst(int[] keys,inthashcode)
    {
        intbeg = 0, end = keys.Length - 1;
        circle.Keys.CopyTo(keys, keys.Length);
        if(hashcode < keys[beg] || hashcode > keys[end])
            returnkeys[0];
        while(end > beg)
        {
            intmid = (end + beg) / 2;
            if(keys[mid] >= hashcode)
                end = mid;
            else
                beg = mid;
        }
        returnkeys[end];
    }
 
    privatevoidInit(ICollection<T> nodes)
    {
        foreach(T nodeinnodes)
        {
            Add(node);
        }
    }
}


  • 没有使用那个默认的Hash code,因为默认的哈希实现可能不够好。最好能够使用自己可以控制的一个好的哈希算法。
  • _replica变量就是每一个结点对应的虚拟节点的个数。虚拟节点是为了解决数据倾斜的问题,也就是说节点分布的不够均匀导致最后分配到每一个节点上的负载不均衡。理论上来说如果实际节点越少,则需要的虚拟节点越多。
  • 使用SortedDictionary是为了查找是能够使用二分查找快速找到一个适合的节点。

更多参考资料:

分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
声明:博客文章版权属于原创作者,受法律保护。如果侵犯了您的权利,请联系管理员,我们将及时删除!
(邮箱:webmaster#sxt.cn(#换为@))
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183