物理クロック論理クロック

物理クロック

ほぼすべてのコンピューターには、内蔵されている水晶発振器によって時刻を計算しています。

水晶は安定した周波数の電気信号を発振するため、振動子として広く使われています。

パソコンの電源が切れたり、充電が切れたりしても、マザーボードに内蔵されているCMOSバッテリーにより水晶は時刻を計算し続けれます。

この水晶発振器は個体ごとに誤差があるため、異なるコンピューターでは全て同じ周波数で動作はしません。

(月で±15秒とか)

時刻同期

上記の通り、複数台のコンピューターがあると、徐々に時間はずれていき、読み出したときに異なる時刻を示すようになります。

これはclock skewと呼ばれます。

手動で時刻を合わせても発振器の誤差の影響などですぐに時刻がずれてしまうので、手動ではなく自動的にコンピュータの時刻同期ができれば、これらの問題を解決することができます。

これを実現するために用いられるのが時刻を同期させるプロトコルがNTPです。

www.spring8.or.jp

ja.wikipedia.org

xtech.nikkei.com

NTP

NTP は、正確な運針をもつ NTP サーバに一致させ、その後時刻を一定の誤差範囲内で維持する仕組みになっています。

つまり、NTP サーバの時刻変更に対して、NTP クライアントの時刻がこれに同期するというものではありません。

NTP プロトコルは、下記 3つで構成されています。

リファレンスクロック(stratum 0) : 原子時計やGPS、電波時計などを使った精度の高い外部時計をもったサーバー
NTP サーバ(stratum 1〜) : 信頼できる上位サーバから提供される時刻を利用して自分の時刻を保持し、他のマシンあるいは下位のサーバに時刻を提供する
NTP クライアント : NTP サーバから時刻を提供される

NTPはネットワークを介して時刻同期を行います。

単純に相手のサーバが通知してきた時刻を信頼するだけでは、ネットワークの遅延により時刻のずれが発生してしまいます。

そのため、NTPではサーバ・クライアント間の通信において、 NTPメッセージを送信した時刻、受信した時刻を、サーバ・クライアントそれぞれがメッセージの中に含めており、これらを使ってネットワークでの遅延時間を推測し、ずれの少ない時刻同期を図っています。

en.wikipedia.org

下記シーケンスを元に考えてみます。

f:id:Spring_MT:20210520162421p:plain

クライアントとサーバーは時刻はずれているとします。

パケットの往復時間(ラウンドトリップ)Δは下記になります。

Δ = (Tc2- Tc1) - (Ts2 - Ts1)

また、時刻差(タイムオフセット) θ はNTPサーバーの時刻と往復時間の半分(パケットの片道は往復の1/2として固定している) と NTPクライアントの時刻の差となります。

θ = (Ts2 + Δ / 2) - Tc2 = Ts2 + ((Tc2- Tc1) - (Ts2 - Ts1)/2) - Tc2 = (Ts2 + Ts1) / 2 - (Tc2 + Tc2) / 2

θ に基づいてNTPクライアントの時刻を調整します。

参照

www.infraexpert.com

www.nic.ad.jp

ja.wikipedia.org

その他の時刻同期の仕組み

NTP以外にも時刻同期をする仕組みはあります。

その一つにBerkeleyアルゴリズムを用いるものがあります。

NTPはクライアントが定期的にNTPサーバー(タイムサーバー)に通信して時刻を同期しているのに対して、Berkeleyアルゴリズムではタイムサーバーが全てのマシンに対して定期的にポーリングし、応答に基づいてメッセージの往復時間を計算し、現在の時間を平均化し、ローカルクロックを調整する必要があることをクライアントに通知します。

ja.wikipedia.org

論理クロック

クロックスキューの問題などで、物理クロックの完全な同期は現実的には難しいです。

しかし、例えばシステム中のイベントのタイムラインにおいて、イベントの相対順序を決めるためには時刻の絶対値は必ずしも必要ありません。

イベントAがイベントBの前に起こることを知る必要がある場合、Ta＝2、Tb＝6でも、Ta＝4、Tb＝10であっても、Ta ＜ Tbが満たされていれば問題ありません。

このようなシチュエーションにおいてはインクリメントされるカウンタに基づいてイベントの順序付けを行うほうが安全性が高いです。

物理クロックではなく、インクリメントされるカウンタに基づくものを論理クロックと呼びます。

Lamportの論理クロック

Lamportの論文( https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf ) では、クロックの同期は必要だが、絶対値的なものである必要はないことを示しました。

2つのプロセスが相互作用しない場合(並行な場合)、クロックを同期させる必要はなく同期していないことは観測できないため、問題にはならない、さらに通常重要なのは、すべてのプロセスが正確な時間に合意することではなく、イベントが発生する順序に合意することであると述べています。

論理クロックの同期のために、happens-before 関係を定義しています。

happens-before 関係 → は以下の3つの条件を満たしている最小の関係としています。(happens-before は日本語では事前発生と訳されます。データ指向アプリケーションデザイン p 199参照)

aとbが同じプロセスのイベントで、bの前にaがくる(aがbよりも先に起こる)場合、a → bとなる。
aがあるプロセスによるメッセージの送信であり、bが他の別のプロセスによる同じメッセージの受信であるならば、a → b (これはaがbに因果関係がある)
a → b、b → cならば、a → c

また、a ↛ b かつ b ↛ a で、aとbのイベントが異なるイベントは concurrent(並行) と呼びます。

つまり、a bのどちらも先に行われていない、互いに相手を知らないのであれば、これらは並行していることになります。

全てのイベントに対して、全てのプロセスが合意する時間の値、論理クロックを定義します。

ここでは、論理クロックは下記のように定義します。

各プロセスPiのクロックCiは、プロセス Piにおける任意のイベント a に番号 Ci<a> を割り当てる関数である
このシステム全体としてのクロックは、任意のイベント a に数値 C<a> を割り当てる関数 C とする。
- bがPjというプロセスのイベントであれば、 C = Cj となるつまり、C はすべてのプロセスが合意する時間の数値を割り当てる

その上で、この論理クロックがイベントの発生する順序に基づいて正しく振る舞うための条件は、あるイベント aが他のイベント bよりも先に発生した場合、a は b よりも早い時間に発生すべきということになります。

これは、

イベントaとbにおいて、 a → b であれば C<a> < C

となります。

これは、前述の happens-beforeの関係を考えると、

C1 プロセスPiのイベントaとbにおいて、aがbの前に発生した場合、 Ci<a> < Ci
C2 プロセスPiのメッセージ送信 a でプロセスPjでのメッセージの受信 b の場合 Ci<a> < Cj

の2つの条件を満たすことになります。

これらの条件を満たす実装のルールは下記の通りです。

各プロセスPiは連続する2つのイベントの間にCiを増加させる。つまりa → b であれば bのイベントの前にCiを増加させる 2-a. イベントaはプロセスPiで mというメッセージ送信のイベントだとすると、メッセージ m にはタイムスタンプ Tm = Ci <a> が含まれている 2-b. Piとは別のプロセスPjがメッセージ mを受信すると、PjはCjの値を現在の値以上かつ、Tmの値より大きい値をセットする

イベントaがプロセスPiで Ci<a> に発生すると、システム全体の論理クロック C<a> = Ci<a> に割り当てることで分散した環境での論理クロックが構築できます。