(57)【要約】      （修正有）【課題】データ記憶システム用のログ構造書込みキャッシュおよび記憶システムの性能を向上させること。【解決手段】記憶システムとして、ＲＡＩＤ、磁気ディスク、光ディスク、磁気テープ記憶などがある。書込みキャッシュは、好ましくは主記憶に実装されるが他の記憶要素でもよく、書込みデータを一時的に不揮発状態で蓄積するキャッシュ・ラインを含む。これにより後で目標記憶位置にデータを順次書き込む事でシステム性能を向上させる。各キャッシュ・ラインごとのメタ・データも、書込みキャッシュに保持される。メタ・データは、ライン中の各セクタに対する目標セクタ・アドレス、およびキャッシュ・ラインに記入されるデータの順序を示す番号を含む。バッファ・テーブルのエントリは、各キャッシュ・ラインごとに提供される。ハッシュ・テーブルは、各データ読出し/書込みに必要なセクタ・アドレスを求めてバッファ・テーブルを探索するのに使用される。【選択図】図１
2004213647.tif 000002
【特許請求の範囲】
【請求項１】
セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体と、
複数のキャッシュ・ラインを有する書込みキャッシュであって、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを備え、
前記書込みキャッシュが、システムの性能を向上させるように、データが順次書き込まれるステージング領域として作用するデータ記憶システム。
【請求項２】
各キャッシュ・ラインが、前記キャッシュ・ラインの一部が失われた場合に前記キャッシュ・ライン中のデータの回復を可能にするパリティ・ブロックをさらに備える、請求項１に記載の記憶システム。
【請求項３】
書込みデータが、前記書込みキャッシュに記入された後で前記システムの前記セクタ・アドレスに書き込まれる、請求項１に記載の記憶システム。
【請求項４】
前記書込みキャッシュが、前記システムの不揮発性メモリ中に維持される、請求項１に記載の記憶システム。
【請求項５】
ホスト・システムおよび前記書込みキャッシュと相互作用する書込みキャッシュ制御をさらに備える、請求項１に記載の記憶システム。
【請求項６】
前記ラインのメタ・データが、前記キャッシュ・ラインを識別するためのシーケンス番号を含む、請求項１に記載の記憶システム。
【請求項７】
前記ラインのメタ・データが、複数のエントリを有するラインのバッファ・テーブルを含み、各エントリが、目標セクタ・アドレス、およびブロック中で占められているセクタ位置を示すビットマップを有する、請求項１に記載の記憶システム。
【請求項８】
前記キャッシュ・ラインすべてに対する前記ラインのバッファ・テーブルが、セクタ・アドレスの探索を可能にするために１つのバッファ・テーブルに統合される、請求項７に記載の記憶システム。
【請求項９】
前記バッファ・テーブルがハッシュ・テーブルを用いて探索される、請求項８に記載の記憶システム。
【請求項１０】
前記バッファ・テーブルおよび前記ハッシュ・テーブルを管理するキャッシュ制御をさらに備える、請求項９に記載の記憶システム。
【請求項１１】
前記媒体が前記書込みキャッシュ全体のための前記ラインのメタ・データのスナップショットを含み、前記スナップショットが、システムがシャットダウンした場合にデータを回復するために用いられる、請求項１に記載の記憶システム。
【請求項１２】
前記キャッシュ・ラインが、クラスタとして前記媒体上でグループ化される、請求項１に記載の記憶システム。
【請求項１３】
前記システムがディスク・ドライブである、請求項１に記載の記憶システム。
【請求項１４】
前記システムが光ディスク・ドライブである、請求項１に記載の記憶システム。
【請求項１５】
前記システムがディスク・アレイである、請求項１に記載の記憶システム。
【請求項１６】
前記システムが記憶サーバである、請求項１に記載の記憶システム。
【請求項１７】
セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体を有するデータ記憶システムの性能を向上させる方法であって、
前記媒体上に書込みキャッシュを提供するステップであって、前記書込みキャッシュが複数のキャッシュ・ラインを有し、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを有するステップと、
前記システムの性能を向上させるように、書込みデータを、順次書き込まれるデータとして前記書込みキャッシュにステージングするステップとを含む方法。
【請求項１８】
前記ステージングするステップが、
前記システムに書き込まれる複数のデータ・ブロックを受け取るステップと、
前記データ・ブロックを前記キャッシュ・ラインの１つに格納するステップと、
前記キャッシュ・ライン用のメタ・データを生成するステップであって、前記メタ・データが、前記キャッシュ・ラインのシーケンス番号および前記データ・ブロックの前記アドレスを含むステップと、
前記メタ・データを前記キャッシュ・ラインに格納するステップとを含む、請求項１７に記載の方法。
【請求項１９】
前記キャッシュ・ライン中のデータ用の複数のパリティ・ブロックを計算するステップと、
前記パリティ・ブロックを前記キャッシュ・ラインに書き込むステップとをさらに含む、請求項１８に記載の方法。
【請求項２０】
前記媒体上にスナップショット領域を提供するステップと、
データが前記書込みキャッシュに書き込まれた後で、前記キャッシュ・ラインの前記メタ・データのコピーを前記スナップショット領域に書き込むステップとをさらに含む、請求項１７に記載の方法。
【請求項２１】
前記スナップショットのメタ・データに基づく初期化に続いて、前記書込みキャッシュの状態を判定するステップをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記判定するステップが、
前記スナップショットのメタ・データを読み出すステップと、
現在キャッシュ済であるデータを含む前記キャッシュ・ラインを判定するステップと、
前記判定されたキャッシュ・ラインに関連づけられた前記メタ・データに基づいて、前記書込みキャッシュの前記状態を判定するステップとを含む、請求項２１に記載の方法。
【請求項２３】
記憶システムとともに用いて、前記システムの性能を向上させるコンピュータ・プログラムであって、前記システムが、セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体を有し、前記プログラムはコンピュータ可読媒体に記憶され、コンピュータを
前記媒体上に書込みキャッシュを提供する手段であって、前記書込みキャッシュが複数のキャッシュ・ラインを有し、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを有する手段と、
前記システムの性能を向上させるように、書込みデータを、順次書き込まれるデータとして前記書込みキャッシュにステージングする手段
として機能させるコンピュータ・プログラム。
【請求項２４】
前記ステージングする手段が、
前記システムに書き込まれる複数のデータ・ブロックを受け取る手段と、
前記データ・ブロックを前記キャッシュ・ラインの１つに格納する手段と、
前記キャッシュ・ライン用のメタ・データを生成する手段であって、前記メタ・データが、前記キャッシュ・ラインのシーケンス番号および前記データ・ブロックの前記アドレスを含む手段と、
前記メタ・データを前記キャッシュ・ラインに格納する手段とを含む、請求項２３に記載のコンピュータ・プログラム。
【請求項２５】
前記キャッシュ・ライン中のデータ用の複数のパリティ・ブロックを計算する手段と、
前記パリティ・ブロックを前記キャッシュ・ラインに書き込む手段とをさらに備える、請求項２４に記載のコンピュータ・プログラム。
【請求項２６】
前記媒体上にスナップショット領域を提供する手段と、
データが前記書込みキャッシュに書き込まれた後で、前記キャッシュ・ラインの前記メタ・データのコピーを前記スナップショット領域に書き込む手段とをさらに備える、請求項２３に記載のコンピュータ・プログラム。
【請求項２７】
前記スナップショットのメタ・データに基づく初期化に続いて、前記書込みキャッシュの状態を判定する手段をさらに備える、請求項２６に記載のコンピュータ・プログラム。
【請求項２８】
前記判定する手段が、
前記スナップショットのメタ・データを読み出す手段と、
現在キャッシュ済であるデータを含む前記キャッシュ・ラインを判定する手段と、
前記判定されたキャッシュ・ラインに関連づけられた前記メタ・データに基づいて、前記書込みキャッシュの前記状態を判定する手段とを備える、請求項２７に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にはデータ記憶装置およびシステムに関し、より詳細には、無作為なデータ書込みを順次式のデータ書込みに変換することによってこうした装置およびシステムの性能を向上させるログ構造の書込みキャッシュに関する。
【背景技術】
【０００２】
無作為書込みを順次書込みに変換することによってデータの書込み性能を向上させるために、ログ構造の記憶システムが提案されている。ハードディスク・ドライブなどの記憶装置は、無作為なＩ／Ｏによるスループットより数段速い、順次アクセスによるスループットを有する。しかし、ログ構造の記憶装置およびシステムは実装費用が高く、重大な欠点を有する。無作為書込みを順次書込みに変換しても、順次読出しは無作為読出しに変換される傾向にあり、それによって性能上の利得が打ち消される。一般に、ログ・ベースのファイル・システムは、実装し管理するのがより複雑である。その結果、ログ構造の記憶装置およびシステムはあまり採用されていない。
【０００３】
Kenchammana-HoskoteおよびSarkar（米国特許出願公報ＵＳ２００２／０１０８０１７Ａ１）は、従来技術による、データ書込みが別個の記憶装置に順次ログ収集され、ログに関連づけられたメタ・データがログとは別々に記録されるという解決策を説明している。この解決策は、性能の一貫性を維持するためにログが主要媒体から独立している必要があるので、単一の主要記憶媒体の場合には現実的ではない。
【０００４】
MattsonおよびMenon（米国特許第５，４１６，９１５号）は、別の従来技術による、ディスクのアレイ全体で書込み動作を並列に行うことによって書込み性能を高めるという解決策を説明している。この解決策は、順次書込みの性能を利用していない。
【０００５】
ローゼンブルーム（Rosenblum）他（「ログ構造ファイル・システムの設計および実装（TheDesign and Implementation of a Log Structured File System）」、コンピュータ・システムにおけるＡＣＭトランザクション（ACMTransactions on Computer Systems）、１９９２年２月、２６〜５２頁）は、さらに別の従来技術による、性能上の理由で順次書込みを行うためにファイル・システムを設計するという解決策を説明している。しかし、この解決策は、ログ構造ファイル・システムを実装することができるシステムにのみ適用可能であり、したがってホスト依存である。さらに、このようなシステムの性能を完全に実現するには、ファイル・システムが記憶システムの基本的な特徴を認識しなければならないが、これは通常成り立たない。
【０００６】
したがって、上述した不利益を伴わずに効率的に無作為データを書き込むことができる、記憶装置およびシステムで使用するためのログ構造の書込みキャッシュに対する必要性が依然としてある。
【特許文献１】米国特許出願公報ＵＳ２００２／０１０８０１７Ａ１、Kenchammana-HoskoteおよびSarkar
【特許文献２】米国特許第５，４１６，９１５号、MattsonおよびMenon
【特許文献３】米国特許第５，６８２，２７３号
【非特許文献１】ローゼンブルーム（Rosenblum）他（「ログ構造ファイル・システムの設計および実装（TheDesign and Implementation of a Log Structured File System）」、コンピュータ・システムにおけるＡＣＭトランザクション（ACMTransactions on Computer Systems）、１９９２年２月、２６〜５２頁）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、ディスク・ドライブ、ディスク・アレイ、光ディスク、および記憶サーバなどのデータ記憶システム用のログ構造の書込みキャッシュを提供し、そうすることによって無作為データが順次データと同程度に効率的にこうしたシステムに書き込まれるようにすることである。本発明の別の目的は、ログ構造の記憶システムの全選択読出し性能による不利益を被ることなく、ログ構造の書込みキャッシュの利点を達成することである。本発明のさらに別の目的は、データを書込みキャッシュに記入し、次いでデータを書込みキャッシュから記憶システム内の目標セクタ・アドレスに書き込むための効率的な動作を提供することである。セクタとは、記憶システムにおけるデータの最小のアドレス指定可能な単位であり、通常５１２バイト（８ビットを１バイトとする）である。ログ構造の書込みキャッシュは、データを目標セクタ・アドレスに移動する前に書込みデータをステージングするために提供される。読出し動作も、キャッシュすることによって向上することができる。
【課題を解決するための手段】
【０００８】
書込みキャッシュは、好ましくはシステムの主記憶媒体に実装されるが、システムの他の記憶要素において提供することもできる。書込みキャッシュは、書込みデータが一時的に不揮発状態で蓄積されるキャッシュ・ラインを含み、そうすることによって後で目標記憶位置に順次書き込むことができ、その結果システム全体の性能を向上させる。各キャッシュ・ライン用のメタ・データも、書込みキャッシュに保持される。メタ・データは、ライン中の各セクタの目標セクタ・アドレス、およびデータがキャッシュ・ラインに記入される順序を示すシーケンス番号を含む。バッファ・テーブルのエントリは、各キャッシュ・ラインごとに提供される。ハッシュ・テーブルは、各データ読出しおよび書込み動作で必要なセクタ・アドレスを求めてバッファ・テーブルを探索するのに使用される。
【０００９】
キャッシュ・システムを評価するための基準がいくつか存在する。データ書込みは、以下の条件を十分に満たさなければならない。すなわち、書込み済みであるとホストに認められたどのデータも、電源切断の際またはシステム・リセット・イベントの際に回復することができる。基本的な基準は、読出しおよび書込みのＩ／Ｏレートである。キャッシュ管理動作のオーバーヘッドも重要である。このオーバーヘッドには、エントリがキャッシュ中にあるかどうか判定する時間、およびキャッシュにエントリを追加しそこからエントリを削除するのに必要な時間ならびに資源が含まれる。キャッシュにメタ・データを格納するのに必要なメモリ量も重要である。予想外のシャットダウンに続くシステム状態の回復に必要な時間は最小限にすべきである。書込みキャッシュをフラッシュしまたは部分的にフラッシュするのに必要な時間は、通常は背景（優先度の低い）動作ではあるが、最小限にすべきである。
【００１０】
本発明のさらなる目的および利点を以下で説明するが、その一部は以下の説明および添付の図面で明らかにされ、本発明の実施において理解されよう。
【発明を実施するための最良の形態】
【００１１】
本発明を、主にデータ記憶装置またはシステムと共に使用するログ構造書込みキャッシュとして説明する。ただし、ＣＰＵ、メモリ、Ｉ／Ｏ、プログラム記憶装置、接続バス、および他の適切な構成要素を含むデータ処理システムなどの機器をプログラミングすることも、あるいは本発明の方法の実施を容易にするために設計することもできることが当業者には理解されよう。このようなシステムは、本発明の動作を実行する適切なプログラム手段を含む。
【００１２】
また、データ処理システムと共に使用する、予め記録されたディスクや他の同様のコンピュータ・プログラム製品などの製造物は、記憶媒体およびそれに記録された、データ処理システムが本発明の方法の実施を容易にするためのプログラム手段を含むことができる。このような機器および製造物も、本発明の精神および範囲内である。
【００１３】
図１は、記憶装置アプリケーション１００における本発明の全体構成を示す。ホスト１０２は、レベル１（Ｌ１）書込みキャッシュ制御１０６と相互作用して、従来技術の記憶システムであるのと同じように記憶システム１０４にアクセスする。書込みキャッシュ制御１０６は、揮発性ランダム・アクセス・メモリ（ＲＡＭ）１２２に格納されているＬ１書込みキャッシュ１０８にデータを一時的に格納する。レベル２（Ｌ２）キャッシュ制御１１０は、このデータおよびそれに関連づけられたメタ・データを渡され、ＲＡＭ１２２中にそのハッシュ・テーブル１１２およびバッファ・テーブル１１４を構築する。通常、データおよびメタ・データは、次いで、不揮発性記憶装置１２０内の領域１２０にキャッシュ・ライン１２４の形でコミットされる。データが揮発性でなくなると、ホスト１０２にはデータが格納済みであると認識される。周期的に、キャッシュ記憶装置のスナップショット領域１３４が、バッファ・テーブル１１４の現在の状況を反映するようにキャッシュ制御１１０によって更新される。さらに、そうすることが役に立つ場合、データがキャッシュ・ライン１２４から読み出されて主記憶装置１２６〜１３２に書き込まれる。主記憶装置は、図に示すように複数の記憶装置を備えることも、１つの装置を備えて１２０、１２６〜１３２が１つの記憶領域に存在するようにすることもできる。
【００１４】
図２は、キャッシュ・ラインの配置２００の一例を示す。主記憶装置１１８の一部でよい不揮発性記憶装置２０２のアドレス指定可能な領域内では、キャッシュ・ライン２０４〜２０８（ｂ）および２１４〜２１８がクラスタにグループ化される。例２０２では、３本のキャッシュ・ラインからなる２つのクラスタがデータ区域内にある。これらのクラスタは、書込みに最適なように整列され、クラスタにはキャッシュ・ラインが順次書き込まれる。たとえば、ハードディスク・ドライブの場合、キャッシュ・ラインのグループは、順次書き込みされる、ディスク上の１つまたは複数の隣接トラックに対応する。記憶アレイでは、クラスタは多くのディスクまたは専用の不揮発性記憶装置上にあってよく、やはり順次書込みの速度に対して最適化される。図２のクラスタは、シーク距離を減少させるために、記憶装置のアドレス指定可能な領域中に分散して示してある。他の選択肢として、回復時間を短くするためにすべてのキャッシュ・ラインを１つのクラスタに配置すること、またはバースト性が乏しい記憶装置のトラフィック性能を向上させるために、回復時間を犠牲にして個々のキャッシュ・ラインを分散させることがある。スナップショットのメタ・データを記憶する領域にも、２１２が割り振られる。それ以外の記憶領域は、キャッシュのためには使用されず、主記憶領域の一部として使用することができる。
【００１５】
スナップショットのメタ・データ２１２、１３４は、不揮発性記憶装置１１８内にある場所であり、キャッシュ全体のメタ・データのスナップショットのコピーを含む。スナップショットは、シャットダウンに続くシステム状態の回復を助ける。性能上の理由により、スナップショットは常に最新である必要がある。スナップショット情報は、たとえばパリティ・セクタを有することによってさらに保護することができる。
【００１６】
図３は、１本のキャッシュ・ライン２０４の内容を示す。ラインは、複数のデータ・ブロック２５２〜２５６、そのブロックに関連づけられたメタ・データ２５８、任意選択のパリティ・ブロック２６０、および任意選択の先行シーケンス番号２５０を含む。各キャッシュ・ラインは、ラインの書込み順序を示すシーケンス番号を有する。この番号はメタ・データ２５８の一部とみなされるが、図に示すようにキャッシュ・ラインに先行してもよい。図３では、図示したキャッシュ・ライン中の第２のデータ・ブロック２５４は、ブロック１と識別され、詳しくは、ブロック・サイズが８セクタの場合にはデータ・セクタ２６４〜２７８を含むと言うことができる。
【００１７】
書込みキャッシュの場合、「記入」という用語はデータをキャッシュ・ラインに書き込む動作を説明するのに用いられ、「フラッシュ」という用語はデータをキャッシュ・ラインから目標の位置に移動する動作を説明するのに用いられる。
【００１８】
キャッシュ・ラインは、書込みデータの完全性を確保するために、一まとまりで記入され、空きラインに対してのみ記入が行われる（ラインは、フラッシュが成功した直後に空になる）。ライン全体に記入が行われたとき、「書込み完了」がホスト１０２に対して示される。ラインのメタ・データ２５０、２５８は、ライン２０４にローカルな情報を含む。したがって、記入動作では、他のどの位置へもメタ・データを書き込まない。このことは、順次アクセス性能を保つ上で重要である。パリティ・ブロック２６０は、データのさらなる完全性を提供して、データまたはメタ・データのブロック全体を破壊するほど深刻な誤りからデータを保護するための選択肢である。
【００１９】
本発明の重要な側面は、キャッシュ・ラインがホール（データが存在しないがデータが予約されている領域）およびデータの複製（主記憶装置内のデータがキャッシュ・ラインの組の中に複数個複製されている）の両方を含むことができることである。データ・セクタに関するこうした情報は、Ｌ２キャッシュ制御によって追跡される。
【００２０】
以下のセクションで、書込みキャッシュの構造および動作を詳細に説明する。
【００２１】
ラインのメタ・データ
ラインのメタ・データは、ライン中にある各セクタの目標アドレスに関する情報を含み、そうすることによって、セクタの位置および識別情報がわかる。ラインは順次書込みを提供しながら一まとまりで記入が行われ、この書込みは、書込み順序が後で識別できるようにシーケンス番号２５０によって識別される。第１の書込み動作の結果第１のラインに記入されたセクタは、続いて第２の書込み動作の結果第２のラインに記入することができる。読出し動作は、セクタの最も新しく書き込まれたバージョンの位置を検出し識別できなければならない。
【００２２】
本明細書で説明する本発明の好ましい実施形態により、揮発性ＲＡＭ１２２中に格納しなければならないメタ・データの量が最小限に抑えられる。キャッシュ・ライン用のラインのメタ・データ２５０、２５８は、最小限には２つのデータ・オブジェクト、すなわちラインのシーケンス番号およびバッファ・テーブルを含む。ＡＮＳＩ  Ｃプログラミング言語でのこれらのオブジェクトの定義の一例は、以下のようになる。
typedef struct{
unsigned int SeqNum:32;
LineBufEntry LBE[LineSize];
}LineBufTable;
【００２３】
SeqNumは、キャッシュ・ラインのシーケンス番号である。３２ビットの整数と示してあるが、１組のキャッシュ・ラインにおいて一義的なシーケンス番号を扱う大きさがあれば十分である。好ましくは、シーケンス番号２５０（SeqNum）およびラインのメタ・データ２５８は、キャッシュ・ライン２０４の先頭および末尾にそれぞれ組み込まれ、そうすることによってラインに正しく書込みが行われたことが保証される。LBEはブロックからなるバッファ・テーブルであり、キャッシュ・ライン中にLineSize個のブロック位置があると想定している。LineBufEntryの構造を以下で説明する。ラインのバッファ・テーブルは、各データ・ブロック位置ごとに１つのエントリを有する。このエントリは、（目標セクタ・アドレスに関連する）目標ブロック番号、およびブロック内のどのセクタ位置が占められているかを示すビットマップから構成される。一般に、ブロック内のすべてのセクタ位置が占められることは予期されない。ビットマップが０であれば、ブロックが空であることを示す。Ｃ言語での構造は以下のようになる。
typedef struct{
unsigned int Block:32;
unsigned int Bitmap:8;
}LineBufEntry;
【００２４】
ブロックは、BlockSizeで示される一定数のセクタに対する記憶域を有する。このサイズは、シフト演算を使って目標セクタ・アドレスからブロック番号が計算されるように、２の累乗であることが好ましい。メモリ効率は、セクタ・アドレスをブロックにグループ化することによって高められ、このことは、ほとんどの記憶システム動作が複数のセクタを同時に操作するという観察を反映している。たとえば、BlockSizeが８の場合、１つのセクタ・アドレス（LBAで示される）に対するビットマップ・エントリおよびブロック番号は、以下のようにして計算することができる。
Block=LBA>>3;
Bitmap=1U<<(LBA&7);
【００２５】
したがって、ブロックおよびビットマップの値はライン中の各セクタ・アドレスを識別するのに十分であることが理解できよう。上記のビットマップの式は、特定のセクタ・アドレスのビット値を計算する。これらの値のビット単位での論理積をとり、ブロックのビットマップ全体を形成する。BlockSizeは、ビットマップ要素のビット長を決定する。
【００２６】
キャッシュ・ラインのシーケンス番号は、ラインの記入順序を決定するのに使用される。特定のシーケンス番号の値は、たとえばラインが空であることを示すために予約することができる。
【００２７】
バッファ・テーブル
動作中、すべてのキャッシュ・ラインのライン・バッファ・テーブルは、ランダム・アクセス・メモリ中の単一のテーブル、つまりバッファ・テーブルに統合される。このテーブルは、別のバッファ・テーブルのエントリをアドレス指定する索引値を格納するために、各エントリごとにさらに要素を有する。バッファ・テーブルのエントリは、以下のように定義することができる。
typedef struct{
unsigned int Block:32;
unsigned int Bitmap:8;
unsigned int NextEntry:16;
}BufEntry;
【００２８】
各ライン・バッファ・テーブルは、バッファ・テーブルに順次格納され、したがってログ・バッファ中の各ブロック・エントリは、データ参照を格納していないときでも特定の固定記憶アドレスを有する。バッファ・テーブルは、以下のように宣言することができる。
BufEntry BufTable[Lines*LineSize];
【００２９】
上式で、Linesはキャッシュ・ラインの数である。各ブロック・エントリは、それに関連づけられた固定メモリ・アドレスを有する。このことは、キャッシュ・ラインに記入しそれをフラッシュするための重大な性能上の利点を提供する。
【００３０】
ハッシュ・テーブル
セクタ・アドレスを求めてバッファ・テーブルを素早く探索できることが、各データ読出しおよび書込み動作において必要である。セクタ・アドレスを求めてキャッシュを探索するのに適した多くの技術があるが、リンクされたリストのエントリからなるハッシュ・テーブルがバッファ・テーブルの探索に適している。ハッシュ・テーブルは、小さいメモリ・フットプリントと高速なルックアップの両方を提供する。ハッシュ機能は、セクタ・アドレス番号またはブロック番号からのハッシュが比較的均一に広がるようにするために用いられる。一例として、ハッシュは、ブロック番号の最下位ビットを使用する。リンクされたリストは、ハッシュ値に対応する、バッファ・テーブル中のすべてのブロックにアクセスするのに使用される。
【００３１】
図４は、ハッシュ・テーブル３０２と、それがどのようにしてバッファ・テーブルを参照するかを示す。ハッシュ・テーブル３０２は、一義的な各ハッシュ値ごとにエントリを有し、ここで、各エントリは、ハッシュに対応するブロックに対するバッファ・テーブル中のエントリへの索引である。バッファ・テーブル３２０は、キャッシュ・ブロックに対するバッファ・エントリを保持する。キャッシュ・ブロックは、ただ１つの対応するハッシュ・エントリを有し、多くのブロックが同じハッシュ・エントリを共有することができる。NextEntry要素は、ハッシュ値に対応する、バッファ・テーブル中の次のブロックの索引を保持する。特定の値、つまりEndが、リンクされたリストの終端を示すために予約される。一般に、NextEntry要素のサイズは、キャッシュに保持することができるブロック数によって決まる。たとえば６４，０００個のエントリの場合は、１６ビットのNextEntryで十分である。
【００３２】
図４は、ハッシュ・テーブル３０２およびリンクされたリスト３１１〜３１８の構成の一例を示す。この例では、ハッシュ・エントリ３１０の[line,block]索引は、[Lines-1,0]である。これは、連結３１６で示されるように、最終キャッシュ・ライン３７０の第１ブロック３７５への索引である。このブロックのNextEntry３７８は、連結３１７で示されるように、[0,1]の索引を含む。これは、キャッシュ・ライン０のブロック１（３４０）への索引である。ブロック１（３４０）は、リンクされたリスト中の最終エントリであり、したがって、NextEntry３４３は、連結３１８で示されるように、End３９０に対応する索引値を含む。他の連結例も図４に示す。
【００３３】
ハッシュ・テーブルを長くすると、リンクされたリストが短くなる傾向にあるので、リンクされたリスト中のセクタ・アドレスをルックアップする際の性能が向上する。しかし、このことはメモリの必要量も増加させる。キャッシュ・ライン番号は、索引値から計算することができるのでバッファ・テーブルに明示的に格納する必要はない。これは、１ラインごとに既知の数のブロックを有している結果である。キャッシュ・ライン中のデータ記憶位置は、上記の情報にキャッシュ・ラインの開始位置を足すことによって計算することができる。
【００３４】
本発明の好ましい実施形態では、ラインに記入が行われると、ハッシュ・テーブルで始まるリンクされたリスト（リストの先頭）にエントリがロードされる。このことは、ルックアップ動作中、最初に一致するエントリが最も新しいことを意味する。したがって、ラインがフラッシュされると、このエントリはリンクされたリストの末尾から削除され、そうすることによって確実にシーケンス順序が保存されるようにする。
【００３５】
記入動作
図５は、記入動作４００の詳細を示す。ステップ４０２で、記入動作は、１組のセクタおよび関連アドレスを渡される。キャッシュは、ステップ４０４で、満杯かどうか調べられる。空きラインがない場合、ステップ４０６で、キャッシュはセクタ・アドレスをそれぞれ求めて探索される。これには、前述したセクタのブロック番号およびビットマップを計算し、ハッシュ値を計算し、および一致を探索するためにハッシュ・テーブル中のリストを横断することが含まれる。ステップ４０８で、どのセクタ・アドレスもキャッシュにない場合、ステップ４３４で、セクタは目標位置に直接書き込まれ、ステップ４３６で、記入動作は完了したものと示される。ステップ４０８で、セクタ・アドレスのいずれかがキャッシュにあった場合、バッファ・テーブル中の対応するエントリは無効にしなければならない。キャッシュにない１組のセクタは、ステップ４１０で目標セクタに書き込まれる。ステップ４１２で、書込みキャッシュ中にスペースを作るためにフラッシュ動作が呼び出される。キャッシュにある１組のセクタは、次いで、ステップ４１４に渡されて記入される。これは、キャッシュ状態の一貫性を保つための多くの可能な方法の１つにすぎない。ステップ４０４で、キャッシュ中にスペースがある場合、セクタはステップ４１４に渡される。
【００３６】
ステップ４１４で、キャッシュ・ラインのクラスタが、キャッシュされたデータを受け取ると判定される。ステップ４１６で、シーケンス番号が増分される。このクラスタに対するキャッシュ・ライン・ポインタ、つまりpostlinecluster#が、次いでステップ４１８で、ラッピングまたは先入れ先出し（ＦＩＦＯ）スタイルで（すなわち、クラスタ中のキャッシュ・ライン数をモジュロとして）増分される。ステップ４２０で、キャッシュ・ラインのメタ・データに加えて１組のブロック番号およびビットマップがセクタ・アドレスから作成される。ステップ４２２で、これらはpostlineで示されるキャッシュ・ラインに一まとまりで書き込まれる。ステップ４２４、４２６および４２８は、キャッシュ・ライン中の各ブロックに対するエントリを追加することによってハッシュ・テーブルが更新されるループを構成する。このループは、各ブロックごとにハッシュを計算し、次いでリンクされたリストに前置されたブロックに対するBufTableエントリに索引を挿入し、以前の第１のリスト・エントリをポイントするようにBufTableエントリの次の索引値を更新する。これによって、リンクされたリストが確実にシーケンス番号順にソートされる。ステップ４３０で、記入は完了したとホスト１０２に示される。最後に、ステップ４３２で、スナップショットの記入動作の信号が送られ、その結果、メタ・データのスナップショットが記憶装置に書き込まれる。図示してはいないが、セクタのリストは、記入が行われる複数のラインでもよい。
【００３７】
上記の説明は、キャッシュ状態の一貫性を保つ記入動作の重要な特徴の例示を意図したものに過ぎない。他の方法を使うこともできる。たとえば、実施すべき一連の動作を最初に決定し、次いで最適化アルゴリズムを使って媒体への書込み動作を合体させて順序づけることが望ましい場合がある。さらに、ステップ４１２および４１４で、キャッシュ状態の一貫性を保つ、フラッシュの次に記入を行う方法を使うこともできる。エントリを無効にするために、システムのメタ・データを修正するなどの他の方法も適用可能である。さらに、リストの先頭に新しい値を挿入する代わりに、ブロックの既存のハッシュ・エントリを置き換えることが望ましい。こうすることによって、記入動作においてリンクされたリストを探索するためにそれ以上の処理を行うことなく、リンクされたリストが短く保たれる。
【００３８】
本発明の好ましい実施形態では、キャッシュ・ラインには、各クラスタにおけるＦＩＦＯ順で充填される。ＦＩＦＯでは、ライン番号をモジュロとしてライン番号の昇順でラインに記入が行われる。この構成では、各クラスタは、読出しポインタ（フラッシュすべき次のラインのシーケンス番号）および書込みポインタpostlinecluster#（記入を行うべき次のラインのシーケンス番号）を有する。こうすることによって、後で説明するように初期化の際のキャッシュ状態の回復が簡単になる。
【００３９】
記入動作は、様々な条件によってトリガすることができる。負荷が高い書込み動作の間、記入は、Ｌ１書込みキャッシュがほぼ満杯のときに開始することができる。また、ラインのデータ値がＬ１書込みキャッシュにあるとき、または書込み活動に脱落があるとき、またはデータが一定期間Ｌ１書込みキャッシュに存在した後でトリガすることもできる。書込み活動に基づく方法は、Ｌ１書込みキャッシュが全く行われない状況によく適している。この場合、目標セクタにデータを書き込む場合と比較して、書込みレートを向上させるレートでラインに記入を行うことが目標である。
【００４０】
フラッシュ動作
フラッシュ動作は、キャッシュ・ラインからデータを消去し目標アドレスにセクタを書き込むのに用いられる。読出し性能は通常、キャッシュされたデータが目標位置に移動されるとき、完全なログ構造システムに比べて強められる。というのは、ホスト１０２によって割り当てられたセクタ・アドレス同士は、順不同に書き込まれはするが、ローカルな文脈において類似していることが多いからである。しかし、フラッシュ動作は時間を消費するので、理想的にはアイドル間隔中に実施される。多くの記憶装置の作業負荷、たとえばデスクトップおよびモバイル記憶システムに対して生成される負荷は、非活動時間が長く、バーストが短い活動（最大Ｉ／Ｏレート）によって特徴づけられる（たとえば、米国特許第５，６８２，２７３号を参照）。こうした作業負荷により、キャッシュ・ラインのフラッシュを行う機会が多く提供される。実際、米国特許第５，６８２，２７３号のアイドル状態検出アルゴリズムは、このようなシナリオを識別するのに使用することができる。
【００４１】
図６は、フラッシュ動作５００の詳細を示す。ステップ５０２で、フラッシュ動作は、シーケンス番号に基づいて、クラスタ中で最も古いラインのライン番号を渡される。こうすることによって、確実に書込みデータ順序が常に保存されるようになる。ステップ５０４で、キャッシュ・ライン全体が、１回の動作でメモリに読み出される。ステップ５０６〜５１４は、キャッシュ・ライン中のブロックにあるすべてのセクタを処理するループを構成する。ステップ５０８で、各ブロックのブロック・アドレス・エントリが、ハッシュ・テーブル中でルックアップされる。ステップ５１０で、セクタの最も新しいエントリが、処理中のエントリと比較される。値が一致しない場合、現在のラインにあるセクタは、最も新しいバージョンではないのでスキップされる。一致する場合、ステップ５１２で、セクタはディスクに書き込まれる。
【００４２】
すべてのセクタが処理されると、ステップ５１６で、ラインは空であるとメモリ中で印がつけられる（かつ、不揮発性メモリに反映される）。ステップ５１８〜５２２で、ラインにあったすべてのブロックを評価する。ステップ５２０で、ブロックに対応するハッシュ・テーブル・エントリが、リストから削除される。これは、現在のラインにあるブロックに対応するエントリを求めて、リンクされたリストを探索することによって達成される。そのエントリは、リスト中に先にあったエントリの次の値を、ブロック・エントリに続くエントリをポイントするように再調整することによって、リストから削除される。ステップ５２４で、スナップショットのフラッシュ動作の信号が送られ、その結果、メタ・データのスナップショットが記憶装置に書き込まれる。メタ・データが更新されるとき、キャッシュ・ラインが空である状態が不揮発性記憶装置に書き込まれる。空の状態をメタ・データにすぐに反映させることは不可欠ではない。予想外の電源低下などによってシステム状態が失われると、ラインが再度フラッシュされる結果となるが、ここでは重要ではない。
【００４３】
キャッシュ・ラインをフラッシュするための重要な動作のみを説明したが、この処理の他の変形形態も可能である。たとえば、セクタは、ステップ５１２で示した順序で書き込まれる必要はない。さらに、最適な性能になるように書込みを合体させソートする並べ替えアルゴリズムを利用することが有益である。
【００４４】
データ書込み動作
図７は、データ書込み動作６００の詳細を示す。ステップ６０２で、書込み動作に１組のセクタおよび関連アドレスが渡される。ステップ６０４で、データをキャッシュすべきかどうか判定が行われる。たとえば、大規模な順次書込みは書込みキャッシュを回避することが有益であろう。セクタをキャッシュすべきである場合は、ステップ６０６で、記入動作にセクタのリストが渡される。記入が完了すると、ステップ６１４で書込み完了が示される。キャッシュを回避する場合は、ステップ６０８で、データは目標セクタ・アドレスに直接書き込まれる。
【００４５】
記入動作と同様に、現在書込みキャッシュにあるどのセクタも、無効にしなければならない。ステップ６１０で、セクタのどれかが現在キャッシュに存在するかどうか調べるために、キャッシュが探索される。存在しない場合、ステップ６１４で、書込み完了が示される。ステップ６１０で、セクタがキャッシュにあった場合、対応するキャッシュ・エントリが無効にされる。本発明の好ましい実施形態では、これらの残っているセクタは、ステップ６１２で、縮小したリストに置かれ、このリストは記入動作に渡される。記入が完了すると、ステップ６１４で、書込み完了が示される。以上はデータ書込みの重要な特徴を例示するために説明したに過ぎない。たとえば、最初にすべての動作を識別し、次いで書込み順序を合体させ最適化する並べ替えアルゴリズムを使用することによって、性能が向上する。
【００４６】
データ読出し動作
図８は、データ読出し動作６００の詳細を示す。ステップ６２０で、読出し動作に１組のセクタ・アドレスが渡される。ステップ６２２〜６３２が、すべてのセクタ・アドレスに対して実行される。ステップ６２４で、セクタ・アドレスに対応するブロックおよびビットマップが、ハッシュ・テーブル中でルックアップされる。ステップ６２６で、セクタがキャッシュにあった場合は、ステップ６２８で、セクタは、ハッシュ・テーブル・エントリから判定されたキャッシュ・ラインから読み出される。セクタがキャッシュになかった場合は、ステップ６３０で、所与のセクタ・アドレスから読み出される。この処理をさらに改良することも可能である。たとえば、ループにおいてデータ位置のリストを構築し、次いで読出し順序を合体させ最適化する並べ替えアルゴリズムを使用することによって、性能を向上させることができる。
【００４７】
スナップショット動作
スナップショット動作は、キャッシュのメタ・データのほぼ最新のコピーを提供するのに用いられる。スナップショットをわずかに古くしておくことによって、システム動作性能が向上する。スナップショット動作には２つの変形形態がある。１つは記入動作用、１つはフラッシュ動作用である。スナップショットの間のキャッシュ動作の数に上限を設けることが有益である。スナップショットは、Ｎ回の記入ごとおよびＭ回のフラッシュごとに行うことができる。フラッシュ動作は一般に背景で起こるので、Ｍ＝１とするのがよい選択であろう。Ｎの値が１０と２０の間であれば、性能に与える影響と回復時間の間の相応な妥協点が提供されるであろう。
【００４８】
図９は、記入動作に応答したスナップショット動作７００の詳細を示す。ステップ７０４で、記入カウンタが増分される。ステップ７０６で、スナップショットが必要かどうか調べるためにカウンタが検査される。必要ない場合、動作は終了する。スナップショットを行うべき時間であれば、制御はステップ７０８に移り、前もって記入されているＮ本のラインのスナップショットのメタ・データがスナップショット領域２１２にコミットされる。記入されたラインは、最も新しいシーケンス番号を有するラインである。ステップ７１０で、カウンタ値がリセットされ、スナップショットの完了を示す。
【００４９】
通常、キャッシュ・ラインのメタ・データは、１個未満のセクタを占有する。Ｎ個のセクタを同時に記入することによって、スナップショットの更新は、性能を向上させるためのストリーミング動作にもなる。
【００５０】
図１０は、フラッシュ動作に応答したスナップショット動作７００の詳細を示す。この動作は、スナップショットの記入動作に類似している。違いは、ステップ７２６で、最も新しくフラッシュされたラインに対応するラインのメタ・データが、ラインが空であることを示すメタ・データで上書きされることである。たとえば、空きライン用に予約されたシーケンス番号を使用することによって、行うことができる。
【００５１】
回復動作
システムが初期化されるとき、不揮発性書込みキャッシュの状態を適切に回復することが必要である。システムがクリーン・シャットダウンを示す方法を有する場合、シャットダウンに先立って完全なスナップショットを行うことができ、したがって、回復はスナップショットの読出しに限定される。たとえば、多くの記憶システムは、最初の書込みの時点でセットされクリーン・シャットダウンの時点でクリアされるダーティ・フラグを使用することができる。ダーティ・フラグがセットされていない場合、スナップショットは良好であることがわかる。フラグがセットされている場合、スナップショットの状態は有効であると保証することができず、キャッシュのメタ・データはキャッシュおよびスナップショットから再構築しなければならない。
【００５２】
図１１は、回復動作８００の詳細を示す。ステップ８０３で、最新のシーケンス番号（newsn）の値および最も古い有効シーケンス番号（oldsn）の値を初期化する。ステップ８０４〜８１６は、キャッシュ中のすべてのライン値に関わるループである。ステップ８０６で、ラインのスナップショットのメタ・データ（ＳＭＤ）が読み出される。ステップ８０８で、スナップショットにある最新のシーケンス番号が更新される。ステップ８１０で、このキャッシュ・ラインのクラスタに対するキャッシュの書込みポインタ（記入動作に使用する次のライン番号、つまりpostlinecluster#）が、クラスタにある最新のシーケンス番号に対応するラインの索引として計算される。ステップ８１２で、読出しポインタ（フラッシュ動作に使用する次のライン番号）が、空きラインを示すキャッシュのメタ・データに次いで最も高いライン番号（ＦＩＦＯのラップ条件の対象）と決定される。ステップ８１４で、最も古いシーケンス番号が計算される。ループが完了すると、すべてのスナップショットのメタ・データがメモリ中にあることになる。さらに、最新のシーケンス番号、すべてのクラスタに対する読出しポインタ、すべてのクラスタに対する書込みポインタ、および最も古いシーケンス番号がこの時点でわかる。
【００５３】
ステップ８２０〜８２８は、書込みポインタ（postline）からスナップショットに先立って記入され得るラインの最大数（N-1）までの、すべてのクラスタ中のライン値に関わるループである。ステップ８２２で、ラインのメタ・データが読み出される。ステップ８２４で、このラインのシーケンス番号が最新のシーケンス番号と比較される。ラインのシーケンス番号が最新のシーケンス番号より小さい場合、またはラインが空であることをシーケンス番号が示す場合、検査すべきそれ以上のラインはなく、ステップ８３０で回復動作が完了する。それ以外の場合、現在のラインはスナップショットの一部ではないことになる。ステップ８２６で、書込みポインタpostlineが（ＦＩＦＯスタイルで）増分され、最新のセクタ番号が更新される。ループの最後で、postlineの最も新しい値およびシーケンス番号がわかる。
【００５４】
ハッシュ・テーブルは、メタ・データには格納されない。ハッシュ・テーブルは、すべてのブロック・エントリをシーケンス番号の昇順で（データが記入されたかのように）ロードすることによって、ラインのメタ・データから再構築される。こうすることによって、異なるブロックに対するリストのエントリ順序は変わり得るが、各ブロックごとのリスト順序が保存されることが保証される。ただし、これは重要なことではない。さらに、ハッシュ・テーブルを再構築するための、より高度な方法を使うことが有益であろう。たとえば、リンクされたリストの長さは、各セクタごとにシーケンス番号が最も高いエントリのみをロードすることによって、最小化される。
【００５５】
上記の例は、Ｍ＝１（すべてのフラッシュにおけるスナップショット）の場合を説明する。Ｍ＞１の場合は、読出しポインタの位置決めをするための、ステップ８２０〜８２８に類似した追加のループが必要になる。スナップショットを使用することにより、キャッシュ・ラインがフラッシュされたときにその中のメタ・データを更新する必要がなくなる。スナップショット領域２１２は１つの隣接アドレス・ブロックに存在する必要がないことに留意されたい。
【００５６】
データの完全性
ログ・バッファ・システムの状態は、常に明確であることが不可欠である。システムは常に、アドレスへの各読出し要求に対して、最も新しく書き込まれたデータを返すことが必要である。したがって、システムは、常に明確な状態をもたなければならず、この状態は、記録媒体に記憶された永続データに反映されなければならない。たとえば、記入動作を使ってキャッシュ・ラインに順序通りに書込みを行うことにより、部分的な書込みを確実に検出できるようになる。完全性は、キャッシュ・ラインにある各セクタ中のシーケンス番号を符号化することによってさらに高められる。これは、各セクタ中の予約位置を使うことによって、またはシーケンス番号をセクタ検査領域に予め符号化することによって達成することができる。部分的な書込みを受けたキャッシュ・ラインは、動作が完了したとホスト１０２には認識されていないので、空であるものとして扱うことができる。スナップショットにおける部分的な書込みも、キャッシュ・ラインの順序からのシーケンス番号の順序の区切りによって検出することができる。前述した回復手順は、スナップショットにおいて更新されていなかったどの記入済みラインも回復することができる。スナップショットに反映されていない、フラッシュされたどのラインも再度フラッシュすることができる。
【００５７】
順次セクタ・パリティなどのマルチ・セクタ誤り訂正符号（ＥＣＣ）と共に用いるときは、バッファ・ラインはＥＣＣアドレス指定可能単位の整数であることが有益であり、パリティは完全なＥＣＣアドレス指定可能単位であることが有益である。
【実施例】
【００５８】
本実施形態のランダム・アクセス・メモリのフットプリントは、キャッシュの容量と比較して非常に小さい。BlockSizeが８の場合、各バッファ・テーブル・エントリは７バイトである。したがって、バッファ・テーブル用のキャッシュ・セクタごとに１バイト未満である。ハッシュ・テーブルのサイズは、所望のルックアップ性能と必要なメモリの間のつり合いによって決まる。一般に、計算能力は、ハッシュ・テーブルおよびリンクされたリストの長さによる。メモリのフットプリントは、以下のようにして計算することができる。ハッシュ・テーブルのバイト数のサイズは、エントリ数（最大６４Ｋ個のエントリ）の２倍である。バッファ・テーブルのサイズは、（７バイト×LineSize×ライン数）に等しい。
【００５９】
５４００ｒｐｍのモバイル・ハードディスク・ドライブを無制限の記憶システムの一例として検討する。データ領域（ＭＤ）の中心近くに置かれたキャッシュ・ラインの唯一のクラスタが、ＨＤＤのシーク距離を最小化するために選ばれる。こうしたディスク・ドライブの場合、ＭＤにおけるトラックごとに４１６セクタがある。それぞれ２０８セクタを有し、すべてのメタ・データに対して１つのパリティ・ブロックと１つのブロックを有する２本のキャッシュ・ラインがトラックごとにあることになる。したがって、LineSizeは、BlockSizeが８である２４個のブロックである。２５６トラックを占有する５１２本のラインがあることになり、キャッシュに１２，２８８ブロックが生じる。したがって、１６Ｋ個のエントリのハッシュ・サイズが適切である。表１は、必要とされる様々なメモリ構造のサイズを示す。（ここではＫは１０２４の要素である。）
【００６０】
このキャッシュの容量は約４８ＭＢだが、メタ・データのフットプリントは１２８ＫＢ未満である。一般に、ブロック構造が原因で、全容量が利用可能になることはない。通常のＩ／Ｏを４ＫＢと仮定すると、整列されていない８セクタのＩ／Ｏが２ブロックを占有するので、キャッシュ容量は半分すなわち２４ＭＢまで低下することがある。
【００６１】
【表１】
2004213647.tif 000003
【００６２】
この設計に対する回復時間は、回転周期および１トラックのシーク時間から見積もることができる。スナップショットのメタ・データは、バッファ・テーブルのサイズである。各ラインの各メタ・データが完全なセクタを占有することを可能にするには、５１２セクタ、すなわち２トラック未満が必要である。最大スナップショット間隔を、記入に対してはＮ＝２０、フラッシュに対してはＭ＝１とするということは、最悪の場合、１２トラック、（２０／２＋１）個のキャッシュ・トラックおよびスナップショットからの読出しを含むことを意味する。この例では、周期は１１．１ミリ秒、１トラックの読出しシークは２．５ミリ秒であり、回復時間は２００ミリ秒になる。これによって、システムの遅延に重大な影響が与えられるべきではない。というのは、従来技術による起動時間は、ログ書込みキャッシュなしで約１．７秒だからである。
【００６３】
拡張
書込みキャッシュを有する記憶システムの性能は、リンクされたリストから古いエントリ（シーケンス番号がより古い複製セクタ）を削除することによって向上することができる。フラッシュ動作は、終了トークンを探すためにハッシュ・リストを横切るので、ただ一度の機会を提供する。古くなったどのエントリも、見つけたときに削除することができる。さらに、フラッシュされているラインの古くなったどのセクタも、フラッシュする必要はない。キャッシュ・ライン同士は、等しい容量である必要はなく、グループごとのキャッシュ・ライン数も同様に変わり得る。こうした状況は、たとえばライン・サイズのテーブルを追加することによって、キャッシュ・テーブルにおいて簡単に処理される。この手法は、隣接する非断続セクタの数が変わるゾーン式記録システムにおいて分散キャッシュ・トラックを利用するときに有益である。一実施形態では、トラックごとに一定数のキャッシュ・ラインは維持されるが、ライン・サイズは変わる。分散キャッシュを、１つのＦＩＦＯではなく１組のＦＩＦＯとして扱うことも有益であろう。こうすることにより、アドレス指定可能な記憶領域の様々な領域に動作が集中するときに、データをキャッシュに配置することが可能になる。
【００６４】
欠陥管理のためにキャッシュ・ラインまたはグループにいくつかの空きセクタを残すことが有益であろう。キャッシュ・ラインを高速アクセス可能に保つことが性能にとって重要である。したがって、キャッシュ・ラインのグループに欠陥があるのは不利であろう。このような欠陥には、キャッシュ・ラインを再度割り当てる必要がある。こうした再割当ては、欠陥のない領域を選んでキャッシュ・ラインとするように割り当てることによって達成することができる。あるいは、キャッシュ・ライン・グループ自体の中で欠陥管理を扱うことができる。パリティは直接使用することができるが、セクタを再度マッピングするためにライン・グループ中の余長スペースを使用することもできる。
【００６５】
キャッシュが満杯のときのシステム性能は、スナップショットのメタ・データを、無効化情報を含むように拡張することによって向上することができる。こうすることによって、満杯のキャッシュ中のセクタを無効にするときにキャッシュをフラッシュしまたは既存のメタ・データを修正する必要が減少する。また、データ書込み動作中にキャッシュのエントリを無効にするための書込み動作の数も減らすこともできる。
【００６６】
キャッシュ・ライン用の固定位置があると、アドレス・スペースの局所的な領域への不均衡なＩ／Ｏアクセスが起こり、このことは一部の記憶システムでは信頼性および長期に渡る性能にとって有害となる場合がある。アクセス位置を周期的に移動するためのアルゴリズムを使用してもよく、フラッシュ動作によってアクセス位置を変える場合もある。別の代替アルゴリズムは、周期的にキャッシュ・ラインを異なる位置に移動する。これは、完全なフラッシュに続いて達成することができるが、必ずしもそうする必要はない。新しい位置にあるデータは、空のキャッシュ・ラインと交換される。このキャッシュ・ラインは、新しい領域において記憶装置の特性が異なる場合はサイズを変えることもできる。
【００６７】
本発明を、好ましい実施形態に関して具体的に示し説明したが、本発明の精神および範囲から逸脱することなく、本発明の形式および細部に様々な変更を加えることができることが理解されよう。したがって、開示した発明は単なる（merely）例示とみなすべきであり、添付の特許請求の範囲で指定した範囲にのみ限定すべきである。
【００６８】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６９】
（１）セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体と、
複数のキャッシュ・ラインを有する書込みキャッシュであって、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを備え、
前記書込みキャッシュが、システムの性能を向上させるように、データが順次書き込まれるステージング領域として作用するデータ記憶システム。
（２）各キャッシュ・ラインが、前記キャッシュ・ラインの一部が失われた場合に前記キャッシュ・ライン中のデータの回復を可能にするパリティ・ブロックをさらに備える、上記（１）に記載の記憶システム。
（３）書込みデータが、前記書込みキャッシュに記入された後で前記システムの前記セクタ・アドレスに書き込まれる、上記（１）に記載の記憶システム。
（４）前記書込みキャッシュが、前記システムの不揮発性メモリ中に維持される、上記（１）に記載の記憶システム。
（５）ホスト・システムおよび前記書込みキャッシュと相互作用する書込みキャッシュ制御をさらに備える、上記（１）に記載の記憶システム。
（６）前記ラインのメタ・データが、前記キャッシュ・ラインを識別するためのシーケンス番号を含む、上記（１）に記載の記憶システム。
（７）前記ラインのメタ・データが、複数のエントリを有するラインのバッファ・テーブルを含み、各エントリが、目標セクタ・アドレス、およびブロック中で占められているセクタ位置を示すビットマップを有する、上記（１）に記載の記憶システム。
（８）前記キャッシュ・ラインすべてに対する前記ラインのバッファ・テーブルが、セクタ・アドレスの探索を可能にするために１つのバッファ・テーブルに統合される、上記（７）に記載の記憶システム。
（９）前記バッファ・テーブルがハッシュ・テーブルを用いて探索される、上記（８）に記載の記憶システム。
（１０）前記バッファ・テーブルおよび前記ハッシュ・テーブルを管理するキャッシュ制御をさらに備える、上記（９）に記載の記憶システム。
（１１）前記媒体が前記書込みキャッシュ全体のための前記ラインのメタ・データのスナップショットを含み、前記スナップショットが、システムがシャットダウンした場合にデータを回復するために用いられる、上記（１）に記載の記憶システム。
（１２）前記キャッシュ・ラインが、クラスタとして前記媒体上でグループ化される、上記（１）に記載の記憶システム。
（１３）前記システムがディスク・ドライブである、上記（１）に記載の記憶システム。
（１４）前記システムが光ディスク・ドライブである、上記（１）に記載の記憶システム。
（１５）前記システムがディスク・アレイである、上記（１）に記載の記憶システム。
（１６）前記システムが記憶サーバである、上記（１）に記載の記憶システム。
（１７）セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体を有するデータ記憶システムの性能を向上させる方法であって、
前記媒体上に書込みキャッシュを提供するステップであって、前記書込みキャッシュが複数のキャッシュ・ラインを有し、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを有するステップと、
前記システムの性能を向上させるように、書込みデータを、順次書き込まれるデータとして前記書込みキャッシュにステージングするステップとを含む方法。
（１８）前記ステージングするステップが、
前記システムに書き込まれる複数のデータ・ブロックを受け取るステップと、
前記データ・ブロックを前記キャッシュ・ラインの１つに格納するステップと、
前記キャッシュ・ライン用のメタ・データを生成するステップであって、前記メタ・データが、前記キャッシュ・ラインのシーケンス番号および前記データ・ブロックの前記アドレスを含むステップと、
前記メタ・データを前記キャッシュ・ラインに格納するステップとを含む、上記（１７）に記載の方法。
（１９）前記キャッシュ・ライン中のデータ用の複数のパリティ・ブロックを計算するステップと、
前記パリティ・ブロックを前記キャッシュ・ラインに書き込むステップとをさらに含む、上記（１８）に記載の方法。
（２０）前記媒体上にスナップショット領域を提供するステップと、
データが前記書込みキャッシュに書き込まれた後で、前記キャッシュ・ラインの前記メタ・データのコピーを前記スナップショット領域に書き込むステップとをさらに含む、上記（１７）に記載の方法。
（２１）前記スナップショットのメタ・データに基づく初期化に続いて、前記書込みキャッシュの状態を判定するステップをさらに含む、上記（２０）に記載の方法。
（２２）前記判定するステップが、
前記スナップショットのメタ・データを読み出すステップと、
現在キャッシュ済であるデータを含む前記キャッシュ・ラインを判定するステップと、
前記判定されたキャッシュ・ラインに関連づけられた前記メタ・データに基づいて、前記書込みキャッシュの前記状態を判定するステップとを含む、上記（２１）に記載の方法。
（２３）記憶システムとともに用いて、前記システムの性能を向上させるコンピュータ・プログラムであって、前記システムが、セクタ・アドレスにそれぞれ関連づけられたデータ・ブロックとしてデータを格納する媒体を有し、前記プログラムはコンピュータ可読媒体に記憶され、コンピュータを
前記媒体上に書込みキャッシュを提供する手段であって、前記書込みキャッシュが複数のキャッシュ・ラインを有し、各キャッシュ・ラインが、複数のデータ・ブロック、前記キャッシュ・ライン中の前記データ・ブロックが書き込まれる前記セクタ・アドレスに関する情報をもつラインのメタ・データ、および前記キャッシュ・ライン中の前記データ・ブロックの、他のキャッシュ・ライン中の前記データ・ブロックとの相対的な順序を示すシーケンス番号を有する書込みキャッシュとを有する手段と、
前記システムの性能を向上させるように、書込みデータを、順次書き込まれるデータとして前記書込みキャッシュにステージングする手段
として機能させるコンピュータ・プログラム。
（２４）前記ステージングする手段が、
前記システムに書き込まれる複数のデータ・ブロックを受け取る手段と、
前記データ・ブロックを前記キャッシュ・ラインの１つに格納する手段と、
前記キャッシュ・ライン用のメタ・データを生成する手段であって、前記メタ・データが、前記キャッシュ・ラインのシーケンス番号および前記データ・ブロックの前記アドレスを含む手段と、
前記メタ・データを前記キャッシュ・ラインに格納する手段とを含む、上記（２３）に記載のコンピュータ・プログラム。
（２５）前記キャッシュ・ライン中のデータ用の複数のパリティ・ブロックを計算する手段と、
前記パリティ・ブロックを前記キャッシュ・ラインに書き込む手段とをさらに備える、上記（２４）に記載のコンピュータ・プログラム。
（２６）前記媒体上にスナップショット領域を提供する手段と、
データが前記書込みキャッシュに書き込まれた後で、前記キャッシュ・ラインの前記メタ・データのコピーを前記スナップショット領域に書き込む手段とをさらに備える、上記（２３）に記載のコンピュータ・プログラム。
（２７）前記スナップショットのメタ・データに基づく初期化に続いて、前記書込みキャッシュの状態を判定する手段をさらに備える、上記（２６）に記載のコンピュータ・プログラム。
（２８）前記判定する手段が、
前記スナップショットのメタ・データを読み出す手段と、
現在キャッシュ済であるデータを含む前記キャッシュ・ラインを判定する手段と、
前記判定されたキャッシュ・ラインに関連づけられた前記メタ・データに基づいて、前記書込みキャッシュの前記状態を判定する手段とを備える、上記（２７）に記載のコンピュータ・プログラム。
【図面の簡単な説明】
【００７０】
【図１】記憶システムにおける本発明の書込みキャッシュを示す概略図である。
【図２】本発明による、ログ構造書込みキャッシュおよびメタ・データを提供するキャッシュ・ラインを示す配置図である。
【図３】データ・ブロックおよびセクタ情報を含む、キャッシュ・ラインのさらなる詳細を示す図である。
【図４】本発明による、バッファ・テーブルの探索で使用されるバッファ・テーブルおよびハッシュ・テーブルの一例を示す図である。
【図５】ログ構造書込みキャッシュのキャッシュ・ラインにデータを入力する記入動作の好ましい実施形態を示すフロー図である。
【図６】データをキャッシュ・ラインから消去してキャッシュ・ライン中のセクタ・アドレスを目標セクタ・アドレスに書き込むフラッシュ動作の好ましい実施形態を示すフロー図である。
【図７】書込みキャッシュが存在する記憶装置にデータを書き込むための好ましい処理を示すフロー図である。
【図８】書込みキャッシュが存在する記憶装置からデータを読み出すための好ましい処理を示すフロー図である。
【図９】記入動作に応答したスナップショット動作の好ましい実施形態を示すフロー図である。
【図１０】フラッシュ動作に応答したスナップショット動作の好ましい実施形態を示すフロー図である。
【図１１】記憶装置が電源投入されるときに書込みキャッシュの状態を回復するための好ましい処理を示すフロー図である。
【符号の説明】
【００７１】
１００  記憶装置アプリケーション
１０２  ホスト
１０４  記憶システム
１０６  レベル１（Ｌ１）書込みキャッシュ制御、書込みキャッシュ制御
１０８  Ｌ１書込みキャッシュ
１１０  レベル２（Ｌ２）キャッシュ制御、キャッシュ制御
１１２  ハッシュ・テーブル
１１４  バッファ・テーブル
１１８  主記憶装置
１２０  領域、不揮発性記憶装置
１２２  揮発性ランダム・アクセス・メモリ（ＲＡＭ）、ＲＡＭ
１２４  キャッシュ・ライン
１２６  主記憶装置
１２８  主記憶装置
１３０  主記憶装置
１３２  主記憶装置
１３４  スナップショット領域
２００  キャッシュ・ラインの配置
２０２  不揮発性記憶装置
２０４  キャッシュ・ライン、ライン
２０６  キャッシュ・ライン
２０８  キャッシュ・ライン
２１２  スナップショット領域
２１４  キャッシュ・ライン
２１６  キャッシュ・ライン
２１８  キャッシュ・ライン
２５０  先行シーケンス番号、メタ・データ
２５２  データ・ブロック
２５４  データ・ブロック
２５６  データ・ブロック
２５８  メタ・データ
２６０  パリティ・ブロック
２６４  データ・セクタ
２６６  データ・セクタ
２６８  データ・セクタ
２７０  データ・セクタ
２７２  データ・セクタ
２７４  データ・セクタ
２７６  データ・セクタ
２７８  データ・セクタ
３０２  ハッシュ・テーブル
３１０  ハッシュ・エントリ
３１１  リンクされたリスト
３１２  リンクされたリスト
３１３  リンクされたリスト、連結
３１４  リンクされたリスト
３１５  リンクされたリスト
３１６  リンクされたリスト、連結
３１７  リンクされたリスト、連結
３１８  リンクされたリスト
３２０  バッファ・テーブル
３３０  キャッシュ・ライン
３４０  ブロック
３４３  NextEntry
３７５  ブロック
３７０  キャッシュ・ライン
３７８  NextEntry
３９０  End
４００  記入動作
５００  フラッシュ動作
６００  データ書込み動作、データ読出し動作
７００  記入動作に応答したスナップショット動作、フラッシュ動作に応答したスナップショット動作
８００  回復動作
【図１】
2004213647.tif 000004
【図２】
2004213647.tif 000005
【図３】
2004213647.tif 000006
【図４】
2004213647.tif 000007
【図５】
2004213647.tif 000008
【図６】
2004213647.tif 000009
【図７】
2004213647.tif 000010
【図８】
2004213647.tif 000011
【図９】
2004213647.tif 000012
【図１０】
2004213647.tif 000013
【図１１】
2004213647.tif 000014