[OSASK 1699] OSASKの記憶域管理(1).Date: Fri, 04 May 2001 08:12:13 -0000

[Hidemi KAWAI <kawai !Atmark! imasy.org>]

  こんにちは、川合です。

  ファイルの記憶域管理において、DOSやWindowsではFAT16やFAT32やNT
FS、UNIXではi-nodeなどが使われています。OSASKは、もちろんどれで
あっても読み書きできますが、独自フォーマット時の方法はおそらくこ
のどれとも異なる方法です。

  ちなみに、僕はFAT12、FAT16とi-node以外の方法についてはあまり詳
しくありません。したがって、FAT32やNTFSとの比較はしません。

  まず、FAT12やFAT16はかなり頭の悪い方法であると断言します。これ
は、シーケンシャルなアクセスでは十分なアクセス性能を持っているで
しょうが、ランダムアクセスになるとFATをたどっていかなければいけ
ないため、速度が落ちます。

  i-nodeはFATと比べるなら何倍もよいシステムです。ランダムアクセ
スであってもシーケンシャルアクセスであっても、十分に高速なアクセ
スができます。階層構造をとって冗長になるのを回避している点も僕は
高く評価しています。

  OSASKの独自のファイルシステムは、i-nodeの拡張版だと言えます。
それで、i-nodeの説明をしてからその欠点を指摘し、改良案として僕の
案を説明したいと思います。

  i-nodeは、ディスクをブロックの集まりに分解し、そのブロック番号
の連なりを並べたテーブルです。ブロックのサイズは512バイトだろう
と思っていたのですが、これは各UNIXによって違っているらしく、8KB
などもあるそうです。・・・ここでは、このブロックをDOS風に「クラ
スタ」と呼ぶことにします。つまり、UNIXによって512バイト／クラス
タだったり、8KB／クラスタだったりするわけです。

  仮に、クラスタサイズが4KB（OSASKでの基本的なクラスタサイズは4
KBです）で、40KBのファイルがあれば、そのi-nodeには、「10, 11, 1
2, 54, 55, 22, 23, 24, 25, 26」などと書かれていることになります
。これはつまり、

・このファイルの最初の4KBは、第10クラスタに書かれている。
・このファイルの次の4KBは、第11クラスタに書かれている。
・このファイルの次の4KBは、第12クラスタに書かれている。
・このファイルの次の4KBは、第54クラスタに書かれている。
      （以下略）

ということを意味しています。

  さて仮に、4MBのファイルがあったとしましょう。このファイル構造
を記憶するには、1024個のクラスタ番号の列を、メディア内に記録して
おかなければいけません。階層構造をとることを考えればさらに記録す
るべきデーターは増えるでしょうが、それは些細なことなので今は気に
しないことにします。もしこのクラスタ番号が32bitで表現されていれ
ば、この4MBのファイルの構造を記録するために4KBを消費することにな
ります。

  全く同様な議論で、4GBのファイルなら4MBの管理データーが記録され
るでしょう。

  僕は、この4MBが惜しいです（笑）。ファイルサイズに対して0.1％に
もならないかすかな容量です。これくらいなら許容できるという考え方
もあるでしょうし、それは確かにそのとおりだと思います。でも、これ
よりも優れている（と僕は思っている）方法を思い付いてしまったので
、どうしても新しい方法を採用したいんです（笑）。

  簡単に言ってしまえば、この4MBを圧縮してしまおうという話です。

  一般に、このクラスタ番号は連番が続きやすいという傾向があります
。先の40KBの例では、３つの連番のブロックで構成されています。これ
は、むしろ過剰に分割されているケースだと言ってもよいでしょう。か
なり大きなファイルでも、10個以上の連番ブロックに分割されることは
滅多にありません。

  それで、先の40KBの例をそのまま使えば、「0, 10, 3, 54, 5, 22」
という風に記録しようというのが僕の案です。これは、「(0, 10), (3,
 54), (5, 22)」という風に読んでください。２つの数字のうち、最初
の数字がファイル内でのアドレスで、後ろの数字は連番の先頭番号です
。これで、10個の数字が6個の数字に減らせたことになります。

  4GBのファイルがあったとしても、分割数が10程度なら、その管理領
域はたったの80バイトです。4MBに対する圧縮率を議論する気にもなら
ないくらいの高圧縮です（笑）。

  僕は、これで浮いた容量のうちの一部を拡張性に投資しようと考えて
います。つまり、クラスタ番号を64bitへ拡張するわけです（遠い将来
にはそれ以上に拡張してもいいでしょう）。２の64乗は4Gの二乗で、16
エクサにもなります（メガ、ギガ、テラ、ペタ、エクサの順）。この先
数十年はこれで苦労することはないはずです。・・・80バイトが２倍に
なっても、痛くもかゆくもないです（笑）。

  ちなみに、i-nodeの方法やFAT32の方法では、クラスタサイズが4KBだ
とすると最大で16TB（テラバイト）までしか扱えないことになります。
これはもちろん途方も無い数字ですが、現時点で160GBを超えるHDDが既
に存在しています。ということはあと100倍前後しか余裕がありません
。100倍進化するのにどれだけ時間がかかるでしょうか？1.6GBが最大容
量だった時代が何年前かを思い起こせば、100倍進化するのにかかる時
間はたいしたことないということが分かっていただけるのではないでし
ょうか（僕は５年くらいだと思っています）。・・・もちろん、クラス
タサイズを増やすという方向で対処することもできるでしょう。しかし
1クラスタ1MBとかになったら、僕はすごくいやです（笑）。

  圧縮をかけるということは、アクセスが複雑になるのではないかと思
う人もいるかもしれません。しかし、ファイル内のアドレスはソートさ
れて並んでいますから２分検索で検索でき、分割数の対数に比例する程
度で、はっきりいって問題外です。圧縮されたテーブルを展開してアク
セスしようなどとは考えていません。テーブルを格納するためのメモリ
領域は節約されるでしょうから、メモリは相対的に増えることになるで
しょう。このことによりスワップが減り、かえって早くなるのではない
かと考えています。

  もちろん、最悪のケースというものが存在します。最悪のケースは、
クラスタが全く連続していないような場合です。4GBのファイルは、16M
Bもの管理データーを必要とします。これは、ファイルサイズに対して0
4％です。・・・しかし、こういう時こそ、僕はいいます。「0.4％ぐ
らいたいしたことはない」と（笑）。・・・それに、デフラグをかける
などしてクラスタが連続するようにしてやれば、この16MBはそっくり返
ってきます。そんなわけで、僕はこの最悪のケースをあまり深刻に考え
てはいません。

  次回の(2)では、クラスタサイズ4KBに満たない小さなファイルの扱い
の話を書きたいと思っています。いつ書くかは分かりませんが。

---

  以上を今読むと、「近いうちに独自フォーマットがサポートされるの
ではないか？」と期待なさるかもしれませんが、それは無理です（笑）
。今は独自フォーマット用のルーチンを書く余裕がありません。また、
この話が急に出てきたのは、最近になってこの考えがまとまったからだ
と想像されるかもしれませんが、それも違います。この案は数年前から
変わっていません。

  「ではどうして急に？」ということになるのですが、まあ、プログラ
ミングに疲れて、何か書きたくなっただけのことなのです（笑）。

  それでは。

--
    川合 秀実(KAWAI Hidemi)
川合堂社長 / OSASK計画総指揮 / カーネル開発班
E-mail:kawai !Atmark! imasy.org
Homepage http://www.imasy.org/~kawai/