j3259の日記： 分散システムの時
日記 by
j3259
分散システムでは同時に知識を共有するということは難しい。
しかし現実的な方法で時という概念を扱う必要がある。
時とは何か？
- グローバルな時計（GPS から受信する）
- マシーンのローカルクロック （正確ではない）
- なんらかの時刻の同意
ランポートの考え方
- 時刻はシステムに「イベントA とイベントB のどちらが先に起こったか」と聞くためのもの
- つまり時刻はイベントに対する以下のようなラベルである
-- もし A の後に B が起こったなら、Time(A) < Time(B)
-- もし Time(A) < Time(B) なら、A の後に B が起こった
ローカル順序
- シングルプロセス上でイベント A の後に B が発生したとする
- A ->p B、C ->q D と書く
メッセージの送受信もイベントとして考える
- snd_p(m) ->M rcv_q(m) と書く
推移性 (transitivity)
- A の後に snd_p(m) が起こり、後で rcv_q(m) が起こり、後で D が起こったとすると、A の後で D が起こったと言える
並行 (concurrent events)
- プロセス p からプロセス q にメッセージを送信して q が受信、配達した後で、p でイベント B、q でイベント D が発生したとする。
実際には B が先に起こったとしても q は知りようがないためイベント B と D は並行している(concurrent)という。
"happens before" 関係
- A の後に B が起こった（A -> B）と書くためには
1. ローカル順序 A ->p B によるか
2. メッセージの送受信 A ->M B であるか
3. A と B は 1. と 2. による推移閉包にて関係付けられていなければならない
論理時計(logical clock)
- 単独整数バージョン
-- 各々のプロセス p がカウンター LT_p を管理する
-- メッセージ m は LT_m を持つ
-- プロセス p においてイベントが発生すると LT_p に一を足す
-- p が m を送信する時は LT_p を LT_m に代入する
-- q が m を受信すると max(LT_q, LT_m) + 1 を LT_q に代入する
因果関係の評価
- A の後に B が起こった（A -> B）場合、LT(A) < LT(B)
- 逆は成り立たない。つまり、LT(A) < LT(B) の場合は A -> B が成り立つことを保証できない
- 半順序(partial order) のものに全順序(total order) を当てはめてるため。
-- http://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88
-- http://www.triplefalcon.com/Lexicon/Correspondence-Relation-1.htm
ベクトル時計(vector clock)
- タイムスタンプをリストとして表現する
- 各々のプロセスが、n個のプロセスに対して一つずつ n個のカウンターをベクトルとして持つ
-- プロセス p においてイベントが発生すると VT_p[index_p] に一を足す。普通はメッセージの送受信も同様。
-- メッセージを送信する時は VT_p を VT(m) に代入する
-- メッセージを受信すると、max(VT_q, VT(m)) を VT_q に代入する
分散計算
- 逐次プロセス(sequential process)の集合によって実現される分散プログラムの実行を分散計算という
-- 内部イベントとコミュニケーションイベントにより構成される
- p_i のローカル履歴を h_i = e_i^1, e_i^2, e_i^3,... と定義する
- 部分ローカル履歴を h_i^k = e_i^1, e_i^2, ... , e_i^k と定義する
- グローバル履歴を H = h_1 ∪ .. ∪ h_n と定義する
因果履歴 (causal history)
- H におけるイベント e の因果履歴を CH(e) = {e' ∈ H | e' -> e } ∪ {e} と定義する
「強い時計」特性("strong clock" property)
e -> e' は CH(e) ⊆ CH(e') の場合にのみ成り立つ
因果履歴のプロセスへの投射
- 因果履歴 CH(e) のプロセス p_i への投射を CH_i(e) = CH(e) ∩ h_i と定義する
- CH(e) = CH_1(e) ∪ ... ∪ CH_n(e)
ベクトル時計 VT(e)[i] = k は CH_i(e) = h_i^k の場合にのみ成り立つ
ベクトル時計の解釈
- VT(e_i)[i] は e_i とそれまでに p_i で発生したイベントの数
- VT(e_i)[j] は p_i の e_i に対して因果的に先立つ p_j におけるイベントの数
ベクトル時刻の比較
- 全ての i について VT_A[i] ≦ VT_B[i] のとき、VT_A ≦ VT_B という
- VT_A[i] ≦ VT_B[i] かつ T_A[i] ≠ VT_B[i] のとき、VT_A ＜ VT_B という
- 例
-- [2, 4] ≦ [2, 4]
-- [1, 3] ＜ [7, 3]
-- [1, 3] と [3, 1] は「比較不可能」
しかし現実的な方法で時という概念を扱う必要がある。
時とは何か？
- グローバルな時計（GPS から受信する）
- マシーンのローカルクロック （正確ではない）
- なんらかの時刻の同意
ランポートの考え方
- 時刻はシステムに「イベントA とイベントB のどちらが先に起こったか」と聞くためのもの
- つまり時刻はイベントに対する以下のようなラベルである
-- もし A の後に B が起こったなら、Time(A) < Time(B)
-- もし Time(A) < Time(B) なら、A の後に B が起こった
ローカル順序
- シングルプロセス上でイベント A の後に B が発生したとする
- A ->p B、C ->q D と書く
メッセージの送受信もイベントとして考える
- snd_p(m) ->M rcv_q(m) と書く
推移性 (transitivity)
- A の後に snd_p(m) が起こり、後で rcv_q(m) が起こり、後で D が起こったとすると、A の後で D が起こったと言える
並行 (concurrent events)
- プロセス p からプロセス q にメッセージを送信して q が受信、配達した後で、p でイベント B、q でイベント D が発生したとする。
実際には B が先に起こったとしても q は知りようがないためイベント B と D は並行している(concurrent)という。
"happens before" 関係
- A の後に B が起こった（A -> B）と書くためには
1. ローカル順序 A ->p B によるか
2. メッセージの送受信 A ->M B であるか
3. A と B は 1. と 2. による推移閉包にて関係付けられていなければならない
論理時計(logical clock)
- 単独整数バージョン
-- 各々のプロセス p がカウンター LT_p を管理する
-- メッセージ m は LT_m を持つ
-- プロセス p においてイベントが発生すると LT_p に一を足す
-- p が m を送信する時は LT_p を LT_m に代入する
-- q が m を受信すると max(LT_q, LT_m) + 1 を LT_q に代入する
因果関係の評価
- A の後に B が起こった（A -> B）場合、LT(A) < LT(B)
- 逆は成り立たない。つまり、LT(A) < LT(B) の場合は A -> B が成り立つことを保証できない
- 半順序(partial order) のものに全順序(total order) を当てはめてるため。
-- http://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88
-- http://www.triplefalcon.com/Lexicon/Correspondence-Relation-1.htm
ベクトル時計(vector clock)
- タイムスタンプをリストとして表現する
- 各々のプロセスが、n個のプロセスに対して一つずつ n個のカウンターをベクトルとして持つ
-- プロセス p においてイベントが発生すると VT_p[index_p] に一を足す。普通はメッセージの送受信も同様。
-- メッセージを送信する時は VT_p を VT(m) に代入する
-- メッセージを受信すると、max(VT_q, VT(m)) を VT_q に代入する
分散計算
- 逐次プロセス(sequential process)の集合によって実現される分散プログラムの実行を分散計算という
-- 内部イベントとコミュニケーションイベントにより構成される
- p_i のローカル履歴を h_i = e_i^1, e_i^2, e_i^3,... と定義する
- 部分ローカル履歴を h_i^k = e_i^1, e_i^2, ... , e_i^k と定義する
- グローバル履歴を H = h_1 ∪ .. ∪ h_n と定義する
因果履歴 (causal history)
- H におけるイベント e の因果履歴を CH(e) = {e' ∈ H | e' -> e } ∪ {e} と定義する
「強い時計」特性("strong clock" property)
e -> e' は CH(e) ⊆ CH(e') の場合にのみ成り立つ
因果履歴のプロセスへの投射
- 因果履歴 CH(e) のプロセス p_i への投射を CH_i(e) = CH(e) ∩ h_i と定義する
- CH(e) = CH_1(e) ∪ ... ∪ CH_n(e)
ベクトル時計 VT(e)[i] = k は CH_i(e) = h_i^k の場合にのみ成り立つ
ベクトル時計の解釈
- VT(e_i)[i] は e_i とそれまでに p_i で発生したイベントの数
- VT(e_i)[j] は p_i の e_i に対して因果的に先立つ p_j におけるイベントの数
ベクトル時刻の比較
- 全ての i について VT_A[i] ≦ VT_B[i] のとき、VT_A ≦ VT_B という
- VT_A[i] ≦ VT_B[i] かつ T_A[i] ≠ VT_B[i] のとき、VT_A ＜ VT_B という
- 例
-- [2, 4] ≦ [2, 4]
-- [1, 3] ＜ [7, 3]
-- [1, 3] と [3, 1] は「比較不可能」
分散システムの時 More ログイン