先日の続き。
こんな状況を想定しよう。hoge.gifのリクエストが集中しているので、負荷分散のため、ノードBもhoge.gifをキャッシュすることになった。さて、ノードBがhoge.gifを取得しようとしたとき、どこから持ってくるのが一番速いか？
ノードAから、が一番速い。なにしろメモリ上にキャッシュしている。
ノードAだけがhoge.gifをHDDから読み込むのなら、他のノードがHDDからhoge.gifを読み込めても意味がない。
というわけで、hoge.gifが書き込まれたHDDは、ノードAのローカルHDDだけでいい。ストレージを共有する必要はない。つまり、シェアードナッシングだ。
以上の議論では、リクエスト（GET /hoge.gif）とそれを処理するためのデータ（hoge.gif）が一対一に対応している。このときには、ハッシュ関数の引数は、「GET /hoge.gif」という文字列で十分だろう。
しかし、もう少し中身のある処理をするなら、これほど単純にはいかない。
「GET /bar?user=maria」というリクエストを考えよう。このリクエストを処理するには、mariaというユーザに関するデータが必要だとする。そして、「GET /fuga?user=maria」というリクエストもあるとする。これを処理するにもやはり、mariaというユーザに関するデータが必要だとする。
文字列「GET /bar?user=maria」と「GET /fuga?user=maria」のハッシュ値は異なる。同じ値を返すようにハッシュ関数を作ろうとすれば、それはすでにハッシュ関数とはいえない。ハッシュ関数の引数には、「maria」という文字列を入れなければならない。
というわけで、文字列「maria」は、mariaというユーザに関するデータのありかを示すタグになる。こういうタグのことを仮に、「ノードタグ」と呼ぶことにする。ディストリビュータは、リクエストを受け取ったときに、ノードタグを取り出して配分先を判断する。また、ノードタグを取り出せるようにリクエストを設計する。
リクエストはこれでいいとして、次はデータ構造だ。
ユーザに関するデータのような構造化されたデータは、RDBに格納することが多い。普通のRDBMSは集中型の権化のような代物だが、ここでは特殊なRDBMSを仮想する。このRDBMSでは、CREATE TABLEのときに、ノードタグとして使われるカラムを指定できるようになっているものとする。そして行の粒度で各ノードに分散される。
（この行の粒度、最小の粒度のことを、仮に「レコード」と呼ぶことにする）
maria固有のデータはこれでいい。が、複数のユーザ情報間で共有されるデータもある。たとえばRDBのインデックスだ。それはどこに置くのか？
どこでもいい。「hoge.gifならノードA」式に、とにかく決まってさえいればいい。それを持っているノードはほぼ常にそれをキャッシュしているので、HDDから読み込むよりも速く読み込める（しかも負荷分散もできる）。また、任意のレコードを持っているノードはクラスタ全体に分散しているので、クラスタ全体のメモリがキャッシュとして使えるのに等しい。
ここまで読んできた暇人の読者諸賢の頭には、山のような疑問が浮かんできたことと思う。
1. レコードの粒度が小さすぎてネットワーク遅延が厳しい
2. トランザクション処理は？ キャッシュ無効化は？
3. 冗長性は？ レプリケーションは？
まず1から。
送信側がプリフェッチのようなおせっかいをする必要がある。が、なにを送ればいいかをレコードから調べるのは大変だ（アンマーシャルして参照を掘り出すことになる）。そこでレコードには参照をメタ情報としてつける。おせっかいで送るときは、このメタ情報を見るだけで、なにを送ればいいかがわかる。
（この参照情報はガベージコレクションにも使える）
2。
トランザクションは分散なので2相コミットになる。
キャッシュ無効化には、楽観ロックに似たテクニックを使う。まず、レコードにUUIDをつける。RDBの主キーのようなIDではなく、楽観ロックに使うタイムスタンプのようなIDだ。このUUIDのことを仮にContent IDと呼ぶ。レコードがUPDATEされたときには、無効になったContent IDをマルチキャストで投げる。もちろん、このマルチキャストがIPマルチキャストである必要はないし、まとめて投げるためにしばらく溜めておくこともできる。
（なお、UPDATEされて消えた行内容も削除せずに残しておく。この行内容のことを仮に「サブレコード」と呼ぶことにする。レコードはmutable、サブレコードはimmutableだ）
3。これが本日のハイライトだ。
結論からいうと、ガベージコレクション＝レプリケーションになる。
まず、並列分散ガベージコレクションをマーク・アンド・スイープでやる方法から。
ガベージコレクション（GC）を、レコード単位ではなくサブレコード単位で行う。GC中もシステムは動いているので、1つのレコードに対して複数のサブレコードが存在しうる。この複数のサブレコードのうち、GC開始時以降に存在したサブレコードの参照すべてをたどってマークをつける。GC開始時に存在しなかったサブレコードは、マークがつかなくても削除しない。こうすることで、システム全体を止めることなくマーク・アンド・スイープをかけることができる。
マーク開始→マーク終了判定→スイープ開始→スイープ終了判定、で1回のGCが完了するが、この1サイクルに対して、開始時にID（GC ID）をつける。
データに冗長性を持たせるため、1つのレコードは複数のノードで保存される。このとき、1つのノードが担当になり、あとは副担当になる。どのノードを副担当とするかは、担当ノードと同様に、ハッシュ関数で決める。
クラスタから離脱したノードがあれば、レコードを保存するノードが1つ減る。減ったぶん、別のノードにコピーする必要がある。それをいつやるか。マーク＆スイープの、マークのときだ。
担当ノードがレコードをマークするとき、副担当ノードにもマークするよう指示を出す。副担当ノードがそのレコードを持っていない場合は、担当ノードから取得する。こうして、クラスタからノードが離脱したあとの冗長性が回復される。
スイープのときに、生きているレコードのレプリカを作ることができる。同じGC IDで作られたレプリカ同士はデータに一貫性がある。
以上、DBもNASもL4ロードバランサもなく、全ノードに同じものがインストールされた（管理のラクな）PCクラスタとハブとルータだけですべてが完結するファンタジーワールドの話をした。（現実にはDNSサーバも必要なのだが。P2P DNSが欲しい）
まったく完璧ですな、あとは実装するだけですな、でもこれ全部を実装する日は永遠にこないんでしょうな、と自画自賛しつつこの項終わり。
追記：
よく考えたら、ガベージコレクションはコンカレントに実行できても、レプリケーションはシステム全体を止めないと無理だった。マーク終了からスイープ開始までのあいだに、クラスタ全体で一度、UPDATEを停止する必要がどうしてもある（INSERTは可能）。理論的に不可避な気がするので、たぶん誰かが証明しているだろう。