Cassandraのストレージには、SizedTierCompactionと、Google LevelDBをもとにしたLeveledCompactionという二つのコンパクション戦略が存在し、ワークロードによって開発者が自由に選択できるようになっています。しかしLeveledCompactionの具体的な挙動がいまひとつ、よく分からず、選択の決め手に欠ける状態でした。

そこで、オリジナルであるLevelDBの実装を調べてみることにしました。インターネット上にLevelDBの解説は多いですが、具体的にどのようなファイルI/Oが発行されているのかはっきりしなかったので、LevelDB開発者向けドキュメントを和訳しました。結果、よく出来てるなーという事がわかったので安心してLeveledCompactionを使おうと思います。

Leveldb file layout and compactions

原文：Leveldb file layout and compactions

Files

leveldbの実装は、気持ちの上では Bigtable tablet (section 5.3). に似ています。しかしながら、その表現を作り上げるファイルの構成は幾分違うので、ここで説明します。

それぞれのデータベースはひとつのディレクトリに格納されるファイルのセットで表現されます。下記のように、いくつかの異なるタイプのファイルが存在します。

Log files

あるログファイル(*.log)は最近の一連の更新を記録します。更新はカレントのログファイルに追記されます。ログファイルがログファイルが事前定義されたサイズ(デフォルトでは約4MB)に達したら、ひとつのsorted table(下記参照)に変換され、その後のための新しいログファイルが作成されます。

カレントログファイルのコピーはひとつのインメモリ構造体(memtable)の中に確保されます。このコピーは全てのリードで参照されるので、リード命令は全てのログされた更新を反映します。

Sorted tables

sorted table(*.sst)はキー順でソートされた一連のエントリーを格納します。各エントリーはそのキーの値か、またはそのキーの削除マーカー(deletion marker)です。(削除マーカーは古いsorted tableに存在ある削除済みの値を隠すために保持されます)

sorted tableのセットは一連のレベルで構成されています。log fileから生成されたsorted tableはある特別な若いレベル(レベル0とも呼ばれる)に配置されます。若いファイルの数が特定のしきい値(いまのところ4)を越えたら、全ての若いファイルはオーバーラップする全てのレベル1と一緒にマージされ、新しい一連のレベル1ファイルを生み出します(データ2MBごとにひとつの新しいレベル1ファイルを作成します)。

若いレベルのファイルはキーがオーバーラップするかもしれません。しかしながら他のレベルのファイルは別個のオーバーラップしないキーレンジを持っています。レベル数L (L >= 1)を考えてください。レベルLのファイルサイズの合計が (10^L) MB (すなわちレベル1のとき10MB、レベル2のとき100MB…)を超過したら、レベルLのあるファイルと全てのオーバーラップするレベル(L+1)のファイルがマージされ、レベル(L+1)の新しいファイルのセットをかたちづくります。このマージは、新しい更新を、バルクリードとバルクライトだけを使って(つまり、高価なシークを最小化して)徐々に若いレベルから最大のレベルに移行する効果を持ちます。

Manifest

MANIFESTファイルは各レベルを構成するsorted tableのセット、対応するキーレンジ、そしてその他の重要なメタデータをリストしています。新しいMANIFESTファイル(ファイル名に新しい番号が埋め込まれている)はデータベースが再オープンされたときに毎回作成されます。MANIFESTファイルはログ形式で、(ファイルの追加や削除など)全ての状態変化はこのログに追記されます。

Current

CURRENTは最新のMANIFESTファイルの名前を保持する単純なテキストファイルです。

Info logs

情報メッセージはLOGとLOG.oldというファイルに書かれます

Others

その他のファイルは多様な目的でそこにあるかもしれません(LOCK, *.dbtmp)。

Level 0

ログファイルが特定のサイズ(デフォルト1MB)まで成長したら：新しいmemtableとログファイルを作成し、今後の更新をここに向ける
バックグラウンドで：
- 以前のmemtableの内容をsstableに書く
- memtableを破棄する
- 古いログファイルと古いmemtableを削除する
- 新しく作ったsstableを若い(level-0)レベルに追加する

Compactions

レベルLのサイズが上限に達したら、バックグラウンドスレッドでそれをコンパクトします。コンパクションはレベルLからひとつのファイルと、次のL+1レベルから全てのオーバーラップするファイルを選びます。レベルLファイルがレベル(L+1)ファイルの一部にしかオーバーラップしない場合でも、そのレベル(L+1)ファイルの全体がコンパクションの入力として使われ、コンパクション後に破棄される事に注意してください。余談：レベル0は特別(その中のファイルはお互いにオーバーラップしているかもしれない)なので、レベル0からレベル1へのコンパクションは特別に扱います：レベル0コンパクションは、これらのファイルが互いにオーバーラップしているとき、一つ以上のレベル0ファイルを選ぶ事があります。

コンパクションは選択されたファイルをマージして一連のレベル(L+1)ファイルを生成します。カレントの出力ファイルがターゲットファイルサイズ(2MB)に到達したら、新しいレベル(L+1)ファイルの生成に切り替わります。また、カレントのアウトプットファイルが10個以上のレベル(L+2)ファイルをオーバーラップするほど大きく成長した場合も、新しいファイルの生成に切り替えます。この最後のルールは、後々のレベル(L+1)ファイルのコンパクションが多すぎるレベル(L+2)ファイルを選択しないことを保証するためです。

古いファイルは捨てられ、新しいファイルが待ち受け状態に追加されます。

特定レベルのコンパクションはキースペースを巡回します。より詳しくいうと、各レベルLでは、レベルLでのコンパクションの最後のキーを記憶しておきます。次のレベルLのコンパクションでは、このキーより後ろで始まる最初のファイルを選択します。(もしそのようなファイルが無かったらキースペースの先頭に戻る)

コンパクションは上書きされた値を捨てます。もし、カレントキーにオーバーラップするレンジを持ったファイルが上位のレベルに存在しない場合は、削除マーカーも捨てます。

Timing

Level-0コンパクションはレベル0から最大で4つの1MBファイルと、最悪で全てのレベル1ファイル(10MB)をリードします。すなわち、14MBリードして14MBをライトします。

特別なレベル0コンパクションを除き、レベルLから2MBファイルを選択し、最悪でレベルL+1から12ファイル (レベルL+1はレベルLサイズの10倍なので10、そしてその他の2はレベルLのファイルレンジは通常レベルL+1のファイルレンジにアラインされていないために発生する境界)を選択します。コンパクションはなので26MBリードと26MBライトです。100MB/sのディスクIOレート(現代的なドライブの概算の範囲)を想定すると、コンパクションコストはワーストでおよそ0.5秒です。

もしバックグラウンド書き込みをなにか小さく制限する、たとえば100MB/sの10%に制限するとしたら、コンパクションは最大で5秒かかるかもしれません。ユーザーが10MB/sで書き込んでいたら、私たちはたくさんのレベル0ファイル(5*10MBに応じる〜50)をくみ上げるかもしれません。これは、毎回のリードで多くのファイルをマージする必要がある事からリードのコストを非常に増大させるかもしれません。

解決策1: この問題を和らげるため、レベル0ファイルの数が多いときにログスイッチのしきい値を上げる必要があると思います。もっとも、大きなしきい値は対応するmemtableを保持するためにより多くのメモリが必要になるという負の一面もありますが。

解決策2：レベル0ファイル数が増加している時は人工的に書き込みレートを下げる必要があると思います。

解決策3：私たちは非常に広いマージのコストを低減するために努力しています。おそらくほとんどのレベル0ファイルは圧縮されずにキャッシュにあり、マージングイテレーターのO(N)の複雑性を心配するだけでいいでしょう。

Number of files

常に2MBファイルを作成する代わりに、合計ファイル数を提言するために高レベルでは大きいファイルを使う事も出来ます、もっとも、より爆発的なコンパクションが必要になりますが。代わりに、ファイルセットを複数のディレクトリにシャードする事も出来ます。

2011年2月4日に行ったext3ファイルシステム上での実験によると、ディレクトリの中にさまざまなファイル数があるとき、100Kファイルをオープンするには以下の時間がかかります。

Files in directory	Microseconds to open a file
1000	9
10000	10
100000	16

たぶんモダンなファイルシステムではシャーディングも要らないんじゃないですかね？

Recovery

CURRENTをリードして最新のコミットされたMANIFESTを見つける
名指しされているMANIFESTファイルを読む
古いファイルをクリンナップする
ここで全てのsstablesを開く事も出来るが、でも多分遅延した方がいいだろう…
ログチャンクを新しいレベル0 sstableに変換する
復旧されたシーケンスで新しいログファイルに新しいライトを振り向ける

Garbage collection of files

全てのコンパクションとリカバリの最後にDeleteObsoleteFiles()が呼ばれます。これはデータベース内の全てのファイルの名前を見つけます。カレントログファイルでない全てのログファイルを削除します。いくつかのレベルから参照されておらずアクティブなコンパクションのアウトプットではない全てのテーブルファイルを削除します。

LevelDBの設計ドキュメント和訳