様々な負荷バランスアルゴリズムとJavaコードの実装

224074 ワード
雑多である
転載元:http://www.duzhi.me/article/864.html?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
まず、負荷バランスとは何かを紹介します。
負荷バランスは既存のネットワーク構造上に構築され、安価で効果的な透明性のある方法拡張を提供する。  ネットワークデバイスと  サーバーの帯域幅、増加  スループット、ネットワークのデータ処理能力を強化し、ネットワークの柔軟性と利用性を向上させる。
負荷バランスは、英語名がLoad Balanceであり、その意味は複数の操作ユニットに割り当てて実行することであり、例えばWebなどである。  サーバ、  FTPサーバ、  企業のキーアプリケーションサーバと他のキーミッションサーバなどが共同で仕事を完成します。
 
本論文では、「外部から送られてきた要求を対称構造のあるサーバに均等に割り当てる」という各種アルゴリズムを説明し、Javaコードで各アルゴリズムの具体的な実現を実証します。OK、次は本題に入ります。本題に入る前に、Ipリストをシミュレートするクラスを先に書きます。
  
import java.util.HashMap;

/**
 * @author [email protected]
 * @date    07, 2017
 */

public class IpMap   {
    //     Ip  ，Key  Ip，Value   Ip   
    public static HashMap<String, Integer> serverWeightMap =
            new HashMap<String, Integer>();

    static
    {
        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);
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
 ポーリング(Round Robin)法
ポーリングスケジューリングアルゴリズムの原理は、ユーザからの要求を順番に内部のサーバに割り当て、N（内部サーバ個数）まで1から開始し、ループを再開することである。アルゴリズムの利点は、現在のすべての接続状態を記録する必要がない簡潔さであり、したがって無状態スケジュールである。
そのコードの実現は大体以下の通りです。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author [email protected]
 * @date    07, 2017
 */

class RoundRobin   {
    private static Integer pos = 0;

    public static String getServer()
    {
        //     Map，                
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        //   Ip  List
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<String>();
        keyList.addAll(keySet);

        String server = null;
        synchronized (pos)
        {
            if (pos > keySet.size())
                pos = 0;
            server = keyList.get(pos);
            pos ++;
        }

        return server;
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
 
serverWeight Mapにおけるアドレスリストはダイナミックであり、いつでもマシンのオンライン、オフライン、またはあたごがありますので、同時に発生する可能性がある問題を回避するために、方法内部にローカル変数serverMapを新規作成し、serverMapの内容をスレッドローカルにコピーして、複数のスレッドによる修正を回避します。このように新しい問題が導入される可能性があります。コピー後のserverWeightMapの修正はserverMapに反映されません。つまり、この選択サーバーの過程で、サーバーまたはオフラインサーバーが追加されます。負荷バランスアルゴリズムは分かりません。追加は構いません。サーバーのオフラインやあたごがあれば、存在しないアドレスにアクセスするかもしれません。したがって、サービスの呼び出し端は、serverの選択を再開して呼び出すなど、対応するフォールト処理が必要である。
 
現在ポーリングされている位置変数posについては、サーバが選択した順序を保証するために、同じ時点で一つのスレッドだけがposの値を修正できるようにロックする必要があります。そうでなければ、pos変数が同時に修正されると、サーバが選択した順序性が保証できなくなり、keyList配列が逸脱する可能性もあります。
 
ポーリング法の利点は、転送の絶対的な均衡を求めることにある。
 
ポーリング法の欠点は、転送の絶対的な均衡を要求するためには相当な代価が必要であり、pos変数の修正の相互反発性を保証するためには、ヘビー級の悲観的なロックsynchronizedを導入する必要があり、これにより、このポーリングコードの同時スループットが著しく低下することになるからである。
 
ランダム(Random)法
 システムのランダムアルゴリズムにより、バックエンドサーバのリストサイズの値に基づいて、ランダムに1台のサーバを選択してアクセスする。確率統計理論により、クライアントがサービスを呼び出す回数が増えるにつれて、
実際の効果は、呼び込み量の平均からバックエンドまでのサーバー、すなわちポーリングの結果に近づいてきました。
ランダム法のコード実現は大体以下の通りです。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author [email protected]
 * @date    07, 2017
 */

 class Random   {
    public static String getServer()
    {
        //     Map，                   
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        //   Ip  List   
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<String>();
        keyList.addAll(keySet);

        java.util.Random random = new java.util.Random();
        int randomPos = random.nextInt(keyList.size());

        return keyList.get(randomPos);
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
 全体コードの考え方はポーリング法と一致しています。まずserver Mapを再構築してからserverリストを取得します。serverを選択する場合、RandomのnextInt方法で0~keyList.size()区間のランダム値をとり、サーバリストからランダムに1台のサーバアドレスを取得して返します。確率統計に基づく理論は，スループットが大きいほど，ランダムアルゴリズムの効果はポーリングアルゴリズムの効果に近い。
ソース・アドレス・ハッシュ(hash)法
 ソース・アドレス・ハッシュの思想は、クライアントのIPアドレスを取得し、ハッシュ関数によって計算された数値に基づいて、サーバリストのサイズをモデル化して演算し、結果として、クライアントがサーバにアクセスするシーケンス番号である。ソース・アドレス・ハッシュ法を用いて負荷等化を行い、同じIPアドレスのクライアントは、バックエンド・サーバ・リストが変わらない場合、毎回同じバックエンド・サーバにマッピングしてアクセスする。
ソース・アドレス・ハッシュ・アルゴリズムのコード実装は、概ね以下の通りである。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author [email protected]
 * @date    07, 2017
 */

 class Hash      {
    public static String getServer()
    {
        //     Map，                
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        //   Ip  List
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<String>();
        keyList.addAll(keySet);

        //  Web      HttpServlet getRemoteIp    
        String remoteIp = "127.0.0.1";
        int hashCode = remoteIp.hashCode();
        int serverListSize = keyList.size();
        int serverPos = hashCode % serverListSize;

        return keyList.get(serverPos);
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
前の二つの部分とポーリング法、ランダム法は同じです。違いはルートの選択部分です。クライアントのip、すなわちremoteIpを通じて、そのHash値を取得し、サーバリストのサイズを型取りし、結果として選択されたサーバのサーバリストのインデックス値を取得します。
 
ソース・アドレス・ハッシュ法の利点は、同じクライアントIPアドレスがバックエンドサーバリストが変更されるまで同一のバックエンドサーバにハッシュされることを保証することである。この特性により、サービス消費者とサービスプロバイダとの間に状態のあるセッションを確立することができる。
 
ソース・アドレス・ハッシュアルゴリズムの欠点は、クラスタ内のサーバが非常に安定していない限り、サーバがオンライン、オフラインしない場合、ソース・アドレス・ハッシュ・アルゴリズムによってルーティングされるサーバはサーバがオンライン、オフライン前にルーティングされるサーバである確率が非常に低く、sessionであればsessionが取れない場合、キャッシュであれば、「雪崩」を誘発する可能性があることである。。このような解釈が適切でないなら、私の前の文章のMemCacheを見てもいいです。
重み付けポーリング(Weight Round Robin)法
バックエンドサーバーによっては、マシンの構成と現在のシステムの負荷が異なりますので、それらのストレス耐性も違います。設定が高く、負荷が低いマシンに、より高い重み付けを配置して、より多くの処理をさせてください。低い負荷の高い機器を構成し、より低い重みを割り当て、そのシステム負荷を低減し、重み付けポーリングはこの問題をうまく処理し、要求順序を後端に重みで配分する。重み付けポーリング法のコード実現は大体以下の通りである。
import java.util.*;

/**
 * @author [email protected]
 * @date    07, 2017
 */
class WeightRoundRobin   {
    private static Integer pos;

    public static String getServer()
    {
        //     Map，                
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        //   Ip  List
        Set<String> keySet = serverMap.keySet();
        Iterator<String> iterator = keySet.iterator();

        List<String> serverList = new ArrayList<String>();
        while (iterator.hasNext())
        {
            String server = iterator.next();
            int weight = serverMap.get(server);
            for (int i = 0; i < weight; i++)
                serverList.add(server);
        }

        String server = null;
        synchronized (pos)
        {
            if (pos > keySet.size())
                pos = 0;
            server = serverList.get(pos);
            pos ++;
        }

        return server;
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
 ポーリング法と同様に、サーバアドレスを取得する前に重み計算コードが追加されただけで、重みの大きさに応じてアドレスをサーバアドレスリストに繰り返し追加すると、重みが大きくなり、サーバがラウンド毎に獲得する要求数が多くなる。
加重ランダム(Weight Random)法
 重み付けポーリング法と同様に、重み付け乱数法もバックエンドマシンの構成に応じて、システムの負荷には異なる重みが割り当てられる。異なるのは、順序ではなく、重みに従ってバックエンドサーバをランダムに要求することである。
import java.util.*;

/**
 * @author [email protected]
 * @date    07, 2017
 */

 class WeightRandom   {
    public static String getServer()
    {
        //     Map，                
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        //   Ip  List
        Set<String> keySet = serverMap.keySet();
        Iterator<String> iterator = keySet.iterator();

        List<String> serverList = new ArrayList<String>();
        while (iterator.hasNext())
        {
            String server = iterator.next();
            int weight = serverMap.get(server);
            for (int i = 0; i < weight; i++)
                serverList.add(server);
        }

        java.util.Random random = new java.util.Random();
        int randomPos = random.nextInt(serverList.size());

        return serverList.get(randomPos);
    }
}
     
     
     
     

      
      
      
      

       
       
       
       Java
このコードはランダム法と重み付けポーリング法の組み合わせに相当しています。よく分かります。説明しません。
最小接続数(Least Connection)法
最小接続数アルゴリズムは比較的に柔軟でインテリジェントです。バックエンドサーバの構成が違っていますので、要求の処理が速くて遅くなります。バックエンドサーバの現在の接続状況によって、動的に選択されます。
接続数が一番少ないサーバを滞積させて、現在の要求を処理して、バックエンドサービスの利用効率をできるだけ高めて、合理的にサーバーごとに分割することに責任を負います。
前のいくつかの方法は工夫を凝らしてサービス消費者の要求回数の配分のバランスを実現します。もちろん、これは間違いないです。バックエンドの複数のサーバーに平均的に仕事量を配分して、サーバーの利用率を最大限に高めることができますが、実際の状況は本当ですか？実際には要求回数のバランスが負荷のバランスを表していますか？これは考えるべき問題です。
上の問題は、もう一つの観点から言えば、後端サーバの視点からシステムの負荷を観察し、発信元を要求して観察するのではない。最小接続数法はこのようなものです。
最小接続数アルゴリズムは比較的に柔軟でインテリジェントです。バックエンドサーバの構成が違っていますので、要求の処理が早くて遅くなります。バックエンドサーバの現在の接続状況に基づいて、現在の滞積接続数が一番少ないサーバを動的に選択して、現在の要求を処理します。バックエンドサーバの利用効率をできるだけ高めます。負荷を各マシンに合理的に分岐します。最小接続数の設計サーバ接続数の集約と感知により、設計と実現がより煩雑であるため、ここではその実現を言わない。
「NGINXが実現した理由について説明します。
blog.cdn.net
javaがcalbackを実現
パスワードなしSSH SCP