複数の負荷分散アルゴリズムとそのJavaコード実装

まず、負荷分散とは何かを紹介します（百科事典より）

負荷分散は既存のネットワーク構造に基づいて構築され、ネットワークデバイスとサーバーの帯域幅を拡張し、スループットを向上させ、ネットワークデータ処理機能を強化し、ネットワークの柔軟性と可用性を向上させるための、安価で効果的かつ透過的な方法を提供します。

負荷分散（英語名は Load Balance）とは、Web サーバー、FTP サーバー、企業の主要なアプリケーションサーバー、その他のミッションクリティカルなサーバーなどの複数の操作ユニットに実行を分散し、作業タスクをまとめて完了することを意味します。

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

java.util.HashMap をインポートします。

/** * @author ashang.peng @aliyun .com * @date 2017年2月7日 */

パブリッククラスIpMap {
    // ルーティングする IP のリスト。キーは IP を表し、値は IP の重みを表します。
    パブリック静的HashMap<String, Integer> 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 );
    }
}

ラウンドロビン

ポーリングスケジューリングアルゴリズムの原理は、ユーザーからの要求を 1 から N (内部サーバーの数) まで順番に内部サーバーに割り当て、その後サイクルを再開することです。このアルゴリズムの利点は、そのシンプルさです。現在のすべての接続のステータスを記録する必要がないため、ステートレススケジューリングになります。

コードの実装はおおよそ次のようになります。

 java.util.ArrayListをインポートします。
java.util.HashMapをインポートします。
java.util.Mapをインポートします。
java.util.Setをインポートします。

/** * @author [email protected] * @date 2017年2月7日 */

クラスラウンドロビン{
    プライベート静的整数 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 変数の変更の相互排他性を保証するために、重い悲観的ロック同期を導入する必要があり、これにより、このポーリングコードの同時スループットが大幅に低下します。

ランダム法

システムのランダムアルゴリズムにより、バックエンドサーバーのリストサイズ値に基づいて、アクセスするサーバーの 1 つがランダムに選択されます。確率統計理論から、クライアントがサーバーを呼び出す回数が増えると、

実際の効果は、ポーリングの結果、バックエンドの各サーバーに呼び出し量が均等に分散されることに近づいています。

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

 java.util.ArrayListをインポートします。
java.util.HashMapをインポートします。
java.util.Mapをインポートします。
java.util.Setをインポートします。

/** * @author [email protected] * @date 2017年2月7日 */

 クラスランダム{
    パブリック静的文字列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() の範囲でランダムな値を取得し、サーバーリストからサーバーアドレスをランダムに取得して返します。確率統計の理論に基づくと、スループットが大きいほど、ランダムアルゴリズムの効果がポーリングアルゴリズムの効果に近くなります。

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

ソースアドレスハッシュの考え方は、クライアントの IP アドレスを取得し、ハッシュ関数を通じて値を計算することです。この値は、サーバーリストのサイズに対してモジュロ演算を実行するために使用されます。結果は、クライアントがアクセスするサーバーのシリアル番号です。負荷分散には送信元アドレスハッシュ方式が使用されます。同じ IP アドレスを持つクライアントの場合、バックエンドサーバーリストが変更されていない場合は、毎回同じバックエンドサーバーにマッピングされてアクセスされます。

送信元アドレスハッシュアルゴリズムのコード実装は次のとおりです。

 java.util.ArrayListをインポートします。
java.util.HashMapをインポートします。
java.util.Mapをインポートします。
java.util.Setをインポートします。

/** * @author [email protected] * @date 2017年2月7日 */

 クラスハッシュ{
    パブリック静的文字列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 アドレスが同じバックエンドサーバーにハッシュされることが保証されることです。この機能に基づいて、サービスコンシューマーとサービスプロバイダーの間でステートフルセッションを確立できます。

ソースアドレスハッシュアルゴリズムの欠点は、クラスター内のサーバーが非常に安定していて、基本的にオンラインまたはオフラインにならない限り、サーバーがオンラインまたはオフラインになると、ソースアドレスハッシュアルゴリズムによってルーティングされたサーバーが、サーバーがオンラインまたはオフラインになる前にルーティングされたサーバーである確率が非常に低くなることです。セッションの場合はセッションが取得できず、キャッシュの場合は「雪崩」が発生する可能性があります。この説明が適切でない場合は、MemCache の非常に詳細な解釈である、一貫性ハッシュアルゴリズムに関する部分を書いた私の以前の記事を読んでください。

加重ラウンドロビン

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

 java.util.*をインポートします。

/** * @author [email protected] * @date 2017年2月7日 */
クラスWeightRoundRobin {
    プライベート静的整数 pos;

    パブリック静的文字列getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しいHashMap< String , Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // IPアドレスリストを取得
        <文字列> keySet = serverMap.keySet()を設定します。
        イテレータ<文字列> iterator = keySet.iterator();

        List< String > serverList =新しいArrayList< String >();
        (イテレータ.hasNext())の間
        {
            文字列サーバー = iterator.next();
            int 重み = serverMap.get(server);
            (int i = 0 ; i < 重み; i++)の場合
                serverList.add(サーバー);
        }

        文字列サーバー = null ;
        同期（正）
        {
            (位置> キーセットのサイズ())
                位置 = 0 ;
            サーバー = serverList.get(pos);
            位置++;
        }

        サーバーを返す。
    }
}

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

加重ランダム法

加重ラウンドロビン方式と同様に、加重ランダム方式でも、バックエンドマシンの構成とシステムの負荷に基づいて異なる重みが割り当てられます。違いは、順序ではなく重みに応じてバックエンドサーバーをランダムに要求することです。

 java.util.*をインポートします。

/** * @author [email protected] * @date 2017年2月7日 */

 クラスWeightRandom {
    パブリック静的文字列getServer()
    {
        // サーバーの起動と停止による同時実行の問題を回避するためにマップを再構築します
        マップ<文字列、整数> serverMap =
                新しいHashMap< String , Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // IPアドレスリストを取得
        <文字列> keySet = serverMap.keySet()を設定します。
        イテレータ<文字列> iterator = keySet.iterator();

        List< String > serverList =新しいArrayList< String >();
        (イテレータ.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);を返します。
    }
}

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

最小接続法

最小接続数アルゴリズムはより柔軟でインテリジェントです。バックエンドサーバーの構成が異なるため、リクエストの処理速度が異なる場合があります。バックエンドサーバーの現在の接続状態に基づいて、現在の接続数を動的に選択します。

バックログ接続数が最も少ないサーバーが現在のリクエストを処理し、バックエンドサービスの利用効率を最大化し、各サーバーにトラフィックを合理的に分散する役割を担います。

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

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

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

「NGINX の実装理由」の説明を添付します。ご覧ください: blog.csdn.net

<<: 2017 年に注目すべき人工知能の 7 つのホットなトレンド

>>: Google がディープラーニングライブラリ TensorFlow Fold をリリース、動的計算グラフをサポート