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

作者：京东科技康志兴

利用场景

古代互联网很多业务场景，比方秒杀、下单、查问商品详情，最大特点就是高并发，而往往咱们的零碎不能接受这么大的流量，继而产生了很多的应答措施：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手动调用流控示例：

@Testpublic 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 - 申请时调配的 namespacekey - key 列表，不超过 1kvalue - 增加量defaultValue - 第一次调用 incr 时的 key 的 count 初始值，第一次返回的值为 defaultValue + value。expireTime - 数据过期工夫，单位为秒，可设绝对工夫或相对工夫（Unix 工夫戳）。*/

2. Redis通过lua脚本实现简略窗口

与Tair实现形式相似，不过redis的incr()办法不能原子性的设置过期工夫，所以须要应用lua脚本，在第一次调用返回1时，设置下过期工夫为1秒。

local currentcurrent = redis.call("incr",KEYS[1])if tonumber(current) == 1 then     redis.call("expire",KEYS[1],1)endreturn 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_rateif current_token == nil then  current_token = max_token  last_time = current_timeelse  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  endendlocal result = 0if(current_token>0) then  result = 1  current_token = current_token-1end 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=1redis.pcall("HMSET",KEYS[1],"last_mill_second",ARGV[1],"curr_permits",ARGV[2],"max_burst",ARGV[3],"rate",ARGV[4])return result

作者：京东科技 康志兴