分散ディスク共有

VIVER

一昨日、PMの筧先生がいらっしゃいました。場所も場所で、楽しく今後の展望などなどを聞いていただきました。
というわけで、どんどん開発を進めるわけです。
ここのところ日記をさぼっていたのですが、開発が止まっていたわけではなく。


今作っているのは、分散ディスク共有システム。従来の方式（NBD）はクライアントサーバーモデルで、サーバーが落ちてしまうと全マシンが落ちてしまう。これをディスクイメージを多数のマシンに重複させつつ分散保持させることで、冗長化する。ついでにパフォーマンスも上がると嬉しい。


様相は完全にP2P。ただし１つのサブネット内（ブロードキャストが届く範囲）で使うことが前提で、何万台というネットワークを構成するようなスケーラビリティは必要ない。一方で遅延に対する要求は厳しくなる。

P2Pと言えば、分散ハッシュテーブル（DHT）なる検索手法が流行らしい。非常に高いスケーラビリティが得られるらしい。しかし今回の場合、他のノードがどんなデータを持っているかを１台のノードがすべて知っていることもできるし、ブロードキャストで検索もできる。ということで分散ハッシュテーブルは使わない。
しかし今考えている方法は、DHTのKademliaから少しアイディアをいただいた。Kademliaについてはこの資料が非常に参考になる。
アイディアをいただいたと言っても、ノード間の距離をXORで定めるとか、ツリー構造を作ったりとかはしない。Unstructured P2P。
データを検索した時やされた時に、同時に経路表（Kademliaで言うところのk-buckets、今回の方法では単なるノード<->持っているデータ位置の対応表）を更新するというところだけ。



各ノードは、「IPアドレスと<->そのIPアドレスのノードが持っているデータの範囲」の対応表を持っている。これを「V-Table」などと呼んでみる。データが欲しいときは、V-Tableから目的のデータを持っているノードを検索する。目的のデータを持っているノードが見つからなかったら、ブロードキャストを投げる。

通信はUDPが５種類、TCPが２種類。

NOTIFY_SELF　　（データ範囲）
UDP。自分が（データ範囲）を持っていることを知らせる。
NOTIFY_SELF_DOWN　　（）
UDP。自分が今からダウンすることを知らせる。
NOTIFY_OTHER　　（IPアドレス、データ範囲）
UDP。（IPアドレス）のノードが、（データ範囲）を持っていることを知らせる。
NOTIFY_OTHER_DOWN　　（IPアドレス）
UDP。（IPアドレス）のノードがダウンしたことを知らせる。
FIND　　（データ範囲、データ範囲）
UDP。（データ範囲）を持っているかどうか聞く。このとき自分の持っている（データ範囲）を一緒に送る。FINDを受け取ったノードは、（データ範囲）の一部でも自分が持っている場合、NOTIFY_SELFを送信元ノードに送信する。
GET_DATA　（データ範囲）（データ）
TCP。（データ範囲）を要求し、受け取ったノードは、データすべてを持っている場合は（データ）を返す。ただし一部分でも持っていないデータを要求された場合は、接続を切断する。
JOIN　　（）（イメージ情報、V-Table）
TCP。要求を受け取ったノードは、共有されているイメージの情報（イメージの大きさなど）と、自分が持っているV-Tableを返す。


NOTIFY_*系は１つとカウントしてしまうと、全部で3種類。さらにNOTIFY_*系はV-Tableの精度を上げるためだけにあり、JOINは初期V-Tableを効率よく作成するためだけにある（初期V-Tableはブロードキャストでも作れる）ので、実はFINDとGET_DATAだけでも成り立つ。


ノードがネットワークに参加するときは、ユーザーから指定された初期ノードにJOINを送り、V-Tableを得る（初期ノードが省略された場合は、データ範囲を長大にしたFINDをブロードキャストして、NOTIFY_SELFを待つ）。得られたV-Tableを参照し、「多重化度が最も低いところ」を、保持できる容量まで他のノードからダウンロードする。このとき保持するデータは「連続して」いなければならない（これによって「データ範囲」は開始位置と終了位置（または開始位置と長さ）だけで表せる）。最後に、V-Tableに載っているすべてのノードに対してNOTIFY_SELFを送る。

ネットワークから安全に抜けるときは、V-Tableに載っているすべてのノードに対してNOTIFY_SELF_DOWNを送る。

ネットワークから抜けるとき、突然落ちても良い。また、NOTIFY_*系パケットやFINDを送信するとき、確認応答を待ったりしない。つまり、V-Tableは常に正確であるとは限らず、ある程度正しい。

データが欲しいときは、V-Tableが正確ではないことを考慮して、欲しいデータ範囲を一部分でも持っているすべてのノードに対してFINDを送る。欲しいデータ範囲に対応するノードが存在しない時や、期待できるノード数に比べて実際に一致したノード数が少ないときは、FINDをブロードキャストする。
FINDを受け取ったノードはNOTIFY_SELFを返す。このパケットを受け取った瞬間は、NOTIFY_SELFの送信元ノードが告知通りのデータを持っている可能性が非常に高いので、そのノードに対してGET_DATAで接続して、目的のデータを得る。V-Tableが正確だと判断できたときは、FINDを送らずに直接GET_DATAしても良いかもしれない。（V-Tableの各エントリに「最終更新時刻」を付けるとか）





ノードが数台ダウンすると、データの多重化度に偏りが発生する。偏りがひどいとき（一部は３重化されているのに、一部は１重しかないなど）は、多重化度が高いデータ範囲を持っているノードが、データの持ち替えを行う。実装的には、１回落ちて、もう一回JOINする、という方法でいこうかと。
このとき、多数のノードが同時にデータの持ち替えを行ってしまうと、データが欠損してしまう可能性がある。
そこで、通信を２つ追加する。

KEEP　　（データ範囲、パケットID）
送信先のノードに、（データ範囲）のデータをしばらくの間手放さないで欲しいことを要請する。
KEEP_ACK　　（パケットID）
（パケットID）のKEEPを了解したことを伝える。


データの持ち替えを行うときは、自分と一部分でも重なったデータ範囲を持ったノードにKEEPを送り、KEEP_ACKを待つ。KEEPを受け取ったノードは、KEEP_ACKを返す。ただし、自分もKEEPを送ってKEEP_ACKを待っている状態である場合は、KEEP_ACKを返さない。

KEEP_ACKが持ち替え先のデータ範囲の多重化度よりも一定以上多い数だけ集まったら、データの持ち替えを行う。一定時間内にKEEP_ACKが集まらなかったら、一定の確率で諦める。諦めた場合は、「KEEP_ACK待ち受け中フラグ」をOFFにして、自分にKEEPが送られたときと同じ状態に移行する。諦めない場合は、もう一回KEEPを送る。

KEEPが有効な「しばらくの間」はどのくらいかとか、「一定以上」がどのくらいかとか、「一定の確率」がどのくらいかとかは、まだ考えていない。




設計は以上。後は実装。