(57)【要約】【課題】改善されたガーベッジコレクションを遂行できるソリッドステートドライブ（ＳＳＤ）を提供する。【解決手段】本ＳＳＤはデータを格納するフラッシュメモリと、フラッシュメモリへのデータのリード（ｒｅａｄ）及びライト（ｗｒｉｔｅ）を管理するＳＳＤコントローラと、を包含する。ＳＳＤコントローラは、データの属性に応答してストリーム識別子を選択する自動ストリーム検出ロジックと、ガーベッジコレクションのために、フラッシュメモリ内の消去ブロックを選択し、自動ストリーム検出ロジックにより決定された第１ストリームＩＤに応答して第２ブロックに消去ブロックの有効データをプログラムする（書き込む）ガーベッジコレクションロジックと、を包含する。自動ストリーム検出ロジックは、ガーベッジコレクションロジックがガーベッジコレクションのために消去ブロックを選択した後に、第１ストリームＩＤを決定する。【選択図】図３
2018185815.tif 000002
【特許請求の範囲】
【請求項１】
データを格納するフラッシュメモリと、
前記フラッシュメモリへのデータのライト（ｗｒｉｔｅ）及び前記フラッシュメモリからのデータのリード（ｒｅａｄ）を管理するＳＳＤコントローラと、を含み、
前記ＳＳＤコントローラは、
前記データの属性に応答してストリーム識別子（ＩＤ）を選択する自動ストリーム検出ロジックと、
ガーベッジコレクションのために、前記フラッシュメモリ内の消去ブロックを選択し、前記自動ストリーム検出ロジックにより決定された第１ストリームＩＤに応答し、第２ブロックに前記消去ブロックの有効データをプログラムする（書き込む）ガーベッジコレクションロジックと、を含み、
前記自動ストリーム検出ロジックは前記ガーベッジコレクションロジックがガーベッジコレクションのために前記消去ブロックを選択した後、前記第１ストリームＩＤを決定する、ソリッドステートドライブ（ＳＳＤ）。
【請求項２】
前記ＳＳＤコントローラは、ホストコンピュータ上のアプリケーションからのリクエスト（ｒｅｑｕｅｓｔ）を管理する入出力（Ｉ／Ｏ）キューを含み、
前記ガーベッジコレクションロジックは前記入出力（Ｉ／Ｏ）キューに前記有効データに対するライト（ｗｒｉｔｅ）リクエストを配置するライト（ｗｒｉｔｅ）リクエストロジックを含む、請求項１に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項３】
前記ＳＳＤコントローラは、前記アプリケーションからの第２ライト（ｗｒｉｔｅ）リクエストを受信するレシーバ（ｒｅｃｅｉｖｅｒ）をさらに含み、
前記第２ライト（ｗｒｉｔｅ）リクエストは、前記アプリケーションからの有効データを含む、請求項２に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項４】
前記ソリッドステートドライブは、前記自動ストリーム検出ロジックからの第２ストリームＩＤに応答して、前記消去ブロックに前記有効データを書き込む、請求項３に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項５】
前記ガーベッジコレクションロジックは、前記消去ブロックを消去する消去ロジックをさらに包含する、請求項２に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項６】
前記消去ロジックは、前記ライトリクエストが前記ソリッドステートドライブにより処理された後、前記消去ブロックを消去する、請求項５に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項７】
前記消去ロジックは、前記ライトリクエストロジックが前記入出力キューに前記ライトリクエストを配置した後、そして前記ライトリクエストが前記ソリッドステートドライブにより処理される前に、前記消去ブロックを消去する、請求項５に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項８】
前記ガーベッジコレクションロジックは、前記有効データをプログラムする前に、前記自動ストリーム検出ロジックから前記第１ストリームＩＤを要請し、
前記ガーベッジコレクションロジックは、
前記第１ストリームＩＤに応答して第２ブロックを選択するブロック選択ロジックと、及び
前記第２ブロックに前記有効データを書き込むプログラミングロジックと、を包含する、請求項１に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項９】
前記第２ブロックは、前記ガーベッジコレクションの間、プログラムされたデータを格納する特殊なブロックである、請求項８に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項１０】
前記ストリームＩＤは、有効データの論理ブロックアドレス（ＬＢＡ）、前記ソリッドステートドライブに前記有効データを元来（ｏｒｉｇｉｎａｌ）書き込んでいるアプリケーションのアプリケーションＩＤ、前記有効データに対する残余寿命、前記有効データに対する順次性、前記有効データに対するアップデート頻度、前記有効データに対する最新性、前記有効データに対するライト（ｗｒｉｔｅ）サイズ、前記有効データに対するライト時間、前記有効データに対するリード（ｒｅａｄ）頻度、及び前記有効データに対するリード（ｒｅａｄ）温度の中で，少なくとも一つに応答する、請求項１に記載のソリッドステートドライブ（ＳＳＤ）。
【請求項１１】
ソリッドステートドライブ（ＳＳＤ）のガーベッジコレクションに係る方法であって、
ガーベッジコレクションのためのソリッドステートドライブ（ＳＳＤ）において消去ブロックを識別するステップと、
プログラミングを要請する前記消去ブロックの有効データを識別するステップと、
ストリームＩＤに応答して選択された第２ブロックに、前記消去ブロックの前記有効データをプログラミングするステップと、を含み、
前記ストリームＩＤは、プログラミングを要請する前記消去ブロックの前記有効データを識別するステップが識別された後に、前記有効データの属性に応答して決定される、方法。
【請求項１２】
前記プログラミングを要請する前記消去ブロックの前記有効データを識別するステップの以前に、
アプリケーションからのライトリクエストの有効データを前記ＳＳＤにおいて受信するステップと、
前記有効データの前記属性に応答して第２ストリームＩＤを決定するステップと、
前記第２ストリームＩＤに応答して前記消去ブロックを選択するステップと、
前記第２ブロックに前記有効データを書き込むステップと、をさらに包含する、請求項１１に記載の方法。
【請求項１３】
前記第２ブロックに、前記消去ブロックの前記有効データをプログラムするステップは、
前記第２ブロックに前記有効データを書き込むように入出力（Ｉ／Ｏ）キューにライトリクエストを配置するステップを包含する請求項１１に記載の方法。
【請求項１４】
前記消去ブロックを消去するステップをさらに包含する、請求項１３に記載の方法。
【請求項１５】
前記消去ブロックを消去するステップは、
前記有効データが前記第２ブロックに書き込まれる前に前記消去ブロックを消去するステップを包含する、請求項１４に記載の方法。
【請求項１６】
前記第２ブロックに、前記消去ブロックの前記有効データをプログラムするステップは、
前記有効データの前記属性に応答して、前記有効データに対する前記ストリームＩＤを決定するステップと、
前記ストリームＩＤに応答して前記第２ブロックを選択するステップと、
前記第２ブロックに前記有効データをプログラムするステップと、を包含する、請求項１１に記載の方法。
【請求項１７】
前記ストリームＩＤに応答して前記第２ブロックを選択するステップは、
前記ストリームＩＤに応答して、特殊なブロックを選択するステップを包含し、前記特殊なブロックは前記ガーベッジコレクションの間にプログラムされたデータを格納する、請求項１６に記載の方法。
【請求項１８】
前記ストリームＩＤは、前記有効データの論理ブロックアドレス（ＬＢＡ）、前記ソリッドステートドライブに前記有効データを元来書き込んでいるアプリケーションのアプリケーションＩＤ、前記有効データに対する残余寿命、前記有効データに対する順次性、前記有効データに対するアップデート頻度、前記有効データに対する最新性、前記有効データに対するライト（ｗｒｉｔｅ）サイズ、前記有効データに対するライト時間、前記有効データに対するリード（ｒｅａｄ）頻度及び前記有効データに対するリード（ｒｅａｄ）温度の中で，少なくとも一つに応答する、請求項１１に記載の方法。
【請求項１９】
ソリッドステートドライブ（ＳＳＤ）のガーベッジコレクションに係る方法の具現に係る、非一時的なストレージ媒体を含む物品（ａｒｔｉｃｌｅ）において、
前記非一時的なストレージ媒体上に、マシンにより実行されると下記の手順を結果する命令語を格納している物品。
ここで該手順は、
ガーベッジコレクションのために、前記ソリッドステートドライブ（ＳＳＤ）において消去ブロックを識別するステップと、
前記消去ブロックにおいてプログラムを要請する有効データを識別するステップと、
ストリーム識別子（ＩＤ）に応答して選択された第２ブロックに、前記消去ブロックの前記有効データをプログラムする（書き込む）ステップと、を含み、
前記ストリームＩＤは、前記プログラミング（書き込み）を要請する前記消去ブロックが識別され、前記識別された消去ブロックの前記有効データを識別するステップがなされた後に、前記有効データの属性に応答して決定される。
【請求項２０】
前記第２ブロックに、前記消去ブロックの前記有効データをプログラミングする（書き込む）ステップは、
前記第２ブロックに前記有効データを書き込むライトリクエストを入出力（Ｉ／Ｏ）キューに配置するステップを包含する、請求項１９に記載の物品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にソリッドステートドライブ（ＳＳＤ、Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）と関連され、さらに具体的にはＳＳＤ内におけるガーベッジコレクションに係る自動データ配置｛Ｇａｒｂａｇｅ  Ｃｏｌｌｅｃｔｉｏｎ−Ａｕｔｏｍａｔｉｃ  Ｄａｔａ  Ｐｌａｃｅｍｅｎｔ｝の改善に関連される。
【背景技術】
【０００２】
マルチストリーミング（ｍｕｌｔｉ−ｓｔｒｅａｍｉｎｇ）は、ソリッドステートドライブ（ＳＳＤｓ）のより良い耐久性と性能を提供するために開発されたスキーム（ｓｃｈｅｍｅ）である。同一のストリームＩＤを持つデータは一つのストリームに割り当てられ、究極的に同一の消去ブロックに共に格納される。同一のストリームＩＤを持つデータは、共に無効化されることが期待され、これはデータが同一の寿命を有することを意味する。ガーベッジコレクションが発生する時、もし消去ブロックの全てのページが無効であれば、消去ブロックに残っていて他のブロックにプログラムされる必要がある有効データがないので、オーバヘッドは減少する。
【０００３】
ＳＳＤ又はフラッシュ変換階層（Ｆｌａｓｈ  Ｔｒａｎｓｌａｔｉｏｎ  Ｌａｙｅｒｓ、ＦＴＬｓ）は自動ストリーム検出アルゴルズムを包含し、データ操作の属性（頻度（ｆｒｅｑｕｅｎｃｙ）、最新性（ｒｅｃｅｎｃｙ）、順次性（ｓｅｑｕｅｎｔｉａｌｉｔｙ）などのような）に基づいてストリームＩＤを生成でき、ストリームに適合する消去ブロックにデータを配置する。但し、ガーベッジコレクションが発生する時、他のストリームと連関された有効データが混入する場合があり、これはマルチストリーミングの有用性を害する。
【０００４】
マルチストリーミングの有利さを維持するためには、有効データがガーベッジコレクションの間にプログラムされるように、ブロックの選択を管理する方法が、依然として必要である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国登録特許第８４２９６５８Ｂ２号公報
【特許文献２】米国登録特許第９４５９８１０Ｂ２号公報
【特許文献３】米国公開特許第２００９０１１９３５２Ａ１号公報
【特許文献４】米国公開特許第２０１２００７２７９８Ａ１号公報
【特許文献５】米国公開特許第２０１４０１８９２７０Ａ１号公報
【特許文献６】米国公開特許第２０１６０２８３１１６Ａ１号公報
【特許文献７】米国公開特許第２０１６０２８３１２４Ａ１号公報
【特許文献８】米国公開特許第２０１７００３１６３１Ａ１号公報
【特許文献９】韓国登録特許第１０１５４４３０９Ｂ１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施例は、改善されたガーベッジコレクションを遂行できるソリッドステートドライブ、そのガーベッジコレクションに係る方法、及びその具現に係る物品を提供する。
【課題を解決するための手段】
【０００７】
本発明に実施例は制限なしに、下の陳述に拡張できる。
【０００８】
ステータス１．本発明の実施例はソリッドステートドライブ（ＳＳＤ）を含む。
該ＳＳＤは、
データを格納するフラッシュメモリと、
フラッシュメモリへのデータのライト（ｗｒｉｔｅ）及びフラッシュメモリからのデータのリード（ｒｅａｄ）を管理するＳＳＤコントローラと、を含み、
前記ＳＳＤコントローラは、
データの属性に応答してストリーム識別子（ＩＤ）を選択する自動ストリーム検出ロジックと、
ガーベッジコレクションのために、フラッシュメモリ内の消去ブロックを選択し、自動ストリーム検出ロジックにより決定された第１ストリームＩＤに応答して第２ブロックに消去ブロックの有効データをプログラムするガーベッジコレクションロジックと、を含み、
自動ストリーム検出ロジックはガーベッジコレクションロジックがガーベッジコレクションのために消去ブロックを選択した後、第１ストリームＩＤを決定するように動作する。
【０００９】
ステータス２．ステータス１によるＳＳＤを含む本発明の実施例において、
ＳＳＤコントローラは、ホストコンピュータ上のアプリケーションからのリクエスト（ｒｅｑｕｅｓｔ）を管理する入出力（Ｉ／Ｏ）キューを含み、
ガーベッジコレクションロジックは入出力キューに有効データに対するライト（ｗｒｉｔｅ）リクエストを配置するライト（ｗｒｉｔｅ）リクエストロジックを含む。
【００１０】
ステータス３．ステータス２によるＳＳＤを含む本発明の  実施例において、ＳＳＤコントローラは、アプリケーションからの第２ライト（ｗｒｉｔｅ）リクエストを受信するレシーバ（ｒｅｃｅｉｖｅｒ）をさらに含み、第２ライト（ｗｒｉｔｅ）リクエストはアプリケーションからの有効データを含む。
【００１１】
ステータス４．ステータス３によるＳＳＤを含む本発明の実施例において、ＳＳＤは自動ストリーム検出ロジックからの第２ストリームＩＤに応答して、消去ブロックに有効データを書き込む。
【００１２】
ステータス５．ステータス４によるＳＳＤを含む本発明の実施例において、第１ストリームＩＤは第２ストリームＩＤである。
【００１３】
ステータス６．ステータス２によるＳＳＤを含む本発明の実施例において、ガーベッジコレクションロジックは消去ブロックを消去する消去ロジックをさらに包含する。
【００１４】
ステータス７．ステータス６によるＳＳＤを含む本発明の実施例において、消去ロジックはライトリクエストがＳＳＤにより処理された後、消去ブロックを消去するように動作する。
【００１５】
ステータス８．ステータス６によるＳＳＤを含む本発明の実施例において、消去ロジックはライトリクエストロジックが入出力キューにライトリクエストを配置した後、そしてライトリケエストがＳＳＤにより処理される前に、消去ブロックを消去するように動作する。
【００１６】
ステータス９．ステータス１によるＳＳＤを含む本発明の実施例において、
ガーベッジコレクションロジックは有効データをプログラムする前に、自動ストリーム検出ロジックから第１ストリームＩＤを要請するように動作するものの、
ガーベッジコレクションロジックは、
第１ストリームＩＤに応答して第２ブロックを選択するブロック選択ロジックと、及び第２ブロックに有効データを書き込むプログラミングロジックと、を包含する。
【００１７】
ステータス１０．ステータス９によるＳＳＤを含む本発明の実施例において、第２ブロックはガーベッジコレクションの間プログラムされたデータだけを格納する特殊なブロックである。
【００１８】
ステータス１１．ステータス１によるＳＳＤを含む本発明の実施例において、ストリームＩＤは有効データの論理ブロックアドレス（ＬＢＡ）、ＳＳＤに有効データを元来（ｏｒｉｇｉｎａｌ）書き込んでいるアプリケーションのアプリケーションＩＤ、有効データに対する残余寿命、有効データに対する順次性、有効データに対するアップデート頻度、有効データに対する最新性、有効データに対するライト（ｗｒｉｔｅ）サイズ、有効データに対するライト時間、有効データに対するリード（ｒｅａｄ）頻度、及び有効データに対するリード（ｒｅａｄ）温度の中で，少なくとも一つに応答する。
【００１９】
ステータス１２．本発明の実施例は方法を含み、方法は、
ガーベッジコレクションのためのソリッドステートドライブ（ＳＳＤ）において消去ブロックを識別するステップと、
プログラミングを要請する消去ブロックの有効データを識別するステップと、及び
第２ブロックに消去ブロックの有効データをプログラミングするステップと、を包含するものの、第２ブロックはストリーム識別子（ＩＤ）に応答して選択され、ストリームＩＤはプログラムを要請する消去ブロックの有効データを識別するステップが識別された後に、有効データの属性に応答して決定される。
【００２０】
ステータス１３．ステータス１２による方法を含む本発明の実施例において、
プログラミングを要請する消去ブロックの有効データを識別するステップの以前に、
アプリケーションからライトリクエストの有効データをＳＳＤから受信するステップと、
有効データの属性に応答して第２ストリームＩＤを決定するステップと、
第２ストリームＩＤに応答して消去ブロックを選択するステップと、及び
第２ブロックに有効データを書き込むステップと、をさらに包含する。
【００２１】
ステータス１４．ステータス１３による方法を含む本発明の実施例において、ストリームＩＤは第２ストリームＩＤである。
【００２２】
ステータス１５．ステータス１２による方法を含む本発明の実施例において、第２ブロックに消去ブロックの有効データをプログラムするステップは、第２ブロックに有効データを書き込むように入出力（Ｉ／Ｏ）キューにライトリクエストを配置するステップ、を包含する。
【００２３】
ステータス１６．ステータス１５による方法を含む本発明の実施例において、消去ブロックを消去するステップ、をさらに包含する。
【００２４】
ステータス１７．ステータス１６による方法を含む本発明の実施例において、消去ブロックを消去するステップは、有効データが第２ブロックに書き込まれる前に、消去ブロックを消去するステップと、を包含する。
【００２５】
ステータス１８．ステータス１２による方法を含む本発明の実施例において、第２ブロックに、消去ブロックの有効データをプログラムするステップは、
有効データの属性に応答して、有効データに対するストリームＩＤを決定するステップと、
ストリームＩＤに応答して第２ブロックを選択するステップと、
第２ブロックに有効データをプログラムするステップと、を包含する。
【００２６】
ステータス１９．ステータス１８による方法を含む本発明の実施例において、ストリームＩＤに応答して第２ブロックを選択するステップは、ストリームＩＤに応答して、特殊なブロックを選択するステップを包含するものの、特殊なブロックはガーベッジコレクションの間にプログラムされたデータのみを格納する。
【００２７】
ステータス２０．ステータス１２による方法を含む本発明の実施例において、ストリームＩＤは有効データの論理ブロックアドレス（ＬＢＡ）、ＳＳＤに有効データを元来書き込んでいるアプリケーションのアプリケーションＩＤ、有効データに対する残余寿命、有効データに対する順次性、有効データに対するアップデート頻度、有効データに対する最新性、有効データに対するライト（ｗｒｉｔｅ）サイズ、有効データに対するライト時間、有効データに対するリード（ｒｅａｄ）頻度及び有効データに対するリード（ｒｅａｄ）温度の中で，少なくとも一つに応答する。
【００２８】
ステータス２１．本発明の実施例は、ソリッドステートドライブ（ＳＳＤ）のガーベッジコレクションに係る方法の具現に係る、非一時的なストレージ媒体を含む物品において、非一時的なストレージ媒体上に、マシンにより実行されると下記の手順を結果する命令語を格納している物品を含む。
ガーベッジコレクションのために、ソリッドステートドライブ（ＳＳＤ）において消去ブロックを識別するステップと、
消去ブロックにおいてプログラムを要請する有効データを識別するステップと、
ストリーム識別子（ＩＤ）に応答して選択された第２ブロックに、消去ブロックの有効データをプログラムする（書き込む）ステップと、
ここで、ストリームＩＤはプログラミング（書き込み）を要請する消去ブロックが識別され、前記識別された消去ブロックの有効データを識別するステップがなされた後に、前記有効データの属性に応答して決定される。
【００２９】
ステータス２２．ステータス２１による物品を含む本発明の実施例において、非一時的ストレージ媒体は、プログラムを要請する消去ブロックの有効データを識別するステップの以前に、アプリケーションからライトリクエストの有効データをＳＳＤから受信するステップと、
有効データの属性に応答して第２ストリームＩＤを決定するステップと、
第２ストリームＩＤに応答して消去ブロックを選択するステップと、
消去ブロックに有効データを書き込むステップと、を、マシンにより実行される時、発生させる命令語を更に格納する。
【００３０】
ステータス２３．ステータス２２による物品を含む本発明の実施例において、ストリームＩＤは第２ストリームＩＤである。
【００３１】
ステータス２４．ステータス２１による物品を含む本発明の実施例において、第２ブロックに、消去ブロックの有効データをプログラムするステップは、第２ブロックに有効データを書き込むように入出力（Ｉ／Ｏ）キューにライトリクエストを配置するステップを包含する。
【００３２】
ステータス２５．ステータス２４による物品を含む本発明の実施例において、非一時的なストレージ媒体は消去ブロックを消去するステップを、マシンにより実行される時、発生させる命令語を格納する。
【００３３】
ステータス２６．ステータス２５による物品を含む本発明の実施例において、消去ブロックを消去するステップは、有効データが第２ブロックに書き込まれる前に、消去ブロックを消去するステップを包含する。
【００３４】
ステータス２７．ステータス２１による物品を含む本発明の実施例において、第２ブロックに、消去ブロックの有効データをプログラムするステップは、
有効データの属性に応答して有効データに対するストリームＩＤを決定するステップと、
ストリームＩＤに応答して第２ブロックを選択するステップと、
第２ブロックに有効データをプログラムするステップと、を包含する。
【００３５】
ステータス２８．ステータス２７による物品を含む本発明の実施例において、ストリームＩＤに応答して第２ブロックを選択するステップは、ストリームＩＤに応答して特殊なブロックを選択するステップを包含し、ここで特殊なブロックはガーベッジコレクションの間にプログラムされたデータのみを格納する。
【００３６】
ステータス２９．ステータス２１による物品を含む本発明の実施例において、ストリームＩＤは有効データの論理ブロックアドレス（ＬＢＡ）、ＳＳＤに有効データを元来書き込んでいるアプリケーションのアプリケーションＩＤ、有効データに対する残余寿命、有効データに対する順次性、有効データに対するアップデート頻度、有効データに対する最新性、有効データに対するライト（ｗｒｉｔｅ）サイズ、有効データに対するライト時間、有効データに対するリード（ｒｅａｄ）頻度及び有効データに対するリード（ｒｅａｄ）温度の中で，少なくとも一つに応答する。
【発明の効果】
【００３７】
本発明の実施例によると、ガーベッジコレクションロジックが自動ストリーム検出ロジックにより決定された第１ストリームＩＤに応答して第２ブロックに消去ブロックの有効データをプログラムする（書き込む）ので、第２ブロックへの書き込みと消去ブロックの消去の機会を低減し、改善されたガーベッジコレクションを提供できる。
【図面の簡単な説明】
【００３８】
【図１】本発明の実施例によるソリッドステートドライブ（ＳＳＤ）を有するマシンを図示した図面である。
【図２】図１のマシンの追加的な詳細を図示した図面である。
【図３】図１のＳＳＤの詳細を図示した図面である。
【図４】ライト（ｗｒｉｔｅ）リクエストに対するストリームＩＤを決定する自動ストリーム検出ロジックを図示した図面である。
【図５】消去ブロックからの有効データを他のブロックにプログラムして移す、図１のＳＳＤにおけるガーベッジコレクションを図示した図面である。
【図６】ストリームＩＤを決定するのに使用され得るデータの多様な属性を図示した図面である。
【図７】図３のＳＳＤコントローラの詳細を図示した図面である。
【図８】図７のガーベッジコレクションロジックの詳細を図示した図面である。
【図９】本発明の実施例により、有効データをプログラムするように図７の入出力（Ｉ／Ｏ）キューに有効データを伝達する図８のライトリクエストロジックを図示した図面である。
【図１０】本発明の実施例により、図７の自動ストリーム検出ロジックから受信されたストリームＩＤに対応するブロックを選択する図８のブロック選択ロジックを図示した図面である。
【図１１】本発明の実施例により、ストリームＩＤを用いたガーベッジコレクションを遂行するための例示的な手順に対する順序図を図示した図面である。
【図１２】本発明の実施例により、消去ブロックからの有効データを選択された第２ブロックにプログラムして移すための例示的な手順に対する順序図を図示した図面である。
【発明を実施するための形態】
【００３９】
本発明の実施例に対する参照が詳細に提供される。本発明の例示は添付された図面に図示される。以下の詳細な説明から、本発明の完全な理解が可能となるように数多くの詳細が陳述される。但し、当業者にとっては、斯かる具体的な詳細な説明なしに本発明を実施できることが理解されるべきである。他の例示で、よく知られた方法、手順、構成要素、回路及びネットワークは実施例の態様を曖昧にしないようにするため、詳細な説明をしない。
【００４０】
例えば、第１、第２などの用語が、ここで多様な要素を説明するのに使用されるが、このような要素は斯かる用語に制限されないと理解されるべきである。斯かる用語は、単純に一つの要素を、他の要素と区別するため使用される。例えば、第１モジュールは第２モジュールと命名され得るし、同様に、本発明の範囲を逸脱しない状態で、第２モジュールは第１モジュールと命名され得る。
【００４１】
ここで、本発明の説明に使用された用語の目的は、特定の実施例を説明するためであって、本発明を制限する意図はない。本発明の説明及び付加された請求項に使用される時、文脈上明白に違うように指示しない限り、単数の形式の“ａ”、“ａｎ”及び“ｔｈｅ”は、なお、複数の形式を含むように意図される。なお、ここで使用される“及び／又は”の用語は一つ以上の連関及び列挙された事項の任意の全ての可能な組合を意味し包含するものとして理解されるべきである。“包含する”及び／又は“包含する〜”の用語は、詳細な説明で使用される時、陳述された特徴、数字、ステップ、動作、要素及び構成要素の存在を明示するものであり、一つ以上の他の特徴、数字、ステップ、要素、構成要素及び／又はそのグループの存在又は付加を排除しない。図面の構成要素及び特徴は、必ずしも実寸通りに描かれない。
【００４２】
ストリーム基盤のガーベッジコレクション（ｇａｒｂａｇｅ  ｃｏｌｌｅｃｔｉｏｎ）の場合、データがストリームＩＤに基づいて当初はブロックに配置されるにも拘わらず、異なる寿命を有するデータが混在する機会を提供する。このような結果は単一のストリーム内のデータの寿命が、時間の経過と共に転変（ｅｖｏｌｖｅ）するので発生する。例えば、ホットデータ（ｈｏｔ  ｄａｔａ）がストリーム識別子（ｉｄｅｎｔｉｆｉｅｒ，  ＩＤ）「８」に割り当てられる時間区間が有り得る。但し、作業負荷がホスト上で変化するにつれデータ温度が変化し、従って与えられたストリームＩＤに割り当てられた、より古いデータブロックは、同一のストリームＩＤに属する、より新しいブロックと同一の期待寿命を有しない場合がある。
【００４３】
しかし、ガーベッジコレクションさえストリーミングを利用できる。ガーベッジコレクションの一部として有効データをプログラムする（書き込む）際に、消去ブロックの有効データに対しては、論理ブロックアドレス（ＬＢＡ：Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ）（又は任意の他の属性）を手交（ｐａｓｓ）し、斯かる有効ＬＢＡに対して、対応して検出された現在のストリームＩＤに該有効データを書き込む（ｗｒｉｔｅ）ことにより、自動ストリーム検出アルゴリズムを利用できる。しかも、ストリームＩＤが、データがプログラムされる時間に再決定されるので、ストリームＩＤをデータと共に格納する必要がない。
【００４４】
ストリームＩＤを使用して有効データをプログラムするのに使用され得る二つの接近法がある。一つの方法は、プログラム動作を新規ライト（ｗｒｉｔｅ、書き込み）として扱うことである。もっと具体的に、有効データは、アプリケーションからの元来のライトリクエスト（書き込み要求）のように見えるライトリクエストとして、ＳＳＤに伝送される。この接近法は２つの長所を有する。一番目に、ガーベッジコレクションは有効データを特別扱いして書き込む必要がなく、ＳＳＤ内に既に存在するロジックに該書き込みプロセスを一任（ｌｅａｖｅ）できる。二番目に、消去ブロックは有効データが実際に新しいブロックに書き込まれる前に消去可能になる。但し、斯かる接近法はブロックが消去された後、そして有効データの予定されたライトが完了される前に、電力障害（又は一部の類似で不運なイベント）が発生すると、データが消失するという問題点を有する。他の方法は、ガーベッジコレクションロジックに自動ストリーム検出アルゴリズムからストリームＩＤを要請させ、そのストリームＩＤを利用して有効データを書き込む場所を決定する。
【００４５】
図１は本発明の実施例によるソリッドステートドライブ（ＳＳＤ）を有するマシンを図示した図面である。図１で、マシン１０５が図示される。マシン１０５は任意のマシンであって、デスクトップ（ｄｅｓｋ  ｔｏｐ）又はラップトップ（ｌａｐｔｏｐ）コンピュータ、サーバ（独立型サーバ（ｓｔａｎｄａｌｏｎｅ））又はラックサーバ（ｒａｃｋ  ｓｅｒｖｅｒ）、又は本発明の実施例を有益に使える任意の他の装置を包含するが、これに制限されない。なお、マシン１０５は専門化された携帯用コンピューティング装置、タブレットコンピュータ、スマートフォン及び他のコンピューティング装置を包含できる。マシン１０５は任意のアプリケーションを実行できるし、データベースアプリケーションが良い例示であるが、本発明の実施例は任意のアプリケーションへ拡張できる。
【００４６】
マシン１０５は、ここに示す特定の形式に限定されないが、プロセッサ１１０、メモリ１１５及びＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）１２０を包含する。プロセッサ１１０は任意の種類のプロセッサであり、例えば、Ｉｎｔｅｌの、Ｘｅｏｎ、Ｃｅｌｅｒｏｎ、Ｉｔａｎｉｕｍ又はＡｔｏｍプロセッサ、ＡＭＤのＯｐｔｅｒｏｎプロセッサ、或いは、ＡＲＭのプロセッサある。図１では単一のプロセッサを示すが、マシン１０５は任意の個数のプロセッサを包含できる。メモリ１１５は、任意の種類のメモリであって、フラッシュメモリ、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））、ＰＲＡＭ（Ｐｅｒｓｉｓｔｅｎｔ  ＲＡＭ）、ＦＲＡＭ（登録商標）（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  ＲＡＭ）、又は、ＮＶＲＡＭ（Ｎｏｎ−Ｖｏｌａｔｉｌｅ  ＲＡＭ）（ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  ＲＡＭ））など）の何れかであり得るが、典型的にはＤＲＡＭである。なお、メモリ１１５は相異なるメモリ形式の任意の組み合わせであり得る。メモリ１１５は、なおマシン１０５の一部であるメモリコントローラ１２５により制御される。
【００４７】
ＳＳＤ１２０は任意の種類のＳＳＤであって、ガーベッジコレクションを遂行する（フラッシュメモリを使用しない場合を含む）他の形式のストレージを包含するように拡張され得る。ＳＳＤ１２０は、メモリ１１５内に駐在（ｒｅｓｉｄｅ）する装置ドライバ１３０により制御される。
【００４８】
図２は図１のマシン１０５の追加的な詳細を図示した図面である。図２を参照すれば、典型的に、マシン１０５はメモリコントローラ１２５とクロック２０５を包含する一つ以上のプロセッサ１１０を含み、プロセッサ１１０はマシン１０５の各構成要素の動作を調整するように使用される。なお、プロセッサ１１０は、例えば、ＲＡＭ（Ｒａｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、又は他の、状態を保存する媒体を含むメモリ１１５と結合される。なお、プロセッサ１１０はストレージ装置１２０とも結合され、例えば、イーサネット（登録商標）コネクタ又は無線コネクタであるネットワークコネクタ２１０と結合される。なお、プロセッサ１１０はバス２１５と連結され、バス２１５には、使用者インタフェース２２０、入出力（Ｉ／Ｏ、Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）エンジン２２５を使用して管理されるインタフェースポート、及び他の構成要素が連結される。
【００４９】
図３は、図１のＳＳＤ１２０の詳細を図示した図面である。図３において、ＳＳＤ１２０は、ホストインタフェースロジック３０５、ＳＳＤコントローラ３１０及び多様なフラッシュメモリチップ３１５−１〜３１５−８を包含し、フラッシュメモリチップ３１５−１〜３１５−８は多様なチャンネル３２０−１〜３２０−４として組織化される。ホストインタフェースロジック３０５は、ＳＳＤ１２０と図１のマシン１０５との間の通信を管理する。
ＳＳＤコントローラ３１０はフラッシュメモリチップ３１５−１〜３１５−８上のガーベッジコレクションの動作と共に、リード及びライト動作を管理する。ＳＳＤコントローラ３１０は、斯かる管理の一部を遂行するフラッシュ変換階層３２５を包含する。ＳＳＤコントローラ３１０の機能の本願に係る詳細については、図７などを参照して後述する。図３は、４個のチャンネル３２０−１〜３２０−４として組織化された８個のフラッシュメモリチップ３１５−１〜３１５−８を包含するＳＳＤ１２０を図示するが、本発明の実施例は任意の個数のチャンネルとして組織された任意の個数のフラッシュメモリチップを支援できる。
【００５０】
図４は、ライトリクエストに対するストリームＩＤを決定する自動ストリーム検出ロジックを図示した図面である。図４で、多様なライトリクエスト４０５−１〜４０５−４が図示される。各々のライトリクエスト４０５−１〜４０５−４は論理ブロックアドレス（ＬＢＡ）４１０−１〜４１０−４を包含する。自動ストリーム検出ロジック４１５は、ＬＢＡ４１０−１〜４１０−４を使用して、ライトリクエスト４０５−１〜４０５−４を割り当てるストリーム識別子（ＩＤｓ）４２０−１〜４２０−４を決定する。例えば、自動ストリーム検出ロジック４１５は、ここでの全ての目的のための参照文献で包含される２０１７年４月２７日出願された米国特許出願第１５／４９９、８７７において説明されたように動作し、ＬＢＡ４１０−１〜４１０−４に基づいてストリームＩＤ４２０−１〜４２０−４を割り当てる。但し、図４は、ＬＢＡ４１０−１〜４１０−４を使用してストリームＩＤ４２０−１〜４２０−４を決定する自動ストリーム検出ロジック４１５を図示するが、本発明の別の実施例はライトリクエスト４０５−１〜４０５−４の任意の属性を使用し、ストリームＩＤ４２０−１〜４２０−４を決定できる。
【００５１】
フラッシュメモリ（又は、ガーベッジコレクションを遂行する他の装置）を使用するＳＳＤにおいて、フラッシュメモリは通常、多重のページを含む消去ブロックとして組織化される。ページの各々は三つの状態の中で一つであり得る。斯かる三つの状態はフリー（ｆｒｅｅ、現在どのようなデータも格納しない状態）、有効（ｖａｌｉｄ、現在データを格納した状態）及び無効（ｉｎｖａｌｉｄ、以前に有効データを格納したが、最早有効データを格納せず、しかし未だフリーではない状態）である。
【００５２】
新しいデータがフラッシュメモリに書き込まれる時、フリーページの位置が探し出され、斯かるフリーページにデータが書き込まれる。その後、該ページは有効データを格納するとしてマーキングされる。ページは、典型的に消去ブロック内で順序通り書き込まれる。但し、フラッシュメモリの個々のページは通常、一旦書き込まれると重ねて書き込まれ（ｏｖｅｒ−ｗｒｉｔｔｅｎ）ない。よって、フラッシュメモリに格納されたデータが、アプリケーションにより変更される時、該データを含む全体のページがフラッシュメモリの新しいページに書き込まれる。その後、元のページは無効としてマーキングされる。“ガーベッジコレクション”は、ＳＳＤが消去ブロック単位で無効ぺージを使用可能（ｒｅｃｌａｉｍ）とする処理過程である。斯かる処理過程は、消去ブロックの全てのページをリセットするステップ及び再びフリーとして該ページをマーキングするステップを包含する。
【００５３】
ページが二つではなくむしろ三つの可能な状態を有する理由は、ガーベッジコレクションが遂行される方式に起因する。もしも、ガーベッジコレクションが個々のページに対して遂行されると仮定するなら、無効状態は必要とならないであろう。ガーベッジコレクションはデータが無効化されるや否や、生起（実行）できるし、ページは即時フリーにされる。しかし実際には、ガーベッジコレクションは典型的に個々のページよりもっと大きいチャンク（ｃｈｕｎｋ、塊り）に対して動作する。
斯かるチャンクは、消去ブロック又はスーパーブロック（ｓｕｐｅｒｂｌｏｃｋｓ）と命名され、任意の個数のページを包含できる。或るブロックがガーベッジコレクションの対象になると、現ブロック中の全てのページはフリー状態に遷移する。よって、現ブロック中の任意の現在有効データは、現ブロック中のページが消去される前に、何処か他のブロックのフラッシュメモリのフリーページに書き込まれ（斯かる処理過程はプログラム（プログラミング）と命名される）なければならない。
もしも、ガーベッジコレクションがブロック中の任意のデータが無効化されると直ちに、スタートすると仮定するならば、ＳＳＤは該ブロック中の有効ページから他のページにデータを移すのに相当膨大な時間を消費しなければならないはずである。消去ブロックからの有効データを他のページにプログラムすること自身が、それによる相当膨大なオーバヘッドを惹起するが、その事実を脇に措くとしても、フラッシュメモリは典型的に、限定された回数以上に書き込み（プログラム）アクセスされると信頼性が低下する（又は、より悪い場合には、使用不能になる）。
よって、消去ブロックからの有効データをプログラムするのに消費される時間量を最小化することが要求される。但し、同時に、ガーベッジコレクションは、消去ブロックの全てのページが無効としてマーキングされるまで遅延することはできない。フラッシュメモリはその全てのブロックが、有効又は無効としてマーキングされたページだけを含む（即ち、フリーページを含まない）状態になると、これは、これ以上データを該フラッシュメモリに書き込めないことを意味する。
【００５４】
図５は、消去ブロックからの有効データを他のブロックにプログラムして（書き込んで）移す、図１のＳＳＤ１２０におけるガーベッジコレクションを図示した図面である。図５において、ブロック５０５−１〜５０５−１０が図示され、ブロック５０５−２は特に詳細に示される。ブロック５０５−２は４個のページ５１０−１〜５１０−４を包含し、ページ５１０−１、５１０−２、５１０−４は現在無効としてマーキングされ、ページ５１０−３は現在有効データが格納されていることを意味する有効としてマーキングされている。従って、ブロック５０５−２がガーベッジコレクションの対象になる時、ページ５１０−３の有効データ（以下、単に「有効データ５１０−３」ともいう）は例えば、ページ５１５−１〜５１５−４を含むと図示されるブロック５０５−８のような他のブロックにプログラムされるべきである。ページ５１０−３の有効データは具体的には例えば、破線の矢印５２０で図示されたように、ページ５１５−１にプログラムされる。ページ５１０−３の有効データがページ５１５−１にプログラムされた後に、ブロック５０５−２の全てのページは無効としてマーキングされ、ブロック５０５−２全体が消去ブロックとしてガーベッジコレクションの対象になる。
【００５５】
図５は、１０個のブロック５０５−１〜５０５−１０を図示し、各々のブロックが４個のページを有する場合を図示するが、本発明の実施例は任意の個数のブロックを含む図１のＳＳＤ１２０を支援でき、各々のブロックは任意の個数のページを有し得る。本発明の実施例は、ブロック又はブロック当りのページの特定の個数に制限されない。
【００５６】
図６は、図４のストリームＩＤ４２０−１〜４２０−４を決定するのに使用され得るデータの多様な属性を図示した図面である。図６には、属性の集合６０５が図示される。属性の集合６０５は、ＬＢＡ４１０、アプリケーションＩＤ６１０及び残余寿命６１５を包含する。例えば、ＬＢＡ４１０は図１のＳＳＤ１２０に書き込まれるべきデータのＬＢＡであり、アプリケーションＩＤ６１０は図１のＳＳＤ１２０に対してデータ書き込みを要請しているアプリケーションの識別子であり、残余寿命６１５はデータが（新しいデータに交替されるか単純に完全に除去されることで）無効化される前に、データが図１のＳＳＤ１２０に残っているであろうと期待される時間である。ストリームＩＤを決定するのに使用される他の可能な属性は、以下を含む。
【００５７】
順次性６２０：書き込まれるべきデータのＬＢＡが以前のＬＢＡ（直前のライトリクエストであるか、又は、或るウィンドウ内の以前のライトリクエスト）に順次的なページにあるか。
アップデート頻度６２５：書き込まれたデータがどの程度頻繁にアップデート（現在データが書き込まれる場所のページを無効化する）されるであろうと期待されるか。
最新性６３０：書き込まれたデータのＬＢＡが、どの程度近い以前に書き込まれたか。
ライトサイズ６３５：（同じ時期になされた他のライトに関するサイズに対して相対的な）書き込まれるべきデータのサイズ。
ライト時間６４０：（同じ時期になされた他のライトに関する書き込み時間に対して相対的な）データの書き込み時間。
リード頻度６４５：（他のデータのリード頻度に対して相対的に）リードされるべきデータがどの程度頻繁にリードされたか。
リード温度６５０：リードされるべきデータの“温度”、即ち、リードされるべきデータが“ホット（ｈｏｔ）”と考慮されるか“クール（ｃｏｏｌ）”と考慮されるか。
【００５８】
本発明の実施例は、図６に図示された属性を超えて、他の属性を支援できる。例えば、データをライトするアプリケーションにより要求されるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）に対しては、要求に応じて、任意の他の属性が使用され得る。
【００５９】
従来技術においては、図４のストリームＩＤ４２０−１〜４２０−４は、ライトリクエスト４０５−１〜４０５−４が全て受信される時、決定される。図４のストリームＩＤ４２０−１〜４２０−４は、図４のライトリクエスト４０５−１〜４０５−４により書き込まれたデータに対するメタデータとして格納され得るが、ストリームＩＤ４２０−１〜４２０−４はアップデートされない。しかし、有効データ５１０−３（正確には、「ページ５１０−３に格納された有効データ」であるが、以下、このように「有効データ５１０−３」と略称する）のような、消去ブロックの有効データがガーベッジコレクションの一部として新しいブロックに書き込まれるべき時、図５の有効データ５１０−３が元来書き込まれた時に決定されたストリームＩＤは、図５の有効データ５１０−３と現在マッチングされるストリームを適切に表わせない場合もある。
別の言葉で言えば、もし図５の有効データ５１０−３がこの時新しいライトリクエストの対象として受信されたと仮定すると、図５の有効データ５１０−３は、元来書き込まれた時に割り当てられたストリームと異なるストリームに割り当てられるであろう。図５の有効データ５１０−３をプログラムする時にストリームＩＤをアップデートすることの長所は、元来のストリームＩＤが図５の有効データ５１０−３を書き込むためのブロックを選択するのに使用されると仮定した場合に生起するであろう属性よりも、さらに類似した属性を有するデータを格納するブロックに有効データ５１０−３がプログラムされ得るという点である。
【００６０】
以上、ガーベッジコレクションの処理過程、及びガーベッジコレクションの処理過程において図４のストリームＩＤ４２０−１〜４２０−４を適用する場合の長所を説明したが、ここで本発明の実施例を追加して記述する。図７は、図３のＳＳＤコントローラ３１０の詳細を図示した図面である。図７においてＳＳＤコントローラ３１０は、フラッシュ変換階層３１５の外に、レシーバ７０５、入出力（Ｉ／Ｏ）キュー７１０、自動ストリーム検出ロジック４１５、及びガーベッジコレクションロジック７１５を含む。レシーバ７０５は、図１のマシン１０５上で走る（実行される）アプリケーションなどの任意のソースから図４のライト（ｗｒｉｔｅ）リクエスト４０５−１〜４０５−４を受信する。一旦受信されると、図４のライト（ｗｒｉｔｅ）リクエスト４０５−１〜４０５−４は処理のために、Ｉ／Ｏキュー７１０に配置される。特定のライト（ｗｒｉｔｅ）リクエストがＩ／Ｏキュー７１０から消去される時に、自動ストリーム検出ロジック４１５が該ライト（ｗｒｉｔｅ）リクエストに対する適切なストリームＩＤを決定するために使用され、その後、データが図３の適切なフラッシュメモリ３１５−１〜３１５−８に書き込まれる。
【００６１】
ガーベッジコレクションロジック７１５は、図３の適切なフラッシュメモリ３１５−１〜３１５−８から消去ブロックを復旧させる。消去ブロックは、任意のアルゴリズムを使用して選択される。但し、任意の使用可能なページをランダムに採用してそのページに図５の有効データ５１０−３をプログラムする場合に比べて、ガーベッジコレクションロジック７１５は、図５の有効データ５１０−３をプログラムするべき適切なブロックを選択するにあたって、自動ストリーム検出ロジック４１５を有利に活用できる。ガーベッジコレクションロジックは、下記の図８を参照してさらに説明される。
【００６２】
図８は、図７のガーベッジコレクションロジック７１５の詳細を図示した図面である。本発明の一実施例において、ガーベッジコレクションロジック７１５はライト（ｗｒｉｔｅ）リクエストロジック８０５及び消去ロジック８１０を含む。ガーベッジコレクションロジック７１５が図５の消去ブロック５０２−２のような消去ブロックを消去するように起動される際に、該消去ブロック内に図５の有効データを含むページ５１０−３がある場合には、まるでライト（ｗｒｉｔｅ）リクエストが図１のマシン１０５上で走るアプリケーションによって提起された場合のように、ライト（ｗｒｉｔｅ）リクエストロジック８０５はライト（ｗｒｉｔｅ）リクエストを図７のレシーバ７０５を介してＩ／Ｏキュー７１０に伝達する。（もし、消去ブロックが有効データを有するページを含まないならば、プログラムが要求される有効データが無いことは自明である。一方、該消去ブロック内の全てのページが無効データを含む場合は、該消去ブロックを直接消去できる。）
このような方式でライト（ｗｒｉｔｅ）リクエストが処理される場合、有効データ５１０−３は、図１のＳＳＤ１２０の新たなページに書き込まれる。図１のＳＳＤ１２０の観点からは、このようなライト（ｗｒｉｔｅ）リクエストは、図１のマシン１０５上を走るアプリケーションによって提起されるライト（ｗｒｉｔｅ）リクエストと異なることはなく、同様に処理される。一旦ライト（ｗｒｉｔｅ）リクエストが図７のＩ／Ｏキュー７１０に伝達されると、消去ロジック８１０は図５の消去ブロック５０５−２を消去する。ガーベッジコレクションロジック７１５は消去ロジック８１０を開始する前に、有効データが新たなページに書き込まれることを待つ必要のない点に留意されたい。何故ならば、該有効データは図７のＩ／Ｏキュー７１０内に完全に存在し、順に書き込まれるであろうから。もちろん、電力障害のような想定外の状況によってもデータが消失しないことを保証され場合には、消去ロジック８１０は図５の消去ブロック５０５−２を消去処理する前に、データの書き込みが成功するまで待たねばならない。但し、図１のＳＳＤ１２０がこのような保証を提供する場合は、想定外の状況によってもデータが消失しないように図７のＩ／Ｏキュー７１０のデータを保証する他のメカニズムが既に図１のＳＳＤ１２０内に通常、存在する。
【００６３】
図９は本発明の実施例によって、有効データをプログラムするように図７のＩ／Ｏキュー７１０に有効データを伝達する図８のライト（ｗｒｉｔｅ）リクエストロジック８０５を図示した図面である。図９において、一旦、ブロック５０５−２が消去ブロックとして選択されて有効データ５１０−３が識別されると、ライト（ｗｒｉｔｅ）リクエストロジック８０５は、ライト（ｗｒｉｔｅ）リクエストを生成して、図１のＳＳＤ１２０上の新たなページに戻り、有効データ５１０−３を再書き込みする。このようなライト（ｗｒｉｔｅ）リクエストはＩ／Ｏキュー７１０に伝達でき、図１のマシン１０５上を走るアプリケーションに由来する元来のライト（ｗｒｉｔｅ）リクエストと同様に処理できる。
【００６４】
図７のガーベッジコレクションロジック７１５によって有効データ５１０−３を直接プログラムすることを避けるために、Ｉ／Ｏキュー７１０に有効データ５１０−３を配置すると、元来のライト（ｗｒｉｔｅ）リクエストの書き込み遅延（ｌａｔｅｎｃｙ）を増加させうると考えられがちであるが、書き込み遅延への実際の影響は僅かである。理想的には、図７のガーベッジコレクションロジック７１５は、図１のＳＳＤ１２０に対する他の需要が低い場合に動作する。図１のＳＳＤ１２０が多数の元来のライト（ｗｒｉｔｅ）リクエストを図１のマシン１０５上で走るアプリケーションから受信している最中には、図７のガーベッジコレクションロジック７１５は消去ブロックの復旧を、望ましくは開始しない。
図７のガーベッジコレクションロジック７１５は、図１のＳＳＤ１２０が異常に低いフリーページカウントを示す場合に開始され得る。但し、このような状況が発生すれば、有効データのプログラミング（書き込み）は何れにしても発生し、元来のライト（ｗｒｉｔｅ）リクエストの書き込み遅延に対しては類似の影響を予期せざるを得ない。よって、有効データ５１０−３をプログラムする際に、あたかも元来のライト（ｗｒｉｔｅ）リクエストの場合のようにＩ／Ｏキュー７１０を使用することは、伝統的な従来のガーベッジコレクションにおけるよりも大きい影響を惹起する可能性がない。そして、有効データ５１０−３は、残余寿命などの類似する属性を有する他のデータと共に配置される可能性が大きいので、ガーベッジコレクションの性能は、将来の有効データに対するプログラミング（書き込み）の機会を低減することにより、向上できる。
【００６５】
図８に戻って、本発明の他の実施例によるガーベッジコレクションロジック７１５は消去ロジック８１０、ブロック選択ロジック８１５、及びプログラミングロジック８２０を含む。ブロック選択ロジック８１５は、図７の自動ストリーム検出ロジック４１５にアクセスして、図５の有効データ５１０−３に対する新たなストリームＩＤを決定する。即ち、ブロック選択ロジック８１５は図５の有効データ５１０−３に係る図６の属性の集合６０５内の一つの属性を図７の自動ストリーム検出ロジック４１５に伝達し、これに応答してストリームＩＤを受信する。その後、ブロック選択ロジック８１５は、そのストリームＩＤを使用して、有効データ５１０−３をプログラミングするための適切なブロックを選択する。これは、従来の伝統的な技術を使用するプログラミングロジック８２０によって行われうる。
ブロック選択ロジック８１５は、図７の自動ストリーム検出ロジック４１５から受信されたストリームＩＤに基づいて任意の適切なブロックを選択できる点に留意されたい。例えば、選択されたブロックは、選択されたストリームＩＤを有する図１のマシン１０５上で走るアプリケーションから受信された元来のライト（ｗｒｉｔｅ）リクエストに応答して、書き込みされたデータを保有するブロックでありうる。又は、選択されたブロックは、ガーベッジコレクションの結果としてプログラムされ、このようなストリームＩＤによって、割り当てられたデータのみ格納する特殊ブロックでありうる。なお、本発明の実施例は、他の方式で受信されたストリームＩＤに応答してブロックを選択するように、ブロック選択ロジック８１５を具現できる。
【００６６】
図１０は本発明の実施例によって、図７の自動ストリーム検出ロジック４１５から受信されたストリームＩＤに応答するブロックを選択する図８のブロック選択ロジック８１５を図示した図面である。図１０において、ブロック選択ロジック８１５は、自動ストリーム検出ロジック４１５からストリームＩＤ１００５を受信する。ストリームＩＤ１００５は、有効データ５１０−３の属性を使用して決定される。一旦、ブロック５０５−８のようなブロックが選択されると、フリーページ１０１０−３のような、ブロック５０５−８のフリーページの位置が探され、プログラミングロジック８２０は、有効データ５１０−３を例えばフリーページ１０１０−３に書き込む。一旦、このような動作が完了されると、図８の消去ロジック８１０は消去ブロック５０５−２を消去し、この消去ブロック５０５−２のページ５１０−１〜５１０−４は全て、フリーになる。
【００６７】
図７のガーベッジコレクションロジック７１５が具現される方法に関わらず、本発明の実施例は、大略、有効データ５１０−３がプログラムされるべき時に、有効データ５１０−３をプログラムするのに使用されるストリームＩＤを決定する。即ち、図７のガーベッジコレクションロジック７１５は、有効データ５１０−３が元来プログラムされる時に決定される図４のストリームＩＤ４２０−１〜４２０−４に依存しない。代わりに、図７のガーベッジコレクションロジック７１５は、大略、有効データ５１０−３が新たな（フリー）ページにプログラムされるべき時に、有効データ５１０−３をプログラムする際に使用されるストリームＩＤを決定する。また、図７のガーベッジコレクションロジック７１５は、有効データ５１０−３とともに格納されていたかも知れないストリームＩＤに依存しない。何故ならば、以前に決定されたストリームＩＤは最早、有効データ５１０−３をプログラムするための最善のストリーム選択を反映しない、からである。
【００６８】
図１１は、本発明の実施例によって、図１０のストリームＩＤ１００５を用いたガーベッジコレクションを行うための例示的な手順に対するフローチャートを図示した図面である。図１１のステップ１１０５において、図７のレシーバ７０５は一つ以上の図４の書き込みコマンド（ライトリクエスト）４０５−１〜４０５−４を受信する。ステップ１１１０において、図７の自動ストリーム検出ロジック４１５は、図４の書き込みコマンド４０５−１〜４０５−４に対するストリームＩＤ４２０−１〜４２０−４を決定する。ステップ１１１５において、図３のＳＳＤコントローラ３１０は、図４のストリームＩＤ４２０−１〜４２０−４に関連されたデータが書き込まれるべきブロックを選択し、ステップ１１２０において、図３のＳＳＤコントローラ３１０は、図３のフラッシュメモリ３１５−１〜３１５−８にデータを書き込むように書き込みコマンド４０５−１〜４０５−４を実行する。
【００６９】
ステップ１１２５において、図３のＳＳＤコントローラ３１０はガーベッジコレクションを行うべき時であるかを確認する。もしそうでなければ、この後の処理ステップは、ステップ１１０５に戻って追加的な書き込み（又は他の）コマンドを処理する。しかしながら、もし、図３のＳＳＤコントローラ３１０がガーベッジコレクションを行うべき時間であれば、この後、処理ステップはステップ１１３０に続けられ、図３のＳＳＤコントローラ３１０は、フォアグラウンド（Ｆｏｒｅｇｒｏｕｎｄ）動作又はバックグラウンド（Ｂａｃｋｇｒｏｕｎｄ）動作の何れかとしてガーベッジコレクションを行う。後者の場合、ステップ１１２５における確認事項は、図３のＳＳＤコントローラ３１０がガーベッジコレクションをするための時が到来したか否かに関することよりも、むしろ、アプリケーションからのリード（ｒｅａｄ）及びライト（ｗｒｉｔｅ）リクエストに対して僅かな、又は最小限の影響しか与えずにガーベッジコレクションが進行できるレベルにまで活動が落ちたか否かに関することになる。
ステップ１１３０において、図７のガーベッジコレクションロジック７１５は、図５の消去ブロック５０５−２のような消去ブロックを識別する。ステップ１１３５において、図３のガーベッジコレクションロジック７１５は、図５の消去ブロック５０５−２内の有効データを識別する。そして、ステップ１１４０において、図７のガーベッジコレクションロジック７１５は、図７の自動ストリーム検出ロジック４１５によって決定されたとおりに、図１０のストリームＩＤ１００５に基づいて選択された、消去ブロック５０５−２とは相異なる第２ブロック５０５−８に図５の有効データ５１０−３をプログラムする。処理ステップはこの後、他の書き込み（又は他の）コマンドを処理するステップ１１０５に戻る。又は、他に消去すべきブロックがある場合はその消去ブロックを識別するステップ１１３０に戻る（図示せず）。
【００７０】
注意深い読者は、図１１に図示された例示的な手順が消去ブロックを消去すること自身に関して陳述しなかった点に気付くであろう。これは、消去動作のタイミングは本発明の実施例に依存して変化できるためである。消去動作は、図１２に図示され、後述される。
【００７１】
図１２は、本発明の一実施例によって、ガーベッジコレクションの間、図５の消去ブロック５０５−２内の図５の有効データ５１０−３（正確には、「ページ５１０−３に格納された有効データ」であるが、以下、簡略に「有効データ５１０−３」という）を、該選択された第２ブロック５０５−８のフリーページにプログラムする（書き込む）ための例示的な手順のフローチャートを図示した図面である。図１２は実際に、プログラム動作を行う二つの異なる接近法を説明する。本発明の一実施例の場合、ステップ１２０５において、図８のライト（ｗｒｉｔｅ）リクエストロジック８０５は、図７のＩ／Ｏキュー７１０にライト（ｗｒｉｔｅ）リクエストを配置する。実効的には、ステップ１２０５は、ライト（ｗｒｉｔｅ）リクエストのソースを除外して、図１１のステップ１１０５と同一である。その時点で、フリーページに図５の有効データ５１０−３を書き込む動作は、図１のマシン１０５上で走るアプリケーションに由来する書き込みとともに処理される。ステップ１２１０にて、図８の消去ロジック８１０は、この後、ライト（ｗｒｉｔｅ）リクエストが完了されることを待つか、又は、待たずに図５の消去ブロック５０５−２を消去する。
【００７２】
本発明の他の実施例の場合、ステップ１２１５において、図８のブロック選択ロジック８１５は、図７の自動ストリーム検出ロジック４１５から図１０のストリームＩＤ１００５を要請する。ステップ１２２０において、図８のブロック選択ロジック８１５は図１０のストリームＩＤ１００５に基づいてブロックを選択する。ステップ１２２５において、図８のプログラミングロジック８２０は、図５の有効データ５１０−３を選択されたブロックのフリーページに書き込む。その後、ステップ１２３０にて、図８の消去ブロック８１０が図５の消去ブロック５０５−２を消去する。
【００７３】
図１１及び図１２において、本発明の一部の実施例が図示される。但し、当業者は、本発明の他の実施例がステップの順序の変更、ステップの省略、及び／又は、図面に図示されてないリンクの追加により、尚、具現可能であることを認識するであろう。このような全てのフローチャートの変化は明示的な記述の有無に関わらず、本発明の実施例として見なされる。
【００７４】
次の記述は、本発明の或る一部の態様が具現できる適切な単数又は複数のマシンの簡略且つ一般的な説明を提供する意図がある。単数又は複数のマシンは、少なくとも部分的には、他のマシン、バーチャルリアリティー（ＶＲ）環境との相互作用、バイオ認識フィードバック、又は他の入力信号から受信された指示のみならず、キーボード、マウス等のような伝統的な入力装置からの入力によって制御される。ここで使用される「マシン」の用語は、単一マシン、仮想マシン、又は複数のマシン、複数の仮想マシン、又は共に動作する装置と通信的に結合されたシステムを広く含むように意図される。例示的なマシンは、例えば、自動車、汽車、タクシー等の個人的又は公的な運送手段のような運送装置のみならず、パーソナルコンピュータ、ワークステーション、サーバ、ポータブルコンピュータ、ハンドヘルド装置、電話、タブレットのようなコンピューティング装置を含む。
【００７５】
単数又は複数のマシンはプログラム可能か、又は、プログラム不可なロジック装置又はアレイ、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ）、組込み式（エンベデッド）のコンピュータ、スマートカード等のような組込み式（ｅｍｂｅｄｄｅｄ）のコントローラを含む。単数又は複数のマシンは、ネットワークインタフェース、モデム、又は他の通信的結合などを介して一つ以上の遠隔マシンとの一つ以上の連結を用いることができる。マシンはイントラネット、インタネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ）、  ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ）等のように、物理的及び／又は論理的ネットワーク方式により互いに連結できる。当業者は、ネットワーク通信がＲＦ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ）、衛星、マイクロ波、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）８０２．１１、Ｂｌｕｅｔｏｏｔｈ（登録商標）、光学、赤外線、ケーブル、レーザー等を含む様々な有線及び／又は無線の短距離又は長距離のキャリアとプロトコルを用い得ることを理解するであろう。
【００７６】
本発明の実施例は、機能、手順、データ構造、アプリケーションプログラム等を含む関連データと結合して、又は該関連データを参照して記述できる。該関連データはマシンによってアクセスされると、該マシンを、実作業を行うか、又は抽象的なデータ形式又は低いレベルのハードウェア文脈を定義するマシンに帰着する。関連するデータは、例えば、ＲＡＭ、ＲＯＭ等の揮発性及び／又は不揮発性メモリ、又はハードドライブ、フロッピーディスク、光学ストレージ、テープ、フラッシュメモリ、メモリスティック、デジタルビデオディスク、生物学的ストレージ等を含む他のストレージ装置、及びそれらの関連するストレージ媒体に格納できる。関連するデータはパケット、シリアルデータ、並列データ、伝播された信号等の形式で、物理的及び／又は論理的ネットワークを含む伝送環境を通じて移動できる。そして、関連するデータは、圧縮又は暗号化されたフォマットで使用できる。関連するデータは分離された環境で使用でき、マシンアクセスのために、ローカル及び／又は遠隔で格納されうる。
【００７７】
本発明の実施例は、一つ以上のプロセッサによって実行可能な命令語を含む類型の非一時的なマシン判読できる媒体を含むことができ、命令語は、ここで説明されるように、本発明の要素を行うための命令語を含むことができる。
【００７８】
図示された実施例を参照して、本発明の原理を説明及び図示したように、図示された実施例は、このような原理を逸脱しない詳細及び配列に変更されうるし、任意の方式に組み合わせることができる。上述の説明は、特定の実施例にフォーカシングされたが、他の構成が考慮されうる。特に、「本発明の実施例による」等の表現がここで使用されるが、このようなフレーズは、一般的に実施例の可能性を参考することを意味し、本発明の特定の実施例の構成を制限するものと意図されない。ここで使用されたように、このような用語は、他の実施例と組み合わせられる同一又は他の実施例を参考できる。
【００７９】
前もって図示された実施例は、本発明をそれによって制限するものと解釈されてはならない。たとえ、一部の実施例が説明されたとしても、当業者は、数々の変更が本発明の新たな教示及び長所から実質的に逸脱しない実施例にできることを容易に理解できるであろう。よって、このような全ての変更は、請求項に定義されることによって、本発明の範囲内に含まれるものと意図される。
【００８０】
結論的に、ここで説明された実施例に対する置き換えの多様性の観点で、このような詳細な説明及び添付資料は、単純に図示的なものと意図され、本発明の範囲を制限するものと受け入れられてはならない。よって、本発明で請求されたものは、下記の請求項及びその均等物の範囲及び思想内に有り得るこのような全ての変更である。
【産業上の利用可能性】
【００８１】
本発明は、改善されたガーベッジコレクションによってソリッドステートドライブ、ストレージ媒体及びその動作方法において有用である。
【符号の説明】
【００８２】
１０５      マシン
１１０      プロセッサ
１１５      メモリ
１２０      ソリッドステートドライブ（ＳＳＤ）
１２５      メモリコントローラ
１３０      装置ドライバ
２０５      クロック
２１０      ネットワークコネクタ
２１５      バス
２２０      使用者インタフェース
２２５      入出力（Ｉ／Ｏ、Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）エンジン
３０５      ホストインタフェースロジック
３１０      ＳＳＤコントローラ
３１５−１〜３１５−８      フラッシュメモリチップ
３２０−１〜３２０−４      チャンネル
３２５      フラッシュ変換階層
４０５−１〜４０５−４      ライトリクエスト
４１０、４１０−１〜４１０−４      論理ブロックアドレス（ＬＢＡ）
４１５      自動ストリーム検出ロジック
４２０−１〜４２０−４      ストリーム識別子（ストリームＩＤ）
５０５−１〜５０５−１０      ブロック、消去ブロック
５１０−１〜５１０−４、５１５−１〜５１５−４      ページ
５１０−３      （ページ４１０−３に格納された）有効データ
５１５−１〜５１５−４      フリーページ
６０５      属性の集合
６１０      アプリケーションＩＤ
６１５      残余寿命
６２０      順次性
６２５      アップデート頻度
６３０      最新性
６３５      ライトサイズ
６４０      ライト時間
６４５      リード頻度
６４５      リード温度
７０５      レシーバ
７１０      入出力（Ｉ／Ｏ）キュー
７１５      ガーベッジコレクションロジック
８０５      ライト（ｗｒｉｔｅ）リクエストロジック
８１０      消去ロジック
８１５      ブロック選択ロジック
８２０      プログラミングロジック
１００５      ストリーム識別子（ＩＤ）１０１０−３      フリーページ
１１０５〜１１４０      ステップ
１２０５〜１２３０      ステップ
【図１】
2018185815.tif 000003
【図２】
2018185815.tif 000004
【図３】
2018185815.tif 000005
【図４】
2018185815.tif 000006
【図５】
2018185815.tif 000007
【図６】
2018185815.tif 000008
【図７】
2018185815.tif 000009
【図８】
2018185815.tif 000010
【図９】
2018185815.tif 000011
【図１０】
2018185815.tif 000012
【図１１】
2018185815.tif 000013
【図１２】
2018185815.tif 000014