本篇内容主要讲解“ASP.NET 核心中使用滑动窗口限流的问题举例分析”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“ASP.NET 核心中使用滑动窗口限流的问题举例分析”吧!
滑动窗口算法用于应对请求在时间周期中分布不均匀的情况,能够更精确的应对流量变化,比较著名的应用场景就是TCP协议的流量控制,不过今天要说的是服务限流场景中的应用。
算法原理
这里假设业务需要每秒钟限流100次,先来看固定窗口算法的两个问题:
漏检
如下图所示,单看第1秒和第2秒,其请求次数都没有超过100年,所以使用固定窗口算法时不会触发限流。但是第1秒的后500毫秒的请求数加上第2秒的前500毫秒的请求数就超过了100年,这时候可能会给系统带来伤害,使用固定窗口算法时不能检测到这种情况。
太刚
针对漏检的问题,你可能会说,可以把时间窗口设置为500毫秒,把限流阈值设置为50。那么来看下图,除了第2个计数周期超过了50岁,从而触发限流,前后几个计数周期的请求都很正常,甚至都不会超过阈值的50%,可能第2个计数周期的情况实在太特殊,一天都不会出现第2次,如果对系统不会造成影响,能不能通融下,做不到!固定窗口算法这时候就会显得太过刚性。
那么滑动窗口如何来解决这两个问题呢?还是先来看图:
如上图所示:
滑动窗口的时间跨度是1秒,每个小计数周期的时间跨度是500 ms,此处的滑动窗口包含2个小计数周期。
<李>随着时间的前进,滑动窗口包含的小计数周期会以500 ms为单位向前移动,但始终是包含2个小计数周期。
<李>判断是否限流时,需要将当前滑动窗口包含的2个小计数周期的计数值加起来。
<李>相比固定窗口计数器算法,滑动窗口可以有效减少漏检,如上图滑动窗口移动到了500 - 1500 ms,发现总数超过100年,则触发限流;滑动窗口在0 - 1000 ms, 1000 - 2000毫秒时都不会触发限流,即使其中某个小周期的计数值超过了阈值的半数,但是总数没有超过100年,就不会限流,能够应对极少出现的突发流量情况。
从分析还可以看的出,滑动窗口的小周期划分的越多,则检测越准确,但用于跟踪的计数也越多,使用的内存和计算量都会增大。
算法实现
这里讲两种实现方法:进程内即内存滑动窗口算法,基于复述的滑动窗口算法。
进程内即内存滑动窗口算法
这里介绍一种性能比较高的方法,使用数组实现滑动窗口,这是环形队列的一种特例,如下图所示:
假设滑动窗口需要5个小的计数周期,则初始化一个长度为5的整形数组,数字表示数组中的第几个元素。
<李>我们知道队列有头有尾,从队头取出数据,向队尾插入数据,带括号的数字表示是队列中的第几个元素。
<李>滑动窗口向前移动时,队尾向右移动1位,同时队头也向右移1位动。
<李>队尾和队头向右移动都可能会溢出数组,此时让它们回到数组的起始位置,即图中数组的第1个位置。
关于这个算法的详细介绍,可以看这篇文章:如何使用数组实现滑动窗口
基于复述的滑动窗口算法
基于复述时也可以使用类似环形队列的方法,比如定义5个KV作为数组的5个元素,不过我之前实现时采用了一种更直观的方式,每个小的计数周期都创建一个KV,同时设置一个绝对超过滑动窗口时间跨度的过期时间,用不到的小计数周期不会一直占用内存;判断是否触发限流时,把这些小滑动窗口的计数值累加起来就可以了。当然实际实现时还需要完善一些细节上的处理,比如怎么找到这些小计数周期,会有多种方案,存起来或者临时计算都可以。
这些操作逻辑可以封装在一个Lua脚本中,因为Lua脚本在复述中执行时也是原子操作,所以复述的限流计数在分布式部署时天然就是准确的。
