滑动窗口算法用于应答申请在工夫周期中散布不平均的状况，可能更准确的应答流量变动，比拟驰名的利用场景就是 TCP 协定的流量管制，不过明天要说的是服务限流场景中的利用。

算法原理

这里假如业务须要每秒钟限流 100 次，先来看固定窗口算法的两个问题：

• 漏检

如下图所示，单看第 1 秒和第 2 秒，其申请次数都没有超过 100，所以应用固定窗口算法时不会触发限流。然而第 1 秒的后 500ms 的申请数加上第 2 秒的前 500 毫秒的申请数就超过了 100，这时候可能会给零碎带来挫伤，应用固定窗口算法时不能检测到这种状况。

• 太刚

针对漏检的问题，你可能会说，能够把工夫窗口设置为 500ms，把限流阈值设置为 50。那么来看下图，除了第 2 个计数周期超过了 50，从而触发限流，前后几个计数周期的申请都很失常，甚至都不会超过阈值的 50%，可能第 2 个计数周期的状况切实太非凡，1 天都不会呈现第 2 次，如果对系统不会造成影响，能不能通融下，做不到！固定窗口算法这时候就会显得太过刚性。

那么滑动窗口如何来解决这两个问题呢？还是先来看图：

如上图所示：

• 滑动窗口的时间跨度是 1 秒，每个小计数周期的时间跨度是 500ms，此处的滑动窗口蕴含 2 个小计数周期。
• 随着工夫的后退，滑动窗口蕴含的小计数周期会以 500ms 为单位向前挪动，但始终是蕴含 2 个小计数周期。
• 判断是否限流时，须要将以后滑动窗口蕴含的 2 个小计数周期的计数值加起来。
• 相比固定窗口计数器算法，滑动窗口能够无效缩小漏检，如上图滑动窗口挪动到了 500-1500ms，发现总数超过 100，则触发限流；滑动窗口在 0 -1000ms、1000-2000ms 时都不会触发限流，即便其中某个小周期的计数值超过了阈值的半数，然而总数没有超过 100，就不会限流，可能应答极少呈现的突发流量状况。

从剖析还能够看出，滑动窗口的小周期划分的越多，则检测越精确，但用于跟踪的计数也越多，应用的内存和计算量都会增大。

算法实现

这里讲两种实现办法：过程内即内存滑动窗口算法、基于 Redis 的滑动窗口算法。

过程内即内存滑动窗口算法

这里介绍一种性能比拟高的办法，应用数组实现滑动窗口，这是环形队列的一种特例，如下图所示：

• 假如滑动窗口须要 5 个小的计数周期，则初始化一个长度为 5 的整形数组，数字示意数组中的第几个元素。
• 咱们晓得队列有头有尾，从队头取出数据，向队尾插入数据，带括号的数字示意是队列中的第几个元素。
• 滑动窗口向前挪动时，队尾向右挪动 1 位，同时队头也向右挪动 1 位。
• 队尾和队头向右挪动都可能会溢出数组，此时让它们回到数组的起始地位，即图中数组的第 1 个地位。

对于这个算法的具体介绍，能够看这篇文章：如何应用数组实现滑动窗口

基于 Redis 的滑动窗口算法

基于 Redis 时也能够应用相似环形队列的办法，比方定义 5 个 KV 作为数组的 5 个元素。不过我之前实现时采纳了一种更直观的形式，每个小的计数周期都创立一个 KV，同时设置一个相对超过滑动窗口时间跨度的过期工夫，用不到的小计数周期不会始终占用内存；判断是否触发限流时，把这些小滑动窗口的计数值累加起来就能够了。当然理论实现时还须要欠缺一些细节上的解决，比方怎么找到这些小计数周期，会有多种计划，存起来或者长期计算都能够。

这些操作逻辑能够封装在一个 Lua script 中，因为 Lua script 在 Redis 中执行时也是原子操作，所以 Redis 的限流计数在分布式部署时人造就是精确的。

利用算法

这里以限流组件 FireflySoft.RateLimit 为例，实现 ASP.NET Core 中的滑动窗口限流。

1、装置 Nuget 包

有多种装置形式，抉择本人喜爱的就行了。

包管理器命令：

Install-Package FireflySoft.RateLimit.AspNetCore

或者.NET 命令:

dotnet add package FireflySoft.RateLimit.AspNetCore

或者我的项目文件间接增加：

<ItemGroup>
<PackageReference Include="FireflySoft.RateLimit.AspNetCore" Version="2.*" />
</ItemGroup>

2、 应用中间件

在 Startup 中应用中间件，演示代码如下（下边会有具体阐明）：

public void ConfigureServices(IServiceCollection services)
        {
           ...
           app.AddRateLimit(new InProcessSlidingWindowAlgorithm(new[] {
                        // 构造函数有两个参数：滑动窗口的工夫长度、小计数周期的工夫长度
                    new SlidingWindowRule(TimeSpan.FromSeconds(5), TimeSpan.FromSeconds(1))
                    {
                        ExtractTarget = context =>
                        {
                                // 提取限流指标
                            return (context as HttpContext).Request.Path.Value;
                        },
                        CheckRuleMatching = context =>
                        {
                                // 判断以后申请是否须要限流解决
                            return true;
                        },
                        Name="sliding window limit rule",
                        LimitNumber=100, // 限流阈值，这里即 5 秒最多 100 次申请
                    }
                })
            );
            ...
        }

public void Configure(IApplicationBuilder app, IWebHostEnvironment env)
        {
            ...
            app.UseRateLimit();
            ...
        }

如上须要先注册服务，而后应用中间件。

注册服务的时候须要提供限流算法和对应的规定：

• 这里应用过程内固定窗口算法 InProcessSlidingWindowAlgorithm，还能够应用 RedisSlidingWindowAlgorithm，须要传入一个 Redis 连贯。两种算法都反对同步和异步办法。
• 限流阈值是 100，限流滑动窗口是 5 秒，小计数周期是 1 秒。
• ExtractTarget 用于提取限流指标，这里是每个不同的申请 Path。如果有 IO 申请，这里还反对对应的异步办法 ExtractTargetAsync。
• CheckRuleMatching 用于验证以后申请是否限流。如果有 IO 申请，这里还反对对应的异步办法 CheckRuleMatchingAsync。
• 默认被限流时会返回 HttpStatusCode 429，能够在 AddRateLimit 时应用可选参数 error 自定义这个值，以及 Http Header 和 Body 中的内容。

根本的应用就是上边例子中的这些了。

如果还是基于传统的.NET Framework，则须要在 Application_Start 中注册一个音讯处理器 RateLimitHandler，算法和规定局部都是共用的，具体能够看 Github 上的应用阐明：https://github.com/bosima/Fir…

FireflySoft.RateLimit 是一个基于 .NET Standard 的限流类库，其内核简略笨重，可能灵便应答各种需要的限流场景。

其次要特点包含：

• 多种限流算法：内置固定窗口、滑动窗口、漏桶、令牌桶四种算法，还可自定义扩大。
• 多种计数存储：目前反对内存、Redis 两种存储形式。
• 分布式敌对：通过 Redis 存储反对分布式程序对立计数。
• 限流指标灵便：能够从申请中提取各种数据用于设置限流指标。
• 反对限流惩办：能够在客户端触发限流后锁定一段时间不容许其拜访。
• 动静更改规定：反对程序运行时动静更改限流规定。
• 自定义谬误：能够自定义触发限流后的错误码和谬误音讯。
• 普适性：原则上能够满足任何须要限流的场景。

Github 开源地址：https://github.com/bosima/Fir…

播种更多架构常识，请关注公众号 萤火架构。原创内容，转载请注明出处。