华东15选5不开奖

memcached全面剖析–4. memcached的分布式算法

發布時間:2016/4/11 11:41:10  關鍵字:ASP.NET、memcached、memcached全面剖析–4. memcached的分布式算法

系列文章導航:

memcached完全剖析–1. memcached的基礎

memcached全面剖析–2. 理解memcached的內存存儲

memcached全面剖析–3. memcached的刪除機制和發展方向

memcached全面剖析–4. memcached的分布式算法

memcached全面剖析–5. memcached的應用和兼容程序


發表日:2008/7/23
作者:長野雅廣(Masahiro Nagano)
原文鏈接:http://gihyo.jp/dev/feature/01/memcached/0004

我是Mixi的長野。 第2次第3次 由前坂介紹了memcached的內部情況。本次不再介紹memcached的內部結構, 開始介紹memcached的分布式。

memcached的分布式

正如第1次中介紹的那樣, memcached雖然稱為“分布式”緩存服務器,但服務器端并沒有“分布式”功能。 服務器端僅包括 第2次第3次 前坂介紹的內存存儲功能,其實現非常簡單。 至于memcached的分布式,則是完全由客戶端程序庫實現的。 這種分布式是memcached的最大特點。

memcached的分布式是什么意思?

這里多次使用了“分布式”這個詞,但并未做詳細解釋。 現在開始簡單地介紹一下其原理,各個客戶端的實現基本相同。

下面假設memcached服務器有node1~node3三臺, 應用程序要保存鍵名為“tokyo”“kanagawa”“chiba”“saitama”“gunma” 的數據。


圖1 分布式簡介:準備

首先向memcached中添加“tokyo”。將“tokyo”傳給客戶端程序庫后, 客戶端實現的算法就會根據“鍵”來決定保存數據的memcached服務器。 服務器選定后,即命令它保存“tokyo”及其值。


圖2 分布式簡介:添加時

同樣,“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應用方面的一些經驗, 和相關的兼容應用程序。

华东15选5不开奖
河北20选5计算器 江西时时彩怎么停的 jdb财神捕鱼打法 北京赛车pk拾开奖查询 中原风采22选5开奖号码预测 北京十一选五最大遗漏数据 网上玩真人龙虎斗 股票配资余额 福建31选7开奖查询280 新疆十一选五走势图一定牛