比較項目

Union機能の比較には次のものを用います。Live CDではループバックマウントが用いられますが、ここでは簡略化のため用いないこととします。

1. ext2
2. ext2(RO) + ext2(RW) + aufs
3. ext2 + dm-snapshot

比較方法は次の通りとし、所要時間を計測します。

1. find(1)
2. 既存のファイルに1バイトを追加書きし、copy-upを発生させる。

いづれも小規模に実行しても、短時間すぎて比較しにくいので、充分に時間がかかるように複数回実行することにします。カーネルバージョンは2.6.33とします。ハードウェア環境はIntel Core2 Duo 3GHz、4GB RAMです。測定結果を表2に示します。測定スクリプト一式は添付ファイルに含めてありますので、必要に応じ参照してください（union.sh）。

表2：Union機能の比較

	find			copy-up
	usr	sys	elapsed	usr	sys	elapsed
ext2	0.89	1.32	3.02	0.00	0.03	0.36
AUFS	1.13	3.14	5.01	0.00	0.02	0.39
dm-snapshot	0.89	1.29	3.02	0.00	0.02	0.36

ほぼ予想通りの結果ですが、今回の小規模な測定ではファイル数が少なく、またファイルサイズもそれほど大きくなかったためかcopy-upの方では有意な差が確認できませんでした。find(1)の結果はやはりaufsが一番遅く、レイヤ数増加に伴い、時間がかかることが予想できます。 dm-snapshotでも僅かながら時間がかかっており、こちらもレイヤ数増加に伴い遅くなることが予想できますが、aufsよりは大きくないだろうと思われます。

過去のレポート

squashfsは歴史がある分、これまでにも性能比較レポートが何度か報告されています。比較的新しいものでは、 平成21年6月にWenqiang SongがLKMLに投稿した"Squashfs 4.0 performance benchmark"があります。

このレポートではsquashfsとext4をディレクトリルックアップ、シーケンシャルI/O、ランダム I/Oの三点で比較しています。大雑把にまとめると、

• squashfsの速度は ext4と比較し遜色ない、またはより高速である。
• squashfsは CPU(%sys)時間をより多く消費する。
• squashfsはループバックマウントすると更に高速になる。
• システムRAMサイズを制限すると遅くなり、ループバックマウントの場合でも差がなくなる。

また、このレポートで取り上げている比較項目は、更に古い squashfs 2.0、2.1時代のもの（"SquashFsComparisons"。最終更新は 平成20年5月）と同等です。

こちらのレポートでは ext3、iso9660、zisofs（圧縮機能あり）、cloop、squashfs 2.0、2.1を比較しており、総じてsquashfs 2.1が優れている、つまり、より小さく、より高速という結果になっています。よく読むと、前述の"Squashfs 4.0 performance benchmark"と同じ点が目を引き、ext3と比較した場合にやはりsquashfsのCPU（%sys）が大きくなっています。

LZMA対応

正式な対応 squashfsと cloopの圧縮方法には、従来から広く用いられている ZLIBと、比較的新しいLZMAがあります。 squashfsは linux-2.6.34でLZMA対応の実装を試み、一通りは動作しているようです[1][2]。

[1]	http://git.kernel.org/?p=linux/kernel/git/pkl/squashfs-lzma.git;a=summary

[2]	git://git.kernel.org/pub/scm/linux/kernel/git/pkl/squashfs-lzma.git

しかし、 mainlineへの取り込みは見送られ、 2.6.35現在でも取り込まれていません。 LZMA対応は未だですが、LZO対応は2.6.36でmainlineへ取り込まれました。またXZ対応も進められています。

sqlzmaパッチ squashfs開発者以外が行ったLZMA対応は複数知られており、その中でもsqlzmaパッチは広く用いられています[3]。

[3]	http://www.squashfs-lzma.org

sqlzmaパッチは、別途開発された7-ZIP内のLZMAルーチンを採用しています。ユーザ空間のツール用に開発されたコードをカーネルモジュールにすることはそれほど珍しいことではありませんが、C++言語で書かれたLZMAルーチンをカーネルモジュールとして使用するのはかなりの力技です。前述のlinux-2.6.34でのLZMA対応でもやはり7-ZIP内のLZMAルーチンを使用していますが、こちらはC言語で書かれたルーチンを採用しており、そんな力技を用いていません。sqlzmaパッチが何故C++の方を採用したかと言うと、単に当時の7-ZIP内にC言語で書かれたルーチンがまだなかったというだけのことです。

また、sqlzmaパッチはハイブリッド方式を採用しています。一般に圧縮処理は、ランダムデータやバイナリファイルに対しては有効ではない場合があり、結果サイズが大きくなってしまうこともあります。ZLIB、LZMA複数の圧縮方式が同時に使用可能な環境では小さくなる方を採用したいところですが、どちらの方が小さくなるかは実際に圧縮してみなければ分かりません。このためsqlzmaパッチは、squashfsが前述のように指定サイズごとに圧縮することに基づき（デフォルトでは128KB）、この単位で両方の圧縮を試み、小さい方の結果を採用しています。まず圧縮処理の軽いZLIBで圧縮し、結果サイズが小さくなればLZMAで圧縮すれば更に小さくなることが期待できるため、同じ元データをLZMAでも圧縮し、結果サイズを比較し、小さい方を採用します。初めのZLIB圧縮でサイズが小さくならないデータはLZMAでもやはり小さくは出来ないだろうと見込み、圧縮しない元データを採用します。つまり、未圧縮、ZLIB圧縮、LZMA圧縮の三者からもっともサイズの小さなものを選択する方式です。もちろん、圧縮時の処理時間は長くなりますが、この労苦はLiveCD製作者のみが負担し、全ての利用者は通常負担しません。展開時には、squashfsが元来持っているブロック毎に圧縮されているか否かの情報と、圧縮データのヘッダからZLIB、LZMAを判断できるため、種別情報を追加する必要はありません。

cloopの対応 cloopも当初はZLIBによる圧縮だけでしたが、平成16年末頃のバージョンからはadvancecompという外部パッケージを用い、より圧縮率が高い（圧縮結果のサイズが小さくなる）LZMAも選択できるようになりました。しかし、v2.636ではまだユーザ空間（つまりcreate_compressed_fsコマンド）のみのようで、カーネルモジュールには実装されていません。

カーネルの対応 ファイルシステム作成時の圧縮処理はユーザ空間（コマンドレベル ）で実行されますが、マウント後の展開処理はカーネル空間です。つまりLinuxカーネル内に展開機能が必要です。ZLIB展開機能は古くから実装されていますが、LZMA展開は平成21年6月のlinux-2.6.30、LZO展開は平成22年2月のlinux-2.6.33で実装された比較的新しいものなので、ZLIB以外の圧縮を用いる場合にはカーネルのバージョンに注意が必要です。さらに、現在の利用方法は両者ともinitramfsの展開を主眼としており、ファイルシステムから利用するにはまだ実績不足の恐れもあります。

本記事では、ZLIB圧縮でのsquashfs、cloopの測定／比較は当然行うとして、他の圧縮方法を比較しないのはちと面白くありません。cloopのLZMAはひとまずあきらめるとして、squashfsについては2.6.34で見送られたLZMA対応のコードを開発者のGITリポジトリからローカルに取り込み、比較対象に加えます。更にsquashfsがmainlineへ取り込まれる以前に広く利用されたsquashfs 3.4用のsqlzmaパッチを比較してみます。こちらはlinux-2.6.27+squashfs 3.4ベースですので参考程度です。

squahfs展開処理の並列化

もともと squashfsの展開処理はシリアライズされています。例えば、同じ squashfs内のfileA、fileBに対し、それぞれ別のプロセスが同時にアクセスしても、先のファイル展開処理が完了するまで次のファイル展開には取り掛かりません。しかし、これでは昨今のマルチコアプロセッサのパワーを活用出来ないので、展開処理も並列化しようというパッチがLinux Kernel Mailing Listへ投稿されたことがあります[4]。ZLIB展開の場合だけですが、これもローカルに取り込み、比較してみます。この機能はsqlzmaパッチでも実装されています。

[4]	次の3つ [RFC0/2] squashfs parallel decompression [RFC1/2] squashfs parallel decompression, early wait on buffer [RFC2/2] squashfs parallel decompression, z stream per cpu

比較項目

上記を踏まえ、比較項目を以下のとおりとします。

1. ext2
2. squashfs-4.0 GIP
3. squashfs-4.0 GIP -no-fragments
4. squashfs-4.0 GIP + parallel decompression patch
5. squashfs-4.0 GIP -no-fragments + parallel decompression patch
6. ext2 + cloop GZIP
7. ext2 + squashfs-4.0 GIP + nested loopback
8. squashfs-4.0 LZMA (linux-2.6.34-rc6)
9. squashfs-3.4 + sqlzma patch (linux-2.6.27.4)

squashfsのブロックサイズやLZMAの辞書サイズを調節すると所要時間を短縮できますが、バリエーションを増やすと測定の手間がかかりますし、条件が同一ならば傾向は変化しないだろうと思われるため、デフォルト値のみを採用することとします。

カーネルバージョンは、squashfs 4.0LZMAおよびsquashfs 3.4+sqlzmaを除き、すべて2.6.33とします。squashfs 4.0 LZMAは2.6.34-rc6、squashfs 3.4+sqlzmaは2.6.27.4とします。cloop-2.636はそのままではコンパイルできなかったので、2.6.33用に修正を加えました（cloop-2.636-2.6.33.patch）。

比較方法は次の通りとし、圧縮結果サイズと、読み取り／展開時の所要時間、CPU消費に注目します。 CPU時間の大半は別カーネルスレッドにより消費され、find(1)やcat(1)を対象とするtime(1)による単純測定では測定範囲外となるので、若干粗くなりますが、vmstat(8)も併用することにします。カーネルレベルのプロファイラなどを使用すれば、より精度の高い測定が可能かもしれませんが、今回は粗いレベルで留めます。

1. 複数ファイルをreaddir(3)で見つかった順にread(2)する（シーケンシャルアクセスとして）。
2. 複数ファイルをreaddir(3)とは異なる順序でread(2)する（ランダムアクセスとして）。

それぞれ、シングルプロセスで繰り返しcat(1)する場合と、cat(1)を複数同時に並列実行（マルチプロセス）する場合の二通りを測定します。 Union機能の比較と同様に複数回実行した測定結果を図6、図7に示します。測定スクリプト一式は添付ファイルに含めてあり（decomp.sh）、測定データは本記事末表3に掲載していますので、必要に応じて参照してください。

図6 読み取り専用圧縮レイヤの比較（シングルプロセス、クリックすると拡大）

図7 読み取り専用圧縮レイヤの比較（マルチプロセス、クリックすると拡大）

ファイルサイズ 当然ですが、squashfsの-no-fragmentsオプションを用いない方がサイズは小さくなります。これは圧縮対象内に小さなサイズのファイル数に依存します。LZMAを用いると-no-fragmentsオプションを用いなくとも、更に小さくなっています（11.1%削減）。ハイブリッド圧縮方式を採用しているsqlzmaパッチでは更に小さくなります（11.2%削減）。

cloopはsquashfsよりも大きなサイズになっていますが、これは今回の測定方法にも一因があります。元のファイルシステムイメージをext2で作成しましたが、ピッタリのサイズにするのは手間がかかるため、イメージファイルはやや大きめにしてあり、未使用領域が含まれます（今回の測定に使用した元イメージのファイルサイズは約732MBで、その内の約75MBが未使用領域です）。この未使用領域が圧縮結果サイズにどれだけ影響するかは調べていませんが、恐らくは圧縮結果サイズを削減できる余地があると思われます。squashfsを作成する場合は未使用領域はゼロもしくは最少になります。ファイルシステム種別もiso9660などに変更することでサイズを削減できる期待があります。今回の測定では前述の通り特に圧縮時にパラメータは与えていませんが、もちろんブロックサイズを指定する方がずっと簡単なサイズ削減方法です。

cloopの元ファイルシステムイメージは ext2ですが、これを圧縮／squashfs化したものがフラグメントブロック不使用とキャッシュ効果を狙ったsq40nestedです。同じ ZLIB圧縮なのにsq40nestedの方がcloopよりも圧縮結果サイズが小さくなっているのは、デフォルトブロックサイズの違いが主な要因と思われます。

所要時間 まず、sq40（Squashfs4.0 in vanilla linux-2.6.33）に注目すると、シングルプロセスのシーケンシャルアクセス以外の遅さが目立ちます。マルチプロセスシーケンシャルアクセスでは二倍以上、ランダムアクセスでは四倍以上時間がかかっています。測定環境はdual coreで、理想的にはマルチプロセスはシングルプロセスの半分の所要時間になって欲しいところですが、マルチプロセスの場合でもあまり短縮されておらず、CPUを充分に使い切っていないことが分かります。ランダムアクセスが遅い理由は前述のフラグメントブロックにあり、マルチプロセスが遅い理由は並列展開に対応していないことにあると思われます。CPUコア数が一つのシステムでは、当然ですが、マルチプロセスや並列展開は決して性能向上に貢献しません。

フラグメントブロックを使用しないsq40nofragを見ると、マルチプロセスでの劣化が抑えられており、シングルプロセスと同等になっています。またランダムアクセスでもシーケンシャルアクセスの二倍程度の時間に抑えられています。（本当はdual coreなのですからマルチプロセスの場合はもっと改善されて良いはずですが）恐らく並列展開に対応していないことが原因だと思われます。

並列展開の効果についてはsq40para、sq40nofrag_paraと比較すると分かります。それぞれlinux-2.6.33のsquashfsに前述のparallel decompression patchをあてたもので、用いたsquashfsイメージファイルはsq40、sq40nofragと同じものです。シングルプロセスの所要時間はsq40、sq40nofragと同等ですが、マルチプロセスの方は大きく改善されています。もちろんその分CPUを多く消費しています。

sq40nestedは二重ループバックによるキャッシュが威力を発揮し、非圧縮のext2と同等の結果となりました。ただ、搭載RAMが少ない環境ではやはり劣化すると恐れがあります。

cloopはデフォルトの圧縮ブロックサイズがsquashfsよりも小さいためか、より長く時間がかかっています。マルチプロセスの場合に遅くなってしまうのは、やはり並列展開未対応が原因と思われます。しかし、ランダムアクセス時の劣化は少なくなっています。ブロックデバイスレイヤでの圧縮/展開という点が有利に働いたと思われます。

ext2では最初に測定したシングルプロセスシーケンシャルリードだけが時間がかかっていますが、これはディスクアクセスが影響したと思われ、実際CPUのio-waitが大きくなっています。以降の測定は（ほぼ？）全てのファイルがキャッシュされたようで、io-waitが発生していません。

参考：LZMA対応 参考程度ですが、sq40lzma（linux-2.6.34-rc6のsquashfs4.0 LZMA対応）とsqlzma34（2.6.27.4 squashfs3.4用の sqlzmaパッチ）も同様に測定してみました。やはりLZMA展開処理が原因と思われる遅さが目立ち、sq40（2.6.33の squashfs4.0 ZLIB）の二倍以上遅い結果となりました。sqlzma32はハイブリッド圧縮、並列展開を実装しており、CPUをほぼ使い切っても、それでも遅い結果です。sq40lzmaは更に悪い。

しかし、 sq40lzmaは正式リリースされたものではありませんので、この簡単な測定 /比較だけをもってして遅いと決めつけるのはフェアではありません。今回は測定対象とはしませんでしたが、squashfsはLZMA以外の圧縮方法にも対応を進めており、mainlineにも取り込まれています。

本記事では既に広く利用されている squashfsを中心に、LiveCDの複数の実現法法を見直してみました。 cloopも dm-snapshotも、squashfsも aufsもどれも悪いものではありません。当然ながら、ユーザがサイズ、展開速度、メモリ消費などに明確に優先順位をつけ、最適な圧縮方法を決定するのが肝要となることは変りません。

（初出H22/12）

Copyright © 2010-11 SENJU Jiro

本記事のサンプルコードは、以下のリンクよりダウンロードすることができます。記事と合わせてご参照ください。
[サンプルコード]
また、本稿で取り上げた内容は、記事の執筆時の情報に基づいており、その後の実装の進展、変更等により、現在の情報とは異なる場合があります。
本連載「プログラマーズ・ハイ」では読者からのご意見、ご感想を切望しています。今後取り上げるテーマなどについてもご意見をお寄せください。

表3:読み取り専用圧縮レイヤの比較（図6および7の元データ）

	size (blocks,KB)			elaspsed time	CPU(dual core)
					usr	sys	idle	io-wait
ext2	-	seq	single	27.8	4	22	59	15
			multi	2.2	10	57	33	0
		rand	single	4.2	6	34	60	0
			multi	2.4	10	57	33	0
sq40	437512, 218536	seq	single	9	3	41	53	3
			multi	23.7	1	85	5	9
		rand	single	44.6	1	48	51	0
			multi	42.8	1	87	7	5
sq40para (parallel decompression)	同上	seq	single	8.9	3	42	55	0
			multi	8	4	85	11	0
		rand	single	44.6	1	49	50	0
			multi	23.4	1	93	5	1
sq40nofrag	458264, 228904	seq	single	8.6	3	40	53	4
			multi	8.7	4	77	11	8
		rand	single	16.3	2	45	53	0
			multi	13.4	3	85	9	4
sq40nofrag_para (parallele decompression)	同上	seq	single	8.6	3	41	55	1
			multi	7.6	4	74	13	9
		rand	single	16.4	2	44	53	1
			multi	10.3	3	82	10	5
cloop	521632, 260552	seq	single	15.2	1	38	23	38
			multi	22.7	1	37	7	54
		rand	single	22.8	1	46	21	32
			multi	25.7	2	52	4	42
sq40nested	515336, 257412	seq	single	11.7	2	36	29	33
			multi	2.7	8	59	33	0
		rand	single	5.1	5	36	56	3
			multi	2.9	8	59	33	0
sq40lzma (2.6.43-rc6)	391616, 195612	seq	single	29.7	1	47	51	1
			multi	297.5	0	70	8	22
		rand	single	280	0	50	50	0
			multi	305.1	0	70	25	5
sqlzma34 (2.6.27.4)	390592, 195100	seq	single	21.1	1	47	52	0
			multi	23.4	1	94	4	1
		rand	single	184.8	0	50	50	0
			multi	94.7	0	98	1	1