【べくとるくろっく】
ベクトルクロック とは？
最終更新:
💡 カウンタの配列で、通信を通じた前後関係を比べる
分散システムで、各ノードのイベントにカウンタの配列を付け、通信を通じた因果的な前後関係を比較する論理時計。実際の時刻や、すべての出来事の一列の順番を表すものではない。
📌 このページのポイント
- 固定したノードごとに1成分を持つ配列で説明できる
- 内部イベントや送信で自分の成分を増やし、受信で情報を取り込む
- 全成分が以下で、少なくとも1成分が小さければ因果的に前
- 比較できない異なるイベントは並行。実時間で同時という意味ではない
ひよこ 普通の時計とどう違うの？
ペンギン先生 何時何分かではなく、ある出来事の情報が別の出来事へ届き得る前後関係を扱うよ。同じノード内の順序と、メッセージの送信から受信への順序を組み合わせて考える。すべての出来事に前後を付けるわけではないんだ。
ひよこ 配列の数字はどう増えるの？
ペンギン先生 AとBの2台なら[A, B]の順にカウンタを持ち、[0, 0]から始める例で考えよう。内部イベントや送信では、自分の成分を1増やす。Aで内部イベントが1回起き、その後送信すると、Aの値は[1, 0]、[2, 0]と進むよ。
ひよこ 受け取ったBはどうするの？
ペンギン先生 Bが[0, 1]のときにAの[2, 0]を受信する例なら、成分ごとの大きい方を取って[2, 1]にし、受信イベントとしてBの成分を1増やして[2, 2]にする。この更新規則なら、Aの情報を受け取ったことも表せるんだ。
ひよこ 配列をどう比べるの？
ペンギン先生 全成分が相手以下で、少なくとも1成分が小さければ因果的に前だよ。[2, 0]は[2, 2]より前で、全部が小さい必要はない。一方、[1, 0]と[0, 1]はどちらも相手以下にならず、並行だと分かるんだ。
ひよこ 並行なら同時に起きたの？
ペンギン先生 実際の時刻が同じという意味ではないよ。このモデルで一方から他方への因果的な経路がないということ。更新の競合を考える材料にはなるけれど、どの値を採用するかまで自動で決める仕組みではないんだ。
まとめ：ざっくりこれだけ覚えればOK！
「ベクトルクロック」って出てきたら「配列で出来事の因果的な前後関係を比べる論理時計」と思えばだいたいOK！
📖 おまけ：英語の意味
「Vector Clock」 ＝ ベクトル時計
💬 複数の成分を持つベクトルで論理時刻を表すよ。各成分には、そのノードの出来事について知っているカウンタ値を持つんだ。