(57)【要約】データストレージデバイス上のデータのデータエントロピを減少させる効率的なデータストレージのためのシステム及び方法。この技術は、関連する複数の不連続データエンティティ（ハードディスクドライブ上のファイル等）を、物理的に近接し、予測可能な又は順序付けられたシーケンスで組織化することによって、記憶／読出装置が要求のシーケンスを処理する際に各データエンティティの位置を特定するために費やされる時間及び（機械的、演算的及びその他の）負担を削減する。例えば、ファイルディレクトリインデクス構造に基づいて、データを組織化及び保存してもよく、これによって、データ及び空き領域の断片化も減少する。【選択図】図１
2014500531.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに実装にされ、ストレージデバイスのファイルを配置するファイル配置方法において、
上記ストレージデバイスのファイルの論理的関係を判定するステップと、
上記判定された論理的関係に基づいて、論理的に関連するファイルを、上記ストレージデバイスに物理的に互いに近接するように配置することによって該ストレージ装置のファイルを再配置するステップとを有し、
上記ファイルを再配置するステップは、上記ストレージデバイスの実質的に全てのファイルについて実行されることを特徴とするファイル配置方法。
【請求項２】
上記再配置の結果、上記ストレージデバイスのファイルのデータエントロピが削減される請求項１記載のファイル配置方法。
【請求項３】
上記論理的関係を判定するステップは、コンピュータシステムにおけるファイルシステムのファイルディレクトリインデクス構造を判定するステップを含む請求項１記載のファイル配置方法。
【請求項４】
上記ファイルの再配置の前にストレージデバイスの使用可能な空き領域を解析するステップを更に有する請求項１記載のファイル配置方法。
【請求項５】
所定のファイルを所定の位置に配置した後、残りのファイルを再配置するステップを更に有する請求項４記載のファイル配置方法。
【請求項６】
各フォルダからのファイルは、上記ストレージデバイスに論理的順序で連続的に保存される請求項５記載のファイル配置方法。
【請求項７】
上記ファイルは、関連するファイルの優先度付けされたグループ化に基づいて、上記ストレージデバイスに物理的に配置される請求項４記載のファイル配置方法。
【請求項８】
上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、該ファイルのグループの全体が保存される前に次の空き領域チャンクが満たされた場合には、該ファイルのグループを保存するために更なる空き領域チャンクが選択される請求項７記載のファイル配置方法。
【請求項９】
上記使用可能な空き領域を解析し、ファイルを再配置するステップは、システムの動作の間に動的に実行される請求項４記載のファイル配置方法。
【請求項１０】
データエントロピのレートがしきい値より高いストレージデバイスの位置を特定するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するステップとを更に有する請求項４記載のファイル配置方法。
【請求項１１】
上記ストレージデバイスにアクセスするコンピュータシステムのタイプに基づいて、共通に用いられるファイルの第１のサブセットを特定するステップと、
システムの動作を監視し、該システムの動作の間に共通に用いられるデータ又はファイルの第２のサブセットを特定するステップと、
上記ファイルの第１及び第２のサブセット並びにすべての関連するファイルを、ストレージデバイスの物理的に連続するグループに保存することによって、上記特定された共通に用いられるファイルの第１及び第２のサブセット及びすべての関連するファイルを再配置するステップとを更に有する請求項１記載のファイル配置方法。
【請求項１２】
上記ストレージデバイスは、ハードディスクドライブであり、上記ファイルは、同じフォルダからファイルにアクセスする際にヘッドの移動を減少させるようにディスクドライブに配置される請求項３記載のファイル配置方法。
【請求項１３】
上記ファイルを再配置するステップは、上記ストレージデバイスのファイル断片化を含む総合的なデータエントロピを最小化する請求項３記載のファイル配置方法。
【請求項１４】
上記ファイルを再配置するステップは、空き領域断片化を最小化する請求項１３記載のファイル配置方法。
【請求項１５】
コンピュータシステムに実装される、ストレージデバイスのファイルを配置するファイル配置方法において、
オペレーティングシステムのタイプの判定を含み、上記ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するステップと、
システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するステップと、
上記共通に用いられるファイル及び関連するファイルの判定に基づいて、上記ストレージデバイスのファイルを保存する特定の物理的順序を決定するステップと、
上記ストレージデバイスのシーケンシャルで連続する位置に上記ファイルを配置することによって、上記判定された特定の順序にしたがって、該ストレージデバイスにファイルを再配置するステップとを有するファイル配置方法。
【請求項１６】
上記ファイルを再配置する前に、上記ストレージデバイス上で使用可能な空き領域を解析するステップを更に有する請求項１５記載のファイル配置方法。
【請求項１７】
所定のファイルを再配置し、所定の位置に配置した後に、残りのファイルを再配置するステップを更に有する請求項１６記載のファイル配置方法。
【請求項１８】
上記ファイルは、関連するファイルの優先度付けされたグループ化に基づいて、ストレージデバイスに物理的に配置され、
上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択される請求項１６記載のファイル配置方法。
【請求項１９】
上記使用可能な空き領域を解析し、ファイルを再配置するステップは、システムの動作の間に動的に実行される請求項１６記載のファイル配置方法。
【請求項２０】
データエントロピのレートがしきい値より高いストレージデバイスの位置を特定するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するステップとを更に有する請求項１６記載のファイル配置方法。
【請求項２１】
上記ストレージデバイスは、ハードディスクドライブであり、上記ファイルは、関連するファイルにアクセスする際にヘッドの移動を減少させるようにディスクドライブ上に配置される請求項１５記載のファイル配置方法。
【請求項２２】
上記ファイルを再配置するステップは、上記ストレージデバイス上のファイル断片化を含む総合的なデータエントロピを最小化する請求項１５記載のファイル配置方法。
【請求項２３】
上記ファイルを再配置するステップは、空き領域断片化を最小化する請求項２２記載のファイル配置方法。
【請求項２４】
コンピュータに実装され、コンピュータシステムのストレージデバイスのデータエントロピを削減するデータエントロピ削減方法において、
ディレクトリ及びファイルを含む、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するステップと、
上記ストレージデバイスの使用可能な空き領域を解析するステップと、
所定のファイルを所定の位置に配置するステップと、
上記ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、上記ストレージデバイスに物理的に互いに近接するように配置することによって、該ストレージデバイスの残りのファイルを再配置するステップとを有し、
上記ファイルは、関連するファイルの優先度付けされたグループ化にしたがって、上記ストレージデバイスに物理的に配置され、上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合は、上記ファイルのグループを保存するために更なる空き領域チャンクが選択されるデータエントロピ削減方法。
【請求項２５】
ストレージデバイスにファイルを配置するファイル配置プログラムのコードを含むコンピュータが読取可能な媒体において、
上記ファイル配置プログラムは、
上記ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、
上記判定された論理的関係に基づいて、論理的に関連するファイルを、上記ストレージデバイスに物理的に互いに近接するように配置することによって、該ストレージデバイスのファイルを再配置するコードを実行するステップとを有し、
上記ファイルを再配置するステップは、上記ストレージデバイスの実質的に全てのファイルについて実行されるファイル配置プログラムが記録された媒体。
【請求項２６】
上記論理的関係を判定するコードを実行するステップは、コンピュータシステムにおけるファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップを含む請求項２５記載の媒体。
【請求項２７】
上記ストレージデバイス上使用可能な空き領域を解析するコードを実行するステップを更に有する請求項２５記載の媒体。
【請求項２８】
所定のファイルを所定の位置に配置した後、残りのファイルを再配置するコードを実行するステップを更に有する請求項２７記載の媒体。
【請求項２９】
各フォルダからのファイルを上記ストレージデバイスで論理的順序で連続的に保存するコードを実行するステップを更に有する請求項２８記載の媒体。
【請求項３０】
上記ファイルを、関連するファイルの優先度付けされたグループ化に基づいて、上記ストレージデバイスに物理的に配置するコードを実行するステップを更に有する請求項２７記載の媒体。
【請求項３１】
上記ファイルの優先度付けされたグループを、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置し、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクを選択するコードを実行するステップを更に有する請求項３０記載の媒体。
【請求項３２】
上記使用可能な空き領域を解析し、ファイルを再配置するコードは、システムの動作の間に動的に実行される請求項２９記載の媒体。
【請求項３３】
データエントロピのレートがしきい値より高い上記ストレージデバイスの位置を特定するコードを実行するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するコードを実行するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するコードを実行するステップとを更に有する請求項２７記載の媒体。
【請求項３４】
上記ストレージデバイスにアクセスするコンピュータシステムのタイプに基づいて、共通に用いられるファイルの第１のサブセットを特定するコードを実行するステップと、
システムの動作を監視し、該システムの動作の間に共通に用いられるデータ又はファイルの第２のサブセットを特定するコードを実行するステップと、
上記ファイルの第１及び第２のサブセット並びにすべての関連するファイルを、ストレージデバイスの物理的に連続するグループに保存することによって、上記特定された共通に用いられるファイルの第１及び第２のサブセット並びにすべての関連するファイルを再配置するコードを実行するステップとを更に有する請求項２５記載の媒体。
【請求項３５】
コンピュータシステムのストレージデバイスのファイルを配置するファイル配置プログラムのコードを含むコンピュータが読取可能な媒体において、
オペレーティングシステムのタイプの判定を含み、上記ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するコードを実行するステップと、
システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するコードを実行するステップと、
上記共通に用いられるファイル及び関連するファイルの判定に基づいて、上記ストレージデバイスのファイルを保存する特定の物理的順序を決定するコードを実行するステップと、
上記ストレージデバイスのシーケンシャルで連続する位置に上記ファイルを配置することによって、上記判定された特定の順序にしたがって、該ストレージデバイスのファイルを再配置するコードを実行するステップとを有するファイル配置プログラムを記録した媒体。
【請求項３６】
上記ファイルを再配置する前に、上記ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップを更に有する請求項３５記載の媒体。
【請求項３７】
所定のファイルを再配置し所定の位置に配置した後に、残りのファイルを再配置するコードを実行するステップを更に有する請求項３６記載の媒体。
【請求項３８】
関連するファイルの優先度付けされたグループ化にしたがって、ストレージデバイスに物理的にファイルを配置するコードを実行するステップを更に有し、上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択される請求項３６記載の媒体。
【請求項３９】
上記使用可能な空き領域を解析し、ファイルを再配置するコードは、システムの動作の間に動的に実行される請求項３６記載の媒体。
【請求項４０】
データエントロピのレートがしきい値より高いストレージデバイス上の位置を特定するコードを実行するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するコードを実行するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するコードを実行するステップとを更に有する請求項３６記載の媒体。
【請求項４１】
コンピュータシステムのストレージデバイスのデータエントロピを削減するデータエントロピ削減プログラムのコードを含むコンピュータが読取可能な媒体において、
上記データエントロピ削減プログラムは、
ディレクトリ及びファイルを含む、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップと、
上記ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップと、
所定のファイルを所定の位置に配置するコードを実行するステップと、
上記ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、上記ストレージデバイスで物理的に互いに近接するように配置することによって、上記ストレージデバイスの残りのファイルを再配置するコードを実行するステップとを有し、
上記ファイルは、関連するファイルの優先度付けされたグループ化にしたがって、ストレージデバイスに物理的に配置され、該ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択されるデータエントロピ削減プログラムを記録した媒体。
【請求項４２】
ストレージデバイスでファイルを配置するコンピュータシステムにおいて、
コンピュータプログラムのコードを実行するプロセッサを備え、
上記コンピュータプログラムは、
上記ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、
上記判定された論理的関係に基づいて、論理的に関連するファイルを、上記ストレージデバイスに物理的に互いに近接するように配置することによって上記ファイルを上記ストレージデバイスで再配置するコードを実行するステップとを有し、
上記ファイルを再配置するコードを実行するステップは、上記ストレージデバイスの実質的に全てのファイルについて実行されることを特徴とするコンピュータシステム。
【請求項４３】
上記論理的関係を判定するコードを実行するステップは、コンピュータシステムのファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップを含む請求項４２記載のコンピュータシステム。
【請求項４４】
上記ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップを更に有する請求項４２記載のコンピュータシステム。
【請求項４５】
所定のファイルを所定の位置に配置した後、残りのファイルを再配置するコードを実行するステップを更に有する請求項４４記載のコンピュータシステム。
【請求項４６】
各フォルダからのファイルを上記ストレージデバイスに論理的順序で連続的に保存するコードを実行するステップを更に有する請求項４５記載のコンピュータシステム。
【請求項４７】
上記ファイルを、関連するファイルの優先度付けされたグループ化に基づいて、上記ストレージデバイスで物理的に配置するコードを実行するステップを更に有する請求項４４記載のコンピュータシステム。
【請求項４８】
上記ファイルの優先度付けされたグループを、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置し、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合は、上記ファイルのグループを保存するために更なる空き領域チャンクを選択するコードを実行するステップを更に有する請求項４７記載のコンピュータシステム。
【請求項４９】
上記使用可能な空き領域を解析し、ファイルを再配置するコードは、システムの動作の間に動的に実行される請求項４６記載のコンピュータシステム。
【請求項５０】
データエントロピのレートがしきい値より高いストレージデバイス上の位置を特定するコードを実行するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するコードを実行するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するコードを実行するステップとを更に有する請求項４４記載のコンピュータシステム。
【請求項５１】
上記ストレージデバイスにアクセスするコンピュータシステムのタイプに基づいて、共通に用いられるファイルの第１のサブセットを特定するコードを実行するステップと、
システムの動作を監視し、該システムの動作の間に共通に用いられるデータ又はファイルの第２のサブセットを特定するコードを実行するステップと、
上記ファイルの第１及び第２のサブセット及びすべての関連するファイルを、ストレージデバイスの物理的に連続するグループに保存することによって、上記特定された共通に用いられるファイルの第１及び第２のサブセット及びすべての関連ファイルを再配置するコードを実行するステップとを更に有する請求項４２記載のコンピュータシステム。
【請求項５２】
ストレージデバイスのファイルを配置するコンピュータシステムにおいて、
コンピュータプログラムのコードを実行するためのプロセッサを備え、上記コンピュータプログラムは、
オペレーティングシステムのタイプの判定を含み、上記ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するコードを実行するステップと、
システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するコードを実行するステップと、
上記共通に用いられるファイル及び関連するファイルの判定に基づいて、上記ストレージデバイス上にファイルを保存する特定の物理的順序を決定するコードを実行するステップと、
上記ストレージデバイスのシーケンシャルで連続する位置に上記ファイルを配置することによって、上記判定された特定の順序にしたがって、該ストレージデバイスのファイルを再配置するコードを実行するステップとを有するコンピュータシステム。
【請求項５３】
上記ファイルを再配置する前に、上記ストレージデバイス上で使用可能な空き領域を解析するコードを実行するステップを更に有する請求項５２記載のコンピュータシステム。
【請求項５４】
所定のファイルを再配置し所定の位置に配置した後に、残りのファイルを再配置するコードを実行するステップを更に有する請求項５３記載のコンピュータシステム。
【請求項５５】
関連するファイルの優先度付けされたグループ化に基づいて、ストレージデバイスで物理的にファイルを配置するコードを実行するステップを更に有し、上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択される請求項５３記載のコンピュータシステム。
【請求項５６】
上記使用可能な空き領域を解析し、ファイルを再配置するコードは、システムの動作の間に動的に実行される請求項５３記載のコンピュータシステム。
【請求項５７】
データエントロピのレートがしきい値より高いストレージデバイス上の位置を特定するコードを実行するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するコードを実行するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するコードとを更に有する請求項５３記載のコンピュータシステム。
【請求項５８】
ストレージデバイスのデータエントロピを削減するコンピュータシステムにおいて、
コンピュータプログラムのコードを実行するためのプロセッサを備え、該コンピュータプログラムは、
ディレクトリ及びファイルを含む、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップと、
上記ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップと、
所定のファイルを所定の位置に配置するコードを実行するステップと、
上記ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、上記ストレージデバイスで物理的に互いに近接するように配置することによって、該ストレージデバイスの残りのファイルを再配置するコードを実行するステップとを有し、
上記ファイルは、関連ファイルの優先度付けされたグループ化にしたがって、ストレージデバイスで物理的に配置され、該ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択されることを特徴とするコンピュータシステム。
【請求項５９】
コンピュータに実装され、データの集合のデータエントロピを削減するデータエントロピ削減方法において、
上記データの集合におけるデータエントロピのレベルを判定するステップと、
上記データの集合内で、論理的関係を有するデータのサブグループを判定するステップと、
上記判定された論理的関係に基づいて、データのサブグループを再配置し、上記データの集合のデータエントロピのレベルを削減するステップとを有するデータエントロピ削減方法。
【請求項６０】
上記再配置のステップは、上記データのサブグループを連続するシーケンスに順序付け、論理的に関連するデータを互いに隣り合うように配置して、該データの間の空き領域を減少させるステップを含む請求項５９記載のデータエントロピ削減方法。
【請求項６１】
コンピュータに実装され、ストレージデバイスにファイルを配置するファイル配置方法において、
上記ストレージデバイスのファイルの論理的関係を判定するステップと、
上記判定された論理的関係に基づいて、論理的に関連するファイルを、上記ストレージデバイスに物理的に互いに近接するように配置することによってファイルを該ストレージデバイスで再配置するステップとを有し、
上記ファイルを再配置するステップは、ファイル使用についての事前の解析なしで実行されるファイル配置方法。
【請求項６２】
上記再配置の結果、上記ストレージデバイスのファイルのデータエントロピが減少する請求項６１記載のファイル配置方法。
【請求項６３】
上記論理的関係を判定するステップは、コンピュータシステムにおけるファイルシステムのファイルディレクトリインデクス構造を判定するステップを含む請求項６１記載のファイル配置方法。
【請求項６４】
上記ファイルの再配置の前にストレージデバイスの使用可能な空き領域を解析するステップを更に有する請求項６１記載のファイル配置方法。
【請求項６５】
所定のファイルを所定の位置に配置した後、残りのファイルを再配置するステップを更に有する請求項６４記載のファイル配置方法。
【請求項６６】
各フォルダからのファイルは、上記ストレージデバイスに論理的順序で連続的に保存される請求項６５記載のファイル配置方法。
【請求項６７】
上記ファイルは、関連するファイルの優先度付けされたグループ化にしたがって、上記ストレージデバイスに物理的に配置される請求項６４記載のファイル配置方法。
【請求項６８】
上記ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクが選択される請求項６７記載のファイル配置方法。
【請求項６９】
上記使用可能な空き領域を解析し、ファイルを再配置するステップは、システムの動作の間に動的に実行される請求項６４記載のファイル配置方法。
【請求項７０】
データエントロピのレートがしきい値より高いストレージデバイスの位置を特定するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するステップとを更に有する請求項６４記載のファイル配置方法。
【請求項７１】
上記ストレージデバイスにアクセスするコンピュータシステムのタイプに基づいて、共通に用いられるファイルの第１のサブセットを特定するステップと、
システムの動作を監視し、該システムの動作の間に共通に用いられるデータ又はファイルの第２のサブセットを特定するステップと、
上記ファイルの第１及び第２のサブセット及びすべての関連するファイルを、ストレージデバイス上の物理的に連続するグループに保存することによって、上記特定された共通に用いられるファイルの第１及び第２のサブセット及びすべての関連ファイルを再配置するステップとを更に有する請求項６１記載のファイル配置方法。
【請求項７２】
上記ストレージデバイスは、ハードディスクドライブであり、上記ファイルは、同じフォルダからファイルにアクセスする際にヘッドの移動を減少させるようにディスクドライブ上に配置される請求項６３記載のファイル配置方法。
【請求項７３】
上記ファイルを再配置するステップは、上記ストレージデバイス上のファイル断片化を含む総合的なデータエントロピを最小化する請求項６３記載のファイル配置方法。
【請求項７４】
上記ファイルを再配置するステップは、空き領域断片化を最小化する請求項７３記載のファイル配置方法。
【請求項７５】
ストレージデバイスのファイルを配置するファイル配置プログラムのコードを含むコンピュータが読取可能な媒体において、
上記ファイル配置プログラムは、
上記ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、
上記判定された論理的関係に基づいて、論理的に関連するファイルを、該ストレージデバイスで物理的に互いに近接するように配置することによってファイルを上記ストレージデバイス再配置するコードを実行するステップとを有し、
上記ファイルを再配置するステップは、ファイル使用についての事前の解析なしで実行されるファイル配置プログラムが記録された媒体。
【請求項７６】
上記論理的関係を判定するコードを実行するステップは、コンピュータシステムにおけるファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップを含む請求項７５記載の媒体。
【請求項７７】
上記ファイルの再配置の前にストレージデバイスの使用可能な空き領域を解析するコードを実行するステップを更に有する請求項７５記載の媒体。
【請求項７８】
所定のファイルを所定の位置に配置した後、残りのファイルを再配置するコードを実行するステップを更に有する請求項７７記載の媒体。
【請求項７９】
各フォルダからのファイルを上記ストレージデバイスに論理的順序で連続的に保存するコードを実行するステップを更に有する請求項７８記載の媒体。
【請求項８０】
上記ファイルを、関連するファイルの優先度付けされたグループ化にしたがって、上記ストレージデバイスで物理的に配置するコードを実行するステップを更に有する請求項７７記載の媒体。
【請求項８１】
上記ファイルの優先度付けされたグループを、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置し、上記ファイルのグループの全体が格納される前に次の空き領域チャンクが満たされた場合には、上記ファイルのグループを保存するために更なる空き領域チャンクを選択するコードを実行するステップを更に有する請求項８０記載の媒体。
【請求項８２】
上記使用可能な空き領域を解析し、ファイルを再配置するコードは、システムの動作の間に動的に実行される請求項７９記載の媒体。
【請求項８３】
データエントロピのレートがしきい値より高いストレージデバイス上の位置を特定するコードを実行するステップと、
上記データエントロピのレートがしきい値より高い位置を監視するコードを実行するステップと、
使用可能な空き領域を解析し、上記特定された位置のファイルを再配置するステップを自動的に実行するコードを実行するステップとを更に有する請求項７７記載の媒体。
【請求項８４】
上記ストレージデバイスにアクセスするコンピュータシステムのタイプに基づいて、共通に用いられるファイルの第１のサブセットを特定するコードを実行するステップと、
システムの動作を監視し、該システムの動作の間に共通に用いられるデータ又はファイルの第２のサブセットを特定するコードを実行するステップと、
上記ファイルの第１及び第２のサブセット及びすべての関連するファイルを、ストレージデバイスの物理的に連続するグループに保存することによって、上記特定された共通に用いられるファイルの第１及び第２のサブセット及びすべての関連するファイルを再配置するコードを実行するステップとを更に有する請求項７５記載の媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、データストレージに関し、より具体的には、システム性能を向上させるためのファイルストレージの改善技術に関する。
【背景技術】
【０００２】
ファイル断片化は、コンピュータデータストレージにおいてよく知られている問題である。典型的なファイルシステムでは、ファイルは、クラスタと呼ばれるユニットに保存される。ファイルが新しいストレージデバイスに最初に保存される場合、ストレージデバイスは、通常、１つの物理的な位置から開始される１つ以上の一組の隣接するクラスタにファイルを保存することができる。しかしながら、ファイルが変更、追加、削除されるにつれて、ストレージデバイスは、１つの位置に特定のファイルを保存できなくなり、ファイルは、分断され、論理的にリンクされた複数の位置に保存されることがある。これをファイル断片化（file fragmentation）と呼ぶ。ある場合には、単一のファイル内の物理データが数百以上の異なる位置に保存されることもあり、通常、ストレージデバイスは、各「フラグメント」の最後で停止し、ファイルの全体を処理するために、この位置の数と同じ回数、読出装置を次のフラグメントの始めに移動させる必要がある。
【０００３】
上述のように、ファイルは、一般的に、ストレージデバイス上のクラスタ（又は幾つかのファイルシステムではブロック）と呼ばれる物理的空間のユニット内に保存される。各クラスタの一定のデータ容量は、ファイルシステムによって決定される。ファイル内のデータの総サイズが単一のクラスタのデータ容量より更に小さい場合であっても、各クラスタは、通常、（全てのデータを含む場合）単一の離散的なファイルからのデータのみを含み、２つ以上のファイルからのデータを含むことはない。データが一度も書き込まれたことがない未使用のクラスタ又はデータが論理的に消去されたクラスタは、「空き領域（free space）」と呼ばれる。更に、２つのファイルがディスク上の近くに位置し、それらの間に１つ以上のクラスタがそのまま残っている場合、この空のクラスタも「空き領域」を形成する。現在のファイルシステム技術における解釈と同様であるが、本明細書の目的において、クラスタの未使用部分（スラック領域（slack space）とも呼ばれる。）は、空き領域とはみなさない。
【０００４】
ディスク上で多くの空のクラスタが連続的に使用可能である場合、これらに、単一の連続するシーケンスで大きいファイルを書き込むことができる。しかしながら、ファイルが変更、追加、削除されるにつれて、ストレージデバイス上の空き領域を含む多くの物理的な位置が小さくなり、使用可能な容量の合計が十分であっても、あるサイズを超えるファイルを連続的に保存することができなくなる。これは空き領域断片化（free space fragmentation）と呼ばれる。
【０００５】
ファイル断片化は、特に、磁気ハードディスクドライブ等の機械的なストレージデバイスを使用する場合、デバイス上で単一のファイルを読み出すために何度も機械的なヘッド位置を変更する必要があるので、深刻なシステム性能劣化を引き起こす場合がある。更に、空き領域断片化は、ストレージデバイスに書き込みを行う場合、ファイルシステムが大きいファイルを使用可能なディスク領域の断片に分割しなければならないので、重要な性能劣化を引き起こす場合がある。このため、機械的なストレージデバイス、例えば、磁気ハードディスクドライブを使用する場合、ドライブヘッドを移動させて複数の位置に書き込みを行う必要がある。断片化された空き領域に書き込まれたファイルは必ず断片化され、これが、ファイル断片化の共通の根源的な要因である。
【０００６】
これらの問題を軽減するために、ストレージデバイスを「非断片化（defragment）する」ためのソフトウェアプログラムが開発されている。これらのプログラムは、一般的に、各ファイルが単一の位置に近接して保存されるようにファイルクラスタを再配列し、可能な範囲内で、小さい空き領域の位置を統合するように動作する。しかしながら、ストレージデバイスは、すぐに再断片化されるので、この手法は、一時的に、限定的な程度にシステム性能を向上させるのみであり、個々のファイルに関して性能を向上させるだけであり、複数の関連するファイル、例えば、特定のソフトウェアアプリケーションを起動するときに読み出される全てのファイルに関して性能を向上させるものではない。
【０００７】
例えば，米国特許第５，３９８，１４２号には、次のような記載がある。
【０００８】
市販されている多くの製品が、ファイル断片化の問題を取り扱い、これを解消しようと試みている。このような製品の１つは、セントラルポイントソフトウェア社（Central Point Software, Inc.）のＰＣツールズデラックス（PC Tools Deluxe：商標）である。このソフトウェアパッケージは、各ファイルが１つの連続的な領域に含まれるようにハードディスク又はディスケット上のファイルを配置する機能を含んでいる。他の機能は、ファイルを非断片化して、ディスクの後部の空き領域に移動させる機能である。また、このソフトウェアでは、ハードディスク上に所定の方式でファイルを配置することができる。例えば、所与のサブディレクトリに属する全てのファイルを一緒に保存することによって、データ及びプログラムオーバレイファイルを互いに隣り合うように保存することができる。これによって、必要なディスクヘッドの移動量を低減することができる。ディレクトリソート機能によって、ディレクトリ内のファイルを、ファイル名、ファイル作成日時、ファイル拡張子又はファイルサイズによってソートすることができる。これらの機能に関する情報は、１９８８年１２月に発売されたＰＣツールズデラックス（PC Tools Deluxe）バージョン５に記載されている。但し、これ及び類似の製品は、ディスクの後部に空き領域を配置する。上述したように、ファイルが作成及び削除されるにつれて、連続する空き領域は、劣化し、断片化問題が再発生する。特に、ブートタイムの間に更にシステム性能を改善するために、マイクロソフトウィンドウズ（Microsoft Windows：商標）オペレーティングシステムは、プリフェッチャ（Prefetcher）と呼ばれるコンポーネントを含む。米国特許第６，６３３，９６８号に開示されているように、プリフェッチャは、ブート処理の間、実行可能なコードと、アクセスされるデータを監視し、この作業のログファイルを記録することによって動作する。そして、プリフェッチャは、ログファイルに記録された情報に予測的で確率的なアルゴリズムを適用して、より最適な手法でコード及びデータをロードする。更に、デフラグメンタ（defragmenter）を用いて、プリフェッチャによってロードされた特定の実行可能なファイルを、ストレージデバイス上の特定の位置に、特定の順序で配置する。例えば、ストレージデバイスの予約された、アクセス速度がより速い領域にファイルを保存できる。プリフェッチャアルゴリズムの１つの短所は、ユーザが既に使用することがなくても、ブート処理の間に、幾つかのファイルが常にロードされることがある点である。
【０００９】
システム性能を改善するための他の技術は、米国特許公開番号第２００８／００２７９０５号に開示されている。１つ以上のストレージデバイスに保存されるファイルは、異なるセットの「ランキング」に分類される。異なる領域の検索値の違いを利用してどの領域にどのファイルを保存するかを選択する。例えば、より上位に分類されるファイルは、読出時間がより速い領域に保存される。一般に、これ及び同様の技術は、「ディスク最適化」と呼ばれる。幾つかのディスク最適化技術では、頻繁に使用されるファイルを追跡し、これらに優先度ランキングを付与する。優先度がより高いファイルは、より速い領域に書き込まれ、優先度がより低いファイルは、より遅い領域に書き込まれる。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述のように、あるファイルを単にデバイス上の特定の位置に移動させることによってストレージデバイスを最適化しても、幾つかの場合、性能がある程度向上する。例えば、ストレージデバイス上の特定の物理的な位置にドキュメントファイルのグループが全て再配置されれば、ファイルが順次的に参照される場合、性能向上を実現することができる。しかしながら、ユーザが文書編集アプリケーションを用いて同じファイルを編集することを望む場合、アプリケーションを使用する前に全て物理的に読み出す必要があるそのプログラムアプリケーションファイル、それらの依存関係及び関連するツールは、不規則で予測不能な状態でストレージデバイスに亘って物理的に離散していることがあり（この明細書では、これを「データエントロピ（data entropy）」と呼ぶ）、この結果、ストレージデバイスは、全体的な実行シーケンス内で、１つのファイルの最後に達する都度、何度も停止して、読出装置の位置を変更し、処理すべき次のファイルの位置を特定する必要がある。ストレージデバイス内のこの「データエントロピ」によって、ファイル又は空き領域の断片化がなくても、一緒に編集されるドキュメントファイルだけをグループ化することによって得られる性能の向上が部分的又は全体的に達成されないことがある。ストレージデバイス上の離散的データエンティティの物理的組織構造内のこのようなデータエントロピは、ファイル又は空き領域の断片化が存在しているか否かに関係なく、深刻な性能損失を生じさせることがある。
【００１１】
また、以下の通り、米国特許公開番号第２００８／００２７９０５号に開示されているように、データをグループ化してもよい。
【００１２】
データグループ化に基づく分類ファイル
［００４４］ファイル又はファイルの一部をストレージ媒体上のある領域にグループ化することによって、性能を大幅に向上させることができる。例えば、ワードプロセッサを起動した場合、幾つかの異なるファイル及び／又はファイルの一部がロードされ、更に起動時にデータがロードされることもある。コンピュータがディスクの幾つかの異なる領域にアクセスして必要なファイル又はファイルの一部をロードする必要がある場合、これらの全てのファイルがこのディスク上の同じ領域にある場合に比べて、実質的に時間がかかる。また、フォルダ（ディレクトリ）に含まれているファイルによってフォルダ（ディレクトリ）を更にグループ化することによって、ある状況下では、コンピュータシステムの速度が向上する。如何なるファイルをグループ化したらよいかを決定するためには、ディスクから如何なるファイルが順に読み出されるかを追跡し続ければよい。パターンが確認できる場合、これらのファイル又はファイルの一部を共にグループ化する。
【００１３】
しかしながら、ストレージデバイスの全体に亘って、システム性能を向上させる系統的な方式で、予め監視を行うことなく、全てのファイル又はデータを組織化する手法は知られていない。
【課題を解決するための手段】
【００１４】
本発明は、包括的には、ストレージデバイスにおけるデータのデータエントロピを低減する効率的なデータストレージのためのシステム及び方法である。本発明は、関連する複数の不連続データエンティティ（ハードディスクドライブ上のファイル等）を、物理的に近接し、予測可能な又は順序付けられたシーケンスで組織化することによって、記憶／読出装置が要求のシーケンスを処理する際に各データエンティティの位置を特定するために費やされる時間及び（機械的、演算的及びその他の）負担を削減する。例えば、ファイルディレクトリインデクス構造に基づいて、データを組織化及び保存してもよく、これによって、データ及び空き領域の断片化も減少する。
【００１５】
一実施の形態では、本発明は、コンピュータに実装され、ストレージデバイスにファイルを配置するファイル配置方法として実現され、この方法は、ストレージデバイスのファイルの論理的関係を判定するステップと、判定された論理的関係に基づいて、論理的に関連するファイルを、ストレージデバイスに物理的に互いに近接するように配置することによって、ファイルをストレージデバイスに再配置するステップとを有し、再配置は、ストレージデバイスの実質的に全てのファイルについて実行される。
【００１６】
他の実施の形態では、コンピュータに実装され、コンピュータシステムにおけるストレージデバイスでファイルを配置するファイル配置方法は、オペレーティングシステムのタイプの判定を含み、ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するステップと、システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するステップと、共通に用いられるファイル及び関連するファイルの判定に基づいて、ストレージデバイスにファイルを保存する特定の物理的順序を決定するステップと、ストレージデバイスのシーケンシャルで連続する位置にファイルを配置することによって、判定された特定の順序に基づいて、ストレージデバイスのファイルを再配置するステップとを有する。
【００１７】
他の実施の形態では、コンピュータに実装され、コンピュータシステムのストレージデバイスのデータエントロピを削減するデータエントロピ削減方法は、ディレクトリ及びファイルを含む、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するステップと、ストレージデバイスの使用可能な空き領域を解析するステップと、所定のファイルを所定の位置に配置するステップと、ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、ストレージデバイスに物理的に互いに近接するように配置することによって、ストレージデバイスの残りのファイルを再配置するステップとを有し、ファイルは、関連するファイルの優先度付けされたグループ化にしたがって、ストレージデバイスに物理的に配置され、ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、ファイルのグループの全体が保存される前に次の空き領域チャンクが満たされた場合は、ファイルのグループを保存するために更なる空き領域チャンクが選択される。
【００１８】
ストレージデバイスにファイルを配置するファイル配置プログラムのコードを含むコンピュータが読取可能な媒体では、ファイル配置プログラムは、ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、判定された論理的関係に基づいて、論理的に関連するファイルを、ストレージデバイスで物理的に互いに近接するように配置することによって、ファイルをストレージデバイスに再配置するコードを実行するステップとを有し、ファイルを再配置するステップは、ストレージデバイスの実質的に全てのファイルについて実行される。
【００１９】
コンピュータシステムのストレージデバイスのファイルを配置するファイル配置プログラムのコードを含む他のコンピュータが読取可能な媒体では、ファイル配置プログラムは、オペレーティングシステムのタイプの判定を含み、ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するコードを実行するステップと、システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するコードを実行するステップと、共通に用いられるファイル及び関連するファイルの判定に基づいて、ストレージデバイスにファイルを保存する特定の物理的順序を決定するコードを実行するステップと、ストレージデバイスのシーケンシャルで連続する位置にファイルを配置することによって、判定された特定の順序に基づいて、ストレージデバイスのファイルを再配置するコードを実行するステップとを有する。
【００２０】
一実施の形態においては、コンピュータシステムにおけるストレージデバイスのデータエントロピを削減するデータエントロピ削減プログラムのコードを含むコンピュータが読取可能な媒体では、データエントロピ削減プログラムは、ディレクトリ及びファイルを含み、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップと、ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップと、所定のファイルを所定の位置に配置するコードを実行するステップと、所定のファイルを所定の位置に配置するコードを実行するステップと、ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、ストレージデバイスで物理的に互いに近接するように配置することによって、ストレージデバイスの残りのファイルを再配置するコードを実行するステップとを有し、ファイルは、関連するファイルの優先度付けされたグループ化にしたがって、ストレージデバイスで物理的に配置され、ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、ファイルのグループの全体が保存される前に次の空き領域チャンクが満たされた場合は、ファイルのグループを保存するために更なる空き領域チャンクが選択される。
【００２１】
本発明は、ストレージデバイスでファイルを配置するコンピュータシステムとして実現してもよく、コンピュータシステムは、コンピュータプログラムのコードを実行するためのプロセッサを備え、コンピュータプログラムは、ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、判定された論理的関係に基づいて、論理的に関連するファイルを、ストレージデバイスに物理的に互いに近接するように配置することによってファイルをストレージデバイスで再配置するコードを実行するステップとを有し、ファイルを再配置するステップは、ストレージデバイスの実質的に全てのファイルについて実行される。
【００２２】
他の実施の形態では、コンピュータシステムのストレージデバイスでファイルを配置するコンピュータシステムは、コンピュータプログラムのコードを実行するためのプロセッサを備え、コンピュータプログラムは、オペレーティングシステムのタイプの判定を含み、ストレージデバイスを使用するコンピュータシステムのタイプの解析に基づいて、共通に用いられるファイルを判定するコードを実行するステップと、システムの動作を監視することによって、共通に用いられるファイル及びすべての関連するファイルを判定するコードを実行するステップと、共通に用いられるファイル及び関連するファイルの判定に基づいて、ストレージデバイスでファイルを保存する特定の物理的順序を決定するコードを実行するステップと、ストレージデバイスのシーケンシャルで連続する位置にファイルを配置することによって、判定された特定の順序に基づいて、ストレージデバイスのファイルを再配置するコードを実行するステップとを有する。
【００２３】
ストレージデバイスのデータエントロピを削減するコンピュータシステムは、コンピュータプログラムのコードを実行するためのプロセッサを備え、コンピュータプログラムは、ディレクトリ及びファイルを含み、ストレージデバイスのファイルシステムのファイルディレクトリインデクス構造を判定するコードを実行するステップと、ストレージデバイスの使用可能な空き領域を解析するコードを実行するステップと、所定のファイルを所定の位置に配置するコードを実行するステップと、ファイルディレクトリインデクス構造に基づいて、論理的に関連するファイルを、ストレージデバイスに物理的に互いに近接するように配置することによって、ストレージデバイスの残りのファイルを再配置するコードを実行するステップとを有し、ファイルは、関連するファイルの優先度付けされたグループ化に基づいて、ストレージデバイスで物理的に配置され、ファイルの優先度付けされたグループは、使用可能な優先度付けされた次の空き領域チャンクに連続的に配置され、ファイルのグループの全体が保存される前に次の空き領域チャンクが満たされた場合は、ファイルのグループを保存するために更なる空き領域チャンクが選択される。
【００２４】
一実施の形態においては、コンピュータに実装され、データの集合のデータエントロピを削減するデータエントロピ削減方法は、データの集合におけるデータエントロピのレベルを判定するステップと、データの集合内で、論理的関係を有するデータのサブグループを判定するステップと、判定された論理的関係に基づいて、データのサブグループを再配置し、データの集合のデータエントロピのレベルを削減するステップとを有する。
【００２５】
他の実施の形態では、コンピュータに実装され、ストレージデバイスにファイルを配置するファイル配置方法は、ストレージデバイスのファイルの論理的関係を判定するステップと、判定された論理的関係に基づいて、論理的に関連するファイルを、ストレージデバイスで物理的に互いに近接するように配置することによってファイルをストレージデバイスに再配置するステップとを有し、ファイルを再配置するステップは、ファイル使用についての事前の解析なしで実行される。
【００２６】
他の実施の形態では、ストレージデバイスにファイルを配置するファイル配置プログラムのコードを含むコンピュータが読取可能な媒体では、ファイル配置プログラムは、ストレージデバイスのファイルの論理的関係を判定するコードを実行するステップと、判定された論理的関係に基づいて、論理的に関連するファイルを、ストレージデバイスに物理的に互いに近接するように配置することによって、ファイルをストレージデバイスに再配置するコードを実行するステップとを有し、ファイルを再配置するステップは、ファイル使用についての事前の解析なしで実行される。
【００２７】
本発明は、添付の図面を参照する以下の詳細な説明によって容易に理解される。
【図面の簡単な説明】
【００２８】
【図１】本発明の一実施の形態を示すフローチャートである。
【図２】本発明の実施の形態に基づいて、ストレージデバイス上でデータ及びファイルを組織化する手順の実施の形態を示すフローチャートである。
【図３】ストレージデバイス上でファイルを順序付けるために本発明で使用する部分的なディレクトリ構造のサンプルリストである。
【図４】本発明の実施の形態による処理の前のストレージデバイスの相対的な断片化を示すサンプルスクリーンショットである。
【図５】本発明によって処理した後にファイルがどのように再配置されるかを示すサンプルスクリーンショットである。
【図６】ファイルがどのように再配置され、及びファイルがどこに由来するかを示すサンプルスクリーンショットである。
【図７】本発明の他の実施の形態のフローチャートである。
【図８】ストレージデバイスが単一の断片化したファイルを通常どのように読み出すかを示す図である。
【図９】ファイル非断片化が実行された後に、ストレージデバイスが単一の連続域ファイルを通常どのように読み出すかを示す図である。
【図１０】ストレージデバイスが、ファイル断片化はないが、データエントロピがある複数のデータファイルを通常どのように読み出すかを示す図である。
【図１１】ストレージデバイスが、データエントロピもファイル断片化もない複数の関連するファイルをどのように読み出すかを示す図である。
【図１２】本発明の実施の形態に基づき、ファイルをストレージデバイス上で組織化し及び優先度付けされたグループ内で順序付けすることによって、データエントロピを最小化し、及びファイル及び空き領域の断片化を防ぐ手法を示す図である。
【図１３】本発明の実施の形態に基づき、優先度付けされたグループ内の既存の論理的なインデクスに基づいて、データ及びファイルを組織化及び順位付けする手法を示す図である。
【図１４】本発明の実施の形態に基づき、図１３に示す優先度付けされたグループ内で、既存の論理的なインデクスに基づいて、ストレージデバイス上でデータ及びファイルを物理的に組織化及び順序付けする手法を示す図である。
【発明を実施するための形態】
【００２９】
以下の説明によって、如何なる当業者も本発明を製造及び実施でき、以下の説明は、本発明を実施するための本発明者が想到する最良の形態を述べるものである。但し、当業者は、様々な変更を容易に想到できる。このような変更、均等物及び代替の全ては、本発明の思想及び範囲内に含まれる。
【００３０】
本発明は、包括的に言えば、関連する複数の不連続データエンティティ（ハードディスクドライブ上のファイル等）を、物理的に近接し、予測可能な又は順序付けられたシーケンスで組織化することによって、記憶／読出装置が要求のシーケンスを処理する際に各データエンティティの位置を特定するために費やされる時間及び（機械的、演算的及びその他の）負担を削減する。ここで使用する「ファイル」という用語は、あらゆる離散的なデータのエンティティを指し、特定のファイルシステム又はファイルシステム構造の一部であってもよく、そうでなくてもよい。以前のシステムとは異なり、本発明は、実質的に全てのファイルシステムのファイルに適用できる。また、本発明は、ストレージデバイス上のファイルの実際の統計的な使用情報の事前の知識又は解析を必要とすることなく、ファイルのサブセットにも適用できる。
【００３１】
この概念は、データ又はファイルが保存及び／又は処理されるストレージデバイス、ファイルシステム、オペレーティングシステム又は他の関連要素に関する既存の知識又は経験的に導出された情報を用いて、複数のデータ又はファイルを物理的にグループ化及び順序付けする予測可能で改善された方法を判定及び適用することによって、システム性能を向上させる。
【００３２】
例えば、ハードディスクドライブ上に常駐するファイルの場合、ファイル自体に潜在的に含まれている情報のみではなく、例えば、ファイルディレクトリインデクスの順序、オペレーティングシステムの微妙な差異（nuances）、ファイルシステムの特徴等の他の論理的な情報から推定可能な情報も利用して、効率的なファイルグループ化及び順序付けシステムを導出及び適用し、ディスク上で物理的なグループを関連付ける際に、ファイルが論理的に予測可能なグループに属するようにし、そして、これらのグループ及びファイルが全体的なシステム性能を向上させるようグループ及びファイルを構成することが目的である。更に、総合的なデータエントロピを減少させることによって、総合的なファイルアクセス時間が短縮され、生来的にファイル及び空き領域の両方の再断片化の速度を最小化する物理的に組織化された構造が得られる。
【００３３】
組織化のための特定のグループ化技術及び方法は、システム動作の監視及び解析、並びに類似のファイルシステムと共に類似のストレージデバイスを使用する類似のコンピュータ又はオペレーティングシステムの既存の知識又は解析に基づいて経験的に導出される情報によって判定される。不連続データ又は不連続ファイルは、それらが関連付けられると判定される優先度が最高のグループに、一旦、保存される。例えば、マイクロソフトウィンドウズ７（Microsoft Windows 7：商標）オペレーティングシステムによって用いられるハードディスクドライブの場合、本発明の好ましい実施の形態では、以下のようなファイル分類を行う。
【００３４】
１．プリフェッチファイル（最高の優先度）
２．Ｗｉｎ３２／６４システムファイル
３．プログラムデータ及びユーザデータ
４．プログラムファイル
５．ウィンドウズＯＳディレクトリツリー
６．ユーザファイルディレクトリツリー
７．全ての残りのファイル（最低の優先度）
【００３５】
グループメンバシップについての判定技術は、グループ及びストレージコンテキストによって異なるが、例えば、ファイルディレクトリ又はインデクス構造、オペレーティングシステムの機能の知識及びファイルシステム組織化構造等の情報を利用する。
【００３６】
好ましい実施の形態では、各グループ内で、メンバファイルは、ファイルシステムのファイルディレクトリ又はインデクス構造に基づいて、ストレージデバイス上で物理的に組織化される。例えば、入れ子構造又は初期のノードがルート又はトップレベルファイルディレクトリを表し、そこから連続的に多数のフォルダが分岐する階層木構造として、多くのファイルシステムディレクトリインデクスが組織化される。したがって、本発明の好ましい実施の形態では、ストレージデバイスのファイルディレクトリ構造を解析し、最初に何らかの所定の優先度のカテゴリに基づいてストレージデバイス上でファイルを物理的にグループ化し、続いて、ファイルが論理的にストレージデバイスのディレクトリ構造内のどこに位置するかに応じて、これらを組織化及び順序付けする。
【００３７】
本発明の一実施の形態では、優先度が最高のグループが最も速い位置に書き込まれる等、より速いアクセス及び処理速度を示すことが既知である物理的な位置にグループを移動させることによって１つ以上のファイルのグループをストレージデバイス上で優先度付けしてもよい。したがって、本発明の実施の形態では、ストレージデバイス上で実行されると、まず、優先度が最も高いファイルのグループを、これらの速度がより速い位置内の連続するユニットに移動させ、続いて、ストレージデバイス上の（優先度付けされたグループのメンバでない）残りのファイルを、ファイルシステムのディレクトリ構造内のそれらの論理的な順序に基づいて、連続するユニットに物理的に再組織化する。
【００３８】
ストレージデバイス内のデータエントロピを減少させるために、ファイルは、特定のシーケンス内で次に処理される可能性が高いファイルが現在処理中のファイルに近くなる（隣接していなくても、近傍にある）尤度が高くなるように物理的に保存され、この結果、連続的アクセスが可能な限り速やかで効率的になる。一実施の形態では、各グループ内で、ストレージデバイス上の各ディレクトリ内のファイルは、それらが最初に書き込まれた又は「インストールされた」日時順に組織化される。ファイルは、所与のシステムの特定の特徴に応じて異なる方式で順序付けしてもよい。包括的に言えば、一貫性がある順序は、順序がないよりも好ましい。この手法は、通常、より効率的で予測的な連続アクセス順序を生成し、これは、全体的なシステム性能を高速化するのにより効果的である。
【００３９】
本発明の新規なデータ組織化方法では、従来の手法と比べて、空き領域劣化問題を大幅に改善し、改善が失われる速度を低減し、より速い連続処理を実現し、この結果、（以下に限定されるものではないが）空き領域非断片化が実現される。更に、ファイルを階層的にグループ化し、自然に順序付けることでデータエントロピを減少させることによって、空き領域断片化及び新たなファイル断片化が生じにくい組織構造が生成され、この結果、向上された持続的なデータ連続性及び性能がより長い期間に亘って維持される。
【００４０】
これまでに周知の方法では、非断片化は、例えば、デバイスの「前部」に使用可能な空き領域を作成するために最初にストレージデバイスの「後部」にデータを移動させる等、空き領域の空間を作成するためにかなりの処理リソースを費やす必要があった。このようなシステムでは、各非断片化処理の一部として、ファイルを後部に移動させる必要がある。これとは対照的に、本発明では、空き領域を作成するための初期の処理は不要である。具体的には、本発明者らは、既にストレージデバイスに存在する既存の空き領域のユニット（「チャンク（chunks）」）を使用することが有利であり、連続する各動作は、生来的に、空き領域の統合を促進し、したがって、物理的に使用される領域も同様に統合されることを見出した。非断片化処理のこの簡素化によって、有効性を損なうことなく、再配置処理がより高速になる。
【００４１】
他の特徴に対するデータエントロピ改善の程度のバランスをとる代替の再配置アルゴリズムを容易に想到できる。例えば、特定のアプリケーションのためのアルゴリズムを決定する際、再配置処理によって消費される時間及び再配置処理を計画するために消費される時間も全て考慮する必要がある。主要な点は、データエントロピのレベルの評価が判定に含まれるということである。
【００４２】
再配置処理から生じる全体的なシステム性能の改善の程度は、システムの初期状態に依存する。再配置処理を繰り返すと、総合性能を漸進的に改善することができる。以下に説明するように、処理は、データエントロピのしきい値に基づいて繰り返してもよい。
【００４３】
周知の技術とは異なり、本発明では、ストレージデバイスの全体内の全てのデータに対するシステム動作の前に適用でき、この結果、最初に使用する前に最適化されたデータストレージ組織化を実現でき、これは、一定以上の使用の後に収集された経験的データに基づいて、頻繁に使用されるファイルのサブセットだけをキャッシング及び／又は最優先するシステムとは異なるものである。
【００４４】
また、他の技術とは異なり、本発明を用いることによって、関連するデータ、例えば他のファイルやディレクトリ等の既存の論理的で物理的な位置に基づいて、ファイル又は離散的なデータユニットを保存する最適な位置を（それがストレージデバイスに書き込まれる前に）事前に決定することができる。これがどう有利であるかを示す具体例として、プログラムが最初にコンピュータシステムにインストールされる際、プログラムが最初から可能な限り速やか且つ効率的に実行されるようにセットアップされることをソフトウェア製造業者が確実にしたい場合がある。他の具体例として、新たなデータが書き込まれてもストレージデバイスが最大性能を維持するように最適化された状態を保ち、この結果、後の最適化オペレーションの必要性を最小化することをファイル又はオペレーティングシステムの製造業者が望む場合がある。
【００４５】
本発明の好ましい実施の形態の動作を図１のハイレベルのフローチャートに示す。本発明は、プロセッサ上で実行されて、ここに説明する処理ステップを実行するように設計されたソフトウェアで実現される。ステップ１では、ストレージボリュームを解析して、ファイルシステムインデクス構造を判定する。次に、ステップ２において、ファイルシステムインデクス構造に基づいてディレクトリ内のディレクトリ及び関連するファイルを判定する。ステップ３において、ストレージデバイス上の使用可能な空き領域を解析する。オプションとして、何らかの特定のファイルを何らかの特定の位置にロードすることが有益である場合、プログラムは、ステップ４において、これらの特定のファイルを特定の位置に配置する。そして、ステップ５において、残りのファイルを、それらの論理的なファイルシステムインデクスのディレクトリ構造の順序に基づいて、ストレージデバイス上で再組織化し、一連の連続するユニットに書き込む（これによって、処理における空き領域及びファイル断片化も軽減又は回避される）。この結果、（同じ又は連続するディレクトリにあるという意味で）関連するファイルがストレージデバイス上に近接して保存され、更にこの結果、ストレージデバイスが非断片化される。最後に、プログラム又はプログラムオペレータは、データエントロピのレベルの上昇について自動又は手動でストレージデバイスを解析し、システム性能を維持するために上述したステップの全て又は一部を再実行する（ステップ６）。
【００４６】
また、本発明は、先にステップ６に関して説明したように、ファイルシステム及び性能を継続的に監視し、再組織化ルーチンを必要に応じて再実行して、データエントロピを最小化して、性能を維持するバックグランド処理として実行してもよい。
【００４７】
図２は、ストレージデバイス上でデータ及びファイルを移動し、順序付けする１つの手法を示すより詳細なフローチャートである。ステップ２１において、ボリューム空き領域を解析し、使用可能な空き領域「チャンク」（連続の空き領域）を判定する。空き領域チャンクは、優先度がより高いファイルをより高速なチャンクに配置できるように、相対的なアクセス速度で順序付けられる。ステップ２２において、オプションとして、マイクロソフトウィンドウズ（Microsoft Windows：商標）プリフェッチ（Prefetch）ファイル等の最上位の使用可能なグループをディスク上の特別に予約された領域に移動させる。そして、システムは、最も速い使用可能な空き領域チャンクを判定し（ステップ２３）、残りの優先度が最高のグループを最も速い使用可能なチャンクに移動し始める（ステップ２４）。ここで使用するグループ化法は、例えば、マイクロソフトウィンドウズ（Microsoft Windows：商標）オペレーティングシステムに関連して上に列記した７個のグループであってもよい。グループの全体が書き込まれる前にチャンクが一杯になった場合、次に速い使用可能な大きなチャンクを選択し（ステップ２５）、残りのファイルをストレージデバイスに書き込む。保存すべきグループが残っている間（ステップ２６）、この処理を繰り返す（ステップ２９）。全てのグループが移動されると、ステップ２７において、処理が完了する。上述のように、この処理のアプリケーションは、如何なるファイルも予め移動する必要がなく、このため、時間が経過するにつれて、空き領域統合が進むという利点がある。
【００４８】
処理は、オプションとして、断片化のレベル及び／又はデータエントロピレベルを監視して、ある所定のしきい値レベルを超えた場合、処理を再実行してもよい（ステップ２８）。
【００４９】
図３は、アドビシステムズ社（Adobe Systems, Inc.）から市販されているアドビリーダ（Adobe Reader、登録商標）９．０プログラムを保存するストレージデバイスからの部分的なディレクトリ構造の一例を示している。このプログラムが新たな空のストレージデバイスにインストールされる場合、プログラムインストールの全体を構成する各ファイルは、ストレージ媒体上に物理的に共に、線形のシーケンスとして順次的に保存してもよい。一方、プログラムが通常の使用を経たストレージデバイス上にインストールされ、したがって、複数の既存のファイルが様々な物理的な位置に既に保存されている場合、インストールされる新たなファイルも、デバイス全体に亘って、物理的に様々な位置に保存される可能性が高い。
【００５０】
図４は、ストレージデバイス上の連続するフォルダ「Ｃ」及び連続するファイル「ｃ」の相対的位置を示している。ここで、プログラムをメモリにロードし又は使用する際に、ファイルがプログラムインストールの一部として互いに関連し、連続して又は順次的に読み出され、処理される可能性が高い場合であっても、これらは、実際には、ドライブ全体に亘って物理的に断片化されており、これは、有意のレベルのデータエントロピを表している。ストレージデバイスが機械的なハードディスクドライブである場合、データを読み出すヘッドは、全ての関連するファイルを読み取るために何度も移動する必要があり、一方、ファイルが完全に又は部分的に予測可能な順序で物理的に組織化されていれば、同じ動作を実行する際、データを読み出すヘッドの移動は少なくて済む。
【００５１】
本発明を適用したソフトウェアプログラムを実行した後、（アドビリーダ（Adobe Reader）９．０プログラムのデータコンポーネントの全てが論理的に格納されている）「Ａｄｏｂｅ」ディレクトリのファイルは、図５に示すように、ストレージデバイス上の連続的な位置に組織化される。図６は、図４のファイルがどのように移動及び組織化されるかを示しており、ここで、「・」記号は、ストレージデバイス上のファイルの以前の物理的な位置を示している。
【００５２】
したがって、図４〜図６に示すように、本発明は、システム性能を向上させる幾つかの利益を提供する。第１に、本発明は、ストレージデバイス上で、データを、より効率的で予測可能に（より少ないデータエントロピで）物理的に組織化し、これにより、連続するシーケンスでアクセスされる可能性が高いファイルは、ストレージデバイス上で物理的に互いに近くに配置される。第２に、この物理的組織化が実行されると、移動される各データファイルは、効果的に非断片化され、更に、システム性能が向上する（データエントロピが更に下がる）。更に、ストレージデバイス上のデータの物理的組織化がその論理的構造により近付くために、更なる再組織化に必要な時間及び労力がより少なくなる。
【００５３】
他の実施の形態においては、ストレージデバイスのデータ構造内のより変更されやすい位置（volatile locations）、例えば、追加、変更及び削除による変更の速度が他の位置のものより高い位置に焦点を合わせることによって本発明を拡張することができる。これらの変更されやすい位置に焦点を合わせることによって、本発明を適用したプログラムは、これらの領域内に含まれているデータをより頻繁に再組織化でき、この結果、再組織化を実行する都度、効率的な構造に含まれる可能性が低いデータを処理する必要なく、デバイス内のデータを安定的且つ効率的に総合的に組織化することを確実にすることができる。
【００５４】
具体的には、データエントロピのレベル（例えば、ファイル断片化、空き領域断片化、最適な物理的ファイル位置の喪失）は、ストレージデバイスのある領域においてより急速に高まる傾向があることが見出された。これらの特定の位置は、データを保存するために使用されるファイルシステム、デバイスを使用するオペレーティングシステム、オペレーティングシステムを実行するために用いられるコンピュータ装置及び他のコンテキスト的要因によって異なる場合がある。但し、包括的に言えば特定の使用のコンテキストにおいて、データエントロピがより速い速度で上昇するストレージデバイス内の特定の位置がある。
【００５５】
本発明の他の実施の形態を図７のフローチャートに示す。コンピュータシステム及びその関連するデータストレージデバイスの動作を監視する周知の方法を使用することによって、最も共通にアクセスされるデータ（又はファイル）を特定できる。これらの共通にアクセスされるファイルストレージデバイス内の他の情報、例えば、その論理ファイル組織化、内部ファイルコンテンツ、ファイルデータタイプ等を解析することによって一組の関連するファイルを特定してもよい。また、関連するファイルは、生来的な依存関係、単一のファイルディレクトリ内での論理的なグループ化、他の１つ以上の経験的に導出された関連付け要因の何れかによって、共通にアクセスされるファイルの１つが処理されるときにアクセスされる可能性が高いファイルであってもよく、例えば、他のあるファイルがアクセスされると、このタイプのファイルを編集するように設計されたプログラムを起動し、編集のために開かれる可能性が高いファイル等であってもよい。
【００５６】
共通に用いられるファイル及び／又はそれらの関連するファイルの判定（ステップ７１）に基づいて、ステップ７２において、ストレージデバイス上にファイルを保存するための特定の順序を決定する。また、これらのファイルのためのより効率的な順序シーケンスを決定する方法は、ステップ７１における判定のみではなく、ストレージデバイス上の全ての他のファイルについて、効率的及び／又は予測可能なストレージ位置を判定することも含む。ステップ７３では、ストレージデバイスの使用可能な空き領域を解析する。ステップ７４では、幾つかのアイテム、例えば、主要なオペレーティングシステム、アプリケーション又はデータファイルをある特定の物理的な位置に移動させ、組織化する。そして、ステップ７２で判定された順序に基づいて、ステップ７５において、不連続データエンティティを連続的に再配置することによって、効率化のために、ストレージデバイス上の残りの何らかのデータを再組織化してもよい。
【００５７】
上述したように、本発明の１つのアプリケーションは、ステップ７６において、動的にシステムを監視し、ストレージデバイスのコンテンツが物理的に組織化された状態を自発的に維持するようにしてもよい。この処理では、ストレージデバイスの全体を監視してもよく、デバイスが使用されるにつれてデータエントロピのレベルが高まることが既知の又はそのように判定された位置のみを監視してもよい。
【００５８】
図８〜図１４は、ディスク上でファイルを物理的にどのように操作するかをより詳細に示している。図８は、ストレージデバイスが、通常、単一の断片化したファイルをどのように読み出すかを示している。ここでは、単一のファイルが、９個の異なる物理的な位置において、９個の異なる断片として保存されている。このために、このファイルにアクセスするには、非常に時間がかかることは明らかである。図９は、ストレージデバイスが、通常、ファイル非断片化が実行された後に単一の連続域ファイルをどのように読み出すかを示している。この場合、ストレージデバイスは、最初から最後まで、如何なる機械的な位置変更を行うこともなく、簡単に単一ファイルを読み出すことができる。
【００５９】
図１０は、ストレージデバイスが、通常、ファイル断片化はないが、データエントロピがある複数のデータファイルをどのようにして連続的に読み出すかを示している。換言すれば、各ファイルは、断片化されてはいないが、ストレージデバイス上の異なる物理的な位置に配置されている。この具体例では、関連するファイルがストレージデバイスに亘って離散しているという意味で、「データエントロピ」が単一のファイルの断片化と同様に、アクセス遅延を引き起こす。このようなストレージデバイスに本発明を適用すると、図１１に示すように、関連するファイルが近接して配置され、非断片化される。ストレージデバイスは、ファイルを読み出すための機械的な位置変更を必要とすることなく、複数の関連するファイルを読み出すことができる。半導体メモリを用いたストレージデバイス（solid state storage devices）の場合、この技術では、単一のファイルを読み出すために必要な「演算的」負担を軽減する。この技術では、データエントロピ及びファイル断片化を排除又は低減することによって、全体的なシステム性能を大幅に改善する。
【００６０】
図１２は、本発明の実施の形態に基づき、ファイルをストレージデバイス上で組織化し及び優先度付けされたグループ内で順序付けすることによって、データエントロピを最小化し、またファイル及び空き領域の断片化を防ぐ手法を更に詳細に示している。各優先度グループ内で、関連するファイルは、ストレージデバイス上の物理的に連続する位置に幾つかのセットとして保存される。例えば、各セットは、上述のように、関連するファイルのディレクトリに対応することができる。上述したように、優先度グループは、ストレージデバイス上で、アクセス速度の降順の位置に配置される。なお、ファイルシステム固有のメタデータを同様に保存してもよい。
【００６１】
詳細な具体例として、図１３は、本発明の実施の形態に基づき、優先度付けされたグループ内の既存の論理的なインデクスに基づいて、データ及びファイルを組織化及び順位付けする手法を示している。各優先度グループ内で、ディレクトリは、ストレージデバイス上の配置のために配列される。あるディレクトリ内では、幾つかのファイルを優先度付けしなくてもよく（他のファイルは優先度付けしてもよい）、ファイルの論理的なインデクス順序に基づいて、最後に保存できる。
【００６２】
図１４は、本発明の実施の形態に基づき、図１３に示す優先度付けされたグループ内で、既存の論理的なインデクスに基づいて、ストレージデバイス上でデータ及びファイルを物理的に組織化及び順序付けする手法を示している。ここでは、図１３からのファイルが、ストレージデバイス上で並べ替えられ、連続する位置に物理的に配置されている。この結果、優先度グループ内のファイルが連続する位置に配置され、ストレージデバイスが効果的に非断片化され、データエントロピが大幅に低減される。
【００６３】
当業者には明らかであるが、本発明の一部は、本明細書の開示に基づいてプログラミングされた従来の汎用又は専用のデジタルコンピュータ又はマイクロプロセッサを用いて好適に実現することができる。
【００６４】
ソフトウェア技術の技術者には明らかであるが、適切なソフトウェアコードは、本明細書の開示に基づいて、技能を有するプログラマが容易に準備できる。また、本発明は、本明細書に基づいて、特定用途向け集積回路を準備することによって、又は適切な従来の構成回路のネットワークを相互接続することによっても実現できることは、当業者にとって明らかである。
【００６５】
また、本発明は、コンピュータを制御し、本発明の処理の何れかを実行させるために用いることができる、命令が格納されたストレージ媒体（メディア）であるコンピュータプログラム製品を含む。ストレージ媒体は、以下に限定されるものではないが、フロッピーディスク、ミニディスク（mini disk：ＭＤ）、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、ＣＤ又はＤＶＤ  ＲＷ＋／−、マイクロドライブ及びＭＯディスクを含むあらゆる種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＮ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス（フラッシュカード及びメモリスティックを含む）磁気又は光カード、ＳＩＭカード、ＭＥＭＳ、ナノシステム（分子メモリＩＣを含む）、ＲＡＩＤデバイス、遠隔データ記憶装置／アーカイブ／ウェアハウジング、又は命令及び／又はデータの保存に適するあらゆる種類のメディア又はデバイスを含むことができる。
【００６６】
本発明は、コンピュータが読取可能な媒体（メディア）の何れかに保存され、汎用又は専用のコンピュータ又はマイクロプロセッサの両方のハードウェアを制御し、コンピュータ又はマイクロプロセッサが本発明の結果を使用する人間のユーザ又は他のメカニズムとインタラクトすることを可能にするソフトウェアを含む。このようなソフトウェアは、以下に限定されるものではないが、デバイスドライバ、オペレーティングシステム及びユーザアプリケーション含むことができる。また、このようなコンピュータ読取可能な媒体は、上述のように、本発明を実行するソフトウェアを更に含む。
【００６７】
汎用／専用コンピュータ又はマイクロプロセッサのプログラミング（ソフトウェア）に含まれるのは、本発明の開示内容及び本発明の処理に基づく結果の表示、保存又は通信を実現するソフトウェアモジュールである。
【００６８】
本発明の範囲及び精神から逸脱することなく、上述した好ましい実施の形態の様々な適応化及び変更を構成できることは、当業者にとって明らかである。したがって、添付の特許請求の範囲の範囲内で、ここに特別に説明した以外にも本発明を実施できることは明らかである。
【図１】
2014500531.tif 000003
【図２】
2014500531.tif 000004
【図３】
2014500531.tif 000005
【図４】
2014500531.tif 000006
【図５】
2014500531.tif 000007
【図６】
2014500531.tif 000008
【図７】
2014500531.tif 000009
【図８】
2014500531.tif 000010
【図９】
2014500531.tif 000011
【図１０】
2014500531.tif 000012
【図１１】
2014500531.tif 000013
【図１２】
2014500531.tif 000014
【図１３】
2014500531.tif 000015
【図１４】
2014500531.tif 000016
【国際調査報告】
2014500531.tif 000017
2014500531.tif 000018