memcached全面剖析–memcached的分佈式算法
memcached的分佈式
正如第1次中介紹的那樣， memcached雖然稱爲「分佈式」緩存服務器，但服務器端並無「分佈式」功能。 服務器端僅包括 第2次、 第3次 前阪介紹的內存存儲功能，其實現很是簡單。 至於memcached的分佈式，則是徹底由客戶端程序庫實現的。 這種分佈式是memcached的最大特色。javascript
memcached的分佈式是什麼意思？
這裏屢次使用了「分佈式」這個詞，但並未作詳細解釋。 如今開始簡單地介紹一下其原理，各個客戶端的實現基本相同。php
下面假設memcached服務器有node1～node3三臺， 應用程序要保存鍵名爲「tokyo」「kanagawa」「chiba」「saitama」「gunma」 的數據。html
圖1 分佈式簡介：準備java
首先向memcached中添加「tokyo」。將「tokyo」傳給客戶端程序庫後， 客戶端實現的算法就會根據「鍵」來決定保存數據的memcached服務器。 服務器選定後，即命令它保存「tokyo」及其值。node
圖2 分佈式簡介：添加時web
一樣，「kanagawa」「chiba」「saitama」「gunma」都是先選擇服務器再保存。算法
接下來獲取保存的數據。獲取時也要將要獲取的鍵「tokyo」傳遞給函數庫。 函數庫經過與數據保存時相同的算法，根據「鍵」選擇服務器。 使用的算法相同，就能選中與保存時相同的服務器，而後發送get命令。 只要數據沒有由於某些緣由被刪除，就能得到保存的值。數據庫
圖3 分佈式簡介：獲取時緩存
這樣，將不一樣的鍵保存到不一樣的服務器上，就實現了memcached的分佈式。 memcached服務器增多後，鍵就會分散，即便一臺memcached服務器發生故障 沒法鏈接，也不會影響其餘的緩存，系統依然能繼續運行。服務器
接下來介紹第1次 中提到的Perl客戶端函數庫Cache::Memcached實現的分佈式方法。
Cache::Memcached的分佈式方法
Perl的memcached客戶端函數庫Cache::Memcached是 memcached的做者Brad Fitzpatrick的做品，能夠說是原裝的函數庫了。
該函數庫實現了分佈式功能，是memcached標準的分佈式方法。
根據餘數計算分散
Cache::Memcached的分佈式方法簡單來講，就是「根據服務器臺數的餘數進行分散」。 求得鍵的整數哈希值，再除以服務器臺數，根據其他數來選擇服務器。
下面將Cache::Memcached簡化成如下的Perl腳原本進行說明。
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 ]; # 根據餘數選擇服務器 printf "%s => %s\n", $key, $server; }
Cache::Memcached在求哈希值時使用了CRC。
首先求得字符串的CRC值，根據該值除以服務器節點數目獲得的餘數決定服務器。 上面的代碼執行後輸入如下結果：
tokyo => node2 kanagawa => node3 chiba => node2 saitama => node1 gunma => node1
根據該結果，「tokyo」分散到node2，「kanagawa」分散到node3等。 多說一句，當選擇的服務器沒法鏈接時，Cache::Memcached會將鏈接次數 添加到鍵以後，再次計算哈希值並嘗試鏈接。這個動做稱爲rehash。 不但願rehash時能夠在生成Cache::Memcached對象時指定「rehash => 0」選項。
根據餘數計算分散的缺點
餘數計算的方法簡單，數據的分散性也至關優秀，但也有其缺點。 那就是當添加或移除服務器時，緩存重組的代價至關巨大。 添加服務器後，餘數就會產生鉅變，這樣就沒法獲取與保存時相同的服務器， 從而影響緩存的命中率。用Perl寫段代碼來驗證其代價。
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並執行。
首先，當服務器只有三臺時：
$ 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
結果如上，node1保存a、c、d、e……，node2保存g、i、k……， 每臺服務器都保存了8個到10個數據。
接下來增長一臺memcached服務器。
$ 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命中了。像這樣，添加節點後 鍵分散到的服務器會發生巨大變化。26個鍵中只有六個在訪問原來的服務器， 其餘的全都移到了其餘服務器。命中率下降到23%。在Web應用程序中使用memcached時， 在添加memcached服務器的瞬間緩存效率會大幅度降低，負載會集中到數據庫服務器上， 有可能會發生沒法提供正常服務的狀況。
mixi的Web應用程序運用中也有這個問題，致使沒法添加memcached服務器。 但因爲使用了新的分佈式方法，如今能夠垂手可得地添加memcached服務器了。 這種分佈式方法稱爲 Consistent Hashing。
Consistent Hashing
關於Consistent Hashing的思想，mixi株式會社的開發blog等許多地方都介紹過， 這裏只簡單地說明一下。
Consistent Hashing的簡單說明
Consistent Hashing以下所示：首先求出memcached服務器（節點）的哈希值， 並將其配置到0～232的圓（continuum）上。 而後用一樣的方法求出存儲數據的鍵的哈希值，並映射到圓上。 而後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個服務器上。 若是超過232仍然找不到服務器，就會保存到第一臺memcached服務器上。
圖4 Consistent Hashing：基本原理
從上圖的狀態中添加一臺memcached服務器。餘數分佈式算法因爲保存鍵的服務器會發生巨大變化 而影響緩存的命中率，但Consistent Hashing中，只有在continuum上增長服務器的地點逆時針方向的 第一臺服務器上的鍵會受到影響。
圖5 Consistent Hashing：添加服務器
所以，Consistent Hashing最大限度地抑制了鍵的從新分佈。 並且，有的Consistent Hashing的實現方法還採用了虛擬節點的思想。 使用通常的hash函數的話，服務器的映射地點的分佈很是不均勻。 所以，使用虛擬節點的思想，爲每一個物理節點（服務器） 在continuum上分配100～200個點。這樣就能抑制分佈不均勻， 最大限度地減少服務器增減時的緩存從新分佈。
經過下文中介紹的使用Consistent Hashing算法的memcached客戶端函數庫進行測試的結果是， 由服務器臺數（n）和增長的服務器臺數（m）計算增長服務器後的命中率計算公式以下：
(1 - n/(n+m)) * 100
支持Consistent Hashing的函數庫
本連載中屢次介紹的Cache::Memcached雖然不支持Consistent Hashing， 但已有幾個客戶端函數庫支持了這種新的分佈式算法。 第一個支持Consistent Hashing和虛擬節點的memcached客戶端函數庫是 名爲libketama的PHP庫，由last.fm開發。
至於Perl客戶端，連載的第1次 中介紹過的Cache::Memcached::Fast和Cache::Memcached::libmemcached支持 Consistent Hashing。
二者的接口都與Cache::Memcached幾乎相同，若是正在使用Cache::Memcached， 那麼就能夠方便地替換過來。Cache::Memcached::Fast從新實現了libketama， 使用Consistent Hashing建立對象時能夠指定ketama_points選項。
my $memcached = Cache::Memcached::Fast->new({ servers => ["192.168.0.1:11211","192.168.0.2:11211"], ketama_points => 150 });
另外，Cache::Memcached::libmemcached 是一個使用了Brain Aker開發的C函數庫libmemcached的Perl模塊。 libmemcached自己支持幾種分佈式算法，也支持Consistent Hashing， 其Perl綁定也支持Consistent Hashing。
總結
本次介紹了memcached的分佈式算法，主要有memcached的分佈式是由客戶端函數庫實現， 以及高效率地分散數據的Consistent Hashing算法。下次將介紹mixi在memcached應用方面的一些經驗， 和相關的兼容應用程序。