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

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

限流


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



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


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,这可能导致在进行周期切换时可能出现流量突发


如图所示


image.png


简化模型


  • 两个周期T0中a时刻有n1个访问同时到达;
  • 周期T1中b时刻有n2个访问同时到达;
  • n1和n2均小于设定的最高访问次数N(否则会触发限流)



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


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



滑动窗口计数


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



实现原理


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


限流流程如下:image.png


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

image.png



周期切换问题


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



非计数限流法


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


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



漏桶限流


实现原理


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

image.png




  • 设定漏桶流出速度及漏桶的总容量,在请求到达时判断当前漏桶容量是否已满,不满则可将请求存入桶中,否则抛弃请求。
  • 采用一个线程以设定的速率取出请求进行处理。
  • 需要确定参数为漏桶流出速度r及漏桶容量N


流程如下:

image.png


算法特点


  • 漏桶算法主要特点在于可以保证无论收到请求的速率如何,真正抵达服务方接口的请求速率最大为r,能够对输入的请求进行平滑处理。
  • 漏桶算法的缺点也非常明显,由于其只能以特定速率处理请求,则如何确定该速率就是核心问题,如果速率设置太小则会浪费性能资源,设置太大则会造成资源不足。
  • 并且由于速率的设置,无论输入速率如何波动,均不会体现在服务端,即使资源有空余,对于突发请求也无法及时处理,故对有突发请求处理需求时,不宜选择该方法。



令牌桶限流


  • 对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。
  • 令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。



实现原理


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


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

image.png


算法特点


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



限流算法比较


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


image.png


image.png








相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
49 1
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
117 4
|
11天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
48 20
|
10天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
25 6
|
2月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
110 23
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
65 1
|
9天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
142 80
|
3天前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。