网络同步-帧同步/状态同步

什么是网络同步

网络同步是指通过网络将数据从一个系统或节点传输到另一个系统或节点，并保持两者之间的数据一致性。换句话说，游戏中的网络同步就是把我的状态同步给远程玩家的“我”的镜像，使双方在屏幕上看到的效果是一致的。
在常见的多人联机游戏（例如下棋、格斗、fps等等等等）中，网络同步是非常重要的一项需求。游戏中的玩家需要时时刻刻了解其他玩家的状态或者行为，才能辅助自己做出下一步决策（例如是否开枪等）。
如何知道其他玩家的状态，又如何让其他玩家知道我的状态呢？这时候就需要网络同步技术了。

同步设计目标

同步设计主要有两个目标，即 一致性 和 及时性 。在实际工程中，我们其实很难同时满足一致性和及时性，因为网络延迟始终存在，客户端在接收到最新状态前只能进行预测（采用一些客户端障眼法，例如插值）。
在这两个核心目标下，我们可以拆解出三个子设计要素，根据实际情况进行优先级权衡。一般来说用户体验是位于首位的。

• 公平
  • 确定
    操作具有幂等性，玩家执行一个操作所得的的结果是确定的。游戏存在明确的规则，玩家知道规则带来的确切的后果，因此才可以基于规则进行博弈。
  • 安全
    数据的安全性代表玩家的数据隐私不应该被第三方破坏或篡改。当计算放在客户端时，数据就很容易被篡改，造成作弊行为。
• 体验
  • 延迟
    由于网络原因，延迟很难避免。延迟分为输入响应延迟和状态延迟。
    • 输入响应延迟
      影响手感、状态变化越剧烈越敏感。对QTE判定、格斗游戏等输入敏感类游戏影响巨大。
    • 状态延迟
      影响判断，例如fps游戏中判断是否击杀对方等。
  • 稳定
    由于网络环境不稳定，可能发生抖动和丢包，一旦发生就很容易引起游戏的“顿挫感”与“拉扯感”。当网络环境中断时就会引起游戏断线，这时会触发断线重连的尝试。
• 开销
  • 流量
    流量代表客户端需要收发多少数据，流量越大越可能遇到网络问题（例如丢包），并对用户的话费造成影响，造成运维成本上升。
  • 计算量
    计算量越大对客户端的负载越大，越容易造成手机发烫、电池消耗大等问题。
  • 研发成本
    不同的同步算法的技术门槛和维护成本是不一样的，在下文中会详细说明。

传输数据分析

在网络同步中，我们一般要传输什么数据呢？在实际生活中，一款游戏可以被拆成“输入-逻辑处理-输出”三个部分。用户通过键鼠/触摸屏等设备对游戏产生输入，经过游戏的核心逻辑处理模块处理之后，将状态输出到屏幕上，最后呈现在用户面前。
那么很明显，我们需要同步的就是用户的输入的操作、或者这些操作所产生的一系列事件，将这些事件同步到其他玩家的客户端上，其他玩家的客户端就可以根据事件类型计算出对应的状态并呈现。
当然，我们也可以直接同步用户的状态，这样就省去了客户端上的计算工作。
展开说说？

一致性：帧同步

古典帧同步
古典帧同步又叫Lockstep Synchronization（锁步同步），其一大特色在于当一个人未同步完成时，其他人都必须等待直到其同步完成。

帧同步就对应于我们在上文中说的同步用户的输入的操作、或者这些操作所产生的一系列事件。之所以被称之为“帧”同步，是因为帧同步是以固定频率（比如60Hz）同步玩家的下一帧的操作的。
在这个过程中，客户端将指令发送给服务端，服务端只做指令的转发（指令->指令），其他客户端接收到服务端传来的指令后进行对应的计算。

正由于最终同步体现在各个服务端接收到指令后计算结果的一致性上，因此帧同步最核心的依赖就是“同样的程序对于同样的输入会产生完全一致的结果”。如果这一前提无法被保证，就无法达成一致性。
由于硬件平台的不同，还真可能出现计算结果不一致的情况（例如用ios和win/Android计算sin(15)得到的值不同，这是因为ios的FPU位宽更大），我们就需要想尽办法避免这种情况出现。例如对于浮点数计算精度的问题，可以采用更改FPU位宽或用定点数计算。

保证一致性逻辑的几种方法

• 保持客户端版本一致（相同的逻辑模块）
• 不要依赖不确定性的外部逻辑（如UI交互逻辑）
• 限制外部逻辑（如UI）对核心逻辑的调用
• 谨慎使用多线程

• 优点
  • 服务器逻辑简单，负载低，不需要做任何计算
  • 项目研发周期缩短
  • 表现一致性高（所有指令都来自服务端）
  • 同步流量小，带宽成本低（一帧的输入量小）
  • 天然支持观战、录像、回放（记录了所有指令，逐个执行就是回放了）
  • 实时性表现好（适用于act/ftg/spg/rts/moba等）
• 缺点
  • 反外挂问题严峻（计算都在客户端上，容易被篡改）
  • 网络延迟敏感度高（容易卡顿）
  • 不同步问题较难定位和解决
  • 单局规模受限（否则一帧内包含的指令太多），不适合中途加入角色的游戏

一致性：状态同步

而状态同步就类似于我们在上文中说的直接同步用户的状态。客户端将指令发送给服务端，服务端计算出状态后广播给其他客户端，客户端收到后进行更新。这样虽然会加重服务端的运算负载，但可以有效避免客户端作弊的发生。
当然，我们还可以结合一下分布式运算的想法，将计算压力分摊到客户端上。在这种模式中，客户端将部分指令即时计算成状态之后，将状态发送给其他客户端（其他客户端同理），其他客户端收到后进行更新。

状态同步的临界问题

仔细观察下图所示的临界情况：

在这个情况中，假设下方的玩家向上走了一步，发送“向上一步、夺旗”的状态；而上方的玩家在接收到这个状态之前向下走了一步，发送“向下一步、夺旗”的状态。此时两个玩家的状态都变成了“夺旗”，到底谁获得了胜利呢？这就涉及到状态同步的仲裁权问题。两个玩家都在竞争“仲裁权”，我们需要结合具体的信息（例如状态更新的时间）进行公平公正的仲裁。有两种可行的思路：

• 强一致性
  • 服务器模式就是一种强一致性的方式，因为只存在一个逻辑仲裁点（服务器），这从根本上避免了冲突。
  • 在分布式模式中，不同客户端仅对单一状态进行仲裁，两个客户端不能仲裁同一个状态，实现仲裁权的分割。只不过这个做法比较理想化，不符合联机游戏的特征、存在扩展风险。
• 弱一致性
  在弱一致性方法中，我们首先要对所有一致性做一个区分：哪些是核心一致性，哪些是非核心一致性？
  • 核心一致性：可能影响双方的状态采用单点仲裁处理、异步交互（如：fps游戏中是否命中、赛车游戏中的道具）
    • 单点逻辑仲裁对操作响应的延迟很敏感。
    • 比较慢，因为需要服务器计算后合包再发送给各个客户端，这中间存在时延。因此更适合对核心仲裁延迟相对不敏感的情况（比如fps的命中判定并不是立刻判定完成的，但结合“子弹存在飞行时间”等ux因素，对玩家的体验影响并不太大）。
    • 一致性有容错空间。
  • 非核心一致性：仅对自身有影响的状态采用仲裁分割、延迟同步（如：赛车游戏中自身位置、fps游戏中的位置等）
    • 对于物理、3D这些比较复杂的运算，如果全部交给服务端将对其造成较大的计算负荷，因此这部分状态判定可以交由客户端本身进行处理。

fps的回溯判定

fps对于精度的判断要求很高，在存在服务器状态延迟、射击指令延迟的时候应该怎么准确的进行命中仲裁呢？此时服务器需要回溯射击发生当时的状态，进行判断。

在上图所示的例子中，蓝色玩家在射击时向服务器发送了射击指令，经过延迟服务器收到后计算出橙色玩家已经走到了下面的位置、子弹飞到了右侧的位置，此时子弹和橙色玩家并没有接触。
但我们就可以直接判断子弹没有命中橙色玩家吗？显然是不行的，因为我们不知道子弹飞行的过程中是否击中了橙色玩家，因此需要做“回溯判定”的操作。服务器会采用一些高效的逐帧检查，直到检测出命中/不命中。

• 优点
  • 适合小规模状态/可划分子系统（适用于fps/赛车/三消等）
  • 较小的计算量
  • 输入延迟低，因为本地就计算好状态了
  • 技术门槛低
• 缺点
  • 大规模状态时同步的数据也大
  • 流量大
  • 分布式计算/复杂逻辑的一致性难以协调，导致后期维护成本高

及时性：通用方案

我们需要考虑为同步的及时性选择一个恰当的网络协议了。传输层有两个著名的协议：TCP 和 UDP。在保证 UDP 传输可靠性的情况下，我们可以有“可靠UDP（RUDP）”。那么，该选择 TCP 还是 RUDP 呢？

可以看到，在不同的网络环境下，RUDP的平均延迟都是要好于TCP的。因此在实际开发的过程中，一般选择RUDP作为传输层协议。
那么，应该怎么实现可靠UDP呢？

基于ARQ（自动重传请求）

首先，我们需要了解以下几个概念：

• RTT（Round Trip Time）
  RTT指的是从客户端发送数据包到客户端收到服务端返回确认数据包（ACK包）的时间间隔，这段时间被称为往返时间（RTT）。

• RTO（Retransmission Timeout）
  RTO指的是超时重传时间，即在客户端发送数据包后，在RTO时间内未收到服务端的ACK包，就会重新发送一个数据包过去。一般来说，RTO = 1.5RTT

• 最小丢包延时
  当丢包发生时，接收方最终收到发送的数据包的最小延时（也就是RTO后发送的包到达接收方的时间）。一般来说，最小丢包延时 = 2RTT

基于上面的三个概念，我们可以发展出以下两种实现RUDP的方式：

1. 等待式
   每次客户端发送一个包，都要等到收到服务端的ACK包后才发送下一个。这种实现模式对信道的浪费比较严重。
   
2. 后退N步
   客户端每次发一堆包，收到服务器的一堆ACK包后检查有没有哪个漏了，有的话从漏掉的包开始重新发送（服务器会丢弃缺漏包后的所有包）。这种模式对流量的占用较大，浪费了信道资源。
   
3. 选择重发
   和后退N步类似，但只选择性地重发未收到ACK包的包，服务器不会丢弃其他包。
   

在ARQ中，已经有了大量现成的解决方案（如KCP），但其最小丢包时延较高。

基于FEC（前向冗余纠错）

在FEC中，最小丢包延迟比ARQ的小，但它只适用于帧同步中，并且实现算法比较复杂、没有现成的实现方案（需要自己造轮子）。

丢包时应该怎么办？

丢包分为两种：相关性丢包和随机性丢包。

1. 相关性丢包
   这种丢包通常是由链路拥塞、路由器负载过高、无线信号衰减、基站/场景切换等程序员无法干预的情况导致的。我们知道丢包的原因，但无法解决。
2. 随机性丢包
   这种丢包通常是由于二进制信道噪声产生的，完全是随机出现的，将近90%的丢包都属于这种类型。
   基于吉尔伯特模型，我们可以计算出连续K次丢包的概率（随着k的增加，概率是会越来越低的）。因此，为了避免随机性丢包，我们可以连发2次同一个包（如果2次不够就发送3次）。

UDP包与MTU
由于网络信道存在MTU的概念，当一个UDP包的大小超过MTU时，打包就会被拆成IP分片小包，在收到时再重组成UDP大包。
但分成小包进行传输，其实是很容易遇到丢包的情况的。一旦IP分片中有一个包丢失了，系统就会丢弃整个UDP大包。
因此，我们有时候需要人为地将一个UDP大包拆成小包发送，并留意信道的MTU大小。经验MTU大小为470字节。

---

对时方案

什么是“对时”？简单来说，对时就是“对齐时间轴”的简称。对于帧同步来说，我们需要对齐第一帧；而对于状态同步来说，我们需要对齐所有状态。说的轻巧，怎么对时呢？

https://zh.wikipedia.org/wiki/網路時間協定#时钟同步算法

预表现

预表现也就是我们常说的“客户端障眼法”。在还未获取玩家的状态或者帧的情况下，我们不能让玩家卡在某个地方（否则会带来很强的顿挫感），而是需要通过插值和预测做出预表现。
因此，在预表现中，存在两个重要的算法：预测算法和插值算法。

• 预测算法
  根据当前的状态预测下一个状态。最经典的预测算法是“航位推测算法（Dead Reckoning）”，常用于交通技术层面，但容易收到误差积累的影响。
  • 规则（人为设置的规则，辅助预测）
  • 无用户输入（硬直状态，根据状态机进行判断）
  • 寻找积分导数（位移是速度积分算的，速度是加速度积分算的，…）
  • 用户输入有限（一个用户就十个指头，手速有限）
• 插值算法
  根据两个状态，平滑地进行过度。插值其实是一个瘦时间影响的操作序列，主要起到视觉上的平滑效果，符合游戏规则。
  • 使用录像数据进行与训练
  • 用户个性化样本训练

除了这两种方法之外，我们还可以寻找视觉掩饰，例如设置前摇与后摇，提供缓冲时间。

方案对比

回到前文的“同步算法设计七大要素”，我们现在可以对比一下帧同步与状态同步在这七大要素中的表现情况了：

• 公平
  • 确定
    • 帧同步：具有强一致性
    • 状态同步：非本地仲裁的数据有延迟或需要修正
  • 安全
    • 帧同步：输入数据和状态数据可能被篡改，拥有所有玩家的状态，隐私问题难以保障。
      在这种情况下，服务器需要进行完整逻辑校验，并对关键状态进行校验（投票）。
    • 状态同步：本地的输入数据和状态数据可能被篡改，远端的状态数据是隐私的。
      对延迟敏感的项目，可以本地维护状态、服务器后校验；对延迟不敏感的项目，可以直接通过服务器维护状态。
• 体验
  • 延迟
    • 帧同步：网络优化，采用RUDP
    • 状态同步：对网络抖动不敏感，可用RUDP也可用TCP
  • 稳定
    • 帧同步：断线重连非常复杂，需要服务器缓存所有帧数据，发回给客户端，从断线处开始播放到当前帧
    • 状态同步：可以由服务器保存当前状态，重连时使用该状态即可
• 开销
  • 流量
    • 帧同步：同步指令，同步流量小
    • 状态同步：同步状态，同步流量大
      可以通过优化编码格式、设置电平触发/边沿触发（是每秒发送按键，还是在按键变化时发送？）、区分重要/不重要数据的方式优化流量开销。
  • 计算量
    • 帧同步：计算量全部集中在客户端（因此无法维护大规模的游戏）
    • 状态同步：部分计算量在客户端（本地状态），部分计算量在服务端
  • 研发成本
    • 帧同步：技术门槛高、维护成本高、研发周期短
    • 状态同步：技术门槛低、维护成本高（随着状态复杂而复杂化）、研发周期长