levelDB implementation notes を読んでみた
The implementation of leveldb is similar in spirit to the representation of a single Bigtable tablet (section 5.3).
という最初の一文に惹かれて、以下のページを読んでみました。
implementation notesをテキトーに訳してみます。大分前に、やろうと思ったまま完全に忘れてた、あまりに遅いのでもう既に誰かやってるかもなー。かなり意訳します、ある程度知っている人には当たり前なことでも、わざと噛み砕いてやっていることを簡単化して訳すつもりです。だから、何も断りなく、英文に書いてないことが、訳文にあっても、そういうもんだということで。文章自体のライセンスは、本家にしたがって、修正BSDライセンスということで。と、書いているけど細かいことはよく分からない。最善は尽くしますが、間違ってたらごめんなさい。
ファイルについて。
leveldbは、bigtableの論文5.3にあるタブレットサーバだと考えてもらってよい。でも、ファイルの構成は若干違うので、以下で説明します。データベースと言ったときには、あるディレクトリに含まれるファイルの集合によって、記述されるとします。詳細はこれから書きますが、永続化されるファイルにはいくつかの役割分担があります。
ログファイル
拡張子logのファイルは、直近の更新を記録します。各更新は追記型で記録されます。つまり、一度追加されたデータその物は、必要がなくなってログファイルが削除されない限り、変更されません。デフォルトで4MBなんですが、ユーザが設定した設定値にしたがって、ログファイルがその値を越えると、キーによってソートされたsoted tableに変換されます（まあ、元々）。んで、これから更新されるファイルのために新しいログファイルを作成します。いわゆる、ログローテションというやつです。
一番最新のログファイルは、memtableと呼ばれる構造でメモリ上にも保持されています。検索された場合には、この構造に対しても検索をかけるので、ログファイルへの更新も検索することができます。
ソート済みのテーブル
ソート済みのテーブルは、キーによってソートされたエントリ（key-valueのことですね）を保持しています。各エントリには、keyだけでなく、valueや削除されたことを示すマーカーも含まれます。削除エントリは、そのエントリよりも前に永続化されたソート済みのテーブルから、検索結果をユーザから隠します。つまり、実際には削除されてないのだけれど、ユーザには検索結果を見せないので、ユーザからは削除されたことと同じなんですね。
ソート済みのテーブルの集合は、レベルと言う概念に基づいて管理されます。まず、ログファイルから作成されたソート済みのテーブルは、もっとも若いレベルとして管理されます。このれベールをlevel-0と呼びます。level-0のファイルの作成数がある値を越えたら、現状では４に設定されていますが、level-0のファイル群は、キーの範囲が重複しているlevel-1のソート済みファイルととともにマージされ、新しいlevel-1のファイルが複数作成されます。このファイルは、一つあたり2MBです。
もっとも若いレベルのファイル群は、キーがかぶっています。でも、それ以外のレベルのファイルにおいては、キーがかぶっていることはありません。L >= 1 であるような、レベル L を考えてみましょう。level-Lに含まれるファイル群の総サイズが10のL乗を越えたとき、level-Lに含まれる一つのファイルとlevel-(L+1)に含まれるすべてのキーが重複していファイルをマージして、level-(L+1)に新しいファイル群を作成します。この時、キーが重複しないようにファイル群を作成しています。このマージ処理は、データが更新されるにしたがって、若いレベルからもっとも大きなレベルまで伝播します。この時、ファイルシステム上では、バルクread/writeのみを使っていて、負荷の高いseekの利用を最小化しています。
マニフェスト
マニフェストファイルには、各レベルで作成されるソート済みテーブル群のキーの範囲や重要なメタデータをリスト化されています。新しいマニフェストファイルは、データベースが新たに開かれる時に作成され、ファイル名にはインクリメンタルな数字が利用されます。マニフェストファイルは、ログ形式で記述され、状態が変わるときにその変化をこのファイルに追記します。状態の変化とは、ファイルが追加されたり、削除されたりすることを意味しています。（注）ユーザが追加・更新・削除したデータは、ソート済みのテーブルとして格納されるのですが、そのテーブルを構成するファイルは、動的に変化します。この変化を記録するために必要なのが、マニフェストファイルということですね。
最新を示すファイル
最新を示すファイルは、単純なテキストファイルで、もっとも新しいマニフェストファイルを記録しています。
ログ
システムからのメッセージを出力する、ログファイルも出力されます。
その他
多目的なその他のファイルも出力されます。LOCK, *.dbtmp
レベル0
ログファイルが一定サイズを超えたときに(1MBがデフォルト)、新しいmemtableとログファイルを作成し、新しい更新はこれらを用いて行います。
バックグラウンドでは、以下のことを行います（つまり、更新要求も止まらずに処理する）。
- 一つ前のmemtableをsstableとして書きだす。
- memtableを無効にする。
- 古いログファイルとmemtableを削除する。
- 新しく作ったsstableをレベル0として追加する。
- コンパクションを行う
レベル L におけるサイズがしきい値を超えた場合、バックグラウンドのスレッドによりコンパクションを行います。コンパクション処理では、まずレベル L からファイルAをひとつピックアップし、レベル L+1 に含まれるファイルからファイルAと範囲がかぶっているファイルを選択します。もし、レベル L のファイルがレベル L+1 のファイルの一部分しかかぶってないとしても、レベル L+1 のファイル全てをコンパクションの入力して用います。で、コンパクションが終わったあと、レベル L+1 のファイルは削除されることになります。（注:sstableは、あるキーの範囲において、必ずソートされている必要があり、かつ、あるキーの範囲はそのsstableにのみ入ってないといけない。なので、ちょっとしかかぶっていないレベル L+1 sstableであっても、全てを取り込まないと、新しく生成したsstable意外にも、お範囲が重複しているsstableがいることになって、よろしくないということ。）
ただし、レベル 0 は特別です(お互いに重複した範囲をもっている)。レベル 0 からレベル 1 へのコンパクションは注意する必要がある。レベル 0 のコンパクションでは、お互いに範囲が重複している場合には、ひとつ以上のレベル 0 のファイルをコンパクションの入力ファイルとします。
コンパクション処理は、連続したレベル L+1 ファイルを生成するために、選択したsstableをマージします。現在利用されている出力ファイルが、閾値（２MB）に届いたら、新しいレベル L+1 のファイルを作成し、出力をそちら側に移します。出力ファイルの切り替えは、現在の出力ファイルのキー範囲が10個以上のレベル L+2 ファイルと重複するくらい大きくなった場合も行います。このルールは、今後生じるであろうレベルL+1 のコンパクションをするときに、やたらと多くのレベルL+2のファイルを選択しないようにするためです。(注：この工夫は結構重要で、一回のコンパクションの負荷を高々10ファイルのマージ程度に抑えることができます。これがないと、コンパクションの処理時間がどこまでも大きくなってしまう可能性があるわけですね。)
コンパクションが古いファイルから新しいマージされたファイル群を作成すると、古いファイル群は削除され、新しいファイルは利用可能な状態になります。
あるレベルで発生する複数のコンパクションは、キーの範囲の観点でローテションします。つまり、各レベルにおいて、コンパクションが発生したら、その時に生成したファイルが含むキーの中で最も大きいキーを覚えておきます。次のコンパクションにおいて、覚えておいたキーの次に大きいキーから、コンパクションの対象となるファイルを選択していきます。もし、そのような大きいキーがない場合には、キー範囲の最初に戻ります、ローテションですね。
コンパクションは、上書きされたような値は、古いほうが削除されます、また、削除マーカーに含まれるキーが一つ上のレベルのファイル群のキー範囲に含まれていない場合は、削除マーカーも削除します。
タイミング
レベル 0 のコンパクションは、レベル 0 に属する4つの1MBファイルまで読み込みを行い、最悪の場合レベル 1 に属するファイル全てと重複する可能性(全部で10MB)があるので、14MBを読み込んで、14MBを書きだすことになります。
特殊な処理を行うレベル 0 のコンパクションを覗いて、コンパクション処理はレベル 0 に属するファイル１つ(2MB)を選択します。最悪の場合、このファイルはレベル L+1 に属するファイル12個と重複する可能性があります(10個は、レベル L より レベル L+1 が容量は10倍、残りの境界上にある二つは、レベル L+1 に属するファイル群とレベル L に属するファイル群との間でアラインメントを考慮していないので、一部重複するかもしれない)。ということで、1回のコンパクションで、26MBの読み込みと、26MBの書き込みを行うかもしれない。
ディスクI/Oが、100MB/s(概算で)だとすると、コンパクションは0.5sくらいで終わる(26MBは、最悪値なので最悪でもこの程度ということ)。
もし、バックグラウンドジョブでの書き込みに絞り込みをかけたなら、例えば、100MB/sの10%としてみよう、1回のコンパクション処理時間は、5秒までになる。もし、ユーザが10MB/sで書いているなら、レベル 0 のファイルが結構出来る(高々50まで)。この分析により、マージするオーバヘッドのためのリードコストがかなり大きく増加するかもしれない。
解決案1: この問題を回避するため、もしレベル 0 に属するファイル数が大きくなってしまったら、ログローテションの閾値を上げるのも手かもしれない。だけれども、ログローテーションの閾値を上げれば、memtableがsstableに吐き出されないので、その分メモリを沢山利用することになる。
解決案2: 利用者が、レベル 0 に属するファイル数が増加したときに、それを監視しlevelDBへの書き込みを絞り込むような、フィードバック制御が有効かもしれない。
解決案3: levelDBの設計では、大きなマージ処理のコストを削減できるように頑張ってきた。多分、レベル 0 のファイルの殆どは、
非圧縮の状態でキャッシュ上にのっているだろう、だから、マージ処理を行う上で注意するべきは、オーダーが線形(注：データサイズに比例して処理時間が線形に伸びるという意味)となる部分に注意すればよいだろう。(多分、この解決案についての詳細が以下に続いている)
ファイルの数
2MBのファイルをいつもつるく代わりに、大きなレベルになるほど大きなファイルを作るという方針がとれる、こうすると全体のファイル数が減ることになります。ただ、１回のコンパクション処理の負荷は大きくなります。代替案として、複数のディレクトリにファイル群を配置するという方法も考えられます。2011/4 現在のext3ファイルシステムで調べたところ、ファイル数を変化させながら、100K のファイルをオープンするというベンチマークで、次のような結論を得ました。
| ディレクトリ内のファイル数 | ひとつのファイルのオープンにかかった時間[マイクロ秒] |
|---|---|
| 1000 | 9 |
| 10000 | 10 |
| 100000 | 16 |
