随着多核处理器的普及,如何充分利用多核并行工作就成为高性能程序设计的一个重点。本系列文章将围绕高性能网游服务器的实现,探讨这方面的技术。

网游服务器的特点是:

具有大量客户端连接(数百至数千个),每个客户端都以一定的速率不断发送和接收数据;
服务器端的数据流量通常在几个至几十个Mbps之间;
数据需要实时处理;
数据包具有时序关系,往往需要按照严格的先后顺序予以处理。

网游服务器实际上代表了一类典型的新兴流数据处理服务器。这里只是为了讨论方便而限定于网游服务器,但是所讨论的原理和技术应该是普适的。

同步多线程技术肯定是无法满足要求的。由于每个客户端都在持续和服务器交换数据,系统将无法有效管理太多的线程;即使使用线程池技术,所能服务的客户连接也是很有限的。至于数据处理的实时性和数据的时序都无法顾及。

异步技术有好几种方式,这里只讨论IOCP和轮询模式。IOCP是微软推动的技术。对非常大量的连接(数千至数万)很有效。但是由于使用了多线程,这些线程需要把所需读写的数据通过共享的FIFO与主线程解耦(否则无法保持时序)。这就造成频繁的线程切换,无法满足大数据量的实时处理要求。另外,由于网卡只有一块(就一个网络地址而言),多线程并不能增加读写的速率。在另外一些时序要求不那么严格的场合,这些线程可以各自独立完成所有的处理任务,只需要在线程内部保持数据的时序。这就是向同步多线程技术退化了。

轮询是常用的模式。程序员把需要处理的Socket连接注册到一个数据结构中,然后提交给系统检查它们的读写状态。系统返回可供操作的Socket连接列表供程序员逐个处理。如果有数据可读就读入并处理,如果可写则把相应的数据写出去。为了提高效率和程序结构的清晰起见,Socket服务器通常单独使用一个线程,并且通过FIFO数据结构和主线程解耦。

在单核处理器上,上面这种轮询的模式是没有问题的。但是在多核平台上,用于解耦的FIFO将会变成并发瓶颈。这是因为传统的实现技术必须对FIFO加锁。虽然网络线程和主线程分别跑在不同的核上,理论上可以物理同时地运行(如果分别操作不同的数据项),但是同步锁却强行迫使其中的一个线程必须等待另外一个线程退出临界段,即使另外一个核空闲着。

这时候就需要一种支持并发的数据结构,下面称之为ConcurrentFIFO。

public interface ConcurrentFIFO {
    public Object remove();
    public void put(Object o);
}

put方法把一个数据对象推进FIFO,而remove方法从FIFO删除并返回一个数据对象。通过精心设计,ConcurrentFIFO的实现是线程安全的,两个线程可以安全而同时地访问FIFO。这样在多核平台上就能达到极高的性能。

通用的ConcurrentFIFO是非常难于实现的。基本的技术是使用原子的CAS操作来实现。CAS即CompareAndSet。现代处理器基本上都能支持这一类指令。但是这种数据结构的实现的一个很大的障碍就是垃圾回收。在多线程并发运行的情况下,被原子替换下来的数据无法得知其是否是其它线程所需要的,也就无法决定是否回收这块内存。除非有垃圾回收器,否则ConcurrentFIFO是很难实现的。(鼓吹手工管理内存效率最高的朋友们请瞪大眼睛看清楚)

其实,即使是对于有垃圾回收和内建线程支持的Java语言,要想构造一个支持并发的数据结构,也是极端困难的。java.util.concurrent包是经过并发领域的专家(Doug Lea,同时也是早期lig++的主要作者,以及DLmalloc的作者。我后面讨论内存管理的时候还要提到他)精心编写,并且由java社区的许多专家仔细评审测试之后才发布的。

现在来讨论上次提到的并发FIFO,其实现需要一些特殊的技巧。我上次说要实现单线程读单线程写的FIFO,但是这里我们先来讨论一般的并发FIFO。

我们知道,传统的生产者——消费者问题,通常是使用一个共享的缓冲区来交换数据的,生产者和消费者各自有对应的指针,在生产或者消费的时候相应地移动。如果达到了缓冲区的边界则回绕。如果生产者指针追上消费者指针,则表明缓冲区满了;如果消费者指针追上生产者指针,则表明缓冲区空了。问题在于,为了防止在缓冲区满的时候插入数据,或者在缓冲区空的时候删除数据,生产者或者消费者的每一次插入或者删除数据操作,都必须同时访问这两个指针,这就带来了不必要的同步。

在单核处理器上,共享缓冲区方式非常高效,并且具有固定的空间开销(有时候你需要保守地估计一个比较大的数值)。但是在多核处理器上(或者SMP系统中),如果要实现并发的FIFO,就必须摒弃这种方式。使用单链表而不是共享缓冲区就可以避开这个问题,这是第一个技巧。

第二个技巧关系到链表的使用方向。一般使用链表,其插入或者删除节点的位置是任意的。但是把链表作为FIFO使用,则只能也只需要在两端操作。需要注意的是这时候必须从尾部TAIL插入新的节点,而从头部HEAD删除节点。否则从尾部删除节点之后,无从得知新的尾部在哪里,除非从头部遍历。这样做的好处是,插入或者删除都只涉及到一个节点。插入的时候,只要让新创建的节点包含所需要插入的数据,并且其后继(下一个节点)为NULL;再让当前尾部的节点的后继从NULL变成这个新节点,这个新节点也就变成了新的尾部节点(这里的操作顺序很关键)。删除的时候,则检查当前头部节点的后继NEXT是否NULL。若是,表明FIFO是空的;否则,取NEXT所包含的数据来使用(是的,是NEXT而不是当前头部节点所包含的数据,参看下一个技巧和不变式),并把该数据从NEXT中删除,而NEXT也成为新的头部节点。(没有配图,各位请自己想象一下)

最后一个技巧:为了隔离对头部和尾部的访问,我们需要一个空节点N(不包含数据的有效节点),其下一个节点为NULL;并且引入HEAD和TAIL。在开始的时候,HEAD和TAIL都等于N。插入和删除数据的过程上面已经讲过了,这里讲一下不变式。

第一个不变式:头部节点总是空的(不包含数据)。在FIFO初始化的时候这是成立的。之后的插入操作不改变头部节点,因此对不变式没有影响。而对于删除操作,则每一个新头部节点的数据都已经在它成为新的头部节点的时候被删除(取用)了。

第二个不变式:插入和删除操作没有数据冲突,也就是说,插入线程和删除线程不会同时读写同一项数据(不是节点)。我们只需要考虑FIFO为空,即相当于刚刚完成初始化之后的情况。对于空节点N,插入操作改变其后继,删除操作则检查其后继。只要插入线程保证先让新节点包含数据再把新节点插入链表(也就是不能先插入空节点,再往节点中填入数据),那么删除线程就不会拿到空的节点。我们看到,唯一可能发生争用的地方就是N的后继指针,插入线程只要在更新N的后继指针之前准备好其它相关数据和设置即可。

这意味着,如果能够做到:1)一个线程对数据的更新能够被另外一个线程即刻看到;2)对数据的读或者写(更新和读取N的后继指针)都是原子的;3)指令没有被乱序执行。那么在单线程读单线程写的情况下,甚至不需要使用锁就可以安全地完成并发FIFO;如果有多个生产者线程,则增加一个生产者锁;如果有多个消费者线程,则可以增加一个消费者锁。也就是说,可以有四种组合。

但是实际情况远非如此。对于2)是容易满足的,因为现代通用处理器上32位数据的读或者写通常都是原子的。对于1),则取决于系统的内存模型:在强内存模型如C/C++中是满足的,在弱内存模型如Java中则不然。但是主要的问题还在于3)。由于指令的乱序执行,第二个不变式所需要的保证很可能被破坏,即使代码确实是那样写的。因此锁是必不可少的,因为加锁的同时还会插入内存屏障。

这样看来,上次说的SRSW并发FIFO就没有特别的意义了。干脆就用两个锁分别对应生产者和消费者,而并不限制生产者或者消费者的数量:T_LOCK和H_LOCK。在插入新建节点到链表尾部的时候使用T_LOCK,而在对头部操作的时候使用H_LOCK。


具体的代码这里先不给了。这里的算法不是我发明的,而是来自Maged M. Michael 和 Michael L. Scott的Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms。请参考其双锁算法的伪码。

现在来讨论游戏消息的传送。在一个网游的运营成本中,带宽费用应该是很大的一块。因此如何高效编码以及收发消息就成为节省运营成本的关键。这里面能做很多文章。

首先是一个基本的判断:随着处理器的计算能力不断提高,以及多核的日益普及,在消息的编码以及收发环节,CPU资源将不会成为瓶颈。相对的,应该千方百计考虑如何在保证游戏正常运行的前提下,降低不必要的通信开销。也就是说,可以对游戏中的消息进行一些比较复杂的编码。

那么游戏中都有哪些消息?我们知道聊天和语音消息优先级比较低,而且可以通过专门的服务器来处理。真正比较关键、能够影响玩家的游戏体验的,是那些状态变更、动作、玩家之间或者玩家和服务器/NPC之间的实时交互的消息。尤其是,这些消息的传送有严格的时序要求。如果一个玩家先看到自己的角色被砍死,然后才看到对方发出来的攻击动作,甚至根本没有看到对方有什么动作,他/她肯定会愤愤不平。因此,消息系统必须保证每一条消息的及时传递,并且不能打乱它们之间的顺序。

这意味着,每一条消息必须有明确的边界。也就是说,收到一条消息之后,接收方必须能够明确这条消息有多少个字节。这是一条显而易见的要求。但是大概是出于惯性,在实践中它常常变为消息编码中的长度字段。

这无疑是一种浪费。很多消息的长度是固定的,仅仅靠检查其消息类型就可以了解其边界。变长消息的处理后面会讨论。我这里并不是说要把具体的游戏逻辑与网络代码混在一起。通过使用元数据就可以有效的把网络代码跟具体的游戏逻辑有效隔离开来。关于元数据的使用后面也会详加探讨。今天时间不多了,下面讨论消息类型的编码作为结束。

通常一个字节会被用来编码消息的类型,以方便接收方的解码。但是我们知道,游戏中并不是每种类型的消息的传送频率都是一样的。事实上,我们知道哪些消息会被大量发送,哪些消息的频率会低很多,而另外一些消息,一天也不会有几条。明乎此,就可以采用非对称的编码方式来编码消息的类型。这就是Huffman编码。对于占据了绝大部分通信量的状态变更消息而言,即使每条消息节省下半个字节,也是非常划算的。以我的经验,一台普通PC可以作为服务器支持2000人同时在线的实时动作类游戏,消息通量是每秒10000条;如果一个服务集群有5台处理器,那么就相当于节省了200kbps的带宽。这还仅仅是从消息类型编码方面榨取的。当然,Huffman编码的解码是比较麻烦的,效率也会低一些。但是正如前面所指出的,这部分的运行开销并不会造成性能瓶颈。