Skip to content

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 を使ってよい

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

順に見ていく。

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

① 枠は貯まらない ​

go

// 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 を配るが、 その期間に残っている枠を超えては配らない。超えたぶんが止められた時間になる。

go

// 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〜994060
100〜199200

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

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

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

同時に走らせる本数最後の1本が終わる枠を使い切った時刻期間のうち止まって過ごす割合
1140 tick40 tick 目60%
2120 tick20 tick 目80%
8105 tick5 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 tick120 tick
使い残しを繰り越す(上限 120)100 tick0 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 を使うことしかしない仕事しか居ない
  • 公平さを見ない: 誰から先に走らせるかは、配列の順そのままになる

参考資料 ​