算法与数据结构 / 无锁写入的三步与 alignas 布局 待审核
FastQueue::write()

无锁写入的三步与 alignas 布局

counter 是绝对偏移（一直累加的 uint64_t），取 % CAP 才映射到 buffer 的物理槽位。绝对偏移免去了「指针绕回之后无法判别先后」的麻烦：两个 counter 的差值就是在途写入的长度。producer 不设背压、从不等待 consumer，写满一圈即覆盖最旧的数据。

1 · 一次写入的三步

一次 write() 的三步顺序是固定的：先推进 mWriteCounter 把即将写的区间标为写入中，再把数据拷进去，最后推进 mReadCounter 发布。

图 1-1 · 单步跟一次写入。绿色是可读区、斜纹是正在写入区（此刻对 readers 不可见）；可逐帧前进，观察两个 counter 如何把 buffer 切成两段，以及第 5 条消息如何绕过 buffer 末尾。

注 · 三步的顺序决定了 readers 看到什么。推进 mWriteCounter 等于抢先声明 [r, r+n) 这段作废，此后开始读的 consumer 会看到它属于写入区而跳过；数据拷完再推进 mReadCounter，这一步才是「发布」。承担可见性的也只有第二个 store：它的 release 必须与 consumer 侧对 mReadCounter 的 acquire 载入配对，才能保证拷贝的字节先于新 counter 可见。第一个 store 需要的是 store-store 次序，release 给不了这层保证——x86-64 的 TSO 模型下普通 store 之间本就不重排，可移植的写法要在其后插一道 atomic_thread_fence。

警示 ·「跳过写入区」拦不住所有撕裂。反例：consumer 在 producer 推进 W 之前已判定某段可读并开始拷出，producer 随即推进 W 覆写同一段——前置检查一律拦不住这种「读时合法、拷贝中被追尾」。这类不等待的 SPMC 队列靠事后校验：consumer 拷完再取一次 counter，发现自己被套圈就丢弃重来。代价是慢 consumer 会丢消息，本设计没有投递保证。

注 · 页面代码里的 % CAP 是为可读性写的。真实实现会把容量取 2 的幂，用 & (CAP - 1) 代替取模——非 2 的幂时 % 是硬件除法，几十个周期，在纳秒级路径上首先要被干掉。同理，跨界的那次拷贝要拆成两段 memcpy，单次连续拷贝会越过 mBuffer 末尾。

2 · alignas 与 false sharing

CPU 缓存以 cache line（通常 64 字节）为单位。若两个 counter 落在同一条 cache line,producer 改 mWriteCounter 会让整条 line 失效——即便 consumer 只想读 mReadCounter，也被迫从内存 / 远核重新加载。这就是 false sharing（伪共享）。与教科书里「两个线程各写各的变量」不同，本设计是单 producer 写两个 counter、consumer 只读，失效同样发生。

图 2-1 · 紧凑布局与 alignas 分行布局下 consumer 被迫重新加载的次数对照。本图只计 producer 对 mWriteCounter 的写入；发布时对 mReadCounter 的写入仍会作废 consumer 所在的那条 line，alignas 把每条消息两次失效降为一次，而非降到零。

注 · alignas 用空间换时间：每个 counter 多占大半条 cache line 的 padding，换来读写互不打扰的稳定低延迟。它只保证起始地址对齐，尾部并不天然独占——本例三个成员各自 alignas(64)，后一个成员从新的一条 line 起头，前一个的剩余字节才成为无人共享的 padding。mBuffer 同样对齐，数据拷贝不会反过来作废 counter。

3 · 参考文献

  1. Gross, D. (2024). When Nanoseconds Matter: Ultrafast Trading Systems in C++. CppCon 2024. 本页是对其中 FastQueue 一节设计的可视化复现。https://www.youtube.com/watch?v=sX2nF1fW7kI
  2. std::memory_order. cppreference. release / acquire / relaxed 的语义定义。https://en.cppreference.com/cpp/atomic/memory_order
  3. False sharing. Wikipedia. 成因（cache line 粒度与 MESI 一致性协议）与 padding / alignment 缓解手段。https://en.wikipedia.org/wiki/False_sharing

相关链接

  • When Nanoseconds Matter: Ultrafast Trading Systems in C++ CppCon (David Gross) 本页设计的出处:FastQueue 的 counter / cache-line 布局、以及一整套纳秒级低延迟工程实践。
  • False sharing Wikipedia 伪共享的成因(cache line 粒度 + MESI 一致性协议)与典型的 padding / alignment 缓解手段。
  • std::memory_order cppreference 本页用到的 release / acquire / relaxed 各自的语义定义。
  • alignas specifier cppreference 对齐说明符的用法;配合 std::hardware_destructive_interference_size 取 cache line 大小。
  • Circular buffer Wikipedia 环形缓冲区基础:用单调 counter + 取模映射物理槽位,以及有背压时区分空 / 满的几种约定。