请问服务端回response或者客户端发送request时所使用的WriteRequest链表为什么需要反转？

[kof02guy]

看实现是类似一个一个MPSC的无锁队列。
多个producer会通过exchange保证调用顺序和WriteRequest的插入顺序是一致的。在single consumer写之前，会找到old_head和new_head之间的WriteRequest进行链表反转，然后往fd里写出这一部分数据。

一般实现是：单纯的单链表，维护一个head和一个tail指针，producer在tail插入新的WriteRequest，而consumer在head处消费。

请问这样的一般实现和目前的实现相比，目前的实现会有哪些advantage么？是否目前的实现使得插入和消费实际上是在两个互不相干的链表上从而减少了需要race的场景？

[lorinlee]

WriteRequest链表是个单向链表，反转就是为了从tail消费吧

[kof02guy]

WriteRequest链表是个单向链表，反转就是为了从tail消费吧

谢谢。但我不太理解的是为什么一定要反转。如果producer在tail增加新的WriteRequest，consumer在head处消费，不需要反转链表。
没能理解反转链表的好处在哪里呢？

[oathdruid]

https://github.com/apache/brpc/blob/master/docs/cn/io.md
https://github.com/apache/brpc/blob/master/docs/cn/execution_queue.md
brpc里的MPSC一般都是这个套路实现的，比如上面这俩都是，braft应该也是广泛用了这个模式；

经典的双端链表队列实现是Michael&Scott的non-blocking queue，boost里有一个对应的实现boost::lock_free:queue，不过入队动作依赖CAS，CAS本身在竞争比较大的时候有自旋问题其实并发能力一般；

brpc这个单端链表核心就是通过不会失败不会自旋的exchange替换CAS提升了并发能力；也因为是通过和当前队尾进行exchage动作来成为新的队尾，整体的单链指向就只能是队尾指向前序节点的逆序链表了；

不过单纯看性能，基于数组的队列一般比链表类队列整体吞吐要高一些；所以这种链表类队列主要的优势点还是在于大量队列（例如作为接入层server承接大链接数）时不用预留数组长度，内存有节省；但是大链接数一般单链接上竞争就不强了，其实哪怕mutex保护的单链其实问题都不大；而有大并发的场景，因为链接数规模可控，可能进一步上数组队列的并发能力会更好（比如直接iouring之类的）；甚至大链接数场景，按链接组做聚簇之后上数组队列可能均衡意义上有时也强过链表队列；

只看MPSC并发能力的话，比较久之前做过一个简易评测

producer=12 consumer=1	qps	cpu	latency	qps	cpu	latency	qps	cpu	latency
boost::lockfree::queue	1W	1.008	0.92	100W	2.608	87.06	170W	5.34	314
bthread::ExecutionQueue	1W	0.015	6.03	100W	0.566	405	347W	1.53	1600
tbb::concurrent_bounded_queue	1W	0.012	4.57	100W	0.561	369	597W	3.37	2400
folly::MPMCQueue	1W	0.012	3.88	100W	0.314	144	895W	3.21	534
babylon::ConcurrentExecutionQueue	1W	0.011	4.86	100W	0.166	5.65	1511W	8.8	3.1
babylon::ConcurrentBoundedQueue	1W	0.010	3.68	100W	0.258	5.37	1690W	7.4	2.9

[kof02guy]

https://github.com/apache/brpc/blob/master/docs/cn/io.md https://github.com/apache/brpc/blob/master/docs/cn/execution_queue.md brpc里的MPSC一般都是这个套路实现的，比如上面这俩都是，braft应该也是广泛用了这个模式；

经典的双端链表队列实现是Michael&Scott的non-blocking queue，boost里有一个对应的实现boost::lock_free:queue，不过入队动作依赖CAS，CAS本身在竞争比较大的时候有自旋问题其实并发能力一般；

brpc这个单端链表核心就是通过不会失败不会自旋的exchange替换CAS提升了并发能力；也因为是通过和当前队尾进行exchage动作来成为新的队尾，整体的单链指向就只能是队尾指向前序节点的逆序链表了；

不过单纯看性能，基于数组的队列一般比链表类队列整体吞吐要高一些；所以这种链表类队列主要的优势点还是在于大量队列（例如作为接入层server承接大链接数）时不用预留数组长度，内存有节省；但是大链接数一般单链接上竞争就不强了，其实哪怕mutex保护的单链其实问题都不大；而有大并发的场景，因为链接数规模可控，可能进一步上数组队列的并发能力会更好（比如直接iouring之类的）；甚至大链接数场景，按链接组做聚簇之后上数组队列可能均衡意义上有时也强过链表队列；

只看MPSC并发能力的话，比较久之前做过一个简易评测

producer=12 consumer=1 qps cpu latency qps cpu latency qps cpu latency
boost::lockfree::queue 1W 1.008 0.92 100W 2.608 87.06 170W 5.34 314
bthread::ExecutionQueue 1W 0.015 6.03 100W 0.566 405 347W 1.53 1600
tbb::concurrent_bounded_queue 1W 0.012 4.57 100W 0.561 369 597W 3.37 2400
folly::MPMCQueue 1W 0.012 3.88 100W 0.314 144 895W 3.21 534
babylon::ConcurrentExecutionQueue 1W 0.011 4.86 100W 0.166 5.65 1511W 8.8 3.1
babylon::ConcurrentBoundedQueue 1W 0.010 3.68 100W 0.258 5.37 1690W 7.4 2.9

@oathdruid 谢谢大佬详尽的解释，这个测试涵盖的实现真全！固定qps下 boost和babylon的实现延迟表现都不错啊看起来，极限吞吐的话也是babylon的更优。

另外现在的实现看起来应该是去往_write_head进行插入：
WriteRequest* const prev_head = _write_head.exchange(req, butil::memory_order_release); if (prev_head != NULL) { req->next = prev_head; return 0; }
就我在想的是如果改为在tail插入例如：
WriteRequest* const prev_tail = _write_tail.exchange(req, butil::memory_order_release); if (prev_tail != NULL) { prev_tail->next = req; return 0; }
是不是也能够利用exchange更优的并发能力？消费的话改为从head消费，也不用反转链表。不知道这样会有什么问题。

[oathdruid]

目前消费动作应该也是用这个exchage摘除队尾的方式来做的。正向链消费感觉会有一些比较困难的点
1、需要再留一个虚拟头，消费从虚拟头发起，也给队尾侧提供一个起点
2、从虚拟头消费时候，不好确定终止点，遇到nullptr有可能是真的尾，也可能是正在准备链接的中间，需要读取当前尾部进行校验
3、要做按需启动消费的话，不能单纯像现在依赖交换结果来判断，需要加一些额外的计数机制联合使用
4、不过最麻烦的还是，正向接链表会导致，最后一个节点消费后，很难直接找到安全delete/recycle掉的时机（因为随时有可能有新的入队需要操作它的next, 逆向是不会有这种问题的）；那么就需要用虚拟头来交换尾节点，然后这个交换又可能交换到更新的插入者，还要再一次尝试跟随nullptr直到这个自己交换得到的尾部；

初步这么理了下，感觉好像不是不能做，不过实现复杂度提升不少

[kof02guy]

目前消费动作应该也是用这个exchage摘除队尾的方式来做的。正向链消费感觉会有一些比较困难的点 1、需要再留一个虚拟头，消费从虚拟头发起，也给队尾侧提供一个起点 2、从虚拟头消费时候，不好确定终止点，遇到nullptr有可能是真的尾，也可能是正在准备链接的中间，需要读取当前尾部进行校验 3、要做按需启动消费的话，不能单纯像现在依赖交换结果来判断，需要加一些额外的计数机制联合使用 4、不过最麻烦的还是，正向接链表会导致，最后一个节点消费后，很难直接找到安全delete/recycle掉的时机（因为随时有可能有新的入队需要操作它的next, 逆向是不会有这种问题的）；那么就需要用虚拟头来交换尾节点，然后这个交换又可能交换到更新的插入者，还要再一次尝试跟随nullptr直到这个自己交换得到的尾部；

初步这么理了下，感觉好像不是不能做，不过实现复杂度提升不少

谢谢。不过只有一个消费者从head消费，除非是writ_head和write_tail重合的时候有竞争，其它的时候这个消费者就直接去从head开始拿直到nullptr之前的结点就好了？然后就把write_head直接指到这个结点。
这样的话确实是可能在多个生产者在exchange write_tail的时候会导致消费者拿到的不是最新的write_tail，可能少拿几个，但由于是用的exchange，不太会发生像cas那样可能有生产者线程一直连不进来从而让消费者下一次来取还取不到的情况。
recycle的话，因为消费者设置了write_head之后，write_head之前的结点是不会再被生产者访问了，所以应该在write_head之前的结点都可以recycle了