《大规模分布式计算深入解析》6.1 全局排序的归并与限额

全局排序要求所有结果共享同一比较器和统一顺序。局部排序加有序归并,以及范围重分布加有序拼接,都是合法实现。

6.1 全局排序的归并与限额

全局排序要求所有结果共享同一比较器和统一顺序。局部排序加有序归并,以及范围重分布加有序拼接,都是合法实现。

两条执行路径

  1. 每个任务先局部排序,按同一比较器输出有序流,目的消费者做多路归并。若每路输入已经有序且可暂停,消费端只需维护流头和一定缓冲。最终 Gather 可能成为吞吐限制。
  2. 采样得到排序键范围,按比较器把各输入发送到非重叠范围,各目的分别排序,然后按范围顺序读出。相同键大量聚集时可使用稳定次序扩展键,或接受热点范围并调整策略。只把无全局范围保证的局部有序流按节点顺序拼接会错。

估算比较与落盘

1 亿行、16 个均匀任务,每个 625 万行。比较模型 n × ceil(log2(n)) 给出单任务约 1.4375 亿,实际取决于排序与输入,复杂度下界量级来自比较决策树 log2(n!)。按 100 B/行,单任务逻辑输入 625 MB。若整个任务用外排,排序 run 至少有写入,归并还有回读,多趟时可能再次写盘。应对照峰值内存、run 数、扇入、读写字节及最终归并的阻塞时间。

实验与资料

下载卷六实验包 ,参照包内 README。src/ 下的 Java 8 教学模型。本章架构或流程见本章机制图 。

Trino 分布式排序

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图