限流算法，接口限流的四种算法

本内容由系统网小编为大家分享，Windows系统安装教程、办公系统、软件怎么使用、软件使用教程、办公软件攻略等信息。

即时流量太高, 服务被压垮了 吗? 恶意用户高频查看,导致服务器延迟? 消息消耗太快,导致太多的数据库压力,性能下降,甚至崩溃?……

在高耦合系统中,由于系统保护角,流量通常是有限的;它不仅在工作场所经常使用,而且在面试中也使用高频测试点。

本文将介绍图形中常见的边界流算法,从各算法的特点出发,提出选择边界流算法的建议,并给出在Java语言中实现代码的实例。

固定窗口

固定窗口(英语:Fixed Window,又称计量算法、固定窗口)是最简单的限制算法,它通过在一定时间内保持计量器来控制在一定时间内的最大访问量。

假设请求限度不超过60分钟,设置一个计数器以拒绝请求,如果计数器在请求到达时达到阈值,否则计数器将增加1,并重定计数器为0分钟。 代码实现如下:

固定窗口的最大优点是易于实现,而且内存小,我们只需要把数目存储在时间窗口中,这样就可以确保处理较近期的请求,堆积的旧请求不会使新请求饿死。当然,我们也面临着关键问题,当两个窗口交界处，瞬时流速可能为2n。

滑动窗口

为了防止瞬时流量，可以把固定窗口近一步划分成多个格子，每次向后移动一小格，而不是固定窗口大小，这就是滑动窗口（Sliding Window）。

例如,每分钟可以分成六分之一秒。每个网格都有单独的计数器,每次窗子向前滑动, 它就会滑动一个单元.每当请求到达时，如果窗口中的单元行总数不超过一个阈值,则可以释放。在TCP协议中传输数据包,同样适用于流动控制的 sliding windows.

实现如下：

滑动窗口解决了计数器中的瞬时流量高峰问题，其实计数器算法也是滑动窗口的一种，只不过窗口没有进行更细粒度单元的划分。对比计数器可见，当窗口划分的粒度越细，则流量控制更加精准和严格。

然而,当窗口中的流动达到阈值时,流动将立即切断,在实际应用中,我们希望限制流动效应往往不是一次扣住流动,而是允许流动顺利进入系统。

漏桶算法

如何使流动更加平稳?看一下LeakyBucket算法。如要求水以任何速度注入泄漏桶,当注射率继续高于泄漏率时,桶会以固定的速度泄漏;漏桶会变满，新输入的请求将暂时被丢弃。限流和塑性是泄漏桶算法的两个核心功能.

实现如下：

这并不是一个完整的漏桶算法的实现，以上代码中只是对流量是否会被抛弃进行校验，即tryAcquire返回true表示漏桶未满，否则表示漏桶已满丢弃请求。

如果流要以固定速率泄漏,它也应该与FIFO队列一起实现。 WhentryAcquire 返回 True,请求被排队,然后通过从队列中抽出请求以固定频率处理。

漏斗算法的主要目的是平滑突然流动,提供一种保证网络中的突然流动被集成到平滑的稳定量流动的机制。

然而,由于泄漏桶的流量控制过于严格,在某些情况下系统资源不能被充分使用,因为泄漏桶的泄漏率是固定的,甚至在下游可以处理更多的流量的时候,泄漏桶不允许突然流过。

令牌桶

如何在够限制流量速率的前提下，又能够允许突发流量呢？令牌桶算法了解一下！令牌桶算法是以恒定速率向令牌桶发送令牌，请求到达时，尝试从令牌桶中拿令牌，只有拿到令牌才能够放行，否则将会被拒绝。

许可证桶具有下列特点:

以恒定的速率发放令牌，假设限流速率为v/s，则表示每1/v秒发放一个令牌 假设卡桶容量为b。 如果卡桶满了,新卡将被丢弃 要求能够通过限制器的假设是有一个卡在卡桶里

令牌桶算法中值得关注的参数有两个，即限流速率v/s，和令牌桶容量b；速率a表示限流器一般情况下的限流速率，而b则是burst的简写，表示限流器允许的最大突发流量。

例如,如果b=10,当卡桶填满时,有10张可用的卡,允许10张请求同时通过限制器(允许一定数量的突然流动),并且当10张请求立刻消耗了卡后,随后的流动只能通过限制器以r的速度。

实现如下：

不用说,最容易想象的实现是生产者-消费者模型;生产者线程按计划将许可证添加到阻塞队列中,而试图通过限制器的线程则只是从阻塞队列中获得许可证并被允许通过限制器的消费者线程。

由于线程调度的不确定性,调度错误在高耦合场景中非常大,并且调度器本身创建了调度线程,这也影响到系统性能。

滑动日志

滑动日志是一个相对“冷门”,但它是一个非常好的限流算法。 滑动日志速度算法需要记录请求时间标记,通常是存储在一个有序集合中,我们可以在一段时间内在一个单一有序集合中跟踪用户的所有请求。

假设我们在指定的T时间内限制请求到N,并且我们只在最后T时间内存储一个请求日志,并判断在最后T时间内总的请求数是否每次请求到达时超过阈值。

实现如下：

滑板可以避免突然流动,实现更精确的限流;更灵活,可以支持更复杂的约束,如多级限流，每分钟不超过100次,不超过每小时300次,每天不超过100次,我们只需要保存过去24小时的所有请求日志。

灵活性并不无成本,其缺点是它占有比其他限制流算法更多的存储空间。

分布式限流

以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的，但是由于机器性能，流量分布不均以及计算数量动态变化等问题，单机限流在分布式场景中的效果总是差强人意。

实现分布式边界流的最简单的方法是使用集中存储,其中一个单台计算机的边界流存储在同一存储空间的本地数据中,例如一般的雷迪斯等。

当然,也可以从上流输入限制流量,恩金克斯代理服务提供限制模块,也可以实现高性能、准确的限制流量,其下层是泄漏桶算法。

总结

固定窗口算法简单高效,但存在一个关键的突然流问题,即最大瞬态流可以达到阈值的两倍。

为了解决临界突然流动问题,窗口可以分成几个较细粒度的单元,每个窗口可以移动一个单元到右边,因此有一个滑动窗口算法。

当流动达到阈值时,滑动窗口立刻将流动切断,导致流动不够平滑。

如果您想达到一个限度流量,请不要将流量按住以使流量更平滑? 考虑泄漏桶算法! 注意泄漏桶算法通常会配置用于实现限度流量的FIFO队列。

由于定速,即使在某些情况下,下游处理的超能力也无法很好地使用。这是泄漏桶算法的一个短板。

限流和瞬时流量其实并不矛盾，在大多数场景中，短时间突发流量系统是完全可以接受的。令牌桶算法就是不二之选了，令牌桶以固定的速率v产生令牌放入一个固定容量为n的桶中，当请求到达时尝试从桶中获取令牌。

当桶满时,最大瞬时流量允许为n;当桶中没有剩余流量时,限速是最低的,为许可证生成的速度是v。

如何实现更灵活的多层次限制流程? 了解滑动记录限制流程算法! 在这里的记录是请求时间标记,计算在执行灵活限制流程期间的请求总数。

当然,由于需要存储时间标记信息,它的存储空间比其他限制流算法大得多。

不管黑猫白猫，能抓到老鼠的就是好猫。限流算法并没有绝对的好劣之分，如何选择合适的限流算法呢？不妨从性能，是否允许超出阈值，落地成本，流量平滑度，是否允许突发流量以及系统资源大小限制多方面考虑。

当然，市场上还有更成熟的限制工具和框架。例如,基于Google的Guava的许可证桶的有限流量组件,把它当作理所当然; Sentinel,一个开放源代码、分布式服务架构的交通控制框架,将使你更爱上它。基于滑动窗口的实现

XTw.com.Cn系统网专业应用软件下载教程，免费windows10系统,win11,办公软件,OA办公系统,OA软件,办公自动化软件,开源系统,移动办公软件等信息，解决一体化的办公方案。