# SFS: Random Write Considered Harmful in Solid State Drives > [!abstract] 概要 > 過去 10 年にわたるフラッシュ型ソリッドステートドライブ(SSD)の絶え間ない技術改善により、SSD は性能や消費電力といった点でハードディスクドライブ(HDD)に対し多くの利点を持つ二次記憶装置となった。しかし、SSD のランダム書き込み性能は依然として懸念事項である。最新の SSD でさえ、ランダム書き込み帯域と逐次書き込み帯域の差は 10 倍以上ある。さらに、ランダム書き込みは 1 書き込みあたりの NAND ブロック消去回数を増やすため、SSD の限られた寿命を縮めうる。ランダム書き込みに起因するこれらの問題を克服するため、本論文は SSD 向けの新しいファイルシステム SFS を提案する。第 1 に、SFS はログ構造化のアプローチを取ることで SSD の最大書き込み帯域を引き出す。SFS はファイルシステム層のすべてのランダム書き込みを、SSD 層では逐次書き込みに変換する。第 2 に、SFS はセグメントクリーニング時の既存のデータ分離戦略の代わりに、書き込み時の新しいデータグルーピング戦略を採る。更新確率の近いデータブロックを同じセグメントに入れる。これによりセグメント使用率が鋭い二峰分布を形成でき、あらゆるログ構造化ファイルシステムに避けがたいセグメントクリーニングのオーバーヘッドを最小化する。Linux 系の NILFS2 を改造して SFS のプロトタイプを実装し、現実的な複数のワークロードで 3 つの最先端ファイルシステムと比較した。SFS はスループットで従来の LFS を最大 2.5 倍上回る。加えて、ext4 や btrfs のような現代のファイルシステムと比べ、SSD 内のブロック消去回数を最大 7.5 倍削減する。 ## 論文情報 - 著者: [[Changwoo Min]]・[[Kangnyeon Kim]]・[[Young Ik Eom]]・[[Sang-Won Lee]]は[[Sungkyunkwan University]]、[[Hyunjin Cho]]は[[サムスン電子 (Samsung Electronics)]]。所属は論文の脚注記号に基づく。 - 掲載: FAST 2012(10th USENIX Conference on File and Storage Technologies)。 - 実装: Linux カーネル 2.6.37 上の [[NILFS2]] を改造した [[SFS (SSD向けファイルシステム)]]。 ## 概要 [[SFS (SSD向けファイルシステム)]] は、[[ログ構造化ファイルシステム]]の枠組みで SSD のランダム書き込み問題を解く。SSD 内の変換層(FTL)による最適化は、論理ブロックアドレス(LBA)だけを見て動くため、更新ごとに新しい LBA へ書く上書きなし型ファイルシステムでは効きにくい。そこで著者らは、ファイルブロック単位のホットネス(更新確率の指標)をファイルシステム側で測り、(1)ログ構造化でランダム書き込みを逐次化し、(2)書き込み時にホットネスの近いブロックを同じセグメントへ先行グルーピングし、(3)反復セグメント量子化でグループ境界を決め、(4)コストホットネス方針でクリーニング対象を選ぶ。TPC-C・RES・合成ワークロードで、LFS 比の書き込みコスト削減とスループット向上、ext4・btrfs 比の消去回数削減を示した。 ## 問題設定 - SSD の普及を妨げる課題は、寿命の限りと、ランダム書き込み性能の低さの 2 つである。NAND フラッシュの書き換え可能回数は直近 2 年で 10K から 5K へ落ちたとされる。 - ランダム書き込みは SSD 内部の断片化を招き、性能を桁違いに落とす。断片化の影響はランダム書き込みを止めた後もしばらく残る。データページのコピーと消去が増えるため寿命も縮む。 - FTL 側の改善(マッピング効率化、ホット・コールド分離)は LBA だけを根拠にする。btrfs・ZFS・WAFL のような上書きなし型では、同じファイルブロックの更新でも毎回新しい LBA が来るため、FTL はホットネスを見抜けない。 - データベース向けのフラッシュ対応ストレージ方式は、特定用途にしか効かない。 ## 提案手法 ### 設計原則 論文は 3 つの設計原則を掲げる。 1. LBA を超えて、ファイルブロック単位の統計(ホットネス)を直接使う。 2. ログ構造化により、ランダム書き込みを SSD への逐次書き込みへ変える(書き込み帯域の最大化)。 3. セグメントクリーニング時の遅延分離ではなく、書き込み時にホットネスで先行グルーピングし、二峰性を強める。 背景として、SSD は複数チャネルの NAND を束ね、書き込みをクラスタ化ページ、消去をクラスタ化ブロック単位で並列実行する。書き込み要求がクラスタ化ブロックの倍数でそろうと、ハイブリッド FTL では最小コストのスイッチマージ、ページ単位 FTL では有効ページのないブロックを回収でき、ランダム書き込みが逐次書き込みに近づく。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig01-seq-vs-rand-throughput.png]] 図1(Figure 1): 3 種の SSD での逐次書き込みとランダム書き込みのスループット(要求サイズ別)。ランダム書き込みは要求サイズが 16 MB 前後(SSD-M は 32 MB)に達してはじめて逐次書き込みに追いつく。エージング後の持続性能で測る。 | 略称 | 機種 | 容量 | 接続 | セル | 逐次書き込み最大(MB/s) | 4 KB ランダム書き込み(MB/s) | 価格($/GB) | |---|---|---|---|---|---|---|---| | SSD-H | Intel X25-E | 32 GB | SATA | SLC | 170 | 5.3 | 14 | | SSD-M | Samsung S470 | 64 GB | SATA | MLC | 87 | 0.6 | 2.3 | | SSD-L | Transcend JetFlash 700 | 32 GB | USB 3.0 | MLC | 38 | 0.002 | 1.4 | 表1(Table 1、抜粋): 評価に用いた 3 種のフラッシュデバイス。逐次読み出し最大は 216.9 / 212.6 / 69.1 MB/s、4 KB ランダム読み出しは 13.8 / 10.6 / 5.3 MB/s。価格は 2011 年 9 月の定価。 ワークロードの偏りは、先行グルーピングの前提となる。書き込みの 90% がブロックの 1% に集中する例など、複数の先行研究が示す偏りを、著者らが取った TPC-C のトレースと RES・WEB のトレースで確認している。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig02-cumulative-write-frequency.png]] 図2(Figure 2): 3 つの実ワークロード(TPC-C、RES、WEB)の累積書き込み頻度分布。少数のブロックに書き込みが集中する。 ### アーキテクチャ SFS の中核動作は、セグメント書き込み、セグメントクリーニング、読み出し、クラッシュ回復である。読み出しは既存のログ構造化ファイルシステムと同じである。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig03-writing-and-cleaning-overview.png]] 図3(Figure 3): SFS の書き込み過程とセグメントクリーニングの概観。ダーティブロックをホット・ウォーム・コールド・読み出し専用の 4 群へ分類し、群ごとにセグメントを満たす。 ### ホットネスの定義 - ブロックのホットネス Hb = 書き込み回数 Wb ÷ 経過時間(現在時刻 T − 最終更新時刻)。新規ブロック(Wb = 0)は所属ファイルのホットネス Hf を継承する。 - ファイルのホットネス Hf = ファイル作成後のブロック更新回数 Wf ÷ (T − ファイルの最終更新時刻)。 - セグメントのホットネス Hs は有効ブロックの平均ホットネスだが、全ブロックの生存判定は高価なので、有効ブロックの時刻総和と書き込み回数総和を保持して近似する(書き込み回数の平均 ÷ 経過時間の平均)。ブロック無効化のたびに総和から差し引く。 ### 反復セグメント量子化 ホットネスの範囲を k 個の区間へ分け、各群の代表値を決める。等幅分割や等高分割は、ほとんどのセグメントがホットでない分布(TPC-C を使用率 70% で走らせた例)では群を正しく表せない。そこで統計学のクラスタリングに倣い、各セグメントを最も近い群へ割り当て、群の平均を新しい代表値にする反復を、収束するか最大 3 回まで行う。代表値はスーパーブロックに保存し、マウント時に読み込んで収束を早める。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig04-segment-quantization.png]] 図4(Figure 4): セグメント量子化の例。セグメントのホットネス順位に対し、ホット・ウォーム・コールド・読み出し専用の 4 群を割り当てる。 ### セグメント書き込み 書き込みは(a)5 秒ごとの定期書き出し、(b)フラッシュデーモンの要求、(c)セグメントクリーニング、(d)fsync・sync で起動する。手順は、代表値の更新、ダーティブロックのホットネス算出、最寄りの群への割り当て、群がセグメントを満たす大きさになった時点での書き出しである。満たない群は書き出しを遅らせる。fsync・sync・チェックポイントでは、群単位で書けるだけ書き、残りを群に関係なく書く。書き込みは整列した大きな逐次要求になる。 クリーニング中のブロックの書き出しが遅れると、元のセグメントが上書きされた後のクラッシュで失われうる。そこで空きセグメントを最も古く解放された順(LRF)で割り当て、次に割り当てるセグメントを元とする未書き出しブロックがあるときは、群に関係なく現セグメントへ書く。これで未書き出しブロックは必ずディスク上にコピーを持つ。 ### セグメントクリーニングとコストホットネス方針 クリーニングは、犠牲セグメントの選択、有効ブロックのページキャッシュへの読み込みとダーティ化、書き込み処理の起動の 3 段である。有効ブロックは通常のブロックと同じく、ホットネスで群へ振り分けられる。 犠牲の選択は、貪欲方針(有効ブロックが最少)やコストベネフィット方針(同数ならコールドを優先し、最終更新時刻を更新確率の代理にする)を拡張したコストホットネス方針を使う。式は「生成される空き領域 ÷ (コスト × セグメントのホットネス) = (1 − Us) / (2 Us Hs)」で、Us はセグメント使用率、コスト 2 Us は有効ブロックの読み出しと書き戻しである。セグメント使用情報は 48 バイト/セグメントで SUFILE に持つ。クリーナーはディスク使用率が 95% を超えると起動し、一度に最大 3 セグメント(96 MB)を処理する。 ### クラッシュ回復 チェックポイント方式で、クラッシュ後は最終チェックポイントへ巻き戻す。チェックポイントは、(a)前回から 30 秒ごと、(b)20 セグメント(640 MB)超の書き込み、(c)sync・fsync、(d)アンマウントで作る。スーパーブロックは 2 つの物理ブロックへ交互に書き、再マウント時に新しいほうを使う。 ## 新規性 - ファイルシステム層でホットネス(書き込み回数 ÷ 経過時間)を管理し、書き込み時にブロックを先行グルーピングする点。従来の LFS はクリーニング時に遅延して分離していた。 - ホットネス分布に合わせてグループ境界を決める反復セグメント量子化と、ホットネスを取り込んだコストホットネス方針。 - FTL の LBA ベース最適化に依存せず、セグメントサイズをクラスタ化ブロックの倍数に合わせることで、SSD 内のランダム書き込み性能の差を吸収する設計。 ## 実験設定 - 実装: [[NILFS2]] を改造。連続スナップショットを削除し、ブロックごとの書き込み回数と最終更新時刻(各 8 バイト)を DAT エントリに持つ。メタデータの実行時オーバーヘッドは 5〜10%。Linux 2.6.37、Core i5 2.67 GHz 4 コア、メモリ 4 GB。 - デバイス: 表1 の SSD-H・SSD-M・SSD-L。セグメントサイズは 32 MB。 - ワークロード: 実トレースは TPC-C(Oracle 11g)と RES(UC Berkeley の 13 台のデスクトップを 113 日追跡)。合成は Zipf 分布と一様ランダム。一様ランダムは偏りがなく、SFS には最悪ケースである。トレースは単一スレッドで可能な限り速く再生する。 - 使用率: 空きを埋めるダミーブロックを先に書いて、40〜90% の使用率を作る。 - 書き込みコスト Wc = (Wcnew + Rcsc + Wcsc) ÷ Wcnew。新データの書き込みコストに、クリーニングによる読み書きの暗黙のコストを加えた比である。 - 他方式との比較: LFS-CB(コストベネフィット方針の LFS)、ext4(その場更新)、btrfs(上書きなし。SSD モードと nodatacow の 2 設定)。8 GB の書き込みを、20 GB のエージング後に計測した。書き込み増幅と消去回数は、blktrace で取ったトレースを FTL シミュレータ(FAST 方式とページ単位方式、32 GB、4 KB ページ、512 KB ブロック、余剰 10%)で再生して求めた。 ## 実験結果 ### 各手法の寄与(SSD-M、使用率 85%) ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig05-write-cost-vs-groups.png]] 図5(Figure 5): 群の数と書き込みコスト。群を 1 個(グルーピングなし)にすると Zipf で 6.96、TPC-C で 5.98 と高い。2〜3 群ではほとんど下がらず、4 群で 4.21 と 2.64 へ下がる。5 群以上は効果が小さく、書き出しの遅延で群外書き込みが増えるため逆効果にもなりうる。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig06-quantization-schemes.png]] 図6(Figure 6): 量子化方式ごとの書き込みコスト(4 群)。等幅分割は反復量子化に対し Zipf で 143%、TPC-C で 192%、等高分割は 115% と 135% になる。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig07-cleaning-policy.png]] 図7(Figure 7): クリーニング方針ごとの書き込みコスト。コストホットネスはコストベネフィットより TPC-C・Zipf の両方で約 7% 低い。 ### LFS との比較(SSD-M) ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig08-write-cost-vs-utilization.png]] 図8(Figure 8): ディスク使用率と書き込みコスト(SFS 対 LFS-CB)。使用率が高いほど SFS の優位が広がる。 - 使用率 90% で書き込みコストは TPC-C が 77.4%、一様ランダムが 27.9% 減る。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig09-throughput-vs-utilization.png]] 図9(Figure 9): ディスク使用率とスループット(SFS 対 LFS-CB)。使用率 90% で TPC-C は 151.9%、一様ランダムは 18.5% 向上する。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig10-segment-utilization-distribution.png]] 図10(Figure 10): セグメント使用率の分布(ディスク使用率 70%)。偏りのない一様ランダム以外で、SFS は明確な二峰分布になる。図10a の例では、SFS は使用率 10% のセグメントを選べるのに対し、LFS-CB は 30% で、コピー量は 3 分の 1 になる。 ### デバイス差と他ファイルシステムとの比較 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig11-throughput-across-ssds.png]] 図11(Figure 11): 3 種の SSD での SFS のスループット。SSD-H は SSD-L より価格が 10 倍高く、逐次書き込みが 4.5 倍速く、4 KB ランダム書き込みが 2,500 倍以上速いが、SFS の性能を決めるのは逐次書き込み性能である。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig12-throughput-filesystems.png]] 図12(Figure 12): ファイルシステム別スループット(SSD-M、使用率 85%)。SFS の平均スループットは LFS-CB の 1.6 倍、btrfs の 7.3 倍、btrfs-nodatacow の 1.5 倍、ext4 の 1.5 倍である。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig13-write-amplification.png]] 図13(Figure 13): FTL 方式(FAST とページ単位)ごとの書き込み増幅。ログ構造化の SFS と LFS-CB は平均で FAST 1.1、ページ単位 1.0 と低い。その場更新の ext4 と btrfs-nodatacow は 5.3 と 2.8、btrfs は 2.8 と 1.2 である。 ![[wiki/sources/_attachments/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives/fig14-erase-counts.png]] 図14(Figure 14): FTL 方式ごとのブロック消去回数。LFS-CB は SFS より合計 20% 多い。ext4 は FAST で 3.1 倍、ページ単位で 1.8 倍、btrfs-nodatacow は 3.4 倍と 2.0 倍、btrfs は 6.1 倍と 3.8 倍(最悪ケースで 7.5 倍)である。 ## 考察 - 上書きなし型の btrfs は書き込み増幅が低くても、コピーオンライトと断片化の管理によるファイルシステム側の書き込み要求が多く、消去回数が最大になる。その場更新型は書き込み増幅の高さが消去回数に直結する。 - 上書きなし型ではランダム書き込みが繰り返されると、ブロックが任意の位置へ散り、LBA 層では全 I/O がランダムになる。デフラグはセグメントクリーニングに似たブロック移動を伴う。 - ログ構造化ファイルシステムでは、セグメントをクラスタ化ブロックに整列させれば書き込み増幅は最小になり、残る主要な負荷はセグメントクリーニングである。SFS はそれを大幅に減らす。 - SFS の性能は SSD のランダム書き込み性能に依らず、逐次書き込み性能に律速される。中位・低位の SSD でも、逐次書き込みが速ければ高い性能を出せる。 - 関連手法との位置づけ。FTL 側(FAST、LAST、DAC、DFTL)は LBA 依存で上書きなし型に弱い。HDD 向けのログ構造化最適化(ホールプラギング、WOLF、HyLog)は HDD の性能特性を前提にする。組み込み向けのフラッシュ用ファイルシステム(JFFS2、YAFFS2、UBIFS)は、ウェアレベリングを組み込んだ順番制のクリーニングを使う。 - 今後の課題は HDD への適用である。手法はデバイスに依存せず、予備実験で有望な結果を得ている。 ## 強み / 弱点・課題 - 強み: 設計原則が SSD の実測特性(クラスタ化ブロックと要求サイズ)に根拠づけられている。3 種の SSD、4 種のワークロード、3 種の比較対象と、書き込みコストの内訳から消去回数まで一貫して評価している。 - 強み: 効果の機序(二峰分布)を分布図で直接示している。 - 弱点: 評価は単一スレッドの最大速度での再生で、実アプリケーションの並行性を反映しない。書き込みコストと消去回数は一部が再生とシミュレータによる。 - 弱点: 偏りのないワークロードでは効果が小さい。群の数は 4 で固定し、他の値の一般性は限定的な検証にとどまる。 - 弱点: 連続スナップショットを削除しており、NILFS2 の機能を一部犠牲にしている。書き込み回数と時刻を保持するメタデータのオーバーヘッドが 5〜10% ある。 - 弱点: 中位・低位の SSD で有利になる主張は、逐次書き込み性能が十分に高いことが前提である。 ## 関連 - 概念: [[ログ構造化ファイルシステム]] / [[SSD書き込み増幅]] / [[ローカルファイルシステム実装比較]] / [[ゾーン名前空間SSD]] / [[LSMツリー]] - エンティティ: [[SFS (SSD向けファイルシステム)]] / [[NILFS2]] / [[Changwoo Min]] / [[Kangnyeon Kim]] / [[Hyunjin Cho]] / [[Sang-Won Lee]] / [[Young Ik Eom]] / [[Sungkyunkwan University]] / [[サムスン電子 (Samsung Electronics)]] ## 出典 - [[.raw/papers/2012__FAST__SFS-random-write-considered-harmful-in-solid-state-drives.pdf]]