6.1 全局排序的归并与限额
全局排序要求所有结果共享同一比较器和统一顺序。局部排序加有序归并,以及范围重分布加有序拼接,都是合法实现。
两条执行路径
- 每个任务先局部排序,按同一比较器输出有序流,目的消费者做多路归并。若每路输入已经有序且可暂停,消费端只需维护流头和一定缓冲。最终 Gather 可能成为吞吐限制。
- 采样得到排序键范围,按比较器把各输入发送到非重叠范围,各目的分别排序,然后按范围顺序读出。相同键大量聚集时可使用稳定次序扩展键,或接受热点范围并调整策略。只把无全局范围保证的局部有序流按节点顺序拼接会错。
估算比较与落盘
1 亿行、16 个均匀任务,每个 625 万行。比较模型 n × ceil(log2(n)) 给出单任务约 1.4375 亿,实际取决于排序与输入,复杂度下界量级来自比较决策树 log2(n!)。按 100 B/行,单任务逻辑输入 625 MB。若整个任务用外排,排序 run 至少有写入,归并还有回读,多趟时可能再次写盘。应对照峰值内存、run 数、扇入、读写字节及最终归并的阻塞时间。
实验与资料
下载卷六实验包
,参照包内 README。src/ 下的 Java 8 教学模型。本章架构或流程见本章机制图
。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。