Instantly share code, notes, and snippets.

@monochromegane /wsa_3.md Secret
Last active Nov 16, 2018

Embed
What would you like to do?

Kaburaya: CPU負荷に応じて継続的に上限値を最適化する動的セマフォ

はじめに

マルチコア時代において,単一のマシンで処理性能を最大化するため処理の並行化が行われる. ノンブロッキングな処理方式の採用によってCPUを効率的に使用する場合には最適な並行数はCPUコア数と等しくなる. しかしノンブロッキングを実現するランタイム実装の限界から,もしくはノンブロッキングを採用していない場合のような,全体的もしくは部分的にブロッキングが発生する状況においては,最適な並行数の決定は依然として開発者の経験と地道なチューニングに依存している. このような最適な並行数を求める例としてnginx, unicornのworker_processes,Sidekiqのconcurrency,Goroutineの起動数などが挙げられる. これらは、実行される処理の負荷や特性がアプリケーションごとに異なるため実行される処理の特性とランタイムやスケジューリングの特性を考慮したチューニングが必要になる. このような複雑な系に対する普遍的なチューニング手法の発見は困難であることから,これらをブラックボックスとして扱い汎用的に調整できる手法が求められる.

三宅らは仮想サーバの予測的オートスケーリングにおいて,アプリケーションの処理内容ではなく運用経験から得られたサーバ単位のスループットを指標として,これを予測するモデルによってサーバ台数調整機能を実現した. また,「全自動パラメータチューニングさん」ではメトリクスを一点に絞りスループットが最大化する値を探索的に求める. これらの手法は指標を限定しても充分な成果が得られることを示した.一方でその求め方は予測的または探索的であり,Webサーバープロセスのように比較的長期稼働する場合に適用可能である. しかしながらCLIのような短期稼働かつ性能が求められるようなプロセスにおいては予測や探索は利用できない. これらの利用用途に対応するため,指標の限定に加え,反応的かつ誤差が少なく指標へ追従する手法が必要である.

本研究では,処理やランタイムの特性に依存せずに,マシンの負荷に応じて反応的かつ継続的に,並行数を最適化する手法を検討する. まず,最適な並行数を求めるために,最適化の手法としてフィードバック制御を用いる.指標にはノンブロッキングな処理方式がCPUを効率的に利用することに着目し,CPU使用率を採用する. 次に,並行数の制御にはセマフォを採用することで提案手法に汎用性を持たせる. 本報告では,ノンブロッキングな処理方式をランタイムとして採用するGo言語において,CPU負荷に応じて継続的に上限値を最適化する動的セマフォを実現するライブラリを開発し,これを評価する.

実装

フィードバック制御を用いてGoroutineの起動数を動的に調整する手法を実装するためには,ある時点で最適なGoroutineの起動数をフィードバック制御によって決定する仕組みと,その起動数を制約としてGoroutineの起動数を制御する仕組みが必要となる. このような並行処理の起動数を制御する仕組みには一般的にセマフォが利用される.Go言語ではセマフォとしてバッファ付きチャンネルを用いるのが定石となっている. そこで本研究では,最適なセマフォの値をフィードバック制御によって動的に変更可能な仕組みを構築した.なおこの実装はOSSのkaburayaとして公開している.

制御器

本研究では,ある時点で最適なGoroutineの起動数をフィードバック制御によって決定する仕組みを制御器と呼ぶ. 今回,制御器の設計についてはGoroutine起動数が制御可能な入力となる.これによって対象のスループットを最大化するのが目的である.しかしながら実行される処理の負荷や特性が異なっても共通に採用できる固定値のスループット値は事前に求めることはできないため別の指標を用いる必要がある. 本研究ではいくつかの制御器の評価を通して効果的な制御器を求める. 以降,Go言語ランタイムがI/Oブロッキングな処理についてもGoroutineの切り替えにより、その負荷をCPU側に移動させることから,CPU負荷が安定になることが一つの上限とみなせると仮定していくつかの制御器を設計する.

  1. 初期値からワーカー数を変えないFixController (比較用)
  2. CPU使用率100%を目標値とし,不足した場合は workerを1ずつ増加させる SimpleController
  3. CPU使用率100%を目標とし,目標との差分のK倍を加える PController(比例制御)
  4. 3.のCPU使用率の目標値を90%としたもの
  5. 直近3観測点の平均を目標値として3観測ごとにPControllerの目標値を変化させるDynamicController
  6. 一定期間のCPU使用率の標準偏差をとってそれが一定の値以下だったら安定したとみなして,workerを減らしていくStabilityController
  7. CPU使用率ではなくてCPU使用率の変化率を元に制御するRateController
  8. 5.のDynamicControllerを元に定期ではなく大きな変動ごとに目標値を見直す方式
  9. 8.のDynamicControllerを元に定常時の不要なworkerを削減する方式
  10. 9.のDynamicControllerを元に変動の精度と速度を向上させるために積分微分制御を導入する方式

セマフォ

本研究では,制御器によって決定された起動数を制約としてGoroutineの起動数を制御する仕組みをセマフォと呼ぶ. 今回のセマフォの要件としてはセマフォの上限値が動的に変更可能であること,そして通常のセマフォと同様にP操作において値が負になる場合に実行がブロックされる.またこれらの値の変更がアトミックに行われる必要がある.

これらはGo言語では二つのチャンネルを組み合わせることで実現可能である.すなわち,それぞれのチャンネルからの入力と出力でセマフォの値を更新し,必要に応じて内部でチャンネルへの操作の有効無効を切り替えることで結果的に利用者側に対するブロック処理を実現する.

評価

本研究では,設計した制御器の出力する起動数が最適であることを検証する.ここで最適であるとは,処理対象のタスク全体を,最低限の,のべ起動数で,最短の時間で処理できる起動数を指す. 評価には,汎用性と再現可能性を高めるため,以下の機能を持つシミュレーターを用いる.

  • シミュレータは実時間ではなく,単位時間をステップとみなす
  • JobはWorkloadを持ち,ステップごとのCPU利用率を定義する
  • Workloadが0のステップはブロッキング処理を表現する
  • シミュレータはステップごとに任意の数のジョブを投入する
  • シミュレータはステップごとに起動可能なワーカー数を制御器から取得する
  • ワーカーはシミュレータで利用可能なCPU利用率までジョブの該当ステップのWorkloadを消費する
  • 消費できなかったWorkloadは次回のステップに回される
  • Workloadが0のステップはCPU資源を消費しないため無条件にステップを進める
  • 現状はスイッチングコストがシミュレータに反映できていない.

JobにはCPUビジーとなる処理,多くのシステムコールが発生する処理,ネットワークのような長期間のブロッキングが発生する処理などを再現したものを投入する.

設計した制御器に対する評価結果は以下のとおり

https://gist.github.com/monochromegane/5e9fc94371a9b2385eedd38d98341e6b#gistcomment-2758500 以下を参考のこと. 制御器の実装の番号とシミュレーション番号が同じにしている.

また,実環境で同様のジョブを用いた評価結果について今回は間に合わず未評価である.

まとめ

本研究では,処理やランタイムの特性に依存せずに,マシンの負荷に応じて反応的かつ継続的に,並行数を最適化する手法として,CPU負荷に応じて継続的に上限値を最適化する動的セマフォを提案した. また,シミュレーション環境においてではあるが,ノンブロッキングな処理方式を前提とする場合に有効なCPU使用率の目標値を負荷情報に応じて変動させる制御器として設計することができた. 本方式はCPU使用率とセマフォというランタイムや実装に依存しない方式を採用しているため,並行数を求めなければならない様々な場面に適用可能であると考える. 今後の課題として,実環境での評価としてGo言語のGoroutineの起動数に対する評価が必要である. また,制御器のパラメタ設計も課題として挙げられるが,フィードバック制御という歴史ある分野の蓄積を有効的に活用することで解決したい.

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 13, 2018

進捗

  • 上記要件を満たすシミュレータを作成
  • シミュレーションとしてWorkloads{10,20,30}のジョブを10個投入する
  • 各制御器とパラメタを変えながら結果を記載する

シミュレーション1

初期値からワーカー数を変えないFixController.
これは最適なワーカー数を求めるのに利用する.worker:7 ぐらいが最小かつ最短の様子

worker: 6

result

worker: 7

result

シミュレーション2

CPU使用率100%を目標値とし,不足した場合は workerを1ずつ増加させる SimpleController
増加が追いついていないので捌ききるのに時間がかかってしまった.

result

シミュレーション3

CPU使用率100%を目標とし,目標との差分のK倍を加える PController(比例制御器)
Kは0.1とした.
増加はかなり急上昇したので最短で捌けた一方でかなり無駄なworkerが立ち上がっているように思える.
また,(シミュレーション2でもstepを長くすれば観察できたはずだが)捌ききった後にCPU使用率が目標に足りないことからひたすらworkerを投入する挙動になった.

result

シミュレーション4

シミュレーション3と同じ条件だが,CPU使用率の目標値を90%とした.
これはCPU100%を目標とすると誤差が絶対に負にならず,worker数を削減することができないためである.
結果,100%の時にworker数を削減する挙動となり,シミュレーション3よりはworker数を抑えることができた.
一方で,捌ききった後に増加する振る舞いは解決していない.

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 13, 2018

現状では積分器,微分器の導入による目標値との誤差削減よりも先に捌ききった後にworker数を増やしてしまう件を解決した方が良い.
案としては

1: 使用率の目標を1割程度削減しておく
-> 常に100%の場合にはある程度一定に保とうとするが,実際に50%程度の状態が続くと増え続ける
2: キューもしくはワーカー数が空いてきたら減らしていく
-> 空きが出るまで増え続ける可能性がある
3: CPU使用率の目標値自体を変動させる
-> 一定期間のロードアベレージを目標値とするなど

1.はやったので,2or3.懸念事項が今の所思い浮かばない3が有効な気がする.

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 13, 2018

あとは,step数が短い & 総worker数が少ない を両方一緒に評価できるようなスコアリングを考えたい

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 13, 2018

3: CPU使用率の目標値自体を変動させる は ロードアベレージを使う方法の他,
worker数の間隔より長い間隔で動作する制御器を外側に組み込む方法もある.制御器へのfeedbackは今のCPU使用率で目標値との差を出力する.ただし目標値自体も更新される必要がある.もしくは制御器としてではなくて,ロードアベレージを出力する.
この場合,一回0%が目標値になった時にworker数も極端に減って細かい新しいジョブが大量に投入されても目標値を変えることができない可能性がある.(worker1で目標値が1%になってもこれ以上は増やさない)
なので,過去の値を元に目標値を決めるのではなくて,未来の値を予測すれば,少しだけCPU使用率が上がった場合でも,未来の値を予測して大きめの目標値を算出できる可能性があるのではないか.

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

シミュレーション5

シミュレーション4の時点の課題である,一方で,捌ききった後に増加する振る舞いは解決していない. の解決を試みる.
より長いステップ数で見るとシミュレーション4はこんな感じで増加し続ける

result

そこで, https://gist.github.com/monochromegane/5e9fc94371a9b2385eedd38d98341e6b#gistcomment-2758504 の 案3を簡易的に実装した
ロードアベレージではなく,直近3観測点の平均を目標値として3観測ごとにPControllerの目標値を変化させる仕組み(DynamicController)
PController自体はシミュレーション4と同じにする.
そうすると以下のように落ち着いた.しかし無駄なworkerは起動したままである.
これはCPU使用率が0%になり,かつ目標値も0%になったため,差分が発生せずに削減方向へのモチベーションがなくなってしまったため.

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

シミュレーション5-2

削減方向へのモチベーションは目標値と実績値の差が発生し得ない状態が原因.
そこでDynamicControllerで算出した目標値に-10することで解消してみた.
ただし,実績値がこの10%を超えない状態だと常にマイナスとなり,今度はこの状態からworkerは増えないことになる.うーむ.

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

シミュレーション6

安定してしまった後に反応できる仕組みを検討する.
一定期間のCPU使用率の標準偏差をとってそれが一定の値以下だったら安定したとみなして,減らしていく.それ以外はPControllerの挙動のままでやって見る (StabilityController, SD: 1.0.削減はとりあえず1づつ)
これだったら変化が少しでもあればPControllerの挙動にはなるが,なんか違う気もする

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

シミュレーション7

CPU使用率ではなくてCPU使用率の変化率を元に制御する.
変化率が一定以上なら,増やす.一定より下なら減らす.RateController.内部の増減はPController(K:0.05)を用い,この結果を反転する.

変化率を100に設定した場合は最初の変化を捉えることができ,一気に削減できる.一方で変化率が100に満たない小さいタスクが複数ある場合の問題を解決していない.また,CPU使用率が100%が続いた場合も削減され続けてしまう.
そもそも目標となる変化率を定めるのが難しい.

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

シミュレーション8

シミュレーション5も7も目標値を変動させるというアプローチで同じ.変化率を対象とする場合は正しい変化率をどうするかがわからない分,難しいと思われる.
シミュレーション5-2では目標値が-10になった時に,細かいタスクでの変動が望めないということであった.
変動する目標値を赤でプロットして5-2を再実行する.やはり目標値は変動しない.

result

そこでこの方式以外で目標値を抑えながらワーカー数を抑える方法を検討する.
目標値を常に-10にするのではなく,期間中(3step)の平均CPU使用率が0になった場合のみ-10にするようにした.
これにより,削減の仕組みは残しつつ,タスク投入時に目標値がマイナスのままにはならなくなった.

result

次にタスク群の完了あたりに不要なワーカー数の急増するが気になって来る.
これは期間中の平均を目標値に設定するが,目標値が設定されるまでの間に差分が大きくなってしまうためであった.
なので,大きく変動する際は目標値も即座に見直すようにする.むしろ定期的に見直しする処理は不要.
変動率が +0.3 以上であれば,ジョブが投入されたとして,目標値を100へ.
変動率が 0 または -0.3以下であれば,目標を現在のCPU使用率へ.ただし現在の使用率が0なら -100にしてワーカー数を一気に減らす.

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 14, 2018

変動ごとに目標値を見直す案,なかなか良さそうだった.
積分器,微分器の必要性は今の所わからない.明日実装して効果を見てみる

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 16, 2018

シミュレーション9

シミュレーション8は,変動を機に目標値を大きく変更する,そして安定したら何も目標値を変更しないという方式によってジョブ群の実行時,安定時,終了時に増減と一定に保つ挙動ができた.
しかしながら,ジョブが立ち上がりが比較的緩やか(安定まで時間がかかる)ような以下の場合にワーカーが純増していく.
またそこで止まるため最適解を求めることはしない.

result

そこで,使用率が停滞した場合に減らしていって足りなくなればまた追加するような仕組みを取り入れる.
色々試行錯誤したが,

変動率が +0.3 以上であれば,ジョブが投入されたとして,目標値を100へ.
変動率が 0 または -0.3以下であれば,目標を現在のCPU使用率へ.ただし現在の使用率が0なら -100にしてワーカー数を一気に減らす.

これを

変動率が +0.3 以上であれば,ジョブが投入されたとして,目標値を現在のCPU使用率+2へ.
変動率が 0 であれば 安定してきたのでワーカーの削減を検討するため,目標値を現在のCPU使用率の-2へ.ただし現在の使用率が0なら何もジョブがない状態のため何もしない.
変動率が -0.3以下であれば,ワーカーの削減によって処理できるジョブが減ったとみなし,目標値を現在のCPU使用率+2へ.ただし現在の使用率が0なら -100にしてワーカー数を一気に減らす.

とした結果がこれ.若干追いつくための勢いがなくなっているが,ある程度追従や削減ができそうになった.

result

目標値の差分を大きく取りすぎるとここのバタつきが大きくなるので+-2ぐらいで落ち着いた.
また,誤差が小さいことで制御器から求められる修正値が1未満になってしまい実際のワーカー数(整数)の変動が発生しないことから,これを切り上げするようにした(負の値は切り下げ)

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 16, 2018

シミュレーション10

シミュレーション9では幾分マイルドな挙動になったが,勢いも欲しい.ここで変動させる目標値をいじるのは職人芸になってしまうのでフィードバック制御のPID制御の仕組みを用いる.
P(比例)制御は現在やっているもの.今回,離散的な世界なので,I(積分)制御はステップごとの誤差の和を取っていく.
これによって,目標の値に近づけやすくなる.

Ki = 0.5 の場合.

result

また D(微分)制御.同様に離散的な世界なので偏差の差.要は前回との差が大きければ修正量が大きくなり,外乱を収めようと頑張る.
結果,早く目標値に近づくとされている. Kd = 0.5

result

@monochromegane

This comment has been minimized.

Owner

monochromegane commented Nov 16, 2018

シミュレーション11

Kp, Ki, Kd のそれぞれの定数はなかなかチューニングのしがいがありそう.
ひとまずは Kp: 0.1, Ki: 0.5, Kd: 0.5 が良さそう.

result

また,特に積分制御に置いて -100 などとしていた時の誤差が響いてきたため,変動率が0,+-3の目標値見直しのタイミングで積分の値をリセットするようにした.

いくつかのパターンのジョブを入れてみたところ.良さそうな感じがする

result

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment