tag:blogger.com,1999:blog-57135785964700442632023-11-16T00:41:30.202+09:00茨の道コンピュータサイエンスな論文を読んだ話とか技術調査をした話とかRyo MATSUMIYAhttp://www.blogger.com/profile/06997443956384162995noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5713578596470044263.post-82068600430988022272015-01-16T01:14:00.003+09:002015-01-16T01:14:48.023+09:00論文紹介: Virtualize Storage, Not DisksUSENIX HotOS 2013で発表された <a href="https://www.usenix.org/conference/hotos13/session/jannen" target="_blank">Virtualize Storage, Not Disks</a> を読みました。<br />
<br />
KVM上で動くゲストOSのディスクには、一般的にファイルシステムが構成されています。つまり、ホストOS上から見ると(ホストOSの)ファイルシステムの上に(ゲストOSの)ファイルシステムが乗っかっているという状況となります。多くのファイルシステムはこの状況を想定せずに設計されているため、ゲストOS側のファイルシステムがホストOS側の環境とマッチせず性能低下を引き起こす可能性があります。<br />
<br />
筆者らは、ゲストマシンが直接ホストマシン上のディスクにアクセスすることを提案しました。具体的には、ゲストマシン上のOSを変更してPOSIX(WIN32API)レベルから、専用のAPIを叩くことでホストOS上のファイルシステムにアクセスするというものです。ホストOS側のファイルシステムにも手を加えます。ファイルのメタデータは「どのOSのファイルか」という情報を持ち、また、固定長(4KB)チャンクによる重複除外機構の導入も行います。atomic系命令を使うことでlock-freeな実装を行い、close-to-openコンシステンシ以上のコンシステンシを保証させます。<br />
<br />
まだ実装していないとのことだが、筆者らがこの続きを発表することはないんじゃないかと思われます。理由は2つあります。1つは「なぜ今まで誰も提案しなかったのか」ということです。おそらくこの問題は、ファイルシステムと仮想マシンの双方についての知識があれば誰でも解決したいと考える問題です。現に<a href="http://id.nii.ac.jp/1001/00106942/" target="_blank">弊研究室の高橋らも似たようなことを考え、実装にまで至っている</a>し、本論文でも類似例を挙げてます。それらの差というのは重複除外と組み合わせていないこととのことですが、それは「やってみたが性能が良くなかった」というオチがあったのではないかと私は考えています。私自身の研究はストレージの重複除外なので、重複除外が性能に与える影響についてはよく分かっているつもりです。ストレージに重複除外を導入したときの性能低下は筆者の想像以上に深刻なものとなるでしょう。<br />
<br />
私がこの研究は行き詰まると予想するもう1つの理由は、おそらくこの研究が対象とする完全仮想化への対応は、それこそオーバーヘッドが膨大なものとなることが予想されるからです。何らかのCPU命令、あるいは例外をホストOSがフックして行う方法以外私は思い付かないのですが、フックすることで発生するオーバヘッドがかなり大きいことは多くのVM研究者にとっては常識でしょう。準仮想化する方向(つまりWindowsへの対応は諦める方向)に転換するべきでしょう。Ryo MATSUMIYAhttp://www.blogger.com/profile/06997443956384162995noreply@blogger.com0tag:blogger.com,1999:blog-5713578596470044263.post-29284060201524856532014-12-18T08:45:00.002+09:002014-12-18T13:38:26.608+09:00論文紹介 : Log-structured Memory for DRAM-based Storage (USENIX FAST '14)<h2>
はじめに</h2>
<div>
この記事は<a href="http://www.adventar.org/calendars/440" target="_blank">システム系論文紹介 Advent Calendar 2014</a>のものです。</div>
<div>
<br /></div>
<div>
<a href="https://www.usenix.org/conference/fast14" target="_blank">USENIX FAST '14</a>というファイルシステムとストレージのカンファレンスでBest paper awardを獲得した<a href="https://www.usenix.org/conference/fast14/technical-sessions/presentation/rumble" target="_blank">Log-structured Memory for DRAM-based Storage</a>という論文の紹介を行います。ここ数年のUSENIXの学会の多くはプレゼンのビデオを公開しており、この発表も例外ではありません。参考にどうぞ。<span style="color: #cccccc;">むしろ英語がある程度できる人はこの記事を読むよりそっちを観た方がいいかも。</span><br />
<span style="color: #cccccc;"><br /></span></div>
<h2>
概要</h2>
<div>
DRAM上にファイルシステムを実装する時、安直にmallocやfreeを使ったりすると必要以上にメモリを消費するそうです。この論文はメモリ消費量を削減するために、DRAM向けログファイルシステムを実装したというお話です。<br />
<br /></div>
<h2>
DRAM上にファイルシステムを使う理由</h2>
<div>
この論文はRAMCloudチームの論文で、RAMCloudに実装することをユースケースとしています。RAMCloudの説明は、偶然にも@suma90hさんの<a href="http://blog.obfuscatism.net/blog/2014/12/01/raft/" target="_blank">Raftの紹介記事</a>で行われているので省略しますが、「全てのデータをメモリ上で読み書きを行い、特定のタイミングでディスク上にフラッシュする分散ファイルシステム」とだけ。</div>
<div>
<br /></div>
<h2>
なぜmallocじゃダメなのか</h2>
<div>
malloc等を使ってメモリを動的に確保したり開放したりするアプリケーションを想定します。アプリケーションが10GBのデータしか確保していないとすれば、DRAMは(OSレベルで見ても)10GBしか消費されないというのが理想だと思われます。しかし、データを小さなブロック単位(100バイトとか)で10GB分確保し、その一部を開放、その後もう少し大きな(10KBとか)で確保し直すといった、ファイルシステムではよくある挙動をシミュレートするとglibcのmallocでDRAMは(OSから見れば)20GB程度消費してしまいます。これは断片化が発生したためです。デフラグすればいいだけの話なのですが、メモリの消費量を抑えつつデフラグを行う方法は既存の研究では存在しておりません。</div>
<div>
<br /></div>
<div>
DRAMがある程度以上消費されたら、アプリケーションを一時的に止めてデフラグを行うという方法がありますが、この方法ではアプリケーションを秒単位で止めてしまう(いわゆるStop the world)ことになることがあるので適切な方法とはいえません。<br />
<br /></div>
<h2>
目標</h2>
<div>
RAMCloudを想定し、DRAM上にファイルシステムを実装するためのSTWのないデフラグを実装することを目標とします。今回はデフラグ処理をインクリメンタルなものとするために、DRAM上に展開するファイルシステムをLog-structuredにしました。<br />
<br />
<h2>
ログの記録方法</h2>
<div>
ある程度の大きさ(本研究だと8MB)のセグメントというものがDRAM上にあります。ログはそのセグメントに順次記録されていき、セグメントが埋まったら新しいセグメントをmallocなどによりDRAM上に確保します。セグメント内のログが全て消去されたらセグメントをfreeなどによりDRAM上から開放します。</div>
<div>
<br /></div>
<div>
ファイルの内容の変更を行うときは、そのファイルに関するログを探索し、変更箇所に関する過去のログを消去します。消去後は、最新のセグメントの末尾にログを追加します。</div>
<div>
<br /></div>
<div>
ファイルを消去するときは、そのファイルに関するログを全消去します。</div>
<div>
<br /></div>
<h2>
デフラグ方法</h2>
</div>
<div>
デフラグは有効となっているログのサイズの総和が、一定値未満となっているセグメントのみを対象に行います。デフラグには2段階あり、セグメント内のデフラグを行った後、全体的なデフラグを行います。</div>
<div>
<br /></div>
<div>
セグメント内のデフラグとは、同じセグメント内で有効となっているログの間の空白を詰めることです。セグメント内でデフラグを行うと、セグメントの末尾が空白となるので、その部分freeします。</div>
<div>
<br /></div>
<div>
全体的なデフラグは、対象となっているセグメント内の全てのログを、最新のセグメントの末尾にログをコピーしていきます。コピーが終わったら、コピー元のセグメントを削除します。</div>
<div>
<br /></div>
<div>
この方法、一見するとセグメント内のデフラグが冗長のように見えます。しかし全体的なデフラグのみを行うと、DRAM使用率が高くなっていくにつれて性能が大幅に下落してしまうという問題点があります。セグメント内のデフラグを行うことで、この問題を解決することができました。ちなみにHDDで同様のデフラグ処理を行うときは、全体的なデフラグのみを行った方が良いそうです。なぜならば、HDDはDRAMに比べて容量が十分に大きく、読み書きの速度が十分に小さいからです。</div>
<div>
<br /></div>
<h2>
評価</h2>
<div>
デフラグによるレイテンシですが、ほとんどの場合(99.9%の確率)はデフラグ導入前後で有意な差は観測されませんでした。また、セグメント内のデフラグを行わなかった時、行った時に比べて最大6倍程度の性能低下が観測されたようです。</div>
<div>
<br /></div>
<h2>
感想</h2>
<div>
RAMCloudそのものが評価を二分する代物ですので、実用的な研究かと言われると微妙なところもあるかもしれません。しかしながら、mallocに焦点を当てたという新しい視点や、近年注目を集めているNVRAMへの応用も期待され、更に実験もかなり精密(ここでは紹介しきれていないが)であるため、FASTというトップカンファレンスでBest paperを取れたのだと思います。</div>
Ryo MATSUMIYAhttp://www.blogger.com/profile/06997443956384162995noreply@blogger.com0