gihyo.jpサイトのロゴ

memcachedを知り尽くす

第4回memcachedの分散アルゴリズム

2008-07-23


株式会社ミクシィの長野です。第2回、第3回と前坂がmemcachedの内部について紹介しました。今回は内部構造から離れて、memcachedの分散についての紹介をいたします。

memcachedの分散


連載の1回目に紹介しましたが、memcachedは﹁分散﹂キャッシュサーバと言われていますが、サーバ側には﹁分散﹂の機能は備わっていません。サーバ側には当連載の第2回、第3回で前坂が紹介したメモリストレージの機能のみが組み込まれており、非常にシンプルな実装となっています。では、memcachedの分散はどのように実現しているのかと言うと、すべてクライアントライブラリによって実現されます。この分散方法はmemcachedの大きな特徴です。

memcachedの分散とは


ここまで数度﹁分散﹂という言葉を用いてきましたが、あまり詳しく触れてきませんでした。ここでは各クライアントの実装に共通する大まかな仕組みから紹介いたします。
memcachedのサーバが、node1〜node3まであり、アプリケーションから﹁tokyo﹂﹁⁠kanagawa﹂﹁⁠chiba﹂﹁⁠saitama﹂﹁⁠gunma﹂というキー︵名前︶のデータを保存する場合を想定してみます。
図1　分散概要‥準備
図1　分散概要：準備
まず﹁tokyo﹂をmemcachedにaddします。クライアントライブラリに﹁tokyo﹂を渡すと、ライブラリに実装されたアルゴリズムよって﹁キー﹂から保存するmemcachedサーバを決定します。サーバが決定したら、そのサーバに対して﹁tokyo﹂とその値を保存する命令をします。
図2　分散概要‥追加時
図2　分散概要：追加時
同じように、﹁⁠kanagawa﹂﹁⁠china﹂﹁⁠saitama﹂﹁⁠gunma﹂もサーバを決定して保存します。
次は保存したデータの取得です。取得の場合も、ライブラリに対して、取得したいキー﹁tokyo﹂を渡します。ライブラリは保存時と同じアルゴリズムを使い、﹁⁠キー﹂からサーバを決定します。同じアルゴリズムを利用しているので保存したときと同じサーバが決定されるので、サーバに対してgetの命令を送るとなんらかの理由でデータが削除されていない限り、保存した値が取得できます。
図3　分散概要‥取得時
図3　分散概要：取得時
このようにキーごとに異なるサーバへ保存することでmemcachedの分散は実現されています。memcachedのサーバが多くなればキーも分散され、もしmemcachedのサーバが1台障害がおきて接続できない状態になったとしても、ほかのキャッシュに影響はせずにシステム全体は動き続けることができます。
次は具体的な実装として、1回目の連載で紹介した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﹂というオプションを指定します。

剰余による分散方法の弱点


この剰余による分散はシンプルでデータの散らばり具合も優れていますが、弱点もあります。その弱点とはmemcachedサーバの追加や削除を行ったときのキャッシュの組み替えのコストが非常に大きいことがあげられます。サーバを追加すると剰余の結果が大きく変わってしまい、その結果データを保存したときと同じサーバへ取得しにいかなくなり、キャッシュのヒット率に影響が出ます。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として保存し実行しました。
まず、最初にサーバが3台のときに
 
$ 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...と1台のサーバに8個から10個のデータが保存されました。
次にmemcachedのサーバを1台増やします。
 
$ 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を増やして実行しました。このようにノードを増やすと、キーが分散されるサーバが大きく変化するのがわかると思います。26個のデータのうち6個のみが元のサーバと同じところを参照し、ほかのデータは異なるサーバへ移動してしまいます。ヒット率では23%まで低下してしまいます。Webアプリケーションでmemcachedを利用している場合、memcachedを増設した瞬間にキャッシュの効率が落ち、データベースサーバに負荷が集中し正常にサービスが行えないような状態になることが考えられます。
mixiのWebアプリケーション運用でもこの問題ありmemcachedサーバの増設ができずにいましたが、新しい分散方法を利用することで現在ではmemcachedを手軽に増設していくことができるようになっています。その分散方法がConsistent Hashingです。

Consistent Hashing


Consistet Hashingの考え方は、株式会社ミクシィのエンジニアブログなどで数多く紹介されていますので、ここでは簡単に説明させていただきます。

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

Consiste Hashingの簡単な説明


Consistent Hasingでは、まずmemcachedのサーバ︵ノード︶のハッシュ値を求め、0から232までの円︵continuum︶の中に配置します。そして格納するデータのキーも同じようにハッシュ値を求め、円の上にマッピングします。データはマッピングされた地点から時計回りで最初に見つかるサーバに保存されます。サーバが見つからず232を超えた場合は最初のmemcachedのサーバに保存します。
図4　Consistent Hashing‥基本
図4　Consistent Hashing：基本
この状態からmemcachedのサーバを1台追加をします。剰余による分散ではキーが保存されるサーバが大きく変化しキャッシュ率に影響がでていましたが、Consistent-Hashingではcontinuum上でサーバが追加された地点から時計回りとは逆方向で最初に見つかるサーバまでにあるキーのみが影響を受けます。
図5　Consistent Hashing‥サーバ追加
図5　Consistent Hashing：サーバ追加
このようにしてConsistent Hashingでは、キーの組み替えを最小限にしています。また、Consistent Hasingの実装によっては仮想ノードという考え方が取り入れられています。通常のhash関数を通す方法ではサーバがマッピングされる場所のばらつきが非常に大きくなります。そこで仮想ノードでは1つのノード︵サーバ︶に対して100〜200個の点をcontinuum上に作成してそれを利用します。これによりばらつきを押さえ、サーバの増減時のキャッシュの組み替えを最小限にしています。
後述するConsistent Hashingに対応したmemcachedのクライアントライブラリを利用した実験の結果からは、現在のサーバの台数︵n︶と増やすサーバの台数︵m︶から、増設後のヒット率を以下の計算で求めることがわかっています。
 
(1 - n/(n + m))*100

Consistent Hashing対応のライブラリ


この連載でも何回か紹介しているCache::Memcachedでは、Consistent Hashingはサポートされていませんが、既にいくつかのクライアントライブラリがこの新しい分散方法をサポートしています。Consistet 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は、Brian Aker氏によるCのライブラリlibmemcachedを利用しているPerlのモジュールになります。libmemcached自体がいくつかの分散アルゴリズムを組み込んでおり、Consistent Hashingも実装されているので、そのPerlバインディングでもConsistent Hashingがサポートされています。

●Tangent Software: libmemcached

まとめ


memcachedの分散の方法について説明をさせていただきました。memcachedの分散はクライアントライブラリによって行われること、また効率的なデータの分散のためにConsistent Hashingが用いられることについて紹介しました。次回はmixiでのmemcachedの運用やノウハウ、互換アプリケーションについて紹介したいと思いますのでよろしくお願いします。
  

おすすめ記事

記事・ニュース一覧