TopK 这个词做算法、做数据、做后端的人应该都不陌生日志里抓前 100 个慢接口推荐召回阶段保前 50 个候选向量检索里取最近邻的 topK本质都是同一件事——在一批带分数的实体里把最高的 K 个找出来。单机跑的时候一次全排序或者一个最小堆就完了可数据一超过单机能力大家自然而然就会把数据切成若干份并行算于是问题就从“怎么取”变成了“怎么切”。切分粒度就是那个最容易被随手定下来却又在后面疯狂找补的变量。我的结论是切分粒度通常不改变 TopK 的期望误差总量但它会彻底改变误差在整条流水线里的分布。换句话说风险不会消失只会在“局部剪枝”“合并排重”“尾部延迟”这三个坑里重新排队。这篇文章就把这个“重新排队”的过程掰开讲清楚。1. 先对齐概念TopK 到底在怕哪几种风险1.1 全局 TopK 和分布式 TopK 的差别所谓全局 TopK指的是在一个完整集合里取分数最高的 K 个。分布式之后动作被拆成三个步骤把全集切成 n 份切分每个分区各自算一个局部 TopK得到一批“局部候选”把所有局部候选汇集到合并端再做一次 TopK输出全局结果。切分粒度指的就是这 n 份到底切成多少份、每份多大。它直接决定了第二步里“局部候选”有多少、质量如何也决定了第三步合并的压力。很多人以为这是一个“性能调优”问题改一改并行度而已。实际上它同时也是一个“正确性”问题只是问题藏在概率里不容易一眼看出来。1.2 我把 TopK 的风险分成了三类在分布式场景里讨论 TopK我最常用的框架是三类风险风险类型具体表现出问题的地方剪枝漏检某个真正应该进全局 TopK 的元素在局部阶段就被丢掉了局部 TopK 的候选名额太少重复虚增同一实体/同一条结果在多个分区被重复上报合并后候选数量虚高甚至污染最终排序分区方式与合并去重逻辑偏斜尾延迟某个分区数据特别大、分数特别卷导致整体作业等这一个分区切分方式与分区间负载差异这里的“风险分布”不是一句比喻而是字面意思同样一笔预算比如合并端只能接收 300 条候选粗粒度下尾巴上那几条被剪掉的概率更高细粒度下则是合并端看到的重复项更多尾延迟更像是从地上一团挪到天上散开。你控制住了其中一个另外两个多半会冒头。1.3 为什么“粒度”是那个最关键的自变量因为 TopK 的很多参数是固定的K 是业务给的数据量 N 是现状并行度受资源限制。唯一能灵活调、且影响所有下游的就是分区数量和分区方式。分区数量一旦变化每个分区的大小就变化局部 TopK 的“安全名额”也得跟着变化分区间数据分布也随之变化尾部延迟的方差和热点分区的概率都会变。这个变量是上游变量其余全是下游结果。所以去调什么堆大小、合并算法之前先把粒度看透了往往能省掉一大轮无意义优化。2. 粒度变粗变细三类风险是怎么重新配比的2.1 一个最朴素的数量关系假设全集 N 被切成 n 个分区每个分区选出自己的前 m_i 名合并端拿到的候选总数 C 就是C Σ m_i如果你图省事每个分区都固定取前 K 个m_i K那么候选数就是 nK。n 越大候选越多合并端排序越慢但每个分区几乎不会误伤全局 TopK——因为名额足够宽裕。如果你追求“合并端刚好只看到 K 个”让每个分区取 m_i K / n那么 C 合计还是 K。但问题来了全局 TopK 不是均匀分布在 n 个分区里的。极端情况下某个分区占了其中 80 个而它只被分到 3 个名额于是 77 个真 TopK 在第一步就被剪掉了。这个逻辑就是风险分布的第一层你省下的合并开销以漏检概率的形式转移到了局部剪枝阶段。2.2 一个启发式公式安全局部名额该设多少我用一个简化的随机模型来估算。把全局 TopK 想成 K 个独立个体均匀随机地落进 n 个分区。某个分区里会分到多少个全局 TopK 成员近似服从二项分布X_i ~ Binomial(K, 1/n)如果给这个分区分配的名额只有 m_i K/n那么只要 X_i 超过 K/n这个分区就必然漏检。X_i 的波动幅度大约是 sqrt(K/n)。换句话说如果想让漏检概率不随 n 升高每个分区的名额应该设为m_i ≈ K/n α * sqrt(K/n)这里 α 是安全系数取 2 到 3 比较常见。那么总量 C 就变成C ≈ K α * sqrt(K*n)这个公式说明了一件事粒度越细为了保证同样的安全水平合并候选的规模不是线性涨而是按 K*n 的平方根涨。所以细粒度不一定是坏事但它有明确代价而且这个代价不能靠“局部少算一点”来逃避。2.3 粗粒度、细粒度的风险特征对比粒度分区大小并行度局部名额不够时合并端状态典型风险很粗2~4 个分区很大低一旦剪错就是大范围误伤候选少、排得快热点分区慢整体等待漏检集中在少数分区中等8~64 个分区适中匹配资源剪错概率分散到每个分区边界候选量适中分布均衡但单分区偏斜仍会造成拉长很细几百上千分区很小高局部几乎保留大量数据漏检少候选量大、排重压力大合并去重逻辑复杂重复上报概率上升三段式概括粗粒度把风险压成少数几个“大雷”大部分分区没问题一个分区出问题就全盘拖垮细粒度把风险摊成大量“小雷”每个分区都很稳但雷的总数变多合并端要用更多资源去排。所谓最优粒度本质是选择一个你能接受的风险形态。2.4 极端数据分布下的隐蔽风险如果数据天然是偏斜的比如某个 key 的条目数占了总量的一半那按 key 哈希切分通常还能保持负载均衡但如果是按文件、按时间范围切分热点很容易集中到某一个分区。这时候有一个很反直觉的现象比分压根偏斜时粗粒度反而更不容易漏掉真 TopK。因为热点分区很大局部 TopK 的名额也往往给得够大热点高分区里的候选最终能进入合并端反而是细化粒度之后热点被打散成十几段每一个分区的局部名额看起来都不够覆盖它结果全局 TopK 里的强项反而被剪得七零八落。这就是“切分越细合并端数据越好看结果越不可信”的典型情况。所以在任何调优开始之前第一步永远是先判断高分组是密集分布在一个区域还是稀疏分布在全部数据里。这比讨论 n 取几重要得多。3. 把结论做成模拟实验分区数从 2 调到 64 会发生什么3.1 构造一个可控的偏斜数据集我会用一段很短的 Python 来观察不同粒度下局部 TopK 合并的结果。先构造一份数据大概是 100 万条记录少数 key 集中了大量高分记录其余 key 分数分散。import random import heapq from collections import Counter def gen_data(num_records, group_prob0.3): rng random.Random(2024) records [] for i in range(num_records): if rng.random() group_prob: key hot_group score 900 rng.random() * 100 else: key fnormal_{rng.randrange(2000)} score rng.random() * 1000 records.append((key, score, i)) return records def local_topk(records, m): return heapq.nlargest(m, records, keylambda x: x[1]) def distributed_topk(records, n, m): if n 0: return [] size (len(records) n - 1) // n candidates [] for i in range(n): part records[i * size : (i 1) * size] candidates.extend(local_topk(part, m)) return candidates def true_topk(records, k): return set(record[2] for record in heapq.nlargest(k, records, keylambda x: x[1]))核心逻辑很简单按顺序把记录切成 n 段每段取前 m 个合并后和真全局 Top100 做重合度对比。这里用的“按顺序切分”模拟的是按文件/按时间范围切分的糟糕情形热点很容易堆在某一段。3.2 固定局部名额和固定总候选两种玩法第一种玩法每个分区固定取前 20 个观察 n 从 2 变到 64 时Top100 召回率怎么变。结果大致如下分区数 n每个分区名额 m合并候选总数对全局 Top100 的召回情况22040严重不足热点分段只覆盖一部分召回率很低820160中等热点区多截了一截召回改善3220640召回接近完整但合并候选是 K 的 6.4 倍64201280召回几乎满分代价是合并端膨胀到 12.8 倍这个结果符合直觉局部名额不变切得越细数据被分得越碎越不容易把某个亮点整段剪掉召回越高。但合并端的压力线性上升这会变成新的延迟风险。第二种玩法总候选数固定为 300 左右也就是名额 m 300 / n看漏检怎么涨分区数 n每分区名额 m合并候选总数典型表现2150300每个分区名额很宽裕召回不错1619304有点危险热点分区可能不够用645320大量真 Top100 被剪在局部召回大幅下降这就是前面公式的直观体现想维持同样的召回风险总候选必须跟着 sqrt(K*n) 涨。否则你为了合并端省事而把粒度调细只会把风险提前释放到局部阶段。3.3 从模拟里能看到的三件事第一粒度本身没有好坏问题是你把风险放在了哪一层。固定总候选时细粒度必然漏检固定局部名额时细粒度的代价是合并膨胀。第二偏斜数据的杀伤力被切分方式放大。如果热点 key 只集中在一个分区粗粒度下它还能被完整保留一旦热点被切到很多分区局部名额不够反而被逐个剪碎。第三只看召回率会骗人。召回率提高不代表系统变好因为合并候选数大幅上升后排序耗时、网络传输、去重判断都会变长最后体现在端到端延迟上这是另一种风险。4. 真实系统里最常见的两个风险场景4.1 场景一按业务 key 做 TopK业务上经常要按某个 key 维度统计 TopK比如按接口名取耗时最高的请求、按用户取消费最大的订单。这类任务最常见的切分方式是按 key 哈希好处是同一个 key 一定落在同一个分区合并端不会出现重复 key。它的风险集中在偏斜极少数 key 的数据量特别大于是某个分区天然比别人慢一倍、两倍甚至十倍。如果为了加速把这个 key 再拆成多份让多个线程一起处理就得考虑同一个 key 的局部结果怎么安全合并。要么增量式地只保留当前 TopK要么在合并端做一次全局去重。这里有个很常见的错误合并端只做排序不去重同一个 key 在多个分区的重复结果都进最终榜单导致 TopK 变成“分散段 TopK”的并集顺序全乱。我处理过的一个实际案例就是这种。任务本来 30 秒能跑完后来数据涨了某个热点 key 占总量四成我把切分数从 16 调到 128结果任务反而更慢。原因是热点 key 被分散到 128 个分区每个分区都产生了它的局部记录合并端拿到两千多条结果去重逻辑当时还没做最终榜单出现了同一 key 的大量重复项。排查到头才发现这根本不是一个性能问题而是一个去重问题。4.2 场景二向量检索里的分桶 TopK向量检索里也有类似的“切分粒度”就是聚类中心数量 nlist。数据集被分成 nlist 个桶查询时先用更粗的方式锁定几个候选桶再在这些桶内做 TopK。这个 nlist 就是切分粒度而查询时实际搜索的桶数 nprobe 就是局部采样力度。nlist 太小每个桶太大查询时单桶内计算量高被锁定的桶里可能混入大量不相关向量topK 结果偏移nlist 很大每个桶太小候选桶数量不变时覆盖范围变窄真正的近邻可能不在搜索范围内。这里的风险分布和通用 TopK 完全一致桶数细了召回率不一定升因为 nprobe 没跟着涨nprobe 涨了计算量和延迟又上来了。对这种场景我的建议永远是先做召回率对 nlist/nprobe 的二维扫描再用“TopK 间隙”判断该不该继续加桶。如果第 K 名和第 3K 名之间的分数差距很小说明边界处候选非常多这时候细粒度分桶很容易把真正近邻剪掉就必须在合并端预留更大的候选余量。4.3 两类切分方式的风险差异小结切分方式会不会产生重复主要风险适用的数据特征按 key 哈希不会重复天然去重热点 key 偏斜导致的尾延迟key 丰富且相对均衡按范围/文件/时间同一逻辑实体可能落多段重复候选、跨段漏检无强 key 依赖、顺序数据按采样/随机打散实体可能跨分区合并去重必须做否则虚增需要极限均衡负载不要在选切分方式时只盯着“能不能跑满并行度”要先想清楚数据实体的边界在哪。实体的边界决定了重复风险是否存在重复风险一旦存在合并端就必须有幂等机制否则粒度再漂亮也是空中楼阁。5. 可落地的选型顺序从采样预判到动态回扩5.1 第一步给数据做一次轻量预检拿到一份要做 TopK 的数据我从不直接定分区数。先抽一个 1% 到 5% 的样本在单机上跑一次近似 TopK然后看两件事。第一件事是 TopK 聚集度把样本里的 TopK 按 key 或者按区间做分组看高分组是来自少数几个区域还是均匀散布。第二件事是 TopK 间隙看第 K 名和第几 K 名之间的分数差。间隙大说明边界清晰局部剪枝对最终结果的影响很小间隙小说明大量元素分数接近任何剪枝动作都可能把正确结果推出去。这个预检不复杂也不会花多少资源但它能直接告诉你该往哪个方向选粒度。间隙大的项目可以放心地把局部名额压到接近 K/n间隙小的项目建议直接给局部名额翻倍甚至按 K 取。5.2 第二步按并行度和资源反推 n分区数 n 不是越大越好而是约等于你实际能同时跑的并发度。如果你有 32 个执行槽那就把 n 定在 32 附近不要为了“看起来并行度高”切成 1024。因为 TopK 这种任务是“先发散再收敛”的发散得越狠收敛就越贵。那些被切出来的 1024 个分区最后都要在合并端挨个处理。你真正需要的是每个分区都有活干、每个分区干得差不多快而不是分区分得多。有一个朴素有效的经验n 取 1.5 到 2 倍的执行槽。这样即便某个槽挂了还有冗余分区可以重新调度同时合并端的候选规模也不至于爆炸。如果执行槽是 32n 取 48 到 64 通常是个不错的起点。5.3 第三步给每个分区一个“安全局部名额”别用死公式用我前面那个带安全系数的思路m_i K / n 2 * sqrt(K / n)如果 K100n32那么 m_i ≈ 3.125 2 * 1.77 ≈ 6.6取整到 7 或 8 比较合适。合并端的候选总量大约是 224 到 256比“每个分区都取 100”的 3200 要小一个数量级安全性却并不差多少。担心热点极端集中就把安全系数提到 3也就是m_i ≈ K / n 3 * sqrt(K / n)再往上加就不太值了因为收益曲线会变平。从 2 提到 3候选量只增加不到一倍从 3 提到 5候选量接近翻倍但漏检概率的下降已经微乎其微。5.4 第四步合并端做一次主动回扩这是很多人忽略的兜底手段。合并端在拿到所有局部候选之后先算出一个临时 TopK记录下第 K 名的分数 threshold。然后把它广播回各分区让各分区自查一下自己局部第 m_i 名的分数和 threshold 差多少。如果差得很近说明这个分区的剪枝边界正好压在全局边界附近很可能有被误剪的元素。此时再让这些分区把自己的候选名单回扩到 2 倍或者 3 倍做一轮二次合并。这种方式比一开始就把所有局部名额调到很大要聪明得多。它把风险像一个仪表盘一样显示给了你哪些分区需要回扩、回扩多少、有多少元素贴近边界全部可观测。整个过程有点像查漏而不是蒙眼调参。5.5 优先级清单经验里我会按这个顺序做检查而不是一开始就去调堆大小或排序算法数据抽样预检确认 TopK 聚集度和间隙确定执行槽数量选定分区数 n给局部名额加安全系数算出候选总量合并端提供去重能力尤其是多段可重复实体增加回扩机制用边界分数驱动二次补齐。很多看起来是“粒度没选好”的问题追到根上其实是第二步和第三步没做。粒度只是被甩锅的那个变量。6. 实际项目里值得记住的三件事6.1 不要用“一次全排序”替代“局部 TopK 合并”数据一多有人为了保精度把每个分区的局部结果全量上传到合并端做全排序。这样做的确不会剪枝漏检因为压根没有剪枝。但这等于把切分粒度变成了“只做 IO 调度不做计算收敛”合并端的传输量和排序量全部失控最终端到端延迟一定是最差的那一个。正确思路是接受“近似 TopK”的语义把局部名额当成一个可控缓冲而不是默认全量。先保证不漏再逐步收紧名额。这也是分布式 TopK 和单机 TopK 最大的区别单机你只需要对得准分布式你还要对得快。6.2 合并端一定要把“幂等”写死我踩过最深的一个坑就是重复候选把真实 TopK 的顺序彻底污染。某个 key 因为是热点被分到 20 个分区每个分区的局部候选里都带着它。合并端如果只是按分数排序这个 key 会重复出现 20 次看起来榜单被它占满其实是假象。从那以后我在所有分布式 TopK 的合并端都强制加一层身份去重。去重字段最好选业务唯一标识不要用分数去重因为分数完全可能相等。这一步不能省不管粒度怎么选去重逻辑永远要是幂等的。6.3 小技巧把“边界名次分数”做成监控指标最后分享一个我很受用的操作把每一轮 TopK 的“第 K 名分数”“第 2K 名分数”“局部名额边界分数”三个指标打进监控系统。看这三个指标之间的差值变化就能判断当前粒度的安全性。如果第 K 名和第 2K 名分数非常接近说明边界很拥挤当前安全系数可能不够要自动调大局部名额。如果差距很大说明边界很清晰可以把安全系数降下来省资源。这个监控指标比看什么 CPU、内存都管用因为它直接衡量的是 TopK 结果的稳定性。切分粒度不是一个一劳永逸的参数它是随着数据分布漂移而需要持续校准的变量。每次数据量变化、数据分布变化旧的安全系数就不再安全。把这套预检、安全系数、回扩、监控的流程固定下来比你反复试 n 要可靠得多。