読者です 読者をやめる 読者になる 読者になる

分散ディスク共有

VIVER

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


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


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

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



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

通信はUDPが5種類、TCPが2種類。

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_*系は1つとカウントしてしまうと、全部で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の各エントリに「最終更新時刻」を付けるとか)





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

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が有効な「しばらくの間」はどのくらいかとか、「一定以上」がどのくらいかとか、「一定の確率」がどのくらいかとかは、まだ考えていない。




設計は以上。後は実装。