Database Internalsを読んでて、7章の最後 Log Stacking のところで疑問が多くていろいろ調べていたなかのひとつ。
LLAMAの話ではないけど同じような話としてこの↑資料が良かったのでこれを見よう。
Log Structured Storageを重ねて使うと起こる問題
ファイルシステムもSSDもLog Structuringを利用していて、昨今Log Structured Storageを利用するアプリケーションも増えてきていて、たくさんの階層でログが使われている。そうするといろいろと不都合があって、その不都合については本でも引用されているこれ↓に書いてあるので
https://www.usenix.org/sites/default/files/conference/protected-files/inflow14_slides_yang.pdf
https://www.usenix.org/system/files/conference/inflow14/inflow14-yang.pdf
ここを見ようという感じだし、本にも書いてあるが、以下のような問題がある
- メタデータが増えて書き込みが増える、メモリの使用量も増える
上の階層で複数の書き込みストリームがあると、上の階層ではそれらがシーケンシャルでも下の階層にはそれらが交互に書き込まれてしまってフラグメンテーションすることがある
- 複数の書き込みストリームというのは、例えばデータベースならデータとログの書き込み。または並列に書き込む場合はそれも複数の書き込みストリームということになる。
Don’t stack your Log on my Log p14より
- 複数の書き込みストリームというのは、例えばデータベースならデータとログの書き込み。または並列に書き込む場合はそれも複数の書き込みストリームということになる。
ストリームが１つの場合でも、上の階層と下の階層でセグメントのサイズが違う場合、上の階層のgcが下の階層の複数のセグメントを無効化する可能性がある。そうすると、下の階層でそのセグメントを回収するためには2つのセグメントをgcしないといけなくなる
Don’t stack your Log on my Log p15より - 上の階層と下の階層で別々にgcするので、まず下の階層でgcしてデータを移動してから、上の階層でgcして、更に下の階層でデータを無効化する、みたいなムダが発生しうる
これはそれぞれの階層が独立してログを書き込み、サイズを管理し、別々にコンパクションをするから問題が起きてしまう。これを解消するために、ファイルシステムもSSDのFTLも統合して管理しましょうというアプローチがある。多分LLAMAはこのアプローチの１つ。
LLAMAとは
Microsoftの「LLAMA: A Cache/Storage Subsystemfor Modern Hardware」というのが（ほぼ？）唯一の詳しい資料。
Microsoftが発表しているキャッシュとストレージを管理するシステム。キャッシュレイヤーとストレージレイヤーを持ち、2つのレイヤーで同一のマッピングテーブルを使ってメモリ内のキャッシュと二次記憶（SSD）のデータを管理する。マッピングテーブルというのはページのIDと物理アドレスの対応を管理するもの。物理アドレスはRAM上だったりFlash上だったりする。
LLAMAはカバーする範囲がかなり広いけど、アプリから扱うところで考えるとキャッシュレイヤーは従来でいえばページキャッシュで、ストレージレイヤーはファイルシステムとかになるんだろうか。
特徴は名前が示すとおり同期が必要な箇所ではCASを使い、一切ラッチを使わないことと、Log Structuringの仕組みを利用しているということ。
この話は同じくMicrosoftが発表しているBw-Treeと同じ。ラッチフリーなLog Structuringの強みは、
- ラッチを使わないことでマルチコアでスケールする
- in place更新をしないで差分の追記のみにすることでキャッシュの無効化を防げる
- ディスクへの書き込みをまとまったシーケンシャルライトにできる
というのを利用してB-Treeを改善したのがBw-Treeで、その考え方をキャッシュとストレージの管理に利用したのがこのLLAMAなんだと思われる。
なぜLLAMAが出てきたのか
上に書いたように（恐らく）LLAMAは従来のファイルシステムやSSDのFlash Translation Layerなどを含んでいてキャッシュとストレージをまとめて管理するので、ログが階層化することで発生する問題を避けられる。
物理層のページの位置をホストが管理していて、それを操作するAPIをアプリケーションに提供するので、そのAPIを使ってアプリケーションを実装していれば書き込みのinterleaveやらセグメンテーションのサイズが違うとかでフラグメンテーションが起きることがない。
LLAMAを使って構築したBw-Treeの場合、Flash Storageに書き出す前に差分をマージしてまとめてから書き込んでスペースを減らしたり、打ち合う操作は消してから書き込んで書き込む量を減らすこともできる。
蛇足
最初「LLAMA: A Cache/Storage Subsystemfor Modern Hardware」を読んでると、良さはlatch freeとlog structuredであることでマルチコアを活かせることとメモリのinvalidationも減らせるのでいいんだということのように思えたので、なんでDatabase InternalsのLog StackingのところでLLAMAが出てきたのかよくわからなかった。ログの階層化の問題を回避するためにFTLをホストレベルで扱うとかはもはや普通のことだから特に書くまでもないということなのか、Cache LayerとStorage Layerで同じマッピングテーブルを使うよ、マッピングテーブルってのはPage IdとPhysical Address（など）との対応を管理するものなんだよ、というところから自明ってことなのかな？
Open-Channel SSDについて調べててなんとなくそういうことかなと理解してきたのと、実験で使ったと書いてあるSSDはFusion-IOで、Fusion-IOはOpen-Channel SSDじゃないだろう？じゃあどうやってFTLをホスト側で？？と思ってFusion-IOで調べてたら資料が出てきた。
Optimizing I/O Operations via the Flash Translation Layer
資料の図を見るとホストからFTLを触れるようになっているような気がするし、 "Client software direct access to flash memory" って書いてある
