分散処理を勉強した記録～その2～

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。

今回は、「時計」についてまとめました。

<予約した順番>

航空券の予約システムを使って、
特定の便の特定の座席をAさんとBさんが予約しようとしていました。
Aさんは「プロセス1」、Bさんは「プロセス2」を使って予約処理を実行しました。
結果として、Aさんの「プロセス1」の予約が先に受信しました。
普通に考えれば、Aさんが争奪戦に勝利したかと思います。
しかし、「Bさんの方が先に予約できていた」ことはあり得るでしょうか？
「プロセス2」の方が早く処理できていたのに、
通信経路でロスが生じて「プロセス2」の到着が遅れた、ということがあるかもしれません。

「時計」を各プロセスが持っていれば解決するかもしれませんが、
「完全に同じ時計」を各プロセスが保持するには至難の業です。
時計のクロック粒度はかなり小さく、電波時計を組み込んだとしても完全に一致しません。
NTPサーバーを使ったとしても誤差は生じます。
そのため、「時計」に相当するものを用意します。

<論理時計>

プロセスが3つあり、
それぞれが論理時計を保持しています。
各プロセスのイベントが実行される度に、論理時計の値を+1していきます。

そして、他のプロセスからメッセージを受信した場合は、
論理時計の値を「自分の論理時計の値」と「受信したメッセージの論理時計の値」を比較し、
大きい方に1を加算したものに更新します。
この例では、プロセス2からのメッセージの論理時計の値は「2」、
プロセス1の受信時点での論理時計の値は「1」なので、
「受信した論理時計の値」+１がプロセス1の論理時計の値となります。

しかし、これだけでは完全なものとは言えません。
イベント「a1」の論理時計は「1」で、
イベント「b2」の論理時計は「2」です。
「a1」の後に「b2」が発生したという保証はどこにもありません。

<ベクトル時計>

そこで、各プロセスの値を保持する「ベクトル時計」を使います。
論理時計と同様にイベントが発生する度に値を加算します。

プロセス1はプロセス2からのメッセージを受信します。
プロセス2からのメッセージにはベクトル時計の値(0,2,0)があるので、
(1,0,0)と(0,2,0)を比較します。
「0」と「2」の大きい方を採用し、
(1,2,0)にします。
更に、プロセス1用の値を加算して、(2,2,0)になります。

イベント「a2」とイベント「b2」のベクトル時計の値は「a2」の方が大きく、
「b2」の後に「a2」が発生していることと矛盾しません。

今回はここまでです。ありがとうございました。