(57)【特許請求の範囲】
【請求項１】
順次行なわれるファイルへのアクセスを、ログを順次追加していくことで記録する、ログ構成のファイルシステムにおけるファイル管理方法であって、
予め、記憶媒体の記憶領域を、ファイルのデータを含むログを格納するデータ領域と、前記データ領域に格納されたログに関するシーケンス番号を複数エントリー分だけ格納可能なシーケンス番号記憶領域とに分割するステップと、
そのエントリーの書き込まれた順序を示す第１のシーケンス番号を新たなエントリーとして前記シーケンス番号記憶領域に順次追加して記録するステップと、を有するファイル管理方法。
【請求項２】
前記第１のシーケンス番号に基づいて最も新しいエントリーを探し出し、該エントリーを用いて先頭ログを検出するステップをさらに有する、請求項１に記載のファイル管理方法。
【請求項３】
前記データ領域は複数のログ領域からなり、前記シーケンス番号記憶領域は前記複数のログ領域に対応する複数のログ領域毎シーケンス番号記憶領域からなり、
前記記憶媒体にログを追加するとき、該ログの追加に新たなログ領域を使用する必要があれば、新たな該ログ領域に対応するログ領域シーケンス番号記憶領域に新たなエントリーを記録する、請求項２に記載のファイル管理方法。
【請求項４】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
先頭ログを検出するステップは、
前記シーケンス番号記憶領域内のログ領域毎シーケンス番号記憶領域に記録された第１のシーケンス番号により最新のエントリーを探し出すステップと、
前記最新のエントリーのログ領域毎シーケンス番号記憶領域に対応するログ領域を探索対象範囲として定めるステップと、
探索対象範囲として定めた前記ログ領域内の全てのログの第２のシーケンス番号から最新のログを判定し、該ログを先頭ログとするステップと、を有する、請求項３に記載のファイル管理方法。
【請求項５】
前記ログ領域毎シーケンス番号記憶領域に記録されるエントリーには、対応するログ領域の各々の最初に格納されたログの開始位置情報がさらに含まれており、
前記先頭ログを検出するステップにおいて、
前記ログ領域に格納されたログの境界を、前記開始位置情報を用いて認識する、請求項４に記載のファイル管理方法。
【請求項６】
前記ログ領域毎シーケンス番号記憶領域の各々は、対応するログ領域の内部に配置されている、請求項３から５のいずれか１項に記載のファイル管理方法。
【請求項７】
前記ログ領域毎シーケンス番号記憶領域が、対応する前記ログ領域内の、最初に前記ログの格納に使用される部分に隣接して配置されている、請求項６に記載のファイル管理方法。
【請求項８】
前記記憶媒体にログを追加するとき、その時点での先頭ログの記録されたログ領域に、追加する該ログを収容できるだけの容量が残っていなければ、前記先頭ログの記録された前記ログ領域の次のログ領域に該ログを追加する、請求項３から７のいずれか１項に記載のファイル管理方法。
【請求項９】
前記記憶媒体にログを追加するとき、該ログの位置を示すログ参照情報を前記第１のシーケンス番号と共にエントリーとして記録する、請求項２に記載のファイル管理方法。
【請求項１０】
先頭ログを検出するステップは、
前記シーケンス番号記録領域内の各エントリーに含まれる第１のシーケンス番号から最新のエントリーを探し出すステップと、
前記最新のエントリーに含まれているログ参照情報により示されるログを先頭ログとして検出するステップと、を有する、請求項９に記載のファイル管理方法。
【請求項１１】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
前記最新のエントリーに含まれているログ参照情報により示されるログの次以降の領域に、該ログの第２のシーケンス番号よりも新しい第２のシーケンス番号が付与されたログがあれば、最も新しい第２のシーケンス番号が付与されたログを先頭ログとする、請求項１０に記載のファイル管理方法。
【請求項１２】
前記ログの有効か無効かが該ログのヘッダ内のフラグで示されており、
前記ログを追加するとき、該ログにおける書き込み先と同じ書き込み先に対する過去のデータを含む既存の有効なログが前記記憶媒体上にあれば、該既存のログのフラグを無効にするステップをさらに有する、請求項１から１１のいずれか１項に記載のファイル管理方法。
【請求項１３】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
前記記憶媒体の使用を開始するとき、書き込み先が同一の有効なログが複数あれば、その複数の中から前記第２のシーケンス番号により最も新しいログを見つけ、前記最も新しいログ以外のログを無効にする、請求項１２に記載のファイル管理方法。
【請求項１４】
前記記憶媒体は、消去された状態で“１”となるフラッシュメモリであり、前記フラグが“１”で有効を示し、“０”で無効を示す、請求項１２または１３に記載のファイル管理方法。
【請求項１５】
前記ログは、該ログが追加された時点での最後尾ログを示す最後尾参照情報をヘッダ内に含んでおり、
最後尾ログを検出する処理として、
先頭ログのヘッダに含まれている最後尾参照情報により示されたログから順に先頭方向に有効なログを探し、最初に見つかった有効なログを最後尾ログと判断するステップをさらに有する、請求項１２から１４のいずれか１項に記載のファイル管理方法。
【請求項１６】
前記エントリーは、該エントリーが書き込まれた時点での最新の最後尾ログを示す最後尾参照情報を含んでおり、
最後尾ログを検出する処理として、
最新のエントリーに含まれている最後尾参照情報により示されたログから順に先頭方向に有効なログを探し、最初に見つかった有効なログを最後尾ログと判断するステップをさらに有する、請求項１２から１４のいずれか１項に記載のファイル管理方法。
【請求項１７】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
最後尾ログがログ領域をまたいで替わるとき、新たな最後尾ログを含むこととなったログ領域に対応するログ領域毎シーケンス番号記憶領域に、最後尾ログを含むこととなった順序を示す第３のシーケンス番号を新たなエントリーとして記録するステップと、
最後尾ログを検出する処理として、
前記シーケンス番号記憶領域内のログ領域毎シーケンス番号記憶領域に記録された第３のシーケンス番号により、最も新しく最後尾ログを含むこととなったエントリーを探し出すステップと、
前記最も新しく最後尾ログを含むこととなったエントリーのログ領域毎シーケンス番号記憶領域に対応するログ領域を探索対象範囲として定めるステップと、
探索対象範囲として定めた前記ログ領域内の有効なログの第２のシーケンス番号から最も古いログを判定し、該ログを最後尾ログとするステップと、をさらに有する、請求項３に記載のファイル管理方法。
【請求項１８】
前記先頭ログを検出する処理として、
探索対象範囲として定めた前記ログ領域から最新のログを判定するとき、該ログ領域内の終わりまでログが記録されており、かつ、その終わりに記録されているログの第２のシーケンス番号が該ログ領域の中で最も新しければ、探索対象範囲とした前記ログ領域の次のログ領域の最初のログの第２のシーケンス番号を確認するステップと、
前記次のログ領域の最初に記録されているログの前記第２のシーケンス番号が、前記探索対象範囲とした前記ログ領域の終わりに記録されているログの前記第２のシーケンス番号よりも新しければ、探索対象範囲を前記次のログ小領域に変更して先頭ログを検出しなおすステップと、をさらに有する請求項４に記載のファイル管理方法。
【請求項１９】
探索対象範囲を前記次のログ領域に変更したとき、該次のログ領域に対応するログ領域毎シーケンス番号記憶領域に新たなエントリーを記録する、請求項１８記載のファイル管理方法。
【請求項２０】
順次行なわれるファイルへのアクセスを、ログを順次追加していくことで記録する、ログ構成のファイルシステムを適用したファイル管理装置であって、
ファイルを格納することのできる記憶領域を備えた記憶媒体と、
前記記憶媒体に格納されたファイルにアクセスするプロセッサと、
予め、前記記憶媒体の記憶領域を、ファイルのデータを含むログを格納するデータ領域と、前記データ領域に格納されたログに関するシーケンス番号を複数エントリー分だけ格納可能なシーケンス番号記憶領域とに分割しておき、そのエントリーの書き込まれた順序を示す第１のシーケンス番号を新たなエントリーとして前記シーケンス番号記憶領域に順次追加して記録するファイル処理部と、を有するファイル管理装置。
【請求項２１】
前記ファイル処理部は、前記データ領域が複数のログ領域からなり、前記シーケンス番号記憶領域が前記複数のログ領域に対応する複数のログ領域毎シーケンス番号記憶領域からなるように前記記憶領域を分割しておき、前記記憶媒体にログを追加するとき、該ログの追加に新たなログ領域を使用する必要があれば、新たな該ログ領域に対応するログ領域毎シーケンス番号記憶領域に新たなエントリーを記録する、請求項２０に記載のファイル管理装置。
【請求項２２】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
前記ファイル処理部は、
先頭ログを検出する処理として、
前記シーケンス番号記憶領域内のログ領域毎シーケンス番号領域に記録された第１のシーケンス番号により最新のエントリーを探し出し、前記最新のエントリーのログ領域毎シーケンス番号記憶領域に対応するログ領域を探索対象範囲として定め、探索対象範囲として定めた前記ログ領域内の全てのログの第２のシーケンス番号から最新のログを判定し、該ログを先頭ログとする、請求項２１に記載のファイル管理装置。
【請求項２３】
前記ファイル処理部は、前記ログ領域毎シーケンス番号記憶領域の各々を、対応するログ領域の内部に配置する、請求項２１または２２に記載のファイル管理装置。
【請求項２４】
順次行なわれるファイルへのアクセスを、ログを順次追加していくことで記録する、ログ構成のファイルシステムにおけるファイル管理をコンピュータに実行させるためのプログラムであって、
予め、記憶媒体の記憶領域を、ファイルのデータを含むログを格納するデータ領域と、前記データ領域に格納されたログに関するシーケンス番号を複数エントリー分だけ格納可能なシーケンス番号記憶領域とに分割する手順と、
そのエントリーの書き込まれた順序を示す第１のシーケンス番号を新たなエントリーとして前記シーケンス番号記憶領域に順次追加して記録する手順と、をコンピュータに実行させるためのプログラム。
【請求項２５】
前記データ領域は複数のログ領域からなり、前記シーケンス番号記憶領域は前記複数のログ領域に対応する複数のログ領域毎シーケンス番号記憶領域からなり、
前記記憶媒体にログを追加するとき、該ログの追加に新たなログ領域を使用する必要があれば、新たな該ログ領域に対応するログ領域毎シーケンス番号記憶領域に新たなエントリーを記録する、請求項２４に記載のプログラム。
【請求項２６】
前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２のシーケンス番号が含まれており、
先頭ログを検出する処理として、
前記シーケンス番号記憶領域内のログ領域毎シーケンス番号記憶領域に記録された第１のシーケンス番号により最新のエントリーを探し出す手順と、
前記最新のエントリーのログ領域毎シーケンス番号記憶領域に対応するログ領域を探索対象範囲として定める手順と、
探索対象範囲として定めた前記ログ領域内の全てのログの第２のシーケンス番号から最新のログを判定し、該ログを先頭ログとする手順と、をさらにコンピュータに実行させる、請求項２５に記載のプログラム。
【請求項２７】
前記ログ領域毎シーケンス番号記憶領域の各々は、対応するログ領域の内部に配置されている、請求項２５または２６に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサからアクセスされる記憶媒体上のファイル管理方法に関し、特に、データを消去する回数に制限のある記憶媒体に適したファイル管理方法に関する。
【背景技術】
【０００２】
データをファイル単位で記憶媒体に格納するコンピュータのファイルシステムは様々な記憶媒体へのファイルの格納を仲介する。例えば、大容量化に適し、電気的に書き換えが可能で、電源を切断してもデータが消滅しないフラッシュメモリがファイルの格納に用いられる場合がある。フラッシュメモリへのデータの書き込みはバイト等の小さな単位で可能であるが、書き込まれたデータの消去はブロックという大きな単位で行なう必要がある。
【０００３】
そして、フラッシュメモリのデータの消去には回数に制限がある。そのため、記憶媒体としてフラッシュメモリを使用する場合、消去回数をブロック間で均等化することにより、フラッシュメモリ全体として使用可能な期間をできるだけ長くする工夫がされる。消去回数の均等化は“ｗｅａｒ  ｌｅｖｅｌｉｎｇ”と呼ばれる。
【０００４】
ＪＦＦＳ（Ｊｏｕｒｎａｌｉｎｇ  Ｆｌａｓｈ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）（非特許文献１参照）のような、フラッシュメモリを記憶媒体として用いるファイルシステムでは、“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”（非特許文献２参照）の手法が用いられる。
【０００５】
“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”は、データを上書きせず、連続的に次々に追加保存していくデータ格納方法である。この方法によれば連続的に保存されたデータの中に古いデータがログとして残る。そして、ログとして残ったデータの中には有効なデータと無効なデータが混在することになる。そのため、ＪＦＦＳのような“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”のファイルシステムは、使用開始時などに実行するマウント処理において、フラッシュメモリの全てのデータを読み出し、有効なデータの範囲を割り出している。このような“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”の手法は、局所的なデータの消去を行なわないので、ブロックを均等に利用することに寄与する。
【非特許文献１】Ｄａｖｉｄ  Ｗｏｏｄｈｏｕｓｅ、「ＪＦＦＳ：Ｔｈｅ  Ｊｏｕｒｎａｌｌｉｎｇ  Ｆｌａｓｈ  Ｆｉｌｅ  Ｓｙｓｔｅｍ」、［ＯＮＬＩＮＥ］、［２００５年８月３日検索］、インターネット＜ＵＲＬ：  http://sources.redhat.com/jffs2/jffs2.pdf＞
【非特許文献２】ユーレッシュ・ヴァハリア著、「最前線ＵＮＩＸのカーネル」、株式会社ピアソン・エデュケーション、２０００年５月１５日、３９８〜３９９ページ
【発明の開示】
【発明が解決しようとする課題】
【０００６】
“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”ファイルシステムによれば、記憶領域の消去回数を均等化することができ、使用可能期間を長くすることができる。しかし、そのようなファイルシステムでは、マウント処理にて先頭のログを見つけるために、マウントする記憶媒体中のデータを全て確認して有効なデータの範囲を洗い出す必要があるため、その処理が重く、使用開始に時間がかかるという問題があった。
【０００７】
従来の他の種類のファイルシステムとして、ファイル管理構造の情報をインデックスファイルに記録することで、全体の構造把握を容易にするファイルシステムもある。この種のファイルシステムとして、例えば、４．４ＢＳＤ（Ｂｅｒｋｅｌｅｙ  Ｓｏｆｔｗａｒｅ  Ｄｉｓｔｒｉｂｕｔｉｏｎ）のＬＦＳ（Ｌｏｇｓｔｒｕｃｔｕｒｅｄ  Ｆｉｌｅｓｙｓｔｅｍ）がある（例えば、Ｍａｒｓｈａｌｌ  Ｋｉｒｋ  Ｍｃｋｕｓｉｃｋ，Ｋｅｉｔｈ  Ｂｏｓｔｉｃ，Ｍｉｃｈａｅｌ  Ｊ．ｋａｒｅｌｓ，Ｊｏｈｏｎ  Ｓ．Ｑｕａｒｔｅｒｍａｎ、４．４ＢＳＤの設計と実装、２００３年１０月１０日、３３１〜３５０ページ参照）。
【０００８】
しかし、ＬＦＳでは、記憶媒体中のインデックスファイルの位置は変化するが、そのインデックスファイルの位置を示す管理情報は、固定位置のスーパーブロックに記録される。そのため、更新によりインデックスファイルの位置が変化する毎にスーパーブロックの内容は更新されることとなる。
【０００９】
そのため、スーパーブロックとして使用されるブロックの消去回数は他のブロックの消去回数よりも多くなり、消去回数がブロック間で均等化されない。その結果、スーパーブロックの消去回数によりフラッシュメモリ全体の使用可能期間が決まってしまうこととなっていた。
【００１０】
本発明の目的は、記憶媒体の使用可能期間を長くすると共に、使用開始にかかる時間を短縮したファイルシステムを提供することである。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明のファイル管理方法は、
順次行なわれるファイルへのアクセスを、ログを順次追加していくことで記録する、ログ構成のファイルシステムにおけるファイル管理方法であって、
予め、記憶媒体の記憶領域を、ファイルのデータを含むログを格納するデータ領域と、前記データ領域に格納されたログに関する管理情報を複数エントリー分だけ格納可能な管理領域とに分割するステップと、
そのエントリーの書き込まれた順序を示す第１の番号を含む前記管理情報を新たなエントリーとして前記管理領域に追加して記録するステップとを有している。
【００１２】
本発明によれば、記憶媒体に記録されたログの管理情報を記憶する管理領域は複数エントリーを記録可能であり、管理情報を追加記録していくので、使用開始時に管理情報を参照すれば記憶領域全体を確認しなくてもよく、使用開始時の時間を短縮することができ、また、その管理情報を前回のエントリーに上書きせず、新たなエントリーとして追加記録するので、管理情報を記録する領域の消去回数を低減し、記憶媒体の使用可能期間を長期化することができる。
【００１３】
また、前記第１の番号に基づいて最も新しいエントリーを探し出し、該エントリーの管理情報を用いて先頭ログを検出するステップをさらに有することとしてもよい。
【００１４】
これによれば、先頭ログを迅速に検出することができるので、使用開始時の時間を短縮することができる。
【００１５】
また、前記データ領域は複数のデータ小領域からなり、前記管理領域は前記複数のデータ小領域に対応する複数の管理小領域からなり、
前記記憶媒体にログを追加するとき、該ログの追加に新たなデータ小領域を使用する必要があれば、新たな該データ小領域に対応する管理小領域に前記管理情報のエントリーを記録することとしてもよい。
【００１６】
これによれば、ログを記録するデータ領域が複数のデータ小領域に分割され、管理情報を格納する管理領域もそれぞれのデータ小領域に対応する複数の管理小領域に分割されており、管理小領域への管理情報の書き込みは、対応するデータ小領域への最初の書き込みのときだけなので、管理領域の消去回数がデータ領域の消去回数と均等になり、記憶媒体の使用可能期間が長期化する。
【００１７】
また、前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２の番号が含まれており、
先頭ログを検出するステップは、
前記管理領域内の各管理小領域に記録された第１の番号により最新のエントリーを探し出すステップと、
前記最新のエントリーの管理小領域に対応するデータ小領域を探索対象範囲として定めるステップと、
探索対象範囲として定めた前記データ小領域内の全てのログの第２の番号から最新のログを判定し、該ログを先頭ログとするステップと、を有することとしてもよい。
【００１８】
これによれば、管理情報として記録した第１の番号により複数エントリーより最新エントリーを見つけ、そのエントリーに対応するデータ小領域を探索対象とし、そのデータ小領域にある各ログの第２の番号から先頭ログを検出するので、使用開始にかかる時間を短縮することができる。
【００１９】
また、前記管理小領域に記録される前記管理情報のエントリーには、対応するデータ小領域の各々の最初に格納されたログの開始位置情報がさらに含まれており、
前記先頭ログを検出するステップにおいて、
前記小領域に格納されたログの境界を、前記開始位置情報を用いて認識することとしてもよい。
【００２０】
これによれば、各エントリーには、対応するデータ小領域の最初のログの開始位置を示す情報が含まれるので、データ小領域とログの境界が一致していなくても容易にログの位置を認識することができる。
【００２１】
また、前記管理小領域の各々は、対応するデータ小領域の内部に配置されていることとしてもよい。
【００２２】
また、前記管理小領域が、対応する前記データ小領域内の、最初に前記ログの格納に使用される部分に隣接して配置されていることとしてもよい。
【００２３】
また、前記記憶媒体にログを追加するとき、その時点での先頭ログの記録されたデータ小領域に、追加する該ログを収容できるだけの容量が残っていなければ、前記先頭ログの記録された前記データ小領域の次のデータ小領域に該ログを追加することとしてもよい。
【００２４】
これによれば、各データ小領域の管理情報の各々は、対応するデータ小領域の内部に記録されるので、管理情報とログとを連続したブロックとして１回の処理で書き込むことができ、管理情報とログのいずれか一方のみが更新されて矛盾した状態が発生するのを低減することができる。
【００２５】
また、本発明において、前記記憶媒体にログを追加するとき、該ログの位置を示すログ参照情報を前記第１の番号と共に前記管理情報のエントリーとして記録することとしてもよい。
【００２６】
また、先頭ログを検出するステップは、
前記管理領域内の各管理情報のエントリーに含まれる第１の番号から最新のエントリーを探し出すステップと、
前記最新のエントリーに含まれているログ参照情報により示されるログを先頭ログとして検出するステップと、を有することとしてもよい。
【００２７】
また、前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２の番号が含まれており、
前記最新のエントリーに含まれているログ参照情報により示されるログの次以降の領域に、該ログの第２の番号よりも新しい第２の番号が付与されたログがあれば、最も新しい第２の番号が付与されたログを先頭ログとすることとしてもよい。
【００２８】
また、前記ログの有効か無効かが該ログのヘッダ内のフラグで示されており、
前記ログを追加するとき、該ログにおける書き込み先と同じ書き込み先に対する過去のデータを含む既存の有効なログが前記記憶媒体上にあれば、該既存のログのフラグを無効にするステップをさらに有することとしてもよい。
【００２９】
また、前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２の番号が含まれており、
前記記憶媒体の使用を開始するとき、書き込み先が同一の有効なログが複数あれば、その複数の中から前記第２の番号により最も新しいログを見つけ、前記最も新しいログ以外のログを無効にすることとしてもよい。
【００３０】
これによれば、再び記憶媒体の使用を開始するとき、正しいデータのファイルが使用可能となる。
【００３１】
また、前記記憶媒体は、消去された状態で“１”となるフラッシュメモリであり、前記フラグが“１”で有効を示し、“０”で無効を示すこととしてもよい。
【００３２】
これによれば、ログの状態を有効から無効に移行させるのにデータの消去が不要となり、記憶媒体の使用可能期間を長くすることができる。
【００３３】
また、前記ログは、該ログが追加された時点での最後尾ログを示す最後尾参照情報をヘッダ内に含んでおり、
最後尾ログを検出する処理として、
先頭ログのヘッダに含まれている最後尾参照情報により示されたログから順に先頭方向に有効なログを探し、最初に見つかった有効なログを最後尾ログと判断するステップをさらに有することとしてもよい。
【００３４】
これによれば、最後尾ログを割り出すとき、全てのログの有効無効を調べる必要が無くなり、使用開始にかかる時間を短縮することができる。
【００３５】
また、前記管理情報のエントリーは、該エントリーが書き込まれた時点での最新の最後尾ログを示す最後尾参照情報を含んでおり、
最後尾ログを検出する処理として、
最新のエントリーに含まれている最後尾参照情報により示されたログから順に先頭方向に有効なログを探し、最初に見つかった有効なログを最後尾ログと判断するステップをさらに有することとしてもよい。
【００３６】
これによっても、最後尾ログを割り出すとき、全てのログの有効無効を調べる必要が無くなり、使用開始にかかる時間を短縮することができる。
【００３７】
また、前記ログのヘッダには、該ログが前記記憶媒体に書き込まれた順序を示す第２の番号が含まれており、
最後尾ログがデータ小領域をまたいで替わるとき、新たな最後尾ログを含むこととなったデータ小領域に対応する管理小領域に、最後尾ログを含むこととなった順序を示す第３の番号を含む管理情報を新たなエントリーとして記録するステップと、
最後尾ログを検出する処理として、
前記管理領域内の各管理小領域に記録された第３の番号により、最も新しく最後尾ログを含むこととなったエントリーを探し出すステップと、
前記最も新しく最後尾ログを含むこととなったエントリーの管理小領域に対応するデータ小領域を探索対象範囲として定めるステップと、
探索対象範囲として定めた前記データ小領域内の有効なログの第２の番号から最も古いログを判定し、該ログを最後尾ログとするステップと、をさらに有することとしてもよい。
【００３８】
これによっても、最後尾ログを割り出すとき、全てのログの有効無効を調べる必要が無くなり、使用開始にかかる時間を短縮することができる。
【００３９】
また、前記先頭ログを検出する処理として、
探索対象範囲として定めた前記データ小領域から最新のログを判定するとき、該データ小領域内の終わりまでログが記録されており、かつ、その終わりに記録されているログの第２の番号が該データ小領域の中で最も新しければ、探索対象範囲とした前記データ小領域の次のデータ小領域の最初のログの第２の番号を確認するステップと、
前記次のデータ小領域の最初に記録されているログの前記第２の番号が、前記探索対象範囲とした前記データ小領域の終わりに記録されているログの前記第２の番号よりも新しければ、探索対象範囲を前記次のデータ小領域に変更して先頭ログを検出しなおすステップと、をさらに有することとしてもよい。
【００４０】
これによれば、異常終了後に再び記憶媒体の使用を開始するとき、正しい先頭ログの認識が可能となる。
【００４１】
また、探索対象範囲を前記次のデータ小領域に変更したとき、該次のデータ小領域に対応する管理小領域に前記管理情報のエントリーを記録することとしてもよい。
【００４２】
これによれば、異常終了した状態から本来の先頭ログが記録されたデータ小領域を検出すると、このとき新たなログを書き込む動作が有っても無くても、管理領域を修正して正常な状態に戻すので、そのときに記憶媒体上の状態を正しくすることができ、次にファイルシステムを使用開始する際には探索範囲を広くする必要が減る。
【発明の効果】
【００４３】
本発明によれば、記憶媒体に記録されたログの管理情報を記憶する管理領域は複数エントリーを記録可能であり、管理情報を追加記録していくので、使用開始時には管理情報を参照すれば記憶領域全体を確認しなくてもよく、使用開始時の時間を短縮することができ、また、その管理情報を前回のエントリーに上書きせず、新たなエントリーとして追加記録するので、管理情報を記録する領域の消去回数を低減し、記憶媒体の使用可能期間を長期化することができる。
【発明を実施するための最良の形態】
【００４４】
本発明を実施するための形態について図面を参照して詳細に説明する。
【００４５】
（第１の実施形態）
図１は、第１の実施形態によるコンピュータシステムの構成を示すブロック図である。図１を参照すると、コンピュータシステムは、プロセッサ１０、ファイル処理部１１、および記憶媒体１２を有している。
【００４６】
プロセッサ１０は、不図示のプログラムを実行することにより所定の計算処理を行なう。
【００４７】
ファイル処理部１１は、プロセッサ１０から記憶媒体１２へのアクセスを仲介し、プロセッサ１０の要求により記憶媒体１２上のファイルに対する書き込みおよび読み出しを行なう。本実施形態のファイル処理部１１で用いられるファイルシステムは“ｌｏｇ−ｓｕｒｕｃｔｕｒｅｄ”である。したがって、記憶媒体１２上に既に記録されているファイル中のブロックに対する書き込み、すなわち“アップデート書き込み”であったとしても、ファイル処理部１１は古いデータに上書きすることはせず、新たなログを作成して記憶媒体１２上に追加し、古いログを無効にする。
【００４８】
記憶媒体１２は、消去（あるいは書き込み）の回数に制限がある記憶媒体であり、例えばフラッシュメモリである。
【００４９】
図２は、第１の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。図２を参照すると、記憶媒体１２の記憶領域は、シーケンス番号記憶領域と複数のログ領域に分割される。
【００５０】
記憶媒体１２に書き込まれるデータの単位をログと呼ぶ。１つのログ領域に複数のログを記録してもよく、また１つのログが複数のログ領域にまたがってもよい。また、各ログ領域は全てが同一サイズであってもよく、あるいはそれぞれ毎に異なってもよい。
【００５１】
図３は、ログ領域に格納されるログの構成を示す図である。図３を参照すると、ログはヘッダ部とデータ部とで構成されている。ヘッダ部には、ログのサイズ、バージョン番号、無効フラグ、ファイルの位置情報、およびファイル中のデータブロックの位置情報等が含まれる。バージョン番号は、そのログを書き込んだ順序を示す番号である。このバージョン番号により各ログの新しさを知ることができる。
【００５２】
図２に戻り、シーケンス番号記憶領域は複数のエントリーからなる管理領域である。複数のエントリーは複数のログ領域の各々に対応しており、各ログ領域のシーケンス番号が記録される。シーケンス番号は、そのログ領域にログが書き込まれた順序を示す番号である。このシーケンス番号により、最も新しくログが書き込まれたログ領域を識別することができる。
【００５３】
なお、ログの状態として有効な状態と無効な状態とがあり、それらは無効フラグにより示される。無効フラグがセットされていることで無効なログであることを示し、セットされていないことで有効なログであることを示す。無効フラグは、データが消去された状態からビット反転した状態で無効（セットされた状態）を示すこととすればよい。フラッシュメモリでは、消去された状態が“１”なので、無効フラグが“０”でセットされた状態を示すこととすればよい。これにより、ログの状態を有効から無効に移行させるのにデータの消去が不要となり、記憶媒体の使用可能期間を長くすることができる。
【００５４】
ここでは、最も新しく書き込まれた（有効な）ログを先頭ログと呼び、最も古く書き込まれた有効なログを最後尾ログと呼ぶこととする。
【００５５】
次に、本実施形態のコンピュータシステムの動作について説明する。図４は、記憶媒体に格納されているデータの変化の一例を示す図である。図４の上段の状態では、記憶媒体１２にはログｉ〜ログｊが格納されている。この状態から、新たに作成したログｊ＋１を先頭に追加すると図４の中段の状態となる。なお、データの書き込みが既に記憶媒体１２上に記録されたファイルのブロックに対するものであったとしても新たなログが作成される。
【００５６】
さらに、ガベージコレクションによってログｉを開放すると、図４の下段に示すように最後尾がログｉ＋１になる。
【００５７】
次に、プロセッサ１０からファイルの読み出しを要求されたファイル処理部１１の動作について説明する。
【００５８】
プロセッサ１０から、ファイルおよびそのファイル中のブロックとを指定して読み出し要求があると、ファイル処理部１１は、指定されたファイルの指定されたブロックのデータを格納している有効なログを記憶媒体１２内から検索する。このとき先頭ログが分かっていれば、そこから最後尾方向に順に対象ログを探していけばよい。また、先頭ログおよび最後尾ログの両方が分かっていれば、その間を探せばよい。検索によって、対象となるログを発見すると、ファイル処理部１１は、そのログに対応する記憶媒体１２のデータを記憶媒体１２から取得し、プロセッサ１０に返却する。
【００５９】
次に、プロセッサ１０からファイルの書き込みを要求されたファイル処理部１１の動作について説明する。図５は、第１の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。ファイル処理部１１は、プロセッサ１０から書き込み要求を受ける。書き込み要求では、データを書き込む対象となるファイルと、そのファイル中のブロックの位置と、書き込むデータとが指定される。
【００６０】
図５を参照すると、まず、ファイル処理部１１は、既に記憶媒体１２に格納されている先頭のログの次に、指定されたデータの書き込みに必要なブロックを確保する（ステップ１００）。次いで、ファイル処理部１１は、ヘッダ部に書き込むヘッダと、データ部に書き込むデータを作成する（ステップ１０１）。
【００６１】
ここでヘッダに書き込むバージョン番号は、その時点での先頭ログのバージョン番号よりも大きい値とする。例えば、バージョン番号は１ずつインクリメントする番号とすればよい。その場合、ファイル処理部１１は、その時点の先頭ログのバージョン番号に１を加算して新たな先頭ログのバージョン番号とする。あるいは、その時点での先頭ログのバージョン番号より大きな値とする代わりに小さな値としてもよい。その場合、バージョン番号が小さい方がより新しく記録したログとなる。
【００６２】
これによって、先頭ログのバージョン番号が全てのログのバージョン番号の中で最も大きな値となり、先頭ログを判別することができるようになる。なお、バージョン番号は、それを表すビット数（桁数）に制限される有限の番号であるが、十分な桁数を確保しておけば、記憶領域１２に存在するログの中から先頭ログを判別できる。
【００６３】
次いで、ファイル処理部１１は、ステップ１００にて確保したブロックに、ステップ１０１で作成したヘッダおよびデータを書き込む（ステップ１０２）。
【００６４】
次いで、ファイル処理部１１は、ステップ１００にて確保した領域が、先頭ログを含むログ領域から他のログ領域に達しているか否か判定する（ステップ１０３）。確保した領域が他のログ領域に達していれば、ファイル処理部１１は、確保した領域が新たに達したログ領域に対応するエントリーに、新たなログを追加する前の時点での先頭ログを含むログ領域のシーケンス番号より大きなシーケンス番号を書き込む（ステップ１０４）。例えば、シーケンス番号は１ずつインクリメントする番号とすればよい。その場合、ファイル処理部１１は、その時点の先頭ログを含むログ領域のシーケンス番号に１を加算して、新たに到達したログ領域のシーケンス番号とする。なお、シーケンス番号は、それを表すビット数（桁数）に制限される有限の番号であるが、十分な桁数を確保しておけば、記憶領域１２に存在するログ領域の中から先頭ログを含むログ領域を判別できる。また、その時点での先頭ログを含むログ領域のシーケンス番号より大きな値とする代わりに小さな値としてもよい。その場合、シーケンス番号が小さい方がより新しく記録したログとなる。
【００６５】
次に、ファイル処理部１１は、ステップ１０２においてデータおよびヘッダを書き込んだログを先頭ログとし、その先頭ログから最後尾の方向に、先頭ログと書き込み対象のファイルおよびブロック位置が同じであるログがあるか記憶媒体１２中を検索し（ステップ１０５）、該当するログが見つかったか否か判定する（ステップ１０６）。
【００６６】
書き込み対象のファイルおよびブロック位置に該当するログが見つかると、ファイル処理部１１は、そのログの無効フラグをセットし（ステップ１０７）、処理を終了する。それが見つからなければ、ファイル処理部１１は、そのまま処理を終了する。
【００６７】
次に、ファイル処理部１１が書き込み処理を異常終了し、無効フラグに矛盾が生じた場合を考慮した動作について説明する。
【００６８】
ここでは、図５のフローチャートに示した書き込み処理において、ステップ１０２を終了した後でステップ１０７を行なう前に、ファイル処理部１１の処理が異常終了したとする。その場合、同じファイルの同じブロックを格納した有効なログが２つ記憶媒体１２上に残ってしまうこととなる。そして、その場合、ヘッダ中のバージョン番号が大きな方が新しいデータである。そこで、ファイル処理部１１は、例えばマウント処理にてバージョン番号が小さい方のログの無効フラグのみをセットし、バージョン番号が大きい方のログを有効とする。これにより、異常終了後に再び記憶媒体１２の使用を開始するとき、正しいデータのファイルが使用可能となる。
【００６９】
次に、ファイルシステムの使用を開始するときのファイル処理部１１の動作について説明する。図６は、ファイルシステムの使用を開始するときのファイル処理部１１の動作を示すフローチャートである。使用開始時には、ファイル処理部１１はマウント処理として様々な処理を実行するが、ここでは本発明に関連する、先頭ログを探索する処理のみを説明する。
【００７０】
図６を参照すると、ファイル処理部１１は、まず、記憶媒体１２のシーケンス番号記憶領域から最大のシーケンス番号を持ったエントリーを調べる（ステップ１１０）。次に、ファイル処理部１１は、そのエントリーに対応するログ領域を、先頭ログを探す対象に定める（ステップ１１１）。そして、ファイル処理部１１は、そのログ領域内の全てのログのヘッダからバージョン番号を読み出す（ステップ１１２）。
【００７１】
次いで、ファイル処理部１１は、得られたバージョン番号の中から最大のものを探し、最大のバージョン番号を有するログを先頭ログと定める（ステップ１１３）。
【００７２】
次に、ファイル処理部１１が書き込み処理を異常終了し、シーケンス番号記録領域とログ領域とで最新のログに矛盾が生じた場合を考慮した動作について説明する。
【００７３】
ここでは、図５のフローチャートに示した書き込み処理において、ステップ１０２を終了した後でステップ１０４を行なう前に、ファイル処理部１１の処理が異常終了したとする。その場合、シーケンス番号記録領域にて最大のシーケンス番号が付与されているエントリーに対応するログ領域に最新ログが無く、その次のログ領域に最新ログがあるという状態が発生しうる。
【００７４】
本実施形態による“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”のファイルシステムでは、記憶領域を順次使用していき、全体を使い終わると、最初に戻って前回の周回でログを記録した領域に新たなログを上書きする。最初の周回では、先頭ログを記録した領域以降はイレースされた状態だが、２回目以降の周回では、先頭ログを記録した領域以降に前回の周回で記録した無効なログが残った状態である。
【００７５】
したがって、ステップ１０２におけるログの書き込みと、ステップ１０４におけるシーケンス番号の書き込みが正常に行われた場合、その先頭ログを記録した以降の領域は、イレースされた状態か、先頭ログよりもシーケンス番号の小さいログが存在する状態のいずれかとなる。
【００７６】
図７Ａは、初回の周回でログが書き込まれている記憶領域の状態を示す図である。ここでは、シーケンス番号記録領域にて最大のシーケンス番号が付与されたエントリーに対応するログ領域をログ領域Ａとする。図７Ａには、ログ領域Ａに先頭ログ５０３が記録された状態が示されている。初回の周回なので、先頭ログ５０３よりも先の領域はイレースされた状態である。
【００７７】
図７Ｂは、２回目以降の周回でログが書き込まれている記憶領域の状態を示す図である。図７Ｂには、シーケンス番号記憶領域にて最大のシーケンス番号が付与されているエントリーに対応するログ領域Ａに先頭ログ５０３が記録された状態が示されている。２回目以降の周回なので、先頭ログ５０３よりも先の領域には、前回の周回で記録されたログ１０、１１、１２・・・が残った状態である。
【００７８】
図７Ｃは、ログ領域の最後までログが書き込まれた記憶領域の状態を示す図である。ここでは２回目以降の周回でログが書き込まれている例を示している。シーケンス番号記憶領域にて最大のシーケンス番号が付与されたエントリーに対応するログ領域Ａのちょうど最後までログが書き込まれている。先頭ログはログ５０４である。ログ領域Ａとログ領域Ａ＋１の境界以降に前回の周回で書き込んだログが残っている。
【００７９】
これらのような正常な状態に対して、新たなログ領域に新たな先頭ログを記録した後、シーケンス番号記憶領域を更新する前に異常終了すると、シーケンス番号記録領域にて最大のシーケンス番号が付与されたエントリーに対応するログ領域には実際には先頭ログがなく、最後までログが埋まった状態となる。その場合、実際の先頭ログは次のログ領域かあるいはその先にある。
【００８０】
図７Ｄは、シーケンス番号記憶領域を更新する前に異常終了した場合の記憶領域の状態を示す図である。図７Ｄを参照すると、シーケンス番号記憶領域にて最大のシーケンス番号が付与されたエントリーに対応するログ領域Ａには、ログ領域Ａ＋１との境界までログが書き込まれている。これだけを見ると図７Ｃに示した正常状態と同様であり区別がつかない。しかし、実際には、さらにログ領域Ａ＋１にもログが書き込まれている。
【００８１】
そこで、本実施形態のファイル処理部１１は、まず、シーケンス番号記録領域にて最大のシーケンス番号が付与されたエントリーに対応するログ領域Ａにおける最後のログのバージョン番号と、ログ領域Ａにおける他のログのバージョン番号を調べる。
【００８２】
このとき、図７Ａまたは図７Ｂに示した状態であれば、次のログ領域以降に先頭ログがある可能性はなく、ログ領域Ａに先頭ログがあると判断できる。しかし、ログ領域Ａの最後までログが書き込まれており、そのログのバージョン番号がログ領域Ａ内で最大であった場合、図７Ｃの正常状態か、図７Ｄの異常状態か判断できない。そこで、ファイル処理部１１は、その場合には次のログ領域Ａ＋１を調べる必要がある。
【００８３】
ログ領域の最後までログが書き込まれており、かつ最後のログのバージョン番号がログ領域Ａの中で最大であれば、ファイル処理部１１は、次のログ領域Ａ＋１における最初のログのヘッダに含まれるバージョン番号を確認する。
【００８４】
そして、ログ領域Ａの最後のログのバージョン番号よりもログ領域Ａ＋１の最初のログのバージョン番号の方が大きければ、ファイル処理部１１は、ログ領域Ａ＋１中から先頭ログとなるべきログを探す。そして、ファイル処理部１１は、シーケンス番号記録領域中のログ領域Ａ＋１に対応したエントリーに、ログ領域Ａに付与されているシーケンス番号より大きな値を書き込む。
【００８５】
これにより、異常終了後に再び記憶媒体１２の使用を開始するとき、正しい先頭ログの認識が可能となる。
【００８６】
また、これによれば、異常終了した状態から本来の先頭ログが記録されたログ領域を検出すると、このとき新たなログを書き込む動作が有っても無くても、ファイル処理部１１はバージョン番号記憶領域を修正して正常な状態に戻すこととなる。書き込み動作がないときバージョン番号記憶領域を修正しなければ、次回の起動時に再び２つのログ領域Ａおよびログ領域Ａ＋１の両方を探索する必要があり、無駄な処理が生じるからである。本実施形態では、書き込み動作の有無によらずバージョン番号記憶領域を修正するので、記憶媒体１２上の状態を正しくすることができ、次にファイルシステムを使用開始する際には探索範囲を広くする必要が減る。
【００８７】
なお、本実施形態のファイルシステムは、他の一般的な“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄファイルシステム”と同様にガベージコレクションを行なう。その際、ファイル処理部１１は、有効なログの範囲を小さくし、記憶媒体１２中の先頭ログよりも先の領域に未使用なブロックを確保するように、ヘッダの無効フラグを参照しながらログを整理する。
【００８８】
本実施形態では、記憶媒体１２のシーケンス番号記憶領域に各ログ領域のシーケンス番号のみを記録していた。しかし、本実施形態の変形例として、各ログ領域のシーケンス番号に加えて、そのログ領域に最初に格納されたログの開始位置情報を記録することとしてもよい。これにより、ログの境界がログ領域の境界に一致していない場合でもログの境界を容易に認識できるようなる。
【００８９】
図８は、記憶媒体にて、ログ領域の境界を跨いでログが格納された様子を示す図である。図８に示すように、ログｋが新たに格納されると、先頭ログはログ領域ｉ−１からログ領域ｉに替わる。
【００９０】
その際、この変形例では、シーケンス番号記憶領域のログ領域ｉに対応するエントリーにログ領域ｉ−１のシーケンス番号より大きなシーケンス番号が記録される。そして、それに加えてログ領域ｉのエントリーに、ログｋの開始位置を示す開始位置情報をも記録することとする。これにより、ログｋの開始位置がログ領域の境界と一致していない場合でもその開始位置を容易に知ることができ、またそれ以降の各ログを個別に識別することができる。
【００９１】
以上説明したように、本実施形態によれば、記憶媒体１２に記録されたログの管理情報であるシーケンス番号を記憶する領域は複数エントリーを記録可能であり、新たなログ領域にログを追加するために管理情報の記録が必要になると、その管理情報を前回のエントリーに上書きせず、新たなエントリーとして追加する。そのため、使用開始時に管理情報を参照して迅速に先頭ログを検出できるので、記憶領域全体を確認する処理が不要となり、使用開始にかかる時間が短縮される。また、それと共に、管理情報を前回と同じ領域に上書きすることなく新たなエントリーとして追加することで、管理情報を記録する領域の消去回数を低減し、記憶媒体１２の使用可能期間を長期化させることができる。
【００９２】
また、本実施形態では、ログを記録する領域が複数のログ領域に分割され、管理情報を格納するシーケンス番号記憶領域もそれぞれのログ領域に対応する複数の領域に分割されており、シーケンス番号記憶領域への管理情報の書き込みは、対応するログ領域への最初の書き込み時にのみ行なうので、シーケンス番号記憶領域の消去回数をログ領域と均等にすることができ、記憶媒体１２の使用可能期間を長期化させることができる。
【００９３】
また、本実施形態によれば、管理情報として記録した複数エントリーのシーケンス番号より最新エントリーを見つけ、そのエントリーに対応するログ領域を探索対象とし、そのログ領域にある各ログのバージョン番号から先頭ログを検出するので、使用開始にかかる時間を短縮することができる。
【００９４】
また、本実施形態によれば、各エントリーには、対応するログ領域の最初のログの開始位置を示す情報が含まれるので、ログ領域とログの境界が一致していなくても容易にログの位置を認識することができ、使用開始にかかる時間を短縮することができる。
【００９５】
（第２の実施形態）
第２の実施形態は、各ログ領域のシーケンス番号を格納する領域がログ領域毎に分離して配置されている点で第１の実施形態と異なる。
【００９６】
図９は、第２の実施形態によるコンピュータシステムの構成を示すブロック図である。図９を参照すると、コンピュータシステムは、プロセッサ２０、ファイル処理部２１、および記憶媒体２２を有している。プロセッサ２０および記憶媒体２２は、第１の実施形態におけるプロセッサ１０および記憶媒体１２と同様のものである。
【００９７】
ファイル処理部２１は、第１の実施形態のファイル処理部１１と同様に、プロセッサ２０から記憶媒体２２へのアクセスを仲介し、プロセッサ２０の要求により記憶媒体２２上のファイルの書き込みおよび読み出しを行う。
【００９８】
また、本実施形態のファイル処理部２１で用いられるファイルシステムは“ｌｏｇ−ｓｕｒｕｃｔｕｒｅｄ”である。したがって、記憶媒体２２上に既に記録されているファイル中のブロックに対する書き込み、すなわち「アップデート書き込み」であったとしても、ファイル処理部２１は古いデータに上書きすることはせず、記憶媒体２２上に新たなログを作成する。
【００９９】
本実施形態のファイル処理部２１が第１の実施形態と異なるのは領域管理情報がログ領域毎に分離して配置される点である。
【０１００】
図１０は、第２の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。図１０を参照すると、記憶媒体２２の記憶領域は、複数の領域０〜Ｍに分割される。分割された各領域は、同一サイズであってもよく、あるいは異なるサイズであってもよい。そして、それら各領域は、領域管理情報とログ領域から構成されている。領域管理情報には、対応するログ領域のシーケンス番号が含まれている。ログ領域は複数のログを記憶する領域である。ここでのログは第１の実施形態におけるログと同じものであり、図３に示したようにヘッダ部およびデータ部からなる。
【０１０１】
次に、本実施形態のコンピュータシステムの動作について説明する。
【０１０２】
プロセッサ２０からファイルの読み出しを要求されたファイル処理部２１の動作については、第１の実施形態のファイル処理部１１の動作と同様である。
【０１０３】
図１１は、第２の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。ファイル処理部２１は、既に記憶媒体２２に格納されている先頭ログの次以降の領域に、データの書き込みに必要なブロックを確保する（ステップ１２０）。次に、ファイル処理部２１は、ステップ１２０にて確保したブロックが、その時点での先頭ログを含む領域に収まっているか、あるいは次の領域に跨っているかを判定する（ステップ１２１）。
【０１０４】
ステップ１２０で確保したブロックが領域を跨いでいれば、ファイル処理部２１は、ステップ１２０で確保したブロックを開放し、次の領域の先頭からデータを書き込むのに必要なブロックを確保する（ステップ１２２）。
【０１０５】
次いで、ファイル処理部２１は、ステップ１２２にて新たにブロックを確保した領域用の領域管理情報およびログを作成する（ステップ１２３）。領域管理情報には、その領域のシーケンス番号が含まれる。その領域管理情報に書き込むシーケンス番号は、その時点の先頭ログを含む領域のシーケンス番号よりも大きな値とする。
【０１０６】
また、ログにはヘッダおよびデータが含まれる。ここでヘッダに書き込むバージョン番号は、その時点での先頭ログのバージョン番号よりも大きい値とする。これによって、新たな先頭ログのバージョン番号が全てのログのバージョン番号の中で最も大きな値となり、先頭ログを判別できるようになる。
【０１０７】
次いで、ファイル処理部２１は、その領域管理情報およびログを記録媒体２２上に確保しておいた領域に書き込む（ステップ１２４）。また、それに伴い、ファイル処理部２１が自身の内部に記録する、先頭ログを示す情報をステップ１２４にて書き込んだログへと変更する。
【０１０８】
一方、ステップ１２０で確保したブロックが領域を跨いでいなければ、ファイル処理部２１は、プロセッサ２０から指定されたデータ等からログのヘッダおよびデータを作成する（ステップ１２５）。次いで、ファイル処理部２１は、ステップ１２０にて記憶媒体２２上に確保したブロックに、ステップ１２１にて作成したデータを書き込む（ステップ１２６）。また、それに伴い、ファイル処理部２１が自身の内部に記録する、先頭ログを示す情報をステップ１２４にて書き込んだログへと変更する。
【０１０９】
ステップ１２４の処理またはステップ１２６の処理の後、ファイル処理部２１は、書き込み対象とされているファイルおよびブロック位置に該当するログを記憶媒体２２上の既存のログから検索する（ステップ１２７）。そして、書き込み対象のファイルおよびブロック位置が既存のログとして発見できたか否か判定する（ステップ１２８）。
【０１１０】
書き込み対象のファイルおよびブロック位置が既存のログとして存在していれば、ファイル処理部２１は、その既存のログの無効フラグをセットし（ステップ１２９）、処理を終了する。書き込み対象のファイルおよびブロック位置が既存のログとして存在していなければ、ファイル処理部２１は、そのまま処理を終了する。
【０１１１】
なお、上述したように、本実施形態では、第１の実施形態と異なり、各ログ領域のシーケンス番号を含む領域管理情報が、各ログ領域を含む領域内に、ログ領域と連続して配置されている。これにより、領域管理情報とログとを連続したブロックとして１回の処理で書き込むことができるので、領域管理情報とログのいずれか一方のみが更新され、最大のシーケンス番号を有する領域に先頭ログが無いという矛盾した状態の発生を低減することができる。
【０１１２】
また、各ログ領域のエントリーを消去の単位としなければ、消去回数を書き換え回数と同じにできない。ＮＡＮＤ型フラッシュメモリのように、消去の最小単位が大きな記憶媒体では、エントリーをシーケンス番号記憶領域としてまとめると、各エントリーの領域が必要以上に大きくなり記憶媒体の使用効率が悪い。これに対して、本実施形態では、領域管理情報を、対応する領域内の最初の部分に配置している。そのため、その領域に先頭ログが移動して領域管理情報の更新が必要となったときに書き込むログと領域管理情報が同じ領域内にあるので、領域管理情報のために消去の最小単位を割り当てなくても、消去回数と書き換え回数を一致させることができ、記憶媒体の使用効率がよい。
【０１１３】
なお、図１１のステップ１２１にてブロックが領域をまたぐとき、本実施形態では、次の領域に新たにブロックを割り当てることとした。領域管理情報が各領域内あるので、領域をまたいでログを記録することができないからである。しかし、本発明は、これに限定されるものではない。記録しようとするデータがログ領域をまたぎそうなとき、そのデータを分割して２つのログにしてもよい。そして、１つのログをこれまでのログ領域に記録し、もう１つのログを新たなログ領域に記録すればよい。
【０１１４】
具体的には、図１１のステップ１２２にて、ステップ１２０で割り当てたブロックに収まる部分と残りの部分との２つのログにデータを分割し、残り部分の方のログにブロックを割り当てることとすればよい。
【０１１５】
次に、ファイル処理部２１が書き込み処理を異常終了し、無効フラグに矛盾が生じた場合の動作について説明する。
【０１１６】
ここでは、図１１のフローチャートに示した書き込み処理において、ステップ１２４を終了した後でステップ１２９を行なう前に、またはステップ１２６を終了した後でステップ１２９を行なう前に、ファイル処理部２１の処理が異常終了したとする。その場合、同じファイルの同じブロックを格納した有効なログが２つ記憶媒体２２上に残ってしまうこととなる。そして、その場合、ヘッダ中のバージョン番号が大きな方が新しいデータである。そこで、ファイル処理部２１は、例えばマウント処理にてバージョン番号が小さいログの無効フラグのみをセットすることにより、バージョン番号が大きいログを有効とする。これにより、異常終了後に再び記憶媒体２２の使用を開始するとき、正しいデータのファイルが使用可能となる。
【０１１７】
なお、本実施形態においてＮＡＮＤ型フラッシュメモリを用いた場合、フラッシュメモリの各ページにある付加領域の一部をシーケンス番号の格納先として利用してもよい。これにより、記憶媒体２２の利用効率を高めることができる。
【０１１８】
また、図１１に示したフローチャートのステップ１２２において、次の領域にログを格納するためのブロックを割り当てたが、本発明はこれに限定されるものではない。他の方法として、書き込もうとするデータを、先頭ログを含む領域に収まる範囲の部分（以下「第１の部分」という）と残りの部分（以下「第２の部分」という）とに分けて複数のログとしてもよい。そして、第１の部分を先頭ログが含まれている領域に格納し、第２の部分を次の領域に格納してもよい。これにより、記憶媒体２２中に使用されないブロックがなくなり、記憶媒体２２の使用効率を高めることができる。
【０１１９】
次に、ファイルシステムの使用を開始するときのファイル処理部２１の動作について説明する。図１２は、ファイルシステムの使用を開始するときのファイル処理部２１の動作を示すフローチャートである。使用開始時には、ファイル処理部２１は様々な処理を実行するが、ここでは本発明に関連する、先頭ログの範囲を探索する処理のみを説明する。
【０１２０】
図１２を参照すると、ファイル処理部２１は、まず、記憶媒体２２の全領域の領域管理情報からシーケンス番号を読み出し、シーケンス番号が最大の（分割された）領域を調べる（ステップ１３０）。次に、ファイル処理部２１は、その領域内のログ領域を、先頭ログを探す対象に定める（ステップ１３１）。そして、ファイル処理部２１は、そのログ領域内の全てのログのヘッダからバージョン番号を読み出す（ステップ１３２）。
【０１２１】
次いで、ファイル処理部２１は、得られたバージョン番号の中から最大のものを探し、最大のバージョン番号を有するログを先頭ログと定める（ステップ１３３）。先頭ログの判定はこのようにして行われる。
【０１２２】
また、本実施形態のファイルシステムは、第１の実施形態と同様にガベージコレクションを行なう。
【０１２３】
また、先頭ログを含む領域以外の領域の領域管理情報は、ガベージコレクションの際に消去する。図１２のフローチャートにおけるステップ１３０では、消去された状態の領域管理情報は比較対照としない。
【０１２４】
以上説明したように、本実施形態によれば、各ログ領域の領域管理情報の各々は、対応するログ領域と同じ領域の内部に配置されているので、領域管理情報とログとを連続したブロックとして１回の処理で書き込むことができるので、領域管理情報とログのいずれか一方のみが更新され、最大のシーケンス番号を有する領域に先頭ログが無いという矛盾した状態の発生を低減することができる。
【０１２５】
また、上述した第１または第２の実施形態の書き込み処理において、新たに書き込むログのヘッダに、その時点での最後尾ログを示す参照情報を付加することとしてもよい。参照情報の例としては、記憶領域中の一意の位置を示すオフセットアドレスが考えられる。ファイルシステムの使用開始時に先頭ログを割り出したら、そのログのヘッダに記録された参照情報によって示されたログから順に先頭方向に進み、最初の有効なログが最後尾ログである。したがって、最後尾ログを割り出すとき、全てのログの有効か無効かを調べる必要が無くなる。
【０１２６】
これによれば、ファイルシステムの使用開始時に最後尾ログの割り出しが必要な場合に、その参照情報を用いることで最後尾ログの割り出しにかかる時間を短縮することができ、ファイルシステムの使用開始にかかる時間を短縮することができる。
【０１２７】
また、上述した第１または第２の実施形態のログ領域に対応するシーケンス番号を格納するエントリーに、シーケンス番号を書き込む時点での最後尾ログを示す参照情報を付加することとしてもよい。その場合、書き込み処理において、新たなログ領域にログを書き込むとき、その時点での最後尾ログを示す参照情報を付加すればよい。ファイルシステムの使用開始時に先頭ログを含むログ領域が分かったら、そのログ領域に対応するエントリーに記録された参照情報によって示されたログから順に先頭方向に進み、最初の有効なログが最後尾ログである。したがって、最後尾ログを割り出すとき、全てのログの有効無効を調べる必要が無くなる。
【０１２８】
また、上述した第１または第２の実施形態のログ領域に対応するシーケンス番号を格納するエントリーに、先頭ログを検出するためのシーケンス番号（以下「第１のシーケンス番号」という）だけでなく、最後尾ログを検出するためのシーケンス番号（以下「第２のシーケンス番号」という）をも付加することとしてもよい。その場合、ファイル処理部２１は、最後尾ログが替わるガベージコレクション処理において、最後尾ログがログ領域を跨いで替わったとき、新たな最後尾ログを含むログ領域に対応するエントリーに、替わる前の最後尾ログを含むログ領域の第２のシーケンス番号よりも大きな第２のシーケンス番号を記録すればよい。そして、ファイルシステムの使用開始時には、ファイル処理部２１は、第１のシーケンス番号から先頭ログを特定するのと同様の方法で、第２のシーケンス番号から最後尾ログを特定すればよい。最新の最後尾ログを含むログ領域は、第２のシーケンス番号を参照することで知ることができる。そして、そのログ領域内の有効なログの中でバージョン番号が最も小さいログが最後尾ログである。
【０１２９】
これによっても、ファイルシステムの使用開始時に最後尾ログの割り出しが必要な場合に、最後尾ログの割り出しにかかる時間を短縮することができ、ファイルシステムの使用開始にかかる時間を短縮することができる。
【０１３０】
（第３の実施形態）
第１および第２の実施形態では、ログを記録するデータ領域とシーケンス番号等の管理情報を記録する管理領域との両方をそれぞれ複数に分割したが、第３の実施形態は、管理情報を記録する領域のみを複数に分割する。
【０１３１】
図１３は、第３の実施形態によるコンピュータシステムの構成を示すブロック図である。図１３を参照すると、コンピュータシステムは、プロセッサ３０、ファイル処理部３１、および記憶媒体３２を有している。プロセッサ３０および記憶媒体３２は、第１の実施形態におけるプロセッサ１０および記憶媒体１２と同様のものである。
【０１３２】
ファイル処理部３１は、第１の実施形態のファイル処理部１１と同様に、プロセッサ３０から記憶媒体３２へのアクセスを仲介し、プロセッサ３０の要求により記憶媒体３２上のファイルの書き込みおよび読み出しを行う。
【０１３３】
また、本実施形態のファイル処理部３１で用いられるファイルシステムは“ｌｏｇ−ｓｕｒｕｃｔｕｒｅｄ”である。したがって、記憶媒体３２上に既に記録されているファイル中のブロックに対する書き込み、すなわち“アップデート書き込み”であったとしても、ファイル処理部３１は古いデータに上書きすることはせず、新たなログを作成して記憶媒体３２上に追加する。
【０１３４】
本実施形態のファイル処理部３１が第１の実施形態と異なるのは、管理情報を記録する領域のみを複数に分割し、ログを記録する領域は分割しない点である。
【０１３５】
図１４は、第３の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。図１４を参照すると、記憶媒体３２の記憶領域は、管理情報記憶領域とデータ領域に分割される。そして、管理情報記憶領域は、さらに複数エントリーの管理領域０〜Ｍに分割される。
【０１３６】
各管理領域には、データ領域に書き込まれたログの参照情報と、管理領域のシーケンス番号とが記録される。本実施形態でいうシーケンス番号は、第１の実施形態でいうシーケンス番号と異なり、ログの参照情報を書き込んだ順序を示す番号である。このシーケンス番号により各管理領域の新しさを知ることができる。ログの参照情報は、データ領域に書き込まれたログを示す情報であり、例えばオフセットアドレスにより示される。最も新しい管理領域にある参照情報により示されたログが先頭ログであると判断できる。ここでのログは第１の実施形態のログと同様、図３に示したようにヘッダ部およびデータ部からなる。
【０１３７】
次に、本実施形態のコンピュータシステムの動作について説明する。
【０１３８】
プロセッサ３０からファイルの読み出しを要求されたファイル処理部３１の動作については、第１の実施形態のファイル処理部１１の動作と同様である。
【０１３９】
次に、プロセッサ３０からファイルの書き込みを要求されたファイル処理部３１の動作について説明する。図１５は、第３の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。ファイル処理部３１は、プロセッサ３０から書き込み要求を受けて書き込み動作を行う。
【０１４０】
図１５を参照すると、まず、ファイル処理部３１は、既に記憶媒体３２に格納されている先頭のログの次に、指定されたデータの書き込みに必要なブロックを確保する（ステップ１４０）。次いで、ファイル処理部３１は、ログのヘッダ部に書き込むヘッダと、データ部に書き込むデータを作成する（ステップ１４１）。
【０１４１】
次いで、ファイル処理部３１は、ステップ１４０にて確保したブロックに、ステップ１４１で作成したヘッダおよびデータからなるログを書き込む（ステップ１４２）。
【０１４２】
ステップ１４２にて書き込んだログが新たな先頭ログとなるので、ファイル処理部３１は、管理情報記憶領域を更新する（ステップ１４３）。その際、ファイル管理部３１は、各エントリーの中からシーケンス番号が最大のエントリーを探すことにより、その時点で最新の管理情報が記録されている管理領域のエントリーを調べる。そして、ファイル処理部３１は、その次のエントリーに、新たに記録したログの参照情報と、最大のエントリーよりも大きな値のシーケンス番号とを記録する。
【０１４３】
次に、ファイル処理部３１は、ステップ１４２にて書き込んだログを先頭ログとし、書き込み対象のファイルおよびブロック位置に該当するログがあるか記憶媒体３２中を検索し（ステップ１４４）、該当するログが見つかったか否か判定する（ステップ１４５）。
【０１４４】
書き込み対象のファイルおよびブロック位置に該当するログが見つかれば、ファイル処理部３１は、そのログの無効フラグをセットし（ステップ１４６）、処理を終了する。それが見つからなければ、ファイル処理部３１は、そのまま処理を終了する。
【０１４５】
次に、ファイルシステムの使用を開始するときのファイル処理部１１の動作について説明する。図１６は、第３の実施形態におけるファイルシステムの使用を開始するときのファイル処理部３１の動作を示すフローチャートである。使用開始時には、ファイル処理部３１は様々な処理を実行するが、ここでは本発明に関連する、先頭ログの範囲を探索する処理のみを説明する。
【０１４６】
図１６を参照すると、ファイル処理部３１は、まず、記憶媒体３２の管理情報記憶領域から最大のシーケンス番号を持ったエントリーを調べる（ステップ１５０）。次に、ファイル処理部３１は、そのエントリーに記録されたログの参照情報（オフセットアドレス）を取得し、その参照情報の示すログを先頭ログと定める（ステップ１５１）。
【０１４７】
次に、ファイル処理部３１が書き込み処理を異常終了し、管理情報記憶領域とデータ領域とで最新のログに矛盾が生じた場合を考慮した動作について説明する。
【０１４８】
ここでは、図１５のフローチャートに示した書き込み処理において、ステップ１４２を終了した後でステップ１４３を行なう前に、ファイル処理部３１の処理が異常終了したとする。その場合、管理情報記憶領域にて最大のシーケンス番号が付与されているエントリーに対応するログが実際の先頭ログではなく、それよりも先に実際の先頭ログがあるという状態が発生しうる。
【０１４９】
書き込み処理が正常終了すると、データ領域に記録された先頭ログ以降の領域は、イレースされた状態か、先頭ログよりもバージョン番号の小さい前回の周回で記録したログがある状態のいずれかとなる。
【０１５０】
そこで、管理情報記憶領域に記録されたエントリーにシーケンス番号から先頭と判断されたログ以降の領域を調べることとすればよい。ファイル処理部３１は、管理情報記憶領域にて最大のシーケンス番号のエントリーを調べる。次に、ファイル処理部３１は、シーケンス番号が最大のログ以降の領域を、イレースされた状態となるか、記録されているログのバージョン番号が小さくなるまで調べていく。そして、イレースされた状態の手前にあるログ、あるいはバージョン番号が小さくなったログの手前にあるログを先頭ログと定める。
【０１５１】
さらに、シーケンス番号が最大のエントリーが先頭ログでなかった場合には、それまで最大であったシーケンス番号よりも大きなシーケンス番号と、その先頭ログの参照情報とを次のエントリーに記録する。これにより、記憶媒体３２上の状態を正しくすることができ、次にファイルシステムを使用開始する際の先頭ログを検出する処理の時間が短縮される。
【０１５２】
本実施形態によれば、“ｌｏｇ−ｓｔｒｕｃｔｕｒｅｄ”ファイルシステムにおいて、データ領域にログを記録するとき、そのログの参照情報と記録順序を示すシーケンス番号とを含む管理情報のエントリーを管理情報記憶領域に記録するので、記憶領域全体を調べなくても管理情報記憶領域を参照することにより先頭ログを容易に検出することができる。また、管理情報記憶領域の複数のエントリーを周回して管理情報が記録されるので、管理情報記憶領域の消去回数を減らし、記憶媒体の使用可能期間を長くすることができる。
【０１５３】
なお、本実施形態では、先頭ログの検出を例示したが本発明はこれに限定されるものではない。他の例として、本発明はＬＦＳにおけるインデックスファイルの検出にも同様に適用可能である。その場合、インデックスファイルの位置を示すスーパーブロックにシーケンス番号を付与し、複数のエントリーに周回して記録することとすればよい。
【図面の簡単な説明】
【０１５４】
【図１】第１の実施形態によるコンピュータシステムの構成を示すブロック図である。
【図２】第１の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。
【図３】ログ領域に格納されるログの構成を示す図である。
【図４】記憶媒体に格納されているデータの変化の一例を示す図である。
【図５】第１の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。
【図６】ファイルシステムの使用を開始するときのファイル処理部１１の動作を示すフローチャートである。
【図７Ａ】初回の周回でログが書き込まれている記憶領域の状態を示す図である。
【図７Ｂ】２回目以降の周回でログが書き込まれている記憶領域の状態を示す図である。
【図７Ｃ】ログ領域の最後までログが書き込まれた記憶領域の状態を示す図である。
【図７Ｄ】シーケンス番号記憶領域を更新する前に異常終了した場合の記憶領域の状態を示す図である。
【図８】記憶媒体にて、ログ領域の境界を跨いでログが格納された様子を示す図である。
【図９】第２の実施形態によるコンピュータシステムの構成を示すブロック図である。
【図１０】第２の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。
【図１１】第２の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。
【図１２】ファイルシステムの使用を開始するときのファイル処理部の動作を示すフローチャートである。
【図１３】第３の実施形態によるコンピュータシステムの構成を示すブロック図である。
【図１４】第３の実施形態にて、記憶媒体に格納されるデータの配置イメージを示す図である。
【図１５】第３の実施形態における、ファイル処理部の書き込み動作を示すフローチャートである。
【図１６】第３の実施形態におけるファイルシステムの使用を開始するときのファイル処理部の動作を示すフローチャートである。
【符号の説明】
【０１５５】
１０、２０、３０    プロセッサ
１１、２１、３１    ファイル処理部
１２、２２、３２    記憶媒体
１００〜１０７、１１０〜１１３、１２０〜１２９、１３０〜１３３、１４０〜１４６、１５０、１５１    ステップ
【図１】
0004766240.tif 000002
【図２】
0004766240.tif 000003
【図３】
0004766240.tif 000004
【図４】
0004766240.tif 000005
【図５】
0004766240.tif 000006
【図６】
0004766240.tif 000007
【図７Ａ】
0004766240.tif 000008
【図７Ｂ】
0004766240.tif 000009
【図７Ｃ】
0004766240.tif 000010
【図７Ｄ】
0004766240.tif 000011
【図８】
0004766240.tif 000012
【図９】
0004766240.tif 000013
【図１０】
0004766240.tif 000014
【図１１】
0004766240.tif 000015
【図１２】
0004766240.tif 000016
【図１３】
0004766240.tif 000017
【図１４】
0004766240.tif 000018
【図１５】
0004766240.tif 000019
【図１６】
0004766240.tif 000020