Block-based Bounded Queue

22 年十一月底，tokio 项目有人提议，用一种新的 queue 去实现目前的调度器管理。我发现这个 queue 的思路看上去有点意思，并且项目上的优化有可能会用到，并且没有发现有现有的实现。自然而然，就萌生了自己去实现一遍的冲动，进而转成现实。

bbq

我自己的实现目前是在这里，所谓的 Block-based Bounded Queue 本质上是一种 ring buffer，正常的 ring buffer 在实现的时候，无论是 push 还是 pop 都需要用 CAS 来同步状态判定操作是独占状态，可以安全地完成数据转移的。而 bbq 的核心思想是，将 ring buffer 先进行分组，每一组就是一个 block，block 有内部的记录，在 push 和 pop 的时候，竞争将会被分解到 block 级别，尤其是 pop 的时候，这样竞争的激烈程度会大幅降低，进而提升性能。

每一个 block 内部的记录分为四种，两个对应 push，两个对应 pop：

allocated 表示记录将要开始 push，committed 表示 push 数据已经完成，可以 pop 了
reserved 表示将要开始 pop，consumed 表示数据已经被 pop，可以再次 push 了

bbq 还有一个全局记录，指向当前正在操作的 block，包括 push 和 pop 操作。

性能问题

在实现 bbq 的时候，性能的瓶颈实际上在于 atomic memory ordering 的选择，但是安全性也在这里，如果无法确认操作的安全，就意味着性能无法达到可能的极限，在保守的情况下，性能虽然说还不错，但实际上并没有达到我想要的数据，但它有个很好的地方是，可以 batch pop 一个 block，绝大部分 mpmc 的 ring buffer 很难做到 batch pop，但因为 bbq 的 block 分组，这样方便了数据安全的批量操作。

在我项目的场景里，目前最好的实现是 rtrb，虽然只是 spsc，但已经足够了，并且也支持 batch 操作。到这里，这个验证项目基本算是结束了，当时并未发现 issue 发起人提出 PR，也就暂时搁置了，安全的多线程数据操作是非常难的，并不是有 ideas 就能真正实现到性能极限的，这里面坑太多了。

提议者的实现

前段时间，我突然发现提议者已经将代码提交了，最近花了点时间大致看了一遍。因为 tokio 需要的是调度器上 queue 的实现，所以它需要额外支持一个 stealer 操作，实际上，可以理解为 spmc 的操作。

如果你仔细看，会发现，他在实现的时候，在 atomic ordering 上的一些操作和我的实现上是不一样的，比如 this

/* reset cursor and advance block */
nblk.committed.store(next, Relaxed);
nblk.stolen.store(next, Relaxed);
// Ensures the writes to `committed` and `stolen` are visible when `reserved` is loaded.
nblk.reserved.store(next, Release);

在这里，它用的 relaxed，而我全局使用的都是 Release + Acquire 这个级别，实际上，这就是一个优化的地方，我在实现的时候，无法确定这样的优化是安全的，所以全局没有任何地方使用了，理论上来说，在 block 级别的查询是可以用 relax 的，但存储的时候，安全起见，理应在 Release 级别以上。

总结

简单来讲，这种尝试实现，是一种很好的体验，但想要达到性能的极限，需要更加深入的研究和背景知识，尤其是内存同步和内存安全方面，甚至是 cpu cache 相关的知识，有时候代码上的优化想法，在 cpu 看来是负优化，这方面我的积累还是不够，不足以支持我做出一些正确的决策。