memcachedを知り尽くす

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

この記事を読むのに必要な時間:およそ 4 分

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」というオプションを指定します。

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

この剰余による分散はシンプルでデータの散らばり具合も優れていますが,弱点もあります。その弱点とは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です。

著者プロフィール

長野雅広(ながの まさひろ)

株式会社ミクシィ 開発部システム運用グループ アプリケーション運用チーム所属。mixiのアプリケーション運用に携わっています。Perlのカンファレンス,YAPC::Asia 2008でもmemcachedに関する発表を行いました。

URLhttp://blog.nomadscafe.jp/