分散ファイルシステム ハッシュテーブル案

ハッシュテーブルを使う案。(分散ハッシュテーブルではなくて、普通のハッシュテーブル)
今まで考えてきた案とはまったく関係ない。書き込み権などなどは使わない。
分散トランザクションが要らなくなるので、たぶん書き込みが速い。(ちなみにハッシュテーブルを使うことと分散トランザクションが要らなくなることは関係ない)
それからノードが落ちた後の復旧が少し簡潔になる。


基本的にファイルの中は分割しないで、データを持つときはファイルの完全なコピーを持つ。そして書き込みは別のファイルシステム(下層のファイルシステム)に行う。
これなら万が一ファイルシステムがクラッシュしたときでも、人の手でファイルを救出できる。
ただしこのままでは、単一の巨大なファイルはまったく分散されない。これはなんとかする。


ファイルサイズやパーミッションなどのメタデータと、実際のデータは、分けて考えない。全部一括して「データ」。そしてファイルシステムに対する操作をwrite系とread系に分ける。

  • write系
    • write()
    • symlink()
    • chmod()
    • chown()
    • unlink()(削除フラグを書き込む)
    • rmdir()(削除フラグを書き込む)
    • アドバイザリロック(アドバイザリロックフラグを書き込む/アドバイザリロック解除フラグを書き込む)
    • 強制ロック(強制ロックフラグを書き込む/強制ロック解除フラグを書き込む)
    • ノードの追加
    • ノードの離脱
  • read系
    • read()
    • readdir()
    • stat()

これで一気に単純化できた。


それからこのファイルシステムは多重化と負荷分散を目的としているので、あるファイルを持っているノードは複数いる。



続いて本題のハッシュテーブル。
各ノードはNodeID(64bit整数)で識別する。(NodeIDはMACアドレスをハッシュするなどなどして生成)
そして各ファイルはFileID(64bit整数)で識別する。FileIDはパスをハッシュして作る。


write

まずwrite系の処理を考える。

「/hoge/fugaにwriteしたい」(このwriteしようとしているノードをWとする)という場合、"/hoge/fuga"をハッシュ関数にかけて、"/hoge/fuga"のFileIDを得る。次に、このFileIDと数値が一番近いNodeIDを持つノード(Mとする)を探す。(数値が一番近いノードでなくても良くて、FileIDに対して一意にノードが決まればいい)


こうして見つかったノード(M)に対して、「/hoge/fugaを持っているノードのうちで、先頭の1台を教えてくれ」と送る。(この応答はキャッシュする)


教えてくれと送られた方のノード(M)は、/hoge/fugaを持っているノードをすべて知っている。ここで、/hoge/fugaを持っているノードは、D1、D2、D3とする(3重化されている)。先頭はD1なので、D1を教えてやる。


教えてくれと送った方のノード(W)は、教えてくれたノード(D1)に対して、writeしたいデータを送る。(このとき「最初の書き込み」というヘッダを付ける)


データを送られたノード(D1)も、/hoge/fugaを持っているノードをすべて知っている(D1=自分、D2、D3)。(ちなみにD1もD2もD3も/hoge/fugaを持っているノードをすべて知っている)
送られてきたデータを自分に書き込みながら、/hoge/fugaを持っているノードのうち、自分の次のノード(つまりD2)にデータを転送する。(「最初の書き込み」というヘッダは削除する)


D2も、/hoge/fugaを持っているノードをすべて知っている。送られてきたデータを自分に書き込みながら、自分の次のノード(つまりD3)にデータを転送する。


D3も、/hoge/fugaを持っているノードをすべて知っている。D3は/hoge/fugaを持っているノードのうち、最後のノード。まず自分にデータを書き込む。書き込み終わったら、最初のノード(つまりD1)に対して、「全部書き込みできたよ」と送る。


D1は「全部書き込みできたよ」と知らされたので、Wに「/hoge/fuga書き込み完了」と送る。


注意しないといけないのは、2台のノードが同じデータに同時に書き込もうとしたとき。「同時に」と言っても、D1の中で順列になる。データはD1→D2→D3の順に回っていくので、あとからのwriteが前のwriteを追い抜かないようにしないといけない。追い抜いてしまうと、D1/D2/D3が持っているデータが異なってしまう。



以上が正常時の書き込み手順。文で書くとデータを次々に回していく処理が大変そうだけど、実装ではおそらく最後の追い抜かないようにする処理が一番大変。
続いて、書き込み途中にどこかのノードが落ちた場合。




落ちたノードがD1/D2/D3の場合(これを区別できるのは、D1/D2/D3のうちデータが回ってきてきているノード。D1が落ちた場合はWも区別できる)、D1/D2/D3はWに「D?が落ちたぞ!」と教えてやる。落ちたノードがD1の場合、WはMに対して、「D1が落ちたらしいので、次の先頭のノードを教えてくれ」と送り、教えられたノード(D2)にデータを送り直す。D2/D3の場合は、D1/D2が落ちたノードをスキップしてデータを送る。(D1/D2/D3すべてが落ちた場合(D1が落ちているのでWも区別できる)は、データ消失でエラー)


落ちたノードがMの場合(これを区別できるのは、/hoge/fugaが書き込み中であることを知っているノード。つまりWと、D1/D2/D3のうちデータが回ってきているノード)、Wは再度/hoge/fugaのFileIDに一番近いNodeIDを探し、データの送信をやり直す(Mの次のNodeIDを持つノードと、ノード一覧を同期している)。D1/D2/D3のうちデータが回ってきているノードは、データを破棄する。


Wが落ちた場合(これを区別できるのは、D1のみ)、D1はデータの転送の途中でWとの接続が切られることになる。D1は、D2へ転送しているデータのうちで、まだ完了していないものが完了するのを待って、D2との接続を切断する。D2は、D1との接続が切られたので、D3へ転送しているデータのうちで、まだ完了していないものが完了するのを待って、D3との接続を切る。D3は、D2との接続が切られた=Wが落ちた or D2が落ちた なので、とりあえず「/hoge/fuga書き込み完了」を送らなことにする。(落ちたノードがWではなくD2だった場合は、そのうちデータが再送されてくる)



以上でwriteはOK。実はそんなに実装は難しくないような。いろいろなケースがあるけど、個々の対応は結局同じだったりする。
writeの中でもノードの追加と離脱は特殊なので後述。


read

続いてread。

「/hoge/fugaをreadしたい」(このreadしようとしているノードをRとする)という場合、writeのときと同じように"/hoge/fuga"をハッシュ関数にかけて、"/hoge/fuga"のFileIDを得る。そしてFileIDと数値が一番近いNodeIDを持つノード(M)を探す。


RはMに、「/hoge/fugaを持っているノードを全部教えてくれ」と送る。MはD1、D2、D3を教えてやる。(この応答はキャッシュする)
WはD1、D2、D3に、並列して「データをくれ」と送る。D1/D2/D3の中になかなかデータを送り返してこないノードがいる場合は、そのノードとの接続を切断して、別のノードにデータを要求する。
readをしている中に、「そのファイルはもう無い」or「そのファイルxからyバイトへのread()は強制ロックされている」という応答が1つでも帰ってきた場合には、そのファイルは無い or xからyバイトへのread()は強制ロックされていると判断する。


D1/D2/D3が全部同時に落ちた場合は、データロストでエラー。


ノードの追加と離脱

ノードがネットワークに参加するとき、管理データを保持せず(Mにならない)、かつ実際のデータも保持しない(Dxにならない)場合は、何もしない。ネットワーク中のノードの1台でも知っていれば、readやwriteを普通に行える。


管理データを保持する場合(Mになる可能性がある)は、NodeIDを決定する。この参加する新しいノードをNとする。
NodeIDを決定すると、そのNodeIDに一番近いFileIDを持っているノードの一覧を持っていないといけなくなるので、以前までそのFileIDを管理していたノード(Oとする)から、その情報をダウンロードしてくる。続いてOに、「参加しました」と送り、同時に「参加しました」とブロードキャストする。(ブロードキャストは確実に届かなくても良い。もしNのことが伝わらなかったノードがOの方にアクセスしてしまったとしても、Oは確実にNのことを知っているので、リダイレクトできる)


実際のデータを保持する場合は、保持したい旨をwriteする。
writeするとD1、D2、D3と情報が伝わっていく。最後に「書き込み完了」を受け取ったら、D3からデータをダウンロードする。(「書き込み完了」まで待たないと不整合が発生する)
ダウンロードが完了したら、Mに「データを保持した」と伝える。Mは自分の次のNodeIDを持つノードと同期する。