分散ファイルシステム 設計メモ

現在進行中の分散ファイルシステムの設計ですが、「書き込みの方法」と「ノードの復帰」と「瞬断問題」と「単一ファイルの分散」の設計が固まらない。

まず、書き込みの方法。前提として多重化しているので、複数のノードに同じデータを書かなければならない。


案1は、書き込みを行うとしているノード(Wとする)から、データの多重化に参加しているノード群(D1、D2、D3で3重化しているとする)に対して、同じデータを送るというもの。
単純で分かりやすい。が、D1にデータを送り終わって、D2とD3にデータを送っている途中で、Wが落ちたらどうする?という問題が解決し難い。
それから遅い。書き込み速度は 1Gbps÷多重化度 に制限されてしまい、多重化度が増加するほど書き込みが遅くなる。
これは廃案。


案2は、WからD1へ、D1からD2へ、D2からD3へと数珠繋ぎにデータを転送していく方法。データは受け取りながらどんどん次に回す。現行案。
この方法は、まず速い。W→D1で1Gbps、D1→D2でも1Gbps、D2→D3でも1Gbps出るので(全二重の場合)、多重化度に応じた性能の低下は、 (ネットワークの遅延+ソフトウェアの遅延)×多重化度 だけになる。スイッチが限界に達しない限りスループットは低下しない。現在開発中のコネクションマネージャでは、ネットワークの遅延は1パケット分だけに抑えられる。
それから、障害の検知を同期できる。Wが落ちたらD1が気づく、D1が落ちたらD2が気づく。自分のW側のノードが落ちたときは、データが流れてこなくなるので、自分から先のノードへのデータの転送を中断する。自分のD3の側のノードが落ちたときは、落ちたノードをスキップして転送を再開する(再開と言っても、落ちたノードがどれだけバッファに抱え込んだまま落ちたか分からないので、もう一度最初から送る。そこのところネゴシエーションしても良いが、遅延が発生するので、1度に書き込むデータが巨大(どれくらいかな…)でない限り、全部再送した方が速い。使い分けるのは実装がキツイ)。2台が連続して落ちたときは、2台スキップする。


流れてきたデータを下層のファイルシステムに書き込む方法は3つ。
1つは、もう1つは、流れてくるそばから書き込んでいく方法。そばからと言っても今やHDDよりネットワークの方が速いので、HDDには非同期で書き込んで、データの転送連鎖がブロックしないようにする。writeの進行中にreadが来ると、中途半端にかきこまれたデータがreadされる。省メモリ。実装は普通。
2つ目は、一端全部メモリにため込んで、データの末尾が送られてきた時点で、ファイル(下層のファイルシステム上のファイル)をロックして(flock()ではなく、プロセス内でpthread_mutex)データを書き込む方法。中途半端に書き込まれたデータがreadされることがない…と思いきや、readは複数のノードに分散されるので、データの末尾が伝わる遅延分の間にreadが来ると、中途半端なデータが読み込まれる可能性がある。実装の難しさはそこそこ。
3つ目は、メモリにため込むまでは2つ目と同じだが、実際にファイルに書き込むときに、「書き込み中」フラグを立ててから書き込む。転送連鎖の一番最後のノード(D3)は、データの末尾が回ってきたら、D1からD2に「回り終わりました」と知らせるパケットを送る(このパケットはとても小さいので、1台から複数台に送っても問題はない)。これを受け取ったら、「書き込み中」フラグを解除する。「書き込み中」フラグが立っている間はreadをブロックする。これで中途半端に書き込まれたデータがreadされることが無くなる。ただし、readに遅延が発生するようになる。分散readを最適化すればこの遅延は回避できそう。ブロックしたらD3にリダイレクトするとか。でもリダイレクトする遅延の方が大きそう。
3つ目の実装はかなりキツイ。「フラグ」系はタイムアウトをどうするかも考えないといけない。D3がデータの末尾を受け取った後、「回り終わりました」を送り出す前に落ちたらどうする?送り出しても応答確認の間に落ちたらどうする?


数珠繋ぎでデータを転送していく方法は、他のどのノードが同じ数珠に参加しているかを確実に知っていないと、だれかが落ちたときに「次のノードにスキップする」などの処理ができなくて困る。数珠の玉(ノード)が増えるとき(多重化が増えるとき)、増えている間にきたwriteは確実にブロックしないと不整合が発生する。誰かが減ったときも、減ったことが確実に周知されないと、やっぱり不整合が発生する。ここの実装は具体的にどのように?




続いてノードの復帰方法。具体的には、下層のファイルシステムに既にファイルがある状態のノードがネットワークに参加してきたときにどうするか。
1回ネットワークを全部落として、ということは普通にあるはずで、その後もう一度立ち上げたときに、データに不整合が発生していると困る。というわけで落とさないで欲しい、というのは最後の手段。
今考えている方法は、参加するとき自分の下層ファイルシステム上にあるファイルと同じ名前のファイルが参加した先のネットワークに既にある場合は、そのファイルを全部ダウンロードして上書きするという方法(無かったら追加する)。従来多重化に参加していたノードが復旧してくると、いっぺんにすさまじい量のトラフィックとwriteの遅延が発生する。これはまぁ良いとしても、ネットワークにあったファイルの方が古かった場合は、新しいファイルが上書きされてしまう。こちらは問題。タイムスタンプを比較するしかなさそうだが、タイムスタンプをどこまで信頼して良いのか。
それから、ネットワークでは削除されていても、復旧してきたノードにファイルが残っていると、削除したファイルが復活してしまう。
もう一つの方法は、下層のファイルシステムが空でないときは、エラーで起動しない方法。素晴らしい。



瞬断問題は、負荷が高くなるなどして応答が遅くなったときに、他のノードから落ちていると認識されたが実は生きていた、というときに不整合が発生する問題。
D1とD2は数珠の中にはD1とD2しかいないと思っているが、D3はD3もいると思っている、と言う状態。WからD1、D1からD2にデータが回った後、D2はD3に回さないので、D3は自分がのけ者にされていることに気づけない。D3が落ちたという情報は当然D3には伝えられないので、D3の中には古い数珠キャッシュが残ってしまい、readすると変なデータが読み込まれてしまう。数珠をキャッシュをしなければ良いが、おそらくキャッシュしないと激しく遅くなる。TTLを設定するとしても、TTLの間は古いデータが読み込まれてしまう。ここは妥協か。
同じように、WとD2はD1は落ちていると判断してWはD2からデータを回し始めるが、実はD1は落ちていなかったという場合。D1はのけ者にされていることに気づけない。
もう一つ、D1はD2が落ちたと思ってスキップしてD3に転送を開始したが、実はD2は落ちていなかったという場合。
ややこしすぎて思考が回らない。




あと速度の問題として、W→D1→D2→D3と回すときに、W == D2のときはD1→D2(=W)の転送は無駄だから省きたい。Wは全部データを持っている。特に2台で2重化しているなんて場合には大量に無駄が出る。
一度どんな順番でも連鎖できるようにしようと思ったのだけど、どうにもややこしすぎる。D1で順列化できなくなるので、別の順序で回ってきたデータと書き込み範囲が衝突したときに、どちらを優先するかを数珠の中で統一して決定しないといけない。D1やD3の中だけで衝突するときは解決できそうだが、D2で衝突するときは、同時にD1かD3でも衝突する(2カ所で衝突する)。3カ所で衝突することはないが、2カ所で必ず同じ判断がなされないといけない。1カ所で衝突したときと2カ所で衝突したときで別の対処をするときは、1カ所で衝突したか2カ所で衝突したか判別しないといけない。
順不同を許可するのはやめて、D1→D2のときに、D2側から転送をキャンセルできれば良いかも、と思ったが、キャンセルする遅延の間にデータの転送が完了してしまうような気がした。D1が落ちたときも困る。





さぁ、ワケわからなくなってきました。




まとめる。

  • 書き込み連鎖を順不同にできないか?
    • 2カ所で衝突したとき、どちらを優先するかの判断方法は?
  • 下層のファイルシステムに書き込む方法は?
  • W→D1→D2→D3で、
    • W, D1, D2, D3の中の任意の1台が落ちた場合
    • W, D1, D2, D3の中の任意の2台が同時に落ちた場合
    • W, D1, D2, D3の中でWを含む組み合わせで任意の3台が同時に落ちた場合
    • WはD1が落ちたと思ったが実は落ちていなかった場合(D2はD1が生きていると思っている)
    • D2はD1が落ちたと思ったが実は落ちていなかった場合(WはD1が生きていると思っている)
    • WとD2はD1が落ちたと思ったが実は落ちていなかった場合
  • ノードが復帰してきたときどうするか?


そういえば、ファイル一つがやけに巨大な場合はどうするかを考えていなかった。今は多重化をファイル単位で考えているので、1つのファイルを分割して分散させることができない。負荷が偏るので全体として性能が落ちる。

そう、ハードリンクはどうする?