(57)【要約】      （修正有）【課題】多数のレコードにスケールし、高トランザクションレートを提供するインデックスを構築するための方法及び装置を提供する。【解決手段】インデックス付けアルゴリズムによって必要とされる論理バケットを、メモリデバイス上の物理バケットにマップする、あるデータ構造である変換テーブル１７が作成される。バケットを集め、大きい順次書き出しとして、メモリデバイスへ順次書き出すために、もう１つのデータ構造である連想キャッシュが使用される。インデックス付けアルゴリズムによって必要とされる（レコードの）バケットでキャッシュ２３をポピュレートする。フリー消去ブロックの生成を容易にするために、追加のバケットが、デマンド読出し中に、或いはスキャベンジング処理によって、メモリデバイス（フラッシュメモリ）２６からキャッシュ２３へ読み出される。【選択図】図１
2015144022.tif 000002
【特許請求の範囲】
【請求項１】
ユニフォームアクセスインデックス付け処理を、ノンユニフォームアクセスメモリ（２６，２３５）に適合させる方法であって、前記インデックス付け処理は、一様に分布した一意のインデックスキーに基づくインデックスレコードのディクショナリに対するランダムアクセス要求を生成し、前記方法は、
ａ）  インデックスレコードのディクショナリを前記ノンユニフォームアクセスメモリ（２６）に記憶するステップであって、各インデックスレコードは関連付けられたインデックスキーを含む、ステップと、
ｂ）  論理バケット識別子を前記メモリの物理バケット位置にマッピングするためのバケット変換テーブル（１７，３００）を維持するステップであって、１つのインデックスキー（１４１）を置き換えハッシングすることにより１つの論理バケット識別子を生成するステップを含み、前記テーブルは、前記１つの論理バケット識別子の、関連付けられた前記インデックスレコード（３１０，３１１，３１２）が記憶された前記メモリの１つの物理バケット位置（２２，３０９）へのマッピングを含む、ステップと、
ｃ）  複数の前記インデックスレコードをキャッシュ（２３）内に集めるステップであって、該ステップは、前記メモリの１つの物理バケット位置への前記キャッシュからの複数のインデックスレコードの集まりの順次書き込みとしての書き込みに先立つ、ステップと、
ｄ）  前記バケット変換テーブル（１７）を前記集まりの中の複数の前記インデックスレコードに対する前記１つの物理バケット位置で更新するステップと
を含む方法。
【請求項２】
請求項１に記載の方法であって、１つ又は複数の順次インデックスレコードを、前記メモリ（２６，２３）から前記キャッシュへ読み出すステップと、
前記１つ又は複数のインデックスレコードが読み出されたメモリ内の物理位置を、フリーとして指定するステップと
を含む方法。
【請求項３】
請求項１又は２に記載の方法であって、前記ブロック内の任意の有効インデックスレコードを前記キャッシュに読み出すこと、及び、そのようなインデックスレコードが読み出された前記メモリ内の物理位置を、フリーとして指定することによって、前記メモリ内の複数の順次物理バケット位置（２２，３０９）をフリーブロックとするステップを含む方法。
【請求項４】
請求項１から３の何れか一項に記載の方法であって、複数の論理バケット識別子を前記インデックスキーに対して生成すること、前記置き換えハッシングの関数は、複数の生成された前記論理バケット識別子の間で選択することを特徴とする方法。
【請求項５】
請求項１から４の何れか一項に記載の方法であって、前記メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とする方法。
【請求項６】
請求項１から５の何れか一項に記載の方法であって、前記メモリは、ランダム書き込みアクセス時間、ランダム読み出し−修正−書き込みアクセス時間、順次書き込み、アラインメント制約、消去時間、消去ブロック境界及び摩耗のうちの１つ又は複数によって制限されることを特徴とする方法。
【請求項７】
請求項１から６の何れか一項に記載の方法であって、前記バケットのサイズは、ページまたは部分ページ等の前記メモリの最小書き込みサイズの関数であることを特徴とする方
法。
【請求項８】
請求項７に記載の方法であって、前記メモリは、複数のページを含む消去ブロックを有することを特徴とする方法。
【請求項９】
請求項１から８の何れか一項に記載の方法であって、前記メモリ内のどの物理バケット位置が有効であるかを追跡するためのバケット有効テーブル（２７１）を維持するステップを含む方法。
【請求項１０】
請求項１から９の何れか一項に記載の方法であって、前記メモリの物理バケット位置（２３）は、１つ又は複数のインデックスレコードのセット、及び、前記バケット変換テーブルへのセルフインデックスを含むことを特徴とする方法。
【請求項１１】
請求項１０に記載の方法であって、前記バケットの前記インデックスレコードは順序付けされないことを特徴とする方法。
【請求項１２】
請求項１から１１の何れか一項に記載の方法であって、前記バケット変換テーブルは、永続メモリに記憶されたことを特徴とする方法。
【請求項１３】
請求項１から１２の何れか一項に記載の方法であって、消去ブロック内のフリー物理バケット位置の数を追跡し、フリーバケット位置のしきい値が満たされたとき、フリー消去ブロックを生成するための処理を実施するステップを含む方法。
【請求項１４】
請求項１から１３の何れか一項に記載の方法であって、前記インデックス付け処理は、インデックスレコードが挿入、削除、ルックアップ及び修正のうちの１以上をされる要求に基づいて、インデックス付けオペレーションを行うことを特徴とする方法。
【請求項１５】
請求項１から１４の何れか一項に記載の方法であって、前記インデックス付け処理は、前記インデックスレコードを記憶する物理バケット位置を読み出し該物理バケット位置に書き込むための論理バケットオペレーションを提示することを特徴とする方法。
【請求項１６】
請求項１から１５に記載の方法であって、前記メモリ（２６）は、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特徴とする方法。
【請求項１７】
請求項１６に記載の方法であって、ランダム読み出しオペレーションに応答して前記キャッシュに対する追加のバケットを読み出すことにより、フリー消去ブロックを生成するステップを含む方法。
【請求項１８】
請求項１６又は１７に記載の方法であって、スキャベンジング処理（１１４）を実行して、前記キャッシュに対する消去ブロックを読みだすことによりフリー消去ブロックを生成するステップを含む方法。
【請求項１９】
プロセッサに請求項１から１８の何れか一項に記載の方法の前記ステップを実行させるプログラムコードを含むコンピュータプログラム。
【請求項２０】
インデックス付け処理を実施するための命令を実行するプロセッサを含むコンピュータシステムであって、前記インデックス付け処理は、一様に分布した一意のインデックスキーに基づくインデックスレコードのディクショナリに対するランダムアクセス要求を生成し、前記システムは、
ノンユニフォームアクセスメモリ（２６）であって、前記メモリの物理バケット位置に記憶されたインデックスレコードのディクショナリを含む前記ノンユニフォームアクセスメモリと、
前記ディクショナリの１つのインデックスキーの置き換えハッシングにより生成された１つの論理バケット識別子を、該１つのインデックスキーに関連付けられたインデックスレコード（３１０，３１１，３１２）が記憶された前記メモリの１つの物理バケット位置にマッピングするためのバケット変換テーブル（１７）と、
前記メモリに書き込まれる複数のインデックスレコードを集めるためのキャッシュ（２３）と、
前記メモリのある物理バケット位置にアクセスするための手段（１８）であって、該ある物理バケット位置は、ユニフォームアクセスインデックス付け処理により前記バケット変換テーブルに供給された論理バケット識別子にマッピングされた、手段と、
前記キャッシュからの複数の前記インデックスレコードの集まりを、前記メモリの少なくとも１つの物理バケット位置に順次書き込むための手段（２４）と、
前記バケット変換テーブル（１７）を前記集まりの中の複数の前記インデックスレコードに対する前記少なくとも１つの物理バケット位置で更新するための手段（１９）と
を含む、コンピュータシステム。
【請求項２１】
請求項２０に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは物理デバイス層を含み、該物理デバイス層は、ノンユニフォーム読み出し及び書き込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられたコンピュータシステム。
【請求項２２】
請求項２０又は２１に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とするコンピュータシステム。
【請求項２３】
請求項２０から２２の何れか一項に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特著とするコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
[001]本発明は、多数のレコードにスケールし、高トランザクションレートを提供する
インデックスの構築のための方法及び装置に関する。
【背景技術】
【０００２】
[002]幾つかの現代のファイルシステムは、ファイルデータ及び他の内部ファイルシス
テム構造（「メタデータ」）を格納するために、オブジェクトを使用する。ファイルは、多数の小さいオブジェクト、恐らくは４ＫＢ（２＾１２バイト）ほどの大きさに分割される。６４ＴＢ（２＾４６バイト）に及ぶファイルシステムでは、例えば、これは、２＾（４６−１２）＝２＾３４、即ち、およそ１６０億個を超えるオブジェクトを追跡し続ける結果となる。
【０００３】
[003]これに関連して、オブジェクトは、バイナリデータのシーケンスであり、しばし
ばＧＵＩＤ（グローバル一意ＩＤ）であるか、或いはコンテンツの暗号ハッシュである、オブジェクト名を有するが、各一意のオブジェクトが一意の名前を有する限り、他の命名規則は可能である。オブジェクト名は通常、人とは対照的に、プログラムによる使用向けの固定長のバイナリ文字列である。オブジェクトサイズは任意であるが、実際には、典型的には２の累乗であり、５１２バイト（２＾９）から最大１ＭＢ（２＾２０）に及ぶ。これに関連するオブジェクトは、Ｊａｖａ（登録商標）及びＣ＋＋等、プログラミング言語で使用されるようなオブジェクトと混同されるべきではない。
【０００４】
[004]全てのオブジェクトのインデックス（時として、ディクショナリ又はカタログと
呼ばれる）は、ファイルシステムによって必要とされる。インデックス内の各レコードは、オブジェクト名、長さ、位置及び他の種々雑多な情報を含む場合がある。インデックスは、その主キーとして、オブジェクト名、オブジェクトの位置、又は場合によっては両方を有する場合がある。レコードは、数十バイト程度であり、３２バイトは一例である。
【０００５】
[005]このインデックスにおける動作は、エントリを追加すること、エントリをルック
アップすること、エントリに修正を行うこと、及び、エントリを削除することを含む。これらは全て、任意のインデックスにおいて行われる典型的な動作である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
[006]これらのファイルシステムはオブジェクトと共に働くので、ファイルシステムが
受け入れ可能な性能レベルを得るために、インデックス付けソリューションは、容易に対処されない２つの課題を有する。
【０００７】
１）インデックス内のエントリの数が大変大きくなる可能性がある。上記の例では、各インデックスエントリが３２（２＾５）バイトである場合、インデックスは、２＾（５＋３４）＝２＾３９、即ち、５１２ＧＢのメモリを要する。これは、現在のメモリ技術に高い費用対効果で適合しない。
【０００８】
２）インデックスに対する動作が大きい。商業的に実現可能なストレージシステムは、約２５６ＭＢ／秒（２＾２８バイト／秒）で行う必要のある場合がある。４ＫＢのオブジェクトサイズでは、それは、毎秒２＾（２８−１２）＝２＾１６、即ち、６４０００個の動作である。ファイルシステムが典型的には他のデータ（オブジェクト）を内部で生成且
つ参照することを考えれば、インデックス動作レートは、１０００００動作／秒を容易に上回る可能性がある。比較のポイントとして、現在の最先端のディスクは、よくても毎秒４００個の動作しか行うことができない。
【０００９】
[007]必要な性能及び容量レベルを達成することは、ＤＲＡＭメモリ技術又はディスク
技術のみを使用するのでは実際的ではない。ＤＲＡＭメモリは十分高速であるが、密度は十分ではない。ディスクは密度を有するが、性能を有していない。所望の特性に達するように、何れか（ＤＲＡＭメモリ又はディスク）をスケールすることは、費用がかかり過ぎる。
【００１０】
[008]オブジェクト名は、それらの分布においても、アクセスパターンにおいても、一
様であることが多いので、空間及び時間局所性によって決まる典型的なキャッシングスキームの効果は限られている。よって、インデックス付けの問題は、サイズにおいても、動作レートにおいても、困難である。
【課題を解決するための手段】
【００１１】
[009]本発明の一実施形態によれば、ユニフォームアクセスインデックス付け処理によ
って、ノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法が提供され、この方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００１２】
一実施形態では、この方法は、
レコードデータエントリの集まりを、キャッシュからメモリのバケット位置へ、順次書込みとして書き込むステップと、
集まりのレコードデータエントリのためのバケット位置により、変換テーブルを更新するステップと
を含む。
【００１３】
一実施形態では、この方法は、
１つ又は複数の順次レコードデータエントリを、メモリからキャッシュへ読み出すステップと、
１つ又は複数のエントリが読み出されたメモリ内の物理位置を、フリーとして指定するステップと
を含む。
【００１４】
一実施形態では、この方法は、
ブロック内の任意の有効エントリをキャッシュに読み出すこと、及び、そのようなエントリが読み出されたメモリ内の物理位置を、フリーとして指定することによって、メモリ内の複数の順次物理バケット位置をフリーブロックとするステップを含む。
【００１５】
一実施形態では、
インデックス付け処理が、一律に配布され一意のインデックスキーに基づいて、インデックスへのランダムアクセス要求を生成する。
【００１６】
一実施形態では、
キーは、暗号ハッシュダイジェストを含む。
【００１７】
一実施形態では、
インデックス付け処理は、置き換えハッシングの処理を含む。
【００１８】
一実施形態では、
置き換え（ｄｉｓｐｌａｃｅｍｅｎｔ）ハッシングは、カッコウハッシング処理を含む。
【００１９】
一実施形態では、
メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含む。
【００２０】
一実施形態では、
メモリは、ランダム書込みアクセス時間、ランダム読出し−修正−書込みアクセス時間、順次書込み、アラインメント制約、消去時間、消去ブロック境界及び摩耗のうちの１つ又は複数によって制限される。
【００２１】
一実施形態では、
物理バケットのサイズは、メモリの最小書込みサイズを含む。
【００２２】
一実施形態では、
物理バケットのサイズは、ページ又は部分ページを含む。
【００２３】
一実施形態では、
メモリは、複数のページを含む消去ブロックを有する。
【００２４】
一実施形態では、この方法は、
メモリ内のどのバケット位置が有効であるかを追跡するためのバケット有効テーブルを維持するステップを含む。
【００２５】
一実施形態では、
メモリ内のバケットは、１つ又は複数のレコードデータエントリのセット、及び、バケット変換テーブルへのセルフインデックスを含む。
【００２６】
一実施形態では、
バケット内のレコードデータエントリは順序付けされない。
【００２７】
一実施形態では、この方法は、
メモリに順次書き込まれたレコードデータエントリを、キャッシュ内で読出し専用として指定するステップを含む。
【００２８】
一実施形態では、
バケット変換テーブルは、永続メモリに格納される。
【００２９】
一実施形態では、この方法は、
消去ブロック内のフリーバケットの数を追跡し、フリーバケットのしきい値が満たされたとき、フリー消去ブロックを生成するための処理を実施するステップを含む。
【００３０】
一実施形態では、
インデックス付け処理は、レコードが挿入、削除、ルックアップ及び修正のうちの１以上をされる要求に基づいて、インデックス付けオペレーションを行う。
【００３１】
一実施形態では、
インデックス付け処理は、インデックスのレコードを格納する物理バケットを読み出し該物理バケットに書き込むための、論理バケットオペレーションを提示する。
【００３２】
一実施形態では、
物理バケットオペレーションは、ランダム読出し及び順次書込みを含む。
【００３３】
一実施形態では、
物理バケットオペレーションは、トリムコマンドを更に含む。
【００３４】
一実施形態では、
メモリは、ノンユニフォーム読出し及び書込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられた物理デバイス層を含む。
【００３５】
一実施形態では、
レコードデータエントリは、キー、参照カウント及び物理ブロックアドレスのためのフィールドを含む。
【００３６】
一実施形態では、
キーは、データの暗号ハッシュダイジェストを含み、
物理ブロックアドレスフィールドは、ストレージデバイス上に格納されたデータの物理ブロックアドレスへのポインタを含む。
【００３７】
一実施形態では、
論理バケット位置は、複数のハッシュ関数によって生成される。
【００３８】
一実施形態では、
メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含む。
【００３９】
本発明の別の実施形態によれば、
プロセッサによって実行されるとき、前述の方法のステップを行うプログラムコード手段を含むコンピュータプログラム製品が提供される。
【００４０】
本発明の別の実施形態によればコンピュータ可読媒体が提供され、このコンピュータ可読媒体は、ユニフォームアクセスインデックス付け処理によってノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法のための実行可能プログラム命令を含み、上記方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００４１】
本発明の別の実施形態によれば、物理プロセッサと、コンピュータ可読媒体を含むメモリデバイスとを含むシステムが提供され、
該コンピュータ可読媒体は、ユニフォームアクセスインデックス付け処理によってノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法のための実行可能プログラム命令を含み、上記方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００４２】
一実施形態では、
インデックスを格納するメモリは、ノンユニフォーム読出し及び書込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられた物理デバイス層を含む。
【００４３】
一実施形態では、
インデックスを格納するメモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含む。
【００４４】
一実施形態では、
インデックスを格納するメモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含む。
【００４５】
本発明の別の実施形態によれば、ユニフォームアクセスインデックス付け処理によって、ノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法が提供され、この方法は、
インデックス内のレコードデータエントリごとに論理バケット識別子をメモリの物理バケット位置にマップする変換テーブルに、インデックス付け処理によって生成された論理バケット識別子を提供するステップと、
論理バケット識別子にマップされた物理バケット位置にアクセスするステップと、
インデックスに書き込まれるレコードデータエントリをキャッシュ内に集めるステップと、
続いて、レコードデータエントリの集まりを、キャッシュから、メモリの少なくとも１つの新しい物理バケット位置におけるインデックスに順次書き込むステップと、
変換テーブルを更新して、少なくとも１つの新しい物理バケット位置を論理バケット識別子に関連付けるステップと
を含む。
【００４６】
本発明の別の実施形態によればあるコンピュータシステムが提供され、このコンピュータシステムは、
ノンユニフォームアクセスメモリであって、メモリの物理バケット位置においてレコードデータエントリを含むインデックスが格納される、ノンユニフォームアクセスメモリと、
ユニフォームアクセスインデックス付け処理によって生成された論理バケット識別子を、レコードデータエントリの各々のためのメモリの物理バケット位置にマップするための、変換テーブルと、
インデックスに書き込まれる集められたレコードデータエントリのためのキャッシュと
、
メモリの物理バケット位置にアクセスする手段であって、該物理バケット位置は、インデックス付け処理によって変換テーブルに供給された論理バケット識別子にマップされた、手段と、
レコードデータエントリの集まりを、キャッシュから、メモリの少なくとも１つの物理バケット位置のインデックスに順次書き込む手段と、
変換テーブルを更新して、少なくとも１つの物理バケット位置を論理バケット識別子に関連付ける手段と
を含む。
【００４７】
[010]本発明は、以下の図面と共に、詳細な説明を参照することによって、より十分に
理解される。
【図面の簡単な説明】
【００４８】
【図１】本発明の一実施形態により行われる、様々なインデックス付けオペレーションを例示する概略ブロック図である。
【図２Ａ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｂ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｃ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｄ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図３】本発明の一実施形態によるルックアップオペレーションを例示する概略ブロック図である。
【図４】本発明の一実施形態による挿入オペレーションを例示する概略ブロック図である。
【図５】本発明の一実施形態による削除オペレーションの概略ブロック図である。
【図６】本発明の一実施形態による更新オペレーションの概略ブロック図である。
【図７Ａ】本発明の一実施形態によるフリー消去ブロックを生成するためのランダム読出し処理を例示する概略ブロック図である。
【図７Ｂ】本発明の一実施形態によるフリー消去ブロックを生成するためのランダム読出し処理を例示する概略ブロック図である。
【図８Ａ】スキャベンジング処理に従ってフリー消去ブロックを生成する別の方法を例示する概略ブロック図である。
【図８Ｂ】スキャベンジング処理に従ってフリー消去ブロックを生成する別の方法を例示する概略ブロック図である。
【図９】本発明の実装を例示するための６層のビュー又はスタックを例示する概略ブロック図である。
【図１０】本発明の一実施形態で使用されるようなレコードエントリの概略図である。
【図１１】図１１Ａ〜１１Ｅは、本発明の一実施形態によるカッコウハッシングの実装を概略的に例示する図である。
【図１２】本発明の一実施形態による、各バケットが複数のレコードを保持する、複数のバケットの概略的例示の図である。
【図１３】本発明の一実施形態によるバケットのコンテンツの概略図である。
【図１４】本発明の一実施形態による、複数のダイ、消去ブロック、ページ及びバケットを有する物理フラッシュチップの一例を例示する概略ブロック図である。
【図１５】図１５Ａ〜図１５Ｂは、本発明の一実施形態によるデバイス管理層のあるコンポーネントを例示する図である。
【発明を実施するための形態】
【００４９】
Ａ．概観
[011]本発明の１つ又は複数の実施形態によれば、特化されたメモリ技術及びアルゴリ
ズムが使用されて、多数のレコード及びトランザクション要件を同時に有するインデックスが構築される。一実施形態は、置き換え（ｄｉｓｐｌａｃｅｍｅｎｔ）ハッシングインデックス付けアルゴリズム、例えばカッコウハッシングを利用する。本発明は、フラッシュ、相変化及びソリッドステートディスク（ＳＳＤ）メモリデバイス等、ノンユニフォームアクセスメモリ技術の使用を可能とする。
【００５０】
[012]本発明の様々な実施形態では、メモリデバイスが、メモリデバイスにとって効率
的であるＩＯ（入力／出力）パターンに遭遇しながら、インデックス付けアルゴリズムがアルゴリズムにとって自然（効率的）である方法で行うことを保証するために、新しいデータ構造及び方法が提供される。
【００５１】
[013]インデックス付けアルゴリズムによって見なされた論理バケットを、メモリデバ
イス上の物理バケットにマップする、あるデータ構造である間接指定テーブルが作成される。このマッピングは、ノンユニフォームアクセスメモリデバイスへの書込み性能が強化されるようにするものである。
【００５２】
[014]キャッシュの追い出し及びライトバックポリシーの一部として、バケットを集め
、メモリデバイスへ順次書き出すために、別のデータ構造である連想キャッシュが使用される。
【００５３】
[015]インデックス付けアルゴリズムによって必要とされる（レコードの）バケットで
キャッシュをポピュレートするために、方法が使用される。追加のバケットは、デマンド読出し中に又はスキャベンジング処理によって、メモリデバイスからキャッシュへ読み出されてもよい。
【００５４】
[016]間接指定テーブルと併せた、キャッシュの使用は、メモリデバイスへの大きい順
次書込みを可能にする。
【００５５】
[017]フラッシュ技術は、インデックス付け問題のために必要とされた容量及びＩＯレ
ートを達成する基本機能を有するが、フラッシュアクセス特性はノンユニフォームである。このノンユニフォーム性はかなり十分なので、通常のインデックス付けアルゴリズムは、フラッシュメモリデバイスと共に、たとえ機能するとしても、うまく機能しない。
【００５６】
[018]本発明で使用されるノンユニフォームアクセスフラッシュメモリは、数百から数
千ビットもの大きいブロックサイズで、即ち、バイトレベルのランダムアクセスではなく、読出し、書込み及び消去が行われなければならない、電気的消去可能プログラマブル読出し専用メモリ（ＥＥＰＲＯＭ）である。物理的には、フラッシュは、フローティングゲートトランジスタからなるメモリセルのアレイに情報を格納する、不揮発性メモリ形式である。２つのタイプのフラッシュメモリデバイス、ＮＡＮＤフラッシュ及びＮＯＲフラッシュがある。ＮＡＮＤフラッシュは、ＮＯＲフラッシュより高密度及び大容量をより低コストで提供し、より高速な消去、順次書込み及び順次読出し速度を有する。本願において、且つ本発明において使用されるとき、「フラッシュ」メモリは、ＮＡＮＤフラッシュメモリを包含するものであり、ＮＯＲメモリを包含しないものである。ＮＡＮＤは、各セルが１ビットの情報のみを格納するシングルレベルセル（ＳＬＣ）デバイス、及び、１つのセルにつき２ビット以上を格納することができる、より新しいマルチレベルセル（ＭＬＣ）デバイスを共に含む。ＮＡＮＤフラッシュは高速なアクセス時間を提供するが、ＰＣ内でメインメモリとして使用された揮発性ＤＲＡＭメモリほど高速ではない。フラッシュメモリデバイスは、フラッシュファイルシステムを含んでも含まなくてもよい。フラッシュファイルシステムは、典型的には、ウェアレベリング及び誤り訂正を行うために内蔵コン
トローラを有していない、内蔵フラッシュメモリと共に使用される。
【００５７】
[019]典型的なＮＡＮＤフラッシュチップは、数ＧＢのコンテンツを格納してもよい。
コンピュータに取り付けられたメモリとは異なり、フラッシュチップ上のメモリは、あるサイズで、且つ、ある境界上でアクセスされなければならない。更に、メモリのセクションに書き込まれた後、それらのメモリ位置が再び書込み可能となる前に、消去オペレーションが行われなければならない。また、位置は徐々になくなるので、全ての位置が同様の数の書込みを得ることを保証することは、使用を更に複雑にする。読出し時間、書込み時間及び消去時間は、大幅に（数マイクロ秒から数ミリ秒まで）変わる可能性がある。よって、タイミング、ウェアレベリング及びアラインメント制約は、フラッシュの実際的な使用を困難にするのがせいぜいである。
【００５８】
[020]フラッシュメモリデバイスは、１つ又は複数のダイ（シリコンウエハ）を含んで
もよい。各ダイは、大部分では、独立してアクセスされうる。
【００５９】
[021]ダイは、数千もの消去ブロックからなる。消去ブロックは典型的には、１２８〜
５１２ＫＢのサイズである。データがクリアされる必要があるとき、消去ブロック境界上でクリアされなければならない。
【００６０】
[022]ＮＡＮＤフラッシュのもう１つの制限は、データが順次書き込まれることのみが
可能であることである。更に、書込みのためのセットアップ時間は長く、読出しのセットアップ時間のおよそ１０倍である。
【００６１】
[023]データは、ページ粒度で読み出される。ページは、特定のフラッシュチップに応
じて、１ＫＢから４ＫＢまでに及ぶ場合がある。各ページに関連付けられるものは、誤り訂正符号（ＥＣＣ）チェックサムのために使用されうる、数バイトである。
【００６２】
[024]データは、ページ粒度で書き込まれる。書き込まれた後、ページは、その消去ブ
ロック（ページを含む）が消去されるまで、再度書き込まれない場合がある。消去ブロックは、数十から１００を超えるページを含む場合がある。
【００６３】
[025]上記の読出し及び書込みページ粒度に対する１つの例外は、サブページ書込み、
又は、部分ページプログラミングである。技術に応じて、ページは、消去が必要とされる前に最大４回、部分的に書き込まれる場合がある。
【００６４】
[026]ＮＡＮＤフラッシュブロック内のページは順次、且つ、ブロック消去オペレーシ
ョンの間に一度のみ書き込まれうるので、後続の書込みは、典型的には異なるフラッシュブロック内に位置する異なるページへの書込みを必要とする。ブロック消去の問題点は、フラッシュファイルシステムの機能である、書込み可能フラッシュブロックのプールを作成することによって、対処される。
【００６５】
[027]消去ブロックを消去することは、数ミリ秒を取りうるので、時間的に最も費用の
かかるオペレーションである。（トラフィック的に）多用されるデバイスでは、消去ブロックが生成されうる速度（即ち、どのくらい速くフリー消去ブロックが使用可能にされうるか）は、フラッシュ設計における制限要因であることが多い。
【００６６】
[028]多数のＳＳＤ（ソリッドステートディスク）は、フラッシュ技術を使用する。Ｓ
ＳＤにおけるファームウェアは、フラッシュ変換層（ＦＴＬ）と呼ばれる層において、前述のアクセスの問題点に対処する。そうすることにおいて、しかし、ファームウェアは、どのようにＳＳＤが使用されるか（例えば、大部分は読出し、大部分は書込み、読出し及
び書込みのサイズ及びアラインメント）について仮定を行い、これらの仮定の結果として、ＳＳＤの性能特性は、インデックス付けアルゴリズムにとって準最適であることが多い。
【００６７】
[029]人が文献において、また実際に発見する多数のインデックス付けアルゴリズムは
、ユニフォームメモリアクセスモデルに基づいており、即ち、全てのメモリが、読出しでも書込みでも時間的に等しくアクセス可能であり、アクセスサイズ又はアラインメントにおけるいかなる一次制約もない。
【００６８】
[030]インデックス付けソリューションを考察する場合、挿入、削除、ルックアップ及
び修正等のオペレーションは典型的には、より多くの多様な時間の量を必要とし、ブロック、典型的には小さいブロック（４ＫＢくらい）の読出し及び書込みは、より短い時間を必要とする。ブロックはランダムであるように見え、即ち、任意のブロックが読み出されてよく、任意の他のブロックが書き込まれてよい。幾つかのアルゴリズムでは、ランダム読出し−修正−書込みＩＯプロファイルがあり、即ち、ランダムブロックが読み出され、次いで、わずかに修正されたデータで同じ位置に書き戻される。
【００６９】
[031]インデックス付けアルゴリズムの効率的な動作を必要とするこのランダムＩＯは
、フラッシュが提供するように意図されるものではない。フラッシュは、ランダム読出しをうまく扱うことができるが、読出し−修正−書込みがそうであるように、ランダム書込みは困難である。この理由は、すでに書き込まれたものを上書きすることはできず、まずそれを消去しなければならないからである。この状況を更に複雑にすることには、消去は時間を要し、大きい境界（典型的には６４ＫＢ）上で起こらなければならない。
【００７０】
[032]消去ブロックが消去されるとき、そのブロック内のいかなる有効データも他のと
ころへ移動される必要がある。アルゴリズムがフラッシュデバイス中でランダムな４ＫＢブロックを書き込む場合、単純な実装は、その間ずっとブロックが消去され続ける結果となる。消去時間は遅いので、性能がかなり損なわれることになる。
【００７１】
[033]本発明によれば、フラッシュへの書込みを順次にすることを可能にするため、イ
ンデックス付けアルゴリズムが期待する論理ランダムアクセスをなお保ちながら、変換又は間接指定テーブルが作成される。このテーブルは、インデックス付けアルゴリズムによって必要とされるような（レコードの）論理バケットを、フラッシュデバイスの物理バケット（例えば、ページ）にマップする。
【００７２】
[034]インデックス付けアルゴリズムがバケット（例えば、フラッシュからのデータの
ページ）を読み込むとき、バケットコンテンツを修正（挿入、更新又は削除オペレーション）するために、バケットはキャッシュに移動される。フラッシュデバイス上の対応するバケットにはこのとき、有効ではない（フリー）としてマークが付けられうる。ＳＳＤの場合、これはＴＲＩＭコマンドの形式を取りうる。
【００７３】
[035]本発明の更なる実施形態によれば、フリー消去ブロックを生成するために、方法
が提供される。いかなる所与の時間でも、消去ブロックは、有効及び無効データの組み合わせを有する場合がある。消去ブロックを解放するため、全ての有効データは、そのブロックから離れるように移動されなければならない。これを達成するために使用されうる、２つの機構がある。１つは、インデックス付けアルゴリズムによって生成されたランダム読出しを使用して、（インデックス付けアルゴリズムによって必要とされるよりも）より多くを読出し、消去ブロックを解放するようにすることである。インデックス付けアルゴリズムはランダム読出しを生成する傾向があるので、経時的に、全ての消去ブロックは最終的に読み出され、空のページのために集積される。例えば、読出しを含む消去ブロック
が、幾つかのフリーページ及び幾つかの有効ページを有する場合、アルゴリズムは、消去ブロック全体を読み込み、且つ、全ての有効ページをキャッシュに入れることを選択してもよい。これは、後続の消去及び次いで書込みのために、その消去ブロックを解放する効果を有する。
【００７４】
[036]別法として、例えば、前述のランダム読出し処理が十分に高速でない場合、消去
ブロックを読み出し、別の消去ブロックと合体するために有効ページをキャッシュに入れるために、分離したスキャベンジング処理（例えば、スレッド）が使用されうる。
【００７５】
[037]キャッシュが一杯になるとき、エントリが書き出されなければならない。キャッ
シュエントリのセットが集められ、部分ページの隣接するセット（部分ページ書込みがフラッシュデバイスによって可能にされる場合）、複数のページ及び１つ又は複数の消去ブロックのうちの１以上へと、順次書き込まれるようになる。キャッシュエントリがフラッシュデバイスに書き込まれるとき、間接指定テーブルは更新されるので、インデックス付けアルゴリズムはなお、エントリが固定された論理アドレスにあるものと見なす。
【００７６】
Ｂ．インデックス付けオペレーション
[038]本発明の様々な実施形態がここで、添付の図１〜６を利用して説明され、本発明
に従って行われた様々なインデックス付けオペレーションが例示される。図７〜８は、ストレージ媒体（例えば、フラッシュメモリ）の効率的利用のためにフリー消去ブロックを生成する、２つの方法を例示する。これらの実施形態は例示的なものであり、限定するものではない。
【００７７】
[039]図１は、本発明の一実施形態による、バケット変換テーブル１７及びキャッシュ
２３を利用する幾つかのインデックス付けオペレーションの概観である。図１の上部に、３つのインデックスオペレーション１２〜１４が、ルックアップ関数１５及び変換関数１６への代替入力として示される。第１のインデックスオペレーション１２は、キーのための（レコードエントリ）から衛星データを返すための「キーをルックアップする」である。第２のインデックスオペレーション１３は、キーのためのレコードエントリを更新（修正）するための「キーのための衛星データを更新する」である。第３のインデックスオペレーション１４は、新しいレコードエントリを挿入するための「新しいキーを挿入する」である。もう１つのインデックスオペレーションである削除は、図１では図示されないが、図５に関して後述される。
【００７８】
[040]全ての３つのインデックスオペレーションは、最初にルックアップ関数１５を行
い、キーのある関数ｆ（キー）が使用されて、インデックスが生成され、ここでは、ハッシュテーブルルックアップをサポート（例えば、加速）する論理バケット識別子である。バケット識別子（インデックス）は、変換関数１６への入力であり、論理バケット識別子のある関数ｆ（インデックス）は、フラッシュメモリ内の物理バケット位置を生成する。この変換関数はバケット変換テーブル１７によって実装され、バケット変換テーブル１７は、対象フラッシュメモリ位置（フラッシュ内の物理バケット位置）への（インデックス付けアルゴリズムによって提供されるような）論理バケット識別子のマップである。フラッシュメモリ２６に格納されたディクショナリ（インデックス）は、ルックアップキー（例えば、オブジェクト名）を衛星データ（例えば、ディスク上に格納されたオブジェクトへの位置ポインタ）にマップするレコードを備えてもよい。
【００７９】
[041]次に、３つのインデックス付けオペレーションのうちどれが行われているか（ル
ックアップ、更新又は挿入）に応じて、図１の下半分に示されたステップのうち１つ又は複数が行われる。
【００８０】
[042]ルックアップオペレーション１８では、変換関数によって識別されたバケットエ
ントリは、キャッシュルックアサイドによる、フラッシュメモリ内の対象バケット２２からの読出し３０である（例えば、対象バケットがキャッシュに格納される場合、フラッシュメモリ２６からではなく、キャッシュ２３から読み出されてもよい）。
【００８１】
[043]更新オペレーション１９では、変換関数によって識別されたバケットエントリ（
元のバケットエントリ）が、フラッシュメモリ（又はキャッシュ）の消去ブロック２１ａ内の対象バケット２２から読み出され３０、バケットが更新され、キャッシュへ移動され３２、且つ、後続の書込み２４では、複数のキャッシュバケットエントリが、フラッシュメモリ内の部分ページの隣接するセット、複数のページ、及び、消去ブロック（例えば、新しい消去ブロック２１ｂ）のうちの１以上に順次読み出される。この処理は、フラッシュ内の全ての移動されたバケットのステータスを、有効ではないデータ（例えば、フリー、又は、トリムオペレーションのために使用可能）に更新する３３。
【００８２】
[044]挿入オペレーション２０では、対象バケットがフラッシュから再度読み出され、
修正されたバケットエントリが、フラッシュメモリ内の新しい位置への後続の順次書込み２４のために再度、キャッシュに移動される３４。
【００８３】
[045]図１は、隣接するフラッシュメモリバケットへの、キャッシュバケットエントリ
の集まりの順次書込み２４を行うことに先立って、複数のバケットエントリを集めるためのキャッシュ２３を概略的に示す。一実施形態では、スキャベンジングオペレーション２５が、フリー消去ブロックを作成するために使用され、この処理は、スキャベンジング処理中に（消去ブロックからの）任意の有効バケットをキャッシュに格納すること、及び、フラッシュ消去ブロックをフリーとして再割振りすることを含む。
【００８４】
[046]図２に例示された新しいデータ構造の考察に続いて、図１で参照されたインデッ
クス付けオペレーションが、図３〜６のフロー図に関してより具体的に説明される。
【００８５】
Ｃ．データ構造
[047]図２は、本発明において有用なデータ構造の様々な実施形態を例示する。そのよ
うなデータ構造は例示的なものであり、限定するものではない。
【００８６】
[048]図２Ａは、（インデックス付けアルゴリズムによって生成された）論理バケット
インデックスを、物理フラッシュバケットアドレスに変換するための、バケット変換テーブル（ＢＴＴ）３００の一実施形態を例示する。ＢＴＴテーブルエントリは、３つのフィールド、即ち、有効３０１、フラッシュ物理バケットアドレス３０２、及び、拡張バケット状態３０３を有して図示される。バケットアドレス粒度は、フラッシュデバイスの最小書込みサイズであり、即ち、（例えば、ＳＬＣ  ＮＡＮＤでの）部分ページ書込み、又は、（例えば、ＭＬＣ  ＮＡＮＤでの）ページ書込みである。ＢＴＴは、論理から物理バケットエントリへの１：１マッピングである。このテーブルは、より高いランダム性能（インデックス付けアルゴリズムによるランダム読出し及びランダム書込み）のために、フラッシュバケット割当ての再編成を可能とする。アルゴリズムのアクセラレーションを可能とするために、追加の状態情報がＢＴＴへ、第３のフィールド内に追加されてもよい。
【００８７】
[049]図２Ｂは、バケット有効テーブル（ＢＶＴ）３０５の一実施形態を示す。このテ
ーブルは、トリミングのためのブロックへのバケットのスキャベンジングを管理するために、フラッシュ内のどの物理バケットが有効であるかを追跡する。一例として、有効とラベル付けされたフィールド３０６は、小型のビット配列（１ビット／バケット）であってもよい。ＢＶＴのサイズは、フラッシュバケットエントリの総数であり、そのサブセットのみがＢＴＴによって使用中である。
【００８８】
[050]図２Ｃは、バケット内に含まれた複数のレコード３１０、３１１、３１２．．．
を、逆ＢＴＴポインタ３１３（バケット変換テーブル１７へのセルフインデックス）と共に有する、フラッシュバケット３０９の一実施形態を例示する。よって、各バケットは、１つ又は複数のレコードのセット、及び、フラッシュバケット（例えば、ページ）が挿入、移動又は削除されるとき、ＢＴＴを更新するための逆ポインタを含む。バケットの各要素（レコード又はポインタ）には、データ構造の個々の信頼性を向上させ、且つ、ストレージデバイスの有用寿命を著しく延ばすために、追加のＥＣＣビット等、冗長コンテンツが追加されてもよい。例えば、任意選択のシーケンス番号フィールドが、停電発生中にデータ一貫性チェックを行うためにフラッシュバケット３０９に追加されてもよく、他の最適化フラグも同様に提供されてもよい。
【００８９】
[051]レコードサイズはバケットサイズに比べて小さいので、これは、個々のレコード
ベースで追加の誤り回復情報を実装する（任意選択の）機会を提供する。この任意選択の機能は、訂正される可能性があるので下にあるストレージ技術の実効動作寿命を延ばす可能性のある、ビット誤り及び障害の数を増すことによって、ソリューションの全体の信頼性を向上させるようになる。
【００９０】
[052]図２Ｄは、複数の消去ブロック３１６（１からＭ）を含む、ＳＬＣ  ＮＡＮＤフ
ラッシュデバイス３１５の一例を示す。各消去ブロックは、複数のページ３１７（１からＮ）を含む。この例では、各ページは４ＫＢであり、各ページは複数のバケット３１８（１からＢ）を含み、各バケットは１ＫＢである。この例では、デバイスは部分ページ書込みをサポートする。
【００９１】
[053]バケットは、フラッシュデバイスの最小書込みサイズを表現する。典型的には、
バケットは１ページとなる。部分ページ書込みが可能にされる場合、１ページにつき４つのバケットをサポートする４部分ページＳＬＣ  ＮＡＮＤデバイス等、１フラッシュページにつき１つ又は複数のバケットが提供されてもよい。
【００９２】
[054]１つの消去ブロックにつき、複数のフラッシュページが提供される。１つのフラ
ッシュデバイスにつき複数の消去ブロックがあり、各ブロックは個々に消去される。
【００９３】
[055]典型的なフラッシュサブシステムは、複数のフラッシュデバイスからなる。ＮＡ
ＮＤフラッシュデバイスは、消去オペレーション間に所与のブロック内で１ページ（又は部分ページ）につき１回、順次書き込まれ、複数のブロックが、同時に書込み及び読出しを行うために使用可能である。
【００９４】
Ｄ．処理フローチャート
[056]図３は、キーの存在を検証し、関連付けられた衛星データを返すためのルックア
ップオペレーション処理の一実施形態を例示する。ステップ１  ４１で、ルックアップキーがルックアップ関数に入力される。ステップ２  ４２で、ルックアップ関数ｆ（キー）は、ハッシュテーブルルックアップをサポート（例えば、加速）する論理バケット識別子を生成する。論理バケット識別子は変換関数に入力され、変換関数は、ステップ３  ４３で、バケット変換テーブル（ＢＴＴ）１７を介してフラッシュメモリ（物理バケット）位置にマップされる。ステップ４  ４４で、バケットがキャッシュに格納されるまで、フラッシュメモリ内の対象バケットがフラッシュメモリから読み出され４５ａ、バケットがキャッシュに格納された場合、キャッシュ２３から読出し可能である４５ｂ。ステップ６  ４６で、キーのための衛星（レコード）データがインデックス付けアルゴリズムに返される。
【００９５】
[057]図４は、挿入オペレーション処理の一実施形態を示す。最初のステップ７１は、
キーをルックアップ関数に入力する。ステップ２  ７２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  ７３で、バケット識別子が変換関数に入力され、変換関数は、バケット変換テーブル（ＢＴＴ）１７を利用して、バケット識別子を、挿入が起こるべきフラッシュメモリ物理バケット位置へマップする。ステップ４  ７４で、挿入処理は、対象バケット位置を変換関数から受信する。ステップ５  ７５で、挿入処理は、対象バケット２２をフラッシュメモリの消去ブロック２１ａから７５ａ、或いはキャッシュから７５ｂ、読み出す。ステップ６  ７６で、挿入処理は、レコードエントリを対象バケットに挿入し、修正済みバケットをキャッシュに書き込む。ステップ７  ７７で、挿入処理によって、複数のバケットエントリ（修正済み対象バケットを含む）がキャッシュ７３から読み出される。ステップ８  ７８で、挿入処理は、キャッシュから読み出された修正済み対象バケット及び他のバケットを、フラッシュ２６内の新しい位置（消去ブロック２１ｂ内のページ）へ書き込む。ステップ９  ７９で、挿入処理は、キャッシュからフラッシュへ移動された全てのバケットのための新しい位置により、バケット変換テーブル１７を更新し７９ａ、また、移動された全てのバケットについて、ＢＶＴ内のバケット有効エントリをも更新する７９ｂ。ステップ１０  ８０で、挿入処理は、移動されたキャッシュエントリに、読出し専用（使用可能）とマークを付ける。ステップ１１  ８１で、挿入処理は、元のフラッシュバケット（このとき、新しい消去ブロックに移動済み）に、フリーとしてマークを付ける。
【００９６】
[058]図５は、削除オペレーション処理の一実施形態を例示する。最初のステップ９１
では、キーがルックアップ関数に提供される。ステップ２  ９２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  ９３で、バケット識別子が変換関数に提供され、変換関数は、バケット変換テーブル１７を利用して、バケット識別子を物理フラッシュメモリバケット位置へマップする。ステップ４
９４で、削除処理は、フラッシュメモリ位置を受信する。ステップ５  ９５で、対象バケットがフラッシュから読み出される。ステップ６  ９６で、処理は、バケット内の元のレコードエントリを削除し、修正済みバケットを（削除済みエントリと共に）キャッシュ２３に書き込む。ステップ７  ９７で、バケットのグループ（集まり）がキャッシュから読み出される。ステップ８  ９８で、キャッシュ２３から読み出された更新済み対象バケット及び他のバケットが、フラッシュ内のフリーページの隣接するセットに順次書き込まれる。ステップ９  ９９で、削除処理は、全ての移動されたバケットのためのフラッシュ内の新しい位置により、バケット変換テーブルを更新し９９ａ、ＢＶＴ内のそれらのバケット有効ステータスを更新する９９ｂ。ステップ１０  １００で、削除処理は、キャッシュエントリに、読出し専用としてマークを付ける。ステップ１１  １０１で、削除処理は、このとき、フラッシュ内の新しい位置に移動された元のフラッシュバケットに、フリーとしてマークを付ける。
【００９７】
[059]図６は、フラッシュメモリに格納されたインデックス内のレコードを修正するた
めの更新オペレーション処理の一実施形態を例示する。最初のステップ５１で、キーが入力としてルックアップ関数に提供される。ステップ２  ５２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。バケット識別子は変換関数に入力される。ステップ３  ５３で、変換関数は、バケット変換テーブル１７を利用して、バケット識別子を、更新が起こるべきフラッシュメモリ内の物理バケットへマップする。ステップ５  ５５で、対象バケットはフラッシュから５５ａ、或いはキャッシュから５５ｂ、読み出される。ステップ６  ５６で、エントリを更新した後、更新済みバケットがキャッシュ２３に書き込まれる。ステップ７  ５７で、バケットのグループがキャッシュ２３から読み出され、ステップ８  ５８で、キャッシュからフラッシュメモリ２６内の新しい位置へ順次書き込まれる。ステップ９  ５９で、更新処理は、全ての移動されたバケットのための新しい位置により、バケット変換テーブル１７を更新し５９ａ、ＢＶＴ
内のそれらの有効ステータスを更新する５９ｂ。ステップ１０  ６０で、更新処理は、移動されたエントリに、キャッシュ２３内で読出し専用（及び、よって上書きされるために使用可能）としてマークを付ける。最後に、ステップ１１  ６１で、更新処理は、このとき新しい位置に移動された元のフラッシュバケットに、フリー（使用可能）としてマークを付ける。
【００９８】
[060]図７Ａは、フリー消去ブロックを生成するための処理の一実施形態を例示し、（
ルックアップ、挿入又は修正等、アップストリームインデックス付けオペレーションによって生成された）デマンド読出しは、（対象バケットと）同じ消去ブロック内の追加のバケットを読み出す。図７Ａで、この処理は、更新要求と共に例示される。ステップ１  １１１で、キーがルックアップ関数に提供される。ステップ２  １１２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  １１３で、バケット識別子が、フラッシュ内の物理対象バケット位置にマップされる。ステップ４  １１４で、更新及びスキャベンジ処理は、対象フラッシュメモリ位置を受信する。ステップ５  １１５で、処理は、対象バケットと同じ消去ブロック内の全ての有効バケットを識別する。ステップ６  １１６で、更新処理は、対象バケット及び全ての識別された有効バケットを、対象バケットを含むフラッシュブロックから読み出す。ステップ７
１１７で、処理は、対象バケット内のレコードエントリを更新し、フラッシュブロックからの全ての有効バケットをキャッシュ２３に書き込む。ステップ８  １１８で、更新処理は、キャッシュからブロックのグループを読み出す。ステップ９  １１９で、更新処理は、キャッシュ２３から読み出された更新済み対象バケット及び他のバケットを、フラッシュ２６に書き込む。ステップ１０  １２０で、更新処理は、移動された（キャッシュからフラッシュ内の新しい消去ブロック２１ｂに書き込まれた）全てのバケットのための新しい位置により、バケット変換テーブル１７を更新し１２０ａ、ＢＶＴ内のバケットエントリを更新する１２０ｂ。ステップ１１  １２１で、更新処理は、このとき古いキャッシュエントリに、読出し専用としてマークを付ける。ステップ１２  １２２で、更新処理は、元のフラッシュブロック（対象ブロック内の全てのバケット）に、フリーとしてマークを付ける。
【００９９】
[061]図７Ｂは、フリー消去ブロックを生成するためにのみ記載された、ランダム読出
し処理の特定の実施形態を例示する。
【０１００】
[062]この実施形態では、置き換えハッシングインデックス付けアルゴリズム１２５は
、論理バケット１２６を生成する。インデックス付けアルゴリズムによって見なされる論理バケットサイズは、インデックス付けアルゴリズム及びフラッシュメモリが互換性を有するように、フラッシュ消去ブロックサイズに関連付けられる。これらのバケットは、インデックス読出し及び更新の結果として、ランダムに読み出されるようになる。
【０１０１】
[063]バケット変換（間接指定）テーブル１２７は、論理バケットインデックスを物理
フラッシュデバイスバケット位置に変換する。この間接指定テーブルは、インデックス付けアルゴリズムが、読出し、書込み及び更新のために、ランダムに動作し、且つ、フラッシュデバイスレベルで行われる大きい順次書込みをなお有することを可能とする。好ましくは、間接指定テーブルは永続メモリに格納されるが、揮発性メモリに格納される場合、必要に応じて再構築されうる。
【０１０２】
[064]間接指定テーブルの出力、即ち、物理デバイスバケット位置は、入力として、完
全連想バケットキャッシュ１２８に提供される。この実施形態では、空の消去ブロックｆｉｆｏ１２９のコンテンツがハイウォーターマークＱ未満である場合、消去ブロック全体（対象４ＫＢバケットを含む）が読み出される。
【０１０３】
[065]消去ブロックは論理バケットをホストし、典型的な構成は、１つの消去ブロック
が１６個の４ＫＢ論理バケットを保持するものである。物理デバイスは、負荷、例えば、９０％のために構成され、バケットの９０％が使用中であることを意味する。キャッシング及び犠牲化（ｖｉｃｔｉｍｉｚａｔｉｏｎ）（追い出し）は、残りのバケットの１０％の大部分がフリー消去ブロックに集中させられるように、フラッシュメモリ内で論理バケットをパックする（集中させる）ために、使用される。
【０１０４】
[066]キャッシュ犠牲化（追い出し処理）は、キャッシュ内に集められた１６個のバケ
ットを取り、それら１６個のバケットをキャッシュからフリー消去ブロック１３０に書き出す。消去ブロックはランダム読出しオペレーションによってランダムに触れられるので、読出しオペレーションは、フリー消去ブロックを生成するために使用されうる。論理バケット識別子を生成するための暗号ハッシュ関数の使用は、読出しオペレーションのランダム性を増大させ、よって、フリー消去ブロックのランダム読出し生成を改善するようになる。
【０１０５】
[067]図８Ａ及び８Ｂは、フリー消去ブロックを生成するための代替スキャベンジング
処理を例示する。このスキャベンジング処理は、何れかのインデックス付けオペレーションの一部ではない。むしろ、より下位レベルのデバイス管理層の一部として実装される。この処理では、フラッシュ消去ブロック内の物理バケットのグループ（一部又は全部）がフラッシュから直接読み出され、バケット有効テーブル２７が、消去ブロック内のどのバケットが有効であるかを決定するために使用される。
【０１０６】
[068]図８Ａに例示されるように、ステップ１  ２２０で、スキャベンジング処理２５
は、完全な消去ブロック２１ａを読み出す。ステップ２  ２２２で、スキャベンジング処理は、バケット有効テーブル２７を使用して、有効であるそれらの読出しの全てのバケットを識別する。ステップ３  ２２４で、各有効バケットについて、論理バケット識別子がバケットから抽出される。ステップ４  ２２６で、有効バケットがキャッシュ２３に格納され、各々はその論理バケット識別子によってインデックス付けされる。
【０１０７】
[069]図８Ｂは、ステップ１で、スキャベンジング処理２５がバケット［９４，９７］
を、９４及び９７を含めて読み出す一例を示す。ステップ２で、処理は、９５及び９６でのバケットが有効であると決定する。有効バケットは、「１」によって指定されたバケット有効テーブルにおいて示され、非有効バケットは「０」による。ステップ３で、バケット９５及び９６のための論理バケット識別子、即ち、タグ２３及び４９がそれぞれバケットから抽出される。ステップ４で、この２つのタグ並びにそれらの各バケット９５及び９６は、それらの各タグ２３、４９をインデックスとして使用して、キャッシュに挿入される。
【０１０８】
Ｅ．スタックレベルビュー及び実装
[070]本発明のもう１つのより具体的な実施例が、ここで図９〜１６を参照して説明さ
れる。
【０１０９】
[071]図９は、物理フラッシュメモリデバイス２１１によって望まれるものとは大変異
なるビューである、インデックス付けアルゴリズム２０３によって望まれたＩＯ使用プロファイルビューを、フラッシュアダプテーション層２０７が適合させる、本発明の一実装を例示するための６層のビュー又はスタック２００を示す。最高レベル２０１で、レコードのディクショナリ（インデックス）が提供され、それに対して、あるインデックス付けオペレーション２０４（レコードをルックアップ、削除、挿入且つ修正する）が必要とされる。インデックス付けアルゴリズム層２０３は、１つ又は複数のインデックス付けアルゴリズムによりディクショナリを実装し、例えば、カッコウ置き換えハッシングアルゴリ
ズムが一例である。インデックス付けアルゴリズムは、インデックスへのキーがどのようにインデックス永続層２０５によって格納されるかのビューを有する。インデックス付けビューは、論理ビューであり、論理アドレス位置を特定する。このビューは更に、サイズ、アラインメント及びタイミングについて、インデックスへのユニフォームアクセスが存在するようになること、及び、インデックスが可変（安定）ストレージ上に格納されることを仮定する。
【０１１０】
[072]インデックス永続層２０５は、インデックスのレコードを格納する物理バケット
を読み出し、それらの物理バケットに書き込むための論理バケットオペレーション２０６を提示するようになる。これらの論理バケットオペレーション２０６は、フラッシュアダプテーション層２０７に提示され、フラッシュアダプテーション層２０７は、前述のように、（インデックス付け処理の）論理バケットをフラッシュストレージデバイス上の物理バケット位置に変換する。フラッシュアダプテーション層は、よって、上記のインデックス付けアルゴリズムによって望まれたビュー及びＩＯ使用プロファイルを、下記の物理ストレージデバイス（フラッシュメモリ２１１）によって望まれた大変異なるビューに適合させる。ここで、物理バケットオペレーション２０８は、ランダム読出し及び集約（ブロック順次）書込みを含み、これらのランダム読出し及び集約（ブロック順次）書込みは、バケットアクセスのノンユニフォームモデルを構成する。この実施例の物理バケットオペレーションは、トリムコマンドを更に含んでもよい。
【０１１１】
[073]物理バケットオペレーションは、物理フラッシュデバイス上の資源を追跡且つ調
節する、デバイス管理層２０９によって実装される。これらの物理デバイスオペレーション２１０はここでは、ランダム読出し、大きい順次書込み及びトリムコマンドを含む。
【０１１２】
[074]物理デバイス層２１１は、そのノンユニフォーム読出し及び書込み、並びに、サ
イズ、アラインメント及びタイミングについての不変性によって特徴付けられる。そのような物理デバイスの例は、生のフラッシュ、相変化、ＳＳＤ、及びデバイス上に存在するフラッシュファイルシステムを有するフラッシュのうちの１以上を含む。
【０１１３】
[075]本発明は、以下のもの等、デバイス管理層より下の追加の任意選択の強化を可能
とする。
【０１１４】
・バケットトリミング（細かいページトリミング）及びページ内のバケット追跡のモデルは、ＳＳＤ又は同等のストレージデバイスのフラッシュファイルシステムに直接組み込まれる場合、よりよい消去ブロック管理を可能とする。
【０１１５】
・フラッシュページ上へのバケットのマッピングは、抽象化である。変化ごとにフラッシュに書き込まれたデータの量を最小化することによって、それらのデバイスの寿命を延ばすために、バケットは、ＳＬＣ  ＮＡＮＤのための部分ページへマップすることができる。バケットはまた、これがシステム全体の性能にとって有益であった場合、複数のフラッシュページ上にマップすることもできる。
【０１１６】
[076]図１０は、インデックスレコードの一例を示す。レコード１４０は、フィンガー
プリント（キー）を格納するための最初の２０バイトのフィールド１４１を含め、合計で３２バイトである。フィンガープリントは、好ましくはデータコンテンツの暗号ハッシュダイジェスト、例えば、ＳＨＡ−１ハッシュアルゴリズムである。例示を容易にするため、フィンガープリントを、「ＡＢ９２３４５Ｅ２０３．．．」等、１６進数で入力するのではなく、個々のフィンガープリントは、図１１〜１４において、Ｐ、Ｑ、Ｒ、Ｓ、Ｔ等、単一の大文字によって指定される。やはり例示のために簡潔にするため、これらの大文字はまた、レコード全体の代理としての役割も果たすようになる。レコードのフィールド
はまた、２バイトの参照カウントフィールド１４２、５バイトの物理ブロックアドレスフィールド１４３、１バイトのフラグフィールド１４４、及び、４バイトの雑フィールド１４５をも含む。ＰＢＡフィールド１４３は、指定されたフィンガープリント１４１のために、ディスク上で格納されたデータの物理ブロックアドレスへのポインタを含む。参照カウントは、ディスク上で格納されたデータへの参照の数を追跡する。
【０１１７】
[077]本発明の一実施形態によれば、インデックスレコードからのフィンガープリント
１４１は、前述（図１）のルックアップ関数ｆ（キー）への入力キーとして使用され、この実施例では、関数ｆ（キー）は、４つのハッシュ関数Ｈ０、Ｈ１、Ｈ２及びＨ３のセットを備える。一般に、２つ以上のハッシュ関数の任意のセットを使用することができる。ハッシュ関数Ｈｘは、フィンガープリントを、０及びＮ−１を含めて範囲[０，Ｎ−１]へマップし、但し、Ｎはハッシュテーブルのサイズである。この実施例では、フィンガープリント自体がハッシュであることを考えれば、ＢｉｔＦｉｅｌｄを抽出して、以下の４つのハッシュ値のファミリを生成することができる。
【０１１８】
Ｈ０（ｘ）＝ｘ＜０：３１＞ｍｏｄ  Ｎ
Ｈ１（ｘ）＝ｘ＜０３２：６３＞ｍｏｄ  Ｎ
Ｈ２（ｘ）＝ｘ＜０６４：９５＞ｍｏｄ  Ｎ
Ｈ３（ｘ）＝ｘ＜０９６：１２７＞ｍｏｄ  Ｎ
[078]抽出されたＢｉｔＦｉｅｌｄ幅は、ｌｏｇ２（Ｎ）以上である。ばらばらのビッ
トの任意の組み合わせを使用することができ、ｌｏｇ２（Ｎ）制約を受ける。図１０に例示されるように、最初のフィールド１４１内のフィンガープリントのみがハッシュされて、キーが形成される。レコード１４０の残りのコンテンツ（フィールド１４２〜１４５）は、値又はペイロードを備える。
【０１１９】
[079]図１１は、カッコウハッシングとして知られる、置き換えハッシングインデック
ス付けアルゴリズムの一例を例示する。例示を容易にするため、２つの関数のみが使用される。図１１Ａは、フィンガープリントＰがそれぞれ関数Ｈ０（ｘ）及びＨ１（ｘ）からハッシュ値２及び５を生成する一方、フィンガープリントＱがこれらの同じ関数からハッシュ値１及び３を生成する、２×３グリッドを示す。カッコウハッシングアルゴリズムは、０〜６のラベルが付けられた７個のスロット（図１１Ｂ）のうち１つにＰ及びＱを入れるための、２つの代替ハッシュ値の中から選択するようになる。Ｐは、２つの位置のうち１つ、２又は５に入る可能性があり、Ｑは、２つの位置のうち１つ、１又は３に入る可能性がある。図１１Ｃに示すように、このアルゴリズムは、Ｑを最下位の空スロット１に、Ｐをスロット２に入れる。この実施例では、レコードコンテナは、１つのレコードを保持するスロットとして見なされるが、本発明はそのように限定されず、インデックス付けアルゴリズムはまた、複数のレコードを保持するバケットをもコンテナと見なすことを理解されたい。ここでは、説明を簡素化するため、単一のレコードスロットが使用される。
【０１２０】
[080]このとき、もう１つのフィンガープリントＲが提供され、Ｒは、同じハッシュ関
数から１及び２のハッシュ値を生成する（図１１Ｄのテーブルを参照）。ハッシングアルゴリズムは、Ｒを左の位置、即ちスロット１に入れ、現在のエントリＱを変位させるようになる（図１１Ｅ）。Ｑはこのとき、Ｈ１（Ｑ）によって指定された他の任意選択の位置、即ち位置３に移動されるようになる。このアルゴリズムは、各レコードが空のスロットに入るまで、レコードを変位させ続けるようになる。
【０１２１】
[081]この実施例では、「Ｒを挿入する」オペレーションを達成するため、インデック
ス付けアルゴリズムは、以下の読出し及び書込み要求を生成する。
【０１２２】
１を読み出す（Ｑを得る）
２を読み出す（Ｐを得る）
１を書き込む（Ｒを書き込む）
３を読み出す（妥当性チェック）
３を書き込む（Ｑ）
[082]最初の２つの読出しは、Ｒがインデックス内にすでに存在しているのではないこ
とを検証するために使用される。妥当性チェック（３を読み出す）は、スロット番号３が空であるかどうかを決定し、そうである場合、Ｑがスロット３に書込み可能となり、どのエントリもスロット３に再書込みされなかったとき、このアルゴリズムは終了される。スロット３が空でなかった場合、スロット３内の現在のエントリが別のスロットに移動されることが必要となる。我々がビットマップを有する場合、スロット３のコンテンツは既知であり、そうでない場合、我々は、そのステータスを決定するために、スロット３内のエントリを読み出す必要がある。各エントリは、そのエントリが有効であるかどうかを示す有効ビットを含む。有効とは、それが使用中である（且つ、その位置を現在占有しているものが変位されなければならない）ことを意味する。有効ではないとは、その位置が空であることを意味し、処理中のレコードがそこに書込み可能である。有効ビットのコンテンツもまた、あるメモリを犠牲にして、別のビットマップに格納されうる。
【０１２３】
[083]カッコウハッシングアルゴリズムは、空のエントリに着地するまで、複数のエン
トリに渡って書き込み、以前のコンテンツを変位させ続けるという点において、再帰的である。実際には、この処理はめったに１回の変位を越えることはない。
【０１２４】
[084]インデックス付けアルゴリズムは、バケット及び個々のレコードオペレーション
を共に有する。インデックス付けアルゴリズムは、１つのレコードを１つのコンテナ（スロット）に入れることとして（図１１で）上述されるが、インデックス付けアルゴリズムによって、レコードがバケット、即ち、複数のレコードを含むバケットに集約されてもよいことは理解される。よって、上記の実施例は非限定的であり、概してレコードオペレーションを例示するものである。
【０１２５】
[085]前述のように、個々のレコードの読出し及び書込みは、フラッシュメモリにとっ
て効率的ではないので、個々のレコードはバケットに集約される。図１２は、各々が２つ以上のレコードを含む、４つのそのようなバケットを例示し、即ち、レコード位置０及び１を有するバケットＢ０、レコード位置２及び３を有するＢ１、レコード位置４及び５を有するＢ２、並びに、レコード位置６及びｘを有するＢ３である。バケットサイズはフラッシュデバイスによって決定された最小書込みサイズ、即ち、完全ページ書込み又は部分ページ書込みの関数である（且つ、好ましくはそれに等しい）。典型的なバケットサイズは、４ＫＢであってもよい。レコードの具体的な順序付けは、バケット内で必要とされない−−ルックアップオペレーション中にバケット全体が有効レコードについて検索されるので、レコードはバケット内のいかなる点でも挿入可能である。カッコウハッシングアルゴリズムによる置き換え時、バケット内のエントリはランダムに置き換えされうる。インデックス付けアルゴリズムは、よって、論理バケットを、ランダムな位置のように見えるものに、１つずつ書き込み、最終的にフラッシュアダプテーション層によって、フラッシュデバイスへのより大きい、物理的に隣接する（順次）書込みに集約される。
【０１２６】
[086]図１３は、バケットエントリ１６０の一例を例示する。４ＫＢのバケットサイズ
は、下にあるデバイスの最小書込みサイズ、ここでは４ＫＢのページに基づく。４ＫＢのバケットは、バケットエントリ内のレコードの数を指定する、４バイトの最初のフィールド１６１を含む。４バイトのタグフィールド１６２は、論理バケット識別子を指定する。この識別子（タグ）は論理アドレスであり、物理的なものではない。変換テーブルは、アルゴリズムバケットアドレス（ＡＢＡ）をフラッシュバケットアドレスＦＢＡにマップする。キャッシュは、（ＣＰＵの用語で）仮想キャッシュとして動作し、各キャッシュライ
ン（エントリ）は、タグ、この場合はＡＢＡによって識別される。アルゴリズムがレコードを要求するとき、キャッシュを通過中にそれが知ることは、要求されたＡＢＡがキャッシュされることのみであり、ＡＢＡがマップされるところ（ＦＢＡ）は、キャッシュの下端（例えば、図２Ｃにおける、ＢＴＴへの逆ポインタ３１３を参照）である。バケットは、複数のレコードＲ０、Ｒ１、Ｒ２．．．を保持するためのフィールド１６３を含み、各レコードは、３２バイトのサイズである。この例では、４ＫＢのバケットは、１バケットにつき（４０９６−４−４）／３２個のレコード、即ち、約１２７個のレコードを保持するようになる。
【０１２７】
[087]図１４は、一実施形態における、バケット、ページ及び消去ブロックの相対サイ
ズを例示する、フラッシュメモリデバイス１６４の概略図である。物理フラッシュデバイスは、２ＧＢのサイズであるチップ（パッケージ）１６５である。チップ上に、２つのダイ（シリコンウエハ）１６６ａ、１６７ｂがある。各ダイ上に、２＾１４個の消去ブロックがあってもよく、各消去ブロック１６７は典型的には６４ＫＢである。ページ１６８は、書込み可能である最小サイズ、ここでは４ＫＢであり、スタック（図９を参照）内のより上位で使用されるような、同じく４ＫＢである、バケット１６９のサイズを決定する。
【０１２８】
[088]図１５は、物理フラッシュデバイス上の資源を追跡且つ調節するためのデバイス
管理層（図９の２０９）の一実施形態による、選ばれたコンポーネントを例示する。図１５Ａは、（上部に）複数のページ（バケット）１７０と、その後に続く、どのページが有効であるか（１は有効、０は有効でない）を示す、ページアロケーションマップ１７１を示す。この下は、将来トリムされることになるが、まだそうされていないページの、保留中トリムマップ１７２である。ページアロケーション及び保留中トリムマップは、前述のような本発明の様々な実施形態では、バケットが有効データを保持するかどうかを決定する（図１に例示されたバケット有効テーブル２７を参照）するために使用されうる。
【０１２９】
[089]図１５Ｂは、消去ブロックインデックスによってインデックス付けされた、消去
ブロック記述子テーブル１７５の一例を例示する。各消去ブロック記述子エントリ１７６は、消去済みの数１７７、部分書込みの数１７８、部分読出しの数１７９、完全読出しの数１８０、完全書込みの数１８１、及び、誤りの数１８２を含む、複数のフィールドを含む。この情報は、本発明の様々な実施形態において前述されたように、フリー消去ブロックの生成において使用されうる。
【０１３０】
Ｆ．更なる実施形態
[090]本発明は、本願と同日に出願され、２００９年６月２６日出願の米国仮特許出願
第６１/２６９，６３３号に対する優先権を主張する、Ａ．Ｊ．Ｂｅａｖｅｒｓｏｎ及び
Ｐ．Ｂｏｗｄｅｎによる、同時係属の、所有者が同じであるＦｉｌｅ  Ｓｙｓｔｅｍ（ファイルシステム）という名称の米国特許出願第＿＿＿＿＿＿＿＿＿＿号に記載された、ファイルシステムのインデックスを実装するために使用されうる。両出願に対する優先権が本明細書で主張され、各々の完全な開示はそれらの全体として参照により本明細書に組み込まれる。
【０１３１】
[091]本発明の実施形態は、デジタル電子回路において、或いは、コンピュータハード
ウェア、ファームウェア、ソフトウェアにおいて、或いは、それらの組み合わせにおいて実装されうる。本発明の実施形態は、コンピュータプログラム製品として、即ち、情報キャリア内で、例えば、マシン可読ストレージデバイス内で、データ処理装置、例えば、プログラマブルプロセッサ、コンピュータ又は複数のコンピュータによる実行のため、或いはそれらのオペレーションを制御するために、有形に実施されたコンピュータプログラムとして実装されうる。コンピュータプログラムは、コンパイラ型又はインタープリタ型言語を含む任意の形式のプログラミング言語で書かれてよく、スタンドアロンのプログラム
又はモジュール、コンポーネント、サブルーチン若しくはコンピューティング環境で使用するために適した他のユニットを含む任意の形式で配置されうる。コンピュータプログラムは、１つのコンピュータ又は複数のコンピュータ上で実行されるように配置することができ、これら複数のコンピュータは、１つの場所にあるか又は複数の場所に渡って分散され通信ネットワークによって相互接続される。
【０１３２】
[092]本発明の実施形態の方法ステップは、１つ又は複数のプログラマブルプロセッサ
がコンピュータプログラムを実行して、入力データに関して動作し、出力を生成することにより、本発明の機能を行うことによって、行われうる。方法ステップはまた、専用論理回路、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）によって行われてもよく、本発明の装置は、専用論理回路、例えば、ＦＰＧＡ又はＡＳＩＣとして実装されうる。
【０１３３】
[093]コンピュータプログラムの実行に適したプロセッサは、例として、汎用及び専用
マイクロプロセッサ、及び、任意の種類のデジタルコンピュータの任意の１つ又は複数のプロセッサを含む。一般に、プロセッサは、命令及びデータを、読出し専用メモリ若しくはランダムアクセスメモリ又は両方から受信するようになる。コンピュータの必須要素は、命令を実行するためのプロセッサ、並びに、命令及びデータを格納するための１つ又は複数のメモリデバイスである。一般に、コンピュータはまた、データを格納するための１つ又は複数の大容量ストレージデバイス、例えば、磁気、光磁気ディスク若しくは光ディスクをも含むか、或いは、それらからデータを受信し、若しくはそれらへデータを転送するように動作可能に結合されるか、或いはその両方となる。コンピュータプログラム命令及びデータを実施するために適した情報キャリアは、例として、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリデバイス等、半導体メモリデバイスと、例えば、内蔵ハードディスク又はリムーバブルディスク等、磁気ディスクと、光磁気ディスクと、ＣＤ  ＲＯＭ及びＤＶＤ−ＲＯＭディスクとを含む、全ての形式の不揮発性メモリを含む。プロセッサ及びメモリは、専用論理回路によって補われるか又は専用論理回路に組み込まれうる。
【０１３４】
[094]前述の記載は、本発明の範囲を例示するためのものであり、限定するように意図
されないことを理解されたい。
【図１】
2015144022.tif 000003
【図２Ａ】
2015144022.tif 000004
【図２Ｂ】
2015144022.tif 000005
【図２Ｃ】
2015144022.tif 000006
【図２Ｄ】
2015144022.tif 000007
【図３】
2015144022.tif 000008
【図４】
2015144022.tif 000009
【図５】
2015144022.tif 000010
【図６】
2015144022.tif 000011
【図７Ａ】
2015144022.tif 000012
【図７Ｂ】
2015144022.tif 000013
【図８Ａ】
2015144022.tif 000014
【図８Ｂ】
2015144022.tif 000015
【図９】
2015144022.tif 000016
【図１０】
2015144022.tif 000017
【図１１】
2015144022.tif 000018
【図１２】
2015144022.tif 000019
【図１３】
2015144022.tif 000020
【図１４】
2015144022.tif 000021
【図１５】
2015144022.tif 000022
【手続補正書】
【提出日】平成27年4月9日(2015.4.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ユニフォームアクセスインデックス付け処理を、ノンユニフォームアクセスメモリに適合させる方法であって、前記方法は、
ａ）  インデックスレコードのディクショナリを前記ノンユニフォームアクセスメモリに記憶するステップであって、前記インデックスレコードはインデックスキーを含む、ステップと、
ｂ）  論理バケット識別子を前記メモリの物理バケット位置にマッピングするためのバケット変換テーブルを維持するステップであって、インデックスキーを置き換えハッシングすることにより論理バケット識別子を生成するステップを含み、前記テーブルは、前記論理バケット識別子の、関連付けられた前記インデックスレコードが記憶される前記メモリの物理バケット位置へのマッピングを含む、ステップと、
ｃ）  複数のバケットエントリであって各バケットエントリは同じ論理バケット識別子を有する複数のインデックスレコードのセットを含む複数のバケットエントリを、キャッシュ内に、前記メモリの隣接又は連続した複数の物理バケット位置への前記キャッシュからの複数のバケットエントリの集まりの順次書き込みとしての書き込みの前に集めるステップと、
ｄ）  前記バケット変換テーブルを、前記キャッシュから前記メモリに書き込まれる前記集まりの中の前記複数のバケットエントリに対する前記複数の物理バケット位置で更新するステップと
を含む方法。
【請求項２】
請求項１に記載の方法であって、１つ又は複数の順次インデックスレコードを、前記メモリから前記キャッシュへ読み出すステップと、
前記１つ又は複数の順次インデックスレコードが読み出されたメモリ内の物理位置を、フリーとして指定するステップと
を含む方法。
【請求項３】
請求項１に記載の方法であって、あるブロック内の任意の有効インデックスレコードを前記キャッシュに読み出すこと、及び、そのようなインデックスレコードが読み出された前記メモリ内の物理位置を、フリーとして指定することによって、前記メモリ内の複数の順次物理バケット位置をフリーブロックとするステップを含む方法。
【請求項４】
請求項１に記載の方法であって、複数の論理バケット識別子を前記インデックスキーに対して生成すること、前記置き換えハッシングの関数は、複数の生成された前記論理バケット識別子の間で選択することを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、前記メモリは、フラッシュメモリデバイス、相変化メモリデバイス及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、前記メモリは、ランダム書き込みアクセス時間、ランダム読み出し−修正−書き込みアクセス時間、順次書き込み、アラインメント制約、消去時間、消去ブロック境界及び摩耗のうちの１つ又は複数によって制限されることを特徴とする方法。
【請求項７】
請求項１に記載の方法であって、バケットサイズは、ページまたは部分ページ等の前記メモリの最小書き込みサイズの関数であることを特徴とする方法。
【請求項８】
請求項７に記載の方法であって、前記メモリは、複数のページを含む消去ブロックを有することを特徴とする方法。
【請求項９】
請求項１に記載の方法であって、前記メモリ内のどの物理バケット位置が有効であるかを追跡するためのバケット有効テーブルを維持するステップを含む方法。
【請求項１０】
請求項１に記載の方法であって、前記メモリの各物理バケット位置には、複数のインデックスレコードの前記セットとともに、前記バケット変換テーブル内へのセルフインデックスが記憶されることを特徴とする方法。
【請求項１１】
請求項１から１０のうちの何れか一項に記載の方法であって、前記物理バケット位置に記憶される前記インデックスレコードは順序付けされないことを特徴とする方法。
【請求項１２】
請求項１に記載の方法であって、前記バケット変換テーブルは、永続メモリに記憶されたことを特徴とする方法。
【請求項１３】
請求項１に記載の方法であって、消去ブロック内のフリー物理バケット位置の数を追跡し、フリーバケット位置のしきい値が満たされたとき、フリー消去ブロックを生成するための処理を実施するステップを含む方法。
【請求項１４】
請求項１に記載の方法であって、前記インデックス付け処理は、インデックスレコードが挿入、削除、ルックアップ及び修正のうちの１以上をされる要求に基づいて、インデックス付けオペレーションを行うことを特徴とする方法。
【請求項１５】
請求項１に記載の方法であって、前記インデックス付け処理は、前記インデックスレコードを記憶する物理バケット位置を読み出し該物理バケット位置に書き込むための論理バケットオペレーションを提示することを特徴とする方法。
【請求項１６】
請求項１に記載の方法であって、前記メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特徴とする方法。
【請求項１７】
請求項１６に記載の方法であって、ランダム読み出しオペレーションに応答して前記キャッシュに対する追加のバケットを読み出すことにより、フリー消去ブロックを生成するステップを含む方法。
【請求項１８】
請求項１６に記載の方法であって、スキャベンジング処理を実行して、前記キャッシュに消去ブロックを読み出すことによりフリー消去ブロックを生成するステップを含む方法。
【請求項１９】
コンピュータシステムに請求項１から１８の何れか一項に記載の方法の前記ステップを実行させるコンピュータプログラム。
【請求項２０】
コンピュータシステムであって、
ノンユニフォームアクセスメモリであって、前記メモリの物理バケット位置に記憶されたインデックスレコードのディクショナリを含む前記ノンユニフォームアクセスメモリと、
前記ディクショナリのインデックスキーの置き換えハッシングにより生成された論理バケット識別子を、該インデックスキーに関連付けられたインデックスレコードが記憶される前記メモリの物理バケット位置にマッピングするバケット変換テーブルと、
複数のバケットエントリを集めるためのキャッシュであって、各バケットエントリは、同じ論理バケット識別子を有する、前記メモリに書き込まれるべき複数のインデックスレコードのセットを含む、キャッシュと、
前記メモリの物理バケット位置にアクセスするための手段であって、該物理バケット位置は、ユニフォームアクセスインデックス付け処理により前記バケット変換テーブルに供給される論理バケット識別子にマッピングされる、手段と、
前記キャッシュからの前記複数のバケットエントリの集まりを、前記メモリの隣接又は連続した複数の物理バケット位置に順次書き込むための手段と、
前記バケット変換テーブルを前記集まりの中の前記複数のバケットエントリに対する前記複数の物理バケット位置で更新するための手段と
を含む、コンピュータシステム。
【請求項２１】
請求項２０に記載のコンピュータシステムであって、前記インデックスレコードを記憶する前記メモリは物理デバイス層を含み、該物理デバイス層は、ノンユニフォーム読み出し及び書き込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられるコンピュータシステム。
【請求項２２】
請求項２０に記載のコンピュータシステムであって、前記インデックスレコードを記憶する前記メモリは、フラッシュメモリデバイス、相変化メモリデバイス及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とするコンピュータシステム。
【請求項２３】
請求項２０に記載のコンピュータシステムであって、前記インデックスレコードを記憶する前記メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特徴とするコンピュータシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
[001]本発明は、多数のレコードにスケールし、高トランザクションレートを提供するインデックスの構築のための方法及び装置に関する。
【背景技術】
【０００２】
[002]幾つかの現代のファイルシステムは、ファイルデータ及び他の内部ファイルシステム構造（「メタデータ」）を格納するために、オブジェクトを使用する。ファイルは、多数の小さいオブジェクト、恐らくは４ＫＢ（２＾１２バイト）ほどの大きさに分割される。６４ＴＢ（２＾４６バイト）に及ぶファイルシステムでは、例えば、これは、２＾（４６−１２）＝２＾３４、即ち、およそ１６０億個を超えるオブジェクトを追跡し続ける結果となる。
【０００３】
[003]これに関連して、オブジェクトは、バイナリデータのシーケンスであり、しばしばＧＵＩＤ（グローバル一意ＩＤ）であるか、或いはコンテンツの暗号ハッシュである、オブジェクト名を有するが、各一意のオブジェクトが一意の名前を有する限り、他の命名規則は可能である。オブジェクト名は通常、人とは対照的に、プログラムによる使用向けの固定長のバイナリ文字列である。オブジェクトサイズは任意であるが、実際には、典型的には２の累乗であり、５１２バイト（２＾９）から最大１ＭＢ（２＾２０）に及ぶ。これに関連するオブジェクトは、Ｊａｖａ（登録商標）及びＣ＋＋等、プログラミング言語で使用されるようなオブジェクトと混同されるべきではない。
【０００４】
[004]全てのオブジェクトのインデックス（時として、ディクショナリ又はカタログと呼ばれる）は、ファイルシステムによって必要とされる。インデックス内の各レコードは、オブジェクト名、長さ、位置及び他の種々雑多な情報を含む場合がある。インデックスは、その主キーとして、オブジェクト名、オブジェクトの位置、又は場合によっては両方を有する場合がある。レコードは、数十バイト程度であり、３２バイトは一例である。
【０００５】
[005]このインデックスにおける動作は、エントリを追加すること、エントリをルックアップすること、エントリに修正を行うこと、及び、エントリを削除することを含む。これらは全て、任意のインデックスにおいて行われる典型的な動作である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
[006]これらのファイルシステムはオブジェクトと共に働くので、ファイルシステムが受け入れ可能な性能レベルを得るために、インデックス付けソリューションは、容易に対処されない２つの課題を有する。
【０００７】
１）インデックス内のエントリの数が大変大きくなる可能性がある。上記の例では、各インデックスエントリが３２（２＾５）バイトである場合、インデックスは、２＾（５＋３４）＝２＾３９、即ち、５１２ＧＢのメモリを要する。これは、現在のメモリ技術に高い費用対効果で適合しない。
【０００８】
２）インデックスに対する動作が大きい。商業的に実現可能なストレージシステムは、約２５６ＭＢ／秒（２＾２８バイト／秒）で行う必要のある場合がある。４ＫＢのオブジェクトサイズでは、それは、毎秒２＾（２８−１２）＝２＾１６、即ち、６４０００個の動作である。ファイルシステムが典型的には他のデータ（オブジェクト）を内部で生成且つ参照することを考えれば、インデックス動作レートは、１０００００動作／秒を容易に上回る可能性がある。比較のポイントとして、現在の最先端のディスクは、よくても毎秒４００個の動作しか行うことができない。
【０００９】
[007]必要な性能及び容量レベルを達成することは、ＤＲＡＭメモリ技術又はディスク技術のみを使用するのでは実際的ではない。ＤＲＡＭメモリは十分高速であるが、密度は十分ではない。ディスクは密度を有するが、性能を有していない。所望の特性に達するように、何れか（ＤＲＡＭメモリ又はディスク）をスケールすることは、費用がかかり過ぎる。
【００１０】
[008]オブジェクト名は、それらの分布においても、アクセスパターンにおいても、一様であることが多いので、空間及び時間局所性によって決まる典型的なキャッシングスキームの効果は限られている。よって、インデックス付けの問題は、サイズにおいても、動作レートにおいても、困難である。
【課題を解決するための手段】
【００１１】
[009]本発明の一実施形態によれば、ユニフォームアクセスインデックス付け処理によって、ノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法が提供され、この方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００１２】
一実施形態では、この方法は、
レコードデータエントリの集まりを、キャッシュからメモリのバケット位置へ、順次書込みとして書き込むステップと、
集まりのレコードデータエントリのためのバケット位置により、変換テーブルを更新するステップと
を含む。
【００１３】
一実施形態では、この方法は、
１つ又は複数の順次レコードデータエントリを、メモリからキャッシュへ読み出すステップと、
１つ又は複数のエントリが読み出されたメモリ内の物理位置を、フリーとして指定するステップと
を含む。
【００１４】
一実施形態では、この方法は、
ブロック内の任意の有効エントリをキャッシュに読み出すこと、及び、そのようなエントリが読み出されたメモリ内の物理位置を、フリーとして指定することによって、メモリ内の複数の順次物理バケット位置をフリーブロックとするステップを含む。
【００１５】
一実施形態では、
インデックス付け処理が、一律に配布され一意のインデックスキーに基づいて、インデックスへのランダムアクセス要求を生成する。
【００１６】
一実施形態では、
キーは、暗号ハッシュダイジェストを含む。
【００１７】
一実施形態では、
インデックス付け処理は、置き換えハッシングの処理を含む。
【００１８】
一実施形態では、
置き換え（ｄｉｓｐｌａｃｅｍｅｎｔ）ハッシングは、カッコウハッシング処理を含む。
【００１９】
一実施形態では、
メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含む。
【００２０】
一実施形態では、
メモリは、ランダム書込みアクセス時間、ランダム読出し−修正−書込みアクセス時間、順次書込み、アラインメント制約、消去時間、消去ブロック境界及び摩耗のうちの１つ又は複数によって制限される。
【００２１】
一実施形態では、
物理バケットのサイズは、メモリの最小書込みサイズを含む。
【００２２】
一実施形態では、
物理バケットのサイズは、ページ又は部分ページを含む。
【００２３】
一実施形態では、
メモリは、複数のページを含む消去ブロックを有する。
【００２４】
一実施形態では、この方法は、
メモリ内のどのバケット位置が有効であるかを追跡するためのバケット有効テーブルを維持するステップを含む。
【００２５】
一実施形態では、
メモリ内のバケットは、１つ又は複数のレコードデータエントリのセット、及び、バケット変換テーブルへのセルフインデックスを含む。
【００２６】
一実施形態では、
バケット内のレコードデータエントリは順序付けされない。
【００２７】
一実施形態では、この方法は、
メモリに順次書き込まれたレコードデータエントリを、キャッシュ内で読出し専用として指定するステップを含む。
【００２８】
一実施形態では、
バケット変換テーブルは、永続メモリに格納される。
【００２９】
一実施形態では、この方法は、
消去ブロック内のフリーバケットの数を追跡し、フリーバケットのしきい値が満たされたとき、フリー消去ブロックを生成するための処理を実施するステップを含む。
【００３０】
一実施形態では、
インデックス付け処理は、レコードが挿入、削除、ルックアップ及び修正のうちの１以上をされる要求に基づいて、インデックス付けオペレーションを行う。
【００３１】
一実施形態では、
インデックス付け処理は、インデックスのレコードを格納する物理バケットを読み出し該物理バケットに書き込むための、論理バケットオペレーションを提示する。
【００３２】
一実施形態では、
物理バケットオペレーションは、ランダム読出し及び順次書込みを含む。
【００３３】
一実施形態では、
物理バケットオペレーションは、トリムコマンドを更に含む。
【００３４】
一実施形態では、
メモリは、ノンユニフォーム読出し及び書込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられた物理デバイス層を含む。
【００３５】
一実施形態では、
レコードデータエントリは、キー、参照カウント及び物理ブロックアドレスのためのフィールドを含む。
【００３６】
一実施形態では、
キーは、データの暗号ハッシュダイジェストを含み、
物理ブロックアドレスフィールドは、ストレージデバイス上に格納されたデータの物理ブロックアドレスへのポインタを含む。
【００３７】
一実施形態では、
論理バケット位置は、複数のハッシュ関数によって生成される。
【００３８】
一実施形態では、
メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含む。
【００３９】
本発明の別の実施形態によれば、
プロセッサによって実行されるとき、前述の方法のステップを行うプログラムコード手段を含むコンピュータプログラム製品が提供される。
【００４０】
本発明の別の実施形態によればコンピュータ可読媒体が提供され、このコンピュータ可読媒体は、ユニフォームアクセスインデックス付け処理によってノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法のための実行可能プログラム命令を含み、上記方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００４１】
本発明の別の実施形態によれば、物理プロセッサと、コンピュータ可読媒体を含むメモリデバイスとを含むシステムが提供され、
該コンピュータ可読媒体は、ユニフォームアクセスインデックス付け処理によってノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法のための実行可能プログラム命令を含み、上記方法は、
インデックス付け処理によって生成された論理バケット識別子を、メモリの物理バケット位置にマップして、インデックス内の各レコードデータエントリにアクセスするために、変換テーブルを維持するステップと、
インデックスに書き込まれる複数のレコードデータエントリをキャッシュ内に集めるステップであって、該ステップは、メモリの少なくとも１つの物理バケット位置へのエントリの集まりの後続の順次書込みに先立つ、ステップと
を含む。
【００４２】
一実施形態では、
インデックスを格納するメモリは、ノンユニフォーム読出し及び書込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられた物理デバイス層を含む。
【００４３】
一実施形態では、
インデックスを格納するメモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含む。
【００４４】
一実施形態では、
インデックスを格納するメモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含む。
【００４５】
本発明の別の実施形態によれば、ユニフォームアクセスインデックス付け処理によって、ノンユニフォームアクセスメモリに格納されたインデックスにアクセスする方法が提供され、この方法は、
インデックス内のレコードデータエントリごとに論理バケット識別子をメモリの物理バケット位置にマップする変換テーブルに、インデックス付け処理によって生成された論理バケット識別子を提供するステップと、
論理バケット識別子にマップされた物理バケット位置にアクセスするステップと、
インデックスに書き込まれるレコードデータエントリをキャッシュ内に集めるステップと、
続いて、レコードデータエントリの集まりを、キャッシュから、メモリの少なくとも１つの新しい物理バケット位置におけるインデックスに順次書き込むステップと、
変換テーブルを更新して、少なくとも１つの新しい物理バケット位置を論理バケット識別子に関連付けるステップと
を含む。
【００４６】
本発明の別の実施形態によればあるコンピュータシステムが提供され、このコンピュータシステムは、
ノンユニフォームアクセスメモリであって、メモリの物理バケット位置においてレコードデータエントリを含むインデックスが格納される、ノンユニフォームアクセスメモリと、
ユニフォームアクセスインデックス付け処理によって生成された論理バケット識別子を、レコードデータエントリの各々のためのメモリの物理バケット位置にマップするための、変換テーブルと、
インデックスに書き込まれる集められたレコードデータエントリのためのキャッシュと、
メモリの物理バケット位置にアクセスする手段であって、該物理バケット位置は、インデックス付け処理によって変換テーブルに供給された論理バケット識別子にマップされた、手段と、
レコードデータエントリの集まりを、キャッシュから、メモリの少なくとも１つの物理バケット位置のインデックスに順次書き込む手段と、
変換テーブルを更新して、少なくとも１つの物理バケット位置を論理バケット識別子に関連付ける手段と
を含む。
【００４７】
[010]本発明は、以下の図面と共に、詳細な説明を参照することによって、より十分に理解される。
【図面の簡単な説明】
【００４８】
【図１】本発明の一実施形態により行われる、様々なインデックス付けオペレーションを例示する概略ブロック図である。
【図２Ａ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｂ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｃ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図２Ｄ】本発明で使用されうるデータ構造の様々な実施形態を例示する図である。
【図３】本発明の一実施形態によるルックアップオペレーションを例示する概略ブロック図である。
【図４】本発明の一実施形態による挿入オペレーションを例示する概略ブロック図である。
【図５】本発明の一実施形態による削除オペレーションの概略ブロック図である。
【図６】本発明の一実施形態による更新オペレーションの概略ブロック図である。
【図７Ａ】本発明の一実施形態によるフリー消去ブロックを生成するためのランダム読出し処理を例示する概略ブロック図である。
【図７Ｂ】本発明の一実施形態によるフリー消去ブロックを生成するためのランダム読出し処理を例示する概略ブロック図である。
【図８Ａ】スキャベンジング処理に従ってフリー消去ブロックを生成する別の方法を例示する概略ブロック図である。
【図８Ｂ】スキャベンジング処理に従ってフリー消去ブロックを生成する別の方法を例示する概略ブロック図である。
【図９】本発明の実装を例示するための６層のビュー又はスタックを例示する概略ブロック図である。
【図１０】本発明の一実施形態で使用されるようなレコードエントリの概略図である。
【図１１】図１１Ａ〜１１Ｅは、本発明の一実施形態によるカッコウハッシングの実装を概略的に例示する図である。
【図１２】本発明の一実施形態による、各バケットが複数のレコードを保持する、複数のバケットの概略的例示の図である。
【図１３】本発明の一実施形態によるバケットのコンテンツの概略図である。
【図１４】本発明の一実施形態による、複数のダイ、消去ブロック、ページ及びバケットを有する物理フラッシュチップの一例を例示する概略ブロック図である。
【図１５】図１５Ａ〜図１５Ｂは、本発明の一実施形態によるデバイス管理層のあるコンポーネントを例示する図である。
【発明を実施するための形態】
【００４９】
Ａ．概観
[011]本発明の１つ又は複数の実施形態によれば、特化されたメモリ技術及びアルゴリズムが使用されて、多数のレコード及びトランザクション要件を同時に有するインデックスが構築される。一実施形態は、置き換え（ｄｉｓｐｌａｃｅｍｅｎｔ）ハッシングインデックス付けアルゴリズム、例えばカッコウハッシングを利用する。本発明は、フラッシュ、相変化及びソリッドステートディスク（ＳＳＤ）メモリデバイス等、ノンユニフォームアクセスメモリ技術の使用を可能とする。
【００５０】
[012]本発明の様々な実施形態では、メモリデバイスが、メモリデバイスにとって効率的であるＩＯ（入力／出力）パターンに遭遇しながら、インデックス付けアルゴリズムがアルゴリズムにとって自然（効率的）である方法で行うことを保証するために、新しいデータ構造及び方法が提供される。
【００５１】
[013]インデックス付けアルゴリズムによって見なされた論理バケットを、メモリデバイス上の物理バケットにマップする、あるデータ構造である間接指定テーブルが作成される。このマッピングは、ノンユニフォームアクセスメモリデバイスへの書込み性能が強化されるようにするものである。
【００５２】
[014]キャッシュの追い出し及びライトバックポリシーの一部として、バケットを集め、メモリデバイスへ順次書き出すために、別のデータ構造である連想キャッシュが使用される。
【００５３】
[015]インデックス付けアルゴリズムによって必要とされる（レコードの）バケットでキャッシュをポピュレートするために、方法が使用される。追加のバケットは、デマンド読出し中に又はスキャベンジング処理によって、メモリデバイスからキャッシュへ読み出されてもよい。
【００５４】
[016]間接指定テーブルと併せた、キャッシュの使用は、メモリデバイスへの大きい順次書込みを可能にする。
【００５５】
[017]フラッシュ技術は、インデックス付け問題のために必要とされた容量及びＩＯレートを達成する基本機能を有するが、フラッシュアクセス特性はノンユニフォームである。このノンユニフォーム性はかなり十分なので、通常のインデックス付けアルゴリズムは、フラッシュメモリデバイスと共に、たとえ機能するとしても、うまく機能しない。
【００５６】
[018]本発明で使用されるノンユニフォームアクセスフラッシュメモリは、数百から数千ビットもの大きいブロックサイズで、即ち、バイトレベルのランダムアクセスではなく、読出し、書込み及び消去が行われなければならない、電気的消去可能プログラマブル読出し専用メモリ（ＥＥＰＲＯＭ）である。物理的には、フラッシュは、フローティングゲートトランジスタからなるメモリセルのアレイに情報を格納する、不揮発性メモリ形式である。２つのタイプのフラッシュメモリデバイス、ＮＡＮＤフラッシュ及びＮＯＲフラッシュがある。ＮＡＮＤフラッシュは、ＮＯＲフラッシュより高密度及び大容量をより低コストで提供し、より高速な消去、順次書込み及び順次読出し速度を有する。本願において、且つ本発明において使用されるとき、「フラッシュ」メモリは、ＮＡＮＤフラッシュメモリを包含するものであり、ＮＯＲメモリを包含しないものである。ＮＡＮＤは、各セルが１ビットの情報のみを格納するシングルレベルセル（ＳＬＣ）デバイス、及び、１つのセルにつき２ビット以上を格納することができる、より新しいマルチレベルセル（ＭＬＣ）デバイスを共に含む。ＮＡＮＤフラッシュは高速なアクセス時間を提供するが、ＰＣ内でメインメモリとして使用された揮発性ＤＲＡＭメモリほど高速ではない。フラッシュメモリデバイスは、フラッシュファイルシステムを含んでも含まなくてもよい。フラッシュファイルシステムは、典型的には、ウェアレベリング及び誤り訂正を行うために内蔵コントローラを有していない、内蔵フラッシュメモリと共に使用される。
【００５７】
[019]典型的なＮＡＮＤフラッシュチップは、数ＧＢのコンテンツを格納してもよい。コンピュータに取り付けられたメモリとは異なり、フラッシュチップ上のメモリは、あるサイズで、且つ、ある境界上でアクセスされなければならない。更に、メモリのセクションに書き込まれた後、それらのメモリ位置が再び書込み可能となる前に、消去オペレーションが行われなければならない。また、位置は徐々になくなるので、全ての位置が同様の数の書込みを得ることを保証することは、使用を更に複雑にする。読出し時間、書込み時間及び消去時間は、大幅に（数マイクロ秒から数ミリ秒まで）変わる可能性がある。よって、タイミング、ウェアレベリング及びアラインメント制約は、フラッシュの実際的な使用を困難にするのがせいぜいである。
【００５８】
[020]フラッシュメモリデバイスは、１つ又は複数のダイ（シリコンウエハ）を含んでもよい。各ダイは、大部分では、独立してアクセスされうる。
【００５９】
[021]ダイは、数千もの消去ブロックからなる。消去ブロックは典型的には、１２８〜５１２ＫＢのサイズである。データがクリアされる必要があるとき、消去ブロック境界上でクリアされなければならない。
【００６０】
[022]ＮＡＮＤフラッシュのもう１つの制限は、データが順次書き込まれることのみが可能であることである。更に、書込みのためのセットアップ時間は長く、読出しのセットアップ時間のおよそ１０倍である。
【００６１】
[023]データは、ページ粒度で読み出される。ページは、特定のフラッシュチップに応じて、１ＫＢから４ＫＢまでに及ぶ場合がある。各ページに関連付けられるものは、誤り訂正符号（ＥＣＣ）チェックサムのために使用されうる、数バイトである。
【００６２】
[024]データは、ページ粒度で書き込まれる。書き込まれた後、ページには、（当該ページを含む）その消去ブロックが消去されるまで、再度書き込むことができない場合がある。消去ブロックは、数十から１００を超えるページを含む場合がある。
【００６３】
[025]上記の読出し及び書込みページ粒度に対する１つの例外は、サブページ書込み、又は、部分ページプログラミングである。技術に応じて、ページは、消去が必要とされる前に最大４回、部分的に書き込ことができる場合がある。
【００６４】
[026]ＮＡＮＤフラッシュブロック内のページは順次、且つ、ブロック消去オペレーションとブロック消去オペレーションとの間に一度のみ書き込まれうるので、後続の書込みは、典型的には異なるフラッシュブロック内に位置する異なるページへの書込みを必要とする。ブロック消去の問題点は、フラッシュファイルシステムの機能である、書込み可能フラッシュブロックのプールを作成することによって、対処される。
【００６５】
[027]消去ブロックを消去することは、数ミリ秒を取りうるので、時間的に最も費用のかかるオペレーションである。（トラフィック的に）多用されるデバイスでは、消去ブロックが生成されうる速度（即ち、どのくらい速くフリー消去ブロックが使用可能にされうるか）は、フラッシュ設計における制限要因であることが多い。
【００６６】
[028]多数のＳＳＤ（ソリッドステートディスク）は、フラッシュ技術を使用する。ＳＳＤにおけるファームウェアは、フラッシュ変換層（ＦＴＬ）と呼ばれる層において、前述のアクセスの問題点に対処する。そうすることにおいて、しかし、ファームウェアは、どのようにＳＳＤが使用されるか（例えば、大部分は読出し、大部分は書込み、読出し及び書込みのサイズ及びアラインメント）について仮定を行い、これらの仮定の結果として、ＳＳＤの性能特性は、インデックス付けアルゴリズムにとって準最適であることが多い。
【００６７】
[029]人が文献において、また実際に発見する多数のインデックス付けアルゴリズムは、ユニフォームメモリアクセスモデルに基づいており、即ち、全てのメモリが、読出しでも書込みでも時間的に等しくアクセス可能であり、アクセスサイズ又はアラインメントにおけるいかなる一次制約もない。
【００６８】
[030]インデックス付けソリューションを考察する場合、挿入、削除、ルックアップ及び修正等のオペレーションは典型的には、より多くの多様な時間の量を必要とし、ブロック、典型的には小さいブロック（４ＫＢくらい）の読出し及び書込みは、より短い時間を必要とする。ブロックはランダムであるように見え、即ち、任意のブロックが読み出されてよく、任意の他のブロックが書き込まれてよい。幾つかのアルゴリズムでは、ランダム読出し−修正−書込みＩＯプロファイルがあり、即ち、ランダムブロックが読み出され、次いで、わずかに修正されたデータで同じ位置に書き戻される。
【００６９】
[031]インデックス付けアルゴリズムの効率的な動作を必要とするこのランダムＩＯは、フラッシュが提供するように意図されるものではない。フラッシュは、ランダム読出しをうまく扱うことができるが、読出し−修正−書込みがそうであるように、ランダム書込みは困難である。この理由は、すでに書き込まれたものを上書きすることはできず、まずそれを消去しなければならないからである。この状況を更に複雑にすることには、消去は時間を要し、大きい境界（典型的には６４ＫＢ）上で起こらなければならない。
【００７０】
[032]消去ブロックが消去されるとき、そのブロック内のいかなる有効データも他のところへ移動される必要がある。アルゴリズムがフラッシュデバイス中でランダムな４ＫＢブロックを書き込む場合、単純な実装は、その間ずっとブロックが消去され続ける結果となる。消去時間は遅いので、性能がかなり損なわれることになる。
【００７１】
[033]本発明によれば、フラッシュへの書込みを順次にすることを可能にするため、インデックス付けアルゴリズムが期待する論理ランダムアクセスをなお保ちながら、変換又は間接指定テーブルが作成される。このテーブルは、インデックス付けアルゴリズムによって必要とされるような（レコードの）論理バケットを、フラッシュデバイスの物理バケット（例えば、ページ）にマップする。
【００７２】
[034]インデックス付けアルゴリズムがバケット（例えば、フラッシュからのデータのページ）を読み込むとき、バケットコンテンツを修正（挿入、更新又は削除オペレーション）するために、バケットはキャッシュに移動される。フラッシュデバイス上の対応するバケットにはこのとき、有効ではない（フリー）としてマークが付けられうる。ＳＳＤの場合、これはＴＲＩＭコマンドの形式を取りうる。
【００７３】
[035]本発明の更なる実施形態によれば、フリー消去ブロックを生成するために、方法が提供される。いかなる所与の時間でも、消去ブロックは、有効及び無効データの組み合わせを有する場合がある。消去ブロックを解放するため、全ての有効データは、そのブロックから離れるように移動されなければならない。これを達成するために使用されうる、２つの機構がある。１つは、インデックス付けアルゴリズムによって生成されたランダム読出しを使用して、（インデックス付けアルゴリズムによって必要とされるよりも）より多くを読出し、消去ブロックを解放するようにすることである。インデックス付けアルゴリズムはランダム読出しを生成する傾向があるので、経時的に、全ての消去ブロックは最終的に読み出され、空のページのために集積される。例えば、読出しを含む消去ブロックが、幾つかのフリーページ及び幾つかの有効ページを有する場合、アルゴリズムは、消去ブロック全体を読み込み、且つ、全ての有効ページをキャッシュに入れることを選択してもよい。これは、後続の消去及び次いで書込みのために、その消去ブロックを解放する効果を有する。
【００７４】
[036]別法として、例えば、前述のランダム読出し処理が十分に高速でない場合、消去ブロックを読み出し、別の消去ブロックと合体するために有効ページをキャッシュに入れるために、分離したスキャベンジング処理（例えば、スレッド）が使用されうる。
【００７５】
[037]キャッシュが一杯になるとき、エントリが書き出されなければならない。キャッシュエントリのセットが集められ、複数の部分ページ（部分ページ書込みがフラッシュデバイスによって可能にされる場合）、複数のページ及び１つ又は複数の消去ブロックのうちの１以上の隣接又は連続するセットへと、順次書き込まれるようになる。キャッシュエントリがフラッシュデバイスに書き込まれるとき、間接指定テーブルは更新されるので、インデックス付けアルゴリズムはなお、エントリが固定された論理アドレスにあるものと見なす。
【００７６】
Ｂ．インデックス付けオペレーション
[038]本発明の様々な実施形態がここで、添付の図１〜６を利用して説明され、本発明に従って行われた様々なインデックス付けオペレーションが例示される。図７〜８は、ストレージ媒体（例えば、フラッシュメモリ）の効率的利用のためにフリー消去ブロックを生成する、２つの方法を例示する。これらの実施形態は例示的なものであり、限定するものではない。
【００７７】
[039]図１は、本発明の一実施形態による、バケット変換テーブル１７及びキャッシュ２３を利用する幾つかのインデックス付けオペレーションの概観である。図１の上部に、３つのインデックスオペレーション１２〜１４が、ルックアップ関数１５及び変換関数１６への代替入力として示される。第１のインデックスオペレーション１２は、キーのための（レコードエントリ）から衛星データを返すための「キーをルックアップする」である。第２のインデックスオペレーション１３は、キーのためのレコードエントリを更新（修正）するための「キーのための衛星データを更新する」である。第３のインデックスオペレーション１４は、新しいレコードエントリを挿入するための「新しいキーを挿入する」である。もう１つのインデックスオペレーションである削除は、図１では図示されないが、図５に関して後述される。
【００７８】
[040]全ての３つのインデックスオペレーションは、最初にルックアップ関数１５を行い、キーのある関数ｆ（キー）が使用されて、インデックスが生成され、ここでは、ハッシュテーブルルックアップをサポート（例えば、加速）する論理バケット識別子である。バケット識別子（インデックス）は、変換関数１６への入力であり、論理バケット識別子のある関数ｆ（インデックス）は、フラッシュメモリ内の物理バケット位置を生成する。この変換関数はバケット変換テーブル１７によって実装され、バケット変換テーブル１７は、対象フラッシュメモリ位置（フラッシュ内の物理バケット位置）への（インデックス付けアルゴリズムによって提供されるような）論理バケット識別子のマップである。フラッシュメモリ２６に格納されたディクショナリ（インデックス）は、ルックアップキー（例えば、オブジェクト名）を衛星データ（例えば、ディスク上に格納されたオブジェクトへの位置ポインタ）にマップするレコードを備えてもよい。
【００７９】
[041]次に、３つのインデックス付けオペレーションのうちどれが行われているか（ルックアップ、更新又は挿入）に応じて、図１の下半分に示されたステップのうち１つ又は複数が行われる。
【００８０】
[042]ルックアップオペレーション１８では、変換関数によって識別されたバケットエントリは、キャッシュルックアサイドによる、フラッシュメモリ内の対象バケット２２からの読出し３０である（例えば、対象バケットがキャッシュに格納される場合、フラッシュメモリ２６からではなく、キャッシュ２３から読み出されてもよい）。
【００８１】
[043]更新オペレーション１９では、変換関数によって識別されたバケットエントリ（元のバケットエントリ）が、フラッシュメモリの消去ブロック２１ａ内の対象バケット２２（又はキャッシュ）から読み出され３０、バケットが更新され、キャッシュへ移動され３２、且つ、後続の書込み２４では、複数のキャッシュバケットエントリが、フラッシュメモリ内の複数の部分ページ、複数のページ、及び、複数の消去ブロック（例えば、新しい消去ブロック２１ｂ）のうちの１以上の隣接又は連続するセットに順次読み出される。この処理は、フラッシュ内の全ての移動されたバケットのステータスを、有効ではないデータ（例えば、フリー、又は、トリムオペレーションのために使用可能）に更新する３３。
【００８２】
[044]挿入オペレーション２０では、対象バケットがフラッシュから再度読み出され、修正されたバケットエントリが、フラッシュメモリ内の新しい位置への後続の順次書込み２４のために再度、キャッシュに移動される３４。
【００８３】
[045]図１は、隣接又は連続するフラッシュメモリバケットへの、キャッシュバケットエントリの集まりの順次書込み２４を行うことに先立って、複数のバケットエントリを集めるためのキャッシュ２３を概略的に示す。一実施形態では、スキャベンジングオペレーション２５が、フリー消去ブロックを作成するために使用され、この処理は、スキャベンジング処理中に（消去ブロックからの）任意の有効バケットをキャッシュに格納すること、及び、フラッシュ消去ブロックをフリーとして再割振りすることを含む。
【００８４】
[046]図２に例示された新しいデータ構造の考察に続いて、図１で参照されたインデックス付けオペレーションが、図３〜６のフロー図に関してより具体的に説明される。
【００８５】
Ｃ．データ構造
[047]図２は、本発明において有用なデータ構造の様々な実施形態を例示する。そのようなデータ構造は例示的なものであり、限定するものではない。
【００８６】
[048]図２Ａは、（インデックス付けアルゴリズムによって生成された）論理バケットインデックスを、物理フラッシュバケットアドレスに変換するための、バケット変換テーブル（ＢＴＴ）３００の一実施形態を例示する。ＢＴＴテーブルエントリは、３つのフィールド、即ち、有効３０１、フラッシュ物理バケットアドレス３０２、及び、拡張バケット状態３０３を有して図示される。バケットアドレス粒度は、フラッシュデバイスの最小書込みサイズであり、即ち、（例えば、ＳＬＣ  ＮＡＮＤでの）部分ページ書込み、又は、（例えば、ＭＬＣ  ＮＡＮＤでの）ページ書込みである。ＢＴＴは、論理から物理バケットエントリへの１：１マッピングである。このテーブルは、より高いランダム性能（インデックス付けアルゴリズムによるランダム読出し及びランダム書込み）のために、フラッシュバケット割当ての再編成を可能とする。アルゴリズムのアクセラレーションを可能とするために、追加の状態情報がＢＴＴへ、第３のフィールド内に追加されてもよい。
【００８７】
[049]図２Ｂは、バケット有効テーブル（ＢＶＴ）３０５の一実施形態を示す。このテーブルは、トリミングのためのブロックへのバケットのスキャベンジングを管理するために、フラッシュ内のどの物理バケットが有効であるかを追跡する。一例として、有効とラベル付けされたフィールド３０６は、小型のビット配列（１ビット／バケット）であってもよい。ＢＶＴのサイズは、フラッシュバケットエントリの総数であり、そのサブセットのみがＢＴＴによって使用中である。
【００８８】
[050]図２Ｃは、バケット内に含まれた複数のレコード３１０、３１１、３１２．．．を、逆ＢＴＴポインタ３１３（バケット変換テーブル１７へのセルフインデックス）と共に有する、フラッシュバケット３０９の一実施形態を例示する。よって、各バケットは、１つ又は複数のレコードのセット、及び、フラッシュバケット（例えば、ページ）が挿入、移動又は削除されるとき、ＢＴＴを更新するための逆ポインタを含む。バケットの各要素（レコード又はポインタ）には、データ構造の個々の信頼性を向上させ、且つ、ストレージデバイスの有用寿命を著しく延ばすために、追加のＥＣＣビット等、冗長コンテンツが追加されてもよい。例えば、任意選択のシーケンス番号フィールドが、停電発生中にデータ一貫性チェックを行うためにフラッシュバケット３０９に追加されてもよく、他の最適化フラグも同様に提供されてもよい。
【００８９】
[051]レコードサイズはバケットサイズに比べて小さいので、これは、個々のレコードベースで追加の誤り回復情報を実装する（任意選択の）機会を提供する。この任意選択の機能は、訂正される可能性があるので下にあるストレージ技術の実効動作寿命を延ばす可能性のある、ビット誤り及び障害の数を増すことによって、ソリューションの全体の信頼性を向上させるようになる。
【００９０】
[052]図２Ｄは、複数の消去ブロック３１６（１からＭ）を含む、ＳＬＣ  ＮＡＮＤフラッシュデバイス３１５の一例を示す。各消去ブロックは、複数のページ３１７（１からＮ）を含む。この例では、各ページは４ＫＢであり、各ページは複数のバケット３１８（１からＢ）を含み、各バケットは１ＫＢである。この例では、デバイスは部分ページ書込みをサポートする。
【００９１】
[053]バケットは、フラッシュデバイスの最小書込みサイズを表現する。典型的には、バケットは１ページとなる。部分ページ書込みが可能にされる場合、１ページにつき４つのバケットをサポートする４部分ページＳＬＣ  ＮＡＮＤデバイス等、１フラッシュページにつき１つ又は複数のバケットが提供されてもよい。
【００９２】
[054]１つの消去ブロックにつき、複数のフラッシュページが提供される。１つのフラッシュデバイスにつき複数の消去ブロックがあり、各ブロックは個々に消去される。
【００９３】
[055]典型的なフラッシュサブシステムは、複数のフラッシュデバイスからなる。ＮＡＮＤフラッシュデバイスは、消去オペレーションと消去オペレーションとの間に所与のブロック内で１ページ（又は部分ページ）につき１回、順次書き込まれ、複数のブロックが、同時に書込み及び読出しを行うために使用可能である。
【００９４】
Ｄ．処理フローチャート
[056]図３は、キーの存在を検証し、関連付けられた衛星データを返すためのルックアップオペレーション処理の一実施形態を例示する。ステップ１  ４１で、ルックアップキーがルックアップ関数に入力される。ステップ２  ４２で、ルックアップ関数ｆ（キー）は、ハッシュテーブルルックアップをサポート（例えば、加速）する論理バケット識別子を生成する。論理バケット識別子は変換関数に入力され、変換関数は、ステップ３  ４３で、バケット変換テーブル（ＢＴＴ）１７を介してフラッシュメモリ（物理バケット）位置にマップされる。ステップ４  ４４で、バケットがキャッシュに格納されるまで、フラッシュメモリ内の対象バケットがフラッシュメモリから読み出され４５ａ、バケットがキャッシュに格納された場合、キャッシュ２３から読出し可能である４５ｂ。ステップ６  ４６で、キーのための衛星（レコード）データがインデックス付けアルゴリズムに返される。
【００９５】
[057]図４は、挿入オペレーション処理の一実施形態を示す。最初のステップ７１は、キーをルックアップ関数に入力する。ステップ２  ７２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  ７３で、バケット識別子が変換関数に入力され、変換関数は、バケット変換テーブル（ＢＴＴ）１７を利用して、バケット識別子を、挿入が起こるべきフラッシュメモリ物理バケット位置へマップする。ステップ４  ７４で、挿入処理は、対象バケット位置を変換関数から受信する。ステップ５  ７５で、挿入処理は、対象バケット２２をフラッシュメモリの消去ブロック２１ａから７５ａ、或いはキャッシュから７５ｂ、読み出す。ステップ６  ７６で、挿入処理は、レコードエントリを対象バケットに挿入し、修正済みバケットをキャッシュに書き込む。ステップ７  ７７で、挿入処理によって、複数のバケットエントリ（修正済み対象バケットを含む）がキャッシュ７３から読み出される。ステップ８  ７８で、挿入処理は、キャッシュから読み出された修正済み対象バケット及び他のバケットを、フラッシュ２６内の新しい位置（消去ブロック２１ｂ内のページ）へ書き込む。ステップ９  ７９で、挿入処理は、キャッシュからフラッシュへ移動された全てのバケットのための新しい位置により、バケット変換テーブル１７を更新し７９ａ、また、移動された全てのバケットについて、ＢＶＴ内のバケット有効エントリをも更新する７９ｂ。ステップ１０  ８０で、挿入処理は、移動されたキャッシュエントリに、読出し専用（使用可能）とマークを付ける。ステップ１１  ８１で、挿入処理は、元のフラッシュバケット（このとき、新しい消去ブロックに移動済み）に、フリーとしてマークを付ける。
【００９６】
[058]図５は、削除オペレーション処理の一実施形態を例示する。最初のステップ９１では、キーがルックアップ関数に提供される。ステップ２  ９２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  ９３で、バケット識別子が変換関数に提供され、変換関数は、バケット変換テーブル１７を利用して、バケット識別子を物理フラッシュメモリバケット位置へマップする。ステップ４  ９４で、削除処理は、フラッシュメモリ位置を受信する。ステップ５  ９５で、対象バケットがフラッシュから読み出される。ステップ６  ９６で、処理は、バケット内の元のレコードエントリを削除し、修正済みバケットを（削除済みエントリと共に）キャッシュ２３に書き込む。ステップ７  ９７で、バケットのグループ（集まり）がキャッシュから読み出される。ステップ８  ９８で、キャッシュ２３から読み出された更新済み対象バケット及び他のバケットが、フラッシュ内のフリーページの隣接又は連続するセットに順次書き込まれる。ステップ９  ９９で、削除処理は、全ての移動されたバケットのためのフラッシュ内の新しい位置により、バケット変換テーブルを更新し９９ａ、ＢＶＴ内のそれらのバケット有効ステータスを更新する９９ｂ。ステップ１０  １００で、削除処理は、キャッシュエントリに、読出し専用としてマークを付ける。ステップ１１  １０１で、削除処理は、このとき、フラッシュ内の新しい位置に移動された元のフラッシュバケットに、フリーとしてマークを付ける。
【００９７】
[059]図６は、フラッシュメモリに格納されたインデックス内のレコードを修正するための更新オペレーション処理の一実施形態を例示する。最初のステップ５１で、キーが入力としてルックアップ関数に提供される。ステップ２  ５２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。バケット識別子は変換関数に入力される。ステップ３  ５３で、変換関数は、バケット変換テーブル１７を利用して、バケット識別子を、更新が起こるべきフラッシュメモリ内の物理バケットへマップする。ステップ５  ５５で、対象バケットはフラッシュから５５ａ、或いはキャッシュから５５ｂ、読み出される。ステップ６  ５６で、エントリを更新した後、更新済みバケットがキャッシュ２３に書き込まれる。ステップ７  ５７で、バケットのグループがキャッシュ２３から読み出され、ステップ８  ５８で、キャッシュからフラッシュメモリ２６内の新しい位置へ順次書き込まれる。ステップ９  ５９で、更新処理は、全ての移動されたバケットのための新しい位置により、バケット変換テーブル１７を更新し５９ａ、ＢＶＴ内のそれらの有効ステータスを更新する５９ｂ。ステップ１０  ６０で、更新処理は、移動されたエントリに、キャッシュ２３内で読出し専用（及び、よって上書きされるために使用可能）としてマークを付ける。最後に、ステップ１１  ６１で、更新処理は、このとき新しい位置に移動された元のフラッシュバケットに、フリー（使用可能）としてマークを付ける。
【００９８】
[060]図７Ａは、フリー消去ブロックを生成するための処理の一実施形態を例示し、（ルックアップ、挿入又は修正等、アップストリームインデックス付けオペレーションによって生成された）デマンド読出しは、（対象バケットと）同じ消去ブロック内の追加のバケットを読み出す。図７Ａで、この処理は、更新要求と共に例示される。ステップ１  １１１で、キーがルックアップ関数に提供される。ステップ２  １１２で、ルックアップ関数ｆ（キー）は、インデックス、ここでは論理バケット識別子を生成する。ステップ３  １１３で、バケット識別子が、フラッシュ内の物理対象バケット位置にマップされる。ステップ４  １１４で、更新及びスキャベンジ処理は、対象フラッシュメモリ位置を受信する。ステップ５  １１５で、処理は、対象バケットと同じ消去ブロック内の全ての有効バケットを識別する。ステップ６  １１６で、更新処理は、対象バケット及び全ての識別された有効バケットを、対象バケットを含むフラッシュブロックから読み出す。ステップ７  １１７で、処理は、対象バケット内のレコードエントリを更新し、フラッシュブロックからの全ての有効バケットをキャッシュ２３に書き込む。ステップ８  １１８で、更新処理は、キャッシュからブロックのグループを読み出す。ステップ９  １１９で、更新処理は、キャッシュ２３から読み出された更新済み対象バケット及び他のバケットを、フラッシュ２６に書き込む。ステップ１０  １２０で、更新処理は、移動された（キャッシュからフラッシュ内の新しい消去ブロック２１ｂに書き込まれた）全てのバケットのための新しい位置により、バケット変換テーブル１７を更新し１２０ａ、ＢＶＴ内のバケットエントリを更新する１２０ｂ。ステップ１１  １２１で、更新処理は、このとき古いキャッシュエントリに、読出し専用としてマークを付ける。ステップ１２  １２２で、更新処理は、元のフラッシュブロック（対象ブロック内の全てのバケット）に、フリーとしてマークを付ける。
【００９９】
[061]図７Ｂは、フリー消去ブロックを生成するためにのみ記載された、ランダム読出し処理の特定の実施形態を例示する。
【０１００】
[062]この実施形態では、置き換えハッシングインデックス付けアルゴリズム１２５は、論理バケット１２６を生成する。インデックス付けアルゴリズムによって見なされる論理バケットサイズは、インデックス付けアルゴリズム及びフラッシュメモリが互換性を有するように、フラッシュ消去ブロックサイズに関連付けられる。これらのバケットは、インデックス読出し及び更新の結果として、ランダムに読み出されるようになる。
【０１０１】
[063]バケット変換（間接指定）テーブル１２７は、論理バケットインデックスを物理フラッシュデバイスバケット位置に変換する。この間接指定テーブルは、インデックス付けアルゴリズムが、読出し、書込み及び更新のために、ランダムに動作し、且つ、フラッシュデバイスレベルで行われる大きい順次書込みをなお有することを可能とする。好ましくは、間接指定テーブルは永続メモリに格納されるが、揮発性メモリに格納される場合、必要に応じて再構築されうる。
【０１０２】
[064]間接指定テーブルの出力、即ち、物理デバイスバケット位置は、入力として、完全連想バケットキャッシュ１２８に提供される。この実施形態では、空の消去ブロックｆｉｆｏ１２９のコンテンツがハイウォーターマークＱ未満である場合、消去ブロック全体（対象４ＫＢバケットを含む）が読み出される。
【０１０３】
[065]消去ブロックは論理バケットをホストし、典型的な構成は、１つの消去ブロックが１６個の４ＫＢ論理バケットを保持するものである。物理デバイスは、負荷、例えば、９０％のために構成され、バケットの９０％が使用中であることを意味する。キャッシング及び犠牲化（ｖｉｃｔｉｍｉｚａｔｉｏｎ）（追い出し）は、残りのバケットの１０％の大部分がフリー消去ブロックに集中させられるように、フラッシュメモリ内で論理バケットをパックする（集中させる）ために、使用される。
【０１０４】
[066]キャッシュ犠牲化（追い出し処理）は、キャッシュ内に集められた１６個のバケットを取り、それら１６個のバケットをキャッシュからフリー消去ブロック１３０に書き出す。消去ブロックはランダム読出しオペレーションによってランダムに触れられるので、読出しオペレーションは、フリー消去ブロックを生成するために使用されうる。論理バケット識別子を生成するための暗号ハッシュ関数の使用は、読出しオペレーションのランダム性を増大させ、よって、フリー消去ブロックのランダム読出し生成を改善するようになる。
【０１０５】
[067]図８Ａ及び８Ｂは、フリー消去ブロックを生成するための代替スキャベンジング処理を例示する。このスキャベンジング処理は、何れかのインデックス付けオペレーションの一部ではない。むしろ、より下位レベルのデバイス管理層の一部として実装される。この処理では、フラッシュ消去ブロック内の物理バケットのグループ（一部又は全部）がフラッシュから直接読み出され、バケット有効テーブル２７が、消去ブロック内のどのバケットが有効であるかを決定するために使用される。
【０１０６】
[068]図８Ａに例示されるように、ステップ１  ２２０で、スキャベンジング処理２５は、完全な消去ブロック２１ａを読み出す。ステップ２  ２２２で、スキャベンジング処理は、バケット有効テーブル２７を使用して、有効であるそれらの読出しの全てのバケットを識別する。ステップ３  ２２４で、各有効バケットについて、論理バケット識別子がバケットから抽出される。ステップ４  ２２６で、有効バケットがキャッシュ２３に格納され、各々はその論理バケット識別子によってインデックス付けされる。
【０１０７】
[069]図８Ｂは、ステップ１で、スキャベンジング処理２５がバケット［９４，９７］を、９４及び９７を含めて読み出す一例を示す。ステップ２で、処理は、９５及び９６でのバケットが有効であると決定する。有効バケットは、「１」によって指定されたバケット有効テーブルにおいて示され、非有効バケットは「０」による。ステップ３で、バケット９５及び９６のための論理バケット識別子、即ち、タグ２３及び４９がそれぞれバケットから抽出される。ステップ４で、この２つのタグ並びにそれらの各バケット９５及び９６は、それらの各タグ２３、４９をインデックスとして使用して、キャッシュに挿入される。
【０１０８】
Ｅ．スタックレベルビュー及び実装
[070]本発明のもう１つのより具体的な実施例が、ここで図９〜１６を参照して説明される。
【０１０９】
[071]図９は、物理フラッシュメモリデバイス２１１によって望まれるものとは大変異なるビューである、インデックス付けアルゴリズム２０３によって望まれたＩＯ使用プロファイルビューを、フラッシュアダプテーション層２０７が適合させる、本発明の一実装を例示するための６層のビュー又はスタック２００を示す。最高レベル２０１で、レコードのディクショナリ（インデックス）が提供され、それに対して、あるインデックス付けオペレーション２０４（レコードをルックアップ、削除、挿入且つ修正する）が必要とされる。インデックス付けアルゴリズム層２０３は、１つ又は複数のインデックス付けアルゴリズムによりディクショナリを実装し、例えば、カッコウ置き換えハッシングアルゴリズムが一例である。インデックス付けアルゴリズムは、インデックスへのキーがどのようにインデックス永続層２０５によって格納されるかのビューを有する。インデックス付けビューは、論理ビューであり、論理アドレス位置を特定する。このビューは更に、サイズ、アラインメント及びタイミングについて、インデックスへのユニフォームアクセスが存在するようになること、及び、インデックスが可変（安定）ストレージ上に格納されることを仮定する。
【０１１０】
[072]インデックス永続層２０５は、インデックスのレコードを格納する物理バケットを読み出し、それらの物理バケットに書き込むための論理バケットオペレーション２０６を提示するようになる。これらの論理バケットオペレーション２０６は、フラッシュアダプテーション層２０７に提示され、フラッシュアダプテーション層２０７は、前述のように、（インデックス付け処理の）論理バケットをフラッシュストレージデバイス上の物理バケット位置に変換する。フラッシュアダプテーション層は、よって、上記のインデックス付けアルゴリズムによって望まれたビュー及びＩＯ使用プロファイルを、下記の物理ストレージデバイス（フラッシュメモリ２１１）によって望まれた大変異なるビューに適合させる。ここで、物理バケットオペレーション２０８は、ランダム読出し及び集約（ブロック順次）書込みを含み、これらのランダム読出し及び集約（ブロック順次）書込みは、バケットアクセスのノンユニフォームモデルを構成する。この実施例の物理バケットオペレーションは、トリムコマンドを更に含んでもよい。
【０１１１】
[073]物理バケットオペレーションは、物理フラッシュデバイス上の資源を追跡且つ調節する、デバイス管理層２０９によって実装される。これらの物理デバイスオペレーション２１０はここでは、ランダム読出し、大きい順次書込み及びトリムコマンドを含む。
【０１１２】
[074]物理デバイス層２１１は、そのノンユニフォーム読出し及び書込み、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられる。そのような物理デバイスの例は、生のフラッシュ、相変化、ＳＳＤ、及びデバイス上に存在するフラッシュファイルシステムを有するフラッシュのうちの１以上を含む。
【０１１３】
[075]本発明は、以下のもの等、デバイス管理層より下の追加の任意選択の強化を可能とする。
【０１１４】
・バケットトリミング（細かいページトリミング）及びページ内のバケット追跡のモデルは、ＳＳＤ又は同等のストレージデバイスのフラッシュファイルシステムに直接組み込まれる場合、よりよい消去ブロック管理を可能とする。
【０１１５】
・フラッシュページ上へのバケットのマッピングは、抽象化である。変化ごとにフラッシュに書き込まれたデータの量を最小化することによって、それらのデバイスの寿命を延ばすために、バケットは、ＳＬＣ  ＮＡＮＤのための部分ページへマップすることができる。バケットはまた、これがシステム全体の性能にとって有益であった場合、複数のフラッシュページ上にマップすることもできる。
【０１１６】
[076]図１０は、インデックスレコードの一例を示す。レコード１４０は、フィンガープリント（キー）を格納するための最初の２０バイトのフィールド１４１を含め、合計で３２バイトである。フィンガープリントは、好ましくはデータコンテンツの暗号ハッシュダイジェスト、例えば、ＳＨＡ−１ハッシュアルゴリズムである。例示を容易にするため、フィンガープリントを、「ＡＢ９２３４５Ｅ２０３．．．」等、１６進数で入力するのではなく、個々のフィンガープリントは、図１１〜１４において、Ｐ、Ｑ、Ｒ、Ｓ、Ｔ等、単一の大文字によって指定される。やはり例示のために簡潔にするため、これらの大文字はまた、レコード全体の代理としての役割も果たすようになる。レコードのフィールドはまた、２バイトの参照カウントフィールド１４２、５バイトの物理ブロックアドレスフィールド１４３、１バイトのフラグフィールド１４４、及び、４バイトの雑フィールド１４５をも含む。ＰＢＡフィールド１４３は、指定されたフィンガープリント１４１のために、ディスク上で格納されたデータの物理ブロックアドレスへのポインタを含む。参照カウントは、ディスク上で格納されたデータへの参照の数を追跡する。
【０１１７】
[077]本発明の一実施形態によれば、インデックスレコードからのフィンガープリント１４１は、前述（図１）のルックアップ関数ｆ（キー）への入力キーとして使用され、この実施例では、関数ｆ（キー）は、４つのハッシュ関数Ｈ０、Ｈ１、Ｈ２及びＨ３のセットを備える。一般に、２つ以上のハッシュ関数の任意のセットを使用することができる。ハッシュ関数Ｈｘは、フィンガープリントを、０及びＮ−１を含めて範囲[０，Ｎ−１]へマップし、但し、Ｎはハッシュテーブルのサイズである。この実施例では、フィンガープリント自体がハッシュであることを考えれば、ＢｉｔＦｉｅｌｄを抽出して、以下の４つのハッシュ値のファミリを生成することができる。
【０１１８】
Ｈ０（ｘ）＝ｘ＜０：３１＞ｍｏｄ  Ｎ
Ｈ１（ｘ）＝ｘ＜０３２：６３＞ｍｏｄ  Ｎ
Ｈ２（ｘ）＝ｘ＜０６４：９５＞ｍｏｄ  Ｎ
Ｈ３（ｘ）＝ｘ＜０９６：１２７＞ｍｏｄ  Ｎ
[078]抽出されたＢｉｔＦｉｅｌｄ幅は、ｌｏｇ２（Ｎ）以上である。ばらばらのビットの任意の組み合わせを使用することができ、ｌｏｇ２（Ｎ）制約を受ける。図１０に例示されるように、最初のフィールド１４１内のフィンガープリントのみがハッシュされて、キーが形成される。レコード１４０の残りのコンテンツ（フィールド１４２〜１４５）は、値又はペイロードを備える。
【０１１９】
[079]図１１は、カッコウハッシングとして知られる、置き換えハッシングインデックス付けアルゴリズムの一例を例示する。例示を容易にするため、２つの関数のみが使用される。図１１Ａは、フィンガープリントＰがそれぞれ関数Ｈ０（ｘ）及びＨ１（ｘ）からハッシュ値２及び５を生成する一方、フィンガープリントＱがこれらの同じ関数からハッシュ値１及び３を生成する、２×３グリッドを示す。カッコウハッシングアルゴリズムは、０〜６のラベルが付けられた７個のスロット（図１１Ｂ）のうち１つにＰ及びＱを入れるための、２つの代替ハッシュ値の中から選択するようになる。Ｐは、２つの位置のうち１つ、２又は５に入る可能性があり、Ｑは、２つの位置のうち１つ、１又は３に入る可能性がある。図１１Ｃに示すように、このアルゴリズムは、Ｑを最下位の空スロット１に、Ｐをスロット２に入れる。この実施例では、レコードコンテナは、１つのレコードを保持するスロットとして見なされるが、本発明はそのように限定されず、インデックス付けアルゴリズムはまた、複数のレコードを保持するバケットをもコンテナと見なすことを理解されたい。ここでは、説明を簡素化するため、単一のレコードスロットが使用される。
【０１２０】
[080]このとき、もう１つのフィンガープリントＲが提供され、Ｒは、同じハッシュ関数から１及び２のハッシュ値を生成する（図１１Ｄのテーブルを参照）。ハッシングアルゴリズムは、Ｒを左の位置、即ちスロット１に入れ、現在のエントリＱを変位させるようになる（図１１Ｅ）。Ｑはこのとき、Ｈ１（Ｑ）によって指定された他の任意選択の位置、即ち位置３に移動されるようになる。このアルゴリズムは、各レコードが空のスロットに入るまで、レコードを変位させ続けるようになる。
【０１２１】
[081]この実施例では、「Ｒを挿入する」オペレーションを達成するため、インデックス付けアルゴリズムは、以下の読出し及び書込み要求を生成する。
【０１２２】
１を読み出す（Ｑを得る）
２を読み出す（Ｐを得る）
１を書き込む（Ｒを書き込む）
３を読み出す（妥当性チェック）
３を書き込む（Ｑ）
[082]最初の２つの読出しは、Ｒがインデックス内にすでに存在しているのではないことを検証するために使用される。妥当性チェック（３を読み出す）は、スロット番号３が空であるかどうかを決定し、そうである場合、Ｑがスロット３に書込み可能となり、どのエントリもスロット３に再書込みされなかったとき、このアルゴリズムは終了される。スロット３が空でなかった場合、スロット３内の現在のエントリが別のスロットに移動されることが必要となる。我々がビットマップを有する場合、スロット３のコンテンツは既知であり、そうでない場合、我々は、そのステータスを決定するために、スロット３内のエントリを読み出す必要がある。各エントリは、そのエントリが有効であるかどうかを示す有効ビットを含む。有効とは、それが使用中である（且つ、その位置を現在占有しているものが変位されなければならない）ことを意味する。有効ではないとは、その位置が空であることを意味し、処理中のレコードがそこに書込み可能である。有効ビットのコンテンツもまた、あるメモリを犠牲にして、別のビットマップに格納されうる。
【０１２３】
[083]カッコウハッシングアルゴリズムは、空のエントリに着地するまで、複数のエントリに渡って書き込み、以前のコンテンツを変位させ続けるという点において、再帰的である。実際には、この処理はめったに１回の変位を越えることはない。
【０１２４】
[084]インデックス付けアルゴリズムは、バケット及び個々のレコードオペレーションを共に有する。インデックス付けアルゴリズムは、１つのレコードを１つのコンテナ（スロット）に入れることとして（図１１で）上述されるが、インデックス付けアルゴリズムによって、レコードがバケット、即ち、複数のレコードを含むバケットに集約されてもよいことは理解される。よって、上記の実施例は非限定的であり、概してレコードオペレーションを例示するものである。
【０１２５】
[085]前述のように、個々のレコードの読出し及び書込みは、フラッシュメモリにとって効率的ではないので、個々のレコードはバケットに集約される。図１２は、各々が２つ以上のレコードを含む、４つのそのようなバケットを例示し、即ち、レコード位置０及び１を有するバケットＢ０、レコード位置２及び３を有するＢ１、レコード位置４及び５を有するＢ２、並びに、レコード位置６及びｘを有するＢ３である。バケットサイズはフラッシュデバイス、即ち、完全ページ書込みか又は部分ページ書込みかによって決定された最小書込みサイズの関数である（且つ、好ましくはそれに等しい）。典型的なバケットサイズは、４ＫＢであってもよい。レコードの具体的な順序付けは、バケット内で必要とされない−−ルックアップオペレーション中にバケット全体が有効レコードについて検索されるので、レコードはバケット内のいかなる点でも挿入可能である。カッコウハッシングアルゴリズムによる置き換え時、バケット内のエントリはランダムに置き換えされうる。インデックス付けアルゴリズムは、よって、論理バケットを、ランダムな位置のように見えるものに、１つずつ書き込み、最終的にフラッシュアダプテーション層によって、フラッシュデバイスへのより大きい、物理的に隣接又は連続する（順次）書込みに集約される。
【０１２６】
[086]図１３は、バケットエントリ１６０の一例を例示する。４ＫＢのバケットサイズは、下にあるデバイスの最小書込みサイズ、ここでは４ＫＢのページに基づく。４ＫＢのバケットは、バケットエントリ内のレコードの数を指定する、４バイトの最初のフィールド１６１を含む。４バイトのタグフィールド１６２は、論理バケット識別子を指定する。この識別子（タグ）は論理アドレスであり、物理的なものではない。変換テーブルは、アルゴリズムバケットアドレス（ＡＢＡ）をフラッシュバケットアドレスＦＢＡにマップする。キャッシュは、（ＣＰＵの用語で）仮想キャッシュとして動作し、各キャッシュライン（エントリ）は、タグ、この場合はＡＢＡによって識別される。アルゴリズムがレコードを要求するとき、キャッシュを通過中にそれが知ることは、要求されたＡＢＡがキャッシュされることのみであり、ＡＢＡがマップされるところ（ＦＢＡ）は、キャッシュの下端（例えば、図２Ｃにおける、ＢＴＴへの逆ポインタ３１３を参照）である。バケットは、複数のレコードＲ０、Ｒ１、Ｒ２．．．を保持するためのフィールド１６３を含み、各レコードは、３２バイトのサイズである。この例では、４ＫＢのバケットは、１バケットにつき（４０９６−４−４）／３２個のレコード、即ち、約１２７個のレコードを保持するようになる。
【０１２７】
[087]図１４は、一実施形態における、バケット、ページ及び消去ブロックの相対サイズを例示する、フラッシュメモリデバイス１６４の概略図である。物理フラッシュデバイスは、２ＧＢのサイズであるチップ（パッケージ）１６５である。チップ上に、２つのダイ（シリコンウエハ）１６６ａ、１６７ｂがある。各ダイ上に、２＾１４個の消去ブロックがあってもよく、各消去ブロック１６７は典型的には６４ＫＢである。ページ１６８は、書込み可能である最小サイズ、ここでは４ＫＢであり、スタック（図９を参照）内のより上位で使用されるような、同じく４ＫＢである、バケット１６９のサイズを決定する。
【０１２８】
[088]図１５は、物理フラッシュデバイス上の資源を追跡且つ調節するためのデバイス管理層（図９の２０９）の一実施形態による、選ばれたコンポーネントを例示する。図１５Ａは、（上部に）複数のページ（バケット）１７０と、その後に続く、どのページが有効であるか（１は有効、０は有効でない）を示す、ページアロケーションマップ１７１を示す。この下は、将来トリムされることになるが、まだそうされていないページの、保留中トリムマップ１７２である。ページアロケーション及び保留中トリムマップは、前述のような本発明の様々な実施形態では、バケットが有効データを保持するかどうかを決定する（図１に例示されたバケット有効テーブル２７を参照）するために使用されうる。
【０１２９】
[089]図１５Ｂは、消去ブロックインデックスによってインデックス付けされた、消去ブロック記述子テーブル１７５の一例を例示する。各消去ブロック記述子エントリ１７６は、消去済みの数１７７、部分書込みの数１７８、部分読出しの数１７９、完全読出しの数１８０、完全書込みの数１８１、及び、誤りの数１８２を含む、複数のフィールドを含む。この情報は、本発明の様々な実施形態において前述されたように、フリー消去ブロックの生成において使用されうる。
【０１３０】
Ｆ．更なる実施形態
[090]本発明は、本願と同日に出願され、２００９年６月２６日出願の米国仮特許出願第６１/２６９，６３３号に対する優先権を主張する、Ａ．Ｊ．Ｂｅａｖｅｒｓｏｎ及びＰ．Ｂｏｗｄｅｎによる、同時係属の、所有者が同じであるＦｉｌｅ  Ｓｙｓｔｅｍ（ファイルシステム）という名称の米国特許出願第＿＿＿＿＿＿＿＿＿＿号に記載された、ファイルシステムのインデックスを実装するために使用されうる。両出願に対する優先権が本明細書で主張され、各々の完全な開示はそれらの全体として参照により本明細書に組み込まれる。
【０１３１】
[091]本発明の実施形態は、デジタル電子回路において、或いは、コンピュータハードウェア、ファームウェア、ソフトウェアにおいて、或いは、それらの組み合わせにおいて実装されうる。本発明の実施形態は、コンピュータプログラム製品として、即ち、情報キャリア内で、例えば、マシン可読ストレージデバイス内で、データ処理装置、例えば、プログラマブルプロセッサ、コンピュータ又は複数のコンピュータによる実行のため、或いはそれらのオペレーションを制御するために、有形に実施されたコンピュータプログラムとして実装されうる。コンピュータプログラムは、コンパイラ型又はインタープリタ型言語を含む任意の形式のプログラミング言語で書かれてよく、スタンドアロンのプログラム又はモジュール、コンポーネント、サブルーチン若しくはコンピューティング環境で使用するために適した他のユニットを含む任意の形式で配置されうる。コンピュータプログラムは、１つのコンピュータ又は複数のコンピュータ上で実行されるように配置することができ、これら複数のコンピュータは、１つの場所にあるか又は複数の場所に渡って分散され通信ネットワークによって相互接続される。
【０１３２】
[092]本発明の実施形態の方法ステップは、１つ又は複数のプログラマブルプロセッサがコンピュータプログラムを実行して、入力データに関して動作し、出力を生成することにより、本発明の機能を行うことによって、行われうる。方法ステップはまた、専用論理回路、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）によって行われてもよく、本発明の装置は、専用論理回路、例えば、ＦＰＧＡ又はＡＳＩＣとして実装されうる。
【０１３３】
[093]コンピュータプログラムの実行に適したプロセッサは、例として、汎用及び専用マイクロプロセッサ、及び、任意の種類のデジタルコンピュータの任意の１つ又は複数のプロセッサを含む。一般に、プロセッサは、命令及びデータを、読出し専用メモリ若しくはランダムアクセスメモリ又は両方から受信するようになる。コンピュータの必須要素は、命令を実行するためのプロセッサ、並びに、命令及びデータを格納するための１つ又は複数のメモリデバイスである。一般に、コンピュータはまた、データを格納するための１つ又は複数の大容量ストレージデバイス、例えば、磁気、光磁気ディスク若しくは光ディスクをも含むか、或いは、それらからデータを受信し、若しくはそれらへデータを転送するように動作可能に結合されるか、或いはその両方となる。コンピュータプログラム命令及びデータを実施するために適した情報キャリアは、例として、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリデバイス等、半導体メモリデバイスと、例えば、内蔵ハードディスク又はリムーバブルディスク等、磁気ディスクと、光磁気ディスクと、ＣＤ  ＲＯＭ及びＤＶＤ−ＲＯＭディスクとを含む、全ての形式の不揮発性メモリを含む。プロセッサ及びメモリは、専用論理回路によって補われるか又は専用論理回路に組み込まれうる。
【０１３４】
[094]前述の記載は、本発明の範囲を例示するためのものであり、限定するように意図されないことを理解されたい。