Linux ファイル システム (ファイル システム) アーキテクチャの簡単な分析

＃＃＃写真＃＃＃

上の図は、このアーキテクチャの中心が仮想ファイル システム VFS であることを示しています。 VFS はファイル システム フレームワークを提供し、ローカル ファイル システムは VFS に基づいて実装できます。主に次のタスクを実行します:

1) VFS は抽象化層として、アプリケーション層に統合インターフェイス (読み取り、書き込み、chmod など) を提供します。

2) i ノード キャッシュやページ キャッシュなど、いくつかの一般的な機能が VFS に実装されています。

3) 特定のファイル システムが実装する必要があるインターフェイスを標準化します。

上記の設定に基づいて、他の特定のファイル システムは、VFS の規則に従い、対応するインターフェイスと内部ロジックを実装し、システムに登録するだけで済みます。ユーザーはファイル システムをフォーマットしてマウントした後、ハードディスク リソースを使用してファイル システムに基づいた操作を実行できます。

Linux オペレーティング システムでは、ディスクをフォーマットした後、mount コマンドを使用して、システム ディレクトリ ツリー内のディレクトリにディスクをマウントする必要があります。このディレクトリはマウント ポイントと呼ばれます。マウントが完了すると、このファイル システムに基づいてフォーマットされたハードディスク領域を使用できるようになります。 Linux オペレーティング システムでは、マウント ポイントはほぼ任意のディレクトリにすることができますが、標準化のため、通常、マウント ポイントは mnt ディレクトリの下のサブディレクトリになります。

次に、比較的複雑なディレクトリ構造を示します。このディレクトリ構造では、ルート ディレクトリはハード ディスク sda 上にあり、mnt ディレクトリの下には ext4、xfs、nfs という 3 つのサブディレクトリがあり、それぞれ Ext4 ファイル システム (sdb ハード ディスク上に構築) とXFS ファイル システム (sdc ハード ドライブ上に構築) および NFS ファイル システム (ネットワーク経由でマウント)。

＃＃＃写真＃＃＃

ディレクトリ ツリー内の複数のファイル システム間の関係は、カーネル内のいくつかのデータ構造によって表されます。ファイルシステムをマウントすると、ファイルシステム間の関係が確立され、特定のファイルシステムの API が登録されます。ユーザー モードが API を呼び出してファイルを開くと、対応するファイル システム API が検索され、それがファイル関連の構造 (ファイルや i ノードなど) に関連付けられます。

上記の説明は比較的概略的なものですが、それでも少し混乱するかもしれません。ただし、心配しないでください。次に、コードに基づいて VFS と複数のファイル システムをサポートする方法について詳しく説明します。

1. ファイル システム API から VFS、そして特定のファイル システムへ

Linux の VFS は最初から利用できませんでした。Linux の最初にリリースされたバージョンには VFS がありませんでした。さらに、VFS は Linux で発明されたものではなく、1985 年に Sun によって SunOS2.0 で最初に開発されました。 VFS を開発する主な目的は、ローカル ファイル システムと NFS ファイル システムを適合させることです。

VFS は、一連のパブリック API とデータ構造を通じて特定のファイル システムの抽象化を実装します。ユーザーがオペレーティング システムが提供するファイル システム API を呼び出すと、カーネル VFS によって実装された関数がソフト割り込みを通じて呼び出されます。次の表は、いくつかのファイル API とカーネル VFS 関数の対応を示しています。

ユーザーモードAPIdo_sys_openファイルを開くksys_closeデータの読み取りksys_write/vfs_writedo_mountファイルシステムのマウント

上の表から、各ユーザーモード API には、それに対応するカーネルモード関数があることがわかります。アプリケーションがファイル システムの API を呼び出すと、カーネル状態の対応する関数がトリガーされます。ここにリストされているものはファイル システム API の比較的小さなサブセットにすぎず、目的は API と VFS の関係を説明することです。他の API について知りたい場合は、カーネルのソース コードを自分で読んでください。この記事では詳しく説明しません。

VFS と特定のファイル システムの関係を誰もが知覚的に理解できるように、このセクションでは Ext2 の書き込み API を例として取り上げ、API から VFS 関数へ、そして Ext2 ファイル システム関数への呼び出し関係を示します。以下の図に示すように、API 関数 write はソフト割り込みを通じてカーネルの ksys_write 関数をトリガーします。いくつかの処理の後、この関数は最終的に関数ポインター (file->f_op) を通じて Ext2 ファイル システムの ext2_file_write_iter 関数を呼び出します。 ->wirte_iter)。

＃＃＃写真＃＃＃

上の図では、カーネル プロセスへの入り口は ksys_write 関数です。実装コードからわかるように、ここでの主な目的は fd を取得し、fd 内のメンバー ファイルを指定して vfs_write を呼び出すことです。パラメータ。このうち、fd は構造体であり、その形式は下図のとおりであり、ファイルメンバは比較的核となるデータ構造です。上の図からわかるように、Ext2 ファイル システムの機能はこのメンバーの内容を通じて転送されます。

＃＃＃写真＃＃＃

非常に簡単に思えますが、VFS は特定のファイル システムによって登録された関数ポインタを呼び出すだけで済みます。しかし、ここには未解決の問題があり、VFS の関数ポインターはいつ登録されたのでしょうか?

Ext2 の関数ポインタは、ファイルが開かれたときに初期化されます (詳細については、「ファイル システム テクノロジの内部」のセクション 3.1.2.2 を参照してください)。ご存知のとおり、ユーザー モード プログラムはファイルを開くときにファイル記述子を返しますが、カーネル内のファイルを表す構造ファイルはそれに対応します。この構造体のより重要なメンバーには、次の図に示すように、f_inode、f_ops、および f_mapping が含まれます。

＃＃＃写真＃＃＃

上の図では、f_inode はファイルに対応する i ノード ノードです。 f_ops は、特定のファイル システム (Ext2 など) でのファイル操作のための関数ポインタのコレクションで、ファイルが開かれたときに初期化されます。 VFS は、この関数ポインターのコレクションを通じて、特定のファイル システムへのアクセスを実装します。

上記には、VFS の別の概念である inode が関係しています。 Linux では、inode はインデックス ノードの略語で、ファイル システム内の特定のオブジェクト (ファイルやディレクトリなど) を表します。 VFS には i ノードという名前のデータ構造があり、これは特定のファイル システムの i ノードを抽象化したものです。たとえば、Ext2 ファイル システムでは、特に ext2_inode_info として定義されますが、XFS では、データ構造 xfs_inode で表されます。さらに、特定のファイル システムの i ノード データ構造は本質的に VFS の i ノードに関連しているため、コードを自分で読み取ることができます。

2.inode キャッシュと dentry キャッシュ

アーキテクチャ図では、VFS にページ キャッシュ、inode キャッシュ、dentry キャッシュなどのいくつかのキャッシュ実装があることがわかります。 inode キャッシュと dentry キャッシュは同じ方法で実装されており、比較的単純です。そこで、この記事ではまずこの 2 つのキャッシュを紹介します。 実際、これら 2 つのキャッシュはハッシュ テーブルを通じて実装されています。ハッシュ テーブルの概念は誰もが知っているので、この記事では詳しく説明しません。 i ノード キャッシュを例にとります。次の図は、その初期化プロセスを示しています。パラメータ ihash_entries を通じて、そのサイズが動的であることがわかります (そのサイズはシステム メモリに関連しています。システム メモリが大きいほど、inode キャッシュは大きくなります)読む）。 ＃＃＃写真＃＃＃

inode と dentry はファイルにアクセスするときに頻繁にアクセスされるため、これらをキャッシュすることで、ハードディスクからのデータの読み取りによるパフォーマンスの低下を回避できます。

3.ページキャッシュ

VFS ページ キャッシュ (Cache) の機能は、主にファイル システムのパフォーマンスを向上させるために使用されます。キャッシュ技術とは、ファイル システムのパフォーマンスを向上させるために、ファイル システムのデータの一部とメタデータをメモリに保存する技術を指します。メモリのアクセス遅延は機械式ハードディスクのアクセス遅延の 10 万分の 1 であるため (下図に示すように、レジスタを基本単位として 1 秒)、キャッシュ技術を使用するとファイルのパフォーマンスを大幅に向上させることができます。システム。

＃＃＃写真＃＃＃ キャッシュは、IO 最適化の 3 つの側面、つまりホット データ、事前読み取り、IO マージを通じてファイル システムのパフォーマンスを向上させます。多くのアプリケーションにはホット データが存在します。たとえば、作成者がドキュメントを編集するとき、現在のデータ ブロックと近くのデータ ブロックはホット データになります。あるいは、人気の記事が登場すると、その記事の内容がホットデータになります。基盤となるストレージ デバイスのパフォーマンスは、多くの場合、大きなブロックの読み取りおよび書き込みの方が優れています。先読みとは、基盤となるデバイスから事前に大きなブロックのデータを読み取ってキャッシュし、アプリケーションのリクエストがキャッシュを通じて応答できるようにすることを意味します。 IO マージは書き込みリクエスト用です。書き込みリクエストはすぐにバックエンド デバイスに永続化されませんが、キャッシュされ、書き込み前に大きな IO チャンクに分割されます。

メモリ容量はハードディスク容量よりもはるかに小さいため、ページ キャッシュは当然ながらすべてのハードディスク データをキャッシュすることはできません。このようにして、ファイル システム データのサブセットのみをキャッシュに保存できます。ユーザーがデータの書き込みを続けると、キャッシュがいっぱいになる状況が発生しますが、このとき、キャッシュ データをディスクにフラッシュし、新しいデータを格納する方法が問題となります。

キャッシュをディスクにフラッシュして新しいデータを保存するプロセスは、キャッシュ置換と呼ばれます。キャッシュ置換には多くのアルゴリズムがあり、それぞれが異なる問題を解決するために使用されます。次に、いくつかの一般的なキャッシュ置換アルゴリズムを紹介します。

LRU アルゴリズム。LRU の正式名は Least Recent Used で、最も最近使用されていません。このアルゴリズムは、時間的局所性の原則に基づいています。つまり、あるデータが最近使用された場合、将来も再使用される可能性が高くなります。したがって、アルゴリズムは最近使用されていないキャッシュを解放します。

LRU アルゴリズムは、通常、リンク リストを使用して実装されます。使用されたばかりのキャッシュはテーブルの先頭に挿入され、頻繁に使用されないデータは、リンクされたリストの最後にゆっくりと圧縮されます。リスト。 LRU の原理をより明確に理解するために、次の図で説明します。

＃＃＃写真＃＃＃

今回はフルヒットを例に紹介します。図の 1 行目に示すように、キャッシュ内に 6 つのデータ ブロックがあるとします。ボックス内の数字はデータ ブロックの番号を表します。最初のアクセス（読み書き可能）がデータブロックNo.3であるとする。アクセスされたのでリンクリストの先頭に移動する。

2 回目のアクセスはデータ ブロック No.4 です。同様の原理により、データ ブロックもリンク リストの先頭に移動します。詳細は、上図の 2 行目に示されています。

同様に、4 ラウンドのアクセスの後、アクセスされたデータは前方に移動され、アクセスされていないデータ ブロック (1 や 2 など) はリンク リストの最後尾にゆっくりと押し込まれます。これは、これら 2 つのデータ ブロックが後でアクセスされる可能性が比較的小さいことをある程度示しています。

フルヒットの場合、キャッシュの置き換えは行われません。実際の状況では、キャッシュが不十分な場合が多く、新しいデータを保存するにはキャッシュ内のデータを解放する必要があります (ディスクにフラッシュする必要があるかどうかは状況に応じて異なります)。このとき、次の図に示すように、末尾のデータ ブロックを使用して新しいデータを格納し、それをリンク リストの先頭に配置する LRU アルゴリズムが役立ちます。このデータ ブロックにダーティ データがある場合は、ディスクにフラッシュする必要があります。そうでない場合は、直接解放できます。

＃＃＃写真＃＃＃

LRU アルゴリズムの原理と実装は比較的単純ですが、その用途は非常に幅広いです。しかし、LRUアルゴリズムには、大量の連続データが突然書き込まれると、すべてのキャッシュブロックが置き換えられ、それまでのキャッシュ使用量の統計がすべて無効になるという欠点があり、この現象はキャッシュ汚染と呼ばれます。キャッシュ汚染の問題を解決するために、多くの改良された LRU アルゴリズムが存在します。その中で、より一般的なものは、LRU-K、2Q、および LIRS です。

LFU アルゴリズム、LFU の正式名は Least Frequently Used で、最近では最も使用頻度が低くなります。このアルゴリズムは、データ アクセスの頻度に基づいて、どのキャッシュ ブロックを解放するかを決定します。アクセス頻度が最も低いキャッシュ ブロックが最初に解放されます。

以下に示すのは、LFU アルゴリズムの概略図です。 1 行目は元の状態で、ボックス内の数字はキャッシュ ブロックがアクセスされた回数を表します。新しいデータの追加とキャッシュブロックの削除は末尾から行われます。あるデータ (点線のボックス) が 4 回アクセスされ、アクセス数が 12 から 16 に変化したため、新しい場所に移動する必要があるとします。これが図の 2 行目のようになります。 。

＃＃＃写真＃＃＃

本書では、理解を容易にするためにリンク リストを例として LFU の原理を説明しますが、プロジェクトの実施中にリンク リストを使用して実装されることはありません。データ ブロックへのアクセス数が変化すると新しい場所を見つける必要があるため、リンク リストの検索操作には非常に時間がかかります。高速な検索を実現するために、一般に検索ツリーが使用されます。

LFU にも欠点があり、データ ブロックが昔一定期間に頻繁にアクセスされ、今後アクセスされなくなった場合、データはキャッシュに残ります。ただし、データにはアクセスされなくなるため、キャッシュの実効容量は減少します。つまり、LFU アルゴリズムは最近の状況を考慮していません。

この記事では主に、LRU と LFU といった 2 つの非常に基本的な置換アルゴリズムを紹介します。上記のアルゴリズムに加えて、2Q、MQ、LRFU、TinyLFU、ARC など、多くの置換アルゴリズムがあり、そのほとんどは LRU と LFU の理論に基づいています。紙面の都合上、本書では詳細には触れませんが、関連する論文をご自身で読んでください。

データの先読みにも一定のアルゴリズムがあり、IO パターンを識別してディスクからデータを事前にキャッシュに読み込みます。このようにして、アプリケーションがデータを読み取るときに、キャッシュから直接データを読み取ることができるため、データ読み取りのパフォーマンスが大幅に向上します。

先読みアルゴリズムで最も重要なことは、トリガー条件、つまりどのような状況で先読み動作が開始されるかです。通常、先読みがトリガーされる状況は 2 つあります。1 つは、複数のアドレスからの連続した読み取り要求があり、先読み操作がトリガーされるときです。もう 1 つは、アプリケーションが先読みマークのあるキャッシュにアクセスするときです。ここで、先読みマークのキャッシュとは、先読み動作が完了したときにキャッシュページに付けられるマークであり、アプリケーションがこのマークが付いたキャッシュを読み込むと、次の先読みがトリガーされ、識別が省略されます。 IOモードの。

＃＃＃写真＃＃＃

先読みのロジックをより明確に説明するために、上の図を通してプロセス全体を紹介します。ファイル システムは、IO モードで事前読み取りが必要であることを認識すると、時間 1 (最初の行) に示すように、コンテンツの追加部分 (同期事前読み取りと呼ばれます) を読み出します。同時に、同期先読みデータの場合、ファイル システムはブロックの 1 つをマークします。このマークの目的は、キャッシュが終了する前にできるだけ早く次の事前読み取りをトリガーすることです。

2 番目の時点で、アプリケーションがデータの読み取りを続けると、マークされたキャッシュ ブロックが読み取られるため、次の事前読み取りが同時にトリガーされます。このとき、ディスクからデータを一気に読み込むことになり、キャッシュが増加していることが図からわかります。

次の時点 3 と 4 で、アプリケーションはキャッシュからデータを直接読み取ることができます。マークされたキャッシュ ブロックが読み取られていないため、次の先読みはトリガーされません。時点 5 では、先読みマークがあるため、再度先読み処理がトリガーされます。

上記の分析から、先読み機能により、データが事前にキャッシュに読み込まれることがわかります。アプリケーションはディスクにアクセスせずにキャッシュから直接データを読み取ることができるため、全体的なアクセス パフォーマンスが大幅に向上します。

カーネル関数	イラスト	＃＃＃開ける＃＃＃
		＃＃＃近い＃＃＃
ファイルを閉じる	＃＃＃読む＃＃＃	ksys_read/vfs_read
	＃＃＃書く＃＃＃	＃＃＃データ入力＃＃＃
＃＃＃マウント＃＃＃