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まで順次行われる。

デフォルトのブロック割り当て

At runtime, F2FS manages six active logs inside the "Main Area:" Hot/Warm/Cold node and Hot/Warm/Cold data.

Block allocation policy
Hot node	Contains direct node blocks of directories.
Warm node	Contains direct node blocks except hot node blocks.
Cold node	Contains indirect node blocks.
Hot data	Contains dentry blocks.
Warm data	Contains data blocks except hot and cold data blocks.
Cold data	Contains multimedia data or migrated data blocks.

LFS has two schemes for free space management: threaded log and copy-and-compaction. The copy-and-compaction scheme which is known as cleaning, is well-suited for devices showing very good sequential write performance, since free segments are served all the time for writing new data. However, it suffers from cleaning overhead during high utilization. Conversely, the threaded log scheme suffers from random writes, but no cleaning process is needed. F2FS adopts a hybrid scheme where the copy-and-compaction scheme is adopted by default, but the policy is dynamically changed to the threaded log scheme according to the file system status.

In order to align F2FS with underlying flash-based storage, F2FS allocates a segment in a unit of a section. F2FS expects the section size to be the same as the garbage collection unit size in FTL. With respect to the mapping granularity in FTL, F2FS allocates each section of the active logs to as many different zones as possible. FTL can write the active log data into one allocation unit according to its mapping granularity.

消去処理

F2FS does cleaning both on demand, and in the background. On-demand cleaning is triggered when there are not enough free segments to serve VFS calls. The background cleaner is executed by a kernel thread, and triggers the cleaning job when the system is idle.

F2FS supports two victim selection policies: greedy, and cost-benefit algorithms. In the greedy algorithm, F2FS selects a victim segment having the smallest number of valid blocks. In the cost-benefit algorithm, F2FS selects a victim segment according to the segment age and the number of valid blocks in order to address the log block thrashing problem present in the greedy algorithm. F2FS uses the greedy algorithm for on-demand cleaning, the background cleaner uses the cost-benefit algorithm.

In order to identify whether the data in the victim segment are valid or not, F2FS manages a bitmap. Each bit represents the validity of a block, and the bitmap is composed of a bit stream covering whole blocks in the Main Area.

脚注

注釈

^ 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日閲覧。

外部リンク

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日閲覧。

[1]

[注釈 1]

[2]

[注釈 2]

[3]

特徴

設計