一个游戏场景题，多线程下更新分数排行榜？｜阿里巴巴测开面经解析

60 秒回答模板

我会先确认业务语义：分数是累计增加、覆盖为最新值，还是只保留历史最高分；排行榜按分数降序，分数相同按玩家 id 或更新时间做确定性排序。单机强一致实现上，我会用 ConcurrentHashMap 保存 playerId 到 score 的当前状态，用 ConcurrentSkipListSet 或 ConcurrentSkipListMap 维护有序索引，索引 key 包含 score 和 playerId，避免同分时元素互相覆盖。更新时不能只依赖 ConcurrentHashMap，因为更新 map、删除旧排行项、插入新排行项是复合操作，需要在同一个临界区完成。简单版可以用一把全局锁保证正确性；性能更好的版本可用按 playerId 的分片锁保护单个玩家更新，同时对全局有序索引的修改使用较小范围的同步控制，或者采用分片排行榜加查询时归并。读多写少时可以维护 AtomicReference 的 TopN 快照，写入路径更新底层状态，按周期或阈值刷新快照，读取直接读不可变快照。写多读也多时可以接受短暂最终一致，用队列聚合更新，单线程或多分片 worker 顺序处理，再发布快照。测试上要覆盖同一玩家并发更新、不同玩家并发更新、同分排序、TopN 边界、旧节点清理、压力测试和与单线程基准结果比对。

考点 先定义问题边界

主线 识别共享状态

易错点 把 ConcurrentHashMap 当成完整排行榜…

深入解析

先定义问题边界

回答前要明确排行榜的写入语义：如果是累计分数，更新操作应是 addScore(playerId, delta)；如果是提交新成绩，可能是 setScore(playerId, score)；如果是历史最高分，应是 maxScore(playerId, score)。这三种语义决定是否允许分数下降、并发写入如何合并、旧值是否能覆盖新值。还要定义同分排序规则，例如 score 降序、playerId 升序，保证比较器稳定，否则有序集合里可能出现不可预期覆盖或顺序抖动。

识别共享状态

排行榜通常至少有两份共享状态：一份是玩家当前分数表，负责回答某个玩家现在是多少分；另一份是排序索引，负责快速取 TopN。常见组合是 ConcurrentHashMap<playerId, score> 加 ConcurrentSkipListSet<RankNode>。不能只维护优先队列，因为优先队列不擅长按玩家 id 删除旧节点；也不能只维护 map，因为每次查 TopN 都要全量排序，代价太高。

复合更新必须原子

线程安全容器只能保证单次方法调用安全，不能自动保证跨容器的一组操作安全。一次更新通常包含读取旧分数、计算新分数、从排序索引删除旧节点、写入 map、向排序索引插入新节点。只要这些步骤被其他线程穿插，就可能出现 map 是新分数但排序索引仍有旧分数，或者同一个玩家在排行榜中出现两个节点。因此要用锁、compute 内的同步策略、单线程事件队列，或其他方式把复合更新封装成原子事务。

强一致单机方案

最容易讲清楚的正确方案是用一把排行榜锁包住完整更新流程：根据 playerId 拿旧分数，按业务规则算新分数，删除旧 RankNode，写入新分数，插入新 RankNode。查询 TopN 时也在同一把锁下从有序集合头部取 N 个元素。这种方案正确性强、实现简单，适合先作为基线答案；缺点是所有更新和查询串行化，在高并发场景下吞吐受限。

锁粒度优化

如果全局锁成为瓶颈，可以引入分片锁。按 playerId 哈希到固定数量的 stripe，保证同一玩家的更新串行，不同玩家可并发计算。难点是全局排序索引仍是共享结构，修改索引时仍需保护。更进一步可以把排行榜也分片，每个分片维护局部有序集合，查询 TopN 时从每个分片取前 N 个候选再做 k 路归并。这样写入扩展性更好，但查询复杂度上升，并且要处理分片间快照一致性。

ConcurrentHashMap 与 SkipList

ConcurrentHashMap 适合做玩家分数的主存储，compute 或 merge 可以解决单个 key 的原子更新问题。ConcurrentSkipListSet 或 ConcurrentSkipListMap 适合维护按分数排序的结构，更新复杂度通常是 O(log M)。关键是排序节点必须包含 playerId，否则相同分数可能被认为是同一个元素；比较器也必须和 equals 的语义一致。即使用了这些并发容器，跨 map 和 skip list 的一致性仍需要额外设计。

优先队列和 TopN

PriorityQueue 本身不是线程安全的，并且任意删除或更新已有玩家分数的成本较高。它适合在只关心 TopN 且能接受延迟修正时使用：维护一个大小为 N 的小顶堆，分数超过堆顶才进入候选，同时用 map 记录玩家最新分数。为了处理旧节点，可以采用懒删除，弹出或读取时发现节点分数不是最新值就丢弃。但这种方案更适合近似或快照型 TopN，若要求实时强一致，SkipList 或全局锁保护的有序结构更稳。

读写分离与快照

排行榜通常读多写多，直接每次查询都加锁遍历会影响写入。可以维护一个不可变 TopN 快照，用 AtomicReference 发布。写入线程更新底层 map 和有序索引，后台任务按固定周期、更新次数阈值或事件驱动重新生成 TopN 快照。读请求直接读取快照，无锁且稳定。代价是读到的数据可能落后几十毫秒或一个刷新周期，需要业务接受最终一致。

最终一致架构

在高并发游戏场景中，排行榜经常不要求每次得分后立即全局可见，可以把用户得分事件写入队列，由一个或多个聚合 worker 顺序消费。每个 worker 负责一个分片，分片内天然串行，避免大量细粒度锁。查询时读取已发布的排行榜快照，延迟由队列堆积和刷新周期决定。该方案牺牲实时强一致，换来更高吞吐、更简单的写入路径和更稳定的读延迟。

验证与压测

测试不能只测单线程示例。要构造同一玩家被多个线程同时加分，验证没有丢失更新；构造不同玩家并发更新，验证 TopN 顺序和单线程基准结果一致；构造同分玩家，验证排序稳定；构造玩家分数下降、重复提交、删除旧节点等边界。压测时关注吞吐、P99 延迟、锁竞争、快照延迟和内存占用。最好用随机并发操作生成最终结果，再与串行模型输出对比。

易错点

把 ConcurrentHashMap 当成完整排行榜方案，忽略 TopN 查询成本。
认为用了线程安全容器就不需要保护跨结构的复合更新。
RankNode 只按 score 比较，导致同分玩家被覆盖或删除错误。
更新分数时只插入新节点，不删除旧节点，导致同一玩家重复上榜。
用 PriorityQueue 保存全部玩家，却没有解决任意玩家更新和删除的复杂度。
在高并发累计加分时使用 get 后 put，造成丢失更新。
全局 TopN 查询没有稳定快照，读到一半时被写线程修改导致结果不一致。
盲目加细粒度锁，结果没有覆盖 map 和排序索引的一致性不变量。
没有定义同分排序、分数下降、重复提交、历史最高分等业务规则。
只做功能测试，不做并发压力测试和单线程基准对比。

面试官追问

只用 ConcurrentHashMap 能不能实现排行榜？

可以保存每个玩家的最新分数，但不能高效实现实时 TopN。每次查询都遍历 map 并排序，复杂度接近 O(M log M)，玩家数量大时不可接受。如果只偶尔查询，可以接受这种简单方案；如果排行榜是高频接口，就需要额外维护有序索引或 TopN 快照。更重要的是，ConcurrentHashMap 只能解决单个玩家分数更新的线程安全，不会自动维护全局排序结果。

ConcurrentHashMap 加 ConcurrentSkipListSet 后还需要加锁吗？

通常仍然需要。因为一次更新要同时修改两个结构：map 中的当前分数和 skip list 中的排序节点。两个结构各自线程安全，不代表它们之间的一致性自动成立。比如线程 A 更新 map 后还没删除旧节点，线程 B 查询 TopN 就可能看到旧排行。除非你能接受这种短暂不一致，或者通过单线程事件流、版本号懒校验、快照发布等方式规避，否则需要锁住复合更新。

为什么 PriorityQueue 不适合直接做完整排行榜？

PriorityQueue 适合快速取最大或最小元素，但不适合根据 playerId 更新某个已有元素。玩家分数变化时，需要删除旧节点再插入新节点，普通堆删除任意元素通常需要 O(N)。并发场景还要额外加锁。它更适合维护 TopN 候选，例如固定大小的小顶堆配合最新分数 map 和懒删除，但这种方案处理强一致、同分排序和频繁更新会更复杂。

读多写少时如何优化？

读多写少适合用有序索引加 TopN 快照。写入时维护完整排行榜结构，定期生成不可变 TopN 列表，并通过 AtomicReference 一次性发布。读请求只读快照，不需要加锁，也不会受写线程影响。这样牺牲的是实时性：刚写入的分数可能要等下一个刷新周期才出现在读结果中。刷新周期可以根据业务要求设置，例如几十毫秒、一秒，或者达到一定更新次数后触发。

写多读多时怎么做扩展？

写多读多时，全局锁会成为明显瓶颈。可以按 playerId 哈希分片，每个分片维护自己的分数表和局部排行榜，写入只影响一个分片。查询全局 TopN 时，从每个分片取局部前 N 个候选，再做归并得到最终 TopN。如果读请求极高，还可以让后台线程周期性合并所有分片并发布全局快照。这样写入扩展性好，读路径也稳定，但系统变成最终一致，需要明确延迟和刷新策略。

同一玩家并发提交多个分数怎么保证不丢？

要看分数语义。如果是累计加分，应使用原子累加语义，确保多个 delta 都被合并进去；如果是覆盖最新值，需要用时间戳、版本号或服务端顺序来判断谁是最新；如果是历史最高分，则应使用 max 逻辑，低分提交不能覆盖高分。实现时不能先 get 再 put 而不加保护，因为两个线程可能读到同一个旧值并互相覆盖。可以使用 ConcurrentHashMap.compute、玩家级锁或队列串行化来保证同一玩家更新有确定结果。

如何测试这个排行榜是否真的并发安全？

需要把并发结果和一个单线程基准模型对比。测试可以随机生成大量玩家更新事件，一份交给并发实现执行，一份按固定顺序交给串行模型执行，然后比较最终每个玩家分数、TopN 顺序和同分排序。还要专门构造同一玩家高并发加分、TopN 边界玩家反复进出榜、同分大量玩家、快照刷新期间读取等场景。仅靠跑几次没有异常是不够的，因为并发错误经常表现为偶发错序或旧节点残留。