在图书馆发现一本《网络多人游戏架构与编程》—— Joshua Glazer, Sanjay Madhav 著。书挺新的,17年出版的,内容很有趣,翻一翻可以学到不少在《计算机网络》上不会讲到的内容,故做此纪录。
前几章,第一章简单介绍了网络游戏的历史和发展,第二章讲了how Internet works, 第三章讲的是 Berkeley Socket,就略过了。
序列化:是指把内存中的内容转化为比特流的形式。比特流是通过网络传输的形式,在主机和服务器上还可以恢复为原始格式。
可能不是很好理解,书中举一个例子来说,如果有一只猫 RoboCat 对象要传输,猫的类定义代码如下:
// 类定义
class RoboCat : public GameObject
{
public:
RoboCat() : mHealth(10), mMeowCount(3) {}
virtual void Update();
private:
int32_t mHealth;
int32_t mMeowCount;
GameObject * mHomeBase
char name[128];
std::vector<int32_t> mMiceIndices;
}
用socket发送这只猫的代码如下:
void SendRoboCat(int inSocket, const RoboCat * inRoboCat)
{
send(inSocket,
reinterpret_cast<const char *>(inRoboCat),
sizeof(RoboCat), 0);
}
乍一看好像是没有什么问题对不对?服务器那端用 recv 函数把这个对象接住就可以。问题在哪呢?比如看这一行:
virtual void Update();
假设在32位系统上,这个对象开始的 4 bytes 是一个虚函数表指针。因为 Update
方法是虚的,每个对象实例都会存储一个指向虚方法实现位置的表指针(如果看不懂自行搜索虚函数的实现方法)。如果直接发送这个对象,会导致一个问题,那就是每个不同进程中那张表的位置其实是不一样的。这段代码,会导致服务器上写入目标的那个 RoboCat 对象的虚函数表指针直接写成一个错的指针。
当然这个例子中还包含别的指针,比如 GameObject * mHomeBase
,结合上面的例子很容易就想通:在客户端上一个进程的某一个指针位置,直接发给服务器肯定是荒谬的(一个进程复制一个指针到另一个进程,肯定不能期望对这个指针解引用后还能得到正确的数据)。解决方案其实很容易就能想到,就是必须对相关的数据进行复制,而不是发送直接的二进制地址。
第二个问题就是对于char name[128];
这个对象,如果直接发送整个对象,很明显的一个问题就是这个128字节的数组大多数情况下包含的数据很少,因为这是一个以\0
结尾的C字符串,后面的字符都没有意义,我们应该仅发送那部分有意义的字符来节省网络的带宽。
最后一个问题出现在对于STL中的vector
直接复制这样的结构,因为里面一般来说都是会有一些什么指针啊乱七八糟的,所以不清楚直接复制内存中的一个vector
的内部字段到另一个进程是否安全(十有八九是不安全的)。事实上,你应该假定使用任何黑匣子数据结构时复制都会失败,按二进制位复制是不安全的。
解决这个问题的原则是序列化。序列化是一种将对象从内存中的随机访问格式转化为比特流格式的行为。也就是收集所有的相关数据到一个缓冲区,然后发送该缓冲区,作为对对象的代表。为此,要引入流的概念。
流在计算机科学中很常见,代表一种数据结构,封装有序的数据元素。
输出流,作为用户数据的输出槽,用户可以顺序插入元素,但不能从中读取。输入流就是可以允许用户提取元素但不允许输入。输入输出流就是既是输入流也是输出流。
序列化,就是用到内存流,封装内存的缓冲区。核心是用动态分配的缓冲区,把数据顺序写入缓冲区,再同时提供对缓冲区本身的访问。用户将数据写入这种对象,再用send
发送给另一个系统,就可以解决上述的问题。为什么能够解决呢?使用源对象的各个值(而不是地址)来填充缓冲区,给远程主机发送这个缓冲区,顺序提取数据,再把这些数据插入到远程主机的进程中一个对象的合适字段里。规避像虚函数表指针这样的问题,很简单,不要发送不应该被改变的东西就好了。
工程师要尽可能关注如何高效地使用带宽。能发送更少的字节和比特表示信息,我们就要发送更少。
举例,char name[128];
直接上代码:
void RoboCat::Write(OutputMemoryStream & inStream) const
{
// ... other code here
uint8_t nameLength = static_cast<uint8_t>(strlen(mName));
inStream.Write(nameLength);
inStream.Write(mName, nameLength);
// ... other code here
}
写入数据本身之前,写一个长度n,然后就写那个数组前n个字节,很好又很简洁的方法。
熵编码是一个术语,指利用数据的不确定性来进行数据压缩。例如 Huffman 编码等就都是这个术语所描述的。
假设,有一个位置字段mPosition,有三个维度X\Y\Z来描述一个Cat的位置,发送这个位置的时候,代码如果这么写:
void OutputMemoryBitStream::Write(const Vector3 & mPosition)
{
Write(mPosition.mX);
Write(mPosition.mY);
Write(mPosition.mZ);
}
那么每次发送一个位置都要用 3*4=12 bytes。下面采纳一个简单的事实:猫常见的情况都是在地面上的,也就是大多数情况下Y都是0,所以我们可以用一个单独的比特来标识猫是在地上还是在天上。如果是在天上,再用4个bytes去存储它在天上的位置。
void OutputMemoryBitStream::Write(const Vector3 & mPosition)
{
Write(mPosition.mX);
Write(mPosition.mZ);
if(mPosition.mY == 0)
{
Write(true); // true 是一个bit?学到了。。。
}
else
{
Write(false);
Write(mPosition.mY);
}
}
假设玩家的猫90%的时间在地面上,那么本来是一直要用32 bits,现在变为 $ 0.9 * 1 + 0.1 * 33 = 4.2 bits $ ,每次传输位置都节省了3个多字节。
当然,过分关注带宽效率可能会导致丑陋的代码,所以有的时候为了软件工程方面的考量,需要牺牲一点点效率来换取代码的可读性、可维护性,总之都是tradeoff。
很好理解,比如你在Minecraft开了个门,那么所有在同一个世界(一定范围内的)玩家必须都看到门打开了。所以世界状态(world state)就是那个世界中所有游戏对象的状态,所以同步世界状态就是传输每个对象的状态。
这涉及到对象的复制。为了成功复制一个游戏对象,一般有三步:
发送大小与MTU尽可能接近的数据包是高效的,所以在一个数据包中发送多个对象可以提升效率的。
每台主机其实都保存了一份世界状态的副本,所以其实没必要在一个数据包中复制整个世界状态。发送方只需要发送那些有发生改变的部分就可以了,用一个状态来表示下面三种复制行为的一种:
书中有一个世界状态管理器的实例。
考虑一下网络拓扑。一般有两种主要的拓扑结构需要考虑:C-S和对等网络。
客户端服务器(client-server)拓扑结构,大部分游戏有一台权威(authoritative)服务器,我们认为:只有服务器上的游戏模拟是正确的(这很好理解,吧,为了防作弊)。如果客户端发现自己的游戏状态和服务器中的不一致,需要根据服务器发过来的信息更新自己的状态。采用相信权威服务器的策略,就意味着客户端的行为一定会有一定的滞后或延迟。这延迟有很多原因,实际情况中游戏需要使用各种技术来降低(或者隐藏)延迟。
对等网络,也就是P2P那样的,每个参与者(对等体)都和其他所有参与者都有连接,客户端之间大量数据来回传输。这样的系统比较难实现,这种模式常见于RTS游戏(real time strategic,即时战略)。常见的做法是输入共享模式,所有的对等体的互相发送所有动作,比如《帝国时代》(Age of Empires),游戏以200ms一轮,一轮中的所有命令放到队列中,200ms结束,把这队列中的所有命令都发送到所有对等体中(即时战略一场游戏的玩家数量有限,一般不会超过十多个),然后在每个玩家的电脑上模拟这个游戏。这种同步的方式虽然概念上很简单,但实际实现是非常复杂的。其中最重要的是要保证游戏的实现需要非常确定,一组给定的输入必须始终得到同样的输出,为此需要使用例如校验和这样的手段来检验对等体之间游戏状态的一致性。对于这种游戏,如果要加入新玩家,一个新的对等体要加入进来,如何让其和每个对等体都建立关系?实际上,可以有一个玩家被选定为所谓的主机(房主),新玩家先与主机建立练习。对于对等网络,由于没有中心服务器,所以不存在由于服务器断网而整个游戏失去连接的情况,有哪位玩家通信中断,其余玩家可以提议暂停游戏或者过一段时间断开这个玩家与主机的连接。
第六章有C-S网络管理器、输入共享模式的命令队列的实现、对等网络的实现。
设计对等体网络游戏,比如即时战略游戏,挑战之一是保存所有实例的同步。要做到这一点经常会使用伪随机数生成器。有必要保证每隔一段时间(或者每一回合/轮/游戏设计者自行规定的一段指定时间间隔),任意两个对等体总是从一个随机数生成器中输出相同的结果。所以
书中提出,C语言的rand
和srand
不是特别适合,原因是因为这东西不是在C标准中有指定的,所以不同平台、不同编译器会使用不同的随机数生成算法,因此就算保证了种子相同,也不一定意味着随机数相同。好消息是C++11引入了标准化的生成器,代码在书中有体现。
同步的过程如下:
另外还有一种方法就是使用校验和(checksum),每一轮结束时,计算游戏状态的校验和。这个过程可以用公开的实现,比如CRC32这样的比较知名的算法。校验和放入轮数据包中被发送,若有发现校验和错误的对等体,处理方式可以是将其剔出游戏(反作弊)
延迟是不可避免的。(这一点,玩过游戏的都知道),网络在物理传输上肯定是存在延迟的。但不同游戏类型对与延迟的容忍程度是不同的(但是这一点,可能不仔细想还真不知道)。例如,VR游戏对延迟是最敏感的,比如,人的头动了一下,我们眼睛就期望看到不同的画面,这个延时需要少于20ms。格斗游戏、射击游戏和其他动作(频繁)游戏是延迟第二敏感的,一般要100ms以内。RTS游戏是对延迟容忍度最高的,可以高达500ms而不影响用户体验。毫无疑问,降低延迟可以提升用户体验,作为学计算机的人,首先要理解延迟来自哪些方面。
一般我们玩游戏觉得延迟都会觉得网络是主要的问题,但其实这是一种误解,网络延迟绝对不是唯一的延迟来源。
这部分《计算机网络》上有讲过,当作复习
主机到服务器的RTT是可以估计的,必须留意RTT不是一个常数,而是会围绕某一个值进行变化,如果RTT与期望值偏差,这个偏差就被称为抖动(jitter)。作为游戏服务器,要做到:
这是非常有意思的一个章节,学《计算机网络》我们最关注的都是TCP比UDP好在哪里,有那些措施等。但,网络游戏的实际情况下的工程是远远超过教科书上面的那些内容的。
几乎每一个游戏的开发早期都需要面临一个抉择就是使用TCP还是UDP。使用TCP的好处就是,它提供了一个经得起考验的、鲁棒的、稳定的可靠连接实现。保证了所有数据都能到达,而且还能按序到达,还提供了复杂的拥塞控制功能。但是,这优点其实也是缺点:所有的东西都一定得可靠发送且按顺序处理,在瞬息万变的游戏世界中,可能会造成如下的问题:
说完TCP,我们再来说UDP。UDP虽然没有TCP提供的可靠性和流量控制,但是,它实际上就是一张空白画布。你可以根据你所设计的游戏的需要来设计一个任何模样的自定义可靠系统。
以上都增加了开发和测试的时间,可以使用一些第三方UDP网络库来减少一定这方面的工作量和风险。如RakNet和Photon。
总结,选择哪个传输层协议需要考虑如下问题:
如果两个问题的答案是肯定的,那么确实应该考虑TCP,在回合制游戏中往往是这样的。如果TCP不是绝对完美适合,那么应该使用UDP,这对大多数游戏都是这种情况。
实现这么一个系统的过程中,创造一个模拟抖动、延迟、丢包的测试环境是非常重要的,看看你的系统是否可以经受得住这些考验。
前面我们提到,权威服务器的概念。服务器是唯一拥有真实和正确游戏状态的主机,服务器是唯一运行最重要模拟的主机。因此,玩家产生一个动作,到玩家观察到这个动作导致的真实游戏状态,总是有一些延迟。例如:玩家按下跳跃按钮,假设 RTT 是 100ms,且假设往返时间大致是一半一半,服务器是在 50ms 时收到玩家主机发来的数据包,则服务器开始执行对该跳跃动作的模拟,并把新的状态发送回玩家,该数据包就也需要 50ms 才能达到客户端,所以按下跳跃按钮的 100ms 后,玩家才能看到人物跳跃的结果。由于数据包传递是需要时间的,所以运行在服务器的真实模拟总是比玩家能在他们主机上感受到的模拟早半个RTT,这个也比较好理解。
这种客户端被称为沉默终端(dumb terminal),它们不对游戏的模拟代码有任何了解,dumb terminal 只是发送输入,接收服务器发来的结果然后渲染给用户看。这种方式叫做保守算法(conservative algorithm),代价是时延,但至少保守算法是绝对正确的。
沉默终端存在一个问题,就是不平滑。举一个例子:
插值法(interpolation)学过数值分析,看到名字就大概懂了。使用这种方法,客户端不是自动将对象移动到服务器发来的数据包指示的位置,而是根据时间平滑地插值到这个位置。
人为规定一个较小的差值周期IP(interpolation period),即从一个状态插值到另一个状态所需要的时间。PP代表数据包周期,即服务器相邻的两个数据包之间的时间。根据定义,数据包到达客户端后的IP时间内完成插值。显然,若IP小于PP,则插值完毕后仍没有拿到新的数据包,则玩家仍然会感觉到卡顿,所以应设置 IP ≥ PP。
人为规定一个IP,收到Y=4这个包后,在随后的IP时间内让人物平滑地从Y=0移动到Y=4,这个技术虽然引入了额外的延迟IP,但游戏看起来更平滑了,让玩家体验更好,这个代价就是值得的。
虽然插值法可以让体验更加顺滑,但仍然不能让客户端的状态更加接近服务器上的状态。一种更为主动的想法是从插值转为推测。客户端根据接收到的略旧的状态,显示一个推测的状态给玩家。(client prediction)
如果是这样的客户端,就不是 dumb terminal 了,因为客户端上也得有一份与服务器相同的模拟代码了。预测是这么预测的:
举例,当玩家按下一个施放攻击咒语的按钮时候,他希望他的虚拟人物能够立即扔出一个大火球之类的东西。这种预测就比上面的更超前了,即客户端直接在本地执行适当的模拟,渲染特效来给玩家的输入提供即使反馈,同时再等待服务器模拟的返回。理想状态下,玩家按下施法——客户端直接开始播放施法动画和声音——客户端与此同时发送施法的数据包给服务器——服务器产生火球,复制返回给客户端——客户端正好赶上显示施法结果的时间点,再向前预测 1/2 RTT 的火球抛射轨迹,玩家看起来,从他按下键盘那一刻起,施法,火球形成,火球打向目标,好像没有延迟。当然,这个方法有的时候也可能会有点问题的。比如,在服务器这里,数据库里状态显示该玩家其实是被沉默的(不能施法),但由于网络延迟,通知该玩家被沉默的信息尚未到达客户端,那么玩家就会出现这种情况:玩家感觉自己是没有被沉默的,可以释放火球,但按下施法按钮后,开始了施法动作(手可能在搓)但迟迟没有火球出现,过了一会(沉默的通知数据包到达后)玩家才发现原来自己其实是被沉默的。不过呢,跟这种方法能够提供的好处相比,这个坏处还是可以容忍的。
有一种常见的游戏动作是客户端预测法不好处理的:长距离即时射击,假设你是一名配备狙击步枪的反恐精英,你希望你瞄准一名玩家并扣下扳机后,立刻就有完美的命中(比如敌人应声暴毙,右上角出现你击杀成功的信息)。这个问题有一个解决方案,是 Valve 的起源引擎中推广开来的,被《Counter-Strike》游戏采用,其核心是:当开火时,让服务器状态回退到玩家扣下扳机时感受到的状态。那么,如果玩家感觉她瞄的很准,那么久可以百发百中。
说得好听点叫深度包检测(deep packet inspection),说得难听点就是数据包嗅探(sniffing)。
任何使用不安全、或公共无线网络的计算机都可能被该网络中另一台计算机读取数据包信息。书中说的非常好的一句话,就是“无论如何你都应该假设玩家总是可以访问网络传输的所有数据”。这意思其实跟防御性编程差不多,考虑代码中处理输入的部分就是假设用户会输入各种千奇百怪的输入而你的程序都能够相应地handle。
(方法就是加密,公钥加密算法,不多说了)
加密数据其实是一种威慑,而不是万无一失的措施。原因:
无论如何,你都必须接受一个事实,就是你永远无法阻止别有用心的人在主机上 sniffing。
除了上面那个假设:无论如何你都应该假设玩家总是可以访问网络传输的所有数据,之外呢,还有下面一种假设需要考虑:
你要假设会有坏蛋了解了你的游戏服务器与主机的通讯方式,然后模仿一个游戏客户端发一个数据包过来,但其实里面的内容是人造的,无效的,非法的或者不公平的。输入验证(input validation)也就是游戏不应该盲目地执行一切网络来源的数据包里的操作,而是应该先验证这个操作是有效的,是由合法的客户端正常地发出的。
例如,收到一个包叫做玩家A开火,接收端不应该无脑地直接去判断这个子弹有没有打到谁,而是首先应确认:玩家A活着,A有武器,武器里有子弹,玩家当前没有因为什么切换枪支的硬直而无法开火的状态等等,只要有一个条件不满足,都应该认定这个动作无效。如果检测到非法的数据包,可以有理由判定玩家作弊,可以试图踢掉违规的玩家,当然更正确的做法是保守点地直接拒绝无效输入。
不过,有没有可能服务器上有坏数据呢?毕竟,权威服务器模型中只有服务器有权利模拟游戏运行,如果服务器告诉某个客户端说:你死了,那么这个玩家必死无疑,那玩家怎么样才会保证我是真的死了而不是因为什么人为因素(比方说,某程序员改数据)而暴毙?唯一的一个解决方法就是:不让人来主持游戏。
书中还提到了战争迷雾的作弊(俗称开图,看到这里的时候我惊了,这书这么屌的么),例如像魔兽争霸这样的RTS游戏的战争迷雾,是把某一方的单位从另一方的视野里抹去,回想之前说到的对等体网络拓扑,那么每个游戏单位的位置信息状态应该是存储在所有对等体内的,因此战争迷雾是在本地的可执行程序中实现的,因此可以通过编写开图软件的方法取消战争迷雾。而被动的防御方法很难发现这一作弊,因为数据包的内容可能都是正常的,就需要软件作弊检测了。
上面说到的防御都是比较被动性的,下面介绍一种作为游戏进程的一部分或游戏进程以外的软件,更主动地检测游戏状态完整性,检测是否有作弊软件在运行的软件作弊检测系统(software cheat detection),例如 Valve 的 VAC(Valve Anti-Cheat)和暴雪的 Warden(典狱长)。
VAC 为每个 steam 游戏都维护一个被禁用户的列表(给卢姥爷上柱香),当被禁用的用户尝试连接 steam 游戏的时候就会被拒绝连接。作弊的大多数方法都是在客户端上运行游戏进程之外,再运行一个作弊软件。诸如:重写游戏的内存、修改游戏使用的数据文件、发自定义内容的作弊数据包。基于此,检测作弊的方法就是扫描游戏进程的内存,看是否有别的进程进行了非法的读写。如果检测到有用户在作弊,通常不会被立刻禁止,因为立即禁止很显然就会表明这个作弊手段被发现了以后就不能再用了,VAC 就是把这些用户保持起来,然后在将来的某一个时刻一次性封禁他们,这样子可以抓到尽可能多的用这种手段作弊的玩家。(666)
Warden 是暴雪(Blizzard Entertainment)的作弊检测系统,用在所有的暴雪游戏上。与 VAC 类似,Warden 也扫描计算机的内存来检测已知的作弊程序,如果检测到作弊也会返回到 Warden 服务器,用户会在未来的某个时间点被封号。Warden 特别强大的方面是游戏运行时的动态更新功能。因为作弊的用户都清楚,在游戏补丁刚发布的时候最好不要作弊,因为有可能反作弊程序也更新了,因此作弊程序可能就不好使了,或者以前不会被抓现在会被抓。但是,Warden 可以游戏在进行的时候更新反作弊系统,所以当 Warden 更新时可能会抓到没有意识到 Warden 更新的作弊用户(666)。
显而易见,关于 VAC 和 Warden 的公开的信息很少。实现这种系统,需要大量的底层操作系统、逆向工程的知识。即使是最好的反作弊系统,都有可能被攻破或避开,也就是所谓道高一尺魔高一丈,所以要不断的更新反作弊系统,保持比任何作弊程序都要先进。
网络游戏安全的另一个重要方面是保护服务器不被攻击。假定又来了,你一定要假定你的服务器易受攻击且有不怀好意的人伺机想要攻击你的服务器,因此你必须做一些防护手段。
几乎每一个主流的网络游戏都遭受过 DDoS。
防御这种攻击的工作一般可以交给云服务提供商,具体的内容就不在此记录了,简单来说就是四个字负载均衡。
应该假定,恶意用户可能会给服务器发送数据格式不正确或不合适的数据包,更阴险的用户也许可以通过构造数据包来达到服务器上缓冲区溢出之类的攻击(可以类比SQL注入)。因此可以采用模糊测试(fuzz)的方法,可以写一个类似于代码生成器的东西,构造大量非结构化数据、或者结构化但内容特定的数据,发送给自己的服务器来看是否会让服务器奔溃。
例如,假设你比较两个数组,来确定他们是否相等,数组a代表用户的证书,数组b代表正确的证书,如果函数是这样子的:
bool Compare(int a[8], int b[8])
{
for(int i = 0; i < 8; i++)
{
if(a[i] != b[i])
{
return false;
}
}
return true;
}
提前return false看起来好像是一个无伤大雅的性能优化,毕竟如果前面的就不同后面似乎的确没有继续比较的必要。但这会导致不正确的值输入会让函数返回地更快。恶意用户可以通过尝试每个可能的b[0],测试哪个值会让 Compare 函数返回时间更长,就可以确定正确的值。解决方案如下:
bool Compare(int a[8], int b[8])
{
int ret = 0;
for(int i = 0; i < 8; i++)
{
ret |= a[i] ^ b[i];
}
return (ret == 0);
}
恶意用户闯入服务器是最大的恶梦,要非常慎重认真地对待这一问题。入侵的常见途径是首先闯入有权限访问中央服务器的个人机器,以此为跳板进入服务器系统。这被称为鱼叉式钓鱼攻击(spear phishing attack),因此,所有开发人员的机器的操作系统、访问 Internet 的任何软件如浏览器等,始终应该保持更新。
假设又来了:你应该假设你的服务器很容易收到高级黑客的攻击,要确保任何敏感数据尽可能安全。例如,不要把用户密码保存成明文(说实话这谁都知道),但也不要仅仅只用简单的哈希算法例如SHA-256过一遍就把hash value存入数据库,因为一些简单的密码例如123456的哈希值还是可以找到那么一些总是这么粗心设置密码的人。而是应该使用诸如河豚加密算法,(或者我知道的,带盐的哈希算法等)。
下面摘抄一段原文的话:P270
“近年来的新闻显示,服务器安全的最大威胁往往不是外部用户,而可能是一个心怀不满的员工。这样的员工可能试图访问或传播他们不应该访问的数据。为了解决这个问题,一个全面的日志和审计制度是非常重要的。如果发生了这样的事情,既可以起到威慑的作用,也可以提供证明犯罪行为的证据。最后,所有的数据都应该定期备份到线下的物理设备上,即使最差的情况下,数据库被完全删除,你仍然可以恢复,虽然这个情况很不好,但总比永远失去所有游戏数据要好得多。”
(做这篇博文后面这部分的时候,B站的后端代码被人传到了 GitHub 上。说实在话由于肯定有备份,“删库跑路”其实公司不是很怕的,从删库跑路进化到开源跑路那是真的牛批。我本人是谴责这一违法行为的,但这些代码已经覆水难收,B站虽然联系了GitHub 紧急 takedown 了那个页面,但也我发现的时候也已经有了 6000 多个 fork,像 V2EX 这种论坛都是各种求代码的,没办法,毕竟是能看B站的产品代码啊。最严密的堡垒都是从内部攻破的,审计确实蛮有用的,学到了,除此之外希望互联网公司都注重权限管理)
《Multiplayer Game Programming》阅读笔记
原文:https://www.cnblogs.com/ZCplayground/p/10752994.html