全順序放送
実装:
distributed/total// 実行:go test ./distributed/total/
因果順序の配送では並行なものに順序を付けなかった。付けないから誰も待たずに済み、切れても止まらない。だが同じ口座への引き落としが並行に起きると、台ごとに適用する順が違えば残高が食い違う。全員で順をそろえる作り方は2つあり、どちらも決める人と待つ相手が要る。待つから止まる。そしてそろっていても、答えが問いより先に来ていることがある。
この章で作るもの
因果順序の配送では、原因の順だけを守って、並行なものには順序を付けなかった。付けないから誰も待たずに済み、切れても止まらない。あの章はそこで終わって、「そろえたいなら合意が要る」と書いて先を Raft に投げた。
その間が空いている。この章がそこになる。
順序を付けないという判断が通らない場面がある。残高 1000 円の口座に、800 円の引き落としと 500 円の引き落としが並行に届いたとする。どちらか片方は拒否されなければならない。台 X が 800 を先に適用して 500 を拒否し、台 Y が 500 を先に適用して 800 を拒否したら、残高が食い違ってしまう。どちらの順でもよいが、全員が同じ順でなければならない。
全員が同じ順で受け取ることを全順序という。作り方は大きく2つになる。
① 番号を振る係を置く
a ──┐ ┌──→ a
b ──┼──→ [係] 1,2,3,... ───┼──→ b 全員が番号順に渡す
c ──┘ └──→ c
速い。だが係が止まると番号が付かず、全員が止まる
② 全員で決める
a ──時刻1「A」──→ b, c 各自が時刻つきで出す
c ──時刻1「C」──→ a, b 同時刻は名前で決める(a < c)
渡す条件: 先頭より後の時刻を、他の全員から聞いていること
b の待ち行列 [A(a,1), C(c,1)]
b が聞いた時刻 a:1 b:3 c:1
▲ ▲
A の 1 より後を c から聞いていない → 渡せない
係は要らない。だが全員から聞くので、1台黙ると全員が止まる順に見ていく。
- 誰が決めるかを決める問題になる: 係を1台置くか、全員で決めるか。決める人は必ず要る
- 全員が同じ順で間違えることがある: 順がそろうことと、順が正しいことは別になる
- 待つ相手が居るから止まる: 因果順序が止まらなかったのは、誰も待っていなかったからだ
① 誰が決めるかを決める
いちばん単純なのは、番号を振る係を1台置くことになる:
// Assign は係にメッセージが届いたことにして、番号を付ける。
//
// 番号は係に届いた順に付く。送り手が出した順でも、原因の順でもない。
// ここが後で効いてくる。
func (s *SeqSim) Assign(from, body string) Numbered {
s.assigned++
m := Numbered{Seq: s.assigned, From: from, Body: body}
s.logf("係が「" + body + "」に番号 " + itoa(m.Seq) + " を付けた")
return m
}
// Deliver は to に番号つきメッセージが届いたことにする。渡せたものを返す。
//
// 番号順にしか渡さない。手前の番号が来ていなければ、後ろは預かる。
func (s *SeqSim) Deliver(to string, m Numbered) []Numbered {
n := s.nodes[to]
if m.Seq <= n.next {
s.logf(to + " に " + itoa(m.Seq) + " が届いたが、すでに渡し済み")
return nil
}
for _, h := range n.hold {
if h.Seq == m.Seq {
s.logf(to + " に " + itoa(m.Seq) + " が届いたが、すでに預かっている")
return nil
}
}
n.hold = append(n.hold, m)
var out []Numbered
for {
i := -1
for j, h := range n.hold {
if h.Seq == n.next+1 {
i = j
break
}
}
if i < 0 {
break
}
h := n.hold[i]
n.hold = append(n.hold[:i], n.hold[i+1:]...)
n.next = h.Seq
n.Delivered = append(n.Delivered, h)
out = append(out, h)
}
if len(out) == 0 {
s.logf(to + " に " + itoa(m.Seq) + " が届いたが、" + itoa(n.next+1) + " がまだ来ていないので渡せない")
} else {
s.logf(to + " が " + itoa(len(out)) + " 件渡した(次は " + itoa(n.next+1) + ")")
}
return out
}係に届いた順に番号を付けて配る。受け取る側は番号順にしか渡さず、手前の番号が来ていなければ預かる。テストで、3台に別々の順で届けても、全員が同じ順で渡すことを固定した。
やっていることは 因果順序の配送と同じ形になる。届いたものをすぐ渡さず、条件がそろうまで預かる。違うのは条件だけで、あちらは「原因を渡したか」、こちらは「手前の番号を渡したか」になる。届くことと渡すことを分けるという骨格は変わらない。
係を置きたくないなら、全員で決める手がある。各自が時刻つきで要求を出し、待ち行列に並べる。時刻は論理時計の数え上げで、同時刻は名前で決める:
// sortByStamp は時刻で並べ、同時刻は名前で決める。
//
// 同じ時刻のものに順序を付けるのは、[論理時計](clock)の LamportLess と同じ手になる。
// 名前で決めるので、どの台で並べても同じ順になる。
func sortByStamp(ms []Msg) {
sort.SliceStable(ms, func(i, j int) bool {
return clock.LamportLess(ms[i].T, ms[i].From, ms[j].T, ms[j].From)
})
}名前で決めるので、どの台で並べても同じ順になる。テストで、a と c が同じ時刻 1 で出したとき、どの台でも a が先に並ぶことを固定した。
渡す条件は1つになる:
// deliverable は待ち行列の先頭を渡してよいかを返す。
//
// 条件は1つだけになる。先頭より後の時刻を、他の全員から聞いていること。
// 聞いていれば、それより小さい時刻の要求はもう出てこない。
// 過半数ではなく全員なのが、この方式の弱点そのものになる。
func (s *VoteSim) deliverable(n *VoteNode, head Msg) bool {
for _, k := range s.names {
if k == head.From {
continue
}
if n.heard[k] <= head.T {
return false
}
}
return true
}
func (s *VoteSim) drain(n *VoteNode) []Msg {
var out []Msg
for len(n.queue) > 0 {
sortByStamp(n.queue)
head := n.queue[0]
if !s.deliverable(n, head) {
return out
}
n.queue = n.queue[1:]
n.Delivered = append(n.Delivered, head)
out = append(out, head)
}
return out
}先頭より後の時刻を、他の全員から聞いていること。聞いていれば、それより小さい時刻の要求はもう出てこないと分かる。だから安心して渡せる。
だが要求を出していない台からは何も聞けない。そこで、時刻だけを知らせる合図が要る。上の筋書きでは、a と c が時刻 1 で出したあと、全員が1巡だけ合図を送り合うと、3台とも A → C の順で渡す。
そろったかどうかは、記録どうしを見比べれば分かる:
// Agreed は、全員が同じ順で渡し終えているかを返す。
//
// 途中まででも、短いほうが長いほうの先頭に一致していればよい。
// 全順序が守れているなら、先に進んでいる台の記録は、遅れている台の記録の続きになる。
func Agreed(orders ...[]string) bool {
for i := 1; i < len(orders); i++ {
a, b := orders[0], orders[i]
if len(b) < len(a) {
a, b = b, a
}
for j := range a {
if a[j] != b[j] {
return false
}
}
}
return true
}進み具合が違ってもよい。全順序が守れているなら、先に進んでいる台の記録は、遅れている台の記録の続きになっているはずだ。テストで、そろうことと、そろうまでは誰も渡さないことを固定した。
② 全員が同じ順で間違えることがある
ここが、この章でいちばん言いたいところになる。
係方式で、因果順序の配送の冒頭と同じ筋書きを流してみる。a が「質問」を出し、b がそれを見て「回答」を出す。ただし係には回答のほうが先に届く。
a ──「質問」───────────────┐
│ 経路が遅い
b ─見てから─「回答」──┐ │
▼ ▼
[係] 回答=1 質問=2
│
┌───────────────┼───────────────┐
▼ ▼ ▼
a b c
回答 → 質問 回答 → 質問 回答 → 質問
3台とも完全に一致している。一致したまま、答えが問いより先に来ているテストで、3台の記録がそろっていることと、その順が 回答 → 質問 であることを、両方固定した。そろっているのに間違っている。
つまり、全順序にすれば因果順も付いてくる、というのは成り立たない。順がそろうことと、順が正しいことは別の性質になる。両方が要るなら、両方を別々に用意することになる。実際、ISIS は原因の順を守る配送(CBCAST)と全順序の配送(ABCAST)を別々に提供し、全順序のほうを原因の順の上に載せる形をとっていた。
同じ形は、後のクォーラムの章でも出てくる。条件(R + W > N)を満たしていても、緩め方しだいで最新が読めないことがある。条件を満たしていることと、欲しい性質が手に入ることは、確かめないと一致しない。
③ 待つ相手が居るから止まる
もう1つの違いが可用性になる。
係方式では、係が止まると番号が付かない。番号が付かなければ誰も渡せない。さらに、番号に穴が空くだけでも後ろが全部止まる。テストで、番号 2 が届かないと 3 以降が渡らず、2 が届いた瞬間にまとめて渡ることを固定した。
全員で決める方式には係が居ないので、その1点は消える。だが代わりに全員から聞く必要が出る。過半数ではなく全員だ。1台が黙るだけで、その台より後の時刻を誰も聞けなくなり、全体が止まる。テストで、c が要求を受け取ったまま返事をしないと b が渡せなくなること、c が一言知らせれば動き出すことを固定した。
待つ相手 1台切れたら
────────────────────────────────────────────────
因果順序 居ない 止まらない(原因が来ないものだけ保留)
全順序(係) 係 係が落ちれば全員止まる
全順序(全員) 全員 誰が落ちても全員止まる
全順序(合意) 過半数 少数が落ちても続くだから Raft の位置が見えてくる。合意は、待つ相手を全員から過半数へ落とす仕組みになる。過半数なら少数が落ちても集められるので、止まらない範囲が広がる。全順序放送と合意が同じ強さだと言われるのは、この意味になる。
そして、どこまで落としても消えない性質がある。全順序は、多数派に届かなければ答えを返せない。切断されて少数側に取り残された台は、待つしかない。因果順序が切れても答えを返せたのは、誰も待っていなかったからだ。この差は作りの巧拙ではなく、求めた性質そのものから来ている。
動かす
下のデモは2つの作り方を切り替えられる。係方式では、回答が先に係へ届いた筋書きを進めると、全員がそろって間違える。全員方式では、待ち行列と「各台から聞いた時刻」が見え、1台を黙らせると止まる。
筋書きは終わり
係を置く方式は、係に届いた順に番号が付き、全員がその番号順に渡す。番号は原因の順を見ていないので、 回答が先に係へ着けば全員がそろって回答を先に渡す。全員で決める方式は係を置かない代わりに、 先頭より後の時刻を他の全員から聞くまで渡さない。だから 1 台が黙るだけで全体が止まる。
設計の観点
- そろえる必要があるかを先に問う: 並行を並行のまま扱えるなら、待たずに済む
- 決める人を1点に置くか、配るか: 置けば速いが単一障害点になる。配れば待つ相手が増える
- 待つ相手の数がそのまま可用性になる: 全員 → 過半数 → 誰も待たない、の順で止まりにくくなる
- そろうことと正しいことを分けて確かめる: 全員一致は、全員が同じように間違っている場合も含む
- 性質は重ねられる: 原因の順の上に全順序を載せれば両方手に入る。1つの仕組みに両方を期待しない
- 穴が空いたときの出口を用意する: 番号順の配送は、1つ欠けるだけで後ろが全部止まる
対照と実例
| 因果順序 | 係を置く全順序 | 全員で決める全順序 | 合意による全順序 | |
|---|---|---|---|---|
| 決める人 | 居ない | 係1台 | 全員 | 過半数 |
| 待つ相手 | 居ない | 係 | 全員 | 過半数 |
| 1台落ちたら | 続く | 係なら全員止まる | 全員止まる | 少数なら続く |
| 原因の順 | 守る | 守らない | 守らない | 守らない |
| 通信の量 | 台数 | 台数 | 台数の2乗 | 台数 |
| 代表例 | COPS、ISIS の CBCAST | Kafka のパーティション、Zab の leader | Lamport(1978) | Raft、Multi-Paxos |
裏どり:
- Lamport(1978): Time, Clocks。時刻と名前で全順序を作り、全員からの返事を待つ方式の原型。「全員から聞く」がそのまま弱点になることも論文中で触れられている
- ISIS(1987): 原因の順(CBCAST)と全順序(ABCAST)を別々に提供した。全順序が因果順を含まないという事実への、実装としての答え
- 全順序放送と合意は等価: 一方があれば他方が作れることが知られている。だから全順序を求めた時点で、合意と同じ代償を払うことになる
- Kafka: パーティション単位で1台のリーダーが順を決める。係方式そのもので、順序が保証されるのはパーティションの中だけ
- Zab / Raft: リーダーが順を決めるところは係方式と同じだが、リーダー自身を過半数で選び直せるところが違う。待つ相手が過半数に落ちている
簡略化したこと
- 係の選び直しなし: 係が止まったら止まったまま。誰を係にするかを安全に決める話は Raft
- 合意の実装なし: 過半数で決める形は作っていない。この章は「全員」まで
- 原因の順との重ね合わせなし: 全順序の下に因果順序を敷く形は作っていない。両方が要るならそうする
- 喪失と再送なし: 誰にいつ届くかは呼び出し側が明示する
- 合図の間隔なし: 時刻を知らせる合図は手で送る。実物は一定の間隔で自動的に流す
- 通信量の削減なし: 全員方式は全員が全員へ送るので台数の2乗になる。実物は間引く
参考資料
- Lamport, Time, Clocks, and the Ordering of Events in a Distributed System(1978)
- Birman, Joseph, Reliable Communication in the Presence of Failures(1987) — CBCAST と ABCAST
- Défago, Schiper, Urbán, Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey(2004) — 作り方の全体像
- 実装: distributed/total