PriorityClass と preemption
実装:
orchestration/preemption// 実行:go test ./orchestration/preemption/
この編のスケジューラは、置ける場所が無ければ Pod を Pending のまま残した。だが待たせるわけにいかない Pod がある。優先度は行列の順序を決めるだけでなく、動いている Pod から場所を奪う権利にもなる。奪うと決めたら次は誰を何個かを決める。低いものから外していくと、外さなくてよいものまで外してしまう。順序を逆にすると最小になる。
この章で作るもの
スケジューラの章では、条件を満たすノードが無ければ Pod は Pending のまま残るとした。Cluster Autoscaler の章では、そういう Pod が居るならノードを増やす、という手も見た。だがノードが増えるまでには時間がかかるし、増やせる上限もある。
ここで、待たせてよい Pod と待たせてはいけない Pod があることに気づく。決済を捌く本番のアプリと、夜間に回すバッチ処理が同じクラスタに載っているとき、空きが無いからといって本番を待たせるわけにはいかない。バッチのほうを退かせばよい。
この「退かせる」を担うのが優先度になる。優先度には2つの意味がある。1つは待ち行列の順序で、これは素直だ。高いほうが先に処理される。もう1つが場所を奪う権利で、こちらは素直ではない。すでに動いていて、何も問題を起こしていない Pod を止めるということだからだ。
奪うと決めたら、次は誰を何個かを決めることになる。ここが素朴に作ると間違えるところで、優先度の低いものから順に止めていくと、止めなくてよいものまで止めてしまう。
そして追い出された Pod は消えない。行列に戻り、別の場所を探す。探した先で、さらに下を追い出すことがある。
ノード node-a (容量 1000)
┌─────────────────────────────────────────┬────────┐
│ small-a 100 │ small-b 100 │ big 600 │ 空き200│
│ 優先度 10 │ 優先度 10 │ 優先度 20 │ │
└─────────────────────────────────────────┴────────┘
ここに api(要求 700、優先度 100)を置きたい
低いものから外していく 全部外してから戻す
(優先度の低い順) (優先度の高い順に戻す)
small-a を外す → 空き 300 ✕ 全部外す → 1000 ✓ 候補になる
small-b を外す → 空き 400 ✕ big を戻す → 400 ✕ これが犠牲
big を外す → 空き1000 ✓ small-a を戻す → 900 ✓ 助かる
small-b を戻す → 800 ✓ 助かる
止まる Pod: 3 つ 止まる Pod: 1 つ
(small-a と small-b は
止めなくてよかった)順に見ていく。
- 優先度は順序であり、権利でもある: 待つ順番だけでなく、動いているものを止める根拠になる
- 犠牲は引き算でなく足し算で決める: 全部外してから戻せるだけ戻す。逆向きだと最小にならない
- 追い出された Pod は消えない: 行列に戻り、行った先でさらに下を追い出す
① 行列の順序としての優先度
まず、素直なほうから:
// Run は待ち行列が空になるまで回す。
//
// 1 周ごとに、優先度のいちばん高い Pod を取り出して置こうとする。置けなければ
// 奪いにいく。奪えば犠牲が行列に戻るので、行列は減るとは限らない。
func (c *Cluster) Run() {
for i := 0; i < maxRounds && len(c.queue) > 0; i++ {
c.sortQueue()
q := c.queue[0]
c.queue = c.queue[1:]
if c.place(q.pod) {
continue
}
if c.preempt(q.pod) {
continue
}
// 奪う相手も居ない。ここで諦める。実物では unschedulable として
// 別の行列に移り、状況が変わるまで再試行されない。
c.stuck = append(c.stuck, q.pod)
c.logf(q.pod.Name + " はどこにも置けない(奪える相手も居ない)")
}
}
// sortQueue は優先度の高い順、同じなら入った順に並べる。
// これが優先度の1つめの意味、待ち行列の順序になる。
func (c *Cluster) sortQueue() {
sort.SliceStable(c.queue, func(i, j int) bool {
if c.queue[i].pod.Priority != c.queue[j].pod.Priority {
return c.queue[i].pod.Priority > c.queue[j].pod.Priority
}
return c.queue[i].seq < c.queue[j].seq
})
}
// place は奪わずに置けるノードを探して置く。
//
// 候補を絞るところは[スケジューラ](scheduler)の Filter をそのまま使う。
// 実物でも preemption は通常のスケジューリングが失敗した後で走る仕組みなので、
// 同じ判定を通ってから来ることになる。
func (c *Cluster) place(p Pod) bool {
var probes []*scheduler.Node
for _, n := range c.nodes {
// 空きぶんの容量を持つ仮のノードとして渡す。
probes = append(probes, scheduler.NewNode(n.name, n.free(nil)))
}
feasible, _ := scheduler.Filter(scheduler.Pod{Name: p.Name, Req: p.Req}, probes)
if len(feasible) == 0 {
return false
}
// 候補が複数あれば空きの大きいほうへ。同点は名前順で決定的にする。
best := c.byName(feasible[0].Name)
for _, f := range feasible[1:] {
n := c.byName(f.Name)
if n.free(nil).CPU > best.free(nil).CPU || (n.free(nil).CPU == best.free(nil).CPU && n.name < best.name) {
best = n
}
}
best.pods = append(best.pods, p)
c.logf(p.Name + "(優先度 " + itoa(p.Priority) + ") を " + best.name + " に置いた")
return true
}
func (c *Cluster) byName(name string) *node {
for _, n := range c.nodes {
if n.name == name {
return n
}
}
return nil
}sortQueue が優先度の高い順に並べ、同じなら入った順にする。Run は1周ごとに先頭を取り出して置こうとする。
置けたらそれで終わりで、ここまでなら奪う話は出てこない。テストで、低い Pod が先に投入されていても高い Pod が先に置かれること、そのとき追い出しが1件も起きないことを固定した。空きがあるなら、優先度は順番を決めるだけの数になる。
奪う話が出てくるのは、置けなかったときだけになる。
② 全部外してから、戻す
置けなかったときに、どのノードから誰を追い出すかを決める:
// selectVictims は、ノード n に p を置くために追い出す Pod を選ぶ。
//
// 素朴には「優先度の低いものから、入るまで外す」と考えたくなる。だがそれだと
// 外さなくてよいものまで外してしまう。小さいものを2つ外しても足りず、
// 結局大きいものも外す、という順序になったとき、先に外した2つは無駄になる。
//
// 実物は逆に考える。まず p より低いものを全部外し、それでも入らないなら
// このノードは候補にしない。入るなら、優先度の高いものから戻していく。
// 戻しても p が入るなら、その Pod は外す必要が無かったということになる。
func (c *Cluster) selectVictims(n *node, p Pod) ([]Pod, bool) {
drop := map[string]bool{}
var lower []Pod
for _, q := range n.pods {
if q.Priority < p.Priority {
lower = append(lower, q)
drop[q.Name] = true
}
}
if !fits(p.Req, n.free(drop)) {
// 低いものを全部どけても入らない。奪っても意味がない。
return nil, false
}
sort.SliceStable(lower, func(i, j int) bool {
if lower[i].Priority != lower[j].Priority {
return lower[i].Priority > lower[j].Priority
}
return lower[i].Name < lower[j].Name
})
var victims []Pod
for _, q := range lower {
delete(drop, q.Name)
if fits(p.Req, n.free(drop)) {
continue // 戻しても入る。この Pod は助かる
}
drop[q.Name] = true
victims = append(victims, q)
}
return victims, true
}
// violations は victims を追い出したときに破ってしまう保護の数を返す。
//
// [PodDisruptionBudget](pdb) の章では、自発的な退去は保護に阻まれるとした。
// 奪うほうは阻まれない。数えはするが、他に道が無ければ破って進む。
func (c *Cluster) violations(victims []Pod) int {
killed := map[string]int{}
for _, v := range victims {
killed[v.App]++
}
apps := make([]string, 0, len(killed))
for a := range killed {
apps = append(apps, a)
}
sort.Strings(apps)
total := 0
for _, a := range apps {
min, ok := c.budgets[a]
if !ok {
continue
}
if left := c.countApp(a) - killed[a]; left < min {
total += min - left
}
}
return total
}
func (c *Cluster) countApp(app string) int {
n := 0
for _, nd := range c.nodes {
for _, p := range nd.pods {
if p.App == app {
n++
}
}
}
return n
}素朴には「優先度の低いものから、入るまで外す」と考えたくなる。だがこれだと、外さなくてよいものまで外してしまう。小さいものを2つ外しても足りず、結局大きいものも外すことになったとき、先に外した2つは無駄死にになる。
実物は逆向きに考える。まず自分より低いものを全部外し、それでも入らないならこのノードは候補にしない。入るなら、優先度の高いものから戻していく。戻しても入るなら、その Pod は外す必要が無かったということになる。
戻す順を優先度の高いほうからにしているのは、助けられる数が限られているなら重要なほうから助けたいからだ。上の図では、いちばん高い big に最初の機会を与えているが、大きすぎて戻せなかった。順序が公平さを決めていて、結果の最小性とは別の話になっている。
テストで、100 と 100 と 600 が載っているノードに 700 を置く場面で、犠牲が 600 の1つだけになることを固定した。素朴なやり方なら3つとも止まる場面になっている。
「全部外しても入らないなら候補にしない」の条件も入れてある。自分より高い Pod が場所を占めていて、低いものを全部どけても足りないなら、奪っても置けない。奪い損になるだけなので、そのノードは最初から候補から外す。
複数のノードが候補になったときの選び方が、次になる:
type candidate struct {
node *node
victims []Pod
violations int
topVictim int // 犠牲の中でいちばん高い優先度
}
// preempt は奪ってでも置く。候補ノードごとに犠牲を計算し、いちばん小さい
// 犠牲で済むノードを選ぶ。
//
// 選び方の順序が、そのまま何を大事にしているかの宣言になる。
// ① 保護を破る数が少ない ② 犠牲の優先度がなるべく低い ③ 犠牲の数が少ない。
// 保護を最優先に見るが、破らずに済む選択肢が無ければ破る。
func (c *Cluster) preempt(p Pod) bool {
var best *candidate
for _, n := range c.nodes {
victims, ok := c.selectVictims(n, p)
if !ok || len(victims) == 0 {
continue
}
cand := candidate{node: n, victims: victims, violations: c.violations(victims)}
for _, v := range victims {
if v.Priority > cand.topVictim {
cand.topVictim = v.Priority
}
}
if best == nil || better(cand, *best) {
cp := cand
best = &cp
}
}
if best == nil {
return false
}
for _, v := range best.victims {
violates := c.violations([]Pod{v}) > 0
best.node.remove(v.Name)
c.Evictions = append(c.Evictions, Eviction{
Victim: v.Name, By: p.Name, Node: best.node.name, Violates: violates,
})
msg := p.Name + "(優先度 " + itoa(p.Priority) + ") が " + best.node.name +
" から " + v.Name + "(優先度 " + itoa(v.Priority) + ") を追い出した"
if violates {
msg += "。保護を破っている"
}
c.logf(msg)
// 追い出された Pod は消えない。行列に戻って別の場所を探す。
c.seq++
c.queue = append(c.queue, queued{pod: v, seq: c.seq})
}
best.node.pods = append(best.node.pods, p)
c.logf(p.Name + " を " + best.node.name + " に置いた(奪って作った場所)")
return true
}
// better は候補 a が候補 b より望ましいかを返す。
func better(a, b candidate) bool {
if a.violations != b.violations {
return a.violations < b.violations
}
if a.topVictim != b.topVictim {
return a.topVictim < b.topVictim
}
if len(a.victims) != len(b.victims) {
return len(a.victims) < len(b.victims)
}
return a.node.name < b.node.name
}順序がそのまま「何を大事にしているか」の宣言になっている。保護を破る数がいちばん先、次に犠牲の優先度、その次に犠牲の数。
ここで PodDisruptionBudget が出てくるが、扱いが前の章と違う。前の章では、保護は自発的な退去を阻んだ。ここでは阻まない。数えて、なるべく避けるが、避けられる選択肢が無ければ破って進む。奪う側の事情のほうが強いからだ。この非対称は覚えておく価値がある。保護は「絶対に守られる約束」ではなく、「自発的な操作に対してだけの約束」になっている。
③ 追い出された Pod は行列に戻る
preempt の最後で、犠牲になった Pod を待ち行列に入れ直しているのがそれになる。追い出しは削除ではない。行き場を失った Pod が1つ増えるだけで、その Pod もまた置き場所を探す。
そして探した先で、自分より低い Pod を追い出すことがある。テストで、保護が絡んだときにこれが実際に起きることを固定した。
その場面はこうなる。node-a に batch(優先度 50)、node-b に log(優先度 10)が居て、log には保護がかかっている。ここに api(優先度 100)が来る。素直に考えれば、いちばん低い log が犠牲になりそうだ。だが log を止めると保護を破ってしまうので、破らずに済む node-a のほうが選ばれ、優先度の高い batch が犠牲になる。
追い出された batch は行列に戻る。行き場は node-b しかなく、そこには log が居る。batch のほうが高いので奪えるが、今度は他に選択肢が無い。保護を破って log を追い出す。
結果として、保護は log を守れなかった。守れなかったが、無駄でもなかった。保護が無ければ最初の一撃で log が消えていたところを、一度は逸らしている。保護がしているのはそういう仕事になる。
動かす
下のデモは、いま説明した場面を動かす。「保護をかける」を切り替えると、同じ配置・同じ要求のまま犠牲だけが入れ替わる。保護なしなら log が1回で消え、保護ありなら batch が犠牲になったうえで玉突きが起きて、結局 log も消える。「犠牲の最小化」の場面に切り替えると、全部外して戻す手順が1段ずつ見える。
node-a に batch(優先度 50、要求 800)、node-b に log(優先度 10、要求 800)。 そこへ api(優先度 100、要求 900)が来る
帯の幅が要求の大きさ、色が優先度の高さ。左が api の来る前、右が落ち着いた後で、左側の赤い枠が これから追い出されるものを表す。「保護と玉突き」では、保護をかけると犠牲が log から batch へ入れ替わり、 押し出された batch が今度は log を追い出す。保護は log を守りきれないが、一度は逸らしている。 「犠牲の最小化」では、全部外してから戻す過程が1段ずつ見える。戻しても api が入るものは、 止める必要が無かったものになる。
設計の観点
- 優先度は相対的: 絶対値に意味は無く、他と比べたときだけ意味を持つ。等しい相手からは奪えない
- 奪えるかを先に確かめる: 全部どけても入らないノードは候補にしない。追い出してから置けないと分かるのが最悪になる
- 最小化は戻す向きで: 外す向きに貪欲だと、途中で外したものが無駄になる。全部外して戻すと、必要なものだけが残る
- 保護の強さはコンテキストで変わる: PodDisruptionBudget は自発的な退去を阻むが、奪う側は阻めない。同じ設定が状況によって違う強さになる
- 玉突きを勘定に入れる: 1つ追い出せば1つ行き場を失う。クラスタ全体では、押し出された Pod がどこへ行くかまでが1回の判断になる
- Cluster Autoscaler との役割分担: 奪うのは今すぐ効くが誰かが止まる。ノードを増やすのは誰も止まらないが遅い。両方あるのは、速さと痛みの取引が違うため
対照と実例
| 優先度なし | 優先度あり(奪わない) | 優先度あり(奪う) | |
|---|---|---|---|
| 置けないとき | Pending のまま待つ | Pending のまま待つ | 低いものを止めて置く |
| 効くまでの時間 | 空きが出るまで | 空きが出るまで | すぐ |
| 動いている Pod | 影響なし | 影響なし | 止まることがある |
| 行列の順序 | 入った順 | 優先度順 | 優先度順 |
| 保護の扱い | 関係なし | 関係なし | 避けようとするが破ることもある |
裏どり:
- PriorityClass: 優先度は名前付きのオブジェクトとして定義し、Pod から参照する。
globalDefaultを持つものが1つだけ既定になる - preemptionPolicy: 既定は
PreemptLowerPriorityで、低いほうから奪う。Neverにすると、行列では優先されるが奪わない。上の表の真ん中の列がこれになる - system-cluster-critical / system-node-critical: 組み込みの高優先度。DaemonSet の一部はこれを使って場所を確保する
- nominatedNodeName: 奪ったあと、その場所が確保されたことを表す印。実物では犠牲の終了処理を待つ間、ここに名前が入る
- PDB は best-effort: 候補ノードの順位付けでは考慮されるが、他に選択肢が無ければ破って追い出す
簡略化したこと
- 終了処理なし: 実物は犠牲に graceful shutdown の猶予を与える。その間、場所はまだ空かない
- 場所の確保なし: 実物は
nominatedNodeNameで場所を押さえる。ここでは追い出しと配置が同じ瞬間に起きる - 横取りなし: 実物では、空けた場所が他の Pod に取られることがある。ここでは起きない
- 配置の点数なし: 奪わずに置けるときの選び方は空きの大きさだけで決める。スケジューラの score は使わない
- 周回に上限: 玉突きが循環しないよう回数を区切ってある。実物は指数的な待ち時間で再試行する
参考資料
- Pod Priority and Preemption — PriorityClass、preemptionPolicy、PDB の扱い
- Scheduler Configuration — preemption が PostFilter として走る位置
- 実装: orchestration/preemption