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

March 29, 2021

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

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

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

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

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

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