Document

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つのプリミティブからなる
• ab
– アクションa、bがスケジュール中に存在するならば、
aはbの前に位置しなければいけない
a
b
• a⇒b
– アクションaがスケジュール中に存在するならば、
bもスケジュール中に存在しなければいけない
a
b
b
a
or
静的な制約 (2/2)
プリミティブを組み合わせて複雑な制約を表現可能
• ab∧b⇒a
– bはaの後でのみ実行されうる
• a⇒b∧b⇒a
– aとbが共に実行される or 共に実行されない
• ab∧ba
– 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 Balance >= 0
共有データの状態
Balance = $600
スケジュール s = a
caに反するので 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 Balance >= 0
共有データの状態
Balance = $600
スケジュール s = a
a
b
eaに反するので
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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 Balance >= 0
共有データの状態
Balance = $500
スケジュール s = c
a
b
ecに反するので 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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)
静的な制約
どちらか実行
どちらか実行
どちらか実行
∧ (ac ∧ ca) ∧ (ce ∧ ec) ∧ (ae ∧ ea)
動的な制約 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

Download Report