いくつかの単純な負荷分散アルゴリズムとそのJavaコード実装

1. 負荷分散とは何ですか?

負荷分散（英語名は Load Balance）とは、複数のサーバーを対称的に構成したサーバーセットを指します。各サーバーは同等のステータスを持ち、他のサーバーの支援なしに独立して外部にサービスを提供できます。何らかの負荷分散技術により、外部から送信されたリクエストは対称構造のサーバーに均等に分散され、リクエストを受信したサーバーはクライアントのリクエストに独立して応答します。ロードバランシングにより、クライアント要求をサーバーアレイに均等に分散できるため、重要なデータへの高速アクセスが可能になり、大量の同時アクセスサービスの問題が解決されます。このクラスターテクノロジにより、最小限の投資でメインフレームに近いパフォーマンスを実現できます。

[[262208]]

負荷分散はソフトウェア負荷分散とハードウェア負荷分散に分かれます。前者はAlibabaの張文松博士が開発したLVSに代表され、後者はF5などのバランシングサーバーです。もちろん、これは言及しただけで、本質ではありません。

この記事では、「外部から送られてきたリクエストを対称構造で均等にサーバーに分配する」ためのさまざまなアルゴリズムについて説明し、各アルゴリズムの具体的な実装を Java コードで示します。では、本題に入りましょう。本題に入る前に、IP リストをシミュレートするクラスを記述してみましょう。

パブリッククラス IpMap
 {
    // ルーティングする IP のリスト。キーはIP を表し、値は IP の重みを表します。
公共 静的ハッシュマップ<文字列、整数> serverWeightMap =
            新しい HashMap<String, Integer >(); 
 
静的 
    {
        serverWeightMap.put( "192.168.1.100" , 1);
        serverWeightMap.put( "192.168.1.101" , 1);
        // 重みは4
        serverWeightMap.put( "192.168.1.102" , 4);
        serverWeightMap.put( "192.168.1.103" , 1);
        serverWeightMap.put( "192.168.1.104" , 1);
        // 重みは3
        serverWeightMap.put( "192.168.1.105" , 3);
        serverWeightMap.put( "192.168.1.106" , 1);
        // 重みは2
        serverWeightMap.put( "192.168.1.107" , 2);
        serverWeightMap.put( "192.168.1.108" , 1);
        serverWeightMap.put( "192.168.1.109" , 1);
        serverWeightMap.put( "192.168.1.110" , 1);
    }
 }

02. ラウンドロビン

ポーリング方式はラウンドロビン方式で、そのコード実装はおおよそ次のようになります。

パブリッククラス RoundRobin
 {
    プライベートスタティック 整数pos = 0; 
 
公共 静的文字列 getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しい HashMap<String, Integer >();
        serverMap.putAll(IpMap.serverWeightMap); 
 
        // IPアドレスリストを取得
<文字列>を設定します。keySet = serverMap.keySet();
        ArrayList<String> keyList = 新しいArrayList<String>();
        キーリストにすべてを追加します(キーセット)。 
 
        文字列サーバー = null ;
        同期（正）
        {
            (位置 >キーセットのサイズ())の場合
                位置 = 0;
            サーバー = keyList.get(pos);
            位置++;
        } 
 
サーバーを返す。
    }
 }

serverWeightMap のアドレスリストは動的であるため、マシンはいつでもオンラインになったり、オフラインになったり、クラッシュしたりする可能性があります。したがって、同時実行の問題を回避するために、メソッド内にローカル変数 serverMap が作成されます。serverMap の内容は、複数のスレッドによって変更されないように、スレッドにローカルにコピーされるようになりました。これにより、新たな問題が発生する可能性があります。レプリケーション後、serverWeightMap への変更は serverMap に反映されません。つまり、このサーバー選択ラウンドでは、負荷分散アルゴリズムは新しいサーバーまたはオフラインサーバーを認識しません。新しいアドレスを追加しても問題ありません。サーバーがオフラインまたはクラッシュしている場合は、存在しないアドレスにアクセスする可能性があります。したがって、サービス呼び出し元は、サーバーの選択と呼び出しの再開など、対応するフォールトトレラント処理を備えている必要があります。

現在のポーリング位置変数 pos については、サーバーの選択順序を保証するために、操作中にロックして、同時に 1 つのスレッドだけが pos の値を変更できるようにする必要があります。そうしないと、pos 変数が同時に変更された場合、サーバーの選択順序が保証されず、keyList 配列が境界を越える可能性もあります。

ラウンドロビン方式の利点は、リクエスト転送の絶対的なバランスを実現しようとすることです。

ポーリング方式の欠点は、リクエスト転送の絶対的なバランスを実現するために、かなりの代償を払わなければならないことです。POS 変数の変更の相互排他性を保証するために、重い悲観的ロック同期を導入する必要があり、これにより、このポーリングコードの同時スループットが大幅に低下します。

03. ランダム法

システムのランダム機能により、バックエンドサーバーリストのサイズに基づいて、バックエンドサーバーの 1 つがアクセス用にランダムに選択されます。確率統計の理論から、呼び出し回数が増えるにつれて、実際の効果は各バックエンドサーバーにトラフィックを均等に分散することにどんどん近づいていること、つまりポーリングの効果であることがわかります。

ランダムメソッドのコード実装は次のとおりです。

パブリッククラス Random
 {
公共 静的文字列 getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しい HashMap<String, Integer >();
        serverMap.putAll(IpMap.serverWeightMap); 
 
        // IPアドレスリストを取得
<文字列>を設定します。keySet = serverMap.keySet();
        ArrayList<String> keyList = 新しいArrayList<String>();
        キーリストにすべてを追加します(キーセット)。 
 
        java.util.Random ランダム = new java.util.Random();
 int randomPos = random.nextInt(keyList.size ( )); 
 
 keyList.get(randomPos);を返します。
    }
 }

全体的なコードのアイデアはポーリングメソッドと一致しています。まず serverMap を再構築し、次にサーバーリストを取得します。サーバーを選択する際は、Random の nextInt メソッドを使用して 0 ～ keyList.size() の範囲でランダムな値を取得し、サーバーリストからサーバーアドレスをランダムに取得して返します。確率統計の理論に基づくと、スループットが大きいほど、ランダムアルゴリズムの効果がポーリングアルゴリズムの効果に近くなります。

04. 送信元アドレスハッシュ方式

ソースアドレスハッシュの考え方は、クライアントがアクセスした IP アドレス値を取得し、ハッシュ関数を通じて値を計算し、この値を使用してサーバーリストのサイズに対してモジュロ演算を実行することです。結果は、アクセスされるサーバーのシリアル番号です。送信元アドレスハッシュアルゴリズムのコード実装は次のとおりです。

パブリッククラスHash
 {
公共 静的文字列 getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しい HashMap<String, Integer >();
        serverMap.putAll(IpMap.serverWeightMap); 
 
        // IPアドレスリストを取得
<文字列>を設定します。keySet = serverMap.keySet();
        ArrayList<String> keyList = 新しいArrayList<String>();
        キーリストにすべてを追加します(キーセット)。 
 
        // Webアプリケーションでは、HttpServletのgetRemoteIpメソッドを通じて取得できます
        文字列 remoteIp = "127.0.0.1" ;
 intハッシュコード = remoteIp.hashCode();
 int serverListSize = keyList.size ( );
 int serverPos = ハッシュコード % serverListSize; 
 
 keyList.get(serverPos);を返します。
    }
 }

最初の2つの部分はポーリング方式とランダム方式と同じなので、詳細は説明しません。違いはルーティングの選択部分にあります。クライアントの IP、つまり remoteIp を通じて、そのハッシュ値を取得し、サーバーリストのサイズを法として計算します。その結果が、サーバーリスト内の選択されたサーバーのインデックス値になります。

ソースアドレスハッシュ方式の利点は、バックエンドサーバーリストが変更されるまで、同じクライアント IP アドレスが同じバックエンドサーバーにハッシュされることが保証されることです。この機能に基づいて、サービスコンシューマーとサービスプロバイダーの間でステートフルセッションを確立できます。

ソースアドレスハッシュアルゴリズムの欠点は、クラスター内のサーバーが非常に安定していて、基本的にオンラインまたはオフラインにならない限り、サーバーがオンラインまたはオフラインになると、ソースアドレスハッシュアルゴリズムによってルーティングされたサーバーが、サーバーがオンラインまたはオフラインになる前にルーティングされたサーバーである確率が非常に低くなることです。セッションの場合はセッションが取得できず、キャッシュの場合は「雪崩」が発生する可能性があります。

05. 加重ラウンドロビン

サーバーによってマシン構成や現在のシステム負荷が異なる場合があり、ストレス耐性も異なります。構成が高く負荷が低いマシンには、より多くのリクエストを処理できるように高い重みが割り当てられ、構成が低く負荷が高いマシンには、システム負荷を軽減するために低い重みが割り当てられます。加重ラウンドロビン方式はこの問題を適切に処理し、重みに応じてリクエストの順序をバックエンドに分散します。加重ラウンドロビン方式のコード実装は次のとおりです。

パブリッククラス WeightRoundRobin
 {
    プライベートスタティック 整数pos; 
 
公共 静的文字列 getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しい HashMap<String, Integer >();
        serverMap.putAll(IpMap.serverWeightMap); 
 
        // IPアドレスリストを取得
<文字列>を設定します。keySet = serverMap.keySet();
        イテレータ<String> iterator = keySet.iterator(); 
 
        リスト<文字列> serverList = 新しい ArrayList<文字列>();
        (イテレータ.hasNext()) の間
        {
            文字列サーバー = iterator.next ();
 int重み = serverMap.get(server);
 ( int i = 0; i < 重み; i++)の場合
                serverList.add (サーバー);
        } 
 
        文字列サーバー = null ;
        同期（正）
        {
            if (pos > serverList.size ())
                位置 = 0;
            サーバー = serverList.get(pos);
            位置++;
        } 
 
サーバーを返す。
    }
 }

ポーリング方式と似ていますが、サーバーアドレスを取得する前に重み計算コードが追加されます。重みに応じて、アドレスはサーバーアドレスリストに繰り返し追加されます。重みが大きいほど、サーバーが各ラウンドで受信するリクエストが多くなります。

06. 加重ランダム法

加重ラウンドロビン方式と同様に、加重ランダム方式でも、バックエンドサーバーのさまざまな構成と負荷条件に基づいて異なる重みが構成されます。違いは、順序ではなく重みに基づいてサーバーをランダムに選択することです。重み付けランダム法のコード実装は次のとおりです。

パブリッククラス WeightRandom
 {
公共 静的文字列 getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しい HashMap<String, Integer >();
        serverMap.putAll(IpMap.serverWeightMap); 
 
        // IPアドレスリストを取得
<文字列>を設定します。keySet = serverMap.keySet();
        イテレータ<String> iterator = keySet.iterator(); 
 
        リスト<文字列> serverList = 新しい ArrayList<文字列>();
        (イテレータ.hasNext()) の間
        {
            文字列サーバー = iterator.next ();
 int重み = serverMap.get(server);
 ( int i = 0; i < 重み; i++)の場合
                serverList.add (サーバー);
        } 
 
        java.util.Random ランダム = new java.util.Random();
 int randomPos = random.nextInt(serverList.size ( )); 
 
 serverList.get(randomPos);を返します。
    }
 }

このコードはランダム方式と重み付けポーリング方式を組み合わせたものと同じです。わかりやすいので説明は省きます。

07. 最小接続法

これまでの方法では、サービスコンシューマーのリクエスト時間のバランスの取れた分散を実現するために最善を尽くしてきました。もちろん、これは正しいです。複数のバックエンドサーバーのワークロードを均等に分散し、サーバーの使用率を最大化できます。しかし、これは本当にそうでしょうか。実際のところ、リクエスト時間のバランスは本当に負荷のバランスを表すことができるのでしょうか。これは考える価値のある質問です。

上記の問題を別の観点から見ると、リクエストの開始者ではなく、バックエンドサーバーの観点からシステム負荷を観察することを意味します。最小接続数方式はこのカテゴリに属します。

最小接続数アルゴリズムは、より柔軟でインテリジェントです。バックエンドサーバーの構成が異なるため、リクエストの処理速度は速くなったり遅くなったりする場合があります。バックエンドサーバーの現在の接続状態に基づいて、現在のリクエストを処理するために接続バックログが最も少ないサーバーを動的に選択し、バックエンドサーバーの利用効率を最大化し、各マシンに負荷を合理的に分散します。最小接続数は、サーバー接続数の集計と認識を伴うため、設計と実装がかなり面倒です。そのため、ここでは実装については説明しません。

<<: 人工知能がスマート交通の発展に与える影響

>>: 快手AIハッカソンは「AIの名の下に」みんなの幸福を向上させるために終了しました