面灵AI→

游戏服务端面经:领奖落库一致性、epoll 与红黑树、王者荣耀寻路与圆形 AOE

轮次
一面
时间
2026-11
来源
牛客网

《面试题目》

  1. 实习期间做过什么功能?挑一个展开讲。
  2. 玩家领取奖励的时候有哪些需要注意的地方?
  3. 领奖的逻辑有做持久化吗?
  4. 落库有了解过什么流程吗?
  5. MySQL 断连一段时间,怎么保障异步落库的数据是正确的?
  6. 为什么硬编码数组长度为 550?为什么一定要有这个长度限制?
  7. 有了解过 protobuf 的机制吗?
  8. 怎么处理大量连接的涌入?
  9. 如果请求太频繁,怎么定位?
  10. 请求太频繁会限流,具体怎么做的?
  11. 怎么维护这么多连接?
  12. 怎么处理大量连接 IO?
  13. epoll 是用什么数据结构实现的?为什么要用红黑树?
  14. 用时间轮回收非活跃连接是怎么实现的?
  15. 「80% 阈值」和「99% 的零网络开销」讲一下?
  16. 11 万 QPS 是怎么测出来的?
  17. 内存分配器的作用是什么?
  18. 用 malloc 申请 2G 内存,操作系统是怎么做的?会直接把 2G 内存交给你吗?
  19. C++ 的特性有哪些?
  20. map 和 unordered_map 的区别?
  21. 链表的底层实现思路?
  22. 王者荣耀里从 A 点走到 B 点,你会怎样计算路径?
  23. 像红蓝 buff 那种地形,有墙不能穿越,你怎么识别?
  24. 王昭君的大招会对圆形内的玩家造成伤害,你怎么处理?
  25. 怎么在 n 个数中快速找到第 m 大的数?
  26. 栈和队列的区别?
  27. Linux 常用的命令?
  28. 进程之间的内存共享?

《参考解析》

领奖逻辑的四个坑:幂等、原子、并发、可追溯。 玩家点「领取」时最常见的错误是「先发东西再改状态」,中途宕机就会重复发。正确顺序是「先原子地把领奖状态从未领取改为已领取(带条件的 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)或原子操作,否则会有数据竞争。优点是零拷贝、速度最快;代价是要自己管生命周期与同步,进程崩溃时可能留下脏数据(所以要设计校验或版本号)。线程之间共享的是同一地址空间,不需要这些机制,但也因此任何线程都能改任意内存,隔离性更差。