コンシステント・ハッシュ法のメモ

雑記 Web

http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashingとhttp://d.hatena.ne.jp/nishiohirokazu/20090430/1241075459の話。分散ものは書いたことがないのでメモ。

コンシステント・ハッシュ法の前に通常版

単純な分散運用に求められる要件を考えてみる。

  • ノードN個が並列に動作する(READのみやWRITEのみでもOK)。
  • 何らかの手段で「キー→担当ノード」の対応が得られる。

で、単純なハッシュ方式の実装は

  • ハッシュ関数h(x)の結果をNで割った余り「id = h(x) mod N」で割り振る。

となっている。

コンシステント・ハッシュ法の場合

追加要件として

  • ノード数が頻繁に増減する。
    • ノードが減った場合、減ったノードが担当していたキーを他のノードになるべく均等に割り振る。
    • (特に書いていないけど)ノードが増えた場合、増えたノードは他のノードが担当していたキーをなるべく均等に受け取る。

が加わる。「頻繁に」とは「再分配のコストが無視できない」くらいの意味。
で、コンシステント・ハッシュ法では

  • ハッシュ関数h(x)の結果に「何らかの処理」を経て担当ノードを決める。ノード数が増減したら「h(x)→id」の対応を変えればOK。
  • 「h(x)→id」の対応の付け方として"責任範囲"方式がある。乱数(的なもの)で"責任範囲"を決めると統計的バラつきが出る。だから"仮想ノード"で振り分ける。

〆。

  • 仮想ノード用のハッシュ計算"hashFunction.hash(node.toString() + i)"
  • キー用のハッシュ計算"hashFunction.hash(key)"

が混ざっているのがミスリーディングかも(定義域は違う、値域は同じ)。両方とも均等分散するという条件なら、"複製数"とバラつきの関係は計算で求められそう。