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

21次阅读

共计 6517 个字符,预计需要花费 17 分钟才能阅读完成。

作者:京东科技 康志兴

利用场景

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

正文完
 0