Skip to content

限流算法

在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩。

计数器

在一段时间间隔内(时间窗/时间区间),处理请求的最大数量固定,超过部分不做处理。

实际应用

线程池大小,指定数据库连接池大小、nginx连接数等

临界问题

假设我们系统中现在只有一个用户,这个用户在59秒的时候发送了100次请求,然后在一分零一秒的时候又发送了100次请求,这个时候实际上在系统当中,一分钟之内就接收了200次请求,可能会导致我们的服务蹦掉。限流算法在这个临界点没有发挥作用

如何解决临界问题——滑动窗口

之所以计数器算法会造成临界值的问题,是因为我们在统计Counter的时候精度太低了。而滑动窗口算法则是在此基础之上,进行了优化

在使用滑动时间窗口,我们可以把1分钟分成6格,每格时间长度是10s,每一格又各自管理一个计数器,单位时间用一个长度为60s的窗口描述。一个请求进入系统,对应的时间格子的计数器便会+1,而每过10s,这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限,便会拒绝后面的请求。

漏斗算法

漏斗算法限流的基本原理为:水(对应请求)从进水口进入到漏桶里,漏桶以一定的速度出水(请求放行),当水流入速度过大,桶内的总水量大于桶容量会直接溢出,请求被拒绝

在系统看来,请求永远是以平滑的传输速率过来,从而起到了保护系统的作用。

漏斗算法的应用

Nginx漏斗限流 limit_req_zone

漏斗算法存在的问题

漏桶出口的速度固定,不能灵活的应对后端能力提升。比如,通过动态扩容,后端流量从1000QPS提升到1WQPS,漏桶没有办法。必须调整算法才行

令牌桶

令牌桶算法是对漏斗算法的一种改进,除了能够起到限流的作用外,还允许一定程度的流量突发,因为处理完后,立马就可以取令牌,而漏斗算法就不行,出水口就那么大。

令牌桶算法以一个设定的速率产生令牌并放入令牌桶,每次用户请求都得申请令牌,如果令牌不足,则拒绝请求。 令牌桶算法中新请求到来时会从桶里拿走一个令牌,如果桶内没有令牌可拿,就拒绝服务。当然,令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关,时间流逝的时间越长,会不断往桶里加入越多的令牌,如果令牌发放的速度比申请速度快,令牌桶会放满令牌,直到令牌占满整个令牌桶,

削峰:有大量流量进入时,会发生溢出,从而限流保护服务可用

缓冲:不至于直接请求到服务器, 缓冲压力

令牌桶的实现

Guava的 RateLimiter提供了令牌桶算法实现:平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。