大文件排序优化实践

在很多应用场景中，我们都会面临着排序需求，可以说是见怪不怪。我们也看过许多的排序算法：从最简单的冒泡排序、选择排序，到稍微好点的插入排序、希尔排序，再到有点理论的堆排序、快速排序，再到高级的归并排序、桶排序、基数排序。

而实际工作中我们可能用到的排序有哪些呢？而且，大部分时序，相信大家都是使用一个现有库API直接就完成了排序功能。所以，讲真，大家还真不一定会很好排序。

不过本文的目的不是基础排序算法，而是如何处理数据量的文件的内容排序问题？

1. 多大的文件算大文件？

多大的文件算大文件？这是个定义的问题，当我每天处理的都是几百几千的数据，那么我遇到几万的数据后，我可以认为这个数据量是大的。

但总体来说，我们还是需要定义一个量级的，不然无法评估处理能力问题。

比如我们定义超过200M的文件算大文件可以不？我们定义超过5000w行的数据算大文件可以不？

好了，基于这样大的数据量的时候，也许我们就不能简单的调用几个库函数就解决问题了，至少你load到内存也将存在一定的风险了。

所以，是时候想想优化的事了！

2. 如何利用好现有的工具？

针对一些问题，我们可以自己做，也可以找别人帮忙做。具体谁来做，这是个问题！

比如，你自己花个一两天的时间，写了个排序算法，搞定了。但是，你能保证你的稳定性吗？你能经受住生产环境复杂的环境考验吗？

再比如，你可以现有的工具进行操作，如果有人提供了稳定的api函数供调用的话，你可以这么干。如果你的服务是跑在linux环境下，那么，我们有必要试一下系统提供的排序功能。 sort . 这工具绝对是经过无数的考验的，可以放心使用。它也有丰富的参数供选择，这对我们的日常工作非常有帮助，但对于一个普通的排序也许我们并不需要。

比如最简单的，自然排序：

sort 1-merged.txt -o 1-sorted.txt

就可以将文件排好序了。但是当数据非常大的时候，比如我使用 7000w+ 的行数（约1.2G）进行排序时，就花费了 6min+ . 也许是我硬件不怎么好，但是实际上它就是会很慢啊！

$ time sort 1-merged.txt -o 1-sorted.txt

real    8m5.709s
user    25m19.652s
sys     0m4.523s

这种性能，在当今大数据横行的时代，基本就是胎死腹中了。大数据应对的都是TB/PB 级别的数量，而我们并没有做其他业务就已经耗费了这么长时间，这是没办法继续了。让我继续。

看到文档里有说，系统本地化配置影响排序，实际就是存在一个编解码的问题，它会依据本地的配置来进行转换字符然后再进行排序。这个开销可是不小哦，比如我们设置都是中文环境。而要去除这个影响，则可以使用添加 LC_ALL=C 之后就会使用原始的值进行排序，具体影响就是省去转换编码的开销了。那么，我们用这个参数试试。

*** WARNING ***
The locale specified by the environment affects sort order.
Set LC_ALL=C to get the traditional sort order that uses
native byte values.

$ time LC_ALL=C sort 1-merged.txt -o 1-sorted.txt

real    2m52.663s
user    2m7.577s
sys     0m5.146s

哇，从8分钟降到了3分钟，虽然不是数据级提供，但至少下降了一半以上的时间消耗，还是非常可观的。到这个地步，也许能满足我们的场景了。

但是，请注意一个问题，这里的 LC_ALL=C 之后，就会使用默认的进行处理了，那么，会有什么影响呢？实际上就是一些本地相关的东西，就会失效了。

最直接的，就是中文处理的问题了，比如我有一个文件内容是这样的：

床前看月光，
疑是地上霜。
举头望山月，
低头思故乡。
天子呼来不上船，
自称臣是酒中仙。
红酥手，
黄藤酒，
满城春色宫墙柳。

那么，我们使用 LC_ALL=C 设置来排序后，将会得到如下结果：

$ LC_ALL=C sort 1.txt -o 1-s1.txt

$ cat 1-s1.txt
举头望山月，
低头思故乡。
天子呼来不上船，
满城春色宫墙柳。
疑是地上霜。
红酥手，
自称臣是酒中仙。
黄藤酒，
床前明月光，

额，看不懂啥意思？中文咋排序的我也给整忘了（而且各自机器上得到的结果也可能不一样）。好吧，没关系，我们去掉 LC_ALL=C 来看看结果：

$ sort 1.txt -o 1-s1.txt

$ cat 1-s1.txt
床前明月光，
低头思故乡。
红酥手，
黄藤酒，
举头望山月，
满城春色宫墙柳。
天子呼来不上船，
疑是地上霜。
自称臣是酒中仙。

这下看懂了吧，这是按照拼音顺序来排序的。所以，你说 LC_ALL=C 重不重要，如果没有本地化设置，很多东西都是不符合情理的。所以，有时候我们还真不能这么干咯。

如果真想这么干，除非你确认你的文件里只有英文字符符号和数字，或者是 ASCII 的127 个字符。

3. 绕个路高级一下

前面的方法，不是不能解决问题，而是不能解决所有问题。所以，我们还得继续想办法。想想当下对大文件的处理文件都有哪些？实际也不多，并行计算是根本，但我们也许做不了并行计算，但我们可以拆分文件嘛。一个文件太大，我们就文件拆小排序后再合并嘛！就是不知道性能如何？

split -l 100000 -d ../1-merged.txt -a 4 sp_; 
for file in sp_*.txt; do; 
    sort -o $file sorted_$file; 
done; 
sort -m sp_*.txt -o targed.txt;
# 一行化后的格式    
$ time for file in sp_*; do sort -o sorted_$file $file; done; sort -m sorted_* -o targetd.txt;

real    12m15.256s
user    10m11.465s
sys     0m18.623s
# 以上时间仅是单个文件的排序时间还不算归并的时间，下面这个代码可以统一计算
$ time `for file in sp_1_*; do sort $file -o sorted_$file; done; sort -m sorted_* -o targetd.txt;`

real    14m27.643s
user    11m13.982s
sys     0m22.636s

看起来切分小文件后，排序太耗时间了，看看能不能用多进程辅助下！（还是回到了并行计算的问题上了）

# shell 异步运行就是在其后面添加 & 就可以了, 但是最后的归并是同步的.
$ time `split -l 100000 -d ../1-merged.txt -a 4 sp_ ; for file in sp_* ; do {sort $file -o $file} &; done; wait; sort -m sp_* -o target.txt ; `
# 多处计时监控
$ time `time split -l 100000 -d ../1-merged.txt -a 4 sp_; time for file in sp_1_*; do { sort $file -o $file } & ; done; time wait; time sort -m sp_* -o target.txt;`
# 以上报错,因为命令行下不允许使用 & 操作, 只能自己写shell脚本,然后运行了
# sort_merge.sh
time split -l 100000 -d ../1-merged.txt -a 4 sp_;
i=0
for file in sp_*;
do
{
    #echo "sort -o $file $file";
    sort -o $file $file;
} &
done;
time wait;
time sort -m sp_* -o target.txt;
# 以上脚本的确是会以异步进行排序，但会开启非常多的进程，从而导致进程调度繁忙，机器假死
# 需要修复下
# sort_merge.sh
split_file_prefix='sp_'
rm -rf ${split_file_prefix}*;
time split -l 1000000 -d ../short-target.csv -a 4 ${split_file_prefix};
i=0
for file in ${split_file_prefix}*;
do
{
    sort -o $file $file;
} &
    # 每开5个进程，就等一下
    (( i=$i + 1 ))
    b=$(( $i % 10 ))
    if [ $b = 0 ] ; then
        # 小优化: 只要上一个进程退出就继续,而不是等到所有进程退出再继续
        time wait $!
        # time wait
    fi;
done;
time wait;
time sort -m ${split_file_prefix}* -o target.txt;
# 以上运行下来,耗时9min+, 比未优化时还要差, 尴尬!
real    9m54.076s
user    19m1.480s
sys     0m36.016s

看起来没啥优势啊, 咋整? 咱们试着调下参试试!

# 1. 将单个文件设置为50w行记录, 耗时如下:
# 额, 没跑完, 反正没啥提升, 单个文件排序由之前的2s左右, 上升到了11s左右
# 2. 将单个设置为20w行记录试试:
# 单个文件排序上升到了4.xs, 也不理想啊;
real    9m2.948s
user    21m25.373s
sys     0m27.067s

增加下并行度试试!

# 增加并行度到10
real    9m3.569s
user    21m4.346s
sys     0m27.519s
# 单文件行数 500000, 并行10个进程
real    8m12.916s
user    21m40.624s
sys     0m20.988s

看起来效果更差了,或者差不多. 难道这参数咋调整也没用了么? 算了, 不搞了.

4. 换个性能好的机器试试

前面的机器太差了，也没了信心。干脆换一个试试。直接进入优化参数环节：

# 50w行, 5进程
real    5m6.348s
user    5m38.684s
sys     0m44.997s
# 100w行, 5进程
real    2m39.386s
user    3m34.682s
sys     0m23.157s
# 100w行, 10进程
real    2m22.223s
user    3m41.079s
sys     0m25.418s
# 以上结论是行数更容易影响结果, 因排序是计算型密集型任务, 进程数也许等于CPU核数比较优的选择
# 不过也有一个干扰项：即文件的读取写入是IO开销，此时2倍以上的CPU核数进程可能是更好的选择
# 100w行, 10进程, 7100w总数(1.6G)
# 使用原始排序 sort
real    6m14.485s
user    5m10.292s
sys     0m13.042s
# 使用 LC_ALL=C 测试结果
real    2m1.992s
user    1m18.041s
sys     0m11.254s
# 使用分治排序, 100w行, 10进程
real    2m53.637s
user    4m22.170s
sys     0m29.979s

好吧，linux的优化估计只能到这里了。

5. 自行实现大文件排序

看起来shell帮不了太多忙了，咋整？用java实现？线程池可以很好利用队列先后问题；但到底有多少优势呢？试试就试试！但线程可以很方便地并行，比如在分片文件的同时，其他线程就可以同进行排序了，也许等分片完成，排序就ok了呢！

简单时序可表示为： split -> f1 -> submit(f1) -> sort(f1) -> merge(f1) -> wait (所有merge都完成)。也就是说所有过程都并行化了，拆分一个文件就可以进行排序文件，排序完一个文件就可以合并一个文件。

线程模型是这样的： 1个拆分线程 -> n个排序线程 -> 1个归并线程；任务执行完成的前提是：n个排序线程完成 + n个归并任务完成；

大体思路是这样，但还可以优化的是，归并线程是否可以维护一个指针，代表最后一次插入的结果，以便可以快速比较插入；（有点困难，还要写新文件，这里可能是个瓶颈点，因为如果有1000次归并，就会存在读写大文件的过程，如果前面的文件分片存在速度慢的问题，那么此处的反复写更是一个瓶颈点，即使是用linux的sort进行归并也要花2min+，更不用说一次次地写读了）

代码实现：待完善！

。。。