系列导航：上一篇 21 有限能力的数据库路由代理 ｜ 本篇 22 ｜ 下一篇 23 分片扩容时的数据交接

订单按买家 user_id 分片之后，“某个买家的订单”只落在一个库里，查询直接路由即可。“某个商户的订单，按下单时间倒序分页”就不同了：同一商户的订单散在每一个分片上，路由层手里没有能把它收窄到单个分片的条件。上一篇的路由代理对这类语句的处理是拒绝。业务上这个查询不能不做，于是有两条路：每次都问遍所有分片，再在协调方合并；或者额外维护一张按商户组织的全局索引，先查索引再回分片取数。

两条路都要回答同一组问题：翻页时同一行会不会出现两次，会不会有行永远翻不到；翻页期间有新订单写入时，边界划在哪里；索引和主数据不一致时返回什么；一次查询最多允许打到几个分片、等多久。代码在 examples/22-shard-query/，输出在 evidence/22/output.txt。

查询契约与规模假设

查询只有一种：给定 merchant_id，按 (created_at desc, order_id desc) 返回一页订单，以及一个用于取下一页的不透明游标。对它的承诺如下：

  • 翻页过程中始终存在且没有被修改的行，恰好返回一次。
  • 任何一行在一次完整翻页中最多出现一次。
  • 翻页期间新插入的行，排序键排在当前游标之后的会在后续页出现；排序键落在已读区间里的不会出现。
  • 一次分页触达的分片数不超过调用方给出的扇出预算，每个分片单次返回的行数不超过行数预算；超出预算在发出任何语句之前拒绝。
  • 某个分片在截止时间内没有返回时，要么整页失败，要么返回标记为不完整的结果；不完整的结果不签发下一页游标。

不承诺跨分片的一致快照。每个分片执行的是各自的语句，PostgreSQL 在 READ COMMITTED 下“只看到语句开始前已提交的数据”（PostgreSQL 16 事务隔离），三个分片的三个语句没有共同的时间点。上面的第三条因此按排序键定义，而不按提交时刻定义。

教学规模：3 个分片（b2_22_s0..s2），12000 个合成订单，300 个用户，10 个商户。created_at 取秒级时间、落在 2 小时窗口内，平均每秒约 1.7 行，重复时间很常见；商户 7 另有 400 行的 created_at 完全相同，用来放大重复排序值的问题。order_id 先生成再打乱，与时间顺序无关，否则 tie-breaker 的作用看不出来。数据由固定种子 22 生成，每组用例前重建。

数据模型

每个分片上的订单表带一个复合索引，列顺序与查询的等值条件和排序一致：

1
2
3
4
create table orders (
  order_id bigint primary key, user_id bigint not null, merchant_id int not null,
  created_at timestamptz not null, amount_cents bigint not null, status text not null);
create index orders_merchant_ct on orders (merchant_id, created_at desc, order_id desc);

多列 B-tree 索引在“前导列上的等值条件，加上第一个没有等值条件的列上的不等式”时能限定扫描范围（PostgreSQL 16 多列索引）；索引顺序与 ORDER BY 一致时，LIMIT n 可以直接取前 n 行而不扫描其余部分（索引与 ORDER BY）。本章没有检查执行计划，这两条只作为建索引的依据。

方案 B 另有一个独立的索引库 b2_22_idx：

1
2
3
4
5
create table merchant_order_idx (
  merchant_id int not null, created_at timestamptz not null, order_id bigint not null,
  user_id bigint not null, shard int not null,
  primary key (merchant_id, created_at, order_id));
create unique index merchant_order_idx_order on merchant_order_idx (order_id);

一个订单只属于一个商户，所以 order_id 唯一，维护时可以按订单号先删后插。

排序必须是全序

PostgreSQL 文档在 LIMIT 一节写得很直接：“When using LIMIT, it is important to use an ORDER BY clause that constrains the result rows into a unique order. Otherwise you will get an unpredictable subset of the query’s rows.”（PostgreSQL 16 LIMIT 与 OFFSET）。只按 created_at 排序时，同一秒的几行之间没有确定的先后，两次执行可能给出不同的排列；分页又依赖“上一页最后一行”来决定下一页从哪里开始，这一行本身不确定，边界也就不确定。

加上唯一的 order_id 作为第二排序键，排序变成全序。游标保存最后一行的 (created_at, order_id)，下一页的条件用行构造器比较写成 (created_at, order_id) < (?, ?)。行构造器的 < 按元素从左到右比较，遇到第一对不相等的元素就由它决定结果（PostgreSQL 16 行比较），所以这个条件恰好等价于“在全序中排在游标之后”。

负向对照把游标退化为只有 created_at。在商户 7 上（1560 行，其中 400 行同一时刻，页大小 37）：

1
2
CASE negative_ts_only_cursor_strict       PASS expectMissing cond='created_at < ?' truth=1560 returned=1196 missing=364 dup=0 pages=33
CASE negative_ts_only_cursor_inclusive    PASS expectDupOrStuck cond='created_at <= ?' returned=74 dup=37 stuck=true pages=2 missing=1523

严格小于时，第一页在 400 行重复值中间停下（这 400 行时间最新，排在最前），下一页从“早于这一秒”开始，同一秒剩下的 363 行全部跳过；其余 1 行丢在另一个落在重复秒内的页边界上，合计 364 行。改成小于等于，第二页又从同一秒开头取，重复了第一页的 37 行，之后游标不再前进。两种写法都没有报错，结果只是悄悄地错了。

方案 A：分散-汇聚

协调方对每个分片执行同一条语句，取各自的前 pageSize 行，再按全局顺序做 k 路归并。全局前 n 行一定落在各分片各自的前 n 行之内：如果全局第 k 行（k ≤ n）来自某个分片，那么它在该分片内部的名次不会超过 k。每个分片多取一行也没有必要。

图 22-1：分散-汇聚的一次分页（共享截止时间、超时取消、不完整结果不签发游标）

sequenceDiagram
    participant C as 调用方
    participant Q as 协调方 ScatterGather
    participant S0 as 分片 s0
    participant S1 as 分片 s1
    participant S2 as 分片 s2
    C->>Q: byMerchant(m, cursor, n, budget)
    Q->>Q: 预算检查 n ≤ maxRowsPerShard, 分片数 ≤ maxFanout，否则拒绝（不发语句）
    par 共享截止时间 shardTimeoutMs
        Q->>S0: keyset 条件 + LIMIT n
        Q->>S1: keyset 条件 + LIMIT n
        Q->>S2: keyset 条件 + LIMIT n
    end
    S0-->>Q: ≤ n 行
    S1-->>Q: ≤ n 行
    Note over Q,S2: s2 超过截止时间 → Statement.cancel()，等语句结束
    alt allowPartial = false
        Q-->>C: SHARD_TIMEOUT
    else allowPartial = true
        Q-->>C: 归并结果, complete=false, missingShards=[2], nextCursor=null
    end

归并部分的实现（src/ScatterGather.java）：

1
2
3
4
5
6
7
8
9
10
11
12
13
while (out.size() < pageSize && !heads.isEmpty()) {
    int[] h = heads.poll();
    List<Db.OrderRow> l = r.rows().get(h[0]);
    out.add(l.get(h[1]));
    if (h[1] + 1 < l.size()) heads.add(new int[]{h[0], h[1] + 1});
}
boolean complete = r.timedOut().isEmpty();
String next = null;
// 不完整结果不签发游标：缺席分片里可能有排在游标之前的行，签发后这些行会被永久跳过。
if (complete && out.size() == pageSize) {
    Db.OrderRow last = out.get(out.size() - 1);
    next = new Cursor(merchantId, last.createdAt(), last.orderId()).encode();
}

最后一个判断定义了不完整结果的契约。缺席的分片里可能有排序靠前的行；如果按已到达的行签发游标，调用方用它翻下一页，这些行就排在游标之前，再也不会出现。不签发游标，调用方只能用原游标整页重试，结果最多是慢，不会错。

游标编码了商户号。拿商户 3 的游标去查商户 4，或者传入无法解码的字符串，返回 BAD_CURSOR。游标没有签名，调用方可以伪造一个排序键，但伪造的结果只是从另一个位置开始翻页，不会越过商户条件。

商户 3（1217 行，页大小 50）与商户 7 的完整翻页结果，与直接读全部分片后在内存中排序得到的真值逐行一致：

1
2
CASE scatter_full_scan                    PASS merchant=3 truth=1217 returned=1217 pages=25 dup=0 missing=0 sameOrder=true statements=75 maxRowsFetchedPerPage=150
CASE scatter_duplicate_sort_values        PASS merchant=7 truth=1560 rowsAtSameTs=400 pageSize=37 pages=43 boundariesInsideTies=13 returned=1560 dup=0 missing=0 sameOrder=true

商户 7 的 43 个页边界中有 13 个落在同一 created_at 的重复值内部，游标靠 order_id 在重复值中间准确续上。代价也写在输出里：25 页共发出 75 条语句，每页从三个分片取回 150 行，只用其中 50 行。扇出系数等于分片数，与结果大小无关。

翻页期间的插入与删除

keyset_concurrent_insert 在翻页的同时开一个线程，持续以当前时间为商户 3 插入新订单；在第 2 页之后，再做四个确定的动作：插入一行排序键在游标之后的订单、插入一行排序键落在已读区间的订单、删除一行尚未读到的初始订单、删除一行已经读过的初始订单。

1
CASE keyset_concurrent_insert             PASS pages=25 returned=1217 dup=0 initial=1217 missingInitial=0 concurrentInserted=34 concurrentSeen=0 behindCursorSeen=true insideReadRangeSeen=false deletedUnreadSeen=false deletedAlreadyReadWasReturned=true

并发插入的 34 行时间都比数据集新，排在第一页之前，后续页一行也看不到；初始行没有遗漏，也没有重复。另外四个动作的结果对应契约的第三条：排在游标之后的回填行出现了，落在已读区间里的行没有出现，删除的未读行不再出现，删除前已读过的行已经在早先的页里返回。

“落在已读区间里的行不会出现”在实际系统中有一个具体来源：created_at 由应用服务器赋值，服务器之间有时钟偏差，或者事务在赋值之后很久才提交。一行订单可能带着早于当前游标的时间戳晚到。keyset 分页对这种行的处理是确定的，它会在下一次从头翻页时出现，本次翻页看不到。需要“翻页期间不遗漏任何晚到行”的场景，排序键必须在提交顺序上单调，例如由单一序列在提交时分配，这超出了本章的数据模型。

全局 OFFSET 分页是常见的错误对照：每个分片取 offset + size 行，归并后跳过前 offset 行。数据静止时它是对的。同样在第 1 页后插入 3 行新订单、第 3 页后删除 1 行已读订单：

1
CASE negative_offset_concurrent_insert    PASS expectDupAndMissing pages=25 returned=1219 initial=1217 dup=3 missingInitial=1 (3 inserts after page 1, 1 delete after page 3)

新插入的 3 行把所有已有行的名次推后 3 位，第 2 页开头重复了第 1 页的最后 3 行；删除一行已读订单又让后面的行整体前移 1 位，一行未读订单滑进已经跳过的区间，从未返回。OFFSET 按名次定位，名次随写入变化；keyset 按排序键定位，排序键不随其它行的写入变化。效率上 OFFSET 还有一个问题，被跳过的行仍需在服务端计算（同一文档），而全局 OFFSET 让每个分片都计算 offset + size 行，第 25 页时每个分片要排出 1250 行。

预算与超时

扇出预算和行数预算在入口检查，不满足时一条语句都不发：

1
CASE fanout_and_size_budget               PASS scatter(maxFanout=2)=FANOUT_EXCEEDED statementsIssued=0 pageSize500=PAGE_TOO_LARGE statementsIssued=0 index(maxFanout=1)=FANOUT_EXCEEDED scatter(maxFanout=3)=OK

分散-汇聚的扇出在查询之前就已知（全部分片），可以提前拒绝。索引方案的扇出要读完一批索引项才知道，IndexQuery 在回分片取数之前检查本页触达的分片数，同样在发出分片语句之前拒绝。

超时用一个慢分片验证：测试先在分片 2 上用管理员连接执行 LOCK TABLE orders IN ACCESS EXCLUSIVE MODE，让该分片的查询一直等锁，再以 300ms 截止时间查询：

1
CASE shard_timeout_contract               PASS strict=SHARD_TIMEOUT elapsed=322ms partial: complete=false missingShards=[2] rows=50 rowsFromShard2=0 nextCursor=null elapsed=308ms lockWaitersAfterCancel=0 afterUnlock: complete=true

到期时 ShardCalls 对该分片的语句调用 Statement.cancel()，并等待语句真正结束后才返回，以免这条连接上残留一个仍在等锁的查询。lockWaitersAfterCancel=0 是在服务端 pg_stat_activity 中查到的等锁会话数。解锁后同一组连接正常完成查询。服务端也可以用 statement_timeout 作为兜底（PostgreSQL 16 客户端连接参数），本实验没有使用。

方案 B：全局二级索引

Vitess 把这类结构叫作 Lookup Vindex：“A Lookup Vindex is implemented as a MySQL lookup table that maps a column value to keyspace IDs”，文档也说明它们“informally referred to as cross-shard indexes”（Vitess v24.0 Vindexes）。同一页面指出，没有这类二级 Vindex 时，VTGate 只能把查询分散到所有分片；非唯一的 lookup 表要带上能唯一标识原行的列，通常就是原表主键。merchant_order_idx 带上 order_id 与 shard，正是为了从索引项定位到一行确切的订单。

索引项与订单不在同一个库里，维护它就是跨库写。Vitess 文档对 owner 表自动维护 lookup 行的描述是“These essentially result in distributed transactions, which traditionally require 2PC to guarantee atomicity”，它的一致 lookup 用加锁和提交顺序来避免 2PC。本章不实现这种方案，只比较两种更朴素的维护方式。

图 22-2：索引方案的状态归属与维护路径（实线为同步，虚线为异步）

flowchart LR
    W[写路径 OrderStore] -->|同一本地事务| O[(分片 sN: orders<br/>权威数据)]
    W -->|同一本地事务| X[(分片 sN: order_outbox<br/>待同步变更)]
    X -.->|FOR UPDATE SKIP LOCKED 取批| I[Indexer]
    I -.->|先删后插, 提交①| IDX[(b2_22_idx: merchant_order_idx<br/>派生数据, 可滞后)]
    I -.->|删除已应用记录, 提交②| X
    R[读路径 IndexQuery] -->|1 读索引项| IDX
    R -->|2 按 order_id 取行并复核| O
    F[修复任务 Repair] -->|扫描比对, 点查后修正| IDX
    F --> O

同步双写（DoubleWriter）先提交分片上的订单，再写索引库。两个库没有共同的提交点，进程在两次提交之间退出，订单存在而索引项不存在。实验用 Runtime.halt(137) 在这个位置终止两个双写进程，第三个正常完成：

1
doubleWriters=[exit=137[DOUBLEWRITE shard_committed order=900044 shard=0], exit=137[DOUBLEWRITE shard_committed order=900045 shard=1], exit=0[...index_committed order=900046]]

调换顺序、先写索引，崩溃留下的就是指向不存在订单的索引项。两种顺序都有残留，区别只是残留的种类。

发件箱（OrderStore + Indexer）把“需要更新索引”这件事写进订单所在分片的同一本地事务，它与订单要么一起提交，要么一起回滚。维护器每轮在分片上用 FOR UPDATE SKIP LOCKED 取一批记录（“any selected rows that cannot be immediately locked are skipped”，PostgreSQL 16 SELECT），在索引库的一个事务里按 order_id 先删后插，提交索引库，再删除发件箱记录并提交分片。第二次提交之前崩溃，发件箱记录还在，下次再应用一遍。先删后插对重复应用不敏感：

1
CASE indexer_crash_replay_idempotent      PASS pendingBefore=30 indexerExit=137 [INDEXER halt_after_index_commit batch=10] pendingAfterCrash=30 indexEntriesAfterCrash=1089 replayed=30 indexEntries=1109 truth=1109 sameAsTruth=true

同一订单的两条发件箱记录（例如先插入、后改商户）由订单行锁串行化：第二个事务要等第一个提交才能更新这一行，它的发件箱记录也就在之后才写入，按 seq 顺序应用即可保持先后。发件箱方案的代价是滞后：订单提交与索引更新之间有一段时间差，长短取决于维护器的轮询频率和积压量，本章没有测量。

读路径必须复核

索引是派生数据，读路径不能把它当作事实。IndexQuery 读一批索引项，按分片分组，用 order_id = any(?) 回主分片取行，再检查三件事：行存在，merchant_id 仍是查询的商户，created_at 与索引项一致。不满足就丢弃，继续读下一批，最多 4 轮：

1
2
3
4
5
6
7
8
for (Entry e : batch) {
    posTs = e.createdAt(); posId = e.orderId();
    Db.OrderRow o = rows.get(e.orderId());
    if (recheck) {
        if (o == null || o.merchantId() != merchantId || o.createdAt() != e.createdAt()) { filtered++; continue; }
        out.add(o);
    } else { ... }
}

游标推进到最后一个已消费的索引项，被丢弃的项也算消费过，否则下一页会再次读到它们。4 轮读完仍凑不满一页时返回短页并签发游标，短页不表示结束，只有索引读完才不签发游标。

index_lag_with_recheck 在发件箱未消费时，把商户 3 的 5 个订单改到商户 4、删除 5 个、新插入 4 个：

1
2
3
CASE index_lag_with_recheck               PASS pendingOutbox=14 merchant3: truth=1211 returned=1207 filteredStale=10 wrongRows=0 missingDueToLag=4(all newly inserted=true) merchant4: missingDueToLag=5
CASE negative_index_without_recheck       PASS expectWrongRows returned=1217 movedOrdersReturned=5 (rows whose merchant is now 4: 5) deletedOrdersReturned=5
CASE index_after_outbox_drain             PASS drained=14 merchant3 sameAsTruth=true filteredStale=0 merchant4 sameAsTruth=true

复核挡住了 10 个过期索引项，返回结果里没有一行不属于商户 3。复核挡不住的是遗漏：4 个新订单的索引项还没写入，商户 3 暂时查不到它们；5 个改到商户 4 的订单在商户 4 那里同样暂时查不到。去掉复核，同一时刻会返回 5 个已经属于商户 4 的订单和 5 个已删除订单的残影。发件箱消费完之后，两个商户的结果都与真值一致。

复核把索引方案的错误限定为一种：过期项可以被检测并丢弃，缺失项只能等待同步或修复。

修复任务

缺失项在读路径上无法察觉，需要独立的修复任务把分片数据与索引对账。Repair.run 按商户扫描三个分片的订单与索引库中的项，分出 missing（分片有、索引无或不符）与 stale（索引有、分片无或不符）。扫描与写入并发时，扫描结果可能已经过时，所以动手前对每个候选按 order_id 回分片点查一次，仍然成立才修正。对上面两个双写崩溃留下的漏项，再加一个绕过发件箱直接删除订单留下的过期项：

1
indexQueryMissing=2 filteredStale=1 repairDryRun=Result[shardRows=1185, indexEntries=1184, missing=2, stale=1, added=0, removed=0] repairApply=Result[..., missing=2, stale=1, added=2, removed=1] recheck=Result[shardRows=1185, indexEntries=1185, missing=0, stale=0, ...] afterRepairSameAsTruth=true

修复任务读全部相关数据，代价与分散-汇聚的一次全量翻页相当，适合低频运行或按商户触发，不适合放在每次查询的路径上。

两个方案的取舍

维度 分散-汇聚 全局索引 + 发件箱
每页语句数 分片数 1 次索引查询 + 本页涉及的分片数
每页取回行数 分片数 × pageSize pageSize（加上被复核丢弃的）
新鲜度 与分片同步 滞后于发件箱消费
错误形态 慢分片拖慢整页 过期项被复核过滤；缺失项要靠修复
额外状态 无 索引库、发件箱、维护器、修复任务
扇出 恒等于分片数 由数据分布决定，本实验平均每页 3.00

最后一行值得多看一眼：index_full_scan_m3 的 avgShardsPerPage=3.00。商户的订单按买家分片，同一商户在每个分片上都有订单，一页 50 行几乎必然覆盖全部 3 个分片。索引方案省掉的是“每个分片多取的行”和“不相关分片上的空查询”，在本数据分布下语句数并没有减少。如果商户的订单集中在少数分片，或者分片数远大于页大小，索引方案的扇出优势才会显现。分片数少、新鲜度要求高时，分散-汇聚的实现与运维成本都更低；分片数多、单页扇出成为瓶颈时，才值得承担索引的同步与修复成本。

用例与证据

用例 类别 观察值（evidence/22/output.txt）
scatter_full_scan 正常 1217 行，25 页，与真值逐行一致
scatter_duplicate_sort_values 边界 400 行同一时刻，13 个页边界落在重复值内，无重漏
negative_ts_only_cursor_* 负向对照 < 漏 364 行；<= 重复 37 行并停滞
keyset_concurrent_insert 并发 并发插入 34 行，可见 0 行，重复 0，遗漏 0
negative_offset_concurrent_insert 负向对照 重复 3 行，遗漏 1 行
fanout_and_size_budget / bad_cursor_rejected 拒绝 预算超限不发语句；游标商户不符被拒
shard_timeout_contract 失败 300ms 截止，322ms 返回超时；部分结果不签发游标
index_full_scan_m3 / _m7 正常 与真值一致，复核过滤 0
index_lag_with_recheck / 对照 失效索引 过滤 10 个过期项；不复核时返回 10 行错误订单
index_missing_found_by_repair 恢复 双写崩溃漏项 2 个、过期项 1 个，修复后一致
indexer_crash_replay_idempotent 恢复 维护器崩溃后重放 30 条，与真值一致

运行入口 examples/22-shard-query/run.sh，环境见 evidence/22/env.txt（PostgreSQL 16.15、OpenJDK 21.0.12.1、pgJDBC 42.7.4、4 核）。三个分片与索引库都在同一个 PostgreSQL 实例上，延迟数字不代表跨机器部署，本章也不以它们作性能结论。

结论边界

实验支持的结论：用唯一的 tie-breaker 构成全序、用行构造器比较实现 keyset 游标，分散-汇聚在重复排序值和并发插入下没有重复、没有遗漏存续行，晚到的行按排序键而非提交时刻决定是否出现；全局 OFFSET 与只按时间的游标在同样的条件下确实出错。扇出与行数预算可以在发出语句前执行；慢分片要么让整页失败，要么得到不签发游标的不完整结果。发件箱维护的全局索引配合读时复核，错误只剩可修复的遗漏，修复任务能发现并补齐它们。

实验不支持的说法：多个分片的结果来自同一时间点（没有跨分片快照）；索引在任何时刻都完整（发件箱只保证最终一致，滞后时间未测）；排序键可变时游标仍然稳定（本章排序键不可变）；多个索引维护器并发时的正确性（只以单个维护器运行）。

本章的分片映射是固定的。按 user_id 增加分片、把一部分桶搬到新分片时，订单要在两个库之间交接，正在写入的事务、迟到的写入和重试都要有确定的去处，这是下一篇 23 分片扩容时的数据交接 的内容。