因果順序の配送
実装:
distributed/causal// 実行:go test ./distributed/causal/
論理時計で前後を見分けられるようになったが、見分けたあとに何をするかは別の話になる。放送では届く順が送った順と違うので、投稿より先に返信が見えることがある。送り手ごとの通し番号では直らない。原因と結果が別の送り手にまたがるからだ。届いてもすぐには渡さず、原因を渡すまで預かる。判定は数の大小だけで書ける。
この章で作るもの
論理時計の章で、2つの出来事のどちらが先かを見分ける道具を作った。ベクタークロックを比べれば、前後があるのか並行なのかが分かる。
だがそこで分かったのは「見分けられる」ところまでで、それを使って何をするかは別の話になる。この章がその使いどころになる。
放送でメッセージを流すと、届く順は送った順と違う。経路が違えば追い越しが起き、届かずに再送されることもある。すると、こういうことが起きる。
- a が「質問」を流す
- b がそれを見て「回答」を流す
- c には回答が先に届く
c から見ると、答えだけが先に現れて、何の答えなのか分からない。原因より結果が先に見えている。
素直な直し方は、送り手ごとに通し番号を振ることになる。同じ相手からの2件目が先に来たら、1件目が来るまで待つ。これで同じ相手の追い越しは直る。
だが、上の例はこれでは直らない。回答は b からの1件目だからだ。原因が a で結果が b という、送り手をまたいだ関係になっている。番号は送り手ごとにしか付いていないので、この関係が見えない。
a ──「質問」──┐ c への経路が遅い
│
b ────────────┴─→ 見てから ──「回答」──→ c ← 先に着く
質問 ──────→ c ← 後から着く
送り手ごとの番号で見ると
回答 = b からの 1 件目 → 待つ理由が無い → 渡してしまう
質問 = a からの 1 件目 → 後から渡る
c が見る順: 回答 → 質問
流した時点で見ていたものを載せると
質問 {a:1} a が自分の1件目として流した
回答 {a:1, b:1} b は質問を見てから流した(a:1 が原因の印)
c は渡し終えた数 {} なので、回答の a:1 に届いていない → 預かる
質問が届いて {a:1} になると、回答の条件も満たす → まとめて渡る
c が見る順: 質問 → 回答順に見ていく。
- 届く順は原因の順ではない: 送り手ごとの番号では、送り手をまたぐ原因と結果を守れない
- 待つ条件は数え上げだけで書ける: 時刻も順序づけも要らない。2つの不等式で済む
- 決まらないところは決めない: 並行なものには順序を付けない。そろえたいなら合意が要る
① 届く順は原因の順ではない
まず、何を守るかを2通り用意する:
// Mode は配る順の決め方。
type Mode int
const (
// Fifo は送り手ごとの順だけを守る。同じ相手からの追い越しは直るが、
// 別の相手をまたぐ原因と結果は守れない。
Fifo Mode = iota
// Causal は原因の順を守る。原因になったものを渡すまで、結果は保留する。
Causal
)
func (m Mode) String() string {
if m == Causal {
return "原因の順"
}
return "送り手ごとの順"
}送り手ごとの順は、同じ相手からの追い越しだけを直す。テストで、同じ相手からの2件目が先に届くと1件目を待つこと、そして冒頭の例では回答が先に渡ってしまうことを、両方固定した。
大事なのは、これが実装の手抜きではないことになる。TCP は接続ごとに順序を守るので、1本の接続だけを見れば送り手ごとの順は自然に手に入る。TCPの章で作った番号と再送が、まさにそれをしている。だが接続は相手ごとに別なので、相手をまたいだ順序は誰も見ていない。
これは分散システムでよく出る形になる。それぞれの部品は自分の担当範囲で正しいのに、範囲をまたぐ性質は誰の担当でもない。1本の経路だけを見ていても分からないことがある、という同じ形は、後のゴシップの章(1台では相手の死を判定できない)でも出てくる。
② 待つ条件は数え上げだけで書ける
メッセージには、流した時点で送り手が見ていたものを載せる:
// Message は放送で流す1件。
//
// Deps が「送った時点で送り手が見ていたもの」になる。送り手自身の分は
// この放送を含めた数で、他人の分は渡し終えた数。[ベクタークロック](clock)
// そのものを載せている。
type Message struct {
From string
Seq int
Body string
Deps clock.Vector
}
// deliverable は、このメッセージを今渡してよいかを返す。
//
// 送り手 j からのメッセージ m を、seen まで渡し終えた側で見るとき:
//
// ① m.Deps[j] == seen[j] + 1 この送り手の次の1件であること(飛ばさない)
// ② m.Deps[k] <= seen[k] (k≠j) 送り手が見ていたものを自分も見ていること
//
// ①だけなら送り手ごとの順で、②が付くと原因の順になる。
// 判定に要るのは数の大小だけで、時刻も順序づけも要らない。
func deliverable(m Message, seen clock.Vector, mode Mode) bool {
if m.Deps[m.From] != seen[m.From]+1 {
return false
}
if mode == Fifo {
return true
}
for k, want := range m.Deps {
if k == m.From {
continue
}
if want > seen[k] {
return false
}
}
return true
}条件は2つの不等式になる。送り手の分は「ちょうど次の1件」で、それ以外は「自分も見ている」。前者だけなら送り手ごとの順で、後者が付くと原因の順になる。この一行の差が、この章のすべてになる。
要るのは数の大小だけで、時刻も、誰が先かの判定も要らない。論理時計の Compare すら呼んでいない。前後を見分ける道具は、比較のためでなく待つ条件を書くためにここで使われている。
受け取り側は、渡せないものを預かりに置く:
// Node は1台。渡し終えた数と、まだ渡せていない預かりを持つ。
type Node struct {
Name string
mode Mode
seen clock.Vector
hold []Message
// Delivered は渡した順の記録。自分が出した放送もここに入る。
Delivered []Message
}
func newNode(name string, mode Mode) *Node {
return &Node{Name: name, mode: mode, seen: clock.Vector{}}
}
// Seen は渡し終えた数を返す。
func (n *Node) Seen() clock.Vector { return n.seen.Clone() }
// Held はまだ渡せていないメッセージを返す。
func (n *Node) Held() []Message { return append([]Message(nil), n.hold...) }
// Order は渡した順の本文を返す。
func (n *Node) Order() []string {
out := make([]string, len(n.Delivered))
for i, m := range n.Delivered {
out[i] = m.Body
}
return out
}
// Recv は1件届いたことにして、渡せるものをすべて渡す。渡した順に返す。
//
// 届いたものをそのまま渡すのではなく、いったん預かりに入れてから
// 渡せるかを見る。1件渡すと条件が変わるので、渡せなくなるまで繰り返す。
func (n *Node) Recv(m Message) []Message {
if n.known(m) {
return nil
}
n.hold = append(n.hold, m)
return n.drain()
}
// known は、すでに渡したか預かっているかを返す。二度渡さないための番人。
func (n *Node) known(m Message) bool {
if m.Deps[m.From] <= n.seen[m.From] {
return true
}
for _, h := range n.hold {
if h.From == m.From && h.Seq == m.Seq {
return true
}
}
return false
}
// drain は渡せるものが無くなるまで渡す。
func (n *Node) drain() []Message {
var out []Message
for {
i := -1
for j, m := range n.hold {
if deliverable(m, n.seen, n.mode) {
i = j
break
}
}
if i < 0 {
return out
}
m := n.hold[i]
n.hold = append(n.hold[:i], n.hold[i+1:]...)
n.apply(m)
out = append(out, m)
}
}
// apply は渡したことにして、数え上げを進める。
func (n *Node) apply(m Message) {
n.seen[m.From] = m.Deps[m.From]
n.Delivered = append(n.Delivered, m)
}Recv が「届く」で、Delivered に入るのが「渡す」になる。この2つを分けているのが、この章の全部だ。届いたものをそのまま上に渡してしまうと、もう順序は直せない。
1件渡すと数え上げが進むので、預かりの中に渡せるようになるものが出る。だから渡せなくなるまで繰り返す。テストで、逆順に届いた3件が、先頭が届いた瞬間にまとめて渡ることを固定した。
そして代償がある。原因が来なければ、結果は永遠に渡らない。テストで、原因を届けないまま結果を10回届けても渡らないことを固定した。待つ側には、それが遅れなのか永久に来ないのかを区別する手立てが無い(分散はなぜ難しいかの部分故障そのもの)。だから、どこかで諦める仕掛けを別に足すことになる。
動かす
下のデモは、冒頭の筋書きを1手ずつ進める。3手目で c に回答が先に届く。配る順を切り替えると、同じ筋書きで結果が変わる。
次の手 — c に「質問」が遅れて届く
各メッセージには「流した時点で送り手が見ていたもの」が載っている。受け取り側は、それが自分の 渡し終えた数に収まっているかを見て、収まっていなければ預かりに置く。収まった瞬間に、預かりも まとめて渡る。送り手ごとの順に切り替えると、別の相手からの原因を見ないので、回答が質問より 先に渡ってしまう。
③ 決まらないところは決めない
守るのは原因の順だけで、それ以外は決めない:
// Sim は放送する側と受け取る側をまとめて動かす。
type Sim struct {
mode Mode
names []string
nodes map[string]*Node
Log []string
}
// New は台を並べる。mode で配る順の決め方を選ぶ。
func New(mode Mode, names ...string) *Sim {
s := &Sim{mode: mode, nodes: map[string]*Node{}}
s.names = append([]string(nil), names...)
for _, n := range s.names {
s.nodes[n] = newNode(n, mode)
}
return s
}
// Node は1台を返す。
func (s *Sim) Node(name string) *Node { return s.nodes[name] }
// Names は台の一覧を返す。
func (s *Sim) Names() []string { return append([]string(nil), s.names...) }
// Mode は配る順の決め方を返す。
func (s *Sim) Mode() Mode { return s.mode }
// Broadcast は from から全員へ流す。出した本人にはその場で渡る。
//
// 送り手は自分の数を1つ進めてから、その時点で見ているものをまるごと載せる。
// 「この放送より前に自分が見たもの」が、そのまま原因の一覧になる。
func (s *Sim) Broadcast(from, body string) Message {
n := s.nodes[from]
n.seen[from]++
m := Message{From: from, Seq: n.seen[from], Body: body, Deps: n.seen.Clone()}
n.Delivered = append(n.Delivered, m)
s.logf(from + " が「" + body + "」を流した")
return m
}
// Deliver は to にメッセージが届いたことにする。渡せたものを返す。
//
// 届くことと渡すことを分けているのが、この章の全部になる。
func (s *Sim) Deliver(to string, m Message) []Message {
n := s.nodes[to]
got := n.Recv(m)
switch {
case len(got) == 0 && len(n.hold) > 0:
s.logf(to + " に「" + m.Body + "」が届いたが、まだ渡せない(預かり " + itoa(len(n.hold)) + " 件)")
case len(got) > 1:
s.logf(to + " に「" + m.Body + "」が届いて、預かりもまとめて " + itoa(len(got)) + " 件渡した")
case len(got) == 1:
s.logf(to + " に「" + m.Body + "」が届いて、そのまま渡した")
default:
s.logf(to + " に「" + m.Body + "」が届いたが、すでに渡し済み")
}
return got
}
// Broadcasts は from から流して、指定した相手にその場で届ける。
func (s *Sim) Broadcasts(from, body string, to ...string) Message {
m := s.Broadcast(from, body)
for _, t := range to {
s.Deliver(t, m)
}
return m
}
// Relation は2つのメッセージの前後を返す。並行なら Concurrent。
func Relation(a, b Message) clock.Ord { return clock.Compare(a.Deps, b.Deps) }互いを見ないまま流された2件は並行なので、台ごとに渡る順が違ってよい。テストで、a の「犬」と c の「猫」が Concurrent であること、そして b には 犬 → 猫、c には 猫 → 犬 の順で渡ることを固定した。どちらも原因の順は満たしている。
全員で同じ順にそろえたいなら、それは別の仕組みになる。全順序の放送は、実質的に合意と同じ強さを持つ。それをやるのが後の Raft で、1つのログの順を全員で決める。
だから選ぶことになる。原因の順で足りるなら、合意を回さずに済むので、切れても止まらない。順序を完全にそろえたいなら、合意の代償を払う。因果順序は、切断されても答えを返し続けられる範囲で、いちばん強い約束という位置にある。
設計の観点
- 届くことと渡すことを分ける: 受け取った瞬間に上へ流すと、もう順序は直せない
- 守る範囲を宣言する: 何を保証して何を保証しないかを先に決める。「たまたま順序が合う」に頼らない
- 範囲をまたぐ性質は誰の担当でもない: 経路ごとに正しくても、経路をまたぐ順序は別に用意する
- 待つ仕掛けには諦める仕掛けを添える: 原因が来ない場合の出口が無いと、預かりが永久に残る
- 持ち回る情報の大きさを見る: ベクタは台数に比例する。台数が増えると1件あたりの荷物が増える
- 決めなくてよいものを決めない: 並行を並行のまま扱えば、合意を回さずに済む
対照と実例
| 何も守らない | 送り手ごとの順(FIFO) | 原因の順 | 全順序 | |
|---|---|---|---|---|
| 同じ相手の追い越し | 直らない | 直る | 直る | 直る |
| 相手をまたぐ原因と結果 | 直らない | 直らない | 直る | 直る |
| 並行なものの順 | ばらばら | ばらばら | ばらばら | 全員そろう |
| 必要なもの | 無し | 送り手ごとの番号 | 台数ぶんのベクタ | 合意 |
| 切断されても答えるか | 答える | 答える | 答える | 答えない |
裏どり:
- ISIS(1987): Birman と Joseph。CBCAST(原因の順)と ABCAST(全順序)を分けて提供した最初期の実装。「どこまで守るかを選ばせる」という形はここから
- happens-before(1978): Lamport。原因の順という言葉の元になった定義
- 因果一貫性の位置: 切断されていても答えを返し続けられる範囲では、これがいちばん強い約束になることが知られている。全順序を求めた時点で、切断中は答えられなくなる
- MongoDB: causally consistent session。セッションの中で「自分が読んだものより古いものを読まない」を保証する
- COPS / Eiger: 地理分散のストアで因果一貫性を実現した系統。ベクタを台数ぶん持ち回るのではなく、明示的な依存だけを載せて荷物を減らしている
- 荷物の大きさ: ベクタは台数に比例するので、台数が増えると1件あたりの付帯情報が増える。実物では依存の間引きや圧縮が要る
簡略化したこと
- 依存の間引きなし: ベクタをまるごと載せる。実物は直前の依存だけを載せるなどして減らす
- 参加と離脱なし: 台の名前は最初に決めたきりで、後から増えない
- 喪失の検知と再送なし: 誰にいつ届くかは呼び出し側が明示する。届かないものは届かないまま
- 諦める仕掛けなし: 預かりに寿命が無い。実物は一定時間で再要求するか、諦めて先へ進む
- 全順序なし: 並行なものの順は決めない。決める話は Raft に置いた
- 状態の合流なし: メッセージを順に渡すところまで。並行な更新をどうまとめるかは CRDT
参考資料
- Birman, Joseph, Reliable Communication in the Presence of Failures(1987) — ISIS。CBCAST と ABCAST
- Lamport, Time, Clocks, and the Ordering of Events in a Distributed System(1978)
- Lloyd et al., Don't Settle for Eventual (COPS)(2011) — 明示的な依存で荷物を減らす
- 実装: distributed/causal