ファイルシステムのメタデータについて調べたことを書いてみようと思います。
勉強のためにファイルシステム関連の資料を見ていると、メタデータの種類に関して列挙しているものはたくさん見つかったのですが、それらがどのように保存されるかについての記述をあまり見つけられず理解に苦しんだ覚えがあるので、そこについて書いていこうと思います。
ファイルのデータの位置
今回は、具体的な例から始めたいと思います。
以下は、ファイルの読み込み処理の流れの図です。この図についての詳細については、以前の記事に書いてありますので必要に応じてご参照ください。
上記の例では、アプリケーションが、read システムコールを通じて、file1.txt というファイルの 300 バイト目から 5000 バイトにかけて読み込もうとしています。
ファイルシステムは、このリクエストを受け、ディスクからそれらのデータを読み出して、アプリケーションへ渡してあげます。
ポイントとして、ファイルシステムは、file1.txt というファイルの 300 バイト目から 5000 バイトにかけてのデータがディスクのどこにあるか、を知っている必要があります。
この位置に関する情報がメタデータの一例になります。メタデータと呼ばれるものには、ファイルのパスや、作成日時も含まれますが、今回は、このファイルデータの位置に関する情報について、特にわかりやすいと思ったので掘り下げていきます。
以前の記事にもあるとおり、多くのファイルシステムは、ファイルを４キロバイトごとに区切ってページ単位で管理します。ファイルデータのディスク上の位置についても、各４キロバイトのブロックごとに位置を記録されることが多いと思います。
また、ファイル内のブロックは、よく４キロバイトで分割したインデックス番号で表現されます。
このようなファイルデータのディスク上の位置に関する情報はテーブルとして表現できます。例として、図中の file1.txt のデータは以下のようなマッピングで保持されているとします。
今回は、ディスクの１ブロックを４キロバイトとしています。
| ファイル内のインデックス | ディスク上のブロック番号 |
|---|---|
| 0: (0KB~4KB) | 400 |
| 1: (4KB~8KB) | 950 |
| 2: (8KB~12KB) | 985 |
| 3: (12KB~16KB) | 986 |
| 4: (16KB~20KB) | 987 |
| 5: (20KB~24KB) | 988 |
上記のテーブルを参照すると、システムコールでリクエストされた 300 バイトから 5000 バイトまでのデータのうち、300 バイトから 4KB まで（インデックス０）はディスク上のブロック番号 400 に、4KB から 5000 バイトまで（インデックス１）はブロック番号 950 の位置にあることがわかります。
図の例では、位置を取得した後に、デバイスドライバを通じて、対応するデータをページキャッシュに読み込んでいます。
メタデータの保存について
このような、データの位置に関するようなメタデータはどのように保持されているかを見ていきます。
ポイントは、ファイルシステムは、ファイルのコンテンツのデータだけでなく、このテーブルもディスクに一緒に書き込んで保存しておく必要があるということです。メモリ（ DRAM ）上のデータは、コンピューターの電源が切れると消えてしまうため、再起動しても保存したファイルのコンテンツにアクセスできるようにするためには、このディスク上のデータの位置に関する情報を保持するテーブル自体もディスクの上に書いておかなければなりません。
ディスクの上で、テーブルのようなキーとバリューのペアを保存する場合には、よくB木のようなデータ構造が利用されます。B木自体の詳細については他の資料をご参照ください。
以下に、ディスク上に保持されるB木の例を図にしました。実際には、色つきの四角いブロックのサイズは、４キロバイト（もしくは４キロバイトの倍数）で、かつ図では各ブロックに２つしかエントリーがありませんが、実際は４キロバイトいっぱいに収まるだけエントリーが入ることにご留意ください。
図のB木は、上記のテーブルの内容を反映したものになっています。図中のツリーは、キー（ファイル内のインデックス）０〜６と、対応するバリュー（ディスク上のブロック番号）を保持しています。
ディスクの上にB木のようなデータ構造を保存する際には、メモリ上で完結するデータ構造のプログラミングと異なる点があります。通常メモリ上で完結するツリーであれば、ノードやリーフへのポインタは仮想アドレスですが、ディスク上に保存されるツリーの場合には、ポインタをディスク上のブロック番号として保存する必要があります。
図の例では、まず inode が、ツリーのルートが保持されているディスク上のブロック番号を保持しています。（この inode 自体もメタデータとして、また別途ディスクの上に保存されています。）
（例の図では、inode に木のルートのポインタを紐付けるように書いてありますが、実際はルート自体を inode に含めてしまう実装のほうが多いかもしれません。）
例えば、テーブルを参照してインデックス０（ファイルの 0 KB目から 4 KBまで）のデータがディスクのどこにあるか知りたい場合には、まずはじめにルートの保存されているディスク上のブロック（今回は 102 番、 赤色のブロック）からデータをメモリに（まだメモリにロードされていなければ）読み出します。
次に、ルートに保存されている情報を見ると、B木の仕様から、キー１より小さいキー０に対応するバリューを得るにはディスク上のブロック番号 110 に保存されているノード（リーフ、黄色のブロック）をたどる必要があることがわかります。その次には、ブロック番号 110 に保存されているデータをメモリへ読み込み、その中を見ていきます。今回の例では、探していたキー０に対応するエントリーが含まれていたのでここで探索を終了し、結果として、バリュー 400 を取得します。
このように、ディスク上のデータ構造は、ポインタが仮想アドレスでなく、ディスク上のブロック番号になっているのが特徴です。連続的なデータブロックの集合であるディスクの上にデータの配置を図示すると、上図の点線以下の部分のようになります。
このように、ファイルシステムは、ファイルのコンテンツのデータ以外にこのようなB木のようなデータ構造をいくつもディスクに書き込んで保存しています。そのようなデータは総称してメタデータと呼ばれています。
その他のメタデータ
他には、典型的に inode やファイルのパスの情報はメタデータとして取り扱われます。ファイルのサイズ、作成時間等については inode の構造体自体に含まれることが多いと思います。
他に重要なものとして、ディスクのどの箇所が使われているかという、ディスクの仕様状況に関する情報もメタデータに含まれます。こちらはビットマップとして表現されることが多いかもしれません。
ポイントとして、それらのようなメタデータも、B木やリストのようなデータ構造を通して紐付けられ保存されます。
ファイルのディスク上のデータの位置は inode から辿れるようになっていますが、ファイルシステム全体の例えば inode を含むメタデータは、（多くの場合パーティションの最初に位置する）スーパーブロックを起点として辿れるようになっています。
実際のファイルシステムではどうなっているか
今回見ているファイルのディスク上のデータ位置に関する対応は、例えば、Linux で広く利用されている ext4 ファイルシステムでは、extent tree というB木っぽいデータ構造で管理されています。主に、extent tree では、ファイル内、ディスク上両方で連続的に保持されているブロックの範囲を保持するようになっています。これにより、位置を記憶するために必要なディスク上の領域が削減できます。
例えば、今回の例としているテーブルは６ページ（24 キロバイト）分のデータのマッピングを保持するために６つテーブルにエントリーが必要ですが、extent tree であれば、以下のようにエントリーは３つで済みます。
| ファイル内のインデックス | ディスク上のブロック番号の開始位置 | 範囲 |
|---|---|---|
| 0: (0KB~4KB) | 400 | 1 |
| 1: (4KB~8KB) | 950 | 1 |
| 2~5: (8KB~24KB) | 985 | 4 |
この最適化は、大きなサイズのファイルを扱う時に、メタデータのサイズが大きくなり、ファイルのコンテンツのデータ自体の保存領域を圧迫しないようにするために重要です。
まとめ
メタデータは、ディスクの上に保存されることを想定したデータ構造を用いて、スーパーブロックから辿れる形で保存されます。
そのようなディスク用のデータ構造は、ポインタの値が仮想アドレスではなくてブロック番号であることが特徴としてあげられます。
