Webサーバクラスタの空間的局所性について。
ノードのキャッシュを効率よく使うには、GET /hoge.gifは常にノードA、GET /foo.jpgは常にノードB、という具合にリクエストを配分する必要がある。全ノードがhoge.gifとfoo.jpgのキャッシュを持つのは無駄だ。ラウンドロビンやランダムロビンでリクエストを配分すると、この無駄が生じる。
では、ノードAがhoge.gifをキャッシュしていることを、どうやって知ればいいだろう。
知る必要はない。「hoge.gifならノードA」と決まってさえいればいい。
クラスタが最初にGET /hoge.gifのリクエストを受け取ったときには、どのノードもhoge.gifをキャッシュしていない。どれでもいい、だからノードAでもいい。
二度目以降はノードAでなければならないが、「hoge.gifならノードA」という関係は変わらない。
というわけで、「hoge.gifならノードA」と決まってさえいればいい。だから、任意のリクエストの配分先を決める関数は、ごく単純なものになる。ただのハッシュ関数だ。現実には、リクエストの集中する一部のリソースを複数ノードでキャッシュしたり、ノードの脱落・追加を処理したりする必要があるが、すべてハッシュ関数をいじるだけで実現できる。
（最近の研究で流行のヘテロジニアスな話やP2Pの話はすべて無視する。アブストラクト中に「heterogeneous」「adaptive」「network transparent」のどれかが出てくる論文を読むのは時間の無駄だってばっちゃが言ってた。でも書くといいことがあるらしい）
リクエストの配分先を決めるディストリビュータはどうすればいいか。クラスタの全ノードに、DNSラウンドロビンでばらまけばいい。各ノードがディストリビュータにもなり、「hoge.gifならノードA」でリクエストを配分する。
ここの研究では、「hoge.gifならノードA」の単純さをどういうわけか採用していないが、だいたい似たようなことをやっている。
以上の議論は、Webサーバクラスタに限らず、次の条件を備えたサーバクラスタすべてにあてはまる。
・ノードのメモリに乗り切らない大きさのデータセットを扱う
・個々のリクエストを処理するうえで必要なデータに空間的局所性がある
・リクエストを処理する前に、その処理に必要なデータ範囲との対応をつけられる（不完全でもいい）
この条件にはかなり一般性がある。RPCの宛先をハッシュ関数で選ぶ機能がついたクラスタ用フレームワークが、どこかにありそうなものだ。
そういうクラスタ用フレームワーク（Java用）を探して、10時間以上ぐぐったが、まだ見つからない。みんな「network transparent」で論文を書くのに忙しいらしい。