JP2016051481A - 非一時的なコンピュータ可読媒体、記憶装置、およびデータを管理するための方法 - Google Patents

Abstract

【課題】記憶システム内のデータを管理するために、ガベージコレクタを用いて、使用されていないデータからメモリを解放する。【解決手段】データを管理する方法を提供する。この方法は、データを永続記憶域に書込む第１リクエストを受信するステップと、第１リクエストに応じて、前述のデータを永続記憶域内の短期存続ブロックに書込むステップとを含む。前述のデータは、短期存続データまたは存続期間未知のデータである。この方法はさらに、修正したガーベッジコレクション操作を実行するステップを含む。この修正したガーベッジコレクション操作は、第１ブロックから第１フラグページを選択するステップと、第１フラグページが使用可能であることを判断するステップと、第１フラグページが使用可能である判断に基づき、第１フラグページを永続記憶域内の長期存続ブロックに移行するステップとを含む。長期存続ブロックは、短期存続ブロックと別体であり、短期存続データを記憶しない。【選択図】図３

Description

背景
一ブロックのデータを記憶システムに書込む場合、平均で一ブロックのデータの半分を移動する必要がしばしばある。よって、記憶システムにデータを書込むことは、システム上に大幅な遅延を引起し、その結果、システムの全体的な性能を低下する。一般的には、記憶システム内のデータを管理するために、ガベージコレクタを用いて、使用されていないデータからメモリを解放する。

概要
一般に、一局面において、本発明は、プロセッサによって実行されると方法を実行する命令を含む非一時的なコンピュータ可読媒体に関する。この方法は、データを永続記憶域に書込む第１リクエストを受信するステップと、第１リクエストに応じて、データを永続記憶域内の短期存続ブロックに書込むステップとを含み、データは、短期存続データであり、修正したガーベッジコレクション操作を実行するステップを含む。修正したガーベッジコレクション操作は、第１ブロックから第１フラグページを選択するステップと、第１フラグページが使用可能であることを判断するステップと、第１フラグページが使用可能である判断に基づき、第１フラグページを永続記憶域内の長期存続ブロックに移行するステップとを含む。長期存続ブロックは、短期存続ブロックと別体であり、長期存続ブロックは、短期存続データを記憶しない。

一般に、一局面において、本発明は、データを管理するための方法に関する。この方法は、データを永続記憶域に書込む第１リクエストを受信するステップと、第１リクエストに応じて、データを永続記憶域内の短期存続ブロックに書込むステップとを含み、データは、短期存続データおよび存続期間未知のデータからなる群から選択され、修正したガーベッジコレクション操作を実行するステップを含む。修正したガーベッジコレクション操作は、第１ブロックから第１フラグページを選択するステップと、第１フラグページが使用可能であることを判断するステップと、第１フラグページが使用可能である判断に基づき、第１フラグページを永続記憶域内の長期存続ブロックに移行するステップとを含む。長期存続ブロックは、短期存続ブロックと別体であり、長期存続ブロックは、短期存続データを記憶しない。

一般に、一局面において、本発明は、記憶装置に関する。この記憶装置は、永続記憶域と、命令を含む非一時的なコンピュータ可読媒体と、命令を実行するように構成されたプロセッサとを含み、命令は、プロセッサによって実行されると方法を実行する。この方法は、（ａ）データを永続記憶域に書込む第１リクエストを受信するステップと、（ｂ）第１リクエストに応じて、データを永続記憶域内の短期存続ブロックに書込むステップとを含み、データは、短期存続データおよび存続期間未知のデータからなる群から選択され、（ｃ）修正したガーベッジコレクション操作を実行するステップを含む。修正したガーベッジコレクション操作は、第１ブロックから第１フラグページを選択するステップと、第１フラグページが使用可能であることを判断するステップと、第１フラグページが使用可能である判断に基づき、第１フラグページを永続記憶域内の長期存続ブロックに移行するステップとを含む。長期存続ブロックは、短期存続ブロックと別体であり、長期存続ブロックは、短期存続データを記憶せず、修正したガーベッジコレクション操作の少なくとも一部は、（ａ）および（２）からなる群から選択される少なくとも１つの操作と並行して実行される。

本発明の他の局面は、以下の説明および添付の特許請求の範囲から明らかになるであろう。

本発明の１つ以上の実施形態に係るシステムを示している。 本発明の１つ以上の実施形態に係る固体メモリモジュールを示している。 本発明の１つ以上の実施形態に係るブロックを示している。 本発明の１つ以上の実施形態に係るフラグページを示している。 本発明の１つ以上の実施形態に係るＴＯＣページを示している。 本発明の１つ以上の実施形態に係るブロックの一例を示している。 本発明の１つ以上の実施形態に係るコンテンツエントリ表（ＴＯＣ）を示している。 本発明の１つ以上の実施形態に係る書込みリクエストを受信するためのフローチャートを示している。 本発明の１つ以上の実施形態に係る修正したガーベッジコレクション操作のフローチャートを示している。 従来処理の書込みリクエストの一例を示している。 従来のガーベッジコレクション操作の一例を示している。 本発明の１つ以上の実施形態に係る修正したガーベッジコレクション操作によるデータ移行の一例を示している。 本発明の１つ以上の実施形態に係る修正したガーベッジコレクション操作によるデータ移行の一例を示している。

詳細な説明
本発明の特定の実施形態は、添付の図面を参照して詳細に説明する。以下、本発明の実施形態の詳細な説明において、本発明に対するより完全な理解を提供するために、特定の詳細が多く記載されている。しかしながら、これらの特定の詳細なしに本発明を実施できることは、当業者にとって明らかであろう。他の例において、説明を必要以上に複雑化しないように、周知の特徴は、詳細に記載されていない。

図１〜６Ｂに関する以下の説明では、本発明のさまざまな実施形態において、１つの図面に関連して説明した構成要素は、他の図面に関連して説明した１つ以上の同様な名前を有する構成要素に相当してもよい。簡潔のために、これらの構成要素は、各図に関して繰返して説明しない。したがって、各図面の構成要素の各実施形態は、いずれも参照により１つ以上の同様な名前の構成要素を有する他のすべての図面に組込まれ、必要に応じて存在すると想定される。さらに、本発明のさまざまな実施形態に係る図面の構成要素の説明は、対応している他の図面の同様な名前を有する構成要素に関連して説明した実施形態に加えて、またはその実施形態と合わせて、またはその実施形態の代わりに実施することができる任意の実施形態であるように解釈されるべきである。

一般に、本発明の実施形態は、データの存続期間を用いて、記憶装置に記憶されているデータまたは書込まれたデータをソートする方法およびシステムに関する。具体的には、本発明の実施形態は、永続的データを短期存続データと別々に記憶することに関する。本発明の１つ以上の実施形態によれば、存続期間に基づいてデータをソートすることによって、記憶装置の書込み量を減少することができる。本発明の１つ以上の実施形態において、書込み量は、記憶装置に各データを書込むのに必要されたデータ移行の回数に対応している。プログラム／消去サイクルの数は、固体メモリモジュールの使用期間を低下する可能性があるため、書込み量の減少は、性能上有利である。

図１は、本発明の一実施形態に係るシステムを示している。図１に示すように、このシステムは、１つ以上のクライアント（１）と記憶装置（１０２）とを含む。以下、各構成要素について説明する。

本発明の１つ以上の実施形態において、クライアント（１００）は、読出しリクエストおよび／または書込みリクエストを記憶装置（１０２）に指示する機能を含むシステム上で実行される任意のシステムまたはプロセスである。本発明の１つ以上の実施形態において、各クライアント（１００）は、プロセッサ（図示せず）と、メモリ（図示せず）と、永続記憶域（図示せず）とを含むことができる。

本発明の１つ以上の実施形態において、クライアント（１００）は、記憶装置（１０２）に動作可能に接続されている。本発明の１つ以上の実施形態において、記憶装置（１０２）は、揮発性記憶域および永続記憶域を含み、１つ以上のクライアント（１００）からの読み出しリクエストおよび／または書込みリクエストを処理するように構成されたシステムである。記憶装置（１０２）はさらに、修正したガーベッジコレクション操作を実行するように構成されている。この修正したガーベッジコレクション操作は、以下（たとえば、図４を参照）に説明したガーベッジコレクション操作と一致する方法で、任意のコンテンツエントリ表(ＴＯＣ)およびフラグを長期存続ブロックに移行することを含む。記憶装置（１０２）はさらに、以下（たとえば、図３を参照）に説明した方法と一致する方法で、書込みリクエストに応じてデータを記憶装置に記憶するように構成されている。

本発明の１つ以上の実施形態において、記憶装置（１０２）は、プロセッサ（１０４）と、メモリ（１０６）と、１つ以上の固体メモリモジュール（たとえば、固体メモリモジュールＡ（１１０Ａ）、固体メモリモジュールＢ（１１０Ｂ）、固体メモリモジュールＮ（１１０Ｎ））とを含む。

本発明の１つ以上の実施形態において、メモリ（１０６）は、任意の揮発性メモリであってもよい。揮発性メモリは、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、シンクロナスＤＲＡＭ、ＳＤＲ ＳＤＲＡＭ、およびＤＤＲ ＳＤＲＡＭを含むが、これらに限定されない。本発明の１つ以上の実施形態において、メモリ（１０６）は、（ＴＯＣエントリおよびフラグ用のデータを含む）さまざまなデータを固体メモリモジュール（たとえば、１１０Ａ、１１０Ｂ、１１０Ｎ）に記憶する前に、そのデータを一時的に記憶するように構成されている。メモリ（１０６）は、プロセッサ（１０４）に動作可能に接続されている。

本発明の１つ以上の実施形態において、プロセッサ（１０４）は、命令を実行するように構成されたシングルコアまたはマルチコアを有する電子回路群である。プロセッサ（１０４）は、本発明の１つ以上の実施形態を実現するための命令を実行するように構成されている。これらの命令は、記憶装置（１０２）の内部に配置されまたは記憶装置（１０２）に動作可能に接続されている非一時的なコンピュータ可読媒体（図示せず）に記憶されている。代替的に、記憶装置（１０２）は、ハードウェアを用いて実現することができる。記憶装置（１０２）は、本発明から逸脱することなく、ソフトウェアおよび／またはハードウェアの任意の組合わせを用いて実現することができる。

本発明の１つ以上の実施形態においては、記憶装置（１０２）は、インメモリデータ構造（１０８）を作成および更新するように構成されている。このインメモリデータ構造は、メモリ（１０６）に記憶されている。本発明の１つ以上の実施形態において、インメモリデータ構造は、論理アドレスと物理アドレスとの間の（直接的または間接的な）マッピングを含む。本発明の１つ以上の実施形態において、論理アドレスは、クライアント（１００）の視点から見れば、データが存在するアドレスである。本発明の１つ以上の実施形態において、論理アドレスは、ハッシュ関数（たとえば、ＳＨＡ−１、ＭＤ−５など）をｎタプルに適用することによって生成されたハッシュ値である（またはハッシュ値を含む）。本発明の１つ以上の実施形態において、ｎタプルは、＜オブジェクトＩＤ、オフセットＩＤ＞である。オブジェクトＩＤは、オブジェクト（たとえば、ファイル）を規定し、オフセットＩＤは、オブジェクトの開始アドレスに関連する位置を規定する。本発明の別の実施形態において、ｎタプルは、＜オブジェクトＩＤ、オフセットＩＤ、生成時間＞である。生成時間は、（オブジェクトＩＤを用いて識別された）ファイルの作成時間に対応する。代替的に、論理アドレスは、論理オブジェクトＩＤおよび論理バイトアドレス、または論理オブジェクトＩＤおよび論理アドレスオフセットを含むことができる。本発明の別の実施形態において、論理アドレスは、オブジェクトＩＤおよびオフセットＩＤを含む。当業者であれば、複数の論理アドレスが単一の物理アドレスにマッピングされることができ、論理アドレスが上記の実施形態に限定されないことを理解するであろう。

本発明の１つ以上の実施形態において、物理アドレスは、メモリ（１０６）の内部位置または固体メモリモジュール（たとえば、１１０Ａ、１１０Ｂ、１１０Ｎ）の内部位置に対応することができる。本発明の１つ以上の実施形態において、複数のコピーのデータが記憶装置（１０２）内に存在する場合、インメモリデータ構造は、単一のハッシュ値を複数の物理アドレスにマッピングすることができる。

本発明の１つ以上の実施形態において、固体メモリモジュール（たとえば、１１０Ａ、１１０Ｂ、１１０Ｎ）は、固体メモリを用いて長期存続データを記憶する任意のデータ記憶装置に相当する。本発明の１つ以上の実施形態において、固体メモリは、ＮＡＮＤフラッシュメモリ、ＮＯＲフラッシュメモリ、磁気ＲＡＭメモリ（Ｍ−ＲＡＭ）、スピントルク磁気ＲＡＭメモリ（ＳＴ−ＭＲＡＭ）、相変化メモリ（ＰＣＭ）、または不揮発性記憶種メモリ（ＳＣＭ）として定義された任意の他のメモリを含むことができ、これらに限定されない。

当業者であれば、本発明は、図１に示した構成に限定されるものではないことを理解するであろう。

以下の説明は、固体メモリ装置を用いて実現された本発明の実施形態を説明する。図２Ａを参照して、図２Ａは、本発明の１つ以上の実施形態に従ったデータ記憶装置（図示せず）の固体メモリモジュールを示している。データ記憶装置（図示せず）は、複数の固体メモリモジュールを含むことができる。固体メモリモジュール（２００）は、１つ以上のブロックを含む。本発明の１つ以上の実施形態において、ブロックとは、固体メモリモジュール（２００）内部に位置する最小の消去可能な記憶単位である。

図２Ｂは、本発明の１つ以上の実施形態に係るブロックを示している。より具体的には、各ブロック（２０２）は、１つ以上のページを含む。本発明の１つ以上の実施形態において、ページとは、固体メモリモジュールの内部において、読出しおよび（ページに初期の書込みを含む）プログラム動作用の最小のアドレス可能な単位である。本発明の１つ以上の実施形態において、ブロック内の各ページは、フラグページ（図２Ｃを参照）またはフラグページ（図２Ｄを参照）のいずれかである。

本発明の１つ以上の実施形態において、ブロック内のページを書換えることは、ブロックの全体を書換える必要がある。ブロックには、限られた数のプログラム（たとえば書込み）／消去サイクルを有する。プログラム／消去サイクルは、１つ以上のページをブロックに書込んだ後、ブロック全体を消去することを含む。１つのブロック内のページを別のブロックに移行することによって、プログラム／消去サイクルの数をブロック全体に亘って同様に維持することができる。これは、「ウェアレベリング」（Wear Leveling）と呼ばれる。

本発明の１以上の実施形態において、長期存続ブロックとは、永続データを記憶するブロックである。永続データとは、少なくとも１つのガベージコレクションサイクルを超える存続期間を有するデータである。換言すれば、データが使用可能ページに関連付けられている場合（図４のステップ４１４を参照）、そのデータは、永続データ（「長期存続データ」とも呼ばれる）であると判断される。本発明の１つ以上の実施形態において、ガーベッジコレクションサイクルは、記憶装置内部のブロックに対し、修正したガーベッジコレクション操作（図４を参照）をブロック毎に反復して実行することに相当する。本発明の１つ以上の実施形態において、短期存続ブロックとは、短期存続データまたは存続期間未知のデータのいずれかを記憶するブロックである。本発明の１つ以上の実施形態に従って、存続期間未知のデータは、短期存続データであると仮定される。本発明の１つ以上の実施形態において、短期存続ブロックに位置する短期存続データは、長期存続ブロックに位置する長期存続データとは別々に記憶されている。本発明の１つ以上の実施形態において、短期存続データは、ガベージコレクションサイクルが終わる前に、古くなるまたは廃止される（すなわち、使わなくなる）可能性がある。換言すれば、短期存続データは、使用不可になる（たとえば、古くなるまたは廃止される）可能性が高いため、修正したガーベッジコレクション操作（図４を参照）において移行されない。代替的に、未知の存続期間を有するデータを短期存続データとして仮定されているが、そのデータが長期存続データである可能性もある（たとえば、図４のステップ４１４を参照するように、未知の存続期間を有するデータは、ガベージコレクション処理の間に使用可能ページに位置する場合、長期存続データとして認められてもよいだろう）。

図２Ｃは、本発明の１つ以上の実施形態に係るフラグページを示している。本発明の１つ以上の実施形態において、フラグページ（２０４）は、１つ以上のフラグを含む。本発明の１つ以上の実施形態において、フラグは、有限量のユーザデータ（たとえば、クライアントによって提供され、記憶装置に記憶されたデータ）に相当する。また、指定ページ内のフラグは、均一なサイズまたは不均一なサイズを有してもよい。さらに、指定ブロック内のフラグは、均一なサイズまたは不均一なサイズを有してもよい。本発明の１つ以上の実施形態において、指定フラグは、ページのサイズより小さくてもよく、ページのサイズと同一であってもよく、または１つ以上のページを跨ってもよい。本発明の１つ以上の実施形態において、フラグページは、フラグのみを含む。本発明の１つ以上の実施形態において、各フラグは、ユーザデータを含む。

図２Ｄは、本発明の１つ以上の実施形態に係るＴＯＣページを示している。本発明の１つ以上の実施形態において、ＴＯＣページ（２０６）は、１つ以上のＴＯＣエントリを含む。ＴＯＣエントリの各々は、指定フラグに対応するメタデータを含む。また、フラグページ（２０６）は、ブロック（２０２）内部の別のフラグページへの参照を含むことができる。本発明の１つ以上の実施形態において、ＴＯＣページは、ＴＯＣエントリのみ（必要に応じて、ブロック内部の別のフラグページへの参照と）を含み、フラグを含まない。本発明の１つ以上の実施形態において、各ＴＯＣエントリは、ブロック（２０２）内部のフラグ（図２Ｃを参照）に相当する。ＴＯＣエントリは、ブロック内のフラグのみに対応している。換言すれば、ＴＯＣページは、ブロックに関連しており、そのブロック内のフラグに対応するＴＯＣエントリのみを含む。本発明の１つ以上の実施形態において、各固体メモリモジュール内の各ブロックに存在している欠陥のない最終ページが、ＴＯＣページである。

図２Ｅは、本発明の１つ以上の実施形態に係るブロックの一例を示している。より具体的には、図２Ｅは、ＴＯＣページ（２１０、２１２、２１４）と、フラグページ（２１６、２１８、２２０、２２２、２２４、２２６）とを含むブロック（２０８）を示している。本発明の１つ以上の実施形態において、ブロック（２０８）は、概念上、「底部」から「頂部」に充填される。さらに、ＴＯＣページは、フラグページ内のフラグに対応するＴＯＣエントリの累計サイズがページのサイズと等しくなるときに、作成され、記憶される。図２Ｅを参照して、たとえば、フラグページ０（２１６）およびフラグページ１（２１８）は、ブロック（２０８）に記憶されている。フラグページ０（２１６）およびフラグページ１（２１８）内のフラグ（図示せず）に対応するＴＯＣエントリ（図示せず）は、ブロック内のページのサイズに等しい総累計サイズを有する。したがって、ＴＯＣページ（２１４）は、（ブロック内のフラグに対応するＴＯＣエントリを用いて）生成され、ブロック（２０８）に記憶される。その後、フラグページ２（２２０）は、ブロック（２０８）に書込まれる。フラグページ２（２２０）内のフラグ（図示せず）に対応するＴＯＣエントリがブロック内のページのサイズに等しい総累計サイズを有するため、ＴＯＣページ（２１２）は、作成され、ブロック（２０８）に記憶される。さらに、ブロック（２０８）に既にＴＯＣページが存在しているため、ＴＯＣページ（２１２）は、ＴＯＣページ（２１４）への参照をさらに含む。

このプロセスは、ブロック（２０８）内に充填するページが１つしか残らないまで反復される。この時点で、ＴＯＣページ（２１０）が作成され、ブロック（２０８）の最終ページに記憶される。当業者であれば、ＴＯＣページ（２１０）内のＴＯＣエントリの累計サイズは、ページのサイズより小さくてもよいことを理解するであろう。このような場合に、ＴＯＣページは、ＴＯＣエントリの総累計サイズとページサイズとの差を対処するために、パディングを含むことができる。最後に、ブロック（２０８）に他のＴＯＣページが存在しているため、ＴＯＣページ（２１０）は、１つの他のＴＯＣページ（２１２）への参照をさらに含む。

図２Ｅに示すように、ＴＯＣページは、ブロックの「頂部」からページの「底部」にリンクされている。これにより、ＴＯＣページの「上方」にあるＴＯＣページからの参照に従って、ＴＯＣページを得ることができる。たとえば、ＴＯＣページ（２１０）内の参照を用いて、ＴＯＣページ（２１２）にアクセスすることができる。

当業者であれば、ブロック（２０８）は、フラグページおよびＴＯＣページのみを含むが、本発明から逸脱することなく、フラグページおよびＴＯＣページ以外の他のページ（たとえば、パリティデータを含むページ）を含んでもよいことを理解するであろう。このような他のページは、ブロック内に存在してもよく、実装に応じてＴＯＣページとフラグページとの間に挟まれてもよい。

図２Ｆは、本発明の１つ以上の実施形態に係るＴＯＣエントリを示している。本発明の１つ以上の実施形態において、各ＴＯＣエントリ（２３０）は、フラグに対応するメタデータを含み、１つ以上の以下のフィールド、すなわち、（ｉ）記憶されているオブジェクトを識別するためのオブジェクトＩＤ（２３２）、（ｉｉ）ＴＯＣエントリに対応するフラグが固体メモリモジュールに書込まれた時間（たとえば、制御モジュール内に配置されたプロセッサのプロセッサクブロック値）を指定するための生成時間（２３４）、（ｉｉｉ）（オブジェクトＩＤによって識別される）オブジェクトの先頭に関連するオブジェクトの位置点を特定するためのオフセットＩＤ（２３６）、（ｉｖ）フラグのサイズを指定するためのフラグメントサイズ（２３８）、（ｖ）フラグが記憶されているブロック内のページを識別するためのページＩＤ（２４０）、および（ｖｉ）（ページＩＤによって識別された）ページ内のフラグの開始位置を特定するためのバイト（２４２）を含んでもよい。ＴＯＣエントリ（２３０）は、本発明から逸脱することなく、他のフィールド（２４８）を含んでもよい。

当業者であれば、ＴＯＣエントリは、本発明から逸脱することなく、図２Ｆに示されたフィールドによりも、追加のフィールドまたは少ないフィールドを含むことができることを理解するであろう。また、本発明から逸脱することなく、ＴＯＣエントリのフィールドを異なる順序で配置してもよくおよび／または組合わせてもよい。さらに、図２Ｆに示されているＴＯＣエントリ内のフィールドがすべて同一のサイズを有するように見えるが、ＴＯＣエントリ内のさまざまなフィールドの大きさが不均一であってもよく、任意の指定フィールドのサイズがＴＯＣエントリの実装に応じて変化してもよい。

フローチャートを参照して、フローチャート内のさまざまなステップが連続的に示され記載されているが、当業者であれば、一部またはすべてのステップは、異なる順序で実行されてもよく、組合わせられまたは省略されてもよく、一部またはすべてのステップは、並行に実行されてもよいことを理解するであろう。本発明の１つ以上の実施形態において、図３および図４に示された１つ以上のステップは、図３および図４に示された１つ以上の他のステップと並行に実行されてもよい。より具体的には、図３の受信した書込みリクエストおよび図４の修正したガーベッジコレクション操作は、並行に行われてもよい。よって、本発明の１つ以上の実施形態によれば、データの存続期間に基づき、記憶装置内のデータをソートすることは、書込みリクエストによってデータ（長期存続データであることが分かった場合）を潜在的に合体すること、および修正したガーベッジコレクション操作によってデータを移行することを生じさせることができる。

図３を参照して、図３は、本発明の１つ以上の実施形態に従った書込みリクエストを受信するためのフローチャートを示している。

ステップ３０２では、データを記憶装置に書込むための書込みリクエストがクライアントから受信される。このリクエストは、記憶すべきデータを含んでもよく、記憶すべきデータへの参照を含んでもよい。このリクエストは、本発明から逸脱することなく、任意の形態をとることができる。

ステップ３０４では、データが永続データであるか否かを判断する。本発明の１つ以上の実施形態において、データが永続データであることを判断することは、データが永続的であることを記憶装置に伝達するアプリケーションプログラミングインタフェース（ＡＰＩ）を介して行うことができる。たとえば、記憶装置が永続的であることを認識するタグまたはビットを書込みリクエストにまたはデータ自体に加えてもよい。データが永続的であることを記憶装置に伝達することは、本発明から逸脱することなく、他の方法を含むことができる。

データが永続データであると判断された場合、方法は、ステップ３０６に進むことができる。ステップ３０６では、長期存続ブロックが識別される。本発明の１つ以上の実施形態において、任意のフリーブロックまたは空きブロックが長期存続ブロックとして選択されてもよい。追加的にまたは代替的には、ブロックをウェアレベリングするために、そのプログラム／消去サイクルが一定の閾値を超えるブロックは、長期存続ブロックとして選択されてもよい。この場合に、長期存続ブロックに書込まれた永続データは、ブロックに残っている可能性が高いため、長期存続ブロックのプログラム／消去サイクルを減少する。長期存続ブロックを選択するための代替方法は、本発明から逸脱することなく使用することができる。

ステップ３０８では、データは、長期存続ブロックに書込まれる。本発明の１つ以上の実施形態において、データは、フラグとして（典型的には、フラグページの一部として）長期存続ブロックに記憶される。ＴＯＣエントリは、このフラグ（典型的には、ＴＯＣページの一部）に対応して生成され、長期存続ブロックに記憶される。

ステップ３０４に戻って、データが永続データではないと判断された場合、方法は、ステップ３１０に進むことができる。本発明の１つ以上の実施形態において、データが永続データではない場合、そのデータは、（たとえば、ＡＰＩを介して）短期存続データとして判明されるかまたは不明の存続期間を有する。本発明の１つ以上の実施形態によれば、そのようなデータは、長期存続ブロック内に記憶されている永続データとは別に、短期存続ブロックに記憶される。換言すれば、長期存続ブロック内の永続データと短期存続ブロック内のデータとは、重複しない。ステップ３１０では、短期存続ブロックが識別される。本発明の１つ以上の実施形態において、任意のフリーブロックまたは空きブロックが短期存続ブロックとして選択されてもよい。追加的にまたは代替的には、ブロックをウェアレベリングするために、そのプログラム／消去サイクルが一定の閾値未満であるブロックは、短期存続ブロックとして選択されてもよい。この場合に、短期存続ブロックに書込まれたデータは、消去される可能性が高いため、短期存続ブロックのプログラム／消去サイクルを増加する。短期存続ブロックを選択するための代替方法は、本発明から逸脱することなく使用することができる。

ステップ３１２では、データは、短期存続ブロックに書込まれる。本発明の１つ以上の実施形態において、データは、フラグとして（典型的にはフラグページの一部として）短期存続ブロックに記憶される。ＴＯＣエントリは、このフラグ（典型的には、ＴＯＣページの一部）に対応して生成され、短期存続ブロックに記憶される。

図４を参照して、図４は、本発明の１つ以上の実施形態に係る修正したガーベッジコレクション操作のフローチャートを示している。上述したように、修正したガベージコレクション操作は、記憶装置によって受信した書込みリクエストと並列に行うことができる。

ステップ４０２では、記憶装置からブロックを選択する。ステップ４０４では、ブロックからＴＯＣページを選択する。ステップ４０６では、ブロック内のフラグページからＴＯＣエントリを選択する。

ステップ４０８では、ＴＯＣエントリの情報を用いて、派生物理アドレスを生成する。本発明の１つ以上の実施形態において、フラグに対応する派生物理アドレスは、＜記憶モジュール、チャネル、チップイネーブル、ＬＵＮ、面、ブロック、ページＩＤ、バイト＞のようなｎタプルとして定義される。ｎタプルのうち、ページＩＤおよびバイトは、ＴＯＣエントリに記憶され、残りのデータは、ページＩＤおよびバイトから得ることができる。

ステップ４１０では、ＴＯＣエントリ内のｎタプル＜オブジェクトＩＤ、オフセットＩＤ＞を用いて、インメモリデータ構造から記憶物理アドレスを検索する。本発明の１つ以上の実施形態において、インメモリデータ構造は、ｎタプル（たとえば、＜オブジェクトＩＤは、オフセットＩＤ＞または＜オブジェクトのＩＤ、オフセットＩＤ、生成時間＞）とフラグの記憶物理アドレスとの間のマッピングを含む。

ステップ４１２では、派生物理アドレスが記憶物理アドレスと一致するか否かを判断する。本発明の１つ以上の実施形態において、ＴＯＣエントリに関連付けられたフラグが使用可能である（たとえば、最新であるまたは使用されている）場合、派生物理アドレスは、記憶物理アドレスと一致する。本発明の１つ以上の実施形態において、ＴＯＣエントリに関連付けられたフラグが使用不可である（たとえば、使わなくなったまたは古くなったまたは廃止された）場合、派生物理アドレスは、記憶物理アドレスと一致しない。派生物理アドレスが記憶物理アドレスと一致すると判断された場合、方法は、ステップ４１４に進み、そうでない場合、方法は、ステップ４１６に進むことができる。ステップ４１４では、ＴＯＣエントリに関連付けられたフラグは、使用可能にマークされる。たとえば、１つ以上のビットは、フラグに関連付けられ、このフラグを使用可能にマークしてもよい。

ステップ４１６では、ＴＯＣエントリに関連付けられたフラグは、使用不可にマークされる。たとえば、１つ以上のビットは、フラグに関連付けられ、このフラグを使用不可にマークしてもよい。

ステップ４１８では、ＴＯＣエントリがまだＴＯＣページに残っているか否かを判断する。本発明の１つ以上の実施形態において、ＴＯＣページは、１つ以上のＴＯＣエントリを含む。ＴＯＣエントリがまだＴＯＣページに残っていると判断された場合、方法は、上述のステップ４０６に戻り、そうでない場合、方法は、ステップ４２０に進むことができる。

ステップ４２０では、ＴＯＣページがまだブロックに残っているか否かを判断する。本発明の１つ以上の実施形態において、ブロックには、１つ以上のフラグページがあってもよい。ＴＯＣページがまだブロックに残っていると判断された場合、方法は、上述のステップ４０４に戻り、そうでない場合、方法は、ステップ４２２に進むことができる。ステップ４２２では、ブロック内のすべてのページが使用不可にマークされているか否かを判断する。ブロック内のすべてのページが使用不可にマークされていると判断された場合、方法は、ステップ４２４に進み、そうでない場合、方法は、ステップ４２８に進むことができる。ステップ４２４では、データを移行する必要がないため、ブロックは、消去される。

ステップ４２６では、ブロックがまだ固体メモリモジュールに残っているか否かを判断する。本発明の１つ以上の実施形態において、固体メモリモジュールは、１つ以上のブロックを含む。ブロックがまだ固体メモリモジュールに残っていると判断された場合、方法は、上述のステップ４０２に戻ることができる。

ステップ４２８では、ブロック内のすべてのページが使用可能にマークされているか否かを判断する。ブロック内のすべてのページが使用可能にマークされていると判断された場合、方法は、ステップ４３０に進み、そうでない場合、方法は、ステップ４３２に進むことができる。ステップ４３０では、ウェアレベリングする必要があるか否かを判断する。上述したように、ウェアレベリングは、固体メモリモジュールにおけるブロックに亘ってプログラム／消去サイクルの数のバランスを保つ。本発明の１つ以上の実施形態において、ブロックのプログラム／消去サイクル値が閾値未満になった場合に、ウェアレベリングする必要があり得る。換言すれば、より高いプログラム／消去サイクルを有する別のブロックのプログラム／消去サイクル値の増加を防ぐために、このプログラム／消去サイクル値が閾値未満のブロックには、プログラム／消去サイクルを行う必要がある。ウェアレベリングする必要があると判断された場合、方法は、ステップ４３２に進み、そうでない場合、方法は、ステップ４２６に戻ることができる。

ステップ４３２では、各使用可能ページが長期存続ブロックに移行される。本発明の１つ以上の実施形態において、各使用可能ページは、少なくとも１つのガベージコレクションサイクル以上に持続したため、永続データとして見なされる。本発明の１つ以上の実施形態において、任意のフリーブロックまたは空きブロックは、長期存続ブロックとして選択されてもよい。追加的にまたは代替的には、ブロックをウェアレベリングするために、そのプログラム／消去サイクルが一定の閾値を超えるブロックは、長期存続ブロックとして選択されてもよい。この場合、長期存続ブロックに書込まれた永続データは、ブロックに残されるべきであり、長期存続ブロックのプログラム／消去サイクルを減少する。長期存続ブロックを選択するための代替方法は、本発明から逸脱することなく使用することができる。本発明の１つ以上の実施形態において、データは、フラグとして（典型的には、フラグページの一部として）長期存続ブロックに書込まれる。ＴＯＣエントリは、このフラグ（典型的には、ＴＯＣページの一部）に対応して生成され、長期存続ブロックに記憶される。その後、方法は、上述のステップ４２４に戻ることができる。

図５Ａ〜６Ｂは、本発明の１つ以上の実施形態に係るさまざまな例を示している。これらの例は、本発明の範囲を限定しないことを意図している。図５Ａおよび５Ｂは、従来処理の書込みリクエストの一例および従来のガーベッジコレクション操作の一例をそれぞれ示している。図６Ａおよび６Ｂは各々、本発明の１つ以上の実施形態に係る修正したガーベッジコレクション操作によるデータ移行の一例を示している。性能比較の目的のために、図５Ａおよび図５Ｂの条件（たとえば、受信した書込みリクエストの数、書込みリクエストを受信した時間、指定ブロックの内容）は、図６Ａおよび６Ｂの条件と同一である。

図５Ａを参照して、図５Ａのシナリオは、ガベージコレクション操作の第１反復が、書込みリクエストＷ１、Ｗ２、Ｗ４、Ｗ５、Ｗ６、Ｗ７およびＷ８の受信と並行して、ブロック０、ブロック１、ブロック２およびブロック３に行われることである。Ｗ４およびＷ８に書込まれたデータが永続データである。ブロック４およびブロック５が空であり、書込みリクエストに応じて、任意の移行データまたはデータを書込むことができる。

まず、ガベージコレクション操作は、書込みリクエストＷ１、Ｗ２およびＷ３の受信と並行して、ブロック０に行われる。ブロック０内の各ページが使用不可にマークされているため、ブロック０は、消去される。書込みリクエストＷ１、Ｗ２およびＷ３に応じてデータを書込むために、ブロック４は、ランダムに選択される。また、Ｗ１、Ｗ２およびＷ３にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４に記憶される。

その後、ガベージコレクション操作は、ブロック１に実行される。ブロック１において、移行する必要のある唯一の使用可能ページは、ページＪである。ページＪを移行するために、ブロック４は、ランダムに選択される。また、ページＪに関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４に記憶される。ページＪの移行後、ブロック１は消去される。その後、書込みリクエストＷ４が受信される。Ｗ４に関連付けられたデータを書込むために、ブロック４はランダムに選択される。さらに、Ｗ４に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４に記憶される。

その後、ガベージコレクション操作は、書込みリクエストＷ５、Ｗ６およびＷ７の受信と並行して、ブロック２に行われる。ブロック２において、ページＱ、ＯおよびＮは、移行する必要がある使用可能ページである。ページＱおよびＯならびに書込みリクエストＷ５、Ｗ６およびＷ７に関連付けられたデータがランダムに選択され、ブロック５に移行される。さらに、ページＱ、Ｏ、書込みリクエストＷ５、Ｗ６およびＷ７にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５に記憶される。ページＮがランダムに選択され、ブロック４に移行される。ページＮに関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４に記憶される。ページＱ、ＯおよびＮの移行後、ブロック２は消去される。

最後に、ガベージコレクション操作は、書込みリクエストＷ８の受信と並行して、ブロック３に行われる。ブロック３において、すべてのページは、使用可能である。ブロック３のウェアレベリングをする必要がないため、ブロック３において移行を行わない。Ｗ８はランダムに選択され、ブロック５に書込まれる。さらに、Ｗ８に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５に記憶される。

よって、ガベージコレクション操作は、すべてのブロック（すなわち、ブロック０、ブロック１、ブロック２およびブロック３）の各々に亘って循環され、任意の使用可能ページをブロック４またはブロック５のいずれかに移行する。また、ガベージコレクション操作と並行して受信した書込みリクエストは、ブロック４またはブロック５のいずれかに割り当てられる。書込みリクエストの合計が８である場合、第１反復には、４回の移行を行う必要がある。

図５Ｂを参照して、図５Ｂのシナリオは、図５Ａで説明した第１反復の後に、ガベージコレクション操作の第２反復を行うことである。ガベージコレクション操作の第２反復は、書込みリクエストＷ９、Ｗ１０、Ｗ１１、Ｗ１２、Ｗ１３、Ｗ１４およびＷ１５の受信と並行して、ブロック２、ブロック３、ブロック４およびブロック５に行われる。Ｗ１３は、長期存続データまたは永続データである。ブロック０およびブロック１は、図５Ｂに示された第１反復の後に消去されるため、書込みリクエストに応じて、任意の移行データまたはデータを書込むことができる。

ガベージコレクション操作は、書込みリクエストＷ９、Ｗ１０、Ｗ１１およびＷ１２の受信と並行して、ブロック２から開始する。ブロック２は、第１反復に消去された（図５Ａを参照）ため、移行するページを含まない。書込みリクエストＷ９、Ｗ１０、Ｗ１１およびＷ１２に関連付けられたデータを書込むために、ブロック０は、ランダムに選択される。また、Ｗ９、Ｗ１０、Ｗ１１およびＷ１２にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０に記憶される。

その後、ガベージコレクション操作は、書込みリクエストＷ１３の受信と並行して、ブロック３に行われる。第１反復（図５Ａを参照）のときにブロック３にすべての使用可能ページが、使用可能に維持される。図５Ａにおいて説明したように、ブロック３のウェアレベリングをする必要がないため、ここでもブロック３において移行を行わない。Ｗ１３に関連付けられたデータを書込むために、ブロック０は、ランダムに選択される。さらに、Ｗ１３に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０に記憶される。

その後、ガベージコレクション操作は、書込みリクエストＷ１４およびＷ１５の受信と並行して、ブロック４に行われる。ブロック４において、ページＷ６およびＷ７は、移行する必要がある使用可能ページである。ページＷ６およびＷ７の書込みと並行してＷ１５に関連付けられたデータを書込むために、ブロック１は、ランダムに選択される。さらに、Ｗ１５、Ｗ１６およびＷ１７にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ７の一部としてブロック１に記憶されてる。書込みリクエストＷ１４に関連付けられたデータを書込むために、ブロック０は、ランダムに選択される。また、Ｗ１４に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０に記憶される。ページＷ６およびＷ７の移行後、ブロック４は消去される。

最後に、ガベージコレクション操作は、ブロック５に行われる。ブロック５において、すべてのページが使用可能である。ブロック５のウェアレベリングをする必要がないため、ブロック５において移行を行わない。

よって、ガベージコレクション操作は、すべてのブロック（すなわち、ブロック２、ブロック３、ブロック４およびブロック５）の各々に亘って循環され、任意の使用可能ページをブロック０またはブロック１のいずれかに移行する。また、修正したガベージコレクション操作と並行して受信した書込みリクエストは、ブロック０またはブロック１のいずれかに割り当てられる。書込みリクエストの合計が７である場合、第２反復には、８回の移行を行う必要がある。この２つの反復操作の間に、１５個のデータを書込むために、１２回の移行が行われる。よって、書込み量は、１書込み＋（１２移行／１５書込み）＝１．８として計算することができる。換言すれば、各書込みのために、０．８の追加書込みが必要とされる。

図６Ａを参照して、図６Ａのシナリオは、修正したガベージコレクション操作の第１反復が、書込みリクエストＷ１、Ｗ２、Ｗ４、Ｗ５、Ｗ６、Ｗ７およびＷ８の受信と並行して、ブロック０、ブロック１、ブロック２およびブロック３に行われることである。Ｗ４およびＷ８に書込まれたデータは、永続データである。ブロック４は、短期存続ブロックとして選択され、ブロック５は、長期存続ブロックとして選択される。

まず、修正したガーベッジコレクション操作は、書込みリクエストＷ１、Ｗ２およびＷ３の受信と並行して、ブロック０に行われる。ブロック０内の各ページが使用不可にマークされているため、ブロック０は消去される。Ｗ１、Ｗ２およびＷ３の存続期間は不明である。そのため、Ｗ１、Ｗ２およびＷ３は、ブロック４（短期存続ブロック）書込まれる。また、Ｗ１、Ｗ２およびＷ３にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４（短期存続ブロック）に記憶される。

その後、修正したガベージコレクション操作は、ブロック１に実行される。ブロック１において、移行する必要のある唯一の使用可能ページは、ページＪである。ページＪは、ガベージコレクション期間よりも長く存在または持続したため、永続データである可能性が高い。よって、ページＪは、ブロック５（長期存続ブロック）に移行される。また、ページＪに関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５（長期存続ブロック）に記憶される。ページＪの移行後、ブロック１は消去される。その後、書込みリクエストＷ４が受信される。Ｗ４は、アプリケーションプログラミングインターフェース（ＡＰＩ）を介して永続データを含むものとして伝達される。よって、Ｗ４は、持続期間未知の書込みリクエストのために保留されたブロック４（短期存続ブロック）ではなく、ブロック５（長期存続ブロック）に書込まれる。また、Ｗ４に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５（長期存続ブロック）に記憶される。

その後、修正したガーベッジコレクション操作は、書込みリクエストＷ５、Ｗ６およびＷ７の受信と並行して、ブロック２に行われる。ブロック２において、ページＱ、ＯおよびＮは、移行する必要がある使用可能ページである。同様に、修正したガーベッジコレクション操作を行うときに、ページＱ、ＯおよびＮは、使用可能であるため、永続データである可能性が高い。書込みリクエストＷ５、Ｗ６およびＷ７に関連付けられたデータの存続期間は、不明であるため、一時データである可能性が高い。Ｗ５、Ｗ６およびＷ７をブロック４（短期存続ブロック）に書込むことと並行して、ページＱ、ＯおよびＮをブロック５（長期存続ブロック）に移行する。また、Ｗ５、Ｗ６およびＷ７にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ４の一部としてブロック４（短期存続ブロック）に記憶される。同様に、ページＱ、ＯおよびＮにそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５（長期存続ブロック）に記憶される。ページＱ、ＯおよびＮの移行後、ブロック２は消去される。

最後に、修正したガーベッジコレクション操作は、書込みリクエストＷ８の受信と並行して、ブロック３に行われる。ブロック３において、すべてのページは使用可能である。ブロック３のウェアレベリングをする必要がないため、ブロック３において移行を行わない。書込みリクエストＷ４と同様に、Ｗ８は、ＡＰＩを介して永続データを含むものとして伝達される。よって、Ｗ８は、ブロック５（長期存続ブロック）に書込まれる。また、Ｗ８に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ５の一部としてブロック５（長期存続ブロック）に記憶される。

よって、修正したガベージコレクション操作は、すべてのブロック（すなわち、ブロック０、ブロック１、ブロック２およびブロック３）の各々に亘って循環され、任意の使用可能ページをブロック５（長期存続ブロック）に移行する。また、修正したガベージコレクション操作と並行して受信した書込みリクエストは、永続データを含む（たとえば、Ｗ４およびＷ８）ことが分かっている場合、ブロック５（長期存続ブロック）に割り当てられ、そうでない場合、ブロック４（短期存続ブロック）に割り当てられる。書込みリクエストの合計が８である場合、第１反復には、４回の移行を行う必要がある。

図６Ｂを参照して、図６Ｂのシナリオは、図６Ａで説明した第１反復の後に、修正したガベージコレクション操作の第２反復を行うことである。修正したガベージコレクション操作の第２反復は、書込みリクエストＷ９、Ｗ１０、Ｗ１１、Ｗ１２、Ｗ１３、Ｗ１４およびＷ１５の受信と並行して、ブロック２、ブロック３、ブロック４およびブロック５に行われる。Ｗ１３は、長期存続データまたは永続データである。第１反復に消去されたブロック０（図６Ａを参照）は、短期存続ブロックとして選択され、第１反復に消去されたブロック１（図６Ａを参照）は、長期存続ブロックとして選択される。

修正したガベージコレクション操作は、書込みリクエストＷ９、Ｗ１０、Ｗ１１およびＷ１２の受信と並行して、ブロック２から開始する。ブロック２は、第１反復に消去された（図５Ａを参照）ため、移行するページを含まない。Ｗ９、Ｗ１０、Ｗ１１およびＷ１２の存続期間は、未知である。よって、Ｗ９、Ｗ１０、Ｗ１１およびＷ１２は、ブロック０（短期存続ブロック）に書込まれる。また、Ｗ９、Ｗ１０、Ｗ１１およびＷ１２にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０（短期存続ブロック）に記憶される。

その後、修正したガーベッジコレクション操作は、書込みリクエストＷ１３の受信と並行して、ブロック３に行われる。第１反復（図６Ａを参照）のときにブロック３にすべての使用可能ページは、使用可能に維持される。図６Ａにおいて説明したように、ブロック３のウェアレベリングをする必要がないため、ここでもブロック３において移行を行わない。書込みリクエストＷ１３は、ＡＰＩを介して永続データを含むものとして伝達される。よって、Ｗ１３は、持続期間未知の書込みリクエストまたは短期存続書込みリクエストのために保留されたブロック０（短期存続ブロック）ではなく、ブロック１（長期存続ブロック）に書込まれる。また、Ｗ１３に関連付けられたＴＯＣエントリが生成され、ＴＯＣページ７の一部としてブロック１（長期存続ブロック）に記憶される。

その後、修正したガベージコレクション操作は、書込みリクエストＷ１４およびＷ１５の受信と並行して、ブロック４に行われる。Ｗ１４およびＷ１５の両方は、期間未知のデータを有するため、短期存続データである可能性が高い。ブロック４において、ページＷ６およびＷ７は、移行する必要がある使用可能ページである。ページＷ６およびＷ７は、ガベージコレクション操作を行うときに使用可能であるため、永続データである可能性が高い。よって、Ｗ１４およびＷ１５をブロック０（短期存続ブロック）に書込むことと並行して、ページＷ６およびＷ７がブロック１（長期存続ブロック）に移行される。また、Ｗ６およびＷ７にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ７の一部としてブロック１（長期存続ブロック）に記憶され、Ｗ１４およびＷ１５にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０（短期存続ブロック）に記憶される。Ｗ６およびＷ７の移行後、ブロック４は消去される。

最後に、修正したガーベッジコレクション操作は、ブロック５に行われる。ブロック５において、すべてのページは、使用可能である。ブロック５のウェアレベリングをする必要がないため、ブロック５において移行を行わない。

よって、修正したガーベッジコレクション操作は、すべてのブロック（すなわち、ブロック２、ブロック３、ブロック４、ブロック５）の各々に亘って循環され、任意の使用可能ページをブロック１（長期存続ブロック）に移行する。また、修正したガベージコレクション操作と並行して受信した書込みリクエストは、永続データを含む（たとえば、Ｗ１３）ことが分かっている場合、ブロック１（長期存続ブロック）に割り当てられ、そうでない場合、ブロック０（短期存続ブロック）に割り当てられる。

書込みリクエストの合計が７である場合、第２反復は、２回の移行を行う必要がある。この２つの反復操作の間に、１５個のデータを書込むために、６回の移行が行われる。よって、書込み量は、１書込み＋（６移行／１５書込み）＝１．４として計算することができる。換言すれば、各書込みのために、０．４の追加書込みが必要とされる。データの存続期間を無視して書込みリクエストを受信する従来のガベージコレクション操作により達成された１．８という書込み量に比べて、書込みリクエストを受信しながら存続期間に基づきデータをソートする修正したガーベッジコレクション操作によって達成された１．４という書込み量は、改良された。

本発明の１つ以上の実施形態は、記憶装置に記憶されたデータの存続期間に基づき、データをソートするためのシステムおよび方法を提供する。よって、すべての永続データとして分かったでデータは、長期存続ブロックに記憶され、短期存続データまたは存続期間未知のデータは、短期存続ブロックに記憶される。本発明のさまざまな実施形態に従ってデータを配置することにより、記憶装置は、ガベージコレクション操作の間にデータの移行を低減することによって所定の固体メモリモジュール（またはそのサブセット）の性能を向上させる。本発明の１つ以上の実施形態によれば、ガベージコレクション操作の間にデータ移行を低減することによって、記憶装置における書込み量を最小化することができる。書込み量を最小化することによって、各書込みに対してデータの移行が低減されたため、固体メモリモジュールのプログラム／消去サイクルの数を減少することができる。プログラム／消去サイクルの数が固体メモリモジュールの使用期間を低下させるため、書込み量の最小化は、性能を向上させることができる。

さらに、本発明の実施形態は、インメモリデータ構造の作成を可能にする。よって、記憶装置は、単一の検索ステップでデータにアクセスすることができる。換言すれば、記憶装置は、インメモリデータ構造を用いて、記憶装置内のデータの物理アドレスを直接確認することができる。この物理アドレス情報を用いて、記憶装置は、データに直接アクセスすることができ、データを得るために任意の中間メタデータ階層を詳しく検討する必要がない。

本発明の１つ以上の実施形態は、システム内の１つ以上のプロセッサによって実行される命令を用いて実現することができる。また、このような命令は、１つ以上の非一時的なコンピュータ可読媒体上に記憶されたコンピュータ可読命令に対応することができる。

本発明は、限定された数の実施形態に関連して説明したが、当業者であれば、この開示に基づき、本開示された発明の範囲から逸脱することなく、他の実施形態を考案できることを理解するであろう。したがって、本発明の範囲は、添付の特許請求の範囲のみによって限定される。

図２Ｆは、本発明の１つ以上の実施形態に係るＴＯＣエントリを示している。本発明の１つ以上の実施形態において、各ＴＯＣエントリ（２３０）は、フラグに対応するメタデータを含み、１つ以上の以下のフィールド、すなわち、（ｉ）記憶されているオブジェクトを識別するためのオブジェクトＩＤ（２３２）、（ｉｉ）ＴＯＣエントリに対応するフラグが固体メモリモジュールに書込まれた時間（たとえば、制御モジュール内に配置されたプロセッサのプロセッサクブロック値）を指定するための生成時間（２３４）、（ｉｉｉ）（オブジェクトＩＤによって識別される）オブジェクトの先頭に関連するオブジェクトの位置点を特定するためのオフセットＩＤ（２３６）、（ｉｖ）フラグのサイズを指定するためのフラグメントサイズ（２３８）、（ｖ）フラグが記憶されているブロック内のページを識別するためのページＩＤ（２４０）、および（ｖｉ）（ページＩＤによって識別された）ページ内のフラグの開始位置を特定するためのバイト（２４２）を含んでもよい。ＴＯＣエントリ（２３０）は、本発明から逸脱することなく、他のフィールド（２４４）を含んでもよい。

図５Ｂを参照して、図５Ｂのシナリオは、図５Ａで説明した第１反復の後に、ガベージコレクション操作の第２反復を行うことである。ガベージコレクション操作の第２反復は、書込みリクエストＷ９、Ｗ１０、Ｗ１１、Ｗ１２、Ｗ１３、Ｗ１４およびＷ１５の受信と並行して、ブロック２、ブロック３、ブロック４およびブロック５に行われる。Ｗ１３は、長期存続データまたは永続データである。ブロック０およびブロック１は、図５Ａに示された第１反復の後に消去されるため、書込みリクエストに応じて、任意の移行データまたはデータを書込むことができる。

修正したガベージコレクション操作は、書込みリクエストＷ９、Ｗ１０、Ｗ１１およびＷ１２の受信と並行して、ブロック２から開始する。ブロック２は、第１反復に消去された（図６Ａを参照）ため、移行するページを含まない。Ｗ９、Ｗ１０、Ｗ１１およびＷ１２の存続期間は、未知である。よって、Ｗ９、Ｗ１０、Ｗ１１およびＷ１２は、ブロック０（短期存続ブロック）に書込まれる。また、Ｗ９、Ｗ１０、Ｗ１１およびＷ１２にそれぞれ関連付けられたＴＯＣエントリが生成され、ＴＯＣページ６の一部としてブロック０（短期存続ブロック）に記憶される。

Claims (20)

1. プロセッサによって実行されると方法を実行する命令を含む非一時的なコンピュータ可読媒体であって、前記方法は、
   （ａ１）データを永続記憶域に書込む第１リクエストを受信するステップと、
   （ｂ１）前記第１リクエストに応じて、前記データを前記永続記憶域内の短期存続ブロックに書込むステップとを含み、前記データは、短期存続データであり、
   （ｃ１）修正したガーベッジコレクション操作を実行するステップを含み、
   前記修正したガーベッジコレクション操作は、
   第１ブロックから第１フラグページを選択するステップと、
   前記第１フラグページが使用可能であることを判断するステップと、
   前記第１フラグページが使用可能である判断に基づき、前記第１フラグページを前記永続記憶域内の長期存続ブロックに移行するステップとを含み、
   前記長期存続ブロックは、前記短期存続ブロックと別体であり、
   前記長期存続ブロックは、前記短期存続データを記憶しない、方法。
2. 前記方法はさらに、
   第２データを永続記憶域に書込む第２リクエストを受信するステップを含み、
   前記第２リクエストは、前記第２データが長期存続データであることを指定し、
   前記第２リクエストに応じて、前記第２データを前記永続記憶域内の前記長期存続ブロックに書込むステップを含む、請求項１に記載の非一時的なコンピュータ可読媒体。
3. 前記第１フラグページが使用可能であることを判断するステップは、
   前記第１フラグページに関連付けられた第１ＴＯＣエントリを用いて、第１派生物理アドレスを生成するステップと、
   第１オブジェクトＩＤおよび第１オフセットＩＤに基づき、第１記憶物理アドレスを選択するステップとを含み、前記第１オブジェクトＩＤおよび前記第１オフセットＩＤは、前記第１ＴＯＣエントリ内に位置し、
   前記第１派生物理アドレスが前記第１記憶物理アドレスと一致することに基づき、前記第１フラグページが使用可能であることを判断するするステップを含む、請求項１に記載の非一時的なコンピュータ可読媒体。
4. 前記第１記憶物理アドレスを選択するステップは、前記第１オブジェクトＩＤおよび前記第１オフセットＩＤを用いて、インメモリデータ構造に対する検索を実行して、前記第１記憶物理アドレスを識別するステップをさらに含む、請求項１に記載の前記非一時的なコンピュータ可読媒体。
5. 前記短期存続ブロックは、ＮＡＮＤブロックである、請求項１に記載の前記非一時的なコンピュータ可読媒体。
6. 前記永続記憶域は、固体メモリである、請求項１に記載の前記非一時的なコンピュータ可読媒体。
7. 前記修正したガーベッジコレクション操作は、
   前記永続記憶域から第２ブロックを選択するステップと、
   前記第２ブロックが複数の使用可能フラグページを含み、使用不可フラグページを含まないことを判断するステップと、
   前記複数の使用可能フラグページの各ページを第２長期存続ブロックに移行するステップとをさらに含む、請求項１に記載の前記非一時的なコンピュータ可読媒体。
8. 前記複数の使用可能フラグページの各ページの移行は、ウェアレベリングのために実行される、請求項７に記載の非一時的なコンピュータ可読媒体。
9. 前記修正したガーベッジコレクション操作の少なくとも一部は、（ａ１）および（ｂ１）からなる群から選択される少なくとも１つの操作と並行して実行される、請求項１に記載の非一時的なコンピュータ可読媒体。
10. データを管理するための方法であって
    （ａ２）データを永続記憶域に書込む第１リクエストを受信するステップと、
    （ｂ２）前記第１リクエストに応じて、前記データを前記永続記憶域内の短期存続ブロックに書込むステップとを含み、前記データは、短期存続データおよび存続期間未知のデータからなる群から選択され、
    （ｃ２）修正したガーベッジコレクション操作を実行するステップを含み、
    前記修正したガーベッジコレクション操作は、
    第１ブロックから第１フラグページを選択するステップと、
    前記第１フラグページが使用可能であることを判断するステップと、
    前記第１フラグページが使用可能である判断に基づき、前記第１フラグページを前記永続記憶域内の長期存続ブロックに移行するステップとを含み、
    前記長期存続ブロックは、前記短期存続ブロックと別体であり、
    前記長期存続ブロックは、前記短期存続データを記憶しない、方法。
11. 前記方法は、
    第２データを永続記憶域に書込む第２リクエストを受信するステップをさらに含み、
    前記第２リクエストは、前記第２データが長期存続データであることを指定し、
    前記第２リクエストに応じて、前記第２データを前記永続記憶域内の前記長期存続ブロックに書込むステップを含む、請求項１０に記載の方法。
12. 前記第１フラグページが使用可能であることを判断するステップは、
    前記第１フラグページに関連付けられた第１ＴＯＣエントリを用いて、第１派生物理アドレスを生成するステップと、
    第１オブジェクトＩＤおよび第１オフセットＩＤに基づき、第１記憶物理アドレスを選択するステップとを含み、前記第１オブジェクトＩＤおよび前記第１オフセットＩＤは、前記第１ＴＯＣエントリ内に位置し、
    前記第１派生物理アドレスが前記第１記憶物理アドレスと一致することに基づき、前記第１フラグページが使用可能であることを判断するするステップを含む、請求項１０に記載の方法。
13. 前記第１記憶物理アドレスを選択するステップは、前記第１オブジェクトＩＤおよび前記第１オフセットＩＤを用いて、インメモリデータ構造に対する検索を実行して、前記第１記憶物理アドレスを識別するステップをさらに含む、請求項１０に記載の方法。
14. 前記修正したガーベッジコレクション操作は、
    前記永続記憶域から第２ブロックを選択するステップと、
    前記第２ブロックが複数の使用可能フラグページを含み、使用不可フラグページを含まないことを判断するステップと、
    前記複数の使用可能フラグページの各ページを第２長期存続ブロックに移行するステップとをさらに含む、請求項１０に記載の方法。
15. 前記複数の使用可能フラグページの各ページの移行は、ウェアレベリングのために実行される、請求項１４に記載の方法。
16. 前記修正したガーベッジコレクション操作の少なくとも一部は、（ａ２）および（ｂ２）からなる群から選択される少なくとも１つの操作と並行して実行される、請求項１０に記載の方法。
17. 記憶装置であって、
    永続記憶域と、
    命令を含む非一時的なコンピュータ可読媒体と、
    前記命令を実行するように構成されたプロセッサとを含み、前記命令は、プロセッサによって実行されると方法を実行し、前記方法は、
    （ａ３）データを前記永続記憶域に書込む第１リクエストを受信するステップと、
    （ｂ３）前記第１リクエストに応じて、前記データを前記永続記憶域内の短期存続ブロックに書込むステップとを含み、前記データは、短期存続データおよび存続期間未知のデータからなる群から選択され、
    （ｃ３）修正したガーベッジコレクション操作を実行するステップを含み、
    前記修正したガーベッジコレクション操作は、
    第１ブロックから第１フラグページを選択するステップと、
    前記第１フラグページが使用可能であることを判断するステップと、
    前記第１フラグページが使用可能である判断に基づき、前記第１フラグページを前記永続記憶域内の長期存続ブロックに移行するステップとを含み、
    前記長期存続ブロックは、前記短期存続ブロックと別体であり、
    前記長期存続ブロックは、前記短期存続データを記憶せず、
    前記修正したガーベッジコレクション操作の少なくとも一部は、（ａ３）および（ｂ３）からなる群から選択される少なくとも１つの操作と並行して実行される、記憶装置。
18. 前記記憶装置は、インメモリデータ構造を記憶するように構成されたメモリをさらに含み、
    前記第１記憶物理アドレスを選択するステップは、前記第１オブジェクトＩＤおよび前記第１オフセットＩＤを用いて、前記インメモリデータ構造に対する検索を実行して、前記第１記憶物理アドレスを識別するステップをさらに含む、請求項１７に記載の記憶装置。
19. 前記永続記憶域は、複数の固体メモリモジュールを含む、請求項１７に記載の記憶装置。
20. 前記方法はさらに、
    第２データを永続記憶域に書込む第２リクエストを受信するステップを含み、
    前記第２リクエストは、前記第２データが長期存続データであることを指定し、
    前記第２リクエストに応じて、前記第２データを前記永続記憶域内の前記長期存続ブロックに書込むステップを含む、請求項１７に記載の記憶装置。
    

Images