THINKING MEGANE

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

このエントリは、第三回 Web System Architecture 研究会 (WSA研)の予稿です。

はじめに

マルチコア時代において，単一のマシンで処理性能を最大化するため処理の並行化が行われる． ノンブロッキングな処理方式の採用によって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ビジーとなる処理，多くのシステムコールが発生する処理，ネットワークのような長期間のブロッキングが発生する処理などを再現したものを投入する．

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

シミュレーション1

初期値からワーカー数を変えないFixControllerによって固定値での最適なワーカー数を求めた．今回のシミュレーションではworker:7 ぐらいが最適と考えられる．

result

シミュレーション2

CPU使用率100%を目標値とし，不足した場合はworkerを1ずつ増加させるSimpleControllerでは，ジョブが多く投入される初期段階においてワーカー数の増加が追いつかないことからジョブ全体の処理がシミュレーション1と比較して長くなってしまっている．

result

シミュレーション4

CPU上限を目標値とした場合に制御器の出力が負にならないため，ワーカー数を削減することができない．そこでCPU使用率90%を目標とした．CPU上限に達した場合に不要なワーカー数を削減する一方で，目標値が固定のため，ジョブが完了し，CPU使用率が低下した場合にも反応してしまった．

result

シミュレーション5

目標値が固定であることからジョブ完了後にワーカー数を増加し続けてしまう問題に対応するためCPU使用率の目標値自体を変動させることとする． 本シミュレーションでは，CPU使用率が均衡する時点をワーカー数の上限であると仮定し，直近3観測点の平均を目標値として3観測ごとに制御器の目標値を変化させるDynamicControllerを実装評価した．

result

シミュレーション9

CPU使用率やジョブ実行状況にできるだけ速く追従するため，一定間隔ごとに目標値を見直すのではなく，CPU使用率の変動があった時点で目標値を変更する． 大きな増減を契機に調整していく仕組みになったことで，CPU安定時に積極的にワーカーを削減することができるようになった

以下では目標値の変動を赤でプロットしている．

result

シミュレーション11

頻繁に変更される目標値に高速かつ誤差が少なく適応していくため古典的制御手法であるPID制御を導入した． 調整の結果，本シミュレーションではPID制御のゲインとしてKp: 0.1, Ki: 0.5, Kd: 0.5が有効であった．

result

result

その他のシミュレーション

検討段階の各シミュレーション結果についてはこちら以降のコメント欄を参照のこと． 制御器の実装の番号とシミュレーション番号が同じにしている．

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

まとめ

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

発表スライド

発表を終えて

第三回のWSA研も様々な観点からの提案と活発な議論が交わされる有意義な場であったと思う． 特にrrreeeyyyさんのA survey of anomaly detection methodologies for web systemは業務で得た知識をサーベイ論文と組み合わせて再体系化していく非常に興味深い試みで，サービス運用者が参考にしていくべき取り組みだと思えた． 自分自身の研究発表では，個人的な開発時の課題であるGoroutine起動数のチューニングという課題から，研究を意識して問いを抽象化することで，実装に囚われない多角的な解決策を講じることができた点が良かったと思う．質疑では本手法が活きる場面を整理できていなかったことに気づけたことでもう一段先に進めた． 自身のアイディアや実装など狭い範囲から視点を広げるのは難しいことではあるが，こうして研究会を契機に継続的に訓練していくことで少しづつでも前に進んでいると思えるのはとても嬉しい．

このエントリーをはてなブックマークに追加