写点什么

🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)

发布于: 2 小时前
🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)

限流

限流的目的是通过对并发访问/请求进行限速,或者对一个时间窗口内的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

限流一词常用于计算机网络之中,定义如下:

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.


  • 通过控制数据的网络数据的发送或接收速率来防止可能出现的 DOS 攻击。而实际的软件服务过程中,限流也可用于 API 服务的保护。

  • 由于提供服务的计算机资源(包括 CPU、内存、磁盘及网络带宽等)是有限的,则其提供的 API 服务的 QPS 也是有限的,限流工具就是通过限流算法对 API 访问进行限制,保证服务不会超过其能承受的负载压力。

主要内容:

常用限流算法的简单介绍及比较

常用限流算法

常用的限流算法主要包括:


  • Token bucket-令牌桶

  • Leaky bucket-漏桶

  • Fixed window counter-固定窗口计数

  • Sliding window log-滑动窗口日志

  • Sliding window counter-滑动窗口计数

  • 以上几种方式其实可以简单的分为计数算法、漏桶算法和令牌桶算法。

计数限流算法

无论固定窗口还是滑动窗口核心均是对请求进行计数,区别仅仅在于对于计数时间区间的处理。

固定窗口计数

实现原理


  • 固定窗口计数法思想比较简单,只需要确定两个参数:计数周期 T 及周期内最大访问(调用)数 N。请求到达时使用以下流程进行操作


算法优点


  • 固定窗口计数实现简单,并且只需要记录上一个周期起始时间与周期内访问总数,几乎不消耗额外的存储空间。


算法缺陷


固定窗口计数缺点也非常明显,在进行周期切换时,上一个周期的访问总数会立即置为 0,这可能导致在进行周期切换时可能出现流量突发


如图所示



简化模型


  • 两个周期 T0 中 a 时刻有 n1 个访问同时到达;

  • 周期 T1 中 b 时刻有 n2 个访问同时到达;

  • n1 和 n2 均小于设定的最高访问次数 N(否则会触发限流)


在发生时间间隔切换的时候,在切换的过程中发生并发突变,所以在实际使用过程中,固定窗口计数器存在突破限额 N 的可能。


  • 举例,限制 QPS 为 10,某用户在周期切换的前后的 0.1 秒内,分两次发送 10 次请求,根据算法规则此 20 次请求可通过限流器,则 0.1 面秒请求数 20,超过每秒最多 10 次请求的限制。

滑动窗口计数

为解决固定窗口计数带来的周期切换处流量突发问题,可以使用滑动窗口计数。滑动窗口计算本质上也是固定窗口计数,区别在于将计数周期进行细化

实现原理

滑动窗口计数法与固定窗口计数法相比较,除了计数周期 T 及周期内最大访问(调用)数 N 两个参数,增加一个参数 M,用于设置周期 T 内的滑动窗口数。


限流流程如下:



滑动窗口计数在固定窗口计数记录数据基础上,需要增加一个长度为 M 的计数数组,用于记录在窗口滑动过程中各窗口访问数据。其流程示例如下:


周期切换问题


滑动窗口针对周期进行了细分,不存在周期到后计数直接重置为 0 的情况,故不会出现跨周期的流量限制问题。

非计数限流法

常用的限流算法有两种:漏桶算法和令牌桶算法


  • 漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。

漏桶限流

实现原理


漏桶限流算法的实现原理图:



  • 设定漏桶流出速度及漏桶的总容量,在请求到达时判断当前漏桶容量是否已满,不满则可将请求存入桶中,否则抛弃请求。

  • 采用一个线程以设定的速率取出请求进行处理。

  • 需要确定参数为漏桶流出速度 r 及漏桶容量 N


流程如下:



算法特点


  • 漏桶算法主要特点在于可以保证无论收到请求的速率如何,真正抵达服务方接口的请求速率最大为 r,能够对输入的请求进行平滑处理。

  • 漏桶算法的缺点也非常明显,由于其只能以特定速率处理请求,则如何确定该速率就是核心问题,如果速率设置太小则会浪费性能资源,设置太大则会造成资源不足。

  • 并且由于速率的设置,无论输入速率如何波动,均不会体现在服务端,即使资源有空余,对于突发请求也无法及时处理,故对有突发请求处理需求时,不宜选择该方法。

令牌桶限流

  • 对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。

  • 令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。

实现原理

设定令牌桶中添加令牌的速率,并且设置桶中最大可存储的令牌,当请求到达时,向桶中请求令牌(根据应用需求,可能为 1 个或多个),若令牌数量满足要求,则删除对应数量的令牌并通过当前请求,若桶中令牌数不足则触发限流规则。


根据描述需要设置的参数为,令牌添加速率 r,令牌桶中最大容量 N,流程如下:


算法特点

令牌桶算法通过设置令牌放入速率可以控制请求通过的平均速度,且由于设置的容量为 N 的桶对令牌进行缓存,可以容忍一定流量的突发。

限流算法比较

以上提到四种算法,本小节主要对四种算法做简单比较算法进行对比。










发布于: 2 小时前阅读数: 3
用户头像

🏆 2021年InfoQ写作平台-签约作者 🏆 2020.03.25 加入

👑【酷爱计算机技术、醉心开发编程、喜爱健身运动、热衷悬疑推理的”极客狂人“】 🏅 【Java技术领域,MySQL技术领域,APM全链路追踪技术及微服务、分布式方向的技术体系等】 “任何足够先进的技术都是魔法“

评论

发布
暂无评论
🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)