【しばらく編集不可モードで運営します】 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

ConsistentHashing - コンシステント・ハッシュ法

差分表示


コンシステント・ハッシュ法

* この文書について

- "Tom White's Blog: Consistent Hashing" の日本語訳です.
-- http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
- 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか...
- 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/

* コンシステント・ハッシュ法

私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。
このアイデアをあらわした論文
(
&link(David Karger,http://people.csail.mit.edu/karger/) らによる
&link(Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,http://citeseer.ist.psu.edu/karger97consistent.html) )
が書かれたのは 10 年前のことだが、近年その用途は多くのサービスに広がりを見せている。
Amazon の &link(Dynamo,http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html) から &link(memcached,http://www.danga.com/memcached/) (&link(Last.fm,http://www.last.fm/) による改良) などがそうだ。
このコンシステント・ハッシュ法とはどんなもので、なぜ気に留めておくべきなのだろうか。

コンシステント・ハッシュ法の必要性は、
複数マシンからなるキャッシュを運用するとわかる、ある制限が示している ... 
例として、 ''n'' 台のキャッシュ用マシンがあったとしよう。このとき負荷分散に使うよくある方法は、
あるオブジェクト ''o'' を hash(o) mod n 番目のマシンに保存するやりかただろう。この方法は上手く行く。何らかの都合でマシンの追加や削除をするまでは。
変数 n を変えるとき、''すべてのオブジェクトは新しい位置を求めるためにハッシュしなおす''必要がある。
これは悲惨だ。オリジナルのコンテンツがあるサーバはキャッシュ用マシンからの要求に溢れてしまう。
キャッシュが突然消えてしまうようなものだ。まあ、ある意味そうなのだけれど。
(これが気に留めておくべきという理由だ。
コンシステント・ハッシュ法を使えばこのサーバ溢れを防ぐことができる。)

こんなのが望ましい。キャッシュ用マシンを追加したら、
そのマシンは他のマシンから適正な分量のオブジェクトをうけとる。
同じくマシンを除去したら、除去したマシンのオブジェクトは残ったマシンがわけあう。
コンシステント・ハッシュ法はまさにこう動く。
可能な限り ''一貫して'' 同じマシンに同じオブジェクトを割り当ててくれる。

コンシステント・ハッシュ法のミソは、オブジェクトとキャッシュ(キャッシュ用マシン)に同じハッシュ関数をつかうこと。
キャッシュはある区間に対応づけられる。その区間は多くのオブジェクトのハッシュ値を含んでいる。
キャッシュが除去されると、隣接する区間のキャッシュが除去されたキャッシュの区間を引き受ける。
他のキャッシュは影響をうけない。

** 実例

詳しく見てみよう。ハッシュ関数はオブジェクトとキャッシュを一定の値域に写像する。
Java プログラマにとっては馴染みのある話だとおもう ... Object の hashCode() メソッドは int を返す。
int は -2^31 から 2^31-1 の値域をもつ。
この値域が円周に写像されると考えよう。数字がぐるりと円を囲う。
以下の図は、 4 つのオブジェクト (1,2,3,4) と 3 つのキャッシュ (A,B,C) が円周に配置されている。
ハッシュでの配置場所には点でマークをつけた。
(図は David Karger らの &link(Web Caching with Consistent Hashing,http://www8.org/w8-papers/2a-webserver/caching/paper2.html) に倣った。)

http://weblogs.java.net/blog/tomwhite/archive/images/consistent_hashing_1.png

&link(college essays,http://customcollegeessays.com/index.php)

各オブジェクトがどのキャッシュに入るのかを調べるには、
キャッシュの点にぶつかるまでオブジェクトの点を時計周りに動かせばいい。
上の図では 1,4 がキャッシュ A に入り、2 は B, 3 は C に入る。

&link(debt management company,http://www.eurodebt.com/)

&link(make money online,http://www.business-opportunities-mentor.co.uk/)

C が削除されたとしよう。するとオブジェクト 3 は A に入る。他の対応は変わらない。
以下の図に示す位置へキャッシュ D が追加されたら、3, 4 が D に移る。そして 1 だけが A に残る。

http://weblogs.java.net/blog/tomwhite/archive/images/consistent_hashing_2.png

割り当てる区間に当たり外れが無ければ、これはうまくいく。
乱数を使う以上、キャッシュ間でオブジェクトの分布が非一様になることはありうる。
これを解決するために "仮想ノード" を使うアイデアがある。仮想ノードではキャッシュ点を円周上で複製する。
ひとつキャッシュを追加するたびに、円周には複数の点が配置される。

仮想ノードの効果を以下のグラフに示す。
下にあるコードを使い、10000 オブジェクトを 10 のキャッシュに保存する
シミュレーションをした結果だ。
X 軸がキャッシュ点の複製数(対数スケール)になる。
複製数が小さいとオブジェクトの分散がバランスしていない。
キャッシュ毎のオブジェクト数の平均値の標準偏差の大きさからそれがわかる。
(Y軸、こちらも対数スケール。) 

この実験から、複製を 100 から 200 用意すると妥当なバランスを実現できるといえる。
(標準偏差が平均値の 5-10% 程度になる。)

http://weblogs.java.net/blog/tomwhite/archive/images/ch-graph.png

** 実装

締めとして Java を使った簡単な実装を示す。
コンシステント・ハッシュ法が効力を発揮するためには
ハッシュ関数がよく振れているのが大切。
Object の hashCode() 実装は大抵よく振れて ''いない''。
たとえば、限られた小さな値しか返さなかったりする。
そこで HashFunction インターフェイスを用意し、
利用するハッシュ関数を差し替えられるようにする。
ここでは MD5 ハッシュを勧めておく。

 import java.util.Collection;
 import java.util.SortedMap;
 import java.util.TreeMap;
 
 public class ConsistentHash<T> {
 
  private final HashFunction hashFunction;
  private final int numberOfReplicas;
  private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
 
  public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
      Collection<T> nodes) {
    this.hashFunction = hashFunction;
    this.numberOfReplicas = numberOfReplicas;
 
    for (T node : nodes) {
      add(node);
    }
  }
 
  public void add(T node) {
    for (int i = 0; i < numberOfReplicas; i++) {
      circle.put(hashFunction.hash(node.toString() + i), node);
    }
  }
 
  public void remove(T node) {
    for (int i = 0; i < numberOfReplicas; i++) {
      circle.remove(hashFunction.hash(node.toString() + i));
    }
  }
 
  public T get(Object key) {
    if (circle.isEmpty()) {
      return null;
    }
    int hash = hashFunction.hash(key);
    if (!circle.containsKey(hash)) {
      SortedMap<Integer, T> tailMap = circle.tailMap(hash);
      hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
    }
    return circle.get(hash);
  }
 
 }

円周はソート済みマップとして表現している。整数のキーはキャシュ(ここでは T 型)のハッシュ値をあらわす。
ConsistentHash を構築するときに各ノードは円周上の複数箇所に配置される(numberOfReplicas 変数で制御)。
複製の位置は数値から求める接頭詞をつけたノード名から計算する。ノード自体はマップの各点に保存される。

ノードからオブジェクトを取得するには (get メソッド)、''オブジェクトのハッシュ値'' をマップの検索に使う。
ハッシュ値で保存されたノードが見付かることは滅多にない。
(ハッシュの値域はノード数よりずっと広いため、複製を含めてもまだ広い。) 
だからその次の値を探すことになり、それには tail map の最初のキーを使う。
tail map が空なら、戻って円周自体の最初のキーを使えばいい。

** 用途

どうやってコンシステント・ハッシュ法を使えばいいだろう? 
自分でコードを書くよりは、ライブラリの中でみつかるのが一番ありそうだ。
たとえば既に述べたように、分散メモリオブジェクトキャッシュシステムである memcached には
コンシステント・ハッシュ法をサポートしたクライアントがある。
Last.fm の &link(Richard Jones,http://www.last.fm/user/RJ/) による  &link(ketama,http://www.audioscrobbler.net/development/ketama/) が最初で、
いまなら &link(Dustin Salling,http://bleu.west.spy.net/%7Edustin/) の Java 実装もある。(これに触発されて上のデモ実装を作った。)
コンシステント・ハッシュ法をクライアント側だけで実現しているのは面白い。
memcached サーバに変更はない。 
コンシステント・ハッシュ法を使う他のシステムとしては 分散ハッシュテーブル実装の &link(Chord,http://pdos.csail.mit.edu/chord/) がある。
また Amazon の Dynamo でも利用している。これは key-value store で、Amazon の外では利用できない。&link(G-class mercedes-benz,http://g-classics.com/shop/page/14?shop_param=)

----
- 「乱数を使う以上」なのではなくて「ランダムに分布するので」なんじゃないかな (2007.12.5 トイレで踏んでしまった人) &link(resume writing,http://cvresumewritingservices.org/)