G. 強力なB木¶

CouchDBはB木といわれるデータ構造を使って、ドキュメントとビューを管理しています。ここでは、B木を持っているCouchDBにどんなクエリが適しているか、それがいかにCouchDBにマッチしているかを見ていきます。

これが、CouchDBの内部への最初の進出になります。CouchDBを使うだけなら、水面下で何が起きているかを知る必要はありませんが、CouchDBの魔法がどのように演出されているかが分かれば、あなたも手品くらいは使えるようになるかもしれません。加えて、あなたのCouchDBの一連の使い方を理解しておけば、よりスマートにシステムを構築できるでしょう。

詳しくみたことがないのなら、CouchDBは、HTTPインターフェースを持ったただのB-tree管理システムに見えてくることでしょう。

Note

CouchDBは、B木のちょっとしたバリエーションのB+木を実際には使っていて、ディスク容量を少し余分に消費する代わりに速度が得られるようになっています。以降、B木と言ったときには、CouchDBのB+木だと思ってください。

B木は巨大なデータを高速に検索するためのとても優れたデータ構造です。百万〜数十億のエントリをB木に楽に格納できます。B木はふつうは浅く広いデータ構造です。他の種類の木構造はとても深くなりがちですが、B木は数百万のエントリを一ケタの深さで保持できます。これはCouchDBのような、ハードディスクのような低速なメディアに格納する際にとても有効です。木構造のどの部分に対して読み込み／書き込みでアクセスしても、数個のノードを経由するだけ（＝ハードディスクの遅さの原因であるディスクシークが少し）で済みます（OSが上層のノードの値をキャッシュするため）。

従って、実用的な観点では、どんなに巨大なデータであっても、B木は10ms以内のアクセス時間を保証するだろう。
                                                     -- B木の発明者 ルドルフ・ベイヤー博士

CouchDBのB木の実装は本来のものとは少し異なります。重要な特徴は全て備えてしますが、MVCC(Multi Version Concurrency Control)かつ追記のみの設計になっています。B木はメインのデータベースとビューのインデックスで使われています。ひとつのデータベースはひとつのB木で、ひとつのビューはB木です。

MVCCを使えば、ロックなしの並行な読み込み・書き込みが実現できます。書き込みは全てシリアライズされ、ひとつのデータベースに同時にはひとつの書き込みだけが許されます。書き込みのオペレーションは読み込みをブロックしませんし、同時にいくらでも読み込みを行うことができます。それぞれの読み込みではデータベースの一貫した状態を見られることが保証されています。これがどのように実現されているかが、CouchDBのストレージモデルの中核になります。

その端的な理由としては、CouchDBは追記のみのファイルを利用しているので、B木の根ノードは、ファイルが更新される度に毎回書き換えられなければなりません。しかし、ファイルの古い部分は書き換えられないので、B木の全ての古い根ノードは（今は根ノードでなかったとしても）、それはデータベースの過去のスナップショットを見ていることになります。

本書の前半では、MVCCでどのようにドキュメントの _rev の値を使って、ドキュメントへのバージョン更新は同時にただ一人だけということを保証しているかを示しました。既存の _rev の値を比較のために見るためにB木を利用します。書き込みが受け入れられる前に、データが受理できる状態になっていることが期待できます。

ドキュメントの古いバージョンは上書きされるか新しいバージョンによって削除されてから、特定のバージョンに対する読み込み要求は、同時に起きる書き込みを許容します。頻繁に更新されるドキュメントに対しても、３通りの過去のバージョンを同時に読み込むことも可能です。新しいバージョンが書き込まれている途中でも、個々のバージョンはそれぞれ最新版になります。新しいバージョンが コミットされた 瞬間から、新しいバージョンが読み込まれるようになります（読み込み中だったクライアントはそのまま古いものを読み込みます）。

B木では、データは葉ノードにのみ保存されます。CouchDBのB木はデータをデータベースファイルに追記するだけですから、ディスク上のB木は増える一方です。新しいドキュメントを追加したい？ファイルの最後に追記されます。ドキュメントを消したい？ファイルの最後に削除が記録されます。結果としてデータベースファイルは強靱です。ハードウェア故障や停電などでコンピュータは故障します。CouchDBはどんなデータも上書きしませんから、ディスクに一旦 コミットされた ものが破壊されることはありません。

図: 追記のみのフラットなB木

コミットする、とはデータベースファイルに更新を反映するという操作です。これはデータベースファイルの フッタの 4kに対して行われる操作です。フッタのサイズは2kで、続けて二つ書き込まれます。CouchDBは最初にファイルに対する変更を書き込み、ファイルの新しいサイズを最初のフッタに書き込みます。次にflushを行い、ディスクに全ての変更を反映します。次に最初のフッタを次の2kの部分に書き込んでまたflushします。

この過程のどこで問題が起きても、例えば、電源が落ちても、CouchDBが後で起動したときにデータベースのファイルは一貫した状態になり、ファイルの再チェックは不要です。CouchDBはデータベースファイルを逆向きに読んでいきます。フッタのペアが見つかれば、次のポイントをチェックします：最初の2kが壊れていたら（フッタがチェックサムを持っている）、CouchDBは二番目のフッタを読み込んで差し替えます。二番目のフッタが壊れているときは、CouchDBは最初の2kを読みこみむだけで問題ありません。両方のフッタがディスクに正常にflushされたときのみ、CouchDBは書き込み操作が成功したものとします。データが失われることはありませんし、ディスク上のデータは絶対に壊れません。この設計によって、CouchDBは終了のスイッチが不要なのです。完了したら落とすだけでよいのです。

一般的なB木の詳細や、SSDがあったとしたらどのように挙動が変わるか、についてはまだ書き足りていません。より詳しく調べたいなら、Wikipediaの B木の記事はよい出発点になるでしょう。B木を発明したルドルフ・ベイヤー博士によるScholarpedia（きちんとレビューされたWikipediaのようなもの）のノートもあります。

Translated by UENISHI Kota