F2FS (Flash-Friendly File System) は、サムスン電子の金載極 (、) によって開発されたLinux向けのフラッシュファイルシステムである。
NANDフラッシュメモリベースのストレージSDカード・SSDなどは、スマートフォン・タブレットからサーバまで、様々な種類のコンピュータで利用されている。F2FSはこれらのストレージの特性を考慮したファイルシステムとして設計が行われている。
F2FSはログ構造ファイルシステムを、NANDフラッシュメモリベースのストレージに適したものにして取り入れている。F2FSでは、従来のログ構造ファイルシステムの問題点であるガベージコレクションの負荷の高さなどを解消している。NANDフラッシュメモリベースのストレージではフラッシュ変換レイヤ (、FTL) が実装されており、フラッシュメモリの特性書き込み回数の上限の存在などの隠蔽とHDDのエミュレートを行い、SATAなどのインタフェースで利用ができるようにしている。F2FSはFTLの存在を前提として、NANDフラッシュメモリベースのストレージの性能を引き出すことができるように設計されている。
特徴 F2FSには、以下の機能が実装されている。
また、以下の機能の実装が予定されている。
設計 ディスクレイアウト F2FSはボリューム全体を多数のセグメントに分割する。各セグメントのサイズは2MB固定である。連続する複数セグメントをまとめてセクションが定義され、セクションの集合としてゾーンが定義される。デフォルト設定では、セクションとゾーンは同じサイズに設定されるが、ユーザはmkfsを用いて簡単にサイズを変更できる。
F2FSはボリューム全体を6個のエリアに分割する。以下に記述するように、スーパーブロックエリアを除き、各エリアは複数のセグメントから構成される。 スーパーブロック (SB) パーティションの先頭に配置される。ファイルシステムが壊れないよう、２つのコピーが作られる。スーパーブロックはパーティションの基本情報とF2FSのデフォルトパラメータを持つ。 チェックポイント (CP) ファイルシステム情報、有効NAT/SIT集合のビットマップ、orphan inodeリスト、現在アクティブなセグメントのエントリーサマリーを持つ。 セグメント情報テーブル (SIT) 有効ブロック数と、全てのメインエリアブロックの有効ビットマップを持つ。 ノードアドレステーブル (NAT) メインエリアを構成するノードブロックのアドレステーブル。 セグメントサマリーエリア (SSA) メインエリアとノードブロックの所有者情報エントリーを持つ。 メインエリア ファイル、ディレクトリ、およびそれらのインデックスを持つ。 ファイルシステムとフラッシュ記憶装置の不整合を避けるため、F2FSはCPの開始ブロックアドレスをセグメントサイズ境界に配置する。また、メインエリアの開始ブロックアドレスもゾーンサイズ境界に配置する。このためにSSAにセグメントを追加確保している。
メタデータ構造 F2FSはチェックポイント(CP)を用いてファイルシステムの一貫性を保持する。F2FSはマウント時にCPエリアをスキャンし、最後に作られた有効なCPを探す。スキャンにかかる時間を短縮するため、F2FSはCPのコピーを２つしか持たない。２つのコピーのうち１つが、最後に作られた有効なCPである。この方式をシャドーコピー方式と呼ぶ。CPだけでなく、ノードアドレステーブル(NAT)とセグメント情報テーブル(SIT)にもシャドーコピー方式が使われる。ファイルシステムの一貫性を保つため、各CPは有効なノードアドレステーブル(NAT)とセグメント情報テーブル(SIT)に関連付けられる。
インデックス構造 ファイルシステムの鍵となるデータ構造は「ノード」である。伝統的なファイルシステムと同様に、F2FSも３種類のノード、すなわち、iノード(inode)、直接ノード、間接ノードを持つ。iノードブロック１つのサイズは4KBである。以下に示すように、iノードブロックは923のデータブロックインデックス、２つの直接ノードポインタ、２つの間接ノードポインタ、そして１つの二重間接ノードポインタを持つ。直接ノードブロックは1018のデータブロックインデックスを持ち、間接ノードブロックは1018のノードブロックインデックスを持つ。よって、１つのiノードブロック (すなわち一つのファイル) は以下のサイズのデータを保持できる。 4 KB × (923 + 2×1018 + 2×10182 + 10183) = 3.94 TB 全てのノードブロックの配置は、ノードアドレステーブル(NAT)によって管理される。すなわち、各ノードの配置アドレスはNATを参照して取得する。F2FSは、このインデックス構造により葉 (リーフ) に当たるデータを書き換えたときのノード情報更新範囲を限定し、木構造放浪問題(wandering tree problem)を軽減している。
ディレクトリ構造 ディレクトリエントリ (dentry) は11バイトのサイズをもち、以下の属性を持つ。 + ディレクトリエントリ構造 hash ファイル名のハッシュ値 ino inode 番号 len ファイル名の長さ type ディレクトリ、シンボリックリンクなどのファイルタイプ dentryブロックは214のdentryスロットとファイル名を持つ。各dentryが有効かどうかは、ビットマップにより管理される。dentryブロックは4KBのサイズを持ち、以下の構造を持っている。 dentry ブロック (4 K) = ビットマップ (27 bytes) + 予約域 (3 bytes) + dentryスロット (11 * 214 bytes) + ファイル名 (8 * 214 bytes) F2FSのディレクトリ構造はマルチレベルハッシュテーブルとして実装されている。以下に示すように、各レベルのハッシュテーブルは専用のハッシュバケットを複数持っている。"A(2B)"は、１つのハッシュバケットが２つのデータブロックを持つことを意味する。 定義 A ... ハッシュバケット B ... ブロック N ... MAX_DIR_HASH_DEPTH (最大ハッシュ深さ) レベル #0 A(2B) レベル #1 A(2B) - A(2B) レベル #2 A(2B) - A(2B) - A(2B) - A(2B) ... レベル #N/2 A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) ... レベル #N A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) F2FSはディレクトリの中にあるファイル名をみつけると、まずそのファイル名のハッシュ値を計算する。次にレベル#0のハッシュテーブルを走査し、そのファイル名を持つdentryとそのinodeを見つける。見つからない場合は、レベル#1のハッシュテーブルを走査する。以下同様に、各レベルのハッシュテーブルを1からNまで順次走査していく。このとき、各レベルの走査対象となるハッシュテーブルは、以下の式によって決まるテーブル１つですむ。この式の複雑さはO(log(ファイル数))である。 レベル#nにおいて走査するバケット番号 = (ハッシュ値) % (レベル#nのバケットの数) ファイル作成時には、F2FSはファイル名を格納できる連続する空エントリを探す。この空エントリの探索は、ファイル名の走査と同様に、ハッシュテーブルの全レベルについて、レベル1からNまで順次行われる。
デフォルトのブロック割り当て F2FSはメインエリアに６つのアクティブログを持つ。Hot/Warm/Coldノード、およびHot/Warm/Coldデータの６つである. + ブロック割り当てポリシー Hotノード ディレクトリの直接ノードブロック Warmノード Hotノード以外の直接ノードブロック Coldノード 間接ノードブロック Hotデータ dentryブロック Warmデータ Hotデータ、Coldデータ以外のデータブロック Coldデータ マルチメディアデータブロックと移行データブロック
F2FSの空領域管理方式は「スレディッドログ方式」と「コピーコンパクション方式」の２つである。コピーコンパクション方式は「消去処理 (クリーニング)」とも呼ばれ、空領域を常に新しいデータの書き込みに使用するため、高い順次書き込み性能を持つデバイスに適している。一方、使用率が高くなると消去処理のオーバーヘッドが大きくなるという欠点がある。対照的に、スレディッドログ方式はランダム書き込みのオーバーヘッドが大きいが、消去処理は不要である。F2FSはこれらの方式のハイブリッド方式を採用している。デフォルトの空領域管理方式はコピーコンパクション方式であるが、ファイルシステムの状態に応じて、動的にスレディッドログ方式に切り替える。
F2FSとフラッシュストレージ境界の整合を取るため、F2FSのセグメントはセクションを単位として確保される。F2FSは、セクションのサイズが、FTLのガベージコレクションの単位サイズと同じであることを仮定している。FTLの持つマッピング精度の観点から、F2FSはアクティブログの各セクションを、より多くの異なるゾーンから確保しようとする。FTLはアクティブログのデータを、FTLのマッピング精度と同じ単位で書き込むことができる。
消去処理 F2FSは、オンデマンドとバックグラウンド、両方のタイミングで消去処理を実行する。オンデマンド消去処理は、VFSコールの実行に必要な空きセグメントが足りないときに実行される。バックグラウンド消去処理は、システムアイドル時にカーネルスレッドにより実行される。
F2FSは２つの犠牲者選択ポリシー(victim selection policy)を持つ。貪欲(greedy)アルゴリズムと、費用便益(cost-benefit)アルゴリズムである。貪欲アルゴリズムでは、最小の有効ブロック数を持つセグメントが選択される。費用便益アルゴリズムでは、セグメントの寿命と有効ブロック数から対象セグメントを選択することで、貪欲アルゴリズムのスラッシング問題を避けている。F2FSは、オンデマンド消去処理に貪欲アルゴリズムを用い、バックグラウンド消去処理には費用便益アルゴリズムを用いている。
犠牲者セグメントに含まれるデータが有効かどうかを確認するため、F2FSはビットマップを管理している。このビットマップはメインエリアに含まれるブロック全体をカバーしており。各ビットは各ブロック１つが有効かどうかを示す。
製品適用 2012年、Motorola Mobility はF2FSをMoto G/E/XとDroid phoneに適用した。 2014年、GoogleはF2FSを初めてNexus 9に適用した。 その後しばらくGoogleは自社製品にF2FSを適用しなかったが、F2FSをインライン暗号化ハードウェアに対応させてPixel 3に適用した。 2016年、ファーウェイはHuawei P9にF2FSを適用した。 2016年、OnePlusはOnePlus 3TにF2FSを適用した。 2019年、ZTE はF2FSを ZTE Axon 10 Proに適用した。
脚注 注釈
出典
関連項目 フラッシュファイルシステム
外部リンク F2FS Wiki