(57)【要約】  不均等アクセス・メモリにレコードを格納する方法および装置。種々の実施形態において、メモリの１つ以上の領域に、レコードの配置を局所化させる。これは、ハッシュ関数の異なる整列リストを利用して行い、メモリの異なる領域に優先的にレコードをマッピングして、１つ以上の性能特性を達成するまたは基礎的なメモリ技術の相違を考慮することができる。例えば、ハッシュ関数の整列リストの１つは、アクセスの迅速化のためにデータを局所化することができる。ハッシュ関数の他のリストは、比較的短い寿命を有することが予想されるデータを局所化することができる。このようなデータを局所化することによって、例えば、古いデータ・エレメントを１つの位置に集中させることによって、消去性能を改善するおよび／またはメモリ寿命を延長することができる。つまり、整列ハッシュ関数の２つ以上のリストが、アクセス・レイテンシ、メモリ寿命、および／または動作速度の内１つ以上を改良することができる。
2015515047.tif 000002
【特許請求の範囲】
【請求項１】
不均等アクセス・メモリにおいてインデックス・レコードを格納する方法であって、各レコードがレコード・キーを含み、複数のハッシュ関数が、前記不均等アクセス・メモリにおける物理位置への変換のために、レコードを論理バケットにマッピングするために使用され、前記方法が、
第１レコード・タイプを前記メモリの第１領域に優先的にマッピングするために、ハッシュ関数の第１整列リストを、前記第１レコード・タイプのレコード・キーに適用するステップと、
第２レコード・タイプを、前記第１領域に限定されない前記メモリの第２領域に優先的にマッピングするために、ハッシュ関数の第２整列リストを、前記第２レコード・タイプのレコード・キーに適用するステップと、
を含む、方法。
【請求項２】
請求項１記載の方法であって、
論理バケット識別子を前記メモリの物理バケット位置にマッピングするためにバケット変換テーブルを維持するステップであって、前記論理バケット識別子が、適用する前記ステップによって生成され、前記テーブルが、論理バケット識別子の、関連する前記レコードが前記メモリにおいて格納される物理バケット位置へのマッピングを含む、ステップを含む方法。
【請求項３】
請求項１記載の方法において、
前記第１レコード・タイプが、前記第２レコード・タイプよりも、前記メモリにおいて、大きな予想アクセス要求を有する、方法。
【請求項４】
請求項１記載の方法において、
前記第１レコード・タイプが、前記第２レコード・タイプよりも、前記メモリにおいて短い予想寿命を有する、方法。
【請求項５】
請求項１記載の方法において、前記第１レコード・タイプが、前記第２レコード・タイプよりも、大きな予想参照要求を有する、方法。
【請求項６】
請求項１記載の方法において、
メモリの前記第１領域が、前記メモリの前記第２領域よりも高速なアクセス特性を有する、方法。
【請求項７】
請求項１記載の方法において、
メモリの前記第１領域が、前記メモリの前記第２領域よりも長い予想メモリ寿命を有する、方法。
【請求項８】
請求項１記載の方法において、前記不均等アクセス・メモリが、
読み取りアクセス時間、書き込みアクセス時間、１回書き込み制限、データ位置またはアドレス特定アクセス回数、複数ステップ書き込みまたは読み出しプロセス、および、全く異なるアクセス特性を呈する異なるアドレスへのアクセスにおいて生ずる他の制約のうちの１つ以上を含む異なる特性を有する複数のコンピュータ記憶媒体を含む、方法。
【請求項９】
請求項１記載の方法において、
前記メモリが、フラッシュ・デバイス、相変化デバイス、ソリッド・ステート・デバイス、ＤＲＡＭ、およびハード・ディスク・メモリ・デバイスの内１つ以上を含む、方法。
【請求項１０】
請求項１記載の方法において、
前記メモリが、複数の消去ブロックを含むフラッシュ・メモリ・デバイスを含み、各消去ブロックが、複数のページを含み、各ページが複数のバケットを含む、方法。
【請求項１１】
請求項１０記載の方法であって、
空きの消去ブロックを生成するためにスカベンジ・プロセスを実行するステップを含む、方法。
【請求項１２】
請求項１記載のシステムにおいて、
前記メモリが、不均等読み出しおよび書き込みアクセスによって特徴付けられる物理デバイス層を含む、システム。
【請求項１３】
請求項１記載の方法であって、更に、
前記第１領域を消去するステップであって、前記第１領域における有効レコードをメモリにおける他の位置に書き換え、前記第１領域において１つ以上のブロックを消去するステップを含むステップを含む方法。
【請求項１４】
請求項１記載の方法であって、
ハッシュ関数の前記第１整列グループにおけるハッシュ関数の数またはタイプ、
ハッシュ関数の前記第２整列グループにおけるハッシュ関数の数またはタイプ、および
前記メモリの前記第１領域および前記第２領域のうちの一方または双方の性能特性
のうちの１つ以上を変更するステップを含む方法。
【請求項１５】
請求項１記載の方法であって、更に、
前記レコードを格納する物理バケット位置に対する読み出しおよび書き込みのために、論理バケット動作を実行するステップを含む方法。
【請求項１６】
プログラム・コードを含むコンピュータ・プログラム製品であって、前記プログラム・コードがプロセッサによって実行されると、請求項１記載の方法のステップを実行する、コンピュータ・プログラム製品。
【請求項１７】
１つ以上のプロセッサと、請求項１記載の方法を実行するために、前記１つ以上のプロセッサによる実行のための１つ以上のプログラムを格納するメモリとを含むコンピュータ・システム。
【請求項１８】
コンピュータ・システムであって、
不均等アクセス・メモリであって、前記メモリの物理パケット位置に格納されたインデックス・レコードを含み、各レコードがレコード・キーを含む、不均等アクセス・メモリと、
論理バケット識別子を生成するためにレコード・キーをハッシュするハッシュ値生成器と、
前記論理バケット識別子を、前記レコード・キーに関連するレコードが格納された前記メモリの物理バケット位置にマッピングする変換コンポーネントと
を含み、前記ハッシュ値生成器が、
第１レコード・タイプを優先的に前記メモリの第１領域にマッピングするために、ハッシュ関数の第１整列リストを、前記第１レコード・タイプのレコード・キーに適用し、
第２レコード・タイプを優先的に、前記第１領域に限定されない前記メモリの第２領域にマッピングするために、ハッシュ関数の第２整列リストを、前記第２レコード・タイプのレコード・キーに適用する、コンピュータ・システム。
【請求項１９】
フラッシュ・メモリにインデックス・レコードを格納する方法であって、各レコードがレコード・キーを含み、複数のハッシュ関数が、前記フラッシュ・メモリにおける物理位置への変換のために、レコードを論理バケットにマッピングするために使用され、前記方法が、
第２レコード・タイプよりも短い予想寿命を有する第１レコード・タイプのレコードを識別するステップと、
前記第１レコード・タイプを優先的に前記フラッシュ・メモリの局所領域にマッピングし、前記第１領域の消去ブロック・スカベンジ中の書き込み時間を短縮するために、ハッシュ関数の第１整列リストを、前記第１レコード・タイプのレコード・キーに適用するステップと、
を含む、方法。
【請求項２０】
請求項１９記載の方法であって、更に、
前記第１領域において空き消去ブロックを生成するためにスカベンジ・プロセスを実行するステップを含む方法。
【請求項２１】
請求項１９記載の方法であって、更に、
前記第２レコード・タイプを優先的に、前記第１領域に限定されない、メモリの第２領域にマッピングするために、ハッシュ関数の第２整列リストを、前記第２レコード・タイプのレコード・キーに適用するステップを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]  本発明は、コンピュータ・データ辞書に関し、更には不均等（non-uniform）アクセス・メモリにおけるレコード配置のための方法および装置に関する。
【従来技術】
【０００２】
[0002]  インデックスは、データ辞書または連想アレイ(associative array)としても知られ、キーとして知られる識別値を、衛星データとして知られる関連値にマッピングするために使用されるデータ構造および関連するアルゴリズムである。キーおよびその衛星データの連係は、レコード・データ入力の一実施形態を構成する。
【０００３】
[0003]  一例では、インデックスがバケット(bucket)に分解され、各バケットはＮ個、例えば、３０個までのレコード・データ入力に対して十分な余裕がある。バケットは、例えば、５１２バイトのサイズ・フィールドを有し、そのバケットにレコードがいくつ収容できるかを示す。レコード・データ・エントリは、バケット内にソートされた順序で、時間順で（これらが到達した順序）格納することができ、あるいはレコード・データ・エントリを任意の順序で格納するために、間接テーブルが使用されることもある。レコード・データ・エントリをバケットに割り当てるために、種々のアルゴリズムが使用されており、通例、全てのバケットにわたってレコード・データ・エントリを均一に分散させることを目標とする。例の中には、最初のバケットが満杯になった場合にオーバーフローを扱うために、複数のレベルのバケットが用意される場合もある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
[0004]  多くのアプリケーションは、非常に大きな数のエントリがあるインデックスを必要とし、つまり関連するデータ構造を格納するためにはギガバイト単位のメモリと、非常に高い動作速度、例えば、毎秒１０万回単位の動作とを必要とする。ＤＲＡＭのように、メモリ技術の中には、必要な性能を提供できるものもあるが、このような多数のレコードを経済的に格納できる程十分に密度が濃くない。ディスク技術のような他のメモリ技術では、密度はあるが要求される性能を欠く場合がある。つまり、大多数のレコードを生成および維持するための記憶サイズおよび動作速度要件の双方を満たすことができるメモリ技術が求められ続けている。
【課題を解決するための手段】
【０００５】
[0005]  本発明によれば、不均等アクセス・メモリにレコード・データ・エントリ（例えば、インデックスのための）を配置するための新たな方法および装置を提供する。種々の実施形態において、レコード・データ・エントリ（レコード）の配置は、メモリの１つ以上の領域に局在化され(localize)、異なる領域が異なるタイプのメモリを含むこともできる。これは、ハッシュ機能の異なる整列リスト(ordered list)を利用し、レコードをメモリの異なる領域に優先的にマッピングして、１つ以上の性能特性を達成する、または基礎であるメモリ技術における相違を考慮することによって遂行することができる。例えば、ハッシュ機能の１つの整列リストは、一層のアクセス迅速化のためにレコードを局在化するのでもよい。ハッシュ機能の他の整列リストは、比較的短い寿命を有することが予想されるレコードを局在化するのでもよい。このようなレコードを局在化すると、例えば、古くなったレコードを１つの位置に集中させることによって、性能および／またはメモリの寿命を著しく改良することができる。つまり、整列ハッシュ機能の２つ（以上）のリストが、アクセス・レイテンシ、メモリ寿命、および／または動作速度の内１つ以上を改良することができる。
【０００６】
[0006]  本発明の一実施形態によれば、不均等アクセス・メモリにおいてインデックス・レコードを格納する方法を提供する。各レコードがレコード・キーを含み、不均等アクセス・メモリにおける物理位置への変換のために、複数のハッシュ関数が、レコードを論理バケットにマッピングするために使用される。この方法は、
第１タイプのレコードをメモリの第１領域に優先的にマッピングするために、 ハッシュ関数の第１整列リストを、第１タイプのレコードのレコード・キーに適用するステップと、
第２タイプのレコードを、第１領域に限定されないメモリの第２領域に優先的にマッピングするために、ハッシュ関数の第２整列リストを、第２タイプのレコード・キーに適用するステップとを含む。
【０００７】
[0007]  一実施形態によれば、論理バケット識別子をメモリの物理バケット位置にマッピングするためにバケット変換テーブルが維持され、論理バケット識別子が、適用するステップによって生成され、前述のテーブルが、論理バケット識別子の、関連するレコードがメモリにおいて格納される物理バケット位置へのマッピングを含む。
【０００８】
[0008]  一実施形態によれば、第１レコード・タイプは、第２レコード・タイプよりも、メモリにおいて、大きな予想アクセス要求回数を有する。
【０００９】
[0009]  一実施形態によれば、第１レコード・タイプは、第２レコード・タイプよりも、メモリにおいて短い予想寿命を有する。
【００１０】
[0010]  一実施形態によれば、第１レコード・タイプは、第２レコード・タイプよりも、大きな予想参照要求回数を有する。
【００１１】
[0011]  一実施形態によれば、メモリの第１領域は、メモリの第２領域よりも高速なアクセス特性を有する。
【００１２】
[0012]  一実施形態によれば、メモリの第１領域は、メモリの第２領域よりも長い予想メモリ寿命を有する。
【００１３】
[0013]  一実施形態によれば、不均等アクセス・メモリは、読み取りアクセス時間、書き込みアクセス時間、１回書き込み制限、データ位置またはアドレス特定アクセス回数（times）、複数ステップ書き込みまたは読み出しプロセス、および／または全く異なるアクセス特性を呈する異なるアドレスへのアクセスが生ずる結果となる他の制約を含む異なる特性を有するコンピュータ記憶媒体を含む。
【００１４】
[0014]  一実施形態によれば、メモリは、フラッシュ・デバイス、相変化デバイス、ソリッド・ステート・デバイス、ＤＲＡＭ、およびハード・ディスク・メモリ・デバイスの内１つ以上を含む。
【００１５】
[0015]  一実施形態によれば、メモリは、複数の消去ブロックを含むフラッシュ・メモリ・デバイスを含み、各消去ブロックは、複数のページを含み、各ページが複数のバケットを含む。
【００１６】
[0016]  一実施形態によれば、この方法は、空きの消去ブロックを生成するためにスカベンジ・プロセスを実行するステップを含む。
【００１７】
[0017]  一実施形態によれば、メモリは、不均等読み出しおよび書き込みアクセスによって特徴付けられる物理デバイス層を含む。
【００１８】
[0018]  一実施形態によれば、メモリは、第１領域を消去するステップであって、第１領域における有効レコードをメモリにおける他の位置に書き換え、第１領域において１つ以上のブロックを消去することを含む、ステップを含む。
【００１９】
[0019]  一実施形態によれば、この方法は、
ハッシュ関数の第１整列グループにおけるハッシュ関数の数またはタイプ、
ハッシュ関数の第２整列グループにおけるハッシュ関数の数またはタイプ、および
メモリの第１および／または第２領域の性能特性、
の内１つ以上を変更するステップを含む。
【００２０】
[0020]  一実施形態によれば、この方法は、レコードを格納する物理バケット位置に対する読み出しおよび書き込みのために、論理バケット動作を実行するステップを含む。
【００２１】
[0021]  一実施形態によれば、プログラム・コードを含むコンピュータ・プログラム製品を提供する。プログラム・コードがプロセッサによって実行されると、請求項１記載の方法のステップを実行する。      
【００２２】
[0022]  本発明の一実施形態によれば、１つ以上のプロセッサと、前述の方法ステップを実行するために、１つ以上のプロセッサによる実行のために１つ以上のプログラムを格納するメモリとを含むコンピュータ・システムを提供する。
【００２３】
[0023]  本発明の他の実施形態によれば、コンピュータ・システムを提供する。このコンピュータ・システムは、
不均等アクセス・メモリであって、当該メモリの物理パケット位置に格納されたインデックス・レコードを含み、各レコードがレコード・キーを含む、不均等アクセス・メモリと、
論理バケット識別子を生成するためにレコード・キーをハッシュするハッシュ値生成器と、
論理バケット識別子を、レコード・キーに関連するレコードが格納されたメモリの物理バケット位置にマッピングする変換コンポーネントと、
を含み、
ハッシュ値生成器は、
第１レコード・タイプを優先的にメモリの第１領域にマッピングするために、ハッシュ関数の第１整列リストを、第１レコード・タイプのレコード・キーに適用し、
第２レコード・タイプを優先的に、第１領域に限定されないメモリの第２領域にマッピングするために、ハッシュ関数の第２整列リストを、第２タイプのレコード・キーに適用する。
【図面の簡単な説明】
【００２４】
[0024]  本発明は、レコードをメモリの選択領域に優先的にマッピングするために、ハッシュ機能の２つ以上の整列リストを含むことは理解されよう。
【図１】図１は、本発明の一実施形態の模式上位システム・アーキテクチャであり、ハッシュ機能の整列リストをレコード・キーに適用することによる、インデックス・レコードの不均等アクセス・メモリへの格納を示す。
【図２Ａ】図２Ａは、本発明の一実施形態にしたがってレコードをメモリに挿入するためのプロセスのフローチャートである。
【図２Ｂ】図２Ｂは、本発明の一実施形態にしたがってレコードをメモリに挿入するためのプロセスのフローチャートである。
【図３Ａ】図３Ａは、本発明の他の実施形態にしたがってレコードを参照するためのプロセスのフローチャートである。
【図３Ｂ】図３Ｂは、本発明の他の実施形態にしたがってレコードを参照するためのプロセスのフローチャートである。
【図４】図４は、本発明の他の実施形態にしたがってレコードを削除するためのプロセスのフローチャートである。
【図５】図５は、本発明の一実施形態による種々のインデックス化動作を示す模式ブロック図である。
【図６Ａ】図６Ａから図６Ｄは、本発明において使用することができるデータ構造およびシステム・コンポーネントの種々の実施形態を示し、図６Ａは、バケット変換テーブルを示し、図６Ｂは、バケット有効テーブルを示し、図６Ｃはフラッシュ・メモリにおけるバケットの内容を示し、図６ＤはＮＡＮＤフラッシュ・メモリの編成を示す。
【図６Ｂ】図６Ａから図６Ｄは、本発明において使用することができるデータ構造およびシステム・コンポーネントの種々の実施形態を示し、図６Ａは、バケット変換テーブルを示し、図６Ｂは、バケット有効テーブルを示し、図６Ｃはフラッシュ・メモリにおけるバケットの内容を示し、図６ＤはＮＡＮＤフラッシュ・メモリの編成を示す。
【図６Ｃ】図６Ａから図６Ｄは、本発明において使用することができるデータ構造およびシステム・コンポーネントの種々の実施形態を示し、図６Ａは、バケット変換テーブルを示し、図６Ｂは、バケット有効テーブルを示し、図６Ｃはフラッシュ・メモリにおけるバケットの内容を示し、図６ＤはＮＡＮＤフラッシュ・メモリの編成を示す。
【図６Ｄ】図６Ａから図６Ｄは、本発明において使用することができるデータ構造およびシステム・コンポーネントの種々の実施形態を示し、図６Ａは、バケット変換テーブルを示し、図６Ｂは、バケット有効テーブルを示し、図６Ｃはフラッシュ・メモリにおけるバケットの内容を示し、図６ＤはＮＡＮＤフラッシュ・メモリの編成を示す。
【図７Ａ】図７Ａは、スカベンジ・プロセス(scavenging process)の一実施形態を示す模式ブロック図である。
【図７Ｂ】図７Ｂは、スカベンジ・プロセスの一実施形態を示す模式ブロック図である。
【図８】図８は、本発明の一実施形態において使用されるレコード・エントリの模式図である。
【図９】図９は、本発明の一実施形態による、複数のダイ(dies)、消去ブロック、ページ、およびバケットを有する物理フラッシュ・チップの一例を示す模式ブロック図である。
【図１０】図１０は、データを処理し格納するための一般的なシステム構成の一実施形態を示す。
【発明を実施するための形態】
【００２５】
[0036]  これより、本発明の種々の実施形態について、図面を参照しながら説明する。以下の記載では、本発明の１つ以上の実現例の完全な理解を得るために、多数の具体的な詳細が説明の目的に限って明示される。しかしながら、本発明はこれらの具体的な詳細がなくても実施できることは明らかである。他方では、周知の構造およびデバイスは、本発明を説明し易くするために、ブロック図形態で示される。
【００２６】
[0037]  本願において使用される場合、「コンポーネント」および「システム」という用語は、ハードウェア、ハードウェアおよびソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェアのいずれかのコンピュータ関連エンティティを指すことを意図する。例えば、コンポーネントが、プロセッサにおいて実行するプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行のスレッド、プログラム、および／またはコンピュータであってもよいが、これらに限定されるのではない。例示として、サーバにおいて実行するアプリケーションおよびこのサーバの双方がコンポーネントであることができる。１つ以上のコンポーネントがプロセスおよび／または実行のスレッド内に存在することもでき、更にコンポーネントが１つのコンピュータに局在化される、および／または２つ以上のコンピュータ間で分散されるのでもよい。
【００２７】
[0038]  また、本発明は、発明のプロセスのフローチャートとしても示すことができる。説明を簡素にする目的に限って、フローチャートの形態で示される１つ以上の方法は一連のアクトとして説明されるが、本発明はアクトの順序には限定されないことは言うまでもなく認められよう。何故なら、本発明によれば、一部のアクトは、本明細書において示され説明される順序とは異なる順序で現れてもよく、および／または他のアクトと同時に現れてもよいからである。例えば、ある方法が、代わりに、状態図のような、一連の相関付けられた状態またはイベントとして表われてもよいことは、当業者には理解され認められよう。更に、図示されるアクトの全てが、本発明による方法を実現するために必要ではない場合もある。
【００２８】
[0039]  本明細書において開示される本発明の種々の実施形態において、「データ」および「データ・エレメント」という用語は、相互交換可能に使用される。本明細書において使用される場合、データは、不透明なデータの集合体、例えば、コンピュータに入力され、その中で格納および処理され、または他のコンピュータに送信されることが可能な任意のシンボル・シーケンス（通例、「０」および「１」で表される）を意味する。本明細書において使用される場合、データは、メタデータ、他のデータの記述を含む。記憶システムに書き込まれるデータは、本明細書において記載される場合、同じサイズのデータ・エレメント、または可変サイズのデータ・エレメントであってもよい。データの例には、情報、プログラム・コード、プログラム状態、プログラム・データ、他のデータ等が含まれる。
【００２９】
[0040]  本明細書において使用される場合、「記憶システム」は、ストレージ、例えば、ファイル・システム、ブロック記憶デバイス、または他のシステムにデータを格納するための任意のシステムまたはアプリケーションとすることができる。記憶システムは、ストレージにおける各データ・エレメントを参照するために識別子または名称を使用することができる。一例では、名称は、データ・コンテンツのハッシュ、好ましくは、データ・コンテンツの暗号ハッシュまたは変転防止ハッシュ(collision resistant hash)というような、グローバル一意識別子（ＧＵＩＤ）である。各データ・エレメントが、格納されたデータをユーザに再現することを可能にする名称を記憶システム内部で有するのである限り、 他の命名慣例(naming convention)も可能である。一実施形態では、中央サーバが名称を生成する。データ名称は、通常、人ではなく、プログラムによる使用が意図された固定長の二進ストリングである。全てのデータのインデックス（辞書またはカタログと呼ばれることもある）が、各データ・エレメントにアクセスする（を突き止める）ために、記憶システムによって必要とされることもある。インデックスにおける各レコードは、データ・エレメントの名称、その論理位置および／または物理位置（アドレス）、ならびにそれぞれのデータ・エレメントに関する他の情報を収容することができる。一実施形態では、各インデックス・エントリは、データ・オブジェクトが格納されるディスクにおける物理ブロック・アドレスを指し示すポインタを含む。一実施形態では、データが格納されるディスクにおける物理位置を突き止めるために、固定アルゴリズムが使用されてもよい。
【００３０】
[0041]  本発明の一実施形態によれば、ディスク・ストレージにデータを格納する記憶システムと共に使用するためのデータ配置方法および装置が提供される。記憶システムは、例えば、ファイル・システム、ブロック記憶デバイス、またはデータを格納するための他の記憶システムを含むことができる。このような記憶システムに書き込まれるデータは、通例、多くの小さな（例えば、４ｋＢ）データ片を含む。データ片は、本明細書では、データまたはデータ・エレメントと相互交換可能に呼ばれ、このデータは同じサイズでも、または可変サイズでもよい。
[0042]  本明細書において使用される場合、不均等アクセス・メモリは、異なる特性を有するコンピュータ記憶媒体を意味する。これら異なる特性には、読み出しアクセス時間、書き込みアクセス時間、１回書き込み限定、データ位置またはアドレス特定アクセス時間、複数ステップ書き込みまたは読み出しプロセス、および／または全く異なるアクセス特性を呈する異なるアドレスへのアクセスが生ずる結果となる他の制約が含まれる。不均等アクセス・メモリは、（一例として）異質メモリ、即ち、１つの論理および／または連続メモリと見なされる、異なるコンピュータ記憶媒体の組み合わせを含む。
【００３１】
[0043]  本明細書において使用される場合、コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造、プログラム・モジュール、または他のデータというような情報の格納のための、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＦＬＡＳＨメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル・バーサタイル・ディスク（ＤＶＤ）または他の光ディスク・ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージまたは他の磁気記憶デバイス、あるいは所望の情報を格納するために使用することができコンピュータによってアクセスすることができる任意の他の媒体を含む。
Ａ．不均等ハッシュ機能を利用するレコード配置
[0044]  図１は、不均等アクセス・メモリにレコードを配置するために、不均等な複数（Ｎ個）のハッシュ機能を利用する、本発明の一実施形態によるプロセスの上位模式図である。レコード・キーＫが、この場合３つのハッシュ関数、即ち、Ｈ０、Ｈ１、およびＨ２を使用してハッシュされ、各々、論理バケット識別子が得られる。これらのハッシュ関数の内の１つ、ＨＯは、論理バケット空間１４の全てにおいてバケットの全てをアドレスするのではない。ここでは、Ｈ０はバケット０からｎまでの部分集合をアドレスする。これは、全てのバケット０からｍよりも少ない。つまり、図１は、キー値(x)に対して、
H0(x) = {0 .. n}
H1 (x) = {0 ..m}
H2 (x) = {n+1 .. m}
であり、任意のキー(x)に対して、
H0(x)<> H1 (x) <>H2(x)
であるハッシュ関数を示す。  
【００３２】
[0045]  キーKが３つのハッシュ関数を使用してハッシュされるとき、３つのバケット識別子の候補が生成される。第１バケット識別子は、ハッシュ関数Ｈ０からであり、最初の数個のバケット０．．ｎのみをターゲットにすることができる。他のハッシュ関数Ｈ１は、任意のバケットをターゲットにすることができ、Ｈ２は、Ｈ０によって生成することができるバケット・アドレスの範囲にないバケットをターゲットにすることができる。これは、図１において、ハッシュ関数Ｈ０に対してバケット０からｎまでに及ぶ第１の線３０、ハッシュ関数Ｈ１に対してバケット０からｍまでに及ぶ第２の線３１、およびハッシュ関数Ｈ２に対してバケットn+1からｍまでに及ぶ第３の線３２によって模式的に示される。整列された１組のこのような不均等ハッシュ関数、即ち、全て（部分集合）のバケット未満をカバーするハッシュ関数の少なくとも１つを利用することによって、メモリを効率的に利用しつつ、種々のメモリ技術においてレコード・キーを選択（局在化）メモリ領域に好ましくマッピングする方法が提供される。論理バケット範囲Ｈ０、Ｈ１、およびＨ２は、例えば、異なるアクセス特性を有する特定の基礎メモリ技術にマッピングされてもよい。また、これらは、同じメモリ技術にマッピングされてもよいが、定められた限定メモリ領域に特定のバケットを集中させ、こうして性能および／またはメモリ耐久性を高める。
【００３３】
[0046]  図１の下側に示すように、１つ以上の変換テーブル１６が、論理バケット空間１４を、不均等アクセス・メモリにおける物理位置にマッピングする。一例では、メモリ１８は、ＭＬＣおよびＳＬＣのような、異なるフラッシュ技術を含む。ＳＬＣは、単一レベル（ＳＬＣ）デバイスを含む一種のＮＡＮＤフラッシュ・メモリであり、各セルが１ビットの情報だけを格納する。それよりも新しいＮＡＮＤフラッシュ・メモリ技術に、多レベルセル（ＭＬＣ）デバイスを利用するものがあり、これはセル当たり１つよりも多いビットを格納することができる。異なるフラッシュ技術は異なる性能特性を有する。
【００３４】
[0047]  第２の例では、均一技術メモリ２０を使用しつつ、Ｈ０によってアドレスされるバケットの部分集合というような、ある種のデータをメモリ２０の一領域に集中させることができる。これも、性能のためまたは他の理由（例えば、寿命）のためである。
【００３５】
[0048]  更に他の例として、メモリ技術２２は、複数のフラッシュ・チップを含むのでもよく、Ｈ０によってカバーされる論理バケットの部分集合が、このフラッシュ・チップにわたって縞状にされた領域(striped region)にデータを局在化するのでもよい。縞のサイズは、消去性能を高めるために、消去ブロック・サイズの倍数とするとよい。この縞は、複数のフラッシュ・チップにわたって上下に動かすことができる。
【００３６】
[0049]  これらは、異なる不均等メモリ技術および不均等ハッシュ関数を利用してデータ・レコードをこのようなメモリの選択領域に配置する異なる方法の内３つの例に過ぎない。
Ｂ．記録動作
[0050]  図２から図４は、本発明の一実施形態にしたがって、それぞれ、レコードを挿入、参照、および消去するための３種類のレコード動作を示す。
【００３７】
[0051]  図２は、レコードを挿入する方法４０の一実施形態を示す。ステップ４１において開始し、レコードを供給する。この例では、レコードはレコード・キーおよび関連データを含む。既に説明したように、このようなレコードの一種にインデックス・レコードがあり、この場合キーは位置にマッピングされる。他の例では、キーはアクセス許可にマッピングされる。他の例では、キーは、データが最後に変更されたときを表す値にマッピングされる。他の例では、キーはデータの特性にマッピングされる。データ自体は、記憶デバイス（図示せず）に格納され、レコード・キーを生成するためにこのデータをハッシュすることができる。関連データは、データが格納された記憶システムにおける物理ブロック・アドレスに対するポインタであってもよい。これは、単なる一例に過ぎず、当業者であれば、複数の他の例がこのようなレコードにはあることを理解するであろう。
【００３８】
[0052]  次のステップ４２において、レコード・タイプに基づいて選択を行う。この例では、レコードが短命で頻繁にアクセスされることが予想されるか、または代わりに長命であり(例えば、永続的)であり頻繁にアクセスされないことが予想されるかに基づく選択である。レコードが第１のタイプであると仮定すると、本方法は図２の左側にある列のステップ４３に進み、ハッシュ関数{H0,H1,H2}の整列リストがレコードに割り当てられる。整列されたハッシュ関数のリスト全体を順次進むプロセス４４に続いて、ステップ４５において第１ハッシュ関数Ｈ０がキーに適用され、論理バケット番号０．．ｎを生成する（４６）。次に、ステップ４７において、論理バケット番号（論理バケット識別子の一形態を含む）を、不均等アクセス・メモリにおける物理バケット位置に変換する。次に、ステップ４８において、物理バケット位置のコンテンツを読み出して、この物理バケット位置にレコードのために利用可能なスロットがあるか否か判定を行う（ステップ４９）。ある場合、本プロセスはステップ５０に進み、このレコードを不均等アクセス・メモリにおけるこの物理バケット位置に追加する。次に、ステップ５１において、バケットを書き換え、論理／物理バケットテーブル（以下で説明する）を、この変更で更新し、本プロセスは終了する。ステップ４９に戻り、物理バケット位置に利用可能なスロットがない場合、本プロセスはステップ４４に戻り、ハッシュ関数Ｈ２の整列リストの次の（第１とは異なる）ハッシュ関数をキーに適用する。この第２ハッシュ関数Ｈ２は、レコードを不均等アクセス・メモリの第１領域に優先的にマッピングするための、ハッシュ関数の整列リストにおける第２の関数である。第２ハッシュ関数は、第１ハッシュ関数Ｈ０によってカバーされない、論理バケット空間におけるバケット、即ち、バケットn+1．．ｍをカバーし、ステップ５６において、ハッシュ関数Ｈ２にしたがってこの空間におけるバケットの１つにレコードを割り当てる。次に、ステップ４７において、論理バケット識別子を、不均等アクセス・メモリにおけるこの物理バケット位置に変換する。ステップ４８において、この物理パケット位置のコンテンツを読み出し、４９において、この物理バケット位置に利用可能なスロットがあるか否か判定を行う。スロットが利用可能である場合、本プロセスは、ステップ５０に進み、レコードをこのバケットに追加し、ステップ５１においてパケットを書き換えて論理／物理バケットテーブルを更新し、本プロセスは終了する。あるいは、ステップ４９において、利用可能なスロットがない場合、ステップ４４から、第３ハッシュ関数を使用して、本処理を繰り返す。そうでなければ、ハッシュ関数の全てが適用され終えた場合（５７）、ステップ５８においてテーブル（インデックス）は全て埋まる。
【００３９】
[0053]  ステップ４２において行われる選択に戻り、代わりに、レコード・タイプが第２タイプである場合（例えば、長命であり頻繁にアクセスされない）、本プロセスは以上のように処理を進めるが、このようなレコードをメモリの第２領域に優先的にマッピングするように、ハッシュ関数が適用される割り当て順序（５２）は｛Ｈ２，Ｈ１，Ｈ０｝となる。
【００４０】
[0054]  図３は、本発明の一実施形態によるレコード参照プロセス７０を示す。ステップ７１において開始し、参照プロセスにキーを供給する。７２において、ハッシュ関数Ｈ０を適用し、７３において、ハッシュ関数Ｈ０から、範囲０．．ｎにおける論理バケット識別子が得られる。次に、７４において、論理バケット識別子を物理バケット位置に変換し、７５において、物理バケット位置のコンテンツを読み出し、７６において物理バケットの検索を行い、キーの値を求める。７７においてキー値を有するレコードがこの物理バケットにおいて見つかった場合、本プロセスは、ステップ９０において、このレコード、即ち、キーおよび関連データを戻し、本プロセスは終了する。見つからない場合、本プロセスは７８に進み（図３の中央を下に進む）、７８において第２ハッシュ関数Ｈ２をキーに適用して、７９において、残りの論理バケット空間に及ぶバケットｎ＋１．．ｍの内の１つにレコードを配置する論理バケット識別子を生成する。８０において、この論理バケット識別子を不均等アクセス・メモリにおける物理バケット位置に変換し、８１において、物理バケットのコンテンツを読み出し、８３において、物理バケットの検索を行ってキーの値を求め、８３においてレコードが見つかった場合、９０においてこのレコードを戻し、本プロセスは終了する。８３においてレコードが見つからない場合、８４において第３ハッシュ関数Ｈ１をキーに適用し、８５において、結果的に得られたバケット識別子が、レコードをバケット０．．ｍの内１つに配置し、８６において、論理バケット識別子を物理バケット識別子に変換し、８７において、物理バケットの内容を読み出し、８８においてバケットを検索してキーの値を求め、８９においてレコードが見つかった場合、９０においてこのレコードを戻し、本プロセスは終了する。８９においてレコードが見つからない場合、本プロセスは９１において終了する。
【００４１】
[0055]  図４は、レコード削除動作のプロセス９２の一実施形態を示す。ステップ９３において開始し、例えば、図３に示した方法にしたがって、参照処理のためにキーを供給する。９４においてレコードが見つかった場合（例えば、図３におけるステップ７７、８３、および８９の内１つ）、本プロセスは９５に進み、物理バケットからこのレコードを除去し、必要に応じてバケットを再編成する。次に、９６において、バケットを書き換え、論理／物理バケットテーブル（以下で説明する）を更新し、本プロセスは完了する。ステップ９４においてレコードが見つからない場合、本プロセスは終了する。
【００４２】
[0056]  当業者であれば、図２から図４において説明した方法およびその他の方法に対する変更が、本発明の主題を利用しつつ、レコード動作のために使用されてもよいことは認められよう。つまり、以上の例は限定ではなく、本発明のある種の実施形態を例示することだけを意図している。
【００４３】
[0057]  既に説明したステップ4２における分類または選択では、ハッシュ関数の異なる整列リストを異なるタイプのレコードに適用する目的のために、レコードを分類することができ、どのハッシュ関数を適用すべきか決定するために他のプロセスから受けた情報を使用することによって実現することができる。一例として、ファイル・システムが、ファイル・データ、メタデータ、ビットマップ、およびディレクトリというような、様々な種類のデータを書き込む。ファイル・システムから来るこれらのデータ・タイプの各々がそのように表示され、本発明のプロセスが、これらのデータ・タイプを使用して、関連するレコードをメモリにおける選択記憶位置に優先的に割り当てることを可能にする。一例として、ファイル・データは、比較的長命で頻繁にアクセスされないと分類されてもよく、一方ファイル・システム・メタデータは、短命で頻繁にアクセスされると分類されてもよい。同様に、記憶システム自体が、レコードの特性およびメモリ領域の特性の１つ以上に基づいて、メモリにおける記憶位置を割り当てる選択ステップにおいて使用するために、メモリにおける異なる領域の性能特性に関する情報を有する。
【００４４】
[0058]  一実施形態では、本発明は、フラッシュ・メモリ・デバイスのスカベンジ・オーバーヘッドを低減するという格別な利点を有する。フラッシュ・メモリは、通例、５１２バイト・セクタ単位で読み出され、８KBページ単位で書き込まれ、１MB消去ブロック単位で消去される。書き込みは読み出しよりも遅く、消去は書き込みよりも遅い。フラッシュ・メモリを管理する単位は、５１２バイト・バケットであり、バケットはランダムに読み出され、書き込まれ、更新される。更新は、読み出し、変更、および書き込みを必要とする。フラッシュ・メモリは、消去せずに上書きすることができないので、空きバケットを生成するためには、バケットにおける有効なデータはいずれも、どこかに書き込まなければならない。
【００４５】
[0059]  スカベンジとは、消去ブロックを調べて、正しいデータを消去ブロックから読み出して他の場所に配置し、この消去ブロックを解放するプロセスである。この結果、システムにおいて余分な読み出し／書き込みが行われ、これは「書き込み増幅」(write amplification)問題と呼ばれることもある。適正に管理されないと、スカベンジ・オーバーヘッドは、デバイスの帯域幅利用において、初期書き込みトラフィックよりも不経済になる（例えば、２〜３倍以上）。本発明によれば、この問題は、頻繁に変更されるレコードをフラッシュ・メモリの局在化領域に局在化することによって解決される。このように頻繁に変更される（短命）データをフラッシュの狭い領域にマッピングすることによって、消去ブロック・スカベンジの間に書き換えるべきデータが減少し、書き込み増幅問題が低減する。
C.システム・アーキテクチャ、例  
[0060]  図５から図９は、不均等アクセス・メモリに格納されたインデックス・レコードにアクセスするシステムおよび方法の一実施形態を示す。このようなシステムおよび方法の更なる詳細は、Bowden et al.の同時係属中で本願と所有者が同じ米国特許出願公開第２０１０／０３３２８６４号に記載されている。この出願は、２０１０年１２月３０日に公開され、「スケーラブル・インデックス化」と題する。この特許出願をここで引用したことにより、その内容全体が本願にも含まれるものとする。
【００４６】
[0061]  図５は、バケット変換テーブル５１７およびキャッシュ５２３を利用する、様々なインデックス化動作を実現するためのシステム・アーキテクチャの全体像である。図５の最上位には、３つのインデックス動作５１２〜５１４が、参照機能５１５および変換機能５１６への選択可能な(alternative)入力として示されている。第１インデックス動作５１２では、キーに対するレコード・エントリから衛星データを戻すために「キーを参照する」。第２インデックス動作５１３では、キーに対するレコード・エントリを更新する（変更する）ために、「キーに対する衛星データを更新する」。第３インデックス動作５１４では、新たなレコード・エントリを挿入するために、「新たなキーを挿入する」。
【００４７】
[0062]  ３つのインデックス動作は全て、最初に参照機能５１５を実行し、インデックス、ここではハッシュテーブル参照をサポートする（例えば、高速化する）論理バケット識別子を生成するために、あるハッシュ関数を適用する。論理バケット識別子（インデックス）を変換機能５１６に入力し、論理バケット識別子ｆ７（インデックス）のある機能が、フラッシュ・メモリ５２６における物理バケット位置を生成する。この変換機能は、バケット変換テーブル５１７によって実現され、バケット変換テーブル５１７は、論理バケット識別子（インデックス化アルゴリズムによって供給される）のターゲット・フラッシュ・メモリ位置（フラッシュ・メモリにおける物理バケット位置）に対するマップである。フラッシュ・メモリ５２６に格納された辞書（インデックス）が、参照キー（例えば、オブジェクト名）を衛星データ（例えば、ディスクに格納されたデータへの位置ポインタ）にマッピングするレコードを含むことができる。
【００４８】
[0063]  次に、３つのインデックス化動作の内どれが実行されているかに依存して（参照、更新、または挿入）、図５の下半分に示すステップの内１つ以上を実行する。
【００４９】
[0064］  参照動作５１８では、変換機能によって識別されたバケット・エントリを、キャッシュ・ルックアサイド(cache lookaside)によって、フラッシュ・メモリにおけるターゲット・バケット５２２から読み出す（５３０）（例えば、ターゲット・バケットがキャッシュに格納されている場合、フラッシュ・メモリ５２５からではなく、キャッシュ５２３から読み出せばよい）。
【００５０】
[0065]  更新動作５１９では、変換機能によって識別されたバケット・エントリ（元のバケット・エントリ）を、フラッシュ・メモリ（またはキャッシュ）の消去ブロック５２１ａにおけるターゲット・バケット５２２から読み出し（５３０）、バケットを更新してキャッシュに移動し（５３２）、後続の順次書き込み５２４において、フラッシュ・メモリにおける順次連続する１組の部分ページ、複数のページ、および／または消去ブロック（例えば、新たな消去ブロック５２１ｂ）に複数のキャッシュ・バケット・エントリを読み出す。次いで、本プロセスはフラッシュにおいて移動した全てのバケットのステータスを、無効データ（例えば、未使用状態またはトリム動作に利用可能）に更新する。
【００５１】
[0066]  挿入動作５２０では、ターゲット・バケットを再度フラッシュから読み出し、フラッシュ・メモリにおける新たな位置への後続の順次書き込み５２４の間に、変更したバケット・エントリを再度キャッシュに移動する（５３４）。
【００５２】
[0067]  図５は、キャッシュ・バケット・エントリの集合体の連続フラッシュ・メモリ・バケットへの順次書き込み５２４を実行する前に、複数のバケット・エントリを収集するためのキャッシュ５２３を模式的に示す。一実施形態では、スカベンジ動作５２５が、空き消去ブロックを作るために使用される。このプロセスは、スカベンジ・プロセスの間に任意の有効バケットを（消去ブロックから）キャッシュに格納し、そのフラッシュ消去ブロックを空きとして再割り当てすることを含む。
【００５３】
[0068]  図６は、本実施形態において有用なデータ構造の種々の例を示す。このようなデータ構造は、例示であり限定でないことを意図する。
【００５４】
[0069]  図６Ａは、論理バケット識別子（インデックス化アルゴリズムによって生成される）を物理フラッシュ・バケット・アドレスに変換するバケット変換テーブル（ＢＴＴ）３００の一実施形態を示す。ＢＴＴテーブルのエントリは、３つのフィールド、即ち、有効３０１、物理バケット・アドレス３０２、および拡張バケット状態３０３を有することが示される。バケット・アドレスの粒度は、フラッシュ・デバイスの最少書き込みサイズにするとよい。即ち、部分的ページ書き込み（例えば、ＳＬＣ  ＮＡＮＤでは）またはページ書き込み（例えば、ＭＬＣ  ＮＡＮＤでは）のいずれかにするとよい。ＢＴＴは、論理対物理バケット・エントリの１：１マッピングである。このテーブルは、ランダム動作性能(random performance)（インデックス化アルゴリズムによるランダムな読み出しおよびランダムな書き込み）を高めるためのフラッシュ・バケット割り当ての再編成を可能にする。アルゴリズムの加速を可能にするために、ＢＴＴの第３フィールドに追加の状態情報を追加することもできる。
【００５５】
[0070]  図６Ｂは、バケット有効テーブル（ＢＶＴ）３０５の一実施形態を示す。このテーブルは、トリミングのためにバケットのブロックへのスカベンジを管理するために、フラッシュにおけるどの物理バケットが有効であるか追跡する。一例として、有効という名称が付けられたフィールド３０６は、コンパクト・ビット・アレイ（１ビット／バケット）であってもよい。ＢＶＴのサイズは、フラッシュ・バケット・エントリの総数であり、その部分集合がＢＴＴによって使用される。
【００５６】
[0071]  図６Ｃは、バケットに含まれる複数のレコード３１０、３１１、３１２．．．を、逆ＢＴＴポインタ３１３（バケット変換テーブル５１７への自己インデックス）と共に有するフラッシュ・バケット３０９の一実施形態を示す。つまり、各バケットは、フラッシュ・バケット（例えば、ページ）が挿入、移動、または削除されるときにＢＴＴを更新するために、１組の１つ以上のレコードおよび逆ポインタを含む。このバケットの各エレメント（レコードまたはポインタ）は、データ構造の個々の信頼性を高め、更に記憶デバイスの寿命を著しく延長させるために、追加のＥＣＣビットというような、冗長コンテンツが追加されていてもよい。例えば、停電イベントの間にデータの一貫性チェックを実施するために、オプションのシーケンス番号フィールドが、フラッシュ・バケット３０９に追加されてもよい。他の最適化フラグを設けてもよい。
【００５７】
[0072]  レコード・サイズはバケット・サイズと比較すると小さいので、これは、個々のレコード毎に追加のエラー復元情報を埋め込む好機（オプション）が得られる。このオプションの機構があると、訂正することができるビット・エラーおよび障害の数が増大し、このために基礎の記憶技術の有効動作寿命が延長することによって、本ソリューションの全体的な信頼性が向上する。
【００５８】
[0073]  図６Ｄは、複数の消去ブロック３１６（１〜Ｍ）を含むＳＬＣ  ＮＡＮＤフラッシュ・デバイス３１５の一例を示す。各消去ブロックは、複数のページ３１７（１〜Ｎ）を含む。この例では、各ページは４ＫＢであり、各ページは複数のバケット３１８（１〜Ｂ）を含み、各バケットは１ＫＢである。この例では、デバイスは部分的なページ書き込みをサポートする。
【００５９】
[0074]  典型的なフラッシュ・サブシステムは、複数のフラッシュ・デバイスで構成される。ＮＡＮＤフラッシュ・デバイスは、消去動作の間に所与のブロック内部においてページ（または部分ページ）毎に１回順次書き込まれ、複数のブロックが書き込みおよび読み出しに同時に利用可能である。
【００６０】
[0075]  バケットは、フラッシュ・デバイスの最少書き込みサイズを表す。通例、バケットはページとなる。部分的なページ書き込みが許される場合、ページ毎に４つのバケットをサポートする四部分ページ(four partial page)ＳＬＣ  ＮＡＮＤデバイスのように、フラッシュ・ページ当たり１つ以上のバケットを設けることもできる。消去ブロック毎に、複数のフラッシュ・ページが設けられる。フラッシュ・デバイス毎に複数の消去ブロックがあり、各ブロックが個々に消去される。
【００６１】
[0076]  図７Ａおよび図７Ｂは、空き消去ブロックを生成するためのスカベンジ・プロセスの一実施形態を示す。このスカベンジ・プロセスは、下位デバイス管理層の一部として実現される。このプロセスでは、フラッシュ消去ブロックにおける物理バケットのグループ（一部または全部）が、フラッシュから直接読み出され、消去ブロックにおけるどのバケットが有効であるか判断するために、バケット有効テーブル５２７が使用される。
【００６２】
[0077]  図７Ａに示すように、ステップ１（２２０）において、スカベンジ・プロセス５２５は消去ブロック５２１ａ全体を読み出す。ステップ２（２２２）において、有効な読み取りの全てのバケットを識別するために、スカベンジ・プロセスはバケット有効テーブル５２７を使用する。ステップ３（２２４）において、有効なバケット毎に、そのバケットにおける逆ＢＴＴポインタ３１３が、バケット変換テーブル５１７への自己インデックスとして使用され、論理バケット識別子をスカベンジ・プロセスに戻す。ステップ４（２２６）において、有効なバケットをキャッシュ５２３に格納する。各バケットは、その論理バケット識別子によってインデックス化される。
【００６３】
[0078]  図７Ｂは、スカベンジ・プロセス５２５が最初に物理パケット［９４，９７］までを読み出すプロセスを模式的に示す。ステップ２において、本プロセスは、バケット９５および９６が有効であると判断する。ステップ３において、バケット９５および９６の論理バケット識別子、即ち、タグ２３および４９が、それぞれ、バケット変換テーブル５１７から戻される。ステップ４において、２つのバケット９５および９６を、それらのそれぞれのインデックス・タグ２３、４９と共にキャッシュ５２３に移動する。
【００６４】
[0079]  図８は、レコード・フォーマットの一例を示す。レコード１４０は、全部で３２ビットであり、指紋（キー）を格納するために最初の２０バイトのフィールド１４１を含む。指紋は、データ・コンテンツの暗号ハッシュ・ダイジェスト、例えば、ＳＨＡ−１ハッシュ・アルゴリズムであってもよい。また、このレコードのフィールドは、２バイトの参照カウント・フィールド１４２、５バイトの物理ブロック・アドレス・フィールド１４３、１バイトのフラグ・フィールド１４４、および４バイトの雑多フィールド１４５も含む。ＰＢＡフィールド１４３は、指定された指紋１４１に対して、ディスクに格納されたデータの物理ブロック・アドレスへのポインタを含む。参照カウントは、ディスクに格納されたデータに対する参照の回数を追跡する。
【００６５】
[0080]  図９は、一実施形態におけるフラッシュ・メモリ・デバイス１６４の模式図であり、バケット、ページおよび消去ブロックの相対的な（代表的な）サイズを示す。ここでは、物理フラッシュ・デバイスは、サイズが２ＧＢであるチップ（パッケージ）１６５である。このチップ上には、２つのダイ（シリコン・ウェハ）１６６ａ、１６７ｂがある。各ダイ上には、２＾１４個の消去ブロックがあり、各消去ブロック１６７は通例６４ＫＢである。ページ１６８は、書き込むことができる最少サイズ、ここでは４ＫＢであり、同様に４ＫＢであるバケット１６９のサイズを決定する。
【００６６】
[0081]  以上で説明した方法は、適した計算および記憶環境において、例えば、１つ以上のコンピュータにおいて実行することができるコンピュータ実行可能命令のコンテキストで実現することができる。分散型計算環境（例えば）では、ある種のタスクは、通信ネットワークを介してリンクされたリモート処理デバイスによって実行され、プログラム・モジュールは、ローカルおよびリモート・メモリ記憶デバイス双方に配置することができる。通信ネットワークは、グローバル・エリア・ネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、または他のコンピュータ・ネットワークを含むことができる。尚、本明細書において説明したネットワーク接続は一例であり、コンピュータ間で通信を設定する(establish)他の手段を使用することもできる。
【００６７】
[0082]  コンピュータは、１つ以上のプロセッサとメモリとを含むことができる。コンピュータは、更に、ディスク・ドライブと、外部コンポーネントへのインターフェースとを含むこともできる。種々のコンピュータ読み取り可能媒体にコンピュータによってアクセスすることができ、揮発性および不揮発性双方の媒体、リムーバブルおよび非リムーバブル媒体を含む。コンピュータは、表示画面、タッチ・スクリーン、キーボード、またはマウスを含む種々のユーザ・インターフェース・デバイスを含むこともできる。
【００６８】
[0083]  これより図１０を参照すると、コンピュータと複数のディスク記憶デバイスとの間における通信のための一般的なシステム構成７００の一例が示されている。ディスク・ストレージは、ハード・ディスク・ドライブ、フロッピ・ディスク・ドライブ、および光ディスク・ドライブを含む、１つ以上の回転ディスクの表面に種々の電子、磁気、光学、または機械的方法によってデータがディジタル的に記録される種々の記憶デバイスの内任意のものとすることができる。ＣＰＵ７０２がシステム・メモリ７０４に取り付けられることが示され、システム・バス７０６がＣＰＵをチップセット７０８に接続する。このチップセットは、Ｉ／Ｏバス７１０および複数のＩＯスロット７１２を介して、複数のディスク・ドライバ７１６を接続するためのドライブ・コントローラというような、種々の入力／出力デバイスの内任意のものに接続される。また、このチップセットは他の記憶デバイス７１８にも接続されてもよい。このチップセットは、ビデオ・ポート７２０、ネットワーク・ポート７２２、マウス・ポート７２４、キーボード・ポート７２６等の内１つ以上を含むことができる。
【００６９】
[0084]  以上で説明したことは、本発明の例を含む。勿論、本発明について説明する目的のために、着想し得るあらゆるコンポーネントまたは方法の組み合わせについて説明することは不可能であるが、本発明の更に他の組み合わせおよび置換(permutations)も可能であることは、当業者には認められよう。したがって、本発明は、本開示および／または特許請求の範囲に該当する、そのような変形、変更、および変容の全てを包含することを意図している。
【図１】
2015515047.tif 000003
【図２Ａ】
2015515047.tif 000004
【図２Ｂ】
2015515047.tif 000005
【図３Ａ】
2015515047.tif 000006
【図３Ｂ】
2015515047.tif 000007
【図４】
2015515047.tif 000008
【図５】
2015515047.tif 000009
【図６Ａ】
2015515047.tif 000010
【図６Ｂ】
2015515047.tif 000011
【図６Ｃ】
2015515047.tif 000012
【図６Ｄ】
2015515047.tif 000013
【図７Ａ】
2015515047.tif 000014
【図７Ｂ】
2015515047.tif 000015
【図８】
2015515047.tif 000016
【図９】
2015515047.tif 000017
【図１０】
2015515047.tif 000018
【国際調査報告】
2015515047.tif 000019
2015515047.tif 000020
2015515047.tif 000021