sacloudy / pipeline

使用go语言并行计算模拟多节点外部排序

pipeline

项目简介

使用go语言并行计算模拟多节点外部排序。

用一个10G的随机整数的文件做待排文件，分4块“读入”4个channel中(channel未设缓冲区)，假设此时数据规模可以一次性装入内存，调用库函数分别将它们排序，然后把 所有的channel append起来传给MergeN函数进行递归地归并。

其中主要功能函数（分块读取，内排序，归并）都是 out:=make(chan int) go function(){} return out 的实现方式

程序存在问题：就是确实还是存在一个时刻所有数据都在内存中的。

​ 原因就出在二路归并函数上，虽然二路归并函数也是开一个goroutine立马返回一个channel。但是整个排序过程中channel都是空的，因为归并函数是从下往上归并的，最后一次归并完了channel中才开始有数据，下面需要这个channel的负责写的goroutine知道全部排完序才能开始写(也就是串行滴)

​ 其实这是归并函数的特性决定的，不是不能用channel进行传输而是归并函数在归并过程中确实没法体现得出结果，插入排序或者选择排序才可以

解决办法可能就有点复杂了，就把每个排好序的channel中的数据都写到磁盘上，然后分别取其前一小部分元素到内存，排好序后写到最终的文件中。 （可以借助堆）