---
title: 時間とクロック
url: https://doc.liz6.com/ja/distributed-systems/01-basic-theory/02-time-and-clocks
locale: ja
area: distributed-systems
tags:
- 分散システム
- クロック
- Lamport
- ベクトルクロック
- TrueTime
- Spanner
- NTP
- PTP
- 論理時間
- distributed-systems
- basic-theory
date: 2026-06-30
modified: 2026-07-16
description: 分散型システムにはグローバルクロックが存在しない——2つのノード上のタイムスタンプを直接比較することはできない。Lamport論理クロック（happens-before）からベクトルクロック（並行性の検出）、そしてTrueTime（GPS＋原子時計）に至るまで、それぞれの「クロック」は、一見単純な「イベントの先后」という問題を、異なるコストのトレードオフの中で追求している。
---

# 時間とクロック

> 分散システムにはグローバルクロックが存在しない——2つのノード上のタイムスタンプを直接比較することはできない。Lamport論理クロック（happens-before）からベクトルクロック（並行性の検出）、そしてTrueTime（GPS＋原子時計）に至るまで、それぞれの「クロック」は、一見単純な「イベントの先后」という問題を、異なるコストのトレードオフの中で追求している。

## 問題: グローバルクロックの欠如

単一マシン上では `gettimeofday()` を用いて、イベントAとBの先后を比較できる。しかし分散システムでは、Aがノード1で 12:00:00.000 に発生し、Bがノード2で 12:00:00.001 に発生した場合——Aが先であると確定できるだろうか？できない。なぜなら、2つのノードのクロックが完璧に同期することは不可能だからだ。NTPによる同期精度は約1msであり、1ms以内のイベント順序は物理時間だけでは判断できない。

## Lamport論理クロック (1978)

Leslie Lamportの洞察：因果関係を判断するために物理時間が必要なのではない——重要なのは、**happens-before関係がタイムスタンプに反映されること**を保証することだ。

### アルゴリズム

各ノードは整数のカウンター `C` を維持し、初期値は0とする：

1. ローカルイベントが発生（メッセージ送信を含む）：`C = C + 1`、イベントのタイムスタンプ = C
2. メッセージを送信する際、自身の現在の C を添付する
3. メッセージを受信（タイムスタンプ = C_msg）：`C = max(C, C_msg) + 1`、受信イベントのタイムスタンプ = C

性質：**a が b より前に発生する場合 (a happens-before b)**、`C(a) < C(b)` となる。しかし逆は成り立たない——`C(a) < C(b)` であっても a → b とは限らない（並行イベントがたまたま異なるカウンター値を持つ可能性がある）。

### 分散排他制御アルゴリズム (Lamport Mutex)

論理クロックを用いて、セントレス（中央ノードなし）の排他制御を実現する：

1. ノード i が臨界領域に入る場合：全ノードに `REQUEST(ts_i, i)` を送信
2. リクエストを受信したノード j：臨界領域にいない、かつ入る予定もない場合、`REPLY` を返信
   臨界領域にいる、または自分のリクエストの優先度が高い場合 (ts_j < ts_i) → 返信を遅延させる
3. ノード i が全 REPLY を受信後 → 臨界領域に入る
4. 臨界領域から退出 → 全ノードに `RELEASE` を送信

利点：単一障害点がなく、完全に分散されている。欠点：3(N-1) 件のメッセージが必要であり、単一ノードの障害がシステム全体のブロックを引き起こす可能性がある。

## ベクトルクロック

Lamportクロックの限界：`C(a) < C(b)` から a → b を逆推論できない。ベクトルクロックはこの問題を解決する。

### データ構造

各ノードは長さ N のベクトル `V[1..N]` を維持する。`V[i]` は、ノード i が何回イベントを発生させたか、そのノードが把握している値である。

```
V_a = [3, 5, 2]  意味: ノード1は、自身で3つのイベント、ノード2で5つ、ノード3で2つのイベントが発生したことを知っている
```

### アルゴリズム

1. ノード i でイベントが発生：`V[i] = V[i] + 1`
2. メッセージを送信する際、現在の V を添付する
3. メッセージを受信（添付された V_msg）：`V[k] = max(V[k], V_msg[k]) for all k`、その後 `V[i] = V[i] + 1`

### 比較ルール

- `V(a) < V(b)` (a が b より前に発生): V(a) の各要素が V(b) の対応する要素以下であり、かつ少なくとも1つが厳密に小さい
- `V(a)` と `V(b)` は比較不可：k, j に対して V(a)[k] < V(b)[k] かつ V(a)[j] > V(b)[j] となる場合 → 並行イベント

### 実践的な応用

Dynamo/Riak KV はベクトルクロックを用いて競合を検出する：`get(key)` がベクトルクロック `V_old` を返す際、クライアントが修正後 `put(key, value, V_old)` を実行する。サーバー上の現在のバージョンが `V_cur` の場合、`V_cur` と `V_old` を比較する：

- `V_cur < V_old`: 直接上書き（クライアントが現在のバージョンを確認して修正した）
- `V_cur > V_old`: 拒否（クライアントが古いバージョンに基づいて修正した）→ read-modify-write が必要
- 比較不可: 並行修正 → 競合解決が必要（アプリケーション層でのマージ、または複数のバージョン（sibling）の保持）

## Google TrueTime (Spanner)

最も過激な産業実践：原子時計とGPSを用いて、グローバルなデータセンターに有界なクロックの不確実性区間を提供する。

### TT.now() は区間 [earliest, latest] を返す

保証：真の時間は必ずこの区間に含まれる。区間の幅は通常約1〜7ms（GPS/原子時計の同期状態による）。

### Spanner の外部一貫性

Spanner のトランザクションは、TrueTime を用いて最も強力な外部一貫性（linearizability よりも強い——データセンター間のリアルタイム順序）を保証する：

```
コミット待機: トランザクションのコミットタイムスタンプ = TT.now().latest
              トランザクションがレプリカで有効になる前、TT.after(commit_ts) = True となるまで待機
              → 全ノードが見るコミット順序が真の時間と一致することを保証
```

### なぜハードウェアが必要なのか

ソフトウェアでは、有界な誤差を持つクロックを提供することは不可能である——NTP は誤差を見積もるのみであり、ネットワーク遅延の非対称性とジッターにより、誤差の境界は不明瞭になる。TrueTime の保証は、GPS/原子時計の物理的特性に由来する：原子時計の周波数誤差は 10^-13 未満である。

## NTP/PTP の実践

NTP (Network Time Protocol): UDPパケットの交換を通じてサーバーとの時間偏差を見積もる。精度は約1ms（LAN）、約10ms（WAN）。課題：

- **ジャンプ**: NTP が大きな偏差を突然補正 → クロックが巻き戻る → `CLOCK_MONOTONIC` はこのジャンプを露呈するが、壁掛け時計の時間は遡る
- **振動**: NTP が継続的に補正 → クロックの周波数が継続的に微小に変化 → 単調時間を依存するPrometheus TSDB が影響を受ける可能性がある（ただしPrometheusはスクレイピングタイミングに `CLOCK_MONOTONIC` を使用）
- **同期失敗**: NTPサーバーに到達不可 → クロックのドリフトが蓄積 → 数時間〜数日後には誤差が秒単位になる

PTP (Precision Time Protocol, IEEE 1588): データセンターレベルの時間同期、精度は約100ns。ハードウェアサポート（NICのタイムスタンプ機能）が必要。金融取引（MiFID II 準拠）や Spanner の代替クロックソースに使用される。

## 参考

- **論文**: "Time, Clocks, and the Ordering of Events in a Distributed System" (Lamport, 1978)
- **論文**: "Spanner: Google's Globally-Distributed Database" (2012, TrueTime セクション)
- **論文**: "Virtual Time and Global States of Distributed Systems" (Mattern, 1989 — ベクトルクロック)

*Keywords: Lamport clock, vector clock, happens-before, TrueTime, Spanner, NTP, PTP, logical time*