|
F2FS
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]。
また、以下の機能の実装が予定されている[3]。 設計ディスクレイアウトF2FSはボリューム全体を多数のセグメントに分割する。各セグメントのサイズは2MB固定である。連続する複数セグメントをまとめてセクションが定義され、セクションの集合としてゾーンが定義される。デフォルト設定では、セクションとゾーンは同じサイズに設定されるが、ユーザは F2FSはボリューム全体を6個のエリアに分割する。以下に記述するように、スーパーブロックエリアを除き、各エリアは複数のセグメントから構成される。
ファイルシステムとフラッシュ記憶装置の不整合を避けるため、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バイトのサイズをもち、以下の属性を持つ。
dentryブロックは214のdentryスロットとファイル名を持つ。各dentryが有効かどうかは、ビットマップにより管理される。dentryブロックは4KBのサイズを持ち、以下の構造を持っている。 dentry ブロック (4 K) = ビットマップ (27 bytes) + 予約域 (3 bytes) +
dentryスロット (11 * 214 bytes) + ファイル名 (8 * 214 bytes)
F2FSのディレクトリ構造はマルチレベルハッシュテーブルとして実装されている。以下に示すように、各レベルのハッシュテーブルは専用のハッシュバケットを複数持っている。"A(2B)"は、１つのハッシュバケットが２つのデータブロックを持つことを意味する。
レベル #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データの６つである.
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] 脚注注釈出典
関連項目外部リンク
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
