Yabu.log

ITなどの雑記

分散システムにおけるイベントの前後関係と論理時計・ベクトル時計について

分散システムでは時刻同期はとらずに順序同期だけをとっている、という話はよく聞きます。順序同期とはいったいどのような仕組みなのでしょうか

前提

  • 各ノード間の処理の順序を適正に処理したい。
  • 個々のサーバーが原子時計などの十分に正確な時計を持っていることを前提としない
  • 時刻の責任を持つノード(FTP電波時計)のある仕組みは順序同期のためには使えない(ミリ秒単位の誤差が発生するため)

前後関係とは

プロセスローカルでの順序と送受信イベントからの推移測で導かれる順序のことを前後関係といいます。 前後関係には以下のルールがあります。

(ルールH1)同一プロセス上でおこなわれたイベントeとe'に対して、eがe'の後に行われていればe→e'が成り立つ
(ルールH2)eがメッセージmの送信イベント、e'がmの受信イベントであればe→e'が成立する
(ルールH3)e→e'、e'→e''ならば、e→e''

これらのルールから察する通り、すべてのイベント間の前後関係を定義できるわけではありません。 特に、本記事で紹介するアルゴリズムでは通信が行われていないノード間ではそれぞれのイベントがどちらが先に起こったか類推することはできません。

なおここで定義した前後関係は以下の特性があるため、半順序(Partial order)になります。

  • 満たしている:推移律(定義より自明)、反射率(自分自身と同値な関係)、反対象律(相違な2要素の同値な関係がない)
  • 満たしていない:完全律(比較できない相違な2要素がある)

比較できない関係を「平行である」といいます。例えば下記の例だと

f:id:yuyubu:20190327185600p:plain
a1とc1は比較できない

  • b1→b2(ルールH1)
  • a1→b1(ルールH2)
  • c1→b2(ルールH2)
  • a1→b2(ルールH3)

という前後関係を導出することができますが、 a1とc1に関しては前後関係の比較ができません。

論理時計

前後関係を実現する実装として「論理時計」というものがあります。 前後関係を定義したルール通通りそのまま実装すると、順序関係の保存と推移の計算などでパフォーマンス上あまり効率的ではありません。ローカルなイベント発生時のカウンタインクリメントと送受信イベント時のカウンターの比較・マージによって効率よくルールH1,H2,H3を満たす実装が論理時計です。

論理時計は以下のルールに沿って動作します

(ルールC1) 各プロセスは初期状態において、時計の時刻t=0である
(ルールC2) 受信以外のイベントeを行うときに、時計の時刻を1増やす
(ルールC3) メッセージ送信イベントeを行うときには、送信イベントeの発生時刻t(e)をメッセージに付加して送る
(ルールC4) メッセージ受信イベントeを行うときには、受信したメッセージに付加された時刻をt'とすると、t←max(t,t')+1として、この値をイベントeの発生時刻t(e)とする

論理時計を使うことで以下のことがわかります。

イベントeとe'でe→e'ならt(e)<t(e')

逆は成り立ちません。t(e)<t(e')ならe→e'ということは言えません。 たとえば下記の図だとt(a1)<t(c2)ですが、a1→c2ではありません。

f:id:yuyubu:20190327195010p:plain
t(a1)<t(c2)だがa1→c2ではない

ベクトル時計

論理時計より強力なベクトルクロックでt(e)<t(e')ならe→e'を成り立たせることができます。 プロセス数n,iэ{1,2,...n}の時ベクトル時計では各プロセスPiがベクトル時計Vi=(v1,v2,...vn)を持ちます。

ベクトル時計は以下のルールV1~V4で実現できます

(V1)各プロセスは初期状態において、ベクトル時計の時刻V=(0,0,...,0)である。
(V2) プロセスPiは受信以外のイベントeを行うときに、ベクトル時計の時刻V=(v1,v2,...,vn)にたいして、vi←vi + 1を行ったV'にベクトル時計の値をへんこうし、この値V'をイベントeの発生時刻V(e)とする
(V3) メッセージ送信イベントeを行うときには、送信イベントeの発生時刻V(e)をメッセージに付加して送る
(V4) プロセスPiがメッセージ受信イベントeを行うときには、受信したメッセージにふかされた時刻をV'=(v1',v2',...,vn')とすると、vj←max(vj,vj')(1<=j<=n)を実行し、さらにvi ← vi + 1を行った値にベクトル時計のアタを変更し、この時刻をイベントeの発生時刻V(e)とする

以下はこのベクトル時計Vを使う例です。ベクトル時計を青字で、論理時計を赤時で引き続き示しています。

f:id:yuyubu:20190327203433p:plain
a1→c2に順序関係がないことがV(a1)<V(a2)が成り立たないという結果からわかる

  • V(b2)=(1,2,2)とV(c2)=(0,0,2)ではV(c2)<V(b2)の大小関係があるのでc2→b2の前後関係があることがわかります。
  • V(a1)=(1,0,0)とV(c2)=(0,0,2)には大小関係がありませんので、a1とc2が並行であることがわかります。

この記事は「分散システム(情報工学レクチャーシリーズ)」の第2章 時刻と時計の個人的まとめです。

分散処理システム (情報工学レクチャーシリーズ)

分散処理システム (情報工学レクチャーシリーズ)