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