--- 摄于 2017 年 9 月 藏川线前段
22 年十一月底,tokio 项目有人提议,用一种新的 queue 去实现目前的调度器管理。我发现这个 queue 的思路看上去有点意思,并且项目上的优化有可能会用到,并且没有发现有现有的实现。自然而然,就萌生了自己去实现一遍的冲动,进而转成现实。
我自己的实现目前是在这里,所谓的 Block-based Bounded Queue 本质上是一种 ring buffer,正常的 ring buffer 在实现的时候,无论是 push 还是 pop 都需要用 CAS 来同步状态判定操作是独占状态,可以安全地完成数据转移的。而 bbq 的核心思想是,将 ring buffer 先进行分组,每一组就是一个 block,block 有内部的记录,在 push 和 pop 的时候,竞争将会被分解到 block 级别,尤其是 pop 的时候,这样竞争的激烈程度会大幅降低,进而提升性能。
每一个 block 内部的记录分为四种,两个对应 push,两个对应 pop:
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 看来是负优化,这方面我的积累还是不够,不足以支持我做出一些正确的决策。
请登录后评论
评论区
加载更多