Chap 20 - Load Balancing in the Datacenter
会社でやったSRE本の輪読。後半のアルゴリズムは口頭で説明したからあっさり。
Load Balancing in the Datacenter
・データセンター内での負荷分散について
┗クエリのストリームを負荷分散するアルゴリズムについて
データセンターに到達するクエリのストリームを想定すると
- クエリをさばくプロセスがデータセンター内にある
- サービスは置換可能なサーバプロセスとして動作する
- サービスは３つ以上のプロセスから、大きいものでは1000以上のプロセスで構成
- これらのプロセスをバックエンドタスクと呼ぶ
- これ以外のタスクをフロントエンドタスクと呼ぶ
- フロントエンドタスクは受信クエリごとにバックエンドを接続
ほとんどのHTTPリクエストはGFEに到達し、GFEはここのプロセスにルーティングする
┗単独のHTTPリクエストが、複数のシステムへの依存のある遷移を引き起こすとファンアウトが大きくなる
The Ideal Case
理想的なケースでは、特定のサービスの負荷は、すべてのバックエンドタスクに完全に分散され、 特定の時点で、負荷の最も少ないバックエンドタスクとまったく同じCPUの量が消費される
データセンタにトラヒックを送れるのはタスクがサチるまで。 サチるとデータを制御する必要があるが、CPUとしては効率が悪くなることも
酷い場合には1000CPUを予約していて７割使用していないことも
Identifying Bad Tasks: Flow Control and Lame Ducks
バックエンドタスクを決定する前に、バックエンドプール内の異常タスクを特定して回避する必要がある。
A Simple Approach to Unhealthy Tasks: Flow Control
- クライアントタスクがvバックエンドタスクへ送信したアクティブなリクエスト数をトラッキングする
- 特定の接続数に達したらリクエストを送らないようにする
リクエストが積み重なるとワークロードは他のバックエンドで実行されるようになる
極端な環境下では有効だが、その前にバックエンドを食いつぶすのが普通
- またバックエンド的には余裕がるが、セッション数としてサチッたとみなされリソースが有効活用できない場合も
- リクエストをすぐ返さないような制限がかけられている場合は、この制限が逆墳して全てのバックエンドに到達負荷になる場合も
┗アクティブリクエスト数を上げると回避できるが、タスクが異常かどうかの判断はできない
A Robust Approach to Unhealthy Tasks: Lame Duck State
クライアントからはバックエンドは以下の３状態に分類される
- healthy
- 正しく初期化され、リクエストをさばく
- コネクションを拒否
- バックエンドが応答しない、タスクが落ちているか異常状態
- レイムダック
- ポートをリッスンしているが、リクエスト送信の停止を応答する
タスクがレイムダック状態になると、クライアントはその状態をブロードキャストする
┗googleのrpc実装では、インアクティブでもヘルスチェックUDPを投げるので状態がインアクティブと判断ができる
レイムダック状態でタスクが存在するの利点
- シャットダウンしているバックエンドでアクティブになっていたリソースへのエラー通知を回避できる
┗エラー処理をせずにバックエンドタスクを停止すると、他のタスクへの影響もある。シャットダウンのフローは以下。
- ジョブスケジューラがSIGTERMシグナルをバックエンドに送信
- バックエンドはレイムダック状態になり、他のプロセスにリクエストするように返答する。
- レイムダック前に受け付けたリクエストは正常に処理される
- リクエストがクライアントに戻るごとに、レイムダックバックエンドの球持ちはへる
- 一定のインターバルのち、バックエンドは正常終了するかジョブスケージューラにkillされる。
Limiting the Connections Pool with Subsetting
ヘルス管理に加えて、負荷分散のもう1つの考慮事項はサブセット化。 クライアントタスクが相互作用する潜在的なバックエンドタスクのプールを制限する。
Picking the Right Subset
- 適切なサブセットサイズはシステムの挙動に左右される。
- サブセットサイズを毛亭したら、サブセットを定義するアルゴリズムが必要
A Subset Selection Algorithm: Random Subsetting
- クライアントがバックエンドリストをシャッフルして使えうものを使う
┗効率が悪かった
A Subset Selection Algorithm: Deterministic Subsetting
ランダムなサブセット化の制限に対するGoogleのソリューションは、 確定的サブセット化
def Subset(backends, client_id, subset_size): subset_count = len(backends) / subset_size ＃クライアントをラウンドにグループ化します。 各ラウンドは同じシャッフルリストを使用します round = client_id / subset_count random.seed(round) random.shuffle(backends) ＃現在のクライアントに対応するサブセットID： subset_id = client_id % subset_count start = subset_id * subset_size return backends[start:start + subset_size]
クライアントタスクを「ラウンド」という単位で分割する
round i = subset_count * i
subeset_count = バックエンドタスクの数を目的のサブセットサイズで割ったもの
[ subset_count = 12/3 ] = 12のバックエンドタスク必要なサブセットサイズが3
クライアントが10個ある場合、前述のアルゴリズムは次のshuffled_backendsを生成する可能性がある
- ラウンド0：[0、6、3、5、1、7、11、9、2、4、8、10]
- ラウンド1：[8、11、4、0、5、6、10、3、2、7、9、1]
- ラウンド2：[8、3、7、2、1、4、9、10、6、5、0、11]
重要な点は、各ラウンドがリスト全体の各バックエンドを1つのクライアントにのみ割り当てること
優れたアプローチとしては、ラウンドごとに異なるシャッフルを使用して、残りのすべてのバックエンドにこの負荷を分散すること
Load Balancing Policies
クライアントタスクがサブセット内のどのバックエンドタスクがクライアント要求を受信するかを選択するために使用するメカニズム
ロードバランシングポリシーの複雑さの多くは、クライアントがそれぞれに使用するバックエンドをリアルタイムで決定すことによる
Simple Round Robin
- 一定程度は有効だが、クエリの変動やリソースのバースト等によってコストがうまく分散できない
Small subsetting
- 作業量単位を小さくしてバックエンドごとの作業量をならす
- 異なるプロセスが同じバックエンドを利用すると、クライアント間でリソース使用量が大きく変わる
┗トラヒックを大きく生成するクライアントのサブセットのバックエンドが高負荷に
Varying query costs
- クエリコストに大きな差異があるシステムでの負荷分散は難しい
- インタフェースを標準化するため、重いリクエストを標準としてサービス設計をすることはある
- そうすると一部のバックエンドに重いたタスクを裁く必要が生じ、最悪は応答不能に
Machine diversity
- 同じデータセンター内のすべてのマシンが必ずしも同じであるとは限らない - マシンごとに処理能力が違うとラウンドロビンじゃ分散できない
- googleはGCUというCPUレートの仮想ユニットを作り、それを各CPUをパフォーマンスに応じてマッピング
Unpredictable performance factors
パフォーマンスに寄与する多くの予測不可能な要因の2つ
- 敵対的な隣人
他のプロセスによる影響。メモリキャッシュ内のスペースや帯域の奪い合い。
- タスクの再開
タスクが再開されると初期に高負荷がかかる
Least-Loaded Round Robin
各クライアントタスクがサブセット内の各バックエンドタスクに対するアクティブリクエストの数を追跡し、最小数のアクティブリクエストを持つタスクのセット間でラウンドロビンを使用すること
Weighted Round Robin
これがいちばんよかった
