多种负载均衡算法及其Java代码实现

首先给大家介绍下什么是负载均衡(来自百科)

负载均衡 建立在现有网络结构之上,它提供了一种廉价有效透明的方法扩展 网络设备和 服务器的带宽、增加 吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。

负载均衡,英文名称为Load Balance,其意思就是分摊到多个操作单元上进行执行,例如Web 服务器、 FTP服务器、 企业关键应用服务器和其它关键任务服务器等,从而共同完成工作任务。

本文讲述的是”将外部发送来的请求均匀分配到对称结构中的某一台服务器上”的各种算法,并以Java代码演示每种算法的具体实现,OK,下面进入正题,在进入正题前,先写一个类来模拟Ip列表:

import java.util.HashMap;

/**  * @author ashang.peng@aliyun.com  * @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);
    }
}

轮询(Round Robin)法

轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器,从1开始,直到N(内部服务器个数),然后重新开始循环。算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。

其代码实现大致如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**  * @author ashang.peng@aliyun.com  * @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;
    }
}

由于serverWeightMap中的地址列表是动态的,随时可能有机器上线、下线或者宕机,因此为了避免可能出现的并发问题,方法内部要新建局部变量serverMap,现将serverMap中的内容复制到线程本地,以避免被多个线程修改。这样可能会引入新的问题,复制以后serverWeightMap的修改无法反映给serverMap,也就是说这一轮选择服务器的过程中,新增服务器或者下线服务器,负载均衡算法将无法获知。新增无所谓,如果有服务器下线或者宕机,那么可能会访问到不存在的地址。因此,服务调用端需要有相应的容错处理,比如重新发起一次server选择并调用。

对于当前轮询的位置变量pos,为了保证服务器选择的顺序性,需要在操作时对其加锁,使得同一时刻只能有一个线程可以修改pos的值,否则当pos变量被并发修改,则无法保证服务器选择的顺序性,甚至有可能导致keyList数组越界。

轮询法的优点在于:试图做到请求转移的绝对均衡。

轮询法的缺点在于:为了做到请求转移的绝对均衡,必须付出相当大的代价,因为为了保证pos变量修改的互斥性,需要引入重量级的悲观锁synchronized,这将会导致该段轮询代码的并发吞吐量发生明显的下降。

随机(Random)法

通过系统的随机算法,根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。由概率统计理论可以得知,随着客户端调用服务端的次数增多,

其实际效果越来越接近于平均分配调用量到后端的每一台服务器,也就是轮询的结果。

随机法的代码实现大致如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**  * @author ashang.peng@aliyun.com  * @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);
    }
}

整体代码思路和轮询法一致,先重建serverMap,再获取到server列表。在选取server的时候,通过Random的nextInt方法取0~keyList.size()区间的一个随机值,从而从服务器列表中随机获取到一台服务器地址进行返回。基于概率统计的理论,吞吐量越大,随机算法的效果越接近于轮询算法的效果。

源地址哈希(Hash)法

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

源地址哈希算法的代码实现大致如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**  * @author ashang.peng@aliyun.com  * @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);
    }
}

前两部分和轮询法、随机法一样就不说了,差别在于路由选择部分。通过客户端的ip也就是remoteIp,取得它的Hash值,对服务器列表的大小取模,结果便是选用的服务器在服务器列表中的索引值。

源地址哈希法的优点在于:保证了相同客户端IP地址将会被哈希到同一台后端服务器,直到后端服务器列表变更。根据此特性可以在服务消费者与服务提供者之间建立有状态的session会话。

源地址哈希算法的缺点在于:除非集群中服务器的非常稳定,基本不会上下线,否则一旦有服务器上线、下线,那么通过源地址哈希算法路由到的服务器是服务器上线、下线前路由到的服务器的概率非常低,如果是session则取不到session,如果是缓存则可能引发”雪崩”。如果这么解释不适合明白,可以看我之前的一篇文章MemCache超详细解读,一致性Hash算法部分。

加权轮询(Weight Round Robin)法

不同的后端服务器可能机器的配置和当前系统的负载并不相同,因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重,让其处理更多的请;而配置低、负载高的机器,给其分配较低的权重,降低其系统负载,加权轮询能很好地处理这一问题,并将请求顺序且按照权重分配到后端。加权轮询法的代码实现大致如下:

import java.util.*;

/**  * @author ashang.peng@aliyun.com  * @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;
    }
}

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

加权随机(Weight Random)法

与加权轮询法一样,加权随机法也根据后端机器的配置,系统的负载分配不同的权重。不同的是,它是按照权重随机请求后端服务器,而非顺序。

import java.util.*;

/**  * @author ashang.peng@aliyun.com  * @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);
    }
}

这段代码相当于是随机法和加权轮询法的结合,比较好理解,就不解释了。

最小连接数(Least Connections)法

最小连接数算法比较灵活和智能,由于后端服务器的配置不尽相同,对于请求的处理有快有慢,它是根据后端服务器当前的连接情况,动态地选取其中当前

积压连接数最少的一台服务器来处理当前的请求,尽可能地提高后端服务的利用效率,将负责合理地分流到每一台服务器。

前面几种方法费尽心思来实现服务消费者请求次数分配的均衡,当然这么做是没错的,可以为后端的多台服务器平均分配工作量,最大程度地提高服务器的利用率,但是实际情况是否真的如此?实际情况中,请求次数的均衡真的能代表负载的均衡吗?这是一个值得思考的问题。

上面的问题,再换一个角度来说就是:以后端服务器的视角来观察系统的负载,而非请求发起方来观察。最小连接数法便属于此类。

最小连接数算法比较灵活和智能,由于后端服务器的配置不尽相同,对于请求的处理有快有慢,它正是根据后端服务器当前的连接情况,动态地选取其中当前积压连接数最少的一台服务器来处理当前请求,尽可能地提高后端服务器的利用效率,将负载合理地分流到每一台机器。由于最小连接数设计服务器连接数的汇总和感知,设计与实现较为繁琐,此处就不说它的实现了。

来源:51CTO

时间: 2017-08-01

多种负载均衡算法及其Java代码实现的相关文章

基于第四层交换技术的负载均衡

摘 要 本文介绍了第四层交换技术的概念,技术原理以及如何使用第四层交换技术实现远程教育系统中的应用服务器负载均衡. 1 引言 当今世界已经步入信息时代,随着社会的迅速发展以及人们对网络应用需求的不断提高,对网络速度及带宽的要求不断上升.正是在这样的发展形势下,许多高速交换的新技术不断涌现.第二层交换实现局域网内主机间的快速信息交流,第三层交换可以说是交换技术与路由技术的完美结合,而下文要详细介绍的第四层交换技术则可以为网络应用资源提供最优分配,实现应用服务的负载均衡. 2 第四层交换技术 2.1

交换机链路聚合负载的均衡算法原理

初衷: 在2011年初我学习交换机链路聚合技术的时候,心中一直有一个疑问: 交换机收到一个报文,到达聚合口的时候,是怎么选择成员口出去的呢? 是随机选的吗?还是按成员编号从小到大或从大到小轮循?如果选择源IP算法,是怎么实现不同源IP就走不同的端口的呢?那时网上也找不到介绍,这个疑问,直到2011年底做测试工程师时,才得到研发兄弟的回答,一直记在心里,总想找个时间发布到网上,让更多人知道,原来负载均衡算法其实是这么的简单! 链路聚合的主要作用是增加带宽,增加可靠性,防止二层环路.在这儿,我不讨论

【转载】四层和七层负载均衡的区别

简单理解四层和七层负载均衡:①所谓四层就是基于IP+端口的负载均衡:七层就是基于URL等应用层信息的负载均衡:同理,还有基于MAC地址的二层负载均衡和基于IP地址的三层负载均衡. 换句换说,二层负载均衡会通过一个虚拟MAC地址接收请求,然后再分配到真实的MAC地址:三层负载均衡会通过一个虚拟IP地址接收请求,然后再分配到真实的IP地址:四层通过虚拟IP+端口接收请求,然后再分配到真实的服务器:七层通过虚拟的URL或主机名接收请求,然后再分配到真实的服务器. ②所谓的四到七层负载均衡,就是在对后台

四层和七层负载均衡的区别

  (一) 简单理解四层和七层负载均衡: ① 所谓四层就是基于IP+端口的负载均衡;七层就是基于URL等应用层信息的负载均衡;同理,还有基于MAC地址的二层负载均衡和基于IP地址的三层负载均衡. 换句换说,二层负载均衡会通过一个虚拟MAC地址接收请求,然后再分配到真实的MAC地址;三层负载均衡会通过一个虚拟IP地址接收请求,然后再分配到真实的IP地址;四层通过虚拟IP+端口接收请求,然后再分配到真实的服务器;七层通过虚拟的URL或主机名接收请求,然后再分配到真实的服务器. ② 所谓的四到七层负载

负载均衡-lvs

常用的负载均衡技术比较DNS 轮询DNS本身的机制不再赘述,这里主要看一看基于DNS的负载均衡,其大致原理很清楚,DNS系统本身支持同一个域名映射到多个ip (A记录),例如 这样每次向DNS系统询问该域名的ip地址时(Tell Me The IP Address of niubility.com.),DNS会轮询(Round Robin)这个ip列表,每次给一个不同的ip,从而达到负载均衡的效果. 来看看这种负载均衡解决方案的优缺点 优点易于实现对于应用系统本身几乎没有任何侵入,配置也很简单,

网络负载均衡详解

一.四层和七层负载均衡简介 1. 常见的负载均衡类型 ① 二层负载均衡 基于MAC地址,它会通过一个虚拟MAC地址接收请求,然后再分配到真实的MAC地址. ② 三层负载均衡 基于IP地址,它会通过一个虚拟IP地址接收请求,然后再分配到真实的IP地址. ③ 四层负载均衡 基于IP地址和端口号,它会通过一个虚拟IP和端口号接收请求,然后再分配到真实的服务器. ④ 七层负载均衡 基于URL等应用层信息,它会通过虚拟的URL或主机名接收请求,然后再分配到真实的服务器. 2. 四层和七层负载均衡 所谓的四

借助LVS+Keepalived实现负载均衡

原文地址:http://www.cnblogs.com/edisonchou/p/4281978.html 一.负载均衡:必不可少的基础手段 1.1 找更多的牛来拉车吧 当前大多数的互联网系统都使用了服务器集群技术,集群即将相同服务部署在多台服务器上构成一个集群整体对外提供服务,这些集群可以是Web应用服务器集群,也可以是数据库服务器集群,还可以是分布式缓存服务器集群等等. 古人有云:当一头牛拉不动车的时候,不要去寻找一头更强壮的牛,而是用两头牛来拉车. 在实际应用中,在Web服务器集群之前总会

三步安装完成nginx负载均衡设置

Nginx负载均衡器的优点许多,简单概括为: ①实现了可弹性化的架构,在压力增大的时候可以临时添加tomcat服务器添加到这个架构里面去; ②upstream具有负载均衡能力,可以自动判断下面的机器,并且自动踢出不能正常提供服务的机器;而Keepalvied可保证单个nginx负载均衡器的有效性,避免单点故障. IP地址 nginx(主负载均衡器):192.168.1.106 nginx(从负载均衡器):192.168.1.107 VIP地址:192.168.1.108 tomcat1的IP:1

F5负载均衡配置手册

负载均衡器通常称为四层交换机或七层交换机.四层交换机主要分析IP层及TCP/UDP层,实现四层流量 负载均衡.七层交换机除了支持四层负载均衡以外,还有分析应用层的信息,如HTTP协议URI或Cookie信 息. 一.F5配置步骤: 1.F5组网规划 (1)组网拓朴图(具体到网络设备物理端口的分配和连接,服务器网卡的分配与连接) (2)IP地址的分配(具体到网络设备和服务器网卡的IP地址的分配) (3)F5上业务的VIP.成员池.节点.负载均衡算法.策略保持方法的确定 2.F5配置前的准备工作 (