一个交集，三种写法：分片缺失交易查询的三版演进

分片存储里有个高频小需求：把一批交易 ID 发到每个分片去查，每个分片只能回答"我这里没有哪些"；而业务要的是"所有分片都没有"的交易。

一句话点破：这是求交集，missing = shard1.missing ∩ shard2.missing ∩ shard3.missing。需求不难，难的是写得让人一眼看懂——同一个需求先后写了三版，回头看算的是同一件事，表达方式却差了十万八千里。

这篇用同一个单测例子，把三版拆开对齐，最后算一笔效率账。

问题：三个分片都说"我没有"

入参 txIds = [tx1, tx2, tx3]，三个分片各自返回"本分片缺失"：

正确答案只有一个：missing = [tx3]——只有它，一个分片都没命中过。

注意一个前提：每个分片的缺失表必然是 txIds 的子集，因为查的本来就是这批 ID。所以最终结果不需要再和 txIds 求交，三张缺失表的交集就是答案。

第一版：从候选集里划掉"被找到的"

思路最直觉：初始认为全都缺失，逐个分片过，凡是这个分片找到了的，就从候选集里删掉。

// 候选集：初始假设全部缺失
missingSet := make(map[string]struct{}, len(txIds))
for _, id := range txIds {
    missingSet[id] = struct{}{}
}

for _, shardMissing := range shardMissings {
    // 索引表：shardMissing 是切片，判断"在不在"是 O(n)，先转 map 才有 O(1)
    shardMissingSet := make(map[string]struct{}, len(shardMissing))
    for _, id := range shardMissing {
        shardMissingSet[id] = struct{}{}
    }
    for id := range missingSet {
        if _, ok := shardMissingSet[id]; !ok { // (1)!
            delete(missingSet, id)
        }
    }
}

1. 不在本分片缺失表里，说明这个分片**找到了**它 → 从候选集划掉。

跑一遍：

{tx3}，结果对。但这版多了一张 shardMissingSet 索引表——它不参与业务语义，纯粹是把切片查询从 O(n) 压到 O(1) 的性能配件。读代码的人会在这儿卡一下：这 map 是干嘛的？

第二版：重建集合，只留"两边都缺"的

第二版换了姿势：不删了，每轮**新建**一个集合，只把符合条件的搬过去。

missingSet := make(map[string]struct{}, len(txIds))
for _, id := range txIds {
    missingSet[id] = struct{}{}
}

for _, shardMissing := range shardMissings {
    nextMissingSet := make(map[string]struct{}) // (1)!
    for _, id := range shardMissing {
        if _, ok := missingSet[id]; ok { // 之前的分片也没找到它
            nextMissingSet[id] = struct{}{}
        }
    }
    missingSet = nextMissingSet // (2)!
}

1. 每轮新建一个集合，只把"本分片缺失 ∩ 当前候选集"的搬进去。
2. 用新集合整体替换旧集合。

跑一遍：

{tx3}，结果也对。这版的实质是**求交集**：候选集 ∩ 本分片缺失，而且不需要 shardMissingSet 索引表——因为遍历的就是 shardMissing 本身。

但"新建 + 替换"这个动作让代码读起来发绕：missingSet = nextMissingSet 藏在循环体末尾，意图不会自己说话，review 时在这儿停了半天。

第三版：不维护集合，只数次数

第三版彻底放弃集合运算，只记一件事：每个 id 被几个分片"说过缺失"。说过缺失的次数等于分片数，才算真缺失。

shardCnt := len(shardMissings)

// 计数表：每个 id 被几个分片"说过缺失"
missingCount := make(map[string]int)
for _, shardMissing := range shardMissings {
    for _, id := range shardMissing {
        missingCount[id]++
    }
}

// 一次性判定 + 遍历入参
missing := make([]string, 0, len(txIds))
seen := make(map[string]struct{}, len(txIds))
for _, id := range txIds {
    if _, dup := seen[id]; dup {
        continue
    }
    seen[id] = struct{}{}
    if missingCount[id] == shardCnt { // (1)!
        missing = append(missing, id)
    }
}

1. 被所有分片都说过缺失 ⇔ 次数等于分片数，语义一行说清。

跑一遍（shardCnt = 3）：

[tx3]，结果一致。

三版对照

三版算的是**同一件事**，结果完全一致，差别只在表达方式：前两版做的是"集合的增删"，计数法是"计数再一次性判定"。

最后留在代码里的是计数法，理由有五个：

• 不维护集合状态、没有中途替换，循环里只剩一个动作——计数
• 判定条件 count == shardCnt 自带语义："所有分片都没有它"
• 最终过滤遍历的是入参 txIds，输出顺序即入参顺序，seen 顺手把去重也做了
• map 只当 counter 用，不承载集合运算，职责单一
• 效率也是三版里最好的——零 per-shard 分配，下面算账

一个前提要留意：计数法默认每个分片的缺失表内部没有重复 id（同一分片里同一笔交易只报一次缺失），否则 count 会虚增，可能把"全缺失"误判成"部分命中"。分片侧保证去重，或者先对每张缺失表去重，都可以。

效率账：微秒级差异，毫秒级瓶颈

语义都对，效率呢？设每批查询 n 个 txIds（去重后 m 个）、分片数 N、第 i 个分片返回的本分片缺失数为 K_i，四版的开销摆在一起：

表格第一行还留了个"并集版"——那是被毙掉的最初版：任一分片说缺就进结果，把"所有分片都没有"算成了"有一个没有"，语义错得干脆。它的效率数字反而最好看，但**语义错的代码跑得再快也没有意义**，留在表里纯属反面教材。

正确三版的差异从哪来：

• 删除法每轮干两件事：先给本分片缺失列表建索引表 O(K_i)，再遍历候选集逐个判断 O(|候选集|)——多了半趟遍历
• 重建法每轮只扫本分片缺失列表，时间上最省，但每轮新建一个 map、丢掉上一轮的，攒下 N-1 个待回收的 map
• 计数法每轮只做 missingCount[id]++，一次分配都不产生，整个函数只有开头一个 map，收尾一次 O(n) 过滤

所以时间三版同为 O(ΣK_i)，但计数法没有 per-shard 分配，GC 压力最小；代价只是 map 的 value 从 struct{} 换成 int——每个 entry 多 8 字节，可忽略。

真正的瓶颈不在集合运算

三种写法跑一轮的差异是**微秒级**，而每个分片要发一次 gRPC 往返——毫秒级。真正决定耗时的不是这几版写法，而是两个结构性因素：

1. 分片数 N。forEachChainClient 串行遍历，N 次 RPC 是串行叠加的。N 上到几十个分片，把各分片查询并发化（sync.WaitGroup + 结果聚合）才是数量级上的优化；代价是要想清楚"某分片失败时怎么办"——当前语义是任一分片失败即整体报错，并发化后不能退化为返回部分结果。
2. txIds 的规模 m。底层一次 RPC 传全部 txIds，m 很大时会撞 gRPC 消息大小上限，需要分批。

一句话：单次查询、m 不大的常规场景，现在的计数法就是最合适的——可读性和效率都是三版里最好的；只有 N 或 m 明显变大时，才轮到并发化、分批这类结构性优化上场。

小结

需求没变、答案没变，三版代码从"划掉""重建"走到"计数"，可读性一路走高，效率也顺带到了最优——虽然这函数真正的时间，都花在等分片 RPC 回来的路上。

回头看，绕的根源不在算法，而在**表达方式离业务语义的距离**：求交集这件事，"每个分片说一次缺，说满 N 次就是真缺"是最贴近人话的一种。

下次写出一段"看着有点绕"的代码，别急着调格式——先问一句：这段代码想表达的语义，一句话能说清吗？说不清，多半是数据结构在替你表达，而不是逻辑本身。

知识库沉淀：多分片求交集：缺失交易查询的三种实现

最后更新：2026-09-29

评论