Fork/Join并发框架：分治算法与工作窃取实战解析

1. 先搞清楚Fork/Join到底在解决什么问题

1.1 分治思想：从“一个人干不完”说起

Fork/Join这个名字，我最早在Java 7的并发工具包里见到时，第一反应是“名字起得真直白”——Fork就是分叉，Join就是合并。说白了，它就是两大思想组成的框架：分治算法加工作窃取调度。分治这块，你小学就学过：把一个大问题拆成若干个小问题，小问题解决了，大问题也就解决了。比如你要算一万个数的总和，最直觉的方式是写个for循环从头加到尾；但如果有四个线程，完全可以切成四段，每段两千五，各算各的，最后再把四段结果加起来。

但分治思想本身并不新鲜，几十年前就有了，经典归并排序就是这种思路。Fork/Join真正值得聊的，是它怎么处理“拆了任务之后谁来执行、执行完怎么拼回来”的编排问题。Java里实现一个分治模型，用普通的ExecutorService加Future也能做：每次递归拆分任务，用线程池submit，再get结果。但你会发现坑很多：任务拆得多了，每个Future都要占内存，线程切换频繁，而且大任务依赖小任务的结果，容易形成层层阻塞，跑起来又慢又耗资源。

Fork/Join之所以能成为专门框架，核心在于两件事：它用双端队列管理每个线程的任务，允许线程从别人的队列尾部"偷"任务来干，也就是所谓的工作窃取（Work-Stealing）；它提供了完整的任务状态管理机制，任务被Fork出去之后，随时可以Join回来，状态通知、异常传播都不需要你操心。这套组合拳，恰恰是并发分治场景里最容易踩坑的地方，Fork/Join直接用框架帮你挡住了。

1.2 工作窃取算法：为什么它是Fork/Join的灵魂

我一直觉得，工作窃取是Fork/Join的精髓。它解决的是一个在并行分治场景里非常实际的问题：任务拆得不均匀怎么办？比如某个递归分支跑得快，某个分支跑得慢；或者某个任务本身比较大，拆开之后两边规模差很多。如果固定把任务分给几个线程执行，快的线程只能闲着等慢的，并行度空有一半，性能还是上不去。

工作窃取的思路是：**给每个工作线程维护一个双端队列，自己负责从队头取任务执行，别人执行完自己队列里的活之后，没活干就去别的线程的队列尾部偷一个任务来跑。**这样空闲线程不会干等，负载天然就均衡了。这就好比一条流水线四条工位，左边工位干完自己的活儿了，不等着下班，而是从右边工位堆叠的半成品里拿点来一起做，整体效率一下就拉上去了。而且从队尾偷、从队头取，两个线程操作同一队列的两端，冲突概率极低，大部分情况下连锁都不用碰，靠CAS就够了。

关键点在于“偷小不偷大”。Fork/Join里，任务拆成Fork之后，子任务是在不断递归产生小任务的。一个线程把自己的子任务Fork出去后，它会先处理自己队头东西；当它发现别的队列有活时，优先偷尾部——因为尾部的任务往往是最近Fork出来的、粒度更小的任务，拿最小的任务去偷，能尽量保证偷过来的任务快速完成，减少偷取过程中的协作成本。这部分原理在各路资料里写得很绕，我自己的经验是：理解到“双端队列+队头执行+队尾偷取+任务粒度递进”这个level就够了，再往深里钻，设计框架的人其实是为了把无谓竞争压到最低。

2. Fork/Join的核心类与参数选择

2.1 四个关键类：ForkJoinPool、ForkJoinTask、RecursiveTask、RecursiveAction

刚上手Fork/Join的人，容易被一堆类名绕晕。抽出主线来看，它其实只有四个角色需要你掌握：

• ForkJoinPool：线程池的总调度容器，维护工作线程、任务队列、公共池引用。它跟普通线程池最大的区别在于支持工作窃取，并且每个线程都自带双端队列。
• ForkJoinTask：所有Fork/Join任务的抽象基类，核心方法就是fork()和join()，以及更高级的invokeAll()。
• RecursiveTask：继承自ForkJoinTask，代表一个有返回结果的递归任务，适合求和、最值、排序这类需要返回值的问题。
• RecursiveAction：也是ForkJoinTask的子类，代表无返回值的递归任务，适合遍历目录、批量处理数据、数组赋值这类只关注副作用（side effect）的场景。

另外还有个细节挺容易忽视：ForkJoinTask实现了Future接口，所以你在任务里调用get()也能拿到结果。但它跟普通Future有个关键区别——它的join()方法在等待任务完成时，不会像Future那样傻傻阻塞一个线程等另一个任务完成，而是会在当前线程里直接执行被等待的任务。这个设计对等待型任务非常友好，后面排查“线程卡死”那块我们会再来回看这一点。

invokeAll()是另一个容易被低估的方法。它接受两个(left, right)子任务，内部做了两个动作：先fork右边的任务，再在当前线程直接在本地执行左边的任务。这样一来，右边的任务会由别的线程偷走，或者排队等待执行，但左边任务不用额外占用一个队列槽位。如果任务拆分得粒度很细，用invokeAll()比手动fork()再join()要高效得多。

2.2 参数怎么定：线程数、拆分阈值、队列容量

用Fork/Join，十个有八个会栽在参数设置上。参数就三个，但每一个都直接影响性能：线程数、拆分阈值、队列容量（严格来说没有配置式设置，由池自己管理，但任务粒度会间接决定队列长度）。

线程数怎么选？ForkJoinPool默认用Runtime.getRuntime().availableProcessors()作为并行度。对于纯CPU密集型任务，并行度=CPU核数是最稳妥的起点。如果任务里偶尔有IO，可以适度调大，比如核数×2。不建议图省事直接调成几十上百，因为Fork/Join工作线程一旦创建，它是常驻的，不干活也在占着资源。

阈值怎么定？这是Fork/Join最容易犯糊涂的地方。阈值太小，任务拆得太多，每个任务对象本身的开销、线程调度开销，可能比计算本身还贵；阈值太大，任务根本拆不动，整个框架退化成单线程递归。我的经验是：先用一个不会让任务拆分超过两层或三层的初始值跑一遍，再逐步调小，观察曲线最低点。如果任务处理的是数组，20万以下基本可以让线程跑；框架里经典示范是求和的阈值设在1万以内，单个元素级别的任务也可以，但那个属于极端场景，非必要不建议。

队列长度其实你很难直接设置，它是动态扩容的。但你可以通过控制“同时Fork出去的子任务数量”来间接影响队列积压。我的习惯是：每次递归只fork一个子任务，另一个用本地线程执行，这样每个工作线程的队列积压量始终受控，不会出现几千个任务对象挤在一个队列里的恐怖状况。这个习惯在没有invokeAll()的年代，被很多人当作“Fork/Join的黄金准则”，到现在依然适用。

我要再次提个醒：**并行度不是越大越好，任务切分次数也绝不是越多越好。**我曾经在某台8核机器上跑数组求和，默认并行度是8，阈值从10万调到1万，再从1万调到1000，数据反而是阈值在1万时最快。原因是任务对象太多导致GC压力暴增，工作线程之间抢任务队列尾部的CAS冲突也多了，开销超过了并行带来的收益。这种“并行反而不如串行”的怪现象，具体分析放第4章来说。

3. 实战：用Fork/Join实现百万级数组求和

3.1 目标定义与实现思路

讲完原理，接下去进入实战环节。我挑了一个最经典的题目：对一个长度为百万级的long数组求和。为什么选这道题？因为它逻辑简单，核心就一个“累加”，所有性能差异都直接反映在“任务拆分+调度+合并”这套机制上，非常适合观察Fork/Join框架自身的成本。

选哪件事用Fork/Join做，有几条判断标准：问题能不能递归切分？切出来的子问题是否相互独立？子问题的结果能不能合并？符合这三条的典型任务有很多——求和、找最大值、归并排序、大数组统计类运算、目录文件遍历汇总。反过来，如果任务本身就不能拆，或者子任务之间有大量共享状态和锁操作，那Fork/Join不仅帮不上忙，还会拖垮你。

实战环境就是一台普通的8核机器，16G内存，Linux环境。为了更贴近真实开发，我没用公共池（公共池的并行度是CPU核数），而是用自定义的ForkJoinPool，这样容易控制并行度做对比。

3.2 核心代码：SumTask实现

定义一个SumTask，继承RecursiveTask<Long>，核心就是compute()方法。逻辑分三步：先判断任务是否已经小到可以不拆；如果能拆，就把数组一分为二，fork出子任务，等两边结果之后相加；如果足够小，就老老实实算。

这个“拆到多大就不拆了”的临界值，就是传说中的阈值（THRESHOLD）。

import java.util.concurrent.ForkJoinPool; import java.util.concurrent.ForkJoinTask; import java.util.concurrent.RecursiveTask; import java.util.concurrent.ThreadLocalRandom; public class ForkJoinSumDemo { static class SumTask extends RecursiveTask<Long> { private static final int THRESHOLD = 100_000; private final long[] array; private final int start; private final int end; SumTask(long[] array, int start, int end) { this.array = array; this.start = start; this.end = end; } @Override protected Long compute() { int length = end - start; if (length <= THRESHOLD) { long sum = 0; for (int i = start; i < end; i++) { sum += array[i]; } return sum; } int mid = start + (end - start) / 2; SumTask left = new SumTask(array, start, mid); SumTask right = new SumTask(array, mid, end); left.fork(); long rightResult = right.compute(); long leftResult = left.join(); return leftResult + rightResult; } } public static void main(String[] args) { int size = 1_000_000; long[] arr = new long[size]; for (int i = 0; i < size; i++) { arr[i] = ThreadLocalRandom.current().nextLong(1, 100); } // 单线程直接求和 long start = System.nanoTime(); long serialSum = 0; for (long v : arr) { serialSum += v; } long serialCost = System.nanoTime() - start; // 默认并行度 ForkJoinPool pool = new ForkJoinPool(); start = System.nanoTime(); long parallelSum = pool.invoke(new SumTask(arr, 0, arr.length)); long parallelCost = System.nanoTime() - start; pool.shutdown(); System.out.println("serialSum = " + serialSum); System.out.println("parallelSum = " + parallelSum); System.out.printf("serial cost : %.2f ms%n", serialCost / 1_000_000.0); System.out.printf("parallel cost : %.2f ms%n", parallelCost / 1_000_000.0); } }

注意上面用了个小技巧：拆任务时只fork一边，另一边在当前线程执行。这样设计的好处，我在前面提过——避免当前线程傻等，同时减少队列槽位被无关子任务占满的可能。你会在很多标准实现里看到写成：

SumTask left = new SumTask(...); SumTask right = new SumTask(...); invokeAll(left, right);

这也可以。两种写法其实是同一个策略的不同表达。invokeAll(left, right)内部做的事，就是先fork一个，再在当前线程执行另一个；手动写出来更好展示背后逻辑，理解框架的人看了也不会觉得突兀。

3.3 性能对比与数据分析

我实测几次，取中间值，结果大致是这样（数组长度100万，数值范围1-99）：

有几个值得聊的点。

差距为什么只有1.5倍而不是8倍？这很正常。求和这种任务是典型的高带宽内存密集型任务，单线程for循环已经能非常有效地把CPU缓存和内存带宽吃满了。把任务拆到多个线程并行，其实是在跟同一个内存带宽抢资源，收益自然有限。换成纯CPU计算任务（比如斐波那契、加密运算、复杂数学公式），并行度高带来的加速比会好看得多。这告诉我们：不是所有任务都适合Fork/Join，计算密度越高的任务越能体现出框架价值。

阈值的影响为什么会呈“倒U型”曲线？波动来自三个开销源的此消彼长：任务对象创建开销、线程调度与队列竞争开销、任务合并开销。阈值太大，拆出来的任务少，并行度利用不充分；阈值太小，任务对象太多，GC和CAS都成了瓶颈。

后期我做对比时发现，当阈值等于1万时，百万数组只拆了大概7层就到叶子了，任务是128个，符合8核并行能力；阈值调到100时，任务直接上万，GC暂停肉眼可感。尽量让任务数量保持在并行线程数的整数倍附近，是比较稳妥的选择。

3.4 不只是写代码：Fork/Join在JDK里的“隐藏应用”

如果你觉得Fork/Join只能用来写求和这类私有工具，那就低估它了。你在日常开发里很可能已经间接用过它，只是完全没意识到。

**Arrays.parallelSort()底层就用了一个叫ForkJoinPool.commonPool()的公共池来并行做排序。Stream.parallel()的默认执行线程池也是这个公共池，只不过严格来说它是Java流的并行实现，底层主要靠Spliterator拆分任务，最终会借助Fork/Join来完成子任务的执行。CompletableFuture**里的异步链路也有Fork/Join的影子。

你可以做一个实验：用Stream的parallel()对一个百万数组求和，再看任务列表里线程名，你会发现线程前缀是ForkJoinPool.commonPool-worker-x，用的就是公共池。这验证了一件事——标准库并没有给Stream另起炉灶，而是复用了Fork/Join的调度体系。这也从侧面说明Fork/Join不是小众玩具，而是Java并发工具箱里被官方重用的大件。

4. 常见问题与排查技巧实录

4.1 性能不升反降，问题出在哪

Fork/Join写着简单，但跑起来“变慢”是新手最常见的事故。我把这种问题总结成三句话：

第一，任务拆得不够粗。这是默认阈值过高导致的。如果你把百万数组求和，阈值设成50万，那任务只被拆一次，一半任务在一个线程上跑，最终性能约等于单线程，看不出任何加速。

第二，任务拆得太细，GC压力爆炸。当一个任务拆出来的对象数以万计时，JVM开始频繁Minor GC，GC本身要暂停所有工作线程，你并行计算的收益全被暂停耗掉了。这时候性能曲线会掉头向下，比你不用Fork/Join还慢。唯一的解法就是调大阈值，让任务数回归到可控范围。

第三，并行度设置不匹配。给你CPU核数为8的机器设并行度为16，线程多了，切换开销反而上升；设成2，并行度不够，空闲核在叹气。想要精确匹配，可以先用Runtime.getRuntime().availableProcessors()获取物理核数，再根据任务CPU/IO比例调整。

排查这类性能问题时，我的顺序是：先看阈值，然后看并行度，再看任务拆分是否合理，最后用jvisualvm看GC曲线。大多数“我Fork/Join好慢”的问题，最终都会落到“我阈值设置不合理”这五个字上。

4.2 任务不执行或线程全部阻塞

这个现象很经典：程序启动后，某些任务一直不跑，有的任务卡在join上出不来。通常原因有两个。

原因一：任务没有使用fork()，而是直接互相join()。当线程A执行任务甲，甲需要等子任务乙的结果，但你只是rightResult = right.get()，没有先fork——这等于让当前线程空等一个从未提交执行的任务，死锁就这样产生了。正确做法是fork之后调用join()，或者用invokeAll()，让当前线程在join时能反过来执行被等待任务，打破相互等待的循环。

原因二：在自定义的ForkJoinPool里写了阻塞调用，把池里所有工作线程都占满了。比如你池里只有8个线程，但有16个任务在等待某个外部资源（数据库连接、Redis、锁），8个工作线程全部处于阻塞状态，剩下8个任务永远得不到执行机会。这个问题凡是线程池都会遇到，但Fork/Join尤其容易忽视，因为它的工作线程数量通常比较固定。我自己的习惯是：如果任务里存在不可控的IO阻塞，就不要用Fork/Join，至少不要用并行度等于CPU核数的默认池。

解决这类问题，可以先用jstack看线程卡在哪，如果看到一片ForkJoinPool管理线程处于WAITING状态，基本就能锁定问题类型了。

4.3 工作窃取引发的CPU飙高

还有一类诡异问题：任务全部完成了，join()都返回了，但CPU占用还是居高不下。有人怀疑是死循环，但线程栈里看不到业务线程，全是ForkJoinPool的工作线程。

这大概率是碰到了公共池线程饥饿的变体。工作线程在处理完队列任务之后，会进入awaitWork()阻塞等待新任务唤醒。正常情况下它应该挂起，但如果池里设置了commonMaxSpares（公共池备用线程上限），或合并了大量长尾任务，它的唤醒机制可能会让部分线程频繁空转，CPU曲线就被“假活”拉高了。排查方法很简单：用jstack看那些ForkJoinPool线程，如果大量处于RUNNABLE状态且堆栈都指向同一个scan()方法，那就是它在空转，等待池里塞入新任务。

真遇到这种情况，不需要太慌张。大多数场景下把自定义池的awaitQuiescence()或shutdown()好好调一调就行，如果没有特殊需求，直接使用默认公共池，让JDK自行管理线程生命周期，反而更省心。

4.4 避坑清单：几个值得牢记的使用习惯

总结一下我踩过坑之后沉淀下来的使用原则，也算是一份速查表：

还有个小技巧：Fork/Join的invoke()返回的是第一个被提交的任务结果，但如果你调动的是多个独立任务，最好还是拆分之后各自维护Future，或者用一个汇总任务包住所有子任务，免得把不同阶段的逻辑混在一棵树上。

另外说个很实际的体会——Fork/Join的调试比普通多线程容易一截，因为任务结构天生是树，任务栈的父子关系可以画出来。我过去排查一个复杂并行查询问题时，就是用日志把每个子任务的fork/join时间打印出来，根据时间线树状结构一眼就看出了瓶颈在哪个子分支上。如果你要把这份经验带进团队协作，建议把任务拆分时的start和end也打出来，调试时能把问题定位到具体的数组片段，节省大量翻日志的时间。

5. 从实战到进阶：这几类任务建议用Fork/Join重写

5.1 数据统计与聚合类任务

最典型的就是批量日志统计、BI报表的DataFrame聚合、多维指标累加。这类任务规模大、数值计算多、各维度之间天然没有依赖，非常适合用Fork/Join切分到几十个子任务并列计算，最后再做汇总。我曾经把一个单线程跑3秒的统计逻辑，用Fork/Join拆到8线程后压到800毫秒以内，效果非常直观。

5.2 递归遍历与目录解析

文件目录遍历是另一个高频场景：统计某个大目录下所有文件夹大小、搜索特定类型文件数量。每个子目录天然就是一个子任务，不需要额外设计拆分逻辑，RecursiveAction正好派上用场。不过要注意，目录遍历里别在任务里直接做打印输出，会频繁抢锁，打印独占锁的大坑我踩过一次。

5.3 分治算法重写：归并排序与快速排序

归并排序和Fork/Join是天生一对。单线程归并排序对十万级数据已经很快，但百万级以上时，并行归并的优势会逐渐体现。代码结构本质上就是invokeAll(left, right)，然后等待两边排序完成后合并。快速排序也类似，每次选定基准把数据一分为二，左右分区互不干扰，并行化以后的分区操作可以让大数组排序吞吐量提升一截。

但这里要给你泼盆冷水：别为了一道排序题把整个系统重构成Fork/Join。JDK已经提供了Arrays.parallelSort()，底层就是Fork/Join，只要你确认自己的数据结构和排序需求满足它的前置条件，直接用就好。自己手写并行排序，多数情况下只适合教学学习或特种算法定制。

6. 写在最后：我这个老用户的一点心得

Fork/Join框架上手不难，难在能不能正确衡量“该不该用它”。我自己用过很多轮之后，最大的感受是：它解决的是结构化分治任务的并行问题，不是所有多线程任务的银弹。你一定要先判断自己的任务是否符合“可递归拆、子任务独立、结果可合并”这三个特征，再决定入手。

参数调优不要靠猜，靠“分而治之”的办法：固定其他变量，只动阈值，跑一组对比；再固定阈值，只动并行度，跑一组对比。每次记录热度和耗时，曲线自然告诉你最佳工作点在哪。学习阶段多写几个小Demo比阅读十篇原理文章有用得多，像合计求和、数组最大值、递归目录统计，每一个都能帮你把fork、join、invokeAll、工作窃取之间的关系揉进手感里。

最后再分享一个小技巧：写给团队用的通用并行工具时，务必把阈值和并行度做成可配置参数，而不是常量写死在类里。这样换机器、换数据规模时不用改代码重新编译，直接通过配置调整就能快速适配。这个习惯让我在跨平台部署时少走了很多弯路，真心建议所有用Fork/Join做组件化开发的人都保留。