背景
談到分布式緩存，大家首先想到的是memcached。確實memcached是目前最流行的方案之一。不過很多互聯網公司不用memcached，例如新蛋。為什麼不選擇memcached呢，命中率？熱插拔？還是性能。這裡先不放結論，用事實來說話。
算法篇 -1.除余法
如果你手上有老版本的memcache官方文檔。你會發現他們用的是除余法來保持節點的一致性。假如你有N台緩存服務器，你需要將某個對象set進某一台節點上。用hash取模這樣可以很均勻的保證每台的負載。那麼，作為最基本的輪詢算法，是否適合分布式緩存我們來看實例。
這裡假設有4台緩存節點，先設置除余方案。
自動設置999條鍵值。
下面來看下除余方案的各種綜合結果
本文URL地址：http://www.bianceng.cn/Programming/csharp/201410/45481.htm
總的來說如果是相對穩定的環境 這種方案還是相當不錯，至於性能我會單獨開篇幅來說。
但是如果添加一台新節點 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)方法，匹配到對應位置。
還是找了幾張圖過來.... 嘴拙 講不清楚 直接看圖吧
本文URL地址：http://www.bianceng.cn/Programming/csharp/201410/45481.htm
在這個環形空間中，如果沿著順時針方向從對象的 key 值出發，直到遇見一個 cache ，那麼就將該對象存儲在這個 cache 上，因為對象和 cache 的 hash 值是固定的，因此這個 cache 必然是唯一和確定的。左下表示移除節點的情況，右下表示添加節點的情況
繼續看圖看結果
在穩定狀態下 發現負載不是很平衡 不過還能接受 繼續看看添加節點的情況
命中率變70多了 能hold住了 低要求的話 應該還是不錯的，再看看新節點的利用情況，隨機再生成200條
馬馬虎虎吧 負載偏差比較大 命中率一般
算法篇 -3 一致性hash算法 _ 虛擬節點 (consistent hashing)
相對普通hash算法 多了一個虛擬節點的概念 這也是目前memcache最主流的算法。
長話短說 就是我把一個節點虛擬成N多個虛節點 這些虛節點指向同一個物理節點 但是key值hash參照虛節點來設置
直接上圖
本文URL地址：http://www.bianceng.cn/Programming/csharp/201410/45481.htm
穩定狀態下不錯 同樣我們在新添一個節點
命中率提高了不上 不過負載還不是很平衡 隨機再加300條
對比普通hash算法好多了
算法篇 -4 一致性hash算法改進
針對一致性hash算法的虛擬節點 說白了就是一個50大小的坑被拆成 5個10大小的坑而已，不過縫隙小了 對於比較聚集的數據來說還是很有好處的
如何改進 將50大小的坑就變成10大小 對於新增的節點 我們不進虛擬節點化或者個性配置節點化
前面效率和一致性hash比較類似 我們直接看添加節點的情況
98% 有木有 有木有！！！ 負載也還不錯 你是不是已經被hold住了。
不過作為不良改進者 蟲子還是要告訴大家這個改進一個很大的弊端 就是新節點的利用率
我們再隨機新建600條鍵值
對於命中率的提高 是以新節點利用率為代價 至於之間怎麼平衡 就看各自把握了
本文URL地址：http://www.bianceng.cn/Programming/csharp/201410/45481.htm
算法篇 -5 完美改進
上一種改進還是基於memcache現有的基礎之上，跳出這個圈子為何要用一致性hash。
大家可以猜想一下這個方案的實現辦法。關於這個方案的設計會單獨開個篇幅來講。
言歸正傳直接上圖看結果
添加一台新服務器
命中率還是100% hold住 還有更精彩的 我們隨機添加500條鍵值
