体系ガイド · 基礎から応用へ

論理時計と因果関係を追う

三プロセスの送受信へLamport番号を付け、因果なら数値順が保たれる性質と、逆が成り立たない反例を確認します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 秒数ではなく出来事の前後を追う
  2. 増分と受信の規則を決める
  3. 三プロセスの履歴に番号を付ける
  4. 同じ番号を全順序へ拡張する
  5. 経過時間や競合検出へ流用しない
  6. DAGの模型で性質を検査する
  7. 時計を持たないメッセージと再送を考える
  8. 受信番号と逆命題の課題
  9. この記事をロゲイアに質問する理解を確かめる

秒数ではなく出来事の前後を追う

注文受付Aから在庫Bへ要求を送り、Bから通知Cへ結果を送る場合、各マシンの壁時計だけでは、表示時刻の順が因果関係と一致するとは限りません。Bの時計が遅れていれば、受信の時刻が送信より小さく見えることがあります。Lamport時計は、プロセス内の順序とメッセージの送受信を使い、原因となる出来事の後へ大きい番号を付ける方法です。前提は部分障害とメッセージの履歴です。番号は経過時間の測定ではなく、因果順序に矛盾しない印です。

出来事aがbより前という関係は、同じプロセスで先に起きた、aの送信をbが受信した、それらをつないで前後が導ける、という規則で作ります。この関係をhappens-beforeと呼びます。どちらへも道がない二つの出来事は、ここでは並行です。実際の物理世界で同時刻だったという意味ではなく、観測した送受信とプロセス順から前後が決まらないという意味です。ログの印字順を、そのまま因果関係の定義へ使わないでください。

増分と受信の規則を決める

各プロセスの時計を0から始め、ローカルな出来事と送信の前に1増やします。送信にはその番号を付けます。番号mのメッセージを受信したら、自分の時計cとmの大きい方に1を足し、max(c,m)+1をその受信の番号にします。同じメッセージについて、受信の番号が送信より必ず大きくなるためです。初期値と、送信前か送信後に増やすかは、教材とコードで揃えます。規則が違う資料の数値を並べても、因果の性質が同じなら番号の差だけで誤りとは判断しません。

番号を増やす操作が複数スレッドから競合する実装では、その更新自体を正しく同期する必要があります。模型の辞書を一つずつ更新したことを、並列実装の証明にはしません。またプロセスが再起動して0へ戻るなら、過去と同じ番号を再利用できます。長く使う識別にはプロセスIDや世代、必要な永続状態を検討します。Lamport時計の規則を採用しただけで、メッセージの重複排除や、全プロセスが同じ時点の番号を共有することまで成立するわけではありません。

三プロセスの履歴に番号を付ける

Aの出来事aを1、Bの独立したbを1とします。Aの次の送信cは2です。Bがcを受けるdでは、自分の1と受信した2を比べて3になります。Bの次の送信eは4です。Cはそれと独立のfを1に進めた後、eを受けるgでmax(1,4)+1=5となります。表ではcからd、eからgが通信の矢印です。AからB、BからCをつなげると、aはgより因果的に前なので1<5が保たれます。

bとcには、この履歴ではどちら向きの因果の道もありません。それでもbの番号1はcの2より小さくなっています。これが「因果的に前なら時計も小さい」は成り立ち、「時計が小さいなら因果的に前」は成り立たない反例です。番号が違うだけで依存があったと判断しないでください。壁時計のcを101、dを90と書いても、メッセージの送受信の前後は変わりません。壁時計のずれと、論理番号が守る規則を同じ表で比較します。

出来事プロセス・関係論理番号
aAのローカル1
bBのローカル1
cAから送信2
dBでcを受信3
eBから送信4
fCの独立な出来事1
gCでeを受信5

同じ番号を全順序へ拡張する

a、b、fは全て1です。安定したプロセスIDをA<B<Cと並べ、(論理番号, プロセスID)の辞書順で比べれば、この三つにも順を付けられます。各プロセス内の番号が重ならないなどの前提も必要です。全順序は、因果関係のある組の順を壊さずに、並行な組へ便宜上の順を足します。IDで先にしたことを、AがBの原因だったという説明へ変えないでください。順番を必要とする表示や模型には使えても、関係そのものの発見ではありません。

全順序のラベルを作れることと、各ノードが同じ全イベント集合を今すぐ知っていることも違います。まだ届いていない小さい番号のイベントがあるかもしれません。後から到着したイベントをどこへ入れるか、いつ出力順を確定するかには別の情報が必要です。Lamport時計だけで合意やリーダー選出が完了するとは言いません。また小さい番号の要求を全て先に実行するだけで、期限や公平性が守られるとは限りません。ラベルを使うアルゴリズムの追加規則へ戻ります。

経過時間や競合検出へ流用しない

番号が2から5へ進んだから、3 ms経ったとは言えません。ローカル出来事が多いプロセスは、通信しなくても番号が速く増えます。タイムアウトには経過時間を測る時計を使い、因果のラベルを秒数へ変換しません。同じ番号だったから同時発生とも言えません。時計の役割を、期限の伝播の教材と比べてください。そちらの単調時計も、このガイドの論理時計とは違うものです。どちらも単調に進み得ますが、意味する量が異なります。

二つの更新の番号が違っても、並行かもしれません。並行性を判定したい場合は、ベクトル時計など、因果の情報をさらに保持する方式を検討します。ただしその分だけメタデータやメンバー管理の費用が増えます。Lamport時計は不要という結論ではなく、必要な問い合わせに合う情報量を選ぶという判断です。重複を避けたいだけなら、要求の安定IDと処理済み記録が主な責務になる場合もあります。求める性質を名前でまとめず、何を比較し何を判断したいかを明記します。

DAGの模型で性質を検査する

付属実験では、プロセス内の前後と送受信を有向非巡回グラフとして与え、依存が既に計算済みの順に処理します。各出来事の先祖集合を求め、全ての因果辺と推移的な関係で時計が増えていることをassertします。bとcの反例、壁時計がcとdで逆転する例も確認します。これは入力で定めた履歴の模型で、実ネットワークのメッセージやスレッドの競合を観測した結果ではありません。模型の保証と入力した関係を一緒に示します。

順序付きのイベント列を使っていても、そのリストで先に出たことを全て因果辺にはしません。A、B、Cが独立して進む可能性を保つためです。実装を変更してリスト順の通し番号を付ければ、因果関係に矛盾しない数字は作れても、分散したローカル時計を計算する実験とは変わります。何を既に知っている入力として渡したかを確認しましょう。未知の送信イベントを参照した入力や、循環する依存を許す拡張では、拒否や別の処理が必要です。

時計を持たないメッセージと再送を考える

同じ送信イベントのメッセージが二回届くと、受信側はその都度ローカル時計を進めることができます。時計が進んだことは、新しい業務要求だと判断した証拠ではありません。重複排除にはメッセージや操作の安定IDを使い、受信という出来事と業務効果を分けます。逆に送信番号を失ったメッセージへ受信側だけの番号を付けても、元の送信との順を検査する材料が不足します。

観測系へログを集めるときも、ログが届いた順と元の出来事の順は違います。バッファリングや再送があり得るためです。相関ID、プロセスの世代、ローカル順、送受信の対応を残せば、後から因果の辺を再構成する助けになります。番号一つへ全情報を詰め込もうとせず、問い合わせたい関係に必要な記録を選んでください。

表示の便利さと、業務判断に必要な因果の根拠を分けて使います。

受信番号と逆命題の課題

課題は、時計7のプロセスが番号4のメッセージを受けた場合です。解答はmax(7,4)+1=8で、5へ戻しません。逆に時計2で番号9を受ければ10です。自分だけ1増やして3にすると、送信9より受信3が小さくなり、守りたい性質を壊します。受信規則を選んだ理由を、送受信の矢印と番号へ戻して説明してください。待ち時間が何msだったかは、この計算から求まりません。

追加課題はbの1とcの2について、bがcの原因だと結論できるかです。解答はできません。この履歴では双方へ道がなく、異なる番号の並行イベントです。同じ番号ならIDで順を足せても、因果を足したことにはなりません。時計の更新、因果辺、全順序の便宜、物理時間の四つを別々に説明できれば到達点です。分散トランザクションへ進む際も、時刻を大きく並べるだけで複数資源が原子的に確定するとは考えないようにします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 16

学習コースから次を選ぶ