(57)【特許請求の範囲】
【請求項１】
ソリッドステート記憶媒体を備えるソリッドステート記憶デバイス上でデータをキャッシングする方法であって、
ソリッドステート記憶デバイスを管理するように構成された記憶コントローラが、前記ソリッドステート記憶デバイスにメタデータを維持することを含み、前記メタデータは前記ソリッドステート記憶媒体の複数の記憶ユニットに関連し、且つ、前記記憶コントローラがアクセス可能なメモリ内に維持されるインデックスを有し、
前記メタデータを維持することは、
ａ）前記ソリッドステート記憶媒体上に記憶されたデータの複数の論理識別子を前記ソリッドステート記憶媒体の前記複数の記憶ユニットの各物理アドレスにマッピングすること、及び
ｂ）前記ソリッドステート記憶媒体上にキャッシュされた補助記憶装置のデータの複数の論理識別子を前記ソリッドステート記憶媒体の複数の記憶ユニットの各物理アドレスにマッピングすること、を含み、
前記方法は、
前記メタデータにアクセスして、前記ソリッドステート記憶媒体上にキャッシュされた前記補助記憶装置の前記データを管理することをさらに含む、方法。
【請求項２】
前記インデックスは、複数の論理識別子によりインデックス付けされたツリーデータ構造を有する、請求項１に記載の方法。
【請求項３】
記憶ユニットに関連する前記メタデータを維持することは、前記ソリッドステート記憶媒体の関連する記憶ユニットのデータが前記補助記憶装置上に記憶されている場合に該データが破棄可能であることを示す破棄可能性インジケータを維持することを含み、
前記方法は、
前記記憶コントローラが、データ復旧対象の記憶区分を選択するために前記破棄可能性インジケータを使用すること、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記方法は、前記記憶コントローラが、
破棄不可能なデータを含む前記ソリッドステート記憶媒体の第１の記憶ユニットを識別することと、
前記記憶ユニットの前記破棄不可能なデータを、前記ソリッドステート記憶媒体の第２の記憶区分上に記憶させることと、を含み、
前記第１の記憶ユニットは、破棄不可能なデータが、前記データは破棄可能であると示している破棄可能性インジケータを含まない前記第１の記憶ユニットに関連する前記メタデータであると認識される、請求項３に記載の方法。
【請求項５】
選択された記憶ユニットに関連する前記メタデータを維持することは、前記記憶コントローラが、前記ソリッドステート記憶媒体上に前記関連する記憶ユニットのデータが保持されるべきことを示すキャッシュ排除メタデータを維持することを含み、前記キャッシュ排除メタデータはデータアクセスパターンに基づいて維持され、
前記方法は、
前記記憶ユニットに関連する前記キャッシュ排除メタデータに基づいてデータ復旧対象の記憶ユニットを選択することをさらに含む、請求項１に記載の方法。
【請求項６】
記憶ユニットに関連する前記メタデータを維持することは、
前記記憶コントローラによって、前記関連する記憶ユニットのデータが前記補助記憶装置上に記憶されている場合に該データが破棄可能であることを示す破棄可能性インジケータを維持することと、
前記記憶コントローラによって、前記関連する記憶ユニットのデータが前記ソリッドステート記憶デバイス上に保持されるべきことを示すキャッシュ排除メタデータを維持することを含み、前記キャッシュ排除メタデータはデータアクセスパターンに基づいて維持され、
前記方法は、前記記憶コントローラが、
破棄可能なデータを含む第１の記憶ユニットを、破棄可能性インジケータに基づいて識別することと、
前記ソリッドステート記憶媒体上に保持されるべき破棄可能なデータを、前記第１の記憶ユニットに関連付けられたキャッシュ排除メタデータに基づいて識別することと、
前記識別された破棄可能なデータを、ソリッドステート記憶媒体の第２の記憶ユニット上に記憶させることと、
をさらに含む、請求項１に記載の方法。
【請求項７】
記憶ユニットに関連する前記メタデータを維持することは、前記記憶コントローラがキャッシュ管理に用いる複数のキャッシュ属性を維持することを含み、前記方法は、前記記憶コントローラが、
１又はそれ以上の記憶ユニットに関連する前記キャッシュ属性にアクセスすることと、
前記アクセスされたキャッシュ属性を使用して、データ復旧対象の記憶ユニットを選択することと、
をさらに含む、請求項１に記載の方法。
【請求項８】
記憶ユニットに関連する前記メタデータを維持することは、前記記憶コントローラが、
前記関連する記憶ユニットのデータが前記補助記憶装置上に記憶されている場合に該データが破棄可能であることを示す破棄可能性インジケータを維持することと、
前記関連する記憶ユニットの前記データが最新である場合に該データが有効であることを示す有効性インジケータを維持することと、をさらに含み、
前記方法は、前記記憶コントローラが、
前記ソリッドステート記憶媒体の第１の記憶区分の記憶ユニットに保持されたデータの論理アドレスを含む記憶要求を受け取ることと、
前記ソリッドステート記憶媒体の第２の記憶区分の記憶ユニット内に、前記記憶要求のデータを記憶することと、
前記インデックスを更新することによって前記データの論理識別子を前記第２の記憶区分内の前記記憶ユニットにマッピングし、前記第１の記憶区分内の前記記憶ユニットの前記データが無効であることを示すように前記有効性インジケータを更新し、前記記憶ユニットの前記データが破棄不可能であることを示すように、前記第２の記憶区分内の前記記憶ユニットに関連付けられた破棄可能性インジケータを更新することによって、前記メタデータを更新することと、
をさらに含む、請求項１に記載の方法。
【請求項９】
前記ソリッドステート記憶デバイスは、前記補助記憶装置に通信可能に結合され、バックアップエンジンを備えており、前記メタデータは、前記ソリッドステート記憶デバイスの現在の容量占有量を示す情報を含み、前記方法は、前記記憶コントローラが、
前記補助記憶装置の容量以上の容量を有する論理アドレス空間をクライアントコンピューティングデバイスに提供することと、
前記ソリッドステート記憶媒体の複数の前記記憶ユニットに関連する前記メタデータに基づいて、前記ソリッドステート記憶デバイスの現在の容量占有量を判定することと、
前記現在の容量占有量が目標の占有量閾値を上回る場合に記憶ユニットの破棄不可能なデータを前記補助記憶装置上に記憶させるように構成された処理であって、前記バックアップエンジンが実行する処理の優先度を高めることと、
をさらに含む、請求項４に記載の方法。
【請求項１０】
前記方法は、前記記憶コントローラが、
前記補助記憶装置の論理アドレス空間の容量よりも大きい容量を有する論理アドレス空間を提供することと、
前記補助記憶装置の前記論理アドレス空間から外れる論理識別子と関連付けられる記憶要求を識別することと、
前記論理識別子と関連付けられる前記記憶ユニットのデータが破棄不可能であることを示すように破棄可能性インジケータを維持すること、
をさらに含む、請求項３に記載の方法。
【請求項１１】
前記方法は、前記記憶コントローラが、
前記メタデータの前記インデックス内に含まれる第１の論理識別子と、前記メタデータの前記インデックス内に含まれない第２の論理識別子とを参照する記憶要求を受け取ることと、
前記インデックス内の前記第１の論理識別子にマッピングされた記憶ユニットに記憶されたデータと、前記補助記憶装置の記憶位置から読み込まれ前記第２の論理アドレスに対応するデータとを返すことにより、前記要求に対応することと、
をさらに含む、請求項１に記載の方法。
【請求項１２】
前記記憶要求のデータの論理アドレス範囲が不連続である、請求項１１に記載の方法。
【請求項１３】
複数の記憶区分を含むソリッドステート記憶デバイス上でデータをキャッシングするための方法であって、前記ソリッドステート記憶デバイスを管理するように構成された記憶コントローラが、前記記憶コントローラがアクセス可能なメモリ上に記憶されるインデックスであって、ａ）前記ソリッドステート記憶デバイス上に記憶されたデータの論理識別子を前記ソリッドステート記憶デバイスの物理アドレスに対応する各記憶位置にマップするように構成され、ｂ）前記ソリッドステート記憶デバイス上にキャッシュされた補助記憶装置のデータに対応する複数の論理識別子を前記ソリッドステート記憶デバイスの物理アドレスに対応する各記憶位置にマップするように構成された前記インデックスを用いて、論理アドレス空間を維持することと、
前記ソリッドステート記憶デバイスの各記憶区分上に前記補助記憶装置のデータを記憶することと、
メタデータにアクセスして前記ソリッドステート記憶デバイスの最大記憶容量よりも少ないキャッシュ占有量閾値を決定することと、を含み、
前記メタデータは、前記記憶コントローラによって維持され、前記ソリッドステート記憶デバイスの現在の容量占有量を示す情報を含む、方法。
【請求項１４】
前記メタデータは、データアクセスパターンに基づいて前記メタデータに関連するデータが前記ソリッドステート記憶デバイス上に保持されるべきことを示すキャッシュ排除メタデータを含み、前記方法は、前記記憶コントローラが、
前記ソリッドステート記憶デバイス上に記憶された前記補助記憶装置のデータに関連するキャッシュ排除メタデータを維持することと、
前記キャッシュ排除メタデータにアクセスして、データ復旧のために選択された記憶区分の記憶ユニットであってキャッシュから排除可能なキャッシュデータを含む前記記憶ユニットを識別することにより、記憶復旧操作を管理することと、
をさらに含む、請求項１３に記載の方法。
【請求項１５】
前記メタデータは、前記メタデータに関連するデータが前記補助記憶装置上に記憶されている場合に該データが破棄可能であることを示す破棄可能性インジケータをさらに含み、前記方法は、前記破棄可能性インジケータに基づいて、データ復旧対象の記憶区分を選択することをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記メタデータは、前記ソリッドステート記憶デバイスの記憶ユニットのデータが前記補助記憶装置上に記憶されている場合に該データが破棄可能であることを示す破棄可能性インジケータをさらに含み、前記方法は、前記記憶コントローラが、
前記メタデータを使用して、復旧のために選択される記憶区分内で、前記ソリッドステート記憶デバイス上に保持するキャッシュエントリと関連付けられる記憶ユニットの破棄可能なデータを識別することと、
前記識別された記憶ユニットの破棄可能なデータを、前記ソリッドステート記憶デバイスの異なる記憶区分上に記憶させることと、
をさらに含む、請求項１４に記載の方法。
【請求項１７】
ソリッドステート記憶デバイス上でデータをキャッシングするための方法であって、
ソリッドステート記憶媒体を備えるソリッドステート記憶デバイスを管理するように構成された記憶コントローラが、前記記憶コントローラがアクセス可能なメモリ上に記憶されるインデックスであって、ａ）前記ソリッドステート記憶デバイス上に記憶されたデータの論理識別子を前記ソリッドステート記憶媒体の物理アドレスに対応する各記憶位置にマップするように構成され、ｂ）前記ソリッドステート記憶媒体上にキャッシュされた補助記憶装置のデータに対応する複数の識別子を前記ソリッドステート記憶媒体の物理アドレスに対応する各記憶位置にマップするように構成された前記インデックスを提供する、前記ソリッドステート記憶媒体の前記記憶ユニット上にキャッシュされた前記補助記憶装置のデータを示すキャッシュエントリを用いて、論理アドレス空間を維持することと、
１つ以上の逐次的な記憶操作において、データをソリッドステート記憶媒体上に記憶することと、
前記ソリッドステート記憶媒体の記憶ユニットの磨耗率及び信頼性のうち少なくとも一方を示す情報を含むメタデータを維持することと、
前記メタデータにアクセスして、前記メタデータにより示される前記記憶ユニットの前記磨耗率及び前記信頼性のうち少なくとも一方に基づいて、前記キャッシュエントリを管理することと、
を含む、方法。
【請求項１８】
前記記憶コントローラが、大量の摩耗を有する前記キャッシュエントリのデータを含む記憶ユニット、小量の摩耗を有する記憶ユニット、および信頼できない記憶ユニットのデータのうちの１つを示す前記メタデータに基づいて、排除対象のキャッシュエントリを選択することをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記記憶コントローラが、大量の摩耗を有する記憶区分、少量の摩耗を有する記憶区分、および信頼できない記憶区分のうちの１つを示す前記メタデータに基づいて、前記ソリッドステート記憶媒体の第１の記憶ユニット上に記憶されるキャッシュエントリのデータを、前記ソリッドステート記憶媒体の第２の記憶ユニット上に記憶させることをさらに含む、請求項１７に記載の方法。
【請求項２０】
前記記憶コントローラが、大量の摩耗を有する記憶区分、少量の摩耗を有する記憶区分、および信頼できない記憶区分のうちの１つを示す前記メタデータに基づいて、ソリッドステート記憶デバイス上に記憶される記憶ユニットのデータを、前記補助記憶装置上に記憶させることをさらに含む、請求項１７に記載の方法。
【請求項２１】
持続性機械可読媒体上に記憶される命令を含むコンピュータプログラムであって、前記命令は、ソリッドステート記憶デバイス上でデータをキャッシングするための方法を機械に行わせるように構成され、前記方法は、
ソリッドステート記憶媒体を備えるソリッドステート記憶デバイスによりアクセス可能なメモリ内に、前記ソリッドステート記憶媒体の記憶ユニットの磨耗率及び信頼性のうち少なくとも一方を示す情報を含むメタデータを維持することと、
前記メタデータにアクセスして、前記ソリッドステート記憶デバイスの記憶操作であって前記メタデータを使用して復旧対象の前記ソリッドステート記憶媒体の記憶区分を選択する前記記憶操作を管理することと、
前記ソリッドステート記憶デバイス上に記憶されるキャッシュを管理するために前記メタデータにアクセスすることと、を含み、
前記キャッシュを管理することは、前記記憶区分の磨耗率及び信頼性のうち少なくとも一方に関連する前記メタデータを使用して、前記ソリッドステート記憶媒体の記憶ユニットを選択して補助記憶装置へバックアップすることを含む、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソリッドステート記憶デバイス上でデータをキャッシングすることに関し、具体的には、キャッシュを管理し、グルーミング操作を行う用途のためにキャッシュおよびソリッドステート記憶デバイスに関するメタデータを維持することに関する。
【背景技術】
【０００２】
キャッシュデバイスは、システム内においてデータがより迅速にアクセスされることを可能にするために使用される記憶デバイスである。キャッシュは、キャッシュ内のデータを使用する操作のための入力／出力（Ｉ／Ｏ）時間を縮小することにより、システム内の性能を著しく改善することができる。一般的に、キャッシュは、キャッシュデバイスより大きな記憶容量を有するがキャッシュデバイスよりＩ／Ｏ時間が遅い別の記憶デバイスの前に実装される。キャッシュの利点はよく理解されており、キャッシュは、ＣＰＵ内のキャッシュからストレージエリアネットワーク（ＳＡＮ）内のキャッシュに及ぶ、様々なコンテキストおよび規模で有利に実装されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願公開第１１／９５２，１０１号明細書
【特許文献２】米国特許出願公開第１１／９５２，０９１号明細書
【特許文献３】米国特許出願公開第１１／９５２，１１５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
キャッシュの性質もまた、コンテキストに基づき変化し得、例えば、単一コンピュータ（デスクトップまたはラップトップ等）において、キャッシュは、スタティックランダムアクセスメモリ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、または他のもの等の揮発性メモリ内に実装することができる。現在、キャッシュグルーミングは、他のメモリ管理操作から独立しているため、効率的ではない。
【課題を解決するための手段】
【０００５】
ソリッドステート記憶デバイスは、不揮発性補助記憶装置のための不揮発性キャッシュデバイスとして作動することができる。このソリッドステート記憶デバイスは、ソリッドステート記憶デバイスにより提示される論理空間を使用し、クライアントに対して透過的であり得る。いくつかの実施形態において、このソリッドステート記憶デバイスは、ソリッドステート記憶デバイスの物理的記憶サイズに関わらず、ソリッドステート記憶デバイスが補助記憶装置と同一のサイズである論理記憶空間をクライアントへ提示するように、補助記憶装置の物理的サイズと同一である論理的サイズをクライアントへ提示するように構成することができる。代替として、またはさらに、このソリッドステート記憶デバイスは、ソリッドステート記憶デバイスおよび補助記憶装置の両方の物理記憶容量を上回る論理アドレス空間をクライアントへ提示することができる。
【０００６】
ソリッドステート記憶デバイスは、ソリッドステート記憶デバイス上で行われるキャッシュ操作および記憶操作に関するメタデータを維持することができる。記憶メタデータは、ソリッドステート記憶デバイス上で行われる逐次的な記憶操作に関するメタデータ（例えば、デバイス上のクライアント論理アドレスと記憶ユニットとの間の関連性、記憶ログメタデータ等）、逐次的な記憶操作に関連する保全操作（例えば、記憶装置復旧、ガーベジコレクション、エラー訂正等）、記憶媒体の状態（例えば、磨耗率、信頼性、整合性等）等を含んでもよいが、それらに限定されない。記憶メタデータは、無効データを含む記憶ユニットと、有効データを含む記憶ユニットからとを区別するための有効性インジケータを含むことができる。記憶ユニットとは、ソリッドステート記憶デバイス上のあらゆるアドレス可能な記憶位置を指すことができる。
【０００７】
ソリッドステート記憶デバイスは、ソリッドステート記憶デバイスの記憶ユニット内のデータをキャッシュすることができる。キャッシュメタデータは、ソリッドステート記憶デバイス上に記憶されるキャッシュ、ソリッドステート記憶デバイス上で行われるキャッシュ操作（例えば、アクセスパターン等）、キャッシュ管理（例えば、キャッシュ排除および／またはキャッシュ保持ポリシー、キャッシュ属性、キャッシュ指令等）等に関するメタデータを含んでもよい。キャッシュメタデータは、破棄することができるデータを識別するための破棄可能性インジケータを含んでもよい。破棄可能なデータは、補助記憶装置上にバックアップされた（例えば、記憶された）キャッシュデータであり得る。
【０００８】
ソリッドステート記憶デバイスにより維持されるメタデータは、デバイス上にキャッシュされるデータ（例えば、ソリッドステート記憶デバイスの記憶ユニット内にキャッシュされるデータ）を表すことができる、キャッシュエントリを含むことができる。キャッシュエントリは、データがソリッドステート記憶デバイス上のどこに記憶されたかを識別する上で、（記憶クライアントの）論理アドレスと１つ以上の記憶位置（例えば、記憶ユニット）を関連付けることができ、キャッシュエントリは、クライアント論理アドレスおよびソリッドステート記憶デバイス記憶位置（例えば、記憶ユニット）間のインデックスまたはマッピングを提供することができる。いくつかの実施形態において、キャッシュエントリは、可変サイズを有することができ、したがってソリッドステート記憶デバイス上の記憶ユニットの一部、単一記憶ユニット、および／または多重記憶ユニットを参照することができる。例えば、第１のキャッシュエントリは、単一記憶ユニット上の第１のデータ量（例えば、単一記憶ユニットの一部上の２５６バイト）を含み得るのに対し、第２のキャッシュエントリは、多重記憶ユニット上の異なる第２のデータ量（例えば、複数の記憶ユニットまたは仮想記憶ユニット上の４キロバイト）を含み得る。
【０００９】
キャッシュエントリは、クライアント記憶要求に応答して高速かつ効率的にキャッシュエントリへアクセスすることを可能にすることができる論理アドレスによりインデックス付けされてもよい。キャッシュエントリは、ソリッドステート記憶デバイスの逐次的な記憶操作に、ならびにキャッシュに関するメタデータを含む、共有メタデータを記憶（および／または参照）するために使用することができる。例えば、ソリッドステート記憶デバイスのグルーマー（以下に記載される）は、記憶装置復旧および／または保全操作を効果的に行うためにキャッシュに関するメタデータにアクセスすることができる。同様に、ソリッドステート記憶デバイス上および／またはそれと併せて作動するキャッシュマネージャ（以下に記載される）は、キャッシュを効果的に管理するためにメタデータにアクセスすることができる（例えば、キャッシュ排除および／または保持に関連するキャッシュポリシーを決定する等）。いくつかの実施形態において、ソリッドステート記憶デバイスは、記憶クライアントにメタデータの一部を現し得る記憶インターフェース（または一般的に「インターフェース」）を提供することができる。このインターフェースを使用して、記憶クライアントは、ソリッドステート記憶デバイスを設定することができる（例えば、キャッシュ属性を設定する、キャッシュ指令、トリム（ＴＲＩＭ）コマンドを発行する等）。さらに、このインターフェースは、冗長アドレス変換層（例えば、フル６４ビットアドレス空間内で）なしに、記憶クライアントがソリッドステート記憶デバイスと情報をやり取りすることを可能にするインターフェースを通して、「まばらな」または「細く供給された」論理アドレス空間を現すことができる。
【００１０】
いくつかの実施形態において、バックアップエンジンは、ソリッドステート記憶デバイス上にキャッシュされるデータを補助記憶装置へバックアップするように構成することができる。補助記憶装置上に記憶される場合、データと関連付けられる（例えば、キャッシュエントリおよび／または対応する記憶ユニットと関連付けられる）メタデータは、データが破棄可能であることを示すように更新されてもよい。バックアップエンジンは、ソリッドステート記憶デバイスの記憶ユニットを通して年代順に（最古から最新へ）繰り返し適用することができる。この走査は、ソリッドステート記憶デバイスにより維持される共有メタデータによって有効にすることができる（例えば、記憶ユニットの逆インデックスおよび／またはシーケンスインジケータ）。バックアップエンジンの動作は記憶メタデータによって情報を得ることができる、例えば、バックアップエンジンは、メタデータが無効であることを示す（例えば、データが、復旧操作、逐次書き込み、修正等に起因して異なる記憶位置へ移動された）キャッシュエントリ（および／または関連付けられた記憶ユニット）と関連付けられるデータを無視することができる。
【００１１】
いくつかの実施形態において、バックアップエンジンは、比較的に低い優先度で作動する（例えば、バックグラウンドプロセスまたは操作として）。バックアップエンジンは、必要に応じて、より高い優先度で作動するように設定されてもよい。例えば、メタデータは、ソリッドステート記憶デバイスの物理記憶容量、対象の占有量、最大占有量、および／または現在の占有量を示すことができる。現在の占有量が閾値を上回る（例えば、対象の占有量、最大占有量、または他の何らかの閾値を上回る）と、バックグラウンドエンジンは、より高い優先度で作動するように設定することができる。
【００１２】
記憶装置復旧および保全操作は、メタデータによって同様に情報を得ることができる。例えば、ソリッドステート記憶デバイスの記憶区分を復旧するように構成されるグルーマープロセスは、メタデータを使用して優先順位を付けることができる（例えば、現在の占有量が閾値を上回る場合、優先度を高める）。グルーマーは、キャッシュに関するメタデータにそのデータ復旧操作を行うときであってもアクセスしてもよい。例えば、このグルーマーは、メタデータに基づく復旧のための記憶区分を選択することができ、メタデータ等を使用して保持する（例えば、異なる記憶区分へ移動する）ために記憶区分内の記憶ユニットを選択することができる。
【００１３】
したがって、いくつかの実施形態において、ソリッドステート記憶デバイス上のデータをキャッシュするための方法は、ソリッドステート記憶デバイス上で行われるキャッシュ操作およびソリッドステート記憶デバイスの記憶操作に関するメタデータを維持すること、ソリッドステート記憶デバイスの記憶操作を管理するためにメタデータにアクセスすること、ならびにソリッドステート記憶デバイス上に記憶されるキャッシュを管理するためにメタデータにアクセスすることを含むことができる。キャッシュ操作に関するメタデータおよび記憶操作に関するメタデータは、共有データ構造内に記憶することができる。
【００１４】
メタデータは、補助記憶装置上に記憶されている記憶ユニットを識別する破棄可能性インジケータを含んでもよく、このインジケータは、復旧のための記憶区分を選択するために使用することができる。キャッシュ排除メタデータ（例えば、コールド、ホット、ウォーム等）は、復旧のための記憶区分を選択するため、および／または復旧のために選択された記憶区分内の記憶ユニットが保持されるべきであるかどうかを判定するために使用することができる。メタデータは、キャッシュエントリの論理アドレスと関連付けられてもよく、したがってデータに対応する記憶位置がソリッドステート記憶デバイス上で変化する時、キャッシュエントリと関連付けられたままであることができる。
【００１５】
キャッシュに関するメタデータ（例えば、共有キャッシュメタデータ）は、記憶区分の復旧、ガーベジコレクション、エラー管理、逐次的な記憶（例えば、ログベースの記憶操作）等のような、ソリッドステート記憶デバイスの逐次的な記憶操作を管理するために使用することができる。逐次的な記憶操作に関するメタデータ（例えば、共有記憶メタデータ）は、キャッシュを管理するために使用することができる。例えば、バックアップ、キャッシュ排除、占有量、キャッシュデータ移動等のようなキャッシュ操作は、共有される記憶メタデータによって情報を得ることができる。
【００１６】
メタデータは、複数のキャッシュエントリを含んでもよく、それぞれは、論理アドレスをキャッシュエントリのデータを含むソリッドステート記憶デバイス上の記憶ユニットと関連付ける。クライアント記憶要求は、キャッシュエントリを使用して対応することができる。特定の論理アドレスに対するキャッシュエントリがメタデータ内に存在する場合、対応するデータは、ソリッドステート記憶デバイス上で利用可能であり得、そうでなければ、データは利用不可であり得る（そしてキャッシュミスが起こる可能性がある）。クライアント記憶要求は、キャッシュエントリが論理アドレスにより（例えば、Ｂツリーデータ構造内において）インデックス付けされているため、迅速かつ効果的に対応することができる。メタデータは、ソリッドステート記憶デバイスの現在の占有量を判定するために使用されることができる。クライアントエントリは、キャッシュおよび／または記憶操作に応じて修正されてもよい。近似の論理アドレスが記憶される場合、対応するキャッシュエントリは、マージされ得、特定の論理アドレスを見つけるために検索されなければならないエントリ数を減らすることができる。同様に、論理アドレスが除去される場合、対応するキャッシュエントリは、分割してもよい（またはしなくてもよい）。キャッシュエントリは、可変サイズのものであってもよく、したがって、単一論理アドレス、論理アドレスの範囲、１組の論理アドレス等を含んでもよい。
【００１７】
本明細書を通じた特徴、利点、または類似する表現への参照は、本発明で実現することができる特徴および利点の全てが本発明のいかなる単一の実施形態内にあるべきまたはあることも暗示することはない。そうではなく、特徴および利点に言及する表現は、１つの実施形態に関して記載される特定の特徴、利点、または特質は本発明の少なくともいくつかの実施形態において含まれることを意味すると理解される。したがって、特徴および利点ならびに同様の表現の考察は、本明細書を通して、必須ではないが、同一の実施形態に言及し得る。
【００１８】
さらに、記載される本発明の特徴、利点、および特質は、任意の好適な方法で、１つ以上の実施形態に組み込まれてもよい。当業者は、本発明を特定の実施形態の１つ以上の特定の特徴または利点なしに実施することができることを認識するであろう。他の事例において、本発明のすべての実施形態において提示されない可能性がある追加の特徴および利点が、いくつかの実施形態において、認識され得る。
【００１９】
本発明のこれらの特徴および利点は、続く説明および付属の請求項からより十分に明白となり、または以下に定める本発明の実施により知ることができ得る。
【００２０】
本発明の利点が容易に理解されるように、上で簡潔に記載した本発明のより具体的な説明が、添付の図面に図示される具体的な実施形態を参照することにより提供される。これらの図面が本発明の典型的な実施形態のみを描写し、したがってその範囲を限定すると見なされるべきではないことを理解した上で、本発明は、添付の図面の使用を通じてさらに具体的かつに記載および説明される。
【図面の簡単な説明】
【００２１】
【図１】データをキャッシュするように構成されるシステムであるソリッドステート記憶デバイスの例示的実施形態を図示する略ブロック図である。
【図２】補助記憶装置により提供される物理空間と同一のサイズである論理記憶空間を提示するソリッドステート記憶デバイスを含むシステムの例示的実施形態を図示する略ブロック図である。
【図３】キャッシュ管理装置の実施形態を図示する略ブロック図である。
【図４】ファイルシステムと、キャッシュとして機能しているソリッドステート記憶デバイスと、および補助記憶装置として機能しているハードディスクドライブとの間の書き込み中における相互作用の例示的実施形態を図示する略ブロック図である。
【図５】ファイルシステムと、キャッシュとして機能しているソリッドステート記憶デバイスと、および補助記憶装置として機能しているハードディスクドライブとの間の読み込み中における相互作用の例示的実施形態を図示する略ブロック図である。
【図６】ソリッドステート記憶デバイスを構成するための方法の別の実施形態を図示する概略フローチャート図である。
【図７】ソリッドステート記憶デバイスにおける読み込みを処理するための方法の例示的実施形態を図示する概略フローチャート図である。
【図８】ソリッドステート記憶デバイスにおける書き込みを処理するための方法の例示的実施形態を図示する概略フローチャート図である。
【図９Ａ】ソリッドステート記憶デバイス内のユニット上で作動しているバックアップエンジンの例示的実施形態を図示している略ブロック図である。
【図９Ｂ】ソリッドステート記憶デバイス内のユニット上で作動しているバックアップエンジンの例示的実施形態を図示している略ブロック図である。
【図１０】ソリッドステート記憶デバイス内のユニットをグルーミングするための方法における例示的実施形態を図示する概略フローチャート図である。
【図１１】共有メタデータを維持するための例示的データ構造の略ブロック図である。
【図１２】ソリッドステート記憶デバイス上のデータをキャッシュするための方法の一実施形態のフロー図である。
【図１３】ソリッドステート記憶デバイス上のデータをキャッシュするための方法の別の実施形態のフロー図である。
【図１４】ソリッドステート記憶デバイス上のデータをキャッシュするための方法の別の実施形態のフロー図である。
【図１５】ソリッドステート記憶デバイス上のデータをキャッシュするための方法の別の実施形態のフロー図である。
【図１６】ソリッドステート記憶デバイス上のデータをキャッシュするための方法の別の実施形態のフロー図である。
【発明を実施するための形態】
【００２２】
本明細書内に記載される機能ユニットの多くは、それらの実装独立性をより詳細に強調する目的でモジュールと呼ばれている。例えば、モジュールは、カスタムＶＬＳＩ回路もしくはゲートアレイ、または論理チップのような既製の半導体、トランジスタ、もしくは他の離散的構成要素を含むハードウェア回路として実装することができる。モジュールはまた、フィールドプログラマブルゲートアレイ、プログラム可能アレイ論理、プログラム可能論理回路等のようなプログラム可能なハードウェアデバイス内に実装されてもよい。
【００２３】
モジュールはまた、様々な種類のプロセッサによる実行のためのソフトフェア内に実装されてもよい。例えば、実行コードの特定されるモジュールは、例えばオブジェクト、手続き、または関数として編成することができるコンピュータ命令の１つ以上の物理または論理ブロックを含む。それにもかかわらず、特定されたモジュールの実行ファイルは、物理的にともに位置する必要はなく、論理的にともに結び付けられる場合、モジュールを含みモジュールのために定められた目的を達成する、異なる位置において記憶される全く異なる命令を含むことができる。
【００２４】
実際に、実行コードのモジュールは、単一命令または多くの命令であってもよく、ならびに数個の異なるコードセグメント、異なるプログラムの間、および数個ににわたるメモリデバイスに至るところに分散される可能性さえある。同様に、操作可能なデータは、モジュール内において本明細書に特定および図示することができ、あらゆる好適な形態において具現化することができ、あらゆる好適な種類のデータ構造内において編成することができる。操作可能なデータは、単一データセットとして収集されてもよく、または異なる記憶デバイスにわたることを含む異なる位置にわたって分散することができ、少なくとも部分的に、ただ単にシステムまたはネットワーク上の電子信号として存在することができる。モジュールまたはモジュールの一部がソフトフェア内に実装される場合、ソフトフェア部は、１つ以上のコンピュータ可読媒体上に記憶される。
【００２５】
本明細書を通じた「一実施形態」、「実施形態」、または類似する表現への言及は、実施形態に関連して記載される特定の特徴、構造、または特質が、本発明の少なくとも一実施形態に含まれることを意味する。したがって、本明細書を通して、「一実施形態において」、「実施形態において」、および類似する表現の出現は、必須ではないが、全て、同一の実施形態を指し得る。
【００２６】
コンピュータ可読媒体への言及は、デジタルデータ処理装置上に機械可読命令を記憶する能力があるあらゆる形態をとり得る。コンピュータ可読媒体は、伝送回線、コンパクトディスク、デジタルビデオディスク、磁気テープ、ベルヌーイドライブ（Ｂｅｒｎｏｕｌｌｉ  ｄｒｉｖｅ）、磁気ディスク、パンチカード、フラッシュメモリ、集積回路、または他のデジタルデータ処理装置メモリデバイスにより具現化され得る。
【００２７】
さらに、本発明の記載される特徴、構造、または特質は、任意の好適な方法で１つ以上の実施形態に組み合わせてもよい。続く説明において、プログラミング、ソフトフェアモジュール、ユーザ選択、ネットワークトランザクション、データベースクエリ、データベース構造、ハードウェアモジュール、ハードウェア回路、ハードウェアチップ等の例のような多数の具体的な詳細は、本発明の実施形態を十分に理解することをもたらすために、提供される。しかしながら、当業者は、本発明が１つ以上の特定の詳細なしに、または他の方法、構成要素、材料、およびその他によって実施されてもよいことを認識するであろう。他の事例において、周知の構造、材料、または操作は、本発明の態様を曖昧にすることを避けるために詳細中に示されないあるいは記載されない。
【００２８】
本明細書に含まれる概略フローチャート図は、概して論理フローチャート図として提示される。それゆえに、この描写される順番および名前が付けられるステップは、提示される方法の一実施形態を示す。図示される方法の１つ以上のステップまたはそれらの一部への機能、論理、または効果において同等である他のステップおよび方法が、想達可能であろう。さらに、採用されるこのフォーマットおよび記号は、方法の論理的なステップを説明するために提供され、方法の範囲を限定しないことが理解される。様々な矢印の種類および線種をフローチャート図内に採用され得るが、それらは対応する方法の範囲を限定しないことが理解される。実際に、いくつかの矢印または他のコネクタを、方法の論理フローのみを示すために使用することができる。例えば、矢印は、描写される方法の列挙されたステップ間の不特定の持続期間における、待機期間または監視期間を示すことができる。さらに、特定の方法が起こる順番は、示されるステップに対応する順番に従っても、従わなくても良い。
【００２９】
本明細書に使用されるメタデータは、ソリッドステート記憶デバイスの操作に関するいかなるデータをも指すことができる。したがって、メタデータは、キャッシュメタデータおよび／または記憶メタデータを指してもよい。いくつかの実施形態において、ソリッドステート記憶デバイスは、キャッシュおよび／または記憶メタデータを含む共有データ構造を維持するように構成することができる。データ構造は、キャッシュマネージャ、グルーマー、および／または他の管理モジュールによりアクセス可能となり得、それらは、ソリッドステート記憶デバイスのキャッシング、記憶装置、および／または保全操作（例えば、グルーミング）を効果的に管理するためにメタデータを使用することができる。
【００３０】
本明細書に使用されるキャッシュメタデータは、ソリッドステート記憶デバイス上に記憶されるキャッシュおよび／またはソリッドステート記憶デバイス上で行われるキャッシュ操作に関するいかなるデータをも指し得る。キャッシュメタデータは、補助記憶装置へバックアップされているキャッシュエントリ記憶ユニットを識別するための破棄可能性インジケータ、キャッシュ排除メタデータ、キャッシュ属性（例えば、ＰＩＮ、ＢＬＡＣＫＬＩＳＴ）、キャッシュ指令（例えば、フラッシュ（Ｆｌｕｓｈ））等を含み得るがそれらに限定されない。例えば、キャッシュ排除メタデータは、最近最も使われていないパターン、アクセス頻度等のデータアクセスパターンを含んでもよい。キャッシュ排除メタデータは、特定のキャッシュエントリに関して、キャッシュ排除を決定するために使用することができる。例えば、このキャッシュ排除メタデータは、「ホット」、「ウォーム」、および／またはコールド等であるキャッシュエントリを識別するために使用されてもよい。コールドキャッシュエントリは排除の対象にされる可能性があり、「ホット」エントリは保持され得る。このキャッシュ排除メタデータは、ＰＩＮ、ＢＬＡＣＫＬＩＳＴ等のようなキャッシュ属性も含んでもよく、それらは、キャッシュ操作を管理するために使用することができる（例えば、ＰＩＮ指令は、データをソリッドステート記憶デバイスから排除されていることから防ぐことができる）。同様に、キャッシュ排除メタデータは、キャッシュからキャッシュエントリをフラシュする、あるいは排除する「ＦＬＵＳＨ」指令のようなキャッシュ指令に応答することができる。
【００３１】
本明細書に使用される記憶メタデータは、ソリッドステート記憶デバイスのソリッドステート記憶媒体および／またはソリッドステート記憶デバイス上で行われる記憶操作に関するいかなるデータをも指すことができる。記憶メタデータは、ソリッドステート記憶デバイス上の有効データおよび／または無効データを識別するための有効性インジケータ、記憶ユニット検索へ効率的な論理アドレスを提供するための順インデックスメタデータ、論理アドレス検索へ効率的な記憶ユニットを提供するための逆インデックスメタデータ、占有量メタデータ（例えば、ソリッドステート記憶デバイス上に記憶されるデータ、占有量閾値等）、記憶媒体ステータス（例えば、磨耗率、信頼性、エラー率等）、逐次記憶メタデータ（例えば、ロギング等）等を含んでもよいがそれらに限定されない。
【００３２】
本明細書に使用される記憶ユニットは、ソリッドステート記憶デバイス上にデータを記憶するためのいかなる位置をも指すことができる。したがって、記憶ユニットは、ソリッドステート記憶素子のブロック、複数のソリッドステート記憶素子上のブロックを含む仮想ブロックまたはそれらの一部分、ページ、複数のソリッドステート記憶素子のページを含む仮想ページ、またはそれらの一部分、記憶区分、仮想記憶区分、消去ブロック、仮想消去ブロック等を含んでもよい。
【００３３】
記憶ユニットは記憶区分の一部であってもよい。本明細書に使用される記憶区分は、ソリッドステート記憶デバイスの消去可能な区分を指すことができる。したがって、記憶区分は、ソリッドステート記憶素子の消去ブロック、複数のソリッドステート記憶素子上の記憶区分を含む仮想消去ブロックまたはそれらの一部分等を指すことができる。
【００３４】
いくつかの実施形態において、キャッシュは複数の「キャッシュエントリ」を含んでもよい。キャッシュエントリは、論理アドレス（または、論理アドレスの範囲、この論理アドレスの範囲は、順序付けられたアドレス、順序付けられていないアドレス、連続アドレス、および不連続なアドレスを含んでもよい）および論理アドレスに対応するデータがソリッドステート記憶デバイス上に記憶される１つ以上の記憶ユニットを含んでもよい。キャッシュエントリのデータは、記憶ユニットの一部、単一記憶ユニット、および／または多重記憶ユニット上に記憶されてもよい。キャッシュエントリは、可変サイズを有してもよい。上述のように、キャッシュエントリは、クライアントの論理アドレスと関連付けることができる。論理アドレスとそれぞれのキャッシュエントリとの間の関連は、ソリッドステート記憶デバイス１１４により（例えば、メタデータ１１７内に）維持することができる。キャッシュエントリのデータは、ソリッドステート記憶デバイスの記憶ユニット内（例えば、ページ、仮想ページ、消去ブロック、および／または消去ブロック）に記憶されてもよい。代替として、キャッシュエントリのデータは、記憶境界をまたがることができる（例えば、複数のページ、仮想ページ、消去ブロック、および／または仮想消去ブロック上に記憶される）。
【００３５】
ソリッドステート記憶デバイスにより維持されるメタデータは、複数のキャッシュエントリを含むことができ、それぞれが論理アドレスを対応するソリッドステート記憶デバイス上の記憶ユニットに関連付ける。これらの関連は、マップまたはインデックス（「順マップ」または「順インデックス」として言及される）内において維持することができる。本明細書に使用される順マップまたは順インデックス（または一般的にインデックス）は、キャッシュエントリ論理アドレス（例えば、クライアントからの論理ブロックアドレス）をソリッドステート記憶デバイスの記憶ユニットと関連付けることができるいかなるデータ構造をも指し得る。いくつかの実施形態において、インデックスは、Ｂツリー等のようなツリーデータ構造を含んでもよい。ツリーデータ構造は、論理アドレス、または論理アドレスのセット（例えば、範囲および／または長さとして）によりインデックス付けされるキャッシュエントリを含んでもよい。したがって、インデックスは、範囲Ｂツリー（Ｒａｎｇｅ  Ｂ−Ｔｒｅｅ）または（一般的にＢツリー）と称することができる。複数のキャッシュエントリを含むデータ構造の例は、図１１と併せて以下に記載される。
【００３６】
順インデックスは、論理アドレスに対応するデータが、ソリッドステート記憶デバイス上に記憶されるかどうかを判定するために使用することができる。例えば、アドレスと関連付けられる節点がインデックス内にある場合、アドレスに対する有効データはソリッドステート記憶デバイス上で利用可能であるが、その反対に、インデックス内に節点が存在しない場合、論理アドレスに対応するデータはソリッドステート記憶デバイス上に記憶されていない。
【００３７】
メタデータは、（順マップ内として論理アドレスによりインデックス付けすることとは逆に）それらの物理アドレスにより記憶ユニットをインデックス付けすることができる逆インデックスをさらに含んでもよい。したがって、この逆インデックスは、特定の記憶ユニットの高速かつ効率的な検索を提供することができ、および／またはソリッドステート記憶デバイスの物理アドレス空間を通して逐次的な走査を提供することができる。いくつかの実施形態において、逆インデックスは、順インデックスと同一の節点（葉節点）につなぐことができる（例えば、逆インデックスは、順インデックスのミラーとすることができ、葉節点が論理アドレスではなく物理アドレスによりインデックス付けされる点で異なる）。代替として、逆インデックスは、ツリー、マップ、配列、テーブル、ビットマップ等のような分離データ構造を含んでよい。いくつかの実施形態において、逆インデックスは、記憶ユニットと、有効性インジケータ、破棄可能性インジケータ（例えば、記憶ユニットのデータが補助記憶装置上に記憶されたかどうか）、記憶ユニット磨耗率、エラー率、アクセスパターン等のような記憶ユニットメタデータとの間の関連付けを提供することができる。
【００３８】
本明細書に使用されるキャッシュ排除メタデータは、キャッシュ排除（または保持）決定するために使用されるメタデータを指すことができる。キャッシュ排除メタデータは、キャッシュエントリと関連付けることができ、したがって、ソリッドステート記憶デバイス上の特定の記憶位置ではなく、論理アドレスによりインデックス付けることができる。これは、（例えば、逐次的な記憶操作による）データの物理的記憶位置の変更にもかかわらず、キャッシュ排除メタデータが維持されることを可能にする。キャッシュ排除メタデータは、「ホット」、「ウォーム」、および／または「コールド」であるキャッシュエントリを識別することができる。本明細書に使用される「ホット」、「ウォーム」、および／または「コールド」データは、特定のアクセスおよび／または使用パターン、他のデータとの物理的な空間相関関係を有するデータを指すことができる（言い換えれば、１組のデータの「温度」は、データが物理的に媒体上でまたは論理的に論理アドレス空間内で、どれほどキャッシュ内で使用される他のデータと近いかによって、決定され得るまたは影響を受け得る）。例えば、「ホット」または「ウォーム」データは、（キャッシュ排除メタデータによって示されるように）最近アクセスされたおよび／または特定の頻度でアクセスされたデータを指すことができる。それに対し、「コールド」データは、（これも、キャッシュ排除メタデータによって示されるように）特定の時間閾値内に、特定の頻度で、または同様にアクセスされていない等のデータを指すことができる。当技術分野において知られる様々な異なる技術および／またはデータアクセスパターンを、「ホット」、「ウォーム」、および／または「コールド」データを識別するために使用することができ、それらのいずれかは本開示の教示下で実現することができる。さらに、キャッシュ排除メタデータは、キャッシュ属性および／または指令を含むことができる。キャッシュ属性は、キャッシュ管理に情報を与えることができ、例えば、「ＰＩＮ」キャッシュ指令は、特定のキャッシュエントリがソリッドステート記憶デバイスから排除されることを防ぐことができ、「ＢＬＡＣＫＬＩＳＴ」属性および／または「ＦＬＵＳＨ」指令は、データがキャッシュ内において保持されることを防ぐことができる。
【００３９】
いくつかの実施形態において、ソリッドステート記憶デバイスは、データを逐次的に記憶することができる。本明細書に使用される逐次的な記憶装置は、データが１つ以上の付加ポイントに記憶される位置のずれた記憶スキームを指すことができる。したがって、ソリッドステート記憶デバイス上に記憶されているデータが修正される（また他の理由のため復元される）場合、データは、（例えば、データが本来記憶された同一の記憶ユニットへ再書き換えされるのではなく）ソリッドステート記憶デバイスの異なる記憶ユニットに記憶され得る。
【００４０】
逐次的な記憶装置はまた、ソリッドステート記憶デバイスにより記憶メタデータ（例えば、ログベースの記憶装置）を維持するための機構を指してもよい。記憶メタデータは、ソリッドステート記憶デバイス上で行われる記憶操作のシーケンスが再構成または再生することを可能にする。記憶メタデータは、記憶区分タイムスタンプ、シーケンスインジケータ、パケットヘッダー、順および／または逆インデックス等を含んでもよい。例えば、第１の論理アドレスに対応するデータがソリッドステート記憶デバイス上に記憶される場合、ロギングデータを維持することができる。メタデータは、上に開示される順インデックス（例えば、Ｂツリー）内のデータをインデックス付けすることを含んでもよい。例えば、論理アドレスに対応するキャッシュエントリはインデックスへ追加され得、インデックスは、論理アドレスに対応するデータを含むソリッドステート記憶装置上の記憶ユニットを参照するように設定することができる。上述のように、論理アドレスは、アドレス、および長さもしくは範囲を含んでよく、および／または１組の論理アドレスを含んでもよい。データがクライアント（または他の実体）により変更される場合、変更されたデータは、ソリッドステート記憶デバイス上に（例えば、「位置がずれて」）逐次的に記憶され得る。したがって、論理アドレスと関連付けられる有効データを含む記憶ユニットは変化し得る。キャッシュエントリは、新しい記憶ユニット（１つまたは複数）を反映するように更新することができ、古い記憶ユニットは無効にすることができる（例えば、逆インデックスまたは他のデータ構造において）。記憶操作のこのシーケンスは、順マップ、ソリッドステート記憶デバイス上に記憶されるシーケンスインジケータ、および／または他の記憶メタデータ（例えば、逆インデックス等）を使用して再生することができる。他の逐次的な記憶操作は、記憶区分復旧、ガーベジコレクション、エラー管理、仮想記憶管理、逐次的な記憶装置（例えば、ログベース記憶操作）等を含んでもよいが、それらに限定はされない。本明細書に使用される逐次的な記憶操作は、上述のいずれの記憶操作をも指し得る。
【００４１】
図１は、クライアント１１０ａ〜ｃ、キャッシュとして操作するよう構成されたソリッドステート記憶デバイス１１４、コミュニケーション・バス１１６、および補助記憶装置１１８を備えるシステム１００の一実施形態を示す。システム１００は、ストレージ接続ネットワーク（「ＳＡＮ」）、ネットワーク接続ストレージ（「ＮＡＳ」）、またはソリッドステート記憶デバイス１１４とともにクライアント１１０ａ〜ｃおよび補助記憶装置１１８の他の構造であってもよい。クライアント１１０ａ〜ｃは、補助記憶装置１１０内に記憶されたデータにアクセスするコンピューティングデバイスである。クライアント１１０ａ〜ｃは、デスクトップ、ワークステーション、サーバ、または他の特定の種類のコンピューティングデバイスのようなパーソナルコンピュータであってもよい。代替として、またはさらに、クライアント１１０ａ〜ｃは、オペレーティングシステム（ＯＳ）、ファイルシステム（ＦＳ）、ウェブサーバ、データベースサーバ等のようなコンピューティングデバイス上で作動しているプロセスまたはサービスを含むことができる。
【００４２】
ソリッドステート記憶デバイス１１４は、クライアント１１０ａ〜ｃおよび／または補助記憶装置１１８へキャッシングサービスを提供するように構成することができる。ソリッドステート記憶デバイス１１４をキャッシュとして使用することは、いくつかの異なる利点を提供することができる。例えば、ソリッドステート記憶デバイス１１４からの読み込み、およびソリッドステート記憶デバイス１１４へ書き込みを行うクライアント１１０ａ〜ｃのアクセス時間は、補助記憶装置１１８から／補助記憶装置１１８へデータを直接的に読み込むならびに書き込むクライアント１１０ａ〜ｃのアクセス時間より少なくなり得、ソリッドステート記憶デバイス１１４はクライアント１１０ａ〜ｃがより迅速にデータにアクセスすることを可能にする。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、論理的なインターフェースをクライアント１１０ａ〜ｃへ提示することができ、ソリッドステート記憶デバイス１１４の物理記憶容量を上回る論理アドレス空間を含むことができる。論理アドレス空間は、補助記憶装置１１８の物理記憶容量と対応することができる、クライアントが透過的に（例えば、それらがあたかも補助記憶装置１１８に直接的にアクセスしていたかのように）ソリッドステート記憶デバイス１１４と情報をやりとりすることを可能にする。代替として、またはさらに、ソリッドステート記憶デバイス１１４はソリッドステート記憶デバイス１１４および補助記憶装置１１８（例えば、「まばらな」または「細い」論理アドレス空間）の両方の物理記憶容量を上回る論理アドレス空間を提示することができる。論理アドレス空間は、６４ビットアドレス空間、３２ビットアドレス空間、またはクライアント１１０ａ〜ｃによって使用される別のアドレス方式を含んでもよい。
【００４３】
ソリッドステート記憶デバイス１１４は、クライアント１１０ａ〜ｃのマップ論理アドレスを、ソリッドステート記憶デバイス１１４上の記憶ユニットへマップするために、論理対物理のインデックスを実装することができ、それによりクライアント１１０ａ〜ｃによって実装される冗長変換層を除去すること、記憶デバイス１１４および１１８へのクライアント１１０ａ〜ｃのアクセスを単純化すること、および／またはクライアント１１０ａ〜ｃのための柔軟な記憶基礎構造（例えば、「まばらな」「細く供給された」記憶サービス）を提供することができる。
【００４４】
ソリッドステート記憶デバイス１１４は、ソリッドステート記憶コントローラ１１５を含むことができ、ソリッドステート記憶コントローラ１１５は、ソリッドステート記憶デバイス１１４上に記憶されるキャッシュと関連する（および／またはデバイス１１４上で行われるキャッシュ操作に関連する）メタデータ１１７、ならびに、ソリッドステート記憶デバイス１１４上で行われる記憶操作に関連する記憶メタデータ、ソリッドステート記憶デバイス１１４上の記憶ユニットのステータス等を維持するように構成され得る。メタデータは、有効性マップおよび破棄可能性マップを含むことができる。有効性マップは、有効データ（最新であり、ならびにクライアント１１０ａ〜ｃの論理アドレスと関連付けられるデータ）を含むソリッドステート記憶デバイス１１４の記憶ユニットを識別することができる。したがって、有効性マップは上述の順インデックスを含んでもよい。無効性マップは、有効性マップから得ることができ（例えば、有効性マップ内にない全ての記憶ユニットは、無効データを含むものとして識別されてもよい）、および／または逆インデックス等のような別個のデータ構造内に維持されてもよい。破棄可能性マップは、補助記憶装置１１８上に記憶されているキャッシュエントリ記憶ユニットを識別することができる。
【００４５】
ソリッドステート記憶デバイス１１４および／またはコントローラ１１５は、クライアント記憶要求に応答してキャッシュエントリを識別するためにメタデータを使用することができるキャッシュ管理装置１３０を含んでもよい。いくつかの実施形態において、キャッシュ管理装置１３０は、デバイスドライバ（例えば、Ｌｉｎｕｘデバイスドライバ）を使用して実装してもよい。
【００４６】
図１は１つのソリッドステート記憶デバイス１１４を示すが、システム１００の他の実施形態は、クライアント１１０ａ〜ｃのためのキャッシュとして機能を果たす複数のソリッドステート記憶デバイス１１４を含んでもよい。いくつかの実施形態において、キャッシュ管理装置１３０は、本システムにおける各ソリッドステート記憶デバイス１１４上に実装されてもよい。他の実施形態において、キャッシュ管理装置１３０は、システム１００内のソリッドステート記憶デバイス１１４の至るところに分配させてもよい。
【００４７】
ソリッドステート記憶デバイス１１４は、補助記憶装置１１８のためのキャッシュとして機能する。いくつかの実施形態において、ソリッドステート記憶デバイス１１４および補助記憶装置１１８は、コミュニケーション・バス１１６によって接続される。コミュニケーション・バス１１６は、ローカルのコミュニケーション・バス（例えば、コンピュータシステムのコミュニケーション・バス）、分散型バス、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、または他の種類の通信ネットワークであってもよく、様々なプロトコルを使用して実装されることができる。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８に直接接続される。ソリッドステート記憶デバイス１１４および補助記憶装置１１８はまた、バスによってさらに接続されてもよい。
【００４８】
ソリッドステート記憶デバイス１１４は、補助記憶装置１１８とほぼ同時にデータアクセス要求を認識するルックアサイドキャッシュとしての機能を果たすように構成されることができる。他の実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８の前にデータアクセス要求を認識するルックスルーキャッシュとして機能を果たすように構成してもよい。ソリッドステート記憶デバイス１１４がルックスルーキャッシュであるいくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４上でのアクセスの試みが失敗した場合データアクセス要求を補助記憶装置１１８へ渡す。さらにソリッドステート記憶デバイス１１４は、書き戻しキャッシュとして実装されてもよい。いくつかの実施形態において、現在のキャッシュモードは、ソリッドステート記憶デバイス１１４によって維持されるメタデータ内において利用可能であり得る。キャッシュモードは、記憶インターフェース、強化記憶インターフェース等を介して、クライアント１１０ａ〜ｃによって変更可能であり得る。さらにメタデータは、ＰＩＮ、ＢＬＡＣＫＬＩＳＴ等のようなキャッシュ属性、および／またはキャッシュ指令（例えば、ＦＬＵＳＨ）を示すことができる。キャッシュ属性および／または指令は、キャッシュ管理装置１３０および／またはソリッドステート記憶コントローラ１１５によるアクセスのためにソリッドステート記憶デバイス１１４によって維持されるメタデータ内で記憶されてもよい。
【００４９】
補助記憶装置１１８は、補助記憶装置１１８から／補助記憶装置１１８へデータを読み込むならびに書き込むクライアント１１０ａ〜ｃのための記憶手段を提供することができる。補助記憶装置１１８は、ソリッドステート記憶装置、ハードディスクドライブ、テープ、他の何らかの不揮発性データ記憶媒体、または先行例の組み合わせのような１つ以上の不揮発性記憶デバイスを含んでもよい。いくつかの実施形態において、補助記憶装置１１８、または補助記憶装置１１８内の少なくともいくつかの記憶媒体は、ソリッドステート記憶デバイス１１４のそれより低いアクセスおよび／またはスループット性能を有し得る。
【００５０】
いくつかの実施形態において、システム１００は、コンピューティングデバイス内に実装される。例えば、ソリッドステート記憶デバイス１１４は、デスクトップのようなコンピューティングデバイスのマザーボードに取り付けられることができ、ハードディスクドライブである補助記憶装置１１８のためのキャッシュとして機能することができる。コンピューティングデバイスのＣＰＵは、データの読み込みならびに書き込みを行うために補助記憶装置１１８と比較してソリッドステート記憶デバイス１１４のより高速な読み込み／書き込み時間を活用することができる。いくつかの実施形態において、システム１００はまた、追加的なソリッドステート記憶デバイス１１４を含む。例えば、システム１００は、キャッシュ階層に編成される複数のソリッドステート記憶デバイス１１４で多層のキャッシュを実装することができる。
【００５１】
図２は、ソリッドステート記憶デバイス１１４により提示される論理的かつ物理的な記憶空間を図示するシステム２００の一実施形態を示す。システム２００は、システム２００の構成要素としてファイルシステム２１０を図示する。ファイルシステム２１０は、物理的コンピューティングデバイス上で作動する論理的実体である。いくつかの実施形態において、ファイルシステム２１０は、図１のクライアント１１０ａ〜ｃの１つの上に実装されてもよい。ファイルシステム２１０はシステム２００内のコンピュータファイルおよびデータを記憶し編成する。多くの実施形態において、ファイルシステム２１０は、記憶装置のブロックをファイルおよびディレクトリに編成し、どのブロックがどのファイルに属するかを追跡する。図２はファイルシステム２１０を描写するが、本開示はこの観点において限定されず、当技術分野において知られる、データベース、サーバ（例えば、ウェブサーバ、記憶サーバ等）、アプリケーション、ユーザ等を含むがそれらに限定されない、いかなる記憶クライアントと併せても使用することができる。
【００５２】
いくつかの実施形態において、補助記憶装置１１８は、ファイルシステム２１０によってデータが実際に記憶される物理的記憶空間を提供する。補助記憶装置１１８によって利用可能である容量は、システム２００に応じて幅広く異なり、５００ＧＢがデスクトップコンピュータの典型であり得るが、テラバイト（「ＴＢ」）またはペタバイト（「ＰＢ」）台の補助記憶装置１１８がストレージエリアネットワーク（ＳＡＮ）等の分散型記憶システムにおいて提供され得る。一般的に、補助記憶装置１１８はブロック記憶デバイスである記憶デバイスで構成されるが、他の種類の補助記憶デバイスが補助記憶装置１１８内において使用されてもよい。
【００５３】
ソリッドステート記憶デバイス１１４は、事前に決定される物理記憶容量を有し得る。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４の物理空間の一部が補助記憶装置１１８のためのキャッシュとして機能を果たすこと専用に用いられ、ならびにソリッドステート記憶デバイス１１４の一部は記憶装置（例えば、補助記憶装置１１８の一部または他の記憶サービス）として作動するよう構成されるように、論理的におよび／または物理的に分割されてもよい。例えば、ソリッドステート記憶デバイス１１４は、２００ＧＢの物理空間がキャッシュとしての機能を果たすことのためだけに用いられ、フォーマットされてもよく、残りの１２０ＧＢが補助記憶装置１１８の一部として扱われ得る。
【００５４】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４の物理的サイズにかかわらず、補助記憶装置１１８の物理空間と同一のサイズであるキャッシュ論理空間２２０をファイルシステム２１０へ提示する。例えば、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８と同一のサイズとなるようにフォーマットされてもよい。典型的な実施形態において、補助記憶装置１１８の物理記憶容量（例えば、１ＰＢ）は、ソリッドステート記憶デバイス１１４の物理記憶容量（例えば、８０ＧＢ）より大きい。
【００５５】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８の物理空間（ならびにソリッドステート記憶デバイス１１４自体）より大きい論理アドレス空間２２０をファイルシステム２１０へ提示することができる。ユーザは、補助記憶装置１１８に物理空間をキャッシュ論理空間２２０のサイズの変更なしに追加することができ得る。ソリッドステート記憶デバイス１１４は、デバイス１１４および／または補助記憶装置１１８における論理アドレスと「まばらな」または「細く供給された」記憶ユニットとの間の関連付けを、上述の順マップを使用して維持することもできる。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４および／または補助記憶装置１１８の占有量が閾値を上回る場合に、追加の記憶空間（例えば、追加の補助記憶装置１１８）を要求するように構成することができる。ソリッドステート記憶デバイス１１４は、クライアント（例えば、ファイルシステム２１０）が、ソリッドステート記憶デバイス１１４の実際の物理容量、補助記憶装置１１８、残存している記憶容量、現在の占有量レベル（例えば、ソリッドステート記憶デバイス上に現在記憶される有効データの量）等を決定するためにクエリを発行することができるインターフェースを提示することができる。さらにインターフェースは、クライアント（例えば、ファイルシステム２１０）へ記憶容量の要求、記憶容量の予約等のコールを提供することもできる。
【００５６】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８の変動する物理的記憶装置に基づきキャッシュ論理空間２２０のサイズを動的に調整することができる。例えば、新しい記憶デバイスが補助記憶装置１１８に追加される場合、ソリッドステート記憶デバイス１１４はファイルシステム２１０に提示されるキャッシュ論理空間２２０のサイズを動的に大きくすることができる。
【００５７】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ファイルシステム２１０に対し透過的であってもよい。ファイルシステム２１０は、ソリッドステート記憶デバイス１１４によってファイルシステム２１０へ提示されるキャッシュ論理空間２２０のみを認識することができる。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８のコントローラとしての機能を果たす。したがって、ファイルシステム２１０は、データアクセスイベント（読み込みおよび書き込み要求等）を、ソリッドステート記憶デバイス１１４によって提示されるキャッシュ論理空間２２０へ向ける。ファイルシステム２１０は、それが処理しているソリッドステート記憶デバイス１１４がキャッシュ論理空間２２０程大きい物理的記憶空間を有していないことを認識しない場合がある。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、データをＲＡＩＤ構造において、補助記憶装置１１８にストライプ状にする。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ＲＡＩＤ構造で、他のソリッドステート記憶デバイスで構成されてもよい。
【００５８】
したがって、ソリッドステート記憶デバイス１１４は、まばらにマップされる６４ビットアドレス空間を実装することができる。いくつかの実施形態において、ファイルシステム２１０がデータ（例えば、読み込み要求）を要求し、要求データのためのアドレス（論理ブロックアドレス、またはＬＢＡ等）を提供する際、ソリッドステート記憶デバイス１１４（および／またはコントローラ１１５）は、ソリッドステート記憶デバイス１１４により維持されるメタデータ１１７（上述の順インデックスのようなインデックス）内のアドレスを検索することができ、論理アドレスと関連付けられるデータがソリッドステート記憶デバイス１１４上で利用可能である場合、対応する記憶ユニットにおいて読み込みを開始する。ソリッドステート記憶デバイス１１４は、データが特定されたアドレスにない場合、および／または論理アドレスがインデックス内にない場合、エラーを生成することができる。エラーはキャッシュミスとして解釈され得、補助記憶装置１１８から要求データを読み込み、１つ以上の記憶ユニット内のデータをキャッシングするソリッドステート記憶デバイス１１４によって処理され得る。キャッシュミスは、論理アドレスを参照するためにメタデータを更新すること（例えばインデックスに葉節点を追加する）等をさらに含み得る。
【００５９】
ソリッドステート記憶デバイス１１４がソリッドステート記憶デバイス１１４の物理空間より大きいキャッシュ論理空間２２０を提示する実施形態において、キャッシュ管理装置１３０は、ソリッドステート記憶デバイス１１４がその物理記憶容量を上回らないことを保証するように、ソリッドステート記憶デバイス１１４を管理する。より大きい論理空間２２０を提示しながらソリッドステート記憶デバイス１１４の物理記憶容量を管理するための例示的アプローチを、以下に記載する。
【００６０】
そのような実施形態において、ソリッドステート記憶デバイス１１４は、ファイルシステム２１０および補助記憶装置１１８へのアクセスを求める他の実体に対し透過的であり得る。ソリッドステート記憶デバイス１１４を管理することおよびデータの検索の複雑性は、ファイルシステム２１０から隠され得る。したがって、ファイルシステム２１０は、読み込む、または補助記憶装置１１８への書き込みの代わりにソリッドステート記憶デバイス１１４へ書き込むデータについてソリッドステート記憶デバイス１１４へチェックインをする必要がない可能性がある。その代わりに、ファイルシステム２１０は、ソリッドステート記憶デバイス１１４によって提示されるキャッシュ論理空間２２０内のデータに簡単にアクセスし、ソリッドステート記憶デバイス１１４が、データを処理する最も効率的な手段を透過的に判定することを可能にする。キャッシュ論理空間２２０の根底にある物理的記憶配置（つまり、ソリッドステート記憶デバイス１１４のおよびその補助記憶装置１１８との関係）は、ファイルシステム２１０から隠される。さらに、ソリッドステート記憶デバイス１１４がデータのキャッシングを管理できるようにさせることにより、キャッシュ管理装置１３０は、ファイルシステム２１０に対して通常利用可能ではないソリッドステート記憶デバイス１１４によって維持されるメタデータ１１７を使用して、キャッシュ保全についての賢い選択をすることができる。
【００６１】
図３は、グルーマー３１０およびキャッシュ管理装置１３０を備えるソリッドステート記憶コントローラ１１５の例示的実施形態を示す。ソリッドステート記憶コントローラ１１５は、ソリッドステート記憶媒体３２０へ結合（例えば、バスまたは他の通信管路を直接的に介して）することができる。ソリッドステート記憶媒体３２０は、ローカルのコミュニケーション・バス、ネットワークバス、ネットワーク接続等を介して、コントローラ１１５へ結合されてもよい。いくつかの実施形態において、ソリッドステート記憶デバイス１１４および／またはコントローラ１１５は、複数のソリッドステート記憶媒体３２０へ通信可能に結合されてもよい。ソリッドステート記憶媒体３２０は、１つ以上のソリッドステート記憶素子（示されていない）を含んでもよく、それらはバンク内に配置されてもよい。ソリッドステート記憶コントローラ１１５は、並行してバンクの１つ以上にアクセスすることができ、および／またはソリッドステート記憶デバイス１１４は、複数のソリッドステート記憶コントローラ１１５を備えることができる。
【００６２】
描写される実施形態において、キャッシュ管理装置１３０は、キャッシュコントローラ３１２およびバックアップエンジン３１４を備える。グルーマー３１０およびキャッシュ管理装置１３０は、とりわけ、有効性マップを含んでもよい記憶メタデータ３１６、および破棄可能性マップを含んでもよい記憶メタデータ３１８を含むことができるメタデータ１１７へのアクセスを有することができる。グルーマー３１０および／またはキャッシュ管理装置１３０は、ファームウェア、ソフトフェア、ハードウェア、またはそれらのある種の組み合わせとして実装されてもよい。図３に示されるように、グルーマー３１０およびキャッシュ管理装置１３０は、ソリッドステート記憶コントローラ１１５上に実装することがきる。しかしながら、本開示はこの観点において限定されない。例えば、いくつかの実施形態において、グルーマー３１０および／またはキャッシュ管理装置１３０は、別個のコントローラ、プロセッサ、ＦＰＧＡ等を使用して実装することができる。代替として、またはさらに、ソリッドステート記憶コントローラ１１５、グルーマー３１０、および／またはキャッシュ管理装置１３０は、ソリッドステート記憶デバイス１１４上で作動する１つ以上のドライバとして実装されてもよい。
【００６３】
グルーマー３１０は、ソリッドステート記憶媒体３２０上に記憶されるデータを、記憶区分復旧（例えば、消去ブロック復旧）、データリフレッシュ操作、データエラー訂正、エラー処理等のような保全操作の一部として移動する。グルーマー３１０は、ファイルシステム２１０および補助記憶装置１１８に対して透過的な方法で、ソリッドステート記憶媒体３２０内の記憶ユニット間でデータを移動することができる。例えば、グルーマー３１０は、ソリッドステート記憶デバイス１１４上の記憶空間を再生するために、ソリッドステート記憶デバイス１１４として作動しているソリッドステート記憶デバイス内のデータ上のガーベジコレクション操作を行うことができる。さらにグルーマー３１０は、ソリッドステート記憶デバイス１１４内において大量に断片化されるファイルをデフラグすることができる。例示的グルーミング操作は、２００７年１２月６日に申請されたＤａｖｉｄ  Ｆｌｙｎｎらの「Ａｐｐａｒａｔｕｓ，  Ｓｙｓｔｅｍ，  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｓｔｏｒａｇｅ  Ｓｐａｃｅ  Ｒｅｃｏｖｅｒｙ  ｉｎ  Ｓｏｌｉｄ−ｓｔａｔｅ  Ｓｔｏｒａｇｅ」と題される米国特許出願第１１／９５２，１０１号に記載され、これは、参照することによりその全体が本明細書に組み込まれる。同様に、グルーマー３１０は、読み込み妨害からデータを保護するため、および／または磨耗レベリング操作の一部として、データを移動する。当業者は、データ保全および空き空間保全の目的のために、記憶デバイス内にデータの移動することを必要とし得る他のグルーミング操作を理解するであろう。復旧のために選択される記憶区分、有効性マップ、記憶区分エラー率、記憶区分磨耗率、アクセスパターン等のようなグルーマーの操作に関するメタデータは、メタデータ１１７内（例えば、記憶メタデータ３１６内）に維持されてもよい。メタデータ１１７（例えば、記憶メタデータ３１６）は、記憶クライアントによって提供される論理アドレスと論理アドレスに関連する有効データが記憶されるソリッドステート記憶媒体３２０上の記憶ユニット間の関連付けを含むインデックスをさらに含むことができる。上述のように、インデックスは、論理アドレスによってインデックス付けされる節点をエンコードされる長さおよび／または範囲を含むＢツリーを備えることができる。
【００６４】
キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４に関して記憶クライアント（クライアント１１０ａ〜ｃ、ファイルシステム２１０、またはその他等）と補助記憶装置１１８との間のデータの交換を調整する。いくつかの実施形態において、キャッシュコントローラ３１２は、いつならびにどのようにソリッドステート記憶デバイス１１４からデータを排除するかを指定する排除ポリシーを維持することに関与する。いくつかの実施形態において、排除ポリシーは、とりわけ、データアクセスパターン（例えば、データは「ホット」、「ウォーム」、「コールド」等であるかどうか）を含むことができるキャッシュ排除メタデータに基づくことができる。排除メタデータは、最後のアクセス時間（最近に最も使用されていない）、アクセス頻度、キャッシュエントリサイズのアクセス時間に対する比率、および／またはアクセス頻度等に対応することができる。
【００６５】
いくつかの実施形態において、キャッシュ排除メタデータは、排除を決定するのに使用することができるキャッシュ属性および／または命令を含むことができる。例えば、ＰＩＮキャッシュ属性は、データが「コールド」であったとしても関連データをキャッシュ内に保持させることができる。キャッシュ指令（例えば、ＦＬＵＳＨ指令）は、特定のキャッシュエントリをソリッドステート記憶デバイス１１４からフラッシュさせることができる。キャッシュ属性および／または指令は、記憶クライアント（例えば、クライアント１１０ａ〜ｃ）によってインターフェースを介して提供されてもよい。例えば、ソリッドステート記憶デバイス１１４は、クライアントがキャッシュ内に保持する（例えば、ＰＩＮ属性）、あるいはキャッシュから除去する（例えば、ＢＬＡＣＫＬＩＳＴまたはＦＬＵＳＨ）等の、データを特定することできるインターフェースを提供することができる。いくつかの実施形態において、キャッシュ排除決定は、記憶メタデータ３１６に基づき得る。上述のように、記憶メタデータ３１６は、個々の論理アドレス（または論理アドレスセットもしくは範囲）をそれぞれ含むキャッシュエントリとソリッドステート記憶装置１１４上のそれぞれの記憶ユニットを関連付ける順マップを含むことができる。インデックスは、アクセスパターンメタデータと対応論理アドレスとの間の関連を維持するのに使用することができる（例えばツリーインデックス内のカウントは、特定の節点、エッジ、または葉がどれくらい頻繁にアクセスされるか、ならびにどの操作の種類（読み込み、書き込み、トリム）のためのものであるかを追跡することができる）。これらの関連は、その根底にあるデータがソリッドステート記憶デバイス上で移動される（例えば、記憶区分復旧操作の間に、変更に応答して第１の記憶ユニットから第２の記憶ユニットへ移動される等の）場合でさえも保持されることができる。したがって、排除決定を行う際、キャッシュコントローラ３１２（または他の実体）は、関連アクセスパターンメタデータを得るために、記憶メタデータ３１６にアクセスすることができる。
【００６６】
いくつかの実施形態において、キャッシュ排除ポリシーは、空間的なおよび／または時間的な近接性に基づくことができる。空間的な近接性は論理アドレスが「ホット」である場合、（それらがまだアクセスされていないとしても）空間的に近接の論理アドレスも「ホット」である可能性が高いとみなす。キャッシュエントリ間の「空間的な位置」は、記憶メタデータ３１６内に維持することができる（例えば、インデックスまたは順マップを使用すること）。上述のように、記憶メタデータ３１６の順インデックスは、論理アドレスをソリッドステート記憶デバイス１１４の物理的記憶ユニットと関連付けることができる。論理アドレスは、記憶ユニットへ恣意的にマップされてもよく、位置のずれた書き込みおよび他の逐次的な記憶操作に起因して、データの物理的位置は時間と共に変化し得る。したがって、記憶ユニットのアドレスのみを使用して論理的な近接を判定することは非実用的である可能性がある。キャッシュコントローラ３１２（または他の実体）は、排除決定をするための空間的な近接を特定するために記憶メタデータ３１６にアクセスすることができる（例えば、論理アドレス空間内において空間的に「ホット」データに近接するデータは、排除がより好ましくなく、空間的に「ホット」データに近接しないデータは排除がより好ましくあり得る）。
【００６７】
いくつかの実施形態において、ソリッドステート記憶コントローラ１１５は、キャッシングのサポートに使用するためにソリッドステート記憶デバイス１１４上で利用可能な物理的記憶空間の最大量で構成される。管理者（または他の実体）は、ソリッドステート記憶デバイス１１４を構成する際にこの情報を提供することができる。他の実施形態において、キャッシュコントローラ３１２は、それ自体のために記憶空間の最大量を見出す（例えば、ソリッドステート記憶デバイス１１４の物理記憶容量を特定することによって）。最大占有量（およびそれによって導き出される閾値）は、時と共に変化し得る。例えば、ソリッドステート記憶デバイス１１４の特定の記憶位置は、信頼性が低下するおよび／または機能しなくなる可能性があり、デバイス１１４の物理記憶容量を縮小し得る。したがって、最大占有量は縮小され得る。いくつかの実施形態において、その縮小は、クライアントに対し透過的に起こり得る（例えば、ソリッドステート記憶デバイス１１４は、操作を継続し、および／またはクライアントに同一の論理アドレス空間を提示することができる）。代替として、クライアント（例えば、クライアント１１０ａ〜ｃ）に、記憶容量内の縮小を知らせる通知を発行する。同様に、ソリッドステート記憶デバイス１１４の物理記憶容量は、増加し得る（例えば、追加ソリッドステート記憶媒体が追加される場合）。占有量閾値は、追加記憶容量に従って調整することができる。
【００６８】
情報内の最大占有量を使用して、キャッシュコントローラ３１２は、キャッシュ管理装置１３０がソリッドステート記憶デバイス１１４内にキャッシュされることを許す最大データ量を特定する最大占有量閾値を導き出すことができる。いくつかの実施形態において、最大占有量閾値は、全ての使用可能な物理容量を使用せず、その代わりに、ソリッドステート記憶デバイス１１４のために、記憶空間復旧、および／または、使い古したまたは信頼性の低い記憶ユニットの交換のような保全操作を行うため、物理容量の一部を確保することができる。いくつかの実施形態において、キャッシュコントローラ３１２（または他の実体）は、最大占有量閾値を動的に決定することができる。最大占有量閾値は、データアクセスパターン等のメタデータ１１７に基づくことができる。例えば、ソリッドステート記憶デバイス１１４が、排除されると後続のキャッシュミスを引き起こす可能性のある大量の「ホット」データを含む場合、占有量閾値は動的に縮小され得る。逆に、ソリッドステート記憶デバイス１１４が後続のキャッシュミスの可能性が低く排除することができる大量の「コールド」データを含む場合、最大占有量閾値を増加さることができる。代替として、またはさらに、ソリッドステート記憶デバイス１１４は、理想的な閾値を帰納的に決定するために、メタデータ１１７内のキャッシュ動作を追跡するように構成することができる。例えば、最近排除されたキャッシュエントリの高いキャッシュミス率は、追加のキャッシュ記憶空間が必要とされること（またはキャッシュ排除ポリシーを調整するべきであること）等を示し得る。あるいは、キャッシュミス率が低い場合、閾値は縮小され、ソリッドステート記憶デバイスの過剰の記憶空間が他の目的（例えば、他の補助記憶装置のためのキャッシュとして、記憶空間として等）に使用してもよい。
【００６９】
最大占有量閾値は、例えば、ソリッドステート記憶デバイス１１４によって提供される記憶の量から、ソリッドステート記憶デバイス１１４によって使用され、それらに記憶されるソフトフェアまたは他のデータによって占有される記憶量を差し引いた記憶量であり得る。他の実施形態において、最大占有量閾値は、ソリッドステート記憶デバイス１１４内において利用可能である記憶量のいくらかの割合（％）であり得る。いくつかの実施形態において、最大占有量閾値は、サービスの質（ＱＯＳ）属性等のような性能基準に基づき、ソリッドステート記憶デバイス１１４によって決定される。最大占有量閾値は、要求、ジョブ優先順位、または管理手順に基づき動的に変化し得る。さらに他の基準を、調整、整調、あるいはそれ以外の最大占有量閾値の変更のために使用することができる。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、占有量閾値が設定され得るインターフェースを提供することができる。代替として、またはさらに、インターフェースは、最大占有量閾値を決定することができる１つ以上のキャッシュ属性および／または指令（例えば、ＱＯＳ、ＰＩＮ、ＢＬＡＣＫＬＩＳＴ等）を、クライアントが設定することを可能にする。
【００７０】
いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が最大占有量閾値を上回らないことを保証するために、ソリッドステート記憶デバイス１１４上で利用可能な残存物理記憶容量の量を判定するためにメタデータ１１７を問い合わせる。キャッシュコントローラ３１２（または他のモジュール）は、ソリッドステート記憶デバイス１１４内へのデータの各挿入に先立ってメタデータ１１７を使用して、残存物理容量を判定することができる。他の実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４内に残存する物理記憶容量の量に依存して可変な頻度で判定することができる。例えば、ソリッドステート記憶デバイス１１４が利用可能なその物理記憶容量の半分を超える容量を有する場合、キャッシュコントローラ３１２は各挿入に先立って残存物理記憶容量を要求しない可能性があり、代わりにキャッシュコントローラ３１２は、特定数のキャッシュ挿入が発生するまで待機した後判定を行う。ソリッドステート記憶デバイス１１４が次第に満杯になるにつれて、残存物理記憶容量を判定するための問い合わせの頻度は、キャッシュコントローラ３１２がソリッドステート記憶デバイス１１４内への各挿入に先立って問い合わせをする時点まで増えることができる。
【００７１】
いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が最大占有量閾値によって定義される最大占有量に達すると、ソリッドステート記憶デバイス１１４へのいかなるキャッシュ挿入も追加記憶容量が利用可能となるまで防ぐ。キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が最大占有量に達した時でさえも、読み込みが、ソリッドステート記憶デバイス１１４内のデータ上で発生することを可能にする。ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４が過剰に記憶されないこと、ならびにソリッドステート記憶デバイス１１４内に記憶されるデータの保護を提供することを、上述のように保証することができる。
【００７２】
いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４上で使用される物理記憶容量の量を定義する対象の占有量閾値をさらに定義することができる。いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が対象の占有量閾値に達すると、ソリッドステート記憶デバイス１１４からデータが排除される比率を高めるための操作を行うことができる。いくつかの実施形態において、キャッシュ管理装置１３０は、対象の占有量閾値が到達された時点でのみソリッドステート記憶デバイス１１４からデータを排除することを開始する。他の実施形態において、キャッシュコントローラ３１２は、対象の占有量閾値に到達した際に、バックアップエンジン３１４の優先度を高めることができる（例えば、フォアグラウンドプロセスとして作動するようにバックアップエンジン３１４を設定する、あるいはその別様に優先度および／またはバックアップエンジン３１４に割り当てられる相対帯域幅を高める）。このような実施形態において、バックアップエンジン３１４は、対象の占有量閾値が到達されるまでバックグラウンド処理として作動する（例えば、低い優先度または低い帯域幅割り当てのバックアップエンジン３１４を与えることにより）。現在の物理記憶容量、閾値等は、キャッシュコントローラ３１２および／またはグルーマー３１０によるアクセスのために、メタデータ１１７内に維持することができる。
【００７３】
上述のように、メタデータ１１７は、有効性マップを含むことができる記憶メタデータ３１６を含むことができる。本明細書で使用されるマップは、固有キーの集団とそれぞれの値とを関連付けるいかなる関連付けデータ構造をも指す。マップ内の固有キーの検索は、関連する値を戻す。有効性マップは、ソリッドステート記憶デバイス１１４の記憶ユニットと、ユニットと関連付けられるデータが、有効または無効のどちらかであると特定する有効性インジケータとを関連付けることができる。有効性インジケータは、１つの状態が有効データを表し、他方の状態が無効データを表す、有効性マップ内のビットであってもよい。有効性マップ３１６は、ビットマップ、テーブル、リスト、または当技術分野において知られる他のデータ構造であり得る。例えば、有効性マップは、アドレス空間のような非常に大きく潜在的にまばらに追加されるドメインを管理することに適した、有効または無効な記憶ユニット（および／または記憶ユニットセットまたは範囲）のみの表現を含むデータ構造であり得る。例えば、有効性マップは、有効データを含む各記憶ユニットのエントリのまばらな配列を含んでもよい。無効性は、有効性マップ（位置が有効性マップ内にない場合、次いで、位置は無効である）から得ることができ、あるいはその逆もまた同様である。
【００７４】
ソリッドステート記憶デバイス１１４のユニットまたは記憶ユニットは、アドレス可能なソリッドステート記憶媒体３２０上の物理的記憶ユニットを指し得る。いくつかの実施形態において、メタデータ１１７は、１対１の記憶ユニットに対する論理ブロックアドレス（ＬＢＡ）の比率を維持することができ、すなわち、１つのＬＢＡは、１つの記憶ユニットまたはユニットと関連付けられ得る。代替として、またはさらに、ＬＢＡ（またはインデックス節点）は、記憶ユニットの長さまたは範囲と関連付けられ得る。いくつかの実施形態において、記憶ユニットは、フラッシュメモリまたは他の不揮発性記憶媒体を備えることができるソリッドステート記憶媒体３２０内の物理的ブロックアドレス（「ＰＢＡ」）によってアドレス決定される、物理的ブロックである。別の実施形態において、記憶ユニットは、ハードディスクドライブ上のシリンダーヘッドセクター（「ＣＨＳ」）位置を指し得る。記憶ユニットの性質は、ソリッドステート記憶デバイス１１４によって使用される特定の記憶媒体によって異なる。ソリッドステート記憶デバイス１１４は、多種類の記憶ユニットを同時サポートすることができる。
【００７５】
有効性マップ３１６内において有効とマークされるソリッドステート記憶デバイス１１４の記憶ユニットと関連付けられるデータはソリッドステート記憶デバイス１１４上に保持することができ、その一方無効ユニットと関連付けられるデータ（マークされるおよび／または推測されるどちらか一方）はソリッドステート記憶デバイス１１４から除去され得る。無効記憶ユニットは、記憶区分再生プロセス（例えば、ガーベジコレクション）における除去の候補となり得る。復旧される記憶区分内の有効データは、ソリッドステート記憶デバイス１１４の他の記憶区分へ有効データを書き込むことによりソリッドステート記憶デバイス１１４上に保持することができる。
【００７６】
キャッシュメタデータ３１６は、ビットマップ、テーブル、リスト、または当技術分野において知られる他のデータ構造を含むことができる破棄可能性マップを含んでもよい。破棄可能性マップは、ソリッドステート記憶デバイス１１４の記憶ユニットを、ユニットに関連付けられるデータが破棄可能または破棄不可能であるかどうかを特定する破棄可能性インジケータと関連付けることができる。ユニットと関連付けられるデータは、それが補助記憶装置１１８に記憶されている場合、破棄可能である。ユニットと関連付けられるデータが補助記憶装置１１８内に記憶されていない場合は一般的に破棄不可能である。
【００７７】
図３の例において、記憶メタデータ３１６およびキャッシュメタデータ３１８は、同一のデータ構造（メタデータ１１７）で実装される。例えば、有効性マップおよび破棄可能性マップは、１つのビットが有効性を表し第２のビットが破棄可能性を表す単一マップ内に実装することができる。しかしながら、いくつかの実施形態において、記憶装置ならびにキャッシュメタデータ３１６および３１８は、別個のデータ構造として実装することができる。このような実施形態において、１つのデータ構造の単一の読み込みで、特定の記憶ユニットの有効性ステータスおよび破棄可能性ステータスとの両方を判定することができる。例えば、有効性インジケータは、組み合わされたマップの１列であってもよく、破棄可能性インジケータは組み合わされたマップの別の列であってもよい。
【００７８】
キャッシュ管理装置１３０は、メタデータ１１７を使用して補助記憶装置１１８上にバックアップするためのキャッシュエントリを識別するように構成されるバックアップエンジン３１４を備えることができる。バックアップエンジン３１４は、記憶メタデータ３１６において有効として、ならびにキャッシュメタデータ３１８において破棄不可能としてマークされる記憶ユニットを、補助記憶装置１１８上に記憶させることができる。補助記憶装置１１８は、補助記憶装置１１８から外へ適切に読み出すことができるようにデータを記憶する。例えば、バックアップエンジン３１４は、メタデータ１１７を使用して有効および破棄不可能としてマークされる記憶ユニットを識別することができる。ユニットと関連付けられるデータは、ＬＢＡおよびＬＢＡに対応するデータを含むことができる（ソリッドステート記憶媒体３２０上に記憶されるように）。バックアップエンジン３１４は、データを読み込み、データを補助記憶装置１１８で記憶させることができる。結果として、補助記憶装置１１８を対象とするＬＢＡのための今後の読み込み要求は、ＬＢＡと関連付けられるデータを適切に受けとる。補助記憶装置１１８上に無事に記憶されたことを判定した後、バックアップエンジン３１４は、記憶ユニットを破棄可能としてマークすることができる。
【００７９】
いくつかの実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４上でバックグラウンド処理として作動する。したがって、バックアップエンジン３１４は、低い優先度で実行され、ソリッドステート記憶デバイス１１４上の予備のサイクルおよび帯域幅を消費するのみである可能性がある。いくつかの実施形態において、キャッシュコントローラ３１２は、バックアップエンジン３１４の優先度を高める、あるいはそれ以外でバックアップエンジン３１４をフォアグラウンドへ移すことができる。いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が目標とする占有量閾値に達する際、バックアップエンジン３１４の優先度を高める。キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が最大占有閾値に近づくにつれて、キャッシュコントローラ３１２の優先度をさらに高め得る。いくつかの実施形態において、キャッシュコントローラ３１２は、バックアップエンジン３１４に、ソリッドステート記憶デバイス１１４が最大占有閾値に達する時点で、ソリッドステート記憶デバイス１１４内において破棄可能としてマークされるユニットがない場合、またはソリッドステート記憶デバイス１１４内において破棄可能としてマークされるユニットが不十分な数存在する場合、最高の優先度を与える。
【００８０】
いくつかの実施形態において、バックアップエンジン３１４は、最古のデータと関連付けられるソリッドステート記憶デバイス１１４内のユニットから開始し、図９に関連してさらに詳しく記載されるバックアップ操作を行うソリッドステート記憶デバイス１１４内のユニットを通して年代順に進行する。上述のように、バックアップエンジン３１４は、破棄可能性インジケータに対応するステータスにかかわらず、バックアップメタデータ１１７内に無効としてマークされる記憶ユニットと関連付けられるデータをバックアップしない可能性がある。記憶ユニットと関連付けられるデータが補助記憶装置１１８内に記憶される時点で、バックアップエンジン３１４は破棄可能性インジケータを破棄不可能から破棄可能へ変更するようメタデータ１１７を更新する。バックアップエンジン３１４は、破棄可能性インジケータを変更する前に、データが補助記憶装置１１８内に無事に記憶されたことを確認するために補助記憶装置１１８に対して待機することができる。いくつかの実施形態において、バックアップエンジン３１４は、グルーマー３１０に対し、ソリッドステート記憶デバイス１１４の特定の記憶領域がバックアップされたこと、ならびに破棄可能であることを示すことができる。関連する実施形態において、バックアップエンジン３１４は、グルーマー３１０に対し記憶領域の年代を示し得、それによりグルーマー３１０が記憶領域をいずれのさらなるデータの移動もなしに再生することを可能にする。
【００８１】
メタデータ１１７は、ソリッドステート記憶デバイス１１４の記憶ユニット内におけるデータの年代を追跡するために、インジケータ（例えば、ログ）を含むことができる。メタデータは、データが特定の記憶ユニットへ書き込まれたとき、および／またはデータが特定の記憶ユニットから読み込まれたときに関するインジケータを含むことができる。参照することにより本明細書に組み込まれる、２００７年１２月６日に申請されたＤａｖｉｄ  Ｆｌｙｎｎらに対する「Ａｐｐａｒａｔｕｓ，  Ｓｙｓｔｅｍ，  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｍａｎａｇｉｎｇ  Ｄａｔａ  Ｕｓｉｎｇ  ａ  Ｄａｔａ  Ｐｉｐｅｌｉｎｅ」と題される米国特許出願第１１／９５２，０９１号は、ソリッドステート記憶デバイス内にデータを連続的に記憶するアプローチを説明する。このようなデバイスにおいて、データが記憶ユニット内に記憶される順、したがって、それらの記憶ユニットと関連付けられるデータの年代は、ほとんどの場合、記憶デバイス内のデータのシーケンスから得られる。上記アプリケーションにおいて記載されるようにソリッドステート記憶デバイス１１４がデータを連続的に記憶する実施形態において、キャッシュコントローラ３１２は、ユニットがソリッドステート記憶デバイス１１４内に記憶されている順、および／または記憶ユニットの記憶区分と関連付けられるシーケンスインジケータからデータの年代に関する情報を導き出すことができる。そのような実施形態において、キャッシュ管理装置１３０は、メモリおよび書き込みが発生した際に追跡するための分離ログを維持することの計算における関連コストなしに、データの年代を導き出すまたは見積もることができる。
【００８２】
いくつかの実施形態において、メタデータ１１７は、ソリッドステート記憶デバイス１１４の特定のユニット内におけるデータ上の読み込み数を追跡するのに使用することができる。メタデータ１１７はまた、いつそれらの読み込みが発行されたかのインジケータを含むこともできる。このメタデータ１１７は、ソリッドステート記憶コントローラ１１５、グルーマー３１０、またはソリッドステート記憶デバイス１１４の他のプロセスによって維持することができる。キャッシュコントローラ３１２は、特定の記憶ユニットの最後の読み込みが発行されたのがいつか、（最も長い間使用されていない記憶ユニットを判定する）、追跡するためにメタデータ１１７にアクセスすることができる。代替として、またはさらに、キャッシュコントローラ３１２は、記憶ユニットアクセスパターンを追跡するためにメタデータ１１７を使用することができ、特定のユニットがホットまたはコールドデータを含んでいるかどうかを判定する際に、アクセスの頻度またはタイミングを考慮に入れることができる。
【００８３】
図４は、記憶クライアント（例えば、ファイルシステム２１０）と、キャッシュデバイスの機能を果たすソリッドステート記憶デバイス１１４と、補助記憶装置１１８の機能を果たすハードディスクドライブとの間の相互作用における例示的実施形態を示す。他の媒体との本システム上の他の変形も、ほかの実施形態で実装することができる。
【００８４】
ファイルシステム２１０が、（例えば、ファイルとして）永続記憶装置で記憶されるべきデータを有する場合、それは使用する１つ以上の適正なＬＢＡを一般的に決定する。ファイルシステム２１０は、関連付けられるデータを持たない利用可能なＬＢＡのプールから１つのＬＢＡを選択することができる。例えば、ファイルシステム２１０がデータＤを書き込む場合、ファイルシステムはデータＤに対してＬＢＡ０のような１つのＬＢＡを選択する。ファイルシステムは、ソリッドステート記憶デバイス１１４の機能を果たすソリッドステート記憶デバイスへデータＤを書き込む。いくつかの実施形態において、上述のように、ファイルシステム２１０は、ソリッドステート記憶デバイス１１４によって提示される論理空間と情報をやり取りし、ソリッドステート記憶デバイス１１４の存在を認識しない。
【００８５】
ソリッドステート記憶デバイスは、初期化され使用できる状態の記憶ユニット４０２を有する。ソリッドステート記憶デバイス１１４は、ＬＢＡとソリッドステート記憶デバイス１１４上の記憶ユニットと関連付けるメタデータを記憶することができる。記憶ユニット４０２は、ソリッドステート記憶デバイス１１４上でアドレス指定可能であり得る、いくつかの実施形態において、記憶ユニット４０２のアドレスは、物理ブロックアドレス（「ＰＢＡ」）である。具体的な実施形態において、ソリッドステート記憶デバイス１１４には、ＰＢＡに対するＬＢＡの１対１のマッピングが存在する。
【００８６】
メタデータ１１７において、記憶ユニット４０２は、有効性インジケータ（「有効」列によって表される）および破棄可能性インジケータ（「破棄」列によって表される）と関連付けることができる。いくつかの実施形態において、メタデータは、「まばら」であってもよく、有効データが存在するエントリのみを含む。したがって、有効性インジケータは、メタデータ１１７内に含められるかどうかから推測することができる（例えば、ＬＢＡおよび／または記憶ユニットがメタデータ内にある場合、記憶ユニットが有効データを含む、さもなければ、記憶ユニットが無効データを含む）。いくつかの実施形態において、記憶ユニット４０２は、記憶ユニット４０２に対する物理アドレス（例えば、ＰＢＡ）を鍵として使用して（例えば、上述の逆インデックス）有効性インジケータおよび破棄可能性インジケータへマップすることができる。
【００８７】
ソリッドステートソリッドステート記憶デバイス１１４が、ファイルシステム２１０から書き込み要求を受け取る際、ソリッドステートソリッドステート記憶デバイス１１４は、要求内で参照されるデータが記憶される初期化されたユニット（記憶ユニット４０２等）を選択する。その要求は、データを含むことができ、データの一部を含んでもよく、および／または実質的にデータがない場合がある。上述のように、記憶ユニット４０２の選択は、逐次的書き込みの機構に従って行われ得る。例えば、メタデータ１１７は、「次の」利用可能な記憶ユニットを参照する１つ以上の付加ポイント（示されない）を維持することができる。データがソリッドステート記憶デバイス１１４に書き込まれると、付加ポイントは、ソリッドステート記憶デバイス１１４の次の記憶ユニットへ逐次的に増加され得る。この逐次的な書き込みは、とりわけ、磨耗レベリングの利点を提供することができ、書き込み増幅（ｗｒｉｔｅ  ａｍｐｌｉｆｉｃａｔｉｏｎ）を低減させることができる。
【００８８】
ソリッドステート記憶デバイス１１４は、選択された記憶ユニット４０２に記憶要求のデータ（例えば、論理アドレスＬＢＡ０およびデータＤ）を記憶し、それに応じてメタデータ１１７を更新する。メタデータ１１７を更新することは、ＬＢＡ０を記憶ユニット４０２の参照（例えば、物理アドレス）と関連付けるようにインデックス４１０を更新することを含んでもよい。更新することは、Ｂツリーへの葉節点を追加することまたは他の順マップデータ構造を含んでもよい。エントリは、高速かつ効率的なＬＢＡ対記憶ユニットの関連付けを可能にするため、ＬＢＡ（ＬＢＡ０）によってインデックス付けされてもよい。
【００８９】
メタデータ１１７を更新することは、記憶ユニット４０２のための有効性および破棄可能性インジケータを設定することをさらに含むことができる。これらの操作は、図４の「ＳＳＤイベントの行を追加する」という列で表され、それは論理アドレスＬＢＡ０がデータ「Ｄ」（順および／または逆インデックスで）と関連付けられ、記憶ユニット４０２の有効性インジケータを「１」（例えば、有効）へ設定し、破棄可能性インジケータを「０」（破棄不可能）へ設定することを示す。破棄可能性インジケータは、データＤが補助記憶装置（例えば、ハードディスクドライブ）上でバックアップされていないため「０」（破棄不可能）に設定され、ハードディスクドライブへバックアップすることなく、ソリッドステート記憶デバイス１１４からデータＤを除去すると、データの損失および／または破損をもたらすこととなる。
【００９０】
図４で示されるように、クライアント（例えば、ファイルシステム２１０）は、データＤを修正することができる。更新されたデータは、Ｄ’によって表される。更新は、データＤを修正する（またはデータＤに対する修正をもたらす別の操作を行う）ファイルシステム２１０（またはいくつかの他の実体）を含むことができる。ファイルシステム２１０は、ＬＢＡ０で修正データＤ´を記憶するための記憶要求を発行することができる。いくつかの実施形態において、ファイルシステム２１０は、ソリッドステート記憶デバイス１１４が存在するということを認識しているが（非透過キャッシュ）、他の実施形態においては、ファイルシステム２１０は、ソリッドステート記憶デバイス１１４を認識せず、更新要求はソリッドステート記憶デバイス１１４によって透過的に処理される。
【００９１】
記憶要求に応答して、ソリッドステート記憶デバイス１１４は、修正データＤ’をソリッドステート記憶媒体へ逐次的に書き込むことができる。上述のように、逐次記憶は、ソリッドステート記憶デバイスの異なるユニットにおいて、修正データＤ’を「位置をずらせて」記憶することを含むことができる。逐次的な書き込みは、とりわけ磨耗レベリングの利点を提供することができ、書き込み増幅を低減させることができる（例えば、同一の記憶ユニット４０２上で修正データＤ’を記憶することは、記憶ユニット４０２の記憶区分を削除すること、および記憶区分上の他の有効データを伴ってＤ’を書き込むことを必要とし得る）。
【００９２】
修正データＤ’を記憶することは、ソリッドステート記憶デバイス１１４が修正データＤ’を記憶するための「次の」記憶ユニット（記憶ユニット４０４）を選択することを含むことができる。この選択は、上述の逐次的な記憶装置の機構に従って行うことができる（例えば、１つ以上の付加ポイントでの「次の」記憶ユニットであり得る）。記憶区分４０２に関するメタデータ１１７は、データがもはや有効ではなく、破棄可能である（または気にしなくてよい状態にある）ことを示すために更新することができる。記憶ユニットに対して論理アドレスを関連付けるメタデータ１１７は、ＬＢＡ０を選択された記憶区分４０４と関連付けるために更新することができる。さらに、選択された記憶ユニット４０４に関するメタデータは、記憶ユニット４０４が有効、破棄不可能データを含むことを示すために更新することができる。図４は、更新１のデータＤ’が、記憶ユニット４０４へ書き込まれ、前と同じく、有効性インジケータは、ユニット４０４のデータＤ’が有効かつ破棄不可能であることを示すために変更されることを示す。
【００９３】
グルーマー３１０は、ある時点で、ユニット４０２の有効性インジケータを検査し、無効に設定されていることを確認し、ユニット４０２上でガーベジコレクション操作（ＧＣ１）を行うことができる。ガーベジコレクション操作は、記憶ユニット４０２を初期化状態に戻し、その時点でユニット４０２はデータを記憶するために再び使用することができる。
【００９４】
図４は、ユニット４０４のデータＤ’上でバックアップ操作（ＢＵ１）を行うソリッドステート記憶デバイス１１４をさらに示す。いくつかの実施形態において、バックアップエンジン３１４は、バックアップを行う。バックアップエンジン３１４は、データＤ’をＬＢＡ０の論理アドレスおよびデータ値Ｄ’でハードディスクドライブ内で記憶させるようにする。バックアップエンジン３１４は、ハードディスクドライブ宛にデータＤ’とともに、ＬＢＡ０に宛てたアドレスを取る書き込み要求を送ることができる。いくつかの実施形態において、バックアップエンジン３１４は、破棄可能性インジケータを破棄不可能から破棄可能（「１」へ）変更する前に、ハードディスクドライブがＬＢＡ０でＤ’を首尾よく保存したという確認を待つ。ハードディスクドライブは、データＤ’のために、ＬＢＡと物理アドレスとの間の独自の内部関連付けを（例えば、特定のＣＨＳに対してのＬＢＡ０のような）行うことができる。
【００９５】
いくつかの実施形態において、バックアップ操作は、ファイルシステムに対して透過的である様態で起こる、すなわち、ファイルシステムは、データＤ’が今や、ソリッドステート記憶デバイス１１４とハードディスクドライブの両方に存在するということを認識しない。同様に、ＧＣ１のようなグルーミング操作は、ファイルシステムに対して透過的に行うことができる。
【００９６】
図４は、データをＤ´´に変更するＬＢＡ０のためにファイルシステム２１０（または他の実体）によって生じるさらなる更新２を示す。ユニット４０２と同様に、それに応答して、ソリッドステート記憶デバイス１１４はユニット４０４をメタデータ１１７内において無効としてマークする。ユニット４０４が無効として識別されるため、破棄可能性インジケータは変更されてもよいし変更されなくてもよく、破棄可能性インジケータのステータスは、ユニット４０４がグルーマー３１０によってゴミ集めされる（ＧＣ２に示される）、ユニット４０４は有効性マップおよび破棄可能性マップ内のエントリとともに、ユニット４０４が新しいデータを記憶するために再び使用されるように初期化されるので、意味を成さなくなる。
【００９７】
さらに更新２は、ＬＢＡ０およびデータＤ´´を、上記のように有効に設定された有効性インジケータを有する新しいユニット４０６へ、逐次的に書き込ませる。データＤ´´がハードディスクドライブへ移動されていないため、でなければ、ハードディスクドライブ内にないため、破棄可能性インジケータは破棄不可能に設定される。更新２は、メタデータ１１７のインデックス４１０を、ＬＢＡ０を記憶ユニット４０６と関連付けるために修正することをさらに含んでもよい。バックアップエンジン３１４が、示されるようにデータＤ´´をハードディスクドライブへフラッシュする時点（ＢＵ２）で、破棄可能性インジケータは破棄可能に変更される。
【００９８】
ファイルシステムは、さらに、ＴＲＩＭコマンドをソリッドステート記憶デバイス１１４として機能しているソリッドステート記憶デバイスへ発行することができる。ＴＲＩＭコマンドは、ファイルシステムが、どのデータ記憶ユニット（論理ブロックアドレス）が使われていないかを、ソリッドステート記憶デバイス（ソリッドステート記憶デバイス１１４等）へ伝えることを可能にする。これは、ソリッドステート記憶デバイス１１４がどの記憶ユニットが使用中であるか、およびどれが空いているかを知ることを確実にし、ソリッドステート記憶デバイスが、ファイルシステムが必要ないおよび／または無効であると認識するデータを保持しないことを確実にする。ＴＲＩＭコマンド仕様は専門委員会（Ｔｅｃｈｎｉｃａｌ  Ｃｏｍｍｉｔｔｅｅ）Ｔ１３が主唱するＡＴ  Ａｔｔａｃｈｍｅｎｔ（「ＡＴＡ」）インターフェース規格の一部として現在標準化されている。
【００９９】
図４に示されるように、いくつかの実施形態において、ファイルシステムは、ＬＢＡ０（テキストファイル等）と関連付けられるデータＤ´´が削除されていることを判定し、ＬＢＡ０を利用可能なプールに追加する。ファイルシステム（または他の実体）は、ＴＲＩＭコマンドを含む記憶要求をソリッドステート記憶デバイス１１４へ送ることができる。ソリッドステート記憶デバイス１１４は、ＴＲＩＭコマンドを受け取り、いくつかの実施形態においては、データを保留している影響されるユニット（ユニット４０６等）を無効としてマークする無効ＳＳＤイベントで応答する。ソリッドステート記憶デバイス１１４は、次いで、その後の時点で、ユニット４０６を復旧するためにガーベジコレクション操作ＧＣ３を将来の使用のために実行することができる。ＴＲＩＭは、ＬＢＡ０のエントリを除去するためにメタデータ１１７のインデックス４１０を更新することをさらに含んでもよい（例えば、０を表す葉節点をＢツリーから除去する）。
【０１００】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４として機能しているソリッドステート記憶デバイスは、ＴＲＩＭをサポートしない場合がある。いくつかの実施形態においては、ソリッドステート記憶デバイス１１４および補助記憶装置１１８の両方ともが、ＴＲＩＭをサポートすることができる。そのような実施形態において、ソリッドステート記憶デバイス１１４は、ＴＲＩＭコマンドを実行することができ、次いで図４に示されるようにＴＲＩＭコマンドを補助記憶装置１１８へ渡すことができる。他の実施形態において、ソリッドステート記憶デバイス１１４および補助記憶装置１１８のうちの１つはＴＲＩＭをサポートすることができるが、他方はサポートしない場合がある。そのような実施形態において、ソリッドステート記憶デバイス１１４および補助記憶装置１１８は、それらがＴＲＩＭコマンドを無視するように構成することができる。他の実施形態において、ＴＲＩＭをサポートするデバイスは、ＴＲＩＭコマンドを実行することができ、他方からＴＲＩＭコマンドを隠すことができる。
【０１０１】
関連する実施形態において、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８内のＬＢＡがトリムされているというインジケータを維持することができ、ＨＤＤがＴＲＩＭをサポートしないにもかかわらず、クライアントファイルシステムに正確に応答するためにこの情報を利用することができる。したがって、例えば、ハードディスクドライブ上のトリムされたＬＢＡ内のデータにアクセスすることを試みる操作は、トリムされたＬＢＡのデータがハードディスクドライブ上に依然として存在するにもかかわらず、ソリッドステート記憶デバイス１１４によって遮られる。ソリッドステート記憶デバイス１１４は、さらに、ＨＤＤ上のＬＢＡに関連するデータを上書きし、あるいは別様に、その不適切な部分を削除し、データが復旧可能でないことを確実にすることができる。ソリッドステート記憶デバイス１１４は、ファイルシステムおよびＨＤＤの観点からすれば、これらの操作を透過的に行うことができる。
【０１０２】
図５は、読み込みアクセス要求を処理する本システムの１つの例を示す。図５に示されるように、ファイルシステムは、ＬＢＡ１を、データＡを保持するように割り当て、このデータが記憶されるようにしている。図５は、データＡがハードディスクドライブのＬＢＡ１と関連付けられるが、ソリッドステート記憶デバイス１１４において不在であることを示す。ファイルシステム２１０は、ＬＢＡ１におけるデータの読み込みを発行する。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、読み込み要求を受信し、ＬＢＡ１と関連付けられるデータＡがソリッドステート記憶デバイス１１４内に記憶されていないことを判定する（図５に示されるようにミスとして解釈される）。いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、ＬＢＡ１と関連付けられるユニットでデータを読み込むことを試みることにより、データＡがソリッドステート記憶デバイス１１４内にないことを判定する。ソリッドステート記憶デバイス１１４は、例えば、メタデータ１１７、具体的にはインデックス４１０を使用してＬＢＡ１にアクセスすることを試みることができる。インデックス４１０内にＬＢＡ１に対するエントリがない場合、ソリッドステート記憶デバイス１１４は、エラーを生成させ得、それはキャッシュミスとして解釈され得る。メタデータ１１７はＬＢＡ（Ｂツリーデータ構造内において）によってインデックス付けすることができるため、この判定は迅速かつ効果的になされる。
【０１０３】
キャッシュミスに応答して、ソリッドステート記憶デバイス１１４は、ハードディスクドライブへ読み込み要求をリダイレクトし、これはＬＢＡ１においてデータＡにアクセスする。データＡはハードディスクドライブから読み出され、ファイルシステム２１０に戻される。ソリッドステート記憶デバイス１１４のキャッシュコントローラ３１２は、さらに、選択記憶ユニット５０２内にデータＡをＬＢＡ１の論理アドレスとともに記憶するために、投入ＳＳＤイベント（投入１）を実行する。ソリッドステート記憶デバイス１１４は、インデックス４１０内の記憶ユニット５０２にＬＢＡ１を関連付けるために、メタデータ１１７を更新することができる。
【０１０４】
図５に示されるように、読み込み２に応答して、ソリッドステート記憶デバイス１１４は、読み込み２がキャッシュヒットとなっているので、ユニット５０２からデータＡを読み出す。ソリッドステート記憶デバイス１１４は、データＡをファイルシステム２１０へ読み込み要求２への応答として返却する。ソリッドステート記憶デバイス１１４は、速くかつ効果的に、ＬＢＡ１に対応するデータがソリッドステート記憶デバイス１１４上で利用可能であることを判定することができ、メタデータ１１７（インデックス４１０）を使用してデータを含む記憶ユニット５０２を特定することができる。
【０１０５】
データＡが投入１操作の一部としてユニット５０２内に記憶される場合、ソリッドステート記憶デバイス１１４は、データＡがハードディスクドライブ内のＬＢＡ１内に適切に記憶され、それと関連付けられていることを反映するために、有効性インジケータを有効に設定し、さらに破棄可能性インジケータを破棄可能に設定する。したがって、データＡは、ソリッドステート記憶デバイス１１４からデータの破損なしに除去することができる。例えば、ソリッドステート記憶デバイス１１４上で作動するキャッシュ管理装置は、排除ポリシーを適用することができ、（例えば、アクセスパターン、グルーミング考慮等に基づいて）データＡが排除されるべきであることを判定することができる。破棄可能性インジケータがメタデータ１１７内において「１」に設定されているため、排除に先立つユニット５０２上のバックアップなしに、排除が発生し得る。
【０１０６】
図５は、ＬＢＡ１と関連付けられるデータをＡからＡ´へ変更する更新１を発行するファイルシステム２１０をさらに示す。前述のように、ソリッドステート記憶デバイス１１４は、無効性マップを使用してユニット５０２を無効としてマークし、グルーマー３１０は、将来使用するために利用可能とするようにユニット５０２を初期化するために、ガーベジコレクション操作ＧＣ１を行う。さらに、ソリッドステート記憶デバイス１１４は、ＬＢＡ１およびデータＡ´を新しいユニット５０４内に記憶し、無効性インジケータを有効に設定し、破棄可能性インジケータを破棄不可能に設定する。メタデータ１１７のインデックス４１０は、上述のようにＬＢＡ１を記憶ユニット５０４に関係付けるように更新することができる。ソリッドステート記憶デバイス１１４は、バックアップ操作ＢＵ１の間、データＡ´をハードディスクドライブへ記憶し、破棄可能性インジケータを破棄可能に設定する。
【０１０７】
図５は、排除ＳＳＤイベント（排除１）においてデータＡ´がソリッドステート記憶デバイス１１４から排除されることをさらに示す。いくつかの実施形態において、排除１操作は、ファイルシステムに対して透過的である。ソリッドステート記憶デバイス１１４は、キャッシュコントローラ３１２がデータがコールドになったことを判定する場合、例えば、ファイルシステム２１０が所定の期間の間データＡ´を読み込んでいない場合、データＡ´を排除することができる。いくつかの実施形態において、キャッシュコントローラ３１２は、有効性インジケータを無効に設定することによりデータＡ´を排除する。排除は、インデックス４１０内のＬＢＡ１と記憶ユニット５０４との間の関連を除去することをさらに含むことができる。除去はＬＢＡ１のデータＡ´がソリッドステート記憶デバイス１１４上にもはや記憶されていないことを示すことができる。
【０１０８】
次いで、ソリッドステート記憶デバイス１１４は、ユニット５０４を初期状態に戻すよう設定するためにユニット５０４をガーベジコレクトすることができる。他の実施形態において、ソリッドステート記憶デバイス１１４は、ユニット５０４を排除１で示される中間状態にする代わりに、排除プロセスの一部としてユニット５０４を直接的にガーベジコレクトする。他の実施形態において、グルーマー３１０は、以下により詳細に説明されるように、データＡ´が有効としてマークされるにもかかわらずグルーミング操作の一部としてデータＡ´を排除する。
【０１０９】
図６は、補助記憶装置１１８のためのソリッドステート記憶デバイス１１４として作動するように記憶デバイスを構成するための方法６００のいくつかの実施形態を示す。いくつかの実施形態において、方法６００のステップは、ソリッドステート記憶デバイス、ソリッドステート記憶媒体、通信インターフェース、プロセッサ、メモリ等のような特定の機械構成要素と結び付けられることができる。機械が方法６００を実装させるよう構成された機械可読命令は、不揮発性メモリ、ディスク、光媒体等のような持続性機械可読記憶媒体上に記憶されてもよい。
【０１１０】
いくつかの実施形態において、クライアント１１０ａ〜ｃは、ファイルサーバ２１０を通してソリッドステート記憶デバイス１１４と通信する。しかしながら、本開示は、この点に限定されず、クライアント１１０ａ〜ｃは、直接的におよび／またはデータベースサーバ、ウェブサーバ、記憶プロトコル等の他のプロセスもしくは実体を通してソリッドステート記憶デバイス１１４と通信することができる。方法６００は、ユーザがソリッドステート記憶デバイス１１４を本システム１００において利用可能にすし６０２、補助記憶装置１１８を本システム１００において利用可能にする６０４ことから開始する。
【０１１１】
いくつかの実施形態において、ステップ６０６において、ソリッドステート記憶デバイスは、補助記憶装置１１８と同じ物理記憶容量を有する論理アドレス空間を提供するように構成することができる。補助記憶装置１１８が、ソリッドステート記憶デバイス１１４の物理記憶容量より大きい物理記憶容量を有する場合、ソリッドステート記憶デバイス１１４は、ソリッドステート記憶デバイス１１４がソリッドステート記憶デバイス１１４上で物理的に利用可能なものより大きい論理アドレス空間を提示することができるように、まばらなアドレスをサポートするよう構成されてもよい。例えば、ソリッドステート記憶デバイス１１４は、ＦＵＳＩＯＮ＿ＳＰＡＲＳＥＦＳ＿ＳＵＰＰＯＲＴフラグセットで構築されてもよい。いくつかの実施形態において、ステップ６０６の構成は、ソリッドステート記憶デバイス１１４および補助記憶装置１１８の両方の物理記憶容量を上回る論理アドレス空間を提示するソリッドステート記憶デバイスを含むことができる。
【０１１２】
ステップ６０８において、ソリッドステート記憶デバイス１１４および補助記憶装置１１８の両方が本システム内に存在する状態で、ソリッドステート記憶デバイス１１４は、補助記憶装置１１８のためのキャッシュとしての機能を果たすよう構築されてもよい。方法６００は、リッドステート記憶デバイス１１４上でキャッシュとして使用するために利用可能である物理空間の最大量を定義する最大の占有量閾値６１０を設定することも含むことができる。最大の占有量閾値は、外部の実体（例えば、管理者）によってソリッドステート記憶デバイス１１４に提供されてもよく、またはキャッシュ管理装置１３０自体が適正な閾値を決定することができる。
【０１１３】
ステップ６１２において、ソリッドステート記憶デバイス１１４に対する目標とする占有量閾値は、上述のように（例えば、実体および／またはソリッドステート記憶デバイス１１４によって）設定することができ、方法６００は終了する。いくつかの実施形態において、キャッシュ管理装置１３０は、ソリッドステート記憶デバイス１１４内の占有量を目標の占有量閾値未満に保つよう試みる。キャッシュ管理装置１３０は、ソリッドステート記憶デバイス１１４が対象の占有量閾値を上回ると、キャッシュ排除を開始することによってそれを行うことができる。
【０１１４】
図７は、ソリッドステート記憶デバイス上でデータをキャッシングするための方法７００の例示的な実施形態を示す。上述のように、方法７００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０１１５】
方法７００は、７０２ソリッドステート記憶デバイス１１４がＬＢＡ等のデータのためのアドレスを含む読み込み要求を受け取ることで開始する。ステップ７０４で、方法７００は、そのアドレスと関連付けられたデータがソリッドステート記憶デバイス１１４上で利用可能かどうかを判定する。判定は、ソリッドステート記憶デバイスによって維持されたメタデータ１１７、具体的には、論理アドレスと関連する記憶ユニットとの関連を含むインデックスを使用して行われ得る。アドレスがインデックスに存在する場合、方法７００は、データが利用可能であると判定することができ、流れは、ステップ７０６へ続くことができ、そうでなければフローはステップ７１０へ続くことができる。
【０１１６】
要求データは、ステップ７０６において１つ以上の記憶ユニット上でアクセスされ得る。記憶ユニットは、上述のように、インデックス内で特定され得る。ステップ７０８において、記憶操作と関するメタデータが、データアクセスを反映するように更新され得る。メタデータは、「ホット」および／または「コールド」論理アドレス等のアクセスパターンを決定すること、アクセス時間を判定すること等のために使用することができる。いくつかの実施形態において、記憶メタデータは、記憶区分の復旧操作を行うためにグルーマー３１０に対して、および／またはキャッシング操作（例えば、排除ポリシー）を管理するためにキャッシュ管理装置１３０に対してアクセス可能であってもよい。フローはその後終了することができる。
【０１１７】
ステップ７１０において、方法７００は、読み込み要求を補助記憶装置１１８内のアドレスへリダイレクトする。キャッシュコントローラ３１２は、データを読み込み７１２、読み込み要求を生み出した実体へそのデータを戻す。
【０１１８】
キャッシュコントローラ３１２は、また、データをソリッドステート記憶デバイス１１４へ挿入し７１４、データを特定したアドレスに（インデックスまたは他のメタデータにおいて）関連付ける。いくつかの実施形態において、データは、逐次的に、および／または図８に関連して説明された書き込み方法に従って、書き込まれる。いくつかの実施形態において、ソリッドステート記憶デバイス１１４に空いている記憶ユニットがない場合、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４へデータを挿入しない。
【０１１９】
キャッシュコントローラ３１２は、データがソリッドステート記憶デバイス１１４から除去されるまで、今後の読み込み要求がソリッドステート記憶デバイス１１４からデータを読み出すように、メタデータ（インデックス）を更新することができる。さらに、キャッシュコントローラ３１２は、メタデータ１１７を更新して、データを含む記憶ユニットが有効かつ破棄可能であることを示すことができる。ステップ７１６は、キャッシュコントローラ３１２がロギングメタデータをいつデータがソリッドステート記憶デバイス１１４に挿入されたかを示すように更新することをさらに含み、方法７００は終了する。他の実施形態において、ソリッドステート記憶デバイス１１４は、データを逐次的に記憶し、データの年代はソリッドステート記憶デバイス１１４内のその位置から導き出される。
【０１２０】
図８は、ソリッドステート記憶デバイス上のデータをキャッシングする方法８００の例示的な実施形態を示す。上述のように、方法８００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０１２１】
キャッシュ管理装置１３０は、ソリッドステート記憶デバイス１１４を書き戻しキャッシュとして構成することができ、そこではデータがまずクライアントによってソリッドステート記憶デバイス１１４に書き込まれ、後に補助記憶装置１１８へ移動される。方法８００は８０２キャッシュ管理装置１３０が書き込み要求を受け取ることで開始する。書き込み要求は、永続記憶装置に記憶されるであろうデータを参照することができる。要求は、このデータを含んでもよく、および／または実質的にデータを含まなくてもよい。書き込み要求は、論理アドレス（例えば、ＬＢＡ）と関連付けられてもよい。
【０１２２】
キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４上に空き領域があるかどうかを判定する８０４。キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４がその最大容量の閾値を上回らないことを確実にするためにこのチェックを行う。いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４へデータを書き込むことに先立って、判定８０４を行う。他の実施形態においては、上述のように、判定８０４の頻度は変動する。
【０１２３】
判定は、ソリッドステート記憶デバイス１１４によって維持されるメタデータにアクセスすることを含み得る。メタデータは、論理ブロックアドレスを記憶ユニットと関連付けるインデックスを含んでもよい。有効データによって占有されている記憶ユニットは記憶に対して利用可能ではなく、一方で占有されていない記憶ユニットは使用に対して利用可能であり得る。メタデータは、さらに、ソリッドステート記憶デバイス１１４の記憶ユニットを各有効性／破棄可能性インジケータに関連付ける逆インデックスを含んでもよい。無効および／または破棄可能である記憶ユニットは、記憶のために利用可能であるとみなされ得る。
【０１２４】
ソリッドステート記憶デバイス１１４内に空き領域がある場合、キャッシュコントローラ３１２はデータをソリッドステート記憶デバイス１１４のユニットへ書き込み８０６、そのユニットを破棄不可能としてマークする。ステップ８０６の書き込みは、上述のような逐次的な記憶操作を含んでもよい。逐次的な書き込みは、データを記憶するために（例えば、付加ポイントまたは他の逐次インジケータを使用して）記憶ユニットを選択すること、選択される記憶ユニット上にデータを書き込むこと、書き込み要求の論理アドレス（１つまたは複数）を選択される記憶ユニットに関連付けるようにソリッドステート記憶デバイス１１４のメタデータを更新すること等を含むことができる。
【０１２５】
バックアップエンジン３１４は、次いで、データが補助記憶装置１１８内に記憶されるように、データを補助記憶装置１１８へバックアップ８０８することができる。記憶ユニットのバックアップは、記憶ユニットが破棄可能であることを示すようにソリッドステート記憶デバイスを更新することを含んでもよい。バックアップエンジン３１４は、選択された優先度レベルで作動することができ、したがって、データを補助記憶装置１１８へバックアップ８０８するのに良いタイミングまで待機することができる。ステップ８０８に続いて、方法８００は終了することができる。
【０１２６】
ソリッドステート記憶デバイス１１４上にデータのための空間が無い場合、キャッシュ管理装置１３０は、キャッシュ管理装置１３０がソリッドステート記憶デバイス１１４内にデータのための場所を用意するまで、書き込み要求を一時停止８１０する。他の実施形態において、キャッシュ管理装置１３０は、データを補助記憶装置１１８に書き込ませることができ、ソリッドステート記憶デバイス１１４内に十分な空間が生み出されると読み込み操作を行い、その結果、ソリッドステート記憶デバイス１１４へデータが挿入されることになる。
【０１２７】
書き込み要求を一時停止８１０した後、キャッシュ管理装置１３０は、（メタデータ１１７を使用して）ソリッドステート記憶デバイス１１４内に破棄可能および／または無効としてマークされる記憶ユニットがあるかどうかを判定する８１２ことができる。このチェックは、さらに、有効／破棄可能メタデータに対する「気にしなくて良い」状態を評価することを含んでもよい。いくつかの実施形態において、破棄不可能な記憶ユニットは、無効としてマークされてもなお保有されることがある（例えば、スナップショット、バックアップ等のために保有されることがある）。破棄可能な記憶ユニットがある場合は、いくつかの実施形態において、キャッシュ管理デバイス１３０は、破棄可能であるユニットを見つけ８２０、それらをソリッドステート記憶デバイス１１４から排除し、戻り、ソリッドステート記憶デバイス１１４上の空間が利用可能かどうかを判定８０４する。キャッシュコントローラ３１２は、例えば、破棄可能である全てのユニットを無効としてマークすることができる。別の実施形態においては、グルーマー３１０は、破棄可能とマークされたユニット内のデータを保存することなくソリッドステート記憶デバイス１１４をグルームしてもよい。排除後にソリッドステート記憶デバイス１１４上に余地がある場合、データはソリッドステート記憶デバイス１１４に記憶される。
【０１２８】
ソリッドステート記憶デバイス１１４に破棄可能な記憶ユニットがない場合、キャッシュ管理装置１３０は、破棄可能性マップにおいて破棄不可能とマークされるキャッシュ内に記憶ユニットを見つけ８１４、それらのユニットを補助記憶装置１１８にバックアップする８１６ことができる。いくつかの実施形態において、キャッシュ管理装置１３０は、バックアップエンジン３１４の優先度を高めることによりこれを行う。データが補助記憶装置１１８に移動されると、キャッシュ管理装置１３０は、それらのユニットを破棄可能としてマーク８１８するようにメタデータ１１７を更新し、破棄可能であるユニットを見つけ８２０、それをソリッドステート記憶デバイス１１４から排除する。キャッシュ管理装置１３０が戻り、ソリッドステート記憶デバイス１１４上にデータを書き込むために空間が利用可能かどうかを再度判定する８０４。
【０１２９】
図９ａはソリッドステート記憶デバイス１１４の記憶ユニット９１４からユニット９２６を通してバックアップ操作を行っているバックアップエンジン３１４の例示的な実施形態を示す。図９ａは、関連する有効性インジケータ９３０ａ〜ｇおよび破棄可能性インジケータ９４０ａ〜ｇを有する各記憶ユニット９１４から９２６を示す。有効性インジケータ９３０ａ〜ｇおよび破棄可能性インジケータ９４０ａ〜ｇは、記憶ユニットの関連に対するキャッシュエントリを備えるマップ等のデータ構造によって、それぞれユニット９１４〜９２６と関連付けられる。図９ａは、初期状態におけるユニットを示し、図９ｂは、バックアップエンジン３１４がユニット９１４〜９２６を通して移動する際のユニットを示す。
【０１３０】
いくつかの実施形態において、ユニット９１４から９２６内のデータは、逐次的に書き込まれる。このような実施形態において、ユニット９１４から９２６は、ソリッドステート記憶デバイス１１４上に徐々に増加する物理アドレスを有する。例えば、ユニット９１４は、物理アドレス「０」を有し得、ユニット９１６は物理アドレス「１」を有する等であり得る。データが逐次的に書き込まれる場合は、データは最も低い利用可能な物理アドレスで書き込まれる。ファイルシステムは、データ「Ａ」をソリッドステート記憶デバイス１１４へ書き込み始める時、データ「Ａ」をユニット９１４へ物理アドレス０で書き込み、その後に次のデータ「Ｂ」をユニット９１６へ物理アドレス１で書き込む等である。
【０１３１】
そのような実施形態において、ソリッドステート記憶デバイス１１４上のデータの物理的構成を、どのデータが最古でどのデータが最新であるかを示すログとして使用することができる。例えば、ユニット９１４内に書き込まれたデータはユニット９２０内に書き込まれたデータより古いことを想定できる。他の実施形態において、ログは、ソリッドステート記憶デバイス１１４内のデータの年代を絶対的（つまり、タイムスタンプの使用を通じて）、またはソリッドステート記憶デバイス１１４内の他のデータと比較して、または双方の方法で特定するデータ構造である。いくつかの実施形態において、ソリッドステート記憶デバイス１１４上のデータの物理的構成が、ソリッドステート記憶デバイス１１４内のユニットの世代を決定するために、ログと併せて使用される。
【０１３２】
図９ｂに示されるように、いくつかの実施形態におけるバックアップエンジン３１４は、データを補助記憶装置１１８にフラッシュすることにより、ソリッドステート記憶デバイス１１４内でデータのバックアップを開始する。いくつかの実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内の最古のデータで始動し、最新の記憶ユニットに達するまでソリッドステート記憶デバイス１１４内の記憶ユニット９１４〜９２６を通して年代順に移動する。いくつかの実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内の記憶ユニット９１４〜９２６を通して逐次的に移動し、１つのユニット内のデータを補助記憶装置１１８へデータをバックアップし、次いで、物理アドレスを増加させて次のユニットへ移動することによってそれを行う。他の実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４によって維持されるメタデータ（例えば、逆インデックスおよび／またはログデータ構造）を参照することによって、ユニット９１４〜９２６を通して年代順に移動する。例えば、バックアップエンジン３１４は、逆インデックスまたはログ内における１つのユニットのためのエントリで始動し、データをバックアップし、次のエントリに移動し、そしてそれをログ全体が読み込まれるまで続けることができ、その時点でバックアップエンジン３１４は、構造の始めにループバックすることができる。
【０１３３】
いくつかの実施形態において、バックアップエンジン３１４は、まずメタデータ（例えば逆インデックスまたはログ）を使用して、特定のユニット９１４〜９２６に対してデータが有効であるか無効であるかを判定し、そのメタデータは、上述のように、有効性インジケータ９３０ａ〜ｇを備えることができる。この有効性インジケータ９３０ａ〜ｇが、無効に設定されている場合、バックアップエンジン３１４は、ユニット９１４〜９２６内のデータをバックアップしないことを選択し得る。例えば、図９ｂに示されるように、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内の最古ユニットであるユニット９１４で始動し、有効性インジケータ９３０ａを検査し、有効性インジケータが無効に設定されるかどうかを調べることができる。有効性インジケータ９３０ａが無効に設定されるため、バックアップエンジン３１４は、ユニット９１４と関連付けられるデータＡをバックアップすることなしに、次のユニット９１６へ移動する。破棄可能性インジケータ９４０ａは、ユニット９１４が無効と判断される場合は意味を成さないため、破棄可能性インジケータ９４０ａは、「気にしなくて良い」として表されることがある、すなわち、破棄可能性インジケータのステータスは、無効性インジケータがデータを無効であることを示す場合、バックアップエンジン３１４に対して無意味である。
【０１３４】
図９ｂにおいて、バックアップエンジン３１４は、次いで、データＢを有するユニット９１６を補助記憶装置１１８に記憶する。有効性インジケータはデータＢがまだ有効であることを示す。いくつかの実施形態において、データＢが有効であるとの判定の後、バックアップエンジン３１４は、次いで破棄可能性インジケータ９４０ｂを検査し、データＢが補助記憶装置１１８にバックアップされたかどうかを判定する。破棄可能性インジケータ９４０ｂが破棄可能に設定される場合は、バックアップエンジン３１４は、データＢが補助記憶装置１１８内に既に記憶されているため、補助記憶装置１１８にデータＢを記憶せずに次のユニット９１８に移動する。
【０１３５】
破棄可能性インジケータ９４０ｂが破棄不可能と設定される場合、バックアップエンジン３１４は、データＢを補助記憶装置１１８に記憶することができる。いくつかの実施形態において、バックアップエンジン３１４は、データＢに対して、補助記憶装置１１８へ向けた書き込み要求を開始する。いくつかの実施形態において、前に説明したように、データは、データおよびそのデータが関連付けられるＬＢＡの両方を含む。そのような実施形態において、バックアップエンジン３１４は、ＬＢＡをユニット９１６におけるデータから抽出し、データが補助記憶装置１１８内のそのＬＢＡに書き込まれることを要求することができる。
【０１３６】
図９ａは、初めに、ユニット９１６におけるデータＢが破棄不可能であることを示す。データＢが補助記憶装置１１８へ書き込まれる際、バックアップエンジン３１４は、図９ｂにおいて示されるように、破棄可能性インジケータ９４０ｂを破棄可能（図９ｂにおいて「１」）に変更するように、メタデータを更新する。いくつかの実施形態において、バックアップエンジン３１４は、破棄可能性インジケータを変更する前にデータＢが無事にバックアップされたという補助記憶装置１１８からの確認を待つ。いくつかの実施形態において、バックアップエンジン３１４が一定の期間内に確認を受け取らない場合、バックアップエンジン３１４は、データを補助記憶装置１１８へ保存することを再試行する。データＢが補助記憶装置１１８に無事にバックアップされ、破棄可能性インジケータ９４０ｂが破棄可能に設定されると、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４のユニット９１８等の次のユニットへ移動する。
【０１３７】
上で説明したように、バックアップエンジン３１４は、ユニット９１８内のデータＣが無効であると判定し得、したがって、データＣのバックアップなしに先へ移動することができる。バックアップエンジン３１４は、次いで、ユニット９２０内のデータＤをバックアップし、破棄可能性インジケータ９４０ｄを破棄可能に変更することができる。
【０１３８】
ある事例において、バックアップエンジン３１４は、ユニット９２４等の有効かつ破棄可能としてマークされるデータＣを伴うユニットと遭遇する可能性がある。破棄可能性インジケータ９４０ｆが破棄可能に設定されている（データＣが既にバックアップされたことを示している）場合、バックアップエンジン３１４は、データＣをバックアップすることなしに次のユニットに移動することができる。
【０１３９】
いくつかの実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内のユニット９１４〜９２６上を連続してスキャンする。他の実施形態においては、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内のユニット９１４〜９２６を通して反復を完了させ、第２の反復を開始する前に、ある期間待機する。いくつかの実施形態において、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４上においてバックグラウンドプロセスとして機能し、予備のサイクル（ＣＰＵサイクル、バスサイクル、または他のサイクルのどれか）が利用可能なである場合に作動する。バックアップエンジン３１４は、設定されたスケジュールを与えられてもよい。例えば、管理者はトラフィックが低い夜間等の間にバックアップエンジン３１４がバッキング操作を行うように、ソリッドステート記憶デバイス１１４を設定することができる。
【０１４０】
いくつかの実施形態において、バックアップエンジン３１４は、動作が求められる場所を判定するために有効性および破棄可能性インジケータを検索し、リソースが利用可能になった時に実行されるバックアップ活動およびコマンドをキューイングすることができる。例えば、バックアップエンジン３１４は、図９の論理を経るが、どのコマンドも実際には実行しない場合がある、より正確には、バックアップエンジン３１４は特定のユニットに対してどのような動作が必要かを判定し、その動作を一覧に追加し、そして次のユニットに移動する。このようにして、バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４上のユニットおよび関連するマップを通して進んで行きながら、動作の一覧を編成することができる。別のプロセスは、非同期的に動作および／またはコマンドを一覧から引き出し、それらを実行することができる。
【０１４１】
バックアップエンジン３１４は、記憶ユニットと関連付けられるメタデータ１１７に基づいて、バックアップ操作に優先度を与えることができる。例えば、メタデータ１１７は、破棄不可能データを含む記憶ユニットが、高いレベルの摩耗および／または高いエラー率を有することを示し得る。メタデータ１１７に基づいて、バックアップエンジン３１４は、識別される記憶ユニットのバックアップの優先度を高めることができる。優先度を高めることは、バックアップ操作をキューの先頭に挿入し、他の破棄不可能な記憶ユニットバックアップ等を飛ばすことを含んでもよい。
【０１４２】
いくつかの実施形態において、上述のように、キャッシュコントローラ３１２は、バックアップエンジン３１４の操作の優先度を高めることができる。例えば、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が満杯であり、ソリッドステート記憶デバイス１１４内に破棄可能としてマークされているユニット９１４〜９２６が全くない（または十分なユニット９１４〜９２６がない）場合、バックアップエンジン３１４に、最も高い優先度を与えることができる。いくつかの実施形態において、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４が埋まり始め、ソリッドステート記憶デバイス１１４上の利用可能な記憶空間が減少するにつれて、バックアップエンジン３１４の優先度を徐々に高める。
【０１４３】
いくつかの実施形態において、バックアップエンジン３１４は、年代順のバックアッププロセスを補うために適切なタイミングで起動することができる。バックアップエンジン３１４は、ソリッドステート記憶デバイス１１４内のユニットを年代順で進むが、それでも順番とは関係なく適切なタイミングで起動するように利用可能なように構成することができる。例えば、ソリッドステート記憶デバイス１１４は、データが読み込まれている時およびバックアップ資源が利用可能である時に、１つ以上のユニットにデータをバックアップするようにバックアップエンジン３１４を起動することができる。読み込みは、データにアクセスしているクライアントによって開始されてもよい。読み込みは、ガーベジコレクションを行うこと、データをスクラブすること、磨耗または故障ブロックからデータを復旧する、または他のグルーミング操作の間に、グルーマー３１０によって開始されてもよい。
【０１４４】
読み込みは、脱重複プロセスによって開始されてもよい。また、読み込みは、２００７年１２月６日に申請されたＤａｖｉｄ  Ｆｌｙｎｎらの「Ａｐｐａｒａｔｕｓ，  Ｓｙｓｔｅｍ，  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｒｅｌｉａｂｌｅ，  Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｓｔｏｒａｇｅ  ｏｆ  Ｄａｔａ  ｗｉｔｈ  Ｐｒｏｇｒｅｓｓｉｖｅ  ＲＡＩＤ」と題される米国特許出願第１１／９５２，１１５号に記載されるように、ＲＡＩＤ再構築またはプログレッシブＲＡＩＤ操作によって開始されてもよく、この出願はその全体が参照として本書に組み込まれる。バックアップエンジン３１４は、システムオーバーヘッドを低減させるために、他のプロセスと併せて動作することができる。当業者は、他のプロセスがバックアップを開始させるために適切に使用されることがあることを認識するだろう。
【０１４５】
バックアップエンジン３１４は、グルーマー３１０によって起動されてもよい。いくつかの実施形態において、グルーマー３１０は、記憶区分（例えば、ソリッドステート記憶デバイス１１４の消去ブロック）を解放するためにバックアップエンジン３１４を起動する。例えば、グルーマー３１０は、メタデータ１１７にアクセスし、特定の記憶区分が、かなり多くの量の破棄不可能データを含み、そのデータがコールドであることを判定し得る。グルーマー３１０は、バックアップエンジン３１４を起動して特定の消去ブロックのユニットをバックアップし、次いで消去ブロックをグルームし、新たに破棄可能なユニットを無効であるかのように扱い、そうしてソリッドステート記憶デバイス１１４上に空間を解放することができる。
【０１４６】
図１０は、グルーミングのためにキャッシュ操作に関するメタデータを使用するグルーマー３１０のための方法１０００の例示的な実施形態を示す。上述のように、方法８００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０１４７】
グルーマー３１０は、図１０に挙げられる判断を行うための操作を行うことができる、または操作の一部もしくは全部の負荷を取り除くために他のルーティンもしくはプロセスをコールすることができる。方法１０００は、グルーマー３１０がグルーミング操作のための記憶区にアクセスする１００２ことで開始する。グルーミング操作は、いくつかの実施形態において、ガーベジコレクション操作であってもよい。他の実施形態においては、グルーミング操作は、読み込みもしくは書き込み妨害、デフラグ、リフレッシュ、または他のデータグルーミング操作に起因するデータ移動であってもよい。いくつかの実施形態において、グルーミング操作のために記憶区分にアクセスする際、グルーマー３１０は、メタデータ（例えば、有効性インジケータ）を使用して、ソリッドステート記憶デバイス１１４のどの記憶ユニットが有効データを含むかを判定する１００４。記憶区分復旧操作では、有効性マップ内に無効データを含むとして識別されるこれらの記憶ユニット内のデータは、新しい消去ブロックへ移動されない。その結果、消去ブロックが初期化される（例えば、全ページに１が書き込まれる）時、無効データは消去される。
【０１４８】
グルーマー３１０は、次いで、破棄可能である有効データを含む１００６記憶ユニットを（例えば、破棄可能性マップを使用して）識別するためにメタデータ１１７にアクセスする。いくつかの実施形態において、グルーマー３１０が破棄不可能と判定するユニットは、グルーミング操作の一部として新しい記憶区分へ移動され１０１０、方法１０００は終了する。グルーマー３１０は、初めに有効かつ破棄不可能なデータを、データを新しい記憶区分へ移動することに備えてバッファ内に移動することができる。いくつかの実施形態において、グルーマー３１０は、バックアップエンジン３１４を起動してこれらのユニット内のデータをバックアップすることもでき、そうしてユニットは破棄可能になる。いくつかの実施形態において、グルーマー３１０は、バックアップエンジン３１４を起動し、バックアップエンジン３１４がデータを補助記憶装置１１８へ移動するまで、グルーミング操作を一時停止してもよい。グルーマー３１０は次いで、バックアップ操作が完了した後に再開し、新しく破棄可能なユニットを破棄可能データとして扱ことができる。
【０１４９】
グルーマー３１０が特定のユニットが破棄可能であると判定する１００６である場合、グルーマー３１０は、破棄可能であるユニットと関連付けられるデータが排除できる（例えば、コールドである）かどうかに関して判定する１００８ことができる。判定は、とりわけ、ソリッドステート記憶デバイス１１４上で行われる記憶操作に関連する、アクセスパターン、頻度等のメタデータを使用してキャッシュ管理装置１３０によって行われてもよい。グルーマー３１０が、データが排除できることを判定する１００８と、グルーマー３１０はデータを新しい消去ブロックへ移動せず１０１２、方法１０００は終了する。グルーマー３１０が、データがコールドではないと判定すると１００８、グルーマー３１０はデータを新しい消去ブロックへ移動し１０１０、方法１０１０は終了する。
【０１５０】
いくつかの実施形態において、グルーマー３１０は、バックアップされ、それによって破棄可能に設定されている破棄可能性インジケータを有する全てのユニットがコールドであると想定することができる。そのような実施形態において、破棄可能に設定された破棄可能性インジケータを有する全てのユニットは、グルーミング操作中に移動されない。そのような実施形態は、グルーマー３１０がソリッドステート記憶デバイス１１４内に空間を積極的に再生することにつながり、ソリッドステート記憶デバイス１１４が最大容量の時または最大容量に近づいている時に特に有用である。さらに、バックアップエンジン３１４がバックアップ操作を年代順に行う実施形態においては、少なくとも書き込みの観点からは、データが古ければ古いほど、より新しいデータよりも破棄可能にマークされやすいため、破棄可能とマークされたユニットがコールドデータを含んでいることは、妥当な想定である。
【０１５１】
他の実施形態において、グルーマー３１０は、単一の記憶ユニットが排除可能（キャッシュ管理装置１３０のキャッシングポリシー等に従って）であるかどうかについて、メタデータ１１７を使用して判定することができる。いくつかの実施形態において、グルーマー３１０は、単一の記憶ユニットについて排除可能性の判定を行い、隣接した１組のユニットを同様に扱う。例えば、論理アドレスの範囲（例えば、インデックスまたはＢツリー内の特定の節点）と関連付けられる１組の記憶ユニットは、グループとして排除（または保持）されてもよい。グルーマー３１０は、排除可能性を判定するのに必要な命令を実装してもよく、どのユニットがコールドデータを含んでいるかについて、キャッシュコントローラ３１２等の他の実体に問い合わせてもよい。
【０１５２】
いくつかの実施形態において、キャッシュコントローラ３１２は、どの記憶ユニットがコールドデータを含んでおり、どの記憶ユニットがウォームデータを含んでいるかを判定するために、記憶操作に関するメタデータにアクセスすることができる。いくつかの実施形態において、メタデータ１１７は、記憶ユニット（または論理アドレス）上の読み込みならびに記憶ユニットへの書き込みを追跡するための読み込みログ（またはタイムスタンプ）を含み、読み込みは、ユニット内のデータがコールドかどうかを判定する際に考慮される。キャッシュコントローラ３１２は、ログの開始時におけるあらゆるデータはコールドになり、一旦データが補助記憶装置１１８へバックアップされると、排除可能であると判断することができる。
【０１５３】
いくつかの実施形態において、キャッシュコントローラ３１２は、対象の占有量が閾値に達するまではデータがコールドであると判断しない。したがって、ソリッドステート記憶デバイス１１４の使用済みの記憶が目標の占有量閾値未満である間は、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４からいかなるデータも排除しないことを選択することができる。そのような実施形態において、バックアップエンジン３１４は、依然としてデータ上でバックアップ操作を行うが、しかしながら、キャッシュコントローラ３１２は、対象の占有量が閾値に達するまでは、グルーマー３１０が破棄可能に設定された破棄可能性インジケータを有するデータを、コールドとして処理しないように指示することができる。キャッシュコントローラ３１２は、一旦対象の占有量が閾値に達すると、グルーマー３１０が破棄可能に設定された破棄可能性インジケータを有するデータを処理するように指示することができる。
【０１５４】
いくつかの実施形態において、キャッシュコントローラ３１２は、データがコールドであるかどうかを判定するために多重の基準を有してもよい。例えば、キャッシュコントローラ３１２は、特定の期間（例えば、４時間）より古いいかなるデータもコールドであり、ソリッドステート記憶デバイス１１４の占有量にかかわらず排除の対象であると判断することができる。また、キャッシュコントローラ３１２は、上述のように、一旦対象の占有量が閾値に達すると、データをコールドであると指定するための新しい規則を有することもできる。
【０１５５】
いくつかの実施形態において、キャッシュコントローラ３１２は、何のデータがコールドであると考えられるのかに対する規則を、パラメータに基づいて動的に変更する。例えば、キャッシュコントローラ３１２は、いつ高い書き込み作業負荷があるのかを学習し、コールド（したがって排除）と判断されるデータ量を増やすことによって、それによりソリッドステート記憶デバイス１１４上の空間を解放することにより、ソリッドステート記憶デバイス１１４を準備することができる。キャッシュコントローラ３１２は、毎日が空のソリッドステート記憶デバイス１１４で開始するように、ソリッドステート記憶デバイス１１４を毎日の終わりに空にすることができる。
【０１５６】
いくつかの実施形態において、キャッシュコントローラ３１２は、ユニットのデータがコールドの場合のみ、記憶ユニットのデータを補助記憶装置１１８へバックアップするようにバックアップエンジン３１４を指示することができる。キャッシュコントローラ３１２は、上述と同様のアプローチを使用して、どのデータがコールドかを判定することができる。そのような実施形態において、グルーマー３１０は、破棄可能に設定された破棄可能性インジケータを有する全てのユニットがコールドであると見なすことができる。
【０１５７】
いくつかの実施形態において、１つより多い記憶ユニットからのデータが、論理的なデータユニットの一部となる。これらの論理ユニット対記憶のユニットの関連は、メタデータ１１７内に（例えば、正および／または逆インデックス内）に維持され得る。例えば、特定のファイルは、単一記憶ユニット内に記憶するには大きすぎることがあり、したがって、そのファイルは、複数の記憶ユニットに記憶されてもよく、ソリッドステート記憶デバイス１１４内の各記憶ユニットは、固有の記憶ユニットＬＢＡに対応する。キャッシュコントローラ３１２が、ＬＢＡ内のデータがどのように（したがって種々のユニット内のデータがどのように）関係しているかを特定するこのコンテキスト情報（マップなど）を説明するメタデータにアクセスするところでは、バックアップエンジン３１４およびキャッシュコントローラ３１２は、より効率的な操作を可能にするために論理的なレベルで動作することができる。
【０１５８】
例えば、バックアップエンジン３１４は、特定のユニットのためのデータをバックアップし、同一の論理データユニットのデータを保持するさらなる記憶ユニットがソリッドステート記憶デバイス１１４内にあるかどうかを判定し、これらの記憶ユニットも同様にバックアップすることができる。同様に、グルーマー３１０が、特定の記憶ユニットが有効、破棄可能、およびコールドなデータを含んでいると判定する場合、グルーマー３１０は、他のユニットのどれが関連データを含んでいるかを判定するために、そのコンテキスト情報を使用することができる。いくつかの実施形態において、グルーマー３１０は、関連データを含む記憶ユニットもバックアップされることを確実にし、無効性インジケータを無効に設定する。記憶ユニットがバックアップされない場合、グルーマー３１０は、関連ユニット内のデータをバックアップするようにバックアップエンジン３１４をコールすることができる。
【０１５９】
いくつかの実施形態において、ソリッドステート記憶デバイス１１４は、キャッシュ管理装置１３０がソリッドステート記憶デバイス１１４の種々の記憶ユニット内のデータ間の関連性を断定的に判定することを可能にするコンテキスト情報へのアクセスを有さないことがある。いくつかの実施形態において、キャッシュコントローラ３１２は、メタデータ１１７（例えば、逐次記憶ログ等の記憶メタデータ３１６）に基づき、どのユニットがグループを成すかについて、賢い推測をすることができる。例えば、キャッシュコントローラ３１２は、連続的に書き込まれた１組の記憶ユニットが、ファイル等の論理的なデータユニットを構成すると想定し得る。同様に、キャッシュコントローラ３１２は、一貫して共に読み込まれる１組のユニットが、論理的なデータユニットを構成すると想定し得る。キャッシュコントローラ３１２は次いで、バックアップエンジン３１４およびグルーマー３１０に、そのユニットのセットを上述のような論理的なデータユニットとして扱うように指示する。関連する実施形態において、一般的に共にアクセスされる複数のファイルおよびデータセットは、ソリッドステート記憶デバイス１１４によって、グループとして論理的に関連付けられる、および操作され得る。
【０１６０】
いくつかの実施形態において、一旦キャッシュコントローラ３１２が、１組のユニットが論理的なデータユニットを形成しているデータを保持すると判定すると、キャッシュコントローラは、ユニットが共にバックアップされることを確実にするように、バックアップエンジン３１４を管理する。これらのユニットは、ソリッドステート記憶デバイス１１４内に連続して記憶される必要はない。補助記憶装置１１８内の多数のハードディスクドライブおよび他の媒体は、データがストリームとして表される際に、より効果的にデータを読み込む。したがって、キャッシュコントローラ３１２は、ソリッドステート記憶デバイス１１４に論理的なデータユニットを形成するユニットからハードディスクドライブにデータをストリームさせることができる。同様に、キャッシュコントローラ３１２は、キャッシュミスに応答して、データ補助記憶装置１１８からのストリームとしてデータを受け取ることができる。
【０１６１】
図１１は、共有メタデータを含む例示的なデータ構造の略ブロック図である。インデックス１１０４は、複数のキャッシュエントリ（例えば、節点１１０８、１１１４、１１１６等）を含むツリー（または他のデータ構造）を備えることができる。インデックス１１０４内の各キャッシュエントリは、論理アドレス（または論理アドレス範囲もしくはセット）を、ソリッドステート記憶デバイス上の１つ以上の記憶場所（例えば、記憶ユニット）と関連付けることができる。記憶ユニットは、アドレス１１１７（例えば、エントリ１１１４において描写されるような）または他の何らかの識別子によって識別することができる。インデックス１１０４内のキャッシュエントリは、単一エントリ（例えば、エントリ１１１４）が１組の論理アドレス、論理アドレスの範囲等を参照することができるように、可変の長さのものであってもよい。論理アドレスは連続したものであり得る（例えば０７２〜０８３）。１１１８等の他のエントリは、論理アドレスの不連続のセット（例えば、論理アドレス４５４〜４７７および５３５〜５９８）を含み得る。したがって、インデックス１１０４は、可変サイズのキャッシュエントリ（例えば、論理アドレスの任意のセットまたは範囲のデータを含むソリッドステート記憶デバイス１１４上の１つ以上の記憶ユニットに対応するキャッシュエントリ）を表すために使用されてもよい。
【０１６２】
図１１において示されるように、キャッシュエントリは、高速かつ効率的な検索を可能にし得る論理アドレスによって（エッジ１１１０などのエッジを使用して）インデックス付けされてもよい。論理アドレス「１８２」を含むキャッシュエントリの例示的な検索は、以下のように進むことができる。検索は、ルートキャッシュエントリで開始してもよく、それは図１１の例におけるキャッシュエントリ１１０８である。単一論理アドレス（またはアドレス範囲）がルートキャッシュエントリ１１０８などの特定のキャッシュエントリに含まれるところでは、検索されている論理アドレス（「１８２」）がキャッシュエントリ１１０８の論理アドレスよりも低い場合、検索は有向エッジ１１１０をキャッシュエントリ１１０８の左へ続けて行くことができる。検索される論理アドレス（「１８２」）が現在のキャッシュエントリ１１０８と一致する場合（例えば、キャッシュエントリ１１０８の範囲内に位置する）、検索は、識別されている現在のキャッシュエントリ１１０８で無事に終了する。検索される論理アドレス１１０６が現在の節点１１０８よりも大きい場合、検索は有向エッジ１１１２を現在のキャッシュエントリ１１０８の右へ続けて行くことができる。１つのキャッシュエントリが、２つの論理アドレスまたはアドレス範囲（例えば、エントリ１１１８において示されるような不連続的なセット）を含み、検索される論理アドレス（「１８２」）が一覧の仮想アドレスの間に位置するところでは、検索は、中央の有向エッジ（示されていない）を現在の節点１１０８の２つの論理アドレスの中間に位置する論理アドレスを持つエントリへ続けていくことができる。検索は、キャッシュエントリが識別されるまで、または葉のキャッシュエントリに達して、検索が失敗するまでインデックス１１０４を続ける。図１１の例において、検索は、一致するキャッシュエントリ１１１６（例えば、検索される論理アドレス「１８２」を含むキャッシュエントリ１１１６）で無事に終了する。
【０１６３】
図１１の例において、インデックス１１０４は、論理アドレスによってインデックス付けされるＢツリーのデータ構造を使用して実装されるが、他の実施形態においては、インデックス１１０４は、内容アドレス可能メモリ（「ＣＡＭ」）、バイナリツリー、ハッシュテーブル、または当該技術分野において知られる他のデータ構造を使用して実装され得る。
【０１６４】
インデックス１１０４内の各キャッシュエントリは、１つ以上の論理アドレスを、ソリッドステート記憶デバイス１１４の各記憶ユニット（１つまたは複数）と関連付けることができる。例えば、エントリ１１１４は、論理アドレス範囲０７２〜０８３を記憶ユニット９５〜１０６と関連付けることができる。当業者は、記憶ユニットの物理アドレスがインデックス１１０４内に記憶されてもよいこと、またはソリッドステート記憶媒体の１つ以上の記憶構造内へのオフセットであってもよいことを認識するだろう。上述のように、エントリ１１１４の記憶ユニットは、根底にあるデータに対する変更のため（例えば、変更、または復旧操作等のため）変化し得る。キャッシュエントリはさらに、キャッシュ排除のメタデータ（例えば、キャッシュエントリのアクセスパターン）、キャッシュエントリ年代、サイズ、キャッシュ属性、キャッシュ指令、記憶メタデータ（例えば、記憶ユニット１１１７のアドレス）等を含むメタデータ１１１９を含むおよび／または参照することができる。メタデータ１１１９は、論理アドレス（例えば、アドレス１１１５）によってインデックス付けされるキャッシュエントリと関連付けられるため、メタデータ１１１９は、根底にあるデータが記憶される位置の変更（例えば、記憶ユニットアドレス１１１７の変更）にかかわらず、キャッシュエントリ１１１４と関連付けられたままであり得る。
【０１６５】
インデックス１１０４は、ソリッドステート記憶デバイス１１４がクライアント記憶要求で参照されるデータを含むかどうかを効果的に判定するため、および／またはデバイス１１４上のデータの位置を特定するために使用することができる。例えば、ソリッドステート記憶デバイス１１４は、特定の論理アドレスのための記憶要求１１０２を受け取り得る。この要求は、補助記憶装置に向けられ得、またはソリッドステート記憶デバイス１１４に向けられ得る。要求１１０２は、論理アドレスおよび長さ（例えば、論理アドレス０７４から始まるデータの３ユニットを要求）を特定することができる。代替として、要求１１０２は、１組の論理アドレス、論理アドレス範囲（連続的または不連続的）等を含むことができる。
【０１６６】
ソリッドステート記憶デバイス１１４は、上述のような検索操作を使用して、要求された論理アドレスに対応するキャッシュエントリがインデックス１１０４内で利用可能かどうかを判定することができる。要求された論理アドレスを含むキャッシュエントリが、インデックス１１０４内に見られる場合、ソリッドステート記憶デバイス１１４は要求されたデータ（キャッシュヒット）を含み、そうでなければキャッシュミスが起こる。
【０１６７】
図１１に描写される例において、記憶要求１１０２に対応するキャッシュエントリは、インデックス１１０４（キャッシュエントリ１１１４）内にあり、したがって、キャッシュヒットが起こる。要求に対応するために、データは、キャッシュエントリ１１４内で識別された記憶ユニット１１１７から読み込まれ、発信者または要求へ返却され得る。キャッシュミスが起こる場合（例えば、要求が、インデックス１１０４内に存在しない論理アドレスを参照する）、ソリッドステート記憶デバイス１１４は補助記憶装置１１８からデータを読み込み、ソリッドステート記憶デバイス１１４上の１つ以上の記憶ユニットにデータを記憶し、新しいキャッシュエントリをインデックス１１０４内に作成する。新しいキャッシュエントリは、その論理アドレスに従ってインデックス付けされ、データを含む記憶ユニットを参照することができる。
【０１６８】
キャッシュミスが既にインデックス１１０４内にあるキャッシュエントリと近似の論理アドレスを参照する場合（例えば、アドレス０８４〜０８８を参照）、マージ操作が起こり得る。マージ操作において、既存のキャッシュエントリは、１つ以上の他のキャッシュエントリと「マージされ」てもよい。例えば、論理アドレス０８４〜０８８のための新しいキャッシュエントリは、エントリ１１１４とマージされてもよい。マージは、新しいアドレス（例えば、０７２〜０８８）を含むためにキャッシュエントリの論理アドレス１１１５を変更することを含むことができ、および／またはデータ書き込みが記憶される記憶ユニットを含む記憶ユニット１１１７であってもよい。
【０１６９】
部分的なキャッシュミスが起こる際に、同様の操作が起こり得る。部分的なキャッシュミスは、インデックス１１０４が要求データの全部ではなく一部を含む際に起こる。例えば、記憶要求１１０２は、アドレス０７８〜０８８を要求し得る。この場合、エントリ１１１４は、要求データの一部を参照するが、データの全部は参照しないことがある。要求に対応するために、ソリッドステート記憶ユニットは、ソリッドステート記憶デバイス上で利用可能なデータを読み込み（例えば、論理アドレス０８３まで）、補助記憶装置１１８から残りの（例えば、欠落）データにアクセスすることができる。補助記憶装置から読み込まれたデータは、ソリッドステート記憶デバイス１１４上に記憶され、別個のキャッシュエントリとしてインデックス１１０４に、および／またはキャッシュエントリ１１１４内に含められることができる。
【０１７０】
インデックス１１０４内のキャッシュエントリは、記憶ユニットのアドレス（例えば、アドレス１１１７）への参照を含むとして示されるが、本開示はこの点に限定されない。他の実施形態において、キャッシュエントリは、記憶ユニットへの参照または間接的なリンクを含む。例えば、キャッシュエントリは、記憶ユニットの識別子（または逆インデックス１１２２への参照）を含むことができる。
【０１７１】
図１１のメタデータは、キャッシュエントリの論理アドレスと関連付けられたデータを含む、記憶ユニットを識別することができる逆マップ１１２２をさらに含むことができる。逆マップ１１２２は、記憶ユニットを有効性インジケータ１１３０、破棄可能性インジケータ１１３２、および／または他のメタデータ１１３６（以下に記載される）等のメタデータと関連付けることができる。いくつかの実施形態において、記憶ユニットアドレス１１２６および／または長さ１１２８は、逆マップ１１２２内に明示的に含まれ得る。代替として、記憶ユニットアドレス１１２６および／またはデータ長１１２８は、逆マップ１１２２内のエントリの位置（例えば、１１２０）から推測され得、したがって、アドレス１１２６および／またはデータ長１１２８は、必要とされない場合がある。いくつかの実施形態において、逆マップ１１２２は、論理アドレス１１３４への参照を随意に含むことができる。論理アドレス参照１１３４は、逆マップ１１２２にアクセスする実体が、記憶ユニットと関連付けられた論理的な実体に関するメタデータ（例えば、インデックス１１０４内の特定のキャッシュエントリ）に迅速にアクセスすることができるようにする。
【０１７２】
メタデータ１１３６は、記憶ユニット上で行われる逐次的な記憶操作に関するメタデータを含むがこれに限定されない。例えば、メタデータ１１３６は、シーケンスインジケータ（例えば、タイムスタンプ）を含むことができ、それは記憶ユニットが記憶されたシーケンス（例えば、ならびに記憶ユニットの「年代」等も）を示すことができる。メタデータは、磨耗率、信頼性、エラー率、妨害ステータス等のような、記憶媒体に関するメタデータをさらに含むことができる。上述のように、記憶メタデータは、キャッシュ排除判定、キャッシュデータ移動（例えば、「ホット」キャッシュエントリのデータが信頼性の低い記憶ユニットに記憶される場合）等のようなキャッシュ管理操作を効果的に実施するために使用されてもよい。
【０１７３】
逆マップ１１２２は、ソリッドステート記憶デバイス１１４の記憶区分（例えば、消去ブロック）に従って構成されてもよい。この例において、キャッシュエントリ１１１８に対応するエントリ１１２０は、消去ブロックｎ  １１３８に位置する。消去ブロックｎ  １１３８の前に、消去ブロックｎ−１  １１４０が先行し、消去ブロックｎ＋１  １１４２（消去ブロックｎ−１およびｎ＋１のコンテンツは示されていない）が続く。消去ブロックは、所定の数の記憶ユニットを含んでもよい。消去ブロックは、記憶装置復旧操作において同時に消去されるソリッドステート記憶デバイス１１４内の領域を参照することができる。
【０１７４】
有効性メタデータおよび／または破棄可能性メタデータ１１３０および１１３２は、キャッシュ管理のバックアッププロセスおよびグルーマー（例えば、記憶装置復旧および維持）によって共有されてもよい。バックアッププロセスは、記憶ユニット上を年代順（最古から最新へ）に反復するために、逆マップ１１２２を使用することができる。バックアッププロセスは、（メタデータ１１３０および１１３２によって示されるように）有効かつ破棄不可能である記憶ユニットを補助記憶装置にバックアップすることができる。バックアッププロセスは、メタデータ１１３６を使用してバックアップに優先順位を与えることができる、例えば、バックアップエンジンは、メタデータ１１３６によって示されるように、信頼できない、または高い量の摩耗を有する等の記憶ユニット上に記憶されたデータのバックアップの優先度を高めることができる。
【０１７５】
同様に、グルーマーは、逐次的な記憶操作を行うために、メタデータ１１３０、１１３２、および／または１１３６を使用することができる。例えば、記憶区分を復旧する際、グルーマーは、次の記憶区分へ有効データを保持する（例えば、書き換える）よう要求され得る。しかしながら、破棄可能性インジケータ１１３２が、データが破棄可能であると示す場合、グルーマーは、データを復元しないように決定することができ、それによりグルーマーが、より効果的に作動すること（例えば、書き込み増幅を低減すること）を可能にする。代替として、またはそれに加えて、グルーマーは、論理アドレス１１３４の関連を使用し、キャッシュメタデータ（例えば、メタデータ１１１９）にアクセスし、記憶区分の復旧操作の際にソリッドステート記憶デバイス上に保有されるべき記憶ユニットを識別することができる（破棄可能データがメタデータ１１１９によると「ホット」の場合、保有する）。グルーマーは、キャッシュメタデータ（例えば、メタデータ１１１９）を、データリフレッシュ操作を行うこと、データ移動を行うこと（例えば、「ホット」データを信頼できない記憶ユニットから別の記憶ユニットへ移動する）等を含むがこれらに限定されない他の目的のために使用することができる。
【０１７６】
一般的に、逆マップ１１２２は、記憶装置復旧および／またはリフレッシュの決定を効果的に行うために消去ブロック（例えば消去ブロックｎ１１３８）と関連付けられたマップのセクションを走査することができるように記憶区分（例えば消去ブロック）または消去領域に従って配置される。仮想アドレス１１０６から物理アドレス１１２６を識別するために迅速に検索され得る順マップ１１０４内、ならびに消去ブロック１１３８内の有効データおよび有効データの量を識別するために速く検索され得る逆マップ１１２２内へ、インデックスを配置することは、逆マップ１１２２が検索と記憶装置復旧操作のために最適化され得るため、有益である。当業者は、インデックス１１０４および逆マップ１１２２を伴うインデックスの他の利点を認識するだろう。
【０１７７】
図１２は、ソリッドステート記憶デバイス上でデータをキャッシングするための方法の一実施形態のフロー図である。上述のように、方法１２００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０１７８】
ステップ１２１０で、ソリッドステート記憶デバイスは使用のために初期化されてもよい。初期化は、通信インターフェース（例えば、バス、ネットワーク等）等のソリッドステート記憶デバイス（例えば、ソリッドステート記憶デバイス１１４）のためのリソースを割り当てること、揮発性メモリを割り当てること、およびソリッドステート記憶媒体にアクセスすること等を含んでもよい。初期化は、図１１と併せて上で説明されたデータ構造のような共有メタデータのデータ構造を初期化すること、補助記憶装置デバイス（例えば、補助記憶装置１１８）を識別すること、および／または１つ以上のクライアント（例えば、クライアント１１０ａ〜ｃ）に対して記憶インターフェースを提供することをさらに含むことができる。
【０１７９】
ステップ１２２０において、ソリッドステート記憶デバイスは、１つ以上のクライアントからの記憶要求に対応することができる。記憶要求は、（ソリッドステート記憶デバイスが透過的にデータをキャッシュするように構成される場合）補助記憶装に向けられ得、および／またはソリッドステート記憶デバイスそのものへ向けられてもよい。
【０１８０】
ステップ１２３０で、ソリッドステート記憶デバイスは記憶要求に関連する共有メタデータ（例えば、メタデータ１１７）を維持してもよい。共有メタデータは、ソリッドステート記憶デバイス上で行われる記憶操作に関連する、および／またはソリッドステート記憶媒体に関連する記憶メタデータ（例えば、メタデータ３１６）を含んでもよい。したがって、記憶メタデータは、論理アドレスとソリッドステート記憶ユニットとの間の関連、有効性マップ、記憶再生利用メタデータ（例えば、磨耗率、信頼性、付加ポイント等）等を含むことができる。
【０１８１】
ステップ１２３０において維持される共有メタデータは、ソリッドステート記憶デバイス上に記憶されるキャッシュに関連する（例えば、ソリッドステート記憶デバイス上で行われるキャッシュ操作に関連する）キャッシュメタデータをさらに含んでもよい。キャッシュメタデータは、記憶メタデータの記憶ユニットインデックスに対する論理アドレスを共有してもよい。共有メタデータは、したがって、それぞれが論理アドレスをソリッドステート記憶デバイスの１つ以上の記憶ユニットに関連づける複数のキャッシュエントリを含む１つのインデックス（例えば、インデックス１１０４）を含んでもよい。キャッシュメタデータは、データアクセスパターン、キャッシュ属性、キャッシュ指令等のようなキャッシュ排除メタデータをさらに含んでもよい（例えば、図１１のメタデータ１１１９内に記憶される）。ステップ１２３０で維持されるメタデータは、インデックス（例えば、図１１のインデックス１１０４）、および／または逆インデックス（例えば、図１１の逆インデックス１１２２）を含んでもよい。
【０１８２】
ステップ１２４０において、方法１２００は、ソリッドステート記憶デバイス上で記憶操作を行うために共有メタデータへアクセスすることができる。逐次的な記憶操作は、逐次的な（例えば、位置のずれた）記憶操作を行うこと、論理対記憶ユニットの関連を維持すること、記憶ユニットの有効性ンジケーターを維持すること、復旧のための記憶区分を選択すること（例えば、ガーベジコレクション）、ソリッドステート記憶デバイスの現在の占有量レベルを判定すること、記憶区分の復旧操作の間に保持する記憶ユニットを選択すること等を含んでもよいが、それに限定されない。
【０１８３】
ステップ１２６０において、方法１２００は、ソリッドステート記憶デバイス上に記憶されるキャッシュを管理するために共有メタデータへアクセスすることができる。キャッシュを管理することは、補助記憶装置へ記憶区分をバックアップすること、キャッシュ排除メタデータを維持すること、排除のためのキャッシュエントリを選択すること等を含んでもよいが、それに限定されない。
【０１８４】
図１３は、ソリッドステート記憶デバイス上のデータをキャッシュするための方法１３００のフロー図である。上述のように、方法１２００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０１８５】
ステップ１３１０、１３２０、および１３３０において、方法１３００は、上述のように、初期化されてもよく、記憶要求に対応してよく、および共有メタデータを維持してもよい。
【０１８６】
ステップ１３４０で、方法１３００は、ソリッドステート記憶デバイスの逐次的な記憶操作を管理するために共有メタデータにアクセスすることができる。
【０１８７】
ステップ１３４２で、方法１３００は、復旧のための記憶区分を選択するためにキャッシュメタデータを使用することができる。ステップ１３４２は、補助記憶装置（例えば、破棄可能記憶ユニット）上に記憶されている記憶ユニットを識別するキャッシュメタデータにアクセスすることを含み得る。記憶区分の選択は、記憶デバイス上に保持されるべき（例えば、別の記憶場所へ書き換えられるべき）記憶区分内の有効データの閾値に基づいてもよい。有効データの量は破棄可能性インジケータを使用して判定することができる。記憶ユニットが有効かつ破棄可能である場合、記憶ユニットはデータを損失することおよび／または破損することなく復旧作業の間に消去することができる。
【０１８８】
ステップ１３４２は、記憶ユニットがソリッドステート記憶デバイス上に保持されるべきであるキャッシュエントリと関連付けられているかどうかを判定するために（例えば、排除ポリシーまたは他のメタデータに従って）、キャッシュメタデータにアクセスすることをさらに含み得る。例えば、キャッシュエントリが「ホット」である（除去されると、キャッシュミスをもたらす可能性が高い）場合、記憶ユニットは、破棄可能として識別されるにもかかわらず、復旧作業の間保持され得る。
【０１８９】
ステップ１３４４において、方法１３００は、選択される記憶区分上に復旧操作を実施することができる。この復旧操作は、復旧操作を行うためにキャッシュメタデータ（共有メタデータ内）にアクセスすることができる。復旧操作は、（キャッシュメタデータを使用して）記憶区分上の破棄不可能記憶ユニットを識別すること、および識別された記憶ユニットを別の記憶区分上に記憶させること、および／または破棄不可能記憶ユニットを補助記憶装置上に記憶させることを含み得る。この操作は、ソリッドステート記憶デバイス上に保持されるべきキャッシュエントリと関連付けられる記憶ユニットを識別するために、メタデータにアクセスすることをさらに含み得る（例えば、キャッシュエントリと関連付けられるキャッシュ排除メタデータに従って）。識別された記憶ユニットは、ソリッドステート記憶デバイスの別の記憶区分に記憶することができる。
【０１９０】
ステップ１３４６で、方法１３００は、記憶ユニットをリフレッシュおよび／または管理するためにデータグルーミング操作を実施することができる（データグルーミング操作は、ステップ１３４２および１３４４と併せて上で説明されるように、記憶装置復旧操作を含むこともできる）。グルーミング操作は、キャッシュ操作に関連する共有メタデータにアクセスすることができる。例えば、グルーミング操作は、「ホット」キャッシュエントリ、または「ＰＩＮ」属性等の特定のキャッシュ属性を有するキャッシュエントリ（例えば、キャッシュ排除メタデータを使用して）、破棄不可能な記憶ユニット等と関連付けられる記憶ユニットを識別することができる。グルーミング操作は、記憶区分磨耗率、信頼性（例えば、エラー率）、読み込み妨害、年代等に基づいて、記憶区分が別の記憶区分へ移動されるべきであるかどうかを判定するために、記憶メタデータを調べることもできる。
【０１９１】
ステップ１３６０で、方法１３００は、ソリッドステート記憶デバイス上に記憶されるキャッシュを管理するために共有メタデータにアクセスすることができる。
【０１９２】
ステップ１３６２で、方法１３００は、補助記憶装置上に記憶するための記憶ユニットを選択することができる。この選択は、記憶ユニットがいつ書き込まれたかという年代順配列（最古から最新へ）に基づいてもよく、それはソリッドステート記憶デバイス上で行われた記憶操作のシーケンスに関連する記憶メタデータを使用して判定することができる。いくつかの実施形態において、この選択は、キャッシュ排除メタデータ（例えば、アクセス頻度等のようなアクセスパターン）に基づいてもよい。使用事例によっては、高い変更率を有するキャッシュは、帯域幅の使用およびバックアップを行う待機時間の費用を最適化するためにバックアップのために選択されない場合がある。ステップ１３６２の選択は、有効性インジケータにアクセスすることを含むことができ、無効としてマークされたデータは、その年代および／または破棄可能性インジケータにかかわらず、バックアップされないことがある。
【０１９３】
いくつかの実施形態において、ステップ１３６２は、バックアップ操作に優先順位を付けることを含んでもよい。優先順位付けは、記憶区分磨耗率、信頼性、占有量等のような記憶メタデータに基づくことができる。例えば、信頼できない（または高摩耗の）記憶区分上に記憶された記憶ユニット（記憶メタデータにより示されるように）は、より信頼性のある（またはあまり摩耗していない）記憶区分上に記憶された記憶ユニットより前にバックアップされることができる。
【０１９４】
ステップ１３６４で、方法１３００は、とりわけ記憶メタデータに基づいて、記憶区分のバックアップ操作の優先順位を付けることができる。この記憶メタデータは、ソリッドステート記憶デバイスの現在の占有量を判定するために使用することができる。バックアップ操作の優先度は、現在の占有量に基づいて判定され得る。占有量が（占有量閾値と比較して）低い場合、バックアップはバックグラウンドにおいて操作するように構成され得る。占有量が高い場合、バックアップ操作の優先度が高くなり得る（例えば、フォアグラウンドへ移動される）。
【０１９５】
ステップ１３６６において、方法１３００は、共有メタデータ（例えば、記憶メタデータ）を使用して、排除のためのキャッシュエントリを識別することができる。上述のように、キャッシュエントリは、アクセスパターン、キャッシュ属性、キャッシュ指令等を含むキャッシュ排除メタデータと関連付けられ得る。このメタデータは、キャッシュエントリデータに関連し得る。しかしながら、逐次的な記憶操作の性質（例えば、位置のずれた書き込み等）のために、記憶ユニットとキャッシュメタデータとの間の関連性は失われることがある（例えば、物理的記憶位置が変化する際）。記憶メタデータは、しかしながら、論理対記憶ユニットの関連（図１１のキャッシュエントリ）を維持することができ、キャッシュエントリとその関連キャッシュ排除メタデータとの間の関連性が、その根底にある逐次的記憶操作（例えば、キャッシュデータの物理アドレスへの変化）にかかわらず保持されることを可能にする。別の実施形態において、記憶メタデータは、論理対記憶区分の関連（図１１のキャッシュエントリ）を維持することができ、キャッシュエントリとそれらの関連キャッシュ排除メタデータとの間の関連性が、その根底にある逐次的記憶操作（例えば、キャッシュデータの物理アドレスへの変化）にかかわらず保持されることを可能にする。
【０１９６】
ステップ１３６６の識別は、他の種類の記憶メタデータにアクセスしてもよい。例えば、高摩耗および／または信頼できない記憶区分上に記憶されるキャッシュエントリは、より信頼性のある記憶区分等上に記憶される同様のエントリを上回って排除に対して好適とされ得る。
【０１９７】
ステップ１３６８において、方法１３００は、共有メタデータ（例えば、記憶メタデータ）を使用してキャッシュ維持操作を行うことができる。キャッシュ維持操作は、「ホット」キャッシュエントリを識別すること、記憶メタデータを使用して、「ホット」キャッシュエントリをソリッドステート記憶デバイスの別の記憶区分へ移動させることを含んでもよい。この移動は、磨耗レベリング目的のため、過剰の読み込み妨害を防ぐ等のために行われてもよい。この選択は、記憶ユニット、記憶区分、仮想記憶区分、または他の粒度レベルにおいて維持される、関連する記憶統計値（例えば、読み込みカウント、年代、等）を維持する記憶メタデータに従って行うことができる。
【０１９８】
ステップ１３６８のキャッシュ維持操作は、一定の年代のおよび／またはバックアップされていない（例えば、破棄不可能である）記憶ユニットを移動することをさらに含む。破棄不可能である記憶ユニットは補助記憶装置上に記憶されておらず、したがって、それが失われると、データの損失および／または破損を引き起こす可能性がある。これらの記憶ユニットは、そのような損失を防ぐために信頼できないおよび／または高摩耗記憶区分から移動することができる。同様に、破棄不可能記憶ユニットは、読み込み妨害により引き起こされるエラーまたは他の状態を防ぐために、「ホット」記憶エントリの近隣から移動することができる。
【０１９９】
図１４は、ソリッドステート記憶デバイス上のデータをキャッシュするための方法１４００のフロー図である。上述のように、方法１４００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０２００】
ステップ１４１０、１４２０、および１４３０において、方法１４００は、上述のように、初期化されること、記憶要求に対応すること、共有メタデータを保持することができる。共有メタデータは、それぞれが論理アドレスをキャッシュエントリのデータを含む１つ以上の記憶ユニットと関連付ける複数のキャッシュエントリを含んでもよい。いくつかの実施形態において、メタデータは、図１１において描写されるＢツリーのデータ構造のような順インデックスを含むことができる。
【０２０１】
ステップ１４４０において、方法１４００は、特定の論理アドレスにおけるデータに対する要求を受け取ることができる。
【０２０２】
ステップ１４５０において、方法１４００は、特定の論理アドレスに対応するデータがソリッドステート記憶デバイス上に記憶されているかどうかを判定することができる。いくつかの実施形態において、ステップ１４５０は、共有メタデータの順インデックスを検索することを含んでもよい。特定の論理アドレスを含むキャッシュエントリが順インデックスにおいて存在する場合、方法１４００は、データが利用可能であることを判定し、このフローはステップ１４６０において続くことができる、さもなければ、このフローはステップ１４７０において続くことができる。
【０２０３】
ステップ１４６０において、記憶要求が対応され得る。記憶要求に対応することは、要求データを含む１つ以上の記憶ユニットを判定するためにステップ１４５０において識別されたキャッシュエントリにアクセスすることを含み得る。記憶ユニットを読み込むことができ、結果のデータを要求側へ戻すことができる。
【０２０４】
ステップ１４７０において、キャッシュミスが起こり得る。キャッシュミスは、補助記憶装置１１８等の別のデータ記憶内の特定の論理アドレスに対応するデータにアクセスすることによって対応することができる。
【０２０５】
ステップ１４７２において、データは、ソリッドステート記憶デバイス上に逐次的に記憶することができる。ステップ１４７４において、メタデータは、データがソリッドステート記憶デバイスで利用可能であることを示すように更新され得、ステップ１４７６において、データが要求側へ提供され得る。
【０２０６】
ステップ１４７４は、新しいキャッシュエントリをメタデータへ追加することを含むことができる。新しいキャッシュエントリは、特定の論理アドレスを、補助記憶装置から読み込まれたデータを含む記憶ユニットと関連付けることができる。
【０２０７】
いくつかの実施形態において、ステップ１４７４は、既存のキャッシュエントリ更新することを含むことができる。特定の論理アドレスは、メタデータ内の論理アドレスに近接し得る。したがって、新しい別個のキャッシュエントリを追加するよりもむしろ、既存のキャッシュエントリが、特定の論理アドレスを含むように、および補助記憶装置から読み込まれたデータを含む記憶ユニットを参照するように更新されてもよい。特定の論理アドレスが２つ以上の既存のキャッシュエントリの間に位置する（例えば、キャッシュエントリ間のギャップを埋める）場合、ステップ１４７４の更新操作は、新しい範囲（例えば、元のキャッシュエントリの論理アドレスおよび特定の論理アドレス）を含むように、ならびに元の記憶ユニットおよび補助記憶装置から読み込まれたデータ含む記憶ユニットを参照するようにキャッシュエントリをマージすることを含んでもよい。
【０２０８】
いくつかの実施形態において、キャッシュエントリは、要求データの一部を含むことができるが、そのデータの全ては含まない場合がある。この場合、ステップ１４７０および１４７２において、方法１４００は、データの欠落部分のみを読み込み、記憶することができる。ステップ１４７４において、新しいキャッシュエントリは、特定の論理アドレスを補助記憶装置から読み込まれるデータを含む記憶ユニットに関連させるために追加することができる。代替として、ステップ１４７４は、上述のように、既存のキャッシュエントリを更新することを含んでもよい。
【０２０９】
図１５は、ソリッドステート記憶デバイス上でデータをキャッシュするための方法１５００の一実施形態のフロー図である。上述のように、方法１５００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０２１０】
ステップ１５１０、１５２０、および１５３０において、方法１５００は、上述のように、初期化されること、記憶要求に対応すること、および共有メタデータを保持することができる。ステップ１５４０において、方法１５００は、ソリッドステート記憶デバイス上に記憶されたデータを除去する記憶要求を受け取り得る。この要求は論理アドレスによってデータを参照し得る。
【０２１１】
ステップ１５５０において、方法１５００は、図１４と併せて上で述べたように、論理アドレスに対応するデータがソリッドステート記憶デバイス上に記憶されているかどうかを判定することができる。
【０２１２】
ステップ１５６０において、この方法は、ソリッドステート記憶デバイスからデータを除去することができる。データを除去することは、論理アドレスと関連付けられるキャッシュエントリをメタデータから除去すること、および／またはキャッシュエントリの記憶ユニットを無効にすることを含み得る。キャッシュエントリがソリッドステート記憶デバイス上に保持されるべきデータを含む場合、キャッシュエントリは、除去される論理アドレスおよび／または無効にされる記憶ユニットとキャッシュエントリとの関連を取り除くように更新することができる。関連を取り除くことは上述のようにキャッシュエントリを分割することを含み得る。ステップ１５６０は、ＴＲＩＭコマンド（例えば、方法１５００によって提供される記憶インターフェースを通して発行される）等に応答して行われ得る。
【０２１３】
ステップ１５７０において、記憶要求は、補助記憶装置がデータを除去するように補助記憶装置へ渡されてもよい。
【０２１４】
図１６は、ソリッドステート記憶デバイス上のデータをキャッシュするための方法１６００の一実施形態のフロー図である。上述のように、方法１６００のステップは、特定の機械構成要素と結び付けられる、および／または持続性機械可読記憶媒体上に記憶される機械可読命令を使用して実装されてもよい。
【０２１５】
ステップ１６１０、１６２０、および１６３０において、方法１６００は、上述のように、初期化されること、記憶要求に対応すること、共有メタデータを維持することができる。ステップ１６３０において維持されるメタデータは、論理アドレスをソリッドステート記憶デバイスの記憶ユニットと関連付ける順インデックスを含んでもよい。メタデータは、有効性および／または破棄可能性メタデータをさらに含んでもよい。
【０２１６】
ステップ１６４０において、ソリッドステート記憶デバイスの最大占有量は、共有メタデータ１１７（例えば、記憶メタデータ３１６）を使用して計算することができる。記憶メタデータ３１６は、エラー率、信頼性、磨耗率等のようなソリッドステート記憶媒体に関するメタデータを含んでもよい。記憶メタデータ３１６は、もはや使用可能でない（許容できないエラー率または他の状態のため）記憶区分または記憶ユニットのインジケータを含んでもよい。ソリッドステート記憶デバイスの最大占有量は、元の最大占有量（例えば、物理記憶容量またはその係数）から使用不可能な記憶区分を差し引くことによって計算することができる。データをキャッシュするために利用可能な物理的記憶空間は、記憶ユニットが摩耗または他のエラー状態のために利用不可能になるにつれて、同様に経時的に変化し得る。ソリッドステート記憶デバイスは、利用不可能な記憶区分および／または記憶ユニットに起因する、利用可能な物理記憶容量の縮小にもかかわらず、（同一のサイズまたは同様のサイズの論理アドレス空間を提示する）キャッシュとして作動し続けることができる。利用可能な物理記憶容量内の縮小は、ソリッドステート記憶デバイスがもはやデータをキャッシュするために利用可能な物理容量を有さず、入力／出力速度が補助記憶装置に直接アクセスことに対する速度に類似するまで継続し得る。
【０２１７】
ステップ１６５０において、ソリッドステート記憶デバイスの現在の占有量は、共有メタデータ１１７を使用して計算することができる。いくつかの実施形態において、現在の占有量は、ソリッドステート記憶デバイス上の全ての有効データを含むものとして計算され得る。有効データは、順インデックス（例えば、図１１のインデックス１１０４）を走査することによって識別され得る。代替として、より積極的な計算は、有効かつ破棄不可能な記憶ユニットのみを計算することを含み得る。この場合、方法１６００は、破棄可能な記憶ユニットがデータ損失なしにソリッドステート記憶デバイスから除去することができ、したがって、利用可能な記憶空間としてカウントされてもよいと想定することができる。
【０２１８】
ステップ１６６０において、方法１６００は、バックアップエンジン、グルーマー、キャッシュマネージャ等のような要求側へ、最大占有量および／または現在の占有量を提供することができる。
【０２１９】
いくつかの実施形態において、方法１６００は、補助記憶装置のアドレス空間を上回る論理アドレス空間を提示することができる。ステップ１６７０において、方法１６００は、補助記憶装置の論理アドレス範囲の外側にある論理アドレスと関連付けられる記憶要求に対応することができる。ソリッドステート記憶デバイスは、ソリッドステート記憶デバイス上にデータを記憶することによって要求に対応することができる。しかしながら、データは、補助記憶装置へバックアップされないことがある（そのアドレスが補助記憶装置の論理アドレスから外れるため）。したがって、論理アドレスと関連付けられるキャッシュエントリの記憶ユニットは、破棄不可能としてマークされ得、追加の論理的または物理的補助記憶装置容量が利用可能になるまで、破棄不可能のままであり得る。いくつかの実施形態において、ステップ１６７０は、追加の補助記憶装置を要求すること、および／または論理記憶空間が上回ったという通知を発行することを含むことができる。
【０２２０】
本明細書を通じた「いくつかの実施形態」または「実施形態」への言及は、実施形態に関連して記載される具体的な特徴、構造、または特質が少なくとも一実施形態において含まれることを意味する。したがって、本明細書中の様々な場所における「一実施形態において」または「いくつかの実施形態において」という表現の出現は、必ずしも全てが同一の実施形態を指しているわけではない。さらに、「実施形態」は、システム、デバイス、製造品目、方法、および／またはプロセスであり得る。
【０２２１】
本明細書中の「に接続される」、「ネットワーク化される」、および「と通信して」、「通信的に結合される」という表現は、機械的な、電気の、磁気の、および電磁気の相互作用を含む２つ以上の実体間における相互作用のあらゆる形態を指す。２つの構成要素は、物理的に直接互いに接しておらず、２つの構成要素の間に中間のデバイスがある可能性があるにもかかわらず、互いに接続し合うことができる。
【０２２２】
本明細書に開示される実施形態とともに使用することができる基礎構造のいくつかは、汎用のプロセッサ、プログラムツールおよび技術、持続性の、コンピュータ可読記憶媒体および／または機械可読記憶媒体、ならびに通信ネットワークおよびインターフェース等であり、既に利用可能である。ＩＥＤおよび／またはモニタリングデバイス等のコンピューティングデバイスは、マイクロプロセッサ、マイクロコントローラ、論理電気回路網等のようなプロセッサを含んでもよい。プロセッサは、ＡＳＩＣ、ＰＡＬ、ＰＬＡ、ＰＬＤ、ＦＰＧＡ、または他の処理手段のような特殊目的のプロセスデバイスを含んでもよい。コンピューティングデバイスはまた、不揮発性メモリ、スタティックＲＡＭ、ダイナミックＲＡＭ、ＲＯＭ、ＣＤ−ＲＯＭ、ディスク、テープ、磁気、光学、フラッシュメモリ、または他の持続性機械可読記憶媒体等のコンピュータ可読記憶媒体も含むことができる。
【０２２３】
上記の説明は、本明細書に記載される実施形態の十分な理解のために多数の具体的な詳細を提供する。しかしながら、当業者は、具体的な詳細のうちの１つ以上が省略されてもよく、または他の方法、構成要素、もしくは材料が使用されてもよいことを認識するだろう。場合によっては、操作が詳細には示されていないかまたは記載されていない。
【０２２４】
本開示の特定の実施形態および応用が例示説明され記載されたが、本開示が本明細書に開示される厳密な構成および構成要素に限定されないことを理解されたい。当業者にとって明白である様々な修正、変更、および変形が、本開示の精神および範囲から逸脱することなく、本開示の方法およびシステムの配置、操作、および詳細になされてもよい。
【図１】
0005999645.tif 000002
【図２】
0005999645.tif 000003
【図３】
0005999645.tif 000004
【図４】
0005999645.tif 000005
【図５】
0005999645.tif 000006
【図６】
0005999645.tif 000007
【図７】
0005999645.tif 000008
【図８】
0005999645.tif 000009
【図９Ａ】
0005999645.tif 000010
【図９Ｂ】
0005999645.tif 000011
【図１０】
0005999645.tif 000012
【図１１】
0005999645.tif 000013
【図１２】
0005999645.tif 000014
【図１３】
0005999645.tif 000015
【図１４】
0005999645.tif 000016
【図１５】
0005999645.tif 000017
【図１６】
0005999645.tif 000018