topology spread

実装: orchestration/topology/ / 実行: go test ./orchestration/topology/

スケジューラの章では、Pod を散らすか詰めるかを選んだ。だが何に対して散らすのかは決めていなかった。ノードに均等に置けば1台の障害には耐えられるが、同じ区画の3台に均等なら、その区画が落ちたとき3台とも失う。偏りを数える単位が、そのまま何の障害に備えるかを決めている。これは願いではなく、置ける場所を絞る制約として書かれる。

この章で作るもの

スケジューラの章では、Pod を散らすか詰めるかを score で選んだ。だが散らすといっても、何に対して散らすのかを決めていなかった。あの章が散らしていたのはノードで、ノードに均等に置けばノード1台の障害には耐えられる。

だが、同じラックの3台に均等に置いていたら、そのラックの電源が落ちたとき3台とも失う。同じ可用域(ゾーン)の中で散らしていても、ゾーンが丸ごと落ちれば同じことになる。1台の障害と、1区画の障害は別物だ。

区画のことを topology domain と呼ぶ。ノード、ラック、ゾーン、地域。どの単位で散らしたいかは、何の障害に耐えたいかで決まる。そして、その単位で数えなければ、散らしたつもりが散っていないことになる。

  ノードごとには均等(各1個)。だが区画では 2 対 1。

   zone-a                zone-b
   ┌ a-1 [web-1] ┐       ┌ b-1 [web-3] ┐
   └ a-2 [web-2] ┘       └ (なし)      ┘

   ノードを1台失う → 2 個残る
   zone-a を失う   → 1 個しか残らない

  区画をまたいで散らすと

   zone-a [web-1]  zone-b [web-2]  zone-c [web-3]
   どの区画を失っても 2 個残る

ノードごとに均等でも、区画では偏っていることがある。数える単位が、備える障害を決める

順に見ていく。

区画ごとに数える: ノードごとではない。数える単位が備える障害を決める
偏りの許容量を宣言する: 最も多い区画と最も少ない区画の差の上限
願いでなく制約: 置ける場所を絞る側に立つ。守れないなら置かない、も選べる

① 区画ごとに数える

まず、区画と偏りの定義を作る:


// Cluster はノードの集まりと制約を持つ。
type Cluster struct {
	cfg   Constraint
	nodes []*Node

	Placed  int
	Refused int
	Log     []string
}

// New は制約 cfg のクラスタを作る。
func New(cfg Constraint) *Cluster {
	if cfg.MaxSkew < 1 {
		cfg.MaxSkew = 1
	}
	return &Cluster{cfg: cfg}
}

// AddNode はノードを1台足す。
func (c *Cluster) AddNode(name, zone string) *Node {
	n := &Node{Name: name, Zone: zone}
	c.nodes = append(c.nodes, n)
	return n
}

// Nodes はノードを名前順に返す。
func (c *Cluster) Nodes() []*Node {
	out := append([]*Node(nil), c.nodes...)
	sort.Slice(out, func(i, j int) bool { return out[i].Name < out[j].Name })
	return out
}

// Zones は区画を名前順に返す。
func (c *Cluster) Zones() []string {
	seen := map[string]bool{}
	var out []string
	for _, n := range c.nodes {
		if !seen[n.Zone] {
			seen[n.Zone] = true
			out = append(out, n.Zone)
		}
	}
	sort.Strings(out)
	return out
}

// Count は区画ごとの Pod 数を返す。
func (c *Cluster) Count(zone string) int {
	n := 0
	for _, node := range c.nodes {
		if node.Zone == zone {
			n += len(node.pods)
		}
	}
	return n
}

// Skew は最も多い区画と最も少ない区画の差を返す。これが偏りの尺度になる。
//
// 数えるのは区画ごとであって、ノードごとではない。ノードに均等でも、
// 区画に偏っていれば skew は大きい。何を数えるかが、何の障害に備えるかを決める。
func (c *Cluster) Skew() int {
	zones := c.Zones()
	if len(zones) == 0 {
		return 0
	}
	min, max := -1, 0
	for _, z := range zones {
		n := c.Count(z)
		if n > max {
			max = n
		}
		if min < 0 || n < min {
			min = n
		}
	}
	return max - min
}

Skew が数えているのは区画ごとの合計で、ノードごとではない。この選択がすべてを決めている。ノードに1個ずつ均等に置いても、そのノードが2台とも同じ区画にあれば、区画としては偏っている。テストで、ノードごとには均等な配置でも、区画で数えれば偏りが出ることを固定した。

区画をどう決めるかは、何の障害に備えるかで決まる。ノードの故障に備えるならノードが区画になるし、ラックの電源やスイッチの障害に備えるならラックが区画になる。クラウドのゾーンが丸ごと落ちる事態に備えるならゾーンだ。実物ではノードに付けたラベルで区画を指定するので、同じクラスタに対して複数の見方を同時に持てる。

② 置いた後を見て絞る

配置の判断はこうなる:


// Result は1回の配置の結果。
type Result struct {
	Placed bool
	Node   string
	Zone   string
	Skew   int
	Reason string
}

// Place は Pod を1つ置く。制約を守れる区画の中で、いちばん少ない区画を選ぶ。
//
// 候補を絞ってから選ぶという順序が、スケジューラの章と同じ形になっている。
// 違うのは、絞る条件が「置いた後の偏り」であることだ。今の状態でなく、
// 置いた後どうなるかを見て判断する。
func (c *Cluster) Place(name string) Result {
	zones := c.Zones()
	if len(zones) == 0 {
		return Result{Reason: "ノードが1台も無い"}
	}

	// ① 置いた後も制約を守れる区画だけを候補にする。
	var feasible []string
	for _, z := range zones {
		if c.skewAfter(z) <= c.cfg.MaxSkew {
			feasible = append(feasible, z)
		}
	}

	if len(feasible) == 0 {
		if c.cfg.When == DoNotSchedule {
			c.Refused++
			c.logf(name + " はどの区画に置いても偏りが " + itoa(c.cfg.MaxSkew) + " を超える。置かない")
			return Result{Skew: c.Skew(), Reason: "制約を守れる区画が無く、守れないなら置かない設定"}
		}
		// 願いとして扱う設定なら、守れなくても置く。
		feasible = zones
		c.logf(name + " は制約を守れないが、置く設定なので置く")
	}

	// ② 候補のうち、いちばん少ない区画を選ぶ。同数なら名前順。
	best := feasible[0]
	for _, z := range feasible {
		if c.Count(z) < c.Count(best) {
			best = z
		}
	}

	// ③ 区画の中では、載っている数がいちばん少ないノードへ。
	var node *Node
	for _, n := range c.Nodes() {
		if n.Zone != best {
			continue
		}
		if node == nil || len(n.pods) < len(node.pods) {
			node = n
		}
	}
	node.pods = append(node.pods, name)
	c.Placed++
	return Result{Placed: true, Node: node.Name, Zone: best, Skew: c.Skew(),
		Reason: name + " を区画 " + best + " の " + node.Name + " へ"}
}

// skewAfter は zone に1つ置いた後の偏りを返す。
func (c *Cluster) skewAfter(zone string) int {
	min, max := -1, 0
	for _, z := range c.Zones() {
		n := c.Count(z)
		if z == zone {
			n++
		}
		if n > max {
			max = n
		}
		if min < 0 || n < min {
			min = n
		}
	}
	return max - min
}

// PlaceN は n 個を順に置く。
func (c *Cluster) PlaceN(prefix string, n int) []Result {
	out := make([]Result, 0, n)
	for i := 1; i <= n; i++ {
		out = append(out, c.Place(prefix+"-"+itoa(i)))
	}
	return out
}

Place は、まず skewAfter で「その区画に置いた後の偏り」を計算し、許容量を超える区画を候補から落とす。残った候補の中で、いちばん少ない区画を選ぶ。

候補を絞ってから選ぶという順序は、スケジューラの章と同じ形になっている。違うのは、絞る条件が「今の状態」でなく「置いた後の状態」であることだ。空き容量なら今を見れば足りるが、偏りは置いてみないと分からない。1つ置くごとに全体の分布が変わるので、その先を計算する必要がある。

そして、これが filter の側にあることに意味がある。score にすると「なるべく散らす」という願いになり、他の点数との兼ね合いで簡単に負ける。filter なら、守れない配置は候補から消える。可用性を配置の好みでなく制約として扱いたいなら、こちらでなければならない。

ただし、常に守れるとは限らない。区画が2つしかないのに3つに散らすことはできない。When がそのときの振る舞いを決める。DoNotSchedule は置かない。可用性を優先し、置けないことを受け入れる。ScheduleAnyway は守れなくても置く。動くことを優先し、偏りを受け入れる。テストで、同じ状況で片方は断り、片方は置くことを固定した。

③ 散らし方は残る数で測る

散らし方が良かったかどうかは、最後は障害が起きたときに何個残るかで測る。

LoseZone と LoseNode が、その2つを別々に返す。区画をまたいで6個を散らしていれば、1区画を失っても4個残る。同じ6個を1区画に寄せていれば、その区画が落ちて0個になる。テストで、この差を固定した。

同時に、ノード1台の障害と区画1つの障害で被害が違うことも確かめられる。6個を3区画6台に散らせば、1台失っても5個残るが、1区画失うと4個になる。備えたい障害の粒度を決めずに「散らす」とだけ言っても、何に対して安全になったかは分からない。テストで、区画の障害のほうが常に痛いことを固定した。

これは後のPodDisruptionBudgetの章とも噛み合う。あちらは「常に2つ以上」という下限を宣言するが、その2つが同じ区画にあれば、区画の障害で両方失う。下限を守るだけでは足りず、どこに置くかまで決めて初めて意味を持つ。

動かす

下のデモは、3区画6台に Pod を置きながら、ノード1台を失った場合と区画1つを失った場合の残り数を並べる。maxSkew を大きくすると制約が緩む。いちばん下の帯は、同じ数を1区画に寄せていた場合で、その区画が落ちると1つも残らない。

デモtopology spread偏り 0 ・ 1区画を失うと 4/6 残る

maxSkew(区画ごとの数の差の上限)126

置く Pod の数369

zone-a2 個

zone-a-1web-1

zone-a-2web-4

zone-b2 個

zone-b-1web-2

zone-b-2web-5

zone-c2 個

zone-c-1web-3

zone-c-2web-6

ノードを1台失うと5 / 6 残る

区画を1つ失うと4 / 6 残る

1区画に寄せていたら0 / 6 残る

区画をまたいで散っている。1区画を失っても 4 個が残り、過半数を保てる

ノードを1台失う場合と、区画を1つ失う場合で、残る数がまるで違う。ノードに均等に置くだけでは、区画の障害には備えられない。偏りを数える単位が、そのまま何の障害に備えるかを決めている。maxSkew を大きくすると制約が緩み、散らばりを保証しなくなる。いちばん下の帯は、同じ数を1区画に寄せていた場合で、その区画が落ちると 1つも残らない。

設計の観点

数える単位が備える障害を決める: 「散らす」だけでは何に安全になったか分からない。ノード、ラック、ゾーンのどれで数えるかを先に決める
filter に置くから守られる: score にすると他の点数との兼ね合いで負ける。制約として書けば、守れない配置は候補から消える
置いた後を見る: 空き容量は今を見れば足りるが、偏りは置いた後の分布を計算しないと分からない
守れないときを決めておく: 置かないか、置くか。可用性と稼働のどちらを優先するかの選択で、既定に任せると後で驚く
下限だけでは足りない: PodDisruptionBudgetで「常に2つ以上」と宣言しても、その2つが同じ区画にあれば意味が薄い。数と配置は両方要る
区画をまたぐ代償: ゾーンをまたぐと通信の遅延と費用が増える。可用性は無料ではない

対照と実例

	ノードで散らす	区画(ゾーン)で散らす
耐えられる障害	ノード1台	区画まるごと
同じ区画に寄ると	気づかない	制約が止める
通信の遅延	変わらない	増える
費用	変わらない	区画をまたぐ通信ぶん
使いどころ	単一の環境	複数の可用域がある環境

裏どり:

Pod Topology Spread Constraints: topologyKey で区画を指定し、maxSkew で偏りの上限を宣言する
whenUnsatisfiable: DoNotSchedule(制約)と ScheduleAnyway(願い)の2つ。前者は filter、後者は score として働く
既定の制約: 実物のスケジューラには、ノードとゾーンに対する既定の制約が入っている。どちらも maxSkew が 3 で ScheduleAnyway、つまり願いのほうになる。Pod が自分で制約を書くと、この既定は使われない
podAntiAffinity との違い: あちらは「同じ区画に置くな」という強い形。topology spread は偏りの度合いを数で表せる

簡略化したこと

区画は1段のみ: 実物はノード・ラック・ゾーン・地域を同時に指定できる
セレクタなし: 実物はラベルで対象の Pod を絞る。ここでは全 Pod が対象
minDomains なし: 何区画以上に散らすかの下限は扱わない
他の条件との併用なし: 空き容量や汚れによる絞り込みはスケジューラの担当として分けている
再配置なし: すでに置いた Pod を偏りのために動かすことはしない

参考資料

Pod Topology Spread Constraints — maxSkew と topologyKey の意味
Assigning Pods to Nodes — affinity との使い分け
実装: orchestration/topology

topology spread ​

この章で作るもの ​

① 区画ごとに数える ​

② 置いた後を見て絞る ​

③ 散らし方は残る数で測る ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​