memcachedを知り尽くす

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

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

Consistent Hashing

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

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で開発されました。

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は,Brian Aker氏によるCのライブラリlibmemcachedを利用しているPerlのモジュールになります。libmemcached自体がいくつかの分散アルゴリズムを組み込んでおり,Consistent Hashingも実装されているので,そのPerlバインディングでもConsistent Hashingがサポートされています。

まとめ

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

著者プロフィール

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

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

URLhttp://blog.nomadscafe.jp/

コメント

コメントの記入