「Linuxにおける10億ファイル問題」記事へのコメント

何を今更………

[Anonymous Coward]

遥か昔(ざっと6～7年位)、200GB超のHDDが出始めた頃に、Newsのアーカイブを試みて正にタレコミで指摘されてるような状況になりましたよ
200GBのうち150GBも余っていてで、残りi-node数にも何の問題無い状況でも、何もかもが遅くて使いものにならないような状態になりましたからね
私も初めは、FSの問題かと思っていましたが、XFSだろうと、ReiserFSだろうと、ext[23]だろうと起こる為、これはLinuxの問題と判断し、急遽FreeBSDをインストール、FFS + Softupdateで再びアーカイブを試みましたが、結局Linux同様にどんどんと遅くなっていきました
結局、その時は200GB単一パーティションでの使用を諦め、50GB×4にして適当なディレクトリに振り分けてアーカイブを完了させたのを覚えています

Re:何を今更………

[saitoh (10803)]

もともとのUNIXは一つのディレクトリの中で指定されたファイルを探す処理は、線形サーチなので、1ディレクトリに多数のファイルがあると遅くなりますね。

線形サーチじゃないファイルシステムとしては、ext3(dir_indexオプションをつけた場合)とかXFSはB-treeを使っているそうですが、それでも遅かったんですね。

Re:何を今更………

[jsi (25633)]

FreeBSDでは線形探索の遅さをカバーできるようdirhashが実装されました。ハッシュテーブルのサイズが固定だったりして、必ずしもO(1)のオーダーで検索できない時代もありましたが、今は最適化されてかなり改善されたはずです。ちなみに、ハッシュテーブルの動的な確保は2008年ぐらいの話題ですね。

UFS2 Dirhash、メモリ確保開放動的化でサイズ上限向上 - 性能は不透明
http://journal.mycom.co.jp/articles/2008/10/28/bsdcon3/index.html [mycom.co.jp]

Re:

[Anonymous Coward]

そもそもdir_indexってdirhashの移植、もしくは翻案ですので。

Re:何を今更………

[taka2 (14791)]

メールソフトの MH なんかはフォルダがディレクトリに対応して1メール1ファイルで保存してるので、
一つのフォルダにメールを貯め込みすぎるとすごく遅くなりましたね。

フォルダは階層的に作れるのですが、その処理のためにディレクトリ内にあるディレクトリを全て列挙する場合があって、
メールをたくさん貯め込んだディレクトリでは「サブディレクトリがあるかどうか」を調べるだけでもとんでもなく時間がかかってました。

で、あるとき出た「ディレクトリのリンク数を調べ、それが2だったらサブディレクトリは存在しないのでその下は探索しない」という枝刈りパッチが出て、
劇的に早くなったのを覚えています。あれは感動したなぁ。
#サブディレクトリの無いディレクトリでは、親から自身を指すのと、自ディレクトリ内の . でリンクカウントが2。
#サブディレクトリを作ると、サブディレクトリからの .. の数だけリンク数が増えていく、と。

Re:

[Anonymous Coward]

NTFSなんかは最初からB+ツリーですからね。
当初はLinuxなんかより遥かに進んでた。
なのに馬鹿にされていたNTFSかわいそう。