# 調停(Reconciliation) ## 定義 調停(reconciliation)とは、本来一致しているべき複数のデータ複製が何らかの理由(データの腐敗・複製ステートマシンの誤り・結果整合性アルゴリズムの中断・管理者の誤操作・切断状態での更新など)で乖離したときに、その差分を事後的に発見し複製を再び一致させる手続きである。調停は「差分の検出」と「差分の解消」という2つの独立したモジュールに分解して考えると見通しがよく、検出された差分のうち意味論的に自動解決できないものが**衝突(conflict)**として残る。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]] §10.4) 調停の実装は3つの現実的な困難を伴う。(1) 大規模データではビット単位比較のような素朴な検出方法のコストが高く、性能最適化のための近道(ウィットネス・タイムスタンプ・世代番号)が別の複雑さを持ち込む。(2) 調停処理自体がクラッシュに対して全か無か・前か後かの原子性を維持する必要がある。(3) 差分の一部は異なる複製が互いに矛盾する形で更新された衝突であり、意味論の理解なしには算法的に解消できない。(Source: ch.10 §10.4) ## たまにしか接続しない運用(occasionally connected operation) デスクトップ機とラップトップ機の両方で同じファイル群を扱う場面が典型例である。切断中の同時更新への対処は、悲観的方式(切断前にチェックアウトしたファイルへの他方の更新をブロックする)と楽観的方式(自由な更新を許し再接続時に検出・解消する)に分かれる。差分検出の手段は段階的な近道として並ぶ。 - ビット単位比較 + 前回調停時の記録コピー — 最も正確だが記録コピーの保持と全データ転送のコストが高い。 - ウィットネス(暗号学的ハッシュ)比較 — 記録コピーより小さく転送も軽いが、ファイル読み取りとハッシュ計算のコストは残る。 - 更新時刻タイムスタンプの比較 — 実装が容易だが、腐敗を検出できない・トランザクションのアボートで誤って「変更あり」と判定する・時計のドリフトや手動修正で誤判定するという3つの弱点を持つ。 - システム全体の世代番号(generation number)の比較 — タイムスタンプと同じ弱点(腐敗検出不可・アボートでの誤判定)を共有するが、クロックのドリフトには影響されない代わりにファイルシステムの改造を要する。 (Source: ch.10 §10.4.1) ## RECONCILE 手順の骨格 タイムスタンプに基づく調停アルゴリズム RECONCILE(Figure 10.3)は、共通ファイル一覧・片側のみのファイル一覧を作り、共通ファイルは両側のタイムスタンプが前回調停時刻より新しいかを調べて衝突・単純コピーを判定し、片側のみのファイルは削除か新規作成かを判定する。全か無かの原子性のため手順全体を冪等に構成し、前か後かの原子性のため実行中は全てのファイル活動を静止させる。解消できない衝突だけがユーザーの手動介入に回される。(Source: ch.10 §10.4.2、擬似コードは Figure 10.3) 改良として、衝突をその場で解決させず後回しにする、アプリケーション固有の意味論(カレンダーアプリが同一ファイル内の別レコードへの追加を自動マージするなど)で算法的に衝突を解消する、ディレクトリやリンクなどファイル名・更新時刻以外のメタデータも扱う、といった方向がある。(Source: ch.10 §10.4.3) ## クロックの協調 RECONCILE はタイムスタンプの正確さに依存する脆い手続きである。片方の時計が誤っていると、衝突の見逃し・新しいファイルの誤上書き・不要な削除・削除済みファイルの誤復活が起こりうる。両システムの現在時刻を読み取って差を記録し、前回からその差が変わっていなければ差を加減して処理を続け、差が変わっていれば不確実性(delta of uncertainty)とみなして手動解決に回す、という保守的な対処が紹介される。(Source: ch.10 §10.4.4) ## 横断的知見 - (今後、他ソースとの突き合わせで蓄積する。現時点では単一ソースのみ。) ## 未解決の問い - 本書の調停はファイル単位・タイムスタンプ/世代番号ベースの検出に留まる。[[結果整合性]]ページが扱う Dynamo/Cassandra のベクタクロックによる衝突検出や、DDIA が扱うアンチエントロピー(読み取り修復・ヒンテッドハンドオフ・Merkle ツリー)と、本書の調停手続きはどの程度対応するか。世代番号はある種の論理クロックとみなせるが、ベクタクロックのような因果関係の追跡はできない点をどう位置づけるべきか。 - RECONCILE はファイルという単位に限定されているが、複製ステートマシンの調停モジュール([[複製ステートマシン]]が扱う「差分の検出・修正」)と本書の RECONCILE 手続きは同じ問題への異なる粒度(ステートマシンの状態全体 vs ファイル単位)の解と言えるか。 ## 関連 - ソース: [[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]](調停の定義・RECONCILE 擬似コード・クロック協調) - 概念: [[複製ステートマシン]](調停を要求する上位の複製管理手法) / [[結果整合性]](調停によって収束を実現する整合性モデル) ## 出典 - Jerome H. Saltzer and M. Frans Kaashoek, *Principles of Computer System Design: An Introduction*, Version 5.0, 2009, Chapter 10, §10.4 Reconciliation. MIT OpenCourseWare, CC BY-NC-SA 3.0 US.