之前開發(fā)的一款基于OpenTelemetry的Tracing組件需要使用基于速率限制（Rate Limiting）的跟蹤采樣策略，本想使用現(xiàn)有的解決方案，比如System.Threading.RateLimiting命名空間下的RateLimiter。大體看了RateLimiter的三種實(shí)現(xiàn)（固定窗口、滑動窗口和令牌桶），覺得過于相對復(fù)雜了點(diǎn)，代碼還涉及到鎖，而且提供的功能我也不太需要，于是嘗試實(shí)現(xiàn)一種簡單且無鎖解決方案。gga28資訊網(wǎng)——每日最新資訊28at.com

一、滑動時(shí)間窗口

我為RateLimiter定義了如下這個(gè)簡單的IRateLimiter接口，唯一的無參方法TryAcquire利用返回的布爾值確定當(dāng)前是否超出設(shè)定的速率限制。我只提供的兩種基于時(shí)間窗口的實(shí)現(xiàn)，如下所示的基于“滑動時(shí)間窗口”的實(shí)現(xiàn)類型SliddingWindowRateLimiter，我們在構(gòu)造的時(shí)候指定時(shí)間窗口和閾值。SliddingWindowRateLimiter采用一種“討巧”的實(shí)現(xiàn)，它直接利用了BoundedChannel<DateTimeOffset>對象，我們將指定的閾值作為它的最大容量。gga28資訊網(wǎng)——每日最新資訊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();            }        }    }}

在實(shí)現(xiàn)的TryAcquire方法中，我們試著將當(dāng)前時(shí)間戳寫入這個(gè)Channel，并將寫入的結(jié)果（成功或者失敗）作為返回值。為了讓Channel中只包含指定時(shí)間窗口的時(shí)間戳，我們利用一個(gè)LongRuning的Task執(zhí)行Trim方法對過期的時(shí)間戳進(jìn)行“裁剪”。Trim會調(diào)用ChannelReader的TRyPeek方法，如果返回False，意味著Channel為空，此時(shí)會等待一段窗口時(shí)間再進(jìn)行“裁剪”。如果提取出來時(shí)間戳在Now-Window與當(dāng)前時(shí)間之間，意味著Channel里面的時(shí)間戳均在設(shè)定的窗口內(nèi)，此時(shí)同樣需要等待，等待時(shí)間為Window - (Now - Timestamp)；只有在提取的時(shí)間超出窗口范圍，我們才需要將其從Channel中移除。gga28資訊網(wǎng)——每日最新資訊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)}");            }         }    })));

我們在上面的演示程序中使用這個(gè)SliddingWindowRateLimiter，設(shè)定的限速規(guī)則為 2/2s。我們創(chuàng)建了100個(gè)Task并發(fā)地調(diào)用這個(gè)SliddingWindowRateLimiter，并將它返回True時(shí)的時(shí)間戳顯示出來，具體輸出如下所示。gga28資訊網(wǎng)——每日最新資訊28at.com

圖片gga28資訊網(wǎng)——每日最新資訊28at.com

二、固定時(shí)間窗口

如下這個(gè)FixedWindowRateLimiter類型是針對“固定窗口”的實(shí)現(xiàn)，字段_windowTicks和_permit同樣表示時(shí)間窗口的時(shí)長（這里我們使用Int64類型的Ticks屬性）和閾值。_nextWindowStartTimeTicks表示下一次固定窗口的起始時(shí)間，這個(gè)需要動態(tài)調(diào)整，為了確保只有一個(gè)線程能夠修改它，我們定義了_windowReseting這個(gè)“信號量”。_count是一個(gè)計(jì)數(shù)器，我們使用它確定是否“超速”。gga28資訊網(wǎng)——每日最新資訊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()    {        // 超出時(shí)間窗口，重置計(jì)數(shù)器，并調(diào)整下一個(gè)時(shí)間窗口的開始時(shí)間        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;    }}

在實(shí)現(xiàn)的TryAcquire方法中，我們先確定當(dāng)前時(shí)間是否超過了設(shè)定的“下一個(gè)窗口開始時(shí)間”，如果是則調(diào)用Interlocked.CompareExchange方法修改__nextWindowStartTimeTicks字段。成功修改__nextWindowStartTimeTicks的線程會調(diào)整窗口開始時(shí)間，并重置計(jì)數(shù)器_count為1，并返回True。如果計(jì)數(shù)器大于等于設(shè)定閾值，方法返回False。否則我們讓計(jì)數(shù)器+1，如果該值<=閾值，返回True，否則返回False。gga28資訊網(wǎng)——每日最新資訊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應(yīng)用到上面的演示程序，依然能得到我們希望的輸出結(jié)果。gga28資訊網(wǎng)——每日最新資訊28at.com

圖片 gga28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-17896-0.html兩種基于時(shí)間窗口的限流器的簡單實(shí)現(xiàn)

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 快速入門 | 輕松掌握Hystrix實(shí)現(xiàn)資源隔離保護(hù)系統(tǒng)穩(wěn)定

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