你的位置:首页 > 软件开发 > ASP.net > 一致性Hash算法在Memcached中的应用

一致性Hash算法在Memcached中的应用

发布时间:2016-01-15 09:00:14
前言  大家应该都知道Memcached要想实现分布式只能在客户端来完成,目前比较流行的是通过一致性hash算法来实现.常规的方法是将server的hash值与server的总台数进行求余,即hash%N,这种方法的弊端是当增减服务器时,将会有较多的缓存需要被重新分配且会造成缓存 ...

前言

  大家应该都知道Memcached要想实现分布式只能在客户端来完成,目前比较流行的是通过一致性hash算法来实现.常规的方法是将server的hash值与server的总台数进行求余,即hash%N,这种方法的弊端是当增减服务器时,将会有较多的缓存需要被重新分配且会造成缓存分配不均匀的情况(有可能某一台服务器分配的很多,其它的却很少).

   今天分享一种叫做”ketama”的一致性hash算法,它通过虚拟节点的概念和不同的缓存分配规则有效的抑制了缓存分布不均匀,并最大限度地减少服务器增减时缓存的重新分布。 

实现思路

  假设我们现在有N台Memcached的Server,如果我们用统一的规则对memcached进行Set,Get操作. 使具有不同key的object很均衡的分散存储在这些Server上,Get操作时也是按同样规则去对应的Server上取出object,这样各个Server之间不就是一个整体了吗?

那到底是一个什么样的规则?

  如下图所示,我们现在有5台(A,B,C,D,E)Memcached的Server,我们将其串联起来形成一个环形,每一台Server都代表圆环上的一个点,每一个点都具有唯一的Hash值,这个圆环上一共有2^32个点.

一致性Hash算法在Memcached中的应用

       那么该如何确定每台Server具体分布在哪个点上? 这里我们通过”Ketama”的Hash算法来计算出每台Server的Hash值,拿到Hash值后就可以对应到圆环上点了.(可以用Server的IP地址作为Hash算法的Key.)

  这样做的好处是,如下图当我新增Server  F时,那么我只需要将hash值落在C和F之间的object从原本的D上重新分配到F上就可以了,其它的server上的缓存不需要重新分配,并且新增的Server也能及时帮忙缓冲其它Server的压力.

一致性Hash算法在Memcached中的应用

  到此我们已经解决了增减服务器时大量缓存需要被重新分配的弊端.那该如何解决缓存分配不均匀的问题呢?因为现在我们的server只占据圆环上的6个点,而圆环上总共有2^32个点,这极其容易导致某一台server上热点非常多,某一台上热点很少的情况.

  ”虚拟节点”的概念很好的解决了这种负载不均衡的问题.通过将每台物理存在的Server分割成N个虚拟的Server节点(N通常根据物理Server个数来定,这里有个比较好的阈值为250).这样每个物理Server实际上对应了N个虚拟的节点. 存储点多了,各个Server的负载自然要均衡一些.就像地铁站出口一样,出口越多,每个出口出现拥挤的情况就会越少.

   代码实现:

一致性Hash算法在Memcached中的应用
   /// <summary>    /// 根据hash key 获取对应的真实Server    /// </summary>    /// <param name="hash"></param>    /// <returns></returns>    public get='_blank'>string GetHostByHashKey(string key)    {      byte[] bytes = Encoding.UTF8.GetBytes(key);      uint hash = BitConverter.ToUInt32(new KetamaHash().ComputeHash(bytes), 0);      //寻找与当前hash值相等的Server.       int i = Array.BinarySearch(ketamaHashKeys, hash);      //如果i小于零则表示没有hash值相等的虚拟节点      if (i < 0)      {        //将i继续按位求补,得到数组中第一个大于当前hash值的虚拟节点        i = ~i;        //如果按位求补后的i大于等于数组的大小,则表示数组中没有大于当前hash值的虚拟节点        //此时直接取第一个server        if (i >= ketamaHashKeys.Length)        {          i = 0;        }      }      //根据虚拟节点的hash key 返回对应的真实server host地址      return hostDictionary[ketamaHashKeys[i]];    }
一致性Hash算法在Memcached中的应用

 

Get一个对象,同样也是通过”Ketama”算法计算出Hash值,然后与Set过程一样寻找节点,找到之后直接取出对象即可.

那么这个”Ketama”到底长什么样呢,让我们来看看代码实现.

一致性Hash算法在Memcached中的应用

原标题:一致性Hash算法在Memcached中的应用

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录