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

作者：京东科技康志兴

运用场景

现代互联网许多业务场景，比方秒杀、下单、查询产品详情，最大特点便是高并发，而往往咱们的体系不能承受这么大的流量，继而产生了许多的应对措施：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

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

运用场景

常用限流算法

1. 计数器

2. 漏桶

3. 令牌桶

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

限流计划

一、容器限流

1. Tomcat

2. Nginx

二、服务端限流

1. Semaphore

2. RateLimiter

3. Hystrix

4. Sentinel

三、分布式下限流计划

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

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

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

作者信息

推广

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

运用场景

常用限流算法

1. 计数器

2. 漏桶

3. 令牌桶

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

限流计划

一、容器限流

1. Tomcat

2. Nginx

二、服务端限流

1. Semaphore

2. RateLimiter

3. Hystrix

4. Sentinel

三、分布式下限流计划

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

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

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

相关文章

2023年的深度学习入门指南(5) – 动手写第一个语言模型

人工智能 | ShowMeAI资讯日报 #2022.06.21

【pytorch算子】torch.arange 算子在 CPU/GPU/NPU 中支持的数据类型格式

曼曼心理咨询【基于ChatGLM-6B微调】

作者信息

推广