ディレクトリ内の大量のシンボリックリンクは大量のディレクトリより目立って重い

Unix

概要

ディレクトリにインデックスを持たずエントリをリニアサーチする種類のファイルシステム(BSDのFFSやLinuxのext3)では1つのディレクトリに大量のファイルやディレクトリを入れるのは得策ではない。しかし、そうなってしまうこともある。最近そういう状況になったの際にどのようなことが観察され、どう対処したか、更に観察内容の理由付けを以下に記す。

環境

ウェブ・アプリケーションがRedHat Linux上のApache 1.3+mod_perlで動いていて、データがNetApp社のNAS(Network Attached Storage)上に置かれている。

観察

1000個のサブディレクトリがあるディレクトリAがあるとしよう。そして100個のサブディレクトリがあるディレクトリBがあるとしよう。

$ ls -F1 A
a0001/
a0002/
a0003/
...
...
a1000/
$ ls -F1 B
b001/
b002/
...
b100/

そして、Bの中でAのサブディレクトリも見えるようにしたいとする。そのためにはBの中にシンボリックリンクを作ることになる。

$ cd B
$ ln -s A/a0001
$ ln -s A/a0002
...
...
$ ln -s A/a1000

こういう状況でA内のサブディレクトリをアクセスするのとB内のサブディレクトリをアクセスするのを比べると、Bのほうが目立って遅かった。尋常でないほどの遅さだった。BをアクセスしているプロセスはI/O待ちが多く、B内にシンボリックリンクがなかったときはロードアベレージが高くても2程度だったものが、シンボリックリンクを加えた結果20程度にまで上がってしまった。一方、Aをアクセスしている同様のプロセスもあり、そちらはそれほど重くない。

AもBもNAS上にある。大量のシンボリックリンクがあると遅くなるのは使っているNASの特性なのかも知れない。NASもLinuxやBSD由来のコードが使われていることが多いので、同様のことはLinuxやBSDでも見られるのではないか。

対策

尋常でない遅さはなんとかしなければならない。そして、BにアクセスしているプロセスがAの内容にもアクセスできるようにしなければならない。そこでどうしたかと言えば、プログラムを変更して、BになければAを見るようにした。こう言ってしまえば簡単だが、既存のそれなりの規模のプログラムだと、実際にはそう簡単でもないこともある。

観察内容の理由付け

以下、観察内容の理由を考えたのだが、十分に理由付けできていない。

B内のエントリの数はAよりたかだか1割多いだけである。なぜそれほどまでにBをアクセスするプログラムは遅くなったのか。シンボリックリンクの格納のされかたに起因しているはずである。

ディレクトリとはエントリ(ファイルまたはディレクトリ)の文字列と、エントリのiノード番号の一覧を格納したファイルである。

ディレクトリA:

エントリ名 iノード番号
a0001 3152
a0002 48592
... ...
a1000 38429

上記はファイルあるいはディレクトリがディレクトリ内にある場合で、シンボリックリンクはその文字列がディレクトリ内に記録される。

ディレクトリB:

エントリ名 iノード番号/リンク先
b001 12742
b002 47281
... ...
b100 82731
a0001 A/a0001
a0002 A/a0001
... ...
a1000 A/a1000

iノード番号は整数値で、通常は4バイトだろう。一方、シンボリックリンクの場合は、iノード番号の代わりにその文字列がそのまま入り多くの場合4バイトよりずっと多くなるはずだ。しかし、実際に比較してみると、AとBとで大きさに目だった差はなかった。Bのほうがずっと大きいだろうと予測していたのだが、当てが外れた。実際のディレクトリの大きさは約80Kバイトだった。

ディレクトリにインデックスを持たないファイルシステムではこの一覧がリニアサーチされる。ディレクトリがアクセスされるたびに、ディレクトリの内容が読み込まれてリニアサーチされる。1000個ものエントリがあると、そのリニアサーチに要する時間がばかにならなくなる。そして、大量のシンボリックリンクがあるディレクトリでは、そのリニアサーチにより多くの時間がかかっていることになる。

ファイルシステム上でのディレクトリデータの大きさはAとBとで同程度ではあるが、実際にそこからエントリを探し出すには、まずメモリに読み込まなければならない。メモリ上に置くべきデータはシンボリックリンクのほうが本質的に多い。リンク先の文字列は可変長なので固定長のiノード番号を扱うよりは複雑なはずである。これらの理由によりBのほうが処理にずっと多くの時間を要するのではないか。