memcachedの分散アルゴリズム

memcashedの分散

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

memcachedの分散とは

memcachedのサーバが，node1〜node3まであり，アプリケーションから「tokyo」「⁠kanagawa」「⁠chiba」「⁠saitama」「⁠gunma」というキー（名前）のデータを保存する場合を想定する。

まず「tokyo」をmemcachedにaddする。クライアントライブラリに「tokyo」を渡すと，ライブラリに実装されたアルゴリズムよって「キー」から保存するmemcachedサーバを決定する。サーバが決定したら，そのサーバに対して「tokyo」とその値を保存する命令する。

同じように，「⁠kanagawa」「⁠china」「⁠saitama」「⁠gunma」もサーバを決定して保存する。

次は保存したデータの取得です。取得の場合も，ライブラリに対して，取得したいキー「tokyo」を渡す。ライブラリは保存時と同じアルゴリズムを使い，「⁠キー」からサーバを決定する。同じアルゴリズムを利用しており保存したときと同じサーバが決定されるので，サーバに対してgetの命令を送るとなんらかの理由でデータが削除されていない限り，保存した値が取得できる。



このようにキーごとに異なるサーバへ保存することでmemcachedの分散は実現される。memcachedのサーバが多くなればキーも分散され，もしmemcachedのサーバが1台障害がおきて接続できない状態になったとしても，ほかのキャッシュに影響はせずにシステム全体は動き続けることができる。

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

Cache::Memcachedの分散方法について簡単に書くと，「⁠サーバの台数の剰余による分散」になる。キーの整数のハッシュ値を求め，その数値をサーバの台数で割った余りでサーバを決定する。この剰余による分散はシンプルでデータの散らばり具合も優れているが、memcachedサーバの追加や削除を行ったときのキャッシュの組み替えのコストが非常に大きい。サーバを追加すると剰余の結果が大きく変わってしまい，その結果データを保存したときと同じサーバへ取得しにいかなくなり，キャッシュのヒット率に影響が出る。

Consiste Hashing

Consistent Hasingでは，まずmemcachedのサーバ（ノード）のハッシュ値を求め，0から232までの円（continuum）の中に配置する。そして格納するデータのキーも同じようにハッシュ値を求め，円の上にマッピングする。データはマッピングされた地点から時計回りで最初に見つかるサーバに保存される。サーバが見つからず232を超えた場合は最初のmemcachedのサーバに保存する。

この状態からmemcachedのサーバを1台追加をします。剰余による分散ではキーが保存されるサーバが大きく変化しキャッシュ率に影響がでていたが，Consistent-Hashingではcontinuum上でサーバが追加された地点から時計回りとは逆方向で最初に見つかるサーバまでにあるキーのみが影響を受ける。

このようにしてConsistent Hashingでは，キーの組み替えを最小限にしている。また，Consistent Hasingの実装によっては仮想ノードという考え方が取り入れられている。通常のhash関数を通す方法ではサーバがマッピングされる場所のばらつきが非常に大きくなる。そこで仮想ノードでは1つのノード（サーバ）に対して100〜200個の点をcontinuum上に作成してそれを利用する。これによりばらつきを押さえ，サーバの増減時のキャッシュの組み替えを最小限にしている。

後述するConsistent Hashingに対応したmemcachedのクライアントライブラリを利用した実験の結果からは，現在のサーバの台数（n）と増やすサーバの台数（m）から，増設後のヒット率を以下の計算で求めることがわかっている。

(1 - n/(n + m))*100