(57)【要約】  ソリッドステート装置を効率的に使用するためのシステム及び方法が提供される。いくつかの実施形態は、性能を最大化するために、データアクセスパターンを下層の隠された装置実装に配列することを目的に、循環ログとして非揮発性ソリッドステート装置を使用するデータ処理システムを提供する。メタデータは、データアクセスパターンを下層の装置実装に配列するために、データが散在可能である。複数の入力／出力（Ｉ／Ｏ）バッファはまた、メタデータ及びデータの線形ログへのパイプライン挿入に使用可能である。複数のＩ／Ｏバッファの観測された待ち行列の動きは、（例えば、過度に長い応答時間を予測するために）ストレージ装置の利用率が飽和にいつ近づくかを判別するために使用可能である。その後、利用率が飽和に近づいたとき、ストレージ装置上のＩ／Ｏ負荷は制限されてもよい。結果として、システムの応答時間全体が改善される。
2015518987.tif 000002
【特許請求の範囲】
【請求項１】
処理システムにおいて、
非揮発性ソリッドステートストレージ装置に書き込まれるべきデータを特定するステップであって、前記非揮発性ソリッドステートストレージ装置は複数の消去ブロックを含み、各消去ブロックは複数の書き込みセクタを含み、前記非揮発性ソリッドステートストレージ装置は論理セクタアドレスを前記非揮発性ソリッドステートストレージ装置における物理アドレスにマップする関連した変換層を有する、ステップと、
データを格納するための循環ログとして前記非揮発性ソリッドステートストレージ装置を使用するステップであって、当該ステップは、書き込みユニット単位で、データを前記非揮発性ソリッドステートストレージ装置に書き込むことを含み、当該書き込みユニットのサイズは前記非揮発性ソリッドステートストレージ装置における消去ブロックのサイズの整数倍である、ステップと、
を含む方法。
【請求項２】
前記非揮発性ソリッドステートストレージ装置は、バッキングストアのためのキャッシュとして動作され、
前記方法は、
ストレージ設備へのアクセスが要求される状態であって、当該アクセスは前記キャッシュへのアクセスによって果たされることが可能である、状態に応答して、
前記非揮発性ソリッドステートストレージ装置にアクセスするための第１の期待応答時間を推定して、
前記バッキングストアにアクセスするための第２の期待応答時間を推定して、
第２の期待応答時間が第１の期待応答時間よりも少ないとき、前記バッキングストアにアクセスして前記要求を満たすことによって、
前記アクセスを指示すべき対象のストレージ設備を判別するステップを更に含む、
請求項１記載の方法。
【請求項３】
前記非揮発性ソリッドステートストレージ装置において、書き込まれるべきデータを含む複数の書き込み動作を受信するステップと、
前記複数の書き込み動作の対象を、前記非揮発性ソリッドステートストレージ装置上の連続的な書き込みセクタに向けるステップと、
を更に含む、請求項１記載の方法。
【請求項４】
バッファに書き込まれるべきデータを、前記バッファが書き込みユニット分のデータを含むまで格納するステップと、
前記書き込みユニット分のデータを、前記バッファから前記非揮発性ソリッドステートストレージ装置に書き込むステップと、
を更に含む、請求項１記載の方法。
【請求項５】
前記データを前記非揮発性ソリッドステートストレージ装置に書き込むことは、書き込みユニットに書き込まれるデータ内のデータに関するメタデータを散在させることを含む、
請求項１記載の方法。
【請求項６】
前記非揮発性ソリッドステートストレージ装置の消去ブロックのサイズを推定するステップと、
書き込みユニットのサイズを、消去ブロックサイズの推定値の整数倍に設定するステップと、
を更に含む、請求項１記載の方法。
【請求項７】
プロセッサと、
前記プロセッサに接続されたメモリと、
前記プロセッサに接続された非揮発性ソリッドステートストレージ装置と、を備え、
前記非揮発性ソリッドステートストレージ装置は、
前記非揮発性ソリッドステートストレージ装置の複数のセルを、前記非揮発性ソリッドステートストレージ装置の消去ブロックのサイズの整数倍に対応するサイズを有するセクタに、論理的にグループ化するセクタマネージャと、
前記プロセッサから書き込み要求を受信して前記非揮発性ソリッドステートストレージ装置のセクタを決定して、前記書き込み要求と関連するデータを前記セクタに書き込む前に、書き出し、無効化し、割り当てるコントローラと、を備える、
処理システム。
【請求項８】
前記非揮発性ソリッドステートストレージ装置は、前記書き込み要求を処理する複数のチャンネルを備え、
前記ストレージシステムは、前記書き込み要求を待ち行列に入れる複数のバッファを更に備える、
請求項７記載の処理システム。
【請求項９】
前記コントローラによって決定された前記セクタは、前記コントローラによって書き込まれる前のセクタに連続的に続くセクタである、
請求項７記載の処理システム。
【請求項１０】
前記非揮発性ソリッドステートストレージ装置は、古いメタデータエントリ及び古いデータエントリを追い出し且つ前記書き込み要求と関連するデータのためのスペースを作るページ置換ポリシーを用いるログクリーニング処理を有する管理モジュールを備える、
請求項７記載の処理システム。
【請求項１１】
前記管理モジュールは、前記ページ置換ポリシーが古いメタデータエントリ及び古いデータエントリのサブセットを保存するときに古いデータエントリが処理のために必要とされる前に、前記非揮発性ソリッドステートストレージ装置から前記メモリに、古いデータエントリを自動的に読み出す、
請求項１０記載の処理システム。
【請求項１２】
前記管理モジュールは、前記ページ置換ポリシーがいかなる古いデータエントリも保存することがない場合、前記非揮発性ソリッドステートストレージ装置からの読み出しを回避する、
請求項１０記載の処理システム。
【請求項１３】
前記コントローラは、クライアントページアドレスを内部ページアドレスにマップするフラッシュ変換層を備える、
請求項７記載の処理システム。
【請求項１４】
前記非揮発性ソリッドステートストレージ装置はＮＡＮＤ型フラッシュストレージ装置である、
請求項７記載の処理システム。
【請求項１５】
非揮発性ソリッドステートストレージ装置と、
コントローラと、を備え、
前記非揮発性ソリッドステートストレージ装置は、複数のセルを、前記非揮発性ソリッドステートストレージ装置の消去ブロックのサイズの整数倍に対応するサイズを有するセクタに、論理的にグループ化し、
前記コントローラは、前記非揮発性ソリッドステートストレージ装置の連続的なセクタからデータエントリを書き出し、前記セクタを実質的に同時に無効化して且つ割り当てる、
システム。
【請求項１６】
メタデータは、前記非揮発性ソリッドステートストレージ装置の前記セクタにおける前記データエントリ内に散在される、
請求項１５記載のシステム。
【請求項１７】
前記メタデータは、前記データエントリの先頭に格納される、
請求項１６記載のシステム。
【請求項１８】
前記コントローラは、前記非揮発性ソリッドステートストレージ装置の連続的なセクタを対象にすることによって、連続的な書き込み動作を操作する、
請求項１５記載のシステム。
【請求項１９】
前記連続的なセクタは、物理的に隣接したセクタである、
請求項１５記載のシステム。
【請求項２０】
セクタを有する非揮発性ソリッドステートストレージ装置の書き込み待ち行列を監視するステップであって、前記セクタは前記非揮発性ソリッドステートストレージ装置の消去ブロックのサイズの整数倍に対応するサイズを有する、ステップと、
プロセッサを使用して、前記書き込み待ち行列に基づいて前記非揮発性ソリッドステートストレージ装置の利用率の推定値を生成するステップと、
前記利用率の推定値が第１の利用率閾値を超えるかを判別するステップと、
前記利用率の推定値が前記利用率閾値を超えると判別したとき、前記書き込み待ち行列内の書き込み要求を第２のストレージ装置に制限するステップと、
を含む、方法。
【請求項２１】
前記第２のストレージ装置に制限された書き込み要求は、非必須の書き込みを含む、
請求項２０記載の方法。
【請求項２２】
前記非必須の書き込みは、読み出し失敗から生じる書き込み要求を含む、
請求項２１記載の方法。
【請求項２３】
前記利用率の推定値が第２の利用率閾値を超えるかを判別するステップと、
前記非揮発性ソリッドステートストレージ装置からの非必須の読み出しを放棄するステップと、
を更に備える、請求項２０記載の方法。
【請求項２４】
前記非必須の読み出しはフラッシュ読み出しを含み、キャッシュ読み出しヒットを満たす、
請求項２３記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示される種々の実施形態は一般に、ソリッドステートストレージ装置に関する。より具体的には、いくつかの実施形態は、ソリッドステートストレージ装置への書き込みを最適化するシステム及び方法に関する。
【背景技術】
【０００２】
例えば、待ち時間が比較的に長い（すなわちアクセス時間がより長い）ハードディスクドライブ装置（ＨＤＤ）、及びフラッシュメモリ又はＤＲＡＭなどの待ち時間が比較的に短い（すなわちアクセス時間がより短い）ソリッドステート装置（ＳＳＤ）などの各種の非揮発性ストレージメディアは、情報を格納するために使用可能である。ＨＤＤは一般に、良好なストリーミング性能（例えば、大きな連続的ブロックの読み出し又は「トラック読み出し」）を提供するが、遅いアクセス時間によってランダムアクセス（すなわち、個別のディスクセクタの読み出し及び書き込み）に対してはうまく機能しない。その一方で、ＳＳＤは、待ち時間が比較的に短いため、ランダムアクセス及び頻繁なメモリアクセスにより適する。ＳＳＤは可動部分有しないために、ＨＤＤによって経験される大きな待ち時間をもたらす機械的な遅延を有さず、シーク時間は大幅に低減されてＳＳＤは非常に高速となる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
フラッシュメモリは一般に、ＤＲＡＭとディスクとの間のメモリ階層における新たな層として受け入れられている。ギガバイト（ＧＢ）当たりのコストの観点から、ＤＲＡＭ容量はフラッシュ容量よりも高価であり、フラッシュ容量はハードディスク容量よりも高価である。同時に、ＤＲＡＭ待ち時間はフラッシュよりも小さく、フラッシュ待ち時間はハードディスクよりも小さい。結果として、フラッシュメモリの入力／出力（Ｉ／Ｏ）動作当たりのコストは、ＤＲＡＭと磁気メディアとの間にある。メモリ階層におけるこの配置によれば、多くの場合、フラッシュメモリはキャッシュのためには理想的となる。
【０００４】
フラッシュ及び他のソリッドステートメモリは時にはＳＣＳＩドライブ又はＳＡＴＡドライブと同一のインタフェースを提供するが、下層の動作、実装、及び性能は、ソリッドステートメモリとＳＣＳＩドライブ又はＳＡＴＡドライブとの間では実質的に相違する場合がある。例えば、主要な相違点のうちの１つは、ＳＳＤにおける格納場所が、情報がそこに書き込み可能である前に、消去される必要があるということである。装置は通常、従来の書き込みユニット（セクタ）よりも大きな単位（消去ブロック）で消去される。これら動作上の相違点があるとしても、ＳＳＤは多くの場合、ＨＤＤのために開発された入力／出力インタフェースを使用する。結果として、ＨＤＤのために開発されたアルゴリズムに基づいたＳＳＤメモリの統合と実装は、アルゴリズムがＳＳＤベースのストレージの特性に合わせて最適化されていないために、ＳＳＤメモリの恩恵を十分に受けることができない場合がある。それ故、フラッシュメモリ及び他のソリッドステート装置をより効率的に用いるために、改善された技術が必要とされる。
【課題を解決するための手段】
【０００５】
本明細書において説明される種々の実施形態は一般に、フラッシュストレージ装置又は他の非揮発性ソリッドステートストレージ装置のための入力／出力（Ｉ／Ｏ）アクセスパターンをカスタマイズするシステム及び方法に関する。いくつかの実施形態はこのカスタマイズを使用して、フラッシュに優しいキャッシングアルゴリズムを創出する。これらの技術は、種々の関連する構成要素及び動作と合わせ、非揮発性ソリッドステート装置（例えば、フラッシュ装置、バッテリでバックアップされたＲＡＭ、及びその他）をより効果的に利用することができる。例えば、ハードディスクドライブとは異なり、ソリッドステートドライブからデータを消去することは通常、書き込みよりもより多くの時間を要する。結果として、１つの空きセクタを回復するために消去を実行することは、セクタの消去ブロック全体を回復するために消去を実行することよりも、価値が低い。従って、本明細書において説明されるいくつかの実施形態において、書き込みは、消去ブロックの整数倍単位でのみ、ソリッドステートストレージ装置に対して実行される。また、ハードディスクドライブは多くの場合、データからメタデータを分離してシーク時間を最小化する。しかしながら、シーク時間はソリッドステート装置にとっての重要ではないために、メタデータは多くの実施形態において、データと混合される場合がある。
【０００６】
ある実施形態において、非揮発性ソリッドステートドライブは、論理セクタアドレスを非揮発性ソリッドステートドライブにおける物理アドレスにマップするための、関連した変換層を有し、非揮発性ソリッドステートドライブは、（例えばホスト側のキャッシュにおける）データを格納するための循環ログとして扱われ、該データは、書き込みユニット単位で、非揮発性ソリッドステートドライブに書き込まれる。ここで、書き込みユニットのサイズは、非揮発性ソリッドステートドライブの消去ブロックのサイズの整数倍である。少なくともいくつかの非揮発性ソリッドステートドライブは書き込みの前に消去ブロック単位で消去される必要があるために、技術のこの組み合わせ、及びその変形例は、性能を改善するために、データアクセスパターンを、下層の隠された装置実装に配列する。
【０００７】
本発明の実施形態はまた、他の方法、種々の構成要素を有するシステム、並びに１つ又は複数のプロセッサに方法、方法の変形例、及び本明細書において説明される他の動作を実行させる命令のセットを含むコンピュータ読み出し可能なストレージメディアを含む。複数の実施形態が開示されるが、本発明の更に他の実施形態は、本発明の例示的な実施形態を示し説明する以下の詳細な説明から、当業者にとって明白となる。当然のことながら、本発明は、本発明の範囲から全く逸脱すること無く、種々の態様において変更可能である。従って、図面及び詳細な説明は、本質的に例示的なものとして見なされるべきであり、限定的なものとして見なされるべきではない。
【図面の簡単な説明】
【０００８】
【図１】本明細書において紹介される技術のいくつかの実施形態が実施され又は利用されることができる処理システムのブロック図を示す。
【図２】非揮発性ソリッドステートメモリ装置の構成要素を示すブロック図である。
【図３】非揮発性ソリッドステートメモリ装置のセクタ、ページ、及び消去ブロックの例を示すブロック図である。
【図４】非揮発性ソリッドステートメモリ装置に提示される書き込み要求を処理するための処理を示すフローチャートである。
【図５】ページ置換ポリシーに基づいて非揮発性ソリッドステートメモリ装置を動作させるための処理を示すフローチャートである。
【図６】非揮発性ソリッドステートメモリ装置と関連する待ち行列からの書き込み要求及び／又は読み出し要求を制限するための処理を示すフローチャートである。
【図７】非揮発性ソリッドステートストレージ装置をバイパスすることによってホスト側の非揮発性ソリッドステート装置のキャッシュの性能を改善するための処理を示すフローチャートである。
【発明を実施するための形態】
【０００９】
関連出願の相互参照
この出願は、２０１２年５月２２日付提出の米国特許出願第１３／４７７９６６号の優先権を主張するものであり、参照によってその全体が本明細書に組み込まれる。
【００１０】
本発明の実施形態は、添付の図面を用いて説明及び解説される。
【００１１】
図面は、必ずしも縮尺通りには描かれていない。例えば、図におけるいくつかの要素の寸法は、本発明の実施形態の理解の向上を助けるために、拡大又は縮小されている場合がある。同様に、本発明の実施形態のうちのいくつかの議論の目的のために、いくつかの構成要素及び／又は動作は、異なる複数のブロックに分離される場合があり、あるいは単一のブロックに組み合わされる場合がある。更に、本発明は種々の変更又は代替の形式に修正可能であるが、特定の実施形態は、図面において例示として示されており、あるいは以下に詳細に説明される。しかしながら、その意図は、発明を、説明される特定の実施形態に限定することではない。むしろ、本発明は、添付の特許請求の範囲によって定義される発明の範囲内に入る全ての変更、均等、及び置換を含むことが意図される。
【００１２】
フラッシュベースのソリッドステートストレージ装置（ＳＳＤ）及び他のＳＳＤはランダムアクセスインタフェースを供給し、時としてＳＣＳＩディスクドライブ又はＳＡＴＡディスクドライブになりすます。しかしながら、下層の実装及び性能プロファイルは、ディスクドライブから実質的に異なる。一般的な場合、ディスクドライブはディスク上に物理セクタを有し、該物理セクタは、ランダムアクセスインタフェースによってエクスポートされる論理セクタと同じ順番で配置される。例えば、セクタｎはセクタｎ＋１に物理的に隣接し、書き込みセクタｎ…（ｎ＋ｍ）は、書き込みセクタｎ…（ｎ＋２ｍ）のおよそ半分の長さを有する。ディスク書き込みを実行するに要する時間は実際上決定論的であり、書き込みのサイズ並びにディスクの物理的特性と状態（すなわち、書き込まれるセクタの数、ディスクヘッドの開始位置、及びプラッタの回転速度）によって導かれる。ひとたびディスクヘッドが適切に位置決めされると、セクタｎ…（ｎ＋ｍ）に書き込む時間はドライブの物理的特性によって決定される。
【００１３】
フラッシュドライブは通例、ディスクドライブと同一のインタフェースを提供するが、実装は大きく異なる。主要な相違点のうちの１つは、フラッシュメモリが書き込みの前に消去され、また、従来の書き込みユニット（セクタ）よりも大きな単位（消去ブロック）で消去される必要がある、ということである。効果的にディスクドライブになりすますために、従来のフラッシュドライブは、フラッシュ変換層（ＦＴＬ）ソフトウェアを使用する。ＦＴＬは、論理セクタアドレスのセットを、実質的により大きな物理ストレージプールにマップし、典型的には論理セクタｎを物理セクタｎにマップすることを試みる。データがフラッシュドライブに書き込まれるとき、ＦＴＬはデータを、現在割り当てられていない物理ストレージに格納して、データと関連する論理セクタ数から、データを保持する物理セクタへのマッピングを維持する。論理セクタが書き込まれるとき、ＦＴＬは新たなデータを同一の物理セクタに格納しようとする試みを行わず、これに代えて、ＦＴＬは、古い論理−物理マッピングを無効としてマークするとともに古い物理セクタを再利用のために利用可能としてマークして、新たなデータを別の物理セクタに書き込む。この処理が継続するものであった場合、それは最終的には結果として、物理ストレージの全てが充填されることとなる。
【００１４】
フラッシュドライブが完全に充填されないように保ってストレージを利用可能にするために、ＳＳＤは通常、該ＳＳＤが論理ストレージとして提供するよりも多くの物理ストレージを備えている。また、ＦＴＬは、（時として「ガベレージコレクション」と呼ばれる）クリーニングを実行する。通常、クリーニング処理は、１つ又は複数の消去ブロックである物理ストレージの領域を選択することと、領域におけるセクタのうちのどれが未だ有効であるかを判別することと、セクタをストレージの利用可能な領域にコピーすることと、そのようなセクタの論理−物理マッピングを更新することと、そして領域のバルク消去を実行することと、を含む。領域における無効なセクタは、利用可能な物理セクタの正味の増加をもたらすこととなる。
【００１５】
残念ながら、消去動作は、書き込み動作よりも実質的に多くの相当な時間を消費する。結果として、フラッシュドライブに書き込むための時間は、ドライブがどの程度「汚い」か（どれだけの空きスペースが現在利用可能であるか）と、そのようなスペースがドライブに亘ってどのように分散しているかと、ＦＴＬがバックグラウンドにおいてクリーニングをどの程度活動的に実行中であるかと、ドライブがどれだけのアイドル時間を有するかと、他の因子のホストと、に依存する。
【００１６】
本明細書に示す技術の種々の実施形態は、必要なハウスキーピングの量を低減する。いくつかの実施形態において、装置から（例えば、小さな時間オーバーヘッド又は小さな待ち時間を生じる）高い性能を提供する方法でメタデータ及びデータをフラッシュストレージ装置に書き込む技術が開示される。これらの技術の１つのアプリケーションはキャッシュ（例えば、ホスト側のフラッシュキャッシュ、又は、ネットワーク、サーバ上の仮想マシンハイパーバイザ等におけるなどの他の種類のフラッシュキャッシュ）にある。
【００１７】
いくつかの実施形態は、性能を最大化するために、データアクセスパターンを下層の隠された装置実装に配列することを目的に、循環ログとして非揮発性ソリッドステートストレージ装置（例えば、フラッシュストレージ装置）を使用するデータストレージシステムを提供する。例えば、書き込みブロックは、装置の消去ブロックの整数倍であることができる。また、メタデータ（記述的データ）は、データアクセスパターンを下層の装置実装に配列するために、データを用いて線形ログ中に散在されることが可能である。いくつかの実施形態はまた、置換アルゴリズムに依存する先読み又は回避を用いる線形ログエントリのクリーニングの技術を使用する。複数のＩ／Ｏバッファはまた、メタデータ及びデータの線形ログ中へのパイプライン挿入のために使用可能である。複数のＩ／Ｏバッファの観測される待ち行列の振る舞いは、（例えば、過度に長い応答時間を予測するために、）ストレージ装置の利用率が飽和に近づいているときを判別するために使用可能である。この場合、ストレージ装置上のＩ／Ｏ負荷は、利用率が飽和に近づいたとき、データの同一のコピーを含むバッキングストアに制限されてもよい。結果として、システムの応答時間全体が改善される。
【００１８】
図１は、本明細書において紹介される技術のいくつかの実施形態が利用されることができる処理システム１００のブロック図を示す。図１に示す実施形態において、処理システム１００はホスト１１０を備える。ホスト１１０は、ハイパーバイザ１１５を使用してストレージサーバ１２０とインタラクトする仮想マシン１１２を有する。図１に示すように、ストレージサーバ１２０は、１つ又は複数のプロセッサ１２２と、バッファキャッシュ１３８を有するメモリ１２４と、ネットワークアダプタ１２６と、システムバス１２５によって相互接続されたストレージアダプタ１２８とを備える。
【００１９】
ハイパーバイザ１１５は、複数のオペレーティングシステムがホストコンピュータ上で同時に動作することを可能にする仮想マシンマネージャ（ＶＭＭ）である。ハイパーバイザ１１５は、仮想オペレーティングプラットフォームをオペレーティングシステムに提供する。多くの場合において、種々のオペレーティングシステムの複数のインスタンスは、仮想化されたハードウェアリソースを共有してもよい。本発明の種々の実施形態において、ライブ仮想マシン移行を通じたキャッシュ一貫性及び仮想ディスク上のデータ管理動作を可能とするために、ホスト１１０に接続されるＳＳＤ１１７Ａ（例えば、ＰＣＩｅフラッシュカード）を使用する非揮発性ソリッドステートキャッシュは、ハイパーバイザ１１５によって使用されてもよい。メタデータ及びデータの書き込みのために開示される技術は、性能を改善する（例えば、オーバーヘッド時間又は待ち時間を減少させる）方法で、ソリッドステートキャッシュを用いて利用可能である。
【００２０】
（複数の）ホスト１１０及び（複数の）仮想マシン１１２はそれぞれ、情報配信のクライアント／サーバモデルに従って、ストレージサーバ１２０とインタラクトしてもよい。すなわち、（複数の）ホスト１１０は、ストレージサーバ１２０のサービスを要求してもよく、システムは、ネットワーク１６０上でパケットを交換することによってなどして、ホスト１１０によって要求されたサービスの結果を返してもよい。（複数の）仮想ホスト１１０は、ファイルの形式で情報にアクセスするとき、ＴＣＰ／ＩＰ上の共通インターネットファイルシステム（ＣＩＦＳ）プロトコル又はネットワークファイルシステム（ＮＦＳ）プロトコルなどのファイルベースのアクセスプロトコルを含むパケットを発行してもよい。変形例として、（複数の）ホスト１１０は、ＬＵＮ又はブロックの形式で情報にアクセスするとき、ＴＣＰ上でカプセル化されたスモールコンピュータシステムインタフェース（ＳＣＳＩ）プロトコル（ｉＳＣＳＩ）及びファイバーチャンネルプロトコル（ＦＣＰ）上でカプセル化されたＳＣＳＩなどの、ブロックベースのアクセスプロトコルを含むパケットを発行してもよい。
【００２１】
ストレージサーバ１２０は、ＳＳＤ及びＨＤＤなどの書き込み可能な持続性ストレージメディア上の情報の編成に関連するストレージサービスを提供するコンピュータであることが可能である。ストレージサーバ１２０はまた、オペレーティングシステム２００を含む。オペレーティングシステム２００はファイルシステムを実装して、電子ストレージメディア１４０及び磁気ストレージメディア１５０上の論理データコンテナ（例えば、ボリューム、論理ユニット、ディレクトリ、及び／又はファイル）の階層構造として、格納されたデータを論理的に編成する。
【００２２】
本明細書において紹介される技術が任意の種類の特定目的コンピュータ（例えば、ファイルサーバ又はストレージサービス機器）、又は独立型のコンピュータ又はその一部を含むストレージサーバとして具現化される、若しくはこれを有する、一般目的コンピュータに適用できる、ということは当業者によって理解されるであろう。図１は、モノリシックの非分散型ストレージサーバ１２０を例示するが、種々の実施形態は他の種類のストレージ構成（例えば、クラスタストレージ構成）に対して適用可能である。更に、この説明の技術は、種々のストレージサーバアーキテクチャに適合可能である。ここで、種々のストレージサーバアーキテクチャは、クライアントコンピュータ又はホストコンピュータに直接的に接続されるネットワークアッタチトストレージ（ＮＡＳ）、ストレージエリアネットワーク（ＳＡＮ）、又はストレージ装置アセンブリを含むが、これらに限定されない。従って、用語「ストレージサーバ」は、データへのファイルベースのアクセス、データへのブロックベースのアクセス、又はその両方を提供するストレージサーバを含むような構成を含むように、広く解釈されるべきである。
【００２３】
メモリ１２４は、（複数の）プロセッサ１２２及びアダプタによってアドレス可能である格納場所を含み、ソフトウェアプログラム及びデータ構造を格納して本明細書において説明される技術を実行することができる。（複数の）プロセッサ１２２及びアダプタは、ソフトウェアプログラムを実行してデータ構造を操作するように構成された、処理要素及び／又は論理回路を備えてもよい。ストレージオペレーティングシステムの一部は、メモリ１２４に常駐してもよく、また（複数の）プロセッサ１２２によって実行されてもよい。このストレージオペレーティングシステムは、サーバ１２０上で実行するソフトウェア処理を支援して、ストレージ動作を起動することによってストレージサーバを機能的に組織化する。種々のコンピュータ読み出し可能なメディアなどの他のメモリ機構がむしろ使用されて、本明細書において説明される実施形態に関するプログラム命令を格納して実行してもよい、ということは当業者にとって明白となろう。電子ストレージメディア１４０及び磁気ストレージメディア１５０は、停電又はストレージサーバ１２０の他の障害の場合にデータを維持可能な、持続性のある書き込み可能なストレージスペースを提供するように構成される。従って、電子ストレージメディア１４０及び磁気ストレージメディア１５０は、大規模メモリアレイとして具現化されてもよい。
【００２４】
ネットワークアダプタ１２６は、ネットワーク１６０を介してストレージサーバ１２０をホスト１１０に接続するために必要とされる回路構成要素と機械的構成要素を備え、これはポイントツーポイント（Ｐ２Ｐ）接続又は共有メディアを含んでもよい。ネットワーク１６０は、情報を交換可能な相互接続される装置の任意のグループであることができる。いくつかの実施形態において、ネットワーク１６０は、ローカルエリアネットワーク（ＬＡＮ）上のわずかのいくつかのパーソナルコンピュータ、特定目的コンピュータ、及び／又は、一般目的コンピュータであってもよく、又は、インターネットと同じ規模であってもよい。いくつかの場合において、ネットワーク１６０は、（プライベート及び／又は公共の）複数のネットワーク、更には複数の異種のネットワークを備えてもよい。ここで、複数の異種のネットワークは、種々のネットワークの間の通信を促進するように動作可能なゲートウェイを介して相互接続される、１つ又は複数のボーダーネットワーク、広帯域ネットワーク、サービスプロバイダーネットワーク、インターネットサービスプロバイダ（ＩＳＰ）ネットワーク、及び／又は公衆交換電話網（ＰＳＴＮ）などである。
【００２５】
ストレージアダプタ１２８は、ストレージサーバ１２０上で実行するストレージオペレーティングシステム２００と協働して、ホスト１１０によって要求された情報にアクセスする。情報は、ＳＳＤ及びＨＤＤとして例示的に具現化される電子ストレージメディア１４０及び磁気ストレージメディア１５０上に格納されてもよい。ストレージアダプタは、従来の高性能ファイバーチャンネルシリアルリンクトポロジーなどの、Ｉ／Ｏ相互接続配置を介してＳＳＤ１４０及びＨＤＤ１５０に接続するＩ／Ｏインタフェース回路を含む。情報はストレージアダプタ１２８によって検索され、必要であれば、システムバス１２５を介してネットワークアダプタ１２６に転送される前に（複数の）プロセッサ１２２（又はアダプタ１２８）によって処理される。ここで、上記情報はパケットにフォーマットされてホスト１１０に返される。
【００２６】
説明された実施形態において、バッファキャッシュ１３８はメモリ１２４の一部である。しかしながらこれは例示であって限定的ではなく、バッファキャッシュ１３８は、例えばポイントツーポイント接続を使用して、メモリと接続されてもよい。また、バッファキャッシュ１３８は、メモリ１２４から、メモリ１２４の一部から、又は（複数の）プロセッサ１２２の一部から分離されてもよい。一般的に、バッファキャッシュ１３８などのバッファキャッシュメモリは、メモリアクセスを実行する平均時間を低減するように動作可能な、ＲＡＭ（例えばＤＲＡＭ）などの、より小型でより小さな待ち時間を有する（高速の）メモリを含む。メモリアクセスが実行されるときにバッファキャッシュがまず、要求されたデータがそこに配置されているかを判別するようにチェックされて、そうである場合にはデータがＳＳＤ又はＨＤＤなどの持続性ストレージメディアに代えてバッファキャッシュ１３８からアクセスされてもよいように、バッファキャッシュは通常、メモリ１２４における最も頻繁に使用される場所からのデータのコピーを格納する。このように、バッファキャッシュ１３８などのバッファキャッシュは、持続性ストレージにアクセスしてデータを取得せざるを得ない状況を回避することによって、メモリアクセス時間を低減する。
【００２７】
図２は、非揮発性ソリッドステートメモリ装置２００の構成要素を示すブロック図である。非揮発性ソリッドステートメモリ装置２００は、ストレージ環境内の、任意の種々の場所において、また任意の種々の目的のために、使用されてもよい。例えば、非揮発性ソリッドステートメモリ装置２００は、ホスト側のキャッシュ、又は、処理システム１００内のディスクバッキングストレージのためのキャッシュであってもよい。図２に例示する非揮発性ソリッドステートメモリ装置２００の実施形態は、ＦＴＬソフトウェア２２０を動作させるコントローラ２１０と、一時ストレージ装置２３０と、各々がデータを格納する複数のセルを有するフラッシュメモリチップ２４０Ａ〜２４０Ｈと、を備える。コントローラ２１０は、バス（例えば、ＰＣＩ、ＳＡＴＡ、ＳＡＳ、ＦＣ、又は他のバス）を介して入力される要求を受け付け、また当該要求に応答し、フラッシュメモリチップ２４０Ａ〜２４０Ｈとインタラクトする。従って、コントローラ２１０は通常、フラッシュメモリチップ２４０Ａ〜２４０Ｈ（例えばＮＡＮＤ型メモリ構成要素）をホスト／クライアントコンピュータ、バス、又はサーバにブリッジする電子回路（例えば埋め込まれたプロセッサ）を備える。
【００２８】
コントローラ２１０は、種々の機能を実行してもよい。この種々の機能は、ガーベジコレクション、暗号化、キャッシング（読み出し及び書き込みの両方）、エラー訂正、及びその他の機能を含むが、これらに限定されない。通常、ＦＴＬソフトウェア２２０は、コントローラ上で（例えば埋め込まれたプロセッサ上で）、動作するソフトウェアを含むことが可能である。ＦＴＬ２２０は、論理（クライアント）セクタ及びページアドレスを物理的（内部）ページアドレスにマップする。新たなデータはフラッシュドライブに送信されると、ＦＴＬ２２０はドライブのフラッシュメモリチップ２４０Ａ〜２４０Ｈ上の適切な未使用スペースを発見して、そこにデータを格納する。多くの実施形態において、ＦＴＬ２２０は内部データ構造を使用して、論理アドレスと物理アドレスとの間の対応を追跡する。
【００２９】
フラッシュメモリチップ２４０Ａ〜２４０Ｈにおける各メモリセルは、空き状態、使用状態、又は無効状態にあることができる。空き状態は、メモリセルが如何なるデータも格納していない状態を示す。使用状態は、メモリセルがあるデータを現在格納している状態を指す。無効状態は、メモリセルに格納されたデータがもはや有効ではない状態を指す。無効としてマークされたセルは、新たなデータがそのセルに書き込まれることができる前に消去される必要がある。しかしながら、非揮発性ソリッドステートメモリ装置の多くは、図３でより詳細に説明するように、ブロック単位で消去されることだけが可能である。
【００３０】
図３は、非揮発性ソリッドステートストレージ装置と関連するセクタ、ページ、及び消去ブロックの例を示すブロック図である。フラッシュ装置などの典型的な従来のＳＳＤは、クライアントが５１２バイトのセクタ３１０を読み出し／書き込みすることを可能にするが、ページ３２０（通常は２キロバイト、４キロバイト、又は８キロバイト）を単位として実装される。ＳＳＤの多くは、何らかの書き込みが対象の格納場所に対して発生する前に、当該対象の格納場所を消去させて空きスペースを作る必要がある。一例はＮＡＮＤ型フラッシュである。消去の最小単位は消去ブロック３３０として参照される。消去ブロックは、３２個、６４個、１２８個、又は他の個数のページであってもよい。
【００３１】
ＳＳＤからデータを消去することは通常、ＳＳＤにデータを書き込むことよりも多くの時間を要するため、ドライブが消去動作を実行するに要する時間の効率を改善するは、性能の大幅な改善をもたらすことができる。例えば、１つの空きセクタを回復するための消去を実行することは、セクタの消去ブロック全体を回復するための消去を実行することよりも価値が低い。本明細書において紹介される技術の種々の実施形態は、無効化されているブロックで書き込まれているブロックを整列する。いくつかの実施形態において、セクタの消去ブロックの整数倍ｉは一度に書き出し可能である。ｉ個の消去ブロックのサイズの領域は、実質的に同時に無効化され且つ割り当てられることが可能である。これにより、十分な価値を有する消去動作が得られる。
【００３２】
メモリ装置の消去ブロックのサイズは、常に始めから知られているとは限らない。いくつかの実施形態は、装置の種類、製造業者などの種々の情報と要素を使用して、消去ブロックのサイズを推定する。推定は、あるｊに対する、２ｊ個のセクタのサイズの消去ブロックから開始する。次いで、２ｋ個のセクタの書き込みブロックは装置に書き込まれてもよい。ここで、ｋは少なくともｊと同じ大きさであるように十分に大きく選択される。これは、各動作についての２ｋ−ｊ個の消去ブロックを無効化して、消去して、そして書き込むドライブをもたらすこととなる。これは、非揮発性ソリッドステートメモリの動作の従来の方法とは対照的であり、ここで、消去は、消去ブロックのサイズよりも小さい１つの書き込みセクタ又は複数のセクタを回復するために、発生する。
【００３３】
従来、メタデータ（記述データ）は、それを記述するデータから分離して、書き込まれて格納される。ディスクストレージを用いて、メタデータは、メタデータが少ない数のＩ／Ｏで読み込み可能であるように連続的な領域に格納可能であり、ディスクシーク動作の回数が低減される。しかしながらＳＳＤはシーク時間遅延を示さず、そのため動機は適用されない。いくつかの実施形態において、メタデータはデータと混合される。
【００３４】
種々の実施形態は、ある時間期間だけ、特定のデータ項目又はメタデータ項目の非揮発性ソリッドステートストレージ装置への書き込みを遅延させてもよく、データ及びメタデータの２ｋ個のセクタが蓄積されるまでバッファは書き込む。いくつかの場合において、これは望まれない場合がある。１つの例はストレージシステムであり、このストレージシステムはディスクバッキングストレージのためのキャッシュとしてフラッシュストレージを使用して、電源の障害又はシステムのクラッシュなどの予定外の中断の間、キャッシュ状態を損傷を受けていない状態に維持する必要がある。この場合において、フラッシュストレージ上に格納されるべきデータ及びメタデータに反映されるキャッシュの状態の変更は、キャッシュの状態の変更を開始したストレージシステムの読み出し又は書き込み動作の完了を確認する前に、フラッシュストレージに直ちに記録される必要がある。
【００３５】
いくつかの非揮発性ソリッドステートストレージ装置は、電力保護されたＲＡＭ書き込みバッファを含む。このバッファは、フラッシュ装置が、データをフラッシュストレージに実際に書き込むこと無く、書き込み要求を迅速に完了することを可能にする。電力保護されたＲＡＭ書き込みバッファを制御している非揮発性ソリッドステートストレージ装置におけるロジックは、バッファがフラッシュストレージにいつ書き込まれる（フラッシュされる）かを制御するポリシーを有する。通常、前の書き込みの連続的に次のものでない書き込み要求が受信されるとき、又はさもなければ、現在バッファされた書き込みの近くのアドレスに書き込まない書き込み要求が受信されるとき、バッファはフラッシュされる。バッファがフラッシュされるが消去ブロック全体よりも少なく含む場合、上述の性能の利点は失われる場合がある。
【００３６】
いくつかの実施形態において、２ｋ個のセクタの部分的に充填された領域がフラッシュストレージに記録される必要があり且つフラッシュストレージ装置が電力保護されたＲＡＭ書き込みバッファを含む場合、更なる技術が用いられる。例えば、部分的に充填された領域の全体は、非揮発性ソリッドステートストレージ装置に書き込まれてもよい。書き込みは、完全に充填された領域のために通常使用され得るアドレスにおいて開始してもよい。部分的に充填された領域が充填されると、後続の記録は、部分的に充填された領域の全体を非揮発性ソリッドステートストレージ装置に書き込むことを継続する。後続の書き込みの各々は、領域全体が完全に充填されることがないとしても、完全に充填された領域のために通常使用され得る次のアドレスにおいて開始してもよい。このことは、部分的に充填された領域の先頭のセクタを上書きすることをもたらすが、互換性のある電力保護されたバッファフラッシュポリシーを有する非揮発性ソリッドステートストレージ装置は、消去ブロック全体が書き込まれるまで、それらのバッファをフラッシュすることはない。
【００３７】
いくつかの実施形態において、部分的に充填された領域の新たに変更されたセクタのみは、非揮発性ソリッドステートストレージ装置に書き込まれる。それらは、あたかも領域全体が書き込まれるかのように、同一のアドレスに書き込まれる。このことは、高々、最後の書き込みの最後のセクタのみにおいて上書きをもたらすが、互換性を有する電力保護されたバッファフラッシュポリシーを有する非揮発性ソリッドステートストレージ装置は、消去ブロック全体が書き込まれるまでそれらのバッファをフラッシュすることはない。
【００３８】
他の実施形態において、粗粒の技術は永続性を提供するために用いられてもよい。非揮発性ソリッドステートストレージ装置上の周知技術のセクタは、（例えば、電源の喪失による）ストレージ装置の制御されないシャットダウンを表示する「不正なシャットダウン」の表示を含むように選択されてもよい。不正なシャットダウンの表示は、単一のビットと同じように小さくてもよい。ストレージ装置が初期化するとき、不正なシャットダウンの表示は、その収容しているセクタを同期的に書き込むことによって、真値の状態に持続的に設定される。規則的なシャットダウンの間、非揮発性ソリッドステートストレージ装置へのＩ／Ｏは休止される。ひとたび非揮発性ソリッドステートストレージ装置への全ての未処理のＩ／Ｏが完了すると、不正なシャットダウンの表示は偽値に設定される。予定外の障害によってストレージ装置が予期せずシャットダウンした場合、不正なシャットダウンの表示は真の状態になり得る。非揮発性ソリッドステートストレージ装置の内容が信用できるかを判別するために、不正なシャットダウンの表示が用いられてもよい。偽値は、非揮発性ソリッドステートストレージ装置の内容が信用できることを示す。真値は、非揮発性ソリッドステートストレージ装置の内容が潜在的に整合性を有さず従って無視されるべきものであることを示す。
【００３９】
整数個の消去ブロックのみへの書き込みの技術はまた、多くの他のアプリケーションにおいて利点を有することが可能である。一例は、非揮発性ソリッドステートストレージ装置が循環ログとして使用されるときである。図４は、循環ログとして利用される非揮発性ソリッドステートメモリ装置に提示される書き込み要求を処理して、ストレージリソースを利用するための効果的で予測可能な処理を可能にする、処理４００を示すフローチャートである。本発明の種々の実施形態によれば、処理４００における１つ又は複数の動作は、図２におけるコントローラ２１０などの種々のシステム構成要素によって実施可能である。受信動作４１０は書き込み要求を受信して、データを非揮発性ソリッドステートストレージ装置（例えばフラッシュドライブ）に書き込む。決定動作４２０は、データをストレージ装置に書き込むために必要なセクタの数を決定する。例えば、セクタの数は、データサイズをセクタのサイズで除算して得られる結果を最も近い整数に切り上げることによって決定可能である。
【００４０】
いくつかの実施形態において、複数の書き込みブロックのセクタは、非揮発性ソリッドステートストレージ装置の消去ブロックのサイズの整数倍に対応するサイズに、（例えばセクタマネージャ又はコントローラによって）論理的に分割されている。循環ログと関連するセクタは、ターゲッティング動作４３０が、各連続的な書き込み動作の対象をストレージ装置上の次の連続的なセクタ範囲に向けるように、順序づけ可能である。ひとたび装置の終端に達すると、ターゲッティング動作４３０は再び、セクタの先頭から開始することができる。例えば、ｗが２ｋであるとき、セクタ０…（ｗ−１）がまず書き込まれ、続いてセクタｗ…（２ｗ−１）が書き込まれ、次いでセクタ２ｗ…（３ｗ−１）が書き込まれ、ドライブの論理的終端に到達するまで行われる。その時点で、ターゲッティング動作４３０は一周して元に戻り、書き込み動作の対象を書き込みブロック０…（ｗ−１）に向ける。
【００４１】
ひとたび（複数の）セクタが決定されると、割り当て動作４４０は、次の連続的な（複数の）セクタに現在格納されているデータエントリを書き出して、関連したセルの状態を無効に変更して、データが書き込まれることを可能にするようにセルを割り当てる。次いで、書き込み動作４５０は、書き込み要求からのデータを（複数の）セクタに書き込む。
【００４２】
ひとたび非揮発性ソリッドステートストレージ装置が満杯になると、循環ログは周回して論理セクタの先頭に至る。この時点で、ログにおける古いメタデータエントリ及びデータエントリは、それらが割り当て動作４４０を用いて上書きされる前に、消去される必要がある（なぜならば、それらをまず消去しなければ、ソリッドステート装置が、現在使用されている場所への書き込みを許さないためである）。用語「ページ置換ポリシー」は、これらの古いログエントリをクリーニングするためのポリシー又はステラテジーを参照するために用いられる。ＣＬＯＣＫなどのいくつかの周知のページ置換ポリシーは、古いメタデータエントリ及びデータエントリのサブセットを保存してもよい。先入れ先出し（ＦＩＦＯ）などの他のページ置換ポリシーは、全てのエントリを事前に追い出す（エビクトする）。いくつかの実施形態は、図５においてより詳細に説明するようにページ置換ポリシーに基づいて、ログクリーニング動作を適応的に発行する。
【００４３】
いくつかの実施形態は、以下に図５を参照して説明するように、ページ置換ポリシーに基づいてログクリーニング動作を発行してもよい。図５は、ページ置換ポリシーの種類に基づいて非揮発性ソリッドステートメモリ装置を動作させる処理５００を示すフローチャートである。ページ置換ポリシーの種類に依存して、古いエントリは、それらが追い出される前に読み出される必要がある場合がある。処理５００における動作は、非揮発性ソリッドステートメモリ装置内のコントローラ、又はメモリ装置若しくはストレージシステムと関連するプロセッサによって、実行されてもよい。ページ置換決定動作５１０は、ストレージシステムのページ置換ポリシーを決定する。次いで、判別動作５２０は、ページ置換ポリシーの種類に基づいて、ページ置換ポリシーが（全てのデータを追い出すこととは対照的に）データを保存するか、を判別する。
【００４４】
ページ置換ポリシーが古いメタデータエントリ及びデータエントリのサブセットを保存してもよいものであるとき、判別動作５２０は読み出し動作５３０に分岐する。読み出し動作５３０は、古いエントリをメモリ（例えば図２のＤＲＡＭ２３０）に読み出して、ページ置換ポリシーに照らしてそれらを評価する。評価動作５４０は、メモリに読み出された古いエントリが保存されるべきであるかを判別する。いくつかの実施形態において、読み出し動作５３０は、古いエントリを、それらが処理のために必要とされる前に、フラッシュストレージ装置からメモリに読み出すことができる。これらのエントリは、いくつかの実施形態において、事前に読み出されることが可能である。ここで、ログは連続的に書き込まれ、従ってこれらのエントリを含んでいるログブロックは、ページ置換ポリシーに照らしてエントリが評価される後まで、書き込まれることとはならない。フラッシュストレージ装置に対して発行される事前読み出し動作の数は、システム管理者又はインテリジェントマネジメントソフトウェアによって、動的に制御可能である。
【００４５】
ページ置換ポリシーが古いメタデータエントリ及びデータエントリを保存しない（すなわち、全てのエントリを追い出す）ものである場合、判別動作５２０は、追い出し動作５５０に分岐する。追い出し動作５５０は、データを読み出すことなく、古いデータエントリを自動的に追い出す。その結果、全てのログクリーニング読み出し動作は、それらが不要であるために、除外される。古いエントリの評価に代えて、ページ置換ポリシーは、メモリ内のデータ構造から古いエントリを追い出す。これらの読み出し動作を除外することによって、フラッシュストレージ装置の性能は、不要な動作を回避することによって改善される。
【００４６】
いくつかの実施形態において、非揮発性ソリッドステートメモリ装置へ／からの書き込み／読み出し動作は、待ち行列に入れられる。メモリ装置の利用率は、待ち行列の特性（例えば、長さ、待ち行列の長さの変化の速度）の関数として、推定可能である。例えばメモリ装置がキャッシュとして使用されており且つ利用率が過度に高い場合、読み出し又は書き込み動作を「制限する」と呼ばれる処理である、キャッシュをバイパスすることは、利点を有する場合がある。図６は、非揮発性ソリッドステートメモリ装置と関連する書き込み待ち行列からの書き込み要求及び／又は読み出し要求をリダイレクトする（制限する）処理６００を示すフローチャートである。処理６００と関連する１つ又は複数の動作は、プロセッサ、ストレージオペレーティングシステム、ＦＴＬ、又は他のハードウェア構成要素によって、実行されてもよい。複数の書き込み動作が非揮発性ソリッドステートストレージ装置への待ち行列に入れられるとき、ストレージ装置の利用率は、監視動作６１０によって実行される書き込み（又は読み出し）待ち行列の長さの観察又は監視によって、推定されてもよい。
【００４７】
推定動作６２０は、非揮発性ソリッドステートメモリ装置の利用率の推定値を生成する。推定値は、監視動作６１０によって測定される書き込み待ち行列の長さに、少なくとも部分的に基づいてもよい。例えば、書き込みバッファの有限プールがほぼ空である（すなわち待ち行列の長さが長い）場合、非揮発性ソリッドステートメモリ装置はほぼ１００％の利用率で動作していると推定され得る。書き込みバッファの有限プールがほぼ満杯である（すなわち待ち行列の長さが短い）場合、非揮発性ソリッドステートメモリ装置はほぼ０％の利用率で動作していると推測され得る。ほぼ１００％の利用率で動作しているとき、新たに提示されたＩ／Ｏ要求は、待ち行列においてそれに先行しているＩ／Ｏの完了を待つことによって生じる待ち行列遅延によって、長い応答時間が認められることとなる。
【００４８】
ひとたび推定値が生成されると、第１の閾値判断動作６３０は、利用率の推定値が第１の閾値を超えるかを判別する。超えない場合、判断動作６３０は監視動作６１０に分岐して戻り、書き込み待ち行列の長さの監視を継続する。第１の閾値を超えていると判断動作６３０が判別した場合、動作６３０は、利用率の推定値が第２の閾値を超えるかを判別する第２の閾値判断動作６４０に分岐する。第２の閾値を超えない場合、判断動作６４０は書き込み制限動作６５０に分岐する。第１及び第２の閾値の両方は、監視されるシステム実行に基づいて、システム管理者によって、ストレージオペレーティングシステムによって、又はストレージシステムと関連する他の構成要素若しくはサブシステムによって、適応的に設定可能である。
【００４９】
書き込み制限動作６５０は、第２のストレージ装置への書き込み待ち行列内の書き込み要求（例えば、読み出し失敗から生じるものなどの非必須の書き込み）をリダイレクト（制限）する。例えば、あるバッキングストアのためのキャッシュとしてフラッシュストレージ装置を使用するストレージシステムに対して、又はいくつかの他のバッキングストア及びフラッシュストレージの両方においてデータが利用可能であるある他の編成に対して、バッキングストアのＩ／Ｏ容量全体（スループット）は、フラッシュストレージ装置のＩ／Ｏ容量全体を超えてもよい。バッキングストアは少なくとも、フラッシュストレージ装置のＩ／Ｏ容量に加えて、いくらかのＩ／Ｏ容量を提供する。Ｉ／Ｏ要求がフラッシュ装置のＩ／Ｏ容量を超える（すなわち、Ｉ／Ｏ要求がフラッシュストレージ装置の１００％の利用率を超える）場合、ストレージシステムは、フラッシュストレージ装置からの負荷を制限することによって、また必要に応じてバッキングストレージを使用してＩ／Ｏ要求を満たすことによって、システムの性能全体を改善できる。
【００５０】
特に、非揮発性ソリッドステート装置（例えばフラッシュ）を使用するキャッシュストレージシステムに関して、システムは、ストレージ装置への書き込み待ち行列のサイズがある閾値を超えるときにキャッシュストレージ装置への非必須の書き込みを放棄することによって、負荷を制限することを選択してもよい。非必須の書き込みの例は、キャッシュにおける読み出し失敗かキャッシュへの書き込みのいずれかの結果としてキャッシュストレージ装置に新たなデータを入力する書き込みである。キャッシュに既に入力されたある場所への書き込みの場合、データがキャッシュストレージ装置に書き込まれない場合があるが、古いキャッシュエントリを無効化するメタデータはなおフラッシュストレージ装置に書き込まれる必要がある。しかしながら、このメタデータはデータよりも非常に小さく、そのため、正味の結果はそれでもやはり、フラッシュストレージ装置上のＩ／Ｏ負荷の減少を示す。キャッシュに入力されない書き込み要求は、データを直接バッキングストレージに書き込むことによって、操作される必要がある。キャッシュに入力されない読み出し失敗は、単に放棄されてもよい。
【００５１】
フラッシュストレージ装置への書き込み待ち行列のサイズがより大きな第２の閾値を超えると第２の閾値判断動作６４０が判別した場合、システムは、制限動作６６０を使用して、キャッシュストレージ装置からの（非必須の書き込みに加えて）非必須の読み出しを放棄することによって、更なる負荷を制限することを選択してもよい。非必須の読み出しの１つの例は、キャッシュの読み出しヒットを満たすためのフラッシュ読み出しである。読み出し要求はむしろ、要求されたデータがキャッシュに一意的に存在しない（例えば、キャッシュがライトスルーポリシー若しくはライトアラウンドポリシーを使用する、又はキャッシュがライトバックポリシーを使用するが要求されたデータがキャッシュにおいて利用可能であるのみとして印が付されていない）ならば、フラッシュストレージ装置よりはむしろ、バッキングストアから読み出すことによって操作されてもよい。その後、制限動作６６０は、書き込み待ち行列の長さが監視される監視動作６１０に分岐する。
【００５２】
書き込み要求の制限（リダイレクト）に加えて、本発明のいくつかの実施形態は、非必須の動作のためにキャッシュストレージをバイパスすることができる。コンピュータストレージシステムにおいて、ストレージキャッシュは頻繁に、バッキングストアよりも短いサービス時間を有するが、より低い全Ｉ／Ｏ容量（最大スループット）を有する。そのようなシステムにおいて、ある高いレベルのＩ／Ｏ要求では、キャッシュにアクセスする応答時間は、キャッシュのための下層のストレージにアクセスする際の大きな待ち行列遅延によって、バッキングストアに直接的にアクセスする応答時間を超える。このレベルのＩ／Ｏ要求では、システムは、非必須の動作のためにキャッシュストレージをバイパスすることによって、より良い性能を提供することができる。例えば、キャッシュからの読み出しＩ／Ｏ要求を提供することよりもむしろ、システムはバッキングストアから直接的に来る読み出しＩ／Ｏ要求を提供することによって、より良い性能を提示しても良い。
【００５３】
従来のキャッシュバイパスメカニズムは、キャッシュストレージとバッキングストレージとのサービス時間及び最大スループットの間に非対称性が無いＣＰＵキャッシュに注目している。そのようなキャッシュにおいて、キャッシュバイパスメカニズムの目的は、再び参照されることのないデータのアドレスを特定することと、そのようなデータをキャッシュすることを回避することである。なぜならば、そのようなデータをキャッシュすると、無用なデータでキャッシュを汚染してしまい、それによってキャッシュヒット率が低下してしまうからである。対照的に、本明細書において議論される種々の実施形態は、キャッシュストレージとバッキングストレージとのサービス時間及び最大スループットの間に非対称性があるときに適用される。それは、キャッシュされるべきではないデータをそのアドレスによって特定することを試みず、むしろ、キャッシュ上の全Ｉ／Ｏ要求に対するキャッシュストレージ装置の利用可能なＩ／Ｏ容量の現在の比率に基づいて、日和見的な決定を行う。
【００５４】
図７は、デバイス上の負荷が非常に高いためにバッキングストアからのデータを取得がより高速であるときに非揮発性ソリッドステートストレージ装置をバイパスすることによって、ホスト側の非揮発性ソリッドステート装置（例えばフラッシュ）キャッシュの性能を改善する処理７００を示すフローチャートである。処理７００と関連する１つ又は複数の動作は、プロセッサ、ストレージオペレーティングシステム、又はバイパスロジックによって実行されても良い。いくつかの実施形態において、バイパスロジックは、キャッシュロジックをストレージ装置のＩ／Ｏ応答時間の直接の測定に結びつけることを必要としない；それはキャッシュアルゴリズムの中で自己完結的である。
【００５５】
図７に示すように、アクセス推定動作７１０は、現在のレベルのＩ／Ｏ要求が与えられたキャッシュにアクセスするための期待応答時間を推定する。アクセス推定動作は、予め決定されたスケジュール通りに、及び／又は１つ又は複数のイベントの検出に応じて、継続的且つ周期的に実行可能である。バイパス推定動作７２０は、キャッシュをバイパスしてバッキングストアに直接的にアクセスするための期待応答時間を推定する。これらの値を推定するための技術は後述される。キャッシュにアクセスするための期待応答時間が、バッキングストアに直接的にアクセスするための期待応答時間よりも小さいかこれに等しい、と比較動作７３０が判別した場合、比較動作７３０は、キャッシュがアクセスされるキャッシュアクセス動作７５０に分岐する。キャッシュにアクセスするための期待応答時間が、バッキングストアに直接的にアクセスするための期待応答時間よりも大きい、と比較動作７３０が判別した場合、比較動作７３０は、キャッシュアクセスが必須であるかを判別する判別動作７６０に分岐する。
【００５６】
キャッシュアクセスはキャッシュの正しい動作に必須である場合があり、この場合それはキャッシュをバイパスしない。必須の動作の一例は、データが上書きされるときのキャッシュにおける既存のデータの無効化である。必須の動作のもう１つの例は、キャッシュがデータの現在のコピーのみを含むときのライトバックキャッシュからのデータの読み出しである。非必須の動作の一例は、データが書き込まれるときのキャッシュにおけるデータの挿入である。非必須の動作のもう１つの例は、データの現在のコピーがバッキングストレージに存在するときのライトバックキャッシュ又はライトスルーキャッシュのいずれかからのデータの読み出しである。キャッシュアクセスが必須ではない場合、判別動作７６０は、システムがキャッシュをバイパスしてバッキングストアに直接的にアクセスするバイパス動作７７０に分岐する。読み出し動作及び書き込み動作の両方に対して、キャッシュアクセスが必須である場合、判別動作７６０は、キャッシュがアクセスされるキャッシュアクセス動作７５０に分岐する。
【００５７】
種々の実施形態において、キャッシュストレージ及びバッキングストレージのための期待応答時間は、モデルへの入力としてキャッシュロジックによって行われる測定を用いる待ち行列理論に基づいたモデルを用いて、推定されてもよい。例えば、キャッシュロジックは、キャッシュ及びバッキングストアのための平均応答時間、並びに、現在及び平均の待ち行列長さの測定結果を維持してもよい。測定された平均応答時間ｔｒ及び測定された平均待ち行列長さＮが与えられると、我々はリトルの法則を使用して、平均サービス時間ｔｓを以下のように表す：
ｔｓ＝ｔｒ／Ｎ
【００５８】
期待される瞬間応答時間ｔｒｉはこの場合、単に、現在の瞬間待ち行列長さＮｉと平均サービス時間ｔｓとの積である：
ｔｒｉ＝Ｎｉｔｓ
【００５９】
キャッシュロジックはこれらの期待応答時間を計算して、動作がキャッシュにとって非必須であり且つバッキングストアに対する期待応答時間がキャッシュストレージの期待応答時間よりも小さい場合に、キャッシュをバイパスするようにＩ／Ｏに命令してもよい。
【００６０】
いくつかの実施形態において、期待応答時間は、完全な統計量よりもむしろ、キャッシュストレージ及び／又はバッキングストレージに対する応答時間のサンプリングの測定と共にモデルを用いて、推定されてもよい。例えば、キャッシュストア上の全ての動作を測定することよりもむしろ、キャッシュロジックは、書き込み動作のみを測定してもよい。これにより、動作の一部のみが性能測定コードのオーバーヘッドコストを招くために、バイパスアルゴリズムのＣＰＵオーバーヘッドコストが低減される。
【００６１】
他の実施形態において、期待応答時間は、定量的に推定されるよりもむしろ、モデルとキャッシュストレージ及び／又はバッキングストレージに対する応答時間のサンプリングの測定値とを用いて、定性的に推定されてもよい。動作のサンプリングされるサブセットの現在の瞬間待ち行列長さが大きいとき（すなわち、多くの未処理のサンプリングされた動作があるとき）、期待応答時間は大きい。キャッシュストレージの期待応答時間が大きく、且つ、バッキングストアの期待応答時間が小さいとき、キャッシュロジックは、動作がキャッシュにとって非必須である場合に、キャッシュをバイパスするようにＩ／Ｏに命令してもよい。
【００６２】
キャッシュストレージに対する期待応答時間は、上述の複数の方法のうちの１つを用いて推定されてもよいが、バッキングストレージに対する期待応答時間は、代表的なＩ／Ｏワークロードを用いて実験室において行われた性能測定に基づいている定数として推定されてもよい。
【００６３】
キャッシュヒット比率に対するキャッシュバイパスの影響は、どの種類の非必須の動作をバイパスさせるかを優先的に選択することによって、加減されてもよい。キャッシュストレージの期待応答時間がバッキングストアの期待応答時間に近づくと、バイパスロジックはまず、新たに書き込まれるデータのキャッシュへの挿入などの比較的に望ましくない動作をバイパスさせることを選択するが、キャッシュからのリードヒットを提供するなどのより望ましい動作をバイパスさせない。キャッシュストレージの期待応答時間がバッキングストアの期待応答時間を超えるとき、バイパスロジックは、全ての非必須の動作をバイパスさせて、キャッシュの正しい動作のために必須である動作のみは残す。
【００６４】
種々の実施形態において、キャッシュは、循環ログに付加しながら、キャッシュストレージ装置への全ての書き込みを管理する。それは、充填され次いでキャッシュストレージ装置上のログに同期的に書き込まれるべき空きバッファの固定サイズのプールを維持する。キャッシュストレージ装置にて進行中の書き込み動作の数は、プールのサイズからプールにおける空きバッファの現在の数を減算することによって推定可能であり、また上述のように、キャッシュストレージに対する応答時間を定性的に推定するために使用可能である。空きバッファの数が、（モデリングを介して又は実験的な測定を経て試行錯誤的に決定された）ある閾値よりも小さくなると、キャッシュロジックは、キャッシュにおける新たに書き込まれたデータの挿入と、キャッシュ読み出し失敗からのデータの挿入とをバイパスさせることを開始する。新たに書き込まれるデータが既にキャッシュにあるデータを上書きする場合、それはなお無効化に入る必要がある。空きバッファの数がより小さな第２の閾値よりも小さくなるとき、キャッシュがデータの最新のコピーのみを含まない限りは、キャッシュにおける新たに書き込まれるデータの挿入とキャッシュ読み出し失敗からのデータの挿入をバイパスすることを継続することに加えて、キャッシュロジックはキャッシュにおいてヒットする読み出し動作をバイパスすることを開始する。これらの実施形態の１つの利点は、それらが各Ｉ／Ｏ上の応答時間統計を集めることのオーバーヘッドを必要としないことであり、キャッシュ書き込みロギングコードに対してローカルなデータ構造のみにアクセスすることのソフトウェア構造的な利点があり、従って、キャッシュストレージとバッキングストレージとに対するデバイスドライバなどの、キャッシュソフトウェアモジュールと他の外部モジュールとの間を接続することを回避することができる。
【００６５】
本明細書において紹介される技術は、特定目的ハードウェア（例えば回路）として、若しくはソフトウェア及び／又はファームウェアを用いて適切にプログラムされたプログラム可能回路として、又は特定目的及びプログラム可能回路の組み合わせとして、具現化可能である。ここで、実施形態は、そこに命令が格納されている機械読み出し可能な媒体を含んでもよく、この命令はコンピュータ（又は他の電子装置）をプログラムして処理を実行するために使用されることができる。機械読み出し可能な媒体は、フロッピー（登録商標）ディスク、光ディスク、コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、及び光磁気ディスク、ＲＯＭ、ランダムアクセスメモリ（ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ＥＰＲＯＭ）、電子的消去可能プログラム可能読み出し専用メモリ（ＥＥＰＲＯＭ）、磁気カード又は光カード、フラッシュメモリ、又は電子的命令を格納することに適合する他の種類のメディア／機械読み出し可能な媒体を備えてもよいが、これらに限定されない。
【００６６】
本明細書において、「いくつかの実施形態において」、「種々の実施形態によれば」、「示される実施形態において」、「他の実施形態において」などの語句は一般的に、当該語句の後に続く特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味し、また本発明の１つより多くの実施形態に含まれてもよいことを意味する。また、そのような語句は必ずしも同一の実施形態を全て参照するものではない。
【００６７】
本発明の１つ又は複数の実施形態の詳細な説明が上に与えられたが、種々の置換、変更、及び均等は、本発明の精神から逸脱することなく、当業者に明白である。例えば、上述の実施形態は特定の特徴について言及しているが、本発明の範囲はまた、複数の特徴の異なる組み合わせを有する実施形態と、説明された特徴の全て有するとは限らない実施形態を含む。従って、本発明の範囲は、特許請求の範囲に入るあらゆる置換、変更、及び変形、並びにそれらの全ての均等を包含することが意図されている。従って、明細書の記載は本発明の範囲を限定するものとして理解されるべきではなく、本発明の範囲は添付の特許請求の範囲によって定義される。
【図１】
2015518987.tif 000003
【図２】
2015518987.tif 000004
【図３】
2015518987.tif 000005
【図４】
2015518987.tif 000006
【図５】
2015518987.tif 000007
【図６】
2015518987.tif 000008
【図７】
2015518987.tif 000009
【国際調査報告】
2015518987.tif 000010
2015518987.tif 000011