先日、 Rendezvous Hashingというアルゴリズムを小耳に挟んだ。少し興味をひかれ、軽く調べつつ実装してみたので、その感想。
※ 思いついたことをテキトウに書いているだけであり、間違っている情報を含んでいる可能性もあるので注意
RendezvousHashingアルゴリズム
実装の参考にしたのはWikipediaの記事（ちゃんと知りたい人はリンク先を参照のこと）。Highest random weight (HRW) hashingとも呼ばれるらしい。
目的
いわゆる分散ハッシュテーブル問題を解くためのアルゴリズムの一つ。
例えば「あるオブジェクトOを冗長度kで保存したい」として、そのために「格納先として、n個のサーバ群の中からk個を選択する」といったことを、各クライアントが独立して（ローカルな計算のみで）、かつ、一貫性を維持した形（i.e., クライアント間で選択結果に差がでない）で行えるようになっている。ただし、後者に関しては対象サーバ集合に変更(追加・削除)があった場合には、それが収束するまでの間は(各クライアントが認識している現在のサーバ集合に応じて)若干のズレは生じ得る。
それ以外に、多数のオブジェクト群を保存する際に、負荷が全てのサーバ群に均等に分散することや、サーバの追加・削除時の影響を最小限にすること（e.g., 一台のサーバ削除に伴って再配置されるオブジェクト数は、全体の1/n程度であるべき）、等も目的。
Consistent Hashingを知っている人であれば、目的自体はそれとほぼ同様、と思って貰って問題はないと思う。
アルゴリズム
基本的なアルゴリズム自体は凄く簡単 で、以下のようなもの:
- クライアントは、各サーバに対して、そのIDと対象オブジェクトのIDを組み合わせたハッシュ値を計算する （e.g.,
md5("${オブジェクトID}_${サーバID}")） - 計算されたハッシュ値が高い順に、サーバ一覧をソートする
- 先頭から順(i.e., ハッシュ値の降順)に、k個のサーバを選択する
全てのクライアントが同じハッシュ関数(とサーバ集合)を用いることで、結果の一貫性は維持されるし、ハッシュ関数の偏りが十分に小さいなら負荷も全てのサーバにほぼ均等に分散にすることになる。また、あるサーバが追加・削除されたとしても、既存のサーバ群に関しては、ハッシュ値が変ることはないので、変更分以外の順序は維持され、影響は最小限。
Consistent Hashing との類似性とか
Wikipediaの記事内でも「Comparison with consistent hashing」という節がある（あまり良く読んではいない…）けど、Rendezvous HashingとConsistent Hashingはだいぶ似ている、という印象を受けた。
Consistent Hashing
Consistent Hashingでは、サーバ群のハッシュ値を（何らかのハッシュ関数を用いて）あらかじめ計算しておき、それを仮想的なリング状のハッシュ空間に配置する。そして、あるオブジェクトの配置先サーバを選択する際には、オブジェクト（のID）のハッシュ値を同様に計算し、その値に対応する位置から開始して、時計回りにリングを辿り、最初に到達したk個のサーバを対象として選択することになる。
ただ、これだけだと「最初に計算したサーバ群のハッシュ値によっては、各サーバのリング上の担当範囲が偏ってしまう可能性がある（綺麗にn等分されるようなハッシュ値になる保証は無いし、たいていはそうはならない）」とか「あるサーバが削除された時に、リング上の次の位置にいるサーバがその分を全部負担することになる（総数としては1/n個のオブジェクトの移動しか発生しないことは変わらないが、できれば残っている各サーバに分散したい)」といった問題がある。
そのため、実用上は各サーバに対してハッシュ値を一つだけ計算するのではなく、例えば "${サーバID}_${1からmまでの通し番号}" といった形でm個の異なるハッシュ値群を計算しリング上に配置する、といった手法をよく見かけるように思う（その際のリング上の各ハッシュ値は 仮想ノード と呼称されることが多い）。
この m の数を多くすればするほど、サーバ群の分散度合い(?)が高まり、負荷分散や割り当ての均等性、といった観点では良好な性質を示すようになるが、反面、「リング構築時や変更時の処理量が多くなる」とか「メモリ消費量が増える」といったデメリットもある。
Rendezvous HashingとConsistent Hashingの類似性
Consistent Hashingにおいて、仮に「仮想ノードを十分に沢山の数だけ生成した」と仮定するなら、両者の違いは本質的には「最初にリングを構築する（Consistent Hashing）」か、それとも「要求に応じて都度構築するか（Rendezvous Hashing）」なのではないかと感じた。
Rendezvous Hashingは「オブジェクト自体のハッシュ値は０に固定で、逆時計回りに辿る」と考えれば、サーバ群のハッシュ値がリング上に配置されている、と見ることができそう。つまり探索開始位置は固定で、ノード群を都度配置。
逆にConsistent Hashingは、ノード群の配置は固定だけど、探索開始位置が（オブジェクト毎に）可変。
両者のメリット・デメリット
Consistent Hashingでは、事前にリングを構築しておく必要があるので、（構築時の計算時間やリングのメモリ使用量の関係上）実際的には個数が(例えば一つのサーバ辺り数百個程度とかに？)制限されてしまい、Rendezvous Hashingの方が使用しているハッシュ関数の理論値に近いオブジェクト群の分散具合ができそう（不確か）。
また、当然Rendezvous Hashingの方が使用メモリも少なくて済む（サーバ一覧と使用するハッシュ関数のみを覚えていれば良い）。Consistent Hashingでは、リングをソート済み配列で表現したとしてハッシュ値のサイズ(バイト幅) * サーバ数 * 一つ辺りの仮想ノード数 程度の領域が必要になる。
反面、Rendezvous Hashingは、オブジェクトに対応するサーバ群を取得しようとした場合には、サーバ数 n に比例した処理量が必要になる、というデメリットがある。具体的には、全てのサーバに対してハッシュ値の計算が必要（ i.e., O(n)）であり、かつ、 それらを順序付ける（ソートする）ために O(n log n)のステップが必要となる（選択数が１で良いならソートは不要）。
サーバ数が多くなってくると、この処理コストも無視できなくなってくると思うが、Wikipediaの記事では、その場合には階層構造を導入すれば O(log n) にオーダーが下げられる（”Skeleton-based variant for very large n”）、との言及はあった（Rendezvous Hashingのメリットの一つであるシンプルさを若干損なうことになりそうなのは少し気になるけど有用ではある）。
逆に、Consistent Hashingの場合には、あるオブジェクトに対応するサーバ群を決定する際には、ハッシュ関数の計算は一度だけ行えば良い。後はそれをキーとしてリング（を表現してソート済み配列）を二分探索すれば、対象サーバ群（を見つけるための探索開始地点）が得られる。
また、リングの二分探索にしても「仮想ノード群がリング上にほぼ一様に分布している」と仮定すれば、（リングの中央からではなく）オブジェクトのハッシュ値をヒントにして二分探索の開始位置を決定する（e.g., hash_ring_staic.erl）ことで、実際に必要な比較回数を削減することができる。
つまり、Consistent Hashingであれば、サーバ総数に依存せずに「一回のハッシュ計算」と「少数のハッシュ値比較および配列アクセス」で、対象サーバを決定できるので、処理量的には優れている（ただし、複数サーバを選択する際には、集合的なデータ構造を使って、仮想ノードの重複を検知・除去する必要はある）。
結論としては、極端に言ってしまえば「メモリ使用量を取るならRendezvous Hashing」で、「計算量を取るならConsistent Hashing」といった感想（前者には、その他に実装のシンプルさや分散度合いがより高そう、といった長所もあるように思うけど、そこまで重要な違いである気はしない）。後は、サーバの構成変更が頻繁にある場合にもRendezvous Hashingの方が良いかもしれない。
その他
サーバのキャパシティを考慮したい場合
「サーバAが、サーバBの二倍のキャパシティを備えているなら、オブジェクトもAの方に倍多く割り当たるようにしたい」といった話。
Consistnt Hashingなら、キャパシティに応じて各サーバで生成する仮想ノード数を調整すれば実現可能（i.e., Aには、Bより二倍多い仮想ノードを生成する）。
Rendezvous Hashingでは、サーバのハッシュ値を決定する際にキャパシティに比例した数だけ多く試行し、その中の最大値を選択すれば良い。
# 例
max([hash("${オブジェクトID}_${サーバID}_${i}") || i <- 0..capacity]この方法は簡単で良いけど、当然キャパシティ数に応じてハッシュ関数の計算数も増えてしまう。
例えば「サーバAのキャパシティは1,000、サーバBは830、サーバCは1,005、…」といった細やかな調整を行おうとするとかなり重くなってしまう可能性があるのが悩ましいので、キャパシティを反映するためのもっと良い方法が何かないものか、とは思う（例えばキャパシティに応じて、サーバのハッシュ値に重み付けしたり、バイアスをかけたりすることで）。
最後に
今まではこういった用途ではConsistent Hashing一択だったけど、Rendezvous Hashingもいろいろと良さそうな特徴を持っていそうなので、必要に応じて使い分けたり試してみたりしていきたい。
キャパシティを考慮する場合に関してだけ(?)は、もっと良い方法がありそうな気もするので、いつか調べてみたいかもしれない。
追記: 2017–05–17
各サーバのキャパシティを考慮した効率的(i.e., o(n) )な割当に関しては「Weighted Distributed Hash Tables」が参考になる (rendezvous_hash-v0.2.0でも対応済み)。
