2008年10月19日(日曜日)

CouchDB の実装(原文

CouchDB は Apache オープンソース・プロジェクトです。生みの親は Damien Katz で、以下に示すように、非常に優れた技術をベースにしたきわめて魅力的な機能を備えています。
  • RESTful API
  • スキーマ不要のドキュメント・ストア(JSON 形式のドキュメント)
  • MVCC (Multi-Version Concurrency Control) モデル
  • map/reduce として構造化されたユーザー定義クエリー
  • インクリメンタルなインデックス更新メカニズム
  • マルチマスター・レプリケーション・モデル
  • Erlang で記述 (Erlang はすばらしい)
CouchDB がうってつけのソリューションとなるアプリケーションは幅広くあります。その中には、たとえば常時接続ではないラップトップ・ベースのアプリケーション、ハイパフォーマンス・データ・クラスタ、さらにはクラウド型仮想データ・ストレージも含まれます。

CouchDB の設計について理解を深めるうえで、私は非常に幸運なことに Damien 本人と話をする機会を持つことができ、Damien は細かな点についても親切に私に説明してくれました。ここでは、Damien との話の中で私が学んだことを記録しておこうと思います。

基本となるストレージ構造

CouchDB は「ドキュメント指向」のデータベースで、ドキュメントは JSON 文字列です(バイナリ添付ファイルが存在することもあります)。基本となる構造を構成しているのは、「ストレージ」と複数の「ビュー・インデックス」です。「ストレージ」はドキュメントを保存するのに使われ、「ビュー・インデックス」はクエリー処理のために使われます。

ストレージ・ファイル内には「連続した」領域があり
、これらの領域がドキュメントを格納するのに使われます。また、ドキュメントへのアクセスを高速化するために、次の 2 つの B ツリー・インデックスがあります。
  • by_id_index(ドキュメント ID をキーとして使います)。このインデックスは主にドキュメント ID によってドキュメントを参照するときに使われ、最後の圧縮以後のリビジョンのリスト(またはレプリケーションで衝突が発生した場合にはリビジョンのツリー)を指しています。また、リビジョンの履歴(これは圧縮による影響を受けません)を保持しています。
  • by_seqnum_index(単調増加する数をキーとして使います)。seqnum はドキュメントが更新されるたびに生成されます。(更新はすべてシリアルに行われるので、seqnum には非並行更新の順序が反映される点に注意してください。)このインデックスは主に、レプリケーションによる同期化の最終ポイント、ビュー・インデックス更新の最終ポイントを記録するのに使われます。


追記のみの操作

あらゆる更新(ドキュメントの作成、ドキュメントの変更、およびドキュメントの削除)は、追記のみの操作で行われます。既存のドキュメントに修正を加えるのではなく、新しくドキュメントのコピーが作成され、これが現在の領域の末尾に追記されます。その後、新しいドキュメントの場所を指すよう、B ツリー・ノードも修正されます。B ツリー・ノードに対する修正も、追記のみの操作で行われます。すなわち、新しい B ツリー・ノードがコピーされ、これがファイルの最後に追記されます。これが今度は B ツリー・ノードの親ノードに対する修正をトリガし、親ノードのコピーが新しく作られ…、と以下同様に、ルート B ツリー・ノードに達するまで同じ処理が繰り返されます。最後に、新しいルート・ノードを指すよう、ファイル・ヘッダが修正されます。

このことから、すべての更新は、ドキュメントへの 1 回の書き込み(削除の場合を除く)と、各 B ツリー・ノード・ページへの logN 回の書き込みをトリガすることになります。したがって O(logN) の計算量となります。

操作が追記のみであることによって、興味深い MVCC (Multi-Version Concurrency Control) モデルができあがります。以前のドキュメントの状態の全バージョンの履歴がファイルに保持されるからです。クライアントが B ツリー・インデックスの以前のルート・ノードを保持している限り、そのクライアントはスナップショットを取得することができるのです。更新はその後も行われているかもしれませんが、クライアントには最新の変更は見えません。このような一貫性のあるスナップショットは、オンライン・バックアップやオンライン圧縮を行う際に非常に有益です。

読み取り操作はほかの読み取りや書き込み操作と並行して実行されますが、書き込み操作では複数のドキュメントが順番に処理される点に注意してください。言い換えると、任意の時点で進行中のドキュメントの更新は一つだけしかないということです(ただし、ドキュメント内の添付ファイルの書き込みは並行して実行することができます)。

ドキュメントの GET

クライアントが CouchDB に対して HTTP REST GET 呼び出しを行うと、CouchDB は次のような処理を行います。
  • ファイル・ヘッダを見て、by_id B ツリー・インデックスのルート・ノードを探します。
  • B ツリーをたどってドキュメントの場所を見つけます。
  • ドキュメントを読み取り、クライアントに返します。

ドキュメントの PUT(修正)

クライアントが CouchDB に対して HTTP REST PUT 呼び出しを行うと、CouchDB は次のような処理を行います。
  • ファイル・ヘッダを見て、by_id B ツリー・インデックスのルート・ノードを探します。
  • B ツリーをたどってリーフ・ノードとドキュメントの場所を見つけます。
  • ドキュメントを読み取ります。リビジョンを比較し、リビジョンが一致しなければエラーを返します。
  • リビジョンが一致したら、現在のリビジョンの古い seqnum を見つけます。
  • (単調増加する)新しい seqnum と、新しいリビジョンを生成します。
  • 最後の領域を見て、ドキュメントを格納する余地があるかどうか調べます。余地がない場合には、新しくもう一つの連続する領域を割り当てます。
  • 新しい領域に(新しいリビジョンで)ドキュメントを書き込みます。
  • 新しいドキュメントの場所を指すよう、by_id B ツリーを修正します。
  • by_seqnum B ツリーに(新しい seqnum の)エントリを新しく追加し、(古い seqnum の)以前のエントリーを削除します。
by_seqnum B ツリー・インデックスは常に最新のリビジョンを指しており、以前のリビジョンは自動的に忘れられてしまう点に注意してください。

ドキュメントの PUT / POST(作成)

クライアントが CouchDB に対して HTTP REST PUT 呼び出しを行うと、CouchDB は次のような処理を行います。
  • (単調増加する)新しい seqnum と、新しいドキュメント ID およびリビジョンを生成します。
  • 最後の領域を見て、ドキュメントを格納する余地があるかどうか調べます。その余地がない場合には、新しくもう一つの連続する領域を割り当てます。
  • 新しい領域に(新しいリビジョンで)ドキュメントを書き込みます。
  • 新しいドキュメントの場所を指すよう、by_id B ツリーを修正します。
  • by_seqnum B ツリーを修正し、(新しい seqnum の)エントリを新しく追加します。

ドキュメントの DELETE(修正)

クライアントが CouchDB に対して HTTP REST DELETE 呼び出しを行うと、CouchDB は次のような処理を行います。
  • ファイル・ヘッダを見て、by_id B ツリー・インデックスのルート・ノードを探します。
  • B ツリーをたどってリーフ・ノードとドキュメントの場所を見つけます。
  • ドキュメントを読み取ります。リビジョンを比較し、リビジョンが一致しなければエラーを返します。
  • リビジョンが一致したら、現在のリビジョンの古い seqnum を見つけます。
  • (単調増加する)新しい seqnum と、新しいリビジョンを生成します。
  • このリビジョン・パスが削除されたことを示すよう、by_id B ツリーのリビジョン履歴を修正します。
  • by_seqnum B ツリーに(新しい seqnum の)エントリを新しく追加し、(古い seqnum の)以前のエントリーを削除します。
オンライン圧縮

追記のみの操作では、ストレージ・ファイルは時間の経過とともに大きくなっていきます。したがって、定期的にファイルを圧縮する必要があります。圧縮は次の要領で行われます。
  • 新しいストレージ・ファイルをオープンします。
  • by_seqnum B ツリー・インデックス(最新のリビジョンを指しているインデックス)を走査し、ドキュメントの場所を見つけます。
  • ドキュメントを新しいストレージ・ファイルにコピーします(この操作によって、新しいストレージ・ファイル内の対応する B ツリー・インデックスは自動的に更新されます)。
圧縮では、MVCC の性質上、一貫性のあるスナップショットが取得され、圧縮開始後に行われた更新による影響を受けることなく、こうした更新と並行して圧縮を実行できます。ただし、更新速度があまりに高い場合、圧縮プロセスは、ファイルに追記し続ける更新に追い付くことができません。そのため、クライアントの更新速度をスローダウンさせるための抑制メカニズムを現在開発中です。

ビュー・インデックス

CouchDB は、データベースに対する「ビュー」というコンセプトをサポートしています。ビューとは、実質的には、根底にあるドキュメント・リポジトリに対してユーザー定義の処理を行った結果です。このユーザー定義の処理は、"map" と "reduce" という 2 つのステップの処理で構造化されている必要があります。(reduce のセマンティクスが Google の Map/Reduce モデルとは大きく異なる点には注意が必要です。)map() は、各ドキュメントを 0 個、1 個、または複数個の中間オブジェクトに変換するユーザー定義関数で、reduce() は、中間オブジェクトから最終結果を導き出すもう一つのユーザー定義関数です。

map() と reduce() の中間オブジェクトは、ビュー・インデックスに格納されます。ストレージが更新されると、ビュー・インデックスに格納された以前の結果は有効ではなくなるので、更新する必要があります。CouchDB ではインクリメンタルな更新メカニズムを使用し、ビュー・インデックスのリフレッシュを効率的に行えるようになっています。

ビューの定義は 1 つのデザイン・ドキュメントにまとめられます。

各ビューは、1 つの "map" 関数と 1 つの "reduce" 関数("reduce" 関数は省略可能)によって定義されます。

map = function(doc) {

emit(k1, v1)

emit(k2, v2)

}

reduce = function(keys, values) {

return result
}
reduce() 関数は、任意の順序で reduce 処理ができるよう、可換的かつ結合的 (commutative and associative) である必要があります。

各デザイン・ドキュメントで定義されたビューは、ビュー・ファイルとして具体的な形を取ることになります。


最初はビュー・ファイルは空です(インデックスはまだ 1 つも構築されていません)。ビューは必要になったとき、すなわち初めてクエリーが実行されたときに作成されます。
  1. CouchDB は、ストレージ・ファイルの by_seqnum B ツリー・インデックスを走査します。
  2. 上の結果に基づいて、CouchDB は既存のすべてのドキュメントの最新リビジョンを取得します。
  3. CouchDB は最後の seqnum を記憶し、"map_doc" を使って各ドキュメントをビュー・サーバーに渡します。
  4. ビュー・サーバーは map(doc) 関数を呼び出し、emit(key, value) のそれぞれの呼び出しに対し、エントリを 1 つ作成します。
  5. 最後に、エントリのセットが計算され、これが CouchDB に返されます。
  6. CouchDB は、これらのエントリを key = emit_key + doc_id として B ツリー・インデックスに追加します。これは B ツリー・リーブ・ノードそれぞれに対して行われます。
  7. CouchDB は、ビュー・ファイルに含まれる map エントリすべてを "reduce" を使ってビュー・サーバーに渡します。
  8. ビュー・サーバーが reduce(keys, values) 関数を呼び出します。
  9. reduce の結果が計算され、CouchDB に返されます。
  10. CouchDB は、ビュー・ファイルに含まれる map の結果の reduce 値を指すよう、B ツリー・リーブ・ノードを更新します。
  11. その後、CouchDB は 1 つ上のレベル、すなわち B ツリー・リーブ・ノードの親ノードに移動します。B ツリー親ノードのそれぞれに対し、CouchDB は、子ノードの対応する reduce の結果を "rereduce" を使ってビュー・サーバーに渡します。
  12. ビュー・サーバーは、再度 reduce(keys, values) 関数を呼び出します。
  13. 最後に rereduce の結果が計算され、CouchDB に返されます。
  14. CouchDB は、rereduce 値を指すよう、B ツリー親ノードを更新します。
CouchDB は 1 つ上のレベルへの移動を続け、rereduce の結果の計算を繰り返します。最終的に、ルート・ノードの rereduce の結果も更新されます。


処理が終わると、ビュー・インデックスは次のような状態になります。



インクリメンタルなビューの更新

CouchDB はビュー・インデックスを、のんびりと (lazily) かつインクリメンタルに更新します。これは、ドキュメントが更新されても、CouchDB はビュー・インデックスをリフレッシュせず、次にクエリーが実行されるまで更新を行わないという意味です。

実際にクエリーが実行されると、CouchDB は以下に示す方法でインデックスをリフレッシュします。
  • CouchDB は、ストレージ・ファイルの by_seqnum B ツリー・インデックスを走査します。このとき出発点となるのは、最後の seqnum です。
  • 最後に実行されたビュー・クエリー以降に変更されたすべてのドキュメントを抽出し、これをビュー・サーバーの map 関数に渡し、map の結果のセットを受け取ります。
  • CouchDB は map の結果を B ツリー・インデックスに組み込んで更新します。一部の B ツリー・リーブ・ノードも更新されます。
  • 更新された B ツリー・リーブ・ノードについては、CouchDB はそこに含まれるすべての map のエントリをビュー・サーバーにもう一度渡し、reduce 値を再計算させます。その後、reduce 値を B ツリー・ノード内に格納します。
  • CouchDB は、更新された B ツリー・リーブ・ノードのすべての親ノードについて、rereduce 値を再計算し、これを B ツリー・ノード内に格納する必要があります。この処理は、ルート・ノードに達するまで繰り返されます。
一貫性のあるスナップショットを取得できるという特質のために、実行に時間がかかるビュー・クエリーも、データベースの更新と並行して(データベースの更新に影響を受けることなく)実行することができます。ただし、クエリーを実行して一貫性のある結果を見るには、ビュー・インデックスの更新が完了するまで待つ必要があります。クライアントが必ずしも最新の結果を必要としない場合には、ビューの古いコピーをただちに返すようにするオプション(現在開発中)もあります。

クエリー処理

クライアントがビューの結果を取得するときに考えられるシナリオは次のとおりです。

map のみのビューに対するクエリー
この場合、ビュー・インデックスの更新に reduce フェーズはありません。CouchDB は、クエリー処理を実行するために、単純に B ツリーを検索し、指定されたキーに対応する出発点を見つけて(キーにはプレフィクス emit_key が付く点に注意してください)、このキーの map の結果をすべて返します。

reduce を伴う map に対するクエリー
2 つのケースがあります。クエリーがビュー全体を対象とした最終的な reduce 値に対するものである場合には、CouchDB はビュー・インデックスの B ツリーのルートが指す rereduce 値を返します。

クエリーが、各キーの reduce 値に対するもの (group_by_key = true) である場合、CouchDB は各キーの境界の特定を試みます。この範囲が B ツリー・ノードと正確に一致する可能性はまずないので、CouchDB は範囲の両端を見つけて、部分的に一致する B ツリー・ノードを特定し、その map の結果を(該当するキーとともに)ビュー・サーバーにもう一度渡す必要があります。この reduce 値は、既存の rereduce の結果とマージされ、該当するキーの最終的な reduce の結果が計算されます。


たとえば、キーがリーブ・ノード A から F にまたがっている場合、このキーは部分的にノード A とノード F に重なるので、これらの map の結果をもう一度 reduce() に渡す必要があります。 結果は、ノード E の既存の reduce 値とノード P の既存の rereduce 値とともに、rereduce されます。


データベースのレプリケーション

CouchDB では、複数のデータベースのレプリカを異なるマシンで実行することができ、これらのデータを同期化する仕組みを提供しています。レプリケーションが役立つ一般的なシナリオとして、次の 2 つがあります。
  • 必要なときに接続するアプリケーション(PDAなど)。この場合、ユーザーは一定期間、ネットワークから切断された状態で作業し、データの変更をローカルに保存することができます。あとで会社のネットワークに接続した時点で、ユーザーは自分が行った変更を会社のデータベースと同期させることができます。
  • ミッションクリティカルなアプリケーション(クラスタなど)。この場合、データベースを複数のマシンにレプリケートし、冗長性によって信頼性を高めるとともに、ロードバランシングによって高いパフォーマンスを達成することができます。
このようなことを可能にしているのがレプリケータ・プロセスで、このプロセスはレプリケーション・コマンドを受け付けます。コマンドでは、ソース・データベースとターゲット・データベースを指定します。レプリケータはソース・データベースに対し、特定の seq_num 以降のすべての更新ドキュメントを要求します。言い換えると、レプリケータは最後の seq_num を記録する必要があります。 次に、レプリケータはターゲット・データベースに対し、すべての更新ドキュメントの最新のリビジョン履歴をプルするようリクエストを送信し、ターゲットのリビジョン履歴がソースより古いかどうかをチェックします。ターゲットのリビジョン履歴がソースより古い場合には、変更されたドキュメントをターゲットにプッシュし、そうでない場合には、ドキュメントの送信をスキップします。

ドキュメントがターゲット・データベース内でも更新されている場合には、ターゲット・データベースで衝突が検出される可能性があります。このような衝突については、by_id インデックスが指すリビジョン・ツリーでフラグが付けられます。

衝突を解決する前に、CouchDB は最も長いパスを持つリビジョンを「承認されたもの」(winner) とみなし、ビューではこのリビジョンを表示します。ただし、CouchDB では、衝突を解決するための独立した(おそらくは手作業による)プロセスが存在するものと想定しています。

以上のことをふまえると、レプリケータを利用し、双方向データ同期化をベースにしたマルチマスター・レプリカ・モデルを構築することはきわめて簡単です。

たとえば、定期的に実行される(または特定のイベントによってトリガされる)ペアワイズの「ゴシップ型」プロセスを作ることができます。このプロセスでは、次のような処理を行います。
  1. ソース(=レプリカ A)からターゲット(=レプリカ B)に変更をコピーします。
  2. 方向を逆にして、ソース(=レプリカ B)からターゲット(=レプリカ A)に変更をコピーします。
  3. レプリカ A または レプリカ B を無作為に選び、選んだ方を承認されたもの (winner) と呼びます。
  4. ユーザーが用意した merge(doc_revA) 関数を呼び出し、リビジョン・ツリーを修正します。基本的には、アプリケーション固有のロジックを実行して、リビジョン・ツリーをリストの形に戻します。
  5. 承認されたレプリカ (winner) から却下されたレプリカ (loser) に変更をコピーします。これで、リビジョン・ツリー修正後の状態がレプリケートされます。


データの一貫性に関する考察

CouchDB は、トランザクションというコンセプトを持たず、ドキュメント間の相互依存関係の記録も行いません。したがって、データ整合性が決して複数のドキュメントにまたがることのないようにすることが重要です。

たとえば、ドキュメント X を読み取り、読み取った結果に基づいてドキュメント Y を更新するようなアプリケーションがあったとすると、このようなアプリケーションではデータ整合性が問題になる可能性があります。ドキュメント X を読み取った後で、ほかの何らかのアプリケーションがドキュメント X に変更を加えた場合、最初のアプリケーションではこの変更については知り得ない可能性があるからです。そうなると、古い値に基づいてドキュメント Y を更新することになります。CouchDB ではこの種の衝突を検出することができません。なぜなら、衝突が 2 つの異なるドキュメントで起きるからです。

データ・レプリケーションの設定でも、データの一貫性に関する別の問題が生じます。データの同期化はバックグラウンドで行われるので、ほかのレプリカでは、最新の変更が見えるまでに遅延が生じます。クライアントが不確定的にレプリカに接続した場合、次のような事態が起きる可能性があります。
  • クライアントがドキュメントを読み取り、その後、同じドキュメントをもう一度読み取ったところ、2 番目に読み取ったドキュメントのリビジョンの方が最初に読み取ったリビジョンより古くなる。
  • クライアントがドキュメントを更新し、その後、そのドキュメントをもう一度読み取ったところ、更新したはずの内容が表示されない。

17 Comments:

At October 20, 2008 4:18 AM , Blogger Cosmin Lehene said...

Hi Ricky,

One of the big changes with CouchDB since it's part of Apache and since Damien Katz is part of IBM is that it won't be written in Erlang anymore. It's being ported to Java.

http://damienkatz.net/2008/04/couchdb_language_change.html

 
At October 20, 2008 8:14 AM , Blogger Ricky Ho said...

You know this is Damien's joke.

 
At October 20, 2008 12:19 PM , Blogger Batok said...

A very good explanation of couchdb.

Just one clarification. You can add any number of attachments to a single document.

Domingo Aguilera.

 
At October 23, 2008 3:25 PM , Blogger rgh said...

Ricky, have a look at the date :-)

 
At October 23, 2008 7:31 PM , Blogger sethladd said...

Thanks for the excellent post! Perfect timing.

 
At October 23, 2008 8:23 PM , Blogger ryan said...

Interesting parallel: The update and snapshot mechanisms you describe sound a lot like what Jeff Bonwick described for how ZFS works at the ACM Reflections Projections conference in Urbana Illinois. http://www.acm.uiuc.edu/conference/2008/speakers#JeffBonwick

 
At October 24, 2008 3:48 AM , Blogger Инженер said...

Excellent work, Ricky! Thank you.

 
At October 24, 2008 1:52 PM , Blogger Pierre Lindenbaum said...

Thank you for this very interesting post !

 
At October 25, 2008 5:39 AM , Blogger que0x said...

the Java thing was an April foul ! couchDB will keep with Erlang because java doesn't fit for such job (concurrency and parallel computing )

 
At February 4, 2009 12:43 PM , Anonymous Helen Hunt said...

Thanks Ricky for posting this CouchDB Implementation blog entry. It covers just about everything to know about the project. I was wondering what it meant till a quick Google search led me to your blog

In fact, I find your blog interesting and have bookmarked it :)

 
At February 17, 2009 1:44 AM , Anonymous Anonymous said...

Thanks for these interesting highlights about CouchDB =)

 
At February 23, 2009 11:38 PM , Anonymous Rene said...

Thanks for this post.

 
At April 29, 2009 10:39 PM , Anonymous gener said...

Good review. Thank you for this very interesting post.

 
At April 29, 2009 10:39 PM , Anonymous usadrug said...

Hi. I was wondering what it meant till a quick Google search led me to your blog

 
At April 29, 2009 10:41 PM , Anonymous robert said...

It covers just about everything to know about the project.

 
At April 29, 2009 10:42 PM , Anonymous provacyl said...

Good review, thanks.

 
At June 15, 2009 3:51 AM , Anonymous Yousuf Fauzan said...

Lovely.

However, I was wondering if the docid index update could be explained a bit more. Would really appreciate if you could amplify it a little.

 

Post a Comment

Subscribe to Post Comments [Atom]

<< Home