云风的 BLOG: 开发笔记 (5) : 场景服务及避免读写锁

这周我开始做场景模块。因为所有 PC 在 server 端采用独立的 agent 的方式工作。他们分离开，就需要有一个模块来沟通他们。在一期目标中，就是一个简单的场景服务。用来同步每个 agent 看到的世界。

这部分问题，前不久思考过。需求归纳如下：

每个 agent 可以了解场景中发生的变化。
当 agent 进入场景时，需要获取整个世界的状态。
agent 进入场景时，需要可以查询到它离开时自己的状态。关于角色在场景中的位置信息由场景服务维护这一点，在开发笔记1 中提到过。

大批量的数据同步对性能需求比较高。因为在 N 个角色场景中，同步量是 N*N 的。虽说，先设计接口，实现的优化在第二步。但是接口设计又决定了实现可以怎样优化，所以需要比较谨慎。

比如，同步接口和异步接口就是不同的。

请求回应模式最直观的方式就是设计成异步接口，柔韧性更好。适合分离，但性能不易优化。流程上也比较难使用。（使用问题可以通过 coroutine 技术来改善）即使强制各个进程（不一定是 os 意义上的进程）在同一个 CPU 上跑，绕开网络层，也很难避免过多的数据复制。虽有一些 zero-copy 的优化方案，但很难跨越语言边界。

同步接口使用简单，但在未经优化前，可能不仅仅是性能较差的问题，而是完全不可用。一旦无法优化，接口修改对系统的变动打击是很大的。（异步接口在使用时因为充分考虑了延迟的存在，及时没有优化，也不至于影响整个系统的运转）

在这次的具体问题上，我判断使用同步接口是性能可以接受的。即，用户可以直接查询场景的各种状态。蜗牛同学希望实现上更简单，干脆就是把所有 agent 以及未来的 npc 服务实现在一起，大家共享场景状态。因为框架使用 coroutine 调度，其实是相互没有冲突的。

在一个场景物理上在一个 CPU 上跑这个问题上，我没有不同意见。但是，我希望在设计上依旧独立。agent 的并发在实现上是不存在的，但在设计上是考虑进去的。agent 之间物理上完全独立，但在交互上使用一些优化手段达到零成本。

模块在物理上分离，是高健壮性和柔韧性的充分条件。最小依赖单一模块实现的质量。

至于性能开销，我的观点是，把所有东西塞到一起，使得沟通成本下降；比如大家都跑在同一 lua state 中，没有跨语言边界的信息传递；其实是一种成本延迟支付。抛开可能引起的健壮性下降问题，动态语言的 GC 代价也是初期无法预期的。

不过无论采用何种实现方案，接口设计总比其它更重要。需要留意的是，先分开实现再合起来，比先合在一起以后再分离，在实践操作中要难得多。这在历史上许多系统的大模块设计中被反复证明过：我看过太多上万行的 C++ 代码，几十个类绞在一起，留下飞线和后门，让类与类之间做必要的沟通。静态语言尚且如此，毋提动态语言这种随意性更高的东西了。

这周，怪物公司和小V 还在忙 client 那边跟美术的沟通和工具插件开发，原定的 C/S 联调一再被推迟。我自己在写了两三百行场景服务的 C 代码后，觉得可以暂放一下。所以最终接口还不需要完全敲定。前两天想到一些优化方案，也暂时不需要实现，先记录一下。

关于并发读场景状态的问题：

场景数据其实是允许读取方不那么严格需要一致的。因为场景数据是局部累积的一种缓慢变化。任何一个读方都不必一定读到最新的版本，而只要求读到一个完整的版本。即，我读到的场景是 0.05s 以前的状态也是可以被容忍的。0.05s 对于人类是一瞬间，但对于计算机却是一个相当长的时间段。

这种延迟本身也是存在的，因为更新场景的写入者本身也一定存在于不同机器上，对于网络通讯， 50ms 已经是一个不错的相应速度了。

如果在本地内存，做同步读取，任何一个需要原子性的读操作，需要的时间都远远低于 0.01s 数个数量级，这个速度差，让我们有一起契机摆脱并发操作需要的锁。

简单说，我想引入一个 triple buffer ，让本地内存中，场景数据有三份几乎相同的 copy 。为了后面好描述，我把它们称为 A B C 。

所有的场景更新者，通过一个消息队列提交更新需求，向 A B C 更新。每个更新请求，都需要依次更新完 A B C 后才销毁。

场景服务提供者控制一个写指针，每隔 0.01s 在 A B C 间翻转。也就是说，当 0.01s 的周期一到，下一次原子写操作就写向下一个场景镜像。

A B C 这三个场景镜像采用共享内存的方式，供唯一的一个写入队列以及不受限的读取者共享。写入队列维护进程在翻转写指针的同时，也翻转读指针。当写指针在 A 时，读指针在 C ；当写指针翻转到 B 时，读指针调整到 A ；等等。

每次读操作可以看成是原子的，操作前先获取目前的读指针指向的镜像，然后直接在这份镜像上做完后续的读操作。因为一次读操作需要消耗的时间远远低于 0.01s ，而写指针触碰回这个镜像的时间则在 0.01s 到 0.02s 之间，不会短于 0.01s 。这样，绝对不会发生读写冲突。

当然，用 double buffer 也是可行的，但需要在读取完毕后重新检查一下当前的读指针，看看是否还指向原来的镜像，如果已经切换了，就需要放弃刚才的结果，重新读一次。而且在读过程中，需要保证错误的数据（可能因为正在写入而不完整）不会引起程序崩溃。这样开发难度会增加。

事后复审读指针依旧可以做，如果发生异常记入 log ，一旦发生再来考量时间窗口的大小设置是否合理，或是看看到底什么意外导致了读写冲突。

对于高负载下，读操作可能被挂起，引起的原子性被破坏的问题，其实也是可测算的。

首先，在读 api 中，应该避免任何 IO 操作以及系统调用，比如写 log 。一切 log 都应该在操作完毕后再统一进行。一次原子读操作中，需要保证是单纯的 CPU/内存操作指令。这样可以保证单一 api 的过程，最多被 os 调度器打断一次。（因为指令数足够少，远小于 os 的最小时间片跑的 cpu 指令数）

写操作的间隔时间足够长，如果调度器是公平的，就可以保证在同样条件下写操作的镜像翻转消耗的时间片大于两倍的单次读操作的时间片。这样，做两次翻转后，保证一次读操作至少经历了同样的两倍以上的时间片。可以认为，单次读操作不会被写操作损坏。

Comments

@john 你可以尝试举出反例. 在何种操作系统的实现中,何种条件下, 会出现破坏上文提到的的情况下的一致性. 你摘取的那句话断章取义了. 我并没有说读操作挂起时间一定很短. 而是说,在同一个系统里, 没有 IO 操作时, 读线程和写线程同在一个调度器下, 不可能读线程被挂起很长时间 (超过 0.01s) 而写线程却被调度运行多次. 下面还有一句话是不可以忽略的前提 "如果调度器是公平的" .

Posted by: Cloud | (28) February 10, 2012 02:21 PM

关于 “对于高负载下，读操作可能被挂起，引起的原子性被破坏的问题，其实也是可测算的” 这个说法，我感觉是有问题：读取数据的时刻，是当前线程刚刚切换还是已经运行了操作系统定义的时间片长？这个是无法保证的，和具体应用有关，不能说只保证读取的时间短就行了。另外，从理论上说，现在的操作系统都是抢占式的，在抢占式的操作系统下，进程自己是无法可靠的保证不被切换的，特别是在高负载的情况下。

Posted by: john | (27) February 10, 2012 01:04 PM

真的好期待你的游戏，同时也期待这个过程中的技术分享

Posted by: 池中物 | (26) December 13, 2011 08:45 PM

期待云风的游戏，我还从来没有玩过一次大型在线游戏呢。期待云风的作品，一定得尝试玩玩。

Posted by: starshine | (25) December 11, 2011 12:36 PM

每次来都能学到新知识，赞！

Posted by: haxixi_keli | (24) December 9, 2011 11:19 AM

err。。不用谢自从有了CAS或者ll/sc之后，百分之百的lockfree算法都是利用了这条指令的。绝无例外。而且几乎所有CAS的具体应用都要用mem fence。这也是逃不掉的。我猜这也是为什么lockfree很难有进展的原因：CPU没有提供新的instruction

Posted by: mataxa | (23) December 8, 2011 09:33 PM

@mataxa 谢谢, 不过你提到的这个我也曾经造过此般轮子. 正如 The Non-Blocking Write Protocol NBW 提到, 它依赖一个 single word 读写的原子性. 从细节实现上, 是可以使用现在 CPU 的 barrier 指令避免调用 InterlockedIncrement 这种 api 去锁住总线的. http://blog.codingnow.com/2007/12/fence_in_multi_core.html 线程间使用 queue 通讯有非常成熟的实现, 现在更不需要自己去编码了.

Posted by: Cloud | (22) December 8, 2011 09:18 PM

哦搞错了不是queue 不过请看这篇论文。很好的解决了你的问题，并且不需要你的两个强设定（读的速度，以及读/写共享一个core）。 The Non-Blocking Write Protocol NBW: A Solution to a Real-Time Synchronization Promblem Hermann Kopetz et al lockfree的数据结构和算法，近几年没什么更新了。啃90年代的老本就足够了。有空多翻翻ACM/IEEE，比自己闭门造车好。

Posted by: mataxa | (21) December 8, 2011 08:08 PM

这不是 producer / consumer 模式. 如果硬要套的话, producer 是用 queue 更新状态. consumer 是 random access 所有历史状态, 而不是从 queue 里读. 回帖请看贴.

Posted by: Cloud | (20) December 8, 2011 07:58 PM

另外， “在一个场景物理上在一个 CPU 上跑” 到底是CPU还是core？？这有本质区别。博主这里太含糊了。

Posted by: mataxa | (19) December 8, 2011 05:36 PM

一个producer，N个consumer的lockfree Queue，这个是有论证过并且我在真实项目中验证过的解决方案的。既然你都肯付出3个buffer的代价，那么不需要“读操作远小于0.01秒”这个强前提条件。我记得当时是在ACM里面翻出来的论文。一个系列，有好几篇。年代大概是80-90年代。

Posted by: mataxa | (18) December 8, 2011 05:28 PM

第一次上来留言。可能Erlang就是你想要的。高并发，大规模数据同步。http://www.cnblogs.com/me-sa/archive/2011/07/03/erlang0001.html

Posted by: coneagoe | (17) December 8, 2011 11:23 AM

终于明白了为什么Agent的数据要场景保存。

Posted by: daseny | (16) December 8, 2011 09:46 AM

最近也在烦一些类(或者说模块)间沟通的问题.不知道博主有啥看法? "需要留意的是，先分开实现再合起来，比先合在一起以后再分离，在实践操作中要难得多。" 在实现时确实一般都是单一模块实现然后合起来.这是为了灵活性和重用性嘛.也易于测试嘛.合起来确实也需要额外的工作.不太明白博主上面的话意图(请原谅我用这个词),是建议先合起来再拆分吗?

Posted by: cbkid | (15) December 8, 2011 09:40 AM

一切 log 都应该在操作完毕后再统一进行。我个人很赞成这句呵呵

Posted by: lele | (14) December 7, 2011 10:00 PM

这不是一个通用问题的解决方案，这是一个特定需求问题的特定方案。里面关于时间限制条件的测算都是可以求得上下限的。所以可以严格实施。

Posted by: Cloud | (13) December 7, 2011 05:25 PM

这个实现依赖读写速度，感觉不靠谱。

Posted by: 0X0000 | (12) December 7, 2011 05:22 PM

我认为我自己这篇 blog 含金量更大的是前半篇。后半篇只是谈到一种优化策略。至于为什么不 copy ，前半篇也讨论过。从更高的层面来看，也就是优化不优化的问题而已。当然路人一般更关注优化这种噱头。因为他们并未真正干活 :)

Posted by: Cloud | (11) December 7, 2011 05:08 PM

COPY的话就不用这么折腾了。

Posted by: huangyi | (10) December 7, 2011 04:59 PM

在写指针翻转的时候，要做BUFFER COPY吧？

Posted by: yg.tang | (9) December 7, 2011 04:48 PM

要是可以用immutable data structure实现就最完美了 ;-)

Posted by: huangyi | (8) December 7, 2011 03:55 PM

读操作是通过 api 进行的，只保证每个 api 的原子性。而 api 的实现又是通过 C 语言实现的，是不超过 O(n) 复杂度的。 n 的最大值是可以被设置的。每条 C 代码对应的机器码是可以被计算出最大值的。换算回 CPU 和内存访问指标，可以得到 "读操作需要消耗的时间远远低于 0.01s" 对 CPU / 内存的配置要求下限。一旦违背硬件需求，通过 log 反馈做人工调整。 ps. 此服务用 C 语言实现最能保证运行时间的可测量性。

Posted by: Cloud | (7) December 7, 2011 03:34 PM

唯一写入队列的数据来源呢？如果有多个来源，如何保证不冲突？

Posted by: Anonymous | (6) December 7, 2011 03:30 PM

你这个设计依赖一个很关键的不变量："读操作需要消耗的时间远远低于 0.01s"。

Posted by: huangyi | (5) December 7, 2011 03:29 PM

整组服有多少物理进程？每个进程负责什么？是按照场景分进程还是按照业务分进程？进程是单线程的吗？

Posted by: Anonymous | (4) December 7, 2011 03:07 PM

个人感觉很像STM，维持一个版本列表。

Posted by: dennis | (3) December 7, 2011 03:00 PM

。当写指针在 A 时，写指针在 C ；当写指针翻转到 B 时，读指针调整到 A ； == 这里应该是这样？：。当写指针在 A 时，读指针在 C ；当写指针翻转到 B 时，读指针调整到 A ；

Posted by: dennis | (2) December 7, 2011 02:59 PM

你这个思路就是软件事务锁的思路。