熬夜的蟲子

前文

　　所謂“高效”，覷頭而已。

 背景

　　談到分布式緩存，大家首先想到的是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條鍵值

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