Alibaba の軽量オープンソース Web サーバー Tengine 負荷分散アルゴリズム

序文

Alibaba レイヤー 7 トラフィック エントリ アクセス レイヤー (アプリケーション ゲートウェイ) シナリオでは、Nginx の公式 Smooth Weighted Round-Robin (SWRR) 負荷分散アルゴリズムは、その機能を十分に発揮できなくなりました。 Tengine は、新しい負荷分散アルゴリズムである Virtual Node Smooth Weighted Round-Robin (VNSWRR) を実装することで、SWRR アルゴリズムの欠陥を巧みに解決するだけでなく、Nginx の公式 SWRR アルゴリズムと比較して QPS 処理能力を約 60% 向上させます。

質問

アクセス層 Tengine は、自社開発の動的アップストリーム モジュールを通じて動的なサービス検出を実現します。つまり、実行時にバックエンド アプリケーション マシンの拡張と縮小、重み調整、ヘルス チェックを動的に認識します。同時に、この機能は多くのことを行うことができます。たとえば、ユーザーはバックエンド アプリケーションで特定のマシンの重みを調整して、オンラインでの実際のトラフィックの迂回ストレス テストの目的を達成できます。ただし、これらの操作は、Nginx のネイティブ SWRR アルゴリズムでは取り返しのつかない事態を引き起こす可能性があります。

• アクセス層 (アプリケーション ゲートウェイ) のシナリオでは、Nginx の負荷分散アルゴリズム SWRR により、重みが高いマシンの QPS が瞬時に急上昇します。たとえば、上図で App2-host-A マシンの重みを 2 に調整すると、特定の瞬間にトラフィックがこのマシンに転送されます。
• Nginx の SWRR アルゴリズムの処理時間の複雑さは O(N) です。大規模なバックエンド シナリオでは、Nginx の処理能力は直線的に減少します。

要約すると、アクセス層 Tengine の負荷分散転送戦略の変革とパフォーマンスの最適化が間近に迫っています。

ネイティブSWRRアルゴリズムの分析

事例を紹介する前に、Nginx の負荷分散アルゴリズム SWRR 転送戦略と特徴について簡単に紹介します。

SWRR アルゴリズムの正式名称は、Smooth Weighted Round-Robin Balancing です。名前が示すように、このアルゴリズムには、他の加重ラウンドロビン (WRR) アルゴリズムに比べて滑らかな機能がさらに追加されています。

簡単な例を使ってアルゴリズムを説明しましょう。

重みがそれぞれ 5、1、1 である 3 台のマシン A、B、C があるとします。ここで、配列 s はマシン リストを表し、n はマシンの数を表し、各マシンの cw は 0 に初期化され、ew はマシンの重みに初期化され、tw はこの選択ラウンドのすべてのマシンの ew の合計を表し、best はこのラウンドで選択されたマシンを表します。簡単に説明すると、マシン リスト内で cw 値が最大のマシンが選択されるたびに、選択されたマシンの cw が tw から減算され、次回選択される可能性が低くなります。簡単な擬似コードの説明は次のとおりです。

ベスト = NULL ;
 tw = 0;
 (i = random() % n; i != i || falg; i = (i + 1) % n)の場合{
フラグ = 0;
 s[i].cw += s[i].ew;
 tw += s[i].ew;
ベスト == NULL || s[i].cw > ベスト->cw) の場合 {
 ベスト = &s[i];
 }
 }
ベスト->cw -= tw;
最高のリターン;

リクエスト番号が選択される前の重み値 選択されたサーバーが選択された後の重み値

0 {5,1,1} A {-2,1,1}

1 {3,2,2} A {-4,2,2}

2 {1,3,3} B {1,-4,3}

3 {6,-3,4} A {-1,-3,4}

4 {4,-2,5} C {4,-2,-2}

5 {9,-1,-1} A {2,-1,-1}

6 {7,0,0} A {0,0,0}

SWRRアルゴリズムによって選択される順序は次のとおりです: { A、A、B、A、C、A、A }

通常のWRRアルゴリズムによって選択される順序は次のようになります: { C, B, A, A, A, A, A }

一般的な WRR アルゴリズムと比較すると、SWRR には滑らかさと分散という特性があります。

権力の強化が引き起こした流血事件

上記の説明から、SWRR アルゴリズムは完璧に思えますが、いくつかのシナリオではまだ欠陥があります。実際のケースでその欠陥を確認してみましょう。

ある朝、交通指令員が私の職場に駆けつけました。彼はとても緊張しているように見えたので、何かがおかしいに違いないと思いました。予想通り、「中央計算機室のマシンの重みを 1 から 2 に調整すると、アクセス層の Tengine がこの重みの比率に従ってトラフィックを転送しないのはなぜか？」という疑問が浮かびます。その際に増加したマシンの QPS の変化傾向は次の図のようになります。

注: 濃い青色の曲線は、重みが増加したマシンの QPS の変化を表し、薄い緑色の曲線は、クラスター内の単一のマシンの平均 QPS を表します。

このトラフィックトレンドの変化グラフを見たとき、私も戸惑いましたが、幸いなことにグラフとデータがあるので、まずはこのグラフのいくつかの特徴的な数字を分析することができます。一部のデータはセンシティブなので、ここでは詳細なデータ分析は展開しません。現象と原因を直接説明します。

重み付けの高いマシンに分散されたトラフィックは、基本的に、その時点でのアプリケーション コンピュータ ルームの総トラフィックの 1/2 でした。しばらくすると、マシンのトラフィックは予想された重み付けの比率に戻りました。その理由は、アクセス レイヤーの Tengine はバックエンド マシン情報の変更を動的に認識して有効にするのに対し、公式の Nginx SWRR アルゴリズム戦略では、まず現在のマシン リスト内で重みが最も大きいマシンを選択してトラフィックを転送するためです。これにより、バックエンド マシンの重みの変化を感知したアクセス レイヤー Tengine は、最初のリクエストを重みが増加したマシンに転送します。

規模が大きくなるとパフォーマンスが劇的に低下する

以下は、アップストリームに 2000 のバックエンドが構成されたリバース プロキシ シナリオでの Nginx ストレス テストの機能ヒート マップです。 ngx_http_upstream_get_peer 関数の CPU 消費は、39% にも上ります。その理由は、マシンを選択するための SWRR アルゴリズムの時間計算量が O(N) であるためです (N はバックエンド マシンの数を表します)。つまり、この転送に対応するバックエンド マシンを見つけるために、各リクエストで約 2,000 サイクルを実行する必要があります。

• ストレステスト環境

CPU モデル: Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz

ストレステストツール: ./wrk -t25 -d5m -c500 'http://ip/t2000'

 Tengine コア構成: 2 つのワーカー プロセス、ストレス ソース-- 長い接続 --> Tengine / Nginx -- 短い接続 --> バックエンドを構成します。  

次に、アップストリームに構成されているサーバーの数を制御変数として実験を行い、さまざまなシナリオにおける Nginx の QPS 処理能力と応答時間 RT の変化を観察します。図から、バックエンドアップストリームのサーバー数が500台増加すると、NginxのQPS処理能力が約10%低下し、応答RTが約1ms増加することがわかります。

以上の分析から、SWRR アルゴリズムには上記 2 つの欠陥があることが基本的に確認されました。では、それらの解決に取り掛かりましょう。

改良されたVNSWRRアルゴリズム

古典的なWRRアルゴリズム（乱数実装など）はO(1)の時間計算量を達成できますが、重みの増加におけるSWRRアルゴリズムの選択欠陥を回避することもできます。ただし、一部のシナリオ (トラフィックが少ない場合など) では、特にトラフィックが突然急増し、不確実性が多すぎるシナリオでは、バックエンドでトラフィックの不均一が発生する可能性があります。そこで、SWRRアルゴリズムの滑らかさと分散特性を持ち、時間計算量がO(1)であるアルゴリズムがあるかどうか考えました。そこで、Virtual Node Smooth Weighted Round-Robin (VNSWRR) アルゴリズムが存在します。

このアルゴリズムを説明する例を次に示します。3 台のマシン A、B、C の重みはそれぞれ 1、2、3 で、N はバックエンド マシンの数を表し、TW はバックエンド マシンの合計重みを表します。

アルゴリズムの要点

• 仮想ノードの初期化の順序は、初期化リスト内のマシンが十分なハッシュを配布できるように、SWRR アルゴリズムに従って厳密に選択されます。
• 集中的なコンピューティングの集中を避けるために、仮想ノードは実行時にバッチで初期化されます。仮想ノードの各バッチが使い果たされると、次の仮想ノード リストのバッチが初期化され、そのたびに min(n, max) 個の仮想ノードのみが初期化されます。

アルゴリズムの説明

• Tengine プログラムが起動するか、実行中にバックエンド マシンの情報の変更を感知すると、TW 仮想ノードが構築され、N ノードのみが初めて初期化されます (注: TW はバックエンド マシンの重みの合計を表し、N はバックエンド マシンの数を表します)。
• 各プロセスは、ポーリングのランダムな開始点を設定します。たとえば、上の図のステップ 1 に対応するリストの開始点は B を指します。
• リクエストが到着すると、設定されたランダム開始点 B から仮想ノード リストがポーリングされます。ポーリングが初期化された仮想ノード配列の末尾に到達した場合 (上図のステップ 2 の赤い矢印で示されているように)、2 番目のバッチの仮想ノードが初期化されます (上図のステップ 2 の赤いノードで示されているように)。すべての仮想ノードが初期化されると、それ以上の初期化作業は実行されません (上図のステップ 3 の状態で示されているように)。

このソリューションは、アルゴリズムの時間計算量を O(N) から O(1) に最適化するだけでなく、重み増加シナリオによって発生する問題も回避します。次の図に示すように、バックエンド マシンの重みを 1 から 2 に調整すると、QPS は予想される比率までスムーズに増加します。

アルゴリズムの効果の比較

同じストレス テスト環境 (wrk ストレス テスト ツール、同時実行数 500、長い接続シナリオ、アップストリーム構成 2000 サーバー) では、Nginx 公式 SWRR アルゴリズムの CPU 消費量は 39% にも上ります (ngx_http_upstream_get_peer 関数)。同じ条件下では、VNSWRR アルゴリズムの CPU 消費量はわずか約 0.27% です (ngx_http_upstream_get_ VNSWRR 関数)。明らかに、SWRR の CPU 消費量は桁違いに高くなります。

上記のストレステスト環境において、Nginx の公式 SWRR アルゴリズムと改良された VNSWRR アルゴリズムの QPS 処理能力は次の図のようになります。VNSWRR の QPS 処理能力は、SWRR アルゴリズムと比較して約 60% 向上しています。

実験してみましょう。アップストリームに設定されているサーバーの数が変わったときに、VNSWRR アルゴリズムと SWRR アルゴリズムを比較して、Nginx の QPS 処理能力と応答時間 RT の変化を観察します。

図から、SWRRアルゴリズムでは、上流のサーバー数が500台増加すると、NginxのQPS処理能力が約10％低下し、応答RTが約1ms増加することがわかります。ただし、VNSWRRアルゴリズムでは、TengineのQPS処理能力とRTは基本的にあまり変化しません。

要約する

この高トラフィックのシナリオでは、Nginx のいくつかの問題が露呈します。諺にあるように、ビジネスとテクノロジーは互いに補完し合います。ビジネスは新しいテクノロジーの誕生を促進し、新しいテクノロジーは新しいビジネスの創出を可能にします。 VNSWRR アルゴリズムは、SWRR アルゴリズムの滑らかさと分散特性を備え、その欠陥を回避します。同時に、新しいアルゴリズムでは、時間計算量も O(N) から O(1) に調整されます。大規模なシナリオでは、VNSWRR の QPS 処理能力は、Nginx の公式 SWRR アルゴリズムと比較して約 60% 向上します。

この記事の著者は、Wang Fakang (ニックネーム: Yisong)、GitHub ID @wangfakang、Tengine オープンソース プロジェクトのメンテナー、Alibaba の技術専門家であり、Alibaba の WEB 統合アクセス レイヤーの開発とメンテナンスを担当しています。