論理時計とベクタークロック
実装:
distributed/clock// 実行:go test ./distributed/clock/
時計が合っていないなら、時刻では順序を決められない。だから時刻を測るのをやめて、出来事を数える。これで原因が結果より小さい数を持つことは保証されるが、逆は言えない。無関係な2つにも順序がついてしまう。本当に無関係かを知りたければ、数を1つでなくノードの数だけ持つ。同時を見分けられることが、次の話の入口になる。
この章で作るもの
分散した複数のマシンは、それぞれ自分の時計で動いている。時計は少しずつずれるし、どれだけずれているかも正確には分からない。だから、他のノードが書いた時刻を自分の時計と比べても、どちらが先に起きたかは決められない。
それでも困らない場面はある。「自分が最後に見てからどれだけ経ったか」のような、自分の時計1つで測れる経過だけで判断が済むなら、ずれは問題にならない(後の leader election の章がその形になる)。
だが、そうはいかない場面がある。複数のノードで起きた出来事に順序をつけたいときだ。「この書き込みとあの書き込み、どちらが先か」を知りたい場面は必ず出てくる。レプリケーションで2台に別々の書き込みが届いたとき、どちらを残すのか。時計が合っていないなら、時刻では決められない。
答えは、時刻を測るのをやめて出来事を数えることになる。
自分のところで何か起きたら数を1つ増やす。誰かに知らせるときは、その数を一緒に送る。受け取った側は、自分の数と受け取った数の大きいほうから続きを数える。これだけで、原因は結果より小さい数を持つ、が保証される。この数え方を、考案者の名前から Lamport 時計と呼ぶ。
そして、この形には片道しかない仕掛けがある。
a1 a2 a3
a ───●──────●─────────────────────●───────────────→
1 2 ╲ 3
╲ 知らせ
╲
b1 ▼b2 b3
b ─────────●───────●────────●──────────────────────→
1 3 4 ╲
╲ 知らせ
c1 ▼c2
c ─────────●─────────────────────────────●─────────→
1 5
Lamport の数だけで並べると(同点はノード名で解く)
a1(1) b1(1) c1(1) a2(2) a3(3) b2(3) b3(4) c2(5)
↑
b1 のほうが小さいので、b1 → a2 に見える
ベクタで見ると
a2 {a:2} ←→ b1 {b:1} どちらも相手を知らない = 同時
a3 {a:3} ←→ b2 {a:2 b:2} 隣に並んでいるのに、これも同時
b2 {a:2 b:2} a2 より後(a のぶんを取り込んでいる)
「原因なら小さい」は言える。「小さいなら原因」は言えない順に見ていく。
- 時刻でなく出来事を数える: 時計を合わせる必要がなくなる
- 約束は片道: 原因なら小さい。だが小さいからといって原因ではない
- 同時を見分けるには、数をノードの数だけ持つ: 見分けられることが、次の話の入口になる
① 時刻でなく出来事を数える
まず、数え上げを1つ持つ形から:
// Lamport は1つのノードが持つ、ただの数え上げ。
//
// 数えているのは時間ではなく、自分が知っている出来事の多さになる。
type Lamport struct {
ID string
t int
}
// NewLamport は 0 から数え始める時計を作る。
func NewLamport(id string) *Lamport { return &Lamport{ID: id} }
// Now は今の値を返す。
func (l *Lamport) Now() int { return l.t }
// Local は自分のところで何か起きたときに呼ぶ。数を1つ進める。
func (l *Lamport) Local() int {
l.t++
return l.t
}
// Send は誰かに知らせるときに呼ぶ。進めた値を、送る印として返す。
func (l *Lamport) Send() int {
l.t++
return l.t
}
// Recv は知らせを受け取ったときに呼ぶ。
//
// 大きいほうから続けるのが肝になる。相手のほうが先に進んでいたら、
// 自分もそこまで追いつく。これで「送信は受信より小さい」が必ず成り立つ。
func (l *Lamport) Recv(remote int) int {
if remote > l.t {
l.t = remote
}
l.t++
return l.t
}
// LamportLess は2つの出来事に全順序をつける。
//
// 数が同じときはノード名で決める。こうすると必ずどちらかが先になるが、
// その順序に因果の意味は無い。並べられることと、意味があることは別になる。
func LamportLess(t1 int, id1 string, t2 int, id2 string) bool {
if t1 != t2 {
return t1 < t2
}
return id1 < id2
}Recv の中身がすべてになる。相手のほうが先に進んでいたら、自分もそこまで追いつく。そのうえで1つ進める。
これだけで、送信は受信より必ず小さくなる。同じノードの中では前の出来事のほうが小さい。この2つが繋がるので、間接的な因果も守られる。テストで、送信を2段挟んだ組でも小さい側が原因になっていることを固定した。
数えているのは時間ではない。自分が知っている出来事の多さになる。誰かから知らせを受け取ると、その相手が知っていたぶんまで一気に増える。何もしていなくても増えることがあるのは、そのためだ。
LamportLess は、この数に全順序をつける。同じ数のときはノード名で決めるので、必ずどちらかが先になる。この「必ず並ぶ」性質は便利で、たとえば分散した処理を一列に並べたいときにそのまま使える。
だが、並べられることと、その順序に意味があることは別になる。
② 約束は片道
ここがこの章の中心になる。
上の図の b1 と a2 を見る。b1 の数は 1、a2 は 2。数だけ見れば b1 が先だ。だが b1 が起きた時点で、b は a のことを何も知らない。a も b のことを知らない。互いに無関係な2つの出来事に、たまたま順序がついている。
テストで、この組について b1 の数のほうが小さいこと、それでも実際には互いを知らないことを、両方固定した。片方だけを固定してもこの章の主張にならないので、同じテストの中で並べてある。
なぜこうなるかというと、数が1つしかないからだ。1つの数に押し込んだ時点で、必ずどちらかが大きくなる。「比べられない」という答えを持てる場所がない。
この片道の性質は、実際の設計に効いてくる。Lamport の数で並べて「後のほうを採用する」とすると、無関係な2つのうち片方が黙って消える。消えたことにも気づかない。「後に書いたほうを勝たせる」規則(last-write-wins、レプリケーションの章で出てくる)が失うものは、これになる。
③ 同時を見分けるには、数をノードの数だけ持つ
// Vector はノードごとの数え上げ。自分が知っている「各ノードでの出来事の数」になる。
type Vector map[string]int
// Clone は写しを返す。元は変えない。
func (v Vector) Clone() Vector {
out := make(Vector, len(v))
for k, n := range v {
out[k] = n
}
return out
}
// Keys はノード名を名前順で返す(表示と比較を決定的にする)。
func (v Vector) Keys() []string {
out := make([]string, 0, len(v))
for k := range v {
out = append(out, k)
}
sort.Strings(out)
return out
}
// Ord は2つのベクタの関係。
type Ord int
const (
// Equal は同じ。
Equal Ord = iota
// Before は左が右の原因になりうる。
Before
// After は右が左の原因になりうる。
After
// Concurrent はどちらも相手を知らない。同時に起きたとみなす。
Concurrent
)
func (o Ord) String() string {
return [...]string{"同じ", "前", "後", "同時"}[o]
}
// Compare は2つのベクタを比べる。
//
// すべての要素で a <= b かつ1つでも a < b があれば、a は b より前になる。
// 逆向きも同じ。どちらでもなければ同時で、これが Lamport では出せない答えになる。
func Compare(a, b Vector) Ord {
aLess, bLess := false, false
seen := map[string]bool{}
for _, k := range append(a.Keys(), b.Keys()...) {
if seen[k] {
continue
}
seen[k] = true
switch {
case a[k] < b[k]:
aLess = true
case a[k] > b[k]:
bLess = true
}
}
switch {
case aLess && bLess:
return Concurrent
case aLess:
return Before
case bLess:
return After
default:
return Equal
}
}
// VClock は1つのノードが持つベクタ。
type VClock struct {
ID string
v Vector
}
// NewVClock は空のベクタから始める時計を作る。
func NewVClock(id string) *VClock { return &VClock{ID: id, v: Vector{}} }
// Now は今のベクタの写しを返す。
func (c *VClock) Now() Vector { return c.v.Clone() }
// Local は自分の要素だけを1つ進める。
func (c *VClock) Local() Vector {
c.v[c.ID]++
return c.Now()
}
// Send は自分の要素を進めて、ベクタごと送る印として返す。
func (c *VClock) Send() Vector {
c.v[c.ID]++
return c.Now()
}
// Recv は受け取ったベクタと自分のベクタを、要素ごとに大きいほうで合わせる。
//
// 要素ごとに最大を取ることが、そのまま「知っていることの合併」になっている。
// 相手が知っていたことは、受け取った時点で自分も知っていることになる。
func (c *VClock) Recv(remote Vector) Vector {
for _, k := range remote.Keys() {
if remote[k] > c.v[k] {
c.v[k] = remote[k]
}
}
c.v[c.ID]++
return c.Now()
}数を1つでなく、ノードごとに持つ。この形をベクタークロックと呼ぶ。受け取ったら要素ごとに大きいほうを取る。この「要素ごとに最大」が、そのまま知っていることの合併になっている。
Compare の判定がこの章のもう1つの山になる。すべての要素で a <= b かつ1つでも a < b があれば、a は b より前。逆向きも同じ。どちらでもなければ同時になる。
この「どちらでもない」という答えを持てることが、数を1つから増やしたことの見返りになる。テストで、b1 と a2 が Concurrent と出ること、因果のある組は Before と出ることを固定した。
代償は大きさになる。動いたノードの数だけ要素が増え、知らせを送るたびにその全部を運ぶ。テストで、5台が順に受け渡すとベクタが5要素になること、Lamport のほうは何台でも数1つのままであることを固定した。ノードが増減する系では、この重さと、消えたノードの要素をいつ捨てるかが問題になる。
同時が見分けられると、何が変わるのか。衝突を検出できるようになる。「どちらが後か」ではなく「どちらも独立に起きた」と分かるので、片方を黙って捨てずに済む。両方を残して後で人に選ばせることも、決まった規則で自動的にまとめることもできる。後者をやるのが、次の章になる。
動かす
下のデモは、上の図の筋書きをそのまま動かす。2つの出来事を選ぶと、Lamport の答えとベクタの答えが並んで出る。答えが割れる組があることが、この章の主張になる。
出来事を2つ選ぶと、2つの時計それぞれの答えが出る。破線の枠は、誰かと同時に起きた出来事
一列には必ず並ぶ。だが赤い印のところは、隣り合っているのに互いを知らない組になっている。 並べられることと、その順序が因果を表すことは別になる。ベクタなら「同時」という3つ目の答えを 持てるので、片方を黙って捨てずに済む。捨てずにどうまとめるかが、次の話になる。
設計の観点
- 合わせられないものは使わない: 時計は合わない。合わないものを判断の根拠にしない
- 「比べられない」を表せる型にする: 1つの数に押し込むと、必ずどちらかが大きくなる。答えが3つ要るなら型も3つ要る
- 並べられることと意味があることは別: 全順序は作れる。作れることと、その順序が因果を表すことは違う
- 検出できないものは直せない: 衝突を検出できて初めて、どう扱うかを選べる
- 重さは参加者の数で決まる: ベクタは動いたノードのぶんだけ増える。台数が動く系では捨て方も要る
- leader electionと対になる: あちらは自分の時計の経過だけで足りる場面、こちらは複数ノードの順序が要る場面
対照と実例
| 物理時計 | Lamport | ベクタ | |
|---|---|---|---|
| 合わせる必要 | ある | 無い | 無い |
| 大きさ | 数1つ | 数1つ | 参加者の数だけ |
| 全順序 | つけられる | つけられる | つけられない |
| 因果の保証 | 無い(ずれる) | 片道だけ | 両方向 |
| 同時の検出 | できない | できない | できる |
| 使いどころ | 人が読むログ | 一列に並べたいとき | 衝突を扱うとき |
裏どり:
- happens-before: 同じノードの中の前後と、送信から受信への向き。この2つの推移閉包が因果の定義になる
- Lamport の定理:
a → bならばL(a) < L(b)。逆は成り立たない、と原論文で明記されている - 全順序への拡張: 同点をノード識別子で解くと全順序になる。相互排除の実装などで使われる
- バージョンベクタ: 出来事でなく更新を数える変種。Dynamo や Riak の衝突検出はこの形になる
- ハイブリッド論理時計: 物理時刻と論理時計を組み合わせ、人が読める値のまま因果を保つ。Spanner の TrueTime や CockroachDB の HLC がこの系統
- 要素の捨て方: 参加者が入れ替わる系では、消えたノードの要素をいつ落とすかが別の問題になる
簡略化したこと
- 順序の入れ替えなし: 知らせは送った順に届く前提にしている。実際には追い越しも起きる
- 紛失なし: 知らせが届かない場合は扱わない
- 参加者は固定: ノードの増減と、それに伴うベクタの要素の整理は扱わない
- 保存なし: 出来事は記録に残すだけで、実際のデータには結びつけない
- ハイブリッドなし: 物理時刻と混ぜる形は文章で触れるだけ
- 要素はまばら: 動いたノードだけを持つ対応表の形にしている。実装によっては固定長の並びを使う
参考資料
- Time, Clocks, and the Ordering of Events in a Distributed System — Lamport(1978)。happens-before と論理時計の原論文
- Detection of Mutual Inconsistency in Distributed Systems — Parker ら(1983)。バージョンベクタによる衝突検出
- 実装: distributed/clock