monochromegane/wsa_3.md Secret

## wsa_3.md

      
    Raw
  

              wsa_3.md
            
          
    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負荷が安定になることが一つの上限とみなせると仮定していくつかの制御器を設計する．

初期値からワーカー数を変えないFixController (比較用)
CPU使用率100%を目標値とし，不足した場合は workerを1ずつ増加させる SimpleController
CPU使用率100%を目標とし，目標との差分のK倍を加える PController(比例制御)
3.のCPU使用率の目標値を90%としたもの
直近3観測点の平均を目標値として3観測ごとにPControllerの目標値を変化させるDynamicController
一定期間のCPU使用率の標準偏差をとってそれが一定の値以下だったら安定したとみなして，workerを減らしていくStabilityController
CPU使用率ではなくてCPU使用率の変化率を元に制御するRateController
5.のDynamicControllerを元に定期ではなく大きな変動ごとに目標値を見直す方式
8.のDynamicControllerを元に定常時の不要なworkerを削減する方式
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の起動数に対する評価が必要である．
また，制御器のパラメタ設計も課題として挙げられるが，フィードバック制御という歴史ある分野の蓄積を有効的に活用することで解決したい．