作る
研究レベルでは「構造化オーバーレイ」という「次世代なP2P技術」が最先端のようですが、どうやらインターネットで使うようにフォーカスされていて、すさまじいスケーラビリティを実現する！というような話で、LANで使うには逆にオーバーヘッドが大きすぎるのではないかと思います。
「Xを膨大な数のノードの中から発見するにのに、nホップで発見できる！」と言うより、「ノードの数はせいぜい100台か200台くらいでないと困りますが、いつも1ホップです」でないといけないと思うわけです。つまりは研究レベルでもLANに特化した（NFSを置き換える）分散ファイルシステムの話は無いんじゃないかということです。
それから、実装を考えるとどうしても何語で作るかという問題が出てくるわけですが、C++が良いのではないかな、と思っています。まぁ主な理由は私がC++（とRuby）くらいしかできないからで、後はCよりC++の方が生産性が良いとか、性能が出るとか。STLを使って全力で手を抜くとか。生産性から言うとRubyが最高に良いのですが、Rubyでファイルシステムを作るというのは、性能面でちょっとキツイかなと…。Javaは？と言うと、Javaは使えないので分からないです！
それからカーネルモードではデバッグがやってられないので、FUSEを使うことになるはずです。（今時のFUSEだと、FreeBSDでもMacでも使えてクロスプラットフォーム！というオマケが）
さて、スケールして冗長性のある分散ファイルシステムを作る上で困るのは、主に3点。（逆に言えば、この3つを解決できればできると言うこと）
1つ目は、スケールアウトするために、ファイルをいろいろなノードに分散させないといけないが、ファイルが分散してしまうと見つけ出すのが大変という点。
2つ目は、冗長化するために、同じデータを複数のノードに持たせないといけないが、そのデータを書き換えても、その複数のノードはいつも同じデータを持っていないといけない点。たとえ書き込み中にノードが落ちたときでも。
3つ目は、分散ファイルシステム全般に言えることですが、ファイルシステムの整合性が常に保たれること。「ファイルAを消す」という操作と、「ファイルAを書き換る」という操作が同時に起こったときに、あるノードは「ファイルAは消されているよ」と思っているけれど、別のノードは「まだファイルAはあるよ」と思っていてはいけない。
「案１」と「案２」は前に日記で書いたのですが、いろいろ足りないので案3です。
基本的なアイディアは、どのノードがどの部分のデータを持っているかという情報は「プライマリノード」が一括して持っていて、データをいろいろなノードに分散させたり、重複させたり、ロックしたりという仕事はプライマリノードが行う。プライマリノードは「セカンダリノード」と常に情報を同期していて、プライマリノードが落ちると自動的にセカンダリノードがプライマリノードに昇格して、さらに次のセカンダリノードを選出する。
さらに、これだとプライマリノードに負荷が集中してしまうので、ネットワークを複数のグループに分けて、それぞれのグループにプライマリノードとセカンダリノードを置く。グループ分けと言っても、ノードの台数分にグループ分けする。つまり、すべてのノードがプライマリノード。
データが分散されていて、かつ少しずつ重複しているので、読み込みは複数のノードに並列して要求できる。よってノードが増えると速くなる。書き込みは整合性を保たないといけないので速くはならないものの、一カ所に負荷が集中しないので、遅くもならない。（データの整合性を保証するのはプライマリノードではなく、実際にデータを書き込むノード。書き込むデータを一度プライマリノードに送ったりはしない）
プライマリノードとして持つ情報を、ファイル-ノードテーブルと言うことで、FN-Tableと呼ぶことにしてみる。
FN-Tableは、ファイル名をキーとした、ハッシュテーブル。ファイル名をハッシュにかけたものを、FSUID（ファイルシステムの中で一意のID）と呼ぶことにする。
値は、「ファイルのタイプ」（ファイル、ディレクトリ、シンボリックリンク、ハードリンク、スペシャルデバイス、名前付きパイプ）と、「ファイルのサイズ（ファイルの場合）」、「メタデータ」（パーミッション、アクセス日時などなど）、「今書き込み権を持っているノードのIPアドレス」と、「そのデータの断片を保持しているノードの一覧」。
「書き込み権」というのは、このファイルのメタデータ（データではない）を変更する権利。ファイルシステムの整合性を保つためのもの。パーミッションとは関係ない。ファイルを書き換えるときは、この権利をプライマリノードから取得しないといけない。一度取得したら、他のノードから要求があるまで解放しなくても良くて、連続して同じノードが書き換えるときはオーバーヘッド無し。
FSUIDは64bit整数が良いと思う。単純にSGI C++ STLのhash_map::size_typeが64bit整数だからという理由。検索や追加はO(1)なので、ファイル数が増えてもスケールする。
「範囲」というのは、開始位置（64bit整数）と長さ（32bit整数）のペア。範囲をたくさん扱う場合は、開始位置をキーとしたツリー構造（std::map）で扱う。（2分検索できる）
- FSUID: uint64_t
タイプ: ファイル
書き込み権を持つノード: IPアドレス
データ保持ノード一覧:
- 持っているデータの 範囲: [uint64_t, uint64_t]
ノードのアドレス: [IPアドレス, ポート番号]
- 持っているデータの 範囲: [uint64_t, uint64_t]
ノードのアドレス: [IPアドレス, ポート番号]
- ...
部分書き込み権保持ノード一覧:
- 範囲: [IPアドレス, 書き込みロックの有無]
- 範囲: [IPアドレス, 書き込みロックの有無]
- …
- FSUID: uint64_t
タイプ: ディレクトリ
書き込み権を持つノード: IPアドレス
ファイル一覧:
- ファイル名: 文字列
タイプ: ファイル|ディレクトリ|キャラクタデバイス|…
ファイルサイズ: uint64_t
パーミッション: [所有者, グループ, アクセス権]
更新日時: …
…
- …
- FSUID: uint64_t
タイプ: ハードリンク
書き込み権を持つノード: IPアドレス
リンク先のファイル: FSUID
（これだけではシンボリックリンク。どうしよう。リンク先のエントリに「ハードリンク元」を持たせる？）
- FSUID: uint64_t
タイプ: キャラクタデバイス
…
- …ファイルの「部分書き込み権」というのは、データ（メタデータではない）の整合性を保つためのもの。ファイル中の一部を書き換えるには、その部分の「部分書き込み権」を取得しないといけない。これもメタデータの書き込み権と同じように、一度取得したら、他のノードから要求されるまで解放しなくて良い。
「部分書き込み権」には、ロック無しとロック有りの2種類がある。ロック無しの書き込み権を取得したときは、他のノードから「その部分の書き込み権をくれ！」と言われたら、書き込み権をすぐに解放する。ロック有りの場合は、すぐに解放しない。これでflock()の書き込みロック対応できる。読み込みロックは別のところで対応する。
どのプライマリノードがどのファイルを管理するかと言うことは、FSUIDを使って決める。FSUIDが0〜1000はノードA、1001〜1051はノードBという具合。FSUIDはファイル名のハッシュなので、プライマリノードの負荷はある程度均等に分散されるはず。
続いて、すべてのノードが持っているテーブル。自分が保持しているデータの断片を、実際にストレージ（HDD）のどこに書き込んでいるかという情報。ストレージ・テーブルということで、S-Tableと呼んでみる。実はXFSのeXtentとまったく同じアイディア。
S-Tableをメモリに保持するときは、ファイル名（FSUID）をキーとしたハッシュテーブル。B-Treeでも良いかも。（と言うか、hash_map<ファイル名, 値>ではなくC++ STLのstd::map
S-Tableもストレージに書き込まないといけないけど、ストレージのどこに書き込むかを決めていない。先頭1MB？
S-Table（実際のデータをストレージ上の位置にマッピング） - FSUID: uint64_t この断片の、ファイル内での開始位置: uint64_t この断片の、ディスク内での開始位置: uint64_t この断片のサイズ: uint32_t - …
S-Tableの問題は、ディスクの真ん中あたりにあるファイルのサイズを増すと、いわゆる「断片化」が発生すること。XFSはここのところ、頭のいい人による頭のいいアルゴリズムがあるのでしょうが、もっとAdHocな解決方法はないものでしょうか。
…と言うとあって、スパースファイルを使って、管理を全部別のファイルシステムにお任せしてしまう方法。どーんと1PB！なんてスパースファイル（ディスク上では0バイト）を作って、その中にデータを書いていく。データを前から順に書いていく必要がない。
それから、書き込みはトランザクションで行うので、書き込み中か否かをメモリ中に保持する。これをWritePending-Tableということで、P-Tableと呼んでみる。
P-Table（トランザクション管理） - FSUID: uint64_t - 範囲: 書き込み中か否か - … - …
それから、読み込みロックのテーブル。
RL-Table（読み込みロックのテーブル） - FSUID: uint64_t - 範囲: [IPアドレス, 読み込みロックの有無] - … - …
読み込みロックはここで実現する。
ノードが持っている情報は以上。続いて通信プロトコル。
- GetWriteAccess
- TCP。ファイルを書き換えたいときに、そのファイルを管理しているプライマリノードに送信する。送信するデータは、ファイル名と、書き換えたい範囲と、書き込みロックの有無。受信するデータは、そのファイルを構成するデータ断片を持っているノードのリストと、取得した書き込み権の範囲。なぜ書き込み権の範囲を受け取るかというと、プライマリノードは要求された書き込み範囲そのままを取得させるわけではないから。連続して書き込むことが予想されるので、その先の範囲の部分書き込み権（ロック無し）まで一度に取得させる。部分書き込み権は、StripWriteAccessを受け取るまで保持し続けられる。
- StripWriteAccess
- TCP。プライマリノードが、GetWriteAccessで書き込み権を持っていったノードに送信する。送信するデータは、ファイル名と範囲。受信するデータは無し。StripWriteAccessを受け取ったときにデータの書き込み中だったら、書き込み終わった後で（WriteCommitを送った後で）StripWriteAccessに応答する。
- GetDataNodes
- TCP。GetWriteAccessと対応させるならGetReadAccess。ただ読み取りは同時に複数のノード行っても良いので、読み込み権は中央管理しない。GetDataNodesはプライマリノードに送信できる。送信するデータは、ファイル名と範囲。受信するデータは、要求した範囲を構成するデータ断片を持っているノードのリスト。（このリストは複数かもしれない。0〜50まで要求したら、0〜20はAとB、21~50はBとCだったり）
- Write
- TCP。データ断片を持っているノードに送信できる。送信するデータは、ファイル名、ファイルのシーク位置、長さ、データ。受信するデータは、エラーか成功か。ここで、Writeを受け取ったノードは、この時点ではデータを書き込まないで、書き込もうとしているファイルにWritePendingフラグをセットする。
- WriteCommit
- TCP。データ断片を持っているノードに送信できる。Writeを送ったノード群すべてから成功が帰ってきたら、そのノード群すべてに送る（分散トランザクション）。送信するデータはファイル名と範囲。受信するデータは無し。WriteCommitを受信したノードは、実際にデータの書き込み反映させ、WritePendingフラグを解除する。
- ReadLock
- TCP。読み込みロックを取得するために、データ断片を持っているノードに送る。送信するデータは、ファイル名と範囲。受信するデータは成功か否か。
- Read
- TCP。データ断片を持っているノードに送信できる。送信するデータは、ファイル名、ファイルのシーク位置、長さ。受信するデータは、要求したデータ。WritePendingフラグがセットされているときでも、構わず読み込む。（「同期要求モード」を後述）
- Discovery
- UDP。ノードを見つけるために使う。
- DiscoveryACK
- UDP。Discoveryを受け取ったら、Discoveryを送信してきたノードに送る。自分が管理しているFSUIDの範囲を載せる。
- SecondaryEntry
- TCP。Discoveryでプライマリノードを見つけて、そのプライマリノードのセカンダリノードになろうと思ったら、そのプライマリノードに送る。「セカンダリなら足りている」とそっけなく返答されるか、またはそのプライマリノードが記録している書き込み権限情報のコピーをもらう。プライマリノードはこのコピーを行っている間は、データが書き換わる要求を遅延させる。
- SyncPush
- TCP。GetWriteAccessを受け取ったプライマリノードが、データを同期するために、セカンダリノードに送る。プライマリノードは、GetWriteAccessを受け取ったとき、まずその時点で部分書き込み権を持っているノードにStripWriteAccessを送って、部分書き込み権を取り戻す（ロック付きの書き込み権だった場合は、GetWriteAccessを送ってきたノードに「ロックされているよ」と応答する）。続いてどのノードが部分書き込み権を持っていったかを記録し、その記録をSyncPushでセカンダリノードにもコピーする。SyncPushが成功したら、GetWriteAccessに応答する。
- JoinDataFragment
- TCP。自分が「あのファイルのこの部分を保持したい！」と思ったら、そのファイルの書き込み権を管理しているプライマリノードに送る。このプロトコルでは、まずGetWriteAccessと同じ手順を踏んで、部分書き込み権を得る。そしてReadを使って既に他のノードからデータ断片をもらってくる（このときこのデータ断片にWritePendingフラグがセットされていることはあり得ない）。Readが成功したら、プライマリに「このデータ保持をしているのでよろしく」と送る。
- TransferPrimary
- TCP。ノードが追加されたときに、プライマリノードの仕事を分けてもらうために、追加されたノードがプライマリノードに送る。送信するデータは、FSUIDの範囲。受信するデータは、要求したファイル群の書き込み権情報と、そのセカンダリノードのIPアドレス、そして実際のメタデータ。TransferPrimaryを受け取って仕事を分担した後、自分が管理しなくなったFSUIDに関する要求を受け取ったときは、リダイレクトさせる。
- PendingReset
- TCP。書き込み権限を持っているノードがダウンしたことをプライマリノードが検知したとき、データ断片を持っているノードに送る。送信するデータは、ファイル名。データ断片を持っているノードは、指定されたファイルにWritePendingフラグがセットされていたら、書き込もうとしていたデータを捨てて、WritePendingフラグを解除し、プライマリノードに「解除できたよ」と応答する。プライマリノードは書き込み権限を自分にセットする。
…おそらく足りないプロトコルがまだたくさん。
非同期IOについて。非同期IOモードのときは、データをすぐに書き込まないで、バッファに書き込む。実際に書き込むのは、StripWriteAccessを受け取ったとき。これだとReadのときにいつも古いデータしか読み込めない。そこで非同期IOモードで、かつ同期要求モードのときは、Readの前にGetWriteAccessを使ってバッファをフラッシュさせる。
非同期IOだと信頼性が落ちるので、基本は同期モード。
ノードの追加手順は、まず新しいノードは、Discoveryをブロードキャストして、すべてのノードを発見する（この方法はたぶんあまり良くない。要他の方法）。続いて自分が管理したいFSUIDの範囲を決める。決める方法は、「大変そうなノードを負荷を軽減させる方向」で。詳しくは未定。決めたら、そのFSUIDの範囲をその時点で管理しているノードに、TransferPrimaryを送る。
ノードが落ちたときは、まず誰かが検知する。検知したら、全員に知らせる。落ちたノードが持っていたデータ断片を含むファイルを管理しているプライマリノードが、データ保持ノードリストから落ちたノードを削除する。それから、自分の読み込みロックテーブルをチェックして、そのノードが読み込みロックを保持しているエントリがあったら、その読み込みロックを解除する。そのノードが書き込み権を保持していた場合は、書き込み権を復旧する（同時に書き込みロックを解除する）。そのノードがWriteを行っているWritePending状態のデータ断片があれば、ロールバックする。
問題はたくさん。
