.NET/JAVA/GO 固定时间窗口算法实现（无锁线程安全）
<h2 id="一前言">一.前言</h2><p>最近有一个生成 APM TraceId 的需求，公司的APM系统的 TraceId 的格式为：<code>APM AgentId+毫秒级时间戳+自增数字</code>，根据此规则生成的 Id 可以保证全局唯一（有 NTP 时间同步），前两个字段好说，最后一个字段也不复杂，我的想法是按秒来进行自增。比如说1秒的时候，自增计数为100，在2秒的时候会重置为0，然后进行自增。其实这个思想就是固定时间窗口算法，这个算法一般常用在限流、Id生成器等场景。</p>
<h2 id="二-net-代码实现">二. .NET 代码实现</h2>
<pre><code class="language-csharp">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);
}
</code></pre>
<p>代码没多少，每调用一次就返回计数，采用的 C# CAS APIInterlocked ，保证每个计数操作都是原子操作，从而达到无锁。</p>
<p>测试代码，使用10个线程并发调用，每个线程调用 1w次，最终期望计数应该是10w。</p>
<pre><code class="language-csharp">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());
}
</code></pre>
<p>执行结果：</p>
<p><img src="https://img2022.cnblogs.com/blog/668104/202202/668104-20220217141527000-1632776314.png" alt="image-20220217141347106" loading="lazy"></p>
<p>符合预期，10线程的计数在 1s 内能执行完毕，所以最终计数是10w，然后sleep 2s，重置计数，再次调用就返回了 1</p>
<h2 id="三java代码实现">三.JAVA代码实现</h2>
<pre><code class="language-java">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;
}
</code></pre>
<p>测试代码：</p>
<pre><code class="language-java">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());
}
</code></pre>
<p>执行结果：</p>
<p><img src="https://img2022.cnblogs.com/blog/668104/202202/668104-20220218105801781-1683737447.png" alt="" loading="lazy"></p>
<p>符合预期，但是以上代码用在生产环境，需要自定替换 currentTimeSeconds 方法的实现，不能每次都调用 System.currentTimeMillis()，在多线程同时调用下，会有性能问题，可以自己实现一个定时器来返回当前时间</p>
<h2 id="四go代码实现">四.GO代码实现</h2>
<pre><code class="language-go">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()
}
</code></pre>
<p>测试代码：</p>
<pre><code class="language-go">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())
}
</code></pre>
<p>执行结果：</p>
<p><img src="https://img2022.cnblogs.com/blog/668104/202202/668104-20220218111635070-274618305.png" alt="" loading="lazy"></p>
<p>符合预期，10个协程的计数在 1s 内能执行完毕，所以最终计数是10w，然后sleep 2s，重置计数，再次调用就返回了 1</p>
<h2 id="五资料">五.资料</h2>
<p>本文 Demo 代码：github</p>
</div>
<div id="MySignature" role="contentinfo">
<blockquote>
<strong>目前学习.NET Core 最好的教程 .NET Core 官方教程 ASP.NET Core 官方教程</strong>
</blockquote><br><br>
来源：https://www.cnblogs.com/stulzq/p/15904454.html
頁:
[1]