sort コマンドで大容量テキストをソートする

概要

テキストをソートする sort コマンド. 気軽に使えて優秀なコマンドだが, 大容量のデータに耐えられる 点も魅力の一つである. 本稿ではこのポイントを紹介したい.

確認環境

以下の sort コマンドの挙動を Mac OS X 上で確認した. 本稿のコマンド例はすべて GNU coreutils sort を用いたものである.

• GNU coreutils 8.31
• 2.3-Apple

大容量のテキストをソートしてみる

sort コマンドは, かなり大容量のテキストを入力してもソートを完遂することができる. 完遂するという要件を満たすだけであれば, マシンスペックにほとんど依存しないことがポイントだ. 試しに大容量テキストをソートしてみよう. 以下に 10,000,000 レコードの乱雑なテキスト ¹ をソートする例を示す.

$ time (base64 /dev/urandom | head -n10000000 | sort > /dev/null)

real    7m42.519s
user    7m13.398s
sys     0m28.383s

やや時間はかかるが, 問題なくコマンド終了するはずだ. 同時にメモリ使用量をチェックしてみてもよい. 1000 万レコードのソートにも関わらず, 驚くほどメモリを使用しないことがわかるだろう.

多くのソート処理は事前にリストアップされたデータを前提としており, 空きメモリ量を上回るサイズのデータをソートすることはできない. 一方で sort コマンドは, 空きメモリ量の制限を上回るデータをソートできる という大きなアドバンテージを持っている.

大容量データをソートすることの重要性

ソートされたデータに対するアルゴリズムは多い. 二分探索 は代表的な例だろう.

他によくある例として, 特定のキーによるグルーピングや, 複数データの結合が挙げられる. いずれも一度全データを展開したり, インデックスを作成したりといった前処理が必要そうに思えるが, 実は入力がキーでソートされていれば展開せずに逐次処理が可能だ. 特にデータの大容量化が著しい現代では重要なテクニックだろう.

ちなみに Python の例になるが, ソートされたデータを前提としたグルーピングは, 標準ライブラリの itertools.groupby に採用例がある. 結合処理の実装としては, 手前味噌で恐縮だが reltools というパッケージを公開している.

なぜ耐えられるのか？

ソートアルゴリズムに精通した読者ならお気づきかもしれないが, 大容量データに耐える秘密は マージソート を採用している点にある.

sort コマンドはメモリ上に一定サイズのバッファを持っている. バッファがいっぱいになるとバッファ中のデータをソートして, 一時ファイルとして出力する. 入力が完了すると, ソートされた一時ファイルを順にマージして, 最終的なソート結果を出力する. マージソートと一時ファイルを組み合わせ, メモリ使用量を限定する好例だ.

実際に大容量テキストをソートしながら一時ディレクトリ以下の様子を観察すると, イメージが持てるだろう.

$ ls -l ${TMPDIR:-/tmp}

チューニング

実装系によってはバッファサイズの変更も可能で, 今回確認した環境では -S ないし --buffer-size オプションで変更可能だった. メモリを潤沢に利用できる環境では, 大きめの値を設定することで高速化が狙えるかもしれない ².

$ time (base64 /dev/urandom | head -n1000000 | sort > /dev/null)

real    0m37.897s
user    0m35.318s
sys     0m2.693s
$ time (base64 /dev/urandom | head -n1000000 | sort -S256M > /dev/null)

real    0m16.930s
user    0m59.136s
sys     0m0.232s

なお, 入力ファイルパスを指定してソートした場合, メモリ使用量が増加する代わりに一時ファイルを利用しにくくなり, 結果的に処理時間が短縮する結果を得られた. ファイル指定の場合は入力データサイズが予め分かるため, バッファサイズが暗黙的にチューニングされたのではないか, と推察している.

$ time (base64 /dev/urandom | head -n1000000 > large-text.txt)

real    0m2.533s
user    0m0.448s
sys     0m2.443s
$ time (sort large-text.txt > /dev/null)

real    0m17.172s
user    0m59.369s
sys     0m0.250s

「大容量」データをソートできると述べてきたが, 上記の実装を踏まえると, sort コマンドでソートできるデータ容量の限界値は, 一時ファイル出力先ストレージの空き容量がおおよその目安となる. 一時ファイルの出力先は -T ないし --temporary-directory オプションで変更可能だ. 高速なストレージが用意できる場合や, より大きい領域を利用したい場合は, 変更するとよいだろう.

まとめ

sort コマンドは大容量テキストのソートが気軽にできる懐の深さを持ち, 現代の大容量テキスト処理に耐えうるポテンシャルを持っている. sort コマンドが利用できない環境においても, sort コマンドのアプローチを思い出すことができれば, 技術選択の引き出しも増えることだろう.

1. 大容量データの生成処理は LinuxやMacで任意のサイズの「テキスト」ファイルを作る方法 を参考にした. ↩

2. ストレージの利用がボトルネックになっている場合に限る. チューニングの鉄則は 予測するな, 計測せよ である. ↩