Linux フラッシュ・ファイルシステムの徹底調査

さまざまな選択肢とそのアーキテクチャー

読者のみなさんは、JFFS (Journaling Flash File System) や YAFFS (Yet Another Flash File System) という言葉は耳にしたことがあると思いますが、ファイルシステムの基礎をフラッシュ・デバイスに置くということが何を意味するのかおわかりでしょうか?この記事では、Linux® 向けフラッシュ・ファイルシステムの概要を説明し、基礎となる消耗デバイス (フラッシュ・メモリー) の管理をウェア・レベリングによって行う方法、そして利用できる各種のフラッシュ・ファイルシステムをその基本的設計と併せて紹介します。

M. Tim Jones (mtj@mtjones.com), Consultant Engineer, Emulex Corp.

M. Tim JonesM. Tim Jones は組み込みソフトウェアのエンジニアであり、『GNU/Linux Application Programming』や『AI Application Programming』(現在、第 2 版)、それに『BSD Sockets Programming from a Multilanguage Perspective』などの著者でもあります。技術的な経歴は静止軌道衛星用のカーネル開発から、組み込みシステム・アーキテクチャーやネットワーク・プロトコル開発まで、広範にわたっています。また、コロラド州ロングモン所在のEmulex Corp. の顧問エンジニアでもあります。



2008年 5月 20日

最近、半導体を用いたドライブが大流行していますが、組み込みシステムではかなり前から半導体デバイスをストレージとして使用しています。例えば携帯情報端末 (PDA)、携帯電話、MP3 プレイヤー、デジタル・カメラ、USB フラッシュ・ドライブ (UFD)、さらにはノート・パソコンでもフラッシュ・ファイルシステムが使用されています。たいていの場合、商用デバイス向けのファイルシステムはカスタマイズされた独自仕様となっていますが、これから説明するように、いずれのファイルシステムにしても抱えている課題は同じです。

フラッシュ・ベースのファイルシステムにはさまざまな形態があります。この記事では読み取り専用ファイルシステムをいくつか取り上げる他、現在利用できる各種の読み取り/書き込みファイルシステムとその動作について検討します。しかしその前に、フラッシュ・デバイスとこれを使用した場合にもたらされる課題について考えてみましょう。

フラッシュ・メモリー技術

フラッシュ・メモリーは不揮発性のメモリーであり、さまざまな技術の中で使われます。不揮発性のメモリーということは、その記録された内容は電源が供給されなくなった後も保持されます。フラッシュ・メモリー・デバイスの輝かしい歴史については、「参考文献」を参照してください。

フラッシュ・デバイスで最も一般的な 2 つのタイプは、NOR および NAND というそれぞれの技術によって定義付けられます。歴史が長いのは NOR ベースのフラッシュのほうです。この技術の読み取りパフォーマンスは優れているものの、容量が少ないという犠牲が伴います。それに比べ、NAND フラッシュは容量も大きく、書き込みと消去のパフォーマンスも遥かに優れています。しかし、NAND には極めて複雑な入出力 (I/O) インターフェースが必要です。

フラッシュ・メモリーは一般に複数のパーティションに区切られるため、複数の操作を同時に行うことができます (1 つのパーティションを消去すると同時に、他のパーティションから読み取りを行うなど)。パーティションはさらにブロックに区切られます (一般的に 64KB または 128KB のブロック)。パーティションを使用するファームウェアはそれに加え、例えばブロック内を 512 バイトのセグメント単位で区切るなど、独自のセグメンテーションを適用することができます (ただし、メタデータは除く)。

フラッシュ・デバイスに共通して現れる制約は、RAM ディスクなどの他のストレージ・デバイスとは異なり、デバイスを管理しなければならないということです。フラッシュ・メモリーで許可される唯一の Write 操作は、ビットを 1 からゼロに変更することだけです。逆の操作が必要になった場合には、ブロックを消去しなければなりません (すべてのビットを 1 の状態にリセットするため)。これはつまり、ブロック内にある他の有効なデータを保持するには、そのブロックを移動させなければならないということです。一般に、NOR フラッシュ・メモリーは 1 バイト単位でプログラミングできますが、NAND フラッシュ・メモリーは一度に複数のバイト (一般的には 512 バイト) をまとめてプログラミングする必要があります。

この2 つのメモリー・タイプのブロック消去プロセスは異なり、それぞれにフラッシュ・メモリーのブロック全体を範囲とする特殊なErase 操作が必要となります。NOR 技術では、前もってすべての値をゼロ・クリアしてからでないと、Erase 操作を開始することができません。Erase はフラッシュ・デバイスで使用する特殊な操作で、時間がかかる可能性があります。Erase を実行するということは、ブロック全体に含まれる各セルから電子を放出する電気的操作だからです。

NOR フラッシュ・デバイスでは通常、Erase 操作には数秒かかる一方、NAND デバイスでは数ミリ秒で消去することができます。フラッシュ・デバイスの重要な特性は、実行可能な Erase 操作の回数です。NORデバイスではフラッシュ・メモリー内の各ブロックを最大 100,000 回消去することが可能です。NAND フラッシュ・メモリーは最大 100 万回消去することが可能です。


フラッシュ・メモリーの課題

前のセクションで説明した制約に加え、その制約の結果としてフラッシュ・デバイスの管理にはいくつかの課題が持ち上がってきます。そのうち最も重要な課題は、ガーベッジ・コレクション、不良ブロックの管理、そしてウェア・レベリングの 3 つです。

ガーベッジ・コレクション

ガーベッジ・コレクションとは、無効なブロック (一定量の無効データが含まれるブロック) を再利用するプロセスのことです。再利用するには、有効なデータを新しいブロックに移してから、無効なブロックを消去してそのブロックを利用できるようにしなければなりません。このプロセスは一般にバックグラウンドで行われるか、あるいはファイルシステムの利用可能スペースが少なくなった場合に必要に応じて行われます。

不良ブロックの管理

使用を繰り返しているうちにフラッシュ・デバイスに不良ブロックが発生したり、さらにはメーカーから使用できない不良ブロックが含まれるフラッシュ・デバイスが出荷される場合もあります。このような不良ブロックの存在はフラッシュ操作 (Erase など) の失敗や、無効な Write 操作の結果、判明します (無効 ECC (Error Correction Code) により検出)。

不良ブロックが特定されると、これらの不良ブロックはフラッシュ内で不良ブロック・テーブルに入れられます。不良ブロックに対処する方法はデバイスによって異なりますが、通常のデータ・ブロックとは別に管理する一連の予備ブロックを使って対処することができます。不良ブロック (出荷時の不良ブロックであるか、時間が経つにつれ発生した不良ブロックであるかに関わらず) を処理するプロセスのことを、不良ブロック管理と呼びます。不良ブロック管理は、場合によっては内部マイクロコントローラーによってハードウェアに実装されるため、上位レベルのファイルシステムには見えないこともあります。

ウェア・レベリング

フラッシュ・デバイスは消耗品であることを思い出してください。ブロックが不良になるまでに (それによって不良ブロック管理の対象となるまでに) 各ブロックで実行できる Erase サイクル数は限られています。そこで、フラッシュの寿命を最大限に延ばすために提供されているのが、ウェア・レベリング・アルゴリズムです。ウェア・レベリングの形態には、動的ウェア・レベリングと静的ウェア・レベリングの 2 種類があります。

動的ウェア・レベリングは、ブロックの Erase サイクル数は限られているという問題に対処します。利用できるブロックをランダムに使用する代わりに、動的ウェア・レベリング・アルゴリズムではブロックの使用をむらなく分散させ、各ブロックの使用回数が均等になるようにします。もう一方の静的ウェア・レベリング・アルゴリズムが対処するのは、さらに興味深い問題です。Erase サイクル数の上限に加え、特定のフラッシュ・デバイスでは Erase サイクル間で行われる Read サイクルの最大数も問題になります。つまり、データがブロック内にとどまっている時間が長引き、何度も読み取られることになると、そのデータが消えてデータ損失につながる可能性があるという問題です。静的ウェア・レベリング・アルゴリズムは、古いデータを定期的に新しいブロックに移動させることによって、この問題に対処します。


システム・アーキテクチャー

これまでフラッシュ・デバイスとその基本的な課題について説明してきたので、今度はこれらのフラシュ・デバイスが階層化アーキテクチャーのなかでどのように位置付けられているのかを見てみましょう (図1 を参照)。最上位にある仮想ファイルシステム (VFS) は、上位レベルのアプリケーションに対する共通インターフェースを表します。VFS の下にはフラッシュ・ファイルシステム (次のセクションで説明) があり、さらにその下には FTL (Flash Translation Layer) があります。この FTL が、基礎となるフラッシュ・デバイスからのブロック割り当て、さらにアドレス変換、動的ウェア・レベリング、ガーベッジ・コレクションを含め、フラッシュ・デバイスの全体的な管理を行います。一部のフラッシュ・デバイスでは、この FTL の部分をハードウェアに実装することができます。

図 1. フラッシュ・システムの基本アーキテクチャー
フラッシュ・システムの基本アーキテクチャー

Linux カーネルが使用する MTD (Memory Technology Device) インターフェースは、フラッシュ・デバイスの汎用インターフェースです。MTD はフラッシュ・デバイスのバス幅、そしてそのバス幅を実際に使い切るために必要なデバイス数を自動的に検知します。


フラッシュ・ファイルシステム

Linux に使用可能なフラッシュ・ファイルシステムはいくつかあります。以降のセクションで、それぞれの設計と利点について説明します。

JFFS (Journaling Flash File System)

JFFS は、初期の Linux 向けフラッシュ・ファイルシステムの 1 つです。JFFS は、NOR フラッシュ・デバイスを対象に設計されたログ構造のファイルシステムで、その設計は独特であり、フラッシュ・デバイスに伴うさまざまな問題に対処しましたが、それと同時に別の問題を作り出しました。

JFFS では、フラッシュ・デバイスをブロックの循環ログとして捉えていました。つまり、フラッシュに書き込まれるデータは末尾にあるブロックに書き込まれ、先頭のブロックが再利用されます。末尾と先頭の間のスペースはフリー・スペースで、このスペースが少なくなると、ガーベッジ・コレクションが実行されます。ガーベッジ・コレクターは有効なブロックをログ末尾に移動させ、無効なブロックや使われなくなったブロックをスキップして消去します (図 2 を参照)。その結果、ファイルシステムでは静的ウェア・レベリングと動的ウェア・レベリングの両方が自動的に行われることになりますが、このようなアーキテクチャーでの根本的な問題は、(最適な消去ストラテジーが使われるのではなく) フラッシュ・デバイスがあまりにも頻繁に消去されるため、デバイスがすぐに劣化してしまうことです。

図 2. ガーベッジ・コレクション実行前と実行後の循環ログ
ガーベッジ・コレクション実行前と実行後の循環ログ

JFFS をマウントすると構造詳細がメモリーに読み込まれます。この読み取りがマウント時間を長引かせ、必要以上にメモリーを消費してしまうことになります。

JFFS2 (Journaling Flash File System 2)

JFFS は、その当時としては極めて有効ではあったものの、そのウェア・レベリング・アルゴリズムは NOR フラッシュ・デバイスの寿命を短くしがちです。そのため基礎アルゴリズムの再設計が行われ、循環ログが廃止されました。JFFS2 アルゴリズムは NAND フラッシュ・デバイス用に設計されたもので、圧縮によってパフォーマンスも改善しています。

JFFS2 では、フラッシュ内の各ブロックがそれぞれ独立して扱われます。JFFS2 はデバイスのウェア・レベリングを十分に行えるよう、何通りかのブロック・リストを保持します。そのうち、クリーン・リストが表すのは有効なノードで構成される、デバイス上のブロックです。ダーティー・リストには 1 つ以上の使われなくなったノードを持つブロックが含まれます。そして最後の 1 つ、フリー・リストは消去済み、または使用可能なブロックを表します。

これらのリストにより、ガーベッジ・コレクション・アルゴリズムは何をどのように再利用すればよいのかをインテリジェントに決定することができます。現在このアルゴリズムではクリーン・リストかダーティー・リストを選択しますが、ブロックを再利用する場合、その 99 パーセントの確率でダーティー・リストが選択され (有効な内容を別のブロックに移動)、残りの 1 パーセントはクリーン・リストが選択されます (単に内容を新しいブロックに移動)。いずれの場合も選択されたブロックは消去されてフリー・リストに配置されるため (図3 を参照)、ガーベッジ・コレクターは使われなくなった (または部分的に使われなくなった) ブロックを再利用できると同時に、静的ウェア・レベリングをサポートするために引き続きフラッシュ関連のデータを移動することができます。

図 3. JFFS2 でのブロック管理とガーベッジ・コレクション
JFFS2 でのブロック管理とガーベッジ・コレクション

YAFFS (Yet Another Flash File System)

YAFFS も同じく NAND フラッシュ用に開発されたフラッシュ・ファイルシステムです。初期バージョン (YAFFS) がサポートしていたのは 512 バイトのページを持つフラッシュ・デバイスでしたが、その後のバージョン (YAFFS2) ではさらに大きなページ・サイズと一層優れた Write 制約を持つ新しいデバイスをサポートします。

ほとんどのフラッシュ・ファイルシステムでは、使われなくなったブロックはそのようなブロックとしてマークされますが、YAFFS2 はそれに加え、単調にインクリメントされるシーケンス番号でブロックにマークを付けます。そのためファイルシステムをマウント時にスキャンするときに、有効な i ノードを素早く識別することができます。また YAFFS は、チェックポイント指定による高速マウント (通常のアンマウント時に RAM ツリー構造をフラッシュ・デバイスに保存し、マウント時にこの構造を RAM に素早く読み込んでリストアできるようにするためのプロセス) を含め、RAM 内にフラッシュ・デバイスのブロック構造を表すツリーを維持します (図 4 を参照)。YAFFS2 のマウント時のパフォーマンスは、他のフラッシュ・ファイルシステムに大きく勝っています。

図 4. YAFFS2 マウント時のチェックポイント指定による最適化
YAFFS2 マウント時のチェックポイント指定による最適化

読み取り専用の圧縮ファイルシステム

組み込みシステムには、可変ファイルシステムを提供する必要がないものもあります。その場合には、不変のファイルシステムで十分です。Linux がサポートする読み取り専用ファイルシステムはさまざまにありますが、そのうちの cramfs と SquashFS の 2 つが最も役に立ちます。

Cramfs

cramfs ファイルシステムは圧縮された読み取り専用 Linux ファイルシステムで、フラッシュ・デバイス内に配置することができます。cramfs の主な特徴は、単純であること、そしてスペース効率に優れているという 2 点です。このファイルシステムは、占有スペースの小さな組み込み設計に使用されます。

メタデータは圧縮されないものの、cramfs はページ単位で zlib 圧縮を使用することによってページへのランダム・アクセスを可能にしています (ページはアクセス時に圧縮解除されます)。

cramfs は、mkcramfs ユーティリティーとループバック・デバイスを使って試してみることができます。

SquashFS

同じく圧縮された読み取り専用 Linux ファイルシステムである SquashFS は、フラッシュ・デバイス内で役立ちます。SquashFS は多数の Live CD Linux ディストリビューションでも使用されています。SquashFS は zlib 圧縮をサポートするだけでなく、LZMA (Lembel-Ziv-Markov chain Algorithm) を使用して圧縮と速度の改善を図っています。

cramfs と同様、SquashFS は mksquashfs およびループバック・デバイスを備えた標準 Linux システムで使用できます。


さらに詳しく学ぶには

ほとんどのオープンソースがそうであるように、ソフトウェアは進化し続けていることから新しいフラッシュ・ファイルシステムの開発が進んでいます。開発中の新規フラッシュ・ファイルシステムのなかで特に興味を引かれるのは、LogFS です。このフラッシュ・ファイルシステムにはいくつかの極めて斬新なアイデアが採用されています。例えば、LogFS はフラッシュ・デバイス自体でツリー構造を維持するため、マウント時間は ext2 などの従来のファイルシステムに匹敵します。また、ガーベッジ・コレクションには B+tree の形態である wandering tree (移動式ツリー) (訳注: ツリーのデータを書き換える際にはそこからルートまで遡った全データを別の場所に移動して書き換える方式のツリー) を使用します。しかし、それにも増して LogFS を特に興味深いものにしているのは、拡張が極めて容易であり、大量のフラッシュ・メモリーをサポートできるという点です。

フラッシュ・ファイルシステムの人気が高まっているなか、フラッシュ・ファイルシステムを対象としたかなりの調査が実施されています。LogFS はその一例ですが、UbiFS をはじめとした他の選択肢も増えてきています。アーキテクチャーとして興味深いフラッシュ・ファイルシステムは、今後も技術革新の源となり続けるはずです。

参考文献

学ぶために

  • ウィキペディアで、 フラッシュ・メモリー技術の概要、そしてディスク・ベースのファイルシステム、分散ファイルシステム、特殊な用途のファイルシステム (半導体を媒体としたファイルシステムなど) を記載したファイルシステムの分類を参照してください。
  • NAND vs. NOR flash technology で、この 2 つのフラッシュ技術についての詳細を読んでください。
  • Tim の記事、「Linux ファイルシステムの徹底調査」(developerWork、2007年10月) で、VFS とその主要な構造、アーキテクチャーを紹介しています。この記事ではファイルシステムの概要、そして Linux が多くのファイルシステムを同時にサポートできる理由も説明しています。
  • JFFS とその後継である JFFS2 がそれぞれに採用しているフラッシュ・デバイス管理手法について読んでください (PDF 版)。
  • よく使用されている他のフラッシュ・ファイルシステムと、YAFFS を比較してみてください。
  • 2 つの新しいフラッシュ・ファイルシステム、LogFSUbiFS は、現行のフラッシュ・ファイルシステムに関する多くの問題を解決します。
  • メモリー・デバイス (フラッシュ・メモリーなど) の汎用サブシステムである MTD は、下位レベルのハードウェア・ドライバーと上位レベルのファイルシステムとの間の汎用インターフェースとなります。
  • CramfsSquashFS は、Linux 向け読み取り専用圧縮ファイルシステムです。どちらもメモリーの制約がある組み込みシステムを対象に設計されていますが、SquashFS に関しては Live CD ディストリビューションでも使用されています。この 2 つは、ファイルシステムのユニオンマウント (ファイルシステム同士を重ね合わせること) を実装する UnionFS で使用されることがよくあります。LZMA一連のパッチを使用する SquashFS は、圧縮およびパフォーマンスの点で勝っています。
  • developerWorks に掲載されているTim の一連の「徹底調査」シリーズの記事を読んでください。
  • developerWorks に掲載されているTim の Linux 関連のすべての記事を読んでください。
  • developerWorks Linux ゾーンに豊富に揃った Linux 開発者向けの資料を調べてください。記事とチュートリアルの人気ランキングも要チェックです。
  • developerWorks に掲載されているすべての Linux のヒントLinux チュートリアルを参照してください。
  • developerWorks technical events and webcasts で最新情報を入手してください。

製品や技術を入手するために

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=316101
ArticleTitle=Linux フラッシュ・ファイルシステムの徹底調査
publish-date=05202008