分散ストレージの収束する方向

サーバーサイドの分散ストレージについて。広域P2Pとかデータセンター間で同期するとかCDN云々は知らない。

kumofsのアプリケーション-Gateway間のインタフェースは Get(key) だが、Gateway-Server間のインタフェースは実は GetByHash(key, partitioning-id)（とGetByHashIfModified(key, partitioning-id, time)）だったりする。（実際の名前は違うけど意味は同じ）
現状ではpartition-idはkeyにハッシュ関数を掛けて自動生成するが、実際には任意の値を指定できる。
つまり関連するkeyには同じpartitioning-idを指定して同じノードに保存されるようにして、partitioning-idが同じkey同士ならトランザクションできるようにすることも、案外に容易にできる。

Consistent Hashing + double-hash-space はわりと強めに一貫性を保証する。kumofsはレプリケーションが失敗したときにロールバックしないのでdouble-hash-spaceを使っていても不整合が発生し得るが、それはレプリケーションの実装がヘタなだけでアルゴリズム上の問題ではない。

id:kazuhookuさんのPacificとそのはてブがソースだが、ユーザーIDとか何かをキーにしてshardingし、異なるキー間ではトランザクションができなくなるのは許容できるらしい。

Pacificはリゾルバがボトルネックになるが、Consistent Hashing + double-hash-space で分散できるのではないか。データの再配置を悲観的ロックではなく楽観的ロックでやるあたりが問題になりそうか…そこはまだ考えてない。
※2009-06-14追記：データの再分配が起こらなければ問題ないので、最初は小さく始めて動的に増やす（動的な運用）を考えなければ、台数固定で分割してやってもリゾルバは分散できそう。

RDBMSをshardingする方面から歩み寄りと、kvsの分散用のhash値をユーザーが指定可能にする + 同じhash値ならバックエンドDBに任意のクエリを発行可能にするという方面からの歩み寄りで、小さなデータを大量に扱うタイプの分散ストレージは Consistent Hashing + double-hash-space + partitioning-idによる分散 + 確実に実装された再配置 に収束するのかな、と思った。

※2009-06-14 追記：Consistent Hashingは局所性が一切失われる問題があるのと、double-hash-spaceは基本的にManagerノードが必要なのでshardingしないとスケーラビリティに限界がある。偏りを妥協してsorted arrayで分割するとか、一貫性を妥協してEventually Consistentにする実装もあるかもしれない。どの程度のスケーラビリティと台数あたりの効率が必要かに依るか。

大きなデータを扱うタイプの分散ストレージは、ノードが増減したときにデータの移動をしていると遅すぎるので、どのノードにデータが保存されているかというインデックス（メタデータ）と、実際のデータを分離するだろう。データは任意のノードに分散して保存しておけるし、インデックスを引くことで目的のデータに１発で到達できる。

メタデータは小さいデータなのでConsistent Hashingで良い。keyの完全一致以上の方法で検索したければ、非同期にインデックスを作る（インデックスの一貫性は保証しない）のが現実的だと思う。多少遅くなってもスケーラビリティを重視するならSkipGraphか。

1MBくらいまでの大きめのデータを扱うタイプは、通信のホップ数よりいかにキャッシュに乗っているノードを見つけるかが重要になる。クライアントのメモリを共有キャッシュとして使い、データサーバーは目的のデータがキャッシュに載っていなければ共有キャッシュにリダイレクトする、共有キャッシュはMOESIプロトコル（あるいはSIプロトコル?）を使って一貫性を維持するなどの手法がありそう。

もっと大きい巨大データを扱うタイプは、どうせキャッシュに乗らないのでレプリカを増やして対応する。人気コンテンツほどレプリカを増やすなど。

あるいはストレージががやたら速くてネットワークのスループットがボトルネックになるのであれば、共有キャッシュと人気コンテンツほどレプリカを増やす方法の両方を使うだろう。

サーバーサイドの分散ストレージはこのあたりに収束するのではないだろうか。

他の機能…たとえばある条件にマッチするデータが保存されたら通知するとか、ロックとか、階層構造（ディレクトリ）を作ってデータ一覧を出すといった機能は、分散ストレージとは疎結合した別のシステムで実装される気がする。
そのあたりはジョブサーバー使って非同期処理しろとか、ディレクトリなんてアプリケーション側でやればいいという気もしなくはないが。