CPU スロットリング

実装: foundations/throttle/ / 実行: go test ./foundations/throttle/

メモリの上限は超えたら断れるが、CPU は断れない。時間は流れ続けるので、できるのは次の期間まで走らせないことだけになる。cpu.max は固定窓なので使い残しが貯まらず、平均で足りていても止まる。同時に走らせる本数を8倍にすると、枠を使い切るのが40 tick目から5 tick目に早まり、期間の95%を待って過ごす。

この章で作るもの

コンテナの章で cgroup を作ったとき、上限は「超えたら断る」だった。メモリはそれでいい。CPU は断れない。時間は流れ続けるので、上限を超えた相手にできることは「次の期間まで走らせない」しかない。これがスロットリングになる。

cgroup v2 では cpu.max に2つの数を書く。

cpu.max = "50000 100000"    100ms ごとに 50ms ぶんだけ CPU を使ってよい

期間の頭で使える量が戻り、使い残しは(既定では)消える。つまり レート制限でいう固定窓であって、トークンバケツではない。

順に見ていく。

枠は貯まらない: 平均で見れば余っていても、その期間で使い切れば止まる
並列度が枠を早く食う: 同時に8本走らせると、枠は8分の1の時間で消える
繰り越せると吸える: 使い残しを持ち込めるようにすると、暇のあとの集中を吸収できる

① 枠は貯まらない


// Limit は cpu.max。1期間 Period tick のうち、Quota tick ぶん CPU を使ってよい。
type Limit struct {
	Quota  int
	Period int
	// Burst は使い残しを次の期間へ繰り越せる上限(cgroup v2 の cpu.max.burst)。
	// 0 なら繰り越さない。これが既定で、期間の頭で使い残しは消える。
	Burst int
}

// Task は仕事。Arrive の時刻に現れて、Need tick ぶんの CPU を使うと終わる。
type Task struct {
	Name   string
	Arrive int
	Need   int
}

// Result は1つの仕事の結果。
type Result struct {
	Name   string
	Arrive int
	Done   int
	// Latency は現れてから終わるまでの時間。Need より長ければ、その差は待たされた時間になる。
	Latency int
	// Throttled は CPU を使いたかったのに、枠を使い切っていて止められた tick の数。
	Throttled int
}

// Period は1期間ぶんの内訳。
type Period struct {
	Start int
	// Used はこの期間に使った CPU tick。
	Used int
	// Stalled は「走りたい仕事が居たのに枠が無かった」壁時計の tick 数。
	Stalled int
	// Carried はこの期間の頭に繰り越されてきた量。
	Carried int
	// Exhausted は枠を使い切った時刻。使い切らなかったら -1。
	// 期間の頭からの距離が短いほど、残りを長く止まって過ごすことになる。
	Exhausted int
}

Run は tick を1つずつ進める。走れる仕事へ最大 ncpu 本まで CPU を配るが、その期間に残っている枠を超えては配らない。超えたぶんが止められた時間になる。


// Run は決定的に模擬する。ncpu は同時に走らせられる本数。
//
// 1 tick ごとに、走れる仕事へ最大 ncpu 本まで CPU を配る。ただし
// その期間に残っている枠を超えては配らない。超えたぶんが止められた時間になる。
func Run(limit Limit, ncpu int, tasks []Task) ([]Result, []Period) {
	res := make([]Result, len(tasks))
	left := make([]int, len(tasks))
	for i, t := range tasks {
		res[i] = Result{Name: t.Name, Arrive: t.Arrive, Done: -1}
		left[i] = t.Need
	}

	var periods []Period
	remaining := 0 // この期間に残っている枠
	done := 0

	for t := 0; done < len(tasks); t++ {
		if t%limit.Period == 0 {
			// 期間の頭。使える量が戻る。
			// 直前の期間の使い残しは Burst までしか持ち込めない。既定の 0 なら消える。
			carry := 0
			if len(periods) > 0 {
				carry = min(remaining, limit.Burst)
			}
			remaining = limit.Quota + carry
			periods = append(periods, Period{Start: t, Carried: carry, Exhausted: -1})
		}
		p := &periods[len(periods)-1]

		ran := 0
		stalledHere := false
		for i := range tasks {
			if left[i] == 0 || tasks[i].Arrive > t {
				continue
			}
			if ran >= ncpu {
				break // CPU の本数が足りない。これは制限ではなく並列度の話
			}
			if remaining == 0 {
				// 枠を使い切っている。走りたいのに走れない。
				res[i].Throttled++
				stalledHere = true
				continue
			}
			remaining--
			p.Used++
			if remaining == 0 && p.Exhausted < 0 {
				p.Exhausted = t + 1
			}
			ran++
			left[i]--
			if left[i] == 0 {
				res[i].Done = t + 1
				res[i].Latency = t + 1 - tasks[i].Arrive
				done++
			}
		}
		if stalledHere {
			p.Stalled++
		}
	}
	return res, periods
}

cpu.max = 40 / 100 の設定で、60 tick ぶんの CPU が要る仕事を1つ流した。 2期間ぶんで見れば枠は 80 あるので、平均では足りている。


CPU が要る量	60 tick
終わった時刻	120 tick
止められた時間	60 tick

期間	使った	止まった
0〜99	40	60
100〜199	20	0

60 tick の仕事に 120 tick かかっている。半分は待っている時間だ。平均では足りているのに止まるのは、枠が期間をまたいで貯まらないからだ。テストで、この前提(平均では足りている)が崩れていないことも一緒に固定した。

② 並列度が枠を早く食う

ここが実物でいちばん効く。合計 80 tick ぶんの仕事を 8本に分けて同時に出す。仕事の総量も枠も変えず、同時に走らせる本数だけ変えて測った。

同時に走らせる本数	最後の1本が終わる	枠を使い切った時刻	期間のうち止まって過ごす割合
1	140 tick	40 tick 目	60%
2	120 tick	20 tick 目	80%
8	105 tick	5 tick 目	95%

  cpu.max = 40 / 100     ■ 走っている     · 止められている

  1 本   ■■■■■■■■■■■■■■■■■■■■········································
         └── 40 tick ──┘ 40 tick 目に使い切る

  2 本   ■■■■■■■■■■············································
         └ 20 ┘

  8 本   ■■■···················································
         └5┘   期間の 95% は走りたくても走れない

同じ枠・同じ仕事量で、同時に走らせる本数だけを変えたときの1期間。濃い部分が走っている時間で、本数を増やすほど期間の頭に固まる

同時に8本走らせると、1 tick あたり8 tick ぶんの CPU を消費するので、 40 tick ぶんの枠が壁時計の5 tick で消える。残り95 tick は、走りたい仕事が8本居るのに1本も動かせない。

ただし、ここは正直に見ておきたい。最後の1本が終わる時刻は 8 本のほうが速い (105 対 140)。並列度を上げること自体が損なのではない。損なのは、 走っている時間が期間の頭に固まって、残りが丸ごと空白になることだ。 1本ずつなら最初の仕事は 10 tick で終わっていたのに、8本同時では全部が 105 tick かかる。 速い仕事が消えて、全部が遅い仕事になる。

これが Kubernetes で limits.cpu を絞ったコンテナの応答時間が跳ねる仕組みそのものになる。 CPU の使用率を平均で見ていると、平均は枠の 40% で余裕に見える。

③ 繰り越せると吸える

固定窓の弱点はそのままレート制限の章の話と同じで、直前が暇でも枠が貯まらないことだ。3期間まるまる暇にしたあと、 100 tick ぶんの仕事が来る筋書きで測った。

	所要	止められた時間
使い残しは消える(既定)	220 tick	120 tick
使い残しを繰り越す(上限 120)	100 tick	0 tick

3期間ぶん暇にしていたのだから、使わなかった枠は 120 ある。それを持ち込めるなら、 100 tick の仕事は待たずに終わる。cgroup v2 が後から cpu.max.burst を足したのはこれのためだ。ただし持ち込める量には上限がある。テストで、上限を 20 にするとまた止まることを固定した。貯め放題にすると、長く眠っていた相手が一気に全部を持っていける。

動かす

同時に走らせる本数を変えると、走っている部分が期間の頭へ寄っていく。使い残しを繰り越す側に切り替えると、最初の期間で吸えるようになる。

デモCPU スロットリング(cpu.max)105 tick で完了

同時に走らせる本数1248使い残しは消える使い残しを繰り越す

cpu.max = 40 / 100 ・合計 80 tick ぶんの仕事を 8 本に分けて同時に出す

0〜走った 5 / 止められた 95

100〜走った 5 / 止められた 0

最初の期間は 5 tick 目で枠を使い切り、残りの 95 tick は走りたくても走れない。同時に走らせる本数を増やすほど、使い切るのが早くなる

濃い印が走った tick、薄い印が「走りたいのに枠が無い」tick。メモリの上限なら断って終わりだが、 CPU は断れないので、次の期間が来るまで止めるしかない。使い残しを繰り越せるようにすると、暇だったあとの一時的な集中を吸える。

設計の観点

断れる資源と断れない資源を分ける: メモリは拒否できる。CPU は拒否できないので、遅らせるしかない
期間の切り方が挙動を決める: 同じ平均でも、固定窓か貯められるかで待たされ方が変わる
平均で見ない: 使用率の平均は枠の 40% でも、期間の 95% は止まっていることがある
並列度と枠を一緒に決める: 枠だけ絞って本数を増やすと、走る時間が期間の頭に固まる
貯められる量に上限を置く: 貯め放題にすると、眠っていた相手が一気に全部を持っていく
止められた時間を数える: 「絞りすぎ」は主張なので、止められた tick を数える口を用意する

対照と実例

	上限を超えたら	期間の扱い	貯まるか
cpu.max(既定)	次の期間まで止める	固定窓	貯まらない
cpu.max.burst	同じ	固定窓 + 繰り越し	上限まで貯まる
cpu.weight(旧 shares)	止めない。取り合いのときの比率	(期間なし)	—
cgroup のメモリ上限	断る。断れなければ殺す	(期間なし)	—
レート制限の固定窓	断る	固定窓	貯まらない
レート制限のトークンバケツ	断る	連続	上限まで貯まる

裏どり:

cpu.max の既定は 100ms: カーネル文書が "max 100000" を既定として書いている。この 100ms が、待たされる時間の粒になる
burst は後から入った: cpu.max.burst は Linux 5.14 で入った。固定窓のままでは「平均では余っているのに止まる」を消せない、と分かってからの追加になる
Kubernetes の limits.cpu はこれ: limits.cpu: 1 は cpu.max = "100000 100000" になる。requests は cpu.weight、limits は cpu.max と、別の仕組みに割り当てられている
limits を外す運用: スロットリングによる応答時間の跳ねを避けるため、CPU の limits を付けない選択が広く議論されている。上限を外すと隣に影響が出るので、どちらを取るかの判断になる
並列度の問題は実測されている: 多コアの機械で GOMAXPROCS やスレッドプールの本数を絞らないまま limits.cpu を小さくすると、枠を一瞬で使い切る。Go の GOMAXPROCS を limits に合わせる運用があるのはこのため

簡略化したこと

tick が単位: 実物はナノ秒。ここでは1 tick を CPU 1 単位として数える
仕事は分割できる前提: 途中で止めてまた動かせるものとして扱っている
weight(取り合いの比率)なし: 枠に余裕があるときの分け合い方は扱わない
階層なし: コンテナの cgroup は親子で効いたが、ここは1段だけ
I/O 待ちなし: CPU を使うことしかしない仕事しか居ない
公平さを見ない: 誰から先に走らせるかは、配列の順そのままになる

参考資料

Control Group v2(カーネル文書) — cpu.max と cpu.max.burst の定義
CFS Bandwidth Control — quota と period の仕組み。burst の説明もここ
実装: foundations/throttle

CPU スロットリング ​

この章で作るもの ​

① 枠は貯まらない ​

② 並列度が枠を早く食う ​

③ 繰り越せると吸える ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​