fision を inoctl に改名して公開2009年02月15日 11時38分51秒

以前に、同一内容のファイルを単一 i-node にまとめるプログラムを fision と命名して公開した。今回、これを inoctl と改名して、更新版を公開する。

機能は、内容の同じファイルを見つけて、同じ i-node に割り当てる事だ。

実は 2008 年の中頃に再度必要になり、その遅さに嫌気がさしたので、高速化した。線型探索から二分木探索に変えたので、だいぶ改善した。その時に公開するのを忘れてしまった。最近、いじっていたのだが、また更新頻度が減って来たので、忘れないうちに公開する事にしたのが、今回の事の運びだ。

今回の主な変更点は以下の通り。

  1. 高速化
  2. -m link_max
  3. -c cmp
  4. -f file

高速化は既に上で述べた通りだ。

-m オプションで、ハードリンクの最大数を指定できる。以前の版は、この扱いが怪しい部分があったが、これを修正した。同じ内容のファイルを同一 i-node に集める時には問題なく動作する。これは、file1 と file2 の内容が同じときに、file2 を削除してハードリンクに置き換える時の動作だ。

実験的な実装として、-m で指定された最大数よりも多いハードリンクを持つものは、他の i-node に割り当てる機能を実装した。既に全ての i-node が -m の最大値に達している時は複製を作る。もし、file1 と file2 が同じ i-node だとし、inoctl で -m 1 を指定すると、file2 を削除し、cp をすることで i-node の数を下げる。同じ i-node を持つファイル全てが、inoctl に処理される時は問題ないはずだが、一部しか処理の対象として渡されずに、-m の最大数よりも下に減らさなければいけない時の動作に自信が無い。実は、i-node の数を増やしたり、減らしたり出来る様になったので、INOde CoNTrol に改名した。

また、-c を指定すると cmp(1) プログラムを呼び出してファイルの内容を比較する。inoctl はファイルの大きさが同じで、md5、sha1、sha256 の全てが同じ場合に、内容が同一だと認定する。確率的には違うファイルの三つのシグナチャが全て同じになる可能性は低いが、絶対的な確実性は無い。このオプションを使うと確実に検証できるが、その分実行速度は遅くなる。

-f にてファイル名を指定できるようにした。-f - で stdin から読む。find(1) などを使って、予め大きいファイルだけを抜き出しておくのに使う。細かいファイルを集めても回収できる容量が少ないが、コマンドラインの引数からは大きすぎて渡せないからだ。

ファイルを削除する動作を伴うので、使う時は -n で何が起きるのかを正しく把握してから使って頂きたい。バックアップを取ってからと言いたいところだが、自身でもバックアップを取る容量が無くなったからこのプログラムを作ったので、微妙な立場だ。

前回

fision を高速化2007年06月05日 12時48分04秒

fision: 同一内容のファイルを単一 i-node にまとめるプログラムを更新した。もし、興味のある方は、fision-20070604.tar.bz2 に公開されている。

久しぶりにディスクの容量が、窮地に陥った。消しても、消しても、まだ容量が足りないのだ。そこで、同じ内容のファイルを i-node を同じにして、消してしまおうという魂胆だ。

前回は、実際に動作するのを確認するための作業だったので、非効率なところは目をつぶっていた。今回は、久しぶりに使うとは言え、遅さに閉口したので、高速化を試みた。

このプログラムは、最初に全てのディレクトリを走査して、全てのファイルの名前を探す。その時にファイルは、デバイス ID とファイルのサイズを元に分類される。この二つが片方を削除して i-node を入れ換えるための最低条件だからだ。ここの部分は、単純に配列を作って、新しい組合せの度に最後に追加していただけだった。そのため、検索が遅い。実際に、この部分のディスクの利用率は 1% を切り、CPU が 100% を占めているのだった。

そこで、この部分を新しい対を追加する度に qsort でソートして、bsearch で検索をするようにした。bsearch だけあって、10 倍以上速くなったが、それでもまだディスクの利用率が低い。まあ、一つ新しい対を入れる度に qsort をしているのだから当り前だ。クイックソートは、どの様な値であっても、効率を損なわずに log(N) でソートできる。しかし、既にソートしてあっても、log(N) がかかるのである。ソートするデータに関しての知識が無い場合は、効率がいいのだが、今回の条件には当てはまらない。

そこで更に、binsert を作成。二分木検索で、挿入場所を探して入れる。基本的に二分木検索なので log(N) で済む。qsort から約 N 倍の効率化だ。

これで、ディスクの利用率が最低でも 60% になった。このプログラムは三段階に分かれて実行されるが、第一段階に劇的な効果をもたらした。

もう一つ、気が付いたのが、第二と第三段階でスワップアウトがかなり多い。そこから推測出来るのが、free でメモリを開放した後の NULL の代入だ。もし、一度スワップアウトされたページが、スワップから読み込まれることがある。もし、次にスワップアウトされるまでに、メモリに変更が無かった場合は、わざわざスワップ領域にこのデータを書き込まなくても、既にスワップに残っているので、メモリ上からそのまま破棄できる。これは、システム依存だ。加えて、しっかり free() をしないで終了する行儀の悪いプログラムになってしまう。しかし、その為に延々と待ち続けるのも、時間の無駄なので、free を無効にした。-DFREEをすると、行儀良く free() をするようになる。

もし、興味のある方は自己責任で試して頂きたい。

前回

inode 単一化処理プログラムの更新2006年10月24日 11時34分13秒

内容が同じファイルの inode を同じものに変えるプログラムを更新した。変更自体は少々前に行なったのだが、なかなか時間が取れず遅くなってしまった。自分の欲しかった機能はほぼ実装が終わった。もう少し、修正したい部分も残っている。テストはしているが、誤動作の責任は保証しない。自己責任で試して頂きたい。

Cntl-C を押すと、動作が途中で止まるようにした。また、タイムスタンプをプログラム実行前に戻す機能も動作を確かめた。タイムスタンプの復元を有効にして、Cntl-C を押すと、作業を止めて、タイムスタンプを元に戻した後に終了する。そのため、大量のファイルを扱っていると、終了までに時間が掛かる事になる。kill -KILL なら、その作業無しで強制終了される。

数百 GB 単位のディスクを扱っているとき様の最適化を実験してみたが、全然変わらなかったので諦めた。大量のファイルを扱うと、メモリがたくさん必要になる。

/usr/ports を tar | tar で復元するのと dump | restore で復元するのを比べると、手元の機械では 2 倍以上の差がでる。tar だとディレクトリに沿って処理するので、キャッシュが効くのだが dump だと i-node 順になるらしく、それが足枷になっている。

このプログラムも i-node を元にファイルにアクセスするので、処理速度は遅い。

前回次回

fision の試用2006年09月20日 11時48分00秒

いくつか、バグを修正し fision-20060919.tar.bz2 を公開。まだ、修正したい部分も残っている。今までは、実験用のファイルを作ってのプログラム自体のテストだけだった。今回は使い方次第では、期待通りの動作をさせることも出来るので、試用してみた。動作は安定してきたと思っているが開発版であることは変わらず、他の人の期待した通りの動作をするかは保証できない。

まずは、ディスクの容量が大きく、元々繋がっていた機械の CPU は遅いので、速い機械に繋ぎ直した。メモリは少ないのでスワップは覚悟している。


FreeBSD 6.1-RELEASE #13: Fri Aug 18 19:37:56 EST 2006
...
Timecounter "i8254" frequency 1193182 Hz quality 0
CPU: AMD Athlon(tm) 64 Processor 2800+ (1799.49-MHz 686-class CPU)
  Origin = "AuthenticAMD"  Id = 0xf4a  Stepping = 10
  Features=0x78bfbff
  AMD Features=0xe0500800
real memory  = 268369920 (255 MB)
avail memory = 253120512 (241 MB)
...
ad10: 238475MB  at ata5-master UDMA100

ディスクの容量が約 250GB で、以前に dump と restore をやったときに、利用可能なメモリを拡張する必要があった。今回も同じ事になるのは容易に予想できるので、/boot/loader.conf に以下のように設定する。


kern.maxdsiz="2048m"

そして、ディスクへのアクセスを軽減するために、noatime を有効にして mount する。


# mount -onoatime /dev/ad10s1c /jail
# df -i /jail
Filesystem   1K-blocks      Used    Avail Capacity iused    ifree %iused  Mounted on
/dev/ad10s1c 236511738 234907068 -5490682   102%  889785 29680709    3%   /jail

まあ、こんな感じで、ディスクはいっぱいだ。pdumpfs でバックアップを繰り返していた。時折り、ディレクトリを移動したり、ファイルを移動したりしたので、余計な複製がある。それを取り除こうと思って、プログラムを書いた。


# fision -e -v -v -v -v /jail
...
process domain(101, 18022) 1 files 111933/111936 domains
free domain(101, 18022)
process domain(101, 1026458178) 1 files 111934/111936 domains
free domain(101, 1026458178)
process domain(101, 995335659) 1 files 111935/111936 domains
free domain(101, 995335659)
2nd stage completed: combined same files
3rd stage completed: restored timestamps
50350 files
47601 dirs
38679 linked
8273.085u 852.376s 28:06:33.77 9.0%     16+-1862k 4594526+638io 2845078pf+0w

統計を取るようにしたが、ファイル、ディレクトリ共に数が明らかにおかしい。int が溢れてしまったのだろうか。また、長時間かかるので、進行状況が全然判らないのは不便だ。結構多めにデバッグの情報を出力した。後、数時間で終わりそうなのか、一日以上掛かりそうなのかで、心構えが変わる。結果は御覧の通り、丸一日かかっている。

そして、これが結果だ。


# df -i /jail
Filesystem   1K-blocks      Used    Avail Capacity iused    ifree %iused  Mounted on
/dev/ad10s1c 236511738 206339330 23077056    90%  753188 29817306    2%   /jail

約一割程のファイルが削除され、ハードリンクに変えられた。大体、予想していたぐらいの容量が空けられた。

今回、メモリの利用量は 1.5 GB まで上がった。もし、大型のパーティションに対して実行する場合は参考にして頂きたい。また、今回の試用で、大量のスワップを利用した時の改善点が見えた。

前回次回

バグの修正と、EMLINK に対応2006年09月14日 10時18分44秒

バグが見つかった。fision-20060913.tar.bz2 を公開。まだ、開発版なのは相変わらず。


inode_x* find_inode(domain_x *domain, ino_t st_ino)
{
    inode_x *inode = domain->inode;
    while(inode != NULL)
        if(st_ino == inode->st_ino)
           return inode;
        else
           inode = inode->next;
    return NULL;
}

ファイルの内容は i-node 毎にまとめて保持しているのだが、inode->st_ino を設定するのを忘れていた。かなり、ショックなバグだ。構造体を分割していた時に忘れたのだろう。テストは何回も繰り返したが、問題は表面化しなかった。*inode は calloc で割り当てられるため、st_ino がゼロになっている。もし、i-node がゼロのファイルがあったら、危険なことになる。それ以外の問題としては、同じ i-node のファイルも何度も読み込むことだ。ただ、実験したときの様子だと、少なくても cache はよく効いていたらしい。

また、「実運用していて分かったのは、同じファイルがそこかしこに存在する場合にハードリンク作りすぎてEMLINKで失敗しちゃう可能性があるって事ですな。」との助言を頂いたので、-m link_max のオプションを追加した。-m でこのプログラムが作成するハードリンクの上限を指定する。

FreeBSD では EMLINK の上限は LINK_MAX によって制限されている。他の UNIX でも同じ様だ。なぜ、このように -m link_max を指定するかというと、LINK_MAX までハードリンクを作ると、その後にやる pdumpfs 等で悲惨な事になることが容易に予想できるからだ。-m link_max の初期値は LINK_MAX から適当に算出している。

現時点での副作用としては、ディレクトリの走査の順によっては、この上限以上のファイルがリンクされている時に、このリンクの数が変更されることである。

分かりづらいので例を上げる。A、B、C という同一の inode をファイルがあるとする。そして、a という i-node は違うが、内容は同じファイルがあるとする。-m2 を使うと、最大の i-node 数は 2 ということになる。そのため、A B C a の順で走査すると、B と C は同じ i-node の為に無視し、A と a をハードリンクを試みようとするが、既に A の st_nlink は 3 なので、結果的に何もしない。逆に a A B C の場合は、A を a のリンクにする。そして、a と B を比べたときに同一の内容だと判断するが、既に a の st_nlink が 2 になるためにハードリンクは行なわない。

これに関しては、どの様な動作がいいのか、もう一度考え直す必要がある。他にも、デバッグの出力を調整を始めたが、まだ終わっていない。

前回次回不具合が見つかっています。このバージョンは使わないで下さい。追記

単一 i-node にまとめるの与太話2006年09月07日 15時36分01秒

アクセスが増えたと思っていたらようやく同じ事を考えてる人を見付けたから、結構飛んできているらしい。

思ったことは同じく、「やっと同じことをやった人を見つけた。」Ruby で書かれたディスク領域を圧縮したつもりになれるスクリプトgoogleFreeBSD ports を探した時には、削除するものはかなり見つけたのだがハードリンクはなかった。

かなり昔から考えてはいたが、実際に動作をするものを書いたのは、今回が最初。実は、最初は Ruby で試したのだが、あまりにも複雑になったため挫折した。始めて書く Ruby だったのも、失敗の大きな原因であろう。mput さんのスクリプトは、私が Ruby で書いたものと比べると、とても簡潔で読みやすい。

何度かあった容量危機は、ディスクの調整や移行、また別の方法でハードリンクへの置換をして、数年の間凌いできた。今回、またディスク利用率が 100% を越えたので、再開した経緯だ。

同じファイルがそこかしこに存在する場合にハードリンク作りすぎて EMLINK で失敗しちゃう可能性があるって事ですな。... EMLINK で失敗したらそれ以上はハードリンクしないような仕組みを入れたほうがいいと思います。
ハードリンクが溢れる件は知らなかった。これは、考慮する必要がある。FreeBSD の man errno には、こう出ていた。

     31 EMLINK Too many links.  Maximum allowable hard links to a single file
             has been exceeded (limit of 32767 hard links per file).


250 GB 以上のディスクで、一千万個のファイルを扱うのが目標なので、ファイルの比較やメモリの管理などは色々と最適化を順次やっているが、まだ目標には届いていない。

なお、私のプログラムの FreeBSD 版は、ファイルのサイズが同じで、ファイルの先頭と末尾の約 512 bytes が同一かつ、 md5、 sha1 と sha256 の全てが同じファイルが出来る可能性は、ゼロだと仮定している。__sun を付けると、sha1 と sha256 が使われなくなるので要注意だ。それゆえ、メモリの利用サイズが多少小さくなる。Solaris に sha が入っていないみたいだったからだが。

前回次回

fision: 同一内容のファイルを単一 i-node にまとめる2006年09月05日 08時12分44秒

pdumpfs を使ってバックアップを取っている。特定の日のファイルを全て、そのままのディレクトリ構造で保存しておきたいからだ。pdumpfs のバックアップは月に一度しかやらないが、ファイルがたまっていく。pdumpfs でも明記されているが、長期にわたって続けていると cp や mv などの影響で複製がどんどん増えていくのも困り物だ。

同じ内容のファイルをハードリンクに変えるプログラムを探したが見つからなかった。同じ内容のファイルを探して、削除するプログラムはたくさん見つかったが。同じ内容だからといって、消されては困るのだ。

そこで、同一内容のファイルを一つの i-node にまとめるプログラムを書いた。指定されたディレクトリ内のファイルの大きさでまとめ、同じサイズのファイルを比較する。もし、ファイルの内容が同じと判定されたら、新しい方のファイルを削除し、古い方のファイルへのハードリンクに変換する。ファイルを同じ i-node に融合、File Inode fuSION をするプログラムなので、取り敢えず、fision と命名とした。fision-20060901.tar.bz2からダウンロード出来る。

まだ、開発版だが GPL で公開することにした。プログラムのオプションは後で、変更する予定である。また、初期の設定では、削除とハードリンクをしないようにしてある。-e オプションを与えると、実際に削除とリンクをする。最初は ffusion でいこうと思っていたが、既にその名前のプログラムが存在したため、性急に改名した。恐らく、プログラムの名前も変えると思う。追記。

大きいディスク上にある大量のファイルに対して、動作させることを目的で始めたが、まだまだ改良の必要がある。今のままでは、まだまだメモリを喰いすぎてしまう。__sun を定義すると、必要なメモリは少なくなるが、恐らく大した違いにはならない。

次回不具合が見つかっています。このバージョンは使わないで下さい。追記