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

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

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

1.取模算法：

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

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

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

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

我們來推算一下產(chǎn)生的后果：

一般地,我們從數(shù)學上歸納之:

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

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

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

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

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

通俗理解一致性哈希：

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

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

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

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

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

所以我們引入了虛擬節(jié)點的概念：

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

散列在圓環(huán)上. 各真實節(jié)點對應的虛擬節(jié)點相互交錯分布

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

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

下面是用php來實現(xiàn)的代碼：

 1 <?php 2  3  4 html' target='_blank'>class Consistent { 5         protected $_nodes = array(); 6  7         //生成一個數(shù)值   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 ?>

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