大文件排序优化实践
在很多应用场景中,我们都会面临着排序需求,可以说是见怪不怪。我们也看过许多的排序算法:从最简单的冒泡排序、选择排序,到稍微好点的插入排序、希尔排序,再到有点理论的堆排序、快速排序,再到高级的归并排序、桶排序、基数排序。
而实际工作中我们可能用到的排序有哪些呢?而且,大部分时序,相信大家都是使用一个现有库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+,更不用说一次次地写读了)
代码实现:待完善!
。。。