高并发处理 | 限流

一、高并发场景做的系统优化

1. 限流：对入口流量做控制，对下游请求流量做自适应限流，根据接口响应时间动态调整流量
2. 消息队列：将请求写到mq里，后面系统逐条消费消息
3. 缓存：对于读多写少的场景，用缓存来提升高并发能力
4. 负载均衡：
5. 路由：若请求都依赖下游第三方的服务，可以将多家下游服务供应商做个动态路由表，将请求优先路由给接口成功率高、耗时低的服务供应商
6. 备份：基本是所有分布式组件都会做的，拆分节点，做多机部署，例如：Redis做三主三备(集群)、MySQL分库分表、MQ 与 Redis 互为备份等等；
7. 静态化数据：静态文件（如图片等）上传cdn，cdn节点缓存静态文件，减少服务器压力
8. 降级：当服务出问题或者影响到核心流程的性能则需要暂时屏蔽掉，待高峰或者问题解决后再打开。使用降级手段保障系统核心功能可用，或让模块达到最小可用。
9. 日志：完整的监控和链路日志，一是方便排查问题，二是可用来做任务重试、任务回滚、数据恢复、状态持久化等

二、限流的概念

1. 通过对并发访问、并发请求进行限速或者一个时间窗口内的的请求进行限速来保护系统，一旦达到限制速率则可以：
   a. 拒绝服务（定向到错误页或告知资源没有了）
   b. 排队或等待（比如秒杀、评论、下单）、
   c. 降级（返回兜底数据或默认数据，如商品详情页库存默认有货）
2. 常见限流手段：
   a. 限制总并发数
   b. 限制瞬时并发数（如nginx的limit_conn模块，用来限制瞬时并发连接数）
   c. 限制时间窗口内的平均速率（如Guava的RateLimiter、Nginx的limit_req模块，限制每秒的平均速率）
   d. 限流某个接口的总并发/请求数
   d. 限制远程接口调用速率、限制MQ的消费速率。
   e. 根据网络连接数、网络流量、CPU或内存负载等来限流
   f. 限制总资源数：可以使用池化技术来限制总资源数（连接池、线程池等），比如数据库连接池、线程池，Mysql（如max_connections）、缓存Redis（如tcp-backlog）
3. 限流的分类
   a. 合法性验证限流：比如验证码、IP 黑名单等，这些手段可以有效的防止恶意攻击和爬虫采集；
   b. 容器限流：比如 Tomcat、Nginx等限流手段，其中Tomcat可以设置最大线程数（maxThreads），当并发超过最大线程数会排队等待执行；而 Nginx 提供了两种限流手段：一是控制速率，二是控制并发连接数；
   c. 服务端限流（应用级限流）：比如我们在服务器端通过限流算法实现限流
   d. 分布式限流

三、限流算法

3.1 时间窗口算法

1. 以当前时间为截止时间，往前取一定的时间，比如往前取60s的时间，限制在这60s之内运行最大的访问数为100，此时算法的执行逻辑为，先清除60s之前的所有请求记录，再计算当前集合内请求数量是否大于设定的最大请求数100，如果大于则执行限流拒绝策略，否则插入本次请求记录并返回可以正常执行的标识给客户端
2. 可以借助 Redis 的有序集合 ZSet 来实现时间窗口算法限流，实现的过程是先使用 ZSet 的 key 存储限流的 ID，score 用来存储请求的时间，每次有请求访问来了之后，先清空之前时间窗口的访问量，统计现在时间窗口的个数和最大允许访问量对比，如果大于等于最大访问量则返回 false 执行限流操作，负责允许执行业务逻辑，并且在 ZSet 中添加一条有效的访问记录
   a. 缺点1：使用 ZSet 存储有每次的访问记录，如果数据量比较大时会占用大量的空间，比如 60s 允许 100W 访问时；
   b. 缺点2：非原子操作，先判断后增加，中间空隙可穿插其他业务逻辑的执行，最终导致结果不准确

3.2 漏桶算法

1. 滑动时间算法有一个问题就是在一定范围内，比如60s内只能有10个请求，当第一秒时就到达了10个请求，那么剩下的 59s 只能把所有的请求都给拒绝掉，而漏桶算法可以解决这个问题。
2. 理解漏桶：无论上面的水流倒入漏斗有多大，也就是无论请求有多少，它都是以均匀的速度慢慢流出的。当上面的水流速度大于下面的流出速度时，漏斗会慢慢变满，当漏斗满了之后就会丢弃新来的请求;当上面的水流速度小于下面流出的速度的话，漏斗永远不会被装满，并且可以一直流出。
3. 解释：
   a. 一个固定容量的漏桶，按照常量固定速率流出水滴；
   b. 如果桶是空的，则不需流出水滴；
   c. 可以以任意速率流入水滴到漏桶；
   d. 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。
4. 实现：先声明一个队列用来保存请求，这个队列相当于漏斗，当队列容量满了之后就放弃新来的请求，然后重新声明一个线程定期从任务队列中获取一个或多个任务进行执行，这样就实现了漏桶算法
5. Nginx 的控制速率其实使用的就是漏桶算法
6. 借助Redis也可以实现漏桶算法，可以使用Redis 4.0版本中提供的Redis-Cell模块中的cl.throttle指令，该模块使用的是漏斗算法，并且提供了原子的限流指令，而且依靠Redis这个天生的分布式程序就可以实现比较完美的限流了

   // 其中 15 为漏斗的容量，30 / 60s 为漏斗的速率。
   > cl.throttle mylimit 15 30 60
   1）（integer）0 # 0 表示获取成功，1 表示拒绝
   2）（integer）15 # 漏斗容量
   3）（integer）14 # 漏斗剩余容量
   4）（integer）-1 # 被拒绝之后，多长时间之后再试（单位：秒）-1 表示无需重试
   5）（integer）2 # 多久之后漏斗完全空出来

3.3 令牌桶算法

1. 一个存放固定容量令牌的桶，有一个程序以某种恒定的速度生成令牌，并存入令牌桶中，而每个请求需要先获取令牌才能执行，如果没有获取到令牌的请求可以选择等待或者放弃执行
2. 令牌桶的方法可以根据系统负载，实时调节系统的处理能力，能够允许一定量级的瞬时高峰流量的快速消化，即请求的速率可以突发
3. Guava包的RateLimiter提供了令牌桶算法的支持（Guava的RateLimiter是程序级别的单机限流方案，上面的Redis-Cell提供的漏桶算法是分布式的限流方案）

3.4 计数器

1. 粗暴的限制限制总并发数，看单位时间内，所接受的QPS的请求有多少，如果超过阈值，则直接拒绝服务。
2. 主要用来限制总并发数，比如数据库连接池、线程池、秒杀的并发数；只要全局总请求数或者一定时间段的总请求数设定的阀值则进行限流
3. 可以用缓存（Guava Cache或者Caffeine Cache） + AtomicLong来实现

三、容器限流

常见思路：

1. 限流总并发/连接/请求数
2. 限流总资源数
3. 控制速率

3.1 Tomcat限流

1. 在conf/server.xml中或者在application.yml中可以配置maxConnections、maxThreads、acceptCount
   a. maxConnections：这个参数是指在同一时间，tomcat能够接受的最大连接数（瞬时最大连接数）。对于Java的阻塞式BIO，默认值是maxthreads的值；如果在BIO模式使用定制的Executor执行器，默认值将是执行器中maxthreads的值。对于Java 新的NIO模式，maxConnections 默认值是10000。
   b. maxThreads：Tomcat的最大线程数，每一次HTTP请求到达Web服务，Tomcat都会创建一个线程来处理该请求，那么最大线程数决定了Web服务容器可以同时处理多少个请求，当请求的并发大于此值（maxThreads）时，请求就会排队执行，从而限流
   c. acceptCount：最大等待数，当所有的请求处理线程都在使用时，所能接收的连接请求的队列的最大长度。当队列已满时，任何的连接请求都将被拒绝
2. 对于maxThreads而言，操作系统对于进程中的线程数有一定的限制，Windows每个进程中的线程数上限2000，Linux 每个进程中的线程数不允许超过1000

3.2 Nginx限流

1. Nginx提供了两种限流手段：一是控制速率，二是控制并发连接数

2. 控制速率：使用 limit_req_zone 用来限制单位时间内的请求数，即速率限制

   // 限制每个IP访问的速度为 2r/s，
   // Nginx的限流统计是基于毫秒的，设置的速度是2r/s，即500ms内单个IP只允许通过1个请求，从501ms开始才允许通过第2个请求。
   limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
   server { 
       location / { 
           limit_req zone=mylimit;
       }
   }

3. 速率限制升级版：上面的速率控制虽然很精准但是应用于真实环境过于苛刻了，真实情况下我们应该控制一个IP单位总时间内的总访问次数，而不是像上面那样精确到毫秒，我们可以使用 burst 关键字开启此设置

   limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
   server { 
       location / { 
           limit_req zone=mylimit burst=4;
       }
   }

4. 控制并发连接数：利用 limit_conn_zone 和 limit_conn 两个指令即可控制并发数

   // limit_conn perip 10 表示限制单个 IP 同时最多能持有 10 个连接
   // limit_conn perserver 100 表示 server 同时能处理并发连接的总数为 100 个
   // 只有当request header被后端处理后，这个连接才进行计数
   limit_conn_zone $binary_remote_addr zone=perip:10m;
   limit_conn_zone $server_name zone=perserver:10m;
   server {
       ...
       limit_conn perip 10;
       limit_conn perserver 100;
   }

3.3 说明

1. 在限制总并发/连接/请求数的场景中，数据库Mysql（如max_connections）、缓存Redis（如tcp-backlog）等，也有类似的限制连接数的配置。

四、服务端限流

4.1 限制某个接口的总并发数/请求数

若接口可能会遇到瞬时高流量访问情况，可能会因为访问量太大造成崩溃，此时需要限制这个接口的总并发/总请求数。由于粒度较细，可以为每个接口都设置相应的阀值。
可以使用Java中的AtomicLong进行限流：

// 简单粗暴，没有平滑处理
long limit = 200L
try
{
    if(atomic.incrementAndGet() > 限流数) 
    {
        //拒绝请求
    }
    //处理请求
}
finally {
    atomic.decrementAndGet();
}

4.2 限流某个接口的时间窗请求数

即一个时间窗口内的请求数，如想限制某个接口或服务每秒/每分钟/每天的请求数或调用量。一些基础服务会被很多其他系统调用，比如商品详情页服务会调用基础商品服务，但是怕因为更新量比较大将基础服务打挂，这时我们要对秒级/分钟级的调用量进行限速。

/**
 * @author dc
 * @date 2020/6/18 22:53
 */
public class WindowRateLimit
{
    // 使用Guava的Cache来存储计数器，过期时间设置为2秒（保证1秒内的计数器是有的）
    // 获取当前时间戳然后取秒数来作为KEY进行计数统计和限流，这种方式也是简单粗暴
    private LoadingCache<Long, AtomicLong> counter = CacheBuilder.newBuilder()
        //设置要统计缓存的命中率
        .recordStats()
        //设置写缓存后2秒钟过期
        .expireAfterWrite(2, TimeUnit.SECONDS).build(new CacheLoader<Long, AtomicLong>()
        {
            @Override
            public AtomicLong load(Long seconds)
                throws Exception
            {
                return new AtomicLong(0);
            }
        });

    public void myMethod()
        throws ExecutionException
    {
        // 该接口限流1000
        long limit = 1000;
        while (true)
        {
            //得到当前秒
            long currentSeconds = System.currentTimeMillis() / 1000;
            if (counter.get(currentSeconds).incrementAndGet() > limit)
            {
                System.out.println("限流了:" + currentSeconds);
                continue;
            }
            //业务处理
            System.out.println("处理业务");
        }
    }
}

4.3 平滑限流某个接口的请求数

1. 上述的两种限流方式都不能很好地应对突发请求，即瞬间请求可能都被允许从而导致一些问题。因此在一些场景中需要对突发请求进行整形，整形为平均速率请求处理（比如5r/s，则每隔200毫秒处理一个请求，平滑了速率）。面对这种场景，可以采用令牌桶算法或漏桶算法。
2. Guava RateLimiter提供了令牌桶算法实现：一种是平滑突发限流(SmoothBursty)，另一种是平滑预热限流(SmoothWarmingUp)

4.3.1 常规速率 SmoothBursty（平滑输出）

public void method1()
{
    // 表示桶容量为5且每秒新增5个令牌，即每隔200毫秒新增一个令牌
    RateLimiter r = RateLimiter.create(5);
    while (true)
    {
        // acquire()表示消费一个令牌，并且返回获取这个令牌所需要的时间。
        // 如果当前桶中有足够令牌则成功。如果桶中没有令牌则暂停一段时间，直到有令牌。
        // 比如发令牌间隔是200毫秒，则等待200毫秒后再去消费令牌
        // acquire(N)可以获取多个令牌
        System.out.println(r.acquire());
        // 输出：
        // 0.0
        // 0.195734
        // 0.174035
        // 0.17114
        // 0.199599
        // 0.199641
        // 0.196775
        // ...
    }
}

4.3.2 SmoothBursty 突发流量

public void method2()
{
    // 表示桶的容量为5且每秒新增5个令牌
    // 令牌桶算法允许一定程度的突发，所以可以一次性消费5个令牌
    // 但接下来的limiter.acquire(1)将等待差不多1秒桶中才能有令牌，且接下来的请求也整形为固定速率了。
    RateLimiter limiter = RateLimiter.create(5);

    System.out.println(limiter.acquire(5));
    System.out.println(limiter.acquire(1));
    // 突发流量可以是突发的多，也可以是突发的少
    // Thread.sleep(2000);
    System.out.println(limiter.acquire(1));
}

4.3.3 SmoothWarmingUp 带缓冲的流量输出

1. 由于SmoothBursty允许一定程度的突发，假设突然间来了很大的流量，那么系统很可能扛不住这种突发。因此需要一种平滑速率的限流工具，从而让系统冷启动后慢慢的趋于平均固定速率（即刚开始速率小一些，然后慢慢趋于我们设置的固定速率）。
2. Guava也提供了SmoothWarmingUp来实现这种场景，其可以认为是漏桶算法，但是在某些特殊场景又不太一样。

   // 速率是梯形上升速率的，即冷启动时会以一个比较大的速率慢慢到平均速率，然后趋于平均速率（梯形下降到平均速率）
   // 可以通过调节warmupPeriod参数实现一开始就是平滑固定速率
   public void method3()
   {
       // 创建一个限流器，设置每秒放置的令牌数为2
       // 设置缓冲时间（在从冷启动速率过渡到平均速率的时间间隔）为3秒
       // 返回的RateLimiter对象可以保证1秒内不会给超过2个令牌，并且是固定速率的放置。
       // 达到平滑输出的效果
       RateLimiter r = RateLimiter.create(2, 3, TimeUnit.SECONDS);
   
       while (true)
       {
           System.out.println(r.acquire(1));
           System.out.println(r.acquire(1));
           System.out.println(r.acquire(1));
           System.out.println(r.acquire(1));
       }
   }

4.4 Alibaba Sentinel

1. Sentinel 是一个带配置中心的分布式缓存，以 “资源名称” 为统计点，提供了多种方式的限流方案，可以基于 QPS、线程数，甚至系统 load 进行集群规模的限流。
2. spring cloud中可以使用@SentinelResource注解，来进行限流或是降级的保护。

五、分布式限流

1. 分布式限流最关键的是要将限流服务做成原子化，而解决方案可以使使用redis+lua或者nginx+lua技术进行实现，通过这两种技术可以实现的高并发和高性能。