高并发场景下常见的限流算法及方案介绍-六虎

作者：京东科技康志兴

运用场景

现代互联网许多业务场景，比方秒杀、下单、查询产品详情，最大特点便是高并发，而往往咱们的体系不能承受这么大的流量，继而产生了许多的应对措施：CDN、音讯行列、多级缓存、异地多活。

可是无论如何优化，毕竟由硬件的物理特性决定了咱们体系性能的上限，假如强行接纳一切恳求，往往形成雪崩。

这时分限流熔断就发挥作用了，约束恳求数，快速失利，确保体系满负载又不超限。

极致的优化，便是将硬件运用率提高到100%，但永久不会超越100%

常用限流算法

1. 计数器

直接计数，简略暴力，举个比如：

比方限流设定为1小时内10次，那么每次收到恳求就计数加一，并判别这一小时内计数是否大于上限10，没超越上限就回来成功，否则回来失利。

这个算法的缺陷便是在时刻临界点会有较大瞬间流量。

持续上面的比如，抱负状态下，恳求匀速进入，体系匀速处理恳求：

但实际状况中，恳求往往不是匀速进入，假设第n小时59分59秒的时分忽然进入10个恳求，悉数恳求成功，抵达下一个时刻区间时改写计数。那么第n+1小时刚开始又打进10个恳求，等于瞬间进入20个恳求，肯定不符合“1小时10次”的规矩，这种现象叫做“突刺现象”。

为解决这个问题，计数器算法经过优化后，产生了滑动窗口算法：

咱们将时刻距离均匀分隔，比方将一分钟分为6个10秒，每一个10秒内独自计数，总的数量约束为这6个10秒的总和，咱们把这6个10秒成为“窗口”。

那么每过10秒，窗口往前滑动一步，数量约束变为新的6个10秒的总和，如图所示：

那么假如在临界时，收到10个恳求（图中灰色格子），在下一个时刻段来暂时，橙色部分又进入10个恳求，但窗口内包含灰色部分，所以已经抵达恳求上线，不再接纳新的恳求。

这便是滑动窗口算法。

可是滑动窗口依然有缺陷，为了确保匀速，咱们要划分尽可能多的格子，而格子越多，每一个格子能够接纳的恳求数就越少，这样就约束了体系瞬间处理才能。

2. 漏桶

漏桶算法其实也很简略，假设咱们有一个固定容量的桶，流速（体系处理才能）固定，假如一段时刻水龙头水流太大，水就溢出了（恳求被抛弃了）。

用编程的言语来说，每次恳求进来都放入一个先进先出的行列中，行列满了，则直接回来失利。另外有一个线程池固定距离不断地从这个行列中拉取恳求。

音讯行列、jdk的线程池，都有类似的设计。

3. 令牌桶

令牌桶算法比漏桶算法稍显复杂。

首先，咱们有一个固定容量的桶，桶里寄存着令牌（token）。桶一开始是空的，token以一个固定的速率往桶里填充，直抵到达桶的容量，多余的令牌将会被丢弃。每逢一个恳求过来时，就会测验从桶里移除一个令牌，假如没有令牌的话，恳求无法经过。

漏桶和令牌桶算法的区别：

漏桶的特点是消费才能固定，当恳求量超出消费才能时，供给一定的冗余才能，把恳求缓存下来匀速消费。长处是对下流保护更好。

令牌桶遇到激增流量会更从容，只需存在令牌，则能够一并消费掉。合适有突发特征的流量，如秒杀场景。

限流计划

一、容器限流

1. Tomcat

tomcat能够装备连接器的最大线程数属性，该属性maxThreads是Tomcat的最大线程数，当恳求的并发大于maxThreads时，恳求就会排队履行(排队数设置：accept-count)，这样就完成了限流的意图。

<Connector port="8080" protocol="HTTP/1.1"
          connectionTimeout="20000"
          maxThreads="150"
          redirectPort="8443" />

2. Nginx

Nginx 供给了两种限流手段：一是操控速率，二是操控并发连接数。

操控速率

咱们需求运用limit_req_zone装备来约束单位时刻内的恳求数，即速率约束，示例装备如下：
```
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
```
第一个参数：$binary_remote_addr 表明经过remote_addr这个标识来做约束，“binary_”的意图是缩写内存占用量，是约束同一客户端ip地址。

第二个参数：zone=mylimit:10m表明生成一个巨细为10M，名字为one的内存区域，用来存储拜访的频次信息。

第三个参数：rate=2r/s表明答应相同标识的客户端的拜访频次，这儿约束的是每秒2次，还能够有比方30r/m的。

并发连接数

运用limit_conn_zone和limit_conn两个指令即可操控并发数，示例装备如下

limit_conn_zone $binary_remote_addr zone=perip:10m;
limit_conn_zone $server_name zone=perserver:10m;
server {   
    ...
    limit_conn perip 10; # 约束同一个客户端ip
    limit_conn perserver 100;
}

只有当 request header 被后端处理后，这个连接才进行计数

二、服务端限流

1. Semaphore

JUC包中供给的信号量东西，它的内部保护了一个同步行列，咱们能够在每个恳求进来的时分，测验获取信号量，获取不到能够堵塞或许快速失利

简略样例：

Semaphore sp = new Semaphore(3);
sp.require(); // 堵塞获取
System.out.println("履行业务逻辑");
sp.release();

2. RateLimiter

Guava中根据令牌桶完成的一个限流东西，运用非常简略，经过办法create()创立一个桶，然后经过acquire()或许tryAcquire()获取令牌：

RateLimiter rateLimiter = RateLimiter.create(5); // 初始化令牌桶，每秒往桶里寄存5个令牌
rateLimiter.acquire(); // 自旋堵塞获取令牌，回来堵塞的时刻，单位为秒
rateLimiter.tryAcquire(); // 获取令牌，回来布尔成果，超越超时时刻（默以为0，单位为毫秒）则回来失利

RateLimiter在完成时，答应暴增恳求的突发状况存在。

举个比如，咱们有一个速率为每秒5个令牌的RateLimiter：

当令牌桶空了的时分，假如持续获取一个令牌，那么会在下一次弥补令牌的时分回来成果

但假如直接获取5个令牌，并不是等候桶内补齐5个令牌后再回来，而是仍旧会在令牌桶弥补下一个令牌的时分直接回来，而预支令牌所需的弥补时刻会在下一次恳求时进行补偿

public void testSmoothBursty() {
    RateLimiter r = RateLimiter.create(5);
    for (int i = 0; i++ < 2; ) {       
        System.out.println("get 5 tokens: " + r.acquire(5) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("end");
    }
}
/**
* 操控台输出
* get 5 tokens: 0.0s	  初始化时桶是空的，直接从空桶获取5个令牌
* get 1 tokens: 0.998068s 滞后效应，需求替前一个恳求进行等候
* get 1 tokens: 0.196288s
* get 1 tokens: 0.200391s
* end
* get 5 tokens: 0.195756s
* get 1 tokens: 0.995625s 滞后效应，需求替前一个恳求进行等候
* get 1 tokens: 0.194603s
* get 1 tokens: 0.196866s
* end
*/

3. Hystrix

Netflix开源的熔断组件，支持两种资源阻隔战略：THREAD（默认）或许SEMAPHORE

线程池：每个command运行在一个线程中，限流是经过线程池的巨细来操控的
信号量：command是运行在调用线程中，可是经过信号量的容量来进行限流

线程池战略对每一个资源创立一个线程池以进行流量管控，长处是资源阻隔完全，缺陷是简单形成资源碎片化。

运用样例：

// HelloWorldHystrixCommand要运用Hystrix功用 
public class HelloWorldHystrixCommand extends HystrixCommand {  
    private final String name; 
    public HelloWorldHystrixCommand(String name) {   
        super(HystrixCommandGroupKey.Factory.asKey("ExampleGroup"));     
        this.name = name; 
    } 
    // 假如承继的是HystrixObservableCommand，要重写Observable construct() 
    @Override 
    protected String run() {     
        return "Hello " + name; 
    } 
}

调用该command：

String result = new HelloWorldHystrixCommand("HLX").execute();
System.out.println(result);  // 打印出Hello HLX

Hystrix已经在2018年中止开发，官方推荐替代项目Resilience4j

更多运用介绍可查看：Hystrix熔断器的运用

4. Sentinel

阿里开源的限流熔断组件，底层核算采用滑动窗口算法，限流方面有两种运用办法：API调用和注解，内部采插槽链来核算和履行校验规矩。

经过为办法添加注解@SentinelResource(String name)或许手动调用SphU.entry(String name)办法开启流控。

运用API手动调用流控示例：

@Test
public void testRule() {
    // 装备规矩.
    initFlowRules();
    int count = 0;
    while (true) {
        try (Entry entry = SphU.entry("HelloWorld")) {
            // 被保护的逻辑
            System.out.println("run " + ++count + " times");
        } catch (BlockException ex) {
            // 处理被流控的逻辑
            System.out.println("blocked after " + count);
            break;
        }
    }
}
// 输出成果：
// run 1 times
// run 2 times
// run 3 times

关于Sentinel的具体介绍可查看：Sentinel-分布式体系的流量岗兵

三、分布式下限流计划

线上环境下，假如对共用资源（如数据库、下流服务）做一致流量约束，那么单机限流显然不能满足，而需求分布式流控计划。

分布式限流主要采取中心体系流量管控的计划，由一个中心体体系一管控流量配额。

这种计划的缺陷便是中心体系的可靠性，所以一般需求备用计划，在中心体系不可用时，退化为单机流控。

1. Tair经过incr办法完成简略窗口

完成办法是运用incr()自增办法来计数并与阈值进行巨细比较。

public boolean tryAcquire(String key) {
    // 以秒为单位构建tair的key
    String wrappedKey = wrapKey(key);
    // 每次恳求+1，初始值为0，key的有效期设置5s
    Result<Integer> result = tairManager.incr(NAMESPACE, wrappedKey, 1, 0, 5);
    return result.isSuccess() && result.getValue() <= threshold;
}
private String wrapKey(String key) {
    long sec = System.currentTimeMillis() / 1000L;
    return key + ":" + sec;
}

【补白】incr办法的参数阐明

// 办法定义：
Result incr(int namespace, Serializable key, int value, int defaultValue, int expireTime)
/* 参数意义：
namespace - 申请时分配的 namespace
key - key 列表，不超越 1k
value - 添加量
defaultValue - 第一次调用 incr 时的 key 的 count 初始值，第一次回来的值为 defaultValue + value。
expireTime - 数据过期时刻，单位为秒，可设相对时刻或绝对时刻（Unix 时刻戳）。
*/

2. Redis经过lua脚本完成简略窗口

与Tair完成办法类似，不过redis的incr()办法不能原子性的设置过期时刻，所以需求运用lua脚本，在第一次调用回来1时，设置下过期时刻为1秒。

local current
current = redis.call("incr",KEYS[1])
if tonumber(current) == 1 then 
    redis.call("expire",KEYS[1],1)
end
return current

3. Redis经过lua脚本完成令牌桶

完成思路是获取令牌后，用SET记录“恳求时刻”和“剩余token数量”。

每次恳求令牌时，经过这两个参数和恳求的时刻、流速等参数进行核算，回来是否获取令牌成功。

获取令牌lua脚本：

local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')
local last_time = ratelimit_info[1]
local current_token = tonumber(ratelimit_info[2])
local max_token = tonumber(ARGV[1])
local token_rate = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])
local reverse_time = 1000/token_rate
if current_token == nil then
  current_token = max_token
  last_time = current_time
else
  local past_time = current_time-last_time
  local reverse_token = math.floor(past_time/reverse_time)
  current_token = current_token+reverse_token
  last_time = reverse_time*reverse_token+last_time
  if current_token>max_token then
    current_token = max_token
  end
end
local result = 0
if(current_token>0) then
  result = 1
  current_token = current_token-1
end 
redis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)
redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
return result

初始化令牌桶lua脚本：

local result=1
redis.pcall("HMSET",KEYS[1],"last_mill_second",ARGV[1],"curr_permits",ARGV[2],"max_burst",ARGV[3],"rate",ARGV[4])
return result

高并发场景下常见的限流算法及方案介绍