负载均衡算法

• 对于要实现高性能集群，选择好负载均衡器很重要，同时针对不同的业务场景选择合适的负载均衡算法也是非常重要的。

一、负载均衡算法分类

• 任务平分类
  负载均衡系统将收到的任务平均分配给服务器进行处理，这里的“平均”可以是绝对数量的平均，也可以是比例或者权重上的平均。
• 负载均衡类
  负载均衡系统根据服务器的负载来进行分配，这里的负载并不一定是通常意义上我们说的“CPU 负载”，而是系统当前的压力，可以用 CPU 负载来衡量，也可以用连接数、I/O 使用率、网卡吞吐量等来衡量系统的压力。
• 性能最优类
  负载均衡系统根据服务器的响应时间来进行任务分配，优先将新任务分配给响应最快的服务器。
• Hash 类
  负载均衡系统根据任务中的某些关键信息进行 Hash 运算，将相同 Hash 值的请求分配到同一台服务器上。常见的有源地址 Hash、目标地址 Hash、session id hash、用户 ID Hash 等。

二、常见负载均衡算法及实现

• 为了后面实现方便，先抽象出一个负载均衡接口

public interface LoadBalance {
    /**
     * 根据某种策略获取相关服务
     * @return
     */
    Service doPickOneService();
}
public class Service {
    /**
     * 服务名称
     */
    private String name;

    public Service(String name) {
        this.name = name;
    }

    /**
     * 判断服务是否可用，这里假设全部可用
     * @return
     */
    public boolean isAvailable(){
        return true;
    }
}

1、轮询

• 负载均衡系统收到请求后，按照顺序轮流分配到服务器上。轮询是最简单的一个策略，无须关注服务器本身的状态。
• 在实现时，轮询算法通常是把所有可用节点放到一个数组里，然后按照数组编号，挨个访问。

public class RoundLoaderBalancer implements LoadBalance {

    private static AtomicInteger idx = new AtomicInteger(0);
    @Override
    public Service doPickOneService() {
        List<Service> serviceList = getServiceList();
        int index = getNextNonNegative();
        for (int i = 0; i < serviceList.size(); i++) {
            //获取服务
            Service service = serviceList.get((i + index) % serviceList.size());
            //判断服务是否可用
            if (service.isAvailable()) {
                return service;
            }
        }
        return null;
    }

    /**
     * 假设有这么一个获取全部服务的列表
     *
     * @return
     */
    public List<Service> getServiceList() {
        List<Service> serviceList = new ArrayList<>();
        Service service0 = new Service("service0");
        Service service1 = new Service("service1");
        Service service2 = new Service("service2");
        Service service3 = new Service("service3");
        Service service4 = new Service("service4");
        Service service5 = new Service("service5");
        serviceList.add(service0);
        serviceList.add(service1);
        serviceList.add(service2);
        serviceList.add(service3);
        serviceList.add(service4);
        return serviceList;
    }

    private int getNextNonNegative() {
        return getNonNegative(idx.incrementAndGet());
    }

    /**
     * 通过二进制位操作将originValue转化为非负数:
     * 0和正数返回本身
     * 负数通过二进制首位取反转化为正数或0（Integer.MIN_VALUE将转换为0）
     * return non-negative int value of originValue
     *
     * @param originValue
     * @return positive int
     */
    public int getNonNegative(int originValue) {
        return 0x7fffffff & originValue;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            System.out.println(new RoundLoaderBalancer().doPickOneService().toString());
        }
    }
}
- 缺点：无法根据服务器的状态差异进行任务分配的问题。

2、加权轮询算法

• 负载均衡系统根据服务器权重进行任务分配，这里的权重一般是根据硬件配置进行静态配置的，加权轮询是轮询的一种特殊形式，其主要目的就是为了解决不同服务器处理能力有差异的问题。
• 加权轮询算法是在轮询算法基础上，给每个节点赋予一个权重，从而使每个节点被访问到的概率不同，权重大的节点被访问的概率就高，权重小的节点被访问的概率就小。在实现时，加权轮询算法是生成一个节点序列，该序列里有n个节点，n是所有节点的权重之和。在这个序列中，每个节点出现的次数，就是它的权重值。比如有三个节点：a、b、c，权重分别是3、2、1，那么生成的序列就是{a、a、b、c、b、a}，这样的话按照这个序列访问，前6次请求就会分别访问节点a三次，节点b两次，节点c一次。从第7个请求开始，又重新按照这个序列的顺序来访问节点。需要注意的是要尽可能保证生产的序列的均匀，如果生成的不均匀会造成节点访问失衡，比如刚才的例子，如果生成的序列是{a、a、a、b、b、c}，就会导致前3次访问的节点都是a。
  （实现思路可以参考：https://blog.csdn.net/gqtcgq/article/details/52076997）
• 缺点：无法根据服务器的状态差异进行任务分配的问题。

3、负载最低优先（可以从连接数、http请求数、cpu负载等情况来）

• 负载最低优先的算法解决了轮询算法中无法感知服务器状态的问题，由此带来的代价是复杂度要增加很多。比如：最少活跃连接算法，顾名思义就是每一次访问都选择连接数最少的节点。因为不同节点处理请求的速度不同，使得同一个服务消费者同每一个节点的连接数都不相同。连接数大的节点，可以认为是处理请求慢，而连接数小的节点，可以认为是处理请求快。所以在挑选节点时，可以以连接数为依据，选择连接数最少的节点访问。但是最少连接数优先的算法要求负载均衡系统统计每个服务器当前建立的连接，其应用场景仅限于负载均衡接收的任何连接请求都会转发给服务器进行处理，否则如果负载均衡系统和服务器之间是固定的连接池方式，就不适合采取这种算法。例如，LVS 可以采取这种算法进行负载均衡，而一个通过连接池的方式连接 MySQL 集群的负载均衡系统就不适合采取这种算法进行负载均衡。
• 负载最低优先算法基本上能够比较完美地解决轮询算法的缺点，因为采用这种算法后，负载均衡系统需要感知服务器当前的运行状态。当然，其代价是复杂度大幅上升负。载最低优先算法如果本身没有设计好，或者不适合业务的运行特点，算法本身就可能成为性能的瓶颈，或者引发很多莫名其妙的问题。所以负载最低优先算法虽然效果看起来很美好，但实际上真正应用的场景反而没有轮询（包括加权轮询）那么多。

4、Hash 类算法

负载均衡系统根据任务中的某些关键信息进行 Hash 运算，将相同 Hash 值的请求分配到同一台服务器上，这样做的目的主要是为了满足特定的业务需求。例如：
（1）源地址 Hash
将来源于同一个源 IP 地址的任务分配给同一个服务器进行处理，适合于存在事务、会话的业务。
（2）ID Hash
将某个 ID 标识的业务分配到同一个服务器中进行处理，这里的 ID 一般是临时性数据的 ID（如 session id）。
（3）一致性hash
一致性hash算法，是通过某个hash函数，把同一个来源的请求都映射到同一个节点上。一致性hash算法最大的特点就是同一个来源的请求，只会映射到同一个节点上，可以说是具有记忆功能。只有当这个节点不可用时，请求才会被分配到相邻的可用节点上。

三、常用负载均衡算法应用场景

• 轮询算法：各个服务节点被访问的概率也基本相同，也主要应用在各个服务节点性能差异不大的情况下。
• 加权轮询算法：在轮询算法基础上的改进，可以通过给每个节点设置不同的权重来控制访问的概率，因此主要被用在服务节点性能差异比较大的情况。比如经常会出现一种情况，因为采购时间的不同，新的服务节点的性能往往要高于旧的节点，这个时候可以给新的节点设置更高的权重，让它承担更多的请求，充分发挥新节点的性能优势。
• 负载最低优先：由于复杂度和不可控制原因，实际应用还是很少的
• hash类算法：因为它能够保证同一个客户端的请求始终访问同一个服务节点，所以适合服务端节点处理不同客户端请求差异较大的场景。比如服务端缓存里保存着客户端的请求结果，如果同一客户端一直访问一个服务节点，那么就可以一直从缓存中获取数据。

四、实际案例分析

问题：微信抢红包的高并发架构，应该采取什么样的负载均衡算法？
思考：

微信抢红包架构应该至少包含两个负载均衡，一个是应用服务器的负载均衡，用于将任务请求分发到不同应用服务器，这里可以采用轮询或加权轮询的算法，因为这种速度快，适合抢红包的业务场景;另一起负载均衡是数据服务器的负载均衡，这里更适合根据红包ID进行hash负载均衡，将所有数据请求在同一台服务器上进行，防止多台服务器间的不同步问题。具体：
首先，发红包使用加权轮询，简单适用，成功后返回红包ID给客户端。
其次，抢红包，查询红包都带着ID给服务端，根据ID计算HASH，再利用一致性hash算法，找到最近的一个结点提供服务。