ゴシップと障害検知

実装: distributed/gossip/ / 実行: go test ./distributed/gossip/

CRDT でまとめ方は用意できたが、誰に届けるかが空いていた。全員が全員を見張ると通信は台数の2乗になる。ゴシップは毎周期1台だけ選ぶ。同時に障害検知も解いていて、返事が無いのは相手の死かもしれないし自分との断線かもしれない。1台では区別できないので他に頼み、それでも駄目なら疑いという中間状態に置く。

この章で作るもの

CRDT の章で、後からまとめられる形を作った。まとめ方が決まっていれば、どの順で届いても同じ値に落ち着く。

だが、そこには話していなかったことがある。そもそも誰に届けるのか。

素朴には全員に配ればよい。だがそれだと、1回の更新で台数ぶんの通信が出る。さらに、全員が全員の生死を見張るなら、通信は台数の2乗になる。100台なら1万通り。1000台なら100万通り。台数を増やすほど、増やしたぶん以上に重くなる。

ゴシップの答えは、毎周期ランダムに1台だけ選んで話しかけることになる。1台が出す通信は台数に関係なく一定で、それでも知らせは全体に広まる。噂が広まるのに、全員が全員に話す必要がないのと同じだ。

そしてこの仕組みは、もう1つ別の問題を同時に解いている。障害検知だ。

話しかけて返事が無ければ死んだ、としたいところだが、それでは足りない。返事が無いのは、相手が死んだからかもしれないし、自分と相手の間だけが切れているからかもしれない。1台では区別できない。

  ① 全員が全員を見張る            ② ゴシップ

     a ──┬── b                      a ──→ ? (毎周期ランダムに1台)
     │ ╲ │ ╱ │                      b ──→ ?
     │  ╳    │                      c ──→ ?
     │ ╱ │ ╲ │                      d ──→ ?
     c ──┴── d                      e ──→ ?

     通信は 台数²                    通信は 台数
     100台で 1万通り                 100台で 100通り


  返事が無いとき

     a ──✕──→ b       この時点で分かるのは「a から b に届かない」だけ

     a ──→ c ──→ b   c から届いた → b は生きている。a と b の間だけの問題
     a ──→ d ──→ b

     どこからも届かない → 疑う(まだ死んだとは決めない)


  疑いから死までの間に、本人が反論できる

     c が b を疑う         b {Suspect, 番号 0}
     b が起きて主張        b {Alive,   番号 1}   ← 本人だけが番号を上げられる
     まとめる              b {Alive,   番号 1}   ← 番号が大きいほうが勝つ

     他人が「生きている」と言っても番号は同じなので、疑いのほうが勝つ

返事が無い理由は2つある。他に頼んで初めて区別できる。それでも駄目なら、即断せず疑う

順に見ていく。

1台が出す通信を台数から切り離す: 毎周期1台だけ選ぶ。それでも知らせは広まる
1台では死を判定できない: 他に頼んで初めて、相手の死と自分との断線を区別できる
主張できるのは本人だけ: 疑いを覆せるのは本人が上げた番号だけになる

① 1台が出す通信を台数から切り離す

進め方はこうなる:


// Round は1周期進める。
//
// 各ノードが1台だけ選んで問い合わせる。返事が無ければ他の何台かに頼み、
// それでも駄目なら疑う。疑ってから一定の周期が過ぎたら死んだと決める。
func (s *Sim) Round() {
	for _, name := range s.names {
		if s.down[name] {
			continue
		}
		s.probe(s.nodes[name])
		s.expire(s.nodes[name])
	}
	s.tick++
}

// probe は1台を選んで問い合わせる。
func (s *Sim) probe(n *Node) {
	target := s.pick(n)
	if target == "" {
		return
	}

	s.Pings++
	if s.reachable(n.Name, target) {
		s.exchange(n, s.nodes[target])
		return
	}

	// 直接は届かない。他の何台かに頼んでみる。
	// ここを飛ばすと、自分と相手の間だけが切れている場合も死んだことにしてしまう。
	if s.askOthers(n, target) {
		s.exchange(n, s.nodes[target])
		return
	}

	cur := n.view[target]
	if cur.State == Alive {
		cur.State = Suspect
		n.view[target] = cur
		n.suspectAt[target] = s.tick
		s.logf(n.Name + " が " + target + " を疑い始めた")
	}
}

// pick は問い合わせる相手を1台選ぶ。死んだと決めた相手は選ばない。
func (s *Sim) pick(n *Node) string {
	var cand []string
	for _, m := range s.names {
		if m != n.Name && n.view[m].State != Dead {
			cand = append(cand, m)
		}
	}
	if len(cand) == 0 {
		return ""
	}
	return cand[s.next(len(cand))]
}

// askOthers は他の何台かに、代わりに問い合わせてもらう。
//
// 誰か1人でも届いたなら、相手は生きている。自分に届かないことと、
// 相手が死んでいることを、ここで初めて区別できる。
func (s *Sim) askOthers(n *Node, target string) bool {
	asked := 0
	for _, m := range s.names {
		if asked >= s.cfg.Indirect {
			break
		}
		if m == n.Name || m == target || s.down[m] {
			continue
		}
		asked++
		s.Pings++
		if s.reachable(m, target) {
			s.logf(n.Name + " は " + target + " に届かないが、" + m + " からは届いた")
			return true
		}
	}
	return false
}

// exchange は互いの見立てを交換する。知らせはこれに相乗りして広まる。
func (s *Sim) exchange(a, b *Node) {
	for _, m := range b.Members() {
		a.apply(m)
	}
	for _, m := range a.Members() {
		b.apply(m)
	}
}

// expire は、疑ってから一定の周期が過ぎた相手を死んだと決める。
func (s *Sim) expire(n *Node) {
	for _, m := range n.Members() {
		if m.State != Suspect {
			continue
		}
		since, ok := n.suspectAt[m.Name]
		if !ok {
			n.suspectAt[m.Name] = s.tick
			continue
		}
		if s.tick-since >= s.cfg.SuspectFor {
			m.State = Dead
			n.view[m.Name] = m
			delete(n.suspectAt, m.Name)
			s.logf(n.Name + " が " + m.Name + " を死んだと決めた")
		}
	}
}

probe が1周期に選ぶのは1台だけになる。相手はランダムで、死んだと決めた相手は選ばない。

これで、1台が出す問い合わせは台数に関係なく一定になる。テストで、3台の系と10台の系で、1周期あたり1台につき1回ずつであることを固定した。全員が全員を見張る形なら、10台の系では1周期に90回になっていたはずのところだ。

知らせの広まり方は exchange にある。問い合わせのついでに、互いの見立てをまるごと交換する。専用の通信を出すのではなく、生死を確かめる通信に相乗りさせる。テストで、直接話していない相手にも知らせが届き、最後には全員の見立てがそろうことを固定した。

広まる速さは指数的になる。知っているノードが毎周期おおよそ倍になっていくので、台数が増えても周期数は対数でしか伸びない。台数を10倍にしても、行き渡るまでの周期は数倍にしかならない。

② 1台では死を判定できない

askOthers がこの章のいちばん大事な部分になる:


// Config は検知の性質を決める。
type Config struct {
	// Indirect は、返事が無かったときに頼む相手の数。
	Indirect int
	// SuspectFor は、疑ってから死んだと決めるまでの周期数。
	SuspectFor int
}

// Sim は台数ぶんのノードを、周期を1つずつ進めながら動かす。
type Sim struct {
	cfg   Config
	names []string
	nodes map[string]*Node

	down  map[string]bool            // 落ちているノード
	block map[string]map[string]bool // 一方向に届かない組

	rnd  uint64
	tick int

	// Pings はこの系で行われた問い合わせの総数。台数への依存を見るために数える。
	Pings int
	Log   []string
}

// New は台数と設定から系を作る。seed で選び方を固定するので、結果は再現する。
func New(cfg Config, seed uint64, names ...string) *Sim {
	s := &Sim{cfg: cfg, nodes: map[string]*Node{}, down: map[string]bool{},
		block: map[string]map[string]bool{}, rnd: seed | 1}
	s.names = append([]string(nil), names...)
	sort.Strings(s.names)
	for _, n := range s.names {
		s.nodes[n] = newNode(n, s.names)
	}
	return s
}

// next は seed から決まる乱数を返す(実時間を使わないための線形合同法)。
func (s *Sim) next(n int) int {
	s.rnd = s.rnd*6364136223846793005 + 1442695040888963407
	return int((s.rnd >> 33) % uint64(n))
}

// Node は1台を返す。
func (s *Sim) Node(name string) *Node { return s.nodes[name] }

// Tick は現在の周期を返す。
func (s *Sim) Tick() int { return s.tick }

// Kill はノードを落とす。落ちたノードは返事をしない。
func (s *Sim) Kill(name string) {
	s.down[name] = true
	s.logf(name + " が落ちた")
}

// Revive はノードを起こす。起きたノードは番号を上げて生存を主張する。
//
// 主張できるのは本人だけになる。他人は疑うことしかできない。
func (s *Sim) Revive(name string) {
	delete(s.down, name)
	n := s.nodes[name]
	me := n.view[name]
	me.Inc++
	me.State = Alive
	n.view[name] = me
	s.logf(name + " が起きて、番号 " + itoa(me.Inc) + " で生存を主張する")
}

// Block は from から to への通信だけを止める。両方とも生きているのに届かない状態。
func (s *Sim) Block(from, to string) {
	if s.block[from] == nil {
		s.block[from] = map[string]bool{}
	}
	s.block[from][to] = true
	s.logf(from + " から " + to + " へ届かなくなった(どちらも生きている)")
}

// reachable は from から to へ問い合わせが通るかを返す。
func (s *Sim) reachable(from, to string) bool {
	if s.down[from] || s.down[to] {
		return false
	}
	return !s.block[from][to]
}

自分から届かないとき、他の何台かに代わりに問い合わせてもらう。誰か1人でも届いたなら、相手は生きている。届かないのは自分との間の問題だと分かる。

テストで、a から b への通信だけを止めた状態で、a が b を生きていると見続けることを固定した。同時に、頼める相手が居ない設定(2台だけ、間接の依頼を 0)にすると疑い始めることも固定した。区別できるかどうかが、この一手にかかっている。

これが無いと何が起きるか。ネットワークの一部が不安定になっただけで、そこから見えないノードが次々に死んだことにされる。生きているノードが外され、そこに載っていた仕事が動き、また別のところで同じことが起きる。検知の誤りが、そのまま障害になる。

後の Kubernetes 編で扱う Service も Cluster Autoscaler も、「あのノードは生きているか」という判定の上に乗っている。判定を間違えれば、その上の全部が間違える。

③ 主張できるのは本人だけ

それでもどこからも届かないとき、即座に死んだとは決めない。


// State は、あるノードから見た他のノードの様子。
type State int

const (
	// Alive は生きていると見ている。
	Alive State = iota
	// Suspect は疑わしい。まだ死んだとは決めていない。
	Suspect
	// Dead は死んだと決めた。
	Dead
)

func (s State) String() string {
	return [...]string{"生きている", "疑わしい", "死んだ"}[s]
}

// Member は1台についての見立て。
//
// Inc は本人だけが上げられる番号になる。疑いをかけられた本人が「生きている」と
// 反論するとき、この番号を1つ上げて広める。番号が大きいほうが新しいので、
// 古い疑いを上書きできる。[論理時計](clock)の単調な数え上げと同じ役目になる。
type Member struct {
	Name  string
	State State
	Inc   int
}

// Merge は2つの見立てを1つにする。
//
// 番号が大きいほうが勝つ。同じなら、悪い知らせのほうが勝つ。
// この規則は可換で結合的で冪等なので、[CRDT](crdt)と同じように、
// どの順で何度届いても同じところへ落ち着く。
func Merge(a, b Member) Member {
	switch {
	case a.Inc > b.Inc:
		return a
	case b.Inc > a.Inc:
		return b
	case a.State >= b.State:
		return a
	default:
		return b
	}
}

まず疑いという中間状態に置く。SuspectFor 周期のあいだ、本人に反論の機会を残す。テストで、猶予を延ばすと死んだと決まるまでが遅くなることを固定した。誤検知を減らすことと、早く気づくことは、この目盛りの両端になる。

反論の仕掛けが Inc になる。疑われた本人が「生きている」を広めるとき、この番号を1つ上げる。Merge は番号の大きいほうを採るので、新しい主張が古い疑いを上書きする。

大事なのは、他人は番号を上げられないことになる。番号が同じなら悪い知らせのほうが勝つので、他人が「あの人は生きているよ」と言っても疑いは消えない。消せるのは本人だけだ。テストで、同じ番号での「生きている」が疑いに負けること、本人が番号を上げたときだけ通ることを固定した。

この規則は可換で結合的で冪等なので、CRDT の章で見た形そのものになっている。番号の単調さは論理時計の数え上げと同じ役目で、状態の優先順位が決定的なまとめ方を与えている。3つの章が、ここで1つに合流する。

動かす

下のデモは、5台の系を動かす。ノードを落とすと、疑いを経て死んだと決まるまでが見える。落とさずに一方向だけ切ると、間接の問い合わせが働いて生きていると判定され続ける。起こし直すと、本人が番号を上げて疑いを覆す。

デモゴシップと障害検知周期 0 ・問い合わせ 0 回

見る側＼見られる側abcde

a生生生生生

b生生生生生

c生生生生生

d生生生生生

e生生生生生

全員が生きていると見ている。周期を進めると、1台ずつ問い合わせて見立てを交換する

(まだ何も起きていない)

表の行が見る側、列が見られる側。緑が生きている、黄が疑わしい、赤が死んだ。小さい数字は本人が上げた番号で、これが大きいほうが勝つ。「e を落とす」と、疑いを経てから死んだと決まっていく。落とさずに「a→b だけ切る」と、a は b に届かないのに生きていると判定し続ける。他の台に頼んで確かめているからで、これが無いと断線しただけのノードが次々に外される。

設計の観点

1台あたりの負荷を台数から切り離す: 全員を見張る形は、台数を増やせないところで詰む
確かめてから決める: 1つの観測で判断しない。別の経路から見た結果を足す
中間状態を用意する: 疑いを置くだけで、誤検知と検知遅れの間に目盛りが作れる
反論の権利を本人に限る: 誰でも取り消せると、疑いが意味を持たない
まとめ方を決定的にする: 状態の広がり方が CRDT なら、届く順も回数も気にしなくてよい
検知の誤りは障害になる: 生きているノードを外すと、その上の全部が連鎖する

対照と実例

	全員が全員を見張る	中央が見張る	ゴシップ(SWIM)
通信	台数の2乗	台数	台数(1台あたり一定)
中央の必要	無し	あり	無し
中央が落ちたら	(該当なし)	何も分からない	(該当なし)
断線と死の区別	台ごとにばらつく	中央から見た1つの見方だけ	間接の問い合わせで区別
広まる速さ	即時	即時	対数の周期数

裏どり:

SWIM(2002): Scalable Weakly-consistent Infection-style Process Group Membership。直接の問い合わせ、間接の問い合わせ、相乗りによる伝播という3つの組み合わせ
suspicion 機構: 元の SWIM 論文の拡張。即座に死と決めず、疑いを広めて反論を待つ
incarnation number: 本人だけが上げられる単調な番号。疑いを覆す権利を持ち主に限定する
実装例: HashiCorp の memberlist(Consul、Nomad)、Cassandra や Riak のゴシップ、Docker Swarm
Kubernetes は別の形: ノードの生死は kubelet からの status の書き戻しで判定する。中央が見張る形になっている
伝播の速さ: 各周期で知っている数がおおよそ倍になるので、全体に行き渡るまでは台数の対数に比例する

簡略化したこと

同時実行なし: 1周期の中で順に動かす。実際は全員が同時に動く
遅延なし: 問い合わせは届くか届かないかの2択で、遅れて届く場合は扱わない
相乗りの上限なし: 見立てをまるごと交換する。実物は1通に載せる件数を絞る
参加と離脱なし: 名前は最初に決めたきりで、後から増えない
周期の同期なし: 全員が同じ周期で動く前提にしている
重み付けなし: 相手の選び方は一様。実物は最近確かめていない相手を優先することがある

参考資料

SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol — Das ら(2002)。原論文
memberlist — SWIM に suspicion 機構などを足した実装
実装: distributed/gossip

ゴシップと障害検知 ​

この章で作るもの ​

① 1台が出す通信を台数から切り離す ​

② 1台では死を判定できない ​

③ 主張できるのは本人だけ ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​