Local Filesystem Survey
(Export版)
Table of Contents
前置き
- What's this Document
- 公開日：2002年7月 (それ以降の情報については書いてない)
- 主にBSD系のUnix FSsについてまとめて論文を読んで作ったゼミ用資料
- 論文が主なのでそれほど新しい情報はない
- Linux系については詳しくない
(ブロックアルゴリズムなどについては
Linux系の FS の各 variant を調べた方がためになると思う)
- ウソや間違いやobsolete情報が含まれてると思われるため、
個々の詳しい知識はそれらの情報源をあたること
- BSD系FSに関する更新事項については
Wiki上
で多少扱っている。
しかし特に網羅的に定点観測しようと思ってるわけでもないので悪しからず…
きそちしき
- File System とは…
- ファイルという単位でデータを管理して、ディスクに貯めておく。
- データを管理するためのデータ(メタデータ)もディスクに貯めておく。
- データ… ファイルをオープンすると見えるデータ。
- メタデータ…
ファイルやディレクトリの構造、データのあるディスクの位置などを管理
するためのデータ。ディレクトリ、inode、空きブロックマップなど。
- メタデータはディスクからメモリに読み込まれて、
ファイルシステムを操作するためのカーネル内の構造体に
- ディスク
- シリンダ：同心円上の1つの筒。シリンダ内の各円盤(ディスク)に
上からトラック番号がつけられる。
- トラック：同心円上の一周。
- セクタ ：トラックをピザみたいに分割したときの一個。
物理的に読み書き可能な最小単位。
主な論点
- 性能向上
- ディスクアクセスをなるべく減らす
キャッシュの活用、遅延書き込み
- 読み書き以外に必要なディスク操作を減らす (シーク、回転遅延)
まとめてアクセスされそうなデータをなるべくくっつけて置く
- ディスクアクセスを非同期に行なう
先読み、遅延(非同期)書き込み
- 一貫性とクラッシュリカバリ
- メモリ内に読み込まれた構造体を操作→ディスクに反映
ディスク上のイメージはメモリ内の状態に比べるといつも少し古い
- 突然マシンがクラッシュすると、ディスク上のイメージが
- 古い (最新データが保存されていない) → しょうがない
- 非一貫 (操作が中途半端に書き出されている) → 困る
- クラッシュリカバリ機構
- クラッシュしたあと、マシンが再起動してきたら
ファイルシステムのイメージをメモリ内に読み込んだあと、
問題のない状態にリカバリする必要がある
→ 例えば fsck
- その他
- ディレクトリ構造
エントリが多くなるとリニアサーチでは遅いとかそれなりにいろいろある。
FreeBSD は最近ハッシュを導入(DIRHASH)。
- ブロック管理・インデックス配置 (2003/10追記)
最近の FFS 系列ではないファイルシステム (reiser, jfs, xfsなど) は
ブロック管理に多重参照ではなく
B-Tree派生の B*-Tree (Reser) や B+-Tree (JFS/XFS) を使ってるようだ。
Ext3 も HTree という木構造を使い出したようで、
商用FS や Linux 系列ではこの辺りの戦いが熱いように見える
(
この
辺の
記事参照)。
*BSD 系の FS ではあまりこういう話を聞かないがどうなっているのだろう…？
系列概観
1980〜1990年前半はデータ読み書きの高速化に焦点 (FFS, Clustering, LFS)
1990年代以降はメタデータ更新とクラッシュリカバリの高速化に焦点 (Journaling, LFS,
Soft-Updates)
- Ext2fs はほとんどFFS
- Journaling は元は DB 技術。
最近のほとんどのファイルシステムに組み込まれている。
FS としては IBM RS/6000 の JFS あたりが発祥?
- LFSは Journaling の流れを受け継いでるが、
かなりエキセントリックなつくり。
- BSDは一貫性問題についてはやや独自路線で、
Soft-Updates に走った
一貫性問題とは?
-
一貫性の問題はざっくり次の2つに分けられる…かも
- 解決できない非一貫性を作らない
これはどのファイルシステムでも守られなければならない。
これをなくすためには、ある種の操作の順番を必ず守る必要がある。
- 解決できる非一貫性を起動時に修復(リカバリ)
1. を守っていても、クラッシュが起きたら再起動時に
解決できる非一貫性を修復してあげなければいけない。
- 解決できない非一貫性を作らない方法
- Traditional FFS…synchronous に個々のメタデータ操作を書き出す
- Journaling, LFS…
更新操作時、更新データを直接上書きしないで、
一貫性のあるデータを別のところに保持しておくようにする
- LFS…ディスク上のブロックレイアウトを時系列にすることで、
書き出し順序による非一貫性ができないようにする
- Soft-Updates…
解決できない非一貫性ができない順番を必ず守って更新を書き込む
- 解決できる非一貫性を起動時に修復(リカバリ)する方法
- Traditional FFS…再起動時にディスク上の全ての
メタデータをみて非一貫性を修復する (これがfsck。時間がかかる)
- Journaling, LFS…ロギングとcheckpointingによりリカバリを高速化。
- 更新を決められたログ領域に書いていくことで、
リカバリ時にチェックしなければならないディスク範囲を小さくする
- ログ書き出しとは別の場所に最新の一貫性のある状態を残しておき、
そこまで戻してあげる (checkpoint)
- 時系列に書き出されたログを用いて、
最後の checkpoint から後に起こった操作をできるだけ
リカバーしてあげる
- Soft-Updates…保守的な順番で変更を書き出すので、
「どこからも指されてないデータはあり得る」が
「どこも指していないポインタはあり得ない」。
従って、リカバリ処理をしなくてもすぐに通常処理をはじめられる
(Background Fsck)。
Journaling と LFS は一貫性処理に関してだけ言えば良く似て見える。
しかし、
Journaling がメタデータの更新についてだけ
ここであげてるような処理をするのに対し、
LFSは全てのデータ更新を上書きなし・時系列書き出しにしてしまった。
ちょっとやり過ぎ?
UFS (Unix File System)
- 基本構成 (ほとんど全FSで共通)
- ディスクはいくつかのパーティションにわかれる。
- 各パーティションは1つのファイルシステムを持つ。
- ファイルシステムはSuper-blockで定義される。
- ファイルシステムは複数のファイルを持ち、
各ファイルはinodeというメタデータによって管理される。
- 全てのデータはブロックという単位に分割して扱われる。
- 構造体
- Super-block … ファイルシステム自身を定義する超重要メタデータ
ブロック数、大ファイル数、各種パラメータ、
各データの開始ブロック番号など
- inode … ファイルを表すメタデータ。
ファイル所有者、タイムスタンプ、
ファイルのデータブロックのアドレスなど
- 直接ブロック (8個)
- 一重間接ブロック (1個)
- 二重間接ブロック (1個)
- 三重間接ブロック (1個)
- UFS は今の基準で言うととても遅い
- UFS のブロックサイズは512バイト (小さ過ぎる)
つまり、データは全部512バイト単位で読み書きしていた。
- 直接ブロックに収まるファイルサイズがとても小さく(4KB)、
それを越えると間接ブロックを読まなければならないのでますます遅い
FFS (Fast File System)
細かいサーベイはココ
UFSの再実装版。今のほとんどのUNIX系FSの原点。
高速化に重点。UFSより〜10倍速いと言われる。
- super-block の冗長化
- 最小ブロックサイズを4096バイトに (4096以上の2^n)
- 直接ブロックを12個に
(2段以上の間接ブロックなしに2^32バイトのファイルを作れる)
- FFSはパーティションをいくつかのシリンダグループに分けて管理する。
- 各シリンダグループは次のような管理情報を持つ
- inodesスペース
- シリンダグループ中の使用可能なブロックを示すビットマップ
- シリンダグループ中のブロックの使用状況を示すサマリ情報
- フラグメント
最小ブロックサイズが大きくなった分、空間的な無駄も増える。
これをなくすために1ブロックを1つ以上のフラグメント
に分割して使う。フラグメントの最小サイズは通常512バイト。
- 余分なフラグメントをなるべく増やさないように、
データが増えたらなるべく半端なフラグメントをコピーしてブロックにまとめる。
- ブロックレイアウト方針
- Global Policy
- 方針A. 関連情報をまとめて同じシリンダグループに
ex. 同じディレクトリ中のデータ
- 方針B. 関連しない情報はなるべく分散させて違うシリンダグループに
ex. 新しいディレクトリ、大きいファイル、間接ブロックなど
- Local Routines
- 要求されたブロックが空いていればそれを確保
- それが空いていなければ、
- 同じシリンダ内で rotationally closest block を確保
- 駄目なら同じシリンダグループ内から確保
- まだ駄目ならシリンダ数を quadratic hash にかけて、
そのシリンダグループを順番に try
- まだ駄目ならすべてのシリンダグループをなめて空きを探す
- 性能
- ディレクトリリスティング … UFSの2倍くらい、
エントリがファイルしかない場合は8倍
- Read Throughput … UFS の 7〜8 倍、
最大でDisk BW の47%
- Write Throughput … UFS の 3〜4.5 倍、
最大でDisk BW の47%。
Write の場合の方が block size の大きさが影響する
- その他の機能的変更
- long filenames(255文字)
- ファイルのロック機構
- symbolic links
- rename システムコールの追加
- quota機構
FFS Clustering
細かいサーベイはココ
ブロック毎にI/Oするのではなく、
まとめてクラスタにしてやってI/O命令を発行するもの。
ちなみにこの頃(1990年前後)トラックバッファが一般的になって来た。
- 書き込みを遅延して隣接するブロックを結合して扱うようにする。
- read ahead を block 単位ではなく cluster 単位で行う
- write が呼ばれたら、連続ブロックが書かれると仮定して一度目はスルー
二度目の呼び出しが連続ではなかったら1回目のを書き込む。
連続だったらそのまま cluster を形成するまで遅延
クラスタの allocation は、フラグメントの allocation とほぼ同様。
つまり、
最初は普通に allocate し、もし普通の方法だと連続
ブロックが確保できない場合、新しく必要な数のブロック(クラスタ)
を realloc してそちらにコピーする。
ディスク操作はクラスタ単位で行なわれるので、
回転遅延(rotdelay)のためのギャップは
ブロック間ではなくクラスタ間に置かれる。
(maxcontig = クラスタサイズ)
- 性能
- 連続読み込みは約2倍
- 連続書き込みは1.7〜1.8倍
- ランダム読み書きはほぼ一緒
LFS
細かいサーベイは
ココ(Sprite-LFS)と
ココ(BSD-LFS)
-
全てのデータをwrite-aheadのログとして書き込むファイルシステム。
- FFSが論理的に関連のあるデータを隣接して置くのに対し、
LFSは書き込みの時系列にしたがってデータを隣接しておく。
- ディスクを複数のセグメントに分割し、
セグメント単位でログを書き出す。
- inode が決まった場所に置かれないので、
各ファイルの inode の位置を示す inode map というデータを管理する。
ちなみに BSD-LFS では inode map は通常ファイルに書き出され、
そのファイルのinodeのアドレスがスーパーブロックに書き込まれる。
- 小さな書き込みをまとめて大きな単位で書き込むことで高速化
- 書き込み間のシークタイムを削減
- 変更が時系列にログとして残るので、クラッシュリカバリを高速化
- 問題点
- どれだけ連続的に書き込めるかが肝なので、連続する空き領域が必要。
- 上書きしないでどんどん新しいところに書いていくので、
空き領域を回収しないと書けなくなってしまう。
- クリーナー
- 古いセグメントを読み込んで、生きてるデータだけを新しい
セグメントに書き出す。(ログの圧縮)
- 世代別GCのように、古くてゆっくり変わるセグメントと
若くてどんどんデータが死んでいくセグメントを分けて扱う。
- ちなみに BSD-LFS ではクリーナーはユーザレベルデーモン。
inode map のある通常ファイルを読み出してガシガシ掃除する。
- 高速クラッシュリカバリ
- LFSでは時系列にデータが書き込まれるので、
クラッシュ直前に書き込んだデータがわかる。
→ そこだけおかしくないか見れば良い。
- 定期的にディスクとメモリを同期 (checkpoint)
- クラッシュ復帰後は、まず最後の checkpoint を読み出して
状態を復元し、そこから先のログを見て状態を復元できるところは
復元する。(roll-forward)
Soft-Updates
細かいサーベイはココ
Soft Updatesとは？
Ext3FSのJournaling
細かいサーベイは
ココ(ext2)と
ココ(ext3)
- ExtFS は MinixFS の後継
- Ext2FS はほぼ FFS (ただしフラグメントとかはないという噂)
- Ext3FS は Ext2FS の Journaling 拡張
- Ext3FSの目標…クラッシュ後のFSを素早くリカバーできるようにすること。
- Journaling の導入
- メタデータ操作時、FS本体のデータを直接書き換えるのではなく、
Journaling領域に対して更新を書き出すようにし、
一連の操作が終ってから変更を一度に本体のFSに書き戻す。
- リカバリ処理は journal 領域を scan して commit されているデータだけ
FS の元データに反映すれば良い。
→ journal 領域は一般にFS全体よりずっと小さいので、
従来のfsckよりずっと早く終るハズ。
- Journal に書き出すデータは次の3種類:
- Metadata
transaction によって更新されるメタデータのあるブロック全体を
保持する。ブロック中で変更されるところが非常に少なかったとしても
ブロック全体を保持。
- Descriptor
メタデータブロックのことを記述する journal ブロック。
Journal 内にある各メタデータブロックに対して、書き出されるべき
メタデータブロックの数と、書き出される先の disk block numbers
を記録する。
- Header Blocks
journal の現在の先頭と末尾、そしてシーケンス番号を記録するブロック。
これらの header blocks は決まった位置に置かれる。
リカバリ時には、この header blocks がスキャンされ、それをもとに
ログの末尾から先頭に向けてログをスキャンする。
- 変更の反映方法
- 未解決の変更を新しい compound transaction として commit する。
(journal に書き出す)
- transaction 中のメタデータをトラックし、それらが本体に書き戻された
ときに通知できるようにする。
- transaction が本体に書き戻されて同期が取れたら、はじめて journal
内のコピーを消す。
各手法のざっくりした比較
- FFS Clustering vs. LFS ([Seltzer95]より)
LFS がシーケンシャル書き込みで高速化を計りだしたころと
FFS が Clustering で高速化を計りだしたころはけっこう同時期。
- 各操作の性能
- メタデータ操作の性能は LFS＞FFS
- 小さなファイルの read 性能は FFS≒LFS
- 大きなファイルの read 性能は FFS＜LFS
- 小さなファイルの write 性能は FFS＜LFS
- 大きなファイルの write 性能は FFS＞LFS
- FFSはフラグメンテーションのために次第に性能低下
- LFSはクリーナの実行時は大幅な性能低下
クリーナ実行時の大幅な性能低下などもあって、LFS はけっきょく
各種改良後の FFS に対してそれほど性能的なアドバンテージは
なかったらしい。
- FFS vs. Journaling
Journaling を synchronous に行なった場合、
- 性能は FFS≒Journaling＜Soft-Update
- メモリとディスクの追従性は FFS≒Journaling＞Soft-Update
Journaling を asynchronous に行なった場合、
- 性能は FFS＜Journaling≒Soft-Update
- メモリとディスクの追従性は FFS＞Journaling≒Soft-Update
論文リスト
- FFS
-
[FFS]
M. K. McKusick, W. N. Joy, S. J. Leffler and R. S. Fabry.
A Fast File System for UNIX.
ACM Transactions on Computer Systems, 2(3):181-197, Aug 1984.
-
[Disk-Scheduling] (FFS高速化)
M. I. Seltzer, P. M. Chen and J. K. Outerhout.
Disk Scheduling Revisited.
Proceedings of the Winter 1990 USENIX Technical Conference, Jan 1990.
-
[FFS-Clustering] (FFS高速化)
L. W. McVoy and S. R. Kleiman.
Extent-like Performance from a UNIX File System.
Proceedings of the 1991 Winter Usenix Conference, pp.33-44, Jan 1991.
-
[Ext2FS]
Remy. Card, Theodore Ts'o and Stephen Tweedie.
Design and Implementation of Second Extended Filesystem.
In the Proceedings of the First Dutch International Symposium on Linux,
Dec 1994.
-
[Soft-Updates]
M. K. McKusick and G. R. Ganger.
Soft Updates: A Technique for Eliminating Most Synchronous Writes
in the Fast Filesystem.
Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference,
Jun 1999.
- LFS
-
[Sprite-LFS]
M. Rosenblum and J. K. Ousterhout.
Design and Implementation of Log-Structured File System
Proceedings of the 13th ACM SOSP, pp.26-52, Feb 1992.
-
[BSD-LFS]
M. Seltzer, K. Bostic, M. McKusick and C. Staelin.
The Design and Implementation of the 4.4BSD Log Structured File System.
Proceedings of the 1993 Winter Usenix, Jan 1993.
- Journaling
- [JFS]
A. Chang, M. F. Mergen, R. K. Rader, J. A. Roberts and S. L. Porter.
Evolution of Storage Facilities in AIX Version 3 for RISC System/6000
Processors.
IBM Journal of Research and Development, Vol.34, No.1, Jan 1990.
-
[Episode]
S. Chutani, O. T. Anderson, M. L. Kazar, B. W. Leverett, W. A. Mason
and R. N. Sidebotham.
The Episode File Systems.
Proceedings of the USENIX Winter 1992 Technical Conference,
pp.43-60, Jun 1992.
-
[Ext2fs-Journaling] (Ext3FS)
S. Tweeide.
Journaling the Linux ext2fs Filesystem.
LinuxExpo '98. 1998.
- 手法比較
- [Logging vs. Clustering]
M. Seltzer and K. A. Amith.
File System Logging Versus Clustering: A Performance Comparison.
Proccedings of the USENIX 1995 Technical Conference, Jan 1995.
- [Journaling vs. Soft-Updates]
M. Seltzer, G. Ganger, M. K. McKusick, K. Smith, C. Soules and C. Stein.
Journaling versus Soft Updates: Asynchronous Meta-data
Protection in File Systems.
Proceedings of USENIX Annual Technical Conference, pp. 18-23, Jun 2000.