程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 一致性Hash算法在Memcached中的應用

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

編輯：C#入門知識

前言

　　大家應該都知道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個點.

那麼該如何確定每台Server具體分布在哪個點上? 這裡我們通過”Ketama”的Hash算法來計算出每台Server的Hash值,拿到Hash值後就可以對應到圓環上點了.(可以用Server的IP地址作為Hash算法的Key.)

　　這樣做的好處是,如下圖當我新增Server F時,那麼我只需要將hash值落在C和F之間的object從原本的D上重新分配到F上就可以了,其它的server上的緩存不需要重新分配,並且新增的Server也能及時幫忙緩沖其它Server的壓力.

　　到此我們已經解決了增減服務器時大量緩存需要被重新分配的弊端.那該如何解決緩存分配不均勻的問題呢?因為現在我們的server只占據圓環上的6個點,而圓環上總共有2^32個點,這極其容易導致某一台server上熱點非常多，某一台上熱點很少的情況.

　　”虛擬節點”的概念很好的解決了這種負載不均衡的問題.通過將每台物理存在的Server分割成N個虛擬的Server節點(N通常根據物理Server個數來定,這裡有個比較好的阈值為250).這樣每個物理Server實際上對應了N個虛擬的節點. 存儲點多了,各個Server的負載自然要均衡一些.就像地鐵站出口一樣,出口越多,每個出口出現擁擠的情況就會越少.

　　代碼實現:

         Dictionary<, > hostDictionary =  Dictionary<, >
         [] ketamaHashKeys =  
         [] realHostArr =  
          VirtualNodeNum =  KetamaVirtualNodeInit(.realHostArr = 
         
         =  Dictionary<, ><> hostKeys =  List<> (realHostArr ==  || realHostArr.Length ==   Exception( ( i = ; i < realHostArr.Length; i++ ( j = ; j < VirtualNodeNum; j++[] nameBytes = Encoding.UTF8.GetBytes(.Format(
                     hashKey = BitConverter.ToUInt32( KetamaHash().ComputeHash(nameBytes),   Exception(=

一致性hash算法的分配規則

　　到此我們已經知道了所有虛擬節點的Hash值, 現在讓我們來看下當我們拿到一個對象時如何存入Server, 或是拿到一個對象的Key時該如何取出對象.

Set一個對象時,先將對象的Key作為”Ketama”算法的Key,計算出Hash值後我們需要做下面幾個步驟.

1:首先檢查虛擬節點當中是否有與當前對象Hash值相等的,如有則直接將對象存入那個Hash值相等的節點,後面的步驟就不繼續了.

2:如沒有,則找出第一個比當前對象Hash值要大的節點,(節點的Hash值按升序進行排序,圓環上對應按照順時針來排列),即離對象最近的節點,然後將對象存入該節點.

3:如果沒有找到Hash值比對象要大的Server,證明對象的Hash值是介於最後一個節點和第一個節點之間的,也就是圓環上的E和A之間.這種情況就直接將對象存入第一個節點,即A.

　　代碼實現:　　

      
         
         
         
          GetHostByHashKey([] bytes = hash = BitConverter.ToUInt32( KetamaHash().ComputeHash(bytes), 
             i =
             (i < 
                i = ~
                 (i >==

Get一個對象,同樣也是通過”Ketama”算法計算出Hash值,然後與Set過程一樣尋找節點,找到之後直接取出對象即可.

那麼這個”Ketama”到底長什麼樣呢,讓我們來看看代碼實現.

     
      
     
         FNV_prime =     offset_basis =  =   =   HashCore([] array,  ibStart,  length = ibStart + ( i = ibStart; i < length; i++= (hash * FNV_prime) ^  += hash << ^= hash >> += hash << ^= hash >> += hash <<