Memcached分布式實現
分布式原理
這里多次使用了 “ 分布式 ” 這個詞，但并未做詳細解釋。 現在開始簡單地介紹一下其原理，各個客戶端的實現基本相同。
下面假設 memcached 服務器有 node1 ～ node3 三臺， 應用程序要保存鍵名為“tokyo”“kanagawa”“chiba”“saitama”“gunma” 的數據。
圖 1 分布式簡介：準備
首先向 memcached 中添加 “tokyo” 。將 “tokyo” 傳給客戶端程序庫后， 客戶端實現的算法就會根據 “ 鍵 ” 來決定保存數據的 memcached 服務器。 服務器選定后，即命令它保存 “tokyo” 及其值。
圖 2 分布式簡介：添加時
同樣， “kanagawa”“chiba”“saitama”“gunma” 都是先選擇服務器再保存。
接下來獲取保存的數據。獲取時也要將要獲取的鍵 “tokyo” 傳遞給函數庫。 函數庫通過與數據保存時相同的算法，根據 “ 鍵 ” 選擇服 務器。 使用的算法相同，就能選中與保存時相同的服務器，然后發送 get 命令。 只要數據沒有因為某些原因被刪除，就能獲得保存的值。
圖 3 分布式簡介：獲取時
這樣，將不同的鍵保存到不同的服務器上，就實現了 memcached 的分布式。 memcached 服務器增多后，鍵就會分散，即使一臺 memcached 服務器發生故障 無法連接，也不會影響其他的緩存，系統依然能繼續運行。
分布式算法
緩存系統中應用比較多的是余數計算分散和一致性 HASH 計算分散。
余數計算分散
余數計算分散法簡單來說，就是 “ 根據服務器臺數的余數進行分散 ” 。
1. 求得傳入鍵的整數哈希值（ int hashCode ）。
2. 使用計算出的 hashCode 除以服務器臺數 (N) 取余數（ C=hashCode % N ）
3. 在 N 臺服務器中選擇序號為 C 的服務器。
余數計算的方法簡單，數據的分散性也相當優秀，但也有其缺點。 那就是當添加或移除服務器時，緩存重組的代價相當巨大。 添加服務器后，余數就會產生巨變，這樣就無法獲取與保存時相同的服務器， 從而影響緩存的命中率。
Consistent Hashing
算法
一致性 HASH 算法我的理解，簡單來說就是 , 在一個大的數據范圍內的構建一個虛擬的環，首（ 0 ）尾（Integer.MAXVALUE ）相接的圓環，然后通過 某種 HASH 算法 增加虛擬節點的方式（ 1 個實體節點可以虛擬 N個虛擬階段，如 160 ， 200 ， 1000 等）讓節點更為均勻的分別在環上。 KEY 請求的時候，也通過相同的 某種 HASH 算法 計算出 HASH 值，然后在在到環上定位同向最接近的虛擬節點，最后通過虛擬節點與實體節點的對應關系找到服務的實體節點。
網上介紹很多，圖也多，不想在截取了。那就給個連接：
http://blog.csdn.net/sparkliang/article/details/5279393
另外公司現有的項目中也使用 Consistent Hashing 用于分表定位，緩存定位等。工程項目中也有先關算法的實現。
特點
1. 算法實現比較麻煩，需要構建虛擬環。
2. 解決了余數算法增加節點命中大幅額度降低的問題，理論上，插入一個實體節點，平均會影響到：虛擬節點數/2 的節點數據的命中
參考 ：http://tech.idv2.com/2008/07/10/memcached-001/
http://acooly.iteye.com/blog/1120819