Chinaunix

标题: 【实测比较half-sync-half-async模式与leader-follower模式的性能与场景(直播)】 [打印本页]
作者: lxyscls_cu    时间: 2013-02-15 23:47
看不懂，权当抢个沙发坐吧{:3_188:}
作者: lxyscls_cu    时间: 2013-02-15 23:48
16核 至强5645么...{:3_189:}
作者: windoze    时间: 2013-02-16 14:55
第2条可以开一个per-connection memory pool，STL那些容器加个allocator就差不多了。
如果还在用C++03，可以改用Boost.Container替换STL容器，它们都支持scoped_allocator_adaptor，可以挽救container-of-container，TMD这个东西烦了我好久。

实话说libevent里面那些宏实在让人没食欲，就算是纯粹出于心情考虑也要换一下，libev或者更加C++一点的Boost.Asio都还不错。

PS.  越发觉得Clay是个不错的语言
作者: yulihua49    时间: 2013-02-16 15:42
本帖最后由 yulihua49 于 2013-02-16 15:57 编辑
linux_c_py_php 发表于 2013-02-15 23:30
比如epoll_wait的时候是不可以从其他线程做epoll_ctl修改event的. ...

没明白。
据我试验，多个线程在epoll_wait的时候，其它多个线程是可以同时或不同时（不使用任何互斥锁）、安全的进行epoll_ctl的 。
这是我们系统常态的运用方法，进行高吞吐量的OLTP（每秒数千次至几万次），没有任何问题。
我感觉，epoll_wait内部已经实现了L/F模型，可以多个线程进行epoll_wait,同时多个线程进行epoll_ctl。一个event只提交给一个线程，从未观察到提交给多个线程情况（如果出现，我们的应用就崩溃了）。
作者: windoze    时间: 2013-02-16 15:54
epoll是线程安全的
http://linux-kernel.2935.n7.nabb ... libaio-td94856.html
Using the interfaces this way is pretty much their entire point. They'd be
almost useless if you couldn't use them in this way.
作者: yulihua49    时间: 2013-02-16 16:02
本帖最后由 yulihua49 于 2013-02-16 16:14 编辑
windoze 发表于 2013-02-16 15:54
epoll是线程安全的
http://linux-kernel.2935.n7.nabb ... -libaio-td94856.htm ...

所以我质疑楼主的那个论断。
当然，多线程epoll_wait，多线程epoll_ctl，会造成复杂的状态（但这是个高效的用法），你是否能驾驭，是个问题。
我猜，楼主的论断可能来自于驾驭问题，而非epoll本身。
因此，我们希望系统能高效运作，又要避免驾驭复杂状态，采用了封装的办法，把epoll这个魔鬼封装在一个模块中，形成框架，应用逻辑完全不知道它的存在。
作者: linux_c_py_php    时间: 2013-02-16 17:47
原来epoll_ctl是线程安全的, 那LF必胜啊.

楼上说了个啥玩意, 别整那么专业, 还驾驭不驾驭的, 你能驾驭了个啥似的.

框架是框架, 测试是测试, 代码里我连应用逻辑和底层逻辑都没划分, 直接写死的代码, 谈啥JB复杂状态, 我连状态机都没上.
作者: linux_c_py_php    时间: 2013-02-16 17:49
就算epoll_wait自己是LF的, 但程序设计也要自己做LF, 因为你保不准A线程监听到可读, 然后开始read, B线程接下来也监听到可读导致了并发read.

只能说epoll_ctl是线程安全的, 并且可能epoll_wait是可以防惊群的?

yulihua49 发表于 2013-02-16 15:42
没明白。
据我试验，多个线程在epoll_wait的时候，其它多个线程是可以同时或不同时（不使用任何互斥锁） ...
作者: yulihua49    时间: 2013-02-16 17:52
本帖最后由 yulihua49 于 2013-02-16 17:56 编辑
linux_c_py_php 发表于 2013-02-16 17:49
因为你保不准A线程监听到可读, 然后开始read, B线程接下来也监听到可读导致了并发read.

...

前边说了，不会发生这种情况。
epoll_wait确实是防惊群的。
前边的话，没有贬义，请多包涵。
作者: linux_c_py_php    时间: 2013-02-16 17:56
yulihua49 发表于 2013-02-16 15:42
没明白。
据我试验，多个线程在epoll_wait的时候，其它多个线程是可以同时或不同时（不使用任何互斥锁） ...



应用层的leader-follower肯定要自己做, epoll只是检测event的一个API, 为什么你们的程序可以无锁epoll_wait? 我认为这是不可能的, 肯定是只有Leader才可以epoll_wait, 你没看清楚你们的代码吧, 要么就是每个线程一个独立的epoll各自维护一批fd.


再有一个问题就是, epoll_wait的同时, 另外一个线程epoll_ctl, 这件事是线程安全的, 这个线程安全的概念是否能做到这个效果: A线程epoll-wait, 但没有任何事件发生并挂起, B线程epoll_ctl恢复一个fd的监听, 并且fd立即可读/可写, 你们知道epoll_wait能否监听到这个事件吗? 有这个试验吗?
作者: linux_c_py_php    时间: 2013-02-16 17:56
yulihua49 发表于 2013-02-16 17:52
前边说了，不会发生这种情况。
epoll_wait确实是防惊群的。
前边的话，没有贬义，请多包涵。


原因是什么? 求详解.
作者: yulihua49    时间: 2013-02-16 17:58
linux_c_py_php 发表于 2013-02-16 17:56
再有一个问题就是, epoll_wait的同时, 另外一个线程epoll_ctl, 这件事是线程安全的, 这个线程安全的概念是否能做到这个效果: A线程epoll-wait, 但没有任何事件发生并挂起, B线程epoll_ctl恢复一个fd的监听, 并且fd立即可读/可写, 你们知道epoll_wait能否监听到这个事件吗? 有这个试验吗...

试过了，不仅试过了，而且已经在应用了。没问题的。
作者: linux_c_py_php    时间: 2013-02-16 17:58
linux_c_py_php 发表于 2013-02-16 17:56
原因是什么? 求详解.


千万别告诉epoll_wait在多线程使用时将FD=A可读告诉线程1, 过一会就不会再告诉线程2了, epoll_wait自己不惊群可以理解, 但epoll_wait到你epoll_ctl移除监听中间不是原子的, 为什么不可能发生两个线程同时检测到事件?
作者: linux_c_py_php    时间: 2013-02-16 17:59
yulihua49 发表于 2013-02-16 17:58
试过了，不仅试过了，而且已经在应用了。没问题的。


有没有理论依据啊, 这太假了, 不能信服
作者: yulihua49    时间: 2013-02-16 18:01
本帖最后由 yulihua49 于 2013-02-16 18:15 编辑
linux_c_py_php 发表于 2013-02-16 17:56
原因是什么? 求详解.

在一个项目开始之前，确实有这个疑惑。
第一个版本就是一个线程监听，把事件分配给线程池。
发现瓶颈竟然在分配线程，要经过一些条件判断再分配，这个过程单线程的。
当我们的吞吐量达到2.5W/S左右时，饱和了。
这时问题是，把分配过程多线程化。最担心的，就是你说的这个问题。
当年进行了大量的试验，包括压力测试。
最后确认了，epoll，多线程安全，对事件队列的控制完整、准确，不惊群。
新的方案，群狼抢奶，实施了，吞吐量达到了6.5W/S,并且未饱和，还有余地。
至于理论根据，我不清楚。但我不认为理论方面会出现什么问题，仅仅是操作问题，把事件的互操作处理好了而已。
作者: linux_c_py_php    时间: 2013-02-16 18:03
linux_c_py_php 发表于 2013-02-16 17:56
应用层的leader-follower肯定要自己做, epoll只是检测event的一个API, 为什么你们的程序可以无锁epol ...


从那个帖子里看, epoll_ctl是线程安全, 并且可唤醒epoll_wait的, 这下做LF省事了.

那么就剩下epoll_wait的问题了.
作者: linux_c_py_php    时间: 2013-02-16 18:04
嗯, 接下来用libev了.

windoze 发表于 2013-02-16 14:55
第2条可以开一个per-connection memory pool，STL那些容器加个allocator就差不多了。
如果还在用C++03，可 ...
作者: linux_c_py_php    时间: 2013-02-16 18:10
@windoze 大侠,

要你做LF的话, 还是需要做cond+mutex抢Leader后做epoll_wait, 监听到event后epoll_ctl移除fd监听, 然后放掉cond转为follower开始read/write/process, 最后epoll_ctl恢复fd监听, 抢cond+mutex做leader.

这个过程**什么影响性能的位置吗.  

  我主要犹豫follower的任务里是否应该包括read/write, 从理论上来讲, 由follower做read/write会提高并发I/O能力, 比leader做I/O(意思就是Leader根据事件做读写, 如果是读并且解析到至少一个请求, 则转为follower)要更高效.
作者: linux_c_py_php    时间: 2013-02-16 18:13
yulihua49 发表于 2013-02-16 18:01
在一个项目开始之前，确实有这个疑惑。
第一个版本就是一个线程监听，把事件分配给线程池。
发现瓶颈竟 ...


意思就是N个线程, 共享一个epoll实例, 然后都调用epoll_wait, 然后每个线程分到的event fd都不一样, 并且你慢慢悠悠的在线程A里read fd=5, epoll_wait过24小时之后也会保证这个fd不会通知给线程B, 从而保证线程A与线程B不会发生同时的慢慢悠悠的read吗 ?

unbelievable啊
作者: linux_c_py_php    时间: 2013-02-16 18:15
yulihua49 发表于 2013-02-16 18:01
在一个项目开始之前，确实有这个疑惑。
第一个版本就是一个线程监听，把事件分配给线程池。
发现瓶颈竟 ...


感觉理论没问题的依据是什么? 我感觉理论依据有问题, 解释不了的事情需要一个官方解释啊, 不能说压力测试没问题就没问题了, 如果你说epoll_wait会保证一个fd的事件一辈子就分配给一个已分配过的线程, 那我就直接信了.
作者: linux_c_py_php    时间: 2013-02-16 18:18
找到了原因了:

       Since  even  with  edge-triggered  epoll, multiple events can be generated upon receipt of multiple chunks of data, the
       caller has the option to specify the EPOLLONESHOT flag, to tell epoll to disable the associated file  descriptor  after
       the receipt of an event with epoll_wait(2).  When the EPOLLONESHOT flag is specified, it is the caller’s responsibility
       to rearm the file descriptor using epoll_ctl(2) with EPOLL_CTL_MOD.

得给epoll上这个选项, 才能保证epoll_wait内置LF, 是吧.
作者: yulihua49    时间: 2013-02-16 18:19
linux_c_py_php 发表于 2013-02-16 18:13
意思就是N个线程, 共享一个epoll实例, 然后都调用epoll_wait, 然后每个线程分到的event fd都不一样, 并 ...

我用的LT模式，据说不是效率最高的，但是可靠。＋ONESHOT。
想试试ET，项目已投产，没机会了。
作者: linux_c_py_php    时间: 2013-02-16 18:20
而且是根据你之前的一个帖子找到的, 这下牛逼了.

这尼玛内置LF, 直接无敌了... 我也不用动手了, 多线程+无脑epoll... 这岂不是无脑扩展服务承载能力吗, 牛逼了.
作者: windoze    时间: 2013-02-16 18:21
回复 14# linux_c_py_php

多个thread同时对同一个epfd调用epoll_wait是完全正当的。

如果你用EPOLLET或者EPOLLONESHOT，epoll_wait就只通知某一个thread，不会产生惊群。
如果你用level trigger，那epoll_wait就会通知到所有的thread
如果在epoll_wait当中，另一个thread用epoll_ctl加入了已经有事件的fd，那epoll_wait就会立即通知到对应的thread
这本来就是epoll的基本用法，不用担心
作者: linux_c_py_php    时间: 2013-02-16 18:21
yulihua49 发表于 2013-02-16 18:19
我用的LT模式，据说不是效率最高的，但是可靠。＋ONESHOT。
想试试ET，项目已投产，没机会了。


用ET会高效的, 一次event就把data读干净就OK了, 区别不大, 但据说减少了epoll_wait唤醒的次数.
作者: linux_c_py_php    时间: 2013-02-16 18:24
windoze 发表于 2013-02-16 18:21
回复 14# linux_c_py_php

多个thread同时对同一个epfd调用epoll_wait是完全正当的。


ET应该也要+ONSHOT才行吧, 我看manpage里是这么说的:

       Since  even  with  edge-triggered  epoll, multiple events can be generated upon receipt of multiple chunks of data, the
       caller has the option to specify the EPOLLONESHOT flag, to tell epoll to disable the associated file  descriptor  after
       the receipt of an event with epoll_wait(2).  When the EPOLLONESHOT flag is specified, it is the caller’s responsibility
       to rearm the file descriptor using epoll_ctl(2) with EPOLL_CTL_MOD.
作者: windoze    时间: 2013-02-16 18:27
回复 27# linux_c_py_php

这是两码事。

Edge Trigger针对的是一个IO事件，它保证对同一个事件只触发一次。
One Shot针对的是一个fd，它保证一个fd产生事件后，在重新enable之前，不会再产生任何事件
作者: linux_c_py_php    时间: 2013-02-16 18:28
linux_c_py_php 发表于 2013-02-16 18:24
ET应该也要+ONSHOT才行吧, 我看manpage里是这么说的:

       Since  even  with  edge-triggered  e ...


这个选项和libevent里~EV_PERSIST是一个设计理念, 有木有.

我感觉这个选项我同事都可能没人知道, 的确有点逆天.
作者: yulihua49    时间: 2013-02-16 18:31
本帖最后由 yulihua49 于 2013-02-16 18:34 编辑
linux_c_py_php 发表于 2013-02-16 18:21
用ET会高效的, 一次event就把data读干净就OK了, 区别不大, 但据说减少了epoll_wait唤醒的次数.

可能是这样的。
我也想试试ET，那就有可能发生那个情况，可以每个event加个状态表明处理步骤。但是状态要想无缝，挺难的。
OO，楼上说没事，那就更好了。

一切基于试验，大家有机会试试吧，结果通报一下。
作者: windoze    时间: 2013-02-16 18:32
本帖最后由 windoze 于 2013-02-16 18:34 编辑

回复 29# linux_c_py_php

如果你不希望同一个连接同时被多个thread处理，当然要加上ONESHOT。这样一旦某个thread由于特定fd上的事件被唤醒，直到有人主动enable这个fd之前，其它thread都不会接收到关于这个fd的事件。
一般你会在工作线程里处理IO，在最后主动enable这个fd。
这样不能保证一个fd始终由同一个thread处理，但是可以保证一个fd不会同时被多个thread处理。

当然，不加ONESHOT的场合也是存在的，比如处理UDP的时候，可能每个包都是独立的请求，这样即便多个thread同时处理同一个fd也没关系，因为它们处理的是不同的请求。
作者: linux_c_py_php    时间: 2013-02-16 18:34
windoze 发表于 2013-02-16 18:27
回复 27# linux_c_py_php

这是两码事。


我以为你说的是ET不需要ONESHOT也自动LF了呢, 理解错了.

还有个问题, epoll_wait自身LF了, 但我要accept与close连接, 我需要自己维护一个Connection数组来做记录, 这个数组的加锁访问(添加新连接, 或者我喜欢把注册的event记录在里面)是没法避免了吧, 这个对性能的损耗影响大吗?
作者: windoze    时间: 2013-02-16 18:36
回复 32# linux_c_py_php

为什么要自己维护这个数组呢？epoll_data不是有地方让你放自己的数据么？
既然都用epoll了，该它管的东西就让它管吧。
作者: linux_c_py_php    时间: 2013-02-16 18:38
windoze 发表于 2013-02-16 18:32
回复 29# linux_c_py_php

如果你不希望同一个连接同时被多个thread处理，当然要加上ONESHOT。这样一旦某 ...


嗯, 多谢, 这些我可以理解的.

相当于 ONESHOT把epoll_wait和epoll_ctl(DEL)做了原子化,  这样对于应用程序来看基本上已经看不到LF的影子了, 都是epoll自己做的.


带出另外一个疑惑, 你们有没有试过这种情况下,        int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);的maxevents是指定为1还是根据情况设置, 因为我认为如果业务逻辑比较慢, 那么设置为1可以保证任务的散列可以均匀到N个线程, 免得一个业务处理慢让一堆event fd等着而让另外一些线程闲着,  但如果业务逻辑很快, 那么maxevents可以设置较大.
作者: yulihua49    时间: 2013-02-16 18:38
linux_c_py_php 发表于 2013-02-16 18:24
ET应该也要+ONSHOT才行吧, 我看manpage里是这么说的:

       Since  even  with  edge-triggered  e ...

找到理论根据了？那就更好了。我是干试的啊，测了几个星期呢。
作者: linux_c_py_php    时间: 2013-02-16 18:41
windoze 发表于 2013-02-16 18:36
回复 32# linux_c_py_php

为什么要自己维护这个数组呢？epoll_data不是有地方让你放自己的数据么？


可以的, 如果是优雅退出想释放干净所有的资源, 或者如果我希望有时候可以遍历在线用户需求的话, 就不太方便了.
作者: yulihua49    时间: 2013-02-16 18:41
linux_c_py_php 发表于 2013-02-16 18:38
嗯, 多谢, 这些我可以理解的.

相当于 ONESHOT把epoll_wait和epoll_ctl(DEL)做了原子化,  这样对于应 ...

我指定为1。
否则又出现单线程分配。
作者: windoze    时间: 2013-02-16 18:42
本帖最后由 windoze 于 2013-02-16 18:44 编辑

回复 35# linux_c_py_php

这都哪儿跟哪儿啊？maxevent不就是说你那个epoll_event数组有多大么？跟分布均匀不均匀有什么关系？
好吧我记错了……
指定为1就好了，除非你打算一次处理多个请求
作者: linux_c_py_php    时间: 2013-02-16 18:42
yulihua49 发表于 2013-02-16 18:41
我指定为1。
否则又出现单线程分配。


非常和谐..
作者: linux_c_py_php    时间: 2013-02-16 18:44
windoze 发表于 2013-02-16 18:42
回复 35# linux_c_py_php

这都哪儿跟哪儿啊？maxevent不就是说你那个epoll_event数组有多大么？跟分布均 ...


5个fd发生可读, 并且假设都能解析到request, 每个request跑10小时, 你有5个线程, 如果设置成5, 那么万一epoll_wait内部实现就是不均匀的散列全分线程1上了, 那就是跑50个小时, 但如果限制maxevent=1, 那就是跑10个小时..
作者: yulihua49    时间: 2013-02-16 18:44
linux_c_py_php 发表于 2013-02-16 18:41
可以的, 如果是优雅退出想释放干净所有的资源, 或者如果我希望有时候可以遍历在线用户需求的话, 就不太 ...

我是二者结合。
有一个context数组，＋ 几个队列，按下标排队。下标进入epoll_data,可直接找到context。
作者: linux_c_py_php    时间: 2013-02-16 18:45
真心没想到, 发了此贴一下子学习到了真理, 草, 这要搁我自己琢磨, 不知道哪年有机会接触到这个flag了, 太lucky了.

作者: linux_c_py_php    时间: 2013-02-16 18:46
windoze 发表于 2013-02-16 18:42
回复 35# linux_c_py_php

这都哪儿跟哪儿啊？maxevent不就是说你那个epoll_event数组有多大么？跟分 ...


嗯, 我也觉得1比较通用.
作者: yulihua49    时间: 2013-02-16 18:48
linux_c_py_php 发表于 2013-02-16 18:45
真心没想到, 发了此贴一下子学习到了真理, 草, 这要搁我自己琢磨, 不知道哪年有机会接触到这个flag了, 太lu ...

很高兴交流，我也有收获。
作者: windoze    时间: 2013-02-16 18:48
回复 40# linux_c_py_php

这事儿是这样的，epoll_wait毕竟是一次系统调用，还是有些开销的，如果你的程序处理请求很快，那么一次wait回多个事件是值得的；但如果像你说的一个请求要几个小时…………老实说你还用epoll干嘛？
作者: linux_c_py_php    时间: 2013-02-16 18:50
windoze 发表于 2013-02-16 18:48
回复 40# linux_c_py_php

这事儿是这样的，epoll_wait毕竟是一次系统调用，还是有些开销的，如果你的程 ...


就举个例子嘛, 看看maxevents是不是也有讲究.
作者: yulihua49    时间: 2013-02-16 18:52
windoze 发表于 2013-02-16 18:48
回复 40# linux_c_py_php

这事儿是这样的，epoll_wait毕竟是一次系统调用，还是有些开销的，如果你的程 ...

嗯。
如果返回多个，就要自己往线程池分配，返回1个是系统分配，怎样好，自己看着办。
作者: linux_c_py_php    时间: 2013-02-16 18:52
yulihua49 发表于 2013-02-16 18:44
我是二者结合。
有一个context数组，＋ 几个队列，按下标排队。下标进入epoll_data,可直接找到context。


如果不提供遍历在线用户的功能的话, 这么做的确可以无锁, 我1楼的代码里也是这么折腾的.

如果遍历在线用户, 但不担心及时性的话, 每个connection里来个flag标记一下该connection是否存活就行, 可以免掉锁.
作者: linux_c_py_php    时间: 2013-02-16 18:54
linux_c_py_php 发表于 2013-02-16 18:52
如果不提供遍历在线用户的功能的话, 这么做的确可以无锁, 我1楼的代码里也是这么折腾的.

如果遍历在 ...


就是遍历的时候得遍历0-MAXFD, 有点低效, 不过计算机那么快还好..
作者: linux_c_py_php    时间: 2013-02-16 18:55
yulihua49 发表于 2013-02-16 18:48
很高兴交流，我也有收获。


嘿嘿， 我还是觉得我收获比较大， 这一个flag可以让我写一个单线程epoll, 然后创建N个线程就变成了多线程epoll。。我会乱说吗- -
作者: yulihua49    时间: 2013-02-16 18:57
本帖最后由 yulihua49 于 2013-02-16 19:06 编辑
linux_c_py_php 发表于 2013-02-16 18:52
如果不提供遍历在线用户的功能的话, 这么做的确可以无锁, 我1楼的代码里也是这么折腾的.

如果遍历在 ...

我们的context里有这个东西。
有时要检测是否有长期挂起的连接，长期不合理占用资源的。。。。
context里还要有应用自定义的数据区（会话数据区），用以表达应用工作的状态。不能使用全局数据，也不能使用线程数据和栈数据。
作者: windoze    时间: 2013-02-16 19:07
有个东东叫timeout...
以HTTP为例，其实你只需要记录所有的keepalive/persistent连接，对于短连接，设好读写timeout就不用管它了
如果你确实需要遍历所有连接，那就要确保用于记录连接数据的记录有正确的生存期，因为很可能在你遍历的时候连接就结束了，如果不小心程序会崩。
我一般会用一个无锁的双链表加一个后台的延时reaper
作者: yulihua49    时间: 2013-02-16 19:09
windoze 发表于 2013-02-16 19:07
有个东东叫timeout...
以HTTP为例，其实你只需要记录所有的keepalive/persistent连接，对于短连接，设好读 ...

对，context里包含好几个timeout，有客户端的timeout，有下一段链接的timeout。。。。。
作者: linux_c_py_php    时间: 2013-02-16 19:22
本帖最后由 linux_c_py_php 于 2013-02-16 19:27 编辑
yulihua49 发表于 2013-02-16 19:09
对，context里包含好几个timeout，有客户端的timeout，有下一段链接的timeout。。。。。


但如果真是需要遍历, 还是用一个预分配的fd索引的连接数组来维护连接信息, 我想了个路子, 但不能解决及时性, 可能A关了fd=2, 但B依旧会向fd=2广播信息:

可以通过一个无锁的flag先行标记连接, 但不close fd, 只取消epoll register, 然后通过一个独立单线程扫整个数组, 独立线程啥时候扫可以用pipe事件做不阻塞的通知, 扫的时候就是检测到flag=true就先重置信息最后close. 这时候, 那些线程池就能accept复用这个fd了. (不知道靠不靠谱... 这个线程能不能忙死)


上面当我没说, 还是会有并发行为, 广播者可能与扫线程同时操作该连接的内存, 只要广播者没意识到flag, 并且扫线程意识到了flag.

无锁链表是什么技术, 求地址科普.

作者: linux_c_py_php    时间: 2013-02-16 19:23
嗯, timeout和lifetime可以保证连接能及时关闭, 但无锁的遍历需求还是需要单独设计一下.

yulihua49 发表于 2013-02-16 19:09
对，context里包含好几个timeout，有客户端的timeout，有下一段链接的timeout。。。。。
作者: windoze    时间: 2013-02-16 19:29
如果你要遍历，就不能在连接结束时删除context；如果你不在连接结束时删除context，就必须在后台延迟回收。
如果回收是延迟的，那么无锁的需求用一个双链表就可以了，正向的链用于遍历，反向的链用于删除context后修复链表。
作者: linux_c_py_php    时间: 2013-02-16 19:36
windoze 发表于 2013-02-16 19:29
如果你要遍历，就不能在连接结束时删除context；如果你不在连接结束时删除context，就必须在后台延迟回收。 ...


需要详细给我讲讲, 完全无锁真心理解不了, 求重点.

1, 连接建立后, 用什么结构体维护连接.
2, 连接断开后, 用什么结构体延迟排队.
3, 怎么保证无锁延迟删除的, 比如你正在延迟删除操作, 而另一个线程正在广播.
作者: windoze    时间: 2013-02-16 20:05
回复 57# linux_c_py_php

用什么结构体保存连接本身的信息没关系，关键是如何把这些信息汇集起来
一个不动脑子的方案可以是这样：
1. 建立一个双链表
2. 新连接建立后，将连接信息插入表尾

  2. context->next=NULL;
  3. context->prev=tail;
  4. tail->next=context;
  5. tail=context;
复制代码
3. 连接结束后，将该连接从链表中摘除，在context中记录结束的时间戳，然后传递给后台的reaper thread

  2. context->prev->next=context->next;
  3. context->next->prev=context->prev;
  4. context->prev=reaper_list_tail;
复制代码
4. reaper thread维护另外一个反向的单链表，这个链表只使用/调整prev指针，不修改next指针，reaper定期扫描这个链表，将时间戳老于一定阈值的节点回收，其它节点不变。

  2. while(1) {
  3.     context_t *p=reaper_list_tail;
  4.     context_t *prev;
  5.     while(prev=p, p=p->prev) {
  6.         if(old_enough(p)){
  7.             prev->prev=p;
  8.             reap(p);
  9.         }
  10.     }
  11. }
复制代码
5. 遍历连接时，只单向遍历，只使用next指针，这样可以保证即使某个连接在遍历期间被放入了reaper链表，它的next依然指向一个存活的context（虽然不一定是有效的）

  2. for(context_t *p=head; p; p=p->next) {
  3.     // do something with p
  4. }
复制代码
整个过程差不多就是这样。

上述代码只在ARM/X86/X86_64这些Strong Order的平台下能工作（前提是我脑子没发晕，代码没写错，这个可能性……哼哼……很小……），对于其它平台需要引入memory order，并且需要编译器不要自作聪明调整代码顺序。
作者: linux_c_py_php    时间: 2013-02-16 20:16
windoze 发表于 2013-02-16 20:05
回复 57# linux_c_py_php

用什么结构体保存连接本身的信息没关系，关键是如何把这些信息汇集起来


-，- 整个过程都不需要锁吗...
作者: linux_c_py_php    时间: 2013-02-16 20:27
本帖最后由 linux_c_py_php 于 2013-02-16 20:28 编辑
linux_c_py_php 发表于 2013-02-16 20:16
-，- 整个过程都不需要锁吗...


好吧, 为了防止A线程正在删除连接, B线程正在向该连接广播, 我决定在广播以及删除与添加连接时使用读写锁- -... 别折腾了- -. 用广播的机会不多... 一般需求还是直接静态connection数组fd索引用Epoll_data维护索引吧, 添加删除都可以无锁, 优雅退出也能正常关闭释放.
作者: sonicling    时间: 2013-02-16 20:42
链表能无锁并发吗？貌似不行吧。memory order也没用。
作者: windoze    时间: 2013-02-16 20:50
回复 60# linux_c_py_php

要是还要锁我折腾这么一圈到底是为神马？

刚才那个例子里有几点要注意
1. old_enough需要保证这个context“足够老”，这个足够就是说它一定要比一次遍历所需的时间更长，说起来比较容易，但是考虑到OS调度的不确定性，要保证这个“一定”还是有点难度的，假设你遍历一遍需要1ms，实际上old_enough可能需要设定到几秒甚至更长。
2. 创建和删除context本身可能用到了malloc/free/new/delete，绝大部分libc实现中这几个操作都用到了锁，为了进一步避免这个开销，我们需要引入自定义的memory management，比如一个lock free的slab分配器，这个的复杂度超过了这个帖子的容量……

读写锁最大的问题就是即便你只读，它也是有开销的，而且锁会导致优先级反转，明明这个线程该干活了，结果它非要等别人……
另外，还有一个问题，如果你只是在context数组上加锁，实际上你没办法保证遍历时不会碰到正在/已经被删除的连接，除非你在整个遍历期间锁定整个context数组，并且对于“所有”context的操作都加锁，漏掉一个都不行。
作者: windoze    时间: 2013-02-16 20:55
本帖最后由 windoze 于 2013-02-16 21:05 编辑

回复 61# sonicling

为什么不行呢？举个栗子？

比如这个：
Lock-Free Linked Lists Using Compare-and-Swap

还有这个：
A Pragmatic Implementation of Non-Blocking Linked-Lists

还有这个：
Lock-Free Programming
作者: linux_c_py_php    时间: 2013-02-16 21:47
windoze 发表于 2013-02-16 20:50
回复 60# linux_c_py_php

要是还要锁我折腾这么一圈到底是为神马？


如果能用锁, 就可以维护在线连接的数组了... 这个倒不是关心问题.

关键是无锁这招总感觉肥猪流, 我还是老实点吧...  

作者: windoze    时间: 2013-02-16 22:04
本帖最后由 windoze 于 2013-02-16 22:18 编辑

回复 64# linux_c_py_php

无锁也可以维护连接表（虽然不一定是数组）。
Lock Free Data Structure是个挺麻烦的事，但是搞好了的确在适用的场合能极大的提高效率。
参见Non-blocking algorithm，这里有不少内容，新版的Boost里也有一组Lock Free类/模板
作者: giantchen    时间: 2013-02-17 09:20
linux_c_py_php 发表于 2013-02-15 07:30
假期最后2天, 计划分别实现  half-sync-half-async 与 leader-follower(没空就回北京再写, 慢慢直播) ...


用 libevent 写的单线程 concurrent line echo server 比你这个多线程 hsha 的快几倍，这里用 hsha 纯粹添堵嘛。
https://gist.github.com/chenshuo/4969564
作者: sonicling    时间: 2013-02-17 17:28
回复 63# windoze


    用CAS实现操作原子性，的确可以无锁。我以为你说贴在58楼的那代码可以无锁。

不过目测遍历效率不高，当队列用用还行。
作者: windoze    时间: 2013-02-17 17:49
回复 67# sonicling

58楼的代码，给读写操作加上MB差不多就可以了，如果你的机器没有NUMA，CPU也没有那么多，不加MB其实也没问题。

至于效率不高，你说的是reaper么？那个东东在后台，隔一阵子才跑一次，慢点无所谓，前台的速度才是关键。
作者: linux_c_py_php    时间: 2013-02-17 19:59
giantchen 发表于 2013-02-17 09:20
用 libevent 写的单线程 concurrent line echo server 比你这个多线程 hsha 的快几倍，这里用 hsha 纯粹 ...


就是测试hsha嘛, 与echo无关- -, 不是为了测echo..
作者: eastany_op    时间: 2013-02-21 19:29
原来在这里，又有很大启发啊。哦也，
早点发现 就不用走那么多弯路了
作者: sadgod    时间: 2013-08-15 18:08
有一点需要请教下，为什么说在epoll_data里加上timeout和lifetime，就可以及时关闭连接呢？ 如果没有全局connection队列，如果一个链接一直一直没有数据到来，早就超过了timeout的限制，那么如何才能拿到这个连接的句柄呢？ 只用epoll自身机制，是否无法支持？
作者: starwing83    时间: 2013-08-16 05:53
@linux_c_py_php 最后不总结一下么亲？

意思是，用了epoll，根本就不需要任何多线程分派方法了，直接单线程的epoll分配多个线程出来干活就OK这样子？

听起来很爽的样子诶= =



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2