树状数组+区间贪心+并行归约：库存批处理性能优化实战

execution并行归约、区间贪心、树状数组，这三样东西单独拿出来都不算冷门，但放在同一个项目里，意味着你遇到的一定是那种“数据量很大、执行窗口很短”的批处理场景。我最近在重构一个库存调度服务时，把这三者硬生生凑到了一起，踩了一整圈的坑。先说结论：树状数组负责高效维护前缀信息，区间贪心负责把复杂选择变成线性扫描，并行归约负责把单机单线程的瓶颈彻底打散。哪一个环节没想清楚，线上就会给你表演execution terminated due to error。

整套方案落地之后，原先需要跑一个多小时的任务被压到了十分钟以内，而且是在没换机器、没加内存的前提下做到的。这篇文章就是整个优化过程的复盘。我尽量把每一步的“为什么”讲清楚，而不是只丢一段代码让你抄。毕竟我踩过最深的坑，就是那些看起来没有理由却跑不通的边界情况。

1. 场景代入：一次被数据逼疯后的优化复盘

1.1 为什么是树状数组

先交代背景。我手上的服务维护着一张 SKU 维度的库存序列，序列长度大约在百万级。外部业务方会频繁做两类操作：一是对某个 SKU 的库存做单点修改，二是查询某个编号区间内的前缀统计值，比如“编号 1 到 100000 的 SKU 库存总和是多少”。这类操作的请求量在白天并不夸张，真正吓人的是每天凌晨的批处理任务，一上来就是千万级的修改和千万级的查询，还会叠加一批库存调拨的区间覆盖判断。

我当时第一个想到的数据结构就是树状数组，也就是 BIT（Binary Indexed Tree）。为什么不用线段树？因为这里只涉及单点加和前缀查询，线段树能做的事树状数组都能做，而且 BIT 的代码量少、常数小、内存占用只有线段树的四分之一。在百万级序列、千万级请求面前，这差距是实打实的。更关键的是，后续做并行归约时，BIT 因为本身结构简单，复制、合并、缓存友好度都明显好于二叉树式的线段树。

如果你对树状数组还不熟，可以把它想象成一种“分块前缀表”：它把数组拆成很多个以 lowbit 为大小的逻辑块，每个下标 i 维护原数组 (i - lowbit(i), i] 这一段的和。这样一来，查询前缀和的时候不是一路累加到底，而是沿着 lowbit 跳着合并，单次复杂度 O(log n)。修改某个点时，也只需要向上更新被影响的块，同样是 O(log n)。

1.2 区间贪心在哪一步出现

业务里有一类调拨需求：给定若干个候选区间，每个区间表示“从 A 点到 B 点的一批货物可以覆盖的 SKU 编号范围”，然后要求用最少的区间把整个目标区间 [L, R] 完整覆盖住。这个问题的经典解法就是区间贪心。

贪心策略很简单：先把所有区间按照左端点排序，然后从左到右扫描，每次在“左端点不大于当前覆盖边界”的所有区间里，选择右端点最远的那个区间，把它纳入方案，然后更新覆盖边界。具体到代码上，排序之后每次要做一件事：找出满足条件的区间集合里右端点最大的值。如果每次都用循环找，最坏情况是 O(n²)，在百万级区间前完全不可用。

这时候树状数组又该上场了。我们把每个候选区间的右端点按照其左端点分组，用 BIT 维护“以某个位置为左端点的区间最大右端点”。这样一来，在贪心扫描时，就可以通过 BIT 查询“前缀区间内的最大值”，把每次决策从线性扫描降成 O(log n)。BIT 通常用来维护求和，其实维护最大值只要改一下内部逻辑，把加和变成取 max，原理是一样的。

1.3 并行归约是被逼出来的

单机单线程跑完这批任务大约需要七十分钟。这个数字其实没有超出业务忍耐极限，但问题是白天会有别的在线请求进来，既不能锁表也不能占满 CPU。于是只能想办法把任务在限定的时间内跑完，给在线服务留出资源。

第一反应自然是改并行。把请求拆成多个分片，分给多个执行线程，最后把结果汇总。听起来很简单，但真的做起来之后，各种毛病层出不穷。最典型的就是多个线程同时操作同一个全局 BIT 导致数据错乱，以及一个 executor 抛错之后，整个任务被标记为“execution terminated due to error”，后续所有分片的结果全部作废。这些坑让我意识到，盲目开线程不是并行，只是把串行 bug 放大成并发 bug。这也是为什么我会专门用一整节来聊并行归约的设计。

2. 树状数组与区间贪心的基础实现

2.1 先放一份最小可用模板

树状数组的核心操作只有两个：单点修改和前缀查询。我习惯用 Python 写原型，Java 或 C++ 实现也几乎等价。以下是最简单的模板，维护长度 n 的序列，下标从 1 开始。

class BIT: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def add(self, i, x): # 单点修改：a[i] += x while i <= self.n: self.tree[i] += x i += i & -i def sum(self, i): # 前缀和：返回 a[1] + ... + a[i] s = 0 while i > 0: s += self.tree[i] i -= i & -i return s

这里i & -i就是 lowbit 运算，表示 i 的二进制里最低位的 1 所代表的数值。add操作会向上跳，sum操作会向左跳。注意 BIT 的数组要多开一位，因为下标从 1 开始，不然 lowbit 会在 i=0 时死循环。网上关于 BIT 的模板很多，但下标这个东西写错一次就能让你排查两小时，我自己就吃过这个亏。

如果你要维护的是区间最大值，只需要把tree[i] += x改成tree[i] = max(tree[i], x)，把sum里的累加改成取 max。其余逻辑几乎不用动。这是 BIT 很划算的一点：只要需求满足“可合并性”，它就能适配。

2.2 拿 n=16 的序列手推 sum(11) 和 add(3, x)

理论说完了，我们来点实的。假设维护一个长度为 16 的序列，初始全是 0。现在执行add(3, x)，也就是给第三个位置加上 x。流程如下：

• i=3，更新 tree[3]，i 变成 3 + lowbit(3)=3+1=4
• i=4，更新 tree[4]，i 变成 4 + lowbit(4)=4+4=8
• i=8，更新 tree[8]，i 变成 8 + lowbit(8)=8+8=16
• i=16，更新 tree[16]，i 变成 16 + lowbit(16)=16+16=32，超过 n，停止

注意这里 tree[4] 会更新两次吗？实际上不会。第一次更新 tree[3] 是因为 lowbit(3)=1，说明 tree[3] 只管原数组第 3 个位置这一个点。紧接着更新 tree[4]，是因为 lowbit(4)=4，tree[4] 管的是原数组 (4-4, 4] 这个区间，也就是第 1 到 4 个位置。一次 add 操作确实会重复访问一些祖先节点，但每层最多访问一个节点，所以总次数就是 log n，我是为了强调流程才把 tree[4] 单独列出来。

再看sum(11)。查询前缀和时，逻辑是逆着 lowbit 走：

• i=11，累加 tree[11]，i 变成 11 - lowbit(11)=11-1=10
• i=10，累加 tree[10]，i 变成 10 - lowbit(10)=10-2=8
• i=8，累加 tree[8]，i 变成 8 - lowbit(8)=8-8=0

所以sum(11)的返回值是 tree[11] + tree[10] + tree[8]。这三段刚好覆盖了原数组 1 到 11 的所有位置：tree[11] 管着第 11 个点，tree[10] 管着第 9、10 两个点，tree[8] 管着第 1 到 8 个点。合并起来就是 1 到 11 的完整前缀。

这就是 BIT 的核心美感：查询时不需要遍历所有位置，只需要顺着二进制的 lowbit 链把不重叠的块拼起来。理解了这个手推过程，写别的变形就不会再心里发虚。

2.3 区间贪心如何靠 BIT 加速

回到区间覆盖问题。假设目标覆盖区间是 [8, 30]，候选区间集合有一大堆。贪心扫描的每一步都希望找到“当前覆盖边界 cur 右侧最远的右端点”。传统做法是扫描所有左端点 <= cur 的区间，逐个比较右端点。候选区间数量一旦到了百万级，每次扫描都会爆炸。

改进做法是：先按左端点把所有区间分组，把每个分组的最大右端点作为“这个左端点对应的价值”，存入 BIT 用于支持“前缀最大值查询”。当 cur 固定时，我们一次性查询 BIT 在左端点不超过 cur 的范围内的最大右端点。这个查询本质上是BIT.query(cur)，也就是对左端点这个维度做前缀 max 查询。到这里，普通 BIT 的“前缀和”就变成了“前缀极值”，但数据结构本身的结构完全没变。

实际操作时有一个边界陷阱：如果当前查询出的最大右端点没有大于 cur，那就说明没有任何候选区间能继续延伸，覆盖失败。这个失败要尽早判断，不然会进入死循环。我专门写了一个哨兵区间，右端点用负数兜底，这样BIT.query返回负数时就知道无解了。

整个贪心过程从“排序后反复扫描区间集”变成“排序一次 + 每个决策一次 O(log n) 查询”，复杂度从 O(n²) 降到 O(n log n)。在数据量大时，这个降幅是致命的。

3. 并行归约架构设计

3.1 请求分流与任务切分

并行执行不是把整个任务简单切几刀就行，而是要先分清请求类型。在我这个场景里，请求分为两类：写请求（单点修改库存）和读请求（前缀查询、区间覆盖判断）。写请求之间是有依赖的，必须先应用到一个版本的数据上，后续查询才能看到正确结果；而读请求之间彼此独立，天然可以并行。

我的方案是两阶段执行：

• 第一阶段只处理写请求。把所有写请求按 SKU 编号分片，每个线程负责一个编号区间内的所有写操作。各线程在本地构建一份 BIT，只维护自己分片内的数据。
• 第二阶段处理读请求。把读请求也按 SKU 编号分片，每个线程读取第一阶段汇合好的全局 BIT，执行前缀查询和区间贪心的 BIT 查询，最后把结果按请求 ID 归约到一起。

这里的关键是“局部 BIT + 全局归约”而非“全局共享 BIT”。如果所有线程直接操作同一个 BIT，那么add和sum之间会疯狂竞争，临界区乱成一锅粥。更糟的是，有些 BIT 操作不是原子的，两个线程同时对同一个 tree[i] 做加法，结果会丢更新。

所以我把“并行归约”中的“归约”真正用在结果层面：每个线程输出自己的局部结果数组，最后通过归约合并。对于只需要一组最终 BIT 的场景，第一阶段可以进一步细分为先并行生成各分片 BIT，再按位相加得到完整 BIT。这其实就是一次标准的 reduce 操作，和 MapReduce 里的 reduce 是一个思路。

3.2 归约顺序与复杂度：不是所有加法都能并行

先算复杂度。假设序列长度 n=1,000,000，写请求数量 W=10,000,000，读请求数量 R=20,000,000，线程/任务数 P=16。

第一阶段：每个分片的写请求数约为 W/P，每个写请求更新 BIT 的代价是 O(log n)，所以单线程处理自己分片的代价是 (W/P) * log n。P 个线程并行，第一阶段耗时约 (W log n) / P。

第二阶段：读请求同理，每个查询为 O(log n)，总代价约 (R log n) / P。

如果共享一个全局 BIT，第一阶段因为竞争，实际耗时不是总耗时除以 P，而可能接近串行耗时甚至更慢。这就像一群人同时改同一份表格，每个人的动作都在等别人松手。局部归约则不同，每个线程各写各的草稿纸，最后把草稿纸加总。代价差异天壤之别。

但归约本身也有坑：当 P 个局部数组相加时，如果直接逐位相加，复杂度是 O(P*n)，也就是 16 * 1,000,000，这非常高。更好的办法是分治归约：两两相加，每层复杂度 O(n)，总共 log P 层，复杂度 O(n log P)。这个优化在 n 百万、P 十六时或许还能接受，但其实现场我连 O(n log P) 都嫌贵，所以我把第二阶段设计成只读查询，根本不需要合并完整 BIT。

具体做法是：第一阶段每个线程完成自己的分片后，把分片结果保留在内存里；第二阶段每个查询请求被路由到所有相关分片，分别查询局部 BIT，再把多个局部结果相加。这种方式把归约从“数据层面”下沉到“查询结果层面”，既避开全局 BIT 的锁竞争，又避开了 O(n log P) 的合并开销。查询延迟从原来的 log n 变成了“分片数量 * log(分片大小)”。当分片数量控制在 4 到 8 时，这个常数很小。

3.3 线程数与调度：16 个线程不一定比 8 个快

并行执行最迷惑人的一点就是：线程越多越快，实际上不是。我在压测时观察到，线程数从 1 调到 8，耗时从 70 分钟降到 12 分钟，很理想；再调到 16，耗时只降到了 11 分钟，几乎没变；调到 32，耗时反而回升到了 13 分钟。

原因主要有三个。第一，CPU 核数有限，超过物理核数后线程切换的成本就开始吃收益。第二，内存带宽有限，BIT 的随机访问特性会迅速吃掉缓存和内存带宽，线程之间开始互相抢带宽。第三，垃圾回收线程和系统调度也会争夺资源。

在那台 16 核的机器上，我最终选定的并行度是 12。这是一组经过压测的数字，不是拍脑袋定的。调整时不要拍脑袋，要盯着 CPU 使用率、平均延迟、以及 GC 时间三个指标一起看。如果 CPU 使用率已经接近 100% 但耗时没有显著下降，说明瓶颈已经转移到了内存访问，而不是计算能力。

4. 实操中的典型错误与排查实录

4.1 并行归约结果不一致：第一现场

第一次改造完，我信心满满地跑了一遍小数据验证，结果发现同样的输入在不同线程数下居然会得出不同的结果。第一反应是“并行有 bug”，于是把线程数降到 1，结果又对了。这种问题十有八九是共享状态出了岔子。

排查过程很朴素：把所有线程的局部结果单独 dump 下来，逐个对比。最后发现是一个很隐蔽的问题：在第一阶段构建局部 BIT 时，我用的是同一个 BIT 对象的“浅拷贝”，线程之间共享了底层数组。这样一来，表面上各个线程在修改自己的分片，实际上大家都在动同一块内存，一旦发生add操作，别人已经写入的 tree[i] 就会被覆盖。

修法也简单：每个线程用copy.deepcopy或者直接 new 一个全新的 BIT 实例。这个错误听起来像新手才会犯，但在重构老系统时，很容易因为“省内存”这种念头把浅拷贝带进来。我的教训是：并行归约的第一性原理就是“分而治之，最后合并”，这个“分”必须是数据层级的完全隔离，共享任何可变状态都是在给未来埋雷。

4.2 “execution terminated due to error”：排查实录

线上环境出现得最频繁的一行日志是：

execution terminated due to error.

这个日志本身非常没营养，不会告诉你具体哪个 executor 出了什么问题，也不会告诉你错误发生在哪个阶段。我一开始以为是框架的通用报错，没有任何价值，后来才发现它的价值在于“触发它之前的那条日志才是关键”。

那一次的情况是：任务执行到 1/3 的时候，某个执行线程在查询时抛了一个ArrayIndexOutOfBoundsException，异常被框架捕获后直接吞掉，最终把整批任务标记成了终止态。排查过程持续了几个小时，最终我看了一眼线程栈和局部 BIT 的边界参数，发现问题出在“请求被路由到与自己编号不相邻的分片”上。简单说，就是分区键不一致，导致某个请求访问了一个比自己维护区间大得多的下标，BIT 数组访问越界。

修复方法是：在构建请求路由表时，统一使用skuId的高位哈希作为分片键，而不是一部分地方用skuId本身、另一部分地方用skuId % P。任何拆分区规则一旦不统一，边缘数据就会乱跑。更稳妥的做法是在 BIT 的add和sum方法入口处加一个断言，检查下标是否在[1, n]范围内。生产环境下断言会消耗一点点性能，但在批处理任务里换来的是“执行错误不再神秘”，非常值得。

4.3 别忽略秘密字符串与隐式类型转换

排查时我还遇到过一条看起来完全无关的错误：

attempt to perform string conversion on a secret string value

这条错误出现得特别诡异，因为我压根没打算把什么秘密字符串转成字符串。后来发现是框架里的日志打印逻辑，在记录某个请求参数时隐式调用了变量的toString()方法，而那个对象被标记为“secret”类型，禁止序列化。这种失败在串行环境下几乎不会触发，因为日志打印频率低；一旦并行线程多了，日志系统会同步输出大量上下文，反而把异常暴露出来。

处理方式很简单：调整日志插件配置，对敏感字段做白名单过滤，禁止全量打印请求体。同时在代码里明确避免把任何敏感对象隐式拼接到日志中。这个问题的教训是：并行任务的报错往往不是计算逻辑本身的问题，而是日志、序列化、资源隔离这些“外围设施”被放大了。排查时要同时关注框架日志和业务日志的上下文，不要只盯着显式的错误信息。

4.4 经验速查表

5. 最终方案与避坑小结

5.1 我最终采用的成熟方案

最后落地的方案可以概括成“读归约 + 写分片 + 贪心检索”。

写请求的处理是：先把所有写请求按 SKU 编号范围分成若干个分区，每个分区由一个独立线程构建局部 BIT，完成后不合并，只保留各自的分片结果。读请求的处理是：每个查询请求根据需要访问相关分片，分别查询局部 BIT，再相加得到前缀和。这样既绕开了全局锁，又把组合成本控制在了一个很小的常数范围内。

区间贪心的部分，我把候选区间按左端点建好索引，每个索引维护到 BIT 中。贪心决策时，先用 BIT 查询当前覆盖范围前缀的最大右端点，若无法推进则提前终止。这个交互逻辑最终融入到了读请求的并行处理里，所以整体流程仍然是“并行归约框架 + BIT 数据结构 + 贪心策略”，三者各司其职。

这套方案上线后，批处理耗时从七十分钟压到了十一分钟，而且是在不加班、不动集群的情况下完成的。对我个人而言，最大收获不是那五倍的性能提升，而是对“并行执行”这件事有了更深的敬畏：任何一处共享的、可变的、非原子的东西，都会在并发放大镜下变成灾难。

5.2 几个容易翻车的细节

• 树状数组下标一定要从 1 开始，0 会死循环；初始化数组长度至少 n+1，很多越界错误都是从这里来的。
• 贪心覆盖问题里，千万别忘记“当前最大右端点没有超过当前边界”这一无解分支，否则会一直用同一个区间无限循环。
• 并行任务数量不要直接等于 CPU 核心数，要做梯度压测。我这里的经验是核心数减 4 往往能用满而未饱和。
• 归约结果时，加法运算符不一定满足结合律？如果数值很大，浮点误差会受线程数影响。整数场景没这个问题，但如果是浮点前缀和，最终结果在不同并行度下可能会有微小差异。若业务要求确定唯一结果，建议改用定点数或统一固定归约顺序。
• 日志打印一定要谨慎。任何自定义对象都可能被日志框架隐式调用 toString，尤其在并行环境下，这种隐式调用频率会突然上升，暴露出来的问题也千奇百怪。

说起来有点讽刺，最初只是想把一个线程改成一堆线程，结果最后真正让我学到最多的，全是那些“看起来和并行无关”的周边问题。如果你正准备做类似的优化，我真心建议在动手前先看完这三个东西：数据是否已经隔离、请求路由规则是否统一、日志链路是否会隐式打敏感数据。整明白这三条，你的并行归约大概率能少走两周弯路。

最后再分享一个小技巧：上线前把“线程数从 1 到最大物理核数”的所有档位都跑一遍回归，记录每个档位的结果和耗时。结果对比只做一次，但那次对比能帮你确认两件事——第一，你的归约逻辑是否在任意并行度下都产生同样的输出；第二，你的最优并行度到底是多少。这两个答案，比任何网上看到的“线程数设置为 CPU 数”的经验都可靠。实测下来很稳，建议你也试试。