あるサービスがあるとしよう。詳細は一旦置いておくとして、外部からリクエストを受け取り、それに応じて何らかの処理を行うものと仮定する。そのリクエストはHTTPリクエストかもしれないし、RPCかもしれないし、ネットワーク層でルーティングすべき単なる入力パケットかもしれない。より具体的な話は後でしよう。

そのパフォーマンスについて、何が言えるだろうか？

現時点でわかっているのは、リクエストを受け取り、それに対して何かをするということだけだ。だがこれだけで、議論に役立つ2つの指標を定義できる。

• リクエストレートについて語ることができる。これは単位時間あたりに流入するリクエストの量だ。多くの場合「リクエスト毎秒（requests per second）」で測るが、個々のリクエストよりもデータの総量が重要な場合もあるため、代わりに（あるいは加えて）「バイト毎秒（bytes per second）」という指標を用いることもある。
• そのうちの一部（最良の場合はすべて）が正常に処理される。このレート、すなわち単位時間あたりに完遂された成功した仕事の量についても語ることができ、これをスループットと呼ぶ。

ここで、この先の議論を通じて何度も立ち戻ることになる具体例をいくつか紹介しておくのがよいだろう。私がよく知るシステムに基づいて2つのシステム像を選んだが、いずれもよくある典型的なアーキタイプなので、見覚えがあるはずだ。

この2つの指標を定義したことで、パフォーマンスを抽象的に両者の関係として語ることができる。すなわち、リクエストレートの関数としてのスループットである。言い換えれば、トラフィックが増えるにつれて、有用な仕事の量にどう影響するかということだ。

純粋な思考上の理想世界であれば、すべてのリクエストは常に正常に処理され、リクエストレートとスループットは1対1の関係になるだろう。

しかし、堕落した現実世界では、システムは有限の物理ハードウェア上で動作しており、したがって有限のキャパシティ、すなわちシステム設計と利用可能なハードウェアから達成可能な最大スループットを持つ。より現実的な目標は、キャパシティの上限までは線形の関係が続き、その後はサチュレーション（飽和）する状態だ。そこでは追加のリクエストは失敗するが、スループットを損なうことはない。

すべてのシステムには何らかの限界があることを覚えておく価値がある。幸運にもその限界が十分に大きく、「無限大」と近似して差し支えない場合もあるが、限界は常に存在する。文書化されたキャパシティ上限がないシステムにも限界は存在する。ただ、それが何であるかを教えてくれていないだけだ。

しかし現実はさらに残酷だ。慎重な設計とチューニングがなければ、ほとんどのシステムは上記のグラフよりもはるかに悪い振る舞いをする。キャパシティに達した後、追加のリクエストは何らかの形でシステムに過負荷をかけ、有用なスループットにつながらないまま貴重なリソースを消費し、結果として次のような振る舞いになる。

あるいは、さらにひどいケースでは次のようになる。

高いリクエストレートを受け取りながら、キャパシティをはるかに下回るスループットしか出せないこの状態を表す言葉はいくつかある。どの言葉を使うかは障害モードの詳細に依存することが多いが、私はこの領域を広く指す言葉として輻輳崩壊（congestion collapse）という用語を使うようにしている。この用語がネットワークという特定の文脈以外で広く使われているかどうかは定かではないが、たいていは容易に理解してもらえると感じている。

具体的なシステムで輻輳崩壊を解決する方法は、詳細や固有の問題に大きく依存するが、しばしば繰り返し現れる一般的なパターンがいくつか存在する。

競合とアドミッション制御

システムが高負荷下でパフォーマンスを落とす最も一般的な理由は、何らかの共有リソースをめぐる競合（コンテンション）だ。この文脈では、複数のプロセスがあるリソースを利用しようとし、その相互作用によるオーバーヘッドのために並行性を高めることでそのリソースの総実効スループットが低下する、あらゆる状況を指すものとする。この種の競合によってパフォーマンスが低下しているシステムの状態を、しばしばスラッシングと呼ぶ。

多くのリソースが競合の影響を受けるが、よくある例をいくつか挙げよう。

• 物理CPUの数をはるかに上回る数のプロセスを実行している場合、コンテキストスイッチやスケジューラのオーバーヘッドが大幅に増加し、スループットは低下する。
• キャッシュ（例えばデータベースのインメモリディスクキャッシュ）がk個の同時リクエスト分の関連データをキャッシュできる程度の大きさである場合、kを超える同時リクエストを実行しようとすると、キャッシュが異なるリクエストのデータ間でスラッシングを起こしてヒット率が急落するため、パフォーマンスは急速に低下する。
• 多くの楽観的同時実行制御システム — 多くのロックフリーアルゴリズムを含む — は高負荷下で著しく劣化し、最悪の場合、競合するトランザクションのためにどのクライアントも処理を進められなくなる状態に陥る。各クライアントが多大な作業をしているにもかかわらず誰も前進できないというこの最悪の障害状態を、ライブロックと呼ぶ。

競合を解消するための基本戦略は、過度な競合を引き起こさないレベルまで意図的に同時実行数を制限することだ。大まかに言えば、入力リクエストを保持するリクエストキューと、空きキャパシティがある場合にのみリクエストがキューを離れて処理を開始することを許可するアドミッションコントローラを追加することで、これを実現できる。「アドミッション制御」1という用語は、ほぼこの意味で一部のデータベースや通信システムで使われているが、私はこの広いパターンに当てはまるあらゆる手法を一般化してそう呼ぶようにしている。

アドミッション制御のポリシーはさまざまだ。最も単純なものでは、最大同時実行数について単一の静的な値を算出し、セマフォを使って処理中のリクエストを制限する。対極には、システム内のボトルネックリソースと、入力リクエストごとに必要なリソースの両方をモデル化した、高度なゲーティングエージェントを用いる手法もある。

競合という現象には、少なくとも1つの重要な含意がある。システムが何らかのクリティカルなリソースでキャパシティの限界に達している場合、同時実行数を増やしてもスループットの向上にはつながらず、むしろ低下させる可能性が高いということだ。最悪の場合、ボトルネックでないリソースにキャパシティを追加することが、かえって限られたリソースでの競合を増大させ、パフォーマンスを低下させることさえある。具体的には、アプリケーションがデータベースでボトルネックになっている場合、同時実行プロセス数を増やすとデータベースをさらに追い詰め、状況を改善するどころか全体のスループットを低下させてしまうかもしれない。

キューは空か満杯かのどちらかだ

適切なアドミッション制御があれば、競合を抑え、どんなリクエストレートでも内部スループットを高く保つことができる。しかし、問題はそれで終わりではない。入力リクエストのレートが最大スループットを恒常的に上回る場合、それらのリクエストはデフォルトではリクエストキューに際限なく蓄積されていく。

この状況についていくつか観察してみよう。

• ここでのスループットはキューの長さとは無関係だ。キューが短くても長くても（空にならない限り）、メッセージを取り出すレートも処理するレートも同じである。この事実は重要だ。キューはピーク時のキャパシティを増やすことはできない。
• キューが伸びるにつれて、全体のレイテンシも増大する。キューにN件のメッセージがある場合、それらを処理するのにN/Y秒かかり、FIFO動作を仮定すれば、リクエストがキューの左端から右端へ到達するのにも同じくN/Y秒かかる。
• キューが伸び続けると、最終的に次のうち1つ以上が起こる。
  • キューが設定された最大サイズに達し、メッセージをドロップせざるを得なくなる。
  • キューに最大サイズが設定されていない場合、サーバー上の利用可能なストレージ空間（通常はディスクやメモリ）を使い果たしてしまう。
  • レイテンシが上昇するにつれて、最終的には当該サービスの上流にあるクライアントがタイムアウトし、たとえ内部的には最終的に成功する可能性があったとしても、リクエストを失敗として扱い始める。

多くのシステムでは、最初に現れる症状である — 設定されたキューサイズ上限によるリクエストドロップ — が、過負荷時に実際にエラーを観測する最初の箇所となる。こうなると、キューサイズを増やすことで目先の問題を解決したくなるが、問題が真のキャパシティ問題、すなわち総スループットがリクエストレートを下回っている状態である限り、そうしても健全性は回復しない。キューはピーク時のキャパシティを増やすことはできないのだ。

代わりに3つ目の問題、すなわち高レイテンシによるタイムアウトに直面した場合、システム内にタイムアウト時間を過ぎても留まっているリクエストは「すでに失敗した」ものであり、それ以上時間を費やす価値はない、ということに気づくかもしれない。そこで、そうしたリクエストにこれ以上労力をかけないように、リクエストキュー内部やデキュー時に明示的なチェックを追加することができる。例えば次のようなロジックを書くことになるだろう。

request = queue.pop()
if time.time() - request.arrival_time >= REQUEST_LATENCY_BUDGET:
  return_error(request, RequestTimedOut()
else:
  process(request)

このようなチェックは、適切に行えば状況をある程度改善できる。平均的にキューのデキュー率をエンキュー率に合わせることで、キューの増大を止めることができるからだ。

しかし、このチェックもキューをある一定のサイズより小さくすることはできない。キューがリクエストの通過にREQUEST_LATENCY_BUDGETかかる大きさになった時点で、ドレインは止まるからだ。リクエストレートが高いままであれば、キューはちょうどそのサイズ付近で推移し、処理するすべてのリクエストに余計なレイテンシが上乗せされることになる。最良の場合でも、良好なスループットは得られるものの、REQUEST_LATENCY_BUDGET分のレイテンシが余分にかかる。最悪の場合、十分な余裕を持たせておらず、結局リクエストはタイムアウトしてしまう。

このようなシステムはスタンディングキューを抱えていると言う。健全なシステムでは、キューは一時的なスパイクを吸収するために使われ、すぐに空になるものだが、ここでは定常状態で持続する大きなキューが存在し、望ましくないレイテンシをもたらしている。

このセクションからの2つの要点は、私が皆さんに持ち帰ってほしい最も重要なことだ。

• キューはバースト的な負荷を時間的に分散させるのには役立つが、全体としてのピークスループットを高めることはできない。
• 負荷下で持続的なスタンディングキューが蓄積される場合、キューは何の利益ももたらさずにレイテンシを追加しているだけであり、その量は破滅的なほど大きくなる可能性がある。

うまくいく方法

最終的に、恒常的にキャパシティを超えており、かつキャパシティを追加できない、あるいは追加したくない場合、解決策は1つしかない。何とかして仕事量を減らすことだ。

私はこの目標に向けて、関連する2つの戦略を考えることが多い。

• クライアントに何らかの形でリクエストを減らすよう求め、入力されるリクエスト負荷を下げる。
• リクエストの一部を処理しないことを選び、可能な限り安価にそれらを破棄して、残りのリクエストを正常に処理するためのリソースを確保する。

これらの戦略の一方または両方をバックプレッシャーと呼ぶ。いずれの場合も、ある意味で入力される仕事に対して「押し返す」ことで、クライアントにこちらのキャパシティ上限を認識させている。前者では明示的に速度を落とすよう求め、後者ではエラーの返却やリクエストのドロップによって、クライアント側で何らかの対処を強いることになる。

可用性やユーザー体験を気にかけるサービス設計者・運用者としては、このように問題をユーザー側に押し返すことは直感に反するように感じられるかもしれない。失敗を認めるように、あるいは責任を放棄するように感じられるからだ。誰も正当なリクエストを意図的に破棄したいとは思わない。しかし、レジリエントなシステムには必然的に何らかの形のバックプレッシャーが必要となる。その理由はいくつかある。

• 前述の通り、すべてのシステムには何らかの限界がある。その限界に直面したとき、何が起こるかについて意図的な判断を下し、できる限り意図的かつグレースフルに振る舞いたいからだ。
• より重要なのは、バックプレッシャーがクローズドループシステムを作り出すことだ。通常は健全なシステムが過負荷になっている場合、その直接的な原因は誰かが過剰なトラフィックを送ってきていることにある。問題を送り手側に押し返すことで、問題とその発生源を近づけ、実際に解決できる可能性を生み出すことができる。

フロー制御

システムとクライアントプロトコルやそれを利用するクライアントを共同で設計できる場合、受信側が送信側に対して安全あるいは許容可能なトラフィックレートがどれくらいかを直接シグナルする、フロー制御メカニズムという形でバックプレッシャーを組み込むことができる場合がある。

ほとんどの低レベルな通信プリミティブ（例えばTCPソケットやUNIXパイプ）は、ストリーム内で送信済みだが未処理のデータ量を制限することで、何らかのフロー制御を実装している。したがって、プロトコルが主に単一あるいは少数のそうしたストリーム上で通信を行う場合、基盤となるレイヤーから基本的なフロー制御を「継承」できることがある。

ロードシェディング

フロー制御メカニズムを利用できない場合や、クライアントがそれを尊重しない場合、残された選択肢はロードシェディングだ。すなわち、リクエストの一部を選び、可能な限り早い段階で破棄する（文字通り忘れ去ることを意味する場合もあれば、十分に安価であればエラーを返すことを意味する場合もある）。そうすることでリソースを解放し、キューを空にして、残りのリクエストを正常に処理できるようにする。

ロードシェディングはレート制限と関連している。レート制限ではユーザーごとの入力リクエスト数を制限し、上限を超えた場合にエラーを返す。一般に、私が見るところ両者の違いは、「レート制限」はシステム全体のキャパシティにかかわらず常に有効で強制されるユーザーごとの上限を示し、「ロードシェディング」はシステム全体が何らかのキャパシティ上限に達したか近づいたときに発動するメカニズムを特に指すということだ。実際には、多くの文脈でキャパシティ超過の一般的な原因の1つは単一の暴走ユーザーであり、両者は密接に関連し、しばしば重なる問題を解決することになる。

負荷を遮断するためにどのリクエストをドロップするかを選択する戦略は数多くある。よくあるものをいくつか挙げよう。

• ランダムドロップ
  • これは実装がシンプルで安価だ。入力リクエストを一切パースすることなく、複数のフロントエンドコンポーネント間の協調もなしに実現できる可能性がある。文脈によっては「公平」と見なされることもある
• クライアントティアリング
  • 無料ティアと有料ティアがある場合、無料リクエストを優先的にドロップできる。これはさまざまな形で一般化でき、極端な例ではリクエスト自体がキャパシティに対する入札を含むスポット市場のようなものまで考えられる。ティアリングは、一部のユーザーが契約上一定のサービスレベルを保証されている一方で、他のユーザーはそうでないといった、明示的なSLAを持つシステムで特にうまく機能する。
• リクエストティアリング
  • 代わりにリクエストの種別に基づいて優先順位をつけ、時間的制約が比較的緩い、あるいは後でリトライしやすいリクエストを優先的にドロップすることもできる。例えばStripeでは、顧客への課金リクエストは過去の支払いの取得や一覧表示といったリクエストよりもはるかにクリティカルと見なされていた。APIサービスが過剰な負荷にさらされた場合、前者を優先し、後者の一部を意図的にドロップしていた。
• フェアな配分
  • 一様なランダムドロップは、すべてのリクエストが等しい確率でドロップされるという意味で公平だ。しかし、これはリクエストを大量に送るインセンティブも生み出してしまう。あるユーザーが全入力リクエストの80%を占めている場合、そのユーザーはスループットの80%を得ることになるからだ。したがって、よりニュアンスのある「公平さ」の定義に従ってキャパシティを割り当てることが理にかなう場合もある。例えば、リクエスト単位ではなくクライアント単位で利用可能なキャパシティを均等に割り当てるといった方法だ。
  • 実際には、これは追加の協調を必要とし実装が難しい場合もあるため、ロードシェダーの前に発動するユーザーごとのレート制限を実装することで十分なことが多く、同様の目的を達成できる。

バトルショート

ロードシェディングやレート制限が適切に機能するためには、システムが致命的に過負荷になる前の、まだ健全で正常に動作している段階で発動しなければならない。しかし、システムがまだ健全であるなら、通常は少数の追加的なリクエストであればまだ処理できるはずであり、したがってロードシェダーは、仮に通していれば成功したはずのリクエストの一部を必然的に拒否あるいはドロップすることになる。

それは飲み込みがたい現実かもしれない。誰も意図的にリクエストをドロップしたいとは思わないからだ。しかし、通常はそれが正しい選択である。システムを過負荷状態に陥らせるよりも、制御された形で意図的なタイミングでリクエストをドロップする方が、たいていは良い結果をもたらす。

しかし、一部のクリティカルなシステムでは、障害のコストがあまりにも高いため、状況によっては、あえて意図的にリクエストをドロップしたりサブシステムを無効化したりするよりも、保護機構を意図的に無効にして運に任せる方がよいと判断されることがある。このようなモードに入るスイッチは、戦闘中に一部の軍事装備でヒューズを無効化、すなわち銅の棒で「短絡（ショート）」させる慣行にちなんで「バトルショート」と呼ばれることがある。その論理は、実戦においては、機動能力や反撃能力を失うことの方が、車両の電気サブシステムの過熱や損傷のリスクよりも高いリスクと判断されるという点にある。

キャパシティの追加

この記事の主な目的は、過負荷、すなわち恒常的に何らかのキャパシティ上限に達しているかそれを超えているシステムを理解し、管理するための手法やフレームワークを探求することだ。実際には、システムが日常的に過負荷になっている場合、過負荷状態をよりグレースフルにするための介入を行う代わりに（あるいはそれに加えて）、キャパシティを追加することで問題を解決したいと考えることが多い。最後に、システムのキャパシティ増強についていくつか述べておきたい。

第一に、「キャパシティを追加すること」と「過負荷をグレースフルに処理すること」は、しばしば二者択一の問題ではない。実際のシステムは両方をある程度備えることで恩恵を受ける傾向がある。例えば、キャパシティを追加するためにオートスケーリングを実装しつつ、そのキャパシティがオンラインになるまでの間もグレースフルに振る舞えるようロードシェダーを用いるといったことが考えられる。あるいは、「正当な」負荷を処理するためにキャパシティを確保しつつ、時折ベースラインの10倍もの負荷を送ってくるバグのある、あるいは設計の悪いプロセスに対処するために、依然としてバックプレッシャーやロードシェディングの手法が必要になることもある。

第二に、キャパシティを追加する際には、ボトルネックとなっているリソースを特定し、それをスケールアップすることが重要だということを強調したい。誤ったリソースをスケールアップした場合（例えば、データベースがボトルネックとなっているサービスでアプリケーションのCPUを増やすなど）、かえって問題を悪化させることさえある。その理由は、ここで論じてきた競合やスタンディングキューをめぐるトピックと密接に関連している。すなわち、システムはより小さなシステムがフラクタルに組み合わさって構成されており、個々のサブシステムがそれぞれ異なる微妙な形でこれらの障害モードに陥りやすいからだ。したがって、常に余裕を持たせるまでキャパシティを追加することを目指す場合であっても、キャパシティ超過時にシステムがどのように振る舞うかについてのこれらの教訓を理解しておくことが、しばしば有益となる。

おわりに

「システムはキャパシティの限界あるいはそれを超えたところでどのように振る舞うか」という問いは、入門的なソフトウェアエンジニアリングの資料や初期のシステム設計ではしばしば軽視されるが、私の経験では、大規模な複雑システムに携わる経験そのものを実質的に定義づける問いだ。

個々のシステムについて言えば、そのシステムの詳細やキャパシティ上限は非常に重要だ。しかし同時に、そうした詳細を数段階抽象化して捉えることができれば、多くの共通する傾向やテーマ、そして高レベルでの多くの類似点があることもわかってきた。そして、それらのパターンを本当に内面化し、認識できるようになれば、どの詳細が重要かを特定し、それらを文脈の中に位置づけるための貴重な指針となりうる。

この記事は、この問いをめぐって私の頭の中にあるテーマや概念の全体像を要約し、それらのパターンや傾向を共有可能な形で言語化する試みだ。新しいアプリケーションでこれらの問題に初めて遭遇するエンジニアが、それらを文脈の中に位置づけ、役立つかもしれない先行事例や概念への手がかりを見つける助けになればと願っている。もし響くところがあれば、ぜひ知らせてほしい。