大型分布式网站之负载均衡算法

空余时间深入研究下关于大型分布式网站架构设计和实践的电子书，大家可在网上下载看看，稍后我上传到我的博客里，下面是部分心得关于负载均衡算法的，纯手动写的哦，希望对大家有帮助吧。

负载均衡算法的种类很多，常见的负载均衡算法包含轮询法，随机法，源地址哈希法，加权轮询法，加权随机法，最小链接发等，应根据具体的使用场景选取对应的算法。

 1.轮询(Round Robin)法

将请求按顺序轮流分配到后端服务器上，它均衡的对待后端每一台服务器，而不关心服务器实际的链接数和当前的系统负载。

这里通过初始化一个serverWeightMap的map变量来表示服务器地址和权重的映射，以此来模拟轮询算法的实现，其中设置的权重值在后面加权算法中会使用到，此处不做描述，

该变量初始化如下：

 serverWeightMap = new HashMap<String,Intager>();

 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);

其中IP地址为192.168.1.102的权重为4，192.168.1.105的权重为3，192.168.1.107的权重为2

通过该地址列表，实现的轮询算法的部分关键代码如下：

public static String testRoundRobin(){

 //重新创建一个map,避免出现由于服务器上线和下线导致并发

 Map<String,Integer> serverMap = new HashMap<String,Integer> ();

 serverMap.putAll(serverWeightMap);

 // 取得IP地址list

 Set<String> keySet = serverMap.keySet(); //IP地址字符串

 ArrayList<String>keyList = new ArrayList<String>(); // IP集合字符串转为数组

 keyList.addAll(keySet);

 String server = null;

 synchronized(pos){

  if(pos >= keySet.size()){ // 好像是取得服务器台数 pos自增 >= 11

    pos = 0;

  }

  server = keyList.get(pos); // 获取该台服务器

  pos++;

 }

return server;

}

由于serverWeightMap中的服务器地址日常中是动态的也就是说随时上下架的，比如宕机等，为了避免可能出现的并发问题如数组越界，通过新建方法的局部变量serverMap，先将域变量复制到现在本地，避免被多个线程修改，轮询算法的位置变量pos是为了保证服务器选择的顺序性，需要在操作的时候加上synchronized锁，使得在同一时刻只有一个线程能够修改pos值，否则pos变量被并发修改则无法保证服务器选择的顺序性，

使用轮询策略希望做到请求转移的绝对均衡，付出的代价也蛮大的：为了pos保证变量修改的互斥性，需要引入重量级的锁synchronized会导致该段轮询代码的并发吞吐量会明显的下降，从而导致性能的降低。

 

2.随机法(Random)

通过系统随机函数，根据后端服务器列表的大小值来随机选取其中一台进行访问，根据概率统计论得知：随着调用量的增大，其实际效果越来越接近平均分配流量到每一台后端服务器也可达到轮询的效果

随机算法的代码：

 public static String testRandom(){

     //重新创建一个map,避免出现由于服务器上线和下线导致并发

     Map<String,Integer> serverMap = new HashMap<String,Integer> ();

     serverMap.putAll(serverWeightMap);

      // 取得IP地址list

      Set<String> keySet = serverMap.keySet(); //IP地址字符串

      ArrayList<String>keyList = new ArrayList<String>(); // IP集合字符串转为数组

      keyList.addAll(keySet);

      Random random = new Random();

      int randomPos = random.nextInt(keyLIst.size()); // 这里统计服务器数11

      String server = keyList.get(randomPos );

      return server;

 }

 通过Random的nextInt方法，取到在0~keyList.size()区间的一个随机值，从而从服务器列表中随机获取一台服务器地址，进行返回。基于概率论的统计，吞吐量越大，随机算法的效果越接近于轮询算法的效果。这种方法不会付出太大的性能代价。

 

3.源地址哈希法(Hash)

源地址哈希的意思是获取客户端访问的IP地址值，通过哈希函数计算得到一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是访问的服务器的序号。采用哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会被映射到同一台后端服务器进行访问。

源地址哈希算法实现代码：

public static String testConsumerHash(String remoteip){

     //重新创建一个map,避免出现由于服务器上线和下线导致并发

     Map<String,Integer> serverMap = new HashMap<String,Integer> ();

     serverMap.putAll(serverWeightMap);

      // 取得IP地址list

      Set<String> keySet = serverMap.keySet(); //IP地址字符串

      ArrayList<String>keyList = new ArrayList<String>(); // IP集合字符串转为数组

      keyList.addAll(keySet);

      int hashCode = remoteip.hashCode();

      int serverListSize = keyList.size();

      int serverPos = hashCode % serverListSize;

      return keyList.get(serverPos);

}

通过参数传入的客户端remoteip参数，取得它的哈希值，对服务器列表的大小取模，结果便是选用的服务器在服务器列表中的索引值。该算法保证了相同的客户端IP地址将会被哈希到同一台后端服务器，直到后端服务器列表变更。根据这特性可以在服务器消费者与服务提供者之间的session会话。

 

 4.加权轮询法(Weight Round Robin)

不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此他们的抗压能力也不尽相同。给配置高负载低的机器配置更高的权重，让其处理更多的请求，而配置低负载高的机器则给其分配较低的权重降低其负载，加权轮询能很好的处理这一问题并将请求顺序按照权重分配到后端

加权轮询代码：

public static String testWeightRoundRobin(){

     //重新创建一个map,避免出现由于服务器上线和下线导致并发

     Map<String,Integer> serverMap = new HashMap<String,Integer> ();

     serverMap.putAll(serverWeightMap);

      // 取得IP地址list

      Set<String> keySet = serverMap.keySet(); //IP地址字符串

      Iterator<Strign>it = keySet.iterator();

      List<String>keyList = new ArrayList<String>(); // IP集合字符串转为数组

      while(it.hasNext()){

          String server = it.next();

           Integer weight = serverMap.get(server);

           for(int i=0;i<weight;i++){

              serverList.add(server);

           }

       }

      String server = null;

      synchronized(pos){

          if(pos >= keySet.size()){ // 好像是取得服务器台数 pos自增 >= 11

              pos = 0;

         }

          server = keyList.get(pos); // 获取该台服务器

          pos++;

     }

      return server;

}

与轮询算法相似，只是在获取服务器地址之前增加一段权重计算的代码，根据权重的大小将地址重复的增加到服务器列表中，权重越大该服务器每轮获得的请求数量越多。

 

5.加权随机法(Weight Random)

与加权轮询法类似，加权随机法也是根据后端服务器不同的配置和负载情况，配置不同的权重，不同的是它是安装权重来随机选取服务器的，尔非顺序。

加权随机实现的代码：

public static String testWeightRandom(){

 //重新创建一个map,避免出现由于服务器上线和下线导致并发

     Map<String,Integer> serverMap = new HashMap<String,Integer> ();

     serverMap.putAll(serverWeightMap);

      // 取得IP地址list

      Set<String> keySet = serverMap.keySet(); //IP地址字符串

      Iterator<String> it = keySet.iterator();

      List<String>serverList = new ArrayList<String>(); // IP集合字符串转为数组

      while(it.hasNext()){

          String server = it.next();

           Integer weight = serverMap.get(server);

           for(int i=0;i<weight;i++){

              serverList.add(server);

           }

       }

      Random random = new Random();

      int randomPos = random.nextInt(keyLIst.size()); // 这里统计服务器数11

      String server = keyList.get(randomPos );

      return server;

}

 

6.最小连接数法(Least Connections)

最小连接数法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的那一台服务器来处理当前的请求，尽可能地提高后端服务器的利用效率，将负载合理地分流到每一台服务器。由于最少连接数涉及服务器连接数的汇总和感知，涉及与实现比较复杂繁琐，所以也请大家慎重选择。

如有问题，请多多指点，谢谢！

---------------完------------