【学习点滴】游戏后台开发-tx

admin管理员组

文章数量:1658496

目录

1.战团匹配算法

自己的思考

2.服务器内存优化

3.高时效的UDP 

4.弱联网优化之道

移动网络的特点

原因

解决方式：

1.快链路

2.轻往复

强监控

多异步

5.服务端其他优化手段：

游戏同步

6.DOS攻击和DDOS攻击

7.网络编程中的粘包问题

---

1.战团匹配算法

原文：https://www.gameres/827195.html

其实后来看了一下，原作者也是摘自《2018腾讯移动游戏技术评审标准与实践案例》

    游戏中存在跨服战等需求，将一些队伍组成固定规模战团，然后战团之间战斗，战团匹配过程应当尽量高效、快速，同时实现战力均衡。为了实现尽可能公平均衡的战团匹配，直观的做法当然是搜索所有队伍组成固定规模的战团，然而其时间复杂度为指数级，以极高的计算代价换取最优匹配显然是不现实的，因此，战团匹配问题也成为制约服务器性能瓶颈问题。
    为此，本文利用压桶法实现了快速组成固定规模为K的战团，在尽量保证匹配战团的战力均衡前提下，将战团匹配的时间复杂度降为O(n)。具体上，当有玩家或队伍（实际中，队伍人数为1到5）申请组成战团时，将其加入队列尾部。然后在游戏的心跳中遍历队列，如果当前遍历的玩家或队伍的人数加上桶里的人数小于等于K，则将当前玩家或队伍加入桶，并从队列中删除；否则新建一个桶，将玩家或队伍加入新桶中。在战团匹配时，找出所有人数为K的桶，将桶里所有玩家的战力值的和设为对应桶的权重值，并以此对所有的满的桶进行排序，每次选择战力值最接近的两个战团进行战力均衡的调整，然后传送到战斗服务器进行战斗。
    然而，由于压桶法是为了节省时间而选择的贪心算法，可能会遗漏能组成战团的玩家或队伍，因此在压桶法后，本文采用查表法对剩余的玩家和队伍再次尝试组成固定规模的战团。首先在服务器启动时做些预处理，群举所有能组成两个固定规模战团的组合（队伍人数为一的队伍数目，队伍人数为二的队伍数目，...，队伍人数为五的队伍数目），并存在set里，该步骤是全局唯一的，并且只需要做一次。然后统计剩下的玩家和队伍，计算人数为一、二、...、五的队伍数目。如果剩下的玩家或队伍队伍人数为一到五的队伍数目均大于set中某个元素，则set中该元素表示能组成两个固定规模战团的组合，并从剩下的玩家或队伍中删除。此步骤重复进行，直到剩下的玩家或队伍无法组成两个固定规模的战团。
    通过上述方法，本文实现尽可能合理的战团组成，在此之后，为了尽可能实现两个战团战力均衡，本文进一步设计战团玩家调整方法。当两个固定规模的战团组成后，通过查询预先生成的表，调整两个战团里的玩家，使得两个战团的战力尽可能相等，增强战斗刺激性。具体上，首先群举所有的能组成两个固定规模战团的可能，并存在map里，map的key为字符串，key唯一标识战团的构成（队伍人数为一的队伍数目，队伍人数为二的队伍数目，...，队伍人数为五的队伍数目），map的value为一个vector容器，vector中存储当前key拆分成两个固定规模战团的所有可能。当调整两个战团的战力时，通过map查询当前两个战团能重组成的所有两个战团的可能，然后遍历所有的可能，找出两个战团战力最接近的组合。

 

自己的思考

   原文中介绍的算法很精彩，考虑的情况也比较复杂。我自己想了下fifaol3这款游戏的匹配对战方式，应该是比较简单的，尝试分析一下。

    玩家点击“排位赛”或者“友谊赛”按钮后会进入对战房间，在房间中可以邀请好友加入，因此在发起对战匹配请求前，我方阵容的情况只有三种：1人、2人、3人。实际上我们可以在服务器维护3个桶分别记录玩家数是1、2、3人的队伍，其中key为队伍中玩家的昵称组合，value为队长的战力（即前场中场后场的能力值，只需要队长的数据是因为对战时使用的是队长的球员阵容）。当玩家发起对战请求时，就在对应的桶里找到战力均衡的两支队伍发起对战。（当然还需要对玩家的排位等级做一些加权影响，因为传奇级的玩家和业余级的玩家对战的话会索然无味，影响游戏体验）。

    上面介绍的是最简单的情况，即玩家只进行与自己队伍人数相同的匹配。比较复杂的是房间中只有1人，但是他选择的是2v2或者3v3对战的情况等，这就涉及到不同人数的队伍之间进行临时组队再进行匹配的算法。思考如下：

    同样维护3个桶队列，分别表示选择1v1、2v2、3v3的房间，那么这三种房间的人数上限分别为2、4、6。例如当1个单独玩家选择参加3v3时，遍历3v3的桶队列，若发现有一个房间的人数已经为5(为什么会出现5，看下一句话),就直接凑成6人加入，若没有就将此玩家加入桶队列。在每次遍历时，可以将一些零散的房间内的玩家拼在一个房间内，供下一次别人匹配来使用，如将1、1、2人的房间拼凑成一个4人的房间。当然这是一种贪心策略，可能会造成有的玩家等了好久都匹配不上的情况，但是游戏中确实存在等了2分钟都没匹配上的情况-_-。（当然房间中还允许有4个观战者，这种情况先不考虑啦）

 

2.服务器内存优化

本部分仍然转自https://www.gameres/827195.html

2.1 内存统计

    在对内存优化之前，需要先确定程序每个模块的内存分配。程序的性能有perf、gprof等分析工具，但内存没有较好的分析工具，因此需要自行统计。在linux下/proc/self(pid)/statm有当前进程的内存占用情况，共有七项：指标vsize虚拟内存页数、resident物理内存页数、share 共享内存页数、text 代码段内存页数，lib 引用库内存页数、data_stack 数据/堆栈段内存页数、dt 脏页数，七项指标的数字是内存的页数，因此需要乘以getpagesize()转换为byte。在每个模块结束后统计vsize的增加，即可知该模块占用的内存大小。

    在面向对象开发中，内存的消耗由对象的消耗组成，因此需要统计每个类的成员变量的占用内存大小。使用CLion或者visual studio都可以导出类中定义的所有成员变量，然后在gdb使用命令：
    p ((unsigned long)(&((ClassName*)0)->MemberName))，即可打印出类ClassName的成员变量MemberName相对类基地址的偏移，根据偏移从小到大排序后，变量的顺序即为定义的顺序，根据偏移相减即可得出每个成员变量大小，然后优化占用内存大的成员变量。

2.2 内存泄露

    内存泄露是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放，导致内存一直增长。虽然有valgrind等工具可以检查内存泄露，但valgrind虚拟出一个CPU环境，在该环境上运行，会导致内存增大、效率降低，对于大规模程序，基本无法在valgrind上运行。因此需要自行检查内存泄露，glibc提供的内存管理器的钩子函数可以监控内存的分配、释放。如图2.2.2、2.2.3所示，分别为钩子函数的分配内存和释放内存。因为服务器启动时需要预先分配很多内存，比如内存池，这些内存是在服务器停止时才释放，因此为了避免这些内存的干扰，在服务器启动之后才能开始内存泄露的统计。

    首先申请固定大小的vec_stack，记录所有分配的内存，如果有释放，则从vec_stack中删除，最后vec_stack中的元素即为泄露的内存，vec_stack必须为固定大小，否则vector扩容中会有内存分配，也不可以用map，map的红黑树旋转也会有内存分配，会造成干扰；然后通过图2.2.1所示的my_back_hook记录原有的malloc、free；并通过图2.2.2所示的my_init_hook将malloc、free换成自定义的钩子函数。

    每次分配内存时，都会进入自定义钩子函数my_malloc_hook中，如图2.2.2所示。在my_malloc_hook中首先通过my_recover_hook将malloc恢复成默认的，否则会造成死递归，然后通过默认的malloc分配大小为size的空间，为了分线程统计内存泄露，还需要对线程号做判断，在stTrace.m_pAttr记录内存分配的地址，m_nSize记录大小，m_szCallTrace记录调用栈，如果vec_stack已满，需要根据m_nSize从大到小排序，如果当前分配内存大于vec_stack记录的最小的分配内存，则替换；如果未满，则直接加入vec_stack，在my_malloc_hook结束时，将malloc替换成自定义的malloc。

    每次释放内存时，都会进入自定义钩子函数my_malloc_free中，如图2.2.3所示。在my_malloc_free中首先通过my_recover_hook将free恢复成默认的，否则会造成死递归，对线程号判断，然后在vec_stack中删除对应的分配，并将free替换成自定义free。

图2.2.1

图2.2.2

图2.2.3

 

3.高时效的UDP 

   摘自《2018腾讯移动游戏技术评审与实践案例》

到底是用tcp还是udp见一些参考指标

    游戏对网络有实时性要求高，带宽要求小的特点。TCP 虽然提供了可靠传输，但是内置的复杂拥塞控制算法并不是专为实时性优化的，也没有提供较好的方法让业务定制化。CF 手游实现了自定义的RUDP 协议方案，使用UDP 保证协议实时性，同时通过自定义重传策略兼顾可靠性，取得了很好效果，主要技术要点包括：

• 数据传输分类

    CF 手游中并非所有数据都要求可靠，按游戏逻辑需要，只有不到50%的协议有可靠性需求，RUDP 中只对这部分协议提供可靠性保证。而非可靠包则保证尽快到达，以满足游戏的实时性需求。对玩家移动状态等信息，由业务层定时冗余重传。

                              

客户端与服务的的交互时序如下：

                  

                                                    图CF 手游网络数据交互时序

• 快速发送

发送方不维护发送窗口，不等待前面包是否ack，有数据需要发送时立即发送。

• 快速重传

CF 手游使用比TCP 更高精度，响应速度更快的重传策略以保证实时性。

                       

• 带宽优化

主要思路是有损服务和降低不必要开销。CFM 持续进行了多轮流量优化，包括：
1.MTU 设计为500+字节，应用逻辑保证数据包大小不超过MTU，避免拆包。
2.减小包头，8 字节。
3.小包合并。同一帧发往同一个目标的多个小数据包合并为大包，减少包数量。
4.降低服务端帧率和位置精度，但不影响玩家体验。

 

4.弱联网优化之道

摘自《2018腾讯移动游戏技术评审与实践案例》，作者：腾讯互娱专家工程师-樊华恒

移动网络的特点

1.移动状态网络信号不稳定，高时延、易抖动丢包、通道狭窄

2.移动状态网络接入类型和接入点变化频繁

3.移动状态用户高频化、碎片化、非wifi流量敏感

原因

如下：

    第一、直观印象是通讯链路长而复杂，从（移动）终端设备到应用服务器之间，相较有线互联网，要多经过基站、核心网、WAP 网关（好消息是WAP 网关正在被依法取缔）等环节，这就像送快递，中间环节越多就越慢，每个中转站的服务质量和服务效率不一，每次传递都要重新交接入库和分派调度，一不小心还能把包裹给弄丢了；

    第二、这是个资源受限网络，移动设备接入基站空中信道数量非常有限，信道调度更是相当复杂，如何复杂就不展开了，莫文蔚那首歌词用在这里正合适：“我讲又讲不清，你听又听不懂......”，最最重要的是分配的业务信道单元如果1 秒钟不传数据就会立马被释放回收，六亲不认童叟无欺；

    第三、这个链条前端（无线端）是高时延（除某些WIFI 场景外）、低带宽（除某些WIFI 场景外）、易抖动的网络，无线各种制式网络带宽上限都比较低而传输时延比较大（参见【表一 运营商移动信号制式带宽标准】），并且，没事就能丢个包裹玩玩，最最重要的是，距离基站的远近，把玩手机的角度、地下室的深度等等都能影响无线信号的质量，让包裹在空中飞一会，再飞一会。这些因素也造成了移动互联网网络质量稳定性差、接入变化频繁，与有线互联网对比更是天上人间的差别，从【图二 有线互联网和移动互联网网络质量差异】中可以有更直观的感受；

    第四、这是个局部封闭网络，空中信道接入后要做鉴权、计费等预处理，WAP 网络甚至还要做数据过滤后再转发，在业务数据有效流动前太多中间代理人求参与，效率可想而知。产品研发为什么又慢又乱，广大程序猿心里明镜似的；最最重要的是，不同运营商之间跨网传输既贵且慢又有诸多限制，聪明的运营商便也用上了缓存技术，催生了所谓网络“劫持”的现象。如果我们再结合用户在移动状态下2G/3G/4G/WIFI 的基站/AP 之间，或者不同网络制式之间频繁的切换，情况就更加复杂了。

    除了这些物理上的约束，还有上层的约束：

    1 DNS 解析，这个在有线互联网上司空见惯的服务，在移动互联网上变成了一种负担，一个往复最少1s，还别提遇到移动运营商DNS 故障时的尴尬；
    2 链路建立成本暨TCP 三次握手，在一个高时延易抖动的网络环境，并且大部分业务数据交互限于一个HTTP 的往返，建链成本尤其显著；
    3 TCP 协议层慢启动、拥塞控制、超时重传等机制在移动网络下参数设定的不适宜；
    4 不好的产品需求规定或粗放的技术方案实现，使得不受控的大数据包、频繁的数据网络交互等，在移动网络侧TCP 链路上传输引起的负荷；
    5 不好的协议格式和数据结构设计，使得协议封装和解析计算耗时、耗内存、耗带宽，甚至协议格式臃肿冗余，使得网络传输效能低下；
    6 不好的缓存设计，使得数据的加载和渲染计算耗时、耗内存、耗带宽；

 </

本文标签： 后台点滴游戏tx