Optimistic Replication Systems ~ IceCubeとWinFSのサーベイ ~ 金田 憲二 Optimistic Replication Systems 例)Lotus Notes, CVS, Unison [Benjamin C. Pierce] • 複数のコンピュータにまたがるデータの共有を 可能にする – PDA・PC間でのメールの共有 – 部屋予約システムなどのグループウェア –… 共有データ Optimistic Replicationの仕組み • Replication – 各マシンに共有データの複製を置く • Reconciliation – 整合性を考慮しながら複製をマージする 複 製 複 製 Reconciliation 複 製 Optimistic Replicationの利点 • 高遅延ネットワークでも高性能を達成 – 書き込みの度に毎回通信する必要はない • ネットワークが一時的に断絶しても動作可能 – Reconciliationの時だけ通信できればよい どうやってReconciliationするか 以下の2つのアプローチが可能 • State transfer 例)ファイルの中身を転送 • Operation transfer 例)ファイルへの読み書きの履歴を転送 本発表の内容 MSR関連のOptimistic Replication Systems • IceCube – Operation transfer型 • WinFS – State transfer型 IceCube Nuno Perguica, Marc Shapiro, and Caroline Matheson. Efficient Semantics-aware Reconciliation for Optimistic Write Sharing. MSRTR-2002-52 A Motivating Scenario • 部屋予約システム – 可能な操作: 時刻と部屋を指定して予約を取る – Reconciliation: double bookingを回避する ユーザ 1 9:00 room A 10:00 room B or 10:00 room C ユーザ 2 9:00 room A 10:00 room C 10:00 room B reconciliation 10:00 room C 既存のタイムスタンプ方式による Reconciliationの問題点 • リクエストを時刻順に並べるだけでは (本当は回避可能な)コンフリクトが発生してしまう ユーザ 2の予約を 処理できない ユーザ 1 1 9:00 room A 2 9:00 room B or 9:00 room C ユーザ 2 9:00 room A 3 9:00 room A or 9:00 room B 9:00 room B reconciliation 既存のタイムスタンプ方式による Reconciliationの問題点 • リクエストを時刻順に並べるだけでは (本当は回避可能な)コンフリクトが発生してしまう ユーザ 1の予約を 処理できない ユーザ 1 2 9:00 room A 3 9:00 room B or 9:00 room C ユーザ 2 9:00 room A 1 9:00 room A or 9:00 room B reconciliation 我々が目指すReconciliation • 各操作の意味を考慮し、より柔軟に処理をする ユーザ 1 ユーザ 2 9:00 room A 9:00 room A or 9:00 room B 9:00 room B or 9:00 room C 9:00 room A 9:00 room B reconciliation 9:00 room C IceCube A general-purpose reconciliation engine 各操作の意味 (例、double bookingに関する制約) IceCube reconcilable アプリケーション (例、部屋予約システム) IceCubeの動作概要 1. 各マシンに共有データの複製を配置する 共有データ Alice Balance $1000 Brian Balance $1000 IceCubeの動作概要 2. 各マシンがローカルの複製を更新する – 実行したアクションをログに記録する – 必要に応じてアクションに制約を課す 共有データ Alice Balance $500 $1000 ひとまとめに実行 しなければいけない $1000 -$300 Brian Balance $200 どちらか片方しか 実行しない 残高は$0以上で なければならない アクションのログ Meeting on Oct. 13 for Alice and Brian Flight Reservation for Alice on Oct. 11 Debit Expense Account $500 Meeting on Oct. 13 for Alice and Brian Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 IceCubeの動作概要 3. Reconciliation i. 各マシンのアクションのログを集める 残高は$0以上で なければならない 共有データ Alice Balance $500 $1000 ひとまとめに実行 しなければいけない $1000 -$300 Brian Balance $200 どちらか片方しか 実行しない 集計されたアクションのログ Meeting on Oct. 13 for Alice and Brian Flight Reservation for Alice on Oct. 11 Debit Expense Account $500 Meeting on Oct. 13 for Alice and Brian Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 IceCubeの動作概要 3. Reconciliation ii. 制約を満たすアクションの列(スケジュール)を ユーザに(いくつか)提示する 残高は$0以上で なければならない 共有データ Alice Balance $500 $1000 ひとまとめに実行 しなければいけない $1000 -$300 Brian Balance $200 どちらか片方しか 実行しない 集計されたアクションのログ Meeting on Oct. 13 for Alice and Brian Flight Reservation for Alice on Oct. 11 Debit Expense Account $500 Meeting on Oct. 13 for Alice and Brian Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 IceCubeの動作概要 3. Reconciliation ii. 制約を満たすアクションの列(スケジュール)を ユーザに(いくつか)提示する 共有データ Alice Balance $500 $1000 $1000 -$300 Brian Balance $200 スケジュール Meetingon onOct. Oct.13 13for forAlice Aliceand andBrian Brian Meeting Meeting on Oct. 13 for Alice and Brian FlightReservation Reservationfor forAlice Aliceon onOct. Oct.11 11 Flight Flight Reservation for Alice on Oct. 11 DebitExpense ExpenseAccount Account$500 $500 Debit Debit Expense Account $500 FlightReservation Reservationfor forBrian Brianon onOct. Oct.11 11 Flight Flight Reservation for Brian on Oct. 11 DebitExpense ExpenseAccount Account$500 $500 Debit Debit Expense Account $500 IceCubeの動作概要 3. Reconciliation iii. ユーザが選択したスケジュールを再実行し、 実行結果を各マシンに伝播させる 共有データ Alice Balance $0 $500 -$300 Brian Balance $0 スケジュール Meetingon onOct. Oct.13 13for forAlice Aliceand andBrian Brian Meeting Meeting on Oct. 13 for Alice and Brian FlightReservation Reservationfor forAlice Aliceon onOct. Oct.11 11 Flight Flight Reservation for Alice on Oct. 11 DebitExpense ExpenseAccount Account$500 $500 Debit Debit Expense Account $500 FlightReservation Reservationfor forBrian Brianon onOct. Oct.11 11 Flight Flight Reservation for Brian on Oct. 11 DebitExpense ExpenseAccount Account$500 $500 Debit Debit Expense Account $500 実際のIceCubeのスクリーンショット ビジネス旅行のプラニングシステム 以降の発表の流れ • ユーザが与えることのできる制約の種類 • 制約を満たすスケジュールを生成する アルゴリズム • IceCubeで実装されたアプリケーション ユーザが与えることのできる 制約の種類 • 静的な制約 – アクション間の依存関係 例)飛行機を予約したならば、金額を支払う • 動的な制約 – 実際に実行しないと確かめられないinvariants – 各アクションのpre-conditionとpost-condition 例)引き落とし後、口座の残高は$0以上 静的な制約 (1/2) 以下の2つのプリミティブからなる • ab – アクションa、bがスケジュール中に存在するならば、 aはbの前に位置しなければいけない a b • a⇒b – アクションaがスケジュール中に存在するならば、 bもスケジュール中に存在しなければいけない a b b a or 静的な制約 (2/2) プリミティブを組み合わせて複雑な制約を表現可能 • ab∧b⇒a – bはaの後でのみ実行されうる • a⇒b∧b⇒a – aとbが共に実行される or 共に実行されない • ab∧ba – aとbのどちらかが実行される or 共に実行されない スケジュールの生成アルゴリズム • 入力 – アクションの集合 – 静的・動的な制約 – 共有データの初期状態 • 出力 – 制約を満たすアクションの列(スケジュール) • なるべく多くのアクションを含む ※最適解を求めるアルゴリズムはNP困難なので ヒューリスティックスを利用する 基本的な動作の流れ アクションの集合 A スケジュール s = ε A中で静的な制約を満たす アクションaを取り出す Yes aは動的な制約を 満たすか? No aをsに追加する 実行をrollbackする No Aが空集合か? Yes sを出力とする 共有データの状態 Balance = $600 スケジュール s = a b c アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジュール s = a a b a をスケジュール c に追加 アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジュール s = a caに反するので a Flight Reservation for Brian on Oct. 12 c を候補から外す b Debit Expense Account $800 c Flight Reservation for Brian on Oct. 11 アクションの集合 d Debit Expense Account $500 e Flight Reservation for Brian on Oct. 10 f Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジュール s = a a b eaに反するので c を候補から外す e アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = -$200 $600 スケジュール s = a b a b c をスケジュール d b アクションの集合 に追加 e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = -$200 スケジュール s = a b 動的な制約に反する a b c アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 -$200 スケジューリングを やり直す Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 スケジュール s = a b a b c アクションの集合 d e f まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジューリングを やり直す Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 スケジュール s = a b 制約違反の原因と c なった b を アクションの集合 d 候補から外す e f まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジューリングを やり直す Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 スケジュール s = a b a⇒b なので c a アクションの集合 も候補から外す d e f まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $600 スケジュール s = c a b c をスケジュール c に追加 アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $500 スケジュール s = c a b ecに反するので c を候補から外す d e アクションの集合 e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $500 スケジュール s = c a b f⇒eに反するので c f アクションの集合 を候補から外す d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $100 $500 スケジュール s = c d a b d をスケジュール c に追加 アクションの集合 d e f Flight Reservation for Brian on Oct. 12 Debit Expense Account $800 Flight Reservation for Brian on Oct. 11 Debit Expense Account $500 Flight Reservation for Brian on Oct. 10 Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 共有データの状態 Balance = $100 スケジュール s = c d アクションの集合 a Flight Reservation for Brian on Oct. 12 が空になったので b Debit Expense Account $800 終了 c Flight Reservation for Brian on Oct. 11 アクションの集合 d Debit Expense Account $500 e Flight Reservation for Brian on Oct. 10 f Debit Expense Account $300 まとめて実行 まとめて実行 まとめて実行 (a⇒b ∧ b⇒a) ∧ (c⇒d ∧ d⇒c) ∧ (e⇒f ∧ f⇒e) 静的な制約 どちらか実行 どちらか実行 どちらか実行 ∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea) 動的な制約 Balance >= 0 IceCubeを用いて実装された アプリケーション • Calendar • Reconcilable Mail Folders 例)同一メールフォルダを異なる名前にrenameした際に コンフリクトを検出 • Replicated File System IceCubeのまとめ • A general-purpose reconciliation engine – ユーザが静的・動的な制約を与えると、 それを満たすスケジュールを生成する WinFS Dahlia Malkhi and Doug Terry. Concise Version Vectors in WinFS. In Proceedings of the 19th International Symposium on Distributed Computing (DISC), 2005 WinFSの概要 • 数百万のオブジェクト(例、メール)の共有 – 各マシンにオブジェクトの複製が置かれる – オブジェクトの更新の依存関係を検出して同期する マシンAの結果を伝播させる o1 o3 o1 o3 o2 o4 o2 o4 同期 A マシンBの結果を伝播させる B WinFSの概要 • 数百万のオブジェクト(例、メール)の共有 – 各マシンにオブジェクトの複製が置かれる – オブジェクトの更新の依存関係を検出して同期する 同一オブジェクトに対する 並列アクセスはコンフリクトとみなす (ユーザが手動で対処する) o1 o3 o1 o3 o2 o4 o2 o4 同期 A B 本論文の要旨 • オブジェクトの更新の依存関係を検出する 新しいアルゴリズムの提案 – 既存のVersion Vectors方式と比較して、 必要とする通信量・記憶容量が小さくて済む 以降の発表の流れ • オブジェクトの更新の依存関係 • Versions Vectors方式による依存関係の計算 • 本論文の手法による依存関係の計算 オブジェクトの更新の依存関係とは aがbより前に行われたという関係( a ⇝ b と表す) 同一マシン上でのオブジェクトの更新 オブジェクト オブジェクト e1 ⇝ e2o2を更新 o1を更新 A e1 e2 異なるマシンをまたがる同期 e2 ⇝ e4 B e3 (注意)e1 ⇝ e3もe3 ⇝ e1も成り立たない 同期 e4 推移律が成り立つ オブジェクト o1を更新 e1 ⇝ e4 依存関係を使って どうやって同期を実現するのか 同一オブジェクトに対する更新a, bにおいて – a ⇝ bならば、bを優先する – a ⇝ bもb ⇝ aも成り立たないならばコンフリクトとみな す A e1 o := 1 B 同期 e1 ⇝ e2 ⇝ e3 なのでo=3 e2 o := 2 C 同期 同期 e3 o := 3 依存関係を使って どうやって同期を実現するのか 同一オブジェクトに対する更新a, bにおいて – a ⇝ bならば、bを優先する – a ⇝ bもb ⇝ aも成り立たないならばコンフリクトとみな す A 同期 B e1 o := 1 C 同期 e2 o := 2 同期 e2 ⇝ e3 も e3 ⇝ e2も 成り立たないのでコンフリクト e3 o := 3 どうやって依存関係を検出するのか Version Vectors方式 • 各オブジェクトごとにVersion Vector(VV)を用意 • オブジェクトの更新・同期に応じてVVを更新する – e1 ⇝ e2 ⇔ (e1のVV) < (e2のVV) が成り立つように Version Vectorの詳細 (1/2) (マシン数)個の要素からなる配列 • マシンiのVersion VectorをViと表す • 初期状態では、配列の各要素の値を0とする • 以下のように順序関係を定義する – Vi > Vj ⇔ ∀k, Vi[k] ≧ Vj[k] かつ∃l, Vi[l] > Vj[l] Version Vectorの詳細 (2/2) e1 ⇝ e2 ⇔ (e1のVV) < (e2のVV) が成り立つように更新される • マシンiがオブジェクトを更新したらVi[i] := Vi[i] +1 • マシンjがマシンiと同期をしたらVi := max(Vi, Vj) A 0 B 0 A A 0 B 0 B A 1 B 0 A 2 B 0 A 3 B 0 e1 e2 e3 同期 A 2 B 0 e1 ⇝ e2 e2 ⇝ e4 A 2 B 1 e4 Version Vectors方式での 異存関係の検出 同一オブジェクトに対する更新a, bにおいて – (aのVV) > (bのVV) なら、aを優先する – (aのVV) > (bのVV) も (aのVV) < (bのVV) も 成り立たないならコンフリクトとみなす a ⇝ b ⇔ (aのVV) < (bのVV) が成り立つことを利用 A Version Vectors方式での VV1 依存関係の検出例1 0 A 1 B 0 B 0 C 0 C 0 A e1 A 0 A 1 A 1 B 0 同期 B 0 B 1 C 0 C 0 C 0 B 同期 VV1 < VV3 (e1 ⇝ e3) なのでo=3 e2 A 0 C o := 1 o := 2 VV3 A 1 A 1 B 0 同期 B 1 B 1 C 0 C 0 C 1 e3 o := 3 A 0 Version Vectors方式での VV2 依存関係の検出例2 A 0 A 1 B 0 B 1 B 1 C 0 C 0 C 0 A A 0 A 0 B 0 B 1 C 0 C 0 B A 0 B 0 C 0 C e2 o := 2 同期 同期 VV2 > VV3 も VV3 > VV2も 成り立たないのでコンフリクト e1 o := 1 同期 A 0 VV3 A 0 B 1 B 1 C 0 C 1 e3 o := 3 Version Vectorsの問題点 各オブジェクトにつきカウンタを用意するので 通信量・記憶容量が大きくなってしまう – O(オブジェクト数 × マシン数) 通信量・記憶容量の削減 (1/2) 全オブジェクトで一つのVersion Vectorを共有 o1 o2 o3 o1 o2 o3 o1 o2 o3 A 0 0 0 B 0 0 0 A 1 0 0 B 0 0 0 A 1 0 1 B 0 0 0 e1 o1 := 1 e3 o3 := 1 A o1 o2 o 3 o1 o2 o 3 A 0 0 0 B 0 0 0 A 0 0 0 B 0 1 0 B e2 o2 := 1 同期 通信量・記憶容量の削減 (1/2) 全オブジェクトで一つのVersion Vectorを共有 A 0 B 0 A A 1 B 0 A 2 B 0 e1 o1 := 1 e3 o3 := 1 同期 B A 0 A 0 B 0 B 1 e2 o2 := 1 通信量・記憶容量の削減 (2/2) 各オブジェクトごとに「最後に誰がいつ更新したか」を記録 o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) A o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) B o1 (A,1) A 1 o2 (A,0) B 0 o3 (A,0) e1 o1 := 1 o1 (A,0) A 0 o2 (B,1) B 1 o3 (A,0) e2 o2 := 1 o1 (A,1) A 2 o2 (A,0) B 0 o3 (A,2) e3 o3 := 1 同期 依存関係の検出方法 • オブジェクトoについて m >= n ⇔ e1 ⇝ e2 が成り立つことを利用する A オブジェクトoが最後に 更新されたのは、 マシンxのカウンタ値がn の時 x B … o (x,n) … … … (.,.) e1 e2は、マシンxの カウンタ値がmになった 以降に発生した x m … … e2 同期 o … (.,.) (.,.) 依存関係の検出の例 o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) A o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) B o1 (A,1) A 1 o2 (A,0) B 0 o3 (A,0) e1 o1 := 1 o1 (A,0) A 0 o2 (B,1) B 1 o3 (A,0) e2 o2 := 1 o1 (A,1) A 2 o2 (A,0) B 0 o3 (A,2) e3 o3 := 1 マシンAの方が 同期 最新の情報 依存関係の検出の例 o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) A o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) B o1 (A,1) A 1 o2 (A,0) B 0 o3 (A,0) e1 o1 := 1 o1 (A,0) A 0 o2 (B,1) B 1 o3 (A,0) e2 o2 := 1 o1 (A,1) A 2 o2 (A,0) B 0 o3 (A,2) e3 o3 := 1 同期 マシンBの方が 最新の情報 依存関係の検出の例 o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) A o1 (A,0) A 0 o2 (A,0) B 0 o3 (A,0) B o1 (A,1) A 1 o2 (A,0) B 0 o3 (A,0) e1 o1 := 1 o1 (A,0) A 0 o2 (B,1) B 1 o3 (A,0) e2 o2 := 1 o1 (A,1) A 2 o2 (A,0) B 0 o3 (A,2) e3 o3 := 1 同期 マシンAの方が 最新の情報 現方式の欠点とその克服 • 同期中にネットワークが断絶すると破綻する – まだ受け取っていない更新を、 受け取ったとみなしてしまう – 既に受け取った更新を、 まだ受け取っていないとみなしてしまう 同期を処理している最中に、 いくつかの情報を各オブジェクトに付与する – 詳細略 WinFSのまとめ • 数百万のオブジェクトの共有を可能にする システム – 改良Version Vector方式により、 各オブジェクトの更新の順序関係を計算する 発表のまとめ • Optimistic Replication Systemsのサーベイ – IceCube – WinFS 参考文献 • Efficient Semantics-aware Reconciliation for Optimistic Write Sharing – Nuno Perguica, Marc Shapiro, and Caroline Matheson – MSR-TR-2002-52 • Concise Version Vectors in WinFS – Dahlia Malkhi and Doug Terry – 19th International Symposium on Distributed Computing, 2005 • Optimistic Replication – Yasushi Saito and Marc Shapiro – ACM Computing Surveys, 2005
© Copyright 2025 ExpyDoc