前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >.NET/JAVA/GO 固定时间窗口算法实现(无锁线程安全)

.NET/JAVA/GO 固定时间窗口算法实现(无锁线程安全)

作者头像
晓晨
发布2022-05-07 19:05:07
3010
发布2022-05-07 19:05:07
举报
文章被收录于专栏:晓晨的专栏晓晨的专栏

一.前言

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

二. .NET 代码实现

代码语言:javascript
复制
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)
        {
            Interlocked.Exchange(ref _current, 0);
        }
    }
    
    return Interlocked.Increment(ref _current);
}

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

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

代码语言:javascript
复制
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());
}

执行结果:

image-20220217141347106
image-20220217141347106

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

三.JAVA代码实现

代码语言:javascript
复制
static AtomicLong currentTime = new AtomicLong();
static AtomicLong currentNumber = new AtomicLong();

public static long fixedWindow() {
    long now = currentTimeSeconds();
    long ct = currentTime.get();
    if (now > ct) {
        if (currentTime.compareAndSet(ct, now)) {
            currentNumber.set(0);
        }
    }

    return currentNumber.incrementAndGet();
}

public static long currentTimeSeconds(){
    return System.currentTimeMillis() / 1000;
}

测试代码:

代码语言:javascript
复制
public static void main(String[] args) throws InterruptedException {
    currentTime.set(currentTimeSeconds());
    currentNumber.set(0);

    long num = 0;
    for (int i = 0; i < 1000; i++) {
        num = fixedWindow();
    }
    System.out.println(num);
    Thread.sleep(2000);
    System.out.println(fixedWindow());
}

执行结果:

符合预期,但是以上代码用在生产环境,需要自定替换 currentTimeSeconds 方法的实现,不能每次都调用 System.currentTimeMillis(),在多线程同时调用下,会有性能问题,可以自己实现一个定时器来返回当前时间

四.GO代码实现

代码语言:javascript
复制
var currentTime atomic.Int64
var currentNumber atomic.Int64

func fixedWindow() int64 {
	now := time.Now().Unix()
	ct := currentTime.Load()
	if now > ct {
		if currentTime.CAS(ct, now) {
			currentNumber.Store(0)
		}
	}

	return currentNumber.Inc()

}

测试代码:

代码语言:javascript
复制
func main() {
	wg := sync.WaitGroup{}
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func() {
			for j := 0; j < 10000; j++ {
				fixedWindow()
			}
			wg.Done()
		}()
	}
	wg.Wait()
	fmt.Println(currentNumber.Load())
	time.Sleep(2 * time.Second)
	fmt.Println(fixedWindow())
}

执行结果:

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

五.资料

本文 Demo 代码:github

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-02-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一.前言
  • 二. .NET 代码实现
  • 三.JAVA代码实现
  • 四.GO代码实现
  • 五.资料
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档