(57)【要約】【課題】ＳＳＤへのコピーオンライト用システム及び方法を提供する。【解決手段】  ＳＳＤ内での改善されたコピーオンライトの機能性のための技術が開示されている。幾つかの実施形態において、デバイスのメモリ内に間接参照データ構造を提供することを含む、ＳＳＤ内での改善されたコピーオンライトの機能性を提供するための方法としての技術が実現され得る。データ構造はクローンデータに対するマスターエントリーを含み得る。マスターエントリーは、１つ以上のインデックスへの参照、及びクローンデータに対するクローンエントリーを有し、クローンエントリーはマスターインデックスへの参照、次のインデックスへの参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する。この技術は、コンピュータプロセッサを用いて、１つ以上の参照を使用し、クローンデータの１つ以上のコピーを横断することを含み得る。【選択図】図５
2016157441.tif 000002
【特許請求の範囲】
【請求項１】
改善されたコピーオンライトの機能性をＳＳＤ内において提供する方法であって、
１つ以上のインデックスに対する参照を有する、クローンデータに対するマスターエントリーと、
マスターインデックスに対する参照、次のインデックスに対する参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する、前記クローンデータに対するクローンエントリーと
を含む間接参照データ構造をデバイスのメモリ内に提供するステップと、
コンピュータプロセッサを用いて、１つ以上の前記参照を使用し、前記クローンデータの１つ以上のコピーを横断するステップと
を含む方法。
【請求項２】
前記間接参照データ構造が複数の物理的アドレスを含む、請求項１に記載の方法。
【請求項３】
前記間接参照データ構造が環状にリンクされたリストの部分であり、クローンデータに対する前記マスターエントリーが、マスターインデックスに対する参照及び次のインデックスに対する参照を含む、請求項１に記載の方法。
【請求項４】
前記間接参照データ構造が環状にリンクされたリストの部分であり、前記クローンデータに対する前記クローンエントリーが、前記マスターインデックスに対する参照及び次のインデックスに対する参照を含む、請求項１に記載の方法。
【請求項５】
前記間接参照データ構造がシングルエンドでリンクされたリストの部分であり、インデックスへのエントリーが、前記インデックスはマスターインデックスであるという指示を提供する、請求項１に記載の方法。
【請求項６】
前記参照が、論理ブロックアドレッシングのためのフラット間接参照テーブルへのエントリーを含む、請求項１に記載の方法。
【請求項７】
前記参照が、論理ブロックアドレッシングのためのツリーデータ構造へのエントリーを含む、請求項１に記載の方法。
【請求項８】
前記改善されたコピーオンライトの機能性が、改善された名前空間コピーの機能性を含む、請求項１に記載の方法。
【請求項９】
１つ以上のパックされた論理ブロックが複製されていることを示すため、前記１つ以上のパックされた論理ブロックに対するインジケータをセットすることを更に含む、請求項１に記載の方法。
【請求項１０】
前記マスターエントリーのマスターインデックスが前記マスターエントリーを指し示す、請求項１に記載の方法。
【請求項１１】
前記クローンエントリーの前記マスターインデックスが前記マスターエントリーを指し示す、請求項３に記載の方法。
【請求項１２】
データ構造への最後のクローンエントリーの次のインデックスが前記マスターエントリーを指し示す、請求項４に記載の方法。
【請求項１３】
前記クローンデータに対する前記クローンエントリーが、唯一のクローンエントリーであることを決定するステップを更に含む方法であって、前記決定するステップが、
前記クローンエントリーの次のインデックスが、前記クローンエントリーの前記マスターインデックスとマッチすることを決定するステップと、
前記マスターエントリーの次のインデックスが前記クローンエントリーを指し示すことを決定するステップと、
パックされた論理ブロックを示す間接参照エントリーへの、前記クローンエントリーの次のインデックスをセットすること、及びパックされた論理ブロックを示す間接参照エントリーへの、前記マスターインデックスのエントリーをセットすることにより、前記クローンデータの前記クローンエントリーを、クローニング不可にするステップと、
オリジナルのマスターエントリーの、最初のパックされた論理ブロックを示す最初の間接参照エントリーへの、前記マスターエントリーの次のインデックスをセットすること、及び前記オリジナルのマスターエントリーの、第二のパックされた論理ブロックを示す第二の間接参照エントリーへの、前記マスターエントリーの前記マスターインデックスをセットすることにより、前記クローンデータの前記マスターエントリーを、クローニング不可にするステップと
を含む、請求項４に記載の方法。
【請求項１４】
前記クローンデータに対する前記クローンエントリーが、複数のクローンエントリーの１つであることを決定するステップを更に含む方法であって、前記決定するステップが、
前記クローンエントリーの次のインデックスが、前記クローンエントリーの前記マスターインデックスとマッチしないこと、及び
前記マスターエントリーの次のインデックスが、前記クローンエントリーを指し示さないこと
の内の、少なくとも１つを決定するステップと、
前記クローンエントリーの次のインデックスにより示されるエントリーを指し示すために、前のエントリーの次のインデックスをセットすることによって、前記クローンデータの前記クローンエントリーを、クローニング不可にするステップと
を含む、請求項４に記載の方法。
【請求項１５】
不要データ収集プロセスの間に、エントリーをレビューするステップと、
前記エントリーが複製されたインジケータを含むことを決定するステップと、
前記エントリーが前記複製されたインジケータを含むという決定に基づいて、前記不要データ収集プロセスへのエントリーが、削除されるべきでない有効なエントリーであることを決定するステップと
を更に含む、請求項１に記載の方法。
【請求項１６】
コンピュータ上で実行可能な一連の命令を含む、コンピュータプログラム製品であって、前記コンピュータプログラム製品が、改善されたコピーオンライトの機能性をＳＳＤ内において提供するためのプロセスを実行し、前記コンピュータプログラムが、
１つ以上のインデックスに対する参照を有する、クローンデータに対するマスターエントリーと、
マスターインデックスに対する参照、次のインデックスに対する参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する、前記クローンデータに対するクローンエントリーと
を含む間接参照データ構造をデバイスのメモリ内に提供するステップと、
コンピュータプロセッサを用いて、１つ以上の前記参照を使用し、前記クローンデータの１つ以上のコピーを横断するステップと
を実施する、コンピュータプログラム製品。
【請求項１７】
改善されたコピーオンライトの機能性をＳＳＤ内において提供するためのシステムであって、前記システムが、
メモリ内に記憶されている格納された命令を含む、第一のデバイスと、
前記命令であって、
１つ以上のインデックスに対する参照を有する、クローンデータに対するマスターエントリーと、
マスターインデックスに対する参照、次のインデックスに対する参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する、前記クローンデータに対するクローンエントリーと
を含む、間接参照データ構造を、第一のデバイスのメモリ内に提供するための命令と、
コンピュータプロセッサを用いて、１つ以上の前記参照を使用し、前記クローンデータの１つ以上のコピーを横断することと
を含む、システム。
【請求項１８】
前記間接参照データ構造が複数の物理的アドレスを含む、請求項１７に記載のシステム。
【請求項１９】
前記間接参照データ構造が環状にリンクされたリストの部分であり、クローンデータに対する前記マスターエントリーが、マスターインデックスに対する参照及び次のインデックスに対する参照を含む、請求項１７に記載のシステム。
【請求項２０】
前記間接参照データ構造が環状にリンクされたリストの部分であり、前記クローンデータに対する前記クローンエントリーが、前記マスターインデックスに対する参照及び次のインデックスに対する参照を含む、請求項１７に記載のシステム。
【請求項２１】
前記間接参照データ構造がシングルエンドでリンクされたリストの部分であり、インデックスへのエントリーが、前記インデックスはマスターインデックスであるという指示を提供する、請求項１７に記載のシステム。
【請求項２２】
前記参照が、論理ブロックアドレッシングのためのフラット間接参照テーブルへのエントリーを含む、請求項１７に記載のシステム。
【請求項２３】
前記第一のデバイスが、周辺装置相互接続エクスプレス（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ））デバイスを含む、請求項１７に記載のシステム。
【請求項２４】
前記１つ以上のパックされた論理ブロックが複製されることを示すために、１つ以上のパックされた論理ブロックに対するインジケータをセットする命令を更に含む、請求項１７に記載のシステム。
【請求項２５】
前記マスターエントリーの前記マスターインデックス、及び前記クローンエントリーの前記マスターインデックスが、前記マスターエントリーを指し示し、そしてデータ構造への最後のクローンエントリーの次のインデックスが、前記マスターエントリーを指し示す、請求項２０に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
不揮発性メモリエクスプレス（Ｎｏｎ−Ｖｏｌａｔｉｌｅ  Ｍｅｍｏｒｙ  ｅｘｐｒｅｓｓ（ＮＶＭｅ））仕様は、半導体デバイス（ＳＳＤ）及び周辺装置相互接続エクスプレス（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ））バスを通じて取り付けられる、その他の対象デバイス用の仕様である。ＮＶＭｅ  ＳＳＤ  ＰＣＩｅホストインターフェースは、ＳＡＳレイド（独立した複数のディスクからなる冗長配列）（ＳＡＳ  ＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ））アダプターによってサポートされる、論理ボリュームに類似した名前空間の概念を定義する。ＳＳＤ内へのコピーオンライトの機能性は、名前空間を用いて実施され得る。名前空間は、ＳＳＤの間接参照システムにおいて追跡される、グローバルな論理ブロックアドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ（ＬＢＡ））空間上の抽出として、一般的に実施される。
【０００２】
ＬＢＡのメタデータは、１つのホストＬＢＡのみを示し、それはリファレンスカウントを含まない。メタデータ内へのリファレンスカウントの包含又は付加は、データを新たなメタデータで書き直すための、追加的書込みを招き、それは良くない解決策である。ＬＢＡのメタデータ内でのそのようなリファレンスカウント無しでは、追加のクローンコピー（例えば、同じデータへの追加的なＬＢＡのポイント）が存在するか否かを決定するための、メカニズムが存在しない。ＳＳＤにおいてデータの複数のクローンコピーを管理することは、それ故不要なデータ収集に関して特別な課題に直面する。例えば、ホストがコピー操作後に「ソース」ＬＢＡを変更する時、それは不要なデータ収集の課題を生じ得る。ソースコピーは事実上、データを１つ以上の追加のホストＬＢＡへと複製するため、コピー操作がなされる以前に書かれた「マスターコピー」であり得る。このマスターＬＢＡが変更されると、追加のホストＬＢＡがそのデータを指示することを示すように、そのデータのメタデータを効果的に変更する方法が存在しないため、無意識コピーの不要データ収集アルゴリズムは、次の機会に物理的データを解放する。
【発明の概要】
【課題を解決するための手段】
【０００３】
ＳＳＤ内での改善されたコピーオンライトの機能性のための技術が開示されている。幾つかの実施形態において、ＰＣＩｅデバイスのメモリ内に間接参照データ構造を提供することを含む、ＳＳＤ内での改善されたコピーオンライトの機能性を提供するための方法としての技術が実現され得る。データ構造はクローンデータの元データ又はソースコピーに対するマスターエントリーを含み得る。マスターエントリーは、マスターインデックスへの参照と、次のインデックスへの参照、クローンデータに対するクローンエントリーとを有し、クローンエントリーはマスターインデックスへの参照と、次のインデックスへの参照とを有する。この技術は、コンピュータプロセッサを用いて、１つ以上の参照を使用し、クローンデータの１つ以上のコピーを横断すること（ｔｒａｖｅｒｓｉｎｇ）を含み得る。
【０００４】
この例示的実施形態の追加的な態様に従って、ホストデバイスは、エンタープライズサーバー、データベースサーバー、ワークステーションのうちの少なくとも１つ、及びコンピュータを含み得る。
【０００５】
この例示的実施形態の追加的な態様に従って、間接参照データ構造は複数の物理的アドレスを含み得る。
【０００６】
この例示的実施形態の更なる態様に従って、間接参照データ構造は環状にリンクされたリストの部分であってもよく、そこでクローンデータ用のマスターエントリーは、マスターインデックスへの参照と、次のインデックスへの参照を含む。
【０００７】
この例示的実施形態のその他の態様に従って、間接参照データ構造は環状にリンクされたリストの部分であってもよく、そこでクローンデータ用のクローンエントリーは、マスターインデックスへの参照と、次のインデックスへの参照を含む。
【０００８】
この例示的実施形態の追加的な態様に従って、間接参照データ構造はシングルエンドでリンクされたリストの部分であってもよく、そこでインデックスへのエントリーは、このインデックスがマスターインデックスであるという表示を提供する。
【０００９】
この例示的実施形態の更なる態様に従って、参照は論理ブロックアドレッシング用のフラット間接参照テーブルへのエントリーを含み得る。
【００１０】
この例示的実施形態の別の態様に従って、参照は論理ブロックアドレッシング用のツリーデータ構造へのエントリーを含み得る。
【００１１】
この例示的実施形態の追加的な態様に従って、改善されたコピーオンライトの機能性は、改善された名前空間でのコピー機能性を含み得る。
【００１２】
この例示的実施形態の更なる態様に従って、本技術は１つ以上のパックされた論理ブロックが複製されていることを示すため、１つ以上のパックされた論理ブロックに対するインジケータをセットすることを含み得る。
【００１３】
この例示的実施形態の別の態様に従って、マスターエントリーのマスターインデックスは、マスターエントリーを指し示し得る。
【００１４】
この例示的実施形態の追加的な態様に従って、クローンエントリーのマスターインデックスは、マスターエントリーを指し示し得る。
【００１５】
この例示的実施形態の更なる態様に従って、データ構造への最後のクローンエントリーの次のインデックスは、マスターエントリーを指し示し得る。
【００１６】
この例示的実施形態の別の態様に従って、本技術は、クローンデータに対するクローンエントリーが、クローンエントリーのみであることを決定するステップを含み得るが、この決定は、クローンエントリーの次のインデックスがクローンエントリーのマスターインデックスにマッチすることを決定するステップと、マスターエントリーの次のインデックスがクローンエントリーを指し示すことを決定するステップと、パックされた論理ブロックを示す間接参照エントリーへの、クローンエントリーの次のインデックスをセットすること、及びパックされた論理ブロックを示す間接参照エントリーへの、マスターインデックスのエントリーをセットすることにより、クローンデータのクローンエントリーをクローニング不可にするステップと、オリジナルのマスターエントリーの、第一のパックされた論理ブロックを示す、第一の間接参照エントリーへの、マスターエントリーの次のインデックスをセットすること、及びオリジナルのマスターエントリーの、第二のパックされた論理ブロックを示す第二の間接参照エントリーへの、マスターエントリーのマスターインデックスをセットすることにより、クローンデータのマスターエントリーをクローニング不可にするステップとを含む。
【００１７】
この例示的実施形態の追加的な態様に従って、本技術は、クローンデータに対するクローンエントリーが複数のクローンエントリーの１つであることを決定するステップを含み得るが、この決定は、クローンエントリーの次のインデックスが、クローンエントリーのマスターインデックスとマッチしないこと、及びマスターエントリーの次のインデックスがクローンエントリーを指し示さず、そして前のエントリーの次のインデックスが、クローンエントリーの次のインデックスによって示されたエントリーを指し示すように設定することにより、クローンデータのクローンエントリーを、クローニング不可にすることの内の少なくとも１つを決定するステップを含む。
【００１８】
この例示的実施形態の更なる態様に従って、本技術は、不要データ収集プロセスの間にエントリーをレビューするステップと、そのエントリーが複製されたインジケータを含むことを決定するステップと、そのエントリーが複製されたインジケータを含むという決定に基づいて、不要データ収集プロセスへのエントリーが、削除されるべきでない有効なエントリーであることを決定するステップとを含み得る。
【００１９】
その他の実施形態において、本技術はコンピュータ上で実行可能な一連の命令から成る、コンピュータプログラム製品として実現され得る。このコンピュータプログラム製品は、ＳＳＤ内において改善されたコピーオンライトの機能性を提供するためのプロセスを実行し得る。このコンピュータプログラムは、１つ以上のインデックスに対する参照を有する、クローンデータに対するマスターエントリーと、マスターインデックスに対する参照、次のインデックスに対する参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する、クローンデータに対するクローンエントリーとを含む間接参照データ構造を、デバイスのメモリ内に提供するステップと、コンピュータプロセッサを用いて、１つ以上の参照を使用し、クローンデータの１つ以上のコピーを横断するステップとを実施し得る。
【００２０】
更に別の実施形態において、本技術はＳＳＤ内において改善されたコピーオンライトの機能性を提供するためのシステムとして実現され得る。このシステムは、第一のデバイスを含み得るが、そこで第一のデバイスはメモリ内に記憶されている、格納された命令を含む。この命令は、１つ以上のインデックスに対する参照を有する、クローンデータに対するマスターエントリーと、マスターインデックスに対する参照、次のインデックスに対する参照、及びデータ構造の最後を示す値の内の少なくとも１つを有する、クローンデータに対するクローンエントリーとを含む、間接参照データ構造を、第一のデバイスのメモリ内に提供するための命令、及びコンピュータプロセッサを用いて、１つ以上の参照を使用し、クローンデータの１つ以上のコピーを横断することを含み得る。
【００２１】
この例示的実施形態の追加的な態様に従って、間接参照データ構造は複数の物理的アドレスを含み得る。
【００２２】
この例示的実施形態の更なる態様に従って、間接参照データ構造は環状にリンクされたリストの部分であってもよく、そこでクローンデータに対するマスターエントリーは、マスターインデックスへの参照及び次のインデックスへの参照を含む。
【００２３】
この例示的実施形態の別の態様に従って、間接参照データ構造は環状にリンクされたリストの部分であってもよく、そこでクローンデータに対するクローンエントリーは、マスターインデックスへの参照及び次のインデックスへの参照を含む。
【００２４】
この例示的実施形態の追加的な態様に従って、間接参照データ構造はシングルエンドでリンクされたリストの部分であってもよく、そこで或るインデックスへのエントリーは該インデックスがマスターインデックスであるという指示を提供する。
【００２５】
この例示的実施形態の更なる態様に従って、参照は論理ブロックアドレッシング用のフラット間接参照テーブルへのエントリーを含み得る。
【００２６】
この例示的実施形態の別の態様に従って、第一のデバイスは周辺装置相互接続エクスプレス（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ））デバイスを含み得る。
【００２７】
この例示的実施形態の追加的な態様に従って、本技術は１つ以上のパックされた論理ブロックが複製されることを示すために、１つ以上のパックされた論理ブロックに対するインジケータをセットする命令を、更に含み得る。
【００２８】
この例示的実施形態の更なる態様に従って、マスターエントリーのマスターインデックス及びクローンエントリーのマスターインデックスは、マスターエントリーを指し示し得る。そしてデータ構造における最後のクローンエントリーの次のインデックスは、マスターエントリーを指し示す。
【００２９】
この例示的実施形態の追加的な態様に従って、対象デバイス（例えば、ＰＣＩｅデバイス）は、図形処理ユニット、オーディオ／ビデオキャプチャーカード、ハードディスク、ホストバスアダプター、及び不揮発性メモリエクスプレス（Ｎｏｎ−Ｖｏｌａｔｉｌｅ  Ｍｅｍｏｒｙ  ｅｘｐｒｅｓｓ（ＮＶＭｅ））コントローラの内の少なくとも１つを含み得る。幾つかの実施形態において、対象デバイスはＮＶＭｅに適合するデバイスであり得る。
【００３０】
本開示は、添付図に示されるような例示的実施形態に関して、ここでより詳細に記述されるであろう。本開示が、例示的実施形態に関して以下で記述される一方で、本開示はそれに限定されないことを理解されたい。本明細書の教示に接する当業者は、ここに記述されている本開示の範囲内で、そして本開示がかなりの効用であり得るものに関して、追加的な実施、変更、実施形態、並びに他の使用領域を認識するであろう。
【００３１】
本開示のより完全な理解を容易にするため、ここで添付図に対する言及がなされ、その中で同様の要素は同様の番号で言及される。これらの図は本開示を限定すると解釈されるべきではなく、例示的となることのみが意図されている。
【図面の簡単な説明】
【００３２】
【図１】本開示の実施形態による、ホストデバイスと連通している複数のＰＣＩｅデバイスを図示する例示的ブロック線図を示す。
【図２】本開示の実施形態による、クローニング不可のパックされた論理ブロックを表わすデータ構造を表わす。
【図３】本開示の実施形態による、マスター及びクローン間接参照データ構造のエントリーを示すテーブルを表わす。
【図４】本開示の実施形態による、ＳＳＤ内での改善されたコピーオンライトの機能性のための例示的モジュールを表わす。
【図５】本開示の実施形態による、ＳＳＤ内での改善されたコピーオンライトの機能性を説明するフローチャートを表わす。
【図６Ａ】本開示の実施形態による、マスターＣ−チャンクデータ構造エントリーフォーマットの、データ構造を表わす。
【図６Ｂ】本開示の実施形態による、クローンＣ−チャンクデータ構造エントリーフォーマットの、データ構造を表わす。
【発明を実施するための形態】
【００３３】
本開示は改善されたコピーオンライトの機能性に関する。幾つかの実施形態において、このコピーオンライトの機能性は名前空間のコピーを含み得る。ＮＶＭｅ  ＳＳＤ  ＰＣＩｅホストインターフェースは、ＳＡＳレイド（独立した複数のディスクからなる冗長配列）（ＳＡＳ  ＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ））アダプターによってサポートされる、論理ボリュームに類似した名前空間の概念を定義する。名前空間は仮想マシン（Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ（ＶＭ））の専用であり得る。ＳＳＤ内において、複数の名前空間は相互に論理的に分離され、そして確実に消去されることができ、そして他の名前空間に影響を与えることなく別の目的のために再利用され得る。
【００３４】
名前空間の識別子は、その名前空間内のＬＢＡと共に、ホストによって出されるメディアアクセス指令の中に含まれ得る。ＳＳＤは、名前空間とＬＢＡの組合せを、ＳＳＤに対して内部的に用いられるグローバルＬＢＡへと変換するために、データ構造（例えば、テーブルルックアップ、ツリー、ハッシュマップ、ビットマップ等）を用い得る。幾つかの実施形態において、ＬＢＡへの言及はこのグローバルＬＢＡに言及し得る。
【００３５】
本開示の実施形態は、ＳＳＤにおいてデータの重複を避ける、効率的な「名前空間コピー」機能を実施するためのシステム及び方法を説明する。これはＳＳＤ内で発生するライトアンプリフィケーションを低減し、それはＳＳＤの寿命を延ばし、一方でより高い性能を提供する。
【００３６】
名前空間コピーは、「コピーオンライト」機能性の一形態である。コピー機能において、媒体上での１回のコピーを指し示すポインターが生成される。媒体上での新たなコピーが１回の書込みで生成され、更新される。名前空間コピー機能は、ＳＳＤにおける「コピーオンライト」の効率的な実施を必要とする。本開示の実施形態は名前空間コピーに適用できる。本開示の実施形態は、ＳＳＤ用の別の「コピーオンライト」実施にも適用可能である。例えば、「スナップショットコピーが名前空間の一瞬のイメージを作り出すために用いられることができ、本実施形態の実施はスナップショットコピーを追跡するために用いられ得る。
【００３７】
本開示の実施形態は、ＳＳＤ間接参照システム（例えば、フラットＬＢＡテーブル）、又は同じ物理的位置を指し示す多重のエントリーを含むための方法を提供する。そのような実施は、多重参照が存在するとき、効率的な不要データ収集を可能にし得る。多重参照の追跡、又は多重ポインターの取り扱い（例えば、ＮＡＮＤフラッシュデータに対する）は、不要データの収集を改善し得る。不要データ収集は、データ用のホストＬＢＡを含む、不揮発性の記憶装置（例えば、ＮＡＮＤフラッシュメモリ、ＮＯＲフラッシュメモリ等）におけるメタデータを用いて実行され得る。不要データ収集のアルゴリズムは、データ構造が依然として該物理的位置を指し示しているかどうかを見るために、間接参照データ構造（例えば、テーブル、ツリー、ハッシュマップ、ビットマップ等）内のそれらのＬＢＡを探索することにより、どのホストセクターが依然として有効であるかを決定し得る。もし示さなければ、該アルゴリズムはそのブロックを解放する。
【００３８】
ここに記述されている１つ以上の実施形態は、１つ以上の重複したホストＬＢＡを追跡する、単一のフラッグ及び代替の間接参照エントリーフォーマットを用いて、重複した間接参照エントリーの効率的な表現を提供する。１つ以上の実施形態は、同じ物理的アドレスを指し示す多重の論理ブロックアドレスを追跡するための、フラット間接参照ルックアップデータ構造を用い得る。重複したＬＢＳを追跡するための、ハッシュマップ、ツリー、又は合成に基づくシステムを用いて、別の実施形態が実施され得る。
【００３９】
ＳＳＤ技術の中での改善されたコピーオンライト機能性は、以下でより詳細に議論される。
【００４０】
図に戻ると、図１は本開示の実施形態による、ホストデバイスと連通しているＰＣＩｅデバイスを図示する例示的ブロック線図である。コピーオンライトの機能性改善は、ホストシステム１０２、ホストＣＰＵ１０４、及びＰＣＩ  Ｅｘｐｒｅｓｓ  Ｒｏｏｔ  Ｃｏｍｐｌｅｘ（ＰＣＩエクスプレスルートコンプレックス）１０６のような、１つ以上の演算技術において実施され得る。ＰＣＩエクスプレススイッチ１０８は、対象１１０、１１６及び１２２のような複数の対象（例えば、ＮＶＭｅに基づく対象のようなＰＣＩｅデバイス）を、ＰＣＩ  Ｅｘｐｒｅｓｓ  Ｒｏｏｔ  Ｃｏｍｐｌｅｘ１０６を介してホストシステム１０２と通信可能に連結し得る。
【００４１】
対象１１０は、ＮＶＭｅコントローラ１１２及び不揮発性の記憶装置１１４を含み得る。対象１１６は、ＮＶＭｅコントローラ１１８及び不揮発性の記憶装置１２０を含み得る。対象１２２は、ＮＶＭｅコントローラ１２４及び不揮発性の記憶装置１２６を含み得る。
【００４２】
システムメモリ１２８は、メモリインターフェース（例えば、ダブルデータレート型スリーシンクロナスダイナミックランダムアクセスメモリ（ｄｏｕｂｌｅ  ｄａｔａ  ｒａｔｅ  ｔｙｐｅ  ｔｈｒｅｅ  ｓｙｎｃｈｒｏｎｏｕｓ  ｄｙｎａｍｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ（ＤＤＲ３  ＳＤＲＡＭ）））を介してホストシステム１０２にアクセス可能な、メモリベースのリソースを含み得る。システムメモリ１２８は、半導体メモリ（例えば、フラッシュメモリ、半導体デバイス（ＳＳＤ））、光メモリ、及び磁気メモリのような、しかしそれに限定されない、あらゆる適切な形態をとることが可能である。システムメモリ１２８は、揮発性又は不揮発性であってもよい。システムメモリ１２８は１つ以上のデータ構造を含み得る。
【００４３】
幾つかの実施形態において、ＰＣＩｅ以外のインターフェース規格は、Ｓｅｒｉａｌ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ（ＳＡＴＡ）、Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ（ＡＴＡ）、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）、ＰＣＩ−ｅｘｔｅｎｄｅｄ（ＰＣＩ−Ｘ）、Ｆｉｂｒｅ  Ｃｈａｎｎｅｌ、Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ（ＳＡＳ）、Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ（ＳＤ）、Ｅｍｂｅｄｄｅｄ  Ｍｕｌｔｉ−Ｍｅｄｉａ  Ｃａｒｄ（ＥＭＭＣ）、及びＵｎｉｖｅｒｓａｌ  Ｆｌａｓｈ  Ｓｔｏｒａｇｅ（ＵＦＳ）を含む、しかしそれらには限定されない１つ以上の部分に対して用いられ得る。
【００４４】
ホストシステム１０２は、エンタープライズサーバー、データベースホスト、ワークステーション、パーソナルコンピュータ、携帯電話機、ゲーム装置、携帯情報端末（ＰＤＡ：個人用デジタル補助装置）、電子メール／テキストメッセージング装置、デジタルカメラ、デジタルメディア（例えばＭＰ３）プレイヤー、ＧＰＳナビゲーション装置、及びＴＶシステムのような、しかしそれに限定されない、あらゆる適切な形態をとることが可能である。
【００４５】
ホストシステム１０２及び対象デバイスは、図を単純化するため、図１に示されていない追加の構成要素を含む事ができる。また、幾つかの実施形態においては、示されている構成要素全てが存在するわけではない。更に、様々なコントローラ、ブロック、及びインターフェースは任意の適切なやり方で実施され得る。例えば、コントローラは、１つ以上のマイクロプロセッサ又はプロセッサ、及び例として（マイクロ）プロセッサ、論理ゲート、スイッチ、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルロジックコントローラ、及び埋め込まれたマイクロコントローラによって実行できる、コンピュータが読取可能なプログラムコード（例えば、ソフトウェア又はファームウェア）を格納する、コンピュータが読取可能な媒体の形態をとることができる。
【００４６】
図２を参照すると、本開示の実施形態による、クローニング不可のパックされた論理ブロックを表わすデータ構造が示されている。８つある、４ＫＢのパックされた論理ブロックのエントリーがこの実施形態において示されている。これらのクローニング不可のパックされた論理ブロック（Ｐａｃｋｅｄ  Ｌｏｇｉｃａｌ  Ｂｌｏｃｋｓ（ＰＬＢｓ））は、論理ブロックアドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓｅｓ（ＬＢＡｓ））を物理的アドレスにマッピングし得る。図示されているように、ＬＢＡｓ０〜７は物理的アドレスブロック（Ｐｈｙｓｉｃａｌ  Ａｄｄｒｅｓｓ  Ｂｌｏｃｋ）０に、ＬＢＡｓ８〜１５は物理的アドレスブロック１に、ＬＢＡｓ１６〜２３は物理的アドレスブロック２に、ＬＢＡｓ２４〜３１は物理的アドレスブロック３に、ＬＢＡｓ３２〜３９は物理的アドレスブロック４に、ＬＢＡｓ４０〜４７は物理的アドレスブロック５に、ＬＢＡｓ４８〜５５は物理的アドレスブロック６に、そしてＬＢＡｓ５６〜６３は物理的アドレスブロック７にマッピングされ得る。
【００４７】
図３は本開示の実施形態による、マスター及びクローン間接参照データ構造のエントリーを示すテーブルを表わす。図３に関して説明されているように、幾つかの実施形態において、コピーオンライトの改善はフラット間接参照システムにおいて実施され得る。ＰＬＢは、ルックアップデータ構造（例えば、フラット間接参照ルックアップテーブル）における「パックされた論理ブロック」であり得る。クローニング操作に関わる８つの連続した８−ＰＬＢ−整列ＰＬＢｓのセットは、「Ｃ−チャンク」と称され得る。媒体上のそのデータがＣ−チャンクに適しているＰＬＢでタグ付けされるＣ−チャンク（すなわち原本）は、「マスターＣ−チャンク」と呼ばれ得る。Ｃ−チャンク内の全てのＰＬＢに対する間接参照データ構造のエントリーは、単一の「Ｃ−エントリー」を形成するように、一緒にグループにされ得る。そのデータが媒体上に存在するＣ−チャンクに対応するＣ−エントリーは、マスターＣ−エントリーと呼ばれ得る。マスターＬＢＡの範囲のコピーであるＬＢＡの範囲を記述するＣ−エントリーは、クローンＣ−エントリーと称され得る。１つ以上のＳＳＤは、４ＫＢのカスタマーデータ＋メタデータ（例えば、８×５１２Ｂのセクター）を追跡するためのＰＬＢを定義し得る。以下で議論される実施形態において、ＰＬＢは単にテーブルへのエントリーであり得る。間接参照データ構造のエントリーは、コピーオンライトを容易にするために（例えば、１ビット分）拡張され得る。追加のビットは、このＰＬＢが原本として作用する他のＰＬＢが存在するか、又はこれが、その原本とする他のＰＬＢを有するクローンであるかを示すための、１に設定され得る「クローントラッキング」ビットであり得る。クローントラッキングビットのセットを伴う間接参照データ構造のエントリーの残りのビットは、ＮＡＮＤメモリアドレスを含み得るか、或いは含み得ない（例えば、そのビットのセット無しでのエントリーのように）。「クローントラッキング＝１」に対する代わりのデータ構造は、一般的なＰＬＢエントリーよりも粗い粒度でトラッキングされ、クローンエントリーのリンクされたリストを作るための領域、及びマスターエントリーに対するポインターを含む。これらの追加領域のためのスペースは、クローニング不可の間接参照エントリーよりも（例えば２倍）大きいＬＢＡのチャンクを記述するために、単一のＣ−エントリーを用いることにより得られうる。クローンデータが個々のホストＬＢＡではなく、大きな仕切り又はファイルセットを含む傾向があるため、このトレードオフは、理に適っている。
【００４８】
個々のホストＬＢＡの物理的アドレスは、追加のルックアップが幾つかのＬＢＡのために必要になるように分配される。これは各々のマスターエントリー及びクローンエントリーにおいて、マスター及びクローンのポインターを含むための余地を作り得る。しかしながら、物理的アドレスに着くためのＤＲＡＭアクセスの数は、大幅には増加しない。図３に示されるように、マスターＣ−エントリーは、全ての物理的アドレス８〜１５に対してマッピングされたＬＢＡを含み得るが、しかし物理的アドレス８〜１１、１４及び１５に対する実際のマッピングのみを含む（物理的アドレス１２及び１３に対するマッピングは、クローンＣ−エントリーから得られうる）。図３のクローンＣ−エントリーにおいて示されるように、マッピングは物理的アドレス８〜１３に対応するＬＢＡのために提供され得る。マスターＣ−エントリーにおいてマッピングされない２つの物理的ブロック（物理的アドレス１２及び１３）は、マスターインデックス及び次のインデックスのためのスペースを提供する。クローンＣ−エントリーにおいてマッピングされない２つの物理的ブロック（物理的アドレス１４及び１５）は、マスターインデックス及び次のインデックスのためのスペースを提供する。マスターＣ−エントリーにおけるマスターインデックスは常に自身を指し示す。クローンＣ−エントリーにおけるマスターインデックスは常にマスターＣ−エントリーを指し示す。マスターＣ−エントリーの次のインデックスは、チェーン内の最初のクローンＣ−エントリーを指し示す。クローンＣ−エントリーの次のインデックスは、１つ以上のクローンＣ−エントリーが存在する場合、次のクローンＣ−エントリーを指し示す。１つだけのクローンＣ−エントリーが存在する場合、又はそれが最後のクローンＣ−エントリーである場合、次のインデックスはマスターＣ−インデックスに戻って指し示し得る（又は、それは例えばゼロポインターのような、リストの最後を示す特別な値を指し示し得る）。これは、マスターＣ−エントリーと１つ以上のクローンＣ−エントリーとの横断を可能にし得る。
【００４９】
フラット間接参照データ構造を有する実施形態において、ＰＬＢ（ｐｈｙｓｉｃａｌ  ｌｏｃａｔｉｏｎ  ｂｌｏｃｋ：物理的位置ブロック）は、単一のルックアップテーブル内の物理的ＮＡＮＤメモリアドレスを含む、個々のエントリーを参照する。一般的なＰＬＢの粒度は、単一のデータ構造のエントリーに対して４ＫＢ（例えば、８×５１２Ｂのセクター）を割り当てる。一例として、８つのＰＬＢのクローンチャンクサイズを考えよう−−クローニングされた範囲への、純粋にランダムな単一セクターのアクセスに対して必要とされるＤＲＡＭアクセスの平均的な数は１．２５である。この数字はより大きなクローンチャンクのサイズと共により小さくなる可能性があり、それはより粗くなる粒度のクローン境界と、ＰＬＢのチャンクを「クローニング不可にする」ために必要とされるより多くのＮＡＮＤアクセスとの相反関係を伴う。
【００５０】
ホストの読取りＰＬＢのルックアップがクローンエントリーを指し示す場合、ＳＳＤは１）物理的アドレスと、２）データが書き込まれた時に使われたＬＢＡとを必要とする。物理的アドレスはマスターエントリー及びクローンエントリーの間に分布しており、対象とされるＬＢＡが２回目のＤＲＡＭ読取りを要する確率を下げるため、重複データを有する全ての得られたＰＬＢエントリーを任意選択的に保管する。＃２に関して、マスターのＬＢＡは、各々のクローンエントリーにおけるマスターポインターに基づき計算され得る−−これは計画的に、追加のＤＲＡＭアクセスを必要とせず、このマスターポインターは（次のクローンポインターと共に）オリジナルのＰＬＢルックアップから隠され得る。
【００５１】
幾つかの実施形態において、現存する間接参照データ構造内に追加の情報を組み込むため、クローニングはＰＬＢのサイズの数倍に過ぎない粒度で追跡され得る。幾つかの実施形態において、粒度は与えられたＬＢＡに対応するＣ−チャンクのインデックスの効率的な計算を可能にするため、ＰＬＢサイズの２のべき乗として選ばれ得る。一例として、乗数は８であっても良いが、より大きなクローニングの粒度が用いられ得る。クローニングは（全体の名前空間のように）一度に大きなＬＢＡの範囲を複製することを含み得る。従って、より大きな粒度を用いるペナルティは最小化され得る。
【００５２】
幾つかの実施形態において、間接参照データ構造は、同じデータを参照する１つ以上のＣ−チャンクの環状にリンクされたリストを、その中に埋め込んでいてもよい。別の実施形態において、他の形態のリンクされたリスト（例えば、シングルエンドでリンクされたリスト）が用いられ得る。Ｃ−チャンクのデータを記述している物理的アドレスは、そのＣ−チャンクリストに対する複数の間接参照エントリーの間で広げられ得る。
【００５３】
そのデータが物理的に媒体上に存在し、Ｃ−チャンクに適しているＰＬＢでタグ付けされるＣ−チャンク（すなわち原本）は、「マスターＣ−チャンク」と呼ばれ得る。媒体上にコピーを格納せずに、同じデータを現在参照する別のＣ−チャンクは、「クローンＣ−チャンク」と呼ばれ得る。
【００５４】
Ｃ−チャンクにおける全てのＰＬＢに対する間接参照データ構造のエントリーは、単一の「Ｃ−エントリー」を形成するため一緒にグループ化される。マスターＣ−チャンクに関して、Ｃ−エントリーは図６Ａに示されるフォーマットであり得る。示されているように、マスターＣ−チャンクは、物理的アドレス６及び７がその後に続く、物理的アドレス０〜３（範囲内の最初の４つの物理的アドレス）を含み得る。欠けている２つの物理的アドレスは、クローンＣ−エントリー内にマッピングされ得る。そして２つの別のスロットが、マスターインデックス及び次のインデックスを提供するために用いられ得る。示されているように、「クローントラッキング」インジケータは１に設定され得る。これは、Ｃ−エントリーが無視されるべき、不要なデータ収集プロセスを示し得る。
【００５５】
クローンＣ−チャンクに関して、Ｃ−エントリーは図６Ｂに示されるフォーマットであり得る。示されているように、物理的アドレス０〜５がマッピングされ得るが、物理的アドレス６及び７は欠け得る。欠けている２つの物理的アドレスは、マスターＣ−エントリー内にマッピングされ得る。そして２つの別のスロットが、マスターインデックス及び次のインデックスを提供するために用いられ得る。示されているように、「クローントラッキング」インジケータは１に設定され得る。これは、Ｃ−エントリーが無視されるべき、不要なデータ収集プロセスを示し得る。
【００５６】
１つ以上の実施形態において、ＮＡＮＤアドレスｉはマスターＣ−チャンクのｉ番目のＰＬＢ用ＮＡＮＤアドレスであり得る（ｉ＝０は最初のＰＬＢを表わす）。マスターインデックスは、マスターＣ−エントリー（それは８つのＰＬＢエントリーのスペースを消費するため、８で割られる）の間接参照データ構造インデックスであり得る。次のインデックスは、同じデータ（それは８つのＰＬＢエントリーのスペースを消費するため、８で割られる）を指し示す次のクローンＣ−エントリー用の間接参照データ構造インデックスであり得る。それ以外に表わすべきクローンＣ−エントリーが存在しない場合、この次のインデックスはマスターＣ−インデックスに戻って指し示し得る。幾つかの実施形態において、この次のインデックスはリストの終了を示す値を指し示し得る（例えばゼロポインター）。
【００５７】
幾つかの実施形態において、Ｃ−チャンクがマスターエントリーであるかどうかを決定するため、１つ以上のテストが用いられ得る。例えば、Ｃ−チャンクは、そのＣ−エントリーのマスターインデックスが、そのＣ−エントリー自体を指し示す場合、そしてその場合だけマスターであり得る。
【００５８】
マスターインデックス及び次のインデックスを介する、マスターＣ−エントリーとクローンＣ−エントリーとの間の関係は、次の動作のうち１つ以上が効率的に行われることを可能にし得る。
【００５９】
８つの連続した８−ＰＬＢ−整列ＰＬＢの一組を複製するために、１つ以上の方法が用いられ得る。例えば、１つ以上の実施形態において、ＰＬＢの一組を複製することは、以下を含み得る。
１．マスターＣ−エントリー及びクローンＣ−エントリーを作り出すとき、参照すべき原本のＰＬＢに対する８つのＮＡＮＤアドレスを読み取ること。
２．８つのオリジナルＰＬＢの間接参照エントリーの代わりに、マスターＣ−エントリーを作り出すこと。
次のインデックスは新たなクローンＣ−エントリーを指し示し得る。
３．現在クローンとして作用するであろう８つのＰＬＢの間接参照エントリーの代わりに、クローンＣ−エントリーを作り出すこと。
次のインデックスは新たなマスターＣ−エントリーを指し示し得る。
【００６０】
１つのＣ−チャンクを新たなＣ−チャンクへと複製するために、１つ以上の方法が用いられ得る。例えば、１つ以上の実施形態において、１つのＣ−チャンクを新たなＣ−チャンクへと複製することは、以下を含み得る。
１．ソースＣ−チャンクがマスターである場合、クローンＣ−エントリーを見出すためにソースＣ−エントリーの次のインデックスをフォローし、それを新たなＣ−エントリーの位置にコピーすること。ソースＣ−チャンクがマスターでない場合、そのソースＣ−エントリーを新たなＣ−エントリーの位置にコピーすること。
２．新たなＣ−エントリーの次のインデックスを、マスターＣ−エントリーの現在の次のインデックスを用いて更新すること。
３．新たなＣ−エントリーを指し示すために、マスターＣ−エントリーの次のインデックスを更新すること。
【００６１】
その間接参照エントリーがクローントラッキングビットのセットを有するＰＬＢに対して、読取りルックアップを行なうために、１つ以上の方法が用いられ得る。例えば、１つ以上の実施形態において、間接参照ビットのセットを用いて読取りルックアップを行なうことは、以下を含み得る。
１．このＰＬＢの間接参照エントリーを含むＣ−エントリーを見ること。このＣ−エントリーがマスターＣ−エントリーか否かを決定すること。その決定に基づき、所望のマスターＰＬＢに対するＮＡＮＤアドレスが、このＣ−エントリー内に格納されているかどうかを更に決定すること。
２．ＮＡＮＤアドレスが最初のＣ−エントリーの読取り内に格納されている場合、そのＮＡＮＤアドレス及びマスターインデックスは戻され得る。マスターインデックスは、何ら追加の間接参照ルックアップを実行することなく、データがどのＰＬＢ番号でタグ付けされるかを決定するために用いられ得る。
３．ＮＡＮＤアドレスが最初のＣ−エントリーの読取り内に格納されておらず、最初のＣ−エントリーの読取りがマスターＣ−エントリーである場合、次のインデックスは、必要とされるＮＡＮＤアドレスを含むクローンＣ−エントリーを見出すためにフォローされ得る。そのＮＡＮＤアドレス及びマスターインデックスは戻され得る。
４．ＮＡＮＤアドレスがＣ−エントリーの読取り内に格納されておらず、それがクローンＣ−エントリーである場合、マスターインデックスは、必要とされるＮＡＮＤアドレスを含むマスターＣ−エントリーを見出すためにフォローされ得る。そのＮＡＮＤアドレス及びマスターインデックスは戻され得る。
【００６２】
クローンＣ−チャンクを「クローニング不可にする」ため、１つ以上の技術が用いられ得る。例えば、幾つかの実施形態において、該技術は以下を含み得る。
１．ただ１つだけのクローンが存在するかどうかを決定すること。例えば、対象のＣ−エントリーの次のインデックスがそのマスターインデックスとマッチし、そのマスターＣ−エントリーの次のインデックスが対象のＣ−エントリーを指し示す場合は、ただ１つだけのクローンが存在する。マスター及びクローンの双方に対して、Ｃ−エントリーを調べ、それらのＰＬＢに対して「正常な」間接参照エントリーで、マスターＣ−エントリーを上書きすること。
２．対象のＣ−エントリーの次のインデックスが、そのマスターインデックスとマッチしない場合、又はそのマスターＣ−エントリーの次のインデックスが対象のＣ−エントリーを指し示さない場合は、別のクローンが存在する。このＣ−エントリーを、その循環リストから取り除くこと。
３．いずれの場合でも、マスターＣ−チャンクに関するデータを読み取り、それをクローンＣ−チャンクにコピーすること、及び新たなコピーのＮＡＮＤアドレスを示す正常な間接参照エントリーで、クローンＣ−エントリーを上書きすること。
【００６３】
マスターＣ−チャンクを「クローニング不可にする」ため、１つ以上の技術が用いられ得る。例えば、幾つかの実施形態において、該技術は以下を含み得る。
１．マスターＣ−エントリー及び最初のクローンＣ−エントリーを読み取ること。
２．マスターＣ−チャンク用の記憶媒体からデータを読み取ること、及びそれを新たな記憶媒体の位置に書き込むことにより、最初のクローンＣ−チャンクのＰＬＢにコピーすること、そしてホストのＬＢＡメタデータを対応するクローンＣ−チャンクと関連付けること。
３．その最初のクローンが唯一のクローンである（すなわち、その次のインデックスがマスターに戻って指し示す）場合、今しがた作り出したコピーに対するＮＡＮＤアドレスを指し示す正常な間接参照エントリーで、最初のクローンＣ−エントリーを上書きすること。オリジナルのマスターＣ−チャンクのＰＬＢを指し示す正常な間接参照エントリーで、マスターＣ−エントリーを上書きすること。
４．その最初のクローンが唯一のクローンではない場合、マスターを環状にリンクされたリストから取り除くこと。今しがた作り出したコピーに対する新たなマスターＣ−エントリーで、最初のクローンＣ−エントリーを上書きすること。今しがた作り出したコピーに対する新たなクローンＣ−エントリーで、別のクローンＣ−エントリーを上書きすること。これは、古いマスターＣ−エントリーの最初のクローンＣ−エントリーが、それ自体及び残りのクローンＣ−エントリーに対する、新たなマスターＣ−エントリーになることを推進し得る。
【００６４】
間接参照の更新が、クローントラッキングビットのセットを有する対象ＰＬＢにとって必要であるとき、本技術はアトミックに以下を含み得る。
１．ＰＬＢのＣ−チャンクをクローニング不可にすること。
２．正常に間接参照の更新を実行すること。
【００６５】
不要データ収集は、不要データ収集のアルゴリズムが、間接参照システムにおけるクローントラッキングビットでそのＰＬＢがマーキングされる、如何なる物理的データに関するデータも決して捨てないように実施され得る。すなわち、不要データ収集のアルゴリズムは、クローントラッキングビットでマーキングされた全てのＰＬＢが、消去よりもむしろ再配置を要する「有効な」データとして見なし得る。
【００６６】
１つ以上の実施形態において、システム内に存在するＣ−チャンクを追跡するために、小さな計数ブルームフィルタがＳＲＡＭ内に格納され得る。書込みの際、ＰＬＢがＣ−チャンクの部分である可能性がない事をブルームフィルタが示す場合、現在のデータ構造のエントリーを最初に読み取ることなく、間接参照システムの直接的な更新が安全に実行され得る。クローンは大きな連続的領域になりがちであるため、ブルームフィルタに用いられるハッシュ関数は、ランダム関数よりもむしろ：
ｆ（Ｃ−エントリーインデックス）＝Ｃ−エントリーインデックス／フィルタサイズ（ｆ（Ｃ−Ｅｎｔｒｙ  Ｉｎｄｅｘ）＝Ｃ−Ｅｎｔｒｙ  Ｉｎｄｅｘ／Ｆｉｌｔｅｒ  Ｓｉｚｅ）のようなものであってもよい。
【００６７】
図４は、本開示の実施形態による、ＳＳＤ内での改善されたコピーオンライトの機能性のための例示的モジュールを表わす。図４に示されるように、コピーオンライトモジュール４１０は、間接参照生成モジュール４１２、間接参照管理モジュール４１４、及びエラー処理モジュール４１６を含み得る。
【００６８】
間接参照生成モジュール４１２は、コピーオンライトでのコピーをトラッキングするための、１つ以上のデータ構造を生成し得る。ＰＬＢは単にテーブルへのエントリーであり得る。間接参照データ構造のエントリーは、コピーオンライトを容易にするために（例えば、１ビット分）拡張され得る。追加のビットは、このＰＬＢが原本として作用する他のＰＬＢが存在するか、又はこれが、その原本として他のＰＬＢを有するクローンであるかを示すための、１に設定され得る「クローントラッキング」ビットであり得る。クローントラッキングビットのセットを伴う間接参照データ構造のエントリーの残りのビットは、ＮＡＮＤメモリアドレスを含み得るか、或いは含み得ない（例えば、そのビットのセット無しでのエントリーのように）。「クローントラッキング＝１」に対する代わりのデータ構造は、クローンエントリーのリンクされたリストを作るための領域、及びマスターエントリーに対するポインターを含む。これらの追加領域のためのスペースは、クローニング不可の間接参照エントリーよりも（例えば２倍）大きいＬＢＡのチャンクを記述するために、単一のエントリーを用いることにより得られる。
【００６９】
間接参照管理モジュール４１４は、間接参照データ構造を用いて１つ以上の動作を実行し得る。間接参照管理モジュール４１４は、データの複製、複製されたデータと複製されないデータの読取りを容易にし得る。そして図３に関連して上記で議論されたような方法の１つ以上を用いて、安全で効率的な不要データ収集を容易にする。
【００７０】
エラー処理モジュール４１６は、複製されたデータの管理に関連する１つ以上のエラーを捕捉し、記録し、報告し、及び／又は処理し得る。
【００７１】
図５は、本開示の実施形態による、ＳＳＤ内での改善されたコピーオンライトの機能性を説明するフローチャートを表わす。しかしながら、プロセス５００は例示的のみである。プロセス５００は、例えばステージが追加、変更、除去、又は再編成されることにより、変更され得る。ステージ５０２において、プロセスが始まり得る。
【００７２】
ステージ５０４において、マスターＣ−エントリーが生成され得る。そのデータが物理的に媒体上に存在し、Ｃ−チャンクに適しているＰＬＢでタグ付けされるＣ−チャンク（すなわち原本）は、「マスターＣ−チャンク」と呼ばれ得る。媒体上にコピーを格納せずに、同じデータを現在参照する別のＣ−チャンクは、「クローンＣ−チャンク」と呼ばれ得る。
【００７３】
Ｃ−チャンクにおける全てのＰＬＢに対する間接参照データ構造のエントリーは、単一の「Ｃ−エントリー」を形成するため一緒にグループ化される。マスターＣ−チャンクに関して、Ｃ−エントリーは図６Ａに示されるフォーマットであり得る。
【００７４】
ステージ５０６において、クローンＣ−エントリーが生成され得る。クローンＣ−チャンクに関して、Ｃ−エントリーは図６Ｂに示されるフォーマットであり得る。
【００７５】
１つ以上の実施形態において、ＮＡＮＤアドレスｉはマスターＣ−チャンクのｉ番目のＰＬＢ用ＮＡＮＤアドレスであり得る（ｉ＝０は最初のＰＬＢを表わす）。
【００７６】
ステージ５０８において、マスターインデックスを示すために或るブロックが割り当てられ得る。マスターインデックスは、マスターＣ−エントリー（それは８つのＰＬＢエントリーのスペースを消費するため、８で割られる）の間接参照データ構造インデックスであり得る。マスターＣ−エントリー及びクローンＣ−エントリーの双方のマスターインデックスは、マスターＣ−エントリーを指し示し得る。
【００７７】
ステージ５１０において、次のインデックスを示すために或るブロックが割り当てられ得る。次のインデックスは、同じデータ（それは８つのＰＬＢエントリーのスペースを消費するため、８で割られる）を指し示す次のクローンＣ−エントリー用の間接参照データ構造インデックスであり得る。それ以外に表わすべきクローンＣ−エントリーが存在しない場合、この次のインデックスはマスターＣ−インデックスに戻って指し示し得る。
【００７８】
幾つかの実施形態において、Ｃ−チャンクがマスターエントリーであるかどうかを決定するため、１つ以上のテストが用いられ得る。例えば、Ｃ−チャンクは、そのＣ−エントリーのマスターインデックスが、そのＣ−エントリー自体を指し示す場合、そしてその場合だけマスターであり得る。
【００７９】
ステージ５１２において、方法５００は終了し得る。
【００８０】
その他の実施形態は、本発明の範囲及び主旨の中にある。例えば、上述の機能性はソフトウェア、ハードウェア、ファームウェア、配線、或いはこれらの任意の組合せを用いて実施され得る。命令に従って動作する１つ以上のコンピュータプロセッサは、上述の本開示に従って改善されたコピーオンライトの機能性と関連する機能を、ＳＳＤ内で実施し得る。その場合には、そのような命令が１つ以上の非一時的な、プロセッサで読取り可能な記憶媒体（例えば、磁気ディスク又は他の記憶媒体）上に記憶され得ることは、本開示の範囲内である。更に、機能を実施するモジュールもまた、機能の部分が様々な物理的位置において実施されるように分配されることを含め、様々な場所に物理的に位置し得る。
【００８１】
本開示は、ここに記述されている特定の実施形態による範囲に限定されるべきではない。実際、本明細書に記述されているものに加えて、本開示の様々な別の実施形態及び本開示に対する様々な変更は、前述の説明及び付図から、当業者にとって明らかであろう。それ故に、そのような別の実施形態及び変更は、本開示の範囲内に入るよう意図されている。更に、本開示は特定の目的のための特定の環境において、特定の実施との関連で本明細書に記述されているが、当業者は、その有用性がその事に限定されず、そして本開示が幾つもの目的のために、幾つもの環境において有益に実施され得ることを認識するであろう。従って、以下で述べられる請求項は、本明細書に記述されている本開示の最大限の広さと意図を考慮して解釈されるべきである。
【符号の説明】
【００８２】
１０２  ホストシステム
１０４  ホストＣＰＵ
１０６  ＰＣＩエクスプレスルートコンプレックス
１０８  ＰＣＩエクスプレススイッチ
１１０  対象
１１２  ＮＶＭｅコントローラ
１１４  不揮発性の記憶装置
１１６  対象
１１８  ＮＶＭｅコントローラ
１２０  不揮発性の記憶装置
１２２  対象
１２４  ＮＶＭｅコントローラ
１２６  不揮発性の記憶装置
１２８  システムメモリ
４１０  コピーオンライトモジュール
４１２  間接参照生成モジュール
４１４  間接参照管理モジュール
４１６  エラー処理モジュール
５００  プロセス
５０２  ステージ
５０４  ステージ
５０６  ステージ
５０８  ステージ
５１０  ステージ
５１２  ステージ
【図１】
2016157441.tif 000003
【図２】
2016157441.tif 000004
【図３】
2016157441.tif 000005
【図４】
2016157441.tif 000006
【図５】
2016157441.tif 000007
【図６Ａ】
2016157441.tif 000008
【図６Ｂ】
2016157441.tif 000009