輪読会:Site Reliability Engineering – 20章

前回に続いて、職場での SRE 本の輪読会のサマリを職場の Qiita:Team から転記しました。

Load Balancing in the Datacenter / データセンタ内でのロードバランス

データセンタ内のマシンの種類は色々あるけれど、その上では単一な (homogeneous な) サーバープロセスが走ります。小さいサービスでも少なくとも3つのプロセスが動き、大きいものであれば10,000プロセスが動くかもしれません。典型的にはサービスは100~1000くらいのプロセスから成ります。このプロセスは backend tasks もしくは単に backends と呼びます。その他のプロセスは client tasks と呼びます。client tasks はどの backend tasks にクエリを処理させるか決めなければなりません。

Google では多種多様なサービスがあり、ポリシの組み合わせも多岐にわたります。ここでは一般的に有用な技術を紹介します。

Google では (ほぼ) 全ての HTTP リクエストはリバースプロキシであるところの GFE (Google Frontend) が受けます。GFE の後ろにいるサーバーに対するロードバランスが本章の対象です。

The Ideal Case / 理想的な場合

どの時間帯にもバックエンドに均一に負荷が分散されることが理想です。全ての backend tasks が同じ CPU 使用率であるべきです。

1

2.png

(右肩下がりなのがダメなわけではなく、均一でないのがダメです。このグラフは CPU[0] が一番 CPU 使用率が高くなるように、意図的にソートされています)

CPU が遊んでいる分だけ無駄にコストがかかっている、ということです。

Identifying Bad Tasks: Flow Control and Lame Ducks / ダメなタスクを特定する: フロー制御とダメなやつ

client request を処理する backends を決めるため、先に backends のヘルスチェックが必要です。

A Simple Approach to Unhealthy Tasks: Flow Control / 機能不全な (backend) tasks を避ける単純な方法: フロー制御

ある backend task に対するアクティブなリクエストが (まだレスポンスを返せていないリクエストという意味) しきい値を超えたとき、その backend task は機能不全だと仮定しましょう。client tasks が機能不全な backend tasks を避けるだけでも簡易なロードバランサと言えるでしょう。

ただし、これだけだと backend tasks に計算資源が余っていても、長い時間居がかかるリクエスト存在するだけで (例えばネットワーク越しで I/O 待ちをしているような task)、それ以上のリクエストを割り当てられなくなります。

A Robust Approach to Unhealthy Tasks: Lame Duck State / 機能不全な (backend) tasks を避ける強力な方法: 役立たず状態

(Lame Duck State という英語を「役立たず状態」と訳しています)

client 視点での backend tasks は次のいずれかの状態に分けられます。

  1. Healthy / (自明なので略)
  2. Refusing connections / 起動中やシャットダウン中であったり、異常な状態に陥っている状態
  3. Lame duck / ポートを listen しているけど、client に対して明示的に「もうリクエストを送らないで」と言っている状態 (=> 以降は「役立たず状態」と表現します)

backend tasks が役立たず状態になると、アクティブな client tasks にその旨をブロードキャストします。アクティブでない client tasks も定期的なヘルスチェックをしているので、それほど時間がかからずに同じ情報を得られます。

役立たず状態を導入する利点は、シャットダウンの処理を簡潔化できることです。運の悪い client tasks が「アクティブだがシャットダウン中」の backend tasks にリクエストをすることを避けられます。

backend tasks のシャットダウンは次のように処理されます。

  1. スケジューラが SIGTERM を該当の backend task に発行する
  2. 該当の backend task が役立たず状態になり、クライアントに新しいリクエストは別な backend tasks に発行するように通知する
  3. 役立たず状態になる前に受け付けたリクエストを処理する
    1. の処理をしつつ、該当の backend task に対するリクエスト数が 0 になるのを待つ
  4. 設定された時間の経過後に、backend task は exit するか、もしくはスケジューラによって kill される

Limiting the Connections Pool with Subsetting / コネクションプールをサブセットで制限する

Google の RPC 実装では client の起動時に backend task に対してコネクションを作り、基本的には開きっぱなしになります。コネクションが idle な場合は、ヘルスチェックの頻度を下げ、TCP コネクションを落として UDP で接続し直します。

Picking the Right Subset / 正しくサブセットを作る

正しいサブセットのサイズは、サービスの種類に依存します。

  • clients の数が backends より極端に少ない場合は、ひとつの client あたりの backends の数を大きくして、リクエストを受けない backends を減らしたい
  • ある client が他よりも大量のリクエストを発行するような場合、その client のリクエストを処理する backends の数は大きくしたい

A Subset Selection Algorithm: Random Subsetting / サブセット選択アルゴリズム: ランダムなサブセット作り

backends をシャッフルして適当にピックアップするというサブセットの作り方もあるでしょう。これだと負荷はそれほど均等に分散されません。次の例を考えてみましょう。

  • 300 clients
  • 300 backends
  • サブセットのサイズは 30% (つまり、各 client は 90 個の backends と接続する)

3.png

最もヒマな backend は平均で 57 コネクションを持ち、忙しい backend は 109 コネクションを持つような分布になる。

サブセットのサイズを小さくしても自体は悪化するだけです。次は各 client に 30 個のコネクションを作らせたときの分布です。

4

A Subset Selection Algorithm: Deterministic Subsetting / サブセット選択アルゴリズム: 決定論的なサブセット作り

「ランダムなサブセット作り」の問題を解消するため、Google は次のようなアルゴリズムを考案しました。

def Subset(backends, client_id, subset_size):
  subset_count = len(backends) / subset_size

  # Group clients into rounds; each round uses the same shuffled list:
  round = client_id / subset_count
  random.seed(round)
  random.shuffle(backends)

  # The subset id corresponding to the current client:
  subset_id = client_id % subset_count

  start = subset_id * subset_size
  return backends[start:start + subset_size]

次のような環境を仮定しましょう。

  • backend tasks は全部で 12 個
  • subset size は 3 個
  • subset count (subset の数) は 4 個 (すなわち 12/3)
  • clients は 10 個 (これは subset_id にマップされる)

冒頭の Python のロジックで backends が次のようにランダムに並び替えられるとしましょう。

  • Round 0: [0, 6, 3, 5, 1, 7, 11, 9, 2, 4, 8, 10]
  • Round 1: [8, 11, 4, 0, 5, 6, 10, 3, 2, 7, 9, 1]
  • Round 2: [8, 3, 7, 2, 1, 4, 9, 10, 6, 5, 0, 11]

これに対して backends[start:start + subset_size] だけのリストを返します。これが client_id に対応する backends のリストになります。

いくつかの補足です。

  • シャッフルしないと backends が id 順にアップデートするような場合に普通になる可能性がある
  • (言葉で説明しづらいけど…) round ごとにシードを変えることで、全ての clients が不通になるケースを減らせる

300 個の clients が300 個の backends に対して各々 10 個のコネクションを張っているときの分布です。

5

Load Balancing Policies / ロードバランスポリシ

Simple Round Robin / シンプルなラウンドロビン

単に順繰りに backends へリクエストしていく方法をラウンドロビンと言います。ナイーブなラウンドロビンでは、暇な backend と忙しい backend でCPU利用率に2倍程度の差が出てきてしまいます。なぜこのような事態が発生してしまうのか、解説していきます。

Small subsetting / 小さなサブセット

ラウンドロビンがうまく負荷分散をできない理由のひとつは、各クライアントが均等に backends に対してリクエストを投げる保証がないからです。特に多くの clients が backends を共有している場合、すなわちサブセットのサイズが小さい場合に起こりがちです。

Varying query costs / 様々なクエリコスト

リクエストによって、必要な計算資源は大きく異なります。Google だと、重いリクエストと軽いものだと 1000 倍程度の差があります。こういう環境ではナイーブなラウンドロビンは負荷分散に向きません。

Machine diversity / マシンの多様性

色々なスペックのマシンが存在していると、ラウンドロビンでは均一に負荷分散できません。速いマシンの 1 CPU ユニットと、遅いマシンのユニットでは、処理効率が違います。この差を吸収するため、Google では GCU (Google Compute Unit) という単位で CPU リソースの計算をしています。

Unpredictable performance factors / 予想しづらいパフォーマンス上の要因

静的に解析しづらい不確定な要素もあります。例えば次のようなものです。

  • 近所の tasks が共有リソースを食い尽くしてしまう (e.g. ネットワーク帯域など)
  • tasks が再起動すると、数分間くらいリソースを多く使ってしまう (ことがある) (e.g. たとえば Java アプリケーションなど)

後者の場合、Google では tasks を役立たず状態 (前述の Lame Duck State) にして、pre-warm します。

Least-Loaded Round Robin / 負荷の低さを指標にしたラウンドロビン

ナイーブなラウンドロビンでは負荷分散しきれないならば、もっともアクティブなコネクションの少ない backends につなぎに行くのはどうでしょう。これは実際のところ だいたい うまくいきます。しかし、落とし穴があります。

healthy でない backend tasks があれば、それはリクエストに対して即座にエラーを返します。つまり、ここに対するアクティブなコネクションは残りにくいのです。結果として clients はこれに対して大量のリクエストを発行しますが、それらは全て失敗します。つらい。

なので、エラー数も鑑みて Least-Loaded Round Robin を組み込みましょう。

Least-Loaded Round Robin では解決しづらい問題は次のふたつです。

  1. tasks にとって支配的な時間は I/O 待ち (e.g. ネットワーク越しのレスポンス待ち) です。あるマシンは別なマシンよりも二倍の処理ができるかもしれないけど、I/O 待ち状態が支配的な場合はそれらのマシンは一緒くたに「アクティブなコネクション数は x」のように扱われてしまう
  2. 各々のクライアントは、別なクライアントが同じバックエンドにどのくらい接続に行っているのかわからない

過去の実験では Least-Loaded Round Robin はナイーブな Round Robin と同程度のパフォーマンスしか出せませんでした。

Weighted Round Robin / 重み付きのラウンドロビン

読んで字のごとしです。これで、ようやくマシンごとの負荷の差がぐっと減りました。

6.png

広告

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中