php連接memcache服務器的時候，最初我們只是按照業務來劃分不同的memcache服務器。
後來隨著流量的增加， 有些業務需要更多台memcache服務器做緩存的負載均衡。
為了增加緩存的命中率，最好是在均衡分布的基礎上保證同一個key只對應一台cache服務器(貌似這個說法不太專業…)。
算法也很簡單，假設cache服務器數量為N， 我們只要把key轉化成int或者long(比如做個md5)，然後mod N就可以了。
恩，看起來很正常，很靠譜。
直到有一天，其中一台cache服務器掛了。於是mod N 變成了 mod N-1。
代價？由於N變成了N-1，mod之後，大量的key對應的cache服務器都發生了變化， 緩存命中率大幅度降低。
添加新服務器的時候，也會有這種現象存在。
看個簡單的例子， 現在有1 2 3 4四份數據， A B C三台cache服務器，mod 3之後，1保存在A中，2保存在B中，3保存在C中，4保存在A中，
如果C服務器掛掉，那麼變成mod2， 1保存在A中，2保存在B中，3保存在A中，4保存在B中。有50%的key(3與4)對應的服務器發生了變化。
為了應對這種情況，一種新的算法就出現了: Consistent Hashing。
A B C是三台cache服務器， 對其進行了hash，分布到一個圓環上面。
1 2 3 4是四份數據， 同樣進行了hash，分布到cache的圓環上面。
數據與cache服務器的對應算法如下：
從數據這一點開始，順時針尋找第一台cache服務器。
所以在上圖中，數據1保存在A服務器中， 2保存在B中，3保存在C中，4保存在A中。
如果C服務器掛掉， 那麼1保存在A，2保存在B，3保存在A，4保存在A， 只有25%的key(3)對應的服務器發生了變化。
不過還是存在一個問題， 如上圖，如果cache服務器比較少，那麼它們在圓環上的分布可能不夠均衡， 所以又加入了新的概念：virtual nodes。
意思就是把每一台cache服務器復制成多份，然後再分布到圓環上。
說起來還是有點復雜的，還好有人已經把這種算法搞成了php library，盡管拿來用吧。
http://github.com/Dynom/Canoma
代碼舉例：
// Create the manager
$manager = new \Canoma\Manager(
new \Canoma\HashAdapter\Md5,
30
);
// Register nodes, using unique strings.
$manager->addNode('cache-1.example.com:11211');
$manager->addNode('cache-2.example.com:11211');
$manager->addNode('cache-3.example.com:11211');
// Do a lookup for your cache-identifier and see what node we can use.
$node = $manager->getNodeForString('user:42:session');
參考：
http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
最後附加一段代碼，用來模擬傳統情況下，取消一台cache服務器，會有多大比例的key對應的服務器發生變化：
<?php
$position_array_1 = $position_array_2 = array();
#key的數量
$number_of_keys = 100000;
#最多允許26台cache服務器。
$all_possible_servers = range('a','z');
#cache服務器的數量。
$number_of_cache_servers = 5;
$servers = array_slice($all_possible_servers, 0, $number_of_cache_servers);
#計算每個key對應的cache服務器。
for($key=0;$key<$number_of_keys;$key++)
{
$position_array_1[$key] = $servers[$key % $number_of_cache_servers];
}
//print_R($position_array_1);
#減去最後一台cache服務器。
array_pop($servers);
$number_of_cache_servers = count($servers);
#重新計算每個key對應的cache服務器。
for($key=0;$key<$number_of_keys;$key++)
{
$position_array_2[$key] = $servers[$key % $number_of_cache_servers];
}
//print_R($position_array_2);
#計算有多少個key對應的服務器發生了變化。
$diffs = 0;
foreach($position_array_1 as $k=>$v)
{
if ($position_array_1[$k] != $position_array_2[$k])
{
$diffs++;
}
}
#80%
print round($diffs*100/$number_of_keys, 2).'%';
附2，在consistent hashing的情況下，如果有一台服務器掛掉，會有多大比例key對應的服務器發生變化：
<?PHP
include "Manager.php";
include "HashAdapterAbstract.php";
include "HashAdapterInterface.php";
include "HashAdapter/Md5.php";
// Create the manager
$manager = new \Canoma\Manager(
new \Canoma\HashAdapter\Md5,
30
);
$position_array_1 = $position_array_2 = array();
#key的數量
$number_of_keys = 100000;
#最多允許26台cache服務器。
$all_possible_servers = range('a','z');
#cache服務器的數量。
$number_of_cache_servers = 5;
$servers = array_slice($all_possible_servers, 0, $number_of_cache_servers);
foreach($servers as $k=>$v)
{
// Register nodes, using unique strings.
$manager->addNode($v);
}
#計算每個key對應的cache服務器。
for($key=0;$key<$number_of_keys;$key++)
{
$node = $manager->getNodeForString('user:'.$key.':session');
$position_array_1[$key] = $node;
}
$manager->removeNode($servers[$number_of_cache_servers-1]);
#計算每個key對應的cache服務器。
for($key=0;$key<$number_of_keys;$key++)
