Replication and conflict model メモ

何か間違いがあればご指摘お願いします。

CouchDB の Replication 機能は確かに便利である。
MySQL の Master１台、Slave１台のような構成であれば、とても簡単に実装できる。
しかし、うまくハンドリングしなければ、ドキュメント不整合の原因となりそうである。
Master 複数台構成にする場合は尚更である。

アクセス数の大きいサービスにおいて CouchDB を利用する場合、どういった構成や実装にしたら良いのか？を考察するため、
また、
CouchDB のレプリケーションがどこまでやってくれるのか？を知るために、とりあえず、
http://docs.couchdb.org/en/latest/replication/index.html
を読んでみた。

レプリケーション操作自体はとても簡単に実施できる。
しかしながら、MySQL のレプリケーションとはだいぶ異なるものであるらしいことも分かった。

以下のドキュメントを読んでの訳とそのまとめをこのドキュメントに残す。
http://docs.couchdb.org/en/latest/replication/conflicts.html

まとめ

CouchDB が言いたいことは、多分、以下である。

用語の定義

CouchDB クラスタ

複数の CouchDB を組み合わせて構築する CouchDB データベース。
DB へのアクセス分散、データの冗長化を実施し高可用性のある CouchDB を構築する、などの目的でクラスタが構築される。

双方向レプリケート使えよ

安全にレプリケーションを実施する方法として、双方向のレプリケートを推奨している。
CouchDB のレプリケート機能は一方向にしか実施できない。
これを双方向にレプリケートするように実装するが、安全なレプリケーションの鍵である。
双方向でレプリケートを実施したい場合は、ユーザーが明示的に、push した後にすぐ（或は、pull した後にすぐ push する）ように実装する必要がある。

衝突は自動的にはマージできないから、とりあえず履歴を全部残しておく

２つの CouchDB ノード間において、双方向のレプリケートを実施した場合、各々のノードにおいてリビジョンのすべての履歴を保持する。
CouchDB は自動的なしてくれない。マージ方法はアプリケーション側で定義する必要がある。

衝突の検知機構も用意してあるから、衝突が発生したら、アプリケーション側で回避して

１つのドキュメントにおいて、衝突しているリビジョンと、それらのリビジョンのハンドリング方法が用意してある。
また、DB のコンパクト化を実施する前であれば、ドキュメントの各リビジョンの内容を取得できるため、異なるリビジョン間において diff を取ることもできる。

コンテンツのマージはアプリケーション側の責任で

衝突が発生した場合のコンテンツのマージ処理はアプリケーション側で実装しなければならない。
これらを実装するために必要なことは以下である。

１つのドキュメントにおいて、衝突しているリビジョンを取得すること
衝突しているリビジョンのドキュメントの内容を取得すること
衝突が解決されたとき、「解決された」というメタ情報をドキュメントに付与すること

開発者は、上記１〜３を理解し、マージ処理を適切に実施する必要がある。
マージ処理の実施タイミングについては特に言及や推奨はされていない。

リビジョン木を知ると便利だよ

リビジョン木の概念を知っていると、効率の良いマージ処理を実装できるかも。

DB コンパクト化についても考慮しておいてね

DB コンパクト化が任意のタイミングで走ってしまうと、特定のリビジョンのドキュメントの内容がコンパクト化により削除されてしまうかもしれない。
ドキュメントの内容が削除されてしまうと、リビジョン間の diff を取れなくなる。
これを回避するための方法が紹介されている。

ドキュメントの訳

4.4. Replication and conflict model

以下のサンプルを通して、レプリケーションにおける衝突のハンドリングについてを述べる。

DescTop: { email: "hoge@com", number: "000-0000-0000" }
LapTop : { email: "hoge@com", number: "000-0000-0000" }

DescTop: { email: "fuga@com", number: "000-0000-0000" }
LapTop : { email: "hoge@com", number: "000-1111-0000" }

DescTop と LapTop では衝突が発生している。
これらをマージすると何が起こるだろうか？

4.4.1. CouchDB replication

CouchDb は DB の中で JSON ドキュメントを扱っている。
データベースのレプリケーションは HTTP において実施され、一方向の pull か push のどちらかである。
従って、最も簡単な同期の実施方法は、push の後に pull することである。
その逆も言える。
すなわち、双方向でレプリケーションを実施すれば良い。

push とは local から remote へのレプリケーション方法のことである。

例えば、以下の例では、ユーザーが couchdb01 への update を実施し、couchdb01 は他の couchdb へドキュメントをレプリケートしている。
couchdb01 がレプリケーション処理を実施するのである。

user
 ||
 || update
 ||
 \/       replication by push
couchdb01 -+-> couchdb02
           |
           +-> couchdb03

pull とは remote から local へのレプリケーション方法のことである。

例えば、以下の例では、ユーザーが couchdb01 への update を実施し、couchdb01 は何もしない。
何らかのタイミングにて、他の couchdb が couchdb01 のドキュメントをレプリケートしている。
couchdb01 以外がレプリケーション処理を実施するのである。

user
 ||
 || update
 ||
 \/       replication by pull
couchdb01 <--- couchdb02
          <--- couchdb03

以下のような場合を考えてみる。

v1 document を作る。
v1 から v2a を作る。
v1 から v2b を作る。
レプリケーションする。
何が起こるだろうか？

答えは簡単である。
両方のバージョンへの変更が両方に対して存在するのである。

DESKTOP                          LAPTOP
+---------+
| /db/bob |                                     INITIAL
|   v1    |                                     CREATION
+---------+

+---------+                      +---------+
| /db/bob |  ----------------->  | /db/bob |     PUSH
|   v1    |                      |   v1    |
+---------+                      +---------+

+---------+                      +---------+  INDEPENDENT
| /db/bob |                      | /db/bob |     LOCAL
|   v2a   |                      |   v2b   |     EDITS
+---------+                      +---------+

+---------+                      +---------+
| /db/bob |  ----------------->  | /db/bob |     PUSH
|   v2a   |                      |   v2a   |
+---------+                      |   v2b   |
                                 +---------+

+---------+                      +---------+
| /db/bob |  <-----------------  | /db/bob |     PULL
|   v2a   |                      |   v2a   |
|   v2b   |                      |   v2b   |
+---------+                      +---------+

結局のところ、これはファイルシステムではないため、/db/bob という名前がつけられたドキュメントが１つだけ存在することができる、という制約がない。
同じ名前におけるリビジョンの衝突が存在するのである。
-> 要は、１つのドキュメントに対する過去の変更履歴を覚えておくことができるということ？

また、変更は常にレプリケートされるため、データは安全である。
両方のマシンが、両方のドキュメントのコピーを持っている、従って、どちらかのマシンにおいてハードドライブ障害が発生したとしても、変更は失われない。

もう１つ注目すべきは、１度限り、その場限りの、push、pull だけ（一方向だけ）のレプリケートが実施されない限り、ピアが設定される必要性、ピアが追跡される必要性がないことである。
-> 「ピアが追跡される必要性がない」とは「ピアの変更を追跡する必要性がない」ということ？
-> 双方向にレプリケートしておけば、絶対に安全であるということを言いたげ？
レプリケーションが実施された後、どのピアによりドキュメントのどのリビジョンがレプリケートされたか？という記録はない。
-> 要は、ピアノ追跡の必要性がない。ということを言いたい？

質問は、/db/bob はデフォルトで読み込もうとした際に何が起きるか？である。
決定的なアルゴリズムを用いて CouchDB は勝者として１つのリビジョンを選択する。
だから、すべてのピアにおいて、同じリビジョンが選択されるため、すべてのピアにおいて同じリビジョンが保証されるのである。
決定的に選ばれた勝者だけが map 関数へ送られる。

先ほどの例に戻る。
v2a が勝者であるとする。
デスクトップにおいて、レプリケーションの前、Alice は v2a だけを読むだろう。
レプリケーションの後においても v2a だけを読むだろう。
それは、あたかも v2b が失われたかのように見えるだろう。
しかし、実際にはそうではない。
失われたように見えるリビジョンは、衝突 revision として、隠されている。
しかし、結局は、これらの隠されたリビジョンを含めて、本来ならばマージされなければならない。
そうでなければ、データが失われてしまう。

懸命なビジネスカードアプリケーションは、最低でも、衝突しているバージョンをアリスに伝え、彼女がそれらのバージョンに基づいて新しいバージョンを作成できるようにしなければならない。
そしてアリスはマージして、完全なバージョンを作らなければならない。

4.4.2. Conflict avoidance

シングルノードにおいて CouchDB が動作しているとき、CouchDB は衝突しているリビジョンが作成されることを回避し、409 Conflict エラーを返す。
新しいドキュメントのバージョンを PUT するとき、前のバージョンの _rev を与えなければならない。
PUT リクエストの際に渡された前のバージョンの _rev と、そのドキュメントの最新のバージョンの _rev を比較し、異なれば 409 Conflict エラーとなるのである。

２人のユーザーが同じノードにおいて、ボブのビジネスカードをフェッチし、各々が同時に更新し、それを DB へ書き込んだとする。

USER1    ----------->  GET /db/bob
         <-----------  {"_rev":"1-aaa", ...}

USER2    ----------->  GET /db/bob
         <-----------  {"_rev":"1-aaa", ...}

USER1    ----------->  PUT /db/bob?rev=1-aaa
         <-----------  {"_rev":"2-bbb", ...}

USER2    ----------->  PUT /db/bob?rev=1-aaa
         <-----------  409 Conflict  (not saved)

User2 の変更は拒否されている。
従って、アプリケーションは /db/bob を再びフェッチし、以下のいずれかを実行しなければならない。

前のリビジョンに適用しようとしていた同じ変更を適用し、新しい PUT リクエストを発行する。
---> 無理矢理上書きすることはないが、アプリケーションロジックから再びやり直し、変更を追加するイメージ。
ドキュメントを再描画し、ユーザーがそれを再び編集する。
---> 要は、再びユーザーに編集を実施させる、一番丁寧な回避方法。
以前保存されたドキュメントを上書きする。
---> ドキュメントを無理矢理上書きする。この方法は、User1 の変更を完全に消してしまうものであるため、おすすめはできない。

従って、シングルモードで動作している場合において、アプリケーションは、これらの衝突をハンドリングし、適切なリトライ戦略を講じることができる。

しかしながら、データベースが自分自身で衝突を回避することはできない。

4.4.3. Conflicts in batches

データベースにおいて、衝突を終了させる方法は２つある。

異なるデータベースにおいて、変更が衝突しているとき、
--> 訳せない（？）
データベースへの変更の書き込みを _bulk_docs を用いて実施し、

_bulk_docs API は、１つの HTTTP POST リクエストの中で、複数のアップデートを発行することができるものである。すなわち一括処理である。
通常、これらの複数のアップデートは独立したアップデートとして扱われる。
一括処理の中において、いくつかは、_rev が最新でないことで失敗する（PUT リクエストから返された 409 エラー等によって）。

_bulk_docs は、各々のドキュメントに対する一括処理における成功/失敗をレスポンスとして返す。

しかしながら、シングルモードではなく別のモードで動作している場合、リクエストの１部として {"all_or_nothing": true} を特定する。
これが、CouchDB における、トランザクション処理の類似機能である。
しかしながら、これは、トランザクション処理を完全に再現するものではない。
なぜなら、CouchDB のトランザクション類似機能では、失敗や、ロールバックがないからである。
リクエストのすべての変更は、強制的に、データベースに適用される。
たとえ衝突が発生したとしても。

従って、１つのデータベースインスタンスにおける衝突を扱う方法がわかる。
PUT を用いたリトライ処理を実施する代わりにこれを実施するならば、409 レスポンスを受け取った際に実施すべきコードを何も書かなくて良い。
マルチマスタモードの中で実施されている場合、後で、これらの発生した衝突を扱わなければならない。

POST /db/_bulk_docs
{
  "all_or_nothing": true,
  "docs": [
    {"_id":"x", "_rev":"1-xxx", ...},
    {"_id":"y", "_rev":"1-yyy", ...},
    ...
  ]
}

4.4.4. Revision tree

CouchDB の中で、ドキュメントをアップデートすると、以前のリビジョンのリストが保持される。
更新が衝突するケースにおいて、この履歴は、木構造のようになる。
現在の衝突しているリビジョンは葉になる。

  ,--> r2a
r1 --> r2b
  `--> r2c

このとき、各々のブランチはそれらのヒストリの枝をのばして行くことができる。
例えば、もし r2b リビジョンを読み、?rev=r2b クエリパラメタを付与して PUT リクエストを実行したならば、特定のブランチ（今の例では、r2b）の新しいリビジョンを作成することができる。

  ,--> r2a -> r3a -> r4a
r1 --> r2b -> r3b
  `--> r2c -> r3c

ここには、r4a, r3b, r3c が衝突リビジョンの集合である。
衝突を解決する方法は、他のブランチの変更を考慮して、葉ノードを削除することである。
従って、r4a+r3b+r3c を１つのブランチへ結合するとき、r4a を配置し、r3b と r3c を削除する。

データベースをコンパクト化するとき、葉ノード以外のドキュメントは破棄される。
しかしながら、_rev の履歴は持ち続けられている。
後の衝突解決の際に役立つからである。

4.4.5. Working with conflicting documents

衝突しているドキュメントを抱えての処理。
基本的な GET /doc/docid 操作のレスポンスには、衝突に関する情報は含まれない。
決定的な勝者として選ばれたドキュメントを見るだけであり、他のリビジョンとの衝突が起きているということが分かるようなものは一切得られない。

{
  "_id":"test",
  "_rev":"2-b91bb807b4685080c6a651115ff558f5",
  "hello":"bar"
}

/db/bob ドキュメントに衝突が起きているとしよう。
もし、GET /db/bob?conflicts=true のように、conflicts クエリパラメタを true にして GET リクエストを発行したならば、ドキュメントは衝突状態に加えて、衝突しているリビジョンをすべて取得することができる。
これらの衝突しているリビジョンをすべて取得し、各々のリビジョンを取得し、それらをマージする処理を書くことで、衝突を回避することができる。

{
  "_id":"test",
  "_rev":"2-b91bb807b4685080c6a651115ff558f5",
  "hello":"bar",
  "_conflicts":[
    "2-65db2a11b5172bf928e3bcf59f728970",
    "2-5bc3c6319edf62d4c624277fdd0ae191"
  ]
}

もし、GET /db/bob?open_revs=all のように、open_revs クエリパラメタを all にして GET リクエストを発行した場合、revision tree の中のすべての葉ノードを取得することができる。
これにより、現在発生しているすべての衝突を検知することができる。
しかしながら、これらの葉ノードにはすでに削除されているもの（既に以前に衝突が解決されており、削除された）も含まれる。
これらの削除された葉を除去するためには、_deleted: true を用いることで実施できる。

[
  {"ok":{"_id":"test","_rev":"2-5bc3c6319edf62d4c624277fdd0ae191","hello":"foo"}},
  {"ok":{"_id":"test","_rev":"2-65db2a11b5172bf928e3bcf59f728970","hello":"baz"}},
  {"ok":{"_id":"test","_rev":"2-b91bb807b4685080c6a651115ff558f5","hello":"bar"}}
]

"ok" タグは、open_revs の成果物である。
リビジョンの明確なリストは JSON 配列として取得できる。

この次の処理の、（根本的な）ドキュメントの衝突回避処理の候補としては、以下のいずれかが考えられる。

一度、すべての衝突しているリビジョンを、アプリケーションのユーザーに表示し、どのリビジョンが良いか選んでもらう。
それらをマージしようと試み、マージされたバージョンのドキュメントをデータベースに書き込み、衝突しているバージョンを削除する。

上で述べたように、１つのリビジョンを更新する必要があり、すべての衝突しているリビジョンを明示的に削除する必要がある！
これらは、１つの POST _bulk_docs リクエスト（削除したいリビジョンに"_deleted": trueを設定することで）を用いて実施できる。

4.4.6. Multiple document API

include_docs=true を用いることで、複数のドキュメントを１度にフェッチすることができる。
しかしながら、conflicts=true リクエストは無視される（"doc" 部は _conflicts メンバーを含まない）。
この場合、各々のドキュメントに対して、新たなクエリを発行し、衝突しているかどうか？という状態を取得する必要がある。

4.4.7. View map function

ビューはドキュメントの中の勝ち組リビジョンだけを取得する。
しかしながら、もしそのドキュメントに衝突しているものが存在すれば、_conflicts メンバーも一緒に取得することができる。
すなわち、衝突しているドキュメントと一緒にドキュメントを配置することができる。
簡単な map 関数の例が以下である。

function(doc) {
  if (doc._conflicts) {
    emit(null, [doc._rev].concat(doc._conflicts));
  }
}

上記の関数は以下の出力を与える。

{
  "total_rows":1,
  "offset":0,
  "rows":[
    {
      "id":"test",
      "key":null,
      "value":[
        "2-b91bb807b4685080c6a651115ff558f5",
        "2-65db2a11b5172bf928e3bcf59f728970",
        "2-5bc3c6319edf62d4c624277fdd0ae191"
      ]
    }
  ]
}

これを実施するならば、"sweep" 処理を分離する可能性がある。
"sweep" 処理とは、データベースをスキャンする処理のことである。
このスキャンにおいて、衝突を持っているドキュメントを見つけ、衝突しているリビジョンを取得する。
そして、それらを解決する。

＜この辺が良く分からない！＞
これにより、アプリケーションをシンプルに保つことができる一方で、問題は、誘発している衝突を取り込み、それらを解決するための手段が必要となることである。
ユーザーの観点からすると、うまく保存されたドキュメントであるにも関わらず、変更が失われているという事象が発生する可能性がある。
これらのは後に生き返る。
これらは受け入れられるものであるかもしれないし、受け入れがたいものかもしれない。

また、sweeper は忘れ易く、適切に実装することができず、検知が難しい奇妙な挙動を誘発することがある。

CouchDB 勝ち組リビジョンアルゴリズムは、その衝突が解決されるまで、ビューから情報が消えることを意味する。
ボブのビジネスカードの例を再び引用してみよう。
アリスがボブの電話番号を発行したビューを持っているとする。
そして、彼女の通話アプリケーションは、発信者 ID に基づいた発信者名を表示するとしよう。
もし、ボブの古い電話番号と新しい電話番号を両方持っているような衝突しているドキュメントが存在したとすると、それらはボブの古い番号を反映し解決され、そのとき、新しい番号を認知することはできない。
このような特殊なケースにおいて、アプリケーションは、衝突している情報から適切なビューを作成する必要があるが、これは、現在のところ不可能である。

＜以下、省略＞

4.4.8. Merging and revision history

実際にマージを実施するのは、アプリケーション側の作業となる。
CouchDB はやってくれない。
マージが実施し易いかどうか？はデータ構造に依存する。
いくつかの場合においては、マージはとても簡単である。
例えば、ドキュメントが、単純にアペンドされるだけのリストを保持している場合、それらのリストの和集合を取ることでマージできる。

いくつかのマージ戦略において、オブジェクトに対する変更が見られる。
これが、マージ関数を作成しなければならない場合である。

例えば、ボブのビジネスカードのバージョン v2a と v2b をマージするためには、v1 と v2b の差異とそれらの変更を v2a にも適用する必要がある。

CouchDB では、しばしば、ドキュメントの古いリビジョンが取られる。
例えば、GET /db/bob?rev=v2b&revs_info=true を実行し、v2b で終わっている古いリビジョンのリストを取得する。
同じことを v2a に対して実施し、v2a の共通の先祖リビジョンを取得することができる。
しかしながらデータベースがコンパクト化されている場合、ドキュメントのリビジョンのコンテンツ内容は失われている。

BEFORE COMPACTION           AFTER COMPACTION

     ,-> v2a                     v2a
   v1
     `-> v2b

従って、diff を実施したいならば、新しいリビジョン自身にそれらの diff を保存する方法が推奨されている。
すなわち、v1 を v2a で置き換えるとき、v2a の余分なフィールドまたはその添付物として、変更内容をを含んでしまうのである。
不幸なことに、この方法は、アプリケーションに対する追加簿記であることを意味する。

4.4.9. Comparison with other replicating data stores

省略