(57)【特許請求の範囲】
【請求項１】
ランダム・アクセス・メモリに、データを、インデックス化動作が必要とされないように前記データのコンテンツに基づいて配置する方法であって、前記データが複数のデータ・エレメントを含み、前記メモリが複数の記憶位置を有し、各記憶位置が複数のデータ・エレメントを記憶可能であり、前記方法が、
コンピュータが、強いハッシュ関数をデータ・エレメントに適用することによって、前記データ・エレメントの署名を生成するステップであって、前記署名は、割り当てられた記憶位置において前記データ・エレメントを発見するための一意の識別子を含む、ステップと、
前記コンピュータが、弱いハッシュ関数を前記署名に適用することによって、前記データ・エレメントに前記メモリにおける記憶位置を割り当てるステップと
を含み、前記弱いハッシュ関数は複数のデータ・エレメントを同じ記憶位置に割り当てる、方法。
【請求項２】
請求項１記載の方法において、
割り当てる前記ステップは、前記コンピュータが、空き空間を有する記憶位置が見つかるまで複数の弱いハッシュ関数を次々と適用することによって、前記データ・エレメントに対する前記メモリにおける記憶位置を決定するステップを含む、方法。
【請求項３】
請求項１又は２記載の方法において、
前記メモリは、異なる性能特性を有し各々が複数の記憶位置を有する複数の領域を含み、
割り当てる前記ステップは、前記コンピュータが、前記データ・エレメントを前記メモリにおける記憶位置の選択領域に優先的に割り当てるよう、メモリにおける異なる性能特性を有する異なる領域における記憶位置をターゲットとする１つ以上の異なる弱いハッシュ関数を選択するステップを含む、方法。
【請求項４】
請求項３記載の方法において、各データ・エレメントが１つ以上の属性を有し、選択する前記ステップが、前記データ・エレメントの１つ以上の属性に基づく、方法。
【請求項５】
請求項３記載の方法において、
前記性能特性がアクセス時間である、方法。
【請求項６】
請求項３記載の方法において、
選択する前記ステップが、前記データ・エレメントの予想アクセス要求に基づく、方法。
【請求項７】
請求項３記載の方法において、
選択する前記ステップが、前記メモリにおける前記データ・エレメントの予想寿命に基づく、方法。
【請求項８】
請求項３記載の方法において、
選択する前記ステップが、前記データ・エレメントの予想参照要求に基づく、方法。
【請求項９】
請求項１記載の方法において、前記ランダム・アクセス・メモリが、一定の最悪アクセス時間を有する均等ランダム・アクセス・メモリを含む、方法。
【請求項１０】
請求項１から９のうちの何れか一項に記載の方法であって、
前記コンピュータが、各署名のビットの部分集合を含む部分署名キャッシュを維持するステップを含む方法。
【請求項１１】
ランダム・アクセス・メモリに、データを、インデックス化動作が必要とされないように前記データのコンテンツに基づいて配置するコンピュータ・システムであって、前記データが複数のデータ・エレメントを含み、前記コンピュータ・システムは、
１つ以上のプロセッサと、前記１つ以上のプロセッサによる実行のために１つ以上のプログラムを記憶するメモリとを有するサーバと、
強いハッシュ関数をデータ・エレメントに適用することによって、複数の前記データ・エレメントの各々の署名を生成するために前記１つ以上のプロセッサによって実行される署名生成モジュールであって、前記署名が、割り当てられた記憶位置において前記データ・エレメントを発見するための前記データ・エレメントの一意の識別子を含む、署名生成モジュールと、
弱いハッシュ関数を前記署名に適用して前記データ・エレメントにランダム・アクセス・メモリにおける記憶位置を割り当てるために、前記１つ以上のプロセッサによって実行される位置割り当てモジュールであって、前記ランダム・アクセス・メモリが複数の記憶位置を有し、各記憶位置が複数のデータ・エレメントを記憶可能であり、前記弱いハッシュ関数は複数のデータ・エレメントを同じ記憶位置に割り当てる、位置割り当てモジュールと、
前記データ・エレメントを前記ランダム・アクセス・メモリの割り当てられた前記位置に記憶するために、前記１つ以上のプロセッサによって実行される記憶モジュールと
を含む、コンピュータ・システム。
【請求項１２】
請求項１１記載のシステムであって、更に、
前記ランダム・アクセス・メモリであって、異なる性能特性を有し、各々が複数の記憶位置を有する複数の領域を含む前記ランダム・アクセス・メモリと、
前記ランダム・アクセス・メモリにおける記憶位置の選択領域に前記データ・エレメントを優先的に割り当てるよう、ランダム・アクセス・メモリにおける異なる性能特性を有する異なる領域における記憶位置をターゲットとする１つ以上の異なる弱いハッシュ関数を選択するために、前記１つ以上のプロセッサによって実行される選択モジュールと
を含むシステム。
【請求項１３】
請求項１２記載のシステムにおいて、
各データ・エレメントが１つ以上の属性を有し、前記選択が、前記データ・エレメントの１つ以上の属性に基づく、システム。
【請求項１４】
請求項１２記載のシステムにおいて、
前記ランダム・アクセス・メモリが、一定の最悪アクセス時間を有する均等ランダム・アクセス・メモリを含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]    本発明は、データの記憶に関し、更に特定すれば、インデックスの使用を必要とせずに、ランダム・アクセス・メモリにおけるデータのコンテンツに基づいてデータを配置する方法および装置に関する。
【従来技術】
【０００２】
[0002]  ファイル・システム、オペレーティング・システム、または他の記憶マネージャの重要な役割（job)は、データを記憶媒体に配置することである。データが書き込まれる場所、ならびにそれがアクセスされるときおよびその方法は、性能に大きな影響を及ぼす可能性がある。従前のファイル・システム、例えば、ＰＯＳＩＸファイル・システムは、データにアクセスするために論理ブロック付番（ＬＢＮ）アドレシングを使用する。しかしながら、記憶密度はアクセス時間よりも速く上昇するので、所与のデータ集合サイズに対して、データにアクセスするために必要とされる時間が増大し、したがってアクセス可能性が低下する。
【０００３】
[0003]  １つの代替案は、インデックスを有するファイル・システムまたは他の記憶システムを構築し、データ自体のコンテンツに基づいて各データ・エレメントを追跡することである。インデックスは、レコードの集合体を含み、各レコードは、データ・エレメントの暗号ハッシュ（署名）、参照カウント、およびデータ・エレメントがディスクにおいて位置する場所へのポインタで構成することができる。通例、各データ・エレメントのサイズは、４、８、１６、または２５６ＫＢであり、したがってインデックスには何十億ものレコードがある可能性がある。何十億ものレコードを有する商用システムでは、インデックスのサイズが６４から２５６ギガバイトになる場合もある。この性質の記憶システムでは、インデックスに対する動作が重要になる可能性があり、システムの性能における制限要因となる可能性があることが多い。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
[0004]  このため、先行技術のシステムの密度および／またはアクセス制限によって制限されない記憶システムが求められ続けている。
【課題を解決するための手段】
【０００５】
[0005]  インデックス化動作が必要とされないように、データのコンテンツに基づいてコンピュータ記憶媒体にデータを配置するための装置および方法を提供する。更に特定すれば、強い（例えば、暗号）ハッシュをデータに提供することによって、データ自体のコンテンツが、記憶媒体においてそれをどこに書き込むべきか判断する。記憶媒体は、ランダム・アクセス・メモリを含み、更に好ましくは、ソリッド・ステート・ディスク（ＳＳＤ）メモリのような均等ランダム・アクセス・メモリ(uniform random access memory)を含む。
【０００６】
[0006]  一実施形態では、強い（暗号）ハッシュをデータ・エレメントに適用して、署名を得る。次いで、データ・エレメントに対してメモリにおける記憶位置を生成するために、それよりも弱いハッシュ関数を署名に適用する。弱い方のハッシュ関数は、複数のデータ・エレメントを同じ記憶位置に割り当てることが予想されるが、署名は、この位置において特定のデータ・エレメントを置く（locating）ために一意の識別子を含む。一実施形態では、メモリにおいて空き空間が見つかるまで、各々有効な記憶位置を提供する複数の弱いハッシュ関数を連続的に適用する。種々の他の実施形態では、割り当てられる記憶位置は、データの署名およびデータ・エレメントの１つ以上の属性、および／または記憶技術、例えば、異なるタイプのデータ（例えば、短命で頻繁にアクセスされるデータ対長命で頻繁にアクセスされないデータ）、および異なる性能（例えば、アクセス・レイテンシ、メモリ寿命）特性を有するメモリの異なる領域の組み合わせによって決定することができる。一実施形態では、メモリは永続的である。本発明のこれらおよびその他の利点について、本発明の種々の実施形態において以下で説明する。
【０００７】
[0007]  本発明の一実施形態によれば、ランダム・アクセス・メモリにおいてデータを配置するコンピュータ実装方法を提供する。データは複数のデータ・エレメントを含み、メモリは複数の記憶位置を有する。この方法は、
強いハッシュ関数をデータ・エレメントに適用することによって、データ・エレメントに署名を生成するステップと、
弱いハッシュ関数を署名に適用することによって、データ・エレメントにメモリにおける記憶位置を割り当てるステップとを含む。署名はデータ・エレメントの一意の識別子を含み、弱いハッシュ関数は複数のデータ・エレメントを同じ記憶位置に割り当てる。
【０００８】
[0008]  一実施形態では、割り当てるステップは、空き空間を有する記憶位置が見つかる（located）まで、複数の弱いハッシュ関数を連続的に適用するステップを含む。
【０００９】
[0009]  一実施形態では、割り当てるステップは、データ・エレメントをメモリにおける記憶位置の選択領域に優先的に割り当てるために、データ・エレメントに適用する１つ以上の異なる弱いハッシュ関数を選択するステップを含む。
【００１０】
[0010]  一実施形態では、選択するステップは、データ・エレメントの１つ以上の属性に基づく。
【００１１】
[0011]  一実施形態では、異なる弱いハッシュ関数は、メモリにおいて異なる性能特性を有する異なる領域をターゲットとする。
【００１２】
[0012]  一実施形態では、性能特性はアクセス時間である。
【００１３】
[0013]  一実施形態では、選択するステップは、データ・エレメントの予想アクセス要求回数に基づく。
【００１４】
[0014]  一実施形態では、選択するステップは、メモリにおけるデータ・エレメントの予想寿命に基づく。
【００１５】
[0015]  一実施形態では、選択するステップは、データ・エレメントの予想参照要求回数に基づく。
【００１６】
[0016]  一実施形態では、弱いハッシュ関数を連続的に適用するステップは、メモリの区間利用度を高める。
【００１７】
[0017]  一実施形態では、この方法は、複数のデータ・エレメントを記憶位置に先入れ先出し順序で配置するステップを含む。
【００１８】
[0018]  一実施形態では、ランダム・アクセス・メモリは、一定の最悪アクセス時間を有する均等ランダム・アクセス・メモリを含む。
【００１９】
[0019]  一実施形態では、この方法は、各署名のビットの部分集合を含む部分署名キャッシュを維持するステップを含む。
【００２０】
[0020]  本発明の他の実施形態によれば、コンピュータ・システムを提供する。このコンピュータ・システムは、
１つ以上のプロセッサと、１つ以上のプロセッサによる実行のために１つ以上のプログラムを格納するメモリとを有するサーバと、
強いハッシュ関数をデータ・エレメントに適用することによって、データ・エレメントに署名を生成するために１つ以上のプロセッサによって実行される署名生成モジュールであって、署名がデータ・エレメントの一意の識別子を含む、署名生成モジュールと、
データ・エレメントにメモリにおける記憶位置を割り当てるために、弱いハッシュ関数を適用するために、１つ以上のプロセッサによって実行される位置割り当てモジュールであって、弱いハッシュ関数が、複数のデータ・エレメントを同じ記憶位置に割り当てる、位置割り当てモジュールと、
ランダム・アクセス・メモリの割り当てられた位置にデータ・エレメントを格納するために、１つ以上のプロセッサによって実行される記憶モジュールと、
を含む。
【００２１】
[0021]  一実施形態では、位置割り当てモジュールは、メモリの空間利用度を高めるために、データ・エレメントに複数の弱いハッシュ関数を連続的に適用する。
【００２２】
[0022]  一実施形態では、このシステムは、ランダム・アクセス・メモリにおける記憶位置の選択領域にデータ・エレメントを優先的に割り当てるために、データ・エレメントに適用する１つ以上の異なる弱いハッシュ関数を選択するために、１つ以上のプロセッサによって実行される選択モジュールを含む。
【００２３】
[0023]  一実施形態では、選択は、データ・エレメントの１つ以上の属性に基づく。
【００２４】
[0024]  一実施形態では、異なる弱いハッシュ関数は、メモリにおいて異なる性能特性を有する異なる領域をターゲットとする。
【００２５】
[0025]  一実施形態では、このシステムは、ランダム・アクセス・メモリを含む。
【００２６】
[0026]   一実施形態では、ランダム・アクセス・メモリは、一定の最悪アクセス時間を有する均等ランダム・アクセス・メモリを含む。
【図面の簡単な説明】
【００２７】
【図１】図１は、記憶位置をデータ・エレメントに割り当てるための本発明の一実施形態によるプロセスのフロー・チャートである。
【図２】図２は、記憶位置をデータ・エレメントに割り当てるためのシステムおよび方法の一例を示すブロック図である。
【図３】図３は、本発明の一実施形態にしたがってデータをストレージに書き込むためのプロセスのフロー・チャートである。
【図４】図４は、本発明の一実施形態にしたがってデータをストレージから読み出すためのプロセスのフロー・チャートである。
【図５】図５は、記憶位置をデータ・エレメントに割り当てるためのシステムの一例を示す模式ブロック図である。
【図６】図６は、データを処理し格納するための一般的なシステム構成の一実施形態を示す。
【発明を実施するための形態】
【００２８】
[0033]  これより、本発明の種々の実施形態について、図面を参照しながら説明する。以下の記載では、説明の目的に限って、多数の具体的な詳細が、本発明の１つ以上の実現例の完全な理解を得るために明示される。しかしながら、本発明はこれらの具体的な詳細がなくても実施できることは明らかである。他方では、周知の構造およびデバイスは、本発明を説明し易くするために、ブロック図形態で示される。
【００２９】
[0034]  本願において使用される場合、「コンポーネント」および「システム」という用語は、ハードウェア、ハードウェアおよびソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェアのいずれかのコンピュータ関連エンティティを指すことを意図する。例えば、コンポーネントが、プロセッサにおいて実行するプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行のスレッド、プログラム、および／またはコンピュータであってもよいが、これらに限定されるのではない。例示として、サーバにおいて実行するアプリケーションおよびこのサーバの双方がコンポーネントであることができる。１つ以上のコンポーネントがプロセスおよび／または実行のスレッド内に存在することもでき、 更にコンポーネントが１つのコンピュータに局在化される、および／または２つ以上のコンピュータ間で分散されるのでもよい。
【００３０】
[0035]  また、本発明は、発明のプロセスのフロー・チャートとしても示すことができる。説明を簡素にする目的に限って、フロー・チャートの形態で示される１つ以上の方法は一連のアクトとして説明されるが、本発明はアクトの順序には限定されないことは言うまでもなく認められよう。何故なら、本発明によれば、一部のアクトは、本明細書において示され説明される順序とは異なる順序で現れてもよく、および／または他のアクトと同時に現れてもよいからである。例えば、ある方法が、代わりに、状態図のような、一連の相関付けられた状態またはイベントとして表すこともできることは、当業者には理解され認められよう。更に、図示されるアクトの全てが、本発明による方法を実現するために必要ではない場合もある。
【００３１】
[0036]  本明細書において開示される本発明の種々の実施形態において、「データ」および「データ・エレメント」という用語は、相互交換可能に使用される。本明細書において使用される場合、データは、不透明なデータの集合体、例えば、コンピュータに入力され、その中で格納および処理され、または他のコンピュータに送信されることが可能な任意のシンボル・シーケンス（通例、「０」お+よび「１」で表される）を意味する。本明細書において使用される場合、データは、メタデータ、他のデータの記述を含む。記憶システムに書き込まれるデータは、本明細書において記載される場合、同じサイズのデータ・エレメント、または可変サイズのデータ・エレメントであってもよい。データの例には、情報、プログラム・コード、プログラム状態、プログラム・データ、他のデータ等が含まれる。
【００３２】
[0037]  本明細書において使用される場合、「記憶システム」は、ストレージ、例えば、ファイル・システム、ブロック記憶デバイス、または他のシステムにデータを格納するための任意のシステムまたはアプリケーションとすることができる。記憶システムは、ストレージにおける各データ・エレメントを参照するために識別子または名称を使用することができる。一例では、名称は、データ・コンテンツのハッシュ、好ましくは、データ・コンテンツの暗号ハッシュまたは変転防止ハッシュ(collision resistant hash)というような、グローバル一意識別子（ＧＵＩＤ）である。各データ・エレメントが、格納されたデータをユーザに再現することを可能にする名称を記憶システム内部で有するのである限り、他の命名慣例(naming convention)も可能である。一実施形態では、中央サーバが名称を生成する。データ名称は、通常、人ではなく、プログラムによる使用が意図された固定長の二進ストリングである。本明細書において使用されるような記憶システムに書き込まれるデータは、通例、同じまたは可変サイズの小さなデータ片（例えば、４、８、１６、または２５６ＫＢ）を数多く（例えば、数十億個）含むと考えられる。
【００３３】
[0038]  本明細書において使用する場合、コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造、プログラム・モジュール、または他のデータというような情報の格納のための、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＦＬＡＳＨメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル・バーサタイル・ディスク（ＤＶＤ）または他の光ディスク・ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージまたは他の時期記憶デバイス、あるいは所望の情報を格納するために使用することができコンピュータによってアクセスすることができる任意の他の媒体を含む。
【００３４】
[0039]  本明細書において使用する場合、ランダム・アクセス・メモリは、回転記憶媒体またはテープとは異なり、媒体内に格納された他のデータにアクセスすることなく、またそうでなければデータを分散させることなく、任意の順序でアクセスすることができるコンピュータ記憶媒体を意味する。ランダム・アクセス・メモリの例には、ソリッド・ステート・ディスク、ＳＲＡＭ、ＤＲＡＭ、ＥＥＰＲＯＭ、およびＦＬＡＳＨメモリが含まれる。
【００３５】
[0040]  本明細書において使用する場合、均等ランダム・アクセス・メモリとは、一定または均等の最悪アクセス時間で任意の順序でアクセスすることができるコンピュータ記憶媒体を意味する。その例には、ソリッド・ステート・ディスク、ＳＲＡＭ、ＲＯＭ、ＯＴＰ、およびＮＡＮＤフラッシュ・メモリが含まれる。
【００３６】
[0041]  図１は、本発明の一実施形態による方法を示す。ステップ１１において、データ・エレメントを本プロセスに入力する。ステップ１２において、強いハッシュ関数をデータ・エレメントに適用して、署名（一意の識別子）を生成する。ステップ１３において、それよりも弱いハッシュ関数を署名に適用し、データ・エレメントの記憶位置を、ランダム・アクセス・メモリに割り当てる。この弱い方のハッシュ関数は、本方法によって、複数のデータ・エレメントを同じ記憶位置に割り当てることが予想される。
【００３７】
[0042]  ハッシュ関数はいずれも、その主要なプロパティの１つが、その「衝突困難性」にある。即ち、結果的に得られるハッシュ値が所与の入力データに対して一意になる確率である。例えば、ＳＨＡ−１の場合、衝突困難性は非常に高く、ＳＨＡ−１関数が適用されたときに同じ値が得られる２つの入力データ・エレメントが同じ値になるという衝突の確率は非常に低いと想定することができる。本発明では、衝突確率が低い、強いハッシュ関数が、データ・エレメントに一意の識別子を生成するために使用される。一方、本発明では、ランダム・アクセス・メモリにおいてデータ・エレメントに記憶位置を割り当てるために、それよりも弱いハッシュ関数が署名に適用される。この弱い方のハッシュ関数は、比較的衝突の確率が高い。このため、弱い方のハッシュ関数が複数のデータ・エレメントをメモリにおける同じ記憶位置に割り当てることが予想され、本プロセスは、その位置における特定のデータ・エレメントを発見するために、一意の識別子に依存する。
【００３８】
[0043]  一実施形態では、弱い方のハッシュ関数は、複数の異なる弱いハッシュ関数を含むことができ、空間利用度を最適化するために、これらのハッシュ関数を署名に連続的に適用することができる。例えば、所与のメモリ位置（第１ハッシュ関数によって生成される）が埋まっている、即ち、利用可能なスロットがない場合、空間（利用可能なスロット）を有するかもしれない他のメモリ位置を生成するために、第２（異なる）ハッシュ関数が適用される。そのための空間（スロット）がある限り、具体的な位置は重要でない。
【００３９】
[0044]  このように、複数の弱いハッシュ関数を使用する理由の１つは、他の有効な位置が埋まっているときにデータのために代わりの位置を提供し、こうしてストレージの最大効率を高め／容量を増やすことである。基本的に、データの分量が増大するに連れて、署名が一意に分散されても、一旦弱いハッシュが署名に適用されると、無視できない確率の衝突がある。代わりの弱いハッシュ・アルゴリズムを設けることによって、衝突があるときにこれを使用することができ、こうしてストレージの利用度を、例えば、７０％（１つの弱いハッシュ・アルゴリズムを使用する場合）からほぼ９９％（３つの弱いハッシュ・アルゴリズムを使用する場合）に高めることができる。
【００４０】
[0045]  本明細書において使用されるような強いハッシュ関数の例には、ＳＨＡ−１、ＭＤ５のような暗号ハッシュ関数、またはＳＨＡ−２のような派生物、あるいはＢＬＡＫＥ、Grostl、ＪＨ、Keccak、およびSKeinのようなもっと新しいハッシュ関数が含まれる。本発明に限って言うと、ハッシュ関数の衝突困難性プロパティが主要な関心事であるが、他のプロパティ（例えば、原像計算困難性）も特定の実施形態では有用である場合もある。
【００４１】
[0046]  本明細書において使用されるような弱い（強いハッシュ関数と比較してそれよりも弱いまたは相対的に弱いとも呼ぶ）ハッシュ関数の例には、ビット・マスク、チェックサム、または指紋というような、単純なアルゴリズムが含まれる。本発明に限って言うと、強いハッシュ関数はハッシュ値の一様な（uniform）分布を生成し、弱いハッシュ関数はこのプロパティが必要とされないと仮定することができる。
【００４２】
[0047]  図２は、本発明を実現するためのシステム／アーキテクチャ２０の一実施形態の模式図である。ここでは、３つのハッシュ関数を使用してデータ・エレメント２１がハッシュされ、３つの候補メモリ位置が生成される。第１ハッシュ関数Ｈ０は、第１メモリ位置２６ａをターゲットにする。第２（異なる）ハッシュ関数Ｈ１（２３）は第２メモリ位置２６ｂをターゲットとし、更に他のハッシュ関数Ｈ２（２４）は更に他のメモリ位置２６ｄをターゲットとする。それぞれのハッシュ関数によって生成することができるアドレスの範囲は、３本の垂直線３６〜３８として、メモリ位置の下に示される。例えば、ハッシュ関数Ｈ０は、最初の３つのメモリ位置２６ａ〜２６ｃに及び、ハッシュ関数Ｈ１は５つのメモリ位置２６ａ〜２６ｅ全てに及び、同様に、ハッシュ関数Ｈ２もメモリ位置２６ａ〜２６ｅ全てに及ぶ。これは、例示の目的を意図する単なる一例であり、限定ではない。異なるメモリ位置が、同じまたは異なるアクセス特性、あるいは他の性能特性を有することもでき、異なるメモリ位置は同じまたは異なるメモリ技術を含むこともできる。
【００４３】
[0048]  メモリ位置２６ａ〜２６ｄの各々は、模式的に図２において、垂直スタックに配列された一連のスロット（２８ａ〜２８ｆ）として示され、矢印２７によって示されるように時間順に書き込まれ、例えば、先入れ先出し順序では、最も古い（最初に読み出された）データ・エレメントが最下位２８ｆにあり、最も新しい（最後に読み出された）データ・エレメントが最上位２８ａにある。データ・エレメントをストレージに書き込むとき、例えば、署名を生成するために強いハッシュ関数を適用し、メモリ位置を生成するために弱いハッシュ関数を署名に適用した後、割り当てられたメモリ位置が読み出され、データ・エレメントが既に存在する場合、それ以上のアクションは行われない。データ・エレメントが存在しない場合、新たなデータ・エレメントが一番上に行き、最上位にあったデータ・エレメントは押し下げられ、連続する順序で、それぞれのスロットにおけるデータ・エレメントが押し下げられ、最下位にあるデータ・エレメントが追い出されるようになっている。
【００４４】
[0049]  読み出し動作では、データ・エレメントの署名は既に分かっている。署名は、データベースまたは他のマッピング構造に格納されてもよく、あるいは本発明にしたがって格納される他のデータに含まれてもよい。その場合、１つ以上のデータ・エレメントがハッシュ・ツリーまたはメルケル・ツリー（Merkle tree)を形成する。弱い方のハッシュ関数が既知の署名に適用され、記憶位置を生成し、次いで記憶位置が読み出される。その位置における各データ・エレメントは、読み出される署名との照合のために検査されなければならない。
【００４５】
[0050]  一実施形態では、アクセス時間を短縮するために、部分署名キャッシュ(partial signature cache)４０を使用することができる。例えば、データ・エレメントの署名が101xxxxxで開始し、候補メモリ位置の署名が110xxxxxで開始する場合、このデータ・エレメントはそのメモリ位置に存続できない(live)。これは、そのメモリ位置において読み出しを行う必要性を回避する。部分署名キャッシュにおいて保持されるビット数は、より多くのメモリを犠牲にしてより大きな読み取り幅縮小(read attenuation)を得るように構成することができる。このキャッシュは、怠惰に（即ち、メモリ位置が読み出される／書き込まれるに連れて）入力する(populate)ことができ、または別のスキャニング・プロセスを使用することもできる。
【００４６】
[0051]  図３は、データ書き込み方法６０の一実施形態を示す。このプロセスはステップ６１において開始し、ここでデータ・エレメントを入力する。ステップ６２においてデータ署名を計算するために、強いハッシュ関数をデータ・エレメントに適用する。ステップ６４において、出力データ署名「Ｘ」（６３）をデータ・タイプによって分類する。この例では、データ・タイプが短命で頻繁にアクセスされるデータ・エレメントであると判定された場合、本プロセスは図３の左側を下に進んでステップ６５に行き、ここでハッシュ関数Ｈ０を署名に適用する。ステップ６６において、その結果がデータ記憶位置となり、６７において、このデータ記憶位置のコンテンツを読み出す。ステップ６８において、指定された記憶位置において利用可能なスロットがある場合、ステップ６９においてその記憶位置にデータ・エレメントを書き込み、本プロセスは完了する。ステップ６８に戻り、指定された位置には利用可能なスロットがない場合、本プロセスは処理を進めて、ステップ７２において、最初にアクセスされたデータを読み出し、それを、例えば、二次ストレージに書き込み、新たなデータ・エレメントをこの位置に書き込めるようにする。あるいは、最後にアクセスされたデータを他のストレージに動かすこと、または単に削除することもできる。
【００４７】
[0052]  ステップ６４に戻り、データ・タイプが、代わりに、長命で（例えば、比較的永続し）余りアクセスされない場合、本プロセスは、図３の右側を下に進んでステップ７０に行き、ここで、異なるハッシュ関数Ｈ１を署名に適用して、ステップ７１において異なる記憶（メモリ）位置を生成する。次いで、本プロセスは、ステップ６７〜６９および７２において既に説明したのと同じように処理を進める。
【００４８】
[0053]  図４は、データ読み出し方法８０の一実施形態を示す。ステップ８１から開始して、データ・エレメントの署名を引き出し（例えば、メタデータ表から）、ステップ８２において、ハッシュ関数Ｈ０を署名に適用する。その結果は、８３において、データ記憶位置となり、８４において、このデータ記憶位置のコンテンツを読み出す。８５において、強いハッシュ関数をデータ署名に適用して、８６においてデータ署名「Ｘ」を生成し、次いで、データ署名Ｘがステップ８１からの初期署名と一致するか否か判定を行う。肯定の場合、一致があり、ステップ８８において署名が一致したデータ・エレメントを戻し、本プロセスは終了する。否定の場合、本プロセスは、処理を進めて異なるハッシュ関数、即ち、Ｈ１．．Ｈｎの内１つ以上を署名に適用し、データ位置を生成し、本プロセスは、既に説明したようにステップ８３〜８８に進む。
【００４９】
[0054]  先に説明した分類または選択ステップ６４では、異なる弱いハッシュ関数を異なるデータに適用する目的のためにデータを分類することができ、他のプロセスから受けた情報を使用してどの弱いハッシュ関数を適用するか決定することによって実現することができる。一例では、ファイル・システムは、ファイル・データ、メタデータ、ビットマップ、およびディレクトリというような、数種類のデータを書き込む。ファイル・システムから来るこれらのデータ・タイプの各々は、そのように表示され(denote)、本発明のプロセスがこれらのデータ・タイプを使用して、データをメモリにおける選択記憶位置に優先的に割り当てることを可能にする。一例として、ファイル・データは、比較的長命で頻繁にアクセスされないものとして分類されるとよく、一方ファイル・システム・メタデータは、短命で頻繁にアクセスされるものとして分類されるとよい。同様に、記憶システム自体が、選択ステップにおける使用のために、メモリにおける異なる領域の性能特性に関する情報を有し、データの特性およびメモリ領域の特性の内１つ以上に基づいて、メモリにおける記憶位置を割り当てる。
【００５０】
[0055]  図５は、本発明を実現するためのコンピュータ・システムの一実施形態を示す。システム１５０は、署名（一意の識別子）を生成するために強いハッシュ関数をデータ・エレメントに適用する署名生成モジュール１５１を含む。位置モジュール１５２は、ランダム・アクセス・メモリにおいて記憶位置を割り当てるために、１つ以上の弱いハッシュ関数を署名に適用する。ここで、１つ以上の弱いハッシュ関数は、同じ記憶位置に複数のデータ・エレメントを割り当てる。記憶モジュール１５３は、ランダム・アクセス・メモリ１５４において、データ・エレメントを割り当てられた位置に格納する。
【００５１】
[0056]  以上で説明した方法は、適した計算および記憶環境、例えば、１つ以上のコンピュータにおいて実行することができるコンピュータ実行可能命令のコンテキストで実現することができる。分散型計算環境（例えば）では、ある種のタスクは、通信ネットワークを介してリンクされたリモート処理デバイスによって実行され、プログラム・モジュールは、ローカルおよびリモート・メモリ記憶デバイス双方に配置することができる。通信ネットワークは、グローバル・エリア・ネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、または他のコンピュータ・ネットワークを含むことができる。尚、本明細書において説明したネットワーク接続は一例であり、コンピュータ間で通信を設定する(establish)他の手段を使用することもできる。
【００５２】
[0057]  コンピュータは、１つ以上のプロセッサとメモリとを含むことができ、例えば、処理ユニット、システム・メモリ、およびシステム・バスを含むことができ、システム・バスは、システム・コンポーネントを結合する。システム・コンポーネントは、システム・メモリおよび処理有ニットを含むが、これらに限定されるのではない。コンピュータは、更に、ディスク・ドライブと、外部コンポーネントへのインターフェースとを含むこともできる。種々のコンピュータ読み取り可能媒体にコンピュータによってアクセスすることができ、揮発性および不揮発性双方の媒体、リムーバブルおよび非リムーバブル媒体を含む。コンピュータは、表示画面、タッチ・スクリーン、キーボード、またはマウスを含む種々のユーザ・インターフェース・デバイスを含むこともできる。
【００５３】
[0058]  これより図６を参照すると、コンピュータと複数のディスク記憶デバイスとの間における通信のための一般的なシステム構成７００の一例が示されている。ディスク・ストレージは、ハード・ディスク・ドライブ、フロッピ・ディスク・ドライブ、および光ディスク・ドライブを含む、１つ以上の回転ディスクの表面に種々の電子、磁気、光学、または機械的方法によってデータがディジタル的に記録される種々の記憶デバイスの内任意のものとすることができる。ＣＰＵ７０２がシステム・メモリ７０４に取り付けられることが示され、システム・バス７０６がＣＰＵをチップセット７０８に接続する。このチップセットは、Ｉ／Ｏバス７１０および複数のＩＯスロット７１２を介して、複数のディスク・ドライバ７１６を接続するためのドライブ・コントローラというような、種々の入力／出力デバイスの内任意のものに接続される。また、チップは他の記憶デバイス７１８に接続されてもよい。チップセットは、ビデオ・ポート７２０、ネットワーク・ポート７２２、マウス・ポート７２４、キーボード・ポート７２６等の内１つ以上を含むことができる。
【００５４】
[0059]  以上で説明したことは、本発明の例を含む。勿論、本発明について説明する目的のために、着想し得るあらゆるコンポーネントまたは方法の組み合わせについて説明することは不可能であるが、本発明の更に他の組み合わせおよび置換(permutations)も可能であることは、当業者には認められよう。したがって、本発明は、本開示および／または特許請求の範囲に該当する、そのような変形、変更、および変容の全てを包含することを意図している。
【図１】
0005902323.tif 000002
【図２】
0005902323.tif 000003
【図３】
0005902323.tif 000004
【図４】
0005902323.tif 000005
【図５】
0005902323.tif 000006
【図６】
0005902323.tif 000007