はじめに
この記事はシステム系論文紹介 Advent Calendar 2014のものです。
USENIX FAST '14というファイルシステムとストレージのカンファレンスでBest paper awardを獲得したLog-structured Memory for DRAM-based Storageという論文の紹介を行います。ここ数年のUSENIXの学会の多くはプレゼンのビデオを公開しており、この発表も例外ではありません。参考にどうぞ。むしろ英語がある程度できる人はこの記事を読むよりそっちを観た方がいいかも。
概要
DRAM上にファイルシステムを実装する時、安直にmallocやfreeを使ったりすると必要以上にメモリを消費するそうです。この論文はメモリ消費量を削減するために、DRAM向けログファイルシステムを実装したというお話です。
DRAM上にファイルシステムを使う理由
この論文はRAMCloudチームの論文で、RAMCloudに実装することをユースケースとしています。RAMCloudの説明は、偶然にも@suma90hさんのRaftの紹介記事で行われているので省略しますが、「全てのデータをメモリ上で読み書きを行い、特定のタイミングでディスク上にフラッシュする分散ファイルシステム」とだけ。
なぜmallocじゃダメなのか
malloc等を使ってメモリを動的に確保したり開放したりするアプリケーションを想定します。アプリケーションが10GBのデータしか確保していないとすれば、DRAMは(OSレベルで見ても)10GBしか消費されないというのが理想だと思われます。しかし、データを小さなブロック単位(100バイトとか)で10GB分確保し、その一部を開放、その後もう少し大きな(10KBとか)で確保し直すといった、ファイルシステムではよくある挙動をシミュレートするとglibcのmallocでDRAMは(OSから見れば)20GB程度消費してしまいます。これは断片化が発生したためです。デフラグすればいいだけの話なのですが、メモリの消費量を抑えつつデフラグを行う方法は既存の研究では存在しておりません。
DRAMがある程度以上消費されたら、アプリケーションを一時的に止めてデフラグを行うという方法がありますが、この方法ではアプリケーションを秒単位で止めてしまう(いわゆるStop the world)ことになることがあるので適切な方法とはいえません。
目標
RAMCloudを想定し、DRAM上にファイルシステムを実装するためのSTWのないデフラグを実装することを目標とします。今回はデフラグ処理をインクリメンタルなものとするために、DRAM上に展開するファイルシステムをLog-structuredにしました。
ログの記録方法
ある程度の大きさ(本研究だと8MB)のセグメントというものがDRAM上にあります。ログはそのセグメントに順次記録されていき、セグメントが埋まったら新しいセグメントをmallocなどによりDRAM上に確保します。セグメント内のログが全て消去されたらセグメントをfreeなどによりDRAM上から開放します。
ファイルの内容の変更を行うときは、そのファイルに関するログを探索し、変更箇所に関する過去のログを消去します。消去後は、最新のセグメントの末尾にログを追加します。
ファイルを消去するときは、そのファイルに関するログを全消去します。
デフラグ方法
デフラグは有効となっているログのサイズの総和が、一定値未満となっているセグメントのみを対象に行います。デフラグには2段階あり、セグメント内のデフラグを行った後、全体的なデフラグを行います。
セグメント内のデフラグとは、同じセグメント内で有効となっているログの間の空白を詰めることです。セグメント内でデフラグを行うと、セグメントの末尾が空白となるので、その部分freeします。
全体的なデフラグは、対象となっているセグメント内の全てのログを、最新のセグメントの末尾にログをコピーしていきます。コピーが終わったら、コピー元のセグメントを削除します。
この方法、一見するとセグメント内のデフラグが冗長のように見えます。しかし全体的なデフラグのみを行うと、DRAM使用率が高くなっていくにつれて性能が大幅に下落してしまうという問題点があります。セグメント内のデフラグを行うことで、この問題を解決することができました。ちなみにHDDで同様のデフラグ処理を行うときは、全体的なデフラグのみを行った方が良いそうです。なぜならば、HDDはDRAMに比べて容量が十分に大きく、読み書きの速度が十分に小さいからです。
評価
デフラグによるレイテンシですが、ほとんどの場合(99.9%の確率)はデフラグ導入前後で有意な差は観測されませんでした。また、セグメント内のデフラグを行わなかった時、行った時に比べて最大6倍程度の性能低下が観測されたようです。
感想
RAMCloudそのものが評価を二分する代物ですので、実用的な研究かと言われると微妙なところもあるかもしれません。しかしながら、mallocに焦点を当てたという新しい視点や、近年注目を集めているNVRAMへの応用も期待され、更に実験もかなり精密(ここでは紹介しきれていないが)であるため、FASTというトップカンファレンスでBest paperを取れたのだと思います。
