論文メモ The Design and Implementation of a Log-Structured File System

March 29, 2021

91年に提唱されたLog-structured file system(LFS)は、バッファリングした変更を、ディスクの連続領域に一度に書き込むことで、小さなファイルの大量の書き込みを高速に処理できる。 また、クラッシュ時のリカバリも、チェックポイント以降に追記された箇所だけを検査すればよく、ディスク全体を参照する必要がないので、高速になる。

ディスクに書き込む新しい情報をログとよぶ。 連続領域にログを追記する場合、ファイルシステムの構造をログから再構成し、また、シークなしでログを書き込める十分な連続領域を確保しなければらならない。

LFSは、Unix File Systemと同様、inodeでファイルシステムを管理する。 inodeには、ファイルのタイプ、所有者、アクセス許可、ファイルの先頭10ブロックのアドレスが含まれる。 10ブロック以上のファイルのinodeであれば、さらに、間接ブロックのアドレスも含まれる。 LFSのinodeは、ファイル同様にログとして書き込まれるため、Unix File Systemのようにディスクの固定領域にあるとは限らない。 変化するinodeの位置を記憶するために、データ構造inode mapでinodeの位置を管理する。 inode map自体も数ブロックに分割されてログに書き込まれるが、inode mapのアドレスは、固定位置にあるチェックポイント領域から特定できる。

空いた連続領域を確保するために、ディスクを固定長のsegmentに分割して管理する。 segment内部の書き込みは常に逐次的であり、削除や上書きで内部が断片化されていれば、書き込み前に必要なデータを移動し、これから書き込むログのための連続領域を確保する。

segmentの内部が逐次的に書き込まれる一方で、segmentは必ずしも隣接する順番に書き込まれるとは限らない。 一定期間よりも長く変更のないデータは、何度も移動させなくてすむように、一箇所に集約される。 ログを書き込む先の連続領域に、この集約されたデータがあれば、データのあるsegmentをスキップし、その先のsegmentにログを書き込む。

論文をこちらからダウンロードできます。