(57)【要約】  ストレージデバイスに格納されるファイルまたは格納される予定のファイルが、ストレージデバイスに関連するファイルシステム構造において、廃棄不能または廃棄可能なもののいずれかとしてマーキングされる。各廃棄可能ファイルが、ファイルに関連させた廃棄優先度レベルを有する。パブリッシャファイルを格納することで、ユーザファイル用に確保されているストレージ使用量安全マージンが少なくならない場合にのみ、ストレージデバイスへのパブリッシャファイルの格納が許容される。ユーザファイルを格納することで、ストレージ使用量安全マージンが少なくなったとしても、ストレージデバイスへのユーザファイルの格納が許容されるが、このような場合、ストレージ使用量安全マージンが、ストレージデバイスから１つ以上の廃棄可能ファイルを取り除くことによって回復される。廃棄優先度レベルが所定の廃棄しきい値以上であれば、ストレージデバイスから廃棄可能ファイルが取り除かれる。
2012512462.tif 000002
【特許請求の範囲】
【請求項１】
ストレージデバイスを管理する方法であって、
ａ）ストレージデバイスの記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信するステップと、
ｂ）１つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングするステップであって、各ファイルをマーキングするステップが前記ストレージデバイスに関連するファイルシステムの構造において実行される、マーキングするステップと、
ｃ）前記ファイルシステムの構造における１つ以上のファイルをマーキングするステップに基づいて、前記ストレージデバイスの記憶領域において１つ以上のファイルの格納を管理するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記管理するステップは、（ｉ）廃棄可能なものとしてマーキングされた１つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、（ｉｉ）廃棄可能なものとしてマーキングされたすべてのファイルを取り除くことによって記憶領域を解放することと、（ｉｉｉ）ファイルのクラスタを低性能ストレージモジュールに再マッピングすることのうちのいずれか１つまたはそれらの組み合わせを含む方法。
【請求項３】
請求項１記載の方法において、
ｄ）マーキングされたファイルを前記ストレージデバイスに送信するステップをさらに含む方法。
【請求項４】
請求項１記載の方法において、
前記マーキングするステップは、ファイルに廃棄優先度レベルを割り当てることを含む方法。
【請求項５】
請求項４記載の方法において、
前記ファイルに廃棄優先度レベルを割り当てることは、（ｉ）マーキングされたファイルに対応するファイルアロケーションテーブルエントリのｍ最上位ビットに対応する値を設定するか、または（ｉｉ）前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって実行される方法。
【請求項６】
請求項５記載の方法において、
前記対応する値は、ファイルの属性である方法。
【請求項７】
請求項５記載の方法において、
前記ｍ最上位ビットの値は、前記マーキングされたファイルが廃棄不能であれば、０に設定され、前記マーキングされたファイルが廃棄可能であれば、１〜２m −１の値に設定される方法。
【請求項８】
請求項７記載の方法において、
前記ｍ最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルである方法。
【請求項９】
請求項７記載の方法において、
値「１」は最低優先度で廃棄可能ファイルを示し、値「２m −１」は最高優先度で廃棄可能ファイルを示す方法。
【請求項１０】
請求項４記載の方法において、
前記廃棄優先度レベルは、（ｉ）ファイルの予測使用法、（ｉｉ）ファイルの使用に関連する予測収入、（ｉｉｉ）ファイルの種類、（ｉｖ）ファイルのサイズ、（ｖ）前記ストレージデバイスにおけるファイルの場所、および（ｖｉ）ファイルの古さのうちのいずれか１つに応じて、マーキングされたファイルに割り当てられる方法。
【請求項１１】
請求項４記載の方法において、
ｄ）前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するステップをさらに含む方法。
【請求項１２】
請求項１１記載の方法において、
前記マーキングされたファイルの廃棄優先度レベルを更新するステップは、前記ストレージデバイスにファイルを格納する１つ以上の新しいリクエストから独立して実行される方法。
【請求項１３】
請求項１記載の方法において、
ｄ）前記ストレージデバイスに格納された廃棄可能ファイルが、廃棄しきい値以上の廃棄優先度レベルに対応付けされている場合、前記廃棄可能ファイルを前記ストレージデバイスから廃棄されるように廃棄しきい値を設定するステップをさらに含む方法。
【請求項１４】
請求項１記載の方法において、
ｄ）前記ストレージデバイスに新しいファイルを格納するリクエストを受信するステップと、
ｅ）所定のストレージ使用量安全マージンより大きな空き記憶空間が前記ストレージデバイスにあるかを評価し、このような記憶空間があれば、空き記憶空間に新しいファイルを格納するステップと、
ｆ）前記ストレージデバイス上の空き記憶空間が所定のストレージ使用量安全マージン以下であれば、（ｉ）削除可能な前記ストレージデバイス内の廃棄可能ファイルを探すステップと、（ｉｉ）このようなファイルが見つかれば、空き記憶空間を拡張するようにファイルを削除し、このようなファイルが見つからなければ、新しいファイルの格納をやめるステップと、
ｇ）拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きければ、前記拡張された空き記憶空間に新しいファイルを格納し、前記拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きくなければ、ステップｅ）およびｆ）を繰り返すステップと、
をさらに含む方法。
【請求項１５】
請求項１４記載の方法において、
廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、廃棄可能ファイルを削除する方法。
【請求項１６】
ストレージデバイスを管理するストレージアロケータであって、
前記ストレージデバイスおよび前記ストレージデバイスのホストとのインターフェイスとなる通信インターフェイスと、
前記ストレージデバイスと関連するファイルシステムを格納するためのメモリユニットと、
前記ストレージデバイスと前記関連するファイルシステムを管理するためのプロセッサと、を備え、
前記プロセッサは、（ｉ）前記ストレージデバイスの記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信し、（ｉｉ）１つ以上のファイルを廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ストレージデバイスの前記関連するファイルシステムの構造において実行され、かつ（ｉｉｉ）前記ファイルシステムの構造における１つ以上のファイルをマーキングすることに基づいて、前記ストレージデバイスの記憶領域において１つ以上のファイルの格納を管理するように構成されるストレージアロケータ。
【請求項１７】
請求項１６記載のストレージアロケータにおいて、
前記プロセッサは、マーキングされたファイルを前記ストレージデバイスに送信するようにさらに構成されるストレージアロケータ。
【請求項１８】
請求項１６記載のストレージアロケータにおいて、
ファイルを廃棄可能としてマーキングすることの一部として、前記プロセッサは、ファイルに廃棄優先度レベルを割り当てるようにさらに構成されるストレージアロケータ。
【請求項１９】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、（ｉ）マーキングされたファイルに対応するファイルアロケーションテーブルエントリのｍ最上位ビットに対応する値を設定するか、または（ｉｉ）前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって、前記マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項２０】
請求項１９記載のストレージアロケータにおいて、
前記プロセッサは、前記マーキングされたファイルが廃棄不能であれば、ｍ最上位ビットの値を０に設定し、前記マーキングされたファイルが廃棄可能であれば、１〜２m −１の値に設定するストレージアロケータ。
【請求項２１】
請求項２０記載のストレージアロケータにおいて、
値「１」は最低優先度で廃棄可能ファイルを示し、値「２m −１」は最高優先度で廃棄可能ファイルを示すストレージアロケータ。
【請求項２２】
請求項２０記載のストレージアロケータにおいて、
前記ｍ最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルであるストレージアロケータ。
【請求項２３】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ファイルの予測使用法に応じて、マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項２４】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項２５】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する１つ以上の新しいリクエストから独立して、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項２６】
請求項１７記載のストレージアロケータにおいて、
前記ストレージデバイスに格納されたファイルが、所定の廃棄しきい値以上の廃棄レベル優先度に関連付けされている場合、前記プロセッサは前記ファイルを削除するストレージアロケータ。
【請求項２７】
請求項１７記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、前記ストレージデバイスの空き記憶空間のサイズを評価するようにさらに構成され、
（ｉ）前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きければ、前記ストレージデバイスに新しいファイルを格納し、
（ｉｉ）前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きくなければ、拡張される空き記憶空間のサイズが所定のストレージ安全マージンより大きくなるように、空き記憶空間を拡張するために削除可能である前記ストレージデバイス内の１つ以上の廃棄可能ファイルを探し、このようなファイルを見つけると、見つけられたファイルを削除して、拡張された空き記憶空間に新しいファイルを格納し、このようなファイルが見つからなければ、新しいファイルの格納をやめるようにさらに構成されるストレージアロケータ。
【請求項２８】
請求項２７記載のストレージアロケータにおいて、
前記廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、前記ストレージデバイスから１つ以上の廃棄可能ファイルが削除可能であるストレージアロケータ。
【請求項２９】
ストレージシステムであって、
通信インターフェイスと、
ストレージデバイスに関連するファイルシステムを管理するためのストレージアロケータであって、前記ストレージデバイスの記憶領域に１つ以上のファイルの格納を管理するためのプロセッサを備えるストレージアロケータと、を備え、
前記プロセッサは、（ｉ）通信インターフェイスを介して、前記記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信し、（ｉｉ）１つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ファイルシステムの構造において実行され、かつ（ｉｉｉ）前記ファイルシステムの構造における１つ以上のファイルをマーキングすることに基づいて、前記記憶領域において１つ以上のファイルの格納を管理するように構成されるストレージシステム。
【請求項３０】
請求項２９記載のストレージシステムにおいて、
前記通信インターフェイスは、前記ストレージアロケータと一体であるストレージシステム。
【請求項３１】
請求項２９記載のストレージシステムにおいて、
前記ファイルの１つ以上を格納するための記憶領域を含むストレージデバイスをさらに備えるストレージシステム。
【請求項３２】
請求項２９記載のストレージシステムにおいて、
前記ストレージアロケータは、前記ファイルシステムを局所的に格納するためのメモリユニットをさらに含むストレージシステム。
【請求項３３】
請求項２９記載のストレージシステムにおいて、
ストレージデバイスおよび／または前記ストレージデバイスのホストをさらに備え、前記ストレージアロケータは、前記ストレージデバイスまたは前記ストレージデバイスのホストに存在するストレージシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ストレージデバイスに関し、さらに詳しく言えば、ストレージデバイスにおけるファイルを管理する方法およびデバイスに関する。
【背景技術】
【０００２】
不揮発性ストレージデバイスの使用が、携帯性、小型の物理的サイズ、および大記憶容量により、長年にわたって急増してきた。ストレージデバイスには、様々に設計されたものがある。「埋め込み型」として見なされるストレージデバイスもあり、埋め込み型とは、すなわち、ユーザが、ストレージデバイスが動作するホストデバイスからストレージデバイスを取り外すことができず、取り外しが想定されていないことを意味する。一方で、取り外し可能なストレージデバイスもあり、取り外し可能とは、すなわち、あるホストデバイスから（例えば、デジタルカメラから）ストレージデバイスを移動可能であり、またはあるストレージデバイスと別のものとを取り替えることができることを意味する。
【０００３】
ストレージデバイスに格納されたデジタルコンテンツは、ストレージデバイスのホストからのものでありうる。例えば、例示的なホストであるデジタルカメラは、画像をキャプチャし、その画像を対応するデジタルデータに変換する。次に、デジタルカメラは、共に動作するストレージデバイスにデジタルデータを格納する。ストレージデバイスに格納されたデジタルコンテンツはまた、リモートソースからのものであってもよく、すなわち、デジタルコンテンツは、例えば、データネットワーク（例えば、インターネット）や通信ネットワーク（例えば、携帯電話ネットワーク）を通してストレージデバイスのホストに送られ、ストレージデバイスのホストによってダウンロードされうる。リモートソースは、例えば、サービスプロバイダやコンテンツプロバイダであってもよい。以下、サービスプロバイダおよびコンテンツプロバイダを総称して「パブリッシャ」と呼ぶ。
【０００４】
ストレージデバイスのユーザは、メディアコンテンツまたはパブリッシャからの広告を要求することによって、積極的にメディアコンテンツおよび広告をダウンロードしうる。しかし、パブリッシャの中には、ユーザの許可を求めずに、ユーザにコンテンツを送信して収入増を試みるものがおり、場合によっては、このようなコンテンツがストレージデバイスにダウンロードされていることをユーザに悟られないようにすることもある。本願明細書において、ユーザの合意を得ずにパブリッシャがユーザに送信するコンテンツのことを「未承認コンテンツ」と呼ぶ。多くの場合、未承認コンテンツは、パブリッシャに料金を支払った後かまたは支払い義務が生じた後にユーザによって消費されるように意図されている。
【０００５】
パブリッシャは、未承認コンテンツをユーザのストレージデバイスにダウンロードすることで、ユーザが有料の未承認コンテンツを最終的に消費して、収入増につなげることを期待している。ユーザが有料コンテンツを消費することを期待しながら、ユーザの合意を得ずに、パブリッシャがストレージデバイスに未承認コンテンツを格納することは、メディアパブリッシング業界では「予測委託販売」として知られている概念である。しかし、未承認コンテンツは、ストレージデバイスのユーザが、その存在を知らずにまたは消費しようと思わなければ、ストレージデバイスに格納されたままでありうる。ストレージデバイスに未承認コンテンツを格納すると、ストレージデバイス上でユーザが利用可能な（すなわち、空いた）記憶空間が減るため、ユーザの視点から言えば、望ましくない。誰か他の人（すなわち、一部のパブリッシャ）が、ストレージデバイスの記憶空間の一部を占有しているために、ユーザ自身のコンテンツ（例えば、音楽ファイル）用のストレージデバイス空間が少なくなっていることや、未承認コンテンツを削除することで、占有されていた記憶空間を取り戻す必要があることにユーザが気づくこともありうる。
【発明の概要】
【０００６】
ユーザの記憶空間の一部を占有する問題への１つの部分的な解決策として、パブリッシャのウェブサイトをブロックするなどして、ストレージデバイスへのパブリッシャのアクセスをブロックする方法がある。この解決策は、ユーザにとって許容可能な場合もあるが、パブリッシャにとっては売り上げが落ち、潜在的な収入源を失ってしまうため、パブリッシャの立場からすると問題である。この問題に対する別の部分的解決策として、コンテンツをホストにパブリッシングし（すなわち、これらのホストのストレージデバイスにコンテンツファイルを格納し）、コンテンツが無関係になるとコンテンツを取り除く方法がある。言い換えれば、コンテンツの出所であるパブリッシャは、コンテンツが無関係になると、格納された未承認コンテンツをストレージデバイスから取り除く。未承認コンテンツは、コンテンツ消費時間が経過するか、またはユーザがコンテンツを消費しそうにないことが見受けられると、無関係なものとして見なされる。
【０００７】
以上のことから、未承認ファイルの問題を解消することが必要とされている。詳細には、パブリッシャが、商取引の過程で未承認コンテンツをストレージデバイスへダウンロードしようとすることは許可されるべきであるが、これらのダウンロードは、ユーザ経験を著しく抑制する影響をもつものであってはならない。
【０００８】
したがって、ストレージデバイスに未承認コンテンツを収容するのに必要な記憶空間が、ユーザファイルに要求されない限り、ストレージデバイスに未承認ファイルを格納し、ユーザファイルの空き記憶空間の最小サイズを確保するために、ストレージデバイスから未承認ファイルを取り除くことが可能であることは有益でありうる。様々な実施形態がこのようなファイル管理を実施するように設計され、本願明細書においてそれらの例をいくつか提供する。
【０００９】
前述した問題を解消するために、ストレージデバイスに格納されたファイルまたは格納予定のファイルは、ストレージデバイスに関連づけられたファイルシステムの構造において、廃棄不能なものまたは廃棄可能なもののいずれかとしてマーキングされる。マーキングされた各ファイルは、ファイルに関連づけられた廃棄優先度レベルを有する。ストレージデバイスにファイルを格納しても、ユーザファイル用に確保されているストレージ使用量安全マージンが所定のマージンを超えて、少なくなることがない場合にのみ新しいパブリッシャファイル（すなわち、未承認ファイル）をストレージデバイスに格納することが許容される。一方で、ユーザファイルは所定の幅を超えてストレージ使用量安全マージンを少なくしたとしても、ストレージデバイスに格納されうる。しかし、このような場合、ストレージ使用量安全マージンの所定の幅は、１つ以上の廃棄可能ファイルをストレージデバイスから取り除くことによって回復する。廃棄優先度レベルが、所定の廃棄しきい値に等しいか、またはこのしきい値より高ければ（または本願明細書において説明するように、低ければ）、廃棄可能ファイルがストレージデバイスから取り除かれる。
【００１０】
さまざまな例示的な実施形態が、限定的なものではないという目的で、添付の図面に例示される。簡潔かつ明確に示すために、以下に参照される図面に示す要素は、必ずしも一定の縮尺で描かれたものではないことに留意するべきである。また、適切であると考慮される場合、参照番号は、同様の対応する要素または類似した要素を示すために図面において繰り返されることもある。
【図面の簡単な説明】
【００１１】
【図１】例示的な実施形態によるストレージシステムのブロック図である。
【図２】別の例示的な実施形態によるストレージシステムのブロック図である。
【図３】例示的な実施形態によるストレージアロケータのブロック図である。
【図４】例示的な実施形態によるファイルを管理する方法を示す図である。
【図５】例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルのストレージを管理する方法を示す図である。
【図６】例示的な実施形態によるＦＡＴ３２形式ファイルシステムにおける１つ以上の未承認ファイルをマーキングする方法を示す図である。
【図７】ＦＡＴ３２テーブルに関連づけられた例示的なディレクトリ領域を示す図である。
【図８】例示的な実施形態によるＦＡＴ３２テーブルを示す図である。
【図９】例示的な実施形態によるＮＴＦＳテーブルを示す図である。
【図１０】例示的な実施形態によるＦＡＴベースのファイルシステムの論理イメージを示す図である。
【図１１】本願明細書における開示によるファイルの格納を管理する方法を示す図である。
【発明を実施するための形態】
【００１２】
以下の記述は、例示的な実施形態のさまざまな詳細を提供する。しかし、この記述は、特許請求の範囲を限定することを意図したものではなく、本発明のさまざまな原理およびその実行方法を説明するためのものである。
【００１３】
未承認コンテンツおよび関連する問題を解消するために、ユーザファイルは、他のファイルより高いストレージ優先度が与えられ、この優先度を確保するために、ストレージ使用量安全マージンが維持される。「ユーザファイル」とは、ストレージデバイスのユーザが、積極的に格納したファイルや、ストレージデバイスへの格納を承認したファイルである。例えば、ユーザが自らのストレージデバイスにダウンロードする音楽ファイルは、ユーザファイルと見なされる。ユーザによってリクエストまたは格納許可が出されているため、ユーザファイルは、「承認」ファイルと見なされる。
【００１４】
「他のファイル」は、本願明細書において、「パブリッシャファイル」および「未承認ファイル」として参照される。「パブリッシャファイル」とは、ユーザがファイルをリクエストしていないのにストレージデバイスに格納されたファイルや、ユーザが、少なくとも、短時間ではない間、ファイルの格納に気がつかずに格納されたファイルのことである。ユーザは、未承認ファイルの使用を望まないこともある。使用されない未承認ファイルは、ユーザのストレージデバイスの貴重な記憶空間を消費する傾向にある。したがって、本願明細書に開示された原理によれば、このようなファイルは、ファイルを格納してもストレージ使用量安全マージンを少なくしない場合にのみ、ストレージデバイスへの格納が許可される。先々のユーザファイル用の格納空き記憶空間（すなわち、ストレージ使用量安全マージン）を維持することによって、ユーザファイルにストレージ優先度が与えられる。ストレージ使用量安全マージンは、要求または所望されれば、ストレージデバイスにユーザファイルが格納可能であることを確保するために維持される必要がある。
【００１５】
何らかの理由で、ストレージ使用量安全マージンが所定のものより少なくなれば、ストレージ使用量安全マージンを回復させるために、ストレージデバイスから１つ以上の未承認ファイルが取り除かれる（すなわち、削除される）。ストレージ使用量安全マージンを維持することで、追加のユーザファイルをストレージデバイスにダウンロードするための記憶空間が確保される。このため、未承認ファイルは、ストレージファイルシステムの構造において「廃棄可能」なものとしてマーキングされ、要求されれば、少なくともストレージ使用量安全マージンを維持するのに要求された空き記憶空間を取り戻すために後で取り除かれる。
【００１６】
ユーザがさまざまな廃棄可能ファイルを使用する可能性は、廃棄可能ファイルごとに異なるため、ファイルの使用の確率、ファイルの使用に関連する考えられる収入、ファイルサイズ、ファイルの種類、ファイルの場所、ファイルの古さなどの１つ以上の基準に応じた廃棄優先度レベルが、事前に、各未承認ファイル（すなわち、各廃棄可能ファイル）に割り当てられる。例えば、廃棄優先度レベルは、収入の可能性によって決定されてもよい。別の例によれば、映画の予告編や広告は、一般に、ユーザが予告編や広告の視聴を好まないため、実際の映画より高い廃棄優先度を有しうる。別の例によれば、ユーザによって最も使用されがちな１つ以上の廃棄可能ファイルには、最低廃棄優先度レベルが割り当てられ、すなわち、このようなファイルは、ストレージデバイスから最も取り除かれないファイルである。言い換えれば、使用確率が高いほど、ファイルに割り当てられる廃棄優先度レベルのレベルが低い廃棄可能ファイルとなる。１つ以上の廃棄可能ファイルを取り除いても、所定のストレージ使用量安全マージンが完全に回復していなければ、所定のストレージ使用量安全マージンが回復されるまで、ストレージデバイスから追加の廃棄可能ファイルが取り除かれる。
【００１７】
簡潔に言えば、ファイルシステムが、コンピュータファイルを格納し体系化するための手法を実施する。ファイルシステムは、データの格納、階層的体系化、操作、ナビゲーション、アクセス、および検索のために実施される抽象データ型およびメタデータのセットを含む。抽象データ型およびメタデータはコンピュータファイル（本願明細書において、簡潔にするために「データファイル」または「ファイル」と称する）のアクセス、操作、および起動が可能な「ディレクトリツリー」を形成する。「ディレクトリツリー」は、典型的に、ルートディレクトリおよび任意のサブディレクトリを含む。ディレクトリツリーは、１つ以上の「ディレクトリファイル」としてファイルシステムに格納される。ファイルシステムに含まれるメタデータおよびディレクトリファイルのセットは、本願明細書において、「ファイルシステム構造」と呼ばれる。したがって、ファイルシステムは、データファイルのアクセス、操作、更新、削除、および起動を行いやすいようにするデータファイルおよびファイルシステム構造を含む。
【００１８】
ファイルアロケーションテーブル（「ＦＡＴ」）は、例示的なファイルシステム構成である。ＦＡＴファイルシステムは、ＤＲ−ＤＯＳ、ＯｐｅｎＤＯＳ、ＭＳ−ＤＯＳ、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ（登録商標）などを含むさまざまなオペレーティングシステムで使用される。ＦＡＴ形式のファイルシステムは、どの記憶領域が空いているかまたは割り付けられているか、各ファイルがストレージデバイスのどこに格納されているかについての情報を集めたテーブルを使用する。テーブルのサイズを制限するために、記憶空間が「クラスタ」と呼ばれる連続するセクタグループ中のファイルに記憶空間が割り当てられる。ストレージデバイスの進化に伴い、クラスタの最大数も増大し、クラスタを識別するために使用されるビット数も増大してきた。ＦＡＴ形式のバージョンは、テーブルビット数に由来し、例えば、ＦＡＴ１２は１２ビットを使用し、ＦＡＴ１６は１６ビットを使用し、ＦＡＴ３２は３２ビットを使用する。
別のファイルシステム構成は、ニューテクノロジーファイルシステム（「ＮＴＦＳ」）として知られている。現在では、ＮＴＦＳが、Ｗｉｎｄｏｗｓ  ＮＴを始め、それ以降のバージョンのＷｉｎｄｏｗｓ  ２０００、Ｗｉｎｄｏｗｓ  ＸＰ、Ｗｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００３、Ｗｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００８、およびＷｉｎｄｏｗｓ  Ｖｉｓｔａの標準的なファイルシステムである。ＦＡＴ３２およびＮＴＦＳは、ストレージデバイス１００と共に提供されうる例示的なファイルシステムである。
【００１９】
図１は、典型的なストレージデバイス１００を示す。ストレージデバイス１００は、ユーザファイルまたはパブリッシャファイルでありうる様々なタイプのファイル（例えば、音楽ファイル、ビデオファイルなど）を格納するための記憶領域１１０を含む。ストレージデバイス１００はまた、データおよび制御ライン１３０を介して記憶領域１１０を管理するストレージコントローラ１２０を含む。ストレージコントローラ１２０はまた、ホストインターフェイス１５０を介してホストデバイス１４０との通信を行う。ホストデバイス１４０は、専用ハードウェアまたは汎用コンピューティングプラットフォームであってもよい。
【００２０】
記憶領域１１０は、例えば、ＮＡＮＤフラッシュの種類のものであってもよい。ストレージコントローラ１２０は、例えば、「読み出し」、「書き込み」、および「消去」動作、ウェアレベリングなどを制御することによって、さらには、ホスト１４０との通信を制御することによって、記憶領域１１０へのデータ転送／記憶領域１１０からのデータ転送およびホストデバイス１４０へのデータ転送／ホストデバイス１４０からのデータ転送のすべてを制御する。記憶領域１１０は、例えば、ユーザファイルおよびパブリッシャファイル、認証ホストデバイスによってのみ使用可能な保護データ、およびストレージコントローラ１２０によって内部のみで使用されるセキュリティデータを含んでもよい。ホスト（例えば、ホスト１４０）は、記憶領域１１０に直接アクセスできない。すなわち、例えば、ホスト１４０が、ストレージデバイス１００からのデータを要求するかまたは必要とすれば、ホスト１４０は、ストレージコントローラ１２０からデータをリクエストする必要がある。ストレージデバイス１００に格納されたデータファイルへのアクセスを容易に行うために、ストレージデバイス１００には、ファイルシステム１６０が設けられる。
【００２１】
記憶領域１１０は、３つの部分、すなわち、ユーザ領域１７０、パブリッシャ領域１８０、および空き記憶空間１９０に機能的に分割される。ユーザ領域１７０は、ユーザファイルが格納される記憶領域１１０内の記憶空間である。パブリッシャ領域１８０は、パブリッシャファイルが格納される記憶領域１１０内の記憶空間である。空き記憶空間１９０は、記憶領域１１０内の空いている記憶空間である。空き記憶空間１９０は、ユーザファイルまたはパブリッシャファイルを保持するために使用されうる。空き記憶空間１９０にユーザファイルを格納すると、ユーザファイルを保持する記憶空間は、空き記憶空間１９０から取り去られ、ユーザ領域１７０に追加される。同様に、空き記憶空間１９０にパブリッシャファイルを格納すると、パブリッシャファイルを保持する記憶空間は、空き記憶空間１９０から取り去られ、パブリッシャ領域１８０に追加される。ユーザファイルまたはパブリッシャファイルが、記憶領域１１０から取り去られれば（すなわち、除去されれば）、空いた記憶空間は、空き記憶空間１９０に追加される（戻る）。
【００２２】
ストレージデバイス１００のユーザは、空き記憶空間１９０のサイズが許容すれば、ホスト１４０から記憶領域１１０へユーザファイルをダウンロードできる。ダウンロードされたユーザファイルは、空き記憶空間１９０に格納され、前に説明したように、このファイルを保持する記憶空間は、空き記憶空間１９０から取り去られ、ユーザ領域１７０に追加される。前に説明したように、ユーザファイルは、他の（例えば、パブリッシャ）ファイルより高い優先度を有し、その優先度を確保するために、所定のストレージ使用量安全マージンが設定され、必要であれば、以下に記載する方法で回復される。
【００２３】
ホスト１４０は、空き記憶空間１９０の回復を行うためのストレージアロケータ１４４を含む。ストレージアロケータ１４４は、ハードウェア、ファームウェア、ソフトウェア、またはこれらの任意の組み合わせであってもよい。一般に、ストレージアロケータ１４４は、ホスト１４０との間で通信されるファイル（例えば、ファイル１４２）が、ユーザファイルであるのかまたはパブリッシャファイルであるのかを決定し、次に、それに応じて（すなわち、廃棄不能ファイルまたは廃棄可能ファイルとして）通信されたファイルをマーキングする。
【００２４】
ストレージアロケータ１４４が、ホスト１４０との間で通信されるファイル（例えば、ファイル１４２）が廃棄不能、例えばユーザファイルであることを決定すれば、ストレージアロケータ１４４は、通常の方法で記憶領域１１０にファイルを格納する。前に説明したように、廃棄不能ファイルを保持する記憶領域１１０内の記憶空間は、ユーザ領域１７０に追加されるか、またはユーザ領域１７０の一部である。しかし、ホスト１４０との間で通信されるファイルが、例えばパブリッシャファイルであるために廃棄可能であるとストレージアロケータ１４４が決定すれば、ストレージアロケータ１４４は、ファイルを廃棄可能なものとしてマーキングする。また、空き記憶空間１９０が所定のストレージ使用量安全マージンより大きければ、ストレージアロケータ１４４は、空き記憶空間１９０にマーキングされた廃棄可能ファイルを格納し、前に説明しれたように、廃棄可能ファイルを保持する空き記憶空間１９０内の記憶空間は、空き記憶空間１９０から取り去られ（すなわち、空き記憶空間は低減され）、パブリッシャ領域１８０に追加される（この追加は、廃棄可能ファイル１８２として論理的に示される）。
前に説明したように、パブリッシャファイルがユーザによって使用されうる可能性は、パブリッシャファイルごとに異なりうるため、使用可能性ができるだけ低いパブリッシャファイルは、記憶領域１１０から取り除く最初の候補となる。したがって、ファイルを廃棄不能または廃棄可能としてマーキングすることに加えて、ストレージアロケータ１４４は、記憶領域１１０への廃棄可能ファイルの格納前、格納と同時、または格納後に、各廃棄可能ファイルに廃棄優先度レベルを割り当てる。
【００２５】
ファイルを廃棄不能または廃棄可能としてマーキングし、ストレージアロケータ１４４によって廃棄優先度レベルを割り当て、かつストレージデバイス１００のファイルシステム１６０（またはそのイメージ）を使用することによって、ストレージアロケータ１４４は、記憶領域１１０におけるユーザファイルおよびパブリッシャファイルの数、ならびに記憶領域１１０内のファイルサイズおよび論理場所を「知る」。この情報（すなわち、ファイルの数、サイズ、および場所）を、特に、１つ以上のマーキングされたファイルに基づいて知ることで、ストレージアロケータ１４４は、記憶領域１１０を管理し、記憶領域１１０の承認および未承認ファイルの格納を管理する。記憶領域１１０を管理するかまたは記憶領域１１０におけるファイルの格納を管理することは、例えば、廃棄可能としてマーキングされた１つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、廃棄可能としてマーキングされたすべてのファイルを取り除くことで記憶領域を解放することと、ファイルのクラスタを性能がより低いストレージモジュールに再マッピングすることとを含んでもよい。記憶領域１１０または記憶領域に格納されたファイルを管理することが、記憶領域１１０または記憶領域１１０に格納されたファイルの他の態様、追加の態様、または別の態様を管理することを含んでもよい。
【００２６】
ストレージアロケータ１４４はまた、先々のユーザファイル用に元々保存されていた空き記憶空間を回復する（すなわち、所定のストレージ使用量安全マージンを回復する）ために、各廃棄可能ファイルに割り当てられた廃棄レベルによって、廃棄可能なまたは廃棄すべき（すなわち、記憶領域１１０から削除または取り除かれる）廃棄可能ファイルの順番を知る。したがって、ユーザが、記憶領域１１０に新しいユーザファイルを格納したいが、そのユーザファイルを収容するための十分な空き容量空間がなければ（すなわち、ストレージ使用量安全マージンが所定のものより少ないことを意味する）、ストレージアロケータ１４４は、廃棄可能ファイルに割り当てられた廃棄優先度レベルを使用して、所定のストレージ使用量安全マージンが完全に回復するまで、より多くの空き記憶空間を取り戻す（すなわち、空き記憶空間１９０を拡張する）ために、廃棄可能ファイルを１つずつ繰り返し削除する。前に説明したように、完全に回復されたストレージ使用量安全マージンは、先々のユーザファイル用に十分な空き記憶空間が確保される可能性が高い。廃棄可能ファイルは、ユーザが格納した廃棄可能ファイルをいずれ使用したいと思うかもしれないということが考慮されているため、新しいユーザファイルを格納するリクエストの受信にのみ応答して、ストレージデバイス１００から取り除かれるかまたは削除され、したがって、廃棄可能ファイルは、そのファイルを収容する記憶空間が新しいユーザファイルに要求される場合のみ、ストレージデバイスから取り除かれる。ストレージアロケータ１４４は、ホスト１４０に埋め込まれるかまたは組み込まれてもよく、あるいはホスト１４０（四角形の破線）およびストレージデバイス１００の外部に存在してもよい。
【００２７】
ストレージアロケータ１４４は、ストレージデバイス１００またはそれに関連するファイルシステムの典型的なイメージを有する。ストレージアロケータ１４４は、ファイルを廃棄不能または廃棄可能としてマーキングし、各廃棄可能ファイルに廃棄レベルを割り当てるために、ストレージデバイスのファイルシステムイメージを使用する。異なるファイルシステムが異なる構造を有するため、ファイルのマーキング（すなわち、廃棄不能または廃棄可能なものとして）および廃棄レベルの割り当ては、図６〜図１０に詳しく述べるように、以下に記載される使用されたファイルシステム構造に適応される。
【００２８】
図２は、別の例示的な実施形態による携帯可能なストレージデバイス２００のブロック図である。ストレージコントローラ２２０は、ストレージコントローラ１２０のように機能し、ストレージアロケータ２４４は、ストレージアロケータ１４４のように機能する。ストレージアロケータ２４４は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組み合わせであってもよい。ストレージアロケータ２４４は、ストレージコントローラ２２０と内部的に協働する。ストレージコントローラ２２０が、ホスト２４０から記憶領域２１０にファイルを格納するための格納要求を受信すると、ストレージコントローラ２２０は、格納リクエストをストレージアロケータ２４４に知らせ、ストレージアロケータ２４４は、ストレージデバイス２００に関連するファイルシステムの構造において廃棄不能または廃棄可能としてファイルをマーキングする。新しいファイルが廃棄可能であるとストレージアロケータ２４４が決定すれば、ストレージアロケータ２４４は、ファイルの使用確率に応じて、廃棄優先度レベルを新しいファイルに割り当てる。次に、ストレージアロケータ２４４は、空き記憶空間２９０の現在のサイズを評価し、新しいファイルのためのスペースを空けるために、記憶領域２１０から１つ以上の廃棄可能ファイルを取り除かれなければならない（すなわち、削除しなければならない）。１つまたは複数の廃棄可能ファイルが、ストレージデバイスから取り除かれるべきであれば、ストレージアロケータ２４４は、どのファイルが現在の取り除かれるべき候補ファイルであるかを決定する。次に、ストレージアロケータ２４４は、記憶領域２１０から取り除かれるべき廃棄可能ファイルをストレージコントローラ２２０に通知し、この通知に応答して、ストレージコントローラ２２０は、ストレージアロケータ２４４によって識別された１つまたは複数の廃棄可能ファイルを取り除く。携帯可能なストレージデバイス２００のいくつかの構成において、ストレージアロケータ２４４は、ストレージコントローラ２２０と記憶領域２１０との間に機能的に配置されてもよい。ストレージアロケータ２４４が、ストレージコントローラ２２０と記憶領域２１０との間に機能的に配置される構成において、ストレージアロケータ２４４または記憶領域２１０は、ストレージコントローラ２２０の機能の一部を想定する必要がある。このような構成において、記憶領域２１０は、フラッシュＮＡＮＤプロトコルより高いレベルで通信するメモリユニットで構成される。
【００２９】
図３は、例示的な実施形態によるストレージアロケータ３００のブロック図である。ストレージアロケータ３００は、メモリユニット３１０と、プロセッサ３２０と、インターフェイス３３０とを含む。メモリユニット３１０は、（例えば、図２のストレージデバイス２００）に関連するファイルシステム構造ストレージデバイスまたはファイルシステム構造のイメージを保持してもよい。プロセッサ３２０は、ストレージデバイスに関連するファイルシステムを管理する。インターフェイス３３０は、図１に示すように、ホストと協働し、ストレージデバイスのストレージコントローラと協働するように適応されてもよく、あるいは、図２に示すように、ストレージデバイスのストレージコントローラのみと協働するように適応されてもよい。
【００３０】
プロセッサ３２０は、ストレージデバイスの記憶領域にファイルを格納し、ストレージアロケータ３００が動作するストレージデバイスに関連するファイルシステムの構造において、ファイルを廃棄可能または廃棄不能なものとしてマーキングするために、インターフェイス３３０を介してリクエストを受信するように構成または適応される。インターフェイス３３０が、図２のストレージコントローラ２２０に機能的に取り付けられ（ひいては、例えば、ファイルレベルコマンドではなく、ＳＣＳＩまたはＵＳＢ／ＭＳＣラップコマンドを受信すれば）、受信したリクエストは、ファイルレベルよりかなり低いレベルにある。すなわち、受信したリクエストは、ホストによって適切に解釈される場合、ファイルに対応する論理ブロックアドレスでセクタを格納するリクエストでありうる。ストレージコントローラ２２０が、ＮＶＭＨＣＩプロトコル、またはＮＦＳや同様のプロトコルなどのネットワーキングファイルシステムプロトコルをサポートすれば、ストレージコントローラ２２０は、ファイルレベルのリクエストを取得しうる。したがって、ストレージコントローラ２２０などのストレージコントローラと、インターフェイス３３０などのインターフェイスとの間の通信は、ＮＶＭＨＣＩの実施例やＮＶＭＨＣＩと同様な実施例に限定されない。通信インターフェイス３３０は、図３に示すように、ストレージアロケータ３００の一部をなすものであってもよい。
【００３１】
プロセッサ３２０は、マーキングされたファイルをストレージデバイスに送信するようにさらに構成または適応され、ファイルを廃棄可能としてマーキングすることは、廃棄優先度レベルをファイルに割り当てることを含む。ストレージデバイスによって使用されるファイルシステムが、ＦＡＴベースのものであれば、プロセッサ３２０は、対応する値を、マーキングされたファイルに対応するＦＡＴにおいて最上位のｍビット（すなわち、最上位）（例えば、ｍ＝４）を設定することによって、マーキングされたファイルに廃棄優先度レベルを割り当てる。ＦＡＴエントリにおいて最上位ビットに設定された対応する値またはＮＴＦＳディレクトリエントリに設定された値は、ファイルの属性であってもよく、あるいはファイルの属性に関係するものであってもよい。「属性」とは、テーブル内に格納されたコンテンツのタイプに関する情報を含むＦＡＴテーブルまたはＮＴＦＳテーブルのヘッダにあるメタデータタグまたは何らかのデータ構造を意味する。「広告」、「プレミアムコンテンツ」、「販売促進用の（無料）コンテンツ」は、ＦＡＴテーブルまたはＮＴＦＳテーブルに格納されてもよい例示的なタイプのコンテンツである。廃棄レベルを設定するための別の基準は、例えば、最終アクセスファイル、ファイルサイズ、ファイルタイプなどである。
【００３２】
ファイルのマーキング専用のＦＡＴ３２エントリの最上ビットの数ｍは、これらのビットが使用されないため、４以下であってもよい。加えて、使用されるビットが大きいほど、使用可能な廃棄優先度レベルが高くなる。例えば、３ビット（すなわち、ｍ＝３）を使用すると、８（２3 ＝８）廃棄優先度レベルが得られ、４ビット（すなわち、ｍ＝４）を使用すると、１６（２4 ＝１６）廃棄優先度レベルが得られる（すなわち、廃棄不能ファイルに割り当てられる廃棄優先度レベル「０」を含む）。言い換えれば、プロセッサ３２０は、マーキングされたファイルが廃棄不能であれば、ｍ最上位ビットの値を０に設定するか、あるいはマーキングされたファイルが廃棄可能であれば、１〜２m −１の値に設定する。廃棄優先度レベルは、マーキングされたファイルが、ストレージデバイスから廃棄可能であるのか、または廃棄されるべきなのかの優先度を示す。例えば、実施例に応じて、値「１」は、最低優先度または最高優先度のいずれかで廃棄可能ファイルであることを示すことが可能であり、値「２m −１」は、最高優先度または最低優先度のいずれかで廃棄可能ファイルをそれぞれ示すものでありうる。
【００３３】
プロセッサ３２０は、未承認ファイルがストレージデバイスのユーザによって使用される可能性または確率に関連して前に説明したように、ファイルの予測使用に応じて、廃棄優先度レベルをマーキングされたファイルに割り当ててもよい。プロセッサ３２０は、ストレージデバイスに新しいファイルを格納するリクエストがあるたびまたは各リクエストの受信に応答して、マーキングされたファイルの廃棄優先度レベルを更新してもよい。プロセッサ３２０は、ストレージデバイスにファイルを格納する１つ以上の新しいリクエストから独立して、所与のマーキングされたファイルの廃棄優先度レベルを更新してもよい。例えば、以前に高優先度のものであったファイルが、ある一定の時間間隔が経過した後に優先度が下げられてもよい。プロセッサ３２０は、ファイルが、所定の廃棄しきい値以上の廃棄優先度レベルに関連づけられていれば、ストレージデバイスに格納されたファイルを削除する。プロセッサ３２０は、ファイルの書き込みや追加の数に基づいて、またはストレージデバイスの空き記憶空間の予測使用や新しいパブリッシャファイルの利用可能性に応じて、廃棄しきい値を（再）設定してもよい。
【００３４】
メモリユニット３１０は、プロセッサ３２０がストレージデバイスに格納されたファイルに割り当てる廃棄優先度レベルを含む割り当てテーブル３４０を保持してもよい。加えて、割り当てテーブル３４０はファイルに割り当てられる廃棄優先度レベルにファイルを関連づけるファイルを識別するとともに、情報を保持してもよい。割り当てテーブル３４０は、廃棄しきい値をさらに保持してもよい。割り当てテーブル３４０に保持される情報により、プロセッサ３２０は、所定のストレージ使用量安全マージンを回復するために、ストレージデバイスから取り除くことが可能な１つまたは複数の廃棄可能ファイルを識別することができる。
【００３５】
ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、プロセッサ３２０は、ストレージデバイスの空き記憶空間（ｆ）のサイズを評価し、ストレージデバイスの空き記憶空間の評価サイズが所定のサイズより大きければ、または所定のサイズより大きくなければ、ストレージデバイスに新しいファイルを格納し、プロセッサ３２０は、削除可能であるストレージデバイス内にある１つ以上の廃棄可能ファイルを探し、１つまたは複数のこのようなファイルが見つかれば、プロセッサ３２０は、現在の空き記憶空間（ｆ）を拡張して、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるようにするために、１つまたは複数のファイルを削除する。１つまたは複数の廃棄可能ファイルは、廃棄可能ファイルに関連する廃棄優先度レベルが、所定の廃棄しきい値（例えば、１〜１５、例えば、１５）以上であれば、ストレージデバイスから削除可能である。
【００３６】
空き記憶空間が十分に拡張された後、プロセッサ３２０は、拡張された空き記憶空間に新しいファイルが格納されることを許容する。「空き記憶空間が十分に拡張される」とは、前述した所定のストレージ使用量安全マージンを少なくすることなく、全空き記憶空間が新しいファイルを収容可能になるまで、あるいは同様に、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるまで、またはすべての廃棄可能ファイルが取り除かれるまで、占有された記憶空間を１つずつ解放することによって、空き記憶空間を拡張することを意味する。
プロセッサ３２０は、標準的な既製のシステムオンチップ（「ＳｏＣ」）デバイスまたはシステムインパッケージ（「ＳｉＰ」）デバイス、あるいは実行時、本願明細書に記載するステップ、演算、および評価を実行する特殊なソフトウェアを備えた汎用処理ユニットでありうる。あるいは、プロセッサ３２０は、ハードウェアを使用することによって、本願明細書に記載するステップ、演算、および評価を実行する特定用途向け集積回路（「ＡＳＩＣ」）でありうる。
【００３７】
図４は、１つの例示的な実施形態による廃棄可能ファイルを格納する方法を示す。図４は、図１に関連して記載される。ステップ４１０において、ホスト１４０は、ストレージデバイス１００にファイル１４２を格納するリクエストを受信する。ステップ４２０において、ストレージアロケータ１４４は、ファイルを「廃棄可能」または「廃棄不能」としてマーキングし、ステップ４３０において、空き記憶空間１９０が十分に大きければ、マーキングされたファイルをストレージデバイス１００のストレージコントローラ１２０に送信する（すなわち、記憶領域１１０に格納するため）。また、廃棄優先度レベルがファイルに割り当てられるという意味でも、ファイルがマーキングされる。ステップ４４０において、ストレージアロケータ１４４は、（ストレージコントローラ１２０との通信により）記憶領域１１０を管理するか、あるいはマーキングされたファイルに基づいて、随意にすでにマーキングされていた１つ以上のファイルに基づいて、記憶領域１１０に格納されるファイルを管理する。
【００３８】
図５は、１つの例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルの格納を管理する方法を示す。図５は、図１に関連して記載される。新しいファイルは、ストレージデバイス１００に格納される候補である。ストレージデバイス１００のファイルシステム１６０の現在のイメージを知ることで、ストレージアロケータ１４４は、ステップ５１０において、空き記憶空間１９０の現在のサイズ「ｆ」を評価して、現在のサイズがｆである空き記憶空間１９０が、新しいファイル（すなわち、格納候補であるファイル）を収容可能であるかを確認する。一般に、ストレージアロケータ１４４が、新しいファイルを取り扱う方法は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかに依存する。したがって、ストレージアロケータ１４４は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかを最初に決定する。
【００３９】
新しいファイルがユーザファイルである場合
ステップ５２０において、ストレージアロケータ１４４は、空き記憶空間１９０が、新しいユーザファイルを収容できるかをチェックする。空き記憶空間１９０が、新しいユーザファイルを収容できれば（ステップ５２０において「Ｙ」で示す）、ストレージアロケータ１４４は、ステップ５６０において、所定のストレージ使用量安全マージンが、新しいユーザファイルの格納の可否によって少なくなるかに関係なく、空き記憶空間１９０に新しいユーザファイルを格納する。ストレージアロケータ１４４が、空き記憶空間１９０に新しいユーザファイルを格納した後、所定のストレージ使用量安全マージンが少なくなれば（すなわち、所定のストレージ使用量安全マージンに対して）、ストレージアロケータ１４４は、新しいユーザファイルの格納に対してさらなるアクションを起こさない。
【００４０】
しかし、ストレージアロケータ１４４が、空き記憶空間１９０に新しいユーザファイルを格納した後に、所定のストレージ使用量安全マージンが少なくなれば、ステップ５５０において、ストレージアロケータ１４４は、所定のストレージ使用量安全マージンを維持するために、格納された最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイル・・・などを以下同様に決定する追加のステップを含む。ストレージアロケータ１４４は、格納された廃棄可能ファイルに割り当てた廃棄レベルに基づいて、最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイルを決定する。
【００４１】
ステップ５２０において、空き記憶空間１９０が新しいユーザファイルを収容できないことをストレージアロケータ１４４が決定すれば（ステップ５２０において「Ｎ」と示す）、ステップ５３０において、空き記憶空間１９０と、廃棄可能ファイルによって消費されている記憶空間とを合わせれば新しいユーザファイルを格納するのに十分かどうかを、ストレージアロケータ１４４が決定する。記憶空間を組み合わせても不十分であれば（ステップ５３０において「Ｎ」と示す）、これは、削除される廃棄可能ファイルの数に関係なく、新しいユーザファイルを、そのファイルサイズにより、「非ユーザ」記憶領域に格納することができないということを意味する。組み合わせた記憶空間が十分であれば（ステップ５３０において「Ｙ」と示す）、ステップ５４０において、新しいユーザファイルに十分な記憶空間を解放するために、格納された廃棄可能ファイルの中から、どの廃棄可能ファイルが削除可能であるかをストレージアロケータ１４４が探す。前に説明したように、ストレージアロケータ１４４が、ストレージデバイスのファイルシステムにおいて廃棄不能または廃棄可能としてファイルをマーキングするために、ストレージデバイス１００のファイルシステムを使用することによって、これらの廃棄可能ファイルをストレージアロケータ１４４が探す。加えて、ストレージアロケータ１４４によってマーキングされたファイルに割り当てられた廃棄レベルは、各廃棄レベルが対応するマーキングされたファイルに関連づけられるように、ストレージデバイスのファイルシステムにも埋め込まれる。
廃棄可能ファイル（「ＤＦ」）であって、最初に廃棄すべき廃棄可能ファイル（以下、このファイルを「ＤＦ１」と呼ぶ）を見つけると、ストレージアロケータ１４４は、このファイルの記憶空間（以下、この記憶空間を「ＳＰ１」と呼ぶ）を記憶空間１９０に追加するかまたは戻すために、ファイルＤＦ１を削除する。
次に、ステップ５５０において、ストレージアロケータ１４４は、拡張された空き記憶空間１９０（すなわち、空き記憶空間１９０と最後に戻された記憶空間を足したもの、すなわち、ｆ＋ＳＰ１）が、新しいユーザファイルを収容可能であるかをチェックする。拡張された空き記憶空間１９０（すなわち、ｆ＋ＳＰ１）が、新しいユーザファイルを収容できないままであれば（ステップ５５０において「Ｎ」として示す）、ステップ５５０において、ストレージアロケータ１４４は、追加の記憶空間を空き記憶空間１９０に戻すために（すなわち、次に削除すべき廃棄可能ファイルを見つけて削除することによって）、ステップ５５０を反復して繰り返す（反復は５５５で示す）。
【００４２】
２番目に優先度が高い廃棄優先度の次の廃棄可能ファイルを見つけると（以下、次の廃棄可能ファイルを「ＤＦ２」と呼ぶ）、ストレージアロケータ１４４は、追加の記憶空間を空き記憶空間１９０に解放および追加するために（以下、追加の記憶空間を「ＳＰ２」と呼ぶ）、ファイルＤＦ２を削除する。次に、ステップ５５０において、ストレージアロケータ１４４は、拡張された空き記憶空間１９０（すなわち、空き記憶空間１９０と、最後に解放された２つの記憶空間を合わせたもの、すなわち、ｆ＋ＳＰ１＋ＳＰ２）が、新しいファイルを収容可能であるかを再度チェックする。拡張された空き記憶空間１９０（すなわち、ｆ＋ＳＰ１＋ＳＰ２）が、新しいファイルを収容できなければ（ステップ５４０において「Ｎ」として示す）、ストレージアロケータ１４４は、削除すべき次の廃棄ファイルを見つけるために、ステップ５４０をもう一度繰り返す。ストレージアロケータ１４４は、蓄積された空き記憶空間１９０が、新しいユーザファイルを収容できるまで、ステップ５４０および５５０を反復する（ステップ５５０において「Ｙ」として示す）。次に、ステップ５６０において、ストレージアロケータ１４４は、記憶領域１１０に新しいユーザファイルを格納する。
前述したように、ストレージアロケータ１４４が、空き記憶空間１９０に新しいユーザファイルを格納した後に、実際のストレージ使用量安全マージンが、所定のストレージ使用量安全マージンより少なくなれば、ステップ５６０は、ストレージアロケータ１４４が、所定のストレージ使用量安全マージンを回復するために、最初に削除すべき格納された廃棄ファイル、次に削除すべき格納された廃棄可能ファイル・・・などを以下同様に決定する際の追加のステップを含んでもよい。
【００４３】
新しいファイルがパブリッシャファイルである場合
新しいファイルがパブリッシャファイルであれば、ストレージアロケータ１４４は、所定のストレージ使用量安全マージンを少なくせずに、空き記憶空間１９０が新しいパブリッシャファイルを収容できる場合のみ、記憶領域１１０に新しいパブリッシャファイルを格納する（ステップ５６０）。すなわち、新しいパブリッシャファイルを格納すると、所定のストレージ使用量安全マージンが少なくなるならば、ストレージアロケータ１４４は、記憶領域１１０に新しいパブリッシャファイルを格納しないように決定してもよい。このような場合、ストレージアロケータ１４４は、そのパブリッシャファイルに対して何らのアクションをとらず、新しいパブリッシャファイル用の記憶空間を解放するためにストレージデバイスからファイルを削除することもない。あるいは、ストレージアロケータ１４４は、ステップ５４０において、廃棄優先度が低い廃棄可能ファイル用の記憶空間を解放するために、より優先度が高い１つ以上の廃棄可能ファイルを削除してもよい。前述したように、ストレージデバイス１００のファイルシステムにおいて、ファイルがマーキングされ、廃棄レベルが埋め込まれ、ファイルがマーキングされ、ファイルシステムに廃棄レベルが埋め込まれる方法は、使用するファイルシステムに依存または適応されうる。
【００４４】
図６は、１つの例示的な実施形態によるＦＡＴ３２形式のファイルシステムにおける未承認ファイルをマーキングする方法を示す。ＦＡＴ３２形式のファイルシステムは、クラスタを使用する。ＦＡＴ３２形式のファイルシステムに関連して前述したように、ＦＡＴ３２クラスタを識別するために使用されるビット数は、３２である。以下、図６は、図１に関連して記載される。
ステップ６１０において、ＦＡＴ３２の各クラスタの３２ビットのｍ最上位ビット（ｍ≦４）が、場合によって、廃棄不能または廃棄可能としてファイルをマーキングするように、さらには、各廃棄可能ファイルの対応する廃棄レベルを保持するように割り付けられるかまたは確保される。廃棄レベルのファイルへの割り当ては、対応する値をマーキングされたファイルに対応する割り付けられたｍビットに設定することによって行われる。
【００４５】
ステップ６２０において、ストレージアロケータ１４４は、ストレージデバイス１００のユーザが未承認ファイルを使用する可能性のレベルを評価する。ファイルを使用する可能性の評価は、委託販売ファイルに関して当業者に既知の様々な方法で実行されうる。例えば、ファイルを使用する可能性の評価は、ストレージデバイスの使用者がいる場所のモニタリング、および／またはモニタリングしたユーザのこれまでの経験や好みに基づいたものであってもよい。ファイルを使用する可能性の評価はまた、例えば、ＦＡＴテーブルまたはＮＴＦＳテーブル内に格納されるコンテンツのタイプ（例えば、「広告コンテンツ」、「プレミアムコンテンツ」、「販売促進用の（無料）コンテンツ」など）に基づいたものであってもよい。ストレージアロケータ１４４は、ファイルが使用される可能性を評価するための代替となるものまたはさらなる基準を用いてもよい。例えば、ストレージアロケータ１４４は、最新アクセスファイル、ファイルサイズ、ファイルタイプなどであってもよく、あるいはそれらに関連されうるファイルの属性または特性を使用してもよい。
ユーザが未承認ファイルを使用する可能性のレベルをストレージアロケータ１４４が評価した後、ストレージアロケータ１４４は、ステップ６３０において、未承認ファイルの評価された使用可能性レベルに対応する廃棄優先度レベルを割り当てる。未承認ファイルが、ストレージデバイス１００のユーザによって使用される可能性が高いほど、廃棄レベルは低い。
【００４６】
ｍが４ビットであれば、これは、廃棄スケールが、１（すなわち、０００１）〜１５（すなわち、１１１１）の１５の廃棄レベルを与えるということを意味する。すなわち、廃棄レベル０は、廃棄不能ファイルすべてに割り当てられ、廃棄レベル１は、最低廃棄優先度の廃棄可能ファイルに割り当てられ、廃棄レベル１５は、最高廃棄優先度の廃棄可能ファイルに割り当てられる。ストレージアロケータ１４４が、対応する廃棄レベルを未承認ファイルに割り当てた後、ストレージアロケータ１４４は、ステップ６４０において、１〜１５の対応する値を、未承認ファイルに関連するクラスタの４つの最上位ビットに設定する。未承認ファイルが、ファイルに関連した２つ以上のクラスタを有すれば、各クラスタの４つの最上位ビットは、同じ値に設定される。
ステップ６５０において、未承認ファイルが、評価を必要とする最後のファイルであるかがチェックされる。未承認ファイルが評価が必要な最後のファイルでなければ（ステップ６５０において「Ｎ」で示す）、前述した方法で別のファイルが評価される。未承認ファイルが評価を必要とする最後のファイルであれば（ステップ６５０において「Ｙ」で示す）、ステップ６４０において値が設定された各々に対してｍビットを有する（１つまたは複数の）未承認ファイルが、ストレージデバイスに送信される。
【００４７】
図７は、ＦＡＴ３２テーブルに関連する例示的なディレクトリテーブル７００を示す。ディレクトリテーブル７００は、説明に使用する部分的なテーブルにすぎず、したがって、ＦＡＴディレクトリエントリのすべてのフィールドを示しているものではない。ディレクトリ領域７００は、ファイル名、ファイルサイズ、関係する記憶空間において、各ファイルが始まる場所など、関係するファイルシステムに格納されるファイルの項目を保持する。ファイルの項目は、以下のフィールドに保持される。フィールド７１０は、関係するファイルシステムに格納されるファイルのディスクオペレーティングシステム（「ＤＯＳ」）ファイル名を保持し、フィールド７２０は、ファイルの拡張を保持し、フィールド７３０は、ファイルのさまざまな属性を保持し、フィールド７４０は、ファイルの先頭クラスタ番号（「ＦＣＮ」）の上位１６ビットワードを保持し、フィールド７５０は、ファイルの先頭クラスタ番号（「ＦＣＮ」）の下位を保持し、フィールド７６０は、ファイルサイズを保持する。各ＦＣＮ番号は、ファイルが見つけられうる第１の論理クラスタを示す。
【００４８】
ディレクトリ領域７００の最初のエントリは、「ＲＥＡＬＦＩＬＥ」（７７０と示す）と呼ぶ例示的なファイルの情報を保持する。ＲＥＡＬＦＩＬＥ７７０は、ファイル拡張子「ＤＡＴ」を有し、ＦＣＮは「００００  ０００２」であり（７５５と示す）、ファイルサイズは、「００００  ２４Ｅ４」である。テーブル７００の数字は、１６進数で示されている。規格の一部として、属性値「００」（７８０と示す）および「２０」（図７に図示せず）は、「通常」ファイルをさすのに対して、属性値「０２」は、ファイルシステム中の隠しファイルをさす。ファイル名「＼ｘＥ５Ｃｏｎｓｉｇｎ」は削除ファイルを示し、ここでの「＼ｘＥ５」は、ファイル名の最初のバイトの値が１６進数のＥ５であることを意味する。一例として、ＦＣＮ数００００  ０００２（７５５と示す）は、ファイルＲＥＡＬＦＩＬＥの最初のクラスタを示す。
【００４９】
図８は、１つの例示的な実施形態による例示的な部分的ＦＡＴ３２テーブル８００を示す。ＦＡＴ３２テーブル８００は、倍長語（「ＤＷＯＲＤ」）アレイとして示され、値は１６進数である。参照番号８１０は、ＦＡＴ３２テーブル８００を保持するタイプのデバイスを示し、ここで「Ｆ８」は、ハードドライブをさす。ＦＡＴ３２テーブル８００は、クラスタ＃１（８２０と示す）、クラスタ＃２（８２５と示す）・・・クラスタ＃２３（８３０と示す）として示された２３個のクラスタを含む。図８は、図７に関連して記載される。ＦＡＴ３２テーブル８００のクラスタは、ファイルの最初のクラスタであってもよく、あるいはファイルの次につながったクラスタを示してもよく、またはファイルの終わり（「ＥＯＦ」）を指し示すものであってもよい。
【００５０】
ディレクトリ領域７００を再度参照すると、ファイルＲＥＡＬＦＩＬＥ（７７０と示す）の最初のＦＣＮは、「００００  ０００２」（７５５と示す）であり、これは、図８のテーブル８００のクラスタ＃２をさす。図８に示すように、クラスタ＃２の値（すなわち、値「００００  ０００３」）は、次のファイルクラスタであるクラスタ＃３をさす（８４０と示す）。同様に、クラスタ＃３の値（すなわち、「００００  ０００４」）は、次のファイルクラスタであるクラスタ＃４をさす。クラスタ＃４は、値「０ＦＦＦ  ＦＦＦＦ」（「Ｆ」は、１０進数の「１５」を表す１６進数字である）を有し、ここで、「ＦＦＦ  ＦＦＦＦ」（８５０と示す）は、ファイルのＥＯＦ指示を示し、ゼロ値（８６０と示す）は、廃棄レベル０を示す。したがって、ファイルＲＥＡＬＦＩＬＥは、３つのクラスタと関連している（すなわち、クラスタ＃２、クラスタ＃３、およびクラスタ＃４）。
【００５１】
前に説明したように、廃棄レベル０が、廃棄不能ファイルに割り当てられる。特定のファイルの各クラスタの最上位１６進数字が、そのファイルに割り当てられた同一の廃棄優先度レベルに設定されることに留意するべきである。例えば、ファイルＲＥＡＬＦＩＬＥは、廃棄レベル「０」が割り当てられ、したがって、クラスタ＃２、＃３、および＃４の最上位１６進数字の各々が、この値を有する（すなわち、値「０」、「０」値には下線が引かれている）。別の例によれば、ＦＣＮが「００００  ０００５」（図７に示す）であるファイル「Ｅ５  Ｃｏｎｓｉｇｎ」には、廃棄優先度レベル「１」が割り当てられている。したがって、このファイルに関係するクラスタ＃５〜１２の各々の最上位１６進数字は、値「１」を有する（例えば、８７０と示す）。言い換えれば、本願明細書における開示によれば、最上位１６進数字（すなわち、換言すれば、特定の廃棄可能ファイルに関するクラスタの４つの最上位ビット）は、特定のファイルに割り当てられた廃棄優先度レベルに対応する同じ値に設定される。前に説明したように、廃棄優先度レベルを示すために使用される最上位ビットの数字ｍは、４とは異なるものであってもよい（すなわち、ｍ≦４）。
【００５２】
図９は、例示的な実施形態による例示的な部分的ＮＴＦＳテーブル９００を示す。ＮＴＦＳテーブル９００は、ファイル名、ファイルサイズなどのファイルの項目を保持する。ＮＴＦＳテーブル９００は、「普通の」データフローに応じて変化するファイルの「通常の」データ（例えば、データ９２０）を保持するためのデータフィールド９１０を含む。本願明細書における開示によれば、ＮＴＦＳテーブル９００はまた、各評価済みファイルの廃棄情報（例えば、廃棄情報９３０）を保持するための「廃棄情報」フィールド９１５を含む。また、廃棄情報フィールド９１５は、廃棄優先度レベル以外の情報を含んでもよい。例えば、廃棄情報フィールド９１５は、ファイルを供給したサーバおよびファイルを廃棄しなければいけない期限の満了時間に関する情報を含んでもよい。ＦＡＴベースのファイルシステムとは異なり、ＮＴＦＳベースのファイルシステムにおいて、廃棄可能ファイルに割り当てられた廃棄値は、ビットセットによって要求される最大数に制限されない。これは、廃棄値の範囲が自由に選択可能であることを意味する。例えば、廃棄値は、１〜２５の範囲のものでありうる。ＮＴＦＳは、例示的な非ＦＡＴファイルシステムである。一般に、対応する廃棄値は、マーキングされたファイルに対応する非ＦＡＴベースのファイルシステムエントリのデータフィールドに設定されてもよい。
【００５３】
図１０は、例示的な実施形態によるストレージデバイスのファイルシステム１０００の論理構成を示す。ストレージアロケータ（例えば、図１のストレージアロケータ１４４）は動作するストレージデバイスのファイルシステム１０００またはファイルシステム１０００のイメージのいずれかを保持するか、またはストレージアロケータはファイルシステム１０００へのアクセスを有してもよい。
ファイルシステム１０００は、ブートセクション１０１０と、ファイルシステム１０００に関連するＦＡＴ１０２０と、ディレクトリテーブル１０３０と、ファイル領域１０４０と、廃棄可能ファイル領域１０５０とを含む。ＦＡＴ１０２０は、廃棄可能ファイルの廃棄優先度レベルを含む廃棄可能ファイル割り付け領域１０２５を含む。ディレクトリテーブル１０３０は、ストレージデバイスに格納されるファイルであれば、どのファイル（すなわち、廃棄可能ファイルおよび／または廃棄不能ファイル）にでもアクセスするためのアクセス情報を含む。ファイル領域１０４０は、廃棄不能ファイルを含む。インデックスおよびデータベース領域１０４５は、廃棄可能ファイルのインデックスと、さらに、廃棄可能ファイルに関係するメタデータとを保持する。インデックスおよびデータベース領域１０４５に保持されるインデックスおよびメタデータは、廃棄レベルを算出するために使用されるが、実際の廃棄プロセス中には要求されない。廃棄可能ファイル領域１０５０は、廃棄可能ファイルを保持する。
【００５４】
図１１は、本願明細書における開示によるファイルを管理する方法を示す。図１１は、図１に関連して記載される。時間Ｔ０で、２つのユーザファイル（すなわち、ファイル「Ｆ１」および「Ｆ２」）が、記憶領域１１０に最初に格納されると仮定する。ファイル「Ｆ１」および「Ｆ２」は、ユーザファイルであるため、ユーザ領域１７０に格納され、ストレージアロケータ１４４によってファイルに割り当てられる廃棄レベルはゼロである。記憶領域１１０の全記憶容量がＴ（１１１０と示す）であり、ファイルＦ１およびＦ２が、ストレージデバイス１００に格納されるため、残りの空き記憶空間１９０（図１を参照）のサイズはｆ（１１２０と示す）である。パブリッシャが、記憶領域１１０に３つの未承認ファイルの格納を望むと仮定する。前述したように、記憶領域１１０にパブリッシャの３つの未承認ファイルを格納することで、先々のユーザファイル用に保存される所定のストレージ使用量安全マージン（１１３０と示す）が少なくならないかを決定するために、ストレージアロケータ１４４が、ストレージデバイス１００における空き記憶空間１９０（または１１２０のｆ）のサイズを評価する。パブリッシャの３つの未承認ファイルを確認することで、ストレージ使用量安全マージン１１３０（すなわち、所定のストレージ使用量安全マージン）が少なくなれば、ストレージアロケータ１４４は、これらのファイルの格納をやめる。
【００５５】
この例において、ストレージアロケータ１４４は、ストレージ使用量安全マージン１１３０を低減することなく、パブリッシャの３つの未承認ファイルが記憶領域１１０に格納可能であることを決定する。したがって、時間Ｔ１で、ストレージアロケータ１４４により、ストレージコントローラ１２０は、記憶領域１１０にパブリッシャの３つの未承認ファイルを格納できる。３つのパブリッシャの未承認ファイルは、「Ｐ１」、「Ｐ２」、および「Ｐ３」として示される。ストレージアロケータ１４４はまた、ストレージデバイス１００のユーザによってファイルＰ１、Ｐ２、およびＰ３が使用される確率を決定し、これらのファイルの各々に対応する廃棄レベルを割り当てる。次に、ストレージアロケータ１４４は、図８に示すようなＦＡＴテーブルまたは図９に示すようなＮＴＦＳテーブルにファイルに割り当てられた廃棄レベルを格納する。
【００５６】
時間Ｔ２で、ストレージデバイス１００のユーザは、記憶領域１１０に、３つ以上のファイル（すなわち、ファイル「Ｆ３」および「Ｆ４」）の格納を望む。ストレージアロケータ１４４は、追加のファイル（すなわち、ファイルＦ３およびＦ４）を格納するのに十分な格納空間が記憶領域１１０にあるかどうかを決定するために、ストレージデバイス１００における空き記憶空間１９０のサイズ（または１１２０のｆ）を再評価する。この例において、ストレージアロケータ１４４は、現在の空き記憶空間がファイルＦ３およびＦ４を収容可能であることを決定する。したがって、時間Ｔ２で、ストレージアロケータ１４４により、ストレージコントローラ１２０は、記憶領域１１０にファイルＦ３およびＦ４を格納できる。
【００５７】
ファイルＦ３およびＦ４がユーザファイルであるため、ストレージデバイス１００のユーザによってファイルＦ３およびＦ４が使用される確率は、ユーザファイルが、ユーザがファイルＦ３およびＦ４を使用するとしても、その回数に関係なく、パブリッシャファイルよりも高いストレージ優先度を有するため重要ではない。したがって、ストレージアロケータ１４４は、廃棄レベル「０」をファイルＦ３およびＦ４に割り当て、図８に示すようなＦＡＴテーブルまたは図９に示すようなＮＴＦＳテーブルに割り当て廃棄レベルを格納する。
時間Ｔ３で、ストレージデバイス１００のユーザは、記憶領域１１０に、別のファイル（すなわち、ファイル「Ｆ５」）の格納を望む。ストレージアロケータ１４４は、追加のファイル（すなわち、ファイルＦ５）を格納するのに十分な格納空間が記憶領域１１０にあるかどうかを決定するために、ストレージデバイス１００における空き記憶空間１９０のサイズ（または１１２０のｆ）を再評価する。
【００５８】
この例において、ストレージアロケータ１４４は、現在の空き記憶空間がファイルＦ５を収容可能であることを決定する。したがって、時間Ｔ３で、ストレージアロケータ１４４により、ストレージコントローラ１２０は、記憶領域１１０にファイルＦ５を格納できる。図１１に示すように、ユーザファイルＦ５を格納すると、ストレージ使用量安全マージンが少なくなる。すなわち、ファイルＦ１〜Ｆ５およびＰ１〜Ｐ３が記憶領域１１０に格納された後に残る記憶領域１１０の空き記憶空間ｆは、ストレージ使用量安全マージン１１３０より少なくなる。したがって、ストレージアロケータ１４４は、パブリッシャのファイル（すなわち、Ｐ１、Ｐ２、およびＰ３）の１つを取り除くことによって、ストレージ使用量安全マージンを復旧または回復させる。前に説明したように、ユーザファイルのストレージ優先度が最も高いため、ストレージ使用量安全マージンが、１つ以上のパブリッシャファイルを取り除く（すなわち、削除する）ことによって復旧または回復される。  前述したように、ストレージアロケータ１４４が、各格納された廃棄可能ファイルに割り当てた廃棄優先度レベルに基づいて、ストレージアロケータ１４４によって、記憶領域１１０から１つまたは複数のパブリッシャファイルを取り除くべきであるという決定がなされる。
【００５９】
図１１を再度参照しながら、格納されたパブリッシャファイルＰ１〜Ｐ３の中から、パブリッシャファイルＰ３に最高廃棄優先度レベル（例えば、１３）を割り当てたと仮定する。したがって、時間Ｔ４で、ファイルＰ３は記憶領域１１０から取り除かれることで、空き記憶空間１９０が拡大される。時間Ｔ４で、空き記憶空間１９０のサイズ（または１１２０のｆ）が、ストレージ使用量安全マージン１１３０より大きいため、パブリッシャファイルをさらに取り除く必要はない。
【００６０】
ストレージデバイス１００のユーザは、１つ以上のユーザファイルを取り除きたいこともある。時間Ｔ５で、ユーザは、自分のファイルのうちの２つ（すなわち、ファイルＦ４およびＦ５）を取り除き、空き記憶空間１９０がさらに拡大される。本願明細書に記載したように、空き記憶空間の取り除きやストレージ使用量安全マージンの回復は、必要に応じて多くの廃棄可能ファイルを取り除くことによって行われるため、ファイルＦ４およびＦ５を取り除くことは、空き記憶区間１９０またはストレージ使用量安全マージンのサイズとは関係がない。パブリッシャは、記憶領域１１０に未承認ファイルを格納することを望んでいると考えられる。前述したように、ストレージアロケータ１４４は、記憶領域１１０にパブリッシャの未承認ファイルを格納することで、ストレージ使用量安全マージン１１３０が少なくならないかを決定するために、空き記憶空間１９０のサイズ（または１１２０のｆ）を評価する。パブリッシャの新しい未承認ファイルを格納することで、ストレージ使用量安全マージン１１３０が少なくなれば、ストレージアロケータ１４４は、このファイルの格納をやめる。
【００６１】
この例において、ストレージアロケータ１４４は、パブリッシャの新しい未承認ファイル（すなわち、ファイル「Ｐ４」）が、ストレージ使用量安全マージン１１３０を低減することなく記憶領域１１０に格納可能であることを決定する。したがって、時間Ｔ６において、ストレージアロケータ１４４により、ストレージコントローラ１２０が、記憶領域１１０にパブリッシャのファイルＰ４を格納できる。ストレージアロケータ１４４はまた、ストレージデバイス１００のユーザによってファイルＰ４が使用される確率を決定し、このファイルに対応する廃棄レベルを割り当てる。次に、ストレージアロケータ１４４は、図８に示すようなＦＡＴテーブルまたは図９に示すようなＮＴＦＳテーブルにファイルＰ４に割り当てられた廃棄レベルを格納する。新しいパブリッシャのファイルおよび新しいユーザファイルを格納し、格納されたファイルを取り除くプロセスは、記憶領域１１０に新しいファイルが追加されるたびに、ストレージアロケータ１４４が、空き記憶空間１９０の現在のサイズを評価し、１つまたは複数のパブリッシャファイル（存在すれば）のうちのどのファイルが記憶領域１１０から取り除かれる必要があるかを決定するまで続きうる。
【００６２】
廃棄レベルを廃棄可能ファイルに割り当てることは、ユーザの経験や好み、ユーザの全地球測位システム（「ＧＰＳ」）位置、および／または他の基準に基づいたものであってもよい。例えば、ストレージデバイスのユーザは、（それまでのユーザの経験に基づいて）ある一定のタイプの音楽を好むようであれば、ストレージアロケータは、パブリッシャファイルが、ユーザが好きなタイプの音楽の１つである音楽を含めば、比較的低い廃棄優先度レベル（例えば、１〜１５の範囲の３）をパブリッシャファイルに割り当ててもよい。しかし、パブリッシャの音楽がユーザの好みでなければ（すなわち、それまでのユーザの経験に基づいて）、ストレージアロケータは、より高い廃棄優先度レベル（例えば、１〜１５の範囲の１２）を関係するパブリッシャファイルに割り当ててもよい。廃棄レベルを廃棄可能ファイルに割り当てるために使用される基準は、ファイルの予測使用、ファイルの使用に関連する予測収入、ファイルの種類、ファイルサイズ、ストレージデバイスにおけるファイルの場所、ファイルの古さ、および本願明細書に明示したような他の基準やパラメータを含んでもよい。他の基準が、単独でまたは本願明細書において述べた任意の基準と組み合わせて、同様に使用されてもよく、廃棄レベルの割り当ては、１つ以上の基準を用いて行われてもよい。加えて、廃棄レベルを異なる廃棄可能ファイルに割り当てるために、異なる基準が使用されてもよい。
【００６３】
別の例において、パブリッシャが、位置依存性の広告（すなわち、特定の区域内で提供する製品やサービスに関する広告）をユーザに送りたければ、ストレージアロケータは、ユーザの位置変化に応じて変化するパブリッシャの広告に廃棄優先度レベルを割り当ててもよい。すなわち、ユーザが、特定の区域から離れることによって、特定の区域で提供される製品やサービスの消費に感心がなくなることが想定されうるため、ユーザが特定の場所から遠ざかるほど、廃棄レベルが高くなる。
【００６４】
関連するファイルシステムにおいて、ファイルをマーキングし、マーキングされたファイルに廃棄レベルを割り当てる本願明細書において開示される手法には、多くの有用な応用がありえ、そのうちの１つでは、ユーザファイルに対して十分な記憶空間を確保するために、ストレージ使用量安全マージンが回復されることに留意するべきである。例えば、ファイルクラスタをより低性能のフラッシュモジュールに再マッピングしたり、リクエストに応じてクラスタをクリアしたりするために、ファイルに割り当てられた廃棄レベルが使用されてもよい。
【００６５】
本願明細書において、冠詞は、文脈に応じて、その冠詞の文法上の目的語が単数あるいは複数（すなわち、少なくとも１つ）であることを言及するように使用される。一例として、文脈に応じて、「要素」は、１つの要素または２つ以上の要素を意味しうる。本願明細書において、「〜を含む」という用語は、「〜を含むが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。「または」と「および」という用語は、本願明細書において、文脈に特別な指示が明示されていない限り、「および／または」という用語を意味し、その用語と交換可能に使用される。「〜など」という用語は、本願明細書において、「〜などであるが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。
【００６６】
以上、本発明の例示的な実施形態を記載してきたが、当業者であれば、開示された実施形態の修正が、本発明の範囲内でなされることは明らかである。したがって、別の実施形態は、より多くのモジュール、より少ないモジュール、および／または機能的に同等のモジュールを含んでもよい。本願明細書における開示は、ＳＤ駆動型フラッシュメモリカード、フラッシュストレージデバイス、非フラッシュストレージデバイス、ユニバーサルシリアルバス（「ＵＳＢ」）インターフェイスが設けられた「ディスクオンキー」デバイス、ＵＳＢフラッシュドライブ（「ＵＦＤ」）、マルチメディアカード（「ＭＭＣ」）、セキュアデジタル（「ＳＤ」）、ミニＳＤ、およびマイクロＳＤなど、様々なタイプの大容量ストレージデバイスに関連する。したがって、添付の特許請求の範囲は、本願明細書の開示によって限定されるものではない。
【図１】
2012512462.tif 000003
【図２】
2012512462.tif 000004
【図３】
2012512462.tif 000005
【図４】
2012512462.tif 000006
【図５】
2012512462.tif 000007
【図６】
2012512462.tif 000008
【図７】
2012512462.tif 000009
【図８】
2012512462.tif 000010
【図９】
2012512462.tif 000011
【図１０】
2012512462.tif 000012
【図１１】
2012512462.tif 000013
【手続補正書】
【提出日】平成22年6月7日(2010.6.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ストレージデバイスを管理する方法であって、
ａ）ストレージデバイスの記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信するステップと、
ｂ）１つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングするステップであって、各ファイルをマーキングするステップが前記ストレージデバイスに関連するファイルシステムの構造において実行され、廃棄可能ファイルにはユーザがリクエストしていない未承認コンテンツが含まれる、マーキングするステップと、
ｃ）前記ファイルシステムの構造における１つ以上のファイルをマーキングするステップに基づいて、前記ストレージデバイスの記憶領域において１つ以上のファイルの格納を管理するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記管理するステップは、（ｉ）廃棄可能なものとしてマーキングされた１つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、（ｉｉ）廃棄可能なものとしてマーキングされたすべてのファイルを取り除くことによって記憶領域を解放することと、（ｉｉｉ）ファイルのクラスタを低性能ストレージモジュールに再マッピングすることのうちのいずれか１つまたはそれらの組み合わせを含む方法。
【請求項３】
請求項１記載の方法において、
ｄ）マーキングされたファイルを前記ストレージデバイスに送信するステップをさらに含む方法。
【請求項４】
請求項１記載の方法において、
前記マーキングするステップは、ファイルに廃棄優先度レベルを割り当てることを含む方法。
【請求項５】
請求項４記載の方法において、
前記ファイルに廃棄優先度レベルを割り当てることは、（ｉ）マーキングされたファイルに対応するファイルアロケーションテーブルエントリのｍ最上位ビットに対応する値を設定するか、または（ｉｉ）前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって実行される方法。
【請求項６】
請求項５記載の方法において、
前記対応する値は、ファイルの属性である方法。
【請求項７】
請求項５記載の方法において、
前記ｍ最上位ビットの値は、前記マーキングされたファイルが廃棄不能であれば、０に設定され、前記マーキングされたファイルが廃棄可能であれば、１〜２m −１の値に設定される方法。
【請求項８】
請求項７記載の方法において、
前記ｍ最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルである方法。
【請求項９】
請求項７記載の方法において、
値「１」は最低優先度で廃棄可能ファイルを示し、値「２m −１」は最高優先度で廃棄可能ファイルを示す方法。
【請求項１０】
請求項４記載の方法において、
前記廃棄優先度レベルは、（ｉ）ファイルの予測使用法、（ｉｉ）ファイルの使用に関連する予測収入、（ｉｉｉ）ファイルの種類、（ｉｖ）ファイルのサイズ、（ｖ）前記ストレージデバイスにおけるファイルの場所、および（ｖｉ）ファイルの古さのうちのいずれか１つに応じて、マーキングされたファイルに割り当てられる方法。
【請求項１１】
請求項４記載の方法において、
ｄ）前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するステップをさらに含む方法。
【請求項１２】
請求項１１記載の方法において、
前記マーキングされたファイルの廃棄優先度レベルを更新するステップは、前記ストレージデバイスにファイルを格納する１つ以上の新しいリクエストから独立して実行される方法。
【請求項１３】
請求項１記載の方法において、
ｄ）前記ストレージデバイスに格納された廃棄可能ファイルが、廃棄しきい値以上の廃棄優先度レベルに対応付けされている場合、前記廃棄可能ファイルを前記ストレージデバイスから廃棄されるように廃棄しきい値を設定するステップをさらに含む方法。
【請求項１４】
請求項１記載の方法において、
ｄ）前記ストレージデバイスに新しいファイルを格納するリクエストを受信するステップと、
ｅ）所定のストレージ使用量安全マージンより大きな空き記憶空間が前記ストレージデバイスにあるかを評価し、このような記憶空間があれば、空き記憶空間に新しいファイルを格納するステップと、
ｆ）前記ストレージデバイス上の空き記憶空間が所定のストレージ使用量安全マージン以下であれば、（ｉ）削除可能な前記ストレージデバイス内の廃棄可能ファイルを探すステップと、（ｉｉ）このようなファイルが見つかれば、空き記憶空間を拡張するようにファイルを削除し、このようなファイルが見つからなければ、新しいファイルの格納をやめるステップと、
ｇ）拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きければ、前記拡張された空き記憶空間に新しいファイルを格納し、前記拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きくなければ、ステップｅ）およびｆ）を繰り返すステップと、
をさらに含む方法。
【請求項１５】
請求項１４記載の方法において、
廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、廃棄可能ファイルを削除する方法。
【請求項１６】
ストレージデバイスを管理するストレージアロケータであって、
前記ストレージデバイスおよび前記ストレージデバイスのホストとのインターフェイスとなる通信インターフェイスと、
前記ストレージデバイスと関連するファイルシステムを格納するためのメモリユニットと、
前記ストレージデバイスと前記関連するファイルシステムを管理するためのプロセッサと、を備え、
前記プロセッサは、（ｉ）前記ストレージデバイスの記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信し、（ｉｉ）１つ以上のファイルを廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ストレージデバイスの前記関連するファイルシステムの構造において実行され、廃棄可能ファイルにはユーザがリクエストしていない未承認コンテンツが含まれ、かつ（ｉｉｉ）前記ファイルシステムの構造における１つ以上のファイルをマーキングすることに基づいて、前記ストレージデバイスの記憶領域において１つ以上のファイルの格納を管理するように構成されるストレージアロケータ。
【請求項１７】
請求項１６記載のストレージアロケータにおいて、
前記プロセッサは、マーキングされたファイルを前記ストレージデバイスに送信するようにさらに構成されるストレージアロケータ。
【請求項１８】
請求項１６記載のストレージアロケータにおいて、
ファイルを廃棄可能としてマーキングすることの一部として、前記プロセッサは、ファイルに廃棄優先度レベルを割り当てるようにさらに構成されるストレージアロケータ。
【請求項１９】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、（ｉ）マーキングされたファイルに対応するファイルアロケーションテーブルエントリのｍ最上位ビットに対応する値を設定するか、または（ｉｉ）前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって、前記マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項２０】
請求項１９記載のストレージアロケータにおいて、
前記プロセッサは、前記マーキングされたファイルが廃棄不能であれば、ｍ最上位ビットの値を０に設定し、前記マーキングされたファイルが廃棄可能であれば、１〜２m −１の値に設定するストレージアロケータ。
【請求項２１】
請求項２０記載のストレージアロケータにおいて、
値「１」は最低優先度で廃棄可能ファイルを示し、値「２m −１」は最高優先度で廃棄可能ファイルを示すストレージアロケータ。
【請求項２２】
請求項２０記載のストレージアロケータにおいて、
前記ｍ最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルであるストレージアロケータ。
【請求項２３】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ファイルの予測使用法に応じて、マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項２４】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項２５】
請求項１８記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する１つ以上の新しいリクエストから独立して、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項２６】
請求項１７記載のストレージアロケータにおいて、
前記ストレージデバイスに格納されたファイルが、所定の廃棄しきい値以上の廃棄レベル優先度に関連付けされている場合、前記プロセッサは前記ファイルを削除するストレージアロケータ。
【請求項２７】
請求項１７記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、前記ストレージデバイスの空き記憶空間のサイズを評価するようにさらに構成され、
（ｉ）前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きければ、前記ストレージデバイスに新しいファイルを格納し、
（ｉｉ）前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きくなければ、拡張される空き記憶空間のサイズが所定のストレージ安全マージンより大きくなるように、空き記憶空間を拡張するために削除可能である前記ストレージデバイス内の１つ以上の廃棄可能ファイルを探し、このようなファイルを見つけると、見つけられたファイルを削除して、拡張された空き記憶空間に新しいファイルを格納し、このようなファイルが見つからなければ、新しいファイルの格納をやめるようにさらに構成されるストレージアロケータ。
【請求項２８】
請求項２７記載のストレージアロケータにおいて、
前記廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、前記ストレージデバイスから１つ以上の廃棄可能ファイルが削除可能であるストレージアロケータ。
【請求項２９】
ストレージシステムであって、
通信インターフェイスと、
ストレージデバイスに関連するファイルシステムを管理するためのストレージアロケータであって、前記ストレージデバイスの記憶領域に１つ以上のファイルの格納を管理するためのプロセッサを備えるストレージアロケータと、を備え、
前記プロセッサは、（ｉ）通信インターフェイスを介して、前記記憶領域に１つ以上のファイルを格納する１つ以上のリクエストを受信し、（ｉｉ）１つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ファイルシステムの構造において実行され、廃棄可能ファイルにはユーザがリクエストしていない未承認コンテンツが含まれ、かつ（ｉｉｉ）前記ファイルシステムの構造における１つ以上のファイルをマーキングすることに基づいて、前記記憶領域において１つ以上のファイルの格納を管理するように構成されるストレージシステム。
【請求項３０】
請求項２９記載のストレージシステムにおいて、
前記通信インターフェイスは、前記ストレージアロケータと一体であるストレージシステム。
【請求項３１】
請求項２９記載のストレージシステムにおいて、
前記ファイルの１つ以上を格納するための記憶領域を含むストレージデバイスをさらに備えるストレージシステム。
【請求項３２】
請求項２９記載のストレージシステムにおいて、
前記ストレージアロケータは、前記ファイルシステムを局所的に格納するためのメモリユニットをさらに含むストレージシステム。
【請求項３３】
請求項２９記載のストレージシステムにおいて、
ストレージデバイスおよび／または前記ストレージデバイスのホストをさらに備え、前記ストレージアロケータは、前記ストレージデバイスまたは前記ストレージデバイスのホストに存在するストレージシステム。
【国際調査報告】
2012512462.tif 000014
2012512462.tif 000015
2012512462.tif 000016