RAMに収まらない大容量ファイルを`sort`コマンドでソートする

はじめに

仕事で非常に大きなファイル(10GB)をソートする必要がありました。

ただし、データ容量が大きいためRAMに乗らず、 /tmp に大量の一時ファイルが配置されてしまい、ディスク不足で何度もハングしてしまいました。ハングしなかったとしても処理時間が大量にかかってしまっていました。

うまい方法がないかを試した結果を共有します。

※大量データを sort コマンドでソートするという方針がそもそも、という意見もありますがリソース不足（金、モノ、時間）でこの方法を取ることになりました。

検証環境

1
2
3
4
5
6
7
8
$ uname -moi
x86_64 x86_64 GNU/Linux

$ bash -version | head -n 1
GNU bash, version 4.2.46(2)-release (x86_64-redhat-linux-gnu)

$ sort --version | head -n 1
sort (GNU coreutils) 8.22

準備

ソート対象となるデータファイルを作成します。業務で問題になったファイルサイズ（10GB）と比べると可愛いサイズとなっています。

1
2
3
4
5
6
7
8
9
$ for i in $(seq 1 50000000); do
  echo $RANDOM
done >target.txt

$ du -hs target.txt
512M    target.txt

$ wc -l target.txt
50000000 target.txt

単純にソートしてみる

単純にソートしてみます。

3回試行してみることにします。

データ容量が大きすぎる場合には処理が終わらない、Swap領域不足になる、メモリ不足で落ちるなどが起こりえますが、今回はソート可能な容量ですね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
$ time bash -c "cat target.txt | sort > 1-1.txt"
real    1m58.322s
user    1m57.123s
sys     0m1.321s

$ time bash -c "cat target.txt | sort > 1-2.txt"
real    1m57.561s
user    1m56.348s
sys     0m1.333s

$ time bash -c "cat target.txt | sort > 1-3.txt"
real    1m57.741s
user    1m56.614s
sys     0m1.248s

# 念の為出力されたファイルに差分がないことを確認
$ diff 1-1.txt 1-2.txt
$ diff 1-2.txt 1-3.txt

分割してソートしてみる

こちらが大量データをソートするときに利用した方法です。

先程同様3回試行してみることにします。

処理が長くなっていますが簡単に説明すると以下のような処理になっています。

target.txt ファイルを split コマンドで分割（ここでは 5000000 行ごとに分割）
分割ファイルを個別にソート( ここではバックグラウンドで並列実行 )
子プロセスが終了するまで待つ
ソート済みの分割ファイルをマージソート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
$ time bash -c '
split -l 5000000 target.txt splitted-target.txt
for FILE in splitted-target.txt*; do
  sort <$FILE >sorted-$FILE
done
wait
sort -m sorted-splitted-target.txt* >2-1.txt
'

real    0m34.539s
user    4m8.908s
sys     0m2.474s

$ time bash -c '
split -l 5000000 target.txt splitted-target.txt
for FILE in splitted-target.txt*; do
  sort <$FILE >sorted-$FILE &
done
wait
sort -m sorted-splitted-target.txt* >2-2.txt
'

real    0m35.166s
user    4m9.946s
sys     0m2.658s

$ time bash -c '
split -l 5000000 target.txt splitted-target.txt
for FILE in splitted-target.txt*; do
  sort <$FILE >sorted-$FILE &
done
wait
sort -m sorted-splitted-target.txt* >2-3.txt
'

real    0m35.083s
user    4m9.716s
sys     0m2.562s

# 念の為出力されたファイルに差分がないことを確認
$ diff 1-1.txt 2-1.txt
$ diff 2-1.txt 2-2.txt

「バックグラウンドによる並列処理が効いたのでは？」 という声も上がりそうなので、並列処理なしの場合も計測してみます。

実はそれほど大きな処理時間の差はありません。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ time bash -c '
split -l 5000000 target.txt splitted-target.txt
for FILE in splitted-target.txt*; do
  sort <$FILE >sorted-$FILE
done
sort -m sorted-splitted-target.txt* >2-4.txt
'

real    0m43.568s
user    3m53.489s
sys     0m2.438s

$ time bash -c '
split -l 5000000 target.txt splitted-target.txt
for FILE in splitted-target.txt*; do
  sort <$FILE >sorted-$FILE
done
sort -m sorted-splitted-target.txt* >2-4.txt
'

real    0m43.697s
user    3m54.126s
sys     0m2.433s

まとめ

それぞれのソート方式にかかる処理時間は以下の通りでした。

各ソート方式の処理時間

試行回数	単純ソート	分割ソート(BG)	分割ソート
1回目	1m58.322s	0m34.539s	0m43.568s
2回目	1m57.561s	0m35.166s	0m43.697s
3回目	1m57.741s	0m35.083s	-

ちなみに、1回しか試行していませんが、

分割ファイル数を 0.25 倍の 2500000 にした場合の処理時間は 0m43.815s
分割ファイル数を 2.00 倍の 10000000 にした場合の処理時間は 1m19.897s

となりました。

最適な分割行数をどうやって特定するかは悩みどころ。

ひとこと

速度的な話にとどまりましたが、大量データがメモリ不足やスワップ不足でソートできないときにお使いください。