(57)【要約】      （修正有）【課題】フラッシュメモリのフラッシングを改善するための方法およびシステムを提供する。【解決手段】フラッシュメモリへ書き込む要求を受信する工程３０４と、要求に関連付けられたデータをフラッシュメモリへ書き込む工程３０６と、書き込み要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別する工程３０８と、要求に対応する領域ビットマップのビットをダーティとしてマーキングする工程３１２と、ダーティブロックカウントを含むように、ポインタ管理部品を使用することにより、領域ビットマップへのポインタを更新する工程３１４とを含む。【選択図】図３
2017084338.tif 000002
【特許請求の範囲】
【請求項１】
フラッシュメモリのフラッシングを改善する方法であって
フラッシュメモリへ書き込む要求を受信する工程と、
前記要求に関連付けられたデータを前記フラッシュメモリへ書き込む工程と、
前記要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別する工程と、
前記要求に対応する前記領域ビットマップのビットをダーティとしてマーキングする工程と、
ダーティブロックカウントを含むように、ポインタ管理部品を使用することにより、前記領域ビットマップへの前記ポインタを更新する工程とを含む方法。
【請求項２】
ダーティブロックカウントを含むように前記領域ビットマップへの前記ポインタを更新する工程は、前記ダーティブロックカウントを含むように前記ポインタの１つまたは複数の上位ビットを更新する工程を含む、請求項１に記載の方法。
【請求項３】
前記ポインタは４８個の最下位ビットと１６個の上位ビットとを有するポインタを含み、前記ダーティブロックカウントは前記１６個の上位ビット内に格納される、請求項２に記載の方法。
【請求項４】
前記要求に対応する前記領域ビットマップのビットをダーティとしてマーキングする工程は、前記ポインタの最下位ビットの値を含むように前記ポインタの前記上位ビットを更新する工程と、前記領域ビットマップを識別するために前記更新ポインタを使用する工程とを含む、請求項２に記載の方法。
【請求項５】
前記ポインタはポインタのアレイのうちの１つを含み、前記ポインタのアレイは前記ポインタのそれぞれの中のダーティブロックカウントに従って順序付けられる、請求項１に記載の方法。
【請求項６】
前記順序付けられたポインタのアレイを使用することにより前記フラッシュメモリの複数の領域のうちの最もダーティな領域を識別する工程と、前記最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込む工程とをさらに含む請求項５に記載の方法。
【請求項７】
１つまたは複数のブロックを従来のストレージへ書き込む工程は１つまたは複数の因子の検出によりトリガされる、請求項６に記載の方法。
【請求項８】
前記１つまたは複数の因子は、到達されるダーティブロックの規定閾値、ＣＰＵ利用率のレベル、ネットワーク利用率のレベル、従来のストレージの入力／出力のレベル、キャッシュからの１つまたは複数のブロックの時間経過、ユーザ指定優先度のうちの少なくとも１つを含む、請求項７に記載の方法。
【請求項９】
前記最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込む工程は、従来のストレージへ書き込まれるデータに関連付けられた論理ブロックアドレスを識別するために、領域ビットマップの基底アドレスと前記領域ビットマップのビットに関連付けられたオフセットとを使用する工程を含む、請求項６に記載の方法。
【請求項１０】
第１の領域に関連付けられた１つまたは複数のブロックを書き込んだ後に、第２の最もダーティな領域に関連付けられたポインタの前記アレイ内の第２のポインタを識別する工程をさらに含む請求項６に記載の方法。
【請求項１１】
第１のポインタに関連付けられた１つまたは複数のブロックが従来のストレージへ書き込まれると、前記第２のポインタのオフセットは前記アレイの開始点になる、請求項１０に記載の方法。
【請求項１２】
コンピュータ上で実行可能な一系列の命令からなり、フラッシュメモリのフラッシングを改善する方法を行うコンピュータプログラム製品であって、
フラッシュメモリへ書き込む要求を受信する工程と、
前記要求に関連付けられたデータを前記フラッシュメモリへ書き込む工程と、
前記要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別する工程と、
前記要求に対応する前記領域ビットマップのビットをダーティとしてマーキングする工程と、
ダーティブロックカウントを含むように前記ポインタを前記領域ビットマップへ更新する工程とを実施するコンピュータプログラム製品。
【請求項１３】
フラッシュメモリのフラッシングを改善するためのシステムであり、記憶媒体装置と、前記記憶媒体装置に関連付けられたＰＣＩｅベース装置コントローラとを含むシステムであって、前記ＰＣＩｅベース装置コントローラは、
フラッシュメモリへ書き込む要求を受信し、
前記要求に関連付けられたデータを前記フラッシュメモリへ書き込み、
前記要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別し、
前記要求に対応する前記領域ビットマップのビットをダーティとしてマーキングし、
ダーティブロックカウントを含むように前記ポインタを前記領域ビットマップへ更新するように構成される、システム。
【請求項１４】
ダーティブロックカウントを含むように前記領域ビットマップへの前記ポインタを更新する工程は、前記ダーティブロックカウントを含むように前記ポインタの１つまたは複数の上位ビットを更新する工程を含む、請求項１３に記載のシステム。
【請求項１５】
前記ポインタは４８個の最下位ビットと１６個の上位ビットとを有するポインタを含み、前記ダーティブロックカウントは前記１６個の上位ビット内に格納される、請求項１４に記載のシステム。
【請求項１６】
前記要求に対応する前記領域ビットマップのビットをダーティとしてマーキングする工程は、前記ポインタの最下位ビットの値を含むように前記ポインタの上位ビットを更新する工程と、前記領域ビットマップを識別するために前記更新ポインタを使用する工程とを含む、請求項１４に記載のシステム。
【請求項１７】
前記ポインタはポインタのアレイのうちの１つを含み、前記ポインタのアレイは前記ポインタのそれぞれの中のダーティブロックカウントに従って順序付けられる、請求項１３に記載のシステム。
【請求項１８】
前記ＰＣＩｅベース装置コントローラはさらに、前記順序付けられたポインタのアレイを使用することにより前記フラッシュメモリの複数の領域のうちの最もダーティな領域を識別し、前記最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込むように構成される、請求項１７に記載のシステム。
【請求項１９】
１つまたは複数のブロックを従来のストレージへ書き込む工程は１つまたは複数の因子の検出によりトリガされる、請求項１８に記載のシステム。
【請求項２０】
前記１つまたは複数の因子は、到達されるダーティブロックの規定閾値、ＣＰＵ利用率のレベル、ネットワーク利用率のレベル、従来のストレージの入力／出力のレベル、キャッシュからの１つまたは複数のブロックの時間経過、ユーザ指定優先度のうちの少なくとも１つを含む、請求項１９に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
固体ドライブ（ＳＳＤ）から従来の記憶装置（例えばハードディスクドライブ）に書き込む際に最良の性能を得るために、書き込みは、それらの論理ブロックアドレス（ＬＢＡ）に従って連続的に順序付けられ得る。書き込み操作中のアドレスの連続的実行が長ければ長いほど、性能はより良好になる。しかし、ＳＳＤから従来のストレージへの書き込みを要求するアドレスの実行の長さは、ＳＳＤストレージのどの部分が従来のストレージへ未だ委託されていない修正を有するか（例えばダーティブロック）に依存し得る。ストレージへの書き込み（例えばフラッシング）を要求するブロックを効率的やり方で識別するためにＳＳＤ（例えばフラッシュメモリを含む）内のこのようなダーティブロックを追跡することは挑戦的な課題である。
【発明の概要】
【課題を解決するための手段】
【０００２】
フラッシュメモリのフラッシングを改善するための技術が開示される。いくつかの実施形態では、フラッシュメモリのフラッシングを改善する方法としていくつかの技術が実現され得る。本方法は、フラッシュメモリへ書き込む要求を受信する工程と、要求に関連付けられたデータをフラッシュメモリへ書き込む工程と、上記要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別する工程と、要求に対応する領域ビットマップのビットをダーティとしてマーキングする工程と、ダーティブロックカウントを含むように、ポインタ管理部品を使用することにより、領域ビットマップへのポインタを更新する工程とを含む。
【０００３】
この実施形態の追加の態様によると、ダーティブロックカウントを含むように領域ビットマップへのポインタを更新する工程は、ダーティブロックカウントを含むようにポインタの１つまたは複数の上位ビットを更新する工程を含み得る。
【０００４】
この実施形態の別の態様によると、ポインタは、４８個の最下位ビットと１６個の上位ビットとを有するポインタを含み得、ダーティブロックカウントは１６個の上位ビット内に格納される。
【０００５】
この実施形態の他の態様によると、要求に対応する領域ビットマップのビットをダーティとしてマーキングする工程は、ポインタの最下位ビットの値を含むようにポインタの上位ビットを更新する工程と、領域ビットマップを識別するために更新ポインタを使用する工程とを含み得る。
【０００６】
この実施形態の追加の態様によると、ポインタは、ポインタのアレイのうちの１つを含み得、ポインタのアレイはポインタのそれぞれの中のダーティブロックカウントに従って順序付けられる。
【０００７】
この実施形態の別の態様によると、本技術は、順序付けられたポインタのアレイを使用することによりフラッシュメモリの複数の領域のうちの最もダーティな領域を識別する工程と、最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込む工程とを含み得る。
【０００８】
この実施形態の他の態様によると、１つまたは複数のブロックを従来のストレージへ書き込む工程は１つまたは複数の因子の検出によりトリガされ得る。
【０００９】
この実施形態の追加の態様によると、１つまたは複数の因子は、到達されるダーティブロックの規定閾値、ＣＰＵ利用率のレベル、ネットワーク利用率のレベル、従来のストレージの入力／出力のレベル、キャッシュからの１つまたは複数のブロックの時間経過、ユーザ指定優先度のうちの少なくとも１つを含み得る。
【００１０】
この実施形態の別の態様によると、最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込む工程は、従来のストレージへ書き込まれるデータに関連付けられた論理ブロックアドレスを識別するために、領域ビットマップの基底アドレスと領域ビットマップのビットに関連付けられたオフセットとを使用し得る。
【００１１】
この実施形態の追加の態様によると、本技術は、第１の領域に関連付けられた１つまたは複数のブロックを書き込んだ後に、第２の最もダーティな領域に関連付けられたポインタのアレイ内の第２のポインタを識別する工程を含み得る。
【００１２】
この実施形態の別の態様によると、第１のポインタに関連付けられた１つまたは複数のブロックが従来のストレージへ書き込まれると、第２のポインタのオフセットがアレイの開始点となる。
【００１３】
他の実施形態では、本技術は、コンピュータ上で実行可能な一系列の命令を含む非一時的コンピュータプログラム製品として実現され得る。非一時的コンピュータプログラム製品はフラッシュメモリのフラッシングを改善する方法を行い得る。このコンピュータプログラムは、フラッシュメモリへ書き込む要求を受信する工程と、要求に関連付けられたデータをフラッシュメモリへ書き込む工程と、要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別する工程と、要求に対応する領域ビットマップのビットをダーティとしてマーキングする工程と、ダーティブロックカウントを含むように領域ビットマップへのポインタを更新する工程とを実施し得る。
【００１４】
さらに他の実施形態では、本技術はフラッシュメモリのフラッシングを改善するためのシステムとして実現され得る。本システムは、記憶媒体装置と、記憶媒体装置に関連付けられたＰＣＩｅベース装置コントローラとを含み得る。ＰＣＩｅベース装置コントローラは、フラッシュメモリへ書き込む要求を受信し、要求をフラッシュメモリへ書き込み、要求に対する書き込み領域に対応する領域ビットマップへのポインタを識別し、要求に対応する領域ビットマップのビットをダーティとしてマーキングし、そしてダーティブロックカウントを含むように領域ビットマップへのポインタを更新するように構成され得る。
【００１５】
この実施形態の追加の態様によると、ダーティブロックカウントを含むように領域ビットマップへのポインタを更新する工程は、ダーティブロックカウントを含むようにポインタの１つまたは複数の上位ビットを更新する工程を含み得る。
【００１６】
この実施形態の別の態様によると、ポインタは４８個の最下位ビットと１６個の上位ビットとを有するポインタを含み得、ダーティブロックカウントは１６個の上位ビット内に格納される。
【００１７】
この実施形態の他の態様によると、要求に対応する領域ビットマップのビットをダーティとしてマーキングする工程は、ポインタの最下位ビットの値を含むようにポインタの上位ビットを更新する工程と、領域ビットマップを識別するために更新ポインタを使用する工程とを含み得る。
【００１８】
この実施形態の追加の態様によると、ポインタはポインタのアレイのうちの１つを含み得、ポインタのアレイはポインタのそれぞれの中のダーティブロックカウントに従って順序付けられる。
【００１９】
この実施形態の別の態様によると、ＰＣＩｅベース装置コントローラはさらに、順序付けられたポインタのアレイを使用することによりフラッシュメモリの複数の領域のうちの最もダーティな領域を識別し、そして最もダーティな領域の１つまたは複数のブロックを従来のストレージへ書き込むように構成され得る。
【００２０】
この実施形態の他の態様によると、１つまたは複数のブロックを従来のストレージへ書き込む工程は１つまたは複数の因子の検出によりトリガされ得る。
【００２１】
この実施形態の追加の態様によると、１つまたは複数の因子は、到達されるダーティブロックの規定閾値、ＣＰＵ利用率のレベル、ネットワーク利用率のレベル、従来のストレージの入力／出力のレベル、キャッシュからの１つまたは複数のブロックの時間経過、ユーザ指定優先度のうちの少なくとも１つを含み得る。
【００２２】
次に、本開示について、添付図面に示すその例示的実施形態を参照してさらに詳細に説明する。本開示は例示的実施形態を参照して以下に説明されるが、本開示はそれに限定されないということを理解すべきである。本明細書の教示へアクセスする当業者は、本明細書で説明する本開示の範囲内でありかつ本開示が著しく実用的であり得る他の分野の使用だけでなく追加の実装、修正、実施形態を認識することになる。
【００２３】
次に、本開示のより完全な理解を容易にするために添付図面を参照するが、ここでは同様な要素は同様な参照符号で参照される。これらの添付図面は本開示を制限するものとして解釈されるべきでなく、単なる例示であるように意図されている。
【図面の簡単な説明】
【００２４】
【図１】本開示の一実施形態による、ホスト装置と通信する複数のＰＣＩｅ装置を描写するブロック図である。
【図２Ａ】本開示の一実施形態による、フラッシュメモリのフラッシングを改善するためのモジュールを描写するブロック図である。
【図２Ｂ】本開示の一実施形態による、書き込まれるべきブロックを格納するためにビットマップを使用する方法を示すフローチャートを描写する。
【図２Ｃ】本開示の一実施形態による、最もダーティな領域を最初に書き戻す方法を示すフローチャートを描写する。
【図２Ｄ】本開示の一実施形態による、領域をソートする方法を示すフローチャートを描写する。
【図３】本開示の一実施形態による、フラッシュメモリのフラッシングを改善する方法を示すフローチャートを描写する。
【図４】本開示の一実施形態による、フラッシュメモリのフラッシングを改善する方法を示すフローチャートを描写する。
【発明を実施するための形態】
【００２５】
本開示は、ＳＳＤ（例えばフラッシュメモリを含む）から従来のストレージ（例えばディスク、テープなど）への修正データのフラッシングを改善するための技術に関する。いくつかの実施形態によると、順不同に書き込まれた一組のデータが提供されると、書き込み要求は最初にラングムアクセスフレンドリ固体ストレージ中に格納される。これらの書き込み要求が、論理ブロックアドレスの連続的実行の改善された尤度でもって、順序付けられたやり方で従来のストレージへ書き戻され得るようにするデータ構造、アルゴリズム、および／または回路構成（例えば（マイクロ）プロセッサ、論理ゲート、スイッチ、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルロジック制御装置（例えばＦＰＧＡ）、埋め込みマイクロコントローラ）が提供され得る。
【００２６】
次に添付図面を参照すると、図１は、本開示の一実施形態による、ホスト装置と通信するＰＣＩｅ装置を描写するブロック図である。図１は、ホストシステム１０２、ホストＣＰＵ１０４、ＰＣＩエクスプレスルートコンプレックス１０６など多くの計算技術を含む。スイッチ１０８は、ターゲット１１０、１１６、１２２などの複数のターゲット（例えばＮＶＭｅベースターゲットなどのＰＣＩｅ装置）をＰＣＩエクスプレスルートコンプレックス１０６を介しホストシステム１０２へ通信可能に結合し得る。
【００２７】
ターゲット１１０はコントローラ１１２（例えばＮＶＭｅコントローラ）と非揮発性ストレージ１１４を含み得る。ターゲット１１６はコントローラ１１８（例えばＮＶＭｅコントローラ）と非揮発性ストレージ１２０を含み得る。ターゲット１２２はコントローラ１２４（例えばＮＶＭｅコントローラ）と非揮発性ストレージ１２６を含み得る。
【００２８】
メモリベース資源はメモリインターフェースを介しホストシステム１０２へアクセス可能であり得る（例えば、ダブルデータレート型３同期ダイナミックランダムアクセスメモリ（ＤＤＲ３  ＳＤＲＡＭ））。メモリは、限定しないが固体メモリなどの任意の好適な形式を採り得る（例えばフラッシュメモリ、または固体ドライブ（ＳＳＤ））、光メモリ、および磁気メモリ）。
【００２９】
いくつかの実施形態によると、ＰＣＩｅ以外のインターフェース標準規格が、限定しないが、シリアルアドバンストテクノロジーアタッチメント（ＳＡＴＡ）、アドバンストテクノロジーアタッチメント（ＡＴＡ）、スモールコンピュータシステムインターフェース（ＳＣＳＩ）、拡張ＰＣＩ（ＰＣＩ−Ｘ）、ファイバチャンネル、シリアルアタッチドＳＣＳＩ（ＳＡＳ）、セキュアデジタル（ＳＤ）、埋め込みマルチメディアカード（ＥＭＭＣ）、およびユニバーサルフラッシュストレージ（ＵＦＳ）を含む１つまたは複数の部分に使用され得る。
【００３０】
ホストシステム１０２は、限定しないが、企業サーバ、データベースホスト、ワークステーション、パーソナルコンピュータ、携帯電話、ゲーム装置、個人用デジタル情報処理端末（ＰＤＡ）、電子メール／テキストメッセージ装置、デジタルカメラ、デジタル媒体（例えばＭＰ３）プレーヤ、ＧＰＳナビゲーション装置、ＴＶシステムなど任意の好適な形式を採り得る。
【００３１】
ホストシステム１０２とターゲット装置は追加の部品（図面を簡単にするために図１において図示しない）を含み得る。また、いくつかの実施形態では、示された部品のすべてが存在するとは限らない。さらに、様々なコントローラ、ブロック、インターフェースが任意の好適なやり方で実装され得る。例えば、コントローラは、マイクロプロセッサまたはプロセッサ、（マイクロ）プロセッサにより実行可能なコンピュータ可読プログラムコード（例えばソフトウェアまたはファームウェア）を格納するコンピュータ可読媒体、論理ゲート、スイッチ、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルロジック制御装置（例えばＦＰＧＡ）、埋め込みマイクロコントローラのうちの１つまたは複数の形式を採り得る。
【００３２】
図２Ａは、本開示の一実施形態による、フラッシュメモリのフラッシングを改善するためのモジュールを描写する。部品は、ハードウェア（例えば専用回路構成）、ファームウェア、ソフトウェアまたはこれらの組み合わせであり得る。
【００３３】
以下の記述は、１つまたは複数の部品を含み得るバックアップおよび回復のためのシステムおよび方法のネットワーク要素、コンピュータ、および／または部品を説明する。本明細書で使用されるように、用語「部品」は、計算ソフトウェア、ファームウェア、ハードウェア、および／またはそれらの様々な組み合わせを指すように理解され得る。しかし、部品は、ハードウェア、ファームウェア上に実装されないまたはプロセッサ可読記録可能記憶媒体上に記録されないソフトウェアとして解釈されてはならない（すなわち、部品それ自体はソフトウェアではない）。部品は例示的であるということに留意されたい。部品は、様々な用途を支援するために組み合わせられ、一体化され、分離されおよび／または複製され得る。また、特定部品において行われるものとして本明細書において説明される機能は、１つまたは複数の他の部品において行われ得る、および／または特定部品において行われる機能の代わりにまたはそれに加えて１つまたは複数の他の装置により行われ得る。さらに、部品は、複数の装置および／またはローカルなまたは互いに離れた他の部品全体にわたって実装され得る。加えて、部品は、１つの装置から移動され、別の装置へ加えられ、および／または両方の装置に含まれ得る。いくつかの実施形態では、１つまたは複数の部品は、ＳＳＤコントローラ、ホストシステムおよび／またはＳＳＤ最適化ソフトウェアの一部として実装され得る。図２Ａに示すように、ＳＳＤフラッシュ改善部品２１０は、書き込み監視部品２１２、ダーティ領域識別部品２１４、アレイ管理部品２１６、エラーログ記録および報告部品２１８を含み得る。
【００３４】
書き込み監視部品２１２は、従来のストレージ（例えばダーティメモリ）へ未だ書き込まれていないＳＳＤ（例えばフラッシュメモリ）へ書き込まれるデータを追跡し得る。変更されたブロックを識別するために補助ストレージ（例えばディスク）と比較するために各ブロックまたは他の記憶ユニットを経由することは、資源集約的であり得るおよび／または時間がかかり得る。いくつかの実施形態では、ＳＳＤストレージの一部が修正されると、書き込み監視部品２１２は、１つまたは複数のデータ構造および／または回路構成を使用することにより書き込みを追跡し得る。例えば、いくつかの実施形態では、書き込み監視部品２１２は領域毎に書き込まれるブロックを格納するためにビットマップを使用し得る。従来の補助記憶装置は固定サイズ領域に分割され得る。例えば、各領域は３２７６８個のブロックを含み得、各ブロックはサイズが４キロバイトであり得る。
【００３５】
図２Ｂは、書き込まれるべきブロックを格納するためにビットマップを使用する例示的方法２２０を示すフローチャートを描写する。いくつかの実施形態によると、システムが開始されると、アレイ管理部品２１６は領域毎に１つずつポインタのアレイを割り振り得（２２２）、アレイをヌル値へ初期化し得る（２２４）。領域が最初に書き込まれると、４キロバイトページのメモリが割り振られ得（２２６）、当該領域のポインタは新たに割り振られたメモリページを指し示すように更新され得る（２２８）。
【００３６】
一例では、４キロバイトのメモリページはメモリの３２７６８の個々のビットを含む。このメモリはビットマップとして使用され得る。ブロックが一時的ランダムアクセスストレージへ最初に書き込まれると、その論理ブロックアドレスは最初にマスクされ、適切な領域を判断する（２３０）ためにシフトされ得る。次に、割り振り後、ポインタは、領域のビットマップを定位する（２３２）ために書き込み監視部品２１２により利用され得る。例えば、ＳＳＤ記憶場所が割り振られると、それは、ビットマップ、ハッシュマップの位置、またはＳＳＤストレージ内のどのビットが従来のストレージへ未だ書き込まれていないかの指標を格納する他のデータ構造を示すポインタ、値または参照子に関連付けられ得る。一時的ランダムアクセスストレージへ書き込まれるブロックの論理ブロックアドレスの下位ビット（例えば最下位ビット）は、次に、対応ビットを定位するためにビットマップ中へのオフセットとして使用され得る。いくつかの実施形態では、これは、ブロックを「ダーティ」としてマーキングするためにいかなる探索も必要としなく一定時間操作だけを必要とする（例えば、従来のストレージへの将来の書き戻しを必要とする）（すなわち、操作を完了するためにかかる時間は入力のサイズと無関係であり得る）。
【００３７】
ダーティ領域識別部品２１４は、ＳＳＤのダーティ部分をいつ従来のストレージへフラッシュすべきかおよび／またはどの部分がどの順序でフラッシュされなければならないかを判断し得る。いくつかの実施形態では、従来のストレージへの書き込みの長い連続実行を有することが望ましいかもしれない。これを達成するために、従来のストレージへの書き込みはＳＳＤの１つまたは複数の領域が十分にダーティになる（例えば、かなりの数の連続ダーティブロックを含む）と行われ得る。１つまたは複数の領域が十分にダーティとなったかの判断は、１つまたは複数の因子（例えば領域内のダーティブロックの数、百分率または量の他の指標）に依存してもよいし、構成可能であってもよい。領域がフラッシングに対して十分にダーティである尤度を改善するために、ダーティ領域識別部品２１４は、最初に書き込むべき最もダーティな領域を識別し得る。
【００３８】
図２Ｃは、本開示の一実施形態による、最もダーティな領域を最初に書き戻す例示的方法２３４を示すフローチャートを描写する。従来のストレージへデータを書き戻す時間になると、一組の領域がソートされ（２３６）、最もダーティな（書き込みを必要とするデータにより最も密集された）領域がダーティ領域識別部品２１４により選択される（２３８）。いくつかの実施形態によると、アレイ管理部品２１６が領域をソートし得る。
【００３９】
対応ビットマップにアクセスするために当該領域のポインタが追随され得る（２４０）。次に、ビットマップは前方へ横断され得る（２４２）。領域の基底論理ブロックアドレスは、書き戻しを要求する論理ブロックアドレスを形成するためにマップ内の各ビットのオフセットと組み合わせられ得る（２４４）。
【００４０】
ソーティング領域は伝統的に、最もダーティな領域を識別するために各ビットマップ内に設定されたビットのすべてをカウントすることを要求し得る。これは、設定されたビットの数を判断するためにビットマップの大きなＣＰＵ集約的走査を使用し得るので禁止的であり得る。いくつかの実施形態では、書き込み監視部品２１２は、領域内のダーティストレージの一部のカウント（例えば４キロバイトビットマップブロック内に設定されたビッのト数）を示すために領域のダーティビットマップへのポインタ内の空間を使用し得る。例えば、ｘ８６＿６４アーキテクチャでは、６４ビットのポインタのうち４８ビットだけが重要であり得る。上位ビットは４８個の下位ビット（例えば最下位ビット）から符号拡張され得る。これは、ビットが上位１６ビットに関して同じであり得るということを意味し、失われれば、この値はビット４７から得られる可能性がある。いくつかの実施形態では、書き込み監視部品２１２は、ポインタのアレイ内のポインタの上位１６ビット内のビットマップブロック内に設定されたビットのカウントを格納し得る。アレイ管理部品２１６は、第１のポインタが最もダーティとなるようにアレイをソートするために、アレイの各ポインタ内のビットカウント、またはポインタの他のデータ構造（または他の参照子構造）を使用し得る。
【００４１】
図２Ｄは、本開示の一実施形態による、領域をソートするための例示的方法２４６を示すフローチャートを描写する。アレイ管理部品２１６は、領域当たり１つのポインタを含む主ポインタアレイ中に４バイトオフセットの小型ソートアレイを維持し得る（２４８）。従来のストレージへいくつかの書き戻しを行う時間になると、アレイはビットマップブロックへのポインタに全く従うことなくソートされ得る（２５０）。これは、書き戻すべき最もダーティな領域を発見するオーバーヘッドを大幅に低減し得る。
【００４２】
ダーティビットカウントを格納するように修正されたポインタに従うために、ポインタは回復され得る（２５２）。いくつかの実施形態では、ポインタは、最下位ビットを上位ビットへ符号拡張することにより回復され得る（例えば、ビット４７からビット４８〜６３へ値を複製することにより）。ビットマップ内に設定されたビットのカウントが調整される（２５４）と、新しいカウントが上位ビット２５６中に格納され得る。
【００４３】
いくつかの実施形態では、ダーティ領域識別部品２１４は複数の領域をランキングし得、１つまたは複数の追加の因子が、領域内のダーティブロックの数、百分率または量の他の指標に加えて評価され得る。例えば、ＳＳＤ領域内のデータの年令が考慮され得る。他の因子としては、ラストインファーストアウト（ＬＩＦＯ）、ファーストインファーストアウト（ＦＩＦＯ）、またはどの領域が書き込まれるべきかを判断するための他の技術などのアルゴリズムが挙げられ得る。例えば、第１の領域は第２の領域よりダーティであるが第１の領域が依然として重要な入出力（Ｉ／Ｏ）トラフィックを受信していれば、いくつかの実施形態では第２の領域が最初に書き込まれ得る。
【００４４】
アレイ管理部品２１６は、ダーティＳＳＤ領域を示すビットマップへの参照子を含むアレイまたは他のデータ構造を維持し得る。いくつかのソーティングアルゴリズムは、アレイが既にほぼソートされていればより良好に行い得る。上述の１つまたは複数の実施形態は、一組の領域をソートし、最もダーティな領域を採り、それを完全にクリーンにし、アレイの残りをソート済み状態のままにし得る。これは、ダーティ領域識別部品を次の最もダーティな領域（等しくダーティでさえあり得る）上へ移動させ得るのでダーティ領域を従来のストレージへフラッシュするためにうまく働き得る。しかし、先頭に１つのミスソートされたブロックを有するほぼソートされたアレイは、病的な振る舞いを呈示し得、アレイの端の新しい適切な位置へ移動するために多くのＣＰＵ演算を必要とし得る。
【００４５】
これに対処するために、アレイ管理部品２１６は、ソート済みアレイを先頭と端とが可動な円形状アレイとして扱い得る。当初、アレイのソート済み開始点はオフセット０にあり得、端は、アレイを含むメモリブロックの最終要素であり得る。最も位の高いランキング領域がクリーンにされると、それは、オフセット０に依然として存在し得るが、誤ってソートされ得る。アレイを従来通りに再ソートし、データを移動させる代わりに、アレイ管理部品２１６は、円形状アレイ全体が１だけシフトされるように、ソート済み開始および端オフセットを調整し得る。ソート済み開始オフセットは１となり得、今やアレイの零番目の要素はアレイの最終要素であり得る。このようにして、零個のダーティブロックへ縮小された領域は、そうでなければソートされるアレイを残して、一定時間操作中にアレイの端の適切な位置へ再ソートされる。
【００４６】
エラーログ記録および報告部品２１８は、エラーを捕捉し、書き込み要求の監視、ダーティ領域の識別、および／またはダーティ領域（例えばポインタのアレイ）を追跡するデータ構造の管理に関連付けられたエラーをログ記録し得る。いくつかの実施形態では、エラーログ記録および報告部品２１８はエラーの通知を提供し得る。
【００４７】
図３は、本開示の一実施形態による、フラッシュメモリのフラッシングを改善する方法を示すフローチャートを描写する。但し、方法３００は例示的に過ぎない。方法３００は、例えば段階を追加、変更、除去、または再配置することにより変更され得る。段階３０２において、方法は開始し得る。
【００４８】
段階３０４において、フラッシュメモリ書き込み要求が受信され得る。段階３０６において、書き込み要求はフラッシュメモリ領域へ書き込まれ得る。ＳＳＤの複数の領域に対して、ポインタのアレイは領域毎に１つ割り振られ得、各アレイはヌル値へ初期化され得る。
【００４９】
段階３０８において、領域が最初に書き込まれると、メモリのページが割り振られ得、その領域のポインタは、新たに割り振られたメモリページを指し示すように更新され得る。
【００５０】
段階３１０では、ポインタが既に割り振られており、ポインタの上位ビットがダーティブロックのカウントを格納するように上書きされていれば、上位ビットが回復され得る。例えば、ｘ８６＿６４アーキテクチャでは、６４ビットのポインタのうち４８ビットだけが重要であり得る。上位ビットは４８個の下位ビット（例えば最下位ビット）から符号拡張され得る。これは、ビットが上位１６ビットに関して同じであり得るということを意味し、失われれば、この値はビット４７から得られる可能性がある。
【００５１】
段階３１２では、割り振り後、領域のビットマップを発見するためにポインタが利用され得る。一時的ランダムアクセスストレージへ書き込まれるブロックの論理ブロックアドレスの下位ビットは、次に、対応ビットを定位するためにビットマップ中へのオフセットとして使用され得る。いくつかの実施形態では、これは、ブロックを「ダーティ」としてマーキングするためにいかなる探索も必要としなく一定時間操作だけを必要とする（例えば、従来のストレージへの将来の書き戻しを必要とする）。
【００５２】
段階３１４では、領域のダーティビットマップへのポインタ内の空間は領域内のダーティストレージの一部のカウント（例えば４キロバイトのビットマップブロック内に設定されたビットの数）を示すために使用され得る。例えば、ｘ８６＿６４アーキテクチャでは、６４ビットのポインタのうち４８ビットだけが重要であり得る。上位ビットは４８個の下位ビット（例えば最下位ビット）から符号拡張され得る。これは、ビットが上位１６ビットに関して同じであり得るということを意味し、失われれば、この値はビット４７から得られる可能性がある。いくつかの実施形態では、ビットマップブロック内に設定されたビットのカウントはポインタのアレイ内のポインタの上位１６ビット内に格納され得る。
【００５３】
段階３１６において、方法３００は終了し得る。
【００５４】
図４は、本開示の一実施形態による、フラッシュメモリのフラッシングを改善する方法を示すフローチャートを描写する。
【００５５】
但し、方法４００は例示的に過ぎない。方法４００は、例えば段階を追加、変更、除去、または再配置することにより変更され得る。段階４０２において、方法は開始し得る。
【００５６】
段階４０４において、ダーティ領域ビットマップへのポインタのアレイがソートされ得る。アレイの各ポインタまたはポインタの他のデータ構造（または他の参照子構造）内のビットカウントは、第１のポインタが最もダーティとなるようにアレイをソートするために使用され得る。
【００５７】
段階４０６では、フラッシング閾値に達したかどうかが判断され得る。ダーティＳＳＤストレージが従来のストレージへフラッシュされるべきかどうかを判断するために１つまたは複数の要因が評価され得る。例えば、因子は、到達されるダーティブロックの規定閾値、ＣＰＵ利用率のレベル、ネットワーク利用率のレベル、従来のストレージの入力／出力のレベル、キャッシュからの１つまたは複数のブロックの時間経過、ユーザ指定優先度のうちの１つまたは複数を含み得る。フラッシングが行われるべきであると判断されれば、本方法は段階４０８へ進み得る。フラッシングが行われるべきでないと判断されれば、本方法は段階４１４において終了し得る。
【００５８】
段階４０８において、最もダーティな領域が識別され得る。いくつかの実施形態では、領域のダーティビットマップへのポインタ内の空間は領域内のダーティストレージの一部のカウント（例えば４キロバイトのビットマップブロック内に設定されたビットの数）を示し得る。例えば、ｘ８６＿６４アーキテクチャでは、６４ビットのポインタのうち４８ビットだけが重要であり得る。上位ビットは４８個の下位ビット（例えば最下位ビット）から符号拡張され得る。これは、ビットが上位１６ビットに関して同じであり得るということを意味し、失われれば、この値はビット４７から得られる可能性がある。ダーティ領域へのポインタのアレイは、アレイの各ポインタ内のビットカウント、または第１のポインタが最もダーティとなるようにアレイをソートするためのポインタの他のデータ構造（または他の参照子構造）を使用し得る。
【００５９】
段階４１０において、ほとんどのダーティ領域に関連付けられたダーティブロックは従来のストレージ（例えばディスク、テープなど）へ書き込まれ得る。いくつかの実施形態では、ダーティブロックは、ダーティ領域ビットマップの基底論理ブロックアドレスと、ダーティビットに対応するダーティブロックの論理ブロックアドレスを提供する特定のダーティビットに対応するオフセットとを使用することによりダーティブロックビットマップから識別され得る。
【００６０】
段階４１０では、別のビットマップポインタがダーティ領域ビットマップへのポインタのアレイ内に存在するかどうかが判断され得る。他のポインタが存在しなければ（例えば、フラッシング閾値を満足するまたは越えるすべてのダーティビットマップはディスクへフラッシュされ、アレイ内にソートされていれば）、方法４００は段階４１４において終了し得る。ダーティ領域の別のビットマップポインタが存在すれば、方法４００は段階４１２において継続し得る。
【００６１】
段階４１２では、次の最もダーティなビットマップに対応するポインタがアレイの開始点としてマーキングされ得る。当初、アレイのソート済みの開始点はオフセット０にあり得、端は、アレイを含むメモリブロックの最終要素であり得る。最も位の高いランキング領域がクリーンにされると（例えば段階４０８後）、領域ポインタは依然としてオフセット０に存在し得るが、誤ってソートされ得る。アレイを従来通りに再ソートし、データを移動させる代わりに、方法４００は、円形状アレイ全体が１だけシフトされるように、ソート済み先頭および端オフセットを調整し得る。ソート済み開始オフセットは１となり得、今やアレイの零番目の要素はアレイの最終要素であり得る。このようにして、零個のダーティブロックへ縮小された領域は、そうでなければソートされるアレイを残して、一定時間操作中にアレイの端の適切な位置へ再ソートされる。アレイ開始要素が調整された後、方法４００は段階４０６へ戻リ得る。
【００６２】
段階４１４において、方法４００は終了し得る。
【００６３】
他の実施形態は本発明の範囲と趣旨内にある。例えば、上述の機能は、ソフトウェア、ハードウェア、ファームウェア、ハードワイヤ、またはこれらの任意の組み合わせを使用することにより実現され得る。命令に従って動作する１つまたは複数のコンピュータプロセッサが、上に説明したように本開示によるフラッシュメモリのフラッシングを改善するために関連付けられた機能を実施し得る。その場合、このような命令が１つまたは複数の非一時的プロセッサ可読記憶媒体（例えば磁気ディスクまたは他の記憶媒体）上に格納され得るということは本開示の範囲内である。加えて、モジュール実施機能がまた様々な位置に物理的に配置され得る（機能の一部が様々な物理的位置において実施されるように配置されることを含む）。
【００６４】
本開示は本明細書において説明された特定の実施形態によりその範囲を制限されるべきではない。実際、本明細書において説明されるものに加え、本開示の他の様々な実施形態およびその修正は、これまでの説明と添付図面から当業者にとって明らかになる。したがって、このような他の実施形態および修正は本開示の範囲に入るように意図されている。さらに、本開示は特定目的のための特定環境内の特定実装形態の文脈で本明細書において説明されたが、当業者は、その有用性はこれに限定されないということと、本開示は任意数の目的のための任意数の環境において効果的に実施され得るということとを認識することになる。したがって、以下に記載の特許請求の範囲は、本明細書において説明された本開示の全広さと趣旨とを考慮して解釈されるべきである。
【符号の説明】
【００６５】
１０２  ホストシステム
１０４  ホストＣＰＵ
１０６  ＰＣＩエクスプレスルートコンプレックス
１０８  スイッチ
１１０  ターゲット
１１２  コントローラ
１１４  非揮発性ストレージ
１１６  ターゲット
１１８  コントローラ
１２０  非揮発性ストレージ
１２２  ターゲット
１２４  コントローラ
１２６  非揮発性ストレージ
２１０  ＳＳＤフラッシュ改善部品
２１２  書き込み監視部品
２１４  ダーティ領域識別部品
２１６  アレイ管理部品
２１８  エラーログ記録および報告部品
２２０、２３４、２４６  例示的方法
３００、４００  方法
３０２、３０４、３０６、３０８、３１０、３１２、３１４、３１６、４０２、４０４、４０６、４０８、４１０、４１２、４１４  段階
【図１】
2017084338.tif 000003
【図２Ａ】
2017084338.tif 000004
【図２Ｂ】
2017084338.tif 000005
【図２Ｃ】
2017084338.tif 000006
【図２Ｄ】
2017084338.tif 000007
【図３】
2017084338.tif 000008
【図４】
2017084338.tif 000009
【外国語明細書】
2017084338000001.pdf