Dropboxの自社ロードバランシングサービス Robinhood

 (dropbox.tech)
9 ポイント 投稿者 GN⁺ 2024-11-01 | 1件のコメント | WhatsAppで共有
  • RobinhoodはDropboxの社内ロードバランシングサービスで、2020年に導入された
  • サーバー間の内部トラフィックをルーティングし、サービス負荷をバランスよく分散する
  • Robinhood以前は、Dropboxの大半のサービスがバックエンド間で不均衡な負荷分散に悩まされていた
  • ハードウェアの違いと従来のロードバランシングアルゴリズムの限界により、過負荷インスタンスに起因する信頼性の問題が発生していた
  • これを解決するためにサービスフリートを過剰にプロビジョニングする必要があり、その結果ハードウェアコストが増加していた

Robinhoodの新機能

  • PID（Proportional-Integral-Derivative）コントローラーを活用することで、負荷の不均衡をより速く効果的に管理できるようになった
  • これにより、インフラの信頼性向上と大幅なハードウェアコスト削減につながった
  • 最新のインテリジェント機能を動かすAIワークロードの増加により、GPUリソース需要の効果的な管理はこれまで以上に重要になっている

Dropboxにおけるロードバランシングの課題

  • Dropboxのサービスディスカバリーシステムは、世界中の複数のデータセンターにまたがる数十万台のホストまでスケール可能である
  • 一部のDropboxサービスは数百万のクライアントを抱えているが、各クライアントがすべてのサーバーインスタンスに接続できるようにはできない
    • それは、サーバーに過大なメモリ負荷をかけ、サーバー再起動時にはTLSハンドシェイクによってサーバーが過負荷になる可能性があるためである
  • その代わりに、サービスディスカバリーシステムを使って各クライアントに接続先となるサーバーのサブセットを提供する
  • クライアントが利用できる最善のロードバランシング戦略は、サービスディスカバリーシステムから提供されたアドレス一覧に対してラウンドロビンを行うことである
    • しかし、この方法では各サーバーインスタンスの負荷が大きく偏る可能性がある
    • サブセットサイズを増やすことは簡単な緩和策ではあるが、不均衡を完全には解消できず、サービスオーナーに別のパラメーターを増やすだけである
  • より根本的な問題は、各サーバーに同じ数のリクエストを送っても、基盤となるハードウェアがサーバーごとに異なり得ることにある
    • つまり、異なるハードウェアクラスでは、リクエストが消費するリソース量も異なる
  • 核心は、クライアントがサーバー負荷を可視化できないことである
  • 過去には、サーバーがレスポンスヘッダーに負荷情報を付与することでこの問題の解決を試みた
    • クライアントはアドレスサブセットの中から最も負荷の低いエンドポイントを選択し、自らロードバランシングを行える
    • 結果は有望だったが、なおいくつかの欠点があった
      • 特別な負荷ヘッダーに対応するため、サーバーとクライアントの双方でコード変更が必要となり、グローバル展開が難しかった
      • 結果は良好だったが、十分に良いとは言えなかった

Robinhood構築の決定

  • 2019年にRobinhoodの構築を正式に決定した
  • この新しいサービスは既存の社内サービスディスカバリーシステムの上に構築され、サーバーから負荷情報を収集してルーティング情報に付加する
  • RobinhoodはEnvoyのEndpoint Discovery Serviceを活用し、負荷情報をエンドポイント重みに統合することで、クライアントが重み付きラウンドロビンを実行できるようにしている
  • gRPCコミュニティがEnvoy xDSプロトコルを採用しつつあったため、RobinhoodはEnvoyとgRPCクライアントの両方と互換性がある
  • 当時、Dropboxの要件を満たす既存のロードバランシングソリューションが存在しなかったため、新しいサービスを構築することにした

Robinhoodの成果

  • 本番環境で数年間使用した結果、有望な成果を示した
  • 一部の大規模サービスではフリート規模を25%削減することに成功し、毎年大幅なハードウェアコストを削減した
  • 過度に利用されるプロセスが減り、信頼性も向上した

Robinhoodのアーキテクチャ

  • 各データセンターにRobinhoodインスタンスが配置され、ロードバランシングサービス、プロキシ、ルーティングデータベースの3つの部分で構成される

ロードバランシングサービス（LBS）

  • Robinhoodの中核
  • 負荷情報を収集し、エンドポイント重みを含むルーティング情報を生成する役割を担う
  • 複数のインスタンスがサービスのルーティング情報を同時に更新するため、内部shard managerを使用して各サービスのプライマリワーカーを割り当てる
  • 各サービスは独立しているため、サービス単位でLBSを分割し、水平方向にスケールできる

プロキシ

  • サービスの負荷情報を、データセンター内の対応するLBSパーティションへルーティングする役割を担う
  • プロキシを使うことで、LBSプロセスに直接接続される数も減らせる
    • プロキシがなければ、すべてのLBSプロセスがインフラ内のすべてのノードに接続しなければならない
    • その代わり、LBSプロセスはプロキシにのみ接続すればよいため、LBSのメモリ負荷は大幅に軽減される
  • プロキシは同一データセンター内のノードにのみ接続するため、水平方向にスケール可能である
  • このパターンは、過剰なTLS接続の受信からサービスを保護するため、インフラの多くの部分で使われている

ルーティングデータベース

  • ホスト名、IPアドレス、LBSが生成した重みなど、サービスに関するルーティング情報を保存するZooKeeper/etcdベースのデータベース
  • ZooKeeperとetcdはノード/キーの変更をリアルタイムですべてのウォッチャーに通知でき、Dropboxの読み取り中心のサービスディスカバリーのユースケースに非常に適している
  • ZooKeeper/etcdが保証する結果整合性は、サービスディスカバリーにも十分である

ロードバランシングサービスを詳しく見る

  • ロードバランシングの目標は、すべてのノードの利用率を平均利用率と等しくすることである
  • PIDコントローラーを使って、各ノードの利用率を平均利用率とほぼ同じに保つ
  • LBSは各ノードごとにPIDコントローラーを作成し、平均利用率を設定値として使用する
  • LBSはPIDコントローラーの出力をエンドポイント重みへのデルタとして使い、サービス内のすべてのエンドポイント間で重みを正規化する
  • 新しいノードが平均利用率へ収束するまでには数回の調整が必要だが、PIDコントローラーはロードバランシングに非常に効果的である

LBSの動作シナリオ

  • LBSは、ノード再起動から負荷レポート欠落に至るまで、ロードバランシングに影響し得るさまざまなシナリオに対処できるよう設計されている
  • 最適なパフォーマンスを維持するため、LBSはこうした例外ケースに対応するいくつかの戦略を実装している

LBS起動

  • LBSは負荷情報とPIDコントローラーの状態をメモリに保持する
  • LBSの再起動中は、すぐに重み更新を開始せず、負荷レポートが到着するまで少し待機する
  • PIDコントローラーの重みについては、LBSはルーティングデータベースからエンドポイント重みを読み取って復元する

コールドスタートノード

  • サービスフリートには新しいノードが頻繁に参加するため、Thundering Herd問題を防ぐことが重要である
  • 新しいノードの初期利用率は通常0であるため、LBSは新規ノードの重みを低いエンドポイント重みに設定し、PIDコントローラーがノードを平均利用率まで引き上げるようにする

欠落した負荷レポート

  • 分散システム環境では障害は一般的である
  • ネットワーク輻輳やハードウェア障害により、一部ノードの負荷レポートが遅延したり到着しなかったりすることがある
  • LBSは重み更新時にこうしたノードをスキップするため、それらのノードのエンドポイント重みは変更されない
  • しかし、大量の負荷レポートが欠落すると平均利用率の計算が不正確になる可能性がある
  • 安全のため、LBSはこの場合、重み更新ステップ自体を完全にスキップする

利用率メトリクス

  • CPU利用率はDropboxで最も広く使われているロードバランシングメトリクスである
  • CPUがボトルネックにならないサービスでは、進行中リクエスト数が有効な代替指標となる
  • LBSはCPUおよび/または進行中リクエストに基づくロードバランシングをサポートするよう実装されている

制限事項

  • PIDコントローラーは、ノードの利用率を目標値（平均利用率）に近づけるためのフィードバックループを構成する
  • トラフィックが非常に少ないサービスや、分単位で測定される非常に高レイテンシなリクエストのようにフィードバックがほとんどない場合、ロードバランシングは効果的に機能しない
  • 高レイテンシなリクエストを持つサービスは非同期であるべきである

データセンター間ルーティング

  • LBSインスタンスはデータセンター内のロードバランシングを処理する
  • データセンター間ルーティングには別の考慮事項がある
    • たとえば、リクエストの往復時間を減らすため、最も近いデータセンターへリクエストをルーティングしたい
  • そのために、対象データセンター間のトラフィック分割を定義するローカリティ構成を導入した

ロードバランサーの性能評価

  • ロードバランシング性能は max/avg 比率で測定する
    • サービスオーナーが CPU ベースのロードバランシングを選択した場合、maxCPU/avgCPU を性能指標として使用する
    • サービスオーナーは一般にノード間の最大使用率を基準にサービスをプロビジョニングしており、ロードバランシングの主な目的はフリートサイズを削減することだからである
  • PID コントローラによるロードバランシング戦略は max/avg 比率を 1 に近く保つことができる

ロードバランシング性能評価グラフ

  • Envoy プロキシクラスターのうち最大のクラスターにおける max/avg CPU および p95/avg CPU を示すグラフ
    • PID コントローラベースのロードバランシングを有効化した後、両方のメトリクスが 1 に近づいて低下した
    • max/avg 比率は 1.26 から 1.01 に低下し、20% の改善を示した
  • ノードごとの CPU 使用率のパーセンタイル分析を示すグラフ
    • PID コントローラベースのロードバランシングを有効化した後、max、p95、avg、p5 がほぼ 1 本の線に統合された
  • データベースフロントエンドクラスターのうち最大のクラスターにおける max/avg CPU および p95/avg CPU を示す別のグラフ
    • PID コントローラベースのロードバランシングを有効化した後、両方のメトリクスが 1 に近づいて低下した
    • max/avg 比率は 1.4 から 1.05 に低下し、25% の改善を示した
  • ノードごとの CPU 使用率のパーセンタイル分析を示す別のグラフ
    • PID コントローラベースのロードバランシングを有効化した後、max、p95、avg、p5 が再びほぼ 1 本の線に統合された

Config Aggregator を構築した理由

  • Robinhood はサービスオーナーが選択できる複数のオプションを提供し、変更を動的に適用することもできる
  • サービスオーナーはコードベース内のサービスディレクトリでサービス向けの Robinhood 設定を作成・更新する
  • これらの設定は構成管理サービスに保存され、Robinhood 設定の変更をリアルタイムで受け取るための便利なライブラリとなっている
  • しかし、いくつかの問題により、コードベースから Robinhood のメガ設定を定期的にビルドしてプッシュすることはできない
    • 設定プッシュによって変更が導入された場合、ロールバックボタンを押すのは危険である
      • 最後のプッシュ以降にどれだけ多くの他サービスが変更されたか分からないためである
    • Robinhood を所有するチームは各メガ設定プッシュについても責任を負う
      • つまり Robinhood チームがすべての設定変更プッシュに関与しなければならず、これはエンジニアリング時間の無駄である
      • ほとんどのインシデントはサービスオーナーが解決できるためである
    • 潜在的なリスクを最小化するため、各プッシュは複数のデータセンターへ展開するのに数時間かかる
  • これらの問題を解決するため、別の小規模サービスである Config Aggregator を構築した

Config Aggregator

  • Config Aggregator はすべてのサービス別設定を収集し、LBS が使用するメガ設定を構成する
  • Config Aggregator はサービス別設定を監視し、変更をリアルタイムでメガ設定へ反映する
  • Config Aggregator は、サービスの Robinhood 設定が誤って削除されるのを防ぐための tombstone 機能も提供する
    • サービスオーナーが Robinhood 設定からサービスを削除する変更をプッシュすると、Config Aggregator はサービス項目を即座に削除する代わりに tombstone としてマークする
    • 実際の削除は数日後に行われる
    • この機能は、Robinhood 設定とその他のルーティング設定（例: Envoy 設定）との間で異なるプッシュ周期により発生し得る競合状態も解決する
  • 構成管理サービスの欠点は、現時点ではバージョン管理されていないことである
  • LBS 設定を既知の正常な状態に戻す必要がある場合に備え、メガ設定を定期的にバックアップしている

Migration 戦略

  • ロードバランシング戦略を一度に切り替えるのは危険になり得る
  • そのため Robinhood では、サービスに対して複数のロードバランシング戦略を設定できるようにしている
  • Dropbox にはパーセントベースの機能ゲートがあるため、2 つのロードバランシング戦略で生成された重みの加重和をエンドポイント重みとして使用する混合戦略をクライアントに実装した
  • これにより、すべてのクライアントがエンドポイントに対して同じ重み割り当てを見ながら、新しいロードバランシング戦略へ段階的に移行できる

学んだこと

  • Robinhood を設計・実装する過程で、何が有効で何がそうでないかについていくつかの重要な教訓を得た
  • 単純さを優先し、クライアント変更を最小限に抑え、最初から移行を計画することで、LBS の開発と展開を簡素化し、高コストな落とし穴を避けることができた

設定は可能な限り単純であるべき

  • Robinhood はサービスオーナーが設定できる多くのオプションを導入した
  • しかし、ほとんどの場合に必要なのは提供されるデフォルト設定である
  • 優れたシンプルなデフォルト設定（あるいは、さらに良いのは設定不要であること）は、膨大なエンジニアリング時間を節約できる

クライアント変更も単純に保つこと

  • 内部クライアントへの変更のロールアウトには数か月かかることがある
    • ほとんどのデプロイは毎週プッシュされるが、多くのデプロイは月に 1 回、あるいは何年もまったくデプロイされない
  • LBS に移せる変更が多いほど望ましい
    • たとえば初期段階でクライアント設計に weighted round robin を使うと決め、それ以降は変更していない
    • これにより進行速度が大幅に向上した
  • 変更の大半を LBS に限定すれば、安定性リスクも低減される
    • 必要であれば LBS の変更は数分以内にロールバックできるためである

移行はプロジェクト設計段階で計画すべき

  • 移行には膨大なエンジニアリング時間がかかる
  • 考慮すべき安定性リスクもある
  • 楽しい作業ではないが重要な仕事である
  • 新しいサービスを設計する際には、既存のユースケースを新サービスへ円滑に移行する方法をできるだけ早く検討すべきである
  • サービスオーナーに求めることが多いほど、移行は悪夢になる
    • とりわけ基本的なインフラコンポーネントではその傾向が強い
  • Robinhood の移行プロセスは最初から十分に設計されていなかったため、想定以上に多くの時間をプロセスの再実装と設定の再設計に費やした
  • 移行に必要なエンジニアリング時間は成功の重要指標であるべきだ

Robinhood の効果

  • 本番環境で約 1 年運用した後、Robinhood の最新イテレーションが Dropbox の長年のロードバランシング課題を効果的に解決したと言える
  • 中核である PID コントローラアルゴリズムは有望な結果を示し、最大規模のサービスで大幅な性能向上を示した
  • Dropbox 規模のロードバランシングサービスを設計・運用するうえで貴重な知見を得た

脚注

  1. N、M、s をそれぞれサーバー数、クライアント数、アドレス部分集合のサイズとする。サーバーに接続するクライアント数は二項分布 B(M, s/n) の標本に従う。前述のとおり、クライアントはサービスディスカバリが提供するアドレス集合に対して単純な round robin を行う。したがって、各クライアントがおおむね同量のリクエストを送るなら、サーバー側の負荷分布は二項分布に近くなる。

  2. 既存のサービスディスカバリシステムを拡張して gRPC xDS プロトコル（A27）をサポートする。このブログ執筆時点では、gRPC クライアントはコントロールプレーンのエンドポイント重みに対する weighted round robin をサポートしていないため、最短期限優先スケジューリングに基づくカスタム weighted round robin セレクタを実装した。

  3. サービスがときどき性能低下した I/O によって停滞するという興味深い事例が発生した。このような状況では、そのノードの CPU は低いままとなり、LBS は CPU を平均まで引き上げようとしてノードの重みを増やし、デッドスパイラルにつながる。対策として、CPU と進行中リクエスト数の最大値を負荷指標として用い、サービスのバランスを取るようにした。

GN⁺の意見

  • Robinhoodは、Dropboxのロードバランシング課題を効果的に解決した優れたサービスに見える。PIDコントローラーを活用している点が印象的だ
  • 非常に大規模なグローバルインフラにおいて、ロードバランシングがどれほど難しい課題かをよく示している事例だ。ハードウェアの違い、不均衡な負荷分散、ネットワーク輻輳など、考慮すべき点が多い
  • すべてのコンポーネントが有機的にうまく連携して動作するよう設計することが重要に見える。LBS、プロキシ、ルーティングDBは分離されているが、リアルタイムで緊密に相互作用している
  • ロードバランシング性能を定量的に評価し、改善点を可視化したグラフが印象的だ。特に max/avg 比を1に近く維持することが、フリートサイズ最適化に重要であることをよく示している
  • Config Aggregatorを導入してサービスごとの構成を分離したのもよいアイデアに見える。サービスオーナーが自分の変更を独立して管理できるようになる
  • tombstoneのような安全装置を用意している点も細やかだ。ミスによる構成削除を防ぐことが重要だ
  • マイグレーション戦略に関する教訓も有用に見える。最初からマイグレーションを考慮しないと、後で多くの時間を費やすことになる
  • 全体としてRobinhoodは、Dropbox規模のロードバランシングに向けた体系的で洗練されたソリューションに見える。ほかの大規模インフラを持つ企業にとっても参考になる事例だ

類似のソリューション:

  • AWSのElastic Load Balancing(ELB)やGoogle CloudのCloud Load Balancingも、大規模ロードバランシング向けのマネージドサービスを提供している
  • Kubernetesの場合、自前のロードバランサー(kube-proxy)を持っているが、IstioやLinkerdのようなサービスメッシュソリューションを活用すれば、より強力なロードバランシングとトラフィック管理機能を利用できる
  • NetflixのZuulやLyftのEnvoyも、プロキシベースのロードバランシング機能を提供している

導入時の検討事項:

  • 既存インフラおよびサービスとの互換性確認が必要だ。マイグレーションが必要な場合は戦略を立てるべきだ
  • 性能と安定性への影響を十分にテストし、監視しなければならない。ロードバランシングロジックのバグは致命的になり得る
  • チームの能力を考慮して、導入範囲と速度を決めるべきだ。性急に全体へ適用するより、段階的導入のほうがよい
  • 長期的には、継続的に最適化と改善を進めていく努力が必要だ。ロードバランシングアルゴリズムを状況に合わせてチューニングし、ボトルネックを取り除くといった活動が役立つだろう

関連記事

1件のコメント

 
kbumsik 2024-11-01

ソフトウェアの分野でPIDコントローラの話を聞くとは思いませんでした（笑）