F2FS

F2FS
開発かいはつ者しゃ	サムスン電子でんし、モトローラ・モビリティ、ファーウェイ
正式せいしき名めい	Flash-Friendly File System
導入どうにゅう	2012年ねん12月がつ20日はつか (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向むけのフラッシュファイルシステムである。

NANDフラッシュメモリベースのストレージは、スマートフォン・タブレットからサーバまで、様々さまざまな種類しゅるいのコンピュータで利用りようされている。F2FSはこれらのストレージの特性とくせいを考慮こうりょしたファイルシステムとして設計せっけいが行おこなわれている。

F2FSはログ構造こうぞうファイルシステムを、NANDフラッシュメモリベースのストレージに適てきしたものにして取とり入いれている。F2FSでは、従来じゅうらいのログ構造こうぞうファイルシステムの問題もんだい点てんであるガベージコレクションの負荷ふかの高たかさなどを解消かいしょうしている。NANDフラッシュメモリベースのストレージではフラッシュ変換へんかんレイヤ (英えい: Flash Translation Layer、FTL) が実装じっそうされており、フラッシュメモリの特性とくせいの隠蔽いんぺいとHDDのエミュレートを行おこない、SATAなどのインタフェースで利用りようができるようにしている。F2FSはFTLの存在そんざいを前提ぜんていとして、NANDフラッシュメモリベースのストレージの性能せいのうを引ひき出だすことができるように設計せっけいされている。

特徴とくちょう

F2FSには、以下いかの機能きのうが実装じっそうされている。

• マルチヘッドログ
• マルチレベルハッシュテーブル
• 静的せいてき/動的どうてきなホットデータとコールドデータの分離ぶんり
• 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)

また、以下いかの機能きのうの実装じっそうが予定よていされている。

• 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×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