网络同步在游戏历史中的发展变化（三）—— 状态同步的发展历程与基本原理（上）

网络同步在游戏历史中的发展变化（一）—— 网络同步与网络架构

网络同步在游戏历史中的发展变化（二）—— Lockstep与帧同步

目录（第三篇）：

四.State Synchronization 状态同步

  1.雷神之锤与快照同步

 （Quake and Snapshot）

  2.星际围攻：部落中的网络架构 （The TRIBES Engine  Networking Model）

  3.客户端预测与回滚（Client-side prediction and Rollback）

  4.事件锁定与时钟同步 (Event Locking and Clock  Synchronization)

  5.插值技术（Interpolation and Extrapolation ）

在二十年前，相比于使用帧同步（为了方便描述，后续的文章中以帧同步代替Lockstep）还是状态同步，开发者们更关心的是网络架构的实现方式（P2P/CS)。换句话讲，在当时业内看来，P2P架构的同步模型虽然减少了延迟，但由于作弊、跨平台、难以维护大型网络游戏等问题，人们更希望用CS架构来取代P2P。同时，开发者们虽然可以继续在CS架构下使用逻辑比较简洁的帧同步，但有不少开发者都认为刚刚诞生的状态同步貌似更符合CS架构的同步理念。

需要强调的是，帧同步与状态同步并不是一个简单的对立概念，其中的差异包括“数据格式与内容”，“逻辑的计算位置”，“是否有权威服务器”等 。随着时间的推进，两种算法互相借鉴互相发展，早已不是当年的样子。网上存在很多概念模糊的文章，包括一些大佬对同步的概念理解也有偏差，这些都很容易对新手产生误导。所以笔者建议，如果你想真正的了解或者学习网络同步，不妨跟着这篇文章去了解二者的发展历史，相信看过后的你一定能更深刻的理解到帧同步与状态同步的异同。（文末同上篇一样贴出了大量的文献内容）

1.雷神之锤与快照同步（Snapshot）

快照是一个通用的行业术语，即在任何给定时刻记录设备的状态并在设备出现故障时进行还原。快照技术常用于计算机的各种存储系统，例如逻辑卷管理、数据库、文件系统等。在游戏领域中，快照的含义更像是照片一样，将当前场景所有的信息保存起来。严格来说，快照同步应该属于状态同步的前身，虽然思想相似但是具体实现却有不小的差异。

1996年，在doom发行不久后，Id software就公开了新作——雷神之锤（Quake）。在Quake里他们舍弃了之前的P2P而改用CS架构，同时也舍弃了lockstep的同步方式。新的架构下，客户端就是一个纯粹的渲染器(称为Dumb Client)，每一帧玩家所有的操作信息都会被收集并发送到服务器，然后服务器将计算后的结果压缩后发给客户端来告知他们有哪些角色可以显示，显示在什么位置上。

上述的这个过程就是我们所说的快照同步，即服务器每帧接受客户端的输入来计算整个世界的状态，然后将结果快照发送给所有客户端。Quake这里所谓的快照，就是把整个游戏世界里面所有对象的状态做一次临时保存（他更强调的是对象的可视化状态，比如位置和旋转等）。通过这个快照，我们可以还原出这一刻世界的状态应该是什么样子的。

Quake运行时，逻辑帧率与渲染帧率是保持一致的。由于所有的核心逻辑都是在服务器进行，所以也不需要通过锁步来避免客户端不同步的问题，只要在收到服务器消息后执行渲染就好了。当然，对于性能以及网络环境较差的玩家来说，游戏体验仍然很糟糕。因为你按下一个按钮后，可能很长时间都没有反应，当收到服务器的快照消息后，你可能已经被网络好的玩家击杀了。

IdSoftware自2012年以来已经陆续把Quake以及Doom相关的源码上传到了GitHub上面[4]。如果你看过其中Quake的源码，会发现整个网络的架构还是比较简单清晰的，博主FABIEN SANGLARD就在网上分享了关于Quake源码的剖析[5]（还有很多其他项目的源码剖析）。

//client   WinMain  {    while (1)    {        newtime = Sys_DoubleTime ();        time = newtime - oldtime;        Host_Frame (time)        {          setjmp          Sys_SendKeyEvents          IN_Commands          Cbuf_Execute
          /* Network */          CL_ReadPackets          CL_SendCmd
          /* Prediction//Collision */          CL_SetUpPlayerPrediction(false)          CL_PredictMove          CL_SetUpPlayerPrediction(true)          CL_EmitEntities
          /* Rendition */          SCR_UpdateScreen        }        oldtime = newtime;    }  }

但Quake里面由于客户端只是一个简单的渲染器，同步过程中会出现很多明显的问题，比如延迟过大，客户端性能浪费，服务器压力大等。而其中最明显的问题就是对带宽的浪费，对于一个物体和角色比较少的游戏，可以使用快照将整个世界的状态都存储并发送，但是一旦物体数量多了起来，带宽占用就会直线上升。所以，我们希望不要每帧都把整个世界的数据都发过去，而是只发送那些产生变化的对象数据（可以称为增量快照同步）。更进一步的，我们还希望将数据拆分的更细一些，并根据客户端的特点来定制发送不同的数据。基于这种思想，《星际部落：围攻》团队的开发者们开始对网络架构进行抽象和分层，构造出来一套比较完善的"状态同步"系统并以此开发出了Tribe游戏系列。

The TRIBES Engine可以认为是第一个实现状态同步的游戏引擎，《星际部落：围攻》也可以认为是第一个比较完美的实现了状态同步的游戏。

下图是该引擎的网络架构[6]：

平台数据包模块（Platform Packet Module）可以理解成被封装的Socket模块，连接管理器（Connection Manager）处理多个客户端与服务器的连接，流管理器（Stream Manager）负责将具体的数据分发到上面的三个高级管理器。

• Ghost管理器：负责向客户端发送需要同步对象的状态信息，类似属性同步。

• 事件管理器：维护事件队列，每个事件相当于一个的RPC。

• 移动管理器：本质上与事件管理器相同，但是由于移动数据的需要高频的捕捉和发送，所以单独封装成一个特殊的管理器。

3.客户端预测与回滚

（Client-side prediction and Rollback）

《毁灭公爵》是上世纪90年代一个经典的FPS游戏系列，首部作品的发布时间与Doom几乎相同，网络架构也极为相似。在1996年发布的《毁灭公爵3D》里面，为了提高客户端的表现与响应速度，他放弃了“Dumb客户端”的方案并首次采用客户端预测来进行优化（这里主要指移动预测）[7]。即在服务器确认输入并更新游戏状态之前，让客户端立即对用户输入进行本地响应。由于这种方式可以大大的降低网络延迟所带来的困扰，很快的Quake也开始参考对网络架构进行的大刀阔斧的修改。在1997年发布的更新版本QuakeWorld里面[8][9]，Quake添加了对互联网对战的支持以及客户端预测等新的内容。

关于预测，其实就是本地先执行，所以并不需要什么特别的算法，反倒是预测后的客户端与服务器的同步处理有很多值得优化的地方。由于玩家的行为是没办法完全预测的，所以你不知道玩家会在什么时候突然停下或者转弯，所以经常会发生预测失败的情况。

如果玩家本地的预测结果与服务器几乎一致，那么我们认为预测是成功且有效的，玩家不会受到任何影响，可以继续操作。反之，如果客户端结果与服务器不一致，我们应该如何处理呢？这里分为两种情况。

一.在没有时间戳的条件下，收到了一条过时的服务器位置数据。你在本地的行为相比服务器是超前的，假如你在time=10ms的和time=50ms时候分别发送了一条指令。由于网络延迟的存在，当你已经执行完第二个指令的时候才收到服务器对第一条指令的位置同步。很明显，我们不应该让过时的服务器数据来纠正你当前的逻辑。解决方法就是在每个指令发出的时候带上他的时间戳，这样客户端收到服务器反馈的时候就知道他处理的是哪条指令信息。

二.假如我们在指令里面添加了时间戳的信息，并收到了一条过时的服务器位置数据。在上一篇文章里我们提到了TimeWarp算法，即当一个对象收到了一个过去某个时刻应该执行的事件时，他应该回滚到那个时刻的状态，并且回滚前面所有的行为与状态（包括取消之前行为所产生的事件）。这个时候我们可以用类似的方法在本地进行纠正，大体的方案就是把玩家本地预执行的指令都记录好时间戳并存放到一个MOVE BUFFER列表里（类似一个滑动窗口）。如果服务器的计算结果与你本地预测相同，可以回复你一个ACKMOVE。如果服务器发现你的某个移动位置有问题时，会把该指令的时间戳以及正确的位置打包发给你。当你收到ACKMOVE的时候，你可以把MOVE BUFFER里面的数据从表里面移除，而当你收到错误纠正信息时就需要本地回滚到服务器指定的位置同时把错误时刻后面MOVE BUFFER里面的指令重新执行一遍。这里读者可能会产生一个疑问——为什么不直接拉回？因为这时候他想纠正的是之前的错误而不是现在的错误，如果简单的拉回就会让你觉得被莫名其妙的拉回到以前的一个位置。同时，考虑到已经在路上的指令以及后续你要发送的预测指令，会让服务器后续的校验与纠正变得复杂且奇怪，具体流程细节可以参考下图。另外，Gabriel Gambetta博主在他的文章中，也对这种情况进行了简单的分析[10]。

关于TimeWarp算法的补充：Timewarp技术最早出现于仿真模拟中[11]，我们可以认为这些仿真程序中采用的是“以事件驱动的帧同步”。也就是说，给出一个指令，他就会产生并触发多个事件，这些事件可能进而触发更多的事件来驱动程序，同理取消一个过去发生的事件也需要产生一个新的取消事件才行。这样造成的问题就是回滚前面的N个操作，就需要产生N个新的对抗事件，而且这N个事件还需要发送到所有其他的客户端执行。如果这N个事件又产生了新的事件，那么整个回滚的操作就显得复杂了很多。换成前面移动的例子来解释一下，就是客户端收到服务器的纠正后，他会立刻发送回滚命令告诉（P2P架构下）所有其他客户端，我要取消前面的操作，然后其他客户端在本地也执行回滚。而在如今的CS架构状态同步的方式下，服务器可能早就拒绝了客户端的不合法行为，所以并不需要处理回滚（同理，其他客户端也是）。所以严格来说，TimeWarp技术以及优化后的BreathTimeWarp技术[12]都是针对“以事件驱动的帧同步”，并不能与预测回滚这套方案完全等价。当然，随着时间的推移，很多概念也变的逐渐宽泛一些，我们平时提到的时间回溯TimeWarp技术大体上与快照回滚是一个意思的。

4.事件锁定与时钟同步(Event Locking and Clock Synchronization)

1997年，Jim Greer与Zack Booth Simpson在开发出了他们第一款基于CS架构的RTS游戏——”NetStorm：Island at war“。随后在发布的文章中又提出了“事件锁定”这一概念[13]，相比帧同步会受到其他客户端延迟的影响，事件锁定是基于事件队列严格按序执行的，客户端只管发消息然后等待服务器的响应即可，其他时候本地正常模拟，不需要等待。在目前常见的游戏中，我们很少会听说到事件锁定这种同步方式，因为事件锁定的本质就是通过RPC产生事件从而进行同步（也就是排除属性同步的状态同步）。事件锁定在CS架构上是非常自然的，相比帧同步，可以定义并发送更灵活的信息，也不必再担心作弊的问题。

不过，由于事件中经常会含有时间相关的信息（比如在X秒进行开火）以及服务器需要对客户端的不合法操作进行纠正，所以我们需要尽可能的保持客户端与服务器的时钟同步。实现时钟同步最常见且广泛的方式就是网络时间协议（Network Time Protocol，简称NTP）[14]，NTP属于应用层协议下层采用UDP实现，1979年诞生以来至今仍被应用在多个计算机领域里，包括嵌入式系统时间、通信计费、Windows时间服务以及部分游戏等。NTP使用了一种树状、半分层的网络结构来部署时钟服务器，每个UDP数据包内包含多个时间戳以及一些标记信息用来多次校验与分析，

整个时钟同步的具体算法涉及到非常多的细节，我们这里只考虑他的时钟同步算法（其他的内容请参考历年的RFC）：

假如一个服务器与客户端通信，客户端在t0向服务器发送数据，服务器在t1收到数据，t2响应并回包给客户端，最后客户端在t3时间收到了服务器的数据。

二者的时间差为“θ”，假如往返延迟相同，则有

所以可以将“θ”定义为

将往返延迟相加，那么可以得到一个RTT延迟

当然，该操作不会只执行一次，客户端会同时请求多个服务器，然后对结果进行统计分析、过滤，并从最好的三个剩余候选中估算时间差，然后调整时钟频率来逐渐减小偏移。如果我们的系统对精度要求不是非常高，我们还可以使用简化版的SNTP(Simple Network Time Protocal），时钟同步算法与NTP是相同的，不过简化了一些流程。

不过无论是NTP还是SNTP，对于游戏来说都过于复杂（而且只能用UDP实现）。因此Jim Greer等人提出了“消除高阶的流式时间同步”，流程如下：

• 1. 客户端把当前本地时间附在一个时间请求数据包上，然后发送给服务器

• 2. 服务器收到以后，服务器附上服务器时间戳然后发回给客户端

• 3. 客户端收到之后，用当前时间减去发送时间除以2得到延迟。再用当前时间减去服务器时间得到客户端和服务端时间差，再加上半个延迟得到正确的时钟差异 delta=(Currenttime - senttime)/2

• 4. 第一个结果应该立刻被用于更新时钟，可以保证本地时间和服务器时间大致一致

• 5. 客户端重复步骤1至3多次，每次间隔几秒钟。期间可以继续发送其他数据包的，但是为了结果精确应该尽量少发

• 6. 每个包的时间差存储起来并排序，然后取中位数作为中间值

• 7.丢弃和中间值偏差过大（超出一个标准偏差，或者 超过中间值1.5倍）的样例，然后对剩余样例取算术平均

上述算法精髓在于丢弃和中间值偏差超过一个标准偏差的数值。其目的是为了去除TCP中重传的数据包。举例来说，如果通过TCP发送了10个数据包，而且没有重传。这时延迟数据将集中在延迟的中位数附近。假如另一个测试中，如果其中第10个数据包被重传了，重传将导致这次的采样在延迟柱状图中极右端，处于延迟中位数两倍的位置。通过直接去掉超出中位数一个标准偏差的样例，可以过滤掉因重传导致的不准确样例。（排除网络很差重传频繁发生的情况）

5.插值技术 （Interpolation and Extrapolation ）

插值技术在早期的帧同步就被应用到游戏里面了。或者说更早的时候就被应用到军事模拟，路径导航等场景中。插值分为内插值[15]（ interpolation ）以及外插值[16]（extrapolation，或者叫外推法）两种。

内插值是一种通过已知的、离散的数据点，在范围内推求新数据点的方法（重建连续的数据信息），常见于各种信号处理和图像处理。在这篇文章中，我们指根据已知的离散点在一定时间内按照一定算法去模拟在点间的移动路径。内插值具体的实现方法有很多，如

片段插值（Piecewise constant interpolation）线性插值（Linear interpolation）多项式插值（Polynomial interpolation）样条曲线插值（Spline interpolation）三角内插法（trigonometric interpolation）有理内插（rational interpolation小波内插（wavelets interpolation）

多项式插值与线性插值对比

外插值，指从已知数据的离散集合中构建超出原始范围的新数据的方法，也可以指根据过去和现在的发展趋势来推断未来，属于统计学上的概念。与外插值还有一个相似的概念称为DeadReckoning（简称DR），即导航推测。DR是一种利用现在物体位置及速度推定未来位置方向的航海技术，属于应用技术方向的概念。DR的概念更贴近游戏领域，即给定一个点以及当前的方向等信息，推测其之后的移动路径，外推的算法也有很多种，

线性外推（Linear extrapolation）多项式外推（Polynomial extrapolation）锥形外推 （Conic extrapolation）云形外推 （French curve extrapolation）

在游戏中，一般按照线性外推或匀变速直线运动推测即可。不过，对于比较复杂的游戏类型，我们也可以采用三次贝塞尔曲线、向心Catmull-Rom曲线等模拟预测。

总之，无论是内插值还是外插值，考虑到运算的复杂度以及表现要求，游戏中以线性插值、简单的多项式插值为主。

应用：

早期的lockstep算法中，在一个客户端在收到下一帧信息前，为了避免本地其他角色静止卡顿，会采用外插值来推断其接下来一小段时间的移动路径[17][18]。普通DR存在一个问题（参考下图），t0时刻其他客户端收到了主机的同步信息预测向虚线的方向移动，不过主机客户端却开始向红色路径方向移动，等其他客户端在t1时刻收到同步信息后会被突然拉倒t1'的位置，这造成了玩家不好的游戏体验。为了解决从预测位置拉扯到真实位置造成的视觉突变，我们会增加一些相应的算法来将预测对象平滑地移动到真实位置。

在状态同步中，由于客户端每次收到的是其他的角色的位置信息，为了避免位置突变，本地会采用内插值来从A点过度到B点。插值的目的很简单，就是为了保证在同步数据到来之前让本地的角色能有流畅的表现。

— 未完待续 —

—   觉得不错请帮忙转发、分享、点个在看吧   —

参考文献：

[1]"State Synchronization's Role in High Availability"  Available:http://etutorials.org/Networking/Check+Point+FireWall/Chapter+13.+High+Availability/State+Synchronization+s+Role+in+High+Availability/[Accessed:2020-07-17][2]WIKI, "Check Point VPN-1" Available: https://en.wikipedia.org/wiki/Check_Point_VPN-1[Accessed:2020-07-17][3]Check Point Documentation, "Synchronizing Connections in the Cluster" Available:https://sc1.checkpoint.com/documents/R80.10/WebAdminGuides/EN/CP_R80.10_ClusterXL_AdminGuide/html_frameset.htm?topic=documents/R80.10/WebAdminGuides/EN/CP_R80.10_ClusterXL_AdminGuide/7288[Accessed:2020-07-17][4]id-Software,"GitHub Game Source Code" Available:https://github.com/id-Software [Accessed:2020-07-17][5]FABIEN SANGLARD," FABIEN SANGLARD'S WEBSITE With GameSource Code Analysis " Available:https://fabiensanglard.net/ [Accessed:2020-07-17][6] Mark Frohnmayer, Tim Gift, "The TRIBES Engine Networking Model or How to Make the Internet Rock for Multi player Games", 1998. Available: https://www.gamedevs.org/uploads/tribes-networking-model.pdf[Accessed:2020-07-17][7]WIKI, "Client-Side Prediction" Available:https://en.wikipedia.org/wiki/Client-side_prediction  [Accessed:2020-07-17] [8]id-Software,"The Quake 2 Networking Data Flow" Available:http://www.gamers.org/dEngine/quake2/Q2DP/Q2DP_Network/Q2DP_Network.html#toc4 [Accessed:2020-07-17][9]WIKI, "QuakeWorld"  Available:https://en.wikipedia.org/wiki/QuakeWorld[Accessed:2020-03-24] [10]Gabriel Gambetta," Client-Server Game Architecture" Available:https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html[Accessed:2020-07-17][11]Dacid Jefferson,Henry Sowizral "Fast concurrent simulation using the time wrap mechanism " 1982.Available: https://www.rand.org/content/dam/rand/pubs/notes/2007/N1906.pdf[[Accessed:2020-07-17][12]M. Damitio S. J. Turner，"Comparing the Breathing Time Buckets Algorithm and the Time Warp Operating System on a Transputer Architecture” January 1999. Available:https://www.researchgate.net/publication/2763616_Comparing_the_Breathing_Time_Buckets_Algorithm_and_the_Time_Warp_Operating_System_on_a_Transputer_Architecture[Accessed:2020-07-17][13]Jim Greer, Zack Booth Simpson, "Minimizing Latency in RealTine Strategy Games" Game Progamming Gems 3 chapter 5.1, 2001.[14]]WIKI, "Network Time Protocol" Available:https://en.wikipedia.org/wiki/Network_Time_Protocol[Accessed:2020-07-17][15]WIKI, "Interpolation" Available:https://en.wikipedia.org/wiki/Interpolation[Accessed:2020-07-17][16]WIKI, "Extrapolation" Available:https://en.wikipedia.org/wiki/Extrapolation[Accessed:2020-07-17][17]Jesse Aronson, "Dead Reckoning: Latency Hiding for Networked Games" September 19, 1997.Available:https://www.gamasutra.com/view/feature/131638/dead_reckoning_latency_hiding_for_.php[Accessed:2020-07-17][18]梁白鸥等,“Dead Reckoning技术在网络游戏中的应用” 2007.Available:http://www.arocmag.com/getarticle/?aid=2f665567e92cf534[Accessed:2020-07-17]