首先我們知道Memcached是一個分布式的緩存系統，但memcached并不像是mongodb那樣，允許配置多個節點，且節點之間是自動分配數據的

也就是說memcached節點之間，是互不相通信的，因此，memcached的分布式，要靠用戶去設計算法，把數據分布在多個memcached節點中。

我們來看一下常用的分布式的算法：

1.取模算法：

最容易想到的就是取模算法，即N個節點要從0-》n-1進行編號，key對N取模，余i，則key落在第i臺服務器上。

就是將server的hash值與server的總臺數進行求余,即hash%N,這種方法的弊端是當增減服務器時,將會有較多的緩存需要被重新分配且會造成緩存分配不均勻的情況(有可能某一臺服務器分配的很多,其它的卻很少).

但我們來看一下這種算法對緩存命中率的影響：

我們假設有8臺服務器，運行中突然down一臺，則求余的底數變成7

我們來推算一下產生的后果：

一般地,我們從數學上歸納之:

有N臺服務器，變成了N-1臺服務器，

每N*(N-1)個數中，只有（n-1）個單元，%n，%（n-1）得到相同的結果

所以 命中率在服務器down的短期內，急遽下降至1/(N-1)

所以 服務器越多，則down機的后果越嚴重！

我們來討論下一致性hash的算法：

通俗理解一致性哈希：

把各個服務器節點放在鐘表的各個時刻上，我們將Key也映射到鐘表的某個時刻上，該key沿鐘表順時針走，碰到第一個比它小的節點后，則這個key就落到這臺服務器上。

1 疑問1:時鐘上的指針最大才11點,如果我有上百個memcached節點怎么辦?2 答: 時鐘只是為了便于理解做的比喻,在實際應用中,我們可以在圓環上分布[0,2^32-1]的數字,3 這樣,全世界的服務器都可以裝下了.4 5 疑問2:我該如何把”節點名”,”鍵名”轉化成整數?6 答: 你可以用現在的函數,如crc32().7 也可以自己去設計轉化規則,但注意轉化后的碰撞率要低.8 即不同的節點名,轉換為相同的整數的概率要低.

好了，那我們再考慮一下當某個節點Down了之后，后產生什么樣的影響？

當某個節點down后,只影響該節點順時針之后的1個節點,而其他節點不受影響.因此，Consistent Hashing最大限度地抑制了鍵的重新分布

我們通過上圖看到，6號節點down后，所有的壓力都轉移到7號節點上，造成了7號節點服務器的壓力特別的大，那我們考慮是否能夠將6號節點的壓力注意到其余的節點上呢？

所以我們引入了虛擬節點的概念：

虛擬節點即----N個真實節點,把每個真實節點映射成M個虛擬節點, 再把M*N個虛擬節點,

散列在圓環上. 各真實節點對應的虛擬節點相互交錯分布

這樣,某真實節點down后,則把其影響平均分擔到其他所有節點上

好了，上面就是一致性hash的理論知識點，接下來我們來考慮一下怎樣實現？

下面是用php來實現的代碼：

 1 <?php 2  3  4 html' target='_blank'>class Consistent { 5         protected $_nodes = array(); 6  7         //生成一個數值   8         public function _hash($str){ 9                 return sprintf('%u',crc32($str));10         }11 12         public function find($key){13                 $point = $this->_hash($key);14                 $pos  = current($this->_nodes);15 16                 foreach($this->_nodes as $k=>$v){17                         if($point <= $k){18                                 $pos = $v;19                                 break;20                         }21                 }22                 return $pos;23         }24 25         public function addServer($server){26                 for($i=1;$i<=32;$i++){27                         $pos = $this->_hash($server.'-'.$i);28                         $this->_nodes[$pos] = $server;29                 }30 31                 ksort($this->_nodes,SORT_REGULAR);32         }33 34         public function printNodes(){35                 print_r($this->_nodes);36         }37 38 }39 40 $cons = new Consistent();41 42 $cons->addServer('a');43 $cons->addServer('b');44 $cons->addServer('c');45 46 echo $cons->_hash('name').'<br/>';47 echo '應該落在'.$cons->find('name').'<br/>';48 49 $cons->printNodes();50 ?>

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。