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

コネクション

  • 全部TCP
  • パッシブコネクションとアクティブコネクション
    • こちらからリクエストを投げるときはアクティブコネクションを使う
    • パッシブコネクションは待ち受け専用
    • 通信の衝突が起きないのでスケーラビリティが良くなる
  • コネクションは贅沢に張る方針
    • epoll/kqueueが前提。コネクションを張り直すのに必要な遅延の方が問題
  • 通信にエラーが起きたら、即座にコネクションを切断する
    • エラー通知はコネクションの切断で行う
      • ムダなパケットが流れないで済む
      • 送信時に返答を待たずにデータを送信できるので、１ホップ短縮できる
    • 別のコネクションを使って通信を再開する
      • ただしステートレス。途中から再開することは考えない
  • 暇なときにコネクションを張り増す
    • 暇なときの判断がそもそも困難なので、新たにコネクションを張るときに一気に複数張ることにする
      • コネクションを張り終わるまで待たないといけない＝暇

JOIN

  • 引数
    • 待ち受けるIPアドレス
    • ストレージパス
    • ブートストラップIP
  • ストレージパスを操作、ファイル名をすべてハッシュ関数に掛けてキャッシュ
  • 自分のノードIDを決定する
  • ソケットをlisten
  • ブートストラップIPに接続（GET_NODE_LIST）
    • ノード一覧を取得
  • 自分の次のノードIDを持つノードに接続（JOIN）
    • ノード一覧を取得・マージ
  • 自分の次のノードIDを持つが変わったら（変わったかどうかはサーバー側が判断する）、再度自分の次のノードIDを持つノードに接続（JOIN）
    • ノード一覧を取得・マージを繰り返す
  • 自分の次のノードを持つノードから管理ID範囲をダウンロード（JOIN）
    • サーバー側が、次のノードIDが変わっていないと判断したら、ノード一覧の代わりに管理ID範囲を分割して送信する
      • これで複数のノードが同時に起動しても大丈夫なはず
  • （すべてのノードにコネクションを張り、ノードが追加されたことを知らせる）
  • （ブロードキャストでテキトーに知らせる）
  • イベントループ開始
  • 緊急に冗長化が必要なファイル連鎖に参加する

ファイル連鎖への参加

ファイル連鎖＝１つのファイルを冗長保持しているグループ。一方向リスト状に繋がっている。

  • ファイル名をハッシュ関数に掛ける→ファイルID
  • （ファイルIDキャッシュテーブルを参照し、キャッシュ済みなら直にストレージノードに接続する）
  • （キャッシュされていなかったら、）ファイルIDとノードIDテーブルを照らし合わせ、ファイルIDに最も近い次のノードIDに接続
    • このノードがそのファイルの管理ノード
    • 接続に失敗した場合は、その前のノードに接続
      • そのノードはファイル管理ノードの冗長化ノード
    • 管理ノードから、そのファイルのファイル連鎖の先頭のストレージノードを聞き出す
  • ストレージノードに接続する
  • ファイル名と参加する旨を書き込む
  • 最後のノードから書き込み完了通知を受け取ったら、書き込み完了通知を受け取ったノードからファイルをダウンロードする
  • 参加完了

読み込みイベント

  • パッシブコネクションでファイル名とコマンドを受け取る
  • ストレージテーブルを参照する
    • 自分が保持しているファイルの場合
      • ストレージにIOを行って結果を返す
    • 自分が保持しているファイルではない場合
      • ヘッダを送信する
      • コネクションを切断する必要はない。パッシブコネクションはこちらから切断する必要はない
      • 読み込み側は大きなバッファサイズでヘッダとデータを一気に、ヘッダしか読み込めなくても問題はない
      • libpioにread_at_least()が必要

書き込みイベント

  • パッシブコネクションでファイル名とコマンドとデータを受け取る
    • データの受け取りは非同期
  • ストレージテーブルを参照する
    • 自分が保持しているファイルで、自分がファイル連鎖の先頭ノードの場合
      • データを非同期にバッファにコピーしていく
      • ファイル連鎖の中で自分の次のノードに接続する
      • 接続できなかったら、回復処理。ノードを一つスキップして次のノードに接続する。そのノードには間を一つ飛ばした旨を別のコネクションで知らせる（知らせ終わるまで、スキップした先のノードへの接続は遅延させる）
      • 自分の次のノードに、データを非同期に転送する
      • すべて転送し終わったら、ストレージに非同期に書き込む
      • すべて書き込み終わったら、バッファをメモリプールに戻す
    • 自分が保持しているファイルだが、自分がファイル連鎖の先頭ノードではない場合
      • 先頭ノードをヘッダに入れて返し、コネクションを切断する
      • 自分は先頭ノードを必ず知っている
    • 自分が保持しているファイルではない場合
      • ヘッダを返してコネクションを切断する

書き込み連鎖イベント

  • パッシブコネクションでファイル名とコマンドとデータを受け取る
    • データの受け取りは非同期
  • ストレージテーブルを参照する
    • 自分が保持しているファイルで、接続元が自分の前のノードの場合
      • データを非同期にバッファにコピーしていく
      • ファイル連鎖の中で自分の次のノードに接続する
      • 自分の次のノードに、データを非同期に転送する
      • すべて転送し終わったら、ストレージに非同期に書き込む
      • 自分がファイル連鎖の最後のノードだった場合は、ファイルの書き込み元に書き込み完了を通知する
    • それ以外の場合
      • ヘッダを返してコネクションを切断する

問題

  • どのファイル連鎖に参加するかを決めるアルゴリズム
    • イベントが発生するごとにストレージテーブルを参照し、手薄なファイル連鎖に参加する
      • イベントが発生するたびにストレージテーブルを線形で参照すると負荷が大きいので、数秒に１回くらいの確立にしておく
      • タイマー用スレッドを回し、起動直後は短いタイマーで、時間が経つほどタイマーを長くする
      • 時間が経過したら、イベントスレッドと共有しているフラグをロック無しで1にする。sig_atomic_t
      • イベントスレッドはイベントごとにフラグを確認し、1になっていたら0に戻す
    • 自分の管理IDの配下にあるファイル連鎖に優先的に参加する
      • 管理IDの配下にあるファイル連鎖にすべて参加したら、他のファイル連鎖にも参加する
      • 管理IDが分割されて、管理IDの配下にあるファイル連鎖で参加できていないものがあったら、管理外のファイル連鎖から離脱する
      • 読み込みを行うとき、管理IDの配下にあるファイルは保持しているだろうと勝手に判断し、確認無しで直接readを仕掛ける
      • 実は↑これは常に使える？持っていなければ返答ヘッダでリダイレクトすれば良い。ゼロホップでreadできる利点は大きい
  • ファイル連鎖の偏りを補正するアルゴリズム
    • 新しいファイルが作成されると、ストレージの空き容量がノードによって偏る
    • どうやってその偏りを検知・補正する？
  • 参加するファイル連鎖を最適化するアルゴリズム
    • 自分でアクセスすることが多いファイルは、手元に置いておくと高速になる可能性がある（キャッシュされている場合はそうでもない）
    • ファイルごとにアクセスされるたびにカウントアップされる変数を付け、オーバーフローしたらそのファイル連鎖に参加する
  • どのノードに読みに行くかを決めるアルゴリズム
  • 新しいファイルをどのノードに書き込むか
    • 管理ノード？
    • 書き込み先のストレージ容量が足りなかった場合は？
  • ファイル名を全部ハッシュ関数に掛けてキャッシュしておくツライ？
    • ファイル名をキーにしたキャッシュテーブルを参照する処理の方が、ハッシュ関数より重い可能性が大いにあり得る
  • ファイルのデータ自体のキャッシュ（ローカルでのキャッシュ）はどうするか
  • open()したファイルディスクリプタをすぐクローズせずにキャッシュするか否か
    • ファイル名をキーとしたテーブルを参照する処理の方が重いか…
    • テーブルが大きくなったら、使われていないものからクローズすればいい
    • プライオリティキュー＋連想配列