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


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

スケールするために

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

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

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

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

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

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

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

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

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

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

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

べき等参照透過性

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

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

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

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

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

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

Lock-Free

Lock-Free動作は並列処理同士でブロックするタイミングがない状態を指す。

  • 排他制御を経由しない。(これはWait-Free扱い)
  • 排他制御はあるが待ちに入る状況にならない。
  • 排他制御による特定の処理に待ちが発生する可能性はあるが他の並列処理や開始をブロックしない。(結果としてその処理の完了時間がブレることがあるかもしれないが)

Lock-Freeな実装が増えると並列度を高く維持できる。

Wait-Free

繰り返し処理の記述にそもそも待ち処理が含まれない実装を指す。 この場合、ひとつの繰り返し処理の完了時間は理論上一定となる。 Wait-Freeである実装はLock-Freeな実装でもある。

Wait-Freeな実装が増えると並列度を高く維持できる。

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

アトミックアクセス

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

ロックの局所化

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

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

例えば設定ファイルの読み込みとメモリへの更新は起動時のみ行い、 実働中はリードオンリーアクセスしか行わない場合、 そのメモリを複数の並行処理で排他ロック(RWLock)を経由して共有 していても実質並行処理を妨げる動作は発生しない。(Lock-Free) (RWLockのRLockは複数の処理で重複してロックを取得できるので) 本当にこれらの挙動が重複して発生しないのを保証できるなら排他ロックをなくすことが可能(Wait-Free)

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

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

更新処理の手順

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

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

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

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

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

まとめ

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

追記:

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