各種ファイルシステム考察
sodexのファイルシステムを書いていて他の各種ファイルシステムの性能について気になったので速度面について簡単にまとめてみます。(誤りのある可能性が非常に高いので使用する場合は下調べをお願いします）
※sodexのファイル検索はファイル名（ハッシュでは無くそのもの）をキーとした線形探索をしてます。実際のext2,3はハッシュ値を元にした線形探索をしてると思われます。
| ファイルシステム名 | 使用されている主要OS | ファイル検索のアルゴリズム | 検索時間のオーダー | ジャーナリング機能 | 雑記 |
|---|---|---|---|---|---|
| ext2 | Linux | ブロックアルゴリズム | O(n) | × | ほとんどFFSらしい |
| ext3 | Linux | ブロックアルゴリズム | O(n) | ○ | ext3の拡張 |
| ReiserFS | Linux | B*-Treeアルゴリズム | O(log(n)) | ○ | B木を採用した古いFS |
| JFS | Linux | B+-Treeアルゴリズム | O(log(n)) | ○ | |
| XFS | IRIX, Linux | B+-Treeアルゴリズム | O(log(n)) | ○ | |
| UFS | UNIX | ブロックアルゴリズム | O(n) | ジャーナリング同等の機能有 | UNIX系最古のFS? 遅い |
| FFS | BSD,Solaris | ブロックアルゴリズム | O(n) | ジャーナリング同等の機能有 | 現UNIX系OSの原点 UFSより10倍弱速い |
| UFS2 | FreeBSD, NetBSD | ? | ? | ジャーナリング同等機能有 | 現BSD標準? |
| ZFS | Solaris | B Tree系 | O(log(n)) | ○ | 次世代UFS |
| NTFS | Windows | B+-Treeアルゴリズム | O(log(n)) | ○ | windows server標準 |
Linuxで主要に使われているext2,ext3などはブロックアルゴリズムを使用しておりファイル検索がO(n)のため、例えばあるディレクトリにファイル数がO(10^3)のオーダーで存在する場合そのファイル検索には100nsec * O(10^3) ≒ 100μsec(100nsecはメモリへのアクセス時間）ほど掛かってしまう。B木系のアルゴリズムを使っている場合はせいぜい1μsecほどとなる。またファイルが巨大になると、ブロックアルゴリズムの場合は３段階層方式でブロック番号を保存しているのでそのブロックを読み込むだけの時間が余分に掛かる。キャッシュされていない場合はディスクI/Oが余分にmsec単位で必要。
※ただし1ディレクトリ数十ファイル、BLOCKSIZE*11(デフォで40KBほど）のファイルを頻繁に扱うシステムの場合はそれほど顕著な差は出ないと思われます。
B+-Treeアルゴリズムを採用しているファイルシステムではインデックスをメモリ上に置いているので巨大ファイルでも、どこに存在するかがインデックスの検索だけで済むのでブロックアルゴリズムに比べてかなり高速になってそうです。
