限流算法探秘

2021-02-17 From 程序之心 By 丁仪
<p> 在资源有限的情况下,遇到突发流量(如双十一)或系统 RT 剧增,为了保证系统不被拖垮引起更大规模的雪崩,必须进行限流。也就是说限流系统的自我保护。限流本质上是根据系统处理能力,限制单位时间处理请求数量。 p>

滑动窗口

<p> 这里的窗口是一个时间窗口,比如把一分钟划分为 6 个窗口,则每个窗口的时间范围是 10 秒。通过移动窗口,统计窗口期内流量,可以实现窗口期的限流。但是滑动窗口存在精度问题,在精度范围内统计到的窗口期流量可能限流范围内,但进一步细分就会看到仍有突增流量。 p> <p> 滑动窗口时间范围越小,就越平滑,限流的效果越精确,但时间细分的粒度受到客观限制。 p> <p> p>

漏桶算法

<p> 漏桶算法,英文名 Leaky Bucket,是网络中流量整形(Traffic Shaping)和速率限制(Rate Limiting)常用的一种算法。漏桶算法调控了访问流量,使得突发流量可以被整形、去毛刺,为系统提供稳定的访问流量。如果漏桶溢出,请求就会被丢弃。 p> <p> p> <p> 桶以固定的速率流出流量,无论水龙头进入的流量是多少,都不改变流出速率。上图中,水龙头处存在突发流量,一共进入 30Mb 数据,分布不均匀,对系统有冲击。经过漏桶算法处理,漏桶以 3 Mbps 速率持续流出数据,为系统做了很好的缓冲。 p> <p> 漏桶算法中,如果桶未满,可以持续接收流量;如果桶已满,流量溢出,后续的流量将无法入桶,会被丢弃。漏桶算法限制的是流出速率,无论流入是多少,都能保证后续系统请求是平稳的。后续系统感知的流量相对固定,但可能系统仍有能力处理更多流量的时候,也会被漏桶限制住。 p>

令牌桶算法

<p> 令牌桶算法,英文名 token bucket,也是网络中流量整形或速率限制常用的一种算法。令牌桶算法以一个恒定的速率向桶里放入令牌,如果有新的请求进来希望进行处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。令牌桶算法限制的是流入速率,允许一定规模的突增流量,最大速率受限于桶的容量和令牌生成速率。可以支持一定程度的突发流量,更适合具有突发特性的流量。 p> <p> p> <p> 令牌桶算法的简单描述如下: p>
  • 每隔 1/r 秒向桶中增加一个 token
  • 桶最多只能存放 b 个 token。如果放置 token 时桶已经满了,丢弃这个 token
  • 当一个包含 n 个字节数据包进来的时候,

自适应限流阈值

<p> 使用自适应阈值可以动态调整限流,通过运行中不断试探,最终可以在系统处理能力限流之间找到一个动态平衡。既能最大限度利用系统处理能力,又能确保系统稳定性。目前比较简单的自定义算法是参考 TCP 拥塞算法的斜率算法。斜率算法设置一个基准值,可以结合应用的 Load、CPU 使用率、总体平均 RT、入口 QPS 和并发线程数等几个维度的监控指标评估系统负载,负载高了降低限流阈值,负载低了提高限流阈值。 p> <p> 目前比较简单的方案使用平均 rt 计算斜率,公式为 p> <p> gradient =(RTTnoload / RTTactual) p> <p> newLimit = currentLimit×gradient + queueSize p> <p> 其中,RTTnoload 表示无负载时的 rt,RTTactual 表示当前实际 rt。gradient 小于 1 表示负载偏高,大于 1 表示负载偏低。经过一段时间的试探,就能把系统流量控制在合理范围。 p> <p> p>

分布式限流

<p> 现代网络服务通常都有多台机器需要对集群做限流。目前使用比较广泛方案是 Redis 。滑动窗口可以使用 Redis 记录时间访问次数;Redis-Cell 是一个实现漏桶算法的分布式限流扩展模块,使用非常方便。 p>

本文来源:程序之心,转载请注明出处!

本文地址:https://chengxuzhixin.com/blog/article/200065.html

发表感想

© 2016 - 2022 chengxuzhixin.com All Rights Reserved.

浙ICP备2021034854号-1    浙公网安备 33011002016107号