廃棄可能ファイル
ストレージデバイスに格納されるファイルまたは格納される予定のファイルが、ストレージデバイスに関連するファイルシステム構造において、廃棄不能または廃棄可能なもののいずれかとしてマーキングされる。各廃棄可能ファイルが、ファイルに関連させた廃棄優先度レベルを有する。パブリッシャファイルを格納することで、ユーザファイル用に確保されているストレージ使用量安全マージンが少なくならない場合にのみ、ストレージデバイスへのパブリッシャファイルの格納が許容される。ユーザファイルを格納することで、ストレージ使用量安全マージンが少なくなったとしても、ストレージデバイスへのユーザファイルの格納が許容されるが、このような場合、ストレージ使用量安全マージンが、ストレージデバイスから1つ以上の廃棄可能ファイルを取り除くことによって回復される。廃棄優先度レベルが所定の廃棄しきい値以上であれば、ストレージデバイスから廃棄可能ファイルが取り除かれる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、一般に、ストレージデバイスに関し、さらに詳しく言えば、ストレージデバイスにおけるファイルを管理する方法およびデバイスに関する。
【背景技術】
【0002】
不揮発性ストレージデバイスの使用が、携帯性、小型の物理的サイズ、および大記憶容量により、長年にわたって急増してきた。ストレージデバイスには、様々に設計されたものがある。「埋め込み型」として見なされるストレージデバイスもあり、埋め込み型とは、すなわち、ユーザが、ストレージデバイスが動作するホストデバイスからストレージデバイスを取り外すことができず、取り外しが想定されていないことを意味する。一方で、取り外し可能なストレージデバイスもあり、取り外し可能とは、すなわち、あるホストデバイスから(例えば、デジタルカメラから)ストレージデバイスを移動可能であり、またはあるストレージデバイスと別のものとを取り替えることができることを意味する。
【0003】
ストレージデバイスに格納されたデジタルコンテンツは、ストレージデバイスのホストからのものでありうる。例えば、例示的なホストであるデジタルカメラは、画像をキャプチャし、その画像を対応するデジタルデータに変換する。次に、デジタルカメラは、共に動作するストレージデバイスにデジタルデータを格納する。ストレージデバイスに格納されたデジタルコンテンツはまた、リモートソースからのものであってもよく、すなわち、デジタルコンテンツは、例えば、データネットワーク(例えば、インターネット)や通信ネットワーク(例えば、携帯電話ネットワーク)を通してストレージデバイスのホストに送られ、ストレージデバイスのホストによってダウンロードされうる。リモートソースは、例えば、サービスプロバイダやコンテンツプロバイダであってもよい。以下、サービスプロバイダおよびコンテンツプロバイダを総称して「パブリッシャ」と呼ぶ。
【0004】
ストレージデバイスのユーザは、メディアコンテンツまたはパブリッシャからの広告を要求することによって、積極的にメディアコンテンツおよび広告をダウンロードしうる。しかし、パブリッシャの中には、ユーザの許可を求めずに、ユーザにコンテンツを送信して収入増を試みるものがおり、場合によっては、このようなコンテンツがストレージデバイスにダウンロードされていることをユーザに悟られないようにすることもある。本願明細書において、ユーザの合意を得ずにパブリッシャがユーザに送信するコンテンツのことを「未承認コンテンツ」と呼ぶ。多くの場合、未承認コンテンツは、パブリッシャに料金を支払った後かまたは支払い義務が生じた後にユーザによって消費されるように意図されている。
【0005】
パブリッシャは、未承認コンテンツをユーザのストレージデバイスにダウンロードすることで、ユーザが有料の未承認コンテンツを最終的に消費して、収入増につなげることを期待している。ユーザが有料コンテンツを消費することを期待しながら、ユーザの合意を得ずに、パブリッシャがストレージデバイスに未承認コンテンツを格納することは、メディアパブリッシング業界では「予測委託販売」として知られている概念である。しかし、未承認コンテンツは、ストレージデバイスのユーザが、その存在を知らずにまたは消費しようと思わなければ、ストレージデバイスに格納されたままでありうる。ストレージデバイスに未承認コンテンツを格納すると、ストレージデバイス上でユーザが利用可能な(すなわち、空いた)記憶空間が減るため、ユーザの視点から言えば、望ましくない。誰か他の人(すなわち、一部のパブリッシャ)が、ストレージデバイスの記憶空間の一部を占有しているために、ユーザ自身のコンテンツ(例えば、音楽ファイル)用のストレージデバイス空間が少なくなっていることや、未承認コンテンツを削除することで、占有されていた記憶空間を取り戻す必要があることにユーザが気づくこともありうる。
【発明の概要】
【0006】
ユーザの記憶空間の一部を占有する問題への1つの部分的な解決策として、パブリッシャのウェブサイトをブロックするなどして、ストレージデバイスへのパブリッシャのアクセスをブロックする方法がある。この解決策は、ユーザにとって許容可能な場合もあるが、パブリッシャにとっては売り上げが落ち、潜在的な収入源を失ってしまうため、パブリッシャの立場からすると問題である。この問題に対する別の部分的解決策として、コンテンツをホストにパブリッシングし(すなわち、これらのホストのストレージデバイスにコンテンツファイルを格納し)、コンテンツが無関係になるとコンテンツを取り除く方法がある。言い換えれば、コンテンツの出所であるパブリッシャは、コンテンツが無関係になると、格納された未承認コンテンツをストレージデバイスから取り除く。未承認コンテンツは、コンテンツ消費時間が経過するか、またはユーザがコンテンツを消費しそうにないことが見受けられると、無関係なものとして見なされる。
【0007】
以上のことから、未承認ファイルの問題を解消することが必要とされている。詳細には、パブリッシャが、商取引の過程で未承認コンテンツをストレージデバイスへダウンロードしようとすることは許可されるべきであるが、これらのダウンロードは、ユーザ経験を著しく抑制する影響をもつものであってはならない。
【0008】
したがって、ストレージデバイスに未承認コンテンツを収容するのに必要な記憶空間が、ユーザファイルに要求されない限り、ストレージデバイスに未承認ファイルを格納し、ユーザファイルの空き記憶空間の最小サイズを確保するために、ストレージデバイスから未承認ファイルを取り除くことが可能であることは有益でありうる。様々な実施形態がこのようなファイル管理を実施するように設計され、本願明細書においてそれらの例をいくつか提供する。
【0009】
前述した問題を解消するために、ストレージデバイスに格納されたファイルまたは格納予定のファイルは、ストレージデバイスに関連づけられたファイルシステムの構造において、廃棄不能なものまたは廃棄可能なもののいずれかとしてマーキングされる。マーキングされた各ファイルは、ファイルに関連づけられた廃棄優先度レベルを有する。ストレージデバイスにファイルを格納しても、ユーザファイル用に確保されているストレージ使用量安全マージンが所定のマージンを超えて、少なくなることがない場合にのみ新しいパブリッシャファイル(すなわち、未承認ファイル)をストレージデバイスに格納することが許容される。一方で、ユーザファイルは所定の幅を超えてストレージ使用量安全マージンを少なくしたとしても、ストレージデバイスに格納されうる。しかし、このような場合、ストレージ使用量安全マージンの所定の幅は、1つ以上の廃棄可能ファイルをストレージデバイスから取り除くことによって回復する。廃棄優先度レベルが、所定の廃棄しきい値に等しいか、またはこのしきい値より高ければ(または本願明細書において説明するように、低ければ)、廃棄可能ファイルがストレージデバイスから取り除かれる。
【0010】
さまざまな例示的な実施形態が、限定的なものではないという目的で、添付の図面に例示される。簡潔かつ明確に示すために、以下に参照される図面に示す要素は、必ずしも一定の縮尺で描かれたものではないことに留意するべきである。また、適切であると考慮される場合、参照番号は、同様の対応する要素または類似した要素を示すために図面において繰り返されることもある。
【図面の簡単な説明】
【0011】
【図1】例示的な実施形態によるストレージシステムのブロック図である。
【図2】別の例示的な実施形態によるストレージシステムのブロック図である。
【図3】例示的な実施形態によるストレージアロケータのブロック図である。
【図4】例示的な実施形態によるファイルを管理する方法を示す図である。
【図5】例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルのストレージを管理する方法を示す図である。
【図6】例示的な実施形態によるFAT32形式ファイルシステムにおける1つ以上の未承認ファイルをマーキングする方法を示す図である。
【図7】FAT32テーブルに関連づけられた例示的なディレクトリ領域を示す図である。
【図8】例示的な実施形態によるFAT32テーブルを示す図である。
【図9】例示的な実施形態によるNTFSテーブルを示す図である。
【図10】例示的な実施形態によるFATベースのファイルシステムの論理イメージを示す図である。
【図11】本願明細書における開示によるファイルの格納を管理する方法を示す図である。
【発明を実施するための形態】
【0012】
以下の記述は、例示的な実施形態のさまざまな詳細を提供する。しかし、この記述は、特許請求の範囲を限定することを意図したものではなく、本発明のさまざまな原理およびその実行方法を説明するためのものである。
【0013】
未承認コンテンツおよび関連する問題を解消するために、ユーザファイルは、他のファイルより高いストレージ優先度が与えられ、この優先度を確保するために、ストレージ使用量安全マージンが維持される。「ユーザファイル」とは、ストレージデバイスのユーザが、積極的に格納したファイルや、ストレージデバイスへの格納を承認したファイルである。例えば、ユーザが自らのストレージデバイスにダウンロードする音楽ファイルは、ユーザファイルと見なされる。ユーザによってリクエストまたは格納許可が出されているため、ユーザファイルは、「承認」ファイルと見なされる。
【0014】
「他のファイル」は、本願明細書において、「パブリッシャファイル」および「未承認ファイル」として参照される。「パブリッシャファイル」とは、ユーザがファイルをリクエストしていないのにストレージデバイスに格納されたファイルや、ユーザが、少なくとも、短時間ではない間、ファイルの格納に気がつかずに格納されたファイルのことである。ユーザは、未承認ファイルの使用を望まないこともある。使用されない未承認ファイルは、ユーザのストレージデバイスの貴重な記憶空間を消費する傾向にある。したがって、本願明細書に開示された原理によれば、このようなファイルは、ファイルを格納してもストレージ使用量安全マージンを少なくしない場合にのみ、ストレージデバイスへの格納が許可される。先々のユーザファイル用の格納空き記憶空間(すなわち、ストレージ使用量安全マージン)を維持することによって、ユーザファイルにストレージ優先度が与えられる。ストレージ使用量安全マージンは、要求または所望されれば、ストレージデバイスにユーザファイルが格納可能であることを確保するために維持される必要がある。
【0015】
何らかの理由で、ストレージ使用量安全マージンが所定のものより少なくなれば、ストレージ使用量安全マージンを回復させるために、ストレージデバイスから1つ以上の未承認ファイルが取り除かれる(すなわち、削除される)。ストレージ使用量安全マージンを維持することで、追加のユーザファイルをストレージデバイスにダウンロードするための記憶空間が確保される。このため、未承認ファイルは、ストレージファイルシステムの構造において「廃棄可能」なものとしてマーキングされ、要求されれば、少なくともストレージ使用量安全マージンを維持するのに要求された空き記憶空間を取り戻すために後で取り除かれる。
【0016】
ユーザがさまざまな廃棄可能ファイルを使用する可能性は、廃棄可能ファイルごとに異なるため、ファイルの使用の確率、ファイルの使用に関連する考えられる収入、ファイルサイズ、ファイルの種類、ファイルの場所、ファイルの古さなどの1つ以上の基準に応じた廃棄優先度レベルが、事前に、各未承認ファイル(すなわち、各廃棄可能ファイル)に割り当てられる。例えば、廃棄優先度レベルは、収入の可能性によって決定されてもよい。別の例によれば、映画の予告編や広告は、一般に、ユーザが予告編や広告の視聴を好まないため、実際の映画より高い廃棄優先度を有しうる。別の例によれば、ユーザによって最も使用されがちな1つ以上の廃棄可能ファイルには、最低廃棄優先度レベルが割り当てられ、すなわち、このようなファイルは、ストレージデバイスから最も取り除かれないファイルである。言い換えれば、使用確率が高いほど、ファイルに割り当てられる廃棄優先度レベルのレベルが低い廃棄可能ファイルとなる。1つ以上の廃棄可能ファイルを取り除いても、所定のストレージ使用量安全マージンが完全に回復していなければ、所定のストレージ使用量安全マージンが回復されるまで、ストレージデバイスから追加の廃棄可能ファイルが取り除かれる。
【0017】
簡潔に言えば、ファイルシステムが、コンピュータファイルを格納し体系化するための手法を実施する。ファイルシステムは、データの格納、階層的体系化、操作、ナビゲーション、アクセス、および検索のために実施される抽象データ型およびメタデータのセットを含む。抽象データ型およびメタデータはコンピュータファイル(本願明細書において、簡潔にするために「データファイル」または「ファイル」と称する)のアクセス、操作、および起動が可能な「ディレクトリツリー」を形成する。「ディレクトリツリー」は、典型的に、ルートディレクトリおよび任意のサブディレクトリを含む。ディレクトリツリーは、1つ以上の「ディレクトリファイル」としてファイルシステムに格納される。ファイルシステムに含まれるメタデータおよびディレクトリファイルのセットは、本願明細書において、「ファイルシステム構造」と呼ばれる。したがって、ファイルシステムは、データファイルのアクセス、操作、更新、削除、および起動を行いやすいようにするデータファイルおよびファイルシステム構造を含む。
【0018】
ファイルアロケーションテーブル(「FAT」)は、例示的なファイルシステム構成である。FATファイルシステムは、DR−DOS、OpenDOS、MS−DOS、Linux、Windows(登録商標)などを含むさまざまなオペレーティングシステムで使用される。FAT形式のファイルシステムは、どの記憶領域が空いているかまたは割り付けられているか、各ファイルがストレージデバイスのどこに格納されているかについての情報を集めたテーブルを使用する。テーブルのサイズを制限するために、記憶空間が「クラスタ」と呼ばれる連続するセクタグループ中のファイルに記憶空間が割り当てられる。ストレージデバイスの進化に伴い、クラスタの最大数も増大し、クラスタを識別するために使用されるビット数も増大してきた。FAT形式のバージョンは、テーブルビット数に由来し、例えば、FAT12は12ビットを使用し、FAT16は16ビットを使用し、FAT32は32ビットを使用する。
別のファイルシステム構成は、ニューテクノロジーファイルシステム(「NTFS」)として知られている。現在では、NTFSが、Windows NTを始め、それ以降のバージョンのWindows 2000、Windows XP、Windows Server 2003、Windows Server 2008、およびWindows Vistaの標準的なファイルシステムである。FAT32およびNTFSは、ストレージデバイス100と共に提供されうる例示的なファイルシステムである。
【0019】
図1は、典型的なストレージデバイス100を示す。ストレージデバイス100は、ユーザファイルまたはパブリッシャファイルでありうる様々なタイプのファイル(例えば、音楽ファイル、ビデオファイルなど)を格納するための記憶領域110を含む。ストレージデバイス100はまた、データおよび制御ライン130を介して記憶領域110を管理するストレージコントローラ120を含む。ストレージコントローラ120はまた、ホストインターフェイス150を介してホストデバイス140との通信を行う。ホストデバイス140は、専用ハードウェアまたは汎用コンピューティングプラットフォームであってもよい。
【0020】
記憶領域110は、例えば、NANDフラッシュの種類のものであってもよい。ストレージコントローラ120は、例えば、「読み出し」、「書き込み」、および「消去」動作、ウェアレベリングなどを制御することによって、さらには、ホスト140との通信を制御することによって、記憶領域110へのデータ転送/記憶領域110からのデータ転送およびホストデバイス140へのデータ転送/ホストデバイス140からのデータ転送のすべてを制御する。記憶領域110は、例えば、ユーザファイルおよびパブリッシャファイル、認証ホストデバイスによってのみ使用可能な保護データ、およびストレージコントローラ120によって内部のみで使用されるセキュリティデータを含んでもよい。ホスト(例えば、ホスト140)は、記憶領域110に直接アクセスできない。すなわち、例えば、ホスト140が、ストレージデバイス100からのデータを要求するかまたは必要とすれば、ホスト140は、ストレージコントローラ120からデータをリクエストする必要がある。ストレージデバイス100に格納されたデータファイルへのアクセスを容易に行うために、ストレージデバイス100には、ファイルシステム160が設けられる。
【0021】
記憶領域110は、3つの部分、すなわち、ユーザ領域170、パブリッシャ領域180、および空き記憶空間190に機能的に分割される。ユーザ領域170は、ユーザファイルが格納される記憶領域110内の記憶空間である。パブリッシャ領域180は、パブリッシャファイルが格納される記憶領域110内の記憶空間である。空き記憶空間190は、記憶領域110内の空いている記憶空間である。空き記憶空間190は、ユーザファイルまたはパブリッシャファイルを保持するために使用されうる。空き記憶空間190にユーザファイルを格納すると、ユーザファイルを保持する記憶空間は、空き記憶空間190から取り去られ、ユーザ領域170に追加される。同様に、空き記憶空間190にパブリッシャファイルを格納すると、パブリッシャファイルを保持する記憶空間は、空き記憶空間190から取り去られ、パブリッシャ領域180に追加される。ユーザファイルまたはパブリッシャファイルが、記憶領域110から取り去られれば(すなわち、除去されれば)、空いた記憶空間は、空き記憶空間190に追加される(戻る)。
【0022】
ストレージデバイス100のユーザは、空き記憶空間190のサイズが許容すれば、ホスト140から記憶領域110へユーザファイルをダウンロードできる。ダウンロードされたユーザファイルは、空き記憶空間190に格納され、前に説明したように、このファイルを保持する記憶空間は、空き記憶空間190から取り去られ、ユーザ領域170に追加される。前に説明したように、ユーザファイルは、他の(例えば、パブリッシャ)ファイルより高い優先度を有し、その優先度を確保するために、所定のストレージ使用量安全マージンが設定され、必要であれば、以下に記載する方法で回復される。
【0023】
ホスト140は、空き記憶空間190の回復を行うためのストレージアロケータ144を含む。ストレージアロケータ144は、ハードウェア、ファームウェア、ソフトウェア、またはこれらの任意の組み合わせであってもよい。一般に、ストレージアロケータ144は、ホスト140との間で通信されるファイル(例えば、ファイル142)が、ユーザファイルであるのかまたはパブリッシャファイルであるのかを決定し、次に、それに応じて(すなわち、廃棄不能ファイルまたは廃棄可能ファイルとして)通信されたファイルをマーキングする。
【0024】
ストレージアロケータ144が、ホスト140との間で通信されるファイル(例えば、ファイル142)が廃棄不能、例えばユーザファイルであることを決定すれば、ストレージアロケータ144は、通常の方法で記憶領域110にファイルを格納する。前に説明したように、廃棄不能ファイルを保持する記憶領域110内の記憶空間は、ユーザ領域170に追加されるか、またはユーザ領域170の一部である。しかし、ホスト140との間で通信されるファイルが、例えばパブリッシャファイルであるために廃棄可能であるとストレージアロケータ144が決定すれば、ストレージアロケータ144は、ファイルを廃棄可能なものとしてマーキングする。また、空き記憶空間190が所定のストレージ使用量安全マージンより大きければ、ストレージアロケータ144は、空き記憶空間190にマーキングされた廃棄可能ファイルを格納し、前に説明しれたように、廃棄可能ファイルを保持する空き記憶空間190内の記憶空間は、空き記憶空間190から取り去られ(すなわち、空き記憶空間は低減され)、パブリッシャ領域180に追加される(この追加は、廃棄可能ファイル182として論理的に示される)。
前に説明したように、パブリッシャファイルがユーザによって使用されうる可能性は、パブリッシャファイルごとに異なりうるため、使用可能性ができるだけ低いパブリッシャファイルは、記憶領域110から取り除く最初の候補となる。したがって、ファイルを廃棄不能または廃棄可能としてマーキングすることに加えて、ストレージアロケータ144は、記憶領域110への廃棄可能ファイルの格納前、格納と同時、または格納後に、各廃棄可能ファイルに廃棄優先度レベルを割り当てる。
【0025】
ファイルを廃棄不能または廃棄可能としてマーキングし、ストレージアロケータ144によって廃棄優先度レベルを割り当て、かつストレージデバイス100のファイルシステム160(またはそのイメージ)を使用することによって、ストレージアロケータ144は、記憶領域110におけるユーザファイルおよびパブリッシャファイルの数、ならびに記憶領域110内のファイルサイズおよび論理場所を「知る」。この情報(すなわち、ファイルの数、サイズ、および場所)を、特に、1つ以上のマーキングされたファイルに基づいて知ることで、ストレージアロケータ144は、記憶領域110を管理し、記憶領域110の承認および未承認ファイルの格納を管理する。記憶領域110を管理するかまたは記憶領域110におけるファイルの格納を管理することは、例えば、廃棄可能としてマーキングされた1つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、廃棄可能としてマーキングされたすべてのファイルを取り除くことで記憶領域を解放することと、ファイルのクラスタを性能がより低いストレージモジュールに再マッピングすることとを含んでもよい。記憶領域110または記憶領域に格納されたファイルを管理することが、記憶領域110または記憶領域110に格納されたファイルの他の態様、追加の態様、または別の態様を管理することを含んでもよい。
【0026】
ストレージアロケータ144はまた、先々のユーザファイル用に元々保存されていた空き記憶空間を回復する(すなわち、所定のストレージ使用量安全マージンを回復する)ために、各廃棄可能ファイルに割り当てられた廃棄レベルによって、廃棄可能なまたは廃棄すべき(すなわち、記憶領域110から削除または取り除かれる)廃棄可能ファイルの順番を知る。したがって、ユーザが、記憶領域110に新しいユーザファイルを格納したいが、そのユーザファイルを収容するための十分な空き容量空間がなければ(すなわち、ストレージ使用量安全マージンが所定のものより少ないことを意味する)、ストレージアロケータ144は、廃棄可能ファイルに割り当てられた廃棄優先度レベルを使用して、所定のストレージ使用量安全マージンが完全に回復するまで、より多くの空き記憶空間を取り戻す(すなわち、空き記憶空間190を拡張する)ために、廃棄可能ファイルを1つずつ繰り返し削除する。前に説明したように、完全に回復されたストレージ使用量安全マージンは、先々のユーザファイル用に十分な空き記憶空間が確保される可能性が高い。廃棄可能ファイルは、ユーザが格納した廃棄可能ファイルをいずれ使用したいと思うかもしれないということが考慮されているため、新しいユーザファイルを格納するリクエストの受信にのみ応答して、ストレージデバイス100から取り除かれるかまたは削除され、したがって、廃棄可能ファイルは、そのファイルを収容する記憶空間が新しいユーザファイルに要求される場合のみ、ストレージデバイスから取り除かれる。ストレージアロケータ144は、ホスト140に埋め込まれるかまたは組み込まれてもよく、あるいはホスト140(四角形の破線)およびストレージデバイス100の外部に存在してもよい。
【0027】
ストレージアロケータ144は、ストレージデバイス100またはそれに関連するファイルシステムの典型的なイメージを有する。ストレージアロケータ144は、ファイルを廃棄不能または廃棄可能としてマーキングし、各廃棄可能ファイルに廃棄レベルを割り当てるために、ストレージデバイスのファイルシステムイメージを使用する。異なるファイルシステムが異なる構造を有するため、ファイルのマーキング(すなわち、廃棄不能または廃棄可能なものとして)および廃棄レベルの割り当ては、図6〜図10に詳しく述べるように、以下に記載される使用されたファイルシステム構造に適応される。
【0028】
図2は、別の例示的な実施形態による携帯可能なストレージデバイス200のブロック図である。ストレージコントローラ220は、ストレージコントローラ120のように機能し、ストレージアロケータ244は、ストレージアロケータ144のように機能する。ストレージアロケータ244は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組み合わせであってもよい。ストレージアロケータ244は、ストレージコントローラ220と内部的に協働する。ストレージコントローラ220が、ホスト240から記憶領域210にファイルを格納するための格納要求を受信すると、ストレージコントローラ220は、格納リクエストをストレージアロケータ244に知らせ、ストレージアロケータ244は、ストレージデバイス200に関連するファイルシステムの構造において廃棄不能または廃棄可能としてファイルをマーキングする。新しいファイルが廃棄可能であるとストレージアロケータ244が決定すれば、ストレージアロケータ244は、ファイルの使用確率に応じて、廃棄優先度レベルを新しいファイルに割り当てる。次に、ストレージアロケータ244は、空き記憶空間290の現在のサイズを評価し、新しいファイルのためのスペースを空けるために、記憶領域210から1つ以上の廃棄可能ファイルを取り除かれなければならない(すなわち、削除しなければならない)。1つまたは複数の廃棄可能ファイルが、ストレージデバイスから取り除かれるべきであれば、ストレージアロケータ244は、どのファイルが現在の取り除かれるべき候補ファイルであるかを決定する。次に、ストレージアロケータ244は、記憶領域210から取り除かれるべき廃棄可能ファイルをストレージコントローラ220に通知し、この通知に応答して、ストレージコントローラ220は、ストレージアロケータ244によって識別された1つまたは複数の廃棄可能ファイルを取り除く。携帯可能なストレージデバイス200のいくつかの構成において、ストレージアロケータ244は、ストレージコントローラ220と記憶領域210との間に機能的に配置されてもよい。ストレージアロケータ244が、ストレージコントローラ220と記憶領域210との間に機能的に配置される構成において、ストレージアロケータ244または記憶領域210は、ストレージコントローラ220の機能の一部を想定する必要がある。このような構成において、記憶領域210は、フラッシュNANDプロトコルより高いレベルで通信するメモリユニットで構成される。
【0029】
図3は、例示的な実施形態によるストレージアロケータ300のブロック図である。ストレージアロケータ300は、メモリユニット310と、プロセッサ320と、インターフェイス330とを含む。メモリユニット310は、(例えば、図2のストレージデバイス200)に関連するファイルシステム構造ストレージデバイスまたはファイルシステム構造のイメージを保持してもよい。プロセッサ320は、ストレージデバイスに関連するファイルシステムを管理する。インターフェイス330は、図1に示すように、ホストと協働し、ストレージデバイスのストレージコントローラと協働するように適応されてもよく、あるいは、図2に示すように、ストレージデバイスのストレージコントローラのみと協働するように適応されてもよい。
【0030】
プロセッサ320は、ストレージデバイスの記憶領域にファイルを格納し、ストレージアロケータ300が動作するストレージデバイスに関連するファイルシステムの構造において、ファイルを廃棄可能または廃棄不能なものとしてマーキングするために、インターフェイス330を介してリクエストを受信するように構成または適応される。インターフェイス330が、図2のストレージコントローラ220に機能的に取り付けられ(ひいては、例えば、ファイルレベルコマンドではなく、SCSIまたはUSB/MSCラップコマンドを受信すれば)、受信したリクエストは、ファイルレベルよりかなり低いレベルにある。すなわち、受信したリクエストは、ホストによって適切に解釈される場合、ファイルに対応する論理ブロックアドレスでセクタを格納するリクエストでありうる。ストレージコントローラ220が、NVMHCIプロトコル、またはNFSや同様のプロトコルなどのネットワーキングファイルシステムプロトコルをサポートすれば、ストレージコントローラ220は、ファイルレベルのリクエストを取得しうる。したがって、ストレージコントローラ220などのストレージコントローラと、インターフェイス330などのインターフェイスとの間の通信は、NVMHCIの実施例やNVMHCIと同様な実施例に限定されない。通信インターフェイス330は、図3に示すように、ストレージアロケータ300の一部をなすものであってもよい。
【0031】
プロセッサ320は、マーキングされたファイルをストレージデバイスに送信するようにさらに構成または適応され、ファイルを廃棄可能としてマーキングすることは、廃棄優先度レベルをファイルに割り当てることを含む。ストレージデバイスによって使用されるファイルシステムが、FATベースのものであれば、プロセッサ320は、対応する値を、マーキングされたファイルに対応するFATにおいて最上位のmビット(すなわち、最上位)(例えば、m=4)を設定することによって、マーキングされたファイルに廃棄優先度レベルを割り当てる。FATエントリにおいて最上位ビットに設定された対応する値またはNTFSディレクトリエントリに設定された値は、ファイルの属性であってもよく、あるいはファイルの属性に関係するものであってもよい。「属性」とは、テーブル内に格納されたコンテンツのタイプに関する情報を含むFATテーブルまたはNTFSテーブルのヘッダにあるメタデータタグまたは何らかのデータ構造を意味する。「広告」、「プレミアムコンテンツ」、「販売促進用の(無料)コンテンツ」は、FATテーブルまたはNTFSテーブルに格納されてもよい例示的なタイプのコンテンツである。廃棄レベルを設定するための別の基準は、例えば、最終アクセスファイル、ファイルサイズ、ファイルタイプなどである。
【0032】
ファイルのマーキング専用のFAT32エントリの最上ビットの数mは、これらのビットが使用されないため、4以下であってもよい。加えて、使用されるビットが大きいほど、使用可能な廃棄優先度レベルが高くなる。例えば、3ビット(すなわち、m=3)を使用すると、8(23 =8)廃棄優先度レベルが得られ、4ビット(すなわち、m=4)を使用すると、16(24 =16)廃棄優先度レベルが得られる(すなわち、廃棄不能ファイルに割り当てられる廃棄優先度レベル「0」を含む)。言い換えれば、プロセッサ320は、マーキングされたファイルが廃棄不能であれば、m最上位ビットの値を0に設定するか、あるいはマーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定する。廃棄優先度レベルは、マーキングされたファイルが、ストレージデバイスから廃棄可能であるのか、または廃棄されるべきなのかの優先度を示す。例えば、実施例に応じて、値「1」は、最低優先度または最高優先度のいずれかで廃棄可能ファイルであることを示すことが可能であり、値「2m −1」は、最高優先度または最低優先度のいずれかで廃棄可能ファイルをそれぞれ示すものでありうる。
【0033】
プロセッサ320は、未承認ファイルがストレージデバイスのユーザによって使用される可能性または確率に関連して前に説明したように、ファイルの予測使用に応じて、廃棄優先度レベルをマーキングされたファイルに割り当ててもよい。プロセッサ320は、ストレージデバイスに新しいファイルを格納するリクエストがあるたびまたは各リクエストの受信に応答して、マーキングされたファイルの廃棄優先度レベルを更新してもよい。プロセッサ320は、ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して、所与のマーキングされたファイルの廃棄優先度レベルを更新してもよい。例えば、以前に高優先度のものであったファイルが、ある一定の時間間隔が経過した後に優先度が下げられてもよい。プロセッサ320は、ファイルが、所定の廃棄しきい値以上の廃棄優先度レベルに関連づけられていれば、ストレージデバイスに格納されたファイルを削除する。プロセッサ320は、ファイルの書き込みや追加の数に基づいて、またはストレージデバイスの空き記憶空間の予測使用や新しいパブリッシャファイルの利用可能性に応じて、廃棄しきい値を(再)設定してもよい。
【0034】
メモリユニット310は、プロセッサ320がストレージデバイスに格納されたファイルに割り当てる廃棄優先度レベルを含む割り当てテーブル340を保持してもよい。加えて、割り当てテーブル340はファイルに割り当てられる廃棄優先度レベルにファイルを関連づけるファイルを識別するとともに、情報を保持してもよい。割り当てテーブル340は、廃棄しきい値をさらに保持してもよい。割り当てテーブル340に保持される情報により、プロセッサ320は、所定のストレージ使用量安全マージンを回復するために、ストレージデバイスから取り除くことが可能な1つまたは複数の廃棄可能ファイルを識別することができる。
【0035】
ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、プロセッサ320は、ストレージデバイスの空き記憶空間(f)のサイズを評価し、ストレージデバイスの空き記憶空間の評価サイズが所定のサイズより大きければ、または所定のサイズより大きくなければ、ストレージデバイスに新しいファイルを格納し、プロセッサ320は、削除可能であるストレージデバイス内にある1つ以上の廃棄可能ファイルを探し、1つまたは複数のこのようなファイルが見つかれば、プロセッサ320は、現在の空き記憶空間(f)を拡張して、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるようにするために、1つまたは複数のファイルを削除する。1つまたは複数の廃棄可能ファイルは、廃棄可能ファイルに関連する廃棄優先度レベルが、所定の廃棄しきい値(例えば、1〜15、例えば、15)以上であれば、ストレージデバイスから削除可能である。
【0036】
空き記憶空間が十分に拡張された後、プロセッサ320は、拡張された空き記憶空間に新しいファイルが格納されることを許容する。「空き記憶空間が十分に拡張される」とは、前述した所定のストレージ使用量安全マージンを少なくすることなく、全空き記憶空間が新しいファイルを収容可能になるまで、あるいは同様に、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるまで、またはすべての廃棄可能ファイルが取り除かれるまで、占有された記憶空間を1つずつ解放することによって、空き記憶空間を拡張することを意味する。
プロセッサ320は、標準的な既製のシステムオンチップ(「SoC」)デバイスまたはシステムインパッケージ(「SiP」)デバイス、あるいは実行時、本願明細書に記載するステップ、演算、および評価を実行する特殊なソフトウェアを備えた汎用処理ユニットでありうる。あるいは、プロセッサ320は、ハードウェアを使用することによって、本願明細書に記載するステップ、演算、および評価を実行する特定用途向け集積回路(「ASIC」)でありうる。
【0037】
図4は、1つの例示的な実施形態による廃棄可能ファイルを格納する方法を示す。図4は、図1に関連して記載される。ステップ410において、ホスト140は、ストレージデバイス100にファイル142を格納するリクエストを受信する。ステップ420において、ストレージアロケータ144は、ファイルを「廃棄可能」または「廃棄不能」としてマーキングし、ステップ430において、空き記憶空間190が十分に大きければ、マーキングされたファイルをストレージデバイス100のストレージコントローラ120に送信する(すなわち、記憶領域110に格納するため)。また、廃棄優先度レベルがファイルに割り当てられるという意味でも、ファイルがマーキングされる。ステップ440において、ストレージアロケータ144は、(ストレージコントローラ120との通信により)記憶領域110を管理するか、あるいはマーキングされたファイルに基づいて、随意にすでにマーキングされていた1つ以上のファイルに基づいて、記憶領域110に格納されるファイルを管理する。
【0038】
図5は、1つの例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルの格納を管理する方法を示す。図5は、図1に関連して記載される。新しいファイルは、ストレージデバイス100に格納される候補である。ストレージデバイス100のファイルシステム160の現在のイメージを知ることで、ストレージアロケータ144は、ステップ510において、空き記憶空間190の現在のサイズ「f」を評価して、現在のサイズがfである空き記憶空間190が、新しいファイル(すなわち、格納候補であるファイル)を収容可能であるかを確認する。一般に、ストレージアロケータ144が、新しいファイルを取り扱う方法は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかに依存する。したがって、ストレージアロケータ144は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかを最初に決定する。
【0039】
新しいファイルがユーザファイルである場合
ステップ520において、ストレージアロケータ144は、空き記憶空間190が、新しいユーザファイルを収容できるかをチェックする。空き記憶空間190が、新しいユーザファイルを収容できれば(ステップ520において「Y」で示す)、ストレージアロケータ144は、ステップ560において、所定のストレージ使用量安全マージンが、新しいユーザファイルの格納の可否によって少なくなるかに関係なく、空き記憶空間190に新しいユーザファイルを格納する。ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後、所定のストレージ使用量安全マージンが少なくなれば(すなわち、所定のストレージ使用量安全マージンに対して)、ストレージアロケータ144は、新しいユーザファイルの格納に対してさらなるアクションを起こさない。
【0040】
しかし、ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後に、所定のストレージ使用量安全マージンが少なくなれば、ステップ550において、ストレージアロケータ144は、所定のストレージ使用量安全マージンを維持するために、格納された最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイル・・・などを以下同様に決定する追加のステップを含む。ストレージアロケータ144は、格納された廃棄可能ファイルに割り当てた廃棄レベルに基づいて、最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイルを決定する。
【0041】
ステップ520において、空き記憶空間190が新しいユーザファイルを収容できないことをストレージアロケータ144が決定すれば(ステップ520において「N」と示す)、ステップ530において、空き記憶空間190と、廃棄可能ファイルによって消費されている記憶空間とを合わせれば新しいユーザファイルを格納するのに十分かどうかを、ストレージアロケータ144が決定する。記憶空間を組み合わせても不十分であれば(ステップ530において「N」と示す)、これは、削除される廃棄可能ファイルの数に関係なく、新しいユーザファイルを、そのファイルサイズにより、「非ユーザ」記憶領域に格納することができないということを意味する。組み合わせた記憶空間が十分であれば(ステップ530において「Y」と示す)、ステップ540において、新しいユーザファイルに十分な記憶空間を解放するために、格納された廃棄可能ファイルの中から、どの廃棄可能ファイルが削除可能であるかをストレージアロケータ144が探す。前に説明したように、ストレージアロケータ144が、ストレージデバイスのファイルシステムにおいて廃棄不能または廃棄可能としてファイルをマーキングするために、ストレージデバイス100のファイルシステムを使用することによって、これらの廃棄可能ファイルをストレージアロケータ144が探す。加えて、ストレージアロケータ144によってマーキングされたファイルに割り当てられた廃棄レベルは、各廃棄レベルが対応するマーキングされたファイルに関連づけられるように、ストレージデバイスのファイルシステムにも埋め込まれる。
廃棄可能ファイル(「DF」)であって、最初に廃棄すべき廃棄可能ファイル(以下、このファイルを「DF1」と呼ぶ)を見つけると、ストレージアロケータ144は、このファイルの記憶空間(以下、この記憶空間を「SP1」と呼ぶ)を記憶空間190に追加するかまたは戻すために、ファイルDF1を削除する。
次に、ステップ550において、ストレージアロケータ144は、拡張された空き記憶空間190(すなわち、空き記憶空間190と最後に戻された記憶空間を足したもの、すなわち、f+SP1)が、新しいユーザファイルを収容可能であるかをチェックする。拡張された空き記憶空間190(すなわち、f+SP1)が、新しいユーザファイルを収容できないままであれば(ステップ550において「N」として示す)、ステップ550において、ストレージアロケータ144は、追加の記憶空間を空き記憶空間190に戻すために(すなわち、次に削除すべき廃棄可能ファイルを見つけて削除することによって)、ステップ550を反復して繰り返す(反復は555で示す)。
【0042】
2番目に優先度が高い廃棄優先度の次の廃棄可能ファイルを見つけると(以下、次の廃棄可能ファイルを「DF2」と呼ぶ)、ストレージアロケータ144は、追加の記憶空間を空き記憶空間190に解放および追加するために(以下、追加の記憶空間を「SP2」と呼ぶ)、ファイルDF2を削除する。次に、ステップ550において、ストレージアロケータ144は、拡張された空き記憶空間190(すなわち、空き記憶空間190と、最後に解放された2つの記憶空間を合わせたもの、すなわち、f+SP1+SP2)が、新しいファイルを収容可能であるかを再度チェックする。拡張された空き記憶空間190(すなわち、f+SP1+SP2)が、新しいファイルを収容できなければ(ステップ540において「N」として示す)、ストレージアロケータ144は、削除すべき次の廃棄ファイルを見つけるために、ステップ540をもう一度繰り返す。ストレージアロケータ144は、蓄積された空き記憶空間190が、新しいユーザファイルを収容できるまで、ステップ540および550を反復する(ステップ550において「Y」として示す)。次に、ステップ560において、ストレージアロケータ144は、記憶領域110に新しいユーザファイルを格納する。
前述したように、ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後に、実際のストレージ使用量安全マージンが、所定のストレージ使用量安全マージンより少なくなれば、ステップ560は、ストレージアロケータ144が、所定のストレージ使用量安全マージンを回復するために、最初に削除すべき格納された廃棄ファイル、次に削除すべき格納された廃棄可能ファイル・・・などを以下同様に決定する際の追加のステップを含んでもよい。
【0043】
新しいファイルがパブリッシャファイルである場合
新しいファイルがパブリッシャファイルであれば、ストレージアロケータ144は、所定のストレージ使用量安全マージンを少なくせずに、空き記憶空間190が新しいパブリッシャファイルを収容できる場合のみ、記憶領域110に新しいパブリッシャファイルを格納する(ステップ560)。すなわち、新しいパブリッシャファイルを格納すると、所定のストレージ使用量安全マージンが少なくなるならば、ストレージアロケータ144は、記憶領域110に新しいパブリッシャファイルを格納しないように決定してもよい。このような場合、ストレージアロケータ144は、そのパブリッシャファイルに対して何らのアクションをとらず、新しいパブリッシャファイル用の記憶空間を解放するためにストレージデバイスからファイルを削除することもない。あるいは、ストレージアロケータ144は、ステップ540において、廃棄優先度が低い廃棄可能ファイル用の記憶空間を解放するために、より優先度が高い1つ以上の廃棄可能ファイルを削除してもよい。前述したように、ストレージデバイス100のファイルシステムにおいて、ファイルがマーキングされ、廃棄レベルが埋め込まれ、ファイルがマーキングされ、ファイルシステムに廃棄レベルが埋め込まれる方法は、使用するファイルシステムに依存または適応されうる。
【0044】
図6は、1つの例示的な実施形態によるFAT32形式のファイルシステムにおける未承認ファイルをマーキングする方法を示す。FAT32形式のファイルシステムは、クラスタを使用する。FAT32形式のファイルシステムに関連して前述したように、FAT32クラスタを識別するために使用されるビット数は、32である。以下、図6は、図1に関連して記載される。
ステップ610において、FAT32の各クラスタの32ビットのm最上位ビット(m≦4)が、場合によって、廃棄不能または廃棄可能としてファイルをマーキングするように、さらには、各廃棄可能ファイルの対応する廃棄レベルを保持するように割り付けられるかまたは確保される。廃棄レベルのファイルへの割り当ては、対応する値をマーキングされたファイルに対応する割り付けられたmビットに設定することによって行われる。
【0045】
ステップ620において、ストレージアロケータ144は、ストレージデバイス100のユーザが未承認ファイルを使用する可能性のレベルを評価する。ファイルを使用する可能性の評価は、委託販売ファイルに関して当業者に既知の様々な方法で実行されうる。例えば、ファイルを使用する可能性の評価は、ストレージデバイスの使用者がいる場所のモニタリング、および/またはモニタリングしたユーザのこれまでの経験や好みに基づいたものであってもよい。ファイルを使用する可能性の評価はまた、例えば、FATテーブルまたはNTFSテーブル内に格納されるコンテンツのタイプ(例えば、「広告コンテンツ」、「プレミアムコンテンツ」、「販売促進用の(無料)コンテンツ」など)に基づいたものであってもよい。ストレージアロケータ144は、ファイルが使用される可能性を評価するための代替となるものまたはさらなる基準を用いてもよい。例えば、ストレージアロケータ144は、最新アクセスファイル、ファイルサイズ、ファイルタイプなどであってもよく、あるいはそれらに関連されうるファイルの属性または特性を使用してもよい。
ユーザが未承認ファイルを使用する可能性のレベルをストレージアロケータ144が評価した後、ストレージアロケータ144は、ステップ630において、未承認ファイルの評価された使用可能性レベルに対応する廃棄優先度レベルを割り当てる。未承認ファイルが、ストレージデバイス100のユーザによって使用される可能性が高いほど、廃棄レベルは低い。
【0046】
mが4ビットであれば、これは、廃棄スケールが、1(すなわち、0001)〜15(すなわち、1111)の15の廃棄レベルを与えるということを意味する。すなわち、廃棄レベル0は、廃棄不能ファイルすべてに割り当てられ、廃棄レベル1は、最低廃棄優先度の廃棄可能ファイルに割り当てられ、廃棄レベル15は、最高廃棄優先度の廃棄可能ファイルに割り当てられる。ストレージアロケータ144が、対応する廃棄レベルを未承認ファイルに割り当てた後、ストレージアロケータ144は、ステップ640において、1〜15の対応する値を、未承認ファイルに関連するクラスタの4つの最上位ビットに設定する。未承認ファイルが、ファイルに関連した2つ以上のクラスタを有すれば、各クラスタの4つの最上位ビットは、同じ値に設定される。
ステップ650において、未承認ファイルが、評価を必要とする最後のファイルであるかがチェックされる。未承認ファイルが評価が必要な最後のファイルでなければ(ステップ650において「N」で示す)、前述した方法で別のファイルが評価される。未承認ファイルが評価を必要とする最後のファイルであれば(ステップ650において「Y」で示す)、ステップ640において値が設定された各々に対してmビットを有する(1つまたは複数の)未承認ファイルが、ストレージデバイスに送信される。
【0047】
図7は、FAT32テーブルに関連する例示的なディレクトリテーブル700を示す。ディレクトリテーブル700は、説明に使用する部分的なテーブルにすぎず、したがって、FATディレクトリエントリのすべてのフィールドを示しているものではない。ディレクトリ領域700は、ファイル名、ファイルサイズ、関係する記憶空間において、各ファイルが始まる場所など、関係するファイルシステムに格納されるファイルの項目を保持する。ファイルの項目は、以下のフィールドに保持される。フィールド710は、関係するファイルシステムに格納されるファイルのディスクオペレーティングシステム(「DOS」)ファイル名を保持し、フィールド720は、ファイルの拡張を保持し、フィールド730は、ファイルのさまざまな属性を保持し、フィールド740は、ファイルの先頭クラスタ番号(「FCN」)の上位16ビットワードを保持し、フィールド750は、ファイルの先頭クラスタ番号(「FCN」)の下位を保持し、フィールド760は、ファイルサイズを保持する。各FCN番号は、ファイルが見つけられうる第1の論理クラスタを示す。
【0048】
ディレクトリ領域700の最初のエントリは、「REALFILE」(770と示す)と呼ぶ例示的なファイルの情報を保持する。REALFILE770は、ファイル拡張子「DAT」を有し、FCNは「0000 0002」であり(755と示す)、ファイルサイズは、「0000 24E4」である。テーブル700の数字は、16進数で示されている。規格の一部として、属性値「00」(780と示す)および「20」(図7に図示せず)は、「通常」ファイルをさすのに対して、属性値「02」は、ファイルシステム中の隠しファイルをさす。ファイル名「\xE5Consign」は削除ファイルを示し、ここでの「\xE5」は、ファイル名の最初のバイトの値が16進数のE5であることを意味する。一例として、FCN数0000 0002(755と示す)は、ファイルREALFILEの最初のクラスタを示す。
【0049】
図8は、1つの例示的な実施形態による例示的な部分的FAT32テーブル800を示す。FAT32テーブル800は、倍長語(「DWORD」)アレイとして示され、値は16進数である。参照番号810は、FAT32テーブル800を保持するタイプのデバイスを示し、ここで「F8」は、ハードドライブをさす。FAT32テーブル800は、クラスタ#1(820と示す)、クラスタ#2(825と示す)・・・クラスタ#23(830と示す)として示された23個のクラスタを含む。図8は、図7に関連して記載される。FAT32テーブル800のクラスタは、ファイルの最初のクラスタであってもよく、あるいはファイルの次につながったクラスタを示してもよく、またはファイルの終わり(「EOF」)を指し示すものであってもよい。
【0050】
ディレクトリ領域700を再度参照すると、ファイルREALFILE(770と示す)の最初のFCNは、「0000 0002」(755と示す)であり、これは、図8のテーブル800のクラスタ#2をさす。図8に示すように、クラスタ#2の値(すなわち、値「0000 0003」)は、次のファイルクラスタであるクラスタ#3をさす(840と示す)。同様に、クラスタ#3の値(すなわち、「0000 0004」)は、次のファイルクラスタであるクラスタ#4をさす。クラスタ#4は、値「0FFF FFFF」(「F」は、10進数の「15」を表す16進数字である)を有し、ここで、「FFF FFFF」(850と示す)は、ファイルのEOF指示を示し、ゼロ値(860と示す)は、廃棄レベル0を示す。したがって、ファイルREALFILEは、3つのクラスタと関連している(すなわち、クラスタ#2、クラスタ#3、およびクラスタ#4)。
【0051】
前に説明したように、廃棄レベル0が、廃棄不能ファイルに割り当てられる。特定のファイルの各クラスタの最上位16進数字が、そのファイルに割り当てられた同一の廃棄優先度レベルに設定されることに留意するべきである。例えば、ファイルREALFILEは、廃棄レベル「0」が割り当てられ、したがって、クラスタ#2、#3、および#4の最上位16進数字の各々が、この値を有する(すなわち、値「0」、「0」値には下線が引かれている)。別の例によれば、FCNが「0000 0005」(図7に示す)であるファイル「E5 Consign」には、廃棄優先度レベル「1」が割り当てられている。したがって、このファイルに関係するクラスタ#5〜12の各々の最上位16進数字は、値「1」を有する(例えば、870と示す)。言い換えれば、本願明細書における開示によれば、最上位16進数字(すなわち、換言すれば、特定の廃棄可能ファイルに関するクラスタの4つの最上位ビット)は、特定のファイルに割り当てられた廃棄優先度レベルに対応する同じ値に設定される。前に説明したように、廃棄優先度レベルを示すために使用される最上位ビットの数字mは、4とは異なるものであってもよい(すなわち、m≦4)。
【0052】
図9は、例示的な実施形態による例示的な部分的NTFSテーブル900を示す。NTFSテーブル900は、ファイル名、ファイルサイズなどのファイルの項目を保持する。NTFSテーブル900は、「普通の」データフローに応じて変化するファイルの「通常の」データ(例えば、データ920)を保持するためのデータフィールド910を含む。本願明細書における開示によれば、NTFSテーブル900はまた、各評価済みファイルの廃棄情報(例えば、廃棄情報930)を保持するための「廃棄情報」フィールド915を含む。また、廃棄情報フィールド915は、廃棄優先度レベル以外の情報を含んでもよい。例えば、廃棄情報フィールド915は、ファイルを供給したサーバおよびファイルを廃棄しなければいけない期限の満了時間に関する情報を含んでもよい。FATベースのファイルシステムとは異なり、NTFSベースのファイルシステムにおいて、廃棄可能ファイルに割り当てられた廃棄値は、ビットセットによって要求される最大数に制限されない。これは、廃棄値の範囲が自由に選択可能であることを意味する。例えば、廃棄値は、1〜25の範囲のものでありうる。NTFSは、例示的な非FATファイルシステムである。一般に、対応する廃棄値は、マーキングされたファイルに対応する非FATベースのファイルシステムエントリのデータフィールドに設定されてもよい。
【0053】
図10は、例示的な実施形態によるストレージデバイスのファイルシステム1000の論理構成を示す。ストレージアロケータ(例えば、図1のストレージアロケータ144)は動作するストレージデバイスのファイルシステム1000またはファイルシステム1000のイメージのいずれかを保持するか、またはストレージアロケータはファイルシステム1000へのアクセスを有してもよい。
ファイルシステム1000は、ブートセクション1010と、ファイルシステム1000に関連するFAT1020と、ディレクトリテーブル1030と、ファイル領域1040と、廃棄可能ファイル領域1050とを含む。FAT1020は、廃棄可能ファイルの廃棄優先度レベルを含む廃棄可能ファイル割り付け領域1025を含む。ディレクトリテーブル1030は、ストレージデバイスに格納されるファイルであれば、どのファイル(すなわち、廃棄可能ファイルおよび/または廃棄不能ファイル)にでもアクセスするためのアクセス情報を含む。ファイル領域1040は、廃棄不能ファイルを含む。インデックスおよびデータベース領域1045は、廃棄可能ファイルのインデックスと、さらに、廃棄可能ファイルに関係するメタデータとを保持する。インデックスおよびデータベース領域1045に保持されるインデックスおよびメタデータは、廃棄レベルを算出するために使用されるが、実際の廃棄プロセス中には要求されない。廃棄可能ファイル領域1050は、廃棄可能ファイルを保持する。
【0054】
図11は、本願明細書における開示によるファイルを管理する方法を示す。図11は、図1に関連して記載される。時間T0で、2つのユーザファイル(すなわち、ファイル「F1」および「F2」)が、記憶領域110に最初に格納されると仮定する。ファイル「F1」および「F2」は、ユーザファイルであるため、ユーザ領域170に格納され、ストレージアロケータ144によってファイルに割り当てられる廃棄レベルはゼロである。記憶領域110の全記憶容量がT(1110と示す)であり、ファイルF1およびF2が、ストレージデバイス100に格納されるため、残りの空き記憶空間190(図1を参照)のサイズはf(1120と示す)である。パブリッシャが、記憶領域110に3つの未承認ファイルの格納を望むと仮定する。前述したように、記憶領域110にパブリッシャの3つの未承認ファイルを格納することで、先々のユーザファイル用に保存される所定のストレージ使用量安全マージン(1130と示す)が少なくならないかを決定するために、ストレージアロケータ144が、ストレージデバイス100における空き記憶空間190(または1120のf)のサイズを評価する。パブリッシャの3つの未承認ファイルを確認することで、ストレージ使用量安全マージン1130(すなわち、所定のストレージ使用量安全マージン)が少なくなれば、ストレージアロケータ144は、これらのファイルの格納をやめる。
【0055】
この例において、ストレージアロケータ144は、ストレージ使用量安全マージン1130を低減することなく、パブリッシャの3つの未承認ファイルが記憶領域110に格納可能であることを決定する。したがって、時間T1で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にパブリッシャの3つの未承認ファイルを格納できる。3つのパブリッシャの未承認ファイルは、「P1」、「P2」、および「P3」として示される。ストレージアロケータ144はまた、ストレージデバイス100のユーザによってファイルP1、P2、およびP3が使用される確率を決定し、これらのファイルの各々に対応する廃棄レベルを割り当てる。次に、ストレージアロケータ144は、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルにファイルに割り当てられた廃棄レベルを格納する。
【0056】
時間T2で、ストレージデバイス100のユーザは、記憶領域110に、3つ以上のファイル(すなわち、ファイル「F3」および「F4」)の格納を望む。ストレージアロケータ144は、追加のファイル(すなわち、ファイルF3およびF4)を格納するのに十分な格納空間が記憶領域110にあるかどうかを決定するために、ストレージデバイス100における空き記憶空間190のサイズ(または1120のf)を再評価する。この例において、ストレージアロケータ144は、現在の空き記憶空間がファイルF3およびF4を収容可能であることを決定する。したがって、時間T2で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にファイルF3およびF4を格納できる。
【0057】
ファイルF3およびF4がユーザファイルであるため、ストレージデバイス100のユーザによってファイルF3およびF4が使用される確率は、ユーザファイルが、ユーザがファイルF3およびF4を使用するとしても、その回数に関係なく、パブリッシャファイルよりも高いストレージ優先度を有するため重要ではない。したがって、ストレージアロケータ144は、廃棄レベル「0」をファイルF3およびF4に割り当て、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルに割り当て廃棄レベルを格納する。
時間T3で、ストレージデバイス100のユーザは、記憶領域110に、別のファイル(すなわち、ファイル「F5」)の格納を望む。ストレージアロケータ144は、追加のファイル(すなわち、ファイルF5)を格納するのに十分な格納空間が記憶領域110にあるかどうかを決定するために、ストレージデバイス100における空き記憶空間190のサイズ(または1120のf)を再評価する。
【0058】
この例において、ストレージアロケータ144は、現在の空き記憶空間がファイルF5を収容可能であることを決定する。したがって、時間T3で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にファイルF5を格納できる。図11に示すように、ユーザファイルF5を格納すると、ストレージ使用量安全マージンが少なくなる。すなわち、ファイルF1〜F5およびP1〜P3が記憶領域110に格納された後に残る記憶領域110の空き記憶空間fは、ストレージ使用量安全マージン1130より少なくなる。したがって、ストレージアロケータ144は、パブリッシャのファイル(すなわち、P1、P2、およびP3)の1つを取り除くことによって、ストレージ使用量安全マージンを復旧または回復させる。前に説明したように、ユーザファイルのストレージ優先度が最も高いため、ストレージ使用量安全マージンが、1つ以上のパブリッシャファイルを取り除く(すなわち、削除する)ことによって復旧または回復される。 前述したように、ストレージアロケータ144が、各格納された廃棄可能ファイルに割り当てた廃棄優先度レベルに基づいて、ストレージアロケータ144によって、記憶領域110から1つまたは複数のパブリッシャファイルを取り除くべきであるという決定がなされる。
【0059】
図11を再度参照しながら、格納されたパブリッシャファイルP1〜P3の中から、パブリッシャファイルP3に最高廃棄優先度レベル(例えば、13)を割り当てたと仮定する。したがって、時間T4で、ファイルP3は記憶領域110から取り除かれることで、空き記憶空間190が拡大される。時間T4で、空き記憶空間190のサイズ(または1120のf)が、ストレージ使用量安全マージン1130より大きいため、パブリッシャファイルをさらに取り除く必要はない。
【0060】
ストレージデバイス100のユーザは、1つ以上のユーザファイルを取り除きたいこともある。時間T5で、ユーザは、自分のファイルのうちの2つ(すなわち、ファイルF4およびF5)を取り除き、空き記憶空間190がさらに拡大される。本願明細書に記載したように、空き記憶空間の取り除きやストレージ使用量安全マージンの回復は、必要に応じて多くの廃棄可能ファイルを取り除くことによって行われるため、ファイルF4およびF5を取り除くことは、空き記憶区間190またはストレージ使用量安全マージンのサイズとは関係がない。パブリッシャは、記憶領域110に未承認ファイルを格納することを望んでいると考えられる。前述したように、ストレージアロケータ144は、記憶領域110にパブリッシャの未承認ファイルを格納することで、ストレージ使用量安全マージン1130が少なくならないかを決定するために、空き記憶空間190のサイズ(または1120のf)を評価する。パブリッシャの新しい未承認ファイルを格納することで、ストレージ使用量安全マージン1130が少なくなれば、ストレージアロケータ144は、このファイルの格納をやめる。
【0061】
この例において、ストレージアロケータ144は、パブリッシャの新しい未承認ファイル(すなわち、ファイル「P4」)が、ストレージ使用量安全マージン1130を低減することなく記憶領域110に格納可能であることを決定する。したがって、時間T6において、ストレージアロケータ144により、ストレージコントローラ120が、記憶領域110にパブリッシャのファイルP4を格納できる。ストレージアロケータ144はまた、ストレージデバイス100のユーザによってファイルP4が使用される確率を決定し、このファイルに対応する廃棄レベルを割り当てる。次に、ストレージアロケータ144は、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルにファイルP4に割り当てられた廃棄レベルを格納する。新しいパブリッシャのファイルおよび新しいユーザファイルを格納し、格納されたファイルを取り除くプロセスは、記憶領域110に新しいファイルが追加されるたびに、ストレージアロケータ144が、空き記憶空間190の現在のサイズを評価し、1つまたは複数のパブリッシャファイル(存在すれば)のうちのどのファイルが記憶領域110から取り除かれる必要があるかを決定するまで続きうる。
【0062】
廃棄レベルを廃棄可能ファイルに割り当てることは、ユーザの経験や好み、ユーザの全地球測位システム(「GPS」)位置、および/または他の基準に基づいたものであってもよい。例えば、ストレージデバイスのユーザは、(それまでのユーザの経験に基づいて)ある一定のタイプの音楽を好むようであれば、ストレージアロケータは、パブリッシャファイルが、ユーザが好きなタイプの音楽の1つである音楽を含めば、比較的低い廃棄優先度レベル(例えば、1〜15の範囲の3)をパブリッシャファイルに割り当ててもよい。しかし、パブリッシャの音楽がユーザの好みでなければ(すなわち、それまでのユーザの経験に基づいて)、ストレージアロケータは、より高い廃棄優先度レベル(例えば、1〜15の範囲の12)を関係するパブリッシャファイルに割り当ててもよい。廃棄レベルを廃棄可能ファイルに割り当てるために使用される基準は、ファイルの予測使用、ファイルの使用に関連する予測収入、ファイルの種類、ファイルサイズ、ストレージデバイスにおけるファイルの場所、ファイルの古さ、および本願明細書に明示したような他の基準やパラメータを含んでもよい。他の基準が、単独でまたは本願明細書において述べた任意の基準と組み合わせて、同様に使用されてもよく、廃棄レベルの割り当ては、1つ以上の基準を用いて行われてもよい。加えて、廃棄レベルを異なる廃棄可能ファイルに割り当てるために、異なる基準が使用されてもよい。
【0063】
別の例において、パブリッシャが、位置依存性の広告(すなわち、特定の区域内で提供する製品やサービスに関する広告)をユーザに送りたければ、ストレージアロケータは、ユーザの位置変化に応じて変化するパブリッシャの広告に廃棄優先度レベルを割り当ててもよい。すなわち、ユーザが、特定の区域から離れることによって、特定の区域で提供される製品やサービスの消費に感心がなくなることが想定されうるため、ユーザが特定の場所から遠ざかるほど、廃棄レベルが高くなる。
【0064】
関連するファイルシステムにおいて、ファイルをマーキングし、マーキングされたファイルに廃棄レベルを割り当てる本願明細書において開示される手法には、多くの有用な応用がありえ、そのうちの1つでは、ユーザファイルに対して十分な記憶空間を確保するために、ストレージ使用量安全マージンが回復されることに留意するべきである。例えば、ファイルクラスタをより低性能のフラッシュモジュールに再マッピングしたり、リクエストに応じてクラスタをクリアしたりするために、ファイルに割り当てられた廃棄レベルが使用されてもよい。
【0065】
本願明細書において、冠詞は、文脈に応じて、その冠詞の文法上の目的語が単数あるいは複数(すなわち、少なくとも1つ)であることを言及するように使用される。一例として、文脈に応じて、「要素」は、1つの要素または2つ以上の要素を意味しうる。本願明細書において、「〜を含む」という用語は、「〜を含むが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。「または」と「および」という用語は、本願明細書において、文脈に特別な指示が明示されていない限り、「および/または」という用語を意味し、その用語と交換可能に使用される。「〜など」という用語は、本願明細書において、「〜などであるが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。
【0066】
以上、本発明の例示的な実施形態を記載してきたが、当業者であれば、開示された実施形態の修正が、本発明の範囲内でなされることは明らかである。したがって、別の実施形態は、より多くのモジュール、より少ないモジュール、および/または機能的に同等のモジュールを含んでもよい。本願明細書における開示は、SD駆動型フラッシュメモリカード、フラッシュストレージデバイス、非フラッシュストレージデバイス、ユニバーサルシリアルバス(「USB」)インターフェイスが設けられた「ディスクオンキー」デバイス、USBフラッシュドライブ(「UFD」)、マルチメディアカード(「MMC」)、セキュアデジタル(「SD」)、ミニSD、およびマイクロSDなど、様々なタイプの大容量ストレージデバイスに関連する。したがって、添付の特許請求の範囲は、本願明細書の開示によって限定されるものではない。
【技術分野】
【0001】
本発明は、一般に、ストレージデバイスに関し、さらに詳しく言えば、ストレージデバイスにおけるファイルを管理する方法およびデバイスに関する。
【背景技術】
【0002】
不揮発性ストレージデバイスの使用が、携帯性、小型の物理的サイズ、および大記憶容量により、長年にわたって急増してきた。ストレージデバイスには、様々に設計されたものがある。「埋め込み型」として見なされるストレージデバイスもあり、埋め込み型とは、すなわち、ユーザが、ストレージデバイスが動作するホストデバイスからストレージデバイスを取り外すことができず、取り外しが想定されていないことを意味する。一方で、取り外し可能なストレージデバイスもあり、取り外し可能とは、すなわち、あるホストデバイスから(例えば、デジタルカメラから)ストレージデバイスを移動可能であり、またはあるストレージデバイスと別のものとを取り替えることができることを意味する。
【0003】
ストレージデバイスに格納されたデジタルコンテンツは、ストレージデバイスのホストからのものでありうる。例えば、例示的なホストであるデジタルカメラは、画像をキャプチャし、その画像を対応するデジタルデータに変換する。次に、デジタルカメラは、共に動作するストレージデバイスにデジタルデータを格納する。ストレージデバイスに格納されたデジタルコンテンツはまた、リモートソースからのものであってもよく、すなわち、デジタルコンテンツは、例えば、データネットワーク(例えば、インターネット)や通信ネットワーク(例えば、携帯電話ネットワーク)を通してストレージデバイスのホストに送られ、ストレージデバイスのホストによってダウンロードされうる。リモートソースは、例えば、サービスプロバイダやコンテンツプロバイダであってもよい。以下、サービスプロバイダおよびコンテンツプロバイダを総称して「パブリッシャ」と呼ぶ。
【0004】
ストレージデバイスのユーザは、メディアコンテンツまたはパブリッシャからの広告を要求することによって、積極的にメディアコンテンツおよび広告をダウンロードしうる。しかし、パブリッシャの中には、ユーザの許可を求めずに、ユーザにコンテンツを送信して収入増を試みるものがおり、場合によっては、このようなコンテンツがストレージデバイスにダウンロードされていることをユーザに悟られないようにすることもある。本願明細書において、ユーザの合意を得ずにパブリッシャがユーザに送信するコンテンツのことを「未承認コンテンツ」と呼ぶ。多くの場合、未承認コンテンツは、パブリッシャに料金を支払った後かまたは支払い義務が生じた後にユーザによって消費されるように意図されている。
【0005】
パブリッシャは、未承認コンテンツをユーザのストレージデバイスにダウンロードすることで、ユーザが有料の未承認コンテンツを最終的に消費して、収入増につなげることを期待している。ユーザが有料コンテンツを消費することを期待しながら、ユーザの合意を得ずに、パブリッシャがストレージデバイスに未承認コンテンツを格納することは、メディアパブリッシング業界では「予測委託販売」として知られている概念である。しかし、未承認コンテンツは、ストレージデバイスのユーザが、その存在を知らずにまたは消費しようと思わなければ、ストレージデバイスに格納されたままでありうる。ストレージデバイスに未承認コンテンツを格納すると、ストレージデバイス上でユーザが利用可能な(すなわち、空いた)記憶空間が減るため、ユーザの視点から言えば、望ましくない。誰か他の人(すなわち、一部のパブリッシャ)が、ストレージデバイスの記憶空間の一部を占有しているために、ユーザ自身のコンテンツ(例えば、音楽ファイル)用のストレージデバイス空間が少なくなっていることや、未承認コンテンツを削除することで、占有されていた記憶空間を取り戻す必要があることにユーザが気づくこともありうる。
【発明の概要】
【0006】
ユーザの記憶空間の一部を占有する問題への1つの部分的な解決策として、パブリッシャのウェブサイトをブロックするなどして、ストレージデバイスへのパブリッシャのアクセスをブロックする方法がある。この解決策は、ユーザにとって許容可能な場合もあるが、パブリッシャにとっては売り上げが落ち、潜在的な収入源を失ってしまうため、パブリッシャの立場からすると問題である。この問題に対する別の部分的解決策として、コンテンツをホストにパブリッシングし(すなわち、これらのホストのストレージデバイスにコンテンツファイルを格納し)、コンテンツが無関係になるとコンテンツを取り除く方法がある。言い換えれば、コンテンツの出所であるパブリッシャは、コンテンツが無関係になると、格納された未承認コンテンツをストレージデバイスから取り除く。未承認コンテンツは、コンテンツ消費時間が経過するか、またはユーザがコンテンツを消費しそうにないことが見受けられると、無関係なものとして見なされる。
【0007】
以上のことから、未承認ファイルの問題を解消することが必要とされている。詳細には、パブリッシャが、商取引の過程で未承認コンテンツをストレージデバイスへダウンロードしようとすることは許可されるべきであるが、これらのダウンロードは、ユーザ経験を著しく抑制する影響をもつものであってはならない。
【0008】
したがって、ストレージデバイスに未承認コンテンツを収容するのに必要な記憶空間が、ユーザファイルに要求されない限り、ストレージデバイスに未承認ファイルを格納し、ユーザファイルの空き記憶空間の最小サイズを確保するために、ストレージデバイスから未承認ファイルを取り除くことが可能であることは有益でありうる。様々な実施形態がこのようなファイル管理を実施するように設計され、本願明細書においてそれらの例をいくつか提供する。
【0009】
前述した問題を解消するために、ストレージデバイスに格納されたファイルまたは格納予定のファイルは、ストレージデバイスに関連づけられたファイルシステムの構造において、廃棄不能なものまたは廃棄可能なもののいずれかとしてマーキングされる。マーキングされた各ファイルは、ファイルに関連づけられた廃棄優先度レベルを有する。ストレージデバイスにファイルを格納しても、ユーザファイル用に確保されているストレージ使用量安全マージンが所定のマージンを超えて、少なくなることがない場合にのみ新しいパブリッシャファイル(すなわち、未承認ファイル)をストレージデバイスに格納することが許容される。一方で、ユーザファイルは所定の幅を超えてストレージ使用量安全マージンを少なくしたとしても、ストレージデバイスに格納されうる。しかし、このような場合、ストレージ使用量安全マージンの所定の幅は、1つ以上の廃棄可能ファイルをストレージデバイスから取り除くことによって回復する。廃棄優先度レベルが、所定の廃棄しきい値に等しいか、またはこのしきい値より高ければ(または本願明細書において説明するように、低ければ)、廃棄可能ファイルがストレージデバイスから取り除かれる。
【0010】
さまざまな例示的な実施形態が、限定的なものではないという目的で、添付の図面に例示される。簡潔かつ明確に示すために、以下に参照される図面に示す要素は、必ずしも一定の縮尺で描かれたものではないことに留意するべきである。また、適切であると考慮される場合、参照番号は、同様の対応する要素または類似した要素を示すために図面において繰り返されることもある。
【図面の簡単な説明】
【0011】
【図1】例示的な実施形態によるストレージシステムのブロック図である。
【図2】別の例示的な実施形態によるストレージシステムのブロック図である。
【図3】例示的な実施形態によるストレージアロケータのブロック図である。
【図4】例示的な実施形態によるファイルを管理する方法を示す図である。
【図5】例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルのストレージを管理する方法を示す図である。
【図6】例示的な実施形態によるFAT32形式ファイルシステムにおける1つ以上の未承認ファイルをマーキングする方法を示す図である。
【図7】FAT32テーブルに関連づけられた例示的なディレクトリ領域を示す図である。
【図8】例示的な実施形態によるFAT32テーブルを示す図である。
【図9】例示的な実施形態によるNTFSテーブルを示す図である。
【図10】例示的な実施形態によるFATベースのファイルシステムの論理イメージを示す図である。
【図11】本願明細書における開示によるファイルの格納を管理する方法を示す図である。
【発明を実施するための形態】
【0012】
以下の記述は、例示的な実施形態のさまざまな詳細を提供する。しかし、この記述は、特許請求の範囲を限定することを意図したものではなく、本発明のさまざまな原理およびその実行方法を説明するためのものである。
【0013】
未承認コンテンツおよび関連する問題を解消するために、ユーザファイルは、他のファイルより高いストレージ優先度が与えられ、この優先度を確保するために、ストレージ使用量安全マージンが維持される。「ユーザファイル」とは、ストレージデバイスのユーザが、積極的に格納したファイルや、ストレージデバイスへの格納を承認したファイルである。例えば、ユーザが自らのストレージデバイスにダウンロードする音楽ファイルは、ユーザファイルと見なされる。ユーザによってリクエストまたは格納許可が出されているため、ユーザファイルは、「承認」ファイルと見なされる。
【0014】
「他のファイル」は、本願明細書において、「パブリッシャファイル」および「未承認ファイル」として参照される。「パブリッシャファイル」とは、ユーザがファイルをリクエストしていないのにストレージデバイスに格納されたファイルや、ユーザが、少なくとも、短時間ではない間、ファイルの格納に気がつかずに格納されたファイルのことである。ユーザは、未承認ファイルの使用を望まないこともある。使用されない未承認ファイルは、ユーザのストレージデバイスの貴重な記憶空間を消費する傾向にある。したがって、本願明細書に開示された原理によれば、このようなファイルは、ファイルを格納してもストレージ使用量安全マージンを少なくしない場合にのみ、ストレージデバイスへの格納が許可される。先々のユーザファイル用の格納空き記憶空間(すなわち、ストレージ使用量安全マージン)を維持することによって、ユーザファイルにストレージ優先度が与えられる。ストレージ使用量安全マージンは、要求または所望されれば、ストレージデバイスにユーザファイルが格納可能であることを確保するために維持される必要がある。
【0015】
何らかの理由で、ストレージ使用量安全マージンが所定のものより少なくなれば、ストレージ使用量安全マージンを回復させるために、ストレージデバイスから1つ以上の未承認ファイルが取り除かれる(すなわち、削除される)。ストレージ使用量安全マージンを維持することで、追加のユーザファイルをストレージデバイスにダウンロードするための記憶空間が確保される。このため、未承認ファイルは、ストレージファイルシステムの構造において「廃棄可能」なものとしてマーキングされ、要求されれば、少なくともストレージ使用量安全マージンを維持するのに要求された空き記憶空間を取り戻すために後で取り除かれる。
【0016】
ユーザがさまざまな廃棄可能ファイルを使用する可能性は、廃棄可能ファイルごとに異なるため、ファイルの使用の確率、ファイルの使用に関連する考えられる収入、ファイルサイズ、ファイルの種類、ファイルの場所、ファイルの古さなどの1つ以上の基準に応じた廃棄優先度レベルが、事前に、各未承認ファイル(すなわち、各廃棄可能ファイル)に割り当てられる。例えば、廃棄優先度レベルは、収入の可能性によって決定されてもよい。別の例によれば、映画の予告編や広告は、一般に、ユーザが予告編や広告の視聴を好まないため、実際の映画より高い廃棄優先度を有しうる。別の例によれば、ユーザによって最も使用されがちな1つ以上の廃棄可能ファイルには、最低廃棄優先度レベルが割り当てられ、すなわち、このようなファイルは、ストレージデバイスから最も取り除かれないファイルである。言い換えれば、使用確率が高いほど、ファイルに割り当てられる廃棄優先度レベルのレベルが低い廃棄可能ファイルとなる。1つ以上の廃棄可能ファイルを取り除いても、所定のストレージ使用量安全マージンが完全に回復していなければ、所定のストレージ使用量安全マージンが回復されるまで、ストレージデバイスから追加の廃棄可能ファイルが取り除かれる。
【0017】
簡潔に言えば、ファイルシステムが、コンピュータファイルを格納し体系化するための手法を実施する。ファイルシステムは、データの格納、階層的体系化、操作、ナビゲーション、アクセス、および検索のために実施される抽象データ型およびメタデータのセットを含む。抽象データ型およびメタデータはコンピュータファイル(本願明細書において、簡潔にするために「データファイル」または「ファイル」と称する)のアクセス、操作、および起動が可能な「ディレクトリツリー」を形成する。「ディレクトリツリー」は、典型的に、ルートディレクトリおよび任意のサブディレクトリを含む。ディレクトリツリーは、1つ以上の「ディレクトリファイル」としてファイルシステムに格納される。ファイルシステムに含まれるメタデータおよびディレクトリファイルのセットは、本願明細書において、「ファイルシステム構造」と呼ばれる。したがって、ファイルシステムは、データファイルのアクセス、操作、更新、削除、および起動を行いやすいようにするデータファイルおよびファイルシステム構造を含む。
【0018】
ファイルアロケーションテーブル(「FAT」)は、例示的なファイルシステム構成である。FATファイルシステムは、DR−DOS、OpenDOS、MS−DOS、Linux、Windows(登録商標)などを含むさまざまなオペレーティングシステムで使用される。FAT形式のファイルシステムは、どの記憶領域が空いているかまたは割り付けられているか、各ファイルがストレージデバイスのどこに格納されているかについての情報を集めたテーブルを使用する。テーブルのサイズを制限するために、記憶空間が「クラスタ」と呼ばれる連続するセクタグループ中のファイルに記憶空間が割り当てられる。ストレージデバイスの進化に伴い、クラスタの最大数も増大し、クラスタを識別するために使用されるビット数も増大してきた。FAT形式のバージョンは、テーブルビット数に由来し、例えば、FAT12は12ビットを使用し、FAT16は16ビットを使用し、FAT32は32ビットを使用する。
別のファイルシステム構成は、ニューテクノロジーファイルシステム(「NTFS」)として知られている。現在では、NTFSが、Windows NTを始め、それ以降のバージョンのWindows 2000、Windows XP、Windows Server 2003、Windows Server 2008、およびWindows Vistaの標準的なファイルシステムである。FAT32およびNTFSは、ストレージデバイス100と共に提供されうる例示的なファイルシステムである。
【0019】
図1は、典型的なストレージデバイス100を示す。ストレージデバイス100は、ユーザファイルまたはパブリッシャファイルでありうる様々なタイプのファイル(例えば、音楽ファイル、ビデオファイルなど)を格納するための記憶領域110を含む。ストレージデバイス100はまた、データおよび制御ライン130を介して記憶領域110を管理するストレージコントローラ120を含む。ストレージコントローラ120はまた、ホストインターフェイス150を介してホストデバイス140との通信を行う。ホストデバイス140は、専用ハードウェアまたは汎用コンピューティングプラットフォームであってもよい。
【0020】
記憶領域110は、例えば、NANDフラッシュの種類のものであってもよい。ストレージコントローラ120は、例えば、「読み出し」、「書き込み」、および「消去」動作、ウェアレベリングなどを制御することによって、さらには、ホスト140との通信を制御することによって、記憶領域110へのデータ転送/記憶領域110からのデータ転送およびホストデバイス140へのデータ転送/ホストデバイス140からのデータ転送のすべてを制御する。記憶領域110は、例えば、ユーザファイルおよびパブリッシャファイル、認証ホストデバイスによってのみ使用可能な保護データ、およびストレージコントローラ120によって内部のみで使用されるセキュリティデータを含んでもよい。ホスト(例えば、ホスト140)は、記憶領域110に直接アクセスできない。すなわち、例えば、ホスト140が、ストレージデバイス100からのデータを要求するかまたは必要とすれば、ホスト140は、ストレージコントローラ120からデータをリクエストする必要がある。ストレージデバイス100に格納されたデータファイルへのアクセスを容易に行うために、ストレージデバイス100には、ファイルシステム160が設けられる。
【0021】
記憶領域110は、3つの部分、すなわち、ユーザ領域170、パブリッシャ領域180、および空き記憶空間190に機能的に分割される。ユーザ領域170は、ユーザファイルが格納される記憶領域110内の記憶空間である。パブリッシャ領域180は、パブリッシャファイルが格納される記憶領域110内の記憶空間である。空き記憶空間190は、記憶領域110内の空いている記憶空間である。空き記憶空間190は、ユーザファイルまたはパブリッシャファイルを保持するために使用されうる。空き記憶空間190にユーザファイルを格納すると、ユーザファイルを保持する記憶空間は、空き記憶空間190から取り去られ、ユーザ領域170に追加される。同様に、空き記憶空間190にパブリッシャファイルを格納すると、パブリッシャファイルを保持する記憶空間は、空き記憶空間190から取り去られ、パブリッシャ領域180に追加される。ユーザファイルまたはパブリッシャファイルが、記憶領域110から取り去られれば(すなわち、除去されれば)、空いた記憶空間は、空き記憶空間190に追加される(戻る)。
【0022】
ストレージデバイス100のユーザは、空き記憶空間190のサイズが許容すれば、ホスト140から記憶領域110へユーザファイルをダウンロードできる。ダウンロードされたユーザファイルは、空き記憶空間190に格納され、前に説明したように、このファイルを保持する記憶空間は、空き記憶空間190から取り去られ、ユーザ領域170に追加される。前に説明したように、ユーザファイルは、他の(例えば、パブリッシャ)ファイルより高い優先度を有し、その優先度を確保するために、所定のストレージ使用量安全マージンが設定され、必要であれば、以下に記載する方法で回復される。
【0023】
ホスト140は、空き記憶空間190の回復を行うためのストレージアロケータ144を含む。ストレージアロケータ144は、ハードウェア、ファームウェア、ソフトウェア、またはこれらの任意の組み合わせであってもよい。一般に、ストレージアロケータ144は、ホスト140との間で通信されるファイル(例えば、ファイル142)が、ユーザファイルであるのかまたはパブリッシャファイルであるのかを決定し、次に、それに応じて(すなわち、廃棄不能ファイルまたは廃棄可能ファイルとして)通信されたファイルをマーキングする。
【0024】
ストレージアロケータ144が、ホスト140との間で通信されるファイル(例えば、ファイル142)が廃棄不能、例えばユーザファイルであることを決定すれば、ストレージアロケータ144は、通常の方法で記憶領域110にファイルを格納する。前に説明したように、廃棄不能ファイルを保持する記憶領域110内の記憶空間は、ユーザ領域170に追加されるか、またはユーザ領域170の一部である。しかし、ホスト140との間で通信されるファイルが、例えばパブリッシャファイルであるために廃棄可能であるとストレージアロケータ144が決定すれば、ストレージアロケータ144は、ファイルを廃棄可能なものとしてマーキングする。また、空き記憶空間190が所定のストレージ使用量安全マージンより大きければ、ストレージアロケータ144は、空き記憶空間190にマーキングされた廃棄可能ファイルを格納し、前に説明しれたように、廃棄可能ファイルを保持する空き記憶空間190内の記憶空間は、空き記憶空間190から取り去られ(すなわち、空き記憶空間は低減され)、パブリッシャ領域180に追加される(この追加は、廃棄可能ファイル182として論理的に示される)。
前に説明したように、パブリッシャファイルがユーザによって使用されうる可能性は、パブリッシャファイルごとに異なりうるため、使用可能性ができるだけ低いパブリッシャファイルは、記憶領域110から取り除く最初の候補となる。したがって、ファイルを廃棄不能または廃棄可能としてマーキングすることに加えて、ストレージアロケータ144は、記憶領域110への廃棄可能ファイルの格納前、格納と同時、または格納後に、各廃棄可能ファイルに廃棄優先度レベルを割り当てる。
【0025】
ファイルを廃棄不能または廃棄可能としてマーキングし、ストレージアロケータ144によって廃棄優先度レベルを割り当て、かつストレージデバイス100のファイルシステム160(またはそのイメージ)を使用することによって、ストレージアロケータ144は、記憶領域110におけるユーザファイルおよびパブリッシャファイルの数、ならびに記憶領域110内のファイルサイズおよび論理場所を「知る」。この情報(すなわち、ファイルの数、サイズ、および場所)を、特に、1つ以上のマーキングされたファイルに基づいて知ることで、ストレージアロケータ144は、記憶領域110を管理し、記憶領域110の承認および未承認ファイルの格納を管理する。記憶領域110を管理するかまたは記憶領域110におけるファイルの格納を管理することは、例えば、廃棄可能としてマーキングされた1つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、廃棄可能としてマーキングされたすべてのファイルを取り除くことで記憶領域を解放することと、ファイルのクラスタを性能がより低いストレージモジュールに再マッピングすることとを含んでもよい。記憶領域110または記憶領域に格納されたファイルを管理することが、記憶領域110または記憶領域110に格納されたファイルの他の態様、追加の態様、または別の態様を管理することを含んでもよい。
【0026】
ストレージアロケータ144はまた、先々のユーザファイル用に元々保存されていた空き記憶空間を回復する(すなわち、所定のストレージ使用量安全マージンを回復する)ために、各廃棄可能ファイルに割り当てられた廃棄レベルによって、廃棄可能なまたは廃棄すべき(すなわち、記憶領域110から削除または取り除かれる)廃棄可能ファイルの順番を知る。したがって、ユーザが、記憶領域110に新しいユーザファイルを格納したいが、そのユーザファイルを収容するための十分な空き容量空間がなければ(すなわち、ストレージ使用量安全マージンが所定のものより少ないことを意味する)、ストレージアロケータ144は、廃棄可能ファイルに割り当てられた廃棄優先度レベルを使用して、所定のストレージ使用量安全マージンが完全に回復するまで、より多くの空き記憶空間を取り戻す(すなわち、空き記憶空間190を拡張する)ために、廃棄可能ファイルを1つずつ繰り返し削除する。前に説明したように、完全に回復されたストレージ使用量安全マージンは、先々のユーザファイル用に十分な空き記憶空間が確保される可能性が高い。廃棄可能ファイルは、ユーザが格納した廃棄可能ファイルをいずれ使用したいと思うかもしれないということが考慮されているため、新しいユーザファイルを格納するリクエストの受信にのみ応答して、ストレージデバイス100から取り除かれるかまたは削除され、したがって、廃棄可能ファイルは、そのファイルを収容する記憶空間が新しいユーザファイルに要求される場合のみ、ストレージデバイスから取り除かれる。ストレージアロケータ144は、ホスト140に埋め込まれるかまたは組み込まれてもよく、あるいはホスト140(四角形の破線)およびストレージデバイス100の外部に存在してもよい。
【0027】
ストレージアロケータ144は、ストレージデバイス100またはそれに関連するファイルシステムの典型的なイメージを有する。ストレージアロケータ144は、ファイルを廃棄不能または廃棄可能としてマーキングし、各廃棄可能ファイルに廃棄レベルを割り当てるために、ストレージデバイスのファイルシステムイメージを使用する。異なるファイルシステムが異なる構造を有するため、ファイルのマーキング(すなわち、廃棄不能または廃棄可能なものとして)および廃棄レベルの割り当ては、図6〜図10に詳しく述べるように、以下に記載される使用されたファイルシステム構造に適応される。
【0028】
図2は、別の例示的な実施形態による携帯可能なストレージデバイス200のブロック図である。ストレージコントローラ220は、ストレージコントローラ120のように機能し、ストレージアロケータ244は、ストレージアロケータ144のように機能する。ストレージアロケータ244は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組み合わせであってもよい。ストレージアロケータ244は、ストレージコントローラ220と内部的に協働する。ストレージコントローラ220が、ホスト240から記憶領域210にファイルを格納するための格納要求を受信すると、ストレージコントローラ220は、格納リクエストをストレージアロケータ244に知らせ、ストレージアロケータ244は、ストレージデバイス200に関連するファイルシステムの構造において廃棄不能または廃棄可能としてファイルをマーキングする。新しいファイルが廃棄可能であるとストレージアロケータ244が決定すれば、ストレージアロケータ244は、ファイルの使用確率に応じて、廃棄優先度レベルを新しいファイルに割り当てる。次に、ストレージアロケータ244は、空き記憶空間290の現在のサイズを評価し、新しいファイルのためのスペースを空けるために、記憶領域210から1つ以上の廃棄可能ファイルを取り除かれなければならない(すなわち、削除しなければならない)。1つまたは複数の廃棄可能ファイルが、ストレージデバイスから取り除かれるべきであれば、ストレージアロケータ244は、どのファイルが現在の取り除かれるべき候補ファイルであるかを決定する。次に、ストレージアロケータ244は、記憶領域210から取り除かれるべき廃棄可能ファイルをストレージコントローラ220に通知し、この通知に応答して、ストレージコントローラ220は、ストレージアロケータ244によって識別された1つまたは複数の廃棄可能ファイルを取り除く。携帯可能なストレージデバイス200のいくつかの構成において、ストレージアロケータ244は、ストレージコントローラ220と記憶領域210との間に機能的に配置されてもよい。ストレージアロケータ244が、ストレージコントローラ220と記憶領域210との間に機能的に配置される構成において、ストレージアロケータ244または記憶領域210は、ストレージコントローラ220の機能の一部を想定する必要がある。このような構成において、記憶領域210は、フラッシュNANDプロトコルより高いレベルで通信するメモリユニットで構成される。
【0029】
図3は、例示的な実施形態によるストレージアロケータ300のブロック図である。ストレージアロケータ300は、メモリユニット310と、プロセッサ320と、インターフェイス330とを含む。メモリユニット310は、(例えば、図2のストレージデバイス200)に関連するファイルシステム構造ストレージデバイスまたはファイルシステム構造のイメージを保持してもよい。プロセッサ320は、ストレージデバイスに関連するファイルシステムを管理する。インターフェイス330は、図1に示すように、ホストと協働し、ストレージデバイスのストレージコントローラと協働するように適応されてもよく、あるいは、図2に示すように、ストレージデバイスのストレージコントローラのみと協働するように適応されてもよい。
【0030】
プロセッサ320は、ストレージデバイスの記憶領域にファイルを格納し、ストレージアロケータ300が動作するストレージデバイスに関連するファイルシステムの構造において、ファイルを廃棄可能または廃棄不能なものとしてマーキングするために、インターフェイス330を介してリクエストを受信するように構成または適応される。インターフェイス330が、図2のストレージコントローラ220に機能的に取り付けられ(ひいては、例えば、ファイルレベルコマンドではなく、SCSIまたはUSB/MSCラップコマンドを受信すれば)、受信したリクエストは、ファイルレベルよりかなり低いレベルにある。すなわち、受信したリクエストは、ホストによって適切に解釈される場合、ファイルに対応する論理ブロックアドレスでセクタを格納するリクエストでありうる。ストレージコントローラ220が、NVMHCIプロトコル、またはNFSや同様のプロトコルなどのネットワーキングファイルシステムプロトコルをサポートすれば、ストレージコントローラ220は、ファイルレベルのリクエストを取得しうる。したがって、ストレージコントローラ220などのストレージコントローラと、インターフェイス330などのインターフェイスとの間の通信は、NVMHCIの実施例やNVMHCIと同様な実施例に限定されない。通信インターフェイス330は、図3に示すように、ストレージアロケータ300の一部をなすものであってもよい。
【0031】
プロセッサ320は、マーキングされたファイルをストレージデバイスに送信するようにさらに構成または適応され、ファイルを廃棄可能としてマーキングすることは、廃棄優先度レベルをファイルに割り当てることを含む。ストレージデバイスによって使用されるファイルシステムが、FATベースのものであれば、プロセッサ320は、対応する値を、マーキングされたファイルに対応するFATにおいて最上位のmビット(すなわち、最上位)(例えば、m=4)を設定することによって、マーキングされたファイルに廃棄優先度レベルを割り当てる。FATエントリにおいて最上位ビットに設定された対応する値またはNTFSディレクトリエントリに設定された値は、ファイルの属性であってもよく、あるいはファイルの属性に関係するものであってもよい。「属性」とは、テーブル内に格納されたコンテンツのタイプに関する情報を含むFATテーブルまたはNTFSテーブルのヘッダにあるメタデータタグまたは何らかのデータ構造を意味する。「広告」、「プレミアムコンテンツ」、「販売促進用の(無料)コンテンツ」は、FATテーブルまたはNTFSテーブルに格納されてもよい例示的なタイプのコンテンツである。廃棄レベルを設定するための別の基準は、例えば、最終アクセスファイル、ファイルサイズ、ファイルタイプなどである。
【0032】
ファイルのマーキング専用のFAT32エントリの最上ビットの数mは、これらのビットが使用されないため、4以下であってもよい。加えて、使用されるビットが大きいほど、使用可能な廃棄優先度レベルが高くなる。例えば、3ビット(すなわち、m=3)を使用すると、8(23 =8)廃棄優先度レベルが得られ、4ビット(すなわち、m=4)を使用すると、16(24 =16)廃棄優先度レベルが得られる(すなわち、廃棄不能ファイルに割り当てられる廃棄優先度レベル「0」を含む)。言い換えれば、プロセッサ320は、マーキングされたファイルが廃棄不能であれば、m最上位ビットの値を0に設定するか、あるいはマーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定する。廃棄優先度レベルは、マーキングされたファイルが、ストレージデバイスから廃棄可能であるのか、または廃棄されるべきなのかの優先度を示す。例えば、実施例に応じて、値「1」は、最低優先度または最高優先度のいずれかで廃棄可能ファイルであることを示すことが可能であり、値「2m −1」は、最高優先度または最低優先度のいずれかで廃棄可能ファイルをそれぞれ示すものでありうる。
【0033】
プロセッサ320は、未承認ファイルがストレージデバイスのユーザによって使用される可能性または確率に関連して前に説明したように、ファイルの予測使用に応じて、廃棄優先度レベルをマーキングされたファイルに割り当ててもよい。プロセッサ320は、ストレージデバイスに新しいファイルを格納するリクエストがあるたびまたは各リクエストの受信に応答して、マーキングされたファイルの廃棄優先度レベルを更新してもよい。プロセッサ320は、ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して、所与のマーキングされたファイルの廃棄優先度レベルを更新してもよい。例えば、以前に高優先度のものであったファイルが、ある一定の時間間隔が経過した後に優先度が下げられてもよい。プロセッサ320は、ファイルが、所定の廃棄しきい値以上の廃棄優先度レベルに関連づけられていれば、ストレージデバイスに格納されたファイルを削除する。プロセッサ320は、ファイルの書き込みや追加の数に基づいて、またはストレージデバイスの空き記憶空間の予測使用や新しいパブリッシャファイルの利用可能性に応じて、廃棄しきい値を(再)設定してもよい。
【0034】
メモリユニット310は、プロセッサ320がストレージデバイスに格納されたファイルに割り当てる廃棄優先度レベルを含む割り当てテーブル340を保持してもよい。加えて、割り当てテーブル340はファイルに割り当てられる廃棄優先度レベルにファイルを関連づけるファイルを識別するとともに、情報を保持してもよい。割り当てテーブル340は、廃棄しきい値をさらに保持してもよい。割り当てテーブル340に保持される情報により、プロセッサ320は、所定のストレージ使用量安全マージンを回復するために、ストレージデバイスから取り除くことが可能な1つまたは複数の廃棄可能ファイルを識別することができる。
【0035】
ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、プロセッサ320は、ストレージデバイスの空き記憶空間(f)のサイズを評価し、ストレージデバイスの空き記憶空間の評価サイズが所定のサイズより大きければ、または所定のサイズより大きくなければ、ストレージデバイスに新しいファイルを格納し、プロセッサ320は、削除可能であるストレージデバイス内にある1つ以上の廃棄可能ファイルを探し、1つまたは複数のこのようなファイルが見つかれば、プロセッサ320は、現在の空き記憶空間(f)を拡張して、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるようにするために、1つまたは複数のファイルを削除する。1つまたは複数の廃棄可能ファイルは、廃棄可能ファイルに関連する廃棄優先度レベルが、所定の廃棄しきい値(例えば、1〜15、例えば、15)以上であれば、ストレージデバイスから削除可能である。
【0036】
空き記憶空間が十分に拡張された後、プロセッサ320は、拡張された空き記憶空間に新しいファイルが格納されることを許容する。「空き記憶空間が十分に拡張される」とは、前述した所定のストレージ使用量安全マージンを少なくすることなく、全空き記憶空間が新しいファイルを収容可能になるまで、あるいは同様に、拡張された空き記憶空間の全サイズが、所定のサイズ以上になるまで、またはすべての廃棄可能ファイルが取り除かれるまで、占有された記憶空間を1つずつ解放することによって、空き記憶空間を拡張することを意味する。
プロセッサ320は、標準的な既製のシステムオンチップ(「SoC」)デバイスまたはシステムインパッケージ(「SiP」)デバイス、あるいは実行時、本願明細書に記載するステップ、演算、および評価を実行する特殊なソフトウェアを備えた汎用処理ユニットでありうる。あるいは、プロセッサ320は、ハードウェアを使用することによって、本願明細書に記載するステップ、演算、および評価を実行する特定用途向け集積回路(「ASIC」)でありうる。
【0037】
図4は、1つの例示的な実施形態による廃棄可能ファイルを格納する方法を示す。図4は、図1に関連して記載される。ステップ410において、ホスト140は、ストレージデバイス100にファイル142を格納するリクエストを受信する。ステップ420において、ストレージアロケータ144は、ファイルを「廃棄可能」または「廃棄不能」としてマーキングし、ステップ430において、空き記憶空間190が十分に大きければ、マーキングされたファイルをストレージデバイス100のストレージコントローラ120に送信する(すなわち、記憶領域110に格納するため)。また、廃棄優先度レベルがファイルに割り当てられるという意味でも、ファイルがマーキングされる。ステップ440において、ストレージアロケータ144は、(ストレージコントローラ120との通信により)記憶領域110を管理するか、あるいはマーキングされたファイルに基づいて、随意にすでにマーキングされていた1つ以上のファイルに基づいて、記憶領域110に格納されるファイルを管理する。
【0038】
図5は、1つの例示的な実施形態によるストレージデバイスにおける廃棄可能ファイルの格納を管理する方法を示す。図5は、図1に関連して記載される。新しいファイルは、ストレージデバイス100に格納される候補である。ストレージデバイス100のファイルシステム160の現在のイメージを知ることで、ストレージアロケータ144は、ステップ510において、空き記憶空間190の現在のサイズ「f」を評価して、現在のサイズがfである空き記憶空間190が、新しいファイル(すなわち、格納候補であるファイル)を収容可能であるかを確認する。一般に、ストレージアロケータ144が、新しいファイルを取り扱う方法は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかに依存する。したがって、ストレージアロケータ144は、新しいファイルがユーザファイルであるのかまたはパブリッシャファイルであるのかを最初に決定する。
【0039】
新しいファイルがユーザファイルである場合
ステップ520において、ストレージアロケータ144は、空き記憶空間190が、新しいユーザファイルを収容できるかをチェックする。空き記憶空間190が、新しいユーザファイルを収容できれば(ステップ520において「Y」で示す)、ストレージアロケータ144は、ステップ560において、所定のストレージ使用量安全マージンが、新しいユーザファイルの格納の可否によって少なくなるかに関係なく、空き記憶空間190に新しいユーザファイルを格納する。ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後、所定のストレージ使用量安全マージンが少なくなれば(すなわち、所定のストレージ使用量安全マージンに対して)、ストレージアロケータ144は、新しいユーザファイルの格納に対してさらなるアクションを起こさない。
【0040】
しかし、ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後に、所定のストレージ使用量安全マージンが少なくなれば、ステップ550において、ストレージアロケータ144は、所定のストレージ使用量安全マージンを維持するために、格納された最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイル・・・などを以下同様に決定する追加のステップを含む。ストレージアロケータ144は、格納された廃棄可能ファイルに割り当てた廃棄レベルに基づいて、最初に削除すべき廃棄可能ファイル、次に削除すべき廃棄可能ファイルを決定する。
【0041】
ステップ520において、空き記憶空間190が新しいユーザファイルを収容できないことをストレージアロケータ144が決定すれば(ステップ520において「N」と示す)、ステップ530において、空き記憶空間190と、廃棄可能ファイルによって消費されている記憶空間とを合わせれば新しいユーザファイルを格納するのに十分かどうかを、ストレージアロケータ144が決定する。記憶空間を組み合わせても不十分であれば(ステップ530において「N」と示す)、これは、削除される廃棄可能ファイルの数に関係なく、新しいユーザファイルを、そのファイルサイズにより、「非ユーザ」記憶領域に格納することができないということを意味する。組み合わせた記憶空間が十分であれば(ステップ530において「Y」と示す)、ステップ540において、新しいユーザファイルに十分な記憶空間を解放するために、格納された廃棄可能ファイルの中から、どの廃棄可能ファイルが削除可能であるかをストレージアロケータ144が探す。前に説明したように、ストレージアロケータ144が、ストレージデバイスのファイルシステムにおいて廃棄不能または廃棄可能としてファイルをマーキングするために、ストレージデバイス100のファイルシステムを使用することによって、これらの廃棄可能ファイルをストレージアロケータ144が探す。加えて、ストレージアロケータ144によってマーキングされたファイルに割り当てられた廃棄レベルは、各廃棄レベルが対応するマーキングされたファイルに関連づけられるように、ストレージデバイスのファイルシステムにも埋め込まれる。
廃棄可能ファイル(「DF」)であって、最初に廃棄すべき廃棄可能ファイル(以下、このファイルを「DF1」と呼ぶ)を見つけると、ストレージアロケータ144は、このファイルの記憶空間(以下、この記憶空間を「SP1」と呼ぶ)を記憶空間190に追加するかまたは戻すために、ファイルDF1を削除する。
次に、ステップ550において、ストレージアロケータ144は、拡張された空き記憶空間190(すなわち、空き記憶空間190と最後に戻された記憶空間を足したもの、すなわち、f+SP1)が、新しいユーザファイルを収容可能であるかをチェックする。拡張された空き記憶空間190(すなわち、f+SP1)が、新しいユーザファイルを収容できないままであれば(ステップ550において「N」として示す)、ステップ550において、ストレージアロケータ144は、追加の記憶空間を空き記憶空間190に戻すために(すなわち、次に削除すべき廃棄可能ファイルを見つけて削除することによって)、ステップ550を反復して繰り返す(反復は555で示す)。
【0042】
2番目に優先度が高い廃棄優先度の次の廃棄可能ファイルを見つけると(以下、次の廃棄可能ファイルを「DF2」と呼ぶ)、ストレージアロケータ144は、追加の記憶空間を空き記憶空間190に解放および追加するために(以下、追加の記憶空間を「SP2」と呼ぶ)、ファイルDF2を削除する。次に、ステップ550において、ストレージアロケータ144は、拡張された空き記憶空間190(すなわち、空き記憶空間190と、最後に解放された2つの記憶空間を合わせたもの、すなわち、f+SP1+SP2)が、新しいファイルを収容可能であるかを再度チェックする。拡張された空き記憶空間190(すなわち、f+SP1+SP2)が、新しいファイルを収容できなければ(ステップ540において「N」として示す)、ストレージアロケータ144は、削除すべき次の廃棄ファイルを見つけるために、ステップ540をもう一度繰り返す。ストレージアロケータ144は、蓄積された空き記憶空間190が、新しいユーザファイルを収容できるまで、ステップ540および550を反復する(ステップ550において「Y」として示す)。次に、ステップ560において、ストレージアロケータ144は、記憶領域110に新しいユーザファイルを格納する。
前述したように、ストレージアロケータ144が、空き記憶空間190に新しいユーザファイルを格納した後に、実際のストレージ使用量安全マージンが、所定のストレージ使用量安全マージンより少なくなれば、ステップ560は、ストレージアロケータ144が、所定のストレージ使用量安全マージンを回復するために、最初に削除すべき格納された廃棄ファイル、次に削除すべき格納された廃棄可能ファイル・・・などを以下同様に決定する際の追加のステップを含んでもよい。
【0043】
新しいファイルがパブリッシャファイルである場合
新しいファイルがパブリッシャファイルであれば、ストレージアロケータ144は、所定のストレージ使用量安全マージンを少なくせずに、空き記憶空間190が新しいパブリッシャファイルを収容できる場合のみ、記憶領域110に新しいパブリッシャファイルを格納する(ステップ560)。すなわち、新しいパブリッシャファイルを格納すると、所定のストレージ使用量安全マージンが少なくなるならば、ストレージアロケータ144は、記憶領域110に新しいパブリッシャファイルを格納しないように決定してもよい。このような場合、ストレージアロケータ144は、そのパブリッシャファイルに対して何らのアクションをとらず、新しいパブリッシャファイル用の記憶空間を解放するためにストレージデバイスからファイルを削除することもない。あるいは、ストレージアロケータ144は、ステップ540において、廃棄優先度が低い廃棄可能ファイル用の記憶空間を解放するために、より優先度が高い1つ以上の廃棄可能ファイルを削除してもよい。前述したように、ストレージデバイス100のファイルシステムにおいて、ファイルがマーキングされ、廃棄レベルが埋め込まれ、ファイルがマーキングされ、ファイルシステムに廃棄レベルが埋め込まれる方法は、使用するファイルシステムに依存または適応されうる。
【0044】
図6は、1つの例示的な実施形態によるFAT32形式のファイルシステムにおける未承認ファイルをマーキングする方法を示す。FAT32形式のファイルシステムは、クラスタを使用する。FAT32形式のファイルシステムに関連して前述したように、FAT32クラスタを識別するために使用されるビット数は、32である。以下、図6は、図1に関連して記載される。
ステップ610において、FAT32の各クラスタの32ビットのm最上位ビット(m≦4)が、場合によって、廃棄不能または廃棄可能としてファイルをマーキングするように、さらには、各廃棄可能ファイルの対応する廃棄レベルを保持するように割り付けられるかまたは確保される。廃棄レベルのファイルへの割り当ては、対応する値をマーキングされたファイルに対応する割り付けられたmビットに設定することによって行われる。
【0045】
ステップ620において、ストレージアロケータ144は、ストレージデバイス100のユーザが未承認ファイルを使用する可能性のレベルを評価する。ファイルを使用する可能性の評価は、委託販売ファイルに関して当業者に既知の様々な方法で実行されうる。例えば、ファイルを使用する可能性の評価は、ストレージデバイスの使用者がいる場所のモニタリング、および/またはモニタリングしたユーザのこれまでの経験や好みに基づいたものであってもよい。ファイルを使用する可能性の評価はまた、例えば、FATテーブルまたはNTFSテーブル内に格納されるコンテンツのタイプ(例えば、「広告コンテンツ」、「プレミアムコンテンツ」、「販売促進用の(無料)コンテンツ」など)に基づいたものであってもよい。ストレージアロケータ144は、ファイルが使用される可能性を評価するための代替となるものまたはさらなる基準を用いてもよい。例えば、ストレージアロケータ144は、最新アクセスファイル、ファイルサイズ、ファイルタイプなどであってもよく、あるいはそれらに関連されうるファイルの属性または特性を使用してもよい。
ユーザが未承認ファイルを使用する可能性のレベルをストレージアロケータ144が評価した後、ストレージアロケータ144は、ステップ630において、未承認ファイルの評価された使用可能性レベルに対応する廃棄優先度レベルを割り当てる。未承認ファイルが、ストレージデバイス100のユーザによって使用される可能性が高いほど、廃棄レベルは低い。
【0046】
mが4ビットであれば、これは、廃棄スケールが、1(すなわち、0001)〜15(すなわち、1111)の15の廃棄レベルを与えるということを意味する。すなわち、廃棄レベル0は、廃棄不能ファイルすべてに割り当てられ、廃棄レベル1は、最低廃棄優先度の廃棄可能ファイルに割り当てられ、廃棄レベル15は、最高廃棄優先度の廃棄可能ファイルに割り当てられる。ストレージアロケータ144が、対応する廃棄レベルを未承認ファイルに割り当てた後、ストレージアロケータ144は、ステップ640において、1〜15の対応する値を、未承認ファイルに関連するクラスタの4つの最上位ビットに設定する。未承認ファイルが、ファイルに関連した2つ以上のクラスタを有すれば、各クラスタの4つの最上位ビットは、同じ値に設定される。
ステップ650において、未承認ファイルが、評価を必要とする最後のファイルであるかがチェックされる。未承認ファイルが評価が必要な最後のファイルでなければ(ステップ650において「N」で示す)、前述した方法で別のファイルが評価される。未承認ファイルが評価を必要とする最後のファイルであれば(ステップ650において「Y」で示す)、ステップ640において値が設定された各々に対してmビットを有する(1つまたは複数の)未承認ファイルが、ストレージデバイスに送信される。
【0047】
図7は、FAT32テーブルに関連する例示的なディレクトリテーブル700を示す。ディレクトリテーブル700は、説明に使用する部分的なテーブルにすぎず、したがって、FATディレクトリエントリのすべてのフィールドを示しているものではない。ディレクトリ領域700は、ファイル名、ファイルサイズ、関係する記憶空間において、各ファイルが始まる場所など、関係するファイルシステムに格納されるファイルの項目を保持する。ファイルの項目は、以下のフィールドに保持される。フィールド710は、関係するファイルシステムに格納されるファイルのディスクオペレーティングシステム(「DOS」)ファイル名を保持し、フィールド720は、ファイルの拡張を保持し、フィールド730は、ファイルのさまざまな属性を保持し、フィールド740は、ファイルの先頭クラスタ番号(「FCN」)の上位16ビットワードを保持し、フィールド750は、ファイルの先頭クラスタ番号(「FCN」)の下位を保持し、フィールド760は、ファイルサイズを保持する。各FCN番号は、ファイルが見つけられうる第1の論理クラスタを示す。
【0048】
ディレクトリ領域700の最初のエントリは、「REALFILE」(770と示す)と呼ぶ例示的なファイルの情報を保持する。REALFILE770は、ファイル拡張子「DAT」を有し、FCNは「0000 0002」であり(755と示す)、ファイルサイズは、「0000 24E4」である。テーブル700の数字は、16進数で示されている。規格の一部として、属性値「00」(780と示す)および「20」(図7に図示せず)は、「通常」ファイルをさすのに対して、属性値「02」は、ファイルシステム中の隠しファイルをさす。ファイル名「\xE5Consign」は削除ファイルを示し、ここでの「\xE5」は、ファイル名の最初のバイトの値が16進数のE5であることを意味する。一例として、FCN数0000 0002(755と示す)は、ファイルREALFILEの最初のクラスタを示す。
【0049】
図8は、1つの例示的な実施形態による例示的な部分的FAT32テーブル800を示す。FAT32テーブル800は、倍長語(「DWORD」)アレイとして示され、値は16進数である。参照番号810は、FAT32テーブル800を保持するタイプのデバイスを示し、ここで「F8」は、ハードドライブをさす。FAT32テーブル800は、クラスタ#1(820と示す)、クラスタ#2(825と示す)・・・クラスタ#23(830と示す)として示された23個のクラスタを含む。図8は、図7に関連して記載される。FAT32テーブル800のクラスタは、ファイルの最初のクラスタであってもよく、あるいはファイルの次につながったクラスタを示してもよく、またはファイルの終わり(「EOF」)を指し示すものであってもよい。
【0050】
ディレクトリ領域700を再度参照すると、ファイルREALFILE(770と示す)の最初のFCNは、「0000 0002」(755と示す)であり、これは、図8のテーブル800のクラスタ#2をさす。図8に示すように、クラスタ#2の値(すなわち、値「0000 0003」)は、次のファイルクラスタであるクラスタ#3をさす(840と示す)。同様に、クラスタ#3の値(すなわち、「0000 0004」)は、次のファイルクラスタであるクラスタ#4をさす。クラスタ#4は、値「0FFF FFFF」(「F」は、10進数の「15」を表す16進数字である)を有し、ここで、「FFF FFFF」(850と示す)は、ファイルのEOF指示を示し、ゼロ値(860と示す)は、廃棄レベル0を示す。したがって、ファイルREALFILEは、3つのクラスタと関連している(すなわち、クラスタ#2、クラスタ#3、およびクラスタ#4)。
【0051】
前に説明したように、廃棄レベル0が、廃棄不能ファイルに割り当てられる。特定のファイルの各クラスタの最上位16進数字が、そのファイルに割り当てられた同一の廃棄優先度レベルに設定されることに留意するべきである。例えば、ファイルREALFILEは、廃棄レベル「0」が割り当てられ、したがって、クラスタ#2、#3、および#4の最上位16進数字の各々が、この値を有する(すなわち、値「0」、「0」値には下線が引かれている)。別の例によれば、FCNが「0000 0005」(図7に示す)であるファイル「E5 Consign」には、廃棄優先度レベル「1」が割り当てられている。したがって、このファイルに関係するクラスタ#5〜12の各々の最上位16進数字は、値「1」を有する(例えば、870と示す)。言い換えれば、本願明細書における開示によれば、最上位16進数字(すなわち、換言すれば、特定の廃棄可能ファイルに関するクラスタの4つの最上位ビット)は、特定のファイルに割り当てられた廃棄優先度レベルに対応する同じ値に設定される。前に説明したように、廃棄優先度レベルを示すために使用される最上位ビットの数字mは、4とは異なるものであってもよい(すなわち、m≦4)。
【0052】
図9は、例示的な実施形態による例示的な部分的NTFSテーブル900を示す。NTFSテーブル900は、ファイル名、ファイルサイズなどのファイルの項目を保持する。NTFSテーブル900は、「普通の」データフローに応じて変化するファイルの「通常の」データ(例えば、データ920)を保持するためのデータフィールド910を含む。本願明細書における開示によれば、NTFSテーブル900はまた、各評価済みファイルの廃棄情報(例えば、廃棄情報930)を保持するための「廃棄情報」フィールド915を含む。また、廃棄情報フィールド915は、廃棄優先度レベル以外の情報を含んでもよい。例えば、廃棄情報フィールド915は、ファイルを供給したサーバおよびファイルを廃棄しなければいけない期限の満了時間に関する情報を含んでもよい。FATベースのファイルシステムとは異なり、NTFSベースのファイルシステムにおいて、廃棄可能ファイルに割り当てられた廃棄値は、ビットセットによって要求される最大数に制限されない。これは、廃棄値の範囲が自由に選択可能であることを意味する。例えば、廃棄値は、1〜25の範囲のものでありうる。NTFSは、例示的な非FATファイルシステムである。一般に、対応する廃棄値は、マーキングされたファイルに対応する非FATベースのファイルシステムエントリのデータフィールドに設定されてもよい。
【0053】
図10は、例示的な実施形態によるストレージデバイスのファイルシステム1000の論理構成を示す。ストレージアロケータ(例えば、図1のストレージアロケータ144)は動作するストレージデバイスのファイルシステム1000またはファイルシステム1000のイメージのいずれかを保持するか、またはストレージアロケータはファイルシステム1000へのアクセスを有してもよい。
ファイルシステム1000は、ブートセクション1010と、ファイルシステム1000に関連するFAT1020と、ディレクトリテーブル1030と、ファイル領域1040と、廃棄可能ファイル領域1050とを含む。FAT1020は、廃棄可能ファイルの廃棄優先度レベルを含む廃棄可能ファイル割り付け領域1025を含む。ディレクトリテーブル1030は、ストレージデバイスに格納されるファイルであれば、どのファイル(すなわち、廃棄可能ファイルおよび/または廃棄不能ファイル)にでもアクセスするためのアクセス情報を含む。ファイル領域1040は、廃棄不能ファイルを含む。インデックスおよびデータベース領域1045は、廃棄可能ファイルのインデックスと、さらに、廃棄可能ファイルに関係するメタデータとを保持する。インデックスおよびデータベース領域1045に保持されるインデックスおよびメタデータは、廃棄レベルを算出するために使用されるが、実際の廃棄プロセス中には要求されない。廃棄可能ファイル領域1050は、廃棄可能ファイルを保持する。
【0054】
図11は、本願明細書における開示によるファイルを管理する方法を示す。図11は、図1に関連して記載される。時間T0で、2つのユーザファイル(すなわち、ファイル「F1」および「F2」)が、記憶領域110に最初に格納されると仮定する。ファイル「F1」および「F2」は、ユーザファイルであるため、ユーザ領域170に格納され、ストレージアロケータ144によってファイルに割り当てられる廃棄レベルはゼロである。記憶領域110の全記憶容量がT(1110と示す)であり、ファイルF1およびF2が、ストレージデバイス100に格納されるため、残りの空き記憶空間190(図1を参照)のサイズはf(1120と示す)である。パブリッシャが、記憶領域110に3つの未承認ファイルの格納を望むと仮定する。前述したように、記憶領域110にパブリッシャの3つの未承認ファイルを格納することで、先々のユーザファイル用に保存される所定のストレージ使用量安全マージン(1130と示す)が少なくならないかを決定するために、ストレージアロケータ144が、ストレージデバイス100における空き記憶空間190(または1120のf)のサイズを評価する。パブリッシャの3つの未承認ファイルを確認することで、ストレージ使用量安全マージン1130(すなわち、所定のストレージ使用量安全マージン)が少なくなれば、ストレージアロケータ144は、これらのファイルの格納をやめる。
【0055】
この例において、ストレージアロケータ144は、ストレージ使用量安全マージン1130を低減することなく、パブリッシャの3つの未承認ファイルが記憶領域110に格納可能であることを決定する。したがって、時間T1で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にパブリッシャの3つの未承認ファイルを格納できる。3つのパブリッシャの未承認ファイルは、「P1」、「P2」、および「P3」として示される。ストレージアロケータ144はまた、ストレージデバイス100のユーザによってファイルP1、P2、およびP3が使用される確率を決定し、これらのファイルの各々に対応する廃棄レベルを割り当てる。次に、ストレージアロケータ144は、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルにファイルに割り当てられた廃棄レベルを格納する。
【0056】
時間T2で、ストレージデバイス100のユーザは、記憶領域110に、3つ以上のファイル(すなわち、ファイル「F3」および「F4」)の格納を望む。ストレージアロケータ144は、追加のファイル(すなわち、ファイルF3およびF4)を格納するのに十分な格納空間が記憶領域110にあるかどうかを決定するために、ストレージデバイス100における空き記憶空間190のサイズ(または1120のf)を再評価する。この例において、ストレージアロケータ144は、現在の空き記憶空間がファイルF3およびF4を収容可能であることを決定する。したがって、時間T2で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にファイルF3およびF4を格納できる。
【0057】
ファイルF3およびF4がユーザファイルであるため、ストレージデバイス100のユーザによってファイルF3およびF4が使用される確率は、ユーザファイルが、ユーザがファイルF3およびF4を使用するとしても、その回数に関係なく、パブリッシャファイルよりも高いストレージ優先度を有するため重要ではない。したがって、ストレージアロケータ144は、廃棄レベル「0」をファイルF3およびF4に割り当て、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルに割り当て廃棄レベルを格納する。
時間T3で、ストレージデバイス100のユーザは、記憶領域110に、別のファイル(すなわち、ファイル「F5」)の格納を望む。ストレージアロケータ144は、追加のファイル(すなわち、ファイルF5)を格納するのに十分な格納空間が記憶領域110にあるかどうかを決定するために、ストレージデバイス100における空き記憶空間190のサイズ(または1120のf)を再評価する。
【0058】
この例において、ストレージアロケータ144は、現在の空き記憶空間がファイルF5を収容可能であることを決定する。したがって、時間T3で、ストレージアロケータ144により、ストレージコントローラ120は、記憶領域110にファイルF5を格納できる。図11に示すように、ユーザファイルF5を格納すると、ストレージ使用量安全マージンが少なくなる。すなわち、ファイルF1〜F5およびP1〜P3が記憶領域110に格納された後に残る記憶領域110の空き記憶空間fは、ストレージ使用量安全マージン1130より少なくなる。したがって、ストレージアロケータ144は、パブリッシャのファイル(すなわち、P1、P2、およびP3)の1つを取り除くことによって、ストレージ使用量安全マージンを復旧または回復させる。前に説明したように、ユーザファイルのストレージ優先度が最も高いため、ストレージ使用量安全マージンが、1つ以上のパブリッシャファイルを取り除く(すなわち、削除する)ことによって復旧または回復される。 前述したように、ストレージアロケータ144が、各格納された廃棄可能ファイルに割り当てた廃棄優先度レベルに基づいて、ストレージアロケータ144によって、記憶領域110から1つまたは複数のパブリッシャファイルを取り除くべきであるという決定がなされる。
【0059】
図11を再度参照しながら、格納されたパブリッシャファイルP1〜P3の中から、パブリッシャファイルP3に最高廃棄優先度レベル(例えば、13)を割り当てたと仮定する。したがって、時間T4で、ファイルP3は記憶領域110から取り除かれることで、空き記憶空間190が拡大される。時間T4で、空き記憶空間190のサイズ(または1120のf)が、ストレージ使用量安全マージン1130より大きいため、パブリッシャファイルをさらに取り除く必要はない。
【0060】
ストレージデバイス100のユーザは、1つ以上のユーザファイルを取り除きたいこともある。時間T5で、ユーザは、自分のファイルのうちの2つ(すなわち、ファイルF4およびF5)を取り除き、空き記憶空間190がさらに拡大される。本願明細書に記載したように、空き記憶空間の取り除きやストレージ使用量安全マージンの回復は、必要に応じて多くの廃棄可能ファイルを取り除くことによって行われるため、ファイルF4およびF5を取り除くことは、空き記憶区間190またはストレージ使用量安全マージンのサイズとは関係がない。パブリッシャは、記憶領域110に未承認ファイルを格納することを望んでいると考えられる。前述したように、ストレージアロケータ144は、記憶領域110にパブリッシャの未承認ファイルを格納することで、ストレージ使用量安全マージン1130が少なくならないかを決定するために、空き記憶空間190のサイズ(または1120のf)を評価する。パブリッシャの新しい未承認ファイルを格納することで、ストレージ使用量安全マージン1130が少なくなれば、ストレージアロケータ144は、このファイルの格納をやめる。
【0061】
この例において、ストレージアロケータ144は、パブリッシャの新しい未承認ファイル(すなわち、ファイル「P4」)が、ストレージ使用量安全マージン1130を低減することなく記憶領域110に格納可能であることを決定する。したがって、時間T6において、ストレージアロケータ144により、ストレージコントローラ120が、記憶領域110にパブリッシャのファイルP4を格納できる。ストレージアロケータ144はまた、ストレージデバイス100のユーザによってファイルP4が使用される確率を決定し、このファイルに対応する廃棄レベルを割り当てる。次に、ストレージアロケータ144は、図8に示すようなFATテーブルまたは図9に示すようなNTFSテーブルにファイルP4に割り当てられた廃棄レベルを格納する。新しいパブリッシャのファイルおよび新しいユーザファイルを格納し、格納されたファイルを取り除くプロセスは、記憶領域110に新しいファイルが追加されるたびに、ストレージアロケータ144が、空き記憶空間190の現在のサイズを評価し、1つまたは複数のパブリッシャファイル(存在すれば)のうちのどのファイルが記憶領域110から取り除かれる必要があるかを決定するまで続きうる。
【0062】
廃棄レベルを廃棄可能ファイルに割り当てることは、ユーザの経験や好み、ユーザの全地球測位システム(「GPS」)位置、および/または他の基準に基づいたものであってもよい。例えば、ストレージデバイスのユーザは、(それまでのユーザの経験に基づいて)ある一定のタイプの音楽を好むようであれば、ストレージアロケータは、パブリッシャファイルが、ユーザが好きなタイプの音楽の1つである音楽を含めば、比較的低い廃棄優先度レベル(例えば、1〜15の範囲の3)をパブリッシャファイルに割り当ててもよい。しかし、パブリッシャの音楽がユーザの好みでなければ(すなわち、それまでのユーザの経験に基づいて)、ストレージアロケータは、より高い廃棄優先度レベル(例えば、1〜15の範囲の12)を関係するパブリッシャファイルに割り当ててもよい。廃棄レベルを廃棄可能ファイルに割り当てるために使用される基準は、ファイルの予測使用、ファイルの使用に関連する予測収入、ファイルの種類、ファイルサイズ、ストレージデバイスにおけるファイルの場所、ファイルの古さ、および本願明細書に明示したような他の基準やパラメータを含んでもよい。他の基準が、単独でまたは本願明細書において述べた任意の基準と組み合わせて、同様に使用されてもよく、廃棄レベルの割り当ては、1つ以上の基準を用いて行われてもよい。加えて、廃棄レベルを異なる廃棄可能ファイルに割り当てるために、異なる基準が使用されてもよい。
【0063】
別の例において、パブリッシャが、位置依存性の広告(すなわち、特定の区域内で提供する製品やサービスに関する広告)をユーザに送りたければ、ストレージアロケータは、ユーザの位置変化に応じて変化するパブリッシャの広告に廃棄優先度レベルを割り当ててもよい。すなわち、ユーザが、特定の区域から離れることによって、特定の区域で提供される製品やサービスの消費に感心がなくなることが想定されうるため、ユーザが特定の場所から遠ざかるほど、廃棄レベルが高くなる。
【0064】
関連するファイルシステムにおいて、ファイルをマーキングし、マーキングされたファイルに廃棄レベルを割り当てる本願明細書において開示される手法には、多くの有用な応用がありえ、そのうちの1つでは、ユーザファイルに対して十分な記憶空間を確保するために、ストレージ使用量安全マージンが回復されることに留意するべきである。例えば、ファイルクラスタをより低性能のフラッシュモジュールに再マッピングしたり、リクエストに応じてクラスタをクリアしたりするために、ファイルに割り当てられた廃棄レベルが使用されてもよい。
【0065】
本願明細書において、冠詞は、文脈に応じて、その冠詞の文法上の目的語が単数あるいは複数(すなわち、少なくとも1つ)であることを言及するように使用される。一例として、文脈に応じて、「要素」は、1つの要素または2つ以上の要素を意味しうる。本願明細書において、「〜を含む」という用語は、「〜を含むが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。「または」と「および」という用語は、本願明細書において、文脈に特別な指示が明示されていない限り、「および/または」という用語を意味し、その用語と交換可能に使用される。「〜など」という用語は、本願明細書において、「〜などであるが、これらに限定されるわけではない」という句を意味し、この句と交換可能に使用される。
【0066】
以上、本発明の例示的な実施形態を記載してきたが、当業者であれば、開示された実施形態の修正が、本発明の範囲内でなされることは明らかである。したがって、別の実施形態は、より多くのモジュール、より少ないモジュール、および/または機能的に同等のモジュールを含んでもよい。本願明細書における開示は、SD駆動型フラッシュメモリカード、フラッシュストレージデバイス、非フラッシュストレージデバイス、ユニバーサルシリアルバス(「USB」)インターフェイスが設けられた「ディスクオンキー」デバイス、USBフラッシュドライブ(「UFD」)、マルチメディアカード(「MMC」)、セキュアデジタル(「SD」)、ミニSD、およびマイクロSDなど、様々なタイプの大容量ストレージデバイスに関連する。したがって、添付の特許請求の範囲は、本願明細書の開示によって限定されるものではない。
【特許請求の範囲】
【請求項1】
ストレージデバイスを管理する方法であって、
a)ストレージデバイスの記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信するステップと、
b)1つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングするステップであって、各ファイルをマーキングするステップが前記ストレージデバイスに関連するファイルシステムの構造において実行される、マーキングするステップと、
c)前記ファイルシステムの構造における1つ以上のファイルをマーキングするステップに基づいて、前記ストレージデバイスの記憶領域において1つ以上のファイルの格納を管理するステップと、
を含む方法。
【請求項2】
請求項1記載の方法において、
前記管理するステップは、(i)廃棄可能なものとしてマーキングされた1つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、(ii)廃棄可能なものとしてマーキングされたすべてのファイルを取り除くことによって記憶領域を解放することと、(iii)ファイルのクラスタを低性能ストレージモジュールに再マッピングすることのうちのいずれか1つまたはそれらの組み合わせを含む方法。
【請求項3】
請求項1記載の方法において、
d)マーキングされたファイルを前記ストレージデバイスに送信するステップをさらに含む方法。
【請求項4】
請求項1記載の方法において、
前記マーキングするステップは、ファイルに廃棄優先度レベルを割り当てることを含む方法。
【請求項5】
請求項4記載の方法において、
前記ファイルに廃棄優先度レベルを割り当てることは、(i)マーキングされたファイルに対応するファイルアロケーションテーブルエントリのm最上位ビットに対応する値を設定するか、または(ii)前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって実行される方法。
【請求項6】
請求項5記載の方法において、
前記対応する値は、ファイルの属性である方法。
【請求項7】
請求項5記載の方法において、
前記m最上位ビットの値は、前記マーキングされたファイルが廃棄不能であれば、0に設定され、前記マーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定される方法。
【請求項8】
請求項7記載の方法において、
前記m最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルである方法。
【請求項9】
請求項7記載の方法において、
値「1」は最低優先度で廃棄可能ファイルを示し、値「2m −1」は最高優先度で廃棄可能ファイルを示す方法。
【請求項10】
請求項4記載の方法において、
前記廃棄優先度レベルは、(i)ファイルの予測使用法、(ii)ファイルの使用に関連する予測収入、(iii)ファイルの種類、(iv)ファイルのサイズ、(v)前記ストレージデバイスにおけるファイルの場所、および(vi)ファイルの古さのうちのいずれか1つに応じて、マーキングされたファイルに割り当てられる方法。
【請求項11】
請求項4記載の方法において、
d)前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するステップをさらに含む方法。
【請求項12】
請求項11記載の方法において、
前記マーキングされたファイルの廃棄優先度レベルを更新するステップは、前記ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して実行される方法。
【請求項13】
請求項1記載の方法において、
d)前記ストレージデバイスに格納された廃棄可能ファイルが、廃棄しきい値以上の廃棄優先度レベルに対応付けされている場合、前記廃棄可能ファイルを前記ストレージデバイスから廃棄されるように廃棄しきい値を設定するステップをさらに含む方法。
【請求項14】
請求項1記載の方法において、
d)前記ストレージデバイスに新しいファイルを格納するリクエストを受信するステップと、
e)所定のストレージ使用量安全マージンより大きな空き記憶空間が前記ストレージデバイスにあるかを評価し、このような記憶空間があれば、空き記憶空間に新しいファイルを格納するステップと、
f)前記ストレージデバイス上の空き記憶空間が所定のストレージ使用量安全マージン以下であれば、(i)削除可能な前記ストレージデバイス内の廃棄可能ファイルを探すステップと、(ii)このようなファイルが見つかれば、空き記憶空間を拡張するようにファイルを削除し、このようなファイルが見つからなければ、新しいファイルの格納をやめるステップと、
g)拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きければ、前記拡張された空き記憶空間に新しいファイルを格納し、前記拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きくなければ、ステップe)およびf)を繰り返すステップと、
をさらに含む方法。
【請求項15】
請求項14記載の方法において、
廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、廃棄可能ファイルを削除する方法。
【請求項16】
ストレージデバイスを管理するストレージアロケータであって、
前記ストレージデバイスおよび前記ストレージデバイスのホストとのインターフェイスとなる通信インターフェイスと、
前記ストレージデバイスと関連するファイルシステムを格納するためのメモリユニットと、
前記ストレージデバイスと前記関連するファイルシステムを管理するためのプロセッサと、を備え、
前記プロセッサは、(i)前記ストレージデバイスの記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信し、(ii)1つ以上のファイルを廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ストレージデバイスの前記関連するファイルシステムの構造において実行され、かつ(iii)前記ファイルシステムの構造における1つ以上のファイルをマーキングすることに基づいて、前記ストレージデバイスの記憶領域において1つ以上のファイルの格納を管理するように構成されるストレージアロケータ。
【請求項17】
請求項16記載のストレージアロケータにおいて、
前記プロセッサは、マーキングされたファイルを前記ストレージデバイスに送信するようにさらに構成されるストレージアロケータ。
【請求項18】
請求項16記載のストレージアロケータにおいて、
ファイルを廃棄可能としてマーキングすることの一部として、前記プロセッサは、ファイルに廃棄優先度レベルを割り当てるようにさらに構成されるストレージアロケータ。
【請求項19】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、(i)マーキングされたファイルに対応するファイルアロケーションテーブルエントリのm最上位ビットに対応する値を設定するか、または(ii)前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって、前記マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項20】
請求項19記載のストレージアロケータにおいて、
前記プロセッサは、前記マーキングされたファイルが廃棄不能であれば、m最上位ビットの値を0に設定し、前記マーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定するストレージアロケータ。
【請求項21】
請求項20記載のストレージアロケータにおいて、
値「1」は最低優先度で廃棄可能ファイルを示し、値「2m −1」は最高優先度で廃棄可能ファイルを示すストレージアロケータ。
【請求項22】
請求項20記載のストレージアロケータにおいて、
前記m最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルであるストレージアロケータ。
【請求項23】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ファイルの予測使用法に応じて、マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項24】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項25】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項26】
請求項17記載のストレージアロケータにおいて、
前記ストレージデバイスに格納されたファイルが、所定の廃棄しきい値以上の廃棄レベル優先度に関連付けされている場合、前記プロセッサは前記ファイルを削除するストレージアロケータ。
【請求項27】
請求項17記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、前記ストレージデバイスの空き記憶空間のサイズを評価するようにさらに構成され、
(i)前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きければ、前記ストレージデバイスに新しいファイルを格納し、
(ii)前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きくなければ、拡張される空き記憶空間のサイズが所定のストレージ安全マージンより大きくなるように、空き記憶空間を拡張するために削除可能である前記ストレージデバイス内の1つ以上の廃棄可能ファイルを探し、このようなファイルを見つけると、見つけられたファイルを削除して、拡張された空き記憶空間に新しいファイルを格納し、このようなファイルが見つからなければ、新しいファイルの格納をやめるようにさらに構成されるストレージアロケータ。
【請求項28】
請求項27記載のストレージアロケータにおいて、
前記廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、前記ストレージデバイスから1つ以上の廃棄可能ファイルが削除可能であるストレージアロケータ。
【請求項29】
ストレージシステムであって、
通信インターフェイスと、
ストレージデバイスに関連するファイルシステムを管理するためのストレージアロケータであって、前記ストレージデバイスの記憶領域に1つ以上のファイルの格納を管理するためのプロセッサを備えるストレージアロケータと、を備え、
前記プロセッサは、(i)通信インターフェイスを介して、前記記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信し、(ii)1つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ファイルシステムの構造において実行され、かつ(iii)前記ファイルシステムの構造における1つ以上のファイルをマーキングすることに基づいて、前記記憶領域において1つ以上のファイルの格納を管理するように構成されるストレージシステム。
【請求項30】
請求項29記載のストレージシステムにおいて、
前記通信インターフェイスは、前記ストレージアロケータと一体であるストレージシステム。
【請求項31】
請求項29記載のストレージシステムにおいて、
前記ファイルの1つ以上を格納するための記憶領域を含むストレージデバイスをさらに備えるストレージシステム。
【請求項32】
請求項29記載のストレージシステムにおいて、
前記ストレージアロケータは、前記ファイルシステムを局所的に格納するためのメモリユニットをさらに含むストレージシステム。
【請求項33】
請求項29記載のストレージシステムにおいて、
ストレージデバイスおよび/または前記ストレージデバイスのホストをさらに備え、前記ストレージアロケータは、前記ストレージデバイスまたは前記ストレージデバイスのホストに存在するストレージシステム。
【請求項1】
ストレージデバイスを管理する方法であって、
a)ストレージデバイスの記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信するステップと、
b)1つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングするステップであって、各ファイルをマーキングするステップが前記ストレージデバイスに関連するファイルシステムの構造において実行される、マーキングするステップと、
c)前記ファイルシステムの構造における1つ以上のファイルをマーキングするステップに基づいて、前記ストレージデバイスの記憶領域において1つ以上のファイルの格納を管理するステップと、
を含む方法。
【請求項2】
請求項1記載の方法において、
前記管理するステップは、(i)廃棄可能なものとしてマーキングされた1つ以上のファイルを選択的に取り除くことによって、ストレージ使用量安全マージンを回復することと、(ii)廃棄可能なものとしてマーキングされたすべてのファイルを取り除くことによって記憶領域を解放することと、(iii)ファイルのクラスタを低性能ストレージモジュールに再マッピングすることのうちのいずれか1つまたはそれらの組み合わせを含む方法。
【請求項3】
請求項1記載の方法において、
d)マーキングされたファイルを前記ストレージデバイスに送信するステップをさらに含む方法。
【請求項4】
請求項1記載の方法において、
前記マーキングするステップは、ファイルに廃棄優先度レベルを割り当てることを含む方法。
【請求項5】
請求項4記載の方法において、
前記ファイルに廃棄優先度レベルを割り当てることは、(i)マーキングされたファイルに対応するファイルアロケーションテーブルエントリのm最上位ビットに対応する値を設定するか、または(ii)前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって実行される方法。
【請求項6】
請求項5記載の方法において、
前記対応する値は、ファイルの属性である方法。
【請求項7】
請求項5記載の方法において、
前記m最上位ビットの値は、前記マーキングされたファイルが廃棄不能であれば、0に設定され、前記マーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定される方法。
【請求項8】
請求項7記載の方法において、
前記m最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルである方法。
【請求項9】
請求項7記載の方法において、
値「1」は最低優先度で廃棄可能ファイルを示し、値「2m −1」は最高優先度で廃棄可能ファイルを示す方法。
【請求項10】
請求項4記載の方法において、
前記廃棄優先度レベルは、(i)ファイルの予測使用法、(ii)ファイルの使用に関連する予測収入、(iii)ファイルの種類、(iv)ファイルのサイズ、(v)前記ストレージデバイスにおけるファイルの場所、および(vi)ファイルの古さのうちのいずれか1つに応じて、マーキングされたファイルに割り当てられる方法。
【請求項11】
請求項4記載の方法において、
d)前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するステップをさらに含む方法。
【請求項12】
請求項11記載の方法において、
前記マーキングされたファイルの廃棄優先度レベルを更新するステップは、前記ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して実行される方法。
【請求項13】
請求項1記載の方法において、
d)前記ストレージデバイスに格納された廃棄可能ファイルが、廃棄しきい値以上の廃棄優先度レベルに対応付けされている場合、前記廃棄可能ファイルを前記ストレージデバイスから廃棄されるように廃棄しきい値を設定するステップをさらに含む方法。
【請求項14】
請求項1記載の方法において、
d)前記ストレージデバイスに新しいファイルを格納するリクエストを受信するステップと、
e)所定のストレージ使用量安全マージンより大きな空き記憶空間が前記ストレージデバイスにあるかを評価し、このような記憶空間があれば、空き記憶空間に新しいファイルを格納するステップと、
f)前記ストレージデバイス上の空き記憶空間が所定のストレージ使用量安全マージン以下であれば、(i)削除可能な前記ストレージデバイス内の廃棄可能ファイルを探すステップと、(ii)このようなファイルが見つかれば、空き記憶空間を拡張するようにファイルを削除し、このようなファイルが見つからなければ、新しいファイルの格納をやめるステップと、
g)拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きければ、前記拡張された空き記憶空間に新しいファイルを格納し、前記拡張された空き記憶空間のサイズが所定のストレージ使用量安全マージンより大きくなければ、ステップe)およびf)を繰り返すステップと、
をさらに含む方法。
【請求項15】
請求項14記載の方法において、
廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、廃棄可能ファイルを削除する方法。
【請求項16】
ストレージデバイスを管理するストレージアロケータであって、
前記ストレージデバイスおよび前記ストレージデバイスのホストとのインターフェイスとなる通信インターフェイスと、
前記ストレージデバイスと関連するファイルシステムを格納するためのメモリユニットと、
前記ストレージデバイスと前記関連するファイルシステムを管理するためのプロセッサと、を備え、
前記プロセッサは、(i)前記ストレージデバイスの記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信し、(ii)1つ以上のファイルを廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ストレージデバイスの前記関連するファイルシステムの構造において実行され、かつ(iii)前記ファイルシステムの構造における1つ以上のファイルをマーキングすることに基づいて、前記ストレージデバイスの記憶領域において1つ以上のファイルの格納を管理するように構成されるストレージアロケータ。
【請求項17】
請求項16記載のストレージアロケータにおいて、
前記プロセッサは、マーキングされたファイルを前記ストレージデバイスに送信するようにさらに構成されるストレージアロケータ。
【請求項18】
請求項16記載のストレージアロケータにおいて、
ファイルを廃棄可能としてマーキングすることの一部として、前記プロセッサは、ファイルに廃棄優先度レベルを割り当てるようにさらに構成されるストレージアロケータ。
【請求項19】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、(i)マーキングされたファイルに対応するファイルアロケーションテーブルエントリのm最上位ビットに対応する値を設定するか、または(ii)前記マーキングされたファイルに対応するファイルシステムエントリのデータフィールドに対応する値を設定するかのいずれかによって、前記マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項20】
請求項19記載のストレージアロケータにおいて、
前記プロセッサは、前記マーキングされたファイルが廃棄不能であれば、m最上位ビットの値を0に設定し、前記マーキングされたファイルが廃棄可能であれば、1〜2m −1の値に設定するストレージアロケータ。
【請求項21】
請求項20記載のストレージアロケータにおいて、
値「1」は最低優先度で廃棄可能ファイルを示し、値「2m −1」は最高優先度で廃棄可能ファイルを示すストレージアロケータ。
【請求項22】
請求項20記載のストレージアロケータにおいて、
前記m最上位ビットのゼロではない値は、前記マーキングされたファイルが前記ストレージデバイスから廃棄可能であるかまたは廃棄すべきである優先度を示す廃棄優先度レベルであるストレージアロケータ。
【請求項23】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ファイルの予測使用法に応じて、マーキングされたファイルに廃棄優先度レベルを割り当てるストレージアロケータ。
【請求項24】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する新しいリクエストがあるたびに、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項25】
請求項18記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスにファイルを格納する1つ以上の新しいリクエストから独立して、マーキングされたファイルの廃棄優先度レベルを更新するようにさらに構成されるストレージアロケータ。
【請求項26】
請求項17記載のストレージアロケータにおいて、
前記ストレージデバイスに格納されたファイルが、所定の廃棄しきい値以上の廃棄レベル優先度に関連付けされている場合、前記プロセッサは前記ファイルを削除するストレージアロケータ。
【請求項27】
請求項17記載のストレージアロケータにおいて、
前記プロセッサは、前記ストレージデバイスに新しいファイルを格納するリクエストの受信に応答して、前記ストレージデバイスの空き記憶空間のサイズを評価するようにさらに構成され、
(i)前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きければ、前記ストレージデバイスに新しいファイルを格納し、
(ii)前記ストレージデバイスの空き記憶空間の評価されたサイズが所定のストレージ安全マージンより大きくなければ、拡張される空き記憶空間のサイズが所定のストレージ安全マージンより大きくなるように、空き記憶空間を拡張するために削除可能である前記ストレージデバイス内の1つ以上の廃棄可能ファイルを探し、このようなファイルを見つけると、見つけられたファイルを削除して、拡張された空き記憶空間に新しいファイルを格納し、このようなファイルが見つからなければ、新しいファイルの格納をやめるようにさらに構成されるストレージアロケータ。
【請求項28】
請求項27記載のストレージアロケータにおいて、
前記廃棄可能ファイルに関連する廃棄優先度レベルが所定の廃棄しきい値以上であれば、前記ストレージデバイスから1つ以上の廃棄可能ファイルが削除可能であるストレージアロケータ。
【請求項29】
ストレージシステムであって、
通信インターフェイスと、
ストレージデバイスに関連するファイルシステムを管理するためのストレージアロケータであって、前記ストレージデバイスの記憶領域に1つ以上のファイルの格納を管理するためのプロセッサを備えるストレージアロケータと、を備え、
前記プロセッサは、(i)通信インターフェイスを介して、前記記憶領域に1つ以上のファイルを格納する1つ以上のリクエストを受信し、(ii)1つ以上のファイルの各々を廃棄可能または廃棄不能なものとしてマーキングし、各ファイルをマーキングすることが前記ファイルシステムの構造において実行され、かつ(iii)前記ファイルシステムの構造における1つ以上のファイルをマーキングすることに基づいて、前記記憶領域において1つ以上のファイルの格納を管理するように構成されるストレージシステム。
【請求項30】
請求項29記載のストレージシステムにおいて、
前記通信インターフェイスは、前記ストレージアロケータと一体であるストレージシステム。
【請求項31】
請求項29記載のストレージシステムにおいて、
前記ファイルの1つ以上を格納するための記憶領域を含むストレージデバイスをさらに備えるストレージシステム。
【請求項32】
請求項29記載のストレージシステムにおいて、
前記ストレージアロケータは、前記ファイルシステムを局所的に格納するためのメモリユニットをさらに含むストレージシステム。
【請求項33】
請求項29記載のストレージシステムにおいて、
ストレージデバイスおよび/または前記ストレージデバイスのホストをさらに備え、前記ストレージアロケータは、前記ストレージデバイスまたは前記ストレージデバイスのホストに存在するストレージシステム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公表番号】特表2012−512462(P2012−512462A)
【公表日】平成24年5月31日(2012.5.31)
【国際特許分類】
【出願番号】特願2011−540766(P2011−540766)
【出願日】平成21年11月23日(2009.11.23)
【国際出願番号】PCT/US2009/065456
【国際公開番号】WO2010/074866
【国際公開日】平成22年7月1日(2010.7.1)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
【出願人】(508159260)サンディスク アイエル リミテッド (33)
【公表日】平成24年5月31日(2012.5.31)
【国際特許分類】
【出願日】平成21年11月23日(2009.11.23)
【国際出願番号】PCT/US2009/065456
【国際公開番号】WO2010/074866
【国際公開日】平成22年7月1日(2010.7.1)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
【出願人】(508159260)サンディスク アイエル リミテッド (33)
[ Back to top ]