Application Crash Consistency and Performance with CCFSを読んだ

FOLIOアドベントカレンダー 9日目です。 昨日は quantroさんの バリュー投資とかグロース投資とかの整理 でした。

NewSQLを調べつつ最近はストレージ周りにも手を出してみたいバックエンドエンジニアの @matsu_chara です。

今回はFAST '17のBest PaperであるApplication Crash Consistency and Performance with CCFS を読んだので紹介や感想を書きたいと思います。 自分が面白いと思ったところを中心にしたり、個人的に調べた内容が入っていたりするので正確かつ完全な情報は上記論文や関連文献等を直接読んでいただければと思います。

ざっくり

アプリケーションレベルでのCrash Consistencyの正確性を向上させるための仕組みを持ったファイルシステム CCFS(Crash-Consistent File System)の提案です。

重要な情報や機能を持ったアプリケーションでは突然の電源断やカーネルのバグなどによるクラッシュに対してロバストであることが求められます。（例：DBのトランザクション）

ところがアプリケーションレベルでは、クラッシュに備えた処理に問題がある実装がよくあります。1 これらの間違った実装による影響はファイルシステムの振る舞いによっては影響を軽減したり、無くしたりすることが出来ます。2

ファイルシステムでクラッシュを考える際は、処理のatomicityとorderingが重要となります。

一貫性の観点からは、この２つが保証されていることが重要です。 このうち、atomicityについては既存のファイルシステムでも上手くサポートされています。

しかしorderingを保証しようとすると性能上のボトルネックになることがあるため、モダンなファイルシステムでは強力な保証は行わず制約を緩めていることが多いです。

例えばext4, xfs, btrfsなどではwriteの順番を並べ替えることがありますし、btrfsではディレクトリ操作の順番が入れ替わることがあります。

このような順序の入れ替えはシーク時間の削減につながるなど性能の面では有意義です。 一方でアプリケーションから見ると、書き込み順が入れ替わることにより生じる問題をケアすることが求められるため、誤った実装をしてしまいやすくなるという問題があります。

書き込み順の入れ替わりによって生じる問題の多くはテストが難しく、設定によっては正しくリカバリーされない実装のアプリケーションが多く存在します。

本論文では性能とordering保証を両立させるための鍵となるStream abstractionと、Stream abstractonを実装したファイルシステムであるCCFSが提案されています。

Stream abstractonの特長は以下のようなものです。

  • ファイルシステムレベルのorderingを少ないオーバーヘッドで提供
  • ユーザーコードの変更を最小限に抑えて利用を開始可能
  • さらにコードを変えると、さらなる性能を得られるといった柔軟性

CCFSの特長は以下です。

  • ext4をベースにStream abstractionを実装したファイルシステム
  • ext4と比べ遜色ない高性能を達成
  • アプリケーションに対し、より強力なcrash consistencyを提供

Background

前述したとおり、クラッシュを考慮する際のファイルシステムの性質を考える上ではatomicityとorderingの2つが重要となります。

一口にatomicity, orderingと言っても、「atomicityはシステムコールレベルで？セクタレベルで？」、「orderingはメタデータのみ？それとも全て？」といった議論すべき点がいくつかあります。

次のセクションでは、どのようなatomicity, orderingが適切かを検討していきます。

理想的な挙動

論文では"ordering", “weak atomicity”が達成されていれば、既存のアプリケーションの大部分が上手くリカバリーできるだろうとされています。(The Ordering Hypothesis)

この仮説は具体的には以下のようになります。

  • 全てのファイルシステムに対する更新はin-orderで行われる(ordering)
  • 書き込みはセクタ単位でatomicに、その他は全てatomicに行われる。(weak atomicity)

これらの制約はアプリケーションで考えなければいけない状態の数を制限するために存在します。

例えば Nセクタに対する更新がある場合、orderingとweak atomicityがあればクラッシュ時に取りうる状態はNです。 一方で並べ替えがある場合、クラッシュ時に取りうる状態は一気に 2N まで増加します。

実際のファイルシステムを見てみると、ext4, btrfs, xfsなどのモダンなファイルシステムでは"weak atomicity"については既に提供されています。 一方でorderingについての保証は稀です。(ext4, ext3のData-journaling modeでは提供されている） 保証が稀なのはorderingの保証を行うことによって性能が減ってしまうことに起因しています。

performance overhead

orderingを保証する場合の性能低下の原因としてFalse ordering dependenciesが挙げられます。

次節ではこのFalse ordering dependenciesについて検討していきます。

False ordering dependencies

例えば全く関係のないApplication A, Application Bが同時に動いているとします。 この時、以下のような動作が順番に起こることを想定します。

  1. Application Aで数百MB程度の大きなwriteがある
  2. Application Bで数Byte程度の小さいwriteを行った後、fsyncを行う

Application Bは通常一瞬でfsyncが終わりますが、orderingがグローバルに保証されているファイルシステムではApplication Aのwriteが終わるまで書き込みを開始することが出来ません。 そのため、結果として長い時間がかかってしまいます。

一方でApplication Bの一貫性の観点からはApplication Aの書き込みを待つ必要はありません。 たしかにApplication Aの書き込みのほうが順番としては早いですが、この２つはそもそも関係のないアプリケーションなのでそれぞれの書き込み順序の保証は本来不要のはずです。

このような不要な順序依存がFalse ordering dependenciesの正体です。 グローバルに順序を保証するファイルシステムではこのような不要な順序依存があちこちで起こってしまい性能が低下してしまいます。3

Stream abstraction

このような性能低下を防ぐために、Stream という概念を導入します。

具体的にはまず、各アプリケーションで行われる更新をいくつかのStreamに分割します。 そして、１つのStreamの中での更新は全て順序どおりに行われることを保証します。

例えば先程の例で、Application AではStream A, Application BではStream Bを使うと言った具合にStreamを分割します。 順序が保証されるのは同一Streamの中だけであるため、Stream Aが大きなデータをwriteしていても、Stream Bが順番待ちになることはありません。

このようにアプリケーション側でFalse ordering dependenciesを回避できるようにするための仕組みがStreamです。

Streamを作成するためには set_stream() を利用します。 Streamを利用するプログラムが既存のコードと異なる点は writeの前に set_stream(A) や set_stream(B) を呼び出す点だけです。 set_streamを呼び出すと、その後の更新は全て指定したStreamに含まれるようになります。4

基本的にはアプリケーション起動時に、そのアプリケーション用のStreamを作成することで不要な順序依存をある程度取り除くことが可能です。 また、Streamはアプリケーション内に複数存在しても良いので、例えばスレッドごとにStreamを割り当てたり、一つのスレッドがStreamを切り替えたりするような最適化も可能です。

この柔軟性により、「粒度の大きいStreamを用意することにして既存のコードは殆ど変えずに安全性を保証したい」といった要求や「細粒度のStreamを用意して適宜使い分けて性能を向上させたい」といった要求など、様々なケースに対応出来るようになります。

CCFS

CCFSはext4のdata-journaling modeをベースに上記のStreamの概念が取り入れられたファイルシステムです。

ext４のjournaingではメモリ上に "Running Transaction", ディスク上に"journal"を保持します。 更新はRunning Transactionに保存され、コミット時にjournalに保存されます。

CCFSではTransactionの保存領域をStreamごとに分け、コミット時にはStream単位でjournalに格納します。 このようにすることで、全ての更新の順序を保存するのではなくStreamごとに順序を保証することが可能になります。5

Evaluation

実装の試験としてext4とCCFSの比較が載っています。

まず、クラッシュ時の挙動に関する試験です。 ext4とCCFSで発見された問題は以下のようになります。

ext4では９個の問題が発見されましたが、CCFSでは2つ(Mercurialでdirstateが破損）に留められました。

ext4 CCFS
LevelDB 1 0
SQLite-Roll 0 0
Git 2 0
Mercurial 5 2
ZooKeeper 1 0

また性能面での試験も行われています。 詳細は割愛しますが性能面も同等レベルになっています。 性能比較の結果は論文Figure 6などを参照してください。

まとめ

streamごとの順序を保証することでアプリケーションを堅牢に保つCCFSを紹介しました。 本記事ではあっさりした内容になっていますが、論文ではStreamを導入したときの様々な最適化について詳細が記してあります。それらを紹介しようとするとext4で行われている最適化についても述べる必要があり、記事が長大になってしまうので割愛しました。 Block Level Journalingやdelta journaling、Pointer-less data structuresなどの面白い要素がたくさん紹介されているのでぜひ論文を読んでいただければ幸いです。

  1. 例えばファイルシステムは書き込みの順番を入れ替えることがありますがアプリケーションレベルでのfsyncによる制御などが順序の入れ替えを考慮しきれていない場合に間違った実装となります。この場合クラッシュしたタイミングによってはアプリケーションが起動しないなどの問題に発展する可能性があります。 詳細は https://www.usenix.org/node/186195 で。↩

  2. filesystemの種類・設定で決まります。最悪ケースでは60種の問題が発見されるようなテストでも、良い種類・設定では10種に収まったという結果が論文で報告されています。↩

  3. 不要な順序依存の他にも、順序入れ替えによる最適化が行えないといった問題もあります。CCFSには、これらについての工夫もたくさん取り込まれていますが今回は割愛しています。↩

  4. 後方互換性を保つためにset_streamは古いファイルシステムに対しては何もしません。そのためstreamが導入されたアプリケーションは古いファイルシステムでも正常に動作します。（もちろんその場合は順序の保証は行われません）↩

  5. 同じブロックを異なるStreamで同時に更新した場合にどうするのかみたいな話はあるのですが、その辺はがっつり省いています。気になる方は論文をお読みください。↩