OpenAI 面试题：设计一个在线国际象棋平台

针对 OpenAI 国际象棋题目的完整解决方案：基于等级分的匹配与原子配对、按对局路由的有状态游戏服务器、走子流水线、服务器持有的时钟与超时检测、延迟补偿、持久化、断线重连以及故障转移。

作者：The Forward Deployed 编辑团队已审阅

本文属于 OpenAI 系统设计题库。该题目具有该轮面试的代表性。分析与解决方案为本站原创。

问题描述

玩家选择一种时间控制方式，例如每步 3 分钟加 2 秒，以及等级分对局或休闲对局。系统需要在几秒内为其匹配等级分相近的对手。对局过程中，走子需在大约 150 毫秒内传递给对手，且每位玩家的时钟只在其回合内倒数。锦标赛、机器人（bot）和反作弊分析不在范围内，除非面试官额外提出。

澄清问题

• 规模？ 练习场景：每天 200 万玩家，峰值时 10 万场对局同时进行。
• 时间控制？ 从 1 分钟超快棋到 30 分钟对局，每步可选增加时间。
• 延迟目标？ 配对 p95 在 5 秒内；走子传递 p95 在 150 毫秒内。
• 时钟精度？ 大约 100 毫秒以内。在超快棋中，这直接决定胜负。
• 断线后怎么办？ 断线玩家的时钟继续倒数，这是国际象棋的正常规则，超时后对手可以选择判胜。
• 对局历史？ 每场已结束的对局都会被存储并可供查看。

在线国际象棋的难点在哪里

国际象棋的逻辑很简单；难的是在网络之上保证公平。

时钟才是问题的核心。每位玩家的屏幕上都显示一个计时器，但网络会让每条消息延迟几十到几百毫秒，且对每位玩家的延迟各不相同。如果由客户端判定时间耗尽，作弊者就可以停掉自己的时钟。如果服务器简单地判定，连接较慢的玩家就会损失他们从未使用过的时间。在 1 分钟的对局中，每步几百毫秒就能决定结果。

对局还是有状态且长时运行的。每一步棋都必须按顺序、恰好一次地应用到同一个权威棋盘上，即使玩家连接中断、客户端重发消息也是如此。

因此，核心矛盾是实时响应性与权威公平性之间的权衡。走子必须感觉上是即时的，而服务器必须是棋盘和时钟的唯一裁判。

flowchart LR A([White]):::user <-->|WebSocket| GW[Gateway]:::svc B([Black]):::user <-->|WebSocket| GW GW -->|route by game_id| GS[Game server<br/>board + clocks in memory]:::store MM[Matchmaking]:::svc -->|create game| GS GS --> LOG[(Move log)]:::store classDef user fill:#e6efec,stroke:#315e55,color:#171717; classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

核心思想。 每场对局只有一个所有者。服务器持有棋盘和时钟；客户端只负责展示。

核心概念

时间控制

时间控制为每位玩家提供一个时间预算，例如 180 秒，以及每步棋后可选增加的加秒，例如 2 秒。当预算归零时，玩家判负，除非对手不可能将杀，此时为和棋。

服务器权威状态

服务器上的对局副本是唯一真相。客户端发送意图（“我把 e2 的棋子走到 e4”），由服务器验证并决定。客户端永远不能告诉服务器时钟的读数。

单一所有者路由

每条与某局对局相关的消息都发送到拥有该对局的唯一一台服务器。该服务器逐个处理对局事件，因此同一棋盘不会出现并发更新。

幂等走子

每步棋都带有步数编号。服务器只应用第 N 步一次，且仅当它是下一步预期走子时才应用。重复发送的走子不会造成任何影响。

延迟补偿

测量每个客户端的网络延迟，并返还其中有限的一部分，这样慢速连接不会让玩家因快速走子而损失时钟时间。

核心思想。 服务器拥有的状态、每局对局一个所有者、用步数编号实现幂等性，以及有界的延迟补偿以保证公平。

需求

在继续阅读之前。 列出需求，然后说出你绝不会牺牲的特性。

1.1 功能需求

• 按时间控制以及等级分或休闲模式加入队列；按等级分配对。
• 实时走子；验证走法合法性。
• 运行双方时钟并加秒；在超时、将杀、逼和、认输、协议和棋或重复局面规则下结束对局。
• 提出和接受和棋；认输。
• 重新连接到进行中的对局。
• 等级分对局结束后更新等级分；存储并展示已结束的对局。

1.2 非功能需求

• 配对 p95 在 5 秒内完成。
• 走子送达 p95 在 150 ms 内完成。
• 时钟精度 约 100 ms 以内。
• 不丢失走子。 服务器已接受的走子能在任何单点故障中存活。
• 进行中对局的可用性为 99.95%。

1.3 约束与特性

公平是特性。 由时钟 bug 或丢失走子决定胜负的对局就是失败的产品。延迟是约束。 走子路径上的一切都必须在大约 150 ms 内完成，这就排除了该路径上的慢速存储和多跳协调。

粗略估算

负载由大量长连接和大量针对独立对局的小型有序更新组成。对局之间互不交互，因此可以干净地分区。一台游戏服务器处理 2,000 场对局约为每秒 200 步，单个进程轻松应对；约 50 台游戏服务器即可覆盖峰值并留有余量。

核心思想。 每秒 10,000 步小规模着法，分布在 100,000 场互不相关的对局中。正是这种独立性让系统得以扩展。

API 设计

继续阅读之前。 一位玩家在发送一步棋后连接立即断开。重连后，客户端重新发送该步棋。服务器应该怎么做？

它检查着法编号。如果该步棋已经应用，则返回当前对局状态；如果没有，则应用它。无论哪种情况，这步棋都只会发生一次。

3.1 匹配系统

POST   /v1/queue        {time_control: "3+2", rated: true}  -> {ticket_id}
DELETE /v1/queue/:ticket
WebSocket event: match_found {game_id, color, opponent, game_endpoint}

3.2 基于 WebSocket 的对局协议

client -> server
  {type: "move", game_id, move_no: 23, uci: "e2e4", client_ts}
  {type: "resign", game_id}
  {type: "draw_offer", game_id, move_no}
  {type: "draw_accept", game_id, move_no}
  {type: "sync", game_id, last_move_no}          // on reconnect
  {type: "ping", client_ts}

server -> client
  {type: "move", game_id, move_no: 23, uci, white_ms, black_ms, server_ts}
  {type: "state", game_id, fen, moves[], white_ms, black_ms, turn, server_ts}
  {type: "game_over", game_id, result: "1-0", reason: "time" | "mate" | ...}
  {type: "pong", client_ts, server_ts}

3.3 历史记录

GET /v1/games/:id -> PGN、每步棋的时钟、结果 GET /v1/players/:id/games?cursor=

数据模型

In memory on the game server (per game):
  game_id, white_id, black_id, time_control, rated,
  board (FEN), move_no, turn,
  white_ms, black_ms, turn_started_at (server monotonic clock),
  draw_offer_by?, status

Durable:
  games      (game_id, white_id, black_id, time_control, rated, status, result,
              reason, started_at, ended_at, server_id)
  moves      (game_id, move_no, uci, mover_ms_left, server_ts)
             primary key (game_id, move_no)
  snapshots  in Redis: game_id -> {fen, move_no, white_ms, black_ms, turn_started_at}
  ratings    (player_id, time_class, rating, deviation, games_played, updated_at)

着法表在以下字段上的主键

(game_id, move_no)

同时保证每个着法编号只存储一次。

高层设计

5.1 单服务器，客户端自己管理时钟

客户端自行倒计时并在超时后上报。这很简单，但极易作弊：被修改的客户端永远不会上报超时。

5.2 修复 1：服务器管理时钟和棋盘

服务器验证每一步棋，并根据自身的时间戳计算时钟。客户端显示服务器给出的结果。

5.3 修复 2：多台游戏服务器，按对局路由

将对局分散到多台游戏服务器上。匹配系统在创建对局时选择一台服务器。网关将对局 ID 的每条消息路由到该服务器，因此每场对局都有且只有一个所有者。

flowchart LR P1([Player]):::user --> GW[Gateway]:::svc P2([Player]):::user --> GW GW -->|game 17| G1[Game server 1]:::new GW -->|game 42| G2[Game server 2]:::new REG[(game_id -> server)]:::new -.-> GW classDef user fill:#e6efec,stroke:#315e55,color:#171717; classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef new fill:#ffffff,stroke:#c4492d,stroke-width:2px,stroke-dasharray:5 3,color:#171717;

5.4 修复 3：按等级匹配

匹配服务按时间控制维护队列，按等级排序，并原子性地为玩家配对。

5.5 修复 4：持久化着法与快照

每步被接受的棋在广播之前先追加到持久化着法日志中，并将一个小快照写入 Redis。故障游戏服务器上的对局可以在另一台服务器上恢复。

5.6 组合后的设计

sequenceDiagram autonumber actor W as 白方 participant G as 网关 participant S as 游戏服务器 participant L as 走子日志 participant R as Redis 快照 actor B as 黑方 W->>G: 第 23 步 e2e4 G->>S: 按 game_id 路由 S->>S: 是第 23 步吗？轮到白方吗？合法吗？ S->>S: 时钟：white_ms -= now - turn_started, += increment S->>L: 追加 (game, 23, e2e4, white_ms) S->>R: 快照 S-->>W: 第 23 步 + 双方时钟 S-->>B: 第 23 步 + 双方时钟 S->>S: turn_started = now，为黑方安排超时检查

核心思想。 权威服务器、单一所有者路由、原子化匹配，以及先写持久化日志再广播。

深入剖析

6.1 时钟

继续阅读之前。 先写出服务器处理一步棋的时钟逻辑。然后说明：当没有消息到达时，服务器如何发现某位玩家超时。

每当玩家 P 的走子被接受时：

now = monotonic_clock() elapsed = now - turn_started_at P.remaining_ms -= elapsed if P.remaining_ms <= 0: 游戏结束，P 超时判负（除非子力不足） P.remaining_ms += increment_ms turn_started_at = now turn = opponent schedule_flag_check(game_id, at = now + opponent.remaining_ms)

使用单调时钟，绝不要用墙上时间。服务器同步时间时，墙上时钟可能跳变。

停止走子的玩家不会发送任何消息，因此服务器必须自行唤醒。在游戏服务器的内存定时器轮中，在对手时间即将耗尽的时刻安排一次检查。每步走子会取消上一次检查并安排新的检查。当检查触发且没有走子到达时，该玩家超时判负。定时器轮能以极低成本处理数十万个定时器。

绝不要每秒把时钟写入数据库。它的值只在走子和超时检查时才有意义，因此随每步走子一起存储，并保存在快照中。

客户端根据服务器最后一次的数值显示本地倒计时，并在每条消息到达时校正为服务器的数值。显示只是装饰性的；服务器的判定才是最终结果。

区分答案高下的关键：时钟

弱：信任客户端，或让数据库计时

让客户端上报自己的时间，或每秒写入时钟。

良好：由服务器持有时钟，并安排超时检查

每步走子时用单调时钟计算已用时间，并为即将走子的玩家安排超时检查。

强：在真实网络条件下依然公平

加入有界的延迟补偿，解释为什么显示只是装饰性的，处理加时和子力不足的和棋，并在服务器故障切换时不让玩家为停机时间买单。

6.2 延迟补偿

继续阅读之前。 黑方的连接延迟是 200 ms，白方是 20 ms。在没有补偿的情况下，谁会损失时间？损失多少？

服务器在发送白方着法时启动黑方的时钟。黑方大约 100 毫秒后看到这步棋（往返时间的一半），思考并落子；这步棋又需要 100 毫秒才能到达。黑方每步棋要被扣除约 200 毫秒的纯网络时间。40 步棋下来就是 8 秒，在 3 分钟的对局中这是很大的开销。

用定期 ping 测量每个客户端的往返时间。当收到一步棋时，返还一部分测得的延迟：例如，取估算的单向延迟对与上限（如每步 100 毫秒）中的较小者。上限至关重要。没有它，玩家可以伪造慢速连接来换取思考时间。一些网站还为使用极慢链路的玩家保证每步棋的最低思考时间。要明确说明这一政策；这是一个公平性决策，而不仅仅是技术问题。

6.3 匹配

在继续阅读之前。 两个匹配工作进程查看同一个队列，都试图为玩家 X 配对。你如何防止 X 同时出现在两局游戏中？

为每个队列（时间控制、计分或休闲）保留一个 Redis 有序集合，以等级分作为分值。玩家 X 的匹配步骤会在一个等级分窗口内寻找最接近的对手。移除两名玩家并创建对局必须是一个原子步骤，例如用一个 Lua 脚本检查两名玩家是否仍在集合中，移除他们，并返回这一对。对于 X，只有一个工作进程的脚本能成功。

窗口随等待时间扩大：从 ±50 等级分开始，每 3 秒扩大 50，直到上限。这能让大多数玩家在 5 秒内完成配对，同时仍能为等级分罕见的玩家找到对手。

对于非常热门的时间控制，按等级分区间对队列分片，以免单个 Redis 键成为热点，并在区间边缘保留重叠。

6.4 着法、顺序与幂等性

游戏服务器一次只处理一局游戏的一条消息。对于每步棋，它按顺序检查：对局是否在进行中、着法编号是否是下一个、是否轮到发送方、着法是否合法。然后更新时钟，将着法追加到持久化日志，更新快照，并进行广播。先追加再广播意味着玩家永远不会看到可能在崩溃中消失的着法。

带有旧着法编号的重发着法会返回当前状态。编号超出预期值的着法意味着客户端状态混乱；服务器回复完整状态，客户端重新同步。

提和与认输也通过同一条有序流处理。提和会记录提出时的着法编号，并在对方走棋时失效。

6.5 重连

断线时，对局继续进行，断线玩家的时钟继续走，就像线下国际象棋一样。重连时，客户端发送

sync

附带它所拥有的最后一个着法编号。服务器会返回缺失的着法和当前时钟，如果差距较大则返回完整状态。如果玩家在设定时间内（例如 60 秒或其剩余时钟时间）未返回，对手可以认领胜利。

6.6 故障转移

在继续阅读之前。 一台承载 2,000 场对局的游戏服务器崩溃了。这些对局及其时钟会发生什么？

网关在几秒内通过健康检查失败检测到故障。协调器将崩溃服务器上的对局重新分配给健康的服务器，并更新路由表。每个新的接管者从 Redis 加载该对局的快照，与着法日志进行核对（若不一致则以日志为准），然后恢复运行。

时钟在故障期间暂停。新的接管者在恢复时将

turn_started_at

设为当前时间，因此双方玩家都不会因这次中断而被扣时。客户端重新连接、同步，并看到短暂的“正在重新连接”提示。任何已接受的着法都不会丢失，因为着法在广播之前就已持久化。

区分答案的关键：故障

弱对局随服务器一起消亡

状态仅保存在内存中，一次崩溃就终结 2,000 场对局。

良好着法与快照可持久化

在广播前写入每个着法，并在另一台服务器上恢复对局。

强公平恢复

还会在故障转移期间暂停时钟，以着法日志而非快照作为事实来源，并按着法编号重新同步客户端。

6.7 对局结束后

写入最终结果，然后向评级服务发出事件，该服务使用标准评级系统异步更新双方的评级。已结束的对局不可更改，在短时间内被频繁读取，之后很少被读取。缓存近期对局；将旧对局转移到更廉价的存储中。每步的用时数据会存入对局记录以供复盘。

6.8 游戏服务器循环

在继续阅读之前。 一台游戏服务器如何在不使用锁的情况下处理数千场对局？

为每场对局分配一个单线程的拥有者。两种常见形式：

• 每场对局一个 Actor。 每场对局都有一个邮箱。与该对局相关的消息，例如走子、和棋提议、认输和定时器触发，都进入其邮箱，由一个工作线程逐个处理。多场对局并行运行；但单场对局的事件绝不会并发执行。
• 分区事件循环。 服务器为每个 CPU 核心运行一个事件循环。对局按对局 ID 的哈希值分配到各个循环。每个循环按顺序处理其所有对局的全部事件。

无论哪种方式，一场对局的状态都只由一个线程处理，因此无需加锁。定时器轮将“超时检查”事件投递到同一个邮箱，因此同一对局的走子和超时永远不会产生竞争：先到达邮箱的事件获胜，后到的事件会发现对局状态已经改变。

flowchart LR GW[Gateway]:::svc -->|move game 42| MB42[[Mailbox: game 42]]:::store TW[Timer wheel]:::svc -->|flag check game 42| MB42 MB42 --> A42[Game 42 actor:<br/>one event at a time]:::svc GW -->|move game 43| MB43[[Mailbox: game 43]]:::store --> A43[Game 43 actor]:::svc classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

6.9 一步移动与一次超时的竞争

继续阅读之前。 黑方只剩 50 毫秒。黑方的移动几乎在超时检查触发的同时到达服务器。谁赢？

由服务器的时钟决定，按邮箱顺序执行。如果超时检查先被处理，黑方已因超时判负，迟到的移动会被以“对局已结束”拒绝。如果移动先被处理，服务器根据自身的接收时间戳计算已用时间；如果剩余时间仍为正，移动有效，而超时检查在处理时会发现回合已经改变，于是不做任何事。

使用网关从套接字取出消息时记录的接收时间戳，而不是 actor 处理它的时间。服务器内部的排队不应消耗玩家的时间。在启用延迟补偿时，先计入封顶的宽限时间再做判定。把这条规则说清楚，因为在超快棋中它决定真实的胜负。

区分答案的关键：并发

在共享棋盘上使用 WeakLocks

对每局棋使用锁，但无法解释移动与超时的竞争。

良好：每局棋一个所有者

在单线程或单个 actor 上按顺序处理每局棋的事件。

优秀：计时器进入同一顺序

将超时事件投递到该局棋自身的事件顺序中，使用接收时间戳做时钟计算，并准确解释移动与超时竞争时如何裁决。

变体

7.1 锦标赛

大量对局同时开始。预先分配对局服务器，批量创建对局，并错开通知的发送，以免网关被洪泛。

7.2 观众

热门对局可能有数千名观众。通过每局棋一个 pub/sub 频道将移动扇出到独立的观众层，并加入少量延迟，以限制对棋手的实时辅助。

7.3 反作弊

将棋手的着法与引擎的选择在多局棋上异步比较。绝不要因此拖慢移动路径。

7.4 玩家数量达到十倍时

当有一百万局棋同时进行时，在多个区域运行对局服务器，并将每局棋放置在离两名玩家延迟中点最近的区域。在快棋时限下，匹配优先选择同区域的对手。移动日志变成按对局 ID 分区的存储，等级分更新则移入按区域处理的队列。

可迁移的模式

在线国际象棋是由权威服务器时钟管理的单所有者实时状态。同样的架构适用于多人游戏、有服务器作为记录方的协作编辑器以及在线拍卖：将实体的每个事件路由到唯一所有者，按序列号排序和去重，先持久化再广播，绝不让客户端决定时间。

回顾：30 秒版答案

• 按等级分进行原子匹配。 每个队列使用有序集合，用一个原子脚本配对，随时间扩大匹配窗口。
• 每局游戏一个所有者。 网关按游戏 ID 路由；事件按顺序处理。
• 服务器拥有的时钟。 单调时间、每步棋的耗时、加秒时间、定时标志检查，无需每秒写入。
• 步数编号。 幂等的走子操作和重连后的重新同步。
• 先持久化再广播；故障转移时暂停时钟。 有上限的延迟补偿以保证公平。

测验

+为什么必须由服务器而不是客户端拥有时钟？

客户端可以被修改来停止自己的时钟。只有服务器对每步棋之间经过时间的测量才是可信的。

+当玩家什么都没发送时，服务器如何检测超时？

服务器会调度一个检查，安排在玩家剩余时间归零的时刻。如果检查触发时走子尚未到达，玩家即因超时判负。

+为什么不每秒把时钟写入数据库？

时钟的值只在走子时和超时检查时才有意义。在每步棋和快照中存储它就足够了；对 10 万局游戏每秒写入将产生每秒 20 万次无用的写入。

+为什么延迟补偿必须有上限？

没有上限的话，玩家可以伪造缓慢的网络连接，从而在每步棋上获得额外的思考时间。

+什么机制防止一个玩家被匹配进两局游戏？

配对操作在一个原子操作中将两名玩家从队列移除，该操作首先检查他们是否仍在队列中。对于给定玩家，只有一个匹配尝试能够成功。

+如何避免在游戏服务器内部使用锁？

给每局游戏一个按顺序处理其事件的所有者，例如带邮箱的 Actor。该游戏的所有事件，包括定时器触发，都经过这同一个序列。

+当走子与超时标志竞争时，由哪个时间戳决定胜负？

以服务器从套接字接收到走子的时间为准，而不是处理它的时间。内部排队不应消耗玩家的时钟时间。

资料来源与延伸阅读

• FIDE 国际象棋规则定义了时间控制、超时标志落下和子力不足的情况。
• Hashed and Hierarchical Timing Wheels介绍了用于大量定时事件的高效定时器。
• Glicko 等级分系统介绍了一种带等级分偏差的评级方法，常见于国际象棋网站。
• 相同的连接路由思路也出现在一对一聊天解决方案中。

NextCloud IDE