OJ竞赛服务：排行榜的实时更新计算

前言

OJ系统的竞赛服务，无疑是除了基础设施（判题机、代码沙箱）以外最复杂的一块内容。 这一块不仅仅涉及到比赛状态的调度（未开始->开始,进行中->结束），还涉及到比赛中排行榜的计算、存储，要尽可能地高效、精准，同时还要支持高并发（比赛场景往往会在短时间内产生大量提交）。

技术选型

对于需要实时计算的排行榜，Redis提供的Zset无疑是最合适的，天然支持去重和排名。

两种赛制的不同

目前主流的两种算法竞赛的赛制，也就是ACM赛制和OI赛制，是完全不同的两种处理逻辑。对于OI赛制比较简单，OI赛制天然以分数排名，只需要累加每题得分作为score即可。而对于ACM赛制，以解题数为先，解题数量相同的情况下按照罚时排名。但是Redis Zset只按照score维度排名，因此需要设计合理$score$计算方案。

合理的$Score$计算方案

为了将 ACM 赛制的二维排序逻辑（解题数、罚时）降维压缩到一维的 Zset score 中，我们采用了一种“高位存解题数，低位存罚时”的加权降维算法。具体公式如下： $Score = SolvedCount \times Unit - Penalty$ 这里的各个参数含义与设计考量如下： $SolvedCount$（解题数）：用户当前总共AC的题目数量。 $Unit$（极大常量单位）：作为区分题数的权重基数。通常我们会取 $10^9$（即 $1,000,000,000$）。 $Penalty$（总罚时）：单位通常为秒。 ACM规则中，某题的罚时 = 该题首次AC的时间 + (AC前的错误次数 $\times$ 20分钟)。

为什么是减去罚时？

在查榜时，我们通常使用 ZREVRANGE 按 score 降序排列（分数越高排名越靠前）。解题数越多，基数越大，排名越靠前；而在解题数相同的情况下，由于我们要保证罚时越少，排名越高，因此必须通过“减去罚时”来让总分数变大。

为什么 $Unit$ 要设置为 $10^9$？

这是为了设定一个严格的安全边界。一场标准的 ACM 比赛通常为 5 小时（$18000$ 秒），即使用户提交了成百上千次错误代码，单题罚时累加也很难超过百万秒级别。将 $Unit$ 设为 $10^9$，可以保证：无论罚时怎么扣，哪怕扣到极致，也绝对不会“吃掉”一道题的权重。 举个直观的例子：选手A：解出 3 题，总罚时 5000 秒。 $Score = 3 \times 10^9 - 5000 = 2,999,995,000$ 选手B：解出 3 题，总罚时 6000 秒。$Score = 3 \times 10^9 - 6000 = 2,999,994,000$ 选手C：解出 2 题，总罚时 10 秒。$Score = 2 \times 10^9 - 10 = 1,999,999,990$ 排序结果完美符合赛制：选手A > 选手B > 选手C。

避坑

数据精度问题很多开发者在选取如此庞大的数字时会担心溢出或精度丢失。实际上，Redis Zset 底层以及 Redis 内置 Lua 引擎处理 number 类型时，使用的都是 IEEE 754标准的 64 位双精度浮点数（Double）。其安全整数上限高达 $2^{53} - 1$（约 9000 万亿，15位十进制数）。即使比赛有成百上千道题，产生的最大分数在 $10^{13}$ 级别，依然游刃有余，绝对不会出现精度丢失。

ACM赛制的封榜处理

一场正规的ACM比赛，通常会在最后一小时开始封榜。这段时间排行榜将会冻结，比赛结束后解冻，这样就可能一下子某个队伍的排行发生很大变化，以增加比赛的刺激性。 经过调查发现，对于排行榜的封榜处理，最好的办法就是在封榜后也不更新排行榜数据（如果管理员需要在封榜期间实时查看排行榜，可能需要将封榜后的排行榜保存快照供封榜后查询），以最小成本的达到封榜的目的。

执行流程

消费者监听

判题服务完成判题后，会对于比赛场景的提交将排行更新消息投递到比赛场景的消息队列。我的项目中使用的是RabbitMQ完全足够。 对于ACM的封榜机制，消费者判断提交时间对应的比赛时段是否需要更新排行榜即可，如果已封榜或者已结束，则直接确认消息返回即可。

比赛排行服务

如果当前比赛需要更新，则调用具体的服务实现。 我这里决定，将计算权完全交由Redis Lua脚本。

传统方案的痛点与“逻辑下沉”

在分布式高并发场景下，排行榜的更新本质上是一个 Read-Modify-Write（读-改-写） 的过程。如果把这部分逻辑放在 Java 层处理，流程通常是这样的：

1. 从 Redis 读取用户某题的当前状态（是否已 AC，错误次数等）。
2. 在 Java 内存中判断并修改状态。
3. 将新状态写回 Redis，并计算总分更新 Zset。

这种模式在比赛期间的并发提交下，极易发生并发事故。例如：用户的两次重复代码提交在极短时间内完成评测，Java 层的两个线程可能同时读取到该题“未 AC”且“尝试次数为 0”的旧状态。在各自修改写回后，尝试次数只增加了 1，导致错误次数少算；或者更糟糕的，同一道题被加了两次分。

为了解决这个问题，常规做法是引入可重入式分布式锁（如 Redisson）。但这会带来额外的网络 I/O 开销，并且在高并发竞争下引发线程阻塞，严重降低评测消息的消费吞吐量。

因此，“逻辑下沉（Logic Pushdown）” 成了最优解。利用 Redis 单线程执行 Lua 脚本的原子性，我们将数据校验、状态修改和分数计算全部封装在一段脚本中发送给 Redis，相当于在数据库层实现了一个免锁（Lock-free）的高性能状态机。

核心架构：O(1) 的原子增量更新

早期的很多系统会在每次提交后，拉取该用户所有的题目详情，重新遍历累加计算一次总成绩（O(N) 复杂度）。随着用户解题数增多，这种全量计算的性能会随之下降。结合 Lua 脚本，我们实现了绝对安全的 O(1) 增量更新（ZINCRBY）。

ACM 赛制的 Lua 状态机演进

ACM 赛制的核心难点在于 “防穿透” 与 “状态封锁”。一旦某题判定为 AC，后续针对该题的任何提交（无论是重复的 AC 还是 WA）都必须被拦截，不能再影响成绩。

我们将计算权移交后，Lua 脚本的执行流如下：

并发防线：脚本首先读取 Hash 中该题的旧详情，若发现 $solved == true$，直接中断并返回当前总榜分数。这道防线彻底杜绝了并发导致的重复刷分。

状态演进：如果未 AC，则根据本次提交的状态码，增加总错误尝试次数。

增量加分：当且仅当本次提交判定为 AC 时，计算该题的最终罚时（答题耗时 + 之前的计罚时错误次数 * 1200秒）。随后计算出增量分数（1,000,000,000 - 最终罚时），利用 ZINCRBY 命令原子性地将其累加到大榜。

持久化写回：最后，将最新的题目状态 JSON 写回 Redis Hash 中。

OI 赛制的极致精简

相比之下，OI 赛制“以最后一次提交得分为准”的逻辑在增量计算模式下显得更为纯粹。它不需要状态防穿透，只需要计算新旧分数的差值即可：

脚本从 Hash 中提取该题上一次的旧得分（如果没有则默认为 0）。

计算分数差值 $Delta = 本次新得分 - 旧得分$

将本次的最新得分覆写进 Hash 详情。

如果 Delta 不为 0，直接执行 ZINCRBY 更新 Zset（ZINCRBY 天然支持负数，即使某次提交得分比上次更低，产生的负数 Delta 也能完美将排行榜分数扣除）。

Java 层的彻底解耦

在上述架构设计下，排行榜服务（Java 端）变得极其“轻薄”。Java 彻底不再关心“当前这道题尝试了几次”、“之前有没有通过”等中间演进状态。

对于每一次需要更新成绩的提交，Java 只需要将几个最基础的元数据计算好并透传给 Redis：userId、questionId、当前答题耗时(秒)、状态码(AC/计罚时错误/不计罚时错误)。剩下的并发控制、状态流转、数值运算，全部交由 Redis 内部的 Lua 引擎在单次网络往返中瞬间完成。

这种将状态机逻辑前置到存储层的做法，极大地释放了 Java 服务的计算与内存压力，让整个 OJ 系统能够从容应对各种高强度的算法竞赛。