F2FS

F2FS
開発者	サムスン電子、モトローラ・モビリティ、ファーウェイ
正式名	Flash-Friendly File System
導入	2012年12月20日 (Linux 3.8)
構造
ディレクトリ	マルチレベルハッシュテーブル
領域管理	ビットマップ (空き容量)、テーブル
限度
最大ファイルサイズ	3.94 TiB
最大ファイル数	ボリュームサイズに依存
最大ファイル名長	255バイト
最大ボリュームサイズ	16 TiB
ファイル名の文字	NUL と '/' 以外の全ての文字
特徴
タイムスタンプ	変更、属性変更、アクセス
日付分解能	1ナノ秒
属性	POSIX、拡張属性
パーミッション	POSIX、ACL
透過的圧縮	なし
透過的暗号化	あり
対応OS	Linux
	テンプレートを表示

F2FS (Flash-Friendly File System) は、サムスン電子の金載極 (朝: 김재극、英: Jaegeuk Kim) によって開発されたLinux向けのフラッシュファイルシステムである^[1]。

NANDフラッシュメモリベースのストレージ^{[注釈 1]}は、スマートフォン・タブレットからサーバまで、様々な種類のコンピュータで利用されている。F2FSはこれらのストレージの特性を考慮したファイルシステムとして設計が行われている^[2]。

F2FSはログ構造ファイルシステムを、NANDフラッシュメモリベースのストレージに適したものにして取り入れている。F2FSでは、従来のログ構造ファイルシステムの問題点であるガベージコレクションの負荷の高さなどを解消している^[1]。NANDフラッシュメモリベースのストレージではフラッシュ変換レイヤ (英: Flash Translation Layer、FTL) が実装されており、フラッシュメモリの特性^{[注釈 2]}の隠蔽とHDDのエミュレートを行い、SATAなどのインタフェースで利用ができるようにしている。F2FSはFTLの存在を前提として、NANDフラッシュメモリベースのストレージの性能を引き出すことができるように設計されている^[1]。

特徴

F2FSには、以下の機能が実装されている^[3]。

マルチヘッドログ
マルチレベルハッシュテーブル
静的/動的なホットデータとコールドデータの分離
Adaptive logging scheme
Configurable operational units
二重チェックポイント
巻き戻しと前進復帰の対応
ヒープ形式のブロック割り当て
TRIM / FITRIMのサポート
オンラインデフラグメンテーション
インライン拡張属性
インラインデータ
インラインディレクトリ
オフラインファイルシステムチェック
Atomic operations
ファイルシステム全体の暗号化
オフラインでのファイルシステムのサイズ変更
キャッシュ (コンピュータシステム)の定期的な書き込み
Extent cache
Move_file_range
Host-managed SMR
複数のデバイスに対応
Large IO submission
Disk Quota (user/group)

また、以下の機能の実装が予定されている^[3]。

FS Fuzzing (AFL)
16 TiB以上のサポート
Open-channel SSD/ lightNVM FTL
スナップショット
トランザクションのサポート
透過圧縮
Tiered storages
Reflink, copy_file_range, clone_file_range
cgroups
DAX
重複排除（英語版）
Better direct I/O
リムーバブルメディアのサポート
Windows向けデバイスドライバの開発
マルチチャネルSSD
OrangeFS（英語版）
GRUB 2への対応

設計

ディスクレイアウト

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×1018² + 1018³) = 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に適用した。^[4] その後しばらくGoogleは自社製品にF2FSを適用しなかったが、F2FSをインライン暗号化ハードウェアに対応させてPixel 3に適用した。 ^[5] 2016年、ファーウェイはHuawei P9にF2FSを適用した。^[6]^[7] 2016年、OnePlusはOnePlus 3TにF2FSを適用した。^[8] 2019年、ZTE はF2FSを ZTE Axon 10 Proに適用した。^[9]

脚注

注釈

^ SDカード・SSDなど
^ 書き込み回数の上限の存在など

出典

^ ^a ^b ^c Jaegeuk Kim (2012年10月5日). “f2fs: introduce flash-friendly file system”. 2018年4月28日閲覧。
^ Jaegeuk Kim (2016年12月3日). “start [F2FS Wiki]”. 2018年4月29日閲覧。
^ ^a ^b Jaegeuk Kim (2017年7月12日). “development [F2FS Wiki]”. 2018年4月29日閲覧。
^ Smith, Joshua Ho, Ryan. “The Google Nexus 9 Review”. www.anandtech.com. 2019年5月10日閲覧。
^ Frumusanu, Andrei (2018年11月2日). “The Google Pixel 3 Review”. www.anandtech.com. 2019年5月11日閲覧。
^ Larabel, Michael (2018年12月28日). “F2FS Gets More Fixes In Linux 4.21 With The File-System Now Supported By Google's Pixel”. www.phoronix.com. 2019年5月10日閲覧。
^ Humrick, Matt (2017年5月12日). “Huawei P10 and P10 Plus”. www.anandtech.com. 2019年5月11日閲覧。
^ Chester, Brandon. “The OnePlus 3T Review”. www.anandtech.com. 2019年5月10日閲覧。
^ “ZTE Axon 10 Pro Officially Uncovered: The First To Use F2FS” (英語). Gizchina.com (2019年5月6日). 2019年5月10日閲覧。

外部リンク

F2FS Wiki

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

この項目は、ソフトウェアに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[2] SDカード・SSDなど

[4] 書き込み回数の上限の存在など

[lwn.net_518718-1] Jaegeuk Kim (2012年10月5日). “f2fs: introduce flash-friendly file system”. 2018年4月28日閲覧。

[3] Jaegeuk Kim (2016年12月3日). “start [F2FS Wiki]”. 2018年4月29日閲覧。

[development-5] Jaegeuk Kim (2017年7月12日). “development [F2FS Wiki]”. 2018年4月29日閲覧。

[6] Smith, Joshua Ho, Ryan. “The Google Nexus 9 Review”. www.anandtech.com. 2019年5月10日閲覧。

[7] Frumusanu, Andrei (2018年11月2日). “The Google Pixel 3 Review”. www.anandtech.com. 2019年5月11日閲覧。

[8] Larabel, Michael (2018年12月28日). “F2FS Gets More Fixes In Linux 4.21 With The File-System Now Supported By Google's Pixel”. www.phoronix.com. 2019年5月10日閲覧。

[9] Humrick, Matt (2017年5月12日). “Huawei P10 and P10 Plus”. www.anandtech.com. 2019年5月11日閲覧。

[10] Chester, Brandon. “The OnePlus 3T Review”. www.anandtech.com. 2019年5月10日閲覧。

[11] “ZTE Axon 10 Pro Officially Uncovered: The First To Use F2FS” (英語). Gizchina.com (2019年5月6日). 2019年5月10日閲覧。

[1]

[注釈 1]

[2]

[注釈 2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

特徴

設計