前言：
我們知道以往資料要放到 M 臺(tái)服務(wù)器上，最簡單的方法就是取余數(shù) (hash_value % M) 然后放到對(duì)應(yīng)的服務(wù)器上，那就是當(dāng)添加或移除服務(wù)器時(shí)，緩存重組的代價(jià)相當(dāng)巨大。 添加服務(wù)器后，余數(shù)就會(huì)產(chǎn)生巨變，這樣就無法獲取與保存時(shí)相同的服務(wù)器， 從而影響緩存的命中率。
下面這篇文章寫的非常好，結(jié)合memcached的 特點(diǎn)利用Consistent hasning 算法，可以打造一個(gè)非常完備的分布式緩存服務(wù)器。
我是Mixi的長野。 本次不再介紹memcached的內(nèi)部結(jié)構(gòu)， 開始介紹memcached的分布式。
memcached的分布式
正如第1次中介紹的那樣， memcached雖然稱為“分布式”緩存服務(wù)器，但服務(wù)器端并沒有“分布式”功能。 服務(wù)器端僅包括 第2次、 第3次 前坂介紹的內(nèi)存存儲(chǔ)功能，其實(shí)現(xiàn)非常簡單。 至于memcached的分布式，則是完全由客戶端程序庫實(shí)現(xiàn)的。 這種分布式是memcached的最大特點(diǎn)。
memcached的分布式是什么意思？
這里多次使用了“分布式”這個(gè)詞，但并未做詳細(xì)解釋。 現(xiàn)在開始簡單地介紹一下其原理，各個(gè)客戶端的實(shí)現(xiàn)基本相同。
下面假設(shè)memcached服務(wù)器有node1～node3三臺(tái)， 應(yīng)用程序要保存鍵名為“tokyo”“kanagawa”“chiba”“saitama”“gunma” 的數(shù)據(jù)。
圖1 分布式簡介：準(zhǔn)備
首先向memcached中添加“tokyo”。將“tokyo”傳給客戶端程序庫后， 客戶端實(shí)現(xiàn)的算法就會(huì)根據(jù)“鍵”來決定保存數(shù)據(jù)的memcached服務(wù)器。 服務(wù)器選定后，即命令它保存“tokyo”及其值。
圖2 分布式簡介：添加時(shí)
同樣，“kanagawa”“chiba”“saitama”“gunma”都是先選擇服務(wù)器再保存。
接下來獲取保存的數(shù)據(jù)。獲取時(shí)也要將要獲取的鍵“tokyo”傳遞給函數(shù)庫。 函數(shù)庫通過與數(shù)據(jù)保存時(shí)相同的算法，根據(jù)“鍵”選擇服務(wù)器。 使用的算法相同，就能選中與保存時(shí)相同的服務(wù)器，然后發(fā)送get命令。 只要數(shù)據(jù)沒有因?yàn)槟承┰虮粍h除，就能獲得保存的值。
圖3 分布式簡介：獲取時(shí)
這樣，將不同的鍵保存到不同的服務(wù)器上，就實(shí)現(xiàn)了memcached的分布式。 memcached服務(wù)器增多后，鍵就會(huì)分散，即使一臺(tái)memcached服務(wù)器發(fā)生故障 無法連接，也不會(huì)影響其他的緩存，系統(tǒng)依然能繼續(xù)運(yùn)行。
接下來介紹第1次 中提到的Perl客戶端函數(shù)庫Cache::Memcached實(shí)現(xiàn)的分布式方法。
Cache::Memcached的分布式方法
Perl的memcached客戶端函數(shù)庫Cache::Memcached是 memcached的作者Brad Fitzpatrick的作品，可以說是原裝的函數(shù)庫了。
該函數(shù)庫實(shí)現(xiàn)了分布式功能，是memcached標(biāo)準(zhǔn)的分布式方法。
根據(jù)余數(shù)計(jì)算分散
Cache::Memcached的分布式方法簡單來說，就是“根據(jù)服務(wù)器臺(tái)數(shù)的余數(shù)進(jìn)行分散”。 求得鍵的整數(shù)哈希值，再除以服務(wù)器臺(tái)數(shù)，根據(jù)其余數(shù)來選擇服務(wù)器。
下面將Cache::Memcached簡化成以下的Perl腳本來進(jìn)行說明。
use strict;
use warnings;
use String::CRC32;
my @nodes = (’node1′,’node2′,’node3′);
my @keys = (’tokyo’, ‘kanagawa’, ‘chiba’, ’saitama’, ‘gunma’);
foreach my $key (@keys) {
my $crc = crc32($key); # CRC値
my $mod = $crc % ( $#nodes + 1 );
my $server = $nodes[ $mod ]; # 根據(jù)余數(shù)選擇服務(wù)器
printf “%s => %s\n”, $key, $server;
}
Cache::Memcached在求哈希值時(shí)使用了CRC。
首先求得字符串的CRC值，根據(jù)該值除以服務(wù)器節(jié)點(diǎn)數(shù)目得到的余數(shù)決定服務(wù)器。 上面的代碼執(zhí)行后輸入以下結(jié)果：
tokyo => node2
kanagawa => node3
chiba => node2
saitama => node1
gunma => node1
根據(jù)該結(jié)果，“tokyo”分散到node2，“kanagawa”分散到node3等。 多說一句，當(dāng)選擇的服務(wù)器無法連接時(shí)，Cache::Memcached會(huì)將連接次數(shù) 添加到鍵之后，再次計(jì)算哈希值并嘗試連接。這個(gè)動(dòng)作稱為rehash。 不希望rehash時(shí)可以在生成Cache::Memcached對(duì)象時(shí)指定“rehash => 0”選項(xiàng)。
根據(jù)余數(shù)計(jì)算分散的缺點(diǎn)
余數(shù)計(jì)算的方法簡單，數(shù)據(jù)的分散性也相當(dāng)優(yōu)秀，但也有其缺點(diǎn)。 那就是當(dāng)添加或移除服務(wù)器時(shí)，緩存重組的代價(jià)相當(dāng)巨大。 添加服務(wù)器后，余數(shù)就會(huì)產(chǎn)生巨變，這樣就無法獲取與保存時(shí)相同的服務(wù)器， 從而影響緩存的命中率。用Perl寫段代碼來驗(yàn)證其代價(jià)。
use strict;
use warnings;
use String::CRC32;
my @nodes = @ARGV;
my @keys = (’a’..’z');
my %nodes;
foreach my $key ( @keys ) {
my $hash = crc32($key);
my $mod = $hash % ( $#nodes + 1 );
my $server = $nodes[ $mod ];
push @{ $nodes{ $server } }, $key;
}
foreach my $node ( sort keys %nodes ) {
printf “%s: %s\n”, $node, join “,”, @{ $nodes{$node} };
}
這段Perl腳本演示了將“a”到“z”的鍵保存到memcached并訪問的情況。 將其保存為mod.pl并執(zhí)行。
首先，當(dāng)服務(wù)器只有三臺(tái)時(shí)：
$ mod.pl node1 node2 nod3
node1: a,c,d,e,h,j,n,u,w,x
node2: g,i,k,l,p,r,s,y
node3: b,f,m,o,q,t,v,z
結(jié)果如上，node1保存a、c、d、e……，node2保存g、i、k……， 每臺(tái)服務(wù)器都保存了8個(gè)到10個(gè)數(shù)據(jù)。
接下來增加一臺(tái)memcached服務(wù)器。
$ mod.pl node1 node2 node3 node4
node1: d,f,m,o,t,v
node2: b,i,k,p,r,y
node3: e,g,l,n,u,w
node4: a,c,h,j,q,s,x,z
添加了node4。可見，只有d、i、k、p、r、y命中了。像這樣，添加節(jié)點(diǎn)后 鍵分散到的服務(wù)器會(huì)發(fā)生巨大變化。26個(gè)鍵中只有六個(gè)在訪問原來的服務(wù)器， 其他的全都移到了其他服務(wù)器。命中率降低到23%。在Web應(yīng)用程序中使用memcached時(shí)， 在添加memcached服務(wù)器的瞬間緩存效率會(huì)大幅度下降，負(fù)載會(huì)集中到數(shù)據(jù)庫服務(wù)器上， 有可能會(huì)發(fā)生無法提供正常服務(wù)的情況。
mixi的Web應(yīng)用程序運(yùn)用中也有這個(gè)問題，導(dǎo)致無法添加memcached服務(wù)器。 但由于使用了新的分布式方法，現(xiàn)在可以輕而易舉地添加memcached服務(wù)器了。 這種分布式方法稱為 Consistent Hashing。
Consistent Hashing
關(guān)于Consistent Hashing的思想，mixi株式會(huì)社的開發(fā)blog等許多地方都介紹過， 這里只簡單地說明一下。
Consistent Hashing的簡單說明
Consistent Hashing如下所示：首先求出memcached服務(wù)器（節(jié)點(diǎn)）的哈希值， 并將其配置到0～232的圓（continuum）上。 然后用同樣的方法求出存儲(chǔ)數(shù)據(jù)的鍵的哈希值，并映射到圓上。 然后從數(shù)據(jù)映射到的位置開始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上。 如果超過232仍然找不到服務(wù)器，就會(huì)保存到第一臺(tái)memcached服務(wù)器上。
圖4 Consistent Hashing：基本原理
從上圖的狀態(tài)中添加一臺(tái)memcached服務(wù)器。余數(shù)分布式算法由于保存鍵的服務(wù)器會(huì)發(fā)生巨大變化 而影響緩存的命中率，但Consistent Hashing中，只有在continuum上增加服務(wù)器的地點(diǎn)逆時(shí)針方向的 第一臺(tái)服務(wù)器上的鍵會(huì)受到影響。
圖5 Consistent Hashing：添加服務(wù)器
因此，Consistent Hashing最大限度地抑制了鍵的重新分布。 而且，有的Consistent Hashing的實(shí)現(xiàn)方法還采用了虛擬節(jié)點(diǎn)的思想。 使用一般的hash函數(shù)的話，服務(wù)器的映射地點(diǎn)的分布非常不均勻。 因此，使用虛擬節(jié)點(diǎn)的思想，為每個(gè)物理節(jié)點(diǎn)（服務(wù)器） 在continuum上分配100～200個(gè)點(diǎn)。這樣就能抑制分布不均勻， 最大限度地減小服務(wù)器增減時(shí)的緩存重新分布。
通過下文中介紹的使用Consistent Hashing算法的memcached客戶端函數(shù)庫進(jìn)行測試的結(jié)果是， 由服務(wù)器臺(tái)數(shù)（n）和增加的服務(wù)器臺(tái)數(shù)（m）計(jì)算增加服務(wù)器后的命中率計(jì)算公式如下：
(1 - n/(n+m)) * 100
支持Consistent Hashing的函數(shù)庫
本連載中多次介紹的Cache::Memcached雖然不支持Consistent Hashing， 但已有幾個(gè)客戶端函數(shù)庫支持了這種新的分布式算法。 第一個(gè)支持Consistent Hashing和虛擬節(jié)點(diǎn)的memcached客戶端函數(shù)庫是 名為libketama的PHP庫，由last.fm開發(fā)。
至于Perl客戶端，連載的第1次 中介紹過的Cache::Memcached::Fast和Cache::Memcached::libmemcached支持 Consistent Hashing。
兩者的接口都與Cache::Memcached幾乎相同，如果正在使用Cache::Memcached， 那么就可以方便地替換過來。Cache::Memcached::Fast重新實(shí)現(xiàn)了libketama， 使用Consistent Hashing創(chuàng)建對(duì)象時(shí)可以指定ketama_points選項(xiàng)。
my $memcached = Cache::Memcached::Fast->new({
servers => ["192.168.0.1:11211","192.168.0.2:11211"],
ketama_points => 150
});
另外，Cache::Memcached::libmemcached 是一個(gè)使用了Brain Aker開發(fā)的C函數(shù)庫libmemcached的Perl模塊。 libmemcached本身支持幾種分布式算法，也支持Consistent Hashing， 其Perl綁定也支持Consistent Hashing。
總結(jié)
本次介紹了memcached的分布式算法，主要有memcached的分布式是由客戶端函數(shù)庫實(shí)現(xiàn)， 以及高效率地分散數(shù)據(jù)的Consistent Hashing算法。下次將介紹mixi在memcached應(yīng)用方面的一些經(jīng)驗(yàn)， 和相關(guān)的兼容應(yīng)用程序。