goroutineの動き方を調べた

2018-07-17

shinjuku.rbで話した内容です。
が、スライドだけだとよくわからないのでもう少し文章を補足した版を上げておきます。

goroutineはどうやって動いているのか from ota42y

要約

以下のように書くと、非同期でgo xxxに渡した関数が実行されます。

実態はスレッドらしいのですが、基本的にはうまく覆い隠されており、以下のような細かい点は意識しなくてよいようになっています。

今回は、goはこれらの点をどう解決しているのかを調べました。

上記のコードのうち、go xxxの部分をコンパイルした結果は以下のようになっています。

go xxxと書いた場合、コンパイルした結果を見る限り、runtime.newprocに関数ポインタ(?)を渡しています。
newprocは実質newproc1を読んでいるだけなので、newproc1で関数の非同期処理を始めていそうです。

newproc1の中身はかなり巨大なため、ここから攻めるのは用意ではありません。
https://github.com/golang/go/blob/99e9be804379d0607de4a322353b317aa087073d/src/runtime/proc.go#L3316

幸いにもおそらくgo1.1の頃のDesign docが存在しています。
現在の実装を見る限り大きく変わってはいないので、これベースで見ていきます。
https://golang.org/s/go11sched

goroutineの処理において関わる要素は以下の3つです。

Gは作成されるとキューに積まれます。

PはGを取り出して、Mにくっつけて関数を実行します。

Mがsyscallとかロックとかで待ち状態になると、別のMを作りGを処理します。
Mのロックが解除されたらまた実行を始めます。

複数Pが存在する場合、キューが１つだと取り出し時に競合が発生します。
そのため、このままだと並列数を上げても速度が上がりません。

そのため、Pごとにキューを用意して自分のキューを操作するようにします。
これにより、競合が発生しなくなるためスケールするようになります。
ただしこの方法ではP間でキューの中身に差が出るので適切な負荷分散が必要です。

Pごとにキューを持つようになったので、キューの量に差が出てしまい、結局スケールしなくなってしまいます。

Goではwork-stealingアルゴリズムで負荷分散を行うことで、この問題を回避しています。

このアルゴリズムは以下のような特徴があります。

このアルゴリズムに従い、Pは自分のキューが空になると、別のPのキューにアクセスして中身を半分奪います。

自分のキューが空になった時だけ奪うので、複数ワーカーでもアクセス回数は少なく抑えられています。
また、どのキューから盗むのかもランダムにしています。
この場合、キューが空になるタイミングが同じで、かつ奪うキューが被った場合のみ競合するため、起きにくくなっています。

なお、Pが持つキューがあふれた場合の待避用としてglobalなキューも用意されています。
ここに対しては競合が発生しやすいですが、他のキューを見る回数は抑えられているため、あまり問題にはならないのではと思います。