150ms流畅体验 NBA2KOnline如何网络同步优化

前言

为了不想彻底沦落为技术理论文章， 所以对于技术细节，仅贴图展示一下。希望大家阅读时，能找到一些感兴趣的内容，一起交流。

NBA2KOnline介绍

NBA2KOnline游戏是我们与Take-Tow，2K sports，以及中国团队VCC合作开发的一款拟真的篮球游戏。

目前，游戏采用服务器帧同步技术， 该技术助长游戏不断攀升到更高的目标。

目前，在我们的体验统计中，超过85%的玩家操作延迟 < 150ms。

（操作延迟为玩家输入后，看到输入表现的时间差，150ms是流畅的分界线）

NBA2K原本是一款Console game，从2K9开始登陆PC平台。游戏真实的呈现了NBA比赛，富有技巧的操作，极其逼真的物理碰撞表现，是其最大的特色。

项目团队是分布式开发模式，VCC负责Game core，我们负责Lobby，期望能发挥各自的优势。

LOL不卡，为什么NBA觉得卡

玩过LOL，DOTA的人，再玩过NBA2KOnline，你会情不自禁的觉得NBA更卡，我们也想了很久，其实这里面是有原因的，我试图分析下。

先定义一个名词：【持续即时操作】

所谓持续性操作， 典型就是要按住键盘，或移动鼠标，进行移动或选择目标。

画面卡顿会造成视觉上停顿，更重要的是打断了【持续即时操作】，画面停顿可以脑补， 但操作停顿就不能愉快的玩耍了。

来分析下各个游戏的持续性操作：

可看到游戏类型不同，网络要求差别也大。越是即时和拟真的游戏，对操作延迟和画面稳定性要求越高，NBA这种体育动作游戏，是所有游戏要求几乎最高的，做个比喻，LOL玩家像是拿炮的，CF是拿枪的，而NBA靠肉搏，对操作敏捷要求高。

另外一种从碰撞细碎性来说：   NBA  >  CF> LOL, 碰撞点太小太细就意味着对操作延迟，和画面流畅性要求更高。

旧架构P2P + Lockstep的问题

最初，网络同步模型采用P2P + Lockstep的方式，这也是欧美公司一脉相承的方法。这部分逻辑集成在Game core中，

特点是：

n         比赛时客户端之间选择一个做主机。

n         P2P：该P2P是广义的概念，包含局域网直连，以及我们补充的P2P穿透，P2P Server转发等技术。

这种方式，局域网自然没问题，可一旦到了更复杂的中国Internet，就问题不断：

n         一人卡，大家卡。同步机制缺少容错，一个客户端按住窗口边框，主机就处于等待状态，结果让其他客户端也都处于停滞。类似的， 只要一个客户端卡顿，会造成所有人也卡顿。

n         网络集成到Game core中，如果想要优化网络，沟通成本很高；靠欧美公司来优化中国网络的体验，实在没有信心。

新架构Relay Server + Lockstep的特点

新架构以帧同步服务器（Relay Server）为中心，进行消息同步转发的机制， 该机制更像MMO的架构， 但是不耦合游戏逻辑，变得很通用，非常适合几人到十几人的即时竞技游戏。

架构非常简单，如下：

n         基本流程是：

1)        Game core不断上报操作数据给Relay Server，30帧 Input/s

2)        Relay Server，整合各个客户端的输入，然后输出Frame数据，到每个客户端，30 Frame/s

3)        Game core接收Frame，拿去渲染，渲染时，接收下一帧操作，继续从1）循环

n         服务器帧同步原理

该机制，各个客户端画面表现完全一致，没有预先表现，比赛中每个Game core不断从RelayServer获得相同的Frame，每个客户端逻辑处理一致，结果也一致，输出的得分，篮板等事件也一致，这点，是防作弊的基础。

n         开发分工

1)        Game core：渲染Frame，接受操作数据，驱动下一帧

2)        我们：接受操作数据，在Relay Server中整合，广播Frame，client缓冲Frame，然后送入Game core。

为什么同步Input，而不是Action

关于同步点，可以是

n         Input: 鼠标，键盘，手柄等操作数据

n         Action:游戏逻辑层的动作触发、技能等

对于MMO各类游戏，可以使用Action同步，因为Action时间粒度很粗，客户端可以从容的做预测拉扯等表现的优化。当然服务器就必然包含游戏逻辑，所以瓶颈往往不在网络IO，而在CPU。

而对于NBA这种即时动作游戏来说，没有预定操作，完全即时碰撞，每一帧动作都是后续计算的基础，同步的时间粒度一般是1帧（1/30 秒），这对网络优化的要求很高。

Input 和 Frame的说明

n         Input是玩家的操作输入数据

如果把Input是按键等状态的全量， 那么就可以丢失，如果是操作的增量就不能丢失了。我们采用的是状态全量，丢失的Input被认为操作状态未曾改变。每个Input size并不大，不足16 byte。

n         Frame是同一局比赛中各玩家的Input的1帧整合

              Lockstep机制要求Frame不能丢失，丢失将导致各个客户端无法计算一致，网络协议要确保不丢包。1Frame size = N * Input size。

Frame如何生成?以及硬件时钟误差

每个客户端时间戳一样， 然后和服务器的时间戳也一样，这么简单的事儿，Input 1 放到 Frame1不就OK啦，so easy，我们曾经是这么想。

经过测试我们发现：只要是电脑，时间戳都有误差。 一般是万分之一以下，即一万秒，会有1秒的误差，也有更糟糕的。

如果按上述方法做， 那么当一局游戏结束时，每个客户端至少造成1帧以上的延迟。

所以，我们没有把Input和Frame严格对应起来，就用最新的Input，放到当前的Frame，过时的Input丢弃掉。带来额外的好处就是，还降低一定的操作延迟。

新架构的疑问

1.        每个客户端上下行共60个消息，服务器吃得消吗？

实际结果是，网络上总的流量比之前要节省的多， 之前每客户端N*10K Byte/s现在< 5K byte/s。

2.        速度快不快？

如果玩家跨城，跨省，甚至跨ISP，此时，P2P不一定比Relay Server快，且P2P存在相当比例的连不通，依然要转发。

更重要的是：

之前P2P玩家网络关系是网状，Relay server玩家的关系是星状，经验告诉我们，星状比网状更容易优化。

Relay server的各种优化

TCP 还是 UDP ?

设计Relay server时，发现会存在两种消息，我们最初是这样设计的：

n         过程控制协议， 采用TCP

n         Input，Frame协议，采用UDP

为什么是UDP？

从其他服务器的运营情况来看，当网络一切都好时，TCP表现很好，但是一旦网络不稳定，存在IP丢包，TCP的延迟会增加，还会断线。

获得经验是：

n         TCP适合对流量敏感的应用，TCP的窗口机制可以很好的利用带宽。

n         UDP适合对延迟敏感的应用。

解决UDP丢包

当前中国普通用户平均0.2%的丢包率，解决丢包的根本方案靠重发。

其中Relay server 30帧/s持续发送的特征，可以得到很好的利用，如果包1没收到，包2收到了，那么初步判断包1丢失了，当然也可能是乱序，我们会等待100ms再判断是否要求Server重传。

网络上肯定存在很多种方案，我们也测试过很多方案，包括超时重传，丢包立即重传，最终方案是这两个的结合体，只不过超时是固定时间100ms，取得结合流量和延迟的平衡。

其实没有所谓的最优，只有尽量合适。当需求满足时，采用成本更低的方案，是明智的选择。

丢包重发后延迟怎么办?

这是丢包重发的后遗症，1次重发，会增加较大的延迟，至少是100ms + 2帧时间+ 一个ping时间。

如果收到Frame3时， 同时携带Frame2， 那么即使之前的Frame 2即使丢了，也不需要重传，就可立刻补充——这就是冗余方案。

冗余是通过流量换速度。

我们做了一套动态冗余算法，包含上行逻辑和下行逻辑，通过每个客户端的丢包状况来动态调整冗余倍数。

当然，也有一些游戏，通过全冗余来做，就是在客户端还没收到ACK时，总是携带所有没有ACK的数据。

这种方式简单粗暴，但是会导致流量增长N倍，各有利弊吧。

下行冗余的倍率图，平均在1.4倍左右。还是比较理想的。（图中纵轴10000表示无冗余）

奇怪的不一致，UDP分组长度的确定

运营过程中，发现有部分玩家，经常出现游戏不一致异常结束。

日志中发现，玩家的Frame包校验码不正确，就是说这个包是错的。

这怎么可能呢？网上都说UDP保证包数据的正确，看来也不尽然。

后来咨询了各种资料，总结出问题：是数据报太大，被分组，部分路由器组包错误。（最大可能）

我们不断缩小分组长度： 1400 – 1200 – 1000 – 576 byte

最终我们定在了internet标准MTU尺寸576 byte（包含IP包头和UDP包头）。

这个问题就基本搞定了。

UDP回发的坑

当服务器收到UDP包后，如何回发也不太简单， 这在TCP里简直不是事。

当收到到第一个UDP包，高兴的记下回发地址， 以为就可以一劳永逸往里面塞包回发，那真是大错特错。

说实话，我们开始就是这么做的，结果客户端动不动就收不到回包。

解决办法是：

服务器每次收到包就都记下回发地址，这样中间路由如何变化，都可以送回去。

真的解决了吗？ 其实依然可能收不到，不过还好，客户端总是会发送数据到服务器，这样就又会在中间路由器中，建立了通路，所以，这个办法还是可行的。

突然间，明白了统一标准的重要性，即便标准确定了，执行还是另一回事，从时钟不一致、UDP组包错误、到这个问题，世界观开始崩溃了，以前整天写逻辑代码，还真是无法理解底层的江湖险恶。

淘汰TCP

运行过程中， 我们发现了个奇怪现象，在跨网用户中，

用户可以流畅的比赛，但是控制协议确频繁的断开。 导致最终比赛异常结束。

其他服务器也有类似情况，问题其实发生在TCP的拥塞退让机制，因为丢包较多嗲话，TCP可能会频繁断线。

咨询了一些大牛，建议我们重构TCP，当然还是被TCP复杂的特性吓退了。最终，我们决心淘汰Relay server的TCP协议，实现了最简单的可靠UDP： 等停协议。

改造后，不单连接更稳定了，因为只侦听UDP端口，连部署也更加容易了。

一个丢包的例子，这种情况UDP工作正常，但TCP就容易断线。

流量的优化

Relay server的瓶颈不在于逻辑这块，而是在于部门开发的连接组件，该组件的CPU占用和网络流量成正比。

我们做了下面一系列优化，最终压缩后的结果，平均单用户比赛时上行1.4K byte/s， 下行 3.3 K byte/s。算是个不错的结果。

n       压榨Input尺寸，Input –> 16byte。

n       降频：

relay server试图从30帧/s降低到15帧/s，渲染仍然30帧以上，但是操作手感有些下降，其实未采用。

n       Input去重复

玩家实际操作中会有，按键并非每帧都变，所以可以不上报。

从上图看出，玩家实际43%的操作是变化的，其余都是未变化。

算法原理摘要

n       帧间压缩

帧间压缩的概念是，玩家的两次按键变化之间，只是部分数据变化。比如： 按住left+shift为向左加速跑，松开shift，变为向左走步。 该变化只是shift按键，数据是1个bit。

具体做法是当前帧和上一帧异或，这样就出现很多0值，很容易压缩掉。

客户端还原时，只需要保存上一帧的数据， 则总是能正确还原出当前帧。

n       Frame压缩

在上述基础上，再进行RLE压缩，进一步压榨。使用RLE算法原因是速度和效果的平衡。

Relay server帧跳如何稳定

为了方便，服务器底层循环，使用公司SERVER组件的tick循环，设置为1ms触发一次，实际测试时，这个1ms很不靠谱，经常超过1ms。

所以，为了确保Frame定时尽量精准，循环中又使用clock_gettime函数不断获取时间，然后在frame帧跳函数中，处理所有玩家当前帧的数据。方式可以说简单粗暴，但效率很高。由于是30帧/s，流量上还是平滑的。

比较偷懒，直接贴代码了

Relay server性能优化，以及动态负载

n         一个玩家上下行60个包/s,  1K个用户就已经6万/s，那时候，公司互娱架构组的前端连接组件，也就10万/s, 怎么办？

n         处理这么多的消息包，CPU吃得消吗？

但我们也发现，在同样的消息量下，Relay server没有任何CPU瓶颈， 这个当然受益于我们自己的一套高性能架构，组件。

主要瓶颈在前端连接组件上，主要热点有两个

n         消息压包解包

之前压解包效率很慢，自从前端连接组件使用了C++编解码方式，这个瓶颈热点消失，强烈推荐新版本，大力赞一下互动娱乐的技术架构部门。

n         系统API调用

•            这个问题比较戏剧化，最早我们认为同型号的服务器，性能应该差不多，这个意识直到很久以后才改变，多次运营冲高时，都发现有玩家卡顿。

•            最终调查发现，服务器CPU 100%，原因是服务器操作系统的问题，具体原因可能是降频或其他设置等，总之，服务器的实际性能差距，可以超过10倍。

•            无奈之下，我们上了动态负载逻辑。通过监控瓶颈进程的CPU，来限制连接人数。使用之后，效果非常好。在大规模集群中，动态负载是必须的。

动态负载的日志输出，能看到服务器性能差别还是很大的：910 –  6997

平滑渲染，Jitter buffer如何优化

收到Frame就去渲染吗？

如果收到Frame就渲染， 有个例子可以想象： 如果视频播放不缓冲，你将看到刺激的抖动画面。同理，游戏也一样， 所以一个有效的Jitter buffer至关重要。

这个Buffer很有挑战

n         不能太早的把Frame送入Game core，否则下一帧没来怎么办。

n         不能太晚把Frame送入Game core，那会造成很大的操作延迟。

n         必须能适应玩家的网络情况，自动调节。

悲剧的是，游戏对延迟要求又远远高于视频和语音。

测试经验值：NBA操作延迟150ms以上，体验将下降。

只有网络会抖动吗？

不尽然，渲染也会抖动，这帧33ms，下一帧可能就100ms；

客户端和服务器的时间戳，也存在误差。

除了小的波动，还有更大的抖动，我们称为毛刺：

如果客户端同时启动了另外一个程序，产生CPU争用，可能某一帧渲染会超过N秒

如果网络拥塞，也可能导致画面卡住超过N秒

画面流畅和低延迟，你选哪一个？

所谓鱼和熊掌不可兼得，想要画面流畅，又要低延迟，在有限条件下，这只是梦。

到底是流畅重要还是低延迟重要，我们纠结了很久，这也直接决定着Jitter buffer的算法模型，以及参数设定。

经过用户的长期反馈，得到一个最可行的理论：

画面的流畅性大于一切，要尽可能消除一切抖动， 牺牲延迟换取稳定。

所以， 策略就是两点

n         增加延迟消除抖动

n         跳过毛刺

然后，也就决定了如何衡量客户端体验数据：

n         操作延迟大小

n         卡顿频繁程度

典型的网络抖动是这样的

时间戳需要修正吗？

比赛中，所有客户端都是跟随者Relay server的脚步，那么问题来了，服务器的时间戳和客户端的时间戳不一致，就算发送到客户端，也还包含了网络延迟时间。

是否要进行客户端的时间戳修正呢？ 看了网上众多时间同步算法。头又开始大了起来。

最终证明，这是不需要的，完全可以推导证明，时间戳同步本身是完全不必要的，在Jitterbuffer算法中，全部在计算中被消掉。

基本原理就是： 虽然长时间来讲，客户端和服务器时间会存在较大误差，但是我们算法中全部使用相对时间，我们相信，在网络近期采样的阶段（10秒），这个误差会缩短到1ms以下，完全不产生任何影响。

所以，Jitterbuffer算法就直接使用：服务器和客户端的时间戳的差。这可大大简化复杂度。

Jitterbuffer算法实现

为了几十ms的延迟， 我们查遍了Google，翻遍了论文，包括我们的土著算法，我们一共研究了懒散法、定时修正法、VoIP算法、MAPDV算法、MAPDV2算法、SMPDV算法、以及我们正在使用的MAX法（暂时命名）等。

下面是一些算法的基本原理，大同小异。

（摘自各个文章，只为助于理解，并未使用）

我们的MAX算法原理是，取近期100个帧Frame的网络延迟，取最高点之上作为Jitterbuffer的上限。估计未来只有极小可能超过大于该值，再通过一些算法，消除大个毛刺。实际的Jitterbuffer上限一般浮在网络抖动曲线的上面。

该算法和其他算法的区别是，

n         取延迟上限，消除一切抖动。其他算法，看起来很美，却不能很好的实现这个目的。

n         速度比其他算法慢，但更精确，因为一个尽量低的合理延迟，会有更好的游戏体验。

n         适应所有抖动模型，因为它简单粗暴。

MAX算法模拟实验图示（参照绿线，制作模拟工具，是早期验证理论的有力武器）

渲染只能30帧吗?

服务器虽然限于能力帧数当然越少越好，这样承载在线人数更高。

但是如果渲染帧太低的话，眼睛就受不了，体验很差。

所以，我们还开发了一套帧数扩展算法，它能保证各个客户端接收30帧，还能准确的扩展到任意帧数，比如30、45、60。

原理比较简单，利用整数的计算一致性，Frame序号乘以一个倍数，立刻变身为45或60帧，同时复制补充中间的Frame data。这些都在客户端进行，并且各个客户端精确一致。当然对于Game core而言，这些是透明的。

防作弊机制

NBA既然是各个客户端表现一致，那么防作弊就变的简单，因为比赛的客户端产生的事件完全一致，只需要汇报到逻辑服务器（另一种服务器）上检查，只要有人事件和其他人不一致，则踢出。这种方式简单且有效。

传统的MMO服务器是把同步和校验整合在一个服务器中，我们是分开，帧同步体系，和游戏逻辑体系是完全分离的，这很合适NBA等类似竞技游戏。

IDC持续优化

优化目的

想让更多人体验更好，延迟更低，那么只有更合理的分布部署Relay server。保证Relay server和玩家很“近”。

帧同步服务器匹配

玩家进入一个比赛，前提连接到一个帧同步服务器。

怎么选择一个服务器，比赛内所有玩家的操作延迟都比较低，是这个命题的目标。

这涉及到三个过程：

1)        收集玩家对服务器的ping

RelayServer有一个管理服务器RelayCenter，负责收集ping数据。

2)        匹配算法根据各个玩家和IDC的延迟，选择一个IDC

我们有一个专门的匹配服务器，并增加了IDC匹配算法。当有一个IDC，比赛中所有玩家和该IDC的平均ping最低，认为是一个合适的IDC。当然还考虑过其他算法，比如是否照顾一下，延迟最差的玩家等。但如果从总体来看， 平均ping最低的算法，所得到的统计数据一定是最好看的，不是吗。

3)        根据服务器负载，从该IDC中选择一个RelayServer

RelayCenter也负责分配一个负载较低的服务器。

RelayCenter收集玩家ping

收集玩家反馈的ping非常关键，怎么收集，如何整理，都对分配的效果影响巨大。

最初，我们可笑的通过比赛统计后的ping汇报来收集，结果这陷入了一个糟糕的正反馈循环系统：

最终这导致了这个优化几乎不生效。

就好像，我一直给孩子吃糖，水果什么的都不给看，孩子就只会要糖。就是这个道理。——只有信息更全面，选择才能更正确。

我们是这样改进的：

n         每个客户端客户端定时取得IDC的ping值

n         Ping是从客户端通过UDP到relay server反馈的一个时间

n         每个玩家，针对每个IDC，都有一系列Ping统计，保存在RelayServer

n         连续多个Ping的采样值进行加权平均

New ping = (oldping *(N-1) + cur ping) / N

通过IDC，省份，ISP等这些key，可以做出ping，操作延迟，人数等各种视图。

一个例子，上海市北IDC各省市ping值，我们和公司数据平台的数据比较。看起来很像不是吗

RelayCenter负载分配算法

RelayServer分布在多个IDC中，通过UDP协议，定时把瓶颈进程的CPU上报给RelayCenter。

既然能及时的得到负载反馈， 分配算法就简化为，取负载最低的Server。

还有个小技巧，当不能及时的得到负载反馈时， 这种分配方式会导致这个Server快速满载，很不均衡，可改为按权重随机分配方式，权重值=空闲单位数。

多线服务器的判断

多线服务器是指，一个服务器同时支持电信、联通、移动等多个ISP。

这样的服务器会有多张网卡，每个网卡对应一个ISP。

可让跨网用户得到更好的体验，也能收敛游戏大区的数量，聚集人气。

实现并不复杂，当客户端连接某Relay server时，需要选择效果最好的IP进行连接。

我们未使用域名方式，原因是智能域名不一定比我们智能：），更主要的是它可能会失效。

最佳ISP端口判断如下：

n         Ping值

连续ping 20个包，取ping值最低的服务器，该ping值算法模拟Lockstep，取上限。

n         ISP判断

由于ping的数量不能太多，采样数量太少，会使判断不精确。所以辅助ISP判断。通过查表得出该IP的ISP，在ping相差不大的情况下，优先连接对口ISP的IP。由于IP配置表经常变更，这也只能时辅助手段。

多线服务器的体验效果

开始我们担心多线服务器的游戏体验，但经过匹配优化后，

从新开的混合大区效果来看，多线服务器的效果，很优秀。

TGW的体验效果

TGW是公司IP收敛的一套方案。这里推广一下，该方案是非常棒的，重要的是，TGW资源容易申请，但很可惜确实会增加一些操作延迟。不过，对于那些延迟不敏感的游戏，TGW应该没什么影响。

用户ISP分布一些参考

用户省份分布

广东无疑是游戏大省

很容易看到哪些省份是电信的天下，哪个省份是联通的天下

用户操作延迟分布

Y=操作延迟，X=用户采样，关注蓝线，红线请无视。

这个图，很有趣，可以看到80%以上用户<150ms，也有部分用户延迟很高，还是坚持打完了比赛。

Relay server分布部署

经过匹配优化后，事情还没有完，要选择部署更多的IDC才能生效。

在部署relay server，总的来说部署越多，越分布，效果越好。

但是要考虑性价比的话，还是需要找到规律：

n       重点IDC明显更稳定更好

n       支持多ISP的IDC更好，即便电信游戏大区， 往往也混杂了15%左右的非电信用户。

Relay center的优化

以前各个大区都有各自的relay center，管理各个大区的RelayServer，各自为政。后来，整合各个大区的Relay center，配置完全使用一份。

有如下好处：

n         用户可从更多的relay选择中受益，得到更好一点的体验

n         降低运维部署成本，大量的Relayserver调整是很痛苦的

如果再进一步，是否可以建立成帧同步云呢？

统计反馈

这是统计系统的部分统计。整个优化过程，得益于建立了完善的反馈统计体系，形成了完整的闭环。有几个关键的数据和大家分享：

n         操作延迟：因为我们把抖动转化为延迟，所以这是最重要的质量参考数据

n         快播率：客户端因为累积太多Frame data，需要快速消耗，类似于丢弃。这是客户端渲染优化的一个重要指标。

n         STALL率：客户端没有Frame data给Game core，需要等待，这个数据是反映网络毛刺的情况。

n         平均FPS：同样反映客户端渲染优化情况

小结

网络优化是一个持续的过程，在解决问题时，作为程序员，往往陷入过度追求完美的方案之中。但事实是，没有哪个专家，也没有哪篇论文，就能告诉你这么做是一定对的。你只有不断的试验、探索，通过模型得到理论数据，通过测试获取第一批用户数据，再改进，再试验，你终究会越来越接近完美。但你也不能丢掉理论，陷入到无休止试验之中，走到一个坑的面前，记得停下来，百度一下，问问专家，或许前人就会留下一些线索。最后，记得总结一下，也把一些线索留给别人。