短時間ジョブのスループットについてのシンプルな実験

背景

ビッグデータという言葉もそろそろ使い古され、耳にする機会も減ってきた気がしますが、そういう分野がなくなってしまったわけではなく、そうしたサイズのデータを扱うことが当たり前になったという解釈が妥当そうです。実際、ビッグデータという単語を聞かなくなったこととは裏腹に、これまで得られた多数の計算結果を網羅的に統計処理をしたり、データ間の相関を取るなど、直接計算結果を得ることの先の業務が必要になって来ていると、よく耳にするようになりました。その分析にAI的な手法を用いることで効率的に目的（予算の獲得ではなく・・・）を達成できることもあるようですが、コンピュータ資源の利用方法が従来と大きく変わったことで、システムが全く機能しなくなるといった事例も枚挙に暇がありません。

並列計算を何時間、時には何週間も回して結果を得ることが目的だった計算機を持ったユーザーが、多数の細かいデータを秒単位で処理していくようなジョブが必要となった場合に、どのようなことが起きるのか、考えてみたいと思います。

簡単な実験

手元に1000個のテキストファイルがあり、リファレンスである1000個のデータと相関を取るというミッションがあるとします。ここでは簡単にリファレンスのファイルの持つ文字列（数文字）が、データ（約２００KBのシステムログ）に含まれているかを検索するということを考えてみます。シェルスクリプトに慣れている人であれば、以下のような感じで実現できると考えるかもしれません。

for REFFILE in $(ls ref/*) ; do
  for DATA in $(ls data/*) ; do
    grep $(cat $REFFILE) $DATA > result/${DATA#data/}-${REFFILE#ref/}.result
  done
done

実際に個別にこれをやってみると、少なくとも１つ１つの処理は数十m秒で終わります。

# echo 3 > /proc/sys/vm/drop_caches　＃ OSのキャッシュをクリアしています。
# time grep $(cat ref/ref0001 ) data/data0001 > result
 real 0m0.025s
 user 0m0.001s
 sys 0m0.013s
# echo 3 > /proc/sys/vm/drop_caches
# time grep $(cat ref/ref0500) data/log.0001 > result
 real 0m0.074s
 user 0m0.000s
 sys 0m0.017s

さて、スクリプトのトータルの実行時間はどの程度になるでしょうか？上記のまま実行するとgrepとcatをそれぞれ１００万回ずつ起動し、ファイルを２00万回開いて読み、結果ファイルを100万個作成することになります。単純に全ての処理に上記の実行時間が必要だとすると25000〜74000秒つまり8〜20時間以上かかることになります。しかしよく見てください。userが1m秒以下となっており、実際の検索にはCPUはほとんど使われていません。繰り返しのアクセスにはキャッシュの効果もあるはずです。

どのようにするのが効率的か、実際にどれくらいまで速く処理できるのか、まずは想像してみてください。

ベンチマーク

効率的な実行方法を確認するため、とりあえず問題のサイズを1/100にしましょう。リファレンスもデータも100個ずつに減らして、処理の回数を10000回とします。すると、このスクリプトは50秒弱で終わりました。

# time ./run.sh
 real 0m48.299s
 user 0m16.243s
 sys 0m35.879s

比較ベンチマークのためスクリプトの先頭にだけキャッシュのクリアを含めています。ループにすると、キャッシュの効果などで一つの処理時間は平均5m秒となりました。１秒間に200個処理でき、元の数量でも１時間半もあれば終わることになります。

あらためてスクリプトを見ると、リファレンスのデータを毎回catで展開しています。この処理が終わった結果をもってgrepが実行されます。これはループの外に出しましょう。catの実行回数が1/100に減ります。

for REFFILE in $(ls ref/*) ; do
  REF=$(cat $REFFILE)
  for DATA in $(ls data/*) ; do
     grep $REF $DATA > result/${REFFILE#ref/}-${DATA#data/}.result
   done
done

なんとこれだけの変更で実行時間は４割減ります。

# time ./run.sh
 real	0m28.520s
 user	0m10.560s
 sys	0m19.783s

この結果をもって、ファイルアクセスがボトルネックだと予想した人もいるかもしれません。リファレンスファイルへのアクセスが減ったのが原因だと思った方、いらっしゃいますよね？では環境をRAMディスクである/dev/shmに移動して実行してみましょう。

# time ./run.sh
real 0m27.026s
user 0m10.618s
sys 0m18.198s

全くと言っていいほど変わりません。ボトルネックはファイルI/Oではなかったわけです。実際topコマンドで様子を見ていてもusは1%程度、syが2%程度しか消費せず、ioは0%のまま動きません。

さてここで、結果ファイルがデータ毎にある必要がない場合、例えば各リファレンス毎に１ファイルになっていても構わないとします。とりあえずデータファイルを50個ずつまとめてgrepした結果をするようにしましょう。幸いなことにgrepは複数ファイルを検索すると、文字列を見つけたファイル名を先頭に出力するので、後からどのデータにあったのかは情報が残ります。複数ファイルを切り出すギミックが少々複雑なので、ループの内側と外側を入れ替えます。結果の書き込みも追記リダイレクト(>>)に変えます。

ls data/* | xargs -L 50 | while read DATA ; do
for REFFILE in $(ls ref/*) ; do
  REF=$(cat $REFFILE)
     grep $REF $DATA >> result/${REFFILE#ref/}.result
   done
done
# time ./run.sh 
 real	0m2.769s
 user	0m1.724s
 sys	0m0.936s

先ほど４割の高速化に貢献したcatをループ内に戻したにも関わらず、10倍以上高速化しました。ここまでくればボトルネックが何だったのかはすぐわかります。シェルがコマンドを起動するのに一番時間がかかっているわけです。ファイルを50個づつにした結果、grepの起動回数は10000回→200回にまで減りました。1処理あたりの実行時間は14m秒です。起動に食われているのが5m秒とすると、データ1件あたり0.18m秒しかかかっていない計算です。

処理の単位を50個にしたのは、ベンチマークデータが１００個しかないというのもありますが、コマンドラインが長くなりすぎないようにするためです。コマンドラインの長さには上限(getconf ARG_MAXで取得でき、CentOS7やUbuntuでは2097152文字です）がありますので、*でファイル名展開をした結果がその値を超えると、too long argumentsとエラーが出て実行できません。実際にはファイル名の長さなどに合わせて調整します。

さて、このケースでは最内周ループ変数（リファレンス）毎に結果ファイルが作られています。いっそのこと並列で実行してしまいましょう。grep 行の末尾に&をつけ、バックグラウンド実行します。14m秒で終わるgrepがそこそこ同時に立ち上がったところで、昨今のサーバーで大した負荷とはなりえないことは明白です。結果も追記で保存しているので、順番こそ変わっても上書きされたり結果が漏れることを心配する必要はありませんが、念のため最内周ループの外にwaitコマンドを入れ、バックグランド処理が終わるまで待つようにします。

 ls data/* | xargs -L 50 | while read DATA ; do
  for REFFILE in $(ls ref/*) ; do
    REF=$(cat $REFFILE)
    grep $REF $DATA >> result/${REFFILE#ref/}.result &
  done
  wait
done
# time ./run.sh
 real 0m0.609s
 user 0m2.187s
 sys 0m1.046s

なんと1秒かからずに終わってしまいました。当初のスクリプトは50秒かかっていましたから、80倍近く高速化しています。

本番

ではこれで1000×1000のデータ処理を実施してみましょう。ついでにファイル名は十分短いので２００ファイル同時に実行するよう変更して実行したところ、結果は以下のようになりました。

# time ./run.sh
 real 0m7.392s
 user 1m55.028s
 sys 0m48.206s

最悪20時間かかるかもしれないと想定した作業が7秒で終わってしまいました。ここでは1000個のgrepをほぼ同時に起動しているように見えますが、コマンド起動より処理時間の方がはるかに短く、200個同時の処理にかかる時間は40m秒程度と見積もれます。catとgrepを実行するループは1秒に２００回くらいしか回らないため、起動している間にどんどん終わってしまうわけです。実際、この時のtop出力を見ていているとgrepが１０個ほど見えますが、usは41%、syが17%程度。ストレージ負荷も低く、問題は一切起きていません。当然ながらもっと長時間ないし高負荷の処理をする場合や、ここで言うリファレンスのような内周ループの数が膨大な場合、並列数を調整することを検討すべきでしょう。

また、ここではlsを使って都度ファイルリストを作りましたが、実のところ数十万ファイルというような状況では、ls *というのはOSにとってかなり高負荷な処理になります。その場合、リストをあらかじめ用意して読み込むようにしたほうが効率が良いです。特にNFS上で実行することはお勧めできません。

いずれにせよ、今回のような要件で「遅いのはストレージが弱いから」と営業トークを真に受け、オールフラッシュストレージなど購入していたら、大変なコストをかけたにも関わらず何も改善しないという結果になるところでした。

まとめ

ここで行ったのは極めて単純な処理によるボトルネック解析の一例に過ぎず、実際の参考にはならないかもしれません。ただし、データの数、やるべき処理の内容、実行時間、メモリ消費、ストレージ性能、何よりその運用方法によって、システムの性能をきちんと発揮できるケースもあれば、いたずらに時間を浪費しているだけというケースもありえる、ということはご理解いただけたと思います。

また、そうした条件を全て照らし合わせてはじめて、最適なシステム構成の提案ができます。それが出来なければ全方位対応せざるを得ず、コストは青天井となります。一方で工夫だけでは限界があるのも事実で、当然ながら何をやっても本質的に無理というケースも当然あります。

アプリケーションの構造、入力ファイルへのアクセス方法、結果の保存方法、実行時のシステム負荷など、もう一度見直してみると、意外な発見があるかもしれません。最近業務内容・研究内容が変化して、計算機の使い方が変わってきたという方は、ぜひ一度やってみてください。