memcachedの徹底分析 – 4. Memcachedの分散アルゴリズム_PHPチュートリアル-PHPチュートリアル-php.cn

元リンク: http://gihyo.jp/dev/feature/01/memcached/0004

この連載記事へのリンクはこちら:

初回: http://www.phpchina. com /html/29/n-35329.html
2回目: http://www.phpchina.com/html/30/n-35330.html
3回目: http://www.phpchina. com /html/31/n-35331.html
4回目: http://www.phpchina.com/html/32/n-35332.html href="http://www.phpchina.com/html/32/n-35332.html">
5回目: http://www.phpchina .com/html/32/n-35333.html href="http://www.phpchina.com/html/32/n-35333.html"> href="http://www.phpchina.com/html/32/n-35332.html">

ミクシィの永野です。第2回、第3回では前坂氏がmemcachedの内部事情を紹介しました。今回は memcached の内部構造の紹介はやめて、memcached のディストリビューションの紹介を始めます。

Memcached のディストリビューション
- memcached のディストリビューションとは何を意味しますか?
Cache::Memcachedの分散メソッド
- 剰余に基づいて分散を計算する
- 剰余に基づいて分散を計算するデメリット
Consistent Hashing
- Consistent Hashingの簡単な説明
- Consistent Hashingをサポートする関数ライブラリ
概要

memcachedの分散

初回でも紹介したように、memcachedは「分散」キャッシュサーバーと呼ばれていますが、サーバー側に「分散」機能はありません。サーバー側は前坂氏が2回目と3回目で紹介したメモリストレージ機能のみで実装は非常にシンプルです。 memcached のディストリビューションに関しては、クライアントライブラリによって完全に実装されます。この分散がmemcachedの最大の特徴です。

memcached のディストリビューションとは何を意味しますか?

ここでは「分散」という言葉が何度も出てきますが、詳しくは説明しません。ここで、各クライアントの実装は基本的に同じであることを簡単に紹介します。

以下では、node1~node3 の 3 つの memcached サーバーがあり、アプリケーションはキー名「tokyo」、「kanagawa」、「chiba」、「saitama」、「gunma」でデータを保存する必要があると想定しています。

memcachedの徹底分析 – 4. Memcachedの分散アルゴリズム_PHPチュートリアル

図1 ディストリビューションの導入:準備

まず、memcachedに「tokyo」を追加します。「tokyo」をクライアントライブラリに渡すと、クライアントによって実装されたアルゴリズムが、「キー」に基づいてデータを保存する memcached サーバーを決定します。サーバーが選択されると、「tokyo」とその値を保存するように命令されます。

図2 ディストリビューションの紹介: 追加時

同様に、「kanakawa」、「chiba」、「saitama」、「gunma」もすべて最初にサーバーを選択してから保存します。

次にセーブデータを取得します。取得時には、取得するキー「tokyo」も関数ライブラリに渡す必要があります。関数ライブラリは、データを保存するときに使用されるのと同じアルゴリズムを使用して、「キー」に基づいてサーバーを選択します。同じアルゴリズムを使用して、保存時と同じサーバーを選択し、get コマンドを送信できます。何らかの理由でデータが削除されない限り、保存された値を取得できます。

図3 分散導入: 取得時

このように、異なるキーを異なるサーバーに保存することでmemcachedの分散を実現します。 memcached サーバーの数が増えるとキーが分散され、1 つの memcached サーバーに障害が発生して接続できなくなっても、他のキャッシュには影響せず、システムは引き続き実行できます。

次に、初回で触れたPerlクライアント関数ライブラリCache::Memcachedで実装される分散メソッドを紹介します。

Cache::Memcached の分散メソッド

Perl の memcached クライアント関数ライブラリ Cache::Memcached は、memcached の作者である Brad Fitzpatrick の作品であり、オリジナルの関数ライブラリと言えます。

Cache::Memcached - search.cpan.org

この関数ライブラリは分散関数を実装しており、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 を使用します。

String::CRC32 - search.cpan.org

まず文字列の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等许多地方都介绍过，这里只简单地说明一下。

mixi Engineers' Blog - スマートな分散で快適キャッシュライフ
ConsistentHashing - コンシステントハッシュ法

Consistent Hashing的简单说明

Consistent Hashing如下所示：首先求出memcached服务器（节点）的哈希值，并将其配置到0～2³²的圆（continuum）上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2³²仍然找不到服务器，就会保存到第一台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开发。

libketama - a consistent hashing algo for memcache clients – RJ ブログ - Users at Last.fm

至于Perl客户端，连载的第1次中介绍过的Cache::Memcached::Fast和Cache::Memcached::libmemcached支持 Consistent Hashing。

Cache::Memcached::Fast - search.cpan.org
Cache::Memcached::libmemcached - search.cpan.org

两者的接口都与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。