Twitterは先頃、自社のRPCフレームワークであるFinagleに、マイクロサービスアーキテクチャに決定論的アパーチャアルゴリズム(deterministic aperture algorithm)を使用したクライアントサイドロードバランシング機能を実装した理由の詳細を発表した。さまざまな試験を行った結果、要求の分散が良好であること、接続数を大幅に削減できること、必要なインフラストラクチャが少ないことなどの理由から、同社は決定論的アプローチを採用したのだ。
Twitterはクライアントサイドロードバランシング技術を数年前に採用し、現在はマイクロサービスアーキテクチャで運用している。同社が"決定論的アパーチャ"と呼ぶこの技術は、JVM用のオープンソースプロジェクトであるFinagleのRPCフレームワークの一部となっている。Finagleでは、すべてのクライアントにクライアンサイドロードバランサを組み込んでいる。中央のサーバサイドロードバランサを呼び出す代わりに、すべてのリクエストを中継することなく、目的のサーバに直接送信することにより、インフラストラクチャ層やネットワークのホップ、バンド幅、システムの障害点(points of failure)の低減を実現している。クライアントサイドロードバランシングのアプローチは、他にもBaker StreetやNetflix Ribbonといったプロジェクトが採用しており、YelpやAirbnb、Stripeなどの企業でもマイクロサービスシステムの運用に導入している。
クライアント側でロードバランシングを使用すれば、システム全体にわたって、クライアント内に — 少なくともクライアントあたりひとつの — ロードバランサが分散することになる。従って、トラフィックを均等に分散しようとすると、特に数千台のサーバを抱えるような場合には、処理が複雑になる。この問題に対して、Finagleの決定論的アパーチャアルゴリズムでは、接続するサーバを選択する際に、トラフィック負荷を分散するP2C(Power of Two Random Choice)アプローチと決定論的アプローチを組み合わせて使用している。P2CはMichael Mitzenmacher氏の論文"The power of two choices in randomized load balancing"に基づくストラテジで、ロードバランサがクラスタ内から少数のサーバをランダムに選択して、最も負荷の少ないものにリクエストをルーティングする方法である。
決定論的アパーチャアルゴリズムの動作を説明するために、Twitterでは、クライアントとバックエンドサーバを等間隔のリングとして表現している。
出典: SREcon19 Americas — Aperture: A Non-Cooperative, Client-Side Load Balancing Algorithm
まず最初にロードバランサは、接続対象とするサーバのサブセットを選択する必要がある。これがアパーチャのサイズである。このサブセットは、バランサが接続してリクエストをルートするサーバという意味に過ぎない。上の図に示したように、アパーチャサイズは、サーバ数Nに対して最小1/Nとなる。この値はFinagleの設定で変更が可能である他、フィードバックコントローラを使ってより最適なサイズを求めることができる。
アパーチャサイズが決定すれば、すべてのリクエストがサーバ内に均等に分散される。ただしこれは、必ずしもリクエストを均等にルートするという意味ではない — その方法では、システム全体としては公平でないからだ。つまり、３台のサーバが100パーセントのリクエストを処理する場合、１台が10パーセント、もう１台が60パーセント、残る１台が30パーセントということもあり得る。クラスタにサーバを追加したり、取り除いたりする必要がある時には、アパーチャサイズが変更される場合がある。このアルゴリズムには、クライアント間の簡単なコーディネーションと、システム全体の中断を最小化する処理が実装されている。
出典: SREcon19 Americas — Aperture: A Non-Cooperative, Client-Side Load Balancing Algorithm
決定論的アパーチャアルゴリズムにたどり着く前のTwitterでは、サービスのサブセットをランダムに選択する方法によって、接続数の削減を可能にしていた。しかしこの方法では、リクエストの負荷が均等に分散されないことが分かった。例えば、次の図に示すように、毎秒400リクエストを受信する過密なサーバがある一方で、ごく少数のリクエストのみでアイドル状態のものもある、といった状況があったのだ。
ランダムアパーチャアルゴリズムを実運用で実行した結果
TwitterのRuben Oanta氏はSPEConで、同社のインフラストラクチャでFinagleの決定論的アパーチャアルゴリズムを実行した結果を公表した。まず、リクエストがサーバ間により均等に分散することにより、リソースが効率的に利用できるようになった。次に、目的サーバへの接続数を91パーセント削減することができた。そして最後に、リクエストエラーの減少、99.9パーセントのリクエストに対するレイテンシ低下、約25パーセントのCPU負荷低減、Java GC停止の総数の半減、などが実現された。
ただし、決定論的アパーチャにはいくつかの制限がある。例えば、小規模なクラスタでは、最小アパーチャサイズの関係で、大規模クラスタよりも接続数が多くなることが少なくない。また、キャッシュフラッシュ後などの理由でトラフィックが集中すると、いくつかのサーバアパーチャが他よりも多くのトラフィックを受け取るようになる。
Finagleの導入方法やアパーチャロードバランサに関しては、同プロジェクトのサイトやGitHubリポジトリで確認することが可能だ。