Yuxu Ge
文章 · 2026-02-26

工业级限流器的博弈：从互斥锁到无锁原子包装

在高频调用的系统组件中，几纳秒的锁竞争往往决定了整体吞吐量的上限。限流器作为微服务和爬虫系统的守门人，常成为优化的焦点。

两种限流算法展示了同一种进阶技术的应用：原子位打包如何将令牌桶和近似滑动窗口都实现为无锁版本。位布局因算法而异，但底层的设计逻辑完全相同。

标准实现：互斥锁的安全性

令牌桶算法需要维护两个状态：

  1. LastUpdated: 上次发放令牌的时间。
  2. Tokens: 当前桶内剩余的令牌数。

多个 Goroutine 同时请求令牌时，必须保证这两个字段的修改是原子的。最直接的方法是使用 sync.Mutex。

type MutexLimiter struct {
    mu          sync.Mutex
    rate        float64 // 每秒生成的令牌数
    capacity    float64 // 桶容量
    tokens      float64 // 当前令牌数
    lastUpdated time.Time
}

func (l *MutexLimiter) Allow() bool {
    l.mu.Lock()
    defer l.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(l.lastUpdated).Seconds()
    
    // 计算新生成的令牌
    newTokens := elapsed * l.rate
    l.tokens = math.Min(l.capacity, l.tokens+newTokens)
    l.lastUpdated = now

    if l.tokens >= 1.0 {
        l.tokens -= 1.0
        return true
    }
    return false
}

这种实现简单且正确，但在高并发场景下（每秒百万次检查），Lock/Unlock 的开销会成为热点。

无锁化的挑战：一次 CAS，多个字段

要去掉锁，必须使用 CPU 提供的 CAS（Compare-And-Swap）指令，Go 的 sync/atomic 包提供了这些能力。但 CAS 有一个根本限制：它一次只能原子地修改一个变量。令牌桶的状态有两个变量——LastUpdated 与 Tokens——如果分别更新，就会出现竞态条件。

解决方案是状态压缩：将时间和令牌数"塞"进一个 64 位的整数中，然后用一次 atomic.CompareAndSwapUint64 同时更新两者。

位布局设计

一个 64 位整数分为：

// State Layout:
// [ 63 ... 24 ] [ 23 ... 0 ]
//   Timestamp     Tokens
const (
    tokenBits = 24
    tokenMask = (1 << tokenBits) - 1
    maxTokens = tokenMask
)

无锁令牌桶实现

基于原子操作的无锁限流器核心逻辑：

package throttler

import (
    "sync/atomic"
    "time"
)

type AtomicLimiter struct {
    state    uint64 // Packed state
    rate     uint64 // Tokens per second
    capacity uint64
}

func NewAtomicLimiter(rate, capacity uint64) *AtomicLimiter {
    return &AtomicLimiter{
        rate:     rate,
        capacity: capacity,
    }
}

func (l *AtomicLimiter) Allow() bool {
    for {
        // 1. 读取当前状态快照
        currState := atomic.LoadUint64(&l.state)
        
        // 解包状态
        currTime := currState >> tokenBits
        currTokens := currState & tokenMask
        
        // 2. 计算新状态
        now := uint64(time.Now().UnixMicro())
        if now < currTime {
            now = currTime // 防止时间回拨导致的计算错误
        }
        
        // 计算生成的令牌
        // 注意：这里简化了浮点运算，实际工程中可能需要定点数处理
        elapsedMicros := now - currTime
        generated := (elapsedMicros * l.rate) / 1_000_000
        
        newTokens := currTokens + generated
        if newTokens > l.capacity {
            newTokens = l.capacity
        }
        
        // 3. 尝试消费
        if newTokens >= 1 {
            newTokens -= 1
            // 打包新状态
            newState := (now << tokenBits) | (newTokens & tokenMask)
            
            // 4. CAS 提交
            if atomic.CompareAndSwapUint64(&l.state, currState, newState) {
                return true
            }
            // CAS 失败，说明有其他协程抢先修改了状态，重试循环
        } else {
            // 令牌不足，无需更新状态（或者可以选择更新时间但不扣减）
            // 这里为了简单，如果不足就不更新时间，但这会导致下次计算时 elapsed 更大
            // 更好的做法是更新时间戳，保持 tokens 不变
            newState := (now << tokenBits) | (newTokens & tokenMask)
            if atomic.CompareAndSwapUint64(&l.state, currState, newState) {
                return false
            }
        }
    }
}

第二种模式：近似滑动窗口

负载均衡器面对的是一个结构上更难的问题：以 $O(1)$ 内存统计每秒请求数（RPS）。近似滑动窗口算法通过只记录"当前窗口计数"与"上一窗口计数"，再通过线性插值估算当前速率来解决这一问题。逐条记录请求时间戳在规模化场景下代价太高。

此时状态变为三个必须保持一致的逻辑字段：

  1. 当前窗口计数（Current Counter）
  2. 上一窗口计数（Previous Counter）
  3. 窗口起始时间戳（Window Timestamp）

用互斥锁保护这三个字段虽然可行，但随着核数增加，锁争用会导致性能急剧下降。位打包的思路可以直接延伸：将三个字段压进一个 64 位机器字。

一种实用的布局方案：

读写循环遵循同样的乐观锁模式：

  1. 加载（Load）：原子读取 64 位整数。
  2. 解包（Unpack）：通过位移和掩码分离 Time、Prev、Curr。
  3. 计算（Calculate）：若当前时间已进入新窗口，将 Curr 移入 Prev，重置 Curr，更新时间戳；否则仅对 Curr 加一。
  4. 打包（Pack）：将新值重新压缩为 64 位整数。
  5. 提交（CAS）：尝试更新。若失败（其他线程抢先），则重试循环。

该滑动窗口计数器的 Go 实现：

package main

import (
	"fmt"
	"sync/atomic"
	"time"
)

// PackedCounter 展示了如何将多个状态压缩进单个 uint64
// 布局: [32-bit Timestamp] [16-bit Prev] [16-bit Curr]
type PackedCounter struct {
	state uint64
}

const (
	mask16 = (1 << 16) - 1
	shiftTime = 32
	shiftPrev = 16
)

func (c *PackedCounter) Inc(now time.Time, winSize time.Duration) {
	nowSec := uint32(now.Unix())
	winSec := uint32(winSize.Seconds())

	for {
		// 1. 原子加载
		current := atomic.LoadUint64(&c.state)
		
		// 2. 解包状态
		ts := uint32(current >> shiftTime)
		prev := uint16((current >> shiftPrev) & mask16)
		curr := uint16(current & mask16)

		var nextTs uint32
		var nextPrev, nextCurr uint16

		// 3. 计算新状态
		// 计算时间差，判断是否跨越窗口
		diff := (nowSec - ts) / winSec

		if ts == 0 { // 初始化
			nextTs = nowSec
			nextCurr = 1
		} else if diff == 0 { // 同一窗口
			nextTs = ts
			nextPrev = prev
			nextCurr = curr + 1 // 注意：此处应处理溢出饱和
		} else { // 窗口轮转
			nextTs = nowSec
			// 如果仅过了一个窗口，Prev 继承 Curr；否则重置为 0
			if diff == 1 {
				nextPrev = curr
			} else {
				nextPrev = 0
			}
			nextCurr = 1
		}

		// 4. 打包并 CAS 提交
		nextState := (uint64(nextTs) << shiftTime) | 
		             (uint64(nextPrev) << shiftPrev) | 
					 uint64(nextCurr)
					 
		if atomic.CompareAndSwapUint64(&c.state, current, nextState) {
			return
		}
		// CAS 失败则自动重试
	}
}

权衡与取舍

两种模式都以精度换性能。代价是具体的，值得从四个维度逐一审视。

精度损失。 位宽限制导致无法存储浮点数令牌（如 0.5 个），只能处理整数。滑动窗口的 16 位计数字段将单窗口最大计数限制在 65,535；对于百万 RPS 级别的流量，这会静默溢出。如果字段可以拓宽，令牌桶中 40 位时间戳所腾出的空间比 32 位方案更充裕。

溢出风险。 时间戳的位数决定了系统运行多久后会产生回绕（Wrap Around）。两种设计都需要显式处理这一事件——它不是可以推迟的边界情况。

ABA 问题。 CAS 能检测值是否发生变化，但无法得知变化的过程。在纯整数打包的场景下，值回到原始位模式通常不构成逻辑错误，因为我们关心的是数值状态的正确流转。但若打包的是指针（在其他语言中偶有出现），则必须引入版本号（Version Tag）来规避悬挂指针风险。

CPU 空转与总线风暴。 在持续高竞争下，CAS 失败率升高会使重试循环消耗大量 CPU 周期。在关键点配合 runtime.Gosched() 让出处理器可以缓解争用。在硬件层面，多核频繁的 CAS 失败会制造大量总线流量——即"总线风暴"——即便单次操作本身很快，也会损害缓存一致性性能。若需要对三个或更多 32 位字段进行原子操作，x86 提供了 128 位原子指令（CMPXCHG16B），但 Go 的 sync/atomic 标准库并未原生暴露这一能力；届时设计要么接受 64 位字段的约束，要么绕开标准库。

总结

从互斥锁到原子操作的演进，不仅仅是 API 的替换，更是数据结构设计的重构。令牌桶与近似滑动窗口诠释了同一套设计原则：将多字段状态压缩进单个机器字，再用一次 CAS 提交。位布局因算法而异——令牌桶用 40+24，滑动窗口用 32+16+16——这源于两者的精度需求和字段数量不同，而非技术本身的差异。

在许多工业级组件（如 Nginx 的限流模块、高性能 RPC 框架、负载均衡器内核）中，都能看到类似"状态压缩"的设计。掌握这种位操作技巧，是通往底层系统开发的必经之路。

© 2026 Yuxu Ge ·