系统设计 25：司机指派竞争与迟到确认

两名乘客同时命中同一位最近司机，地理查询都没有错，却只能有一单得到有效指派。附近搜索解决“谁可能接单”；派单解决“谁独占接单权”。如果将位置索引中的司机从“可用”改为“忙碌”就算确认，两个请求仍可能在旧副本中各拿到一次成功。

本文用一位本地模拟司机、十二个并发乘客请求和真实 SQLite 写事务划清派单边界；不假设任何网约车公司的内部实现。规模和服务目标均为教学假设，非实测性能。

把一次派单拆成两个确认

乘客请求 POST /trips {pickup, destination, request_key}；服务返回 trip_id、状态。派单内部接口 offer(trip_id, driver_id, offer_token, deadline) 把“占有接单机会”写入权威存储；司机本地模拟回调 POST /offers/{token}/ack。状态路径为 requested → offered → accepted → started → completed，在发车前可 cancelled，超时可 expired。本次实验只实现至 accepted 的发车前取消；发车后的取消、计价、资金清算和真实司机设备均不在范围内。

不变量：同一司机同一时刻至多有一个 offered/accepted 行程；同一行程只能接受其当前有效 offer token；迟到确认不能复活已超时或已取消的行程。一次 API 重试还需用稳定 request_key 返回同一行程，不能凭 HTTP 超时就创建第二单；实验只验证指派竞争，不验证请求入口的幂等键。教学 SLO：候选查询 p99 ≤ 100 ms、从下单到得到有效司机确认 p95 ≤ 15 s、取消到该司机重回可派池 p99 ≤ 2 s，均未做负载验证。排除真实 GPS 漂移、派单最优解、司机作弊、跨城漫游与支付。

权威表可简化为 drivers(id PK, state, location_version)、trips(id PK, request_key UNIQUE, state, driver_id, deadline, offer_token)，在 trips(driver_id) WHERE state IN ('offered','accepted') 上建部分唯一索引；位置索引是非权威候选视图。数据库事务里先确认行程仍 requested，再条件地占司机、更新行程和提交，事务提交后才推送 offer。推送失败回收租约，而非把“没收到消息”解释为司机已确认。SQLite 事务说明对 BEGIN IMMEDIATE 的写事务有明确语义；部分索引文档说明 WHERE 如何只索引满足条件的行。部分唯一索引是多行行程表的候选防线；本地脚本只用一行 driver 的条件更新验证单司机指派，不代表跨地域多主写入已被协调。

候选再多也不能突破单车容量

假设 10 万活跃司机每 5 s 发一次 96 B 的位置更新，均值为 100,000 / 5 = 20,000 update/s、有效数据约 1.92 MB/s；短时 3 倍为 60,000 update/s、5.76 MB/s。假设每天 200 万次下单，平均 23.15 request/s，晚高峰系数 12 得约 277.8 request/s；每次半径检索 30 个候选，调度判断约 8,334 candidate-check/s，并不是 8,334 次数据库写入。假设请求/响应共 1 KiB，峰值 API 有效带宽约 277.8 KiB/s；推送另计。

当前司机状态按 128 B/人估计是 12.8 MB 逻辑量，三副本 38.4 MB；若每次位置上报都保留 80 B 且保留一天，新增日志约 20,000 × 86,400 × 80 B = 138.24 GB/天，三副本 414.72 GB/天（未计压缩与索引）。将上报频率从 5 s 缩为 1 s，写入增为 100,000 update/s、一天约 691.2 GB 日志，却不会把可用车辆增为五倍。若商业活动让 30% 峰值订单在同一商圈，热点大约 83.3 order/s，应监控候选司机复用率与事务冲突，而非只看整体 QPS。

flowchart LR
    M[司机位置更新] --> G[(地理候选索引)]
    C[乘客行程] --> Q[筛选邻近司机]
    G --> Q
    Q --> D[派单事务服务]
    D --> T[(权威司机与行程表)]
    D --> O[本地模拟司机 offer]
    O --> A[带 token 的确认]
    A --> D
    D --> C

起步方案是单写者 SQLite（工程部署可选一套具有同等条件更新和唯一约束能力的事务库），完整设计要求司机与行程同一事务；本实验压缩为 driver 上的 owner、state、generation、deadline 四个字段，避免靠事件通知决定占用状态。第二方案是按司机 ID 划归属分片、每位司机只有一名有效写入者，可扩展不同司机的写入，但分区迁移、栅栏令牌、主从切换和跨分片重试变复杂；未验证前不宣称其能消除跨节点竞态。另一个被放弃的方案是“每个派单 worker 在本地缓存可用标记”：读取快，但两个 worker 在同一时刻仍会各发 offer，适合仅生成候选、再交由权威事务做最终占位，不适合确认独占。

sequenceDiagram
    participant P1 as 乘客甲
    participant P2 as 乘客乙
    participant D as 派单事务
    participant S as 模拟司机
    P1->>D: 请求司机 1
    P2->>D: 请求司机 1
    D-->>P1: 占位并提交 offer token 1
    D-->>P2: 已被占用 换候选
    D->>S: 发送 offer 有效至 t=110
    Note over D,S: 无确认 到期释放司机
    S->>D: t=111 迟到确认 token 1
    D-->>S: 拒绝 已过期

恢复由权威状态驱动：过期定时器重放时用 deadline <= now AND state=offered 条件更新，释放司机必须和行程状态更新处于同一事务；取消请求重复到达时返回终态，不得再次释放已分配给新行程的司机。若事务成功却丢失派单响应，按行程 ID/幂等键查询终态，不盲目再次占用司机。司机已经确认后的取消只覆盖发车前状态；发车后订单与司机资源需另一套明确的结算流程。主库不可写时停止发放“已占用成功”答复，恢复后扫描过期 offer、对账司机与 active 行程数，确认索引与权威表一致再开放派单。

实测命令 python3 -B examples/system-design/labs/25/dispatch.py，版本、逻辑时间、输出与退出码见 examples/system-design/evidence/25/RUN.md。12 个线程各自连接同一磁盘 SQLite，只有一个条件更新把司机从 idle 改为 offered。t=10 释放旧占位后，订单 99 获得 generation 2；t=11 的旧代际确认更新 0 行，当前代际确认更新 1 行，取消后迟到确认再次更新 0 行。最终司机 idle。脚本未创建 trips 表或部分唯一索引，未验证请求幂等键；两表生产候选设计须另做事务约束实验。线程赢家不固定，断言与赢家 ID 无关。

[PATTERN] 候选与承诺分离：地理筛选返回可能对象集合，权威原子占位才授予资源；确认携带版本/令牌且检查截止时间。换成仓库工位或共享设备，资源 ID、过期时间和确认消息换参数即可复用；只有最终写入点能作出“已经分配”的承诺。

追问与速查

司机确认恰好和超时在同一秒抵达，谁赢？约定严格 now < deadline 才接受，以权威事务顺序和统一时钟裁决。司机端显示“已接单”，但确认响应丢失，该怎样查询？按 token 查询行程状态，而非发新 offer。一个司机跨城迁移时旧分片仍在写，该怎样防止旧写者复活？需要排他归属或栅栏版本，不是把缓存 TTL 调低。

触发条件	模式	恢复条件
并发命中一位司机	原子占位 + active 唯一约束	确认事务提交
确认超时/迟到	deadline + token 条件转移	回收后才能重派
取消与新派单交错	条件释放对应行程	状态与司机一致