【C#|.NET】跳出一緻性Hash算法 打造更高效的分布式緩存

背景

　　談到分布式緩存，大家首先想到的是memcached。确實memcached是目前最流行的方案之一。不過很多網際網路公司不用memcached，例如新蛋。為什麼不選擇memcached呢，命中率？熱插拔？還是性能。這裡先不放結論，用事實來說話。

算法篇 -1.除餘法

　　　　如果你手上有老版本的memcache官方文檔。你會發現他們用的是除餘法來保持節點的一緻性。假如你有N台緩存伺服器，你需要将某個對象set進某一台節點上。用hash取模這樣可以很均勻的保證每台的負載。那麼，作為最基本的輪詢算法，是否适合分布式緩存我們來看執行個體。

這裡假設有4台緩存節點，先設定除餘方案。

自動設定999條鍵值。

下面來看下除餘方案的各種綜合結果

　　總的來說如果是相對穩定的環境 這種方案還是相當不錯，至于性能我會單獨開篇幅來說。

但是如果添加一台新節點 192.168.0.5

再來重新擷取鍵值

再随機追加200條鍵值

注意看資料中的命中率資料 新節點會投入環境 參與新的取模運算 但是之前因為模運算變化的鍵值就丢失了

算法篇 -2 普通hash算法

既然取模運算沒辦法保證我們的鍵值一緻性，那麼就要考慮新的方案了。不過設計我們自己的方案之前，我們可以繼續看看memcache的使用者們進行了哪些改進。

通常的 hash 算法都是将 value 映射到一個 32 位的 key 值，也即是 0~2的32-1 次方的數值空間；

我不喜歡畫圖，大家就想象一下吧，一個首尾相接的圓。用hash算法将節點分布在圓的不同部位，同樣對key值進行hash算法，通過       

public static int BinarySearch<T>(T[] array, T value)方法，比對到對應位置。

還是找了幾張圖過來.... 嘴拙 講不清楚 直接看圖吧

在這個環形空間中，如果沿着順時針方向從對象的 key 值出發，直到遇見一個 cache ，那麼就将該對象存儲在這個 cache 上，因為對象和 cache 的 hash 值是固定的，是以這個 cache 必然是唯一和确定的。左下表示移除節點的情況，右下表示添加節點的情況

繼續看圖看結果

在穩定狀态下 發現負載不是很平衡 不過還能接受 繼續看看添加節點的情況

命中率變70多了 能hold住了 低要求的話 應該還是不錯的，再看看新節點的利用情況，随機再生成200條

馬馬虎虎吧 負載偏差比較大 命中率一般

算法篇 -3 一緻性hash算法 _ 虛拟節點 (consistent hashing)

相對普通hash算法 多了一個虛拟節點的概念 這也是目前memcache最主流的算法。

長話短說 就是我把一個節點虛拟成N多個虛節點 這些虛節點指向同一個實體節點 但是key值hash參照虛節點來設定

直接上圖

穩定狀态下不錯 同樣我們在新添一個節點

命中率提高了不上 不過負載還不是很平衡 随機再加300條

對比普通hash算法好多了

算法篇 -4 一緻性hash算法改進

針對一緻性hash算法的虛拟節點 說白了就是一個50大小的坑被拆成 5個10大小的坑而已，不過縫隙小了 對于比較聚集的資料來說還是很有好處的

如何改進 将50大小的坑就變成10大小 對于新增的節點 我們不進虛拟節點化或者個性配置節點化

前面效率和一緻性hash比較類似 我們直接看添加節點的情況

98% 有木有 有木有！！！ 負載也還不錯 你是不是已經被hold住了。

不過作為不良改進者 蟲子還是要告訴大家這個改進一個很大的弊端 就是新節點的使用率

我們再随機建立600條鍵值

對于命中率的提高 是以新節點使用率為代價 至于之間怎麼平衡 就看各自把握了

算法篇 -5 完美改進

上一種改進還是基于memcache現有的基礎之上，跳出這個圈子為何要用一緻性hash。

大家可以猜想一下這個方案的實作辦法。關于這個方案的設計會單獨開個篇幅來講。

言歸正傳直接上圖看結果

添加一台新伺服器

命中率還是100% hold住 還有更精彩的  我們随機添加500條鍵值

本篇先到此 希望對大家有幫助

本文轉自 熬夜的蟲子  51CTO部落格，原文連結:http://blog.51cto.com/dubing/757518