射撃しつつ前転

ディレクトリの中にある大量の小さなファイルを高速に読み込む方法

　ディレクトリの中にある大量のファイルを高速に読み込む方法が知りたかったので、実験してみた。想定しているシチュエーションは、一つ一つのファイルは数KB程度だが数が多い、という場合である。適当な順番でアクセスすると、ランダムアクセスになってしまいとても時間がかかる。個々のファイルを読み込む順番はどうでも良く、すべてのファイルを処理することさえできればいいので、原理的にはシーケンシャルアクセスで処理できてしかるべきである。

　まず、ファイルシステムについて。HDDやSSDなどのハードウェアにアクセスする際には、ファイル名などという概念はもちろん存在しない。ファイル名と実際のディスク上の対応を管理するのがファイルシステムの主な役割である。ファイルシステムは、ファイル名からそのファイルに対応するブロック番号（メモリアドレスみたいなもんだな）を調べて、そのブロック番号を指定してHDDやSSDにアクセスする。セクタとかシリンダとか、そんな概念はどこにいったのかと、高校生の頃にDOS/Vマガジンで読んだ知識が疑問を投げかけてくるが、その疑問は放置して先に進むことにしよう。

　このブロック番号が近い順に並べてアクセスすれば、読み取りヘッダを移動させる時間が減るので、読み取りが高速に行える。本当にシーケンシャルにアクセスしたければ、ブロック番号からディスク上の物理的位置を推測してアクセススケジュールを組み立てたりするべきだが、そういうことを考え出すと1日仕事ではとても終わらないし、とりあえずはブロック番号でよしとする。

　ディレクトリは、ファイルシステム上での実際の扱いとしては一種のファイルみたいなもので、ディレクトリ毎に、ファイル名とそのファイルがどのブロックにはいっているかを表現する領域がある。（より正確にはファイル名とinodeの対応、でいいのかな。）これをディレクトリエントリという。

　ディレクトリの中にあるファイル名のリスト（実際に線形リストで表現される場合もあるし、B-treeとかで表現される場合もある）になにも考えずにアクセスするとそれがそのままシーケンシャルアクセスになっていると、こんな面倒な事を考えなくていいのだが、実際にはそれではシーケンシャルアクセスにならないようだ。考えてみれば、ファイルシステムがデフラグを行うときに、ブロックを移動させる度にいちいちディレクトリエントリ内のファイル名リストを並べ替えるだなんてめんどくさい事をしているような気がしない。ということはシーケンシャル性を保証するようなことはやらないだろう。

　システムが自動でシーケンシャルアクセスにしてくれないのならば、残された可能性は自分でディレクトリエントリを読んで、ファイルアクセスをできるだけシーケンシャルにできるようにソートすることだけである。しかし、ファイル名からそのファイルに対応するブロック番号をどうやって手に入れたものかがわからない。fsckとかではブロック番号が出てきたりするし、ファイルシステムは絶対に知っているはずの情報なわけだが、どうやればファイルシステムに依存せずにこの情報を取得できるのか。

　検索しても皆目検討がつかず、ここで一旦お手上げとなったのだが、そういえば昔readaheadで起動を早くする、みたいな話題があったなぁということを思い出してシステムコールじゃない方のreadaheadのコードを読んでみた。するとブロック番号を取得するっぽいコードがあった。以下に一行引用する。

int ioctl_ret = ioctl( fd, FIBMAP, &block );

　FIBMAPというのが何を意味するのか分からないが、ここが重要らしいので検索してみると、ユーザースペースでのI/Oスケジューリングという、完全に目的と合致する記事が見つかった。上でいろいろ自分でぐちゃぐちゃ考えたり調べたりしてたのはなんだったのだろうか…。

　後はこの記事を読めば完全な説明が載っている訳だが、実験とかしてみたいので話を続ける。記事内容を簡単に要約する（連載記事で他の回もおもしろいので、ぜひリンク先も読むべきですが）と

• ディレクトリが同じだとディスク上で近い位置に配置されやすいので、同じようなタイミングで読むファイルは同じディレクトリに入れる（今回の問題の解決にはあまり役立たなさそう）
• inode（ファイル毎のメタデータを置く領域みたいなもの。使わないファイルシステムもある）番号の大小と物理ブロックアドレスの大小が一致するなら、inodeの値でソートしてアクセスすればいい。
  • ext2やext3（ext4も？）ではこの仮定は正しいそうだ。それら以外のファイルシステムについては、「iノード番号が優れた一次近似であることは確かです。」と、仮定が正しいのか正しくないのか断定を避けているので、そういうことなのだろう。
• ioctl( fd, FIBMAP, &block ); は、blockに論理ブロック番号（0からファイルが使うブロック数-1までの整数。ファイル自体はfdで指定される）を入れて呼び出すと、&blockに物理ブロック番号を入れて返すので、これを使うとブロック番号が取れる。ただし、実行には事実上root権限が必要である。

　ということで、最終的な調査の結果としては、ブロック番号を取るためにはroot権限が必要、という結果になった。root権限が必要なのではあまりにも使いにくいので、inodeを使う手法を実験してみることにしたい。

　と言うわけで、実験用のコードを書いてみた。実験用と言いつつ、ツールとして実際に使いたい用事があるのでちょっと頑張って書いたら100行を越えてしまった。Cだとやっぱり、コード量が膨らむなぁ。

　dirdump.cがやることは、プログラムに引数として与えられたディレクトリに入っているすべてのファイルを実際に開いて読み込む事である。なにもオプションをつけない場合は、ファイルを開いた後にinode順にソートして、シーケンシャルに読み込もうとする。最後に--nosortというオプションをつけるとソートせずに読み込みを行う。

　実験環境はCPUがCore2 Duo 2GHz, HDDはよくわからないが2.5インチであまり早くない感じで、要するに2007年発売のmacbookにLinuxを入れたものだ。ファイルシステムはext3を使っている。

　ファイル数 57000、平均ファイルサイズ 4.3KBのデータに対してdirdumpを実行すると、以下のような結果が得られた。

./dirdump data  0.26s user 6.43s system 18% cpu 36.962 total
./dirdump data --nosort 0.40s user 9.28s system 1% cpu 14:08.45 total

　36秒と850秒という、圧倒的な速度差（23.6倍！）が得られた。実験中にiotopを見ていると、シーケンシャル読み込みの方は6〜15MB/secぐらいの速度を出しており、ノートPCの2.5インチHDDとしてはかなり理想に近い速度が出ていると思う。全部ファイルをくっつけてcatしても11.4秒 (21MB/sec) かかるし。

　ということで、inode番号はext3ではブロック番号の近似として十分に使え、inode番号でソートすることで、ファイル数が多い場合のディレクトリ内のファイル読み込みを高速化することができた。

　また、この実験結果からではわからないが、readdirに6,7秒程度の時間がかかっている。この部分の時間短縮できるかどうかは、今後の課題である。ディレクトリエントリをシーケンシャルに読み込むことができればいいと思うんだけど、どうやればいいのかな。単純に "." を読み込んだりするだけで良かったりするんだろうか。

　dirdumpは基本的にはベンチマークプログラムだが、特定の状況下ではツールとして使える。つまり、合計数百MBぐらいのサイズの小さなファイルの集合をこれから読み書きしたい、というときにdirdumpをそのディレクトリに対して適用すると、catするよりも高速にOSのディスクキャッシュに載せることができる。一旦ディスクキャッシュに載ればそもそもディスクアクセスはまったく発生しないので、ディスクアクセスの大幅な高速化が見込める。

　追記：ReiserFSでも実験してみた。Core2 Duo 3GHz, 500GBの2.5インチHDDの環境で測定した。

./dirdump data  0.08s user 2.76s system 15% cpu 18.867 total
./dirdump data --nosort  0.07s user 3.19s system 0% cpu 6:11.62 total

　ReiserFSでも19倍の高速化！

　さらに追記：実験条件を詳しく知りたい方がいるみたいなので、もうちょっと詳細なデータを追記しておきます。

• ディスクキャッシュは実験毎にディスクキャッシュを簡単にクリアするにメモした方法でクリアしています。
• ファイルサイズは100バイトぐらいから20KBぐらいまでバラバラです。
• HDDについてるキャッシュのサイズは16MBで、実験用のファイルは全部catでくっつけると合計250MBぐらいです。

Permalink | コメント(4) | トラックバック(5) | 09:01