![? ベクトルクロックの特性
? イベント ? のベクトルクロック ??(?) は、イベント ? に対して
??(?) < ??(?) ならば、イベント ? は ? に因果的に先行す
るという特性を持つ
? ?? ? = ?1, ?2, … , ? ? , ?? ? = (?1, ?2, … , ? ?)
? ?? ? < ?? ? ? (?? 1 ≦ ? ≦ ? : ?? ≦ ??) ∧ (? ≠ ?)
? ???[?] は ?? において今まで発生したイベントの数を表す
? ??? ? = ? ならば、?? において ? 個のイベントが発生したと
?? は判断する
http://fan.naist.jp/~kounoe/lecture/compII/2006/slide/compII7_12.pdf](https://image.slidesharecdn.com/06-130530222844-phpapp01/85/06-45-320.jpg)
![? プロセス ?? はベクトル ??? を次のように維持する
1. イベントを実行する前に、 ?? は ??? ? ← ??? ? + 1 する
2. プロセス ?? が ?? にメッセージ ? を送信するとき、 ?? は先行す
るステップを実行した後に、 ?? は ? の（ベクトル）タイムスタンプ
??(?) を ??? に等しくなるように設定する
3. メッセージ ? を受信すると、プロセス ?? は最初のステップを実
行し、アプリケーションにメッセージを配信した後に、自己のベクト
ルを各 ? について、??? ? ← max?{ ??? ? , ??(?)[?]} に調整す
る
? 特性
? イベント ? がタイムスタンプ ??(?) を持つならば、 ?? ? ? ? 1 は
因果的に ? に先行する ?? で処理されてイベントの数を示す。
? メッセージ ? が他のプロセスで因果的に依存しているか可能性が
あるかを知らせている](https://image.slidesharecdn.com/06-130530222844-phpapp01/85/06-46-320.jpg)
More Related Content
What's hot (20)
分散システム読書会 06章-同期（前編）
- 3. ? ざっくり言えば 「プロセス間の協調動作のための手段?手順」 ? 例えば ? 複数のプロセスがプリンタなどの共有リソースに同時にアク セスせず、互いに排他的にアクセスすることに協力すること ? プロセス ? からのメッセージ ?1 がプロセス ? からのメッ セージ ?2 よりも前または後である、といったイベントの順序 に関して複数のプロセスが同意すること ? ただし ? 分散システムでの同期は非分散に比べて難しい
- 4. ? 6.1 クロック同期：実際の時間に基づく同期 ? 6.2 論理クロック：相対的な順序に基づく同期 ? 6.3 相互排他 ? 6.4 ノードの全地球测位 ? 6.5 選任アルゴリズム ? 6.6 まとめ
- 6. ? 集中システムでの時間にあいまいさはないが、分散 システムでその合意を得るのは容易ではない ? 集中：システムコールの呼び出し順と、得られる時間の前後 関係が合っている ? 分散：時間についてグローバルな合意が得られていない ? UNIXのmakeシステムでの例 ? makeシステムでは、更新されたソースファイルのみ再コンパ イルすることで作業効率が向上した ? エディタが動作するコンピュータとコンパイラが動作するコン ピュータが独立したクロックを持っている場合、想定どおりに 機能しないことがある
- 7. ? エディタのローカルクロックが遅れていると ? 前回のコンパイルでの output.o の出力時間(2144)より、 更新されたソースファイル output.c の更新時間(2143)が 大きいような場面で、コンパイラが呼び出されず古いソース が混在したプログラムになる可能性がある
- 8. ? すべてのコンピュータは時間を管理するための回路、 クロック（用語的にはタイマのほうが適切）を持っている ? 水晶の発振をカウントし指定した回数ごとに割り込み（クロッ クティック）を発生させる回路をクロックと言う。システムは起 動時の日時をある開始日付からのティック数に変換してメモ リに格納する。以後クロックティックごとにこの値に１を加算す ることでクロックが更新される ? 分散システムでのクロック ? 複数のクロックを持つシステムでは、各水晶は異なる速度で 動作しクロックが徐々にずれる。この時間の相違はクロックス キューと呼ばれ、先のmakeの例のような問題を引き起こす
- 9. ? ある種のシステムでは実際のクロック時間（clock time）が重要。効率性?冗長性から、複数の物理的ク ロックが望ましいが、次の２つの問題が生じる 1. どのように実世界のクロックすなわち時計と同期させるか 2. それらのクロックを互いにどのようにして同期させるか ? そもそも、時間とはどのように測定されている？
- 10. ? 古来、時計は天文学的な方法で観測されてきた ? 太陽が最大の高さに昇るイベ ントを「南中(transit of the sun)」（毎日正午頃） ? 連続する南中の間隔を「太陽 日(solar day)」 ? 「太陽秒(solar second)」は 太陽日の1/86,400 ? 地球の自転周期は一定ではないため、多数の日の測定して一日の長さとし、 それを86,400で割った結果を「平均太陽秒(mean solar second)」と呼ぶ
- 11. ? 原子時計と国際原子時間(TAI) ? セシウム133原子が9,192,631,770回の遷移を行なう時間 を1秒と定義した（当時の平均太陽秒による）。およそ3000 万年に1秒の誤差（参照：原子時計の仕組み） ? 世界中のいくつかのセシウム133時計が刻んだ数をパリの 国際時間局(BIH)で平均して国際原子時間(TAI)を作成する ? TAIは1958年1月1日0時を基準とする ? TAIの問題点 ? 86,400TAI秒は平均太陽日よりも約3ミリ秒短い（平均太陽 日は長くなってきている） ? TAIをそのまま時刻として使うと正午がどんどん早くなり、ユリ ウス暦からグレゴリオ暦への改暦のような混乱が生じる
- 12. ? 問題： UNIXのカレンダーコマンドで $ cal 9 1752 と実行すると、どうなるでしょう？ $ cal 9 1752
- 13. ? 答え： ? ちゃんとグレゴリオ暦への改暦が実装されています ? プロテスタントの国のシステムなので1582年でなく1752年 ? 昔とあるシステムのカレンダにこっそり実装しましたw $ cal 9 1752 September 1752 Su Mo Tu We Th Fr Sa 1 2 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
- 14. ? 世界協定時(UTC)の導入 ? BIHではTAIと太陽時間との差が800msecより大きくなった ときに、閏秒(leap second)を導入することにした ? この時間システムを協定世界時(UTC)と呼び、旧来のグリ ニッジ標準時(GMT)を置き換えた ? 現在UTC=TAI-35 （最近では2012/7/1のうるう秒挿入）
- 15. ? 地球上の地理的にどこにいるのかを解決する ? GPSは29個の周回衛星からなる分散システムである ? 各衛星は原子時計を持ち、連続的に自己の位置とタイムスタ ンプを付けたメッセージを放送する ? 地球上の各受信機は、3つの衛星からのメッセージで位置を 計算することができる ? 受信機の位置は衛星の 位置と衛星からの距離で 計算できる。2次元では 右の図のように、円の交 点として求まる。この計算 は3次元に拡張できる
- 16. ? 位置計算での問題点 ? 衛星の位置データが受信機に届くまでに時間を要する ? 受信機のクロックは衛星のクロックと同期していない ? 100万分の1秒の誤差でも300mの誤差になりうる
- 17. ? 受信機で測定される遅れ Δ? は、実際の信号の遅れと受信機のクロックの偏 差 Δ ? からなると言える Δ? = ???? ? ?? + Δ ? ? 信号は光の速度 ? で伝搬するので、受信機と衛星の距離 ?? は明らかに ?Δ? である ?? = ?(???? ? ??) ? 受信機で測定された距離は ?? + ?Δ ? となる ? 座標(??, ??, ??)にある衛星?への距離は次式で計算される ?? = (?? ? ? ?)2+(?? ? ??)2+(?? ? ? ?)2 ? 4つの衛星がある場合、4つの未知変数に対して4つの方程式が得られ、受 信機の位置(? ?, ??, ? ?)だけでなく Δ ? も求めることができる ? 実際には衛星の位置精度や地球が完全な球体でないことから、複雑な補正 計算をさらに行なっている
- 18. ? すべてのマシンの時間をあわせることが目標 ? 各アルゴリズムは同じシステムモデルに基づいている ? 各マシンは1秒に?回の割り込みを発生するタイマを持ち、過 去のある時点以来のティック数を追跡管理している ? あるUTC時間?におけるマシン?のクロック値を ? ?(?) とする ? 完全な世界ではすべてのpとtに対して ? ? ? = ? である ? 言い換えると ? ? ′ ? = ?? ?? は理想的には1である ? ? ? ′ ? は時間 ? における ? のクロック周波数と呼ばれる ? クロックスキューは ? ? ′ ? ? 1 で定義される ? ある時間 ? との偏差は ? ? ? ? ? である
- 19. ? 実際のタイマは誤差がある ? ? = 60 のタイマは理論的には1時間に216,000のティック を発生するが、一般的なタイマの相対誤差は10?5であり、1 時間に215,998から216,002の範囲でティックをとり得るこ とがある ? タイマが仕様の範囲内で動作していることは以下で示される。 定数?は製造者が規定する最大ドリフト率と言う 1 ? ? ≤ ?? ?? ≤ 1 + ? ? 最大ドリフト率とはクロックスキューがどの程度許容されるか を規定している
- 20. ? クロックの再同期 ? 2つのクロックがUTCと異なる方向にずれていくと、同期した 時点から Δ? 経過後では、2?Δ? 離れるかもしれない ? 2つのクロックが ? より大きくずれないようにするには、すくな くとも ? 2? ごとに再同期しなければならない ? 再同期をどうするかで 様々なアルゴリズムが 存在する
- 21. ? クライアントが時間サーバと交信し現在時刻を得る ? サーバと交信するときのメッセージの伝達遅れが、報告され た時刻を遅らせる問題があるので、これを推定する ? ????? と ????? がほぼ同じと仮定すると、AはBに対する偏差 を次式で推定できる ? = ?2 ? ?2??1 + ?4??3 2 ? ?1 = ?2??1 + ?3??4 2
- 22. ? 時刻の調整 ? もしAのクロックが進んでいる場合、Aは基本的にクロックを 遅らせなければならないが、時刻の逆戻りは許されない ? このような変更は徐々に行なう必要がある ? 例：タイマが毎秒100回の割り込みを生成する設定の場合 ? 通常：各割り込みは時刻に10ミリ秒を加算する ? クロックを遅らせる場合：訂正が完了するまで9ミリ秒を加算する ? クロックを進める場合：訂正が完了するまで11ミリ秒を加算する $ man adjtime
- 23. ? NTPの場合 ? NTPではこのプロトコルはサーバ間で一対で行われる ? 偏差 ? に加え、遅延時間 ? が計算される ? = ?2 ? ?1 + ?4 ? ?3 2 ? 8つの (?, ?) の値の対がバッファされ、2つのサーバ間の遅延時 間 ? に対して誤差を最小にする最善の推定値が計算され、偏差 の最も信頼できる推定値としての ? が得られる... （？） ? NTPはサーバを階層(stratum)にわける。原子時計のような標準 時計(reference clock)を持つサーバは階層-1サーバ(stratum- 1 server)と呼ばれる。AがBに通信するとき、Bの階層レベルよりA の階層レベルが高いときのみ時刻を調整する
- 25. ? Berkeleyアルゴリズム ? NTPでは時間サーバは受動的であるが、Berkeley UNIXで はこれとは逆の方法をとる。時間サーバが能動的に各マシン が保持している時刻を問い合わせ、平均時刻を算出し、すべ てのマシンに平均時刻にむけての調整値を通知する。
- 26. ? 無線ネットワークにおけるクロックの同期 ? ここまでのアルゴリズムは、比較的簡単に情報の配信が可 能なことが前提であるが、無線ネットワーク、とくにセンサネッ トワークでは成り立たない。リソースの制限や電力消費を考 慮したアルゴリズムの最適化も重要となる。 ? 一つの解決策として、参照ブロードキャスト同期(RBS)がある ? 全ノードのUTC時刻同期でなく、内部的なクロック同期を狙う ? 送受信者間の同期でなく、受信者のみを同期させる ? RBSでは、送信者は参照メッセージをブロードキャストし、受 信者は自己のクロックを調整する。
- 27. ? RBSは遅延時間の変動が小さい（？） ? NTPなどではNICにメッセージが渡される前にタイムスタンプが付 加されるため、送信側の処理時間が不確定 ? 無線ネットワークはコンテンションプロトコルに基づいているので、 メッセージが実際に送信されるまでの時間は不確定 ? RBSではこれらの不特定な要素が存在しないため変動が小さい
- 28. ? RBSでの時間同期 ? あるノードが基準メッセージをブロードキャストすると、各ノード ? は メッセージ ? を受信した時刻 ??,? （? のローカルクロックから読ん だ値）を記録する ? 2つのノード ? と ? は、その相互の相対的偏差を推定するために 互いの受信時刻を交換して、次式で求める。 ?????? ?, ? = (??,? ? ??,?)? ?=1 ? ? Mは送信されて基準メッセージの総数である ? しかし、互いのクロックは独立して離れていくので、次のような回帰 直線を用いて補償する ?????? ?, ? ? = ?? + ? ? ? と ? は (??,?, ??,?) の組から計算される
- 29. ? ? ? ?,? ? ?,? ? ?,? ? ? ?,? ?????? ?, ? 1 1050 10521 10431 90 90.00 2 1051 10534 10444 90 90.00 3 1052 10548 10456 92 90.67 4 1053 10561 10469 92 91.00 5 1054 10575 10481 94 91.60 6 1055 10589 10494 95 92.17 7 1056 10602 10506 96 92.71 8 1057 10616 10518 98 93.38 ? = 1.1548 ? = ?1123.2 y = 1.1548x - 1123.2 88 90 92 94 96 98 100 1050 1052 1054 1056 ? ?,? ? ? ?,? ? と ? のクロックが独立してい ると平均で求める相対的偏差 は誤差が徐々に大きくなる 回帰直線で補償する
- 30. ? クロック同期とは ? みんなの時計をきちんと合わせたい ? そもそも時間はどのように決められていたか ? 旧来、時間は地球と太陽の関係によって決まっていた ? 天体の動きは一定でなく、一日の長さも一定にならない ? 現代では、原子時計に基づいて時間が決まる ? 一秒の長さは一定になったが、一日の長さに合わない (TAI) ? うるう秒の挿入?削除により微調整される (UTC) ? みんなの時計を合わせよう ? みんなが原子時計を持つことはできないけど、GPSやネットワーク タイムプロトコルを利用して、合わせられるようになった ? 時計の合わせ方には、環境に応じたいろんな方法がある
- 32. ? 概要 ? クロック同期は実時間に関連すると仮定してきたが、ノード間 の時間の合意で十分で、実時間に等しい必要はない ? make の例では、新しい input.c に対してすでにある input.o が旧バージョンであることに、2つのノードが合意す れば十分である。この場合、お互いのイベントを追跡できるこ とが問題であり、これらのアルゴリズムに対してのクロックを 「論理クロック」と呼ぶ ? Lamportはプロセスが時間を正確に合意していることより、 イベントの発生順序について合意しているかが問題とした
- 33. ? 事前発生(happens-before) ? 式 ? → ? は、「? は ? 以前に発生する」と読み、イベント ? がまず 発生し、次にイベント ? が発生する、ということにすべてのプロセス が同意していることを表す ? ? および ? が同じプロセスにおけるイベントであり、? が ? 以前に発生 するならば、? → ? は真である ? ? が1つのプロセスによって送信されたあるメッセージのイベントであり、 ? が別のプロセスによって受信されたそのメッセージのイベントであるな らば、? → ? はまた真である ? 事前発生関係は遷移関係である ? ? → ? かつ ? → ? ならば、 ? → ? である ? 並行イベント ? 2つのイベント ? および ? が、メッセージを交換しない異なるプロセスで 発生するならば、 ? → ? は真ではない、 y → ? も真ではない
- 34. ? クロック時間 ? 論理クロックで必要なのは、イベント ? に対して、すべてのプ ロセスが合意する時間値 ?(?) を測定する方法である ? ? → ? ならば、 ?(?) < ?(?) でなければならない ? クロック時間 ? は常に前向き（増加方向）でなければならな い。すなわち時間の訂正は正の値の加算に限る ? 事前発生の関係はクロック時間の関係に換言できる ? ? および ? が同じプロセスにおけるイベントであり、? が ? 以前 に発生するならば、?(?) < ?(?) である ? ? が1つのプロセスによって送信されたあるメッセージのイベント であり、 ? が別のプロセスによって受信されたそのメッセージの イベントであるならば、?(?) < ?(?) であることを誰もが合意でき るように割り当てなければならない。
- 35. ? イベントに時間を割り当てるアルゴリズム a. 複数マシンが異なる速度でティックを刻んでいると、メッセージの 事前発生関係を表現できない b. Lamportのアルゴリズムでは受信時に、送信時間よりも1つ大き く自己クロックを進める
- 37. ? 各プロセス ?? はローカルカウンタ ?? を保有して以下 のステップでカウンタを更新する ? イベント（メッセージの送信、配信、または内部イベント）を実 行する前に、 ?? は ?? ← ?? + 1 を実行する ? プロセス ?? が ?? にメッセージ ? を送信するとき、先のス テップの実行を完了した後に ?? は ? のタイムスタンプ ??(?) を ?? に等しくセットする ? メッセージ ? を受信すると、プロセス ?? は自己のローカルク ロックカウンタを ?? ← max?{ ??, ?? ? } に調整する。その後、 第1のステップを実行しアプリケーションにメッセージを渡す 2つのイベントが完全に同じ時刻では発生しないようにする必要がある 場合は、時間にプロセス番号を小数点で付加するなどで対処する 例）時間40でプロセス??? でのイベントのタイムスタンプは?40. ? とする
- 38. ? 複製されたDBの更新による不整合の問題 ? NYとSFに口座データベースのコピーがある ? SFで顧客が1000ドルの口座に100ドル加える ? NYで銀行が1%の金利増加させる ? 遠隔地側への更新が遅延して伝搬すると、不整合が生じる ? SFでは100ドル預金後に1%を加え、1111ドルが記録される ? NYでは1%加えた後に100ドル預金され、1110ドルが記録される
- 39. ? 一貫性と全順序マルチキャスト ? 預金と金利更新の順序によって結果が異なるが、一貫性の 観点からその順序は重要ではない。2つの更新がそれぞれ のコピーに同じ順序で行われること、両方のコピーが正確に 同じであることが重要である ? 全順序マルチキャスト(totally-ordered multicast)：すべて のメッセージが各受信者に同じ順序でわたされることが必要 ? 受信メッセージは一旦待ち行列に置かれ、確認通知をマルチ キャストする。待ち行列の先頭のメッセージが、他のプロセス すべてによって確認通知されたときにアプリケーションに渡さ れるようにすることで、すべてのメッセージはどこでも同じ順 序で配信されるようになる。
- 40. ?1 ?2 ?3 0 0 0 ?1: 1.1 1 ?2: 1.2 1 ??? ?1 ?2 ?3 ?1 ?? ??? ?1 ?2 ?3 ?2 ?? ??? ?1 ?2 ?3 受信メッセージと各プロセ スからの確認通知の状態 を持つ待ち行列。一番下 の行が先頭を示す
- 41. ?1 ?2 ?3 0 0 0 ?1: 1.1 1 ?2: 1.2 1 ??? ?1 ?2 ?3 ?2 ?? ?? ?1 ?? ??? ?1 ?2 ?3 ?2 ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? (?1) ?? ??? ?2,?1 2 2 ??? ?1,?2 1 2 ??? ?2,?3 2
- 42. ?1 ?2 ?3??? ?1 ?2 ?3 ?2 ?? ?? ?1 ?? ??? ?1 ?2 ?3 ?2 ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?1 ?? ?? ?? ??? ?2,?1 ??? ?1,?2 ??? ?2,?3 ?1 ??? ?1,?3 ??? ?1 ?2 ?3 ?2 ?? ?? ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?1 ?? ?? 待ち行列の先頭の メッセージ ? ?? が、 すべてのプロセス によって確認された のでアプリケーショ ンに配信できる すべてのプロセスがメッ セージ ? ?? を確認した が、待ち行列の先頭では ないので配信できない
- 43. ?1 ?2 ?3 ??? ?1 ?2 ?3 ?2 ?? ?? ??? ?2,?1 ??? ?2,?3 ??? ?1,?3 ??? ?1 ?2 ?3 ?2 ?? ?? ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?? ?1 ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?? ?1 ?? ?? ?? ??? ?1 ?2 ?3 ?2 ?? ?? ?? ?1 ?? ?? ??
- 44. ? Lamportの論理クロックの弱点 ? ? が ? より前に発生したなら ? ? < ?(?) と導かれるが、 ? ? < ? ? のとき ? が ? より以前に発生したとは限らない ? 下図で ????(?1) < ????(?2) であることが分かっても、?2 の送信 は ?1 の受信とはなんら関係がない（ことが判断できない） → Lamportのクロックは因果性(causality)を把握していない
- 45. ? ベクトルクロックの特性 ? イベント ? のベクトルクロック ??(?) は、イベント ? に対して ??(?) < ??(?) ならば、イベント ? は ? に因果的に先行す るという特性を持つ ? ?? ? = ?1, ?2, … , ? ? , ?? ? = (?1, ?2, … , ? ?) ? ?? ? < ?? ? ? (?? 1 ≦ ? ≦ ? : ?? ≦ ??) ∧ (? ≠ ?) ? ???[?] は ?? において今まで発生したイベントの数を表す ? ??? ? = ? ならば、?? において ? 個のイベントが発生したと ?? は判断する http://fan.naist.jp/~kounoe/lecture/compII/2006/slide/compII7_12.pdf
- 46. ? プロセス ?? はベクトル ??? を次のように維持する 1. イベントを実行する前に、 ?? は ??? ? ← ??? ? + 1 する 2. プロセス ?? が ?? にメッセージ ? を送信するとき、 ?? は先行す るステップを実行した後に、 ?? は ? の（ベクトル）タイムスタンプ ??(?) を ??? に等しくなるように設定する 3. メッセージ ? を受信すると、プロセス ?? は最初のステップを実 行し、アプリケーションにメッセージを配信した後に、自己のベクト ルを各 ? について、??? ? ← max?{ ??? ? , ??(?)[?]} に調整す る ? 特性 ? イベント ? がタイムスタンプ ??(?) を持つならば、 ?? ? ? ? 1 は 因果的に ? に先行する ?? で処理されてイベントの数を示す。 ? メッセージ ? が他のプロセスで因果的に依存しているか可能性が あるかを知らせている
- 47. ?1 ?2 ?3 (0,0,0) ?1(1,0,0) (0,0,0) (0,0,0) (1,0,0) (1,1,0) (2,5,3) (0,0,1) ?2(0,0,1) (1,2,1) (1,3,1) ?3(1,3,1) (1,3,2) (1,3,3) ?3(1,3,3)(1,4,3) (1,5,3) ?4(1,5,3) 各プロセスが持つVC メッセージにピギーバックされる （ベクトル）タイムスタンプ
- 49. ? ミドルウェアによるサポート ? いくつかのミドルウェア、特にISISやその後継であるHorusは、 全順序および因果的順序マルチキャストをサポートしている ? ミドルウェアでメッセージ順序を扱う場合の問題 ? ミドルウェアはメッセージの内容を把握できない ? 同じ送信者からの完全に独立な２つのメッセージも、常に因果性 があると扱われる ? 因果性のすべては把握できない ? 外部通信（電話等）に起因するイベントの因果性は把握できない ? エンドツーエンド問題 ? 順序問題は通信が行われるアプリケーションを十分に観察 することで解きうる問題である。
- 50. ? すべてのコンピュータの物理クロックが完全に同期で きていればいいけど、結構大変、というか無理 ? でも実際には、ノード間のイベントの順序や依存関係 がわかれば十分ということも多い。そこで論理クロック という考えが登場 ? 順序関係に注目 ? Lamportの論理クロック ? 全順序マルチキャスト ? 依存関係に注目 ? ベクトルクロック ? 因果的順序マルチキャスト
- 53. ノードの全地球测位
- 55. まとめ