两种基于时间窗口的限流器的简单实现

之前开发的一款基于OpenTelemetry的Tracing组件需要使用基于速率限制（Rate Limiting）的跟踪采样策略，本想使用现有的解决方案，比如System.Threading.RateLimiting命名空间下的RateLimiter。大体看了RateLimiter的三种实现（固定窗口、滑动窗口和令牌桶），觉得过于相对复杂了点，代码还涉及到锁，而且提供的功能我也不太需要，于是尝试实现一种简单且无锁解决方案。F0628资讯网——每日最新资讯28at.com

一、滑动时间窗口

我为RateLimiter定义了如下这个简单的IRateLimiter接口，唯一的无参方法TryAcquire利用返回的布尔值确定当前是否超出设定的速率限制。我只提供的两种基于时间窗口的实现，如下所示的基于“滑动时间窗口”的实现类型SliddingWindowRateLimiter，我们在构造的时候指定时间窗口和阈值。SliddingWindowRateLimiter采用一种“讨巧”的实现，它直接利用了BoundedChannel<DateTimeOffset>对象，我们将指定的阈值作为它的最大容量。F0628资讯网——每日最新资讯28at.com

public interface IRateLimiter{    bool TryAcquire();}public sealed class SliddingWindowRateLimiter: IRateLimiter{    private readonly TimeSpan _window;    private readonly ChannelReader<DateTimeOffset> _reader;    private readonly ChannelWriter<DateTimeOffset> _writer;    public SliddingWindowRateLimiter(TimeSpan window, int permit)    {        _window = window;        var options = new BoundedChannelOptions (permit)        {            FullMode = BoundedChannelFullMode.Wait,            SingleReader = false,            SingleWriter = true        };        var channel = Channel            .CreateBounded<DateTimeOffset>(options);        _reader = channel.Reader;        _writer = channel.Writer;        Task.Factory.StartNew(            Trim,TaskCreationOptions.LongRunning);    }    public bool TryAcquire()     => _writer.TryWrite(DateTimeOffset.UtcNow);    private void Trim()    {        if (!_reader.TryPeek(out var timestamp))        {            Task.Delay(_window).Wait();            Trim();        }        else        {            var delay = _window                 - (DateTimeOffset.UtcNow - timestamp);            if (delay > TimeSpan.Zero)            {                Task.Delay(delay).Wait();                Trim();            }            else            {                var valueTask = _reader.ReadAsync();                if (!valueTask.IsCompleted)                     _ = valueTask.Result;                Trim();            }        }    }}

在实现的TryAcquire方法中，我们试着将当前时间戳写入这个Channel，并将写入的结果（成功或者失败）作为返回值。为了让Channel中只包含指定时间窗口的时间戳，我们利用一个LongRuning的Task执行Trim方法对过期的时间戳进行“裁剪”。Trim会调用ChannelReader的TRyPeek方法，如果返回False，意味着Channel为空，此时会等待一段窗口时间再进行“裁剪”。如果提取出来时间戳在Now-Window与当前时间之间，意味着Channel里面的时间戳均在设定的窗口内，此时同样需要等待，等待时间为Window - (Now - Timestamp)；只有在提取的时间超出窗口范围，我们才需要将其从Channel中移除。F0628资讯网——每日最新资讯28at.com

var limiter = new SliddingWindowRateLimiter(    TimeSpan.FromSeconds(2),2);var index = 0;await Task.WhenAll( Enumerable.Range(1, 100)    .Select(_ => Task.Run(() => {        while (true)        {            if (limiter.TryAcquire())            {                Console.WriteLine(                    $"[{DateTimeOffset.Now}]{Interlocked.Increment(ref index)}");            }         }    })));

我们在上面的演示程序中使用这个SliddingWindowRateLimiter，设定的限速规则为 2/2s。我们创建了100个Task并发地调用这个SliddingWindowRateLimiter，并将它返回True时的时间戳显示出来，具体输出如下所示。F0628资讯网——每日最新资讯28at.com

图片F0628资讯网——每日最新资讯28at.com

二、固定时间窗口

如下这个FixedWindowRateLimiter类型是针对“固定窗口”的实现，字段_windowTicks和_permit同样表示时间窗口的时长（这里我们使用Int64类型的Ticks属性）和阈值。_nextWindowStartTimeTicks表示下一次固定窗口的起始时间，这个需要动态调整，为了确保只有一个线程能够修改它，我们定义了_windowReseting这个“信号量”。_count是一个计数器，我们使用它确定是否“超速”。F0628资讯网——每日最新资讯28at.com

public sealed class FixedWindowRateLimiter : IRateLimiter{    private readonly long _windowTicks;    private readonly int _permit;    private long _nextWindowStartTimeTicks;    private volatile int _count = 0;    public FixedWindowRateLimiter(TimeSpan window, int permit)    {        _windowTicks = window.Ticks;        _permit = permit;        _nextWindowStartTimeTicks             = DateTimeOffset.UtcNow.Add(window).Ticks;    }    public bool TryAcquire()    {        // 超出时间窗口，重置计数器，并调整下一个时间窗口的开始时间        var now = DateTimeOffset.UtcNow.Ticks;        var nextWindowStartTimeTicks = nextWindowStartTimeTicks;        if (now >= nextWindowStartTimeTicks             && Interlocked.CompareExchange(            ref _nextWindowStartTimeTicks            , now + _windowTicks, nextWindowStartTimeTicks)             == nextWindowStartTimeTicks)        {            Interlocked.Exchange(ref _count, 1);            return true;        }        return _count < _permit             && Interlocked.Increment(ref _count) <= _permit;    }}

在实现的TryAcquire方法中，我们先确定当前时间是否超过了设定的“下一个窗口开始时间”，如果是则调用Interlocked.CompareExchange方法修改__nextWindowStartTimeTicks字段。成功修改__nextWindowStartTimeTicks的线程会调整窗口开始时间，并重置计数器_count为1，并返回True。如果计数器大于等于设定阈值，方法返回False。否则我们让计数器+1，如果该值<=阈值，返回True，否则返回False。F0628资讯网——每日最新资讯28at.com

IRateLimiter limiter = new FixedWindowRateLimiter(    window: TimeSpan.FromSeconds(2), permit: 2);var index = 0;await Task.WhenAll( Enumerable.Range(1, 100)    .Select(_ => Task.Run(() => {        while (true)        {            if (limiter.TryAcquire())            {                Console.WriteLine(                    $"[{DateTimeOffset.Now}]{Interlocked.Increment(ref index)}");            }               }    })));

将FixedWindowRateLimiter应用到上面的演示程序，依然能得到我们希望的输出结果。F0628资讯网——每日最新资讯28at.com

图片 F0628资讯网——每日最新资讯28at.com

本文链接：http://www.28at.com/showinfo-26-17896-0.html两种基于时间窗口的限流器的简单实现

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇： 快速入门 | 轻松掌握Hystrix实现资源隔离保护系统稳定

下一篇： IntelliJ IDEA 一些不为人知的功能