巨大テキストファイルをsortコマンドでソートしてみる

巨大なテキストファイルをソートする問題について、sortコマンドの挙動を中心にAmazon EC2インスタンス上で検証を行いました。その結果を記事にまとめたものです。

お題の説明

先日のTwitterでこんな話題がありました。論旨としては、非常に大きくメインメモリに収まらないサイズのテキストファイルをソートしたい場合にどうすればよいか、というものです。

https://twitter.com/ebiebi_pg/status/1564814296651280384

解法はさまざまなものがありえると思いますが、この記事ではsortコマンドによるソートを試してみました。

一般論としての解法

stackoverflowなどを軽く眺める限りだと「普通のsortコマンドが最良ではないか」「GNUのsortは入力が大きい場合は外部ソートをしてくれる」などの回答が見つかります。

• https://unix.stackexchange.com/questions/120096/how-to-sort-big-files
• https://stackoverflow.com/questions/930044/how-could-the-unix-sort-command-sort-a-very-large-file/930051

この回答は、個人的には納得できるものです。もっとも、2022年現在のハードウェアでも同じ結論になるのか、あるいは具体的にどれぐらい時間がかかるのかは、それほど明らかではないように感じました。

実験

そこで、実際に100GB程度のファイルを作り、ソートしてみます。

• ソートはおそらくCPUもたくさん使うはずなので、CPUがリッチな環境を
• IOもたくさん使うのでファイルはローカルSSDに置くことにしたい

条件に当てはまる環境として、今回はAWSのc6id.4xlargeを使うことにします。Intel系のインスタンスでは記事執筆時点の最新世代(IceLake-SP)で、950GBのNVMe SSDが付いています。一時ファイルを置く領域のことを考えても十分な容量があります。

この記事の執筆時点だと、C6idインスタンスは東京リージョンで利用できませんでした。やむなくオレゴンリージョンで検証を行いました。

（2022/09/19追記） 東京リージョンでも利用可能になっています。
https://aws.amazon.com/jp/about-aws/whats-new/2022/09/amazon-ec2-c6id-m6id-r6id-instances-additional-region/

項目	値
vCPU	16
メインメモリ	32GB
インスタンスストレージ	1x950 NVMe SSD
OS	Ubuntu 22.04 LTS
sort	sort (GNU coreutils) 8.32

検証環境の構築

NVMe SSDを使えるようにするためにはマウント等の処理が要るのですが、難しいことを考えない限りはクラスメソッドの記事のコマンドをそのまま打つだけでいいです。
https://dev.classmethod.jp/articles/howto-ec2-volatile-block-storage-instance-store/

sudo mkfs -t xfs /dev/nvme1n1
sudo mkdir /data
sudo mount /dev/nvme1n1 /data

sudo chown ubuntu:ubuntu /data
cd /data
mkdir part tmp

ダミーテキストの生成

100GBのテキストを準備するのは意外と大変です。
雑なスクリプトだと生成が遅くて困ったので、C/C++でざっと書くことにしました。

#include <iostream>
#include <cstdlib>

#include <uuid/uuid.h>

int main(int argc, char *argv[]) {
  const int n = std::atoi(argv[1]);

  uuid_t uu;
  char buf[37];
  const char *pad62 = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
  for (int i = 0; i < n; i++) {
    uuid_generate_random(uu);
    uuid_unparse(uu, buf);
    std::cout << buf << " " << pad62 << "\n";
  }
}

このプログラムは実行すると、1行100バイト（改行文字含む）の文字列をn行生成します。
先頭フィールドはUUIDで、これをキーにしてソートすることにしてみます。

$ ./a.out 3
dd605a73-b9cc-4d65-a073-10af5751afb1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
683b8f0c-9ce0-435d-a6a3-4a3d9e66f1d0 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
8c9f1c81-fb0c-49dd-a730-a9c27c37d353 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

このコードからダミーテキストファイルを作成しました。

# 104857600 = 1024 * 1024 * 100
$ seq 1 10 | xargs -L 1 -P 10 bash -c './a.out 104857600 > ./part/${BASHPID}.txt'
$ cat ./part/*.txt > input.txt

ソート

ただsortしようとすると上手くいかない

とりあえず素朴にソートしようとしてみます。

$ sort input.txt >/dev/null 
sort: write failed: /tmp/sortIpNTix: No space left on device

ダメそうですね。外部ソートの一時ファイル置き場として、デフォルトだと /tmp を使おうとするようです。

sortのオプションを調整する

改めてsortのドキュメントを眺めてみます。外部ソートの挙動などについて、いくつか指定するべきオプションがあるようです。
https://man7.org/linux/man-pages/man1/sort.1.html

       -S, --buffer-size=SIZE
              use SIZE for main memory buffer
       -T, --temporary-directory=DIR
              use DIR for temporaries, not $TMPDIR or /tmp; multiple
              options specify multiple directories
       --parallel=N
              change the number of sorts run concurrently to N

これらのオプションをいくつか変えつつ、改めてソートを実行してみます。ちなみにsortはロケールを見て動作するようですが今回は単純なバイナリの順序でソートしてもらいます。
今回は未検証ですが、ロケール指定によっては、おそらく比較のためにUTF-8のパースを伴うなどの追加コストが発生するはずです。

$ export LC_ALL=C
$ /usr/bin/time sort -k 1,1 --temporary-directory=/data/tmp --parallel=16 --buffer-size=28G input.txt >/dev/null
1484.96user 136.13system 9:12.45elapsed 293%CPU (0avgtext+0avgdata 29362408maxresident)k
421364360inputs+210662032outputs (11major+14680424minor)pagefaults 0swaps

成功するようになりました。maxresidentの値を見るに--buffer-sizeをちゃんと守ってメモリアロケーションを行っている様子も見て取れます。

一時ファイルの中身

もう少し細かく様子を見ると、一時ディレクトリの中ではせっせと一時ファイルが作成されています。中身はそれぞれがソート済みのテキストでした。これらを最終的にマージして出力するのかもしれません。ちゃんと確認するためには、本来ソースを読むべきだと思いますが……。

ls -lha tmp/
total 44G
drwxrwxr-x 2 ubuntu ubuntu   96 Sep  1 12:57 .
drwxr-xr-x 4 ubuntu ubuntu   75 Sep  1 12:34 ..
-rw------- 1 ubuntu ubuntu  11G Sep  1 12:56 sortIJTVGd
-rw------- 1 ubuntu ubuntu 351M Sep  1 12:57 sortOBbBLP
-rw------- 1 ubuntu ubuntu  11G Sep  1 12:57 sortSvXvZC
-rw------- 1 ubuntu ubuntu  11G Sep  1 12:55 sortVyTrLg
-rw------- 1 ubuntu ubuntu  11G Sep  1 12:56 sortqu5zk1

$ head -5 tmp/sortIJTVGd 
00000048-10d4-4fb7-bc1e-73b44b46954f xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
000000c0-5c46-481d-b410-17969b54e706 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000178-398d-468d-8bca-7aa60e677f9a xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000180-15f3-46b6-8818-99aa544944d1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
000001a7-4590-4d1c-85d3-b7c877fa9c4a xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
$ head -5 tmp/sortSvXvZC
0000003c-0ca5-425a-9320-bcd622d6a573 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
0000003e-c992-461e-a4a4-83191f076741 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000064-bd9b-4c40-9264-c58335fa3386 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000082-d6f3-40cf-9418-652b776275be xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
000000a9-fe84-4f40-90b9-50ce4052751a xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

オプションの影響

最後に--parallelや--buffer-sizeが性能にどれぐらい寄与しているかを確認します。

sort -k 1,1 --temporary-directory=/data/tmp --parallel=16 --buffer-size=28G input.txt >/dev/null を基準に --parallelや--buffer-size の値を変えてみて、実行時間の比を取ってみます。

--parallel	--buffer-size(GB)	実行時間（秒）
16	28	621.99
8	28	646.41
4	28	776.79
2	28	1046.88
16	16	767.81
16	8	742.88
16	4	737.41

parallelによるマルチスレッド化は効いています。ただし、多スレッドでもスケーラビリティが良好とまでは行かないようです。--parallel=8よりさらに盛っても性能向上はそれほど望めなさそうな様子が見て取れます。
実際、プロセスの挙動を観察していても、シングルスレッド動作していると思われる区間がかなり長いように見えました。

buffer-sizeは、測定上の問題があるのかあまり一貫した結果を示しませんでした。parallelと上手く釣り合うように選ばないといけないのかもしれません？

---

（2022/09/03追記）GNU Coreutilsのドキュメントを見ると、--parallelの値は8に制限されているとの記述がありました。測定上も8と16にほとんど差がないように見えるのは、測定誤差以上の意味がなかったかもしれません。

Set the number of sorts run in parallel to n. By default, n is set to the number of available processors, but limited to 8, as there are diminishing performance gains after that.
https://www.gnu.org/software/coreutils/manual/html_node/sort-invocation.html

結果についてのまとめ

巨大なテキストファイルに対してsortコマンドを使ってみましたが、結果はそれなりに良好でした。

• 比較的巨大（10億行・100GB程度）なテキストファイルをソートするのにsortコマンドを用いるのは現実的だった
  • 今回の条件だと、10分程度でソートは完了しそうだった
• オプションには多少注意が必要だった（特に --temporary-directory は高速で空き容量のあるディレクトリを指定しなければならなかった）

確認した限りにおいてマルチコアによる並列化は、効いていますが限定的でした。今回のインスタンスはそれなりに強力なものを選びましたが、さらに強力なマシンを使ったとしても劇的に速くなる事はなさそうです。

また、メモリは多くて悪くなることはあまりなさそうですが、どれぐらいあると適切なのかは、今回の調査だと判然としませんでした。

留意事項

実は元のツイートだと、フォーマットとしてCSVが想定されています。よく知られているように、CSVはそれほど単純なフォーマットではないため、sortコマンドが常にうまく適用できるとは限らないとは思います。

もうひとつ「そもそも本当にソートがしたいのか」は、解きたい問題によっては要確認かなと思いました。例えば、テキスト全体から見てごく一部である上位k件が欲しくて、そのためにソートをしているのだとします。

# 例: 辞書順に並べた時に上位10件を出力
sort input.txt | head -10

このとき全体をソートするのではなく、メモリに収まるように分割したそれぞれの範囲で上位k件を抽出した上で、改めてそれらをソートするほうがずっと効率的なはずです。

つまり、単純にsortコマンドを使うのはあまり効率的ではないかもしれません。例えばデータウェアハウス製品などは、この種の処理を単純なソートよりずっと上手く扱えることが多いと思います。

参考資料

• https://stackoverflow.com/questions/930044/how-could-the-unix-sort-command-sort-a-very-large-file/930051
• https://dev.classmethod.jp/articles/howto-ec2-volatile-block-storage-instance-store/