游戏服务端面经:领奖落库一致性、epoll 与红黑树、王者荣耀寻路与圆形 AOE
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 实习期间做过什么功能?挑一个展开讲。
- 玩家领取奖励的时候有哪些需要注意的地方?
- 领奖的逻辑有做持久化吗?
- 落库有了解过什么流程吗?
- MySQL 断连一段时间,怎么保障异步落库的数据是正确的?
- 为什么硬编码数组长度为 550?为什么一定要有这个长度限制?
- 有了解过 protobuf 的机制吗?
- 怎么处理大量连接的涌入?
- 如果请求太频繁,怎么定位?
- 请求太频繁会限流,具体怎么做的?
- 怎么维护这么多连接?
- 怎么处理大量连接 IO?
- epoll 是用什么数据结构实现的?为什么要用红黑树?
- 用时间轮回收非活跃连接是怎么实现的?
- 「80% 阈值」和「99% 的零网络开销」讲一下?
- 11 万 QPS 是怎么测出来的?
- 内存分配器的作用是什么?
- 用 malloc 申请 2G 内存,操作系统是怎么做的?会直接把 2G 内存交给你吗?
- C++ 的特性有哪些?
- map 和 unordered_map 的区别?
- 链表的底层实现思路?
- 王者荣耀里从 A 点走到 B 点,你会怎样计算路径?
- 像红蓝 buff 那种地形,有墙不能穿越,你怎么识别?
- 王昭君的大招会对圆形内的玩家造成伤害,你怎么处理?
- 怎么在 n 个数中快速找到第 m 大的数?
- 栈和队列的区别?
- Linux 常用的命令?
- 进程之间的内存共享?
《参考解析》
领奖逻辑的四个坑:幂等、原子、并发、可追溯。 玩家点「领取」时最常见的错误是「先发东西再改状态」,中途宕机就会重复发。正确顺序是「先原子地把领奖状态从未领取改为已领取(带条件的 UPDATE 或 Redis 的 SETNX/分布式锁),成功的那一次才发放奖励」。要注意的地方:① 幂等——客户端重试、网络重发都可能触发两次,用(玩家 ID + 活动 ID + 档位)做唯一键,重复请求直接返回上次结果;② 原子性——状态变更与发奖要么在同一个事务里,要么用可靠消息/事件表串起来,保证最终一致;③ 并发——同一条奖励被多个线程同时领,需要行锁、乐观锁(版本号)或单键串行化;④ 可追溯——每一次发放都留流水(谁、什么时间、哪个活动、发了什么),出问题能对账。
MySQL 断连时异步落库怎么保证正确。 这类链路的标准解法是「先写可靠的消息/事件表,再由消费者异步落库」,而不是直接异步写库。具体做法:业务操作在本地事务里同时写业务状态和一条 outbox 事件;后台消费者读 outbox(或走 MQ),落库成功后标记已处理;MySQL 断连时消费失败会重试,消息不会丢;消费端按业务唯一键做幂等,重投不会重复写。断连期间也要有兜底——本地队列或磁盘缓冲避免内存爆掉,重连后按顺序补投;外加定时对账任务比对「Redis/内存侧状态」与「数据库侧状态」,差异超阈值告警并自动修正。要主动说出「用 Stream/MQ 也只是至少一次,不保证一定不丢」,所以幂等和对账这两层不能省。
为什么硬编码 550 是个问题。 面试官问的不是「550 这个数怎么来的」,而是「为什么要把容量写死在代码里」。硬编码上线的风险是:业务上限一变就要改代码发版;同一个魔法数字散落在多处容易改漏;超出时是静默截断还是崩溃取决于写法,很容易埋成线上事故。正确做法是配置化(配置中心或策划表),并在入口做校验与明确的拒绝/降级,同时给出监控(接近上限时告警)。如果 550 有性能依据(比如一个包的字段上限、一帧最多处理的实体数),要把这个依据写进注释与文档,并给出「超限怎么办」的确定行为。
protobuf 的机制。 核心是「用字段号而不是字段名编码」,所以兼容性好、体积小。可变长整数(varint)编码小整数只占一个字节;每个字段编码成「tag(字段号 + 线类型)」加值;嵌套消息整体当成长度前缀的字节串;repeated 默认用打包编码。兼容规则:加字段用新字段号且设默认值,删字段要把字段号保留(reserved)防止被复用,不能改已有字段的类型。相比 JSON 省掉键名、解析更快;代价是需要 schema 与代码生成,可读性差,跨版本排查问题要看工具。
海量连接与 epoll 的底层结构。 大量连接涌入时首先要分层处理:接入层做 SYN 队列与 backlog 调优、连接数上限与快速拒绝;业务层做限流与排队;单机侧用「一连接一对象的轻量结构 + 连接池/分片」控制内存。epoll 在内核里维护三样东西:一个红黑树存所有注册的 fd(epoll_ctl 增删改是 O(log n)),一个就绪链表存已触发的事件(epoll_wait 只遍历它就绪的,O(1) 拿到事件数),以及等待队列。用红黑树是因为需要「按 fd 快速插入、删除、查找且有序」,链表删除慢、哈希表虽然 O(1) 但没有序且扩容抖动大,红黑树的 O(log n) 与稳定最坏复杂度正合适。水平触发与边缘触发的区别也要能说清:LT 只要缓冲区还有数据就一直通知,编程简单;ET 只在状态变化时通知一次,必须一次读到 EAGAIN,通常配合非阻塞 IO。
时间轮回收非活跃连接。 把时间分成固定大小的槽(比如 1 秒一格、共 60 格),每个槽挂一个双向链表存该时刻到期的连接;连接每次有活动就把它的到期时间往后挪(从旧槽摘掉、插到新槽);一个指针每秒走一格,走到哪格就把那格里到期的连接关掉。插入与删除都是 O(1),比「遍历所有连接查最后活跃时间」的 O(n) 扫描高效得多。层级时间轮解决长超时的问题(秒轮、分轮、时轮),Kafka 与 Netty 的 HashedWheelTimer 都是这个思路。要注意的边界:同一连接多次续期不能重复插入、时间轮线程与业务线程的并发安全、以及到期关闭时要做优雅关闭(先半关再等对端)。
「80% 阈值和 99% 的零网络开销」 指的是自适应限流/背压里的两个设计点:请求量达到容量 80% 时开始预警或轻度限流(留出突发余量),到 99% 时对新请求快速失败或排队,不再消耗额外的网络与计算资源做无谓处理。答的时候要落到可实现的动作上:阈值来自压测的容量曲线而不是拍脑袋;拒绝要发生在最外层(接入层),越早拒绝越省资源;拒绝时返回明确的重试提示而不是超时。
11 万 QPS 怎么测出来的。 压测要说清五件事:压测工具与施压机数量(单机端口与文件句柄上限往往是瓶颈,常用多台施压机分布式压)、业务模型(请求比例、包大小、长短连接)、指标定义(QPS 是按成功请求算还是按发出请求算)、瓶颈定位(CPU、内存、网络带宽、GC、锁竞争,用 perf、pidstat、火焰图看)、以及稳定性(压多久、P99 延迟、错误率)。只报一个 QPS 数字没有意义,必须带 P99 与错误率——「11 万 QPS 但错误率 5%」和「10 万 QPS 错误率 0.01%」是两个完全不同的结论。
malloc 2G 时操作系统做了什么。 对大多数 64 位 Linux 上超过 MMAP_THRESHOLD(默认 128KB)的请求,glibc 的 malloc 会走 mmap,内核只是划出一段虚拟地址空间并记账,返回一个地址,并不马上分配物理页——这叫惰性分配(demand paging)。真正占物理内存是在第一次读写触发缺页异常时,内核才分配物理页并建立映射。所以「申请 2G 成功」不等于「有 2G 可用物理内存」;后续访问可能触发 OOM Killer。/proc/<pid>/status 里的 VmSize 与 VmRSS 的区别就在这里。相关的还有 overcommit 策略、madvise(MADV_HUGEPAGE) 大页、以及内存分配器(tcmalloc/jemalloc)的作用:减少频繁 brk/mmap 的系统调用、按线程本地缓存降低锁竞争、减少内存碎片、提升缓存局部性。
map 与 unordered_map。 std::map 是红黑树,元素按 key 有序,查找/插入/删除都是 O(log n),支持范围查询与有序遍历,节点分散、缓存不友好,每个节点有额外指针开销。std::unordered_map 是哈希表(链地址法),平均 O(1),最坏 O(n),元素无序,扩容时整体 rehash 会造成尖峰延迟,但通常更快更省内存。选型依据:需要有序遍历或范围查询用 map;只做点查且 key 的哈希质量好、在意吞吐用 unordered_map;对延迟稳定性极敏感(不能接受 rehash 尖峰)可以用预分配 reserve 或自己写开放寻址的哈希表。
链表的底层实现。 单向链表每个节点存数据与 next 指针;双向链表再加 prev,插入删除时改四个指针;带哨兵头节点可以省掉「删除首节点」的边界判断。工程上的变体:侵入式链表(把 next/prev 直接嵌进业务结构体,省一次内存分配,Linux 内核的 list_head 就是这样)、内存池或 slab 分配节点避免频繁 malloc、以及用数组模拟链表(下标代替指针)提高缓存命中。
王者荣耀 A 到 B 的寻路。 地图是带障碍的网格或导航网格(navmesh)。静态地形预先烘焙成导航网格,运行时把起点与终点映射到网格上,用 A* 搜索:f = g + h,h 用欧氏或对角线距离做启发,开放集用二叉堆(或更快的桶/跳点优化),得到折线路径后再做路径平滑(拉直、贝塞尔或漏斗算法过拐角),最后交给移动组件按速度行走。性能要点:分块与分层寻路(远处用粗略图)、路径缓存与复用、把寻路放到工作线程、限流(同屏大量单位同时寻路时排队或降精度)。要主动区分「寻路」与「避障」——A* 解决静态地形,动态单位之间的避让用局部避障(RVO/ORCA)或转向行为。
墙体怎么识别。 在网格地图里,墙就是不可通行的格子(标记位),A* 扩展时跳过;在导航网格里,墙是导航多边形之间的非连通边,寻路只在多边形的邻接图上走。实际项目里两者常混合:美术做出的地形导出成高度图与碰撞体,服务端与客户端用同一份导出的寻路数据,避免「客户端能过、服务端判定穿墙」的作弊与不同步。红蓝 buff 那种带凹槽的地形要注意「单位半径」——按格子中心走会让大体型单位卡墙,所以要用膨胀(把障碍按单位半径外扩)或多边形偏移来处理。
王昭君大招的圆形伤害判定。 一次技能释放要做三件事:确定圆形区域(圆心、半径)、找出区域内的目标、结算伤害。目标查找用空间索引而不是遍历全场:均匀网格(把地图切成格子,只查圆形覆盖到的格子里的单位)、四叉树或 BVH;AABB 粗筛后再做精确的「点到圆心距离 ≤ 半径 + 单位半径」判定。伤害结算要处理:命中时机(引导型技能是每隔一段时间结算一次,还是结束时结算一次)、同一目标是否可重复命中、护盾与减伤的结算顺序、以及服务端权威——伤害判定必须在服务端做,客户端只做表现。
n 个数里找第 m 大。 两种标准解:① 快速选择(基于快排的 partition),期望 O(n),最坏 O(n²),可以用随机化或三数取中缓解;② 维护一个大小为 m 的小根堆,遍历一遍,堆顶就是第 m 大,O(n log m),优点是数据流式到达也能用、内存只要 O(m)。补充:数据范围小时可以用计数排序或桶;海量数据分块后各块取 TopK 再归并。要说清「第 m 大」与「第 m 小」的堆方向区别,这是最常答反的地方。
栈与队列。 栈是后进先出,只在栈顶操作,用于函数调用栈、表达式求值、括号匹配、DFS 与撤销;队列是先进先出,队尾入队首出,用于 BFS、任务调度、消息缓冲、生产者消费者。变体:双端队列(两端都能进出,滑动窗口最值)、优先队列(按优先级出队,堆实现)、循环队列(数组复用空间,避免频繁移动)。实现上要注意循环队列的空满判定(牺牲一格或用 size 计数)与并发队列的无锁实现(CAS + 环形数组)。
Linux 常用命令按场景答比背清单好:看进程与资源(ps、top、htop、pidstat、free、iostat、vmstat);看网络(ss、netstat、tcpdump、curl、ping、traceroute);看文件与磁盘(ls、find、du、df、lsof);看日志(tail -f、grep、awk、sed、journalctl);排查性能(perf top、strace、gdb、pstack);以及 systemctl、crontab、tar、chmod。能讲一个自己用它定位过问题的例子,比背二十条命令更有用。
进程间内存共享。 主要方式有:mmap 映射同一个文件或匿名共享内存(MAP_SHARED)、System V 共享内存(shmget/shmat)、POSIX 共享内存(shm_open + mmap)。共享内存本身不提供同步,必须配信号量、互斥锁(放在共享内存里的 pthread_mutex 要设 PTHREAD_PROCESS_SHARED)或原子操作,否则会有数据竞争。优点是零拷贝、速度最快;代价是要自己管生命周期与同步,进程崩溃时可能留下脏数据(所以要设计校验或版本号)。线程之间共享的是同一地址空间,不需要这些机制,但也因此任何线程都能改任意内存,隔离性更差。