(57)【特許請求の範囲】
【請求項１】
ガベージデータを収集するための方法であって、前記方法は、
時点２での記憶装置の各セグメントにおける第１データのデータ量と、時点１から前記時点２における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録するステップであって、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じである、ステップと、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するステップと、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するステップと、
を具備し、
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す
ことを特徴とするガベージデータを収集するための方法。
【請求項２】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得するステップと、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得するステップと、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得するステップと、
を具備することを特徴とする請求項１に記載の方法。
【請求項３】
時点２での記憶装置の各セグメントにおける第１データのデータ量と、時点１から前記時点２における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
前記時点２での各セグメントにおけるガベージデータのデータ量と、前記時点１から前記時点２における各セグメントにおける前記ガベージデータの増加量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、前記時点２での各セグメントにおける前記ガベージデータのデータ量に従って、前記時点２での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
前記時点２での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備することを特徴とする請求項２に記載の方法。
【請求項４】
時点２での記憶装置の各セグメントにおける第１データのデータ量と、時点１から前記時点２における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
前記時点２での各セグメントにおける有効データのデータ量と、前記時点１から前記時点２における各セグメントにおける前記有効データの減少量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、前記時点２での各セグメントにおける有効データの前記データ量に従って、前記時点２での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
前記時点２での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備することを特徴とする請求項２に記載の方法。
【請求項５】
時点２での記憶装置の各セグメントにおける第１データのデータ量と、時点１から前記時点２における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
前記時点２での各セグメントにおけるガベージデータのデータ量と、前記時点１から前記時点２における各セグメントにおける有効データの減少量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、前記時点２での各セグメントにおける前記ガベージデータのデータ量に従って、前記時点２での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
前記時点２での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備することを特徴とする請求項２に記載の方法。
【請求項６】
時点２での記憶装置の各セグメントにおける第１データのデータ量と、時点１から前記時点２における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
前記時点２での各セグメントにおける有効データのデータ量と、前記時点１から前記時点２における各セグメントにおけるガベージデータの増加量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、前記時点２での各セグメントにおける有効データの前記データ量に従って、前記時点２での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
前記時点２での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備することを特徴とする請求項２に記載の方法。
【請求項７】
ガベージデータを収集するための記憶装置であって、前記記憶装置は、
時点２での各セグメントにおける第１データのデータ量と、時点１から前記時点２における各セグメントにおける前記第１データの変量とを別々に記録するように構成された記録ユニットであって、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じである、記録ユニットと、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するように構成された計算ユニットと、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するように構成された判定ユニットと、
を具備し、
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す
ことを特徴とするガベージデータを収集するための記憶装置。
【請求項８】
前記計算ユニットは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得し、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得し、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得する
ように特に構成されていることを特徴とする請求項７に記載の記憶装置。
【請求項９】
前記記録ユニットは、
前記時点２での各セグメントにおけるガベージデータのデータ量と、前記時点１から前記時点２における各セグメントにおける前記ガベージデータの増加量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、前記時点２での各セグメントにおける前記ガベージデータのデータ量に従って、前記時点２での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
前記時点２での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されていることを特徴とする請求項８に記載の記憶装置。
【請求項１０】
前記記録ユニットは、
前記時点２での各セグメントにおける有効データのデータ量と、前記時点１から前記時点２における各セグメントにおける前記有効データの減少量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、前記時点２での各セグメントにおける有効データの前記データ量に従って、前記時点２での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
前記時点２での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されていることを特徴とする請求項８に記載の記憶装置。
【請求項１１】
前記記録ユニットは、
前記時点２での各セグメントにおけるガベージデータのデータ量と、前記時点１から前記時点２における各セグメントにおける有効データの減少量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、前記時点２での各セグメントにおける前記ガベージデータのデータ量に従って、前記時点２での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
前記時点２での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されていることを特徴とする請求項８に記載の記憶装置。
【請求項１２】
前記記録ユニットは、
前記時点２での各セグメントにおける有効データのデータ量と、前記時点１から前記時点２における各セグメントにおけるガベージデータの増加量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、前記時点２での各セグメントにおける有効データの前記データ量に従って、前記時点２での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
前記時点２での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されていることを特徴とする請求項８に記載の記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータの分野に関連し、具体的には、ガベージデータを収集するための方法及び記憶装置に関連する。
【背景技術】
【０００２】
一般に、記憶装置にデータが書き込まれた後、論理ブロックアドレス(Logical Block Address, LBA)に従って、対応するアドレスが求められ、その後データはその対応するアドレスに書き込まれる。多入力出力(Input Output, IO)コマンドのアドレスが連続する場合、多入力出力コマンドはシーケンシャルIO(sequential IOs)であり、そうでなければ多入力出力コマンドはランダムIOである。
【０００３】
記憶装置内のハードディスクドライブ(Hard Disk Drive, HDD)がデータの一部を読み出す必要がある場合、磁気ヘッドが、データの位置するトラックに、最初に移動しなければならず、前記磁気ヘッドは、ターゲットセクタが配置されている位置にランダムな方向において移動する。この期間は、シークタイムと呼ばれており、平均で約10ミリ秒である。ターゲットトラックが発見された後、ターゲットセクタは、ディスクシートが回転することにより、磁気ヘッドの下の位置まで回転する。この期間は、回転待ち時間と呼ばれている。7200(回転数／時間)のハードディスクでは、一回転に要する時間はおよそ8.33ミリ秒であり、回転待ち時間の平均時間はおよそ4.17秒である。ターゲットセクタからデータの読み出し又はターゲットセクタへのデータの書き込みの時間はおよそ数ミリ秒である。シーケンシャルIOに対し、アドレッシング及び待ちはIO間では必要ではなく、それゆえシーケンシャルIOのパフォーマンスは比較的高く、ランダムIOに対し、シーク及び待ちが各IOのために必要とされ、シーク及び待ち時間は、データの読み出し又は書き込み時間よりもかなり長く、それゆえランダムIOのパフォーマンスは非常に悪い。
【０００４】
一般に、レイド(Redundant Array of Independent Disks, RAID)保護が、記憶装置に使用される。ランダムライトIOに対し、RAID5及びRAID6の双方は、パフォーマンスに重大な影響を与えるライト・ペナルティを有しており、シーケンシャルライトIOに対し、ライト・ペナルティは非常に小さい。8-ディスクRAID5が、書き込みパフォーマンス上のライト・ペナルティの影響を説明する例として使用される。8-ディスクRAID5は、７つのデータディスク(D)と１つのパリティディスク(P)からなる。小さなIOがランダムに書き込まれたならば、最良の場合で、元のパリティデータはメモリ内に読み出される必要があり、新たなパリティデータを生成するために、新たなデータ及び元のパリティデータが再びチェックされ、その後、新たなデータ及び新たなパリティデータがディスクに書き込まれる。各ホストIOは、少なくとも３回のディスクIO動作をトリガし、書き込みは、３倍増加し、システム全体のパフォーマンスが2/3低下する。シーケンシャルライトの間、７つのホストIOが受信された後、新たなパリティデータを生成するために７つのホストIOが同時にチェックされ、その後７つのIOと新たなパリティデータがディスクに同時に書き込まれる。７つのホストIO毎に８回のディスク動作をトリガし、それゆえ、書き込みが8/7倍増加し、パフォーマンスが若干低下する。
【０００５】
リダイレクト・オン・ライトは、HDDランダムライトのパフォーマンスの低下の問題を解決出来るのみではなく、RAIDのライト・ペナルティ問題を解決できる、完全なシーケンシャルライトであり、したがって、ライトIO処理の場合において、リダイレクト・オン・ライト機能が導入される。記憶装置の物理空間は、有効データ空間と冗長空間に分割される。有効データ空間は、書き込まれたデータを格納する。マッピングが、ライトIOの論理アドレスと、有効データ空間の物理アドレスとの間に確立される。ランダムライトIOが、論理アドレスに行き渡された後、有効データ空間における元の物理アドレスは上書きされず、代わりに、多数ランダムライトIOが連続した冗長空間に順次書き込まれるように、空間のセグメントが冗長空間から割り振られ、その後、論理アドレスと、新たな物理アドレスとのマッピングが、マッピングテーブルを使用することにより記録され、書き込まれた元の有効データ物理空間がガベージとなる。この方法において、ランダムライトは、記憶装置の書き込みパフォーマンスを改善する、完全な一つのストライプのシーケンシャルライトに変換することができる。
【０００６】
リダイレクト・オン・ライトは、元の物理空間においてガベージを生成し得る。冗長空間が規定した程度より小さくなった場合には、ガベージコレクションを有効にする必要があり、そうでなければ、冗長空間が使い果されると、新たなライトIOは、冗長空間が割り当てられないため処理されることができない。ガベージコレクションを容易にするため、記憶装置の物理空間は、一般に特定のサイズで複数のセグメントに分割される。RAIDシナリオにおいて、セグメントはストライプ全体を指し、固体ディスク(Solid State Disk, SSD)シナリオにおいて、セグメントは消去可能なブロックを差し、他のシナリオにおいて、セグメントは、連続空間のセグメントを指す。システムが、一定期間稼働した後は、ガベージが各セグメントにおいて生成され得、セグメントにおけるガベージ量対ブロック量の比が、セグメントにおけるガベージ比と呼ばれている。ガベージコレクションの間、一般に、ガベージ比が高いセグメントが最初に見つかり、このセグメントにおいて残っている有効データは、冗長空間にマイグレートされ、このセグメントにおける有効データがマイグレートされた後、セグメントが再割り当てされるための冗長空間となるように、このセグメントは、再利用され得る。
【０００７】
SSDにおいて、ブロックは、最小書き込み単位であるページで構成されている。SSDにおいて、ブロックは、ガベージデータコレクションが実行されるセグメントである。データがSSDに書き込まれる前に、まず消去が実行される必要があり、消去単位はブロックであり、それゆえ、リダイレクト・オン・ライトもSSD内部で使用され、ガベージコレクションも存在する。動作処理は、消去動作のステップが収集の前に追加されていることを除き上述のリダイレクト・オン・ライトと全く同じである。
【０００８】
一般に、記憶装置のリダイレクト・オン・ライトベースのガベージコレクションは、収集条件として一般にガベージ比を使用する。冗長空間が不足した後、コレクションがガベージ比の値に従って、ガベージ比の高いセグメント上で実行される。有効データは、ガベージコレクション処理においてマイグレートされる必要があり、有効データは、マイグレーションのために読み出される必要があり、その後有効データは新たなアドレスに書き込まれる。この処理において生成されるリードIO及びライトIOは、リダイレクト・オン・ライト機能の一部に属し、したがって、新たなIOがマイグレーション処理において生成される必要があり、新たなIOは、IOリソースと、記憶装置の帯域幅を占有する。一般的な記憶装置において、IOリソースと帯域幅は限られており、セグメントにおける低いガベージ比はセグメントにおいてマイグレートされる必要のある有効データの量が多く、より多くのIOリソース及び記憶装置のより高い帯域幅が占有され、記憶装置のパフォーマンスに重大な影響を与えることを示している。従来技術においては、基本的に、各セグメントはガベージ比が所定の値に到達すると直ちに再利用され、ガベージデータコレクションの低い効率性の原因となる。
【発明の概要】
【課題を解決するための手段】
【０００９】
本発明の実施形態は、ガベージコレクションの効率を向上させる方法についての問題を解決することを目的とするガベージデータを収集するための方法及び記憶装置を提供する。
【００１０】
第１の態様によれば、ガベージデータ収集のための方法が提供され、前記方法は、
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録するステップであって、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じであるステップと、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するステップと、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するステップと、
を具備し、
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す。
【００１１】
第１の態様に関連し、第１の態様の第１の可能な実施様式において、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得するステップと、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得するステップと、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得するステップと、
を具備する。
【００１２】
第１の態様の第１の可能な実施様式に関連し、第１の態様の第２の可能な実施様式において、
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記ガベージデータの増加量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備する。
【００１３】
第１の態様の第１の可能な実施様式に関連し、第１の態様の第３の可能な実施様式において、
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記有効データの減少量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、:
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備する。
【００１４】
第１の態様の第１の可能な実施様式に関連し、第１の態様の第４の可能な実施様式において、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける有効データの減少量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備する。
【００１５】
第１の態様の第１の可能な実施様式に関連し、第１の態様の第５の可能な実施様式において、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおけるガベージデータの増加量とを別々に記録するステップ
を具備し、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備し、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備する。
【００１６】
第２の態様によれば、ガベージデータを収集するための記憶装置が提供され、前記デバイスは、
現時点での各セグメントにおける第１データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記第１データの変量とを別々に記録するように構成された記録ユニットであって、前記第１データは、ガベージデータ又は前記有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、前記有効データの減少量であり、ガベージデータの前記増加量の値は、前記有効データの前記減少量の値と同じである、記録ユニットと、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するように構成された計算ユニットと、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するように構成された判定ユニットと、
を具備し、
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す。
【００１７】
第２の態様に関連し、第２の態様の第１の可能な実施様式において、前記計算ユニットは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得し、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得し、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得する
ように特に構成されている。
【００１８】
第２の態様の第１の可能な実施様式に関連し、第２の態様の第２の可能な実施様式において、前記記録ユニットは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記ガベージデータの増加量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されている。
【００１９】
第２の態様の第１の可能な実施様式に関連し、第２の態様の第３の可能な実施様式において、前記記録ユニットは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記有効データの減少量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されている。
【００２０】
第２の態様の第１の可能な実施様式に関連し、第２の態様の第４の可能な実施様式において、前記記録ユニットは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける有効データの減少量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されている。
【００２１】
第２の態様の第１の可能な実施様式に関連し、第２の態様の第５の可能な実施様式において、前記記録ユニットは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおけるガベージデータの増加量とを別々に記録する
ように特に構成され、
前記計算ユニットは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成され、
前記判定ユニットは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されている。
【００２２】
本発明の実施形態において提供されるガベージデータを収集するための方法及び記憶装置によれば、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とが別々に記録され、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じであり、前記第１データの予測値は、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、計算により取得され、ガベージデータが収集される必要のあるセグメントが、各セグメントにおける第１データの前記予測値に従って、判定される。より多くのガベージデータを有するとともにガベージ生成率のより低いセグメントは、優先的に再利用され、これによりガベージデータコレクションの効率性を改善する。
【００２３】
本発明の実施形態における、または従来技術における技術的ソリューションをより明瞭に説明するのに、以下に、それらの実施形態、または従来技術を説明するのに必要な添付の図面を簡単に概説する。以下の説明における添付の図面は、本発明のいくつかの実施形態を示すに過ぎず、当業者は、創造的な取り組みなしに、添付の図面に従って他の図面をさらに得ることができる。
【図面の簡単な説明】
【００２４】
【図１】図１は、本発明の実施形態によるガベージデータ収集のための方法のフローチャートである。
【図２】図２は、本発明の実施形態によるガベージデータ収集のための方法のフローチャートである。
【図３】図３は、本発明の実施形態によるガベージデータ収集のための方法のフローチャートである。
【図４】図４は、本発明の実施形態によるガベージデータ収集のための記憶装置の構造図である。
【図５】図５は、本発明の実施形態によるガベージデータ収集のための記憶装置の構造図である。
【発明を実施するための形態】
【００２５】
本発明の実施形態における添付の図面を参照しながら、本発明の実施形態における技術的解決策について以下で明確かつ完全に説明する。説明する実施形態は、本発明の実施形態のすべてではなく、一部にすぎないことは明らかである。創造的な努力なしに本発明の実施形態に基づいて当業者によって得られるすべての他の実施形態は、本発明の保護範囲内に入るものである。
【００２６】
図１を参照すると、図１は、本発明の実施形態によるガベージデータ収集のための方法のフローチャートである。図１に示されているように、前記方法は、以下のステップを具備する。
【００２７】
ステップ１０１：現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録し、ここで、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じである。
【００２８】
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す。
【００２９】
記憶装置において、物理空間は、一般に特定のサイズで複数のセグメントに分割される。記憶装置がRAIDであるシナリオにおいて、セグメントは、ストライプ全体を指し、記憶装置がSSDであるシナリオにおいて、セグメントは、消去可能なブロックを指し、他のシナリオにおいて、セグメントは、連続空間のセグメントを指す。
【００３０】
具体的には、リダイレクト・オン・ライトを使用する記憶装置において、論理アドレスと、物理アドレスの２つのデータアドレスがある。論理アドレスと物理アドレスとの間に、論理アドレスと、物理アドレスとの間のマッピング関係を記録するために使用されるマッピングテーブルがある。リダイレクト・オン・ライトを使用する記憶装置がライトIOを受信した後、ライトIOは、論理アドレスを搬送する。データが、初めて論理アドレスに書き込まれる場合、新しい物理アドレスが記憶装置の物理空間から割り振られ、データは、この新しい物理アドレスに書き込まれ、論理アドレスと新しい物理アドレスとの間のマッピング関係がマッピングテーブルにおいて確立される。同じ論理アドレスに２度目にデータが書き込まれる場合、他の新たな物理アドレスが物理空間から割り振られ、データは、前記他の新たな物理アドレスに書き込まれ、論理アドレスと前記他の新たな物理アドレスとの間のマッピング関係がマッピングテーブルにおいて確立される。他の新たな物理アドレスに格納されているデータが有効データであり、元の物理アドレスに格納されているデータは、ガベージデータとなる。セグメントを再利用するために、ガベージデータはマイグレートされる必要はないが、有効データのみがマイグレートされる必要がある。
【００３１】
ステップ１０２：各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する。
【００３２】
任意選択で、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得するステップと、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得するステップと、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得するステップと、
を含む。
【００３３】
現時点での各セグメントにおける第１データは、ガベージデータであり、第１の重みは、1/2であり、各セグメントにおける第１データの変量は、ガベージデータの変量であり、第２の重みは、1/3であると仮定する。より多くのガベージデータを有するセグメントが優先的に再利用されるという原理によれば、ガベージデータの量を第１の重みで乗算することにより得られるより大きい積は、セグメントにおいて、より多くのガベージデータ及び少ない有効データであり、再利用の間にマイグレートされる有効データが少ない量であることを示しており、したがって、セグメントは優先的に再利用され、ガベージデータの変量を第２の重みで乗算することにより得られる大きい積は、セグメントにおけるガベージデータがより大きく増加したことを示しており、再利用を延長すると、多くのガベージデータをセグメントにおいてさらに生成することを可能にするため、セグメントは後で再利用される。これらの２つの要素を包括的に考慮すると、以下のように表現され得る。
ガベージデータの量 × 第１の重み − ガベージデータの変量 × 第２の重み
【００３４】
現時点での各セグメントにおける第１データは、有効データであり、第１の重みは、1/2であり、第１データの変量は、有効データの変量であり、第２の重みは、1/3であると仮定する。より少ない有効データを有するセグメントが優先的に再利用されるという原理によれば、有効データの量に第１の重みを乗算することにより得られるより小さな積は、より少ない有効データであり、再利用の間にマイグレートされる有効データがより少ないことを示しており、したがって、セグメントは優先的に再利用され、有効データの変量を第２の重みにより乗算することにより得られるより小さい積は、ガベージデータの増加が少なかったことを示しており、したがって、セグメントは早期に再利用されている。これらの２つの要素を包括的に考慮すると、以下のように表現され得る。
有効データの量 × 第１の重み − 有効データの変量 × 第２の重み
【００３５】
ステップ１０３：各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する。
【００３６】
任意選択で、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記ガベージデータの増加量とを別々に記録するステップ
を具備する。
【００３７】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備する。
【００３８】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備する。
【００３９】
具体的には、図２は、本発明の実施形態１によるガベージデータ収集のための方法のフローチャートである。図２に示されているように、記憶装置において再利用される必要がある３つのセグメントがあり、時点１でのセグメント０の総記憶容量は、100 MB、有効データは、80 MB、及びガベージデータは、20 MB、時点１でのセグメント１の総記憶容量は、100 MB、有効データは、60 MB、及びガベージデータは、40 MB、時点１でのセグメント２の総記憶容量は、100 MB、有効データは、40 MB、及びガベージデータは、60 MB、時点２でのセグメント０の総記憶容量は、100 MB、有効データは、40 MB、及びガベージデータは、60 MB、時点２でのセグメント１の総記憶容量は、100 MB、有効データは、40 MB、及びガベージデータは、60 MB、時点２でのセグメント２の総記憶容量は、100 MB、有効データは、40 MB、及びガベージデータは、60 MB、であると仮定する。
【００４０】
予め設定された第１の重みは、1であり、及び予め設定された第２の重みは、1/2であると仮定し、その後、各セグメントにおいてガベージデータの予測値が、時点１から時点２の各セグメントにおけるガベージデータの増加量にしたがって、計算により取得される。セグメント0における時点１から時点２でのガベージデータの増加量は、40 MBであり、40 MBに重み1/2を乗算することにより得られるセグメント0におけるガベージデータ予測値は、20 MBであり、セグメント1における時点１から時点２でのガベージデータの増加量は、20 MBであり、20 MBに重み1/2を乗算することにより得られるセグメント1におけるガベージデータの予測値は、10 MBであり、セグメント2における時点１から時点２でのガベージデータの増加量は、0であり、セグメント2におけるガベージデータの予測値は、0である。
【００４１】
前述のデータによると、セグメント0におけるガベージデータの予測値は、ガベージデータの量 × 第１の重み − ガベージデータの変量 × 第２の重み、に従って計算により取得され得、それは、60 MB × 1 − 40 MB × 1/2 ＝ 40 MBであり、
セグメント1におけるガベージデータの予測値は、ガベージデータの量 × 第１の重み − ガベージデータの変量 × 第２の重み、に従って計算により取得され得、それは、60 MB × 1 − 20 MB × 1/2 ＝ 50 MBであり、
前記セグメント2におけるガベージデータの予測値は、ガベージデータの量 × 第１の重み − ガベージデータの変量 × 第２の重み、に従って計算により取得され得、それは、60 MB × 1 − 0 MB × 1/2 ＝ 60 MBである。
【００４２】
ガベージデータが収集される必要のあるセグメントが、ガベージデータの予測値の降順で判定されるという原理に従うと、セグメント2におけるガベージデータが優先的に収集され、その後セグメント1におけるガベージデータが収集され、最後にセグメント0におけるガベージデータ0が収集される。
【００４３】
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記有効データの減少量とを別々に記録するステップ
を具備する。
【００４４】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備する。
【００４５】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備する。
【００４６】
具体的には、図３は、本発明の実施形態２によるガベージデータ収集のための方法のフローチャートである。図３に示されているように、記憶装置において、収集される必要のある３つのセグメントがあり、時点1でのセグメント0の総記憶容量は100 MB、有効データは、80 MB、及びガベージデータは20 MBであり、時点1でのセグメント1の総記憶容量は100 MB、有効データは、60 MB、及びガベージデータは40 MBであり、時点1でのセグメント2の総記憶容量は100 MB、有効データは、40 MB、及びガベージデータは60 MBであり、時点2でのセグメント0の総記憶容量は100 MB、有効データは、40 MB、及びガベージデータは60 MBであり、時点2でのセグメント1の総記憶容量は100 MB、有効データは、40 MB、及びガベージデータは60 MBであり、及び時点2でのセグメント2の総記憶容量は100 MB、有効データは、40 MB、及びガベージデータは60 MBであると仮定する。
【００４７】
第１の重みは、1であり、そして第２の重みは、1/2であると仮定し、その後、各セグメントにおける有効データの予測値が、時点1から時点2の各セグメントにおける有効データの減少量に従って、計算により取得される。セグメント0における時点1から時点2での有効データの減少量は、40 MBであり、40 MBに重み1/2を乗算することにより得られるセグメント0における有効データの予測値は、20 MBであり、セグメント1における時点1から時点2での有効データの減少量は、20 MBであり、20 MBに重み1/2を乗算することにより得られるセグメント1における有効データの予測値は、10 MBであり、セグメント2における時点1から時点2での有効データの減少量は、0であり、セグメント2における有効データの予測値は、0である。
【００４８】
先述のデータによると、セグメント0における有効データの予測値は、有効データ × 第１の重み ＋ 有効データの変量 × 第２の重み、に従って計算により取得され得、それは、40 MB × 1 ＋ 40 MB × 1/2 ＝ 60 MBであり、
セグメント1における有効データの予測値は、有効データの量 × 第１の重み ＋ 有効データの変量 × 第２の重み、に従って計算により取得され得、それは、40 MB × 1 ＋ 20 MB × 1/2 ＝ 50 MBであり、
セグメント2における有効データの予測値は、有効データの量 × 第１の重み ＋ 有効データの変量 × 第２の重み、に従って計算により取得され得、それは、40 MB × 1 ＋ 0 MB × 1/2 ＝ 40 MBである。
【００４９】
ガベージデータが収集される必要のあるセグメントが、有効データの予測値の昇順で判定され、したがって、セグメント2におけるガベージデータが優先的に収集され、その後セグメント1におけるガベージデータが収集され、最後にセグメント0におけるガベージデータが収集される。
【００５０】
任意選択で、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける有効データの減少量とを別々に記録するステップ
を具備する。
【００５１】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備する。
【００５２】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備する。
【００５３】
任意選択で、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおけるガベージデータの増加量とを別々に記録するステップ
を具備する。
【００５４】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備する。
【００５５】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備する。
【００５６】
本発明のこの実施形態において提供されるガベージデータを収集するための方法によると、現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とが別々に記録され、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じであり、前記第１データの予測値は、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、計算により取得され、ガベージデータが収集される必要のあるセグメントは、各セグメントにおける第１データの前記予測値に従って、判定される。より多くのガベージデータを有するとともにガベージ生成率のより低いセグメントは、優先的に再利用され、これによりガベージデータコレクションの効率性を改善する。
【００５７】
図４を参照すると、図４は、本発明の実施形態によるガベージデータを収集するための記憶装置の構造図である。記憶装置は、記録ユニット401、計算ユニット402、及び判定ユニット403を具備する。
【００５８】
前記記録ユニット４０１は、
現時点での各セグメントにおける第１データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記第１データの変量とを別々に記録するように構成され、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じである。
【００５９】
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す。
【００６０】
具体的には、リダイレクト・オン・ライトを使用する記憶装置において、論理アドレスと、物理アドレスの２つのデータアドレスがある。論理アドレスと物理アドレスとの間に、論理アドレスと、物理アドレスとの間のマッピング関係を記録するために使用されるマッピングテーブルがある。リダイレクト・オン・ライトを使用する記憶装置がライトIOを受信した後、ライトIOは、論理アドレスを搬送する。データが、初めて論理アドレスに書き込まれる場合、新しい物理アドレスが記憶装置の物理空間から割り振られ、データは、この新しい物理アドレスに書き込まれ、論理アドレスと新しい物理アドレスとの間のマッピング関係がマッピングテーブルにおいて確立される。同じ論理アドレスに２度目にデータが書き込まれる場合、他の新たな物理アドレスが物理空間から割り振られ、データは、前記他の新たな物理アドレスに書き込まれ、論理アドレスと前記他の新たな物理アドレスとの間のマッピング関係がマッピングテーブルにおいて確立される。他の新たな物理アドレスに格納されているデータが有効データであり、元の物理アドレスに格納されているデータは、ガベージデータとなる。セグメントを再利用するために、ガベージデータはマイグレートされる必要はないが、有効データのみがマイグレートされる必要がある。
【００６１】
前記計算ユニット４０２は、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するように特に構成されている。
【００６２】
任意選択で、前記計算ユニット４０２は、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得し、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得し、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得する
ように特に構成されている。
【００６３】
現時点での各セグメントにおける第１データは、ガベージデータであり、第１の重みは、1/2であり、各セグメントにおける第１データの変量は、ガベージデータの変量であり、第２の重みは、1/3であると仮定する。より多くのガベージデータを有するセグメントが優先的に再利用されるという原理によれば、ガベージデータの量を第１の重みで乗算することにより得られるより大きい積は、セグメントにおいて、より多くのガベージデータ及びより少ない有効データであり、再利用の間にマイグレートされる有効データが少ない量であることを示しており、したがって、セグメントは優先的に再利用され、ガベージデータの変量を第２の重みで乗算することにより得られる大きい積は、セグメントにおけるガベージデータがより大きく増加したことを示しており、再利用を延長すると、多くのガベージデータをセグメントにおいてさらに生成することを可能にするため、セグメントは後で再利用される。これらの２つの要素を包括的に考慮すると、以下のように表現され得る。
ガベージデータの量 × 第１の重み − ガベージデータの変量 × 第２の重み
【００６４】
現時点での各セグメントにおける第１データは、有効データであり、第１の重みは、1/2であり、第１データの変量は、有効データの変量であり、第２の重みは、1/3であると仮定する。より少ない有効データを有するセグメントが優先的に再利用されるという原理によれば、有効データの量に第１の重みを乗算することにより得られるより小さな積は、より少ない有効データであり、再利用の間にマイグレートされる有効データがより少ないことを示しており、したがって、セグメントは優先的に再利用され、有効データの変量を第２の重みにより乗算することにより得られるより小さい積は、ガベージデータの増加が少なかったことを示しており、したがって、セグメントは早期に再利用されている。これらの２つの要素を包括的に考慮すると、以下のように表現され得る。
有効データの量 × 第１の重み − 有効データの変量 × 第２の重み
【００６５】
前記判定ユニット４０３は、各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するように構成されている。
【００６６】
任意選択で、前記記録ユニット４０１は、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記ガベージデータの増加量とを別々に記録する
ように特に構成されている。
【００６７】
前記計算ユニット４０２は、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成されている。
【００６８】
前記判定ユニット４０３は、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されている。
【００６９】
本発明のこの記憶装置の実施形態の具体的な実施様式については、図２の先述の説明を参照し得る。
【００７０】
任意選択で、前記記録ユニット４０１は、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記有効データの減少量とを別々に記録する
ように特に構成されている。
【００７１】
前記計算ユニット４０２は、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成されている。
【００７２】
前記判定ユニット４０３は、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されている。
【００７３】
本発明のこの記憶装置の実施形態の具体的な実施様式については、図３の先述の説明を参照しうる。
【００７４】
任意選択で、前記記録ユニット４０１は、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける有効データの減少量とを別々に記録する
ように特に構成されている。
【００７５】
前記計算ユニット４０２は、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得し、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から、各セグメントにおける前記有効データの変量の前記予測値を減算し、前記ガベージデータの予測値を取得する
ように特に構成されている。
【００７６】
前記判定ユニット４０３は、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定する
ように特に構成されている。
【００７７】
任意選択で、前記記録ユニット４０１は、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおけるガベージデータの増加量とを別々に記録する
ように特に構成されている。
【００７８】
前記計算ユニット４０２は、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得し、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得し、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記ガベージデータの変量の前記予測値とを加算し、前記有効データの予測値を取得する
ように特に構成されている。
【００７９】
前記判定ユニット４０３は、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定する
ように特に構成されている。
【００８０】
本発明のこの実施形態において提供されるガベージデータを収集するための記憶装置によると、前記記憶装置は、現時点での前記記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録し、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じであり、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得し、各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する。より多くのガベージデータを有するとともにガベージ生成率のより低いセグメントは、優先的に再利用され、これによりガベージデータコレクションの効率性を改善する。
【００８１】
図５は、本発明の実施形態による記憶装置の構造図である。図5を参照すると、図５は、本発明のこの実施形態による記憶装置500を示しており、記憶装置の具体的な実施は、本発明の具体的な実施形態において限定されるものではない。前記記憶装置500は、
プロセッサ(processor)501、通信インターフェース(Communications Interface)502、メモリ(memory)503、及びバス504
を具備する。
【００８２】
プロセッサ501、通信インターフェース502、及びメモリ503はバス504を使用することにより相互通信を完了する。
【００８３】
通信インターフェース502は、他のデバイスと通信するように構成されている。
【００８４】
プロセッサ501は、プログラムを実行するように構成されている。
【００８５】
具体的には、プログラムは、プログラムコードを具備し得、プログラムコードは、コンピュータ動作指示を含む。
【００８６】
プロセッサ501は、中央演算処理装置(Central Processing Unit, CPU)、又は特定用途向け集積回路(Application-specific Integrated Circuit, ASIC)、又は本発明の実施形態を実施するように構成されている1つ又は複数の集積回路であり得る。
【００８７】
メモリ503は、プログラムを格納するように構成されている。メモリ503は、例えば、ランダムアクセスメモリ(random-access memory, RAM)などの揮発性メモリ(volatile memory)、又は読み取り専用メモリ(read-only memory, ROM)、フラッシュメモリ(flash memory)、ハードディスク(hard disk drive, HDD)、又はソリッド・ステート・ドライブ(solid-state drive, SSD)などの不揮発性メモリ(non-volatile memory)であり得る。プロセッサ501は、メモリ503に格納されたプログラム実行命令に従って以下の方法を実行する：
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録するステップであって、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じである、ステップと、
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得するステップと、
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定するステップ。
【００８８】
前記有効データは、セグメント内で論理アドレスとのマッピング関係にある物理アドレスに格納されているデータを指し、前記ガベージデータは、セグメント内で論理アドレスとのマッピング関係を有しない物理アドレスに格納されているデータを指す。
【００８９】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
第１の重みと、各セグメントにおける前記第１データの前記データ量とに従って、前記第１データの前記データ量の予測値を計算により取得するステップと、
第２の重みと、各セグメントにおける前記第１データの前記変量とに従って、前記第１データの変量の予測値を計算により取得するステップと、
前記第１データのデータ量の前記予測値と、前記第１データの変量の前記予測値とに従って、前記第１データの予測値を計算により取得するステップと、
を具備する。
【００９０】
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおけるガベージデータのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記ガベージデータの増加量とを別々に記録するステップ
を具備する。
【００９１】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける前記ガベージデータのデータ量に従って、現時点での前記ガベージデータのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおけるガベージデータの前記増加量とに従って、前記ガベージデータの変量の予測値を計算により取得するステップと、
現時点での各セグメントにおける前記ガベージデータのデータ量の前記予測値から各セグメントにおける前記ガベージデータの変量の前記予測値を減算し、前記ガベージデータの予測値を取得するステップと、
を具備する。
【００９２】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記ガベージデータの前記予測値の降順で判定するステップ
を具備する。
【００９３】
現時点での記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録する前記ステップは、
現時点での各セグメントにおける有効データのデータ量と、現時点より前のプリセットされた期間における各セグメントにおける前記有効データの減少量とを別々に記録するステップ
を具備する。
【００９４】
各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得する前記ステップは、
前記第１の重みと、現時点での各セグメントにおける有効データの前記データ量に従って、現時点での前記有効データのデータ量の予測値を計算により取得するステップと、
前記第２の重みと、各セグメントにおける前記有効データの前記減少量とに従って、前記有効データの変量の予測値を計算により取得するステップと、
現時点での前記各セグメントにおける有効データのデータ量の前記予測値と、各セグメントにおける前記有効データの変量の前記予測値とを加算し、前記有効データの予測値を取得するステップと、
を具備する。
【００９５】
各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する前記ステップは、
ガベージデータが収集される必要のあるセグメントを、前記有効データの前記予測値の昇順で判定するステップ
を具備する。
【００９６】
本発明のこの実施形態において提供されるガベージデータを収集するための記憶装置に対し、方法の実施形態及び記憶装置の実施形態の説明がなされているため、個々では詳細は説明しない。
【００９７】
本発明のこの実施形態において提供されるガベージデータを収集するための記憶装置によると、前記記憶装置は、現時点での前記記憶装置の各セグメントにおける第１データのデータ量と、前記現時点より前のプリセットされた期間における前記記憶装置の各セグメントにおける第１データの変量とを別々に記録し、前記第１データは、ガベージデータ又は有効データであり、前記第１データの変量は、ガベージデータの増加量、又は、有効データの減少量であり、ガベージデータの前記増加量の値は、有効データの前記減少量の値と同じであり、各セグメントにおける第１データの前記データ量及び各セグメントにおける第１データの前記変量に従って、前記第１データの予測値を計算により取得し、各セグメントにおける第１データの前記予測値に従って、ガベージデータが収集される必要のあるセグメントを判定する。より多くのガベージデータを有するとともにガベージ生成率のより低いセグメントは、優先的に再利用され、これによりガベージデータコレクションの効率性を改善する。
【００９８】
上記の説明は本発明の例示的な特定の実施形態にすぎないが、本発明の保護範囲を限定するものではない。本発明を逸脱することなく当業者によって行われるいかなる変形または置換も、本発明の保護範囲内に入るものとする。したがって、本発明の保護範囲は、特許請求の範囲の保護範囲に従うものとする。
【符号の説明】
【００９９】
４０１    記録ユニット
４０２    計算ユニット
４０３    判定ユニット
５０１    プロセッサ
５０２    通信インターフェース
５０３    メモリ
５０４    通信バス
【図１】
0006300132.tif 000002
【図２】
0006300132.tif 000003
【図３】
0006300132.tif 000004
【図４】
0006300132.tif 000005
【図５】
0006300132.tif 000006