恐竜本の11章です。先週は忙しくて勉強にあてる時間がなくて2週間ぶりです。ところでアプリケーションを開発していく上で関係ありそうな話が13章あたりまでで、以降はユーザー認証の話だったり分散システムだったりRTOSの話だったりみたいです。アプリケーション開発に直結しそうにないので、13章あたりで恐竜本は終わろうと思います。もちろん勉強しておくと似たような課題にあたったときにアナロジーが成り立って解決が早くなることもあるとは思いますが。
ファイルシステムの構成
アプリケーションプログラムがファイルに対して操作を行う時、次のようなヒエラルキーのシステムが動作する。
- アプリケーションプログラム
- 論理ファイルシステム
- ファイル構成モジュール
- 基本ファイルシステム
- I/O制御
- デバイス
I/O制御はデバイスドライバが担当しており、ストレージデバイスに対して直接命令を発したりする。例えば、「○○ブロックのデータを読む」という命令を受け取り、デバイス上の特定のメモリ領域に値を書き込む。すると、デバイスが理解してディスクを回したりする。
ベーシックファイルシステムは特定のブロックへの読み書き命令をI/O制御に渡したり、ブロックのキャッシュを管理したりする。
ファイル構成モジュールはファイルのブロック情報を持っている。物理的にどの番号のブロックにファイルがあるか、ファイルは全体でいくつのブロックからなるかを理解している。また、空きブロックを管理している。
論理ファイルシステムはファイルのメタデータを管理している。メタデータはfile-control block (FCB, UNIXではinode)という構造体で表される。
ファイルシステムの実装
ディスク上のファイルシステムには以下の構造が存在している。
- Boot control block
- Volume control block
- ディレクトリ構成情報
- FCB
Boot control blockにはコンピュータがOSを起動するための情報が入っている。UFSではboot block、NTFSではpartition boot sectorと呼ばれる。
Volume control blockにはパーティション内のブロック数やブロックサイズ、空きブロックへのポインタ、空きFCBの数、FCBへのポインタなどが入っている。UFSではsuperblock、NTFSではmaster file tableという。
また、メモリ上ではファイルシステム管理のための情報が保持される。これには、マウント済みファイルシステムのテーブル、オープン済みファイルのテーブル（システム全体、プロセスごと）などがある。
ファイルをオープンするとき、OSはまずシステムワイドのオープン済みファイルテーブルからエントリーを探す。そこでエントリーが見つかればディスクを見なくて良いのでオープンを高速化できる。なければディレクトリ構造をめぐり、ファイルを探す。ファイルが見つかったら、プロセスごとのオープンファイルテーブルにエントリーを追加する。エントリーにはファイル上の現在位置ポインタが含まれている。UNIXではこのエントリーのことをfile descriptor、Windowsではfile handleと呼ぶ。
ファイルを閉じるときはプロセスごとのオープンファイルテーブルからエントリを消し、システムワイドのテーブルのオープンカウントをデクリメントする。カウントが0になったらエントリーを消去するのが基本動作であるが、あえて消さずキャッシュしておく実装がよく取られる。次に同じファイルをオープンするときの速度がこれにより向上する。
パーティションとマウント
パーティションはraw diskである場合とファイルシステムを含んでいる場合がある。raw diskである場合、特定のファイルシステムが入っておらず、swap領域に使われたり、データベースが独自のフォーマットでデータを格納したりする。
システムの実行はディスク上の特定位置から始まり、たいていディスクの先頭パーティションになっている。そのようにしてブートローダーが起動され、ブートローダーはファイルシステムを理解できるので、ディスク上に存在するパーティション構造とファイルシステムを調べる。複数のOSが入っていることを認識したらブートローダーは起動するOSを選択する。
OSが起動されたら、OSカーネルが入っているパーティション、すなわちルートパーティションがマウントされる。それ以外のボリュームはそれ以後にマウントされる。Windowsでは各ボリュームは別のボリュームラベルで区別されるが、UNIXではファイルシステムの木構造のどの位置でも別ボリュームをマウントすることができる。
様々なファイルシステムがディスク上に同居でき、OSは色々なファイルシステムを理解できるが、ユーザーはいちいちその違いを意識する必要は無い。これは、各ファイルシステムの取り扱いを抽象化するVFSという仕組みが存在し、ユーザーのopen(), read(), write(), close()と各ファイルシステムの間を取り持っているためである。VFSはあらゆるファイルシステムを以下のオブジェクトで抽象化する。
- inode
- file
- superblock
- dentry (directory entryの略)
また、ファイルに対してopen,read,write,mmap(memory mapped file)の操作を提供する。
ディレクトリの実装
ディレクトリ上に存在しているファイルや子ディレクトリをどうやって管理するかには主に２つの方法がある。1つ目の方法は線形リストを使うというものである。この方法は実装が簡単であるが、パフォーマンスが低くなる。例えば、ファイルを作成する時、同じ名前のファイルがディレクトリ内に存在しないことを保証する必要があるが、リストに対してシーケンシャルアクセスすることで全エントリーと被っていないことを確かめなければならない。また、ファイルの検索もファイル数に対して線形時間がかかる。
2つ目の方法は、ハッシュテーブルを使うというものである。検索時間はファイル数に依存しなくなる。この方法ではハッシュの衝突に対応できなければならない。例えば同じハッシュ値のファイルを連結リストで管理するなどが必要となる。
ディスク領域の割当
ファイルを作るときには、そのファイルをディスク上のどこに置くかを決めなければならない。領域割当の問題はメモリの割当のときに考察した問題と全く同じである。
Contiguous Allocationでは連続した領域にファイルを配置する。例えばnブロックのファイルをブロック番号bに配置する場合は、ブロック番号b～b+n-1までの領域がそのファイルに割り当てられる。この場合はexternal fragmentation、つまりファイルの削除などでファイルとファイルの間に小さな隙間ができるとなんのファイルも入れられない死んだ領域と化す問題がでる。この問題へは、一旦ファイルを別のストレージに退避して隙間を詰めながら元のストレージに戻すcompactionで対応することになるが、あまり速い操作ではない。加えて、この方法ではファイルサイズをファイル作成開始時に知っている必要がある。なぜなら、小さすぎる領域を割り当てるとファイルを書き込みきれなくなるからである。この問題に対処するため、contiguous allocationを改良してextentという動作をサポートするファイルシステムがある。この場合、ある領域が足りなくなると別の領域が割り当てられ、ブロックの最後にそこへのポインタが書き込まれる。
Linked allocationはcontiguous allocationの問題をすべて解決する。ディレクトリ情報にはファイルの先頭ブロックと末尾ブロックのポインタが記録される。また、各ブロックには次のブロックのポインタが記録されている。全ブロックをつなげると一つのファイルとなる。この方法はシーケンシャルアクセスするファイルに対しては問題ないが、ランダムアクセスするファイルの場合は、頭からポインタをたどる必要があるため、非効率である。また、次のブロックのポインタを記録する必要があるのでポインタサイズ分使える領域が減る。この非効率性を軽減する方法として、複数のブロックを1個のクラスターとし、より大きな単位にするというものがある。また、別の問題としては、連結リストでファイルがつながっているので、どこかで情報が損傷するとおかしな領域を参照することになる、つまり信頼性の問題がある。対応策としては連結リストではなく二重連結リストにするというものがあるが、オーバーヘッドを伴う。このLinked allocationの亜種としてはfile-allocation table(FAT)を使うものがある。FATではブロック上に次のブロックのポインタがあるのではなく、ポインタばかりを１箇所に固めたデータ構造を用意する。FATをメモリ上にキャッシュしていない場合、ディスクから読み取ってブロック位置を探すのはディスクヘッドのシークが増えて非効率である。一方で、FAT上の情報を読めばヘッド位置がわかるのでランダムアクセス時間は向上する。
Indexed allocationではファイルの先頭から、物理ブロック番号を順番に記録したインデックスを用意する。これはファイル上の論理的なブロック番号と物理的なブロック番号を紐づけるという点でページングに似た仕組みになっている。Indexed allocationではインデックス情報専用のブロックを用意するので、ファイルが小さいとインデックス情報が専有するブロックのほうが大きく非効率となる。
Indexed allocationでは大きなファイルに対応するため、複数のインデックスブロックを連結リストとしてつなぐ方法や、複数階層を持ったインデックスで管理するなどの方法が取られる。また、直接ファイル上のデータを指し示すポインタと、別のインデックスを指し示すポインタとを両方持つ方法もとられる。
空き領域管理
ファイルシステムは空き領域の場所を把握している。その方法として、bitmapやbit vectorと呼ばれる方法がある。これは空いているブロックを0、専有されているブロックを1として全ブロックを管理する方法である。また、bitmapを前提として、領域割当の際にすぐ0のブロックを探し出せるようなハードウェア命令が用意されている。bitmapはメインメモリ上に保持されていないと非効率であり、非常に大きなストレージが出てきたらbitmapのサイズが問題となる。1PBのストレージの場合、512Bのブロックを管理するためには32GBのbitmapが必要となる。
連結リストによる空き領域管理では、空き領域がポインタでつながっている。全空き領域をトラバースしたい場合は非効率だが、空き領域の割当では先頭だけ取れればいいので問題ない。この方法の亜種として、空きブロックが連続する場合は始まりのブロック番号と終わりのブロック番号を各ノードが持つことで、多くの空きブロックを割り当てるときの速度を高速化できる。
領域が基本的にバルクで割当たったり解放されたりするという性質を利用して、空き領域の先頭ポインタと空きブロック数をテーブル上に記録するという方法やmetaslabを使った方法がある。
キャッシュ・先読み
いくつかのシステムではバッファーキャッシュという領域をメモリ上に持っており、ブロックの内容を保持している。再度同じブロックを読み込む場合はバッファーキャッシュから読み込まれ高速化が期待できる。また、メモリーマップトファイルの場合はページキャッシュが存在している場合があり、同一ページの読み込みは同じく高速化される。バッファーキャッシュとページキャッシュが両方存在する場合があり、この場合はdouble cachingと呼ばれる。メモリが無駄であるだけでなく、両方のキャッシュが整合しないとファイルの破壊につながる。この問題に対処するためUNIXではunified buffer cacheという仕組みでメモリーマップトファイルと普通の読み書きのキャッシュを統一している。
キャッシュ以外の高速化の仕組みとして、シーケンシャルアクセスで使われるfree-behindとread-aheadがある。free-behindでは次のページがリクエストされたら前に読み取ったページをすぐキャッシュから消し、read-aheadではあるページがリクエストされたらそれに続く複数のページを先読みしておく。
復元
ファイルが破損した場合の復元方法をファイルシステムが用意していることがある。システムはstatus bitというフラグをファイル書き込み前にセットし、ファイル書き込み完了後にクリアする。書き込み中に異常終了した場合はフラグが残っているので次回起動時に整合性チェッカを動かす。整合性チェッカは空き領域管理アルゴリズムに依存して整合性を検証する。例えば連結リストによる空き領域管理の場合、ブロック同士のリンクが生き残っていればディレクトリ構造を復元できる。一方でインデックスを使った空き領域管理をしていた場合はブロック同士がどういう関係性にあるかがわからず、災害的となる。
ログベースのトランザクション志向ファイルシステムでは、データベースの仕組みを利用してログからのファイル復元を行う。通常時はデータ操作はログに記録され、あとから内容をファイルシステムに書き込む（コミット）。ログはリングバッファで実装されており、古いログは自動で上書きされる。システムがクラッシュしたらコミットされていないログが残るので、最後のコミット時点からログを辿って内容を復元する。
NFS
NFSはネットワーク上の別コンピュータのファイルシステムを利用するための仕組みである。NFSではNFSプロトコルというもので互いに通信する。マウントプロトコルではサーバーとクライアントの間でコネクションを確立する。サーバーはexport listというネットワークに晒すディレクトリのリストを持っている。クライアントは自分のディレクトリ構造の好きな場所にエクスポートされたディレクトリをマウントする。
NFSプロトコルではディレクトリ内のファイル検索、ディレクトリ内部のファイルリスト取得、リンク操作、ファイル属性へのアクセス、ファイルの読み書きをサポートしている。オープンが無いのは、NFSはステートレスになるよう設計されたからである。
NFSはVFSによって抽象化され、ユーザーはNFSを使っているからといって他のファイルシステムとの違いを感じない。
パスの変換では、パスに含まれるディレクトリごとにその直下に指定されるファイルやディレクトリが存在するかを確認する。例えば/usr/local/dir1/file.txtというパスがあったとき、usr下にlocalがあるか確認し、local下にdir1があるか確認し、dir1下にfile.txtがあるかを確認する。なん往復も通信するのを防ぐためパス全体をサーバーに渡して確認するようにしたいが、パス内に別ファイルシステムがマウントされている可能性があり、サーバーはクライアントが勝手にマウントした別ファイルシステムに遭遇することがある。そのため、パス全体を渡すことはできない。
NFSはステートレスに設計されているが、OSが取ったファイル属性やファイルブロックをキャッシュすることでパフォーマンスの向上が行われることもある。
コメント