楽観的複製

楽観的複製（怠惰な複製とも呼ばれる）^{[ 1 ] [ 2 ]}は、複製の戦略であり、複製された複製が分岐することを許容する。^{[ 3 ]}

従来の悲観的レプリケーションシステムは、最初からすべてのレプリカが互いに同一であることを保証しようとします。まるでデータのコピーが最初から1つしか存在しないかのようにです。楽観的レプリケーションは、この考え方を廃止し、結果整合性を採用します。つまり、システムが一定期間静止状態になった場合にのみ、レプリカが収束することが保証されます。その結果、データ更新時にすべてのコピーが同期されるのを待つ必要がなくなり、並行処理と並列処理が向上します。ただし、その代償として、異なるレプリカ間で後から明示的な調整が必要になる場合があり、その調整が困難、あるいは不可能になる可能性もあります。

楽観的複製アルゴリズムは、以下の5つの要素から構成される。

1. 操作の提出：ユーザーは独立したサイトで操作を提出します。
2. 伝播：各サイトは、自身が認識している操作をシステム全体と共有します。
3. スケジュール：各拠点は、把握している作業の順序を決定します。
4. 競合解決：サイトがスケジュールした操作に競合が生じた場合、何らかの方法でそれらを修正する必要があります。
5. コミットメント：各拠点が最終的​​なスケジュールと紛争解決結果に合意し、操業が恒久的なものとなる。

伝播には2つの戦略があります。1つは状態転送で、サイトは現在の状態の表現を伝播します。もう1つは操作転送で、サイトは実行された操作（基本的に、新しい状態に到達する方法に関する指示のリスト）を伝播します。

スケジューリングと競合解決は、構文的または意味論的に行うことができます。構文的システムは、操作がいつ、どこで実行されたかといった一般的な情報に依存します。意味論的システムは、アプリケーション固有の情報を活用して、より賢明な判断を下すことができます。状態転送システムは、転送されるデータの意味に関する情報を一般的に持っていないため、構文的なスケジューリングと競合解決を用いる必要があることに注意してください。

楽観的レプリケーションに基づくシステムのよく知られた例としては、CVSバージョン管理システム、あるいはコピー・変更・マージのパラダイムを使用するその他のバージョン管理システムが挙げられます。CVSは以下の5つの要素を網羅しています。

1. 操作の送信：ユーザーはファイルのローカルバージョンを編集します。
2. 伝播：ユーザーは中央サーバーから手動でアップデートを取得するか、準備が整ったと感じた時点で変更をプッシュ配信します。
3. スケジューリング：操作は、中央サーバーが受信した順序でスケジュールされます。
4. 競合解決：ユーザーが中央リポジトリにプッシュまたはプルを行う際、競合が発生した場合は、そのユーザーが手動で解決する必要があることが通知されます。
5. コミットメント：中央サーバーがユーザーがプッシュした変更を受け入れると、その変更は永続的にコミットされます。

複製の一種として同期があり、これはレプリカが2つしかない場合を指します。例えば、携帯情報端末（PDA）では、ユーザーはPDAまたはコンピュータ上でデータを編集し、それらを統合することができます。ただし、複製は同期よりも広範な問題であり、レプリカが2つ以上存在する可能性があることに注意してください。

その他の例としては、以下のようなものがあります。

• Usenet、およびトーマス書き込みルールを使用するその他のシステム（RFC677を参照）
• マルチマスターデータベースレプリケーション^{[ 4 ]}
• Coda分散ファイルシステム
• オペレーション変革：グループ編集のための理論的枠組み
• ピアツーピア型ウィキ
• 競合のない複製データ型
• Bayou ^{[ 5 ]}分散データベース
• アイスキューブ^{[ 6 ]}

楽観的レプリケートデータベース上に構築されたアプリケーションは、観測される更新の遅延がアプリケーションの正確性を損なわないように注意する必要があります。

簡単な例を挙げると、アプリケーションにデータベースの状態の一部を表示する機能と編集機能がある場合、ユーザーはその状態を編集しても、ビューア上で変更が反映されないことがあります。編集が「うまくいかなかった」と不安になったユーザーは、何度も編集を試みるかもしれません。更新が冪等でない場合（例えば、値をインクリメントする場合）、これは深刻な問題につながる可能性があります。たとえ冪等であっても、誤ったデータベース更新によってパフォーマンスのボトルネックが発生する可能性があり、特にデータベースシステムが高負荷を処理している場合は、悪循環に陥る可能性があります。

アプリケーションのテストは、多くの場合、本番環境よりも規模が小さく（場合によってはサーバー1台のみ）、負荷も低いテスト環境で行われます。このような環境でのレプリケーション動作は、本番環境とは異なる場合があり、テストではレプリケーション遅延が観測されにくく、レプリケーションに敏感なバグが隠蔽される可能性があります。アプリケーション開発者は、データベース更新の影響に関する想定に十分注意し、テスト環境で遅延を確実にシミュレートする必要があります。

楽観的に複製されたデータベースでは、データの有効性制約などの機能を提供する際に細心の注意を払う必要があります。レコードの現在の状態に基づいて特定の更新が受け入れられる場合と受け入れられない場合がある場合、2つの更新（AとB）はシステムの開始状態に対しては個別に正当である可能性がありますが、一方の更新後のシステムの状態に対しては、一方の更新が正当でない可能性があります（たとえば、AとBは両方とも正当ですが、ABまたはBAは不正です）。AとBがデータベース内でほぼ同時に開始された場合、Aは一部のノードで、Bは他のノードで正常に適用される可能性がありますが、AとBが「遭遇」し、一方が既に他方を適用したノードで試行されると、競合が発生します。この場合、システムは最終的にどちらの更新が「勝つ」かを決定し、既に負けた更新を適用したノードがそれを元に戻すように手配する必要があります。しかし、一部のノードでは、更新が元に戻された状態が一時的に公開される可能性があり、更新を開始したユーザーにその失敗を通知する方法がない場合、ユーザーはすべてのノードでの承認確認を（場合によっては永久に）待つ必要があるかもしれません。

• 斎藤康、シャピロ、マーク（2003年9月）。「楽観的複製」（PDF）。マイクロソフト。