🚀

tar.gzをそのままgrep出来るツールを作った話

2022/10/10に公開約2,000字

TL;DR

tarのgrepを2000倍高速化した

$ time tar xf test_data.tar -O | rg hogeP # 速いがファイル名が分からない
gRRay4bho5P4hZZWvBDCX50cX2fJAyLNhogePvGaFWwaPFdmi3Y8zvJai2OLpQ13+tZB2zm8KbAI

real	0m1.392s
user	0m0.828s
sys	0m1.513s
$ tar xf test_data.tar '--to-command=grep --label=$TAR_FILENAME -H hogeP; true' # ファイル名は分かるがすごく遅い
test_data/863227.txt:gRRay4bho5P4hZZWvBDCX50cX2fJAyLNhogePvGaFWwaPFdmi3Y8zvJai2OLpQ13+tZB2zm8KbAI

real	24m21.333s
user	20m9.365s
sys	4m32.069s
$ tzgrep hogeP test_data.tar # ファイル名も分かるし速い (今回作ったツール)
test_data/863227.txt:gRRay4bho5P4hZZWvBDCX50cX2fJAyLNhogePvGaFWwaPFdmi3Y8zvJai2OLpQ13+tZB2zm8KbAI

real	0m0.644s
user	0m0.475s
sys	0m0.168s

cargo install tzgrep でインストール出来る。
https://crates.io/crates/tzgrep

動機

小さいテキストファイルが大量に(数百万、数千万オーダー)入った.tar.gzに対してgrepをかけようとすると上のようになってファイル名が分からないかすごく遅いということが分かった。かと言って展開するのも時間がかかる上にディスク容量の無駄である。
なんとかならないか調べているとtarファイルの構造は結構単純であることが分かった。
なので、tar.gzをそのままgrep出来るツールを作って見ることにした。

ちなみに --to-command を使うバージョンがなぜ遅いかと言うとファイルごとにgrepコマンドを起動しているためである。つまりgrepの文字検索自体は速いが、コマンドの起動回数が多いため時間がかかっている。
1番目と3番目はそのようなことはしていないので速い。

tarのフォーマット

512バイトのブロックがいくつか連なった形をしている。ファイルごとにヘッダブロックが存在し、それに続いてファイルの中身のブロックが0個以上存在する。tarの末尾2ブロックは0で埋められている。

headerのフォーマット

詳しくは man 5 tar参照

tarと言っても何種類かフォーマットが存在するが、今回はgrepしたいだけなのでnamesizetypeflag だけパースしている。幸いこの3つはどのフォーマットでも位置が変わらないので特に難しいことはなかった。

若干ハマったポイントとしてはsizeなどが8進数のテキストで表現されている点がある。

実装していて気がついたことなど

最初はnomでパースしようと思ったが、欲しい部分は上で書いたように単純だったのとnomの使い方がよく分からなかったので結局自前でパースした。
Readトレイトのtakeを知らなくて自前で同様のことをするstructを実装してしまったが要らなかった。
grepの結果と一緒にテキストファイルの後にNUL文字で埋められている領域も表示してしまっていたが、普通に端末に表示すると表示されないため気づくのに時間がかかった。
tarにバイナリファイルが含まれている場合の処理が少し面倒だった。
圧縮ファイルの展開はそれぞれ簡単に使えるクレートがあったので簡単だった。
clapの#[derive(Parser)]はfeatureを追加する必要があるという所で少しハマった。
zstdの展開が思ってた以上に速かった。

おわりに

tarをそのままgrepする機会があれば是非使ってみて下さい。
バグや要望があれば気軽にissueを立てて下さい。

Discussion

ログインするとコメントできます