前阵子我们某个内部数据分析服务做了一次排序性能改造场景很常规一张宽表里几千万条明细需要按某个数值型主键排序后做分页单线程跑一趟排序要好几百毫秒到秒级已经影响到查询接口的响应时间。我们试过直接调 JDK 自带的并行排序效果还行但总觉得还能再压一压。后来花了点时间把思路重新理了一遍做了一个“基于快排和二项归并改进的多线程排序器”最终在一台普通四核机器上把千万级整数的排序耗时降到了原来的四分之一左右。这篇文章就把这套方案从头到尾拆开讲为什么单线程快排不够用、二项归并在这套方案里扮演什么角色、线程模型怎么设计、核心代码怎么写、实测数据和几个真正影响性能的细节。适合那些遇到过大数据量排序瓶颈、想自己控制并行行为而不是只调用黑盒 API 的开发者。1. 单纯快排不够用归并才是并行的钥匙在做并行排序之前得先把两种经典排序算法的脾气摸清楚。很多人的第一反应是“快排直接多线程递归不就行了”但真去做的时候会发现快排的并行化不是一个简单加线程池的事。1.1 快排为什么难并行快速排序的核心是选择一个基准元素pivot通过 partition 把数组分成左小右大两部分然后递归处理两边。这个递归结构本身是有并行潜力的左右两个子问题理论上可以分给两个线程。问题在于 partition 这一步是阻塞的。你必须要等划分完成、知道基准元素的最终位置才能确定左右子问题的边界。pivot 选得不好两边数据量差距大线程负载就严重倾斜。典型情况下快排的递归深度是 O(log n)也就是说整棵递归树里只有前几层能并行越往深处并行度越低。极端情况下 partition 之后一边是空、一边是全部数据后面根本并行不起来。还有一个容易忽略的点快排是原地排序数据交换频繁但交换本身是有缓存代价的。多线程各干各的还好一旦多个线程在同一个数组区域附近做交换缓存行争用会让性能断崖式下跌。但这不是说快排没法用而是说它更适合在“小范围内”发挥威力。1.2 归并排序的并行机会归并排序正好相反。它的分拆是机械的——直接按数组下标从中间切开左右两半谁先排完都不影响对方只要每一半内部有序最后一步做 merge 就能得到完整有序数组。合并这个动作没有随机访问性从头到尾扫一遍而已非常适合顺序访问。更重要的是归并过程天然能构造出一棵“满并行”的树第一步把 n 个元素分成两半两个子任务可以并行每个子任务再分两半四个孙任务可以并行……理想情况下第一轮并行度翻倍直到线程数用满。这个特性非常宝贵。我们看到很多工业级的并行排序实现本质都是“先切分再局部排序最后归并”而不是一根筋地去并行化快排的递归树。1.3 二项归并在这套方案里的含义标题里说的“二项归并”在我这个项目里有明确的约定在这里先定义清楚免得后续代码看不懂。我指的是把初始分片数看成二的幂次形成的归并树每一趟归并的段数量减半、段大小翻倍。比如一开始分成 32 个块第一趟两两合并成 16 块第二趟 16 块合并成 8 块……直到最后 1 块。整个归并过程的段数序列是 32、16、8、4、2、1每一趟可以并行处理的任务数就是当前段数的一半。这正好符合二项式规模递减的规律所以叫“二项归并”。普通的二路归并只强调了“两两合并”这个微观动作而二项归并强调的是整个归并序列要按 2 的幂来组织这样每一层的并行任务数一目了然、容易用工控同步原语去安排。这就是它能和分片快排漂亮地组合在一起的原因快排负责把大数组切成一堆内部有序的分片二项归并负责把这些分片用极致的并行度合并成完整有序数组。2. 整体设计与线程模型分片快排 二项归并树有了上面两种排序思路整体的框架其实已经呼之欲出了就是两阶段第一阶段快速切分并各自排序第二阶段逐层并行归并。这一节把架构层面的决策讲透尤其是线程模型和分片数的选择这是很多人容易翻车的地方。2.1 两阶段流水线第一阶段叫分片快排。我们把整个数组按连续区间切成 (K) 个块每个块交给一个任务做单线程快速排序。第二阶段叫二项归并从 (K) 个有序块开始第一趟并行执行 (\lceil K/2 \rceil) 次两两归并得到 (\lceil K/2 \rceil) 个更大的有序块然后继续合并直到变成一个整体。为什么要“先快排再归并”而不是一开始就完全用归并排序因为归并排序在数据规模小的时候也就是底部递归层有大量函数调用和临时数组分配不如快排的原地交换来得爽快。反过来完全用快排又解决不了深层次并行度下降的问题。所以让快排在局部发挥长处、让归并在全局组织并行这是一个互补性很强的组合。实际测试中我们最初也试过“分片用标准库排序再并行归并”性能就已经不差了。但后来发现标准库排序为了通用性做了很多分支判断换成分片内自定义快排之后输入规模缩小、数据类型固定分支预测命中率明显上升整体又快了 5%~10%。所以有追求的话分片内的排序也值得自己写。2.2 分片数 K 怎么选分片数 (K) 直接决定归并树的深度和每个任务的大小这是个权衡问题。如果 (K) 等于线程数那么第一阶段每个线程刚好处理一大块看起来最“公平”但随机数据里快排的 partition 会有轻微的不均匀导致某些线程提前排完、某些线程还在忙整个阶段被最慢的那个任务拖住。如果 (K) 取线程数的 4 倍第一阶段任务数量更多、单块更小常用任务队列去抢活天然就做了负载均衡。但代价是归并树深度从 (\log_2 P) 变成 (\log_2 (4P))多了两层而每一层结束都需要等一下最慢的那个归并任务所以不是 (K) 越大越好。以 8 线程为例几种分片数的表现大致如下分片数 K第一轮归并任务数需要轮次负载均衡风险我们的选择843 轮归并高不推荐1684 轮归并中可用32165 轮归并低推荐64326 轮归并极低过度收益不明显这里说的“轮次”是指整个归并阶段的趟数每一趟内部如果任务数多于线程数还要分多波执行。所以 (K 4 \times threads) 是个不错的折中负载风险够低归并趟数增长可控。当线程数更高比如 16、32时这个比例还可以再微调。2.3 线程池选择ForkJoinPool 还是固定线程池市面上并行排序优先想到的就是 ForkJoinPool因为它有工作窃取算法适合递归分治场景。但我最后在主归并流程里用的是 FixThreadPool CountDownLatch而不是把所有逻辑塞进 RecursiveTask。原因在于二项归并是一个分层屏障结构每一趟之间必须等所有任务完成才能开始下一趟。ForkJoin 的 join 模型适合“父子任务依赖”的树形结构而这里每层任务之间是兄弟关系、层与层之间是全局屏障用 CountDownLatch 表达更直白也更好控制。实测结果也印证了这个选择两种模型在这种批量任务下的吞吐接近但固定线程池的代码心智负担明显更小排查问题也更方便。ForkJoinPool 的优势是可以自动负载均衡所以我把第一阶段的“分片快排”仍交给 ForkJoinPool 的普通提交接口在分片数量足够多的情况下效果也还可以。这里给出我们项目的核心架构图用文字描述就是申请线程池大小 CPU 核数。把原始数组切成 K 块提交 K 个快排任务。等待 K 个任务全部完成得到 K 个有序分片。进入归并循环每趟提交 (\lceil tasks/2 \rceil) 个归并任务等本趟完成后再进入下一趟。如果最后结果在临时数组里拷贝回原数组。3. 核心实现Java 里的快排分片与二项归并下面进入代码环节。为了保证可复现性我尽量给出完整但精简的实现语言用的是 Java 17线程并发用 ThreadPoolExecutor 和 CountDownLatch。代码逻辑不复杂重点看归并调度的结构。3.1 分片内的快排实现分片内的排序核心是就地快排。我对基础快排做了三个改进三数取中选 pivot、小数组回落到插入排序、递归时始终优先处理较小的一半避免递归深度过大。static void quickSort(int[] arr, int low, int high) { while (low high) { if (high - low 16) { insertionSort(arr, low, high); return; } int mid (low high) 1; // 三数取中low、mid、high 的中间值作为 pivot 索引 int pivotIndex medianIndex(arr, low, mid, high); int pivot arr[pivotIndex]; // partition 双指针把 pivot 换到 low 位置便于循环 int i low, j high 1; swap(arr, pivotIndex, low); while (true) { while (arr[i] pivot) { if (i high) break; } while (arr[--j] pivot) { if (j low) break; } if (i j) break; swap(arr, i, j); } swap(arr, low, j); // 递归处理更小的一半较大的一半用迭代继续 if (j - low high - j) { quickSort(arr, low, j - 1); low j 1; } else { quickSort(arr, j 1, high); high j - 1; } } }这个 partition 是从左右两端向中间逼近的经典写法配合三数取中后随机数据下基本不会出现愚蠢的 O(n²) 退化。插入排序阈值取 16 是经验值低于这个规模函数调用和循环开销反而比插入排序更重。分片任务的提交很简单把数组切成 K 段每一段边界算好后丢给线程池执行即可int block (n K - 1) / K; CountDownLatch sortLatch new CountDownLatch(K); for (int i 0; i K; i) { int start i * block; int end Math.min(n, start block); if (start end) { sortLatch.countDown(); continue; } int finalStart start, finalEnd end; executor.execute(() - { quickSort(arr, finalStart, finalEnd - 1); sortLatch.countDown(); }); } sortLatch.await();这段代码几乎没有深奥的东西但它是整条并行的起点。切段必须按连续区间切不能交错切否则第二阶段归并时数据位置会和有序性要求对不上。3.2 二项归并的调度代码分片排完之后就进入核心的二项归并循环。我在每个生命周期内维护两个数组引用src和dst一趟归并从src读出、写入dst下一趟再交换角色。这样只需要一块额外临时空间避免了频繁 GC。int[] tmp new int[n]; int[] src arr; int[] dst tmp; int segmentSize block; while (segmentSize n) { int taskCount 0; for (int left 0; left n; left segmentSize * 2) { taskCount; } CountDownLatch phaseLatch new CountDownLatch(taskCount); for (int left 0; left n; left segmentSize * 2) { int mid Math.min(left segmentSize, n); int right Math.min(left segmentSize * 2, n); if (right mid) { // 最后一个块不参与合并直接拷贝到目的地 phaseLatch.countDown(); continue; } executor.execute(() - { merge(src, dst, left, mid, right); phaseLatch.countDown(); }); } phaseLatch.await(); // 交换 src 和 dst下一趟反向归并 int[] t src; src dst; dst t; segmentSize 1; } if (src ! arr) { System.arraycopy(src, 0, arr, 0, n); }这段代码有几个细节值得留意segmentSize从初始块大小block开始每趟翻倍直到覆盖整个数组正好对应“二项归并”的树结构。phaseLatch是每一趟的屏障。任务之间没有依赖同一趟内不同任务处理不同区间互不干扰。左边界left、中间mid、右边界right都用Math.min做了边界保护处理数组长度不是 2 的整数次幂的情况。最后一个不成对的块不参与归并直接视为空任务。如果countDown放的位置不对会导致整趟提前结束或者永久阻塞这类问题测并发代码时很容易遇到。3.3 merge 函数本身的小优化merge 是最底层的操作理论上越简单越好static void merge(int[] src, int[] dst, int left, int mid, int right) { int i left, j mid, k left; while (i mid j right) { if (src[i] src[j]) { dst[k] src[i]; } else { dst[k] src[j]; } } while (i mid) dst[k] src[i]; while (j right) dst[k] src[j]; }如果你想榨取更多性能可以考虑 galloping merge当某一侧连续赢得超过某个阈值次比较时说明这一侧剩下的元素很可能整体小于另一侧的当前值这时候用二分搜索找到插入位置然后用System.arraycopy整段搬移。在接近有序或者大量重复元素的数据上galloping 能省掉大量逐元素比较。但要注意收益对随机数据不明显代码复杂度却上去了。我的建议是先实现朴素版跑通正确性再在真正出现瓶颈时加上 galloping。工程上第一版求稳是对的。4. 实测数据不同规模、不同线程下的表现代码写完了自然要跑数据验证。我不会去吹“加速比接近 8 倍”这种鬼话实测下来能到 4 倍就很不错了。这里给出我们项目里的实际记录。4.1 测试环境与对比基线测试环境是一台普通办公机四核八线程的 CPUJVM 堆 2GBJDK 17系统后台没有跑其他重负载任务。对比的基线有三个Arrays.sortJDK 的单线程快速排序代表最朴素做法。Arrays.parallelSortJDK 自带的并行排序代表工业级黑盒方案。本文方案K 4 × 线程数线程数取 8分片快排 二项归并。数据是随机生成的int[]生成后先拷贝几份独立的数组分别测不同方案避免前一次排序影响后一次。每组规模跑 5 次取中位数。排序的目标是升序。4.2 结果数据数据规模Arrays.sortArrays.parallelSort本文方案相对单线程加速100 万145ms38ms32ms≈4.5x500 万720ms152ms118ms≈6.1x1000 万1350ms310ms228ms≈5.9x2000 万2800ms680ms483ms≈5.8x单独看不同线程数下的表现1000 万随机整数线程数本文方案耗时11250ms2680ms4385ms8228ms16246ms4.3 为什么接近线性加速但又达不到从表里能看出8 线程下相对单线程大约加速 5.5 到 6 倍没法做到 8 倍。这是正常的。第一个原因是归并阶段最后几趟任务数小于线程数。比如 32 个分片最后第 6 趟只有一个任务在跑而 8 条线程里 7 条在空转。越是小规模、任务数越少这个问题越明显所以 100 万的时候加速比只有 4.5 倍。第二个原因是内存带宽的物理瓶颈。快排阶段是计算密集归并阶段变成内存拷贝密集大量读写同一块缓冲区内存带宽很容易触顶。数据规模越大内存带宽瓶颈越突出。2000 万时耗时不再线性下降和这个关系很大。第三个原因是线程切换和任务提交开销。任务提交到线程池有加锁和唤醒成本归并趟数越多这些固定开销占比越大。这也是为什么我不建议把 (K) 无限放大。再补一个对比数据量 1000 万、完全有序时Arrays.sort会退化成接近归并的逻辑依然要 300 多毫秒而我们的分片快排在第一个分片内发现数据有序时可以提前跳过部分操作。当然这里没有做专门的“有序检测”真实收益不完全来自算法本身还包括分片后快排的三数取中策略对有序数据有天然改善。5. 工程化落地负载均衡、伪共享与内存复用的优化细节如果把上面代码直接部署到生产环境大概率会在某些机器上踩到性能大坑。这一章说几个我们在调试过程中真正影响性能的工程细节都是文档里不会写的东西。5.1 分片快排的负载不均衡随机数据经过三数取中的快排分区不均衡的概率不大但一旦出现最慢的线程会影响整个第一阶段。我们遇到过一个很隐蔽的情况数据里含有大量重复值。标准三数取中会把大量相等元素扔到两侧“看心情”导致 partition 返回的位置偏向一端某些块的任务时间长了 50%。后来我们在 partition 里加入了类似“双路切分”的处理把等于 pivot 的元素固定在中间重复值越多收益越明显。另一个思路是后面再补一层不把 K 设为固定的 4 × threads而是用一个“任务池”动态领取分片。第一阶段每个线程排完一块之后去队列里取下一块继续排直到所有分片被取完。这样即使有一块特别慢完成快的线程也会去帮忙负载自动均衡。5.2 连续内存写入的伪共享二项归并阶段同一趟内多个线程在写同一个目标数组的相邻区域。如果两个线程恰好挨着写入相邻的缓存行就会发生伪共享false sharing。这不是数据竞争程序结果依然正确但性能可能下降 20%~30%。处理办法有几种。最“硬核”的是让每个线程在写目标数组之前先把自己的输出攒到一个独立的小缓冲区里最后再整块拷贝。但这样等于每趟都多了一次拷贝得不偿失。我们最后的选择是把归并任务按不连续的顺序提交例如第一趟合并 (0, 1) 和 (2, 3)我们反而先提交 (0, 1) 和 (4, 5)让两个相邻任务错开写不同缓存行。这种调度顺序上的小改动在低并发机器上实测有不错的收益。如果不想在代码里加入奇怪的调度顺序也可以利用线程亲和性让每个归并任务尽量沿着一个方向持续读取和写入大段内存避免两个线程交叉访问同一段数据。5.3 临时数组与 GC 抖动我最初版本在归并循环里每趟都new int[n]跑 1000 万数据直接触发 GC耗时会突然出现 200~300ms 的抖动。后来才改成文章里一次性分配tmp数组、来回交换的做法GC 问题立刻消失了。这里还要注意一个点分片快排阶段和归并阶段需要的内存是“前高后平”或“前平后高”峰值也就是一个原数组加一个临时数组。如果你用堆内存检查工具去观察会发现老年代里两块大数组占得满满当当。若机器内存紧张可以考虑先把原始数组拷贝到堆外再用MemorySegment映射性能未必提高但至少不挤堆。5.4 这版排序器最后长什么样最终落地到项目里的多线程排序器对外只暴露了一个静态方法parallelSortByCustom(int[] arr, int threads)。内部流程是根据线程数算分片数 (K 4 \times threads)最多不超过 CPU 核数的 8 倍。分片内快排使用三数取中 插入排序阈值 尾递归优化。二项归并循环使用固定线程池 CountDownLatch 同步每趟。最后一趟结果在临时数组时拷贝回原数组。排序完成后关闭线程池或复用池实例避免重复创建。生产环境里我们没有让每个排序调用都新建线程池而是复用一个全局池并把线程数设为Runtime.getRuntime().availableProcessors()。这样大量小任务共用线程池不会频繁触发线程创建销毁。从我们线上服务的表现来看这个排序器把一批原本 600ms 左右的排序任务压到了 110ms 左右接口 P90 响应时间明显改善。当然它也有明显局限只针对一维原生数组不支持对象、不支持稳定排序、不直接支持范围内排序。但作为一个内部数据预处理工具已经足够用了。最后分享一个实操习惯这种多线程排序代码一定要在 32 核或 64 核的高并发机器上复测一遍因为线程池提交任务的开销在低核机器上不明显在高核机器上会放大。先跑出单线程基线再逐级加线程才能看清每个阶段的真实瓶颈在哪里。