.NET固定时间窗口算法实现（无锁线程安全）

一.前言

最近有一个生成 APM TraceId 的需求，公司的APM系统的 TraceId 的格式为：APM AgentId+毫秒级时间戳+自增数字，根据此规则生成的 Id 可以保证全局唯一（有 NTP 时间同步），前两个字段好说，最后一个字段也不复杂，我的想法是按秒来进行自增。比如说1秒的时候，自增计数为100，在2秒的时候会重置为0，然后进行自增。其实这个思想就是固定时间窗口算法，这个算法一般常用在限流、Id生成器等场景。

二.代码实现

long _currentTime;long _current;public long FixedWindow(){    var now = DateTimeOffset.Now.ToUnixTimeSeconds();    var ct = Interlocked.Read(ref _currentTime);    if (now > ct)    {        if (Interlocked.CompareExchange(ref _currentTime, now, ct)==ct)        {            return Interlocked.Exchange(ref _current, 0);        }    }        return Interlocked.Increment(ref _current);}

代码没多少，每调用一次就返回计数，采用的 C# CAS API Interlocked ，保证每个计数操作都是原子操作，从而达到无锁。

测试代码，使用10个线程并发调用，每个线程调用 1w次，最终期望计数应该是10w。

private static long _currentTime;private static long _current;private static Semaphore _semaphore = new Semaphore(0, 10);static void Main(string[] args){    _currentTime = DateTimeOffset.Now.ToUnixTimeSeconds();    _current = 0;    for (int i = 0; i < 10; i++)    {        Task.Factory.StartNew(() =>        {            for (int j = 0; j < 10000; j++)            {                FixedWindow();            }            _semaphore.Release(1);        });    }    for (int i = 0; i < 10; i++)    {        _semaphore.WaitOne();    }        Console.WriteLine(_current);    Console.WriteLine("sleep 2s");    Thread.Sleep(2000);    Console.WriteLine(FixedWindow());}

执行结果：

符合预期，10线程的计数在 1s 内能执行完毕，所以最终计数是10w，然后sleep 2s，重置计数，再次调用就返回了 1

三.资料

本文 Demo 代码：github