技术研究：DOOM3网络模型的演化与网络架构

2016-09-01

今天下午读到一组 DOOM 3 相关的技术文章，这些文章描述的是十年前 (2006) 的技术，但依然有较强的参考价值。其中的一份技术记录描述了 DOOM3 BFG 开发过程中遇到的一些特定的性能问题。

[注] DOOM3 BFG 是 DOOM3 的全平台资料片。

一、DOOM3 技术点滴

技术背景

DOOM3 在发售时 (2004) 的性能状况是，在最低配的机器上效果全关 640*480 的情况下维持在 20fps，而资料片 DOOM 3 BFG 的目标是在 2012 年的机器上 1280*720 下平稳地地运行在 60 fps 上，这意味着使用原版的 1/3 的时间绘制 3 倍于原版的像素数量。

硬件变化上，这些年中 CPU 频率变化不大，但多核化使得多线程能够更有效率 (而 DOOM3 原版是单线程)；GPU 发展很快，使用新功能来优化特定的渲染特性 (比如用 coarse Z-Cull / Hierarchical-Z 来优化 Stencil Shadow Volumes)就很重要；内存的性能提高不大，导致单次内存访问对应的可执行指令数提高了，利用这一点可以做很多对应的优化。

内存约束

从 DOOM3 到 DOOM3 BFG 的一大困扰是缓存颠簸 (cache thrashing)，由于 DOOM 的光影模型及由此导致的特殊的内存访问模式，使得内存带宽问题一直比较严重。

DOOM3 通常会惰性地对“可能不需要的运算”做尽可能的延迟，这就需要在代码中用一些特定的标记来保存状态信息 (某一样东西算过没有，是否需要重算，等等) 而对多核更友好的则是现在比较流行的流式编程模型 (streaming programming model) ([注]也是曾提到的向无状态的 functional 的思维转换)。

角色的可见部分和阴影体 (visible meshes and shadow volumes) 的蒙皮都在 GPU 上完成，这些 GPU 上的顶点避免了运行时拷贝。而 CPU 这边也同样需要动态生成的索引来生成角色的 shadow volume 及 light volume 内的部分，这个动态的数据量还是挺大的，在 Mars City 1 的过场中，每帧 shadow volume / light culling 的数据需求在 6MB 左右，数据生成在 2.5MB 左右。这里生成的索引使用了合并写 (write-combined buffer) 由于这些线程存在不同线程内不同时序的读，很容易造成大量的缓存颠簸。这种颠簸的结果是，即使在使用了流式模型的 x86 上，也很难达到与 Cell SPU 处理器 (PS3) 匹配的吞吐量。这类读取使用了 SSE4.1 的一个指令 _mm_stream_load_si128() 来在合并写上尽可能地做合并读而不经过缓存。虽然合并写及其上的读取被认为是效率低下，但好在这里都是静态数据（也就是仅写入一次）。

用即时运算替代“预计算+存储”

在首节末尾提到，CPU和内存演化速率不同是可以被利用的。这里用蒙皮来做一个非常典型的实例。在原版 DOOM3 里每个角色每帧只蒙一次皮，运算结果存下来给需要的场合用（构建 shadow volume 和渲染）；而 DOOM3 BFG 内同一个角色在一帧内可能会蒙皮多次，仅仅是因为这样做速度更快。(在 GPU 上) 对一个 mesh 蒙皮的运算开销已经小于从内存中读取“未蒙皮版”的源数据的开销了。也就是说，每次都即时蒙皮的开销并不比去内存里读已蒙皮的数据高了。更何况还有如下几个巨大的优势：

1.如果是用于渲染的话，读取和蒙皮都发生在 GPU 上，不需要通过总线，能获得较大的总线带宽节省

2.未蒙皮的源数据可以所有相同的模型共享一份，而蒙过皮的话是每个角色都得存一份，内存开销是 1:n，能获得较大内存带宽的节省

3.在多线程读的情况下，读同样的数据可以降低缓存颠簸的几率

DOOM3 BFG 的 shadow volume 本质上是一组(针对未蒙皮数据即时生成的)索引。举个例子，如果一个蒙皮角色与两个投影光源交互，就会做 7 次蒙皮：2*2 次分别是两个 shadow volumes 的生成和渲染；1 次是正常的渲染，剩下两次是两个 light surfaces 的渲染。由于前面提到的诸多原因，7 次蒙皮的性能比 DOOM3 原版的 1 次蒙皮后到处使用还要高，而且随着时间的推移，优势还会被进一步放大。

这再一次凸显了 functional 的潜在巨大优势（跟直觉相反，即使考虑较大数据量，无状态仍然是更优的）而且由于不再维护一个 skinned version，代码更清晰和易懂了，理解和调试的成本降低许多。无状态也使得很多操作（如 shadow volumes 的构建）可以完全并行化。

内存-缓存友好的数据结构

这里总得来说是把之前实现的一些要么冗余，要么 cache-unfriendly 的一些数据结构改写为对缓存更友好的版本。总得来说其实我不太理解为啥在原始版本中很多可以用数组的地方需要用链表，而文中也一再表示所谓改好了的 'idList' 本质上也就是 resizable heap array（跟 vector 区别不大了）

小结

最重要的几句话，可以直接摘录了：

·if these threads touch a significant amount of memory then cache thrashing may occur while many CPUs are poorly equipped to avoid large scale cache pollution. Without additional instructions to manage or bypass the cache, a shared cache between all CPU cores can result in less than ideal performance.

·various data structures that exhibit poor performance on today's hardware. These data structures tend to result in poor memory access patterns and excessive cache misses.

二、DOOM/Quake I/II/III 网络模型的演化

一般性说明

游戏网络架构通常体现在四个要素的平衡上：一致性，响应性，带宽，延迟 (consistency, responsiveness, bandwidth and latency requirements)

“Multiplayer gaming is about shared reality.”

FPS 游戏的状态通常表现为一个实体列表：玩家，怪物，导弹，门等，这些实体 (entities) 与其全部作为不同的元素去区分对待，不如提供一个公共的结构和接口来简化通信。

“Networking in first person shooters is all about synchronizing the state of multiple copies of the same game entities such that all players experience the same changes and events in the virtual environment.”

为了达到即时同步这些状态的目的，有些实现方式需要参与者去管理和维护其自有的那份拷贝，通过施加一致的逻辑来推动所有的状态去同步地更新，而另一些实现则是随着时间的流逝不断地比较和发送最小的状态变化和差异。

P2P 模型 (DOOM)

DOOM (1994) 的网络模型是完全同步的 P2P 系统。该系统每秒钟对玩家的动作 (move/turn/use/fire, etc.) 采样 35 次 (得到一个 tick command) 并发送给其他所有玩家，每个玩家都接受来自所有玩家的 tick command，当某个玩家收到所有其他玩家的下一帧 tick command 后，该玩家的本地游戏状态推进到下一帧。这样的后果是全局性的延迟 (每个玩家从做出动作到收到反馈的响应时间) 由最慢网络连接的玩家决定。

这个网络模型逻辑上非常简单，但存在这些问题：

1.所有玩家都需要主动维护完美的状态同步，由于硬件不同(有时甚至是未初始化的变量)等引入的不一致，会让每个参与者细微的不同被累积下来，导致参与者之间显著的视觉和逻辑的差异。这种不一致的引入很难查，因为只有当它们累积起来才会有明显的效果，而等感觉到差异时，真正的问题已经发生很久了。

2.完全同步的网络无法跨平台。不同的硬件上，由不同编译器生成的汇编指令有时会产生轻微不同的行为 (浮点指令尤甚)。

3.随着玩家数量增长，延迟会迅速变得难以接受。而且只要有一个玩家的网络有波动，会影响到所有人的体验。

4.随着玩家数量增长，带宽需求会指数性地同步增长。

5.同步网络由于只发送 tick command，所有玩家必须同时启动游戏 (来保证游戏状态的一致性) 无法做到随时的加入和退出。

6.由于玩家本地维护了所有的状态，方便了作弊的实现。

Packet Server (包的简单中继)

这个模型在原版 DOOM 的基础上增加了一个 Packet Server，负责转发所有的 tick command。玩家不再直连其他所有玩家，而是连到这个服务器 (某个玩家机器上) 以获取最新的状态。这样改进后，同步量降低了，而且如果一个玩家很卡，只会影响到他自己的游戏体验。但上述的大多数问题依然存在。

Client Server (Quake I/II/III)

Quake I/II/III 实现了比较典型的 C/S 架构 (1996)，这个模型中服务器负责所有的逻辑判断，客户端本质上只是一个渲染终端。玩家把自己的操作和输入发送给服务器，收到一个实体列表用于渲染。服务器把压缩后的快照发给客户端 (10-20Hz) 客户端使用这些快照来插值或推导出平滑连贯的体验 (interpolates between, or extrapolates from the last two snapshots)。

在一般情况下(比如在古代的引擎Quake 1中)，客户端收集到用户命令后发送给服务器，此后就在等待服务器返回新的游戏状态。这是很笨的。在Quake 3中，客户端不会傻等，而会预测可能的游戏状态，其实预测状态所用的代码跟服务器端的代码是一样的，所以服务器端的状态和客户端的状态往往是一致的。如果确实不一致，则“服务器为准原则”将生效。

"Quake III Arena 网络协议规范(非官方)"

响应性和预判

这个模型同样有响应性问题，从输入的采样和发送到屏幕反馈同样需要一个 roundtrip 延时。为了克服延时客户端预测了玩家的下一步行动。玩家的输入在发出去的同时，本地立刻处理，而环境状态做了上文说到的 interpolate/extrapolate，也就是说玩家看到的自身是 (可预计的) 操作结果，而其他人是过去的状态。(这一点与魔兽世界是一致的) 这个 C/S 架构是异步的。对任何一个玩家而言，服务器的全局模拟落后于该玩家在本地的实际操作快照，而环境的状态同步更是落后于全局模拟。

这个模型允许中途加入和退出 (除了做 server 的玩家，如果不是 dedicated 的话)。由于玩家的判断基于的是其他玩家过去的状态，实际的击中检测发生在晚些时候的服务器上，在延时较高的情况下，玩家需要不断考虑延时状况并打提前量才能在未来的实际判断中击中对方。

延迟补偿的潜在问题

半条命在这个基础上引入了一种特定的延迟补偿 (lag compensation)，当玩家向某个目标 (若干毫秒前的状态) 射击时，做实际检测的服务器会采用该目标若干毫秒前的状态来检验是否击中。这么做需要服务器把之前一小段时间的状态持续地保存下来，这样不仅增加了实现复杂度，而且导致了某种程度的不一致性。延时高的玩家反而更容易因为补偿获得更有利的判断，严重影响游戏体验。这种补偿只能对目标的位置回滚，而所有其他环境状态的改变却已无法倒退，这也会影响实际的体验。

工程问题：逻辑和预测代码分离

Q3 里服务器上跑的逻辑代码 ("game code") 跟客户端跑的渲染和预测代码 ("client game code") 实现在物理上不同的模块里，但却需要对彼此的内部细节非常清楚 (才能保证预测和实际行为的一致性)。这个强耦合使得扩展游戏变得很困难，这也是难以实现单人游戏模式的原因之一。有时使用 Q3 引擎的游戏得为多人模式和单人模式发布两个不同的 exe，其中单人模式直接使用 game code 来简化逻辑流程。

插值/推导的局限性

由于快照的接收频率往往低于实际渲染的帧速，就需要上文提到的 interpolate/extrapolate，考虑物理模拟和交互的话，(为了跟服务器逻辑一致) 推导会增加额外的实现复杂度。这些插值对位置数据很有效，但其他一些状态很难插值，有时性能也是问题，比如四元数的 slerp 就挺费的。

压缩、状态同步冗余、固定字长

Quake III 里只有在 PVS 内的实体才会被同步状态，而且被同步的是压缩后的与上一次同步比较的差值 (delta compressed relative to the entity states from a previous snapshot) 这导致的结果是如果一个物体频繁进出 PVS 就没法做 delta 比较，总是发送完整状态，会导致不少冗余的同步量。

为了提高网络通讯速度，降低带宽，Quake 3中采用了压缩的技术。这并不是指用一些压缩算法来直接压缩数据。而是指，在传送游戏状态数据时，只传送改变了的游戏状态，而不是全部发送过来。一般来说，这个叫做Delta技术。

"Quake III Arena 网络协议规范(非官方)"

出于简化，Q3 使用了固定长度的同步结构，导致不少字段被不同的功能各种复用，一晦涩复杂度就上去了。

三、DOOM3 网络架构

架构

客户端把输入采样等玩家动作发给服务器，服务器回之以 PVS 内的压缩后的状态快照。

C/S 架构图

Doom3 做到了同样的玩家输入序列总是能产生同样的结果，因为以下两点得到了保证：

1.除玩家输入外整个系统的确定性 (system-wide deterministic)

2.不管渲染性能如何，整个游戏的逻辑状态总是以 60 fps 的频率更新

C/S 时间线

服务器以 10-20 Hz 的频率向客户端发状态快照。由于快照是一个 rtt 之前的状态，客户端需要回到那个时间点上去处理这个“过去的”状态，然后再基于这个状态重新预测并刷新所有物体在当下的状态，如下图：

预测示意图 (Prediction at the client with a snapshot rate at 20Hz and a ping of around 80 milliseconds)

由于玩家输入的频率 (input per second) 远低于逻辑处理的频率 (60 Hz)，一个合理的推论是，最接近当下的几个逻辑帧，继续沿用与之前同样的输入一般是安全的。客户端使用服务器同步过来的其他玩家的输入来预测其接下来的运动，这些物理响应的机制与服务器上的真实逻辑是一致的。

与 Quake 3 不同的是，玩家在屏幕上看到的渲染结果与真实的逻辑状态是无时差的 (注意是无时差而不是 100% 绝对准确)，因此不需要像 Q3 那样在本地延时比较大时需要充分考虑提前量，因为系统把下发同步的预测也完全实现了。系统的确定性保证了服务器和客户端可以运行完全一致的逻辑 (dead reckoning)，因此得到至少与服务器上一样好的行为预测结果。Quake 3 的 bot 已经展示了通过算法来预测玩家移动可以达到什么样的程度，即使用慢速导弹武器 (火箭筒 RL) 也可以非常精确地命中。(Q3 bot 使用考虑碰撞检测的简化物理逻辑来预测玩家在之后的位置)

与 Quake 3 不同，Doom 3 的服务器和客户端使用同一份代码来更新/预测实体的状态，这样不用担心早先提到的互相干扰，开发新的单人模式 (并兼容多人) 也变得更简单了。

通信

基于 UDP 的轻量级 reliable / unreliable 实现 (最小化额外负担)

对于大多数状态同步而言，像 TCP 那样重发价值不大，因为被重发的状态十有八九因为过期已经不再有意义。

Doom 3 实现了下面这样一个基于 UDP 特性的 FPS 通信架构

层次结构图

上行和下行均为单连接，同时可发送 reliable & unreliable 的消息 (前者确保抵达)，后者用于输入 (c2s) 和状态 (s2c) 的同步，只有非常特定和关键的消息使用可靠方式发送。

这个网络系统被设计为不间断地生成一个不可靠消息流 (unreliable stream) (包括 10-20Hz 的状态同步和更高频的输入同步)，可靠消息被驼运 (piggy back) 在这个不可靠消息流上 (蚂蚁搬家)。具体实现上，可靠消息被先缓存在队列里，每一个都由一个不可靠消息搭载着发出，ack 后再发下一个 (ack 直接借用了对面过来的 unreliable stream) 这样整个信道实现了最重要的保证：(通过1:1的驼载)任何一条可靠消息总是能在首个紧接着的不可靠消息之前抵达。 (the message channel guarantees that a reliable message arrives before the first next unreliable messages comes through)

此外，对于不可靠的信息流，客户端的发送频率比服务器高3-4倍 (可靠消息的运输和响应能力)，这样的话来自服务器的可靠消息是不需要 timeout 机制的，因为接下来的几个客户端消息没有 ack 的话，服务器就可以直接重发了。

Unreliable Message Headers

整个系统的大部分信息是来自服务器的状态快照 (Snapshots) 和来自客户端的玩家输入 (User Commands)，这些业务数据都通过 unreliable message 传递。(message header 如下图所示)

服务器：

32 位 game id 里包含了游戏本身的识别 id，地图信息和关键的业务设置
8 位的 message type 用来区分本条消息的类型。

客户端：

首个 seq id 是最近收到的服务器消息的序列号 (用于 ack)，unreliable message 本身是不需要 ack 的，但是当需要的时候，服务器可以在特定的时间点上用这个 seq id 检查客户端是否有及时的反馈。
game id 用于环境的合法性校验，没通过校验的话，服务器会追加一条完全配置信息，用于指导客户端去尝试进入正确的环境。
快照的 seq id 用于差异压缩 (delta compression)
同样也有 message type。

快照 (snapshots)

下图是下发快照的构成和完整的操作序列：

快照包含的几项关键信息：

序列号 (seq id)
帧编号 (frame id)
帧时刻 (frame time)
客户端领先的时间量 (client ahead time, 参考客户端最近一次发上来的时刻及延时)

实际的业务数据信息 (以下信息均做了差异压缩)：

entity states 是与上次快照相比较的状态变化
pvs bit string 是 pvs 的完整可见状态列表 (这个信息由服务器随时下发更新)
pvs 无关的游戏状态更新
其他玩家的指令信息

用户指令 (User Commands)

下图是上行的用户指令构成和完整的操作序列：

调试用的客户端预测毫秒数
这一组用户指令中，第一个的所在帧编号
后续的每个 user command 对应接下来的一帧，反映了输入的变化差异

压缩

Bit Packing

移除逻辑上的无用位。
如 Health (HP) 虽然是 32 位整形，但实际在 0-100之间，只需 7 位就够了。
浮点精度大部分取值范围不大的情况下 (如实体的移动速度，角度，朝向等) 只需要半精度。

差异压缩 (Delta Compression)

1.变量级的差异压缩。如果一个变量没变过，就写一个 0 (1 bits) 如果变过，就写 1 (1 bits) + 实际变量内容 (bit packed)

2.实体级的差异压缩。

o快照之间的差异比较

o基于一个包含完全实体信息的公共基 (common base)

o当进出某个客户端的 pvs 时开始/结束同步

3.pvs 差异压缩。

o每个实体 1 bit 则 4096 个完整信息会消耗 512 字节

o由于不同帧之间 pvs 变化不大，可以按组压缩，每组 32 bits

o如果任何一组没有实体进出 pvs，写个 0 (1 bits)

o假设 pvs 没有任何变化，4096 个对象只需要 16 字节

客户端随着 User Commands 上报的 ack 频率远高于下发快照的频率，所以丢包也没关系。服务器一旦收到 ack 就可以更新公共基并用 reliable message 通知客户端做同样的改动，驼运机制保证了 reliable message 总是先于新快照抵达客户端，这样被 ack 的快照总是能在处理新快照前被用于更新客户端的公共基。这样，公共基的状态维护就可以保证是整体上同步的

消息压缩 (0-compressor)

上面的差异压缩会产生大量的 0 (没有变化)，所以开销最小也最有效的压缩是针对 0 的特殊处理。

每次处理 3 位，如果中间有一位不为 0 就保持不变，否则继续读，直到遇到不为零的情况，此时写下三个零 (3 bits) 和重复次数 (3 bits)

最大压缩比为 4:1，这里可以用不同的位数但 3 被验证为实际压缩比最高的。

举个例子：

000'000'000'010'000'000'000'000'110'000'000'000'000'000

会被压缩为

000'011'010'000'100'110'000'101

这个例子里压缩比为 14:8。

反过来也可以针对这种压缩方式对快照中的变量排列进行优化。把变量按照改变频率分组放在一起，以促使产生更多的连续 0。

效果

bit packing: 10-15%
delta compression: 90%+
zero-compressing: 15-50%

更多的潜在改进