Goでスケールする実装を書く

スケールする実装を書くためのガイド

スケールするために

• 並列度とアムダールの法則
• べき等参照透過性
• Lock-FreeとWait-Free
• アトミックアクセス
• ロックの局所化

並列度とアムダールの法則

時間単位の場合は繰り返し処理のトータル時間に対し、 並列処理を妨げない処理時間の割合を「並列度」という。 （コードプロファイルを使って求める場合もあるが、 比較的単純なコードでないと計算が複雑になりやすい。）

p 並列度
n 並列数
性能比 1/((1-p)+p/n)

p=0.9のとき４倍の性能を得るにはn=6が必要。
n=5で４倍の性能を得るにはp=0.938が必要。

n=無限大とすると、性能比は以下の式におちつく。

理論上の性能向上限界 = 1/(1-p)

• 並列度90%の処理をどれだけ多数コアに分散しても理論上10倍処理効率が限界。
• 並列度95%の処理をどれだけ多数コアに分散しても理論上20倍処理効率が限界。

この法則をアムダールの法則という（名前があるのは最近知った）

ただし並列度を正確に導出するのは難しいため、負荷試験を通じて 並列度の推測値を求めるほうが容易。 実装時に並列処理を妨げる実装かそうでないかを意識して より並列処理を妨げない実装を目指しておくことが重要。

もちろん並列処理の間で共有するリソースが無い場合は並列度100%が保てる。 並列度100%の処理になれば処理効率はコア数に比例して向上する。 （32コアに分散すれば32倍の処理効率が得られる）

べき等参照透過性

ある実装が他のコアやプロセス、他のホストで稼働中の場合、 どこにある実装で処理を実行したとしても 引き渡す情報が同じなら結果も同じであることを「参照透過」であるという。

このような実装の場合、いくつもその実装が動く環境を用意しておいて、 順番に使われていない実装に丸投げするように分散させることで スケールして大きく性能を確保できる。 （各処理系に入力値をばらまくところは並列に動かないので並列度100%にはできない）

以下の構成とすれば１０個前後のワーカーやホストに関してはほぼリニアにスケールする。

• goroutineワーカーパターン
• Loadbalancer＋マルチホスト

参照透過でない処理を参照透過にするのは大変難しい。 設計段階で参照透過を維持できるところを抽出しておき、 参照透過のまま維持することを心がける。

参照透過な実装は並列に分散させやすい特性を持つ。

Lock-Free

• 複数同時処理の際にそれぞれの処理の進行を妨げない実装。
• 複数同時処理の1つ以上は一定の処理量で完了する。

Wait-Free

• 複数の並行処理にかかわらず一定の処理量で完了することを保証する実装。
• この場合、それぞれの処理の完了時間は理論上一定となる。
• Wait-Freeである実装はLock-Freeな実装でもある。
• こちらはスループットよりもレイテンシを一定にする目的が強い。

並列度の高いコンテナ実装

例えば https://github.com/zond/gotomic パッケージを使うとか。 （コンテナ操作コストは増えるけれどロックを使っていないので並列度がキープできる）

go1.9であれば標準の「sync.Map」が 複数の参照処理と単一の変更処理を同時にブロックせずに実行できる実装になってる。

アトミックアクセス

• sync/atomicパッケージによるアトミックアクセスは排他制御なしに競合することなくメモリ操作が可能。
• ただしCPUアーキテクチャ上のプリミティブな値やポインタ型しか扱えない。
• Lock-Free,Wait-Freeを実現するのにもっとも有効な方法。

ロックの局所化

極力ロック範囲を局所化することで アクセスが同時に行われようとする確率を下げる。 （ロック時間が減少する）

また、リードオンリーなデータ参照はLock-Free化する方法がある。

例えば設定ファイルの読み込みとメモリへの更新は起動時のみ行い、 実働中はリードオンリーアクセスしか行わない場合、 そのメモリを複数の並行処理で排他ロック(RWLock)を経由して共有 していても実質並行処理を妨げる動作は発生しない。 （RWLockのRLockは複数の処理で重複してロックを取得できるので）

リードやライトが入り交じるようなデータコンテナが並列度を上げるのに厄介な障害となるが、 更新処理が低頻度であればひとつの手法として、以下のような方法がある。

• 複数の並列処理が同時に読み出しを行い、
• コンテナの更新は単一の処理だけが行うとする

更新処理の手順

• 更新処理の排他ロックを取得
• 読み出し専用コンテナのコピーを作成して更新専用コンテナとする。
• 更新処理を更新専用コンテナに対し行う
• アトミックSwap操作にて読み出し専用と更新専用のコンテナ参照を入れ替える
• 更新処理の排他ロックを開放

以上の仕掛けでロック対象を分離して 更新側はがっちりロックするけど参照側をロックフリー化する。

並列度の高い実装の注意点

上記の例やsync.Mapにおいても単一コアからみた処理コストは増えてしまってる。 マイクロベンチにおけるスコアは多くの場合単純な実装よりは悪化する傾向がある。 しかし、並列度が高いのでCPUコア数を増やすことでトータル性能を引き出せる（場合が多い）。

それでも共有せざるを得ないリソース

• ログ出力まわり
• 永続化データ（データベース等）
• 物理デバイス(NIC,タイマー,SIMDブロック,GPUリソース)

これらのロック時間をどれだけ小さくできるかが並列度を高く保つキモになる。 キャッシュなどを併用することで更新系と参照系を分離しロック時間を抑える方法もある。

まとめ

• 設計段階で参照透過性が維持できる箇所を作って維持する。
• よりLock-Freeな実装を心がける。sync.Mapやatomicパッケージは強い味方。
• 並列度100%ならフリーランチなアプリになる(ホストマシン投資だけで性能が向上する)。
• 更新頻度が高い永続化が必要になると途端に並列度が下がるが仕方がない。
• 排他制御はデータ構造やチャネルをうまく使うことでロック機構の利用を避ける。
• ロックを使わざるを得ない場合は範囲をできるだけ狭くなるよう設計する。
• マスタデータへの更新は1goroutineが担当し、その他のgoroutineはキャッシュを参照するのは結構使えるパターン。

追記:

べき等というよりは参照透過というツッコミをたくさんいただきましたので修正します。

追記2:

Lock-FreeやWait-Freeの説明がおかしいとの指摘をいただきましたので修正しました。 またgo1.9にてsync.Mapが追加されましたのでそれについての言及を追記しました。

• tips
• concurrency