GolangのGCを追う

Go1.5とGo1.6でGoのGCのレイテンシが大きく改善された．この変更について﹁ちゃんと﹂理解するため，アルゴリズムレベルでGoのGCについて追ってみた．

まずGoのGCの現状をパフォーマンス︵レイテンシ︶の観点からまとめる．次に具体的なアルゴリズムについて，そして最後に実際の現場でのチューニングはどうすれば良いのかについて解説する．

GoのGCの今

最初にGoのGCの最近の流れ︵2016年5月まで︶をまとめる．

Go1.4までは単純なStop The World︵STW︶GCが実装されていたがGo1.5からは新たなGCアルゴリズムが導入された．導入の際に設定された数値目標は大きなヒープサイズにおいてもレイテンシを10ms以下に抑えることであった．Go1.5で新たなアルゴリムが実装されGo1.6で最適化が行われた．

以下は公開されているベンチマーク．まずはGo1.5を見る．


GopherCon 2015: Rick Hudson - Go GC: Solving the Latency Problem

グラフの横軸はヒープサイズで縦軸はレイテンシである︵小さいほどよい︶．以前のバージョンと比較するとヒープの増加に伴ってレイテンシが3.0sを超えていたのがほぼ0sに抑えらているのがわかる．コミュニティからも以下のようなベンチマークが公開されている．


●https://twitter.com/brianhatfield/status/634166123605331968

●Billions of request per day meet Go 1.5 (The new version of Go reduces our 95-percentile garbage collector from 279 milliseconds down to just 10 ms)


次に以下はGo1.6のベンチマーク．


QCon: Go GC: Prioritizing Low Latency and Simplicity

縦軸と横軸はGo1.5と同じ．まずGo1.5のグラフと比べると10倍のヒープサイズでベンチマークが行われているのがわかる．Go1.5が50GBに達する前にレイテンシが増大しているのに対してGo1.6は250GBのヒープに対しても10msのレイテンシで抑えらているのが確認できる．

Go1.7のリリースが近いが，既に今までと同じくTwitterの@brianhatfield氏がCanaryテストを行い，さらにGCのレイテンシが改善されたことが報告されている．


●Go 1.7 observed performance changes (production canary@eeca3ba)


これらのアップデートからGoにおいてGCのレイテンシは大規模プロダクション環境においても全く問題にならないレベルになっていることがわかる．つまりパフォーマンスに問題があったときに疑うべき場所としては優先度は低いと言える．

以下ではこれらをどのように達成したのかを追っていく．

参考文献

まず最初に筆者はGCに関してはほぼ初心者であった．GoのGCを少しでも﹁ちゃんと﹂理解したいがために勉強したにすぎない．そのためGCの知識は素人に毛が生えた程度でしかない．先に参考文献やリンクをまとめておくので，気になるひとは自分でそれらを追ってみるのが良い．

まずGCの基礎については以下の書籍が勉強になった．


●ガベージコレクションのアルゴリズムと実装 - とにかく初心者はまずこれを読むのが良い．本書はアルゴリズム編と実装編に分かれている．アルゴリズム編では基本となるアルゴリズムが図解と疑似コードで丁寧に解説されておりGCの基礎を抑えることができる．中で述べられているようにGCの基本はGCが登場して50年たってもそれほど変わっていないのでこれらを抑えるだけでもだいぶ話に入っていける．実装編では実際のruntime例えばPythonやV8などをのコードを追っていく．これで﹁GCのコードの追い方﹂がなんとなくわかった

●ガベージコレクション - こちらは最近︵2016年3月︶発売されたばかりの本．先に上げた﹁ガベージコレクションのアルゴリズムと実装﹂がカジュアルな本であるのに対してこちらは膨大なGC研究がまとめられておりより硬派な本であると言える．基礎アルゴリズムから説明していくのは同じであるが本書は並列・並行処理/マルチコア時代のことが意識されているのが特徴的である．Goで採用されているConcurrent GCはこちらで学んだ．また参照局所性といったハードウェアに対する言及も多い


次にGoのGCそのものについての解説は以下のRick Hudson氏の一連の発表及びブログ，デザインノートを見るとよい．


●GopherCon 2015: Rick Hudson - Go GC: Solving the Latency Problem (slide)

●Go GC: Prioritizing low latency and simplicity

●Go 1.4+ Garbage Collection (GC) Plan and Roadmap


GopherConとQconの内容は基本的に同じだが後者はGo1.6に関するアップデートを幾つか含んでいる．

以下の論文が参考として挙げられている．


●On-the-Fly Garbage Collection: An Exercise in Cooperation - 基礎となったアルゴリズムについて述べた論文

●Sapphire: Copying GC Without Stopping the World - 上記のアルゴリズムの正確さと完全性，GCが﹁終了すること﹂を示した論文


またruntime packageのソースコード︵mgc.go︶にも具体的な実装の解説がコメントで書かれているので参考になる．


●https://golang.org/src/runtime/mgc.go


またGo1.4以前のGCの歴史はstackovwerflowに良い回答があったのでそちらを見ると良い．


●What kind of Garbage Collection does Go use?


以下はこれらを自分の言葉で整理し直したものである．

ハードウェアの進化とソフトウェアの進化

Rick Hudson氏が発表でもブログでも述べていたことだが，GoのGCは現在だけではなくて10年後も使えるものを目指している．ハードウェアの進化を見据えてソフトウェアを改善している．

今回のGoのGCの変更で仮定されているのは﹁将来のハードウェアがGCのスループットを改善する﹂である．そのためGCが目指したのはレイテンシの改善である︵レイテンシのためにスループットを犠牲にされている︶．

GoのGCアルゴリズム

Go1.5以降のGCアルゴリズムはConcurrent Mark & Sweepである．GC中のオブジェクトの状態の表現にはTri-color markig︵三色マーキング︶を用いている．

Mark & Sweep

まずMark & Sweepについて説明する．Mark & Sweepは基礎中の基礎のGCアルゴリズムである．アルゴリズムはその名前の通りMarkとSweepという2つのフェーズに分けられる．まずMarkフェーズではルートを起点にポインタを辿りオブジェクトにマークをつけていく．次にSweepフェーズではマークが付けられていないオブジェクトをフリーリストに追加していく．フリーリストに追加された領域は次回のアロケーションで利用可能になる．

つまりMark & Sweepではルートから到達可能なオブジェクトを生きているオブジェクトとし到達不可能なオブジェクトを死んでいると判別し回収する．オブジェクトがミューテータ︵アプリケーション︶に実際に使われているか?といった判別は行わない︵つまり全く使われていないにもかかわらずルートから到達できればオブジェクトは掃除されることはない︶．

GCはなぜ問題になるのか?

こう見るとGCは非常に単純に見える．しかしGCは多くのアプリケーションで大きな問題になる．それはStop The World︵STW︶，つまりミューテータの実行を止めること，が必要になるからである．なぜならミューテータはGCがオブジェクトが生きているか死んでいるかを判断している間にヒープのトポロジを変更してしまうからである．

例えば，GCの途中にミューテータが新たにアロケーションを行ってしまった場合を考える．するとそのオブジェクトはマークされず，生きているのにもかかわらずSweepの対象になってしまうかもしれない．これは大きなバグになる．GCの正確さを保証するためにはミューテータとコレクタの動作を同期させる必要がある．

この同期のための最も単純な戦略はGCを行っている間はミューテータを完全に止めてしまう方法である．しかしこれではアプリケーションはまともなサービスを提供できなくなる．例えばWebアプリケーションにおいてはしばらくレスポンスを返せないなどといった状況が発生してしまうかもしれない．GCの研究においてSTWをいかに短くするか，レイテンシをいかに小さくするか，もしくは避けるか，は大きな分野である︵他には断片化をいかに少なくしてヒープの使用効率を良くするかといった方向もある︶．

Go1.4以前のGCはこの単純なSTWであり，レイテンシが大きな問題になっていた．以下で説明する，Tri-color markingやConcurrent GCはSTWを減らし，レイテンシを改善するための方法である．

Tri-color marking

一度にGCのプロセスを全て実行するのではなく，GCの実行を分割し，ミューテータと交互に実行させることでレイテンシを小さくすることができる．このように実行するGCをインクリメンタルGCと呼ぶ．Tri-color marking︵三色マーキング︶は，インクリメンタルGCを可能にするためのオブジェクトの抽象化である．

Tri-color markingはその名の通りGC中のオブジェクトを状態に応じて以下の3種類に分類する．


●白 - まだ探索されていないオブジェクト

●グレー - 探索途中のオブジェクト

●黒 - 探索済みのオブジェクト


Mark & SweepをTri-color markingを使ってインクリメンタルに実行すると以下の3つのフェーズに分けることができる．GCの開始時点では全てのオブジェクトの色は白である．


●ルートスキャンフェーズ - ルートから直接参照可能なオブジェクトをグレーに塗る

●マークフェーズ - グレーのオブジェクトを取り出し，その子オブジェクトをグレーに塗る．全ての子オブジェクトがグレーに塗られたらそのオブジェクトは黒に塗られる

●スイープフェーズ - ヒープ領域をスキャンし白いオブジェクトを死んでいるオブジェクトであると判別してフリーリストに連結する．また黒いオブジェクトは白色に戻す


ルートスキャンフェーズはGCの開始時に一度だけ実行される．マークフェーズでは，全てのグレーオブジェクトを一度に全て処理するのではなく，一定個数だけ処理して中断し，ミューテータの実行を再開する．これを繰り返しグレーのオブジェクトがなくなるまでこのフェーズを続ける．スイープフェーズもヒープを一括でスキャンするのではなく順次スキャンする．ミューテーターは，ルートスキャンフェーズとマークフェーズの間，マークフェーズの間，そしてスイープフェーズの間に実行が再開される．

ライトバリア

マークフェーズを中断しミューテータを再開する場合を考える．この時に何も考慮しないと問題が発生する．

例えば，ミューテータを再開した際に，グレーのオブジェクトAから参照された白いオブジェクトBがあるとする．ミューテータがこのオブジェクトBを別の黒いオブジェクトCから参照するようにポインタを更新し，かつオブジェクトAからの参照を削除してしまったとする．このままマークフェーズが再開するとどうなるか?黒いオブジェクトCは﹁探索済み﹂である．よってオブジェクトCは再びスキャンされることはない．新たに参照された白いオブジェクトBもスキャンされることはなく﹁マーク漏れ﹂が発生する．つまり生きいるのに回収されるという大きな問題が発生してしまう．

この﹁マーク漏れ﹂︵オブジェクトの迷子︶が発生するのは以下の2つの条件が成立する時である．


●ミューテータが白いオブジェクトへのポインタを黒いオブジェクトに書き込む

●すべてのグレーのオブジェクトから，その白いオブジェクトへの経路が削除される


これを防ぐのがライトバリアである．ライトバリアはGenerational GC︵世代別GC︶などでも使われる手法である．インクリメンタルGCのライトバリアはいくつか提案されている．Dijkstraによって提案された手法では﹁新たに参照されるオブジェクトが白いオブジェクトであればそれをグレーとする﹂．上の例だと，白いオブジェクトBを黒いオブジェクトCから参照するときにオブジェクトBをグレーにする．こうすることでBの﹁マーク漏れ﹂を防ぐことができる．

インクリメンタルGCによりミューテータの実行を長時間妨げることはなくなり，レイテンシは大きく改善できる．しかし，このライトバリアによってオーバーヘッドを避けることができない．よってスループットを犠牲にする必要がある．

Concurrent Mark & Sweep

これらをConcurentに実行しているのがGoのGCである．並行への移行は単純なステップである．新たに加わる困難はコレクタとミューテータが適切に同期してヒープの一貫したビューを維持することである．

GoはそれぞれのOSスレッド上にスケジューリングのコンテキストを持つ．このコンテキストはGoroutineのためのローカルのスケジューラであるとみなせ，runtimeのコードではPと呼ばれる︵詳しくは“The Go scheduler” がわかりやすい︶．GCにおいては，フェーズ︵スキャンフェーズなど︶が変わるたびに，すべてのPからのackを待つことで複数のスレッド間の同期を行っている．

GCは終了することが重要である．Concurrent GCではミューテータがGCプロセスと同時に動くためオブジェクトは次々に新たにアロケートされていく．このためマークフェーズが収束しない可能性がある．これを解決するためにGoではマークフェーズ後にmarkterminationフェーズが存在する．ここでは新たなオブジェクトは全て黒色でアロケートされる．これによりGCは収束に向かう．

GOGC︵GOのGCをチューニングする︶

GCというとJavaのようなたくさんのチューニングパラメーター︵xmsやxmx︶を思い浮かべる．Goにはただ1つのGOGCという環境変数がGCをチューニングするパラメーターとして提供されている．

GOGCはGoにおける最も古い環境変数の1つである︵A whirlwind tour of Go’s runtime environment variables︶．この環境変数はGCのAggressivenessを決める．

デフォルト値は100である．これはある時点でのGC完了後に到達可能であったオブジェクトのサイズよりも100%，つまり2倍大きなヒープサイズが消費されたら次のGCを実行するという意味である．

どのようにチューニングするか?まずより大きな値，例えば200をセットする．これはある時点でのGC完了後に到達可能であったあったオブジェクトのサイズよりも200%，つまり3倍のヒープサイズが消費されたら次のGCを実行するという意味である．つまりGCの実行を遅らせることができる．RAMに余裕がありGCに使われる合計時間を減らしたい︵スループットを向上させたい︶場合は大きな値を設定する．．

次により小さな値を設定するとGCの実行間隔が短くなる．メモリの使用量を少なくしたい場合は小さな値を設定する︵offを設定するとGCは実行されなくなる︶．

GoのGCはハードウェアの進化が考慮されているのであった．もしハードウェアが進化してRAMの容量が2倍なったらどうするか．GOGCの値を2倍にすればGCのサイクルを半分にすることができ，チューニングなしでアプリケーションを簡単にスケールさせることができる．

まとめ

GoのGCの変更について追ってみた．追ってみて他の言語と比べてもシンプルなGCが実装されているなあと感じた．そのためアルゴリズムなどを理解するのは容易だった．シンプルさの思想がGCにもあるのは良いなあと感じた．

GCにはレイテンシやスループット以外にも解決するべき問題がある．例えばGoの場合は断片化の問題などは考慮されていない．今後その他の問題にどのように対処していくのかも楽しみになった．