(57)【要約】      （修正有）【課題】データを格納および取得する効率を向上するための方法およびシステムを提供する。【解決手段】ＮバイトのＩ／Ｏストリームを受信し、ＮバイトをＸバイトのフラグメント化ユニットにフラグメント化する。暗号化ハッシュ関数をＸバイトの各フラグメント化ユニットに適用してハッシュ関数値を形成する。相関ファイルがＹビットの格納されたハッシュ関数値を、複数の格納されたＸバイトのシーケンスの各々と関連付けて保存されており、生成したハッシュ関数値が相関ファイル内に存在する場合、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用する。生成したハッシュ関数値が相関ファイル内に存在しない場合、Ｙビットの生成されたハッシュ関数値をＸバイトのフラグメント化ユニットとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、生成されたハッシュ関数値を使用する。【選択図】図６
2018152126.tif 000002
【特許請求の範囲】
【請求項１】
データを格納するための方法であって、前記方法が、
データのストリームを受信することと、
前記データのストリームをフラグメント化ユニットにフラグメント化することであって、各フラグメント化ユニットに対して、
（ａ）ハッシュ関数を前記フラグメント化ユニットに適用して、前記フラグメント化ユニットと関連付けられているハッシュ関数値を生成し、
（ｂ）前記ハッシュ関数値が、ハッシュ関数値をフラグメント化ユニットと相関させるエントリを含む相関ファイル内にあるかどうかを判断し、
（ｉ）前記フラグメント化ユニットに対する生成されたハッシュ関数値が前記相関ファイル内にある場合には、前記ハッシュ関数値を非キャッシュ記録媒体上に格納し、
（ｉｉ）前記フラグメント化ユニットに対する生成されたハッシュ関数値が前記相関ファイル内にない場合には、前記ハッシュ関数値を前記フラグメント化ユニットと相関させる相関ファイル内にエントリを作成し、前記フラグメント化ユニットを前記非キャッシュ記録媒体上に格納する
ことと、
を備える、方法。
【請求項２】
前記非キャッシュ記録媒体がランダムアクセスメモリを備える、請求項１に記載の方法。
【請求項３】
前記ランダムアクセスメモリに書き込まれるデータのサイズが、前記データのストリームのサイズ未満である、請求項２に記載の方法。
【請求項４】
前記方法が、前記データのストリーム内の冗長データが格納される回数を最小限にする、請求項１に記載の方法。
【請求項５】
前記ハッシュ関数がＭＤ５メッセージダイジェストアルゴリズムを備える、請求項１に記載の方法。
【請求項６】
ビットマーカーテーブルの使用を通して格納のための各ハッシュ関数値を符号化して、格納のための各ハッシュ関数値に対するビットマーカーを生成することをさらに備える、請求項１に記載の方法。
【請求項７】
各ビットマーカーを前記非キャッシュ記録媒体内に格納することをさらに備える、請求項６に記載の方法。
【請求項８】
頻度変換器の使用を通して格納のための各ハッシュ関数値を符号化することをさらに備える、請求項１に記載の方法。
【請求項９】
格納のための各ハッシュ関数値に対して、変換されたビット列が生成され、少なくとも２つの異なる列に対して、出力される変換されたビット列が異なる長さのものである、請求項８に記載の方法。
【請求項１０】
データを格納するためのシステムであって、前記システムが、
ハッシュ関数値をデータのフラグメント化ユニットと相関させるエントリを含む相関ファイルを格納するメモリと、
命令を実行するプロセッサであって、前記命令は、前記プロセッサに、
データのストリームを受信し、
前記データのストリームをフラグメント化ユニットにフラグメント化し、各フラグメント化ユニットに対して、
（ａ）ハッシュ関数を前記フラグメント化ユニットに適用して、前記フラグメント化ユニットと関連付けられているハッシュ関数値を生成し、
（ｂ）前記ハッシュ関数値が前記相関ファイル内にあるかどうかを判断し、
（ｉ）前記フラグメント化ユニットに対する生成されたハッシュ関数値が前記相関ファイル内にある場合には、前記ハッシュ関数値を非キャッシュ記録媒体上に格納し、
（ｉｉ）前記フラグメント化ユニットに対する生成されたハッシュ関数値が前記相関ファイル内にない場合には、前記ハッシュ関数値を前記フラグメント化ユニットと相関させる相関ファイル内にエントリを作成し、前記フラグメント化ユニットを前記非キャッシュ記録媒体上に格納する
ようにさせる、プロセッサと、
を備える、システム。
【請求項１１】
前記非キャッシュ記録媒体がランダムアクセスメモリを備える、請求項１０に記載のシステム。
【請求項１２】
前記メモリがランダムアクセスメモリを備える、請求項１０に記載のシステム。
【請求項１３】
前記ランダムアクセスメモリに書き込まれるデータのサイズが、前記データのストリームのサイズ未満である、請求項１１または１２に記載のシステム。
【請求項１４】
前記システムが、前記データのストリーム内の冗長データが格納される回数を最小限にする、請求項１０に記載のシステム。
【請求項１５】
前記ハッシュ関数がＭＤ５メッセージダイジェストアルゴリズムを備える、請求項１０に記載のシステム。
【請求項１６】
前記システムが、ビットマーカーテーブルの使用を通して格納のための各ハッシュ関数値を符号化して、格納のための各ハッシュ関数値に対するビットマーカーを生成するようにさらに構成されている、請求項１０に記載のシステム。
【請求項１７】
前記システムが、各ビットマーカーを前記非キャッシュ記録媒体内に格納するようにさらに構成されている、請求項１６に記載のシステム。
【請求項１８】
前記システムが、頻度変換器の使用を通して格納のための各ハッシュ関数値を符号化するようにさらに構成されている、請求項１０に記載のシステム。
【請求項１９】
格納のための各ハッシュ関数値に対して、変換されたビット列が生成され、少なくとも２つの異なる列に対して、出力される変換されたビット列が異なる長さのものである、請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶および取得の分野に関する。
【背景技術】
【０００２】
２１世紀は、人々および企業が生成および格納するデジタル化された情報の量において急激な増加を示してきた。この情報は、通常、ディスクなどの磁気面上に格納されている電子データから成り、磁気面は、サイズがサブマイクロメータで、情報の個々のバイナリ断片を格納可能な、小さな領域を含む。
【０００３】
多数のエンティティが生成する大量のデータのために、データ記憶産業は、ネットワークベースの記憶システムに方向転換している。これらのタイプの記憶システムは、１つ以上のエンティティの代わりに、データを格納および取得するように構成されている、処理システムを形成するか、または処理システムの一部である、少なくとも１つのストレージサーバーを含み得る。データは、ブロックおよび／またはファイルなどの、記憶オブジェクトとして格納および取得され得る。
【０００４】
格納のために使用される１つのシステムは、ネットワーク接続ストレージ（ＮＡＳ：Ｎｅｔｗｏｒｋ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ）システムである。ＮＡＳのコンテキストでは、ストレージサーバーは、１つ以上のクライアントの代わりに、データを格納して、データに対するファイルレベルのアクセスを管理するように動作する。ファイルは、磁気もしくは光ディスクまたはテープなどの、大容量記憶装置の１つ以上のアレイを含む、記憶システム内に格納され得る。加えて、このデータ記憶モデルは、独立ディスクの冗長アレイ（ＲＡＩＤ：Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ）技術を採用し得る。
【０００５】
格納のために使用される別のシステムは、ストレージエリアネットワーク（ＳＡＮ）である。ＳＡＮシステムでは、通常、ストレージサーバーは、クライアントに、格納されたデータに対するファイルレベルのアクセスではなく、ブロックレベルのアクセスを提供する。しかし、いくつかのストレージサーバーは、クライアントに、ファイルレベルアクセスおよびブロックレベルアクセスの両方を提供することが可能である。
【０００６】
ＮＡＳを使用するか、ＳＡＮを使用するかに関わらず、データを生成する全ての産業は、そのデータを格納および取得するための費用を考慮する必要がある。それ故、データを経済的に格納および取得するための新しい技術に対する必要性がある。
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明は、データを格納および取得する効率を向上するための方法、システムおよびコンピュータプログラム製品を提供する。本発明の様々な実施形態を使用することにより、任意選択で変換または符号化されているデータを効率的に格納してアクセスすることができる。追加または代替として、本発明の様々な実施形態は、データの効率的な格納およびデータへのアクセスを容易にするメディエータ（ｍｅｄｉａｔｏｒ）を使用する。
【０００８】
本発明の様々な実施形態は、生データおよび／または生データとは別個のメタデータで動作する。その結果として、本発明に関連して格納および／または取得できるファイルのタイプに基づく制限がない。使用され得るファイルタイプの例は、ＪＰＥＧ、ＰＤＦ、ＷＯＲＤ文書、ＭＰＥＧおよびＴＸＴ文書を含み得るが、それらに制限されない。本発明の様々な実施形態を通して、データを変形し得、かつ／または変形もしくは変換されたデータが格納される物理装置を変更し得る。これらの実施形態は、実行される際に、本発明の方法またはプロセスのステップの実行を引き起こす、コンピュータプログラム製品を含むか、またはそれに動作可能に結合されているコンピュータを採用する自動化プロセスを通して実施され得る。これらの方法またはプロセスは、例えば、コンピュータアルゴリズムもしくはスクリプトで具現化されるか、またはそれを含み、任意選択で、本発明のシステムによって実施され得る。
【０００９】
第１の実施形態によれば、本発明は、記録媒体上にデータを格納するための方法を対象とし、（ｉ）複数のデジタル２値信号を受信することであって、デジタル２値信号が複数のチャンクレットに編成されており、各チャンクレットがＮビット長で、Ｎが１より大きい整数であり、チャンクレットが順序を有する、複数のデジタル２値信号を受信すること、（ｉｉ）各チャンクレットを均一なサイズのサブユニットに分割して、Ｘ個のマーカーのセットから、１つのマーカーを各サブユニットに割り当てて、複数のマーカーのセットを形成することであって、Ｘがサブユニット内のビットの異なる組合せの数に等しく、同一のサブユニットが同じマーカーに割り当てられて、少なくとも１つのマーカーがサブユニットのサイズよりも小さい、複数のマーカーのセットを形成すること、および（ｉｉｉ）複数のマーカーのセットを、チャンクレットの順序に対応する順序、またはチャンクレットの順序の再作成を可能にする別の構成のいずれかで、持続性記録媒体上に格納すること：を含む。
【００１０】
第２の実施形態によれば、本発明は、記録媒体からデータを取得するための方法を対象とし、（ｉ）記録媒体にアクセスすることであって、記録媒体が複数のマーカーをある順序で格納する、記録媒体にアクセスすること、（ｉｉ）複数のマーカーをチャンクレットのセットに翻訳することであって、各チャンクレットがＮビット長で、Ｎが１より大きい整数であり、チャンクレットが、複数のマーカーの順序に対応する順序を有し、翻訳がビットマーカーテーブルにアクセスすることによって達成され、ビットマーカーテーブル内で、各一意のマーカーが一意のビット列に対応するとして識別される、複数のマーカーをチャンクレットのセットに翻訳すること、および（ｉｉｉ）チャンクレットのセットを含む出力を生成すること：を含む。マーカーは、チャンクレットの順序と同じ順序で格納されることもあれば、格納されないこともあるが、それらが格納される順序に関わらず、チャンクレットの順序およびそれらが導出された任意のファイルを再作成することができる。
【００１１】
第３の実施形態によれば、本発明は、データを記録媒体上に格納するための方法を対象と、（ｉ）複数のデジタル２値信号を受信することであって、デジタル２値信号がチャンクレットに編成されており、各チャンクレットがＮビット長で、各チャンクレットが第１の端部および第２の端部を有し、Ｎが１より大きい整数であり、チャンクレットが順序を有する、複数のデジタル２値信号を受信すること、（ｉｉ）各チャンクレットを複数のサブユニットに分割することであって、各サブユニットがＡビット長である、各チャンクレットを複数のサブユニットに分割すること、（ｉｉｉ）各サブユニットを分析して、第２の端部におけるビットが値０を有するかを判断し、第２の端部におけるビットが値０を有する場合に、第２の端部におけるビットおよび値０を有して、第２の端部におけるビットとともに連続的なビット列を形成する全てのビットを除去し、それにより第２の端部に０を有する任意のチャンクレットに対して修正されたチャンクレットを形成すること、ならびに、（ｉｖ）持続性記録媒体上に、Ａビット長で、その第２の端部に１を有する、各修正されたサブユニットおよび各サブユニットを、その順序でチャンクレットの再構築を可能にする方法で格納すること：を含む。例えば、修正されたサブユニット（および修正されなかった任意のサブユニット）は、修正される前に、各チャンクレット内のサブユニットの順序に対応する順序で編成され得、データの格納は、元のファイル内の対応するチャンクレットと同じ順序であり得る。
【００１２】
第４の実施形態によれば、本発明は、記録媒体上にデータを格納するための方法を提供し、（ｉ）複数のデジタル２値信号を受信することであって、デジタル２値信号がチャンクレットに編成されており、各チャンクレットがＮビット長で、各チャンクレットが第１の端部および第２の端部を有し、Ｎが１より大きい整数であり、チャンクレットが順序を有する、複数のデジタル２値信号を受信すること、（ｉｉ）各チャンクレットを分析して、第１の端部におけるビットが値０を有するかを判断し、第１の端部におけるビットが値０を有する場合に、第１の端部におけるビットおよび値０を有して、第１の端部におけるビットとともに連続的なビット列を形成する全てのビットを除去し、それにより第１の端部に０を有する任意のチャンクレットに対して第１の修正されたチャンクレットを形成すること、（ｉｉｉ）各チャンクレットを分析して、第２の端部におけるビットが値０を有するかを判断し、第２の端部におけるビットが値０を有する場合に、第２の端部におけるビットおよび値０を有して、第２の端部におけるビットとともに連続的なビット列を形成する全てのビットを除去し、それにより第２の端部に０を有する任意のチャンクレットに対して第２の修正されたチャンクレットを形成すること、（ｉｖ）各チャンクレットに対して、（ａ）第１の修正されたチャンクレットおよび第２の修正されたチャンクレットのサイズが同じである場合、第１の修正されたチャンクレットまたは第２の修正されたチャンクレットを格納すること、（ｂ）第１の修正されたチャンクレットが第２の修正されたチャンクレットよりも小さい場合、第１の修正されたチャンクレットを格納すること、（ｃ）第２の修正されたチャンクレットが第１の修正されたチャンクレットよりも小さい場合、第２の修正されたチャンクレットを格納すること、（ｄ）修正されたチャンクレットがない場合、そのチャンクレットを格納すること、（ｅ）第１の修正されたチャンクレットはないが、第２の修正されたチャンクレットがある場合には、第２の修正されたチャンクレットを格納すること、（ｆ）第２の修正されたチャンクレットはないが、第１の修正されたチャンクレットがある場合には、第１の修正されたチャンクレットを格納することであって、格納される各修正されたチャンクレットが、１つ以上のビットが第１の端部または第２の端部から除去されたかを示す情報とともに格納されること：を含む。１つ以上のビットが第１の端部または第２の端部から除去されたかを示す情報は、例えば、サブユニットの一意性の形であり得る。任意の比較において比較される、第１および第２の修正されたチャンクレットの各々を生成する際に、好ましくは、０が、両方の端部ではなく、いずれかの端部から除去されている。
【００１３】
第５の実施形態によれば、本発明は、記録媒体上にデータを格納するための方法を提供し、（ｉ）複数のデジタル２値信号を受信することであって、デジタル２値信号がチャンクレットに編成されており、各チャンクレットがＮビット長で、各チャンクレットが第１の端部および第２の端部を有し、Ｎが１より大きい整数であり、チャンクレットが順序を有する、複数のデジタル２値信号を受信すること、（ｉｉ）各チャンクレットを複数のサブユニットに分割することであって、各サブユニットがＡビット長である、各チャンクレットを複数のサブユニットに分割すること、（ｉｉｉ）各サブユニットを分析して、第１の端部におけるビットが値０を有するかを判断し、第１の端部におけるビットが値０を有する場合に、第１の端部におけるビットおよび値０を有して、第１の端部におけるビットとともに連続的なビット列を形成する全てのビットを除去し、それにより第１の端部に０を有する任意のサブユニットに対して第１の修正されたサブユニットを形成すること、（ｉｖ）各サブユニットを分析して、第２の端部におけるビットが値０を有するかを判断し、第２の端部におけるビットが値０を有する場合に、第２の端部におけるビットおよび値０を有して、第２の端部におけるビットとともに連続的なビット列を形成する全てのビットを除去し、それにより第２の端部に０を有する任意のサブユニットに対して第２の修正されたサブユニットを形成すること、ならびに、（ｖ）各サブユニットに対して、（ａ）第１の修正されたサブユニットおよび第２の修正されたサブユニットのサイズが同じである場合、第１の修正されたサブユニットまたは第２の修正されたサブユニットを格納すること、（ｂ）第１の修正されたサブユニットが第２の修正されたサブユニットよりも小さい場合、第１の修正されたサブユニットを格納すること、（ｃ）第２の修正されたサブユニットが第１の修正されたサブユニットよりも小さい場合、第２の修正されたサブユニットを格納すること、（ｄ）修正されたサブユニットがない場合、そのサブユニットを格納すること、（ｅ）第１の修正されたサブユニットはないが、第２の修正されたサブユニットがある場合には、第２の修正されたサブユニットを格納すること、（ｆ）第２の修正されたサブユニットはないが、第１の修正されたサブユニットがある場合には、第１の修正されたサブユニットを格納することであって、格納される各修正されたサブユニットが、１つ以上のビットが第１の端部または第２の端部から除去されたかを示す情報とともに格納されること：を含む。１つ以上のビットが第１の端部または第２の端部から除去されたかを示す情報は、例えば、サブユニットの一意性の形であり得る。
【００１４】
第６の実施形態によれば、本発明は、記録媒体からデータを取得するための方法を提供し、（ｉ）記録媒体にアクセスすることであって、記録媒体が複数のデータユニットを複数の位置に格納し、各データユニットが複数のビットを含み、データユニットの最大サイズがＮビットであり、少なくとも１つのデータユニットがＮビットよりも少ないビットを含み、データユニットが順序を有する、記録媒体にアクセスすること、（ｉｉ）データユニットを取得し、１つ以上のビットを、Ｎビット長よりも少ない任意のデータユニットの端部に追加して、データユニットに対応するチャンクレットのセットを生成することであって、各チャンクレットが同じビット数を含む、チャンクレットのセットを生成すること、および（ｉｉｉ）チャンクレットのセットを含む出力を、データユニットの順序に対応する順序で生成すること：を含む。
【００１５】
第７の実施形態によれば、本発明は、電子データを格納するための方法を対象とし、前記方法は、（ｉ）パラメータのセットを受信することであって、パラメータがファイルシステム情報、ブート可能性情報、およびパーティション情報の１つ以上を含む、パラメータのセットを受信すること、（ｉｉ）メタデータを受信すること、（ｉｉｉ）１つ以上のファイルを受信することであって、各ファイルがファイル名を有する、１つ以上のファイルを受信すること、（ｉｖ）パラメータおよびメタデータをメディエータ上に格納すること、（ｖ）ファイルの各々をある位置において非キャッシュ媒体上に格納すること、ならびに（ｖｉ）メディエータ上に、各ファイル名と非キャッシュ媒体上の位置との相関関係を格納すること：を含む。本発明のメディエータは、次の目的：（１）データを符号化するためのプロトコルを格納すること、（２）記録媒体上に物理空間を割り当てること、（３）ホストイニシエータのディスクジオメトリに対する中心点として機能すること、（４）セキュリティを追加すること、（５）システム内部装置が、ログをとること、読み取ること、および１つまたは２つの予約（Ｒ１およびＲ２）とやりとりすることを可能にすること、（６）スナップショットをとる（すなわち、特定の時間において格納されたデータを凍結する）ため、および／またはディスクを複製するための新しい方法に対する枠組みを提供すること、ならびに（７）メタデータを提供すること：の１つ以上を果たし得る。全部ではないにしろ、これらの特徴の１つ以上を実現すると、データの格納、データの権限のないアクセスからの保護、および／またはデータの取得のための方法の効率性に寄与できる。
【００１６】
第８の実施形態によれば、本発明は、データをバックアップするための方法を対象とし、前記方法は、（ｉ）第１のメディエータ上で、複数のファイル名を複数のデータファイルの位置と相互に関連付けることであって、データファイルの位置が第１の非キャッシュ媒体上の位置に対応し、第１のメディエータが、特定のファイル名を識別するユーザーが、その特定のファイル名に対応するデータファイルを取得するのを可能にする、複数のファイル名を複数のデータファイルの位置と相互に関連付けること、（ｉｉ）複数のデータファイルを第２の非キャッシュ媒体にコピーすること、（ｉｉｉ）第２のメディエータを生成することであって、第２のメディエータが時間Ｔ１における第１のメディエータのコピーであり、第２のメディエータ内で、第２の非キャッシュ媒体上の複数のデータファイルの位置がファイル名と相互に関連付けられている、第２のメディエータを生成すること、（ｉｖ）データファイルに対する修正を保存するための命令を受信すること、および（ｖ）Ｔ１の後である、時間Ｔ２において、第１の非キャッシュ媒体上で、データファイルに対する修正を保存すること：を含む。好ましくは、修正は、第２の非キャッシュ媒体上の対応するデータファイル内に保存されない。
【００１７】
第９の実施形態によれば、本発明は、データ格納および取得システムを提供し、（ｉ）非キャッシュデータ記憶媒体、（ｉｉ）メディエータであって、メディエータが非キャッシュデータ記憶媒体からリモートに保存され、メディエータが：（ａ）トラックの第１のセット、（ｂ）トラックの第２のセット、（ｃ）トラックの第３のセット、および（ｄ）トラックの第４のセット、を含む、メディエータ、ならびに（ｉｉ）マネージャであって、マネージャが：（ａ）ファイルシステム情報、ブート可能性情報、およびパーティション情報の１つ以上を含むデータをトラックの第１のセット内に格納すること、（ｂ）メタデータをトラックの第３のセット内に格納すること、（ｃ）１つ以上のファイルを非キャッシュ媒体上に格納することであって、１つ以上のファイルが非キャッシュ媒体上に、ファイルシステム情報、ブート可能性情報、およびパーティション情報のいずれもなしで保存される、１つ以上のファイルを非キャッシュ媒体上に格納すること、（ｄ）トラックの第４のセット内に、非キャッシュ媒体内の各ファイルの位置を格納すること、ならびに（ｅ）非キャッシュ媒体内の各ファイルの位置の、ファイルに対するホスト名との相関関係を格納すること、を行うように構成されている、マネージャ：を含む。従って、マネージャは、マネージャ自身上に格納されない可能性がある、情報をメディエータ上に格納させ得る。
【００１８】
第１０の実施形態によれば、本発明は、データを非キャッシュ記録媒体上に格納するための方法を対象とし、（ｉ）ＮバイトのＩ／Ｏストリームを（例えば、Ｉ／Ｏプロトコルを使用して）受信すること、（ｉｉ）Ｎバイトを、Ｘバイトのフラグメント化ユニットにフラグメント化すること、（ｉｉｉ）（値アルゴリズムである）暗号化ハッシュ関数をＸバイトの各フラグメント化ユニットに適用して、Ｘバイトの各フラグメント化ユニットに対して生成されたハッシュ関数値を形成すること、（ｉｖ）相関ファイルにアクセスすることであって、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＸバイトのシーケンスの各々と関連付けて、（ａ）Ｘバイトのフラグメント化ユニットに対して生成されたハッシュ関数値が相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）Ｘバイトのフラグメント化ユニットに対して生成されたハッシュ関数値が相関ファイル内にない場合は、Ｙビットの生成されたハッシュ関数値をＸバイトのフラグメント化ユニットとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、生成されたハッシュ関数値を使用する、相関ファイルにアクセスすること：を含む。
【００１９】
第１１の実施形態によれば、本発明は、データを非キャッシュ記録媒体上に格納するための方法を対象とし、（ｉ）ＮバイトのＩ／Ｏストリームを受信すること、（ｉｉ）Ｎバイトを、Ｘバイトのフラグメント化ユニットにフラグメント化すること、（ｉｉｉ）暗号化ハッシュ関数値をＸバイトの各フラグメント化ユニットと関連付けることであって、前記関連付けることが、相関ファイルにアクセスすることを含み、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＸバイトのシーケンスの各々と関連付けて、（ａ）Ｘバイトのフラグメント化ユニットのシーケンスが相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）Ｘバイトのフラグメント化ユニットのシーケンスが相関ファイル内にない場合は、Ｙビットの新しく生成されたハッシュ関数値をＸバイトのフラグメント化ユニットとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、Ｙビットの新しく生成されたハッシュ関数値を使用する、暗号化ハッシュ関数値をＸバイトの各フラグメント化ユニットと関連付けること：を含む。
【００２０】
第１２の実施形態によれば、本発明は、データを非キャッシュ記録媒体上に格納するための方法を対象とし、（ｉ）ＮバイトのＩ／Ｏストリームを受信すること、（ｉｉ）暗号化ハッシュ関数をＮバイトの各ユニットに適用して、Ｎバイトの各ユニットに対して生成されたハッシュ関数値を形成すること、（ｉｉｉ）相関ファイルにアクセスすることであって、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＮバイトのシーケンスの各々と関連付けて、（ａ）Ｎバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）Ｎバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にない場合は、Ｙビットの生成されたハッシュ関数値をＮバイトのユニットとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、生成されたハッシュ関数値を使用する、相関ファイルにアクセスすること：を含む。
【００２１】
本発明の様々な方法が、例えば、電子データを格納するように記憶システムを構成するための次の方法に関連して使用され得る：（ｉ）パラメータのセットを受信することであって、パラメータが，ファイルシステム情報、ブート可能性情報、およびパーティション情報のうちの、全部ではないにしろ、１つ以上を含む、パラメータのセットを受信すること、（ｉｉ）メタデータを受信すること、ならびに（ｉｉｉ）パラメータおよびメタデータをメディエータ上に格納すること。記憶システムの構成後、システムは、各ファイルがファイル名を有する、１つ以上のファイルを受信し；ファイルの各々を（任意選択で、翻訳するための前述の方法の１つを通して処理されたとおり）非キャッシュ媒体上のある位置に格納して；メディエータ上に、各ファイル名と、非キャッシュ媒体上の位置との相関関係を格納する準備ができている可能性がある。
【００２２】
本発明のある方法を採用する際に、命令が、持続性コンピュータ可読記憶媒体上で符号化されて、データ処理装置に、（ａ）サーバーから、ＮバイトのＩ／ＯストリームをＩ／Ｏプロトコルを通して受信すること、（ｂ）Ｎバイトの各ユニットに対して、または複数のＮバイトのフラグメント化ユニットに対して、ハッシュ関数値を取得すること、および（ｃ）複数のハッシュ値または複数の変換されたハッシュ値のいずれかを含む、データを格納させること：を含む動作を実行させるように動作可能な、コンピュータプログラム製品上に格納され得る。ハッシュ値を変換されたハッシュ値に変換することにより、格納されたファイル内の情報への権限のないアクセスに対する保護が高められ得る。任意選択で、コンピュータプログラム製品は、Ｎバイトの異なるユニットまたはＮバイトの異なるフラグメント化ユニットに割り当てられている同じハッシュ関数値の識別を可能にして、矛盾するハッシュ関数値の各々に対応する、異なるデータを格納させる、矛盾解決モジュールをさらに含む。コンピュータプログラム製品は、実行される際に、前述した特徴の開始および自動実行を引き起こすことができる。これらの命令は、１つのモジュール内、または動作可能に互いに結合されている、複数の別個のモジュール内に格納され得る。
【００２３】
加えて、本発明の様々な実施形態は、システム上でも実装され得る。本発明のシステムの一例は、（ａ）（永続的または持続性記憶装置であり得る）非キャッシュ記憶媒体、および（ｂ）非キャッシュ記憶媒体とやりとりするように動作可能な１つ以上のプロセッサ：を含む。任意選択で、システムは、ユーザーが１つ以上のプロセッサとやりとりするのを可能にできる１つ以上のユーザーインタフェース（例えば、グラフィックユーザーインタフェース）をさらに含む。１つ以上のプロセッサは、本発明の方法の１つ以上を実施するようにさらに動作可能であり、それらは、例えば、持続性媒体内に格納されるコンピュータプログラム製品上に格納され得る。
【００２４】
いくつかの実施形態では、システムは、（ｉ）メディエータであって、非キャッシュデータ記憶媒体からリモートに保存され、メディエータが：（ａ）トラックの第１のセット、（ｂ）トラックの第２のセット、（ｃ）トラックの第３のセット、および（ｄ）トラックの第４のセット、を含む、メディエータ、（ｉｉ）非キャッシュ媒体、ならびに（ｉｉｉ）マネージャであって、マネージャが：（ａ）ファイルシステム情報、ブート可能性情報、およびパーティション情報の１つ以上を含むデータをトラックの第１のセット内に格納させること、（ｂ）メタデータをトラックの第３のセット内に格納させること、（ｃ）１つ以上のファイルを非キャッシュ媒体上に格納させることであって、１つ以上のファイルが非キャッシュ媒体上に、ファイルシステム情報、ブート可能性情報、およびパーティション情報のいずれもなしで保存される、１つ以上のファイルを非キャッシュ媒体上に格納させること、（ｄ）トラックの第４のセット内に、非キャッシュ媒体内の各ファイルの位置を格納させること、ならびに（ｅ）非キャッシュ媒体内の各ファイルの位置の、ファイルに対するホスト名および／またはアドレス（複数可）との相関関係を格納させること、を行うように構成されている、マネージャ： を含む。
【発明の効果】
【００２５】
本発明の様々な実施形態を通して、データの格納および取得の効率が向上できる。効率の向上は、一般に使用される方法で使用されるよりも少ない記憶空間を使用し、情報を格納する活動において、より少ない時間および努力を投資することにより、実現され得る。いくつかの実施形態では、データファイルの権限のない取得に対する保護も改善できる。これらの利益は、データを、リモートまたはローカルのいずれかで格納する際に実現され得、本発明の様々な実施形態は、ＲＡＩＤ技術と併せて、またはＲＡＩＤ技術とは無関係に使用され得る。
【図面の簡単な説明】
【００２６】
【図１】本発明のシステムの概要の表現である。
【図２】メディエータおよび非キャッシュ媒体（ＮＣＭ：ｎｏｎ−ｃａｃｈｅ−ｍｅｄｉｕｍ）の表現である。
【図３】メディエータを使用して、情報を格納するためのシステムの表現である。
【図４】格納されている情報をバックアップするために２つのメディエータを使用するためのシステムの表現である。
【図５】二分木の表現である。
【図６】本発明の方法を表す流れ図である。
【発明を実施するための形態】
【００２７】
ここで、本発明の様々な実施形態に対する参照を詳細に行うが、その例が付随する図に示されている。以下の詳細な記述では、多数の具体的詳細が、本発明の完全な理解を提供するために記載されている。しかし、別段の指示がないか、またはコンテキストから暗黙的でない限り、詳細は例であることを意図し、本発明の範囲をいかなる方法でも制限すると見なされるべきでない。さらに、見出しは、本発明の実施形態のいずれかの範囲を制限すること、または、任意の特徴を特定の見出し内の節に制限することを意図するのではなく、読者の便宜のために使用される。
【００２８】
定義
【００２９】
別段の指示がないか、またはコンテキストから暗黙的でない限り、次の用語および句は、以下に規定する意味を有する。
【００３０】
用語「ビット」は、二進数字を指す。それは、０または１のいずれかによって表すことができる、２つの値の１つを有することができる。
【００３１】
用語「ブロック」は、所定の長さを有するデータのバイトまたはビットのシーケンスを指す。
【００３２】
句「ブート可能性コード」、「ブート可能性情報」および「ブート可能性特徴」は、ブート可能状態に入るための手段を提供する情報を指し、ブートセクター上に格納され得る。ブートセクターは、ファームウェアによってＲＡＭ（ランダムアクセスメモリ）内にロードされるように構成されている機械コードを含み得、それは、その結果として、ブートプロセスがプログラムを記憶装置から、または記憶装置にロードするのを可能にする。例として、マスターブートレコードが、アクティブなパーティションを見つけて、ボリュームブートレコードを呼び出すコードを含み得、ボリュームブートレコードは、オペレーティングシステムまたは他のスタンドアロンプログラムをロードして呼び出すためのコードを含み得る。
【００３３】
用語「バイト」は、８ビットのシーケンスを指す。
【００３４】
用語「キャッシュ」は、データに対する将来の要求がより迅速に対応されるため、またはバッファリングを目的として、データが一時的に格納される位置を指す。Ｌ１キャッシュ（レベル１キャッシュ）は、例えば、プロセッサコアと統合されている、スタティックメモリを指す。Ｌ１キャッシュは、ＣＰＵ（汎用処理装置）が同じデータを複数回アセスする場合にデータアクセス速度を向上するために使用され得る。Ｌ２キャッシュ（レベル２キャッシュ）は、通常、Ｌ１キャッシュよりも大きく、データファイルが検索されたが、Ｌ１内で見つからなかった場合に、検索は、外部メモリを目指す前に、Ｌ２キャッシュで行われ得る。いくつかの実施形態では、Ｌ１キャッシュは、中央処理装置内ではない。代わりに、それは、ＤＤＲ、ＤＩＭＭまたはＤＲＡＭ内に置かれ得る。追加または代替として、Ｌ２キャッシュは、ＰＣＩ２．０／３．０の一部であり得、それは、マザーボードに入る。従って、Ｌ１キャッシュおよびＬ２キャッシュの各々は、マザーボードの別々の部分にあり得る。サイズに関して、本発明のいくつかの実施形態では、Ｌ１キャッシュは、２ギガバイトと１２８テラバイトの間、または２ギガバイトと４テラバイトの間であり、Ｌ２キャッシュは、１６ギガバイトと１ペタバイトの間、または１６ギガバイトと３．２テラバイトの間である。いくつかの実施形態では、本発明の方法が実装される際に、ビットマーカーテーブル、頻度変換器（ｆｒｅｑｕｅｎｃｙ  ｃｏｎｖｅｒｔｅｒ）またはハッシュ値テーブルの１つ以上が、Ｌ２キャッシュ内に常駐する。
【００３５】
用語「チャンクレット」は、セクタークラスタに対応し得るビットのセットを指す。チャンクレットのサイズは、記憶システムによって決定され得、チャンクレットサイズを有し得る。慣例的に、チャンクレットサイズは、ＣＨＳ方式によって導出されたが、ＣＨＳ方式は、シリンダー、ヘッドおよびセクターを、ハードディスク上にそれらが出現したところで定義するタプルによってブロックをアドレス指定した。ごく最近では、チャンクレットサイズは、論理ブロックアドレス（ｌｏｇｉｃａｌ  ｂｌｏｃｋ  ａｄｄｒｅｓｓｉｎｇ）を指す、ＬＢＡ測定から導出されており、コンピュータ記憶装置上に格納されるデータのブロックの位置を指定するための別の手段である。例として、チャンクレットサイズは、５１２Ｂ、１Ｋ、２Ｋ、４Ｋ、８Ｋ、１６Ｋ、３２Ｋ、６４Ｋまたは１ＭＢであり得る。当業者として、１Ｋ＝１０２４Ｂが分かっている。チャンクレットは、生データとしてホストから受信され得る。
【００３６】
「ファイル」は、長さを有する関連したバイトまたはビットの集合である。ファイルは、チャンクレットよりも小さいか、チャンクレットと同じサイズか、またはチャンクレットよりも大きい可能性がある。
【００３７】
句「ファイル名」は、コンピュータが特定のファイルを識別して、そのファイルを他のファイルから区別できるようにする表記法またはコードを指す。
【００３８】
句「ファイルシステム」は、ファイルのセットを格納、取得、および更新するために使用される抽象化を指す。従って、ファイルシステムは、ファイルのデータおよびメタデータへのアクセス、ならびにデータを含む記憶装置上の利用可能な空間を管理するために使用されるツールである。いくつかのファイルシステムは、例えば、サーバー上に常駐し得る。ファイルシステムの例は、Ｕｎｉｘ（登録商標）ファイルシステムおよびその関連したディレクトリテーブルおよびｉノード、Ｗｉｎｄｏｗｓ（登録商標）  ＦＡＴ１６およびＦＡＴ３２ファイルシステム（ＦＡＴは、ファイルアロケーションテーブルを指す）、マスターファイルテーブルに基づく、Ｗｉｎｄｏｗｓ（登録商標）  ＮＴＦＳ、ならびに、ＨＦＳまたはＨＦＳプラスを使用する、Ａｐｐｌｅ  Ｍａｃ  ＯＳＸを含むが、それらに制限されない。
【００３９】
句「ハッシュ関数」、「暗号化ハッシュ関数値アルゴリズム」、および「ハッシュ関数値アルゴリズム」は、大きなデータセット（任意選択で可変長の）を、特定のハッシュ関数に対して固定長を有する、より小さいデータセットにマッピングする、アルゴリズムまたはサブルーチンを指す。「ハッシュ関数値」は、ハッシュ関数アルゴリズムの適用後に返される出力を指す。アルゴリズムが返す値は、ハッシュ値、ハッシュコード、ハッシュ合計、チェックサムまたはハッシュとも呼ばれ得る。例えば、ＭＤ５を使用する場合、出力は１２８ビットであり、他方、ＳＨＡ−１を使用する場合、出力は１６０ビットである。
【００４０】
用語「ホスト」および「イニシエータ」は、区別しないで使用され得、データを格納のために、本発明のデータ記憶および取得仲介システムに送信するエンティティまたはシステムを指す。ホストは、１つ以上のタイプの文書またはファイルに対応するデータおよび受信したデータを送信し得る。好ましくは、任意の入力／出力（Ｉ／Ｏ）ストリーム内で、データは、単一の文書タイプのファイルに対応する。便宜上、句「Ｉ／Ｏストリーム」は、データが１つのエンティティから別のエンティティに伝送されることを指すために使用される。第１のエンティティに対して出力されるものは、第２のエンティティに対する入力であり得る。
【００４１】
略語「ＬＢＡ」は、論理ブロックアドレス（ｌｏｇｉｃａｌ  ｂｌｏｃｋ  ａｄｄｒｅｓｓｉｎｇ）を指す。ＬＢＡは、リニアアドレス指定方式であり、ある記憶媒体、例えば、ハードディスク、内に格納されるデータブロックの位置を指定するために使用されるシステムである。ＬＢＡ方式では、ブロックは、整数によって見つけられ、１つだけの番号がデータをアドレス指定するために使用される。通常、第１のブロックはブロック０である。
【００４２】
略語「ＬＵＮ」は、論理ユニット番号（ｌｏｇｉｃａｌ  ｕｎｉｔ  ｎｕｍｂｅｒ）を指し、論理ユニットを識別するために使用される。ＬＵＮは、通常、ＳＡＮを介して共有されるブロックストレージアレイを管理するために使用される。
【００４３】
用語「マネージャ」は、コンピュータプログラム製品、例えば、持続性媒体内に格納され得、かつ１つ以上の他の動作（例えば、データの受信、送信、格納、および処理）をとらせるコードを指す。マネージャは、ハードウェア、ソフトウェアまたはそれらの組合せ上に格納され得る。いくつかの実施形態では、マネージャは、マネージャがその意図する機能を実施するのを可能にするように構成されている、コンピュータおよび／またはシステムの一部であり得る。
【００４４】
用語「メディエータ」は、ハードウェア、ソフトウェアまたはそれらの組合せ上に格納され得、かつ少なくとも１つの非キャッシュ媒体内の記憶空間の１つ以上のユニットをファイル名と相互に関連付ける、コンピュータプログラム製品を指す。メディエータは、それがポイントする非キャッシュ媒体よりも数桁小さい可能性がある。例えば、メディエータは、おおよそ、通常のシリンダーのサイズの約０．２％の大きさしかない可能性がある。いくつかの実施形態では、メディエータは、コンピューティングクラウド内に存在し得、一方、他の実施形態では、メディエータは、持続性有形的記録媒体内に存在する。メディエータは、データが実際には、記録媒体の異なるトラック内に出現している間に、ホストが、記録媒体のあるトラック内にあると認識する位置内のデータの、編成、変換、翻訳および格納の制御を行うことが可能であり得るか、または、全てではないにしろ、これらの機能の１つ以上に対応するマネージャに動作可能に結合され得る。さらに、メディエータは、セクターマップ、テーブル、または物理装置もしくは構造内に配置され得るデータの他の編成を含み得、従って、メディエータの内容は、物理装置もしくは構造にあるジオメトリを持たせ得る。いくつかの実施形態では、メディエータは、Ｌ２キャッシュ上に永続的に常駐する。他の実施形態では、メディエータは、ソリッドステートドライブ上に常駐する。
【００４５】
用語「メタデータ」は、データのコンテナに関する管理情報を指す。メタデータの例は、読み取られているファイルの長さまたはバイトカウント；ファイルが修正された最後の時間に関する情報；ファイルタイプおよびアクセス許可を記述する情報；ならびにＬＵＮ  ＱｏＳ、ＶＭおよびＷＯＲＭを含むが、それらに制限されない。他のタイプのメタデータは、オペレーティングシステム情報、自動初期化情報、グループ許可、および文書タイプ内のビットの頻度を含む。いくつかの実施形態では、格納されたメタデータは、例えば、イニシエータが格納しようとする文書の数およびサイズが縮小または増大するにつれて、イニシエータに対して記憶空間の効率的な収縮または拡張を可能にするために使用され得る。
【００４６】
略語「ＮＡＳ」は、ネットワークエリアストレージ（ｎｅｔｗｏｒｋ  ａｒｅａ  ｓｔｏｒａｇｅ）を指す。ＮＡＳシステムでは、ディスクアレイは、ローカルエリアネットワークトランスポートにアクセスできるコントローラに接続され得る。
【００４７】
句「動作可能に結合された」は、システム、装置、および／またはモジュールが、互いにまたは相互に通信するように構成されて、通信時または通信した後に、それらの意図する目的を実施することが可能である。
【００４８】
句「オペレーティングシステム」は、コンピュータハードウェア資源を管理するソフトウェアを指す。オペレーティングシステムの例は、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘ（登録商標）、およびＭａｃ  ＯＳ  Ｘを含むが、それらに制限されない。
【００４９】
用語「パーティション」は、記憶媒体、例えば、ディスクドライブをユニットに分割するフォーマットを指す。従って、パーティションは、ディスクパーティションとも呼ばれ得る。パーティションの例は、ＧＵＩＤパーティションテーブルおよびＡｐｐｌｅパーティションマップを含むが、それらに制限されない。
【００５０】
略語「ＲＡＩＤ」は、独立ディスクの冗長アレイ（ｒｅｄｕｎｄａｎｔ  ａｒｒａｙ  ｏｆ  ｉｎｄｅｐｅｎｄｅｎｔ  ｄｉｓｋｓ）を指す。関連したサーバーに対して、ディスクのこのグループは、単一ボリュームのように見え得る。ＲＡＩＤ技術は、データの単一ストリップを複数のディスクからプルすることにより性能を向上させて、（１）データのミラーリング、（２）データのストライプ化、または（３）データのミラーリングとストライプ化の組合せ：などの１つまたは複数のプレミスタイプ上に構築される。
【００５１】
句「記録媒体」は、ビットに対応する磁気信号をその中に格納できる、持続性有形的コンピュータ可読記憶媒体を指す。例として、記録媒体は、ハードディスクおよびソリッドステートドライブなどの非キャッシュ媒体を含むが、それらに制限されない。当業者であれば分かっているように、ソリッドステートドライブもキャッシュを有し、スピンする必要がない。持続性有形的コンピュータ可読記憶媒体の例は、ハードドライブ、ハードディスク、フロッピィディスク、コンピュータテープ、ＲＯＭ、ＥＥＰＲＯＭ、不揮発性ＲＡＭ、ＣＤ−ＲＯＭおよびパンチカードを含むが、それらに制限されない。
【００５２】
略語「ＳＡＮ」は、ストレージエリアネットワーク（ｓｔｏｒａｇｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を指す。このタイプのネットワークは、コンピューティング装置を、ディスク、テープアレイおよび他の記録媒体にリンクするために使用できる。データは、例えば、ブロックの形でＳＡＮを介して伝送され得る。
【００５３】
略語「ＳＡＰ」は、システムアシストプロセッサ（ｓｙｓｔｅｍ  ａｓｓｉｓｔ  ｐｒｏｃｅｓｓｏｒ）を指し、それは、オペレーティングシステムによって使用されるＩ／Ｏ（入力／出力）エンジンである。
【００５４】
略語「ＳＣＳＩ」は、小規模コンピュータシステムインタフェース（ｓｍａｌｌ  ｃｏｍｐｕｔｅｒ  ｓｙｓｔｅｍｓ  ｉｎｔｅｒｆａｃｅ）を指す。
【００５５】
用語「セクター」は、ディスク、例えば、磁気ディスク上のトラックの下位区分を指す。各セクターは、一定量のデータを格納する。ディスクに対する一般的なセクターサイズは、５１２バイト（５１２Ｂ）、２０４８バイト（２０４８Ｂ）、および４０９６バイト（４Ｋ）である。チャンクレットが４Ｋのサイズであり、各セクターが５１２Ｂのサイズである場合、各チャンクレットは８セクターに相当する（４＊１０２４／５１２＝８）。セクターは、トラックを有し、プラッター上に配置される。一般に、２つまたは４つのプラッターが１つのシリンダーを構成し、２５５のシリンダーがハードディスクおよび媒体装置を構成する。
【００５６】
句「セクターマップ」は、ホストから要求を受信して、ファイルが格納されている記憶装置内の位置を相互に関連付けるツールを指す。セクターマップは、例えば、ＳＣＳＩプロトコルによって定義されるパラメータ下で動作し得る。本発明のいくつかの実施形態では、セクターマップは、メディエータのビットフィールド内に配置され得る。
【００５７】
用語「トラック」は、全てのセクターをトラバースするディスク内の円形の単位を指す。「トラックセクター」は、任意の１つのセクター内のトラックである。「トラッククラスタ」は、２つ以上のセクターに及ぶ。
【００５８】
好ましい実施形態
【００５９】
本発明は、データを非キャッシュ記録媒体上に格納するための方法、これらの方法を実施するためのコンピュータプログラム製品、およびこれらの方法を実施するように構成されているシステムを提供する。本発明の様々な実施形態を通して、データを効率的に格納および取得することができる。
【００６０】
ビットマーカー
【００６１】
一実施形態によれば、本発明は、ビットマーカーを、生データ内のビット列の表現として使用する、記録媒体上にデータを格納するための方法を対象とする。従って、生データは、生データを表す一連のマーカーに翻訳され、本方法は、格納のために、信号のセット（ビットマーカーと呼ばれ得る）に変換されるデータを含む、ファイルまたはストリームを受信することおよびそれらの信号を格納することを提供する。
【００６２】
ファイルは、ホストと呼ばれる人またはエンティティから受信され得る。好ましくは、ホストは、信号を生データの形で送信する。例えば、ホストは、ＪＰＥＧ、ＰＤＦ、ＴＩＦＦまたはＷＯＲＤ文書などの、１つ以上のファイルを個々に、または全体として形成する１つ以上のチャンクレットを送信し得る。本発明の様々な実施形態は、チャンクレットを受信するか、チャンクレットのサブユニットを受信するか、またはチャンクレットに変換される１つ以上のファイルを受信すると、開始する。好ましくは、受信されるチャンクレットまたはチャンクレットのサブユニットは、全て均一なサイズである。任意選択で、本方法は、サイズの均一性を検証し、非均一性が検出される、例えば、１つ以上のチャンクレットが少なすぎるビットしか有していない場合、本方法は、全てのチャンクレットが均一のサイズになるまで、ゼロを追加させる。
【００６３】
一例として、データは、Ｎビット長のチャンクレットで受信され得、Ｎは１よりも大きい整数である。例えば、Ｎは、１２８バイトから１６Ｋまで、例えば、４Ｋであり得、それは、４０９６Ｂに相当する。
【００６４】
チャンクレットは順番に受信される。例えば、ファイルが、システムによって連続的に受信される１０のチャンクレットを含み得る。あるいは、所与のファイルに対する複数のチャンクレットが、それらが、ホストのオペレーティングシステムによるファイルの再作成および使用を可能にするような方法で、それらの相互の再関連付けを可能にする情報を含む場合、並行して、または一緒に伝送され得る。従って、いくつかの実施形態では、本発明の方法は、マーカーを、チャンクレットが受信されるのと同じ順序で格納する。それに応じて、ホストがファイルの取得を要求する場合、対応する取得手段が、符号化されたデータを同じ順序で呼び戻して、それを適切な順序でチャンクレットに復号するであろう。
【００６５】
任意選択で、符号化の前に、システムは、チャンクレットをビットのグループ（サブユニットとも呼ばれる）に分割し得、その各々はＡビット長である。システムがチャンクレットをサブユニットに分割する場合、サブユニットがビットマーカーテーブルと比較され得る。システムがチャンクレットをサブユニットに分割しない場合、各チャンクレットがビットマーカーテーブルと比較され得る。
【００６６】
ビットマーカーテーブルは、ビットの一意のセットを一意のマーカーと相互に関連付ける。いくつかの実施形態では、ビットマーカーテーブルは、サブユニットが使用される場合にはサイズＡ、またはサブユニットが使用されない場合にはサイズＮの、各一意のビット列に対するマーカーを含む。それ故、この方法では、コンピュータプログラムは、チャンクレットのセットを入力として受信し得る。それは、次いで、各チャンクレットを、同じサイズで、各々Ａビット長のＹ個のサブユニットに分割し得、Ａ／８は整数である。各一意のＡに対して、テーブル内に１つのマーカーがあり得る。
【００６７】
このように、自動化プロトコルを通して、チャンクレットの受信後、コンピュータプログラム製品は、ビットマーカーテーブルをアクセスさせる。それに応じて、各チャンクレットまたはサブユニットは、入力として機能し得、各ビットマーカーは、出力として機能し得、それによりマーカーの出力セットを形成する。マーカーの出力セットは、翻訳されたか、コード化されたか、または符号化されたデータと呼ばれ得る。各チャンクレットが細分されない実施形態では、各チャンクレットは１つのマーカーを受信するであろう。チャンクレットが２つのサブユニットに分割される場合、それは、２つのマーカーに翻訳されるか、または符号化されるであろう。従って、コンピュータプログラム製品は、マーカーを入力と相互に関連付けるビットマーカーテーブルを使用して、各チャンクレットに対応する少なくとも１つのマーカーを割り当てる。コンピュータプログラム製品は、各個々のマーカーに対応する異なる出力が生成されるように、各チャンクレットに対応するマーカーのセットを含む異なる出力が生成されるように、または、完全なファイルに対応するマーカーのセットを含む異なる出力が生成されるように、設計され得る。
【００６８】
ビットマーカーテーブルは、Ｘ個のマーカーを含む。いくつかの実施形態では、Ｘは、本方法がチャンクレットをサブユニットに分割しない場合には、長さＮのチャンクレット内のビットの異なる組合せの数、または本方法がチャンクレットを分割する場合には、長さＡのサブユニット内のビットの異なる組合せの数のいずれかに等しい。文書タイプが分かっているか、または所与の長さのサブユニットもしくはチャンクレットに対するビットの全ての組合せよりも少ないと予測される場合、Ｘ（マーカーの数）は、ビットの考えられる組合せの実数よりも小さい可能性がある。例えば、いくつかの実施形態では、全てのビットマーカーが同じサイズであり、ビットマーカーテーブル内のビットマーカーの数が、サイズＮまたはＡのビット列内のビットの組合せの数に等しい。他の実施形態では、全てのビットマーカーが同じサイズであり、ビットマーカーテーブル内のビットマーカーの数が、サイズＮまたはＡのビット列内のビットの組合せの数の、９０％未満、８０％未満、７０％未満、もしくは６０％未満である。
【００６９】
例として、いくつかの実施形態では、各チャンクレットは、複数の０および／または１から成るコード（すなわち、マーカー）を割り当てられる。他の実施形態では、各チャンクレットは、各々が、複数の０および１から成るコード（すなわち、マーカー）を割り当てられている複数のサブユニットに分割される。サブユニットは、長さＡによって定義され得、Ｎ／Ａ＝Ｙで、Ｙは整数である。サブユニットがその数のビットを有していない場合、例えば、１つ以上のサブユニットが、システムが入力として受信するように構成されているビット数よりも少ないビット数しか持たない場合、システムはビット、例えば、ゼロを、全てのサブユニットが同じサイズになるまで、追加し得る。このステップは、例えば、チャンクレットがサブユニットに分割された後、全てのチャンクレットが同じサイズであるかどうかをまず確かめない場合に、実行され得る。あるいは、前述のように、それは、チャンクレットをサブユニットに分割する前に、チャンクレットレベルで実行され得る。
【００７０】
上の説明で示唆するように、アルゴリズムは、ビット列をコード化されたデータのセットに翻訳するように構成され得、アルゴリズムは、ビット列が、チャンクレットまたは、チャンクレットのサブユニットのいずれかに対応するように、設計され得る。好ましくは、コード化されたデータのセットは、ホストまたはクライアントから受信される際のファイルよりも小さい。しかし、コード化されたデータのセットが元のデータよりも小さいかどうかに関わらず、それは、変換してファイルのチャンクレットに戻すことが可能である。当業者であれば認識するように、格納のためにホストから受信されるデータは、生データであり、従って、任意の文書タイプに対応できる。
【００７１】
符号化は、２つの独立した目的に役だち得る。第１に、格納のためにデータを符号化することにより、セキュリティが向上する。コードを知っている（すなわち、ビットマーカーテーブルにアクセスできる）人またはエンティティだけが、それを復号して文書を再構築することができる。第２に、コードが元の文書よりも少ないビットを使用して作成される場合、必要な記憶空間が少なくなって、費用を節約できる。１つ以上のファイルに対する記憶空間が削減されると、ＮＣＭは、もっと多くの数のファイルおよび／またはもっと大きなファイルに相当するデータを格納できる。
【００７２】
テーブル内のビットの少なくとも複数の一意の組合せに対して、好ましくは、システムがチャンクレットをサブユニットに分割しない場合、マーカーは、チャンクレット長Ｎよりも小さいか、またはシステムがチャンクレットをサブユニットに分割する場合には、サブユニット長Ａよりも小さい。好ましくは、システムがチャンクレットをサブユニットに分割しない場合、どのマーカーもチャンクレット長Ｎよりも大きくないか、またはシステムがチャンクレットをサブユニットに分割する場合、どのマーカーもサブユニット長Ａよりも大きくない。いくつかの実施形態では、全てのマーカーは、Ｎよりも小さいか、またはＡよりも小さい。加えて、いくつかの実施形態では、各マーカーは、同じサイズであり得るか、または２つ以上のマーカーが異なるサイズであり得る。異なるサイズのマーカーがある場合、これら異なるサイズのマーカーは、例えば、テーブル内にあり得る。あるいは、テーブル内で全てのマーカーが同じサイズであるが、格納前に、全ての０がマーカーの一方または両方の端部から除去される。
【００７３】
コンピュータプログラム製品がチャンクレットを複数のマーカーに翻訳した後、コンピュータプログラム製品は、複数のマーカー（０が端部から除去されているかいないかに関わらず）を、持続性記録媒体上に、チャンクレットの順序に対応する順序で、またはチャンクレットが別の方法で再作成され得る順序で、格納させる。最終的に、マーカーは、非キャッシュ媒体である、持続性媒体内に格納される。しかし、任意選択で、それらは、まず、キャッシュ媒体、例えば、Ｌ１および／またはＬ２に送信され得る。従って、情報が失われないように、ビットマーカーテーブルが、永続的メモリ内に格納され得るが、使用時には、コピーが、例えば、Ｌ２キャッシュ内にあり得、ブートまたは再ブート時に、Ｌ２キャッシュ内のテーブルは永続的メモリから生成され得る。
【００７４】
一実施形態では、記憶装置は、所与のファイルに対応する、複数のビットマーカーを、非キャッシュ媒体内に格納する。ビットマーカーは、Ｘ〜Ｙのサイズ範囲であり、ＸはＹよりも小さく、少なくとも２つのマーカーが異なるサイズを有する。ビットマーカーの取得時または取得後に、コンピュータアルゴリズムは、所定のサイズのＺよりも小さい、全てのビットマーカーの一方の端部に０を追加するが、ここで、ＺはＹよりも大きいか、または等しい。サイズＺの各マーカーが長さＡのビット列に翻訳される、ルックアップテーブルが、参照され得るが、ここで、ＡはＺ以上である。限定されない例では、Ｘ＝４、Ｙ＝２０、Ｚ＝２４、Ａ＝３２である。いくつかの実施形態では、Ａは少なくともＺより５０％大きい。Ａに対応するビット列は、チャンクレットに結合されるサブユニットであり得るか、またはチャンクレット自身であり得る。
【００７５】
頻度変換器
【００７６】
前述のように、ビットマーカーテーブルは、マーカーをビット列に、生データに対してランダムまたは非ランダムに、割り得て得、ビットマーカーは、均一または不均一なサイズであり得る。しかし、前述のようなビットマーカーテーブルの代わりに、頻度変換器を使用し得る。
【００７７】
当業者であれば認識するように、本開示の例の節におけるテーブル１およびテーブル２は、ビットマーカー（すなわち、変換されたビット）を、生データ内のビット列の頻度とは無関係な方法で割り当てる。しかし、前述し、以下の例３で説明するように、ある文書タイプまたは文書のセット内により頻繁に出現すると見込まれる生データに対して、より小さいマーカーを割り当て得る。この方策は、全ての情報のほぼ８０％が、最も頻出するサブユニットのほぼ上位２０％内に含まれるという事実を利用する。言い換えれば、データに対応するサブユニットは、非常に繰返しが多い。
【００７８】
頻度変換器が異なるサイズのビット列をどのように使用できるかをさらに示すために、図５が参照され得る。図５は、５ユニット長であって、数１から始まる、全ての２進シーケンスに対する二分木を示す。その木が示すように、最上位行から始まって、木を最下層まで下方に移動する、長さが５桁のシーケンスを作成するための１６の経路がある。しかし、木を下方に移動する際に、例えば、第３、第４、または第５の行への分岐を進むことができる。それに応じて、本方法は、一片のデータに対して、木を一部下方に移動することに対応するコードを割り当て得、他方、他のデータに対しては、本方法は、異なる分岐に沿って、もっと多くの数のユニットを移動することに対応するコードを割り当てる。限定されない例として、変換されたデータの特定の一片に対して、第３行で止まって、例えば、１０１のシーケンスを生成し得、他方、データの他の全てに対して、最初の３桁は１０１ではない。従って、本方法は、（図５のボックス内にある）１０１０、１０１１、１０１００、１０１０１、１０１１０および１０１１１：の使用を決して許可しないであろう。メモリからデータを取得すると、システムは、数字を、それらが一意であると認識するまで読み取り、それらが一意であると認識すると、その一意の文字列を、復号を可能にするプログラムへの入力として使用し、そのプログラムは、ホストに対して生データファイルの再作成を可能にし得る。
【００７９】
本発明の様々な実施形態は、（最も短い一意のコードに対応する）最小数のビットおよびその後の最小数の読取りに対する取得要求の間またはその後に、データファイルまたはテーブルと比較することにより一意性をチェックし得、コードがデータファイルまたはテーブル内で一意でない場合は、ビット数の拡張を継続して、シーケンスが一意であると認識されるまで各個々のビットを追加した後に、その拡張されたコードの一意性をチェックする。上記の例は、３、４、または５ビット列に関して記述しているが、それらのサイズは、例示のみを目的として使用されている。いくつかの実施形態では、頻度変換器に関連して使用するための一意のビットの最も短いシーケンスは、１０〜１５ビット長であり、ビットの最も長いシーケンスは２５〜４０ビット長である。
【００８０】
いくつかの実施形態では、異なるサイズの複数の変換されたビット列の全てに対して、Ａビット長の第１の変換されたビット列、およびＢビット長の第２の変換されたビット列があり、ここで、Ａ＜Ｂであって、第１の変換されたビット列のＡビットの識別が、第２の変換されたビット列の最初のＡビットの識別と同じでない。
【００８１】
テーブル１、２および３（例を参照）が示すように、ビットのグループを表すためにマーカーが使用されるので、情報が変換され得、出力コードが、入力よりも少ない空間を占めるように構成できる。従って、好ましくは、テーブル内で、少なくとも１つの、複数の、少なくとも５０％の、少なくとも６０％の、少なくとも７０％の、少なくとも８０％の、少なくとも９０％の、または少なくとも９５％の、マーカーが、サブユニットよりもサイズが小さい。しかし、変換されたデータを同じサイズにするか、またはホストから受信したか、もしくはハッシュ関数値アルゴリズムから生成したデータよりも長くするのを妨げる技術的障害はない。
【００８２】
フラグメンテーション
【００８３】
前述のように、データストリームの受信後、いくつかの実施形態では、本方法は、受信されるデータのフラグメント化を必要とする。受信されるデータが大規模なファイルの形式である場合、それは、チャンクレットにフラグメント化され得る。受信されるデータがチャンクレットの形式である場合、チャンクレットはサブユニットにフラグメント化され得る。大規模なファイルは、まず、チャンクレットにフラグメント化され得、次いで、それらのチャンクレットがサブユニットにフラグメント化され得る。従って、ホストからの任意の入力に対して、０、１、または２つのフラグメンテーションのステップがあり得る。
【００８４】
Ｉ／Ｏストリームをフラグメント化することにより、本方法は、各Ｉ／Ｏストリームを、所定の、好ましくは、均一サイズのもっと小さい（ブロックとも呼ばれ得る）ユニットに分割する。当業者であれば認識するように、より小さいブロックサイズを使用することの１つの利益は、小さいブロックは、データのさらに容易な処理を可能にすることである。限定されない例として、Ｉ／Ｏストリームは、４０９６バイト長であり得、本方法は、そのストリームを、１０２４、５１２、２５６、または１２８バイト長のフラグメント化されたユニットにフラグメント化し得る。データが受信された後、またはデータが受信されているときに、チャンクレットを、例えば、３２ビットのサブユニットに分割する、アルゴリズムが実行され得る。
【００８５】
サブユニットのサイズは、データをホストから受信するシステムの設計者の選択である。しかし、サブユニットのサイズは、チャンクレットが、一貫したサイズのサブユニットに分割されるように、選択されるべきであり、サブユニットは、ビットマーカーテーブルまたは頻度変換器の参照に関連して、容易に使用できる。
【００８６】
チャンクレットのいずれかが他よりも小さい場合、任意選択で、小さいサイズのチャンクレットの受信時に、アルゴリズムが、その小さいチャンクレットを他のチャンクレットと同じサイズにするために、ゼロを追加する。代替として、システムは、チャンクレットをサブユニットに分割し、所望の長さより小さいサブユニットの取得時には、そのサブユニットの端部にゼロを追加し得る。
【００８７】
前処理
【００８８】
（符号化プロセスとも呼ばれ得る）翻訳プロセス中に、アルゴリズムが、ビットマーカーテーブルまたは頻度変換器に対する入力として使用する、ビット列（すなわち、チャンクレットまたはサブユニット）が、前処理され得る。これらのビット列の各々は、第１の端部および第２の端部によって画定され得、マーカーを割り当てる前に、本方法は、各ビット列を分析して、第２の端部におけるビットが０の値を有するかを判断することをさらに含む。第２の端部におけるビットが０の値を有する場合、本方法は、第２の端部におけるビット、および０の値を有して、第２の端部におけるビットとともに連続的なビット列を形成する全ての後続ビットを除去し、それにより、削減されたサイズのビット列を形成する。前処理ステップの利益は、より小さいビットマーカーテーブルまたは頻度変換器が使用できることである。例えば、同じコード化されたデータを生成するために、テーブルＩの代わりに、テーブル２が使用できる。当業者であれば認識するように、この前処理は、第２の端部からゼロの代わりに１を探して除去することにより達成できる。
【００８９】
切捨て
【００９０】
本発明の別の実施形態では、ビットマーカーテーブルまたは頻度変換器の使用を通して翻訳するのではなく、切り捨てられたサブユニットを、それらがチャンクレット内に存在するのと同じ順序で格納できる（または、サブユニットが使用されない場合には、チャンクレットが切り捨てられて格納できる）。従って、短くされた文字列を、例えば、ビットマーカーテーブル内で入力として使用するために、前処理されたデータとして機能させる代わりに、それら自体が格納され得る。
【００９１】
このように、いくつかの実施形態では、データを記録媒体上に格納するための別の方法がある。この方法によれば、複数のデジタル２値信号を受信し、デジタル２値信号が、前述したフォーマットのチャンクレットに編成される。任意選択で、各チャンクレットは、前述のように、サブユニットに分割され得る。
【００９２】
各チャンクレットまたはサブユニットは、その長さによって定義され得、各チャンクレットまたはサブユニットは、第１の端部および第２の端部を有する。各チャンクレットまたはサブユニットを分析して、第２の端部におけるビットが値０を有するかを判断し得、第２の端部におけるビットが値０を有する場合、第２のビットにおけるビットおよび両方が値０を有して、第２の端部におけるそのビットとともに連続的なビット列を形成する全てのビットを除去し、それにより、第２の端部に０を有する任意のチャンクレットまたはサブユニットに対して、修正されたチャンクレットまたは修正されたサブユニットを形成する。これらの修正されたビット列は元のビット列よりも短いので、それらは切り捨てられたと呼ばれ得る。
【００９３】
チャンクレットまたはサブユニットが切り捨てられた後、その切り捨てられた情報を持続性記録媒体内に格納し得る。切り捨てられた情報を格納することにより、そうでなければ、切り捨てられなかったビット列で格納されていた同じ情報を格納するために、少ないビットしか使用されない。
【００９４】
前述の様々な実施形態では、各サブユニットまたは各チャンクレットの、両方ではなく、第１の端部または第２の端部から、桁（複数可）を除去できる。しかし、各サブユニットまたはチャンクレットの第１の端部から桁の除去を検討し、各サブユニットまたはチャンクレットの第２の端部から桁を除去することを別に検討して、各サブユニットまたはチャンクレットに対して、第１の端部および第２の端部の一方または両方のいずれかで、切捨てが生じているかどうかを分析し、切捨てが一方の端部のみで生じている場合、切り捨てられたチャンクレットまたはサブユニットを保存し、切捨てが両方の端部で生じている場合には、切り捨てられたユニットの小さい方を保存する、方法を実施することは、本発明の様々な実施形態の範囲内である。チャンクレットまたはサブユニットの両方の端部から桁が除去できる方法を実施することも、本発明の範囲内である。
【００９５】
このように、複数のデジタル２値信号を受信し得る。２値信号は、ユニットで、例えば、チャンクレットまたはチャンクレットのサブユニットで、受信され得る。各ユニットは、同じビット数長であり得、各ユニットは、第１の端部および第２の端部を有する。ユニット内のビット数は、１より大きい整数であり、ビットは、ユニット内に順序を有し、ユニットは順序を有する。
【００９６】
次いで、第１の端部におけるビットが値０を有するかを判断するために各ユニットを分析し得、第１の端部におけるビットが値０を有する場合は、第１の端部におけるビットおよび両方が値０を有して、そのビットとともに連続的なビット列を形成する全てのビットを除去し、それにより、第１の端部に０を有する任意のユニットに対して第１の修正されたユニットを形成する。
【００９７】
第２の端部におけるビットが値０を有するかも判断するために各ユニットを分析し得、第２の端部におけるビットが値０を有する場合は、第２の端部におけるビットおよび両方が値０を有して、そのビットとともに連続的なビット列を形成する全てのビットを除去し、それにより、第２の端部に０を有する任意のユニットに対して第２の修正されたユニットを形成する。
【００９８】
各ユニットに対して、以下のデシジョンツリーが適用され得る：（ａ）第１の修正されたユニットおよび第２の修正されたユニットのサイズが同じである場合は、第１の修正されたユニット（または第２の修正されたサブユニット）を格納する；（ｂ）第１の修正されたユニットが第２の修正されたユニットより小さい場合は、第１の修正されたユニットを格納する；（ｃ）第２の修正されたユニットが第１の修正されたユニットより小さい場合は、第２の修正されたユニットを格納する；（ｄ）修正されたユニットがない場合は、そのユニットを格納する；（ｅ）第１の修正されたユニットはないが、第２の修正されたユニットがある場合は、第２の修正されたユニットを格納する；ならびに、（ｆ）第２の修正されたユニットはないが、第１の修正されたユニットがある場合は、第１の修正されたユニットを格納する。
【００９９】
１つ以上のビットが第１の端部または第２の端部から除去されているか、またはビットが第１の端部から除去されるユニットに対して第１のビットマーカーテーブルを、またビットマーカーが第２の端部から除去されるユニットに対して第２のビットマーカーテーブルを使用できるかを示す情報も格納し得、２つのビットマーカーテーブル間には、ビットマーカーの重複がない。これらの２つの異なるビットマーカーテーブルは、同じテーブルのセクションとして編成でき、修正されていないユニットに対するビットマーカーを含む。テーブルまたは複数のテーブルでは、第１の修正されたユニット、第２の修正されたユニットおよび修正されていない任意のユニットに対して、例えば、それらは両方の端部に１を有しているので、ビットマーカーの重複がない。
【０１００】
当業者であれば認識するように、前述の方法はゼロの除去に関連して説明されているが、システムは代わりに１を除去できる。さらに、これらの方法は、ビットマーカーテーブルもしくは頻度変換器の使用に対する代替手段として使用されているとして説明される。しかし、これらの方法を、ビットマーカーテーブルまたは頻度変換器と併せて、例えば、それらのプロトコルの出力であるマーカーを、それらが元のファイルの取得および再構成を可能にする方法で格納されている限り、切り捨てることにより、使用することは、本発明の範囲内である。
【０１０１】
ハッシュ値
【０１０２】
前述したある実施形態では、データを符号化するためにビットマーカーテーブルまたは頻度変換器にアクセスする。別の実施形態では、チャンクレットまたはサブユニットが、暗号化ハッシュ関数値アルゴリズムに対する入力として機能する。
【０１０３】
従って、各入力に対して、入力よりサイズが小さい出力がある。例えば、Ｘバイトのサブユニット（Ｘバイトのフラグメント化されたユニットとも呼ばれ得る）がある場合、出力は、Ｘバイトの各フラグメント化されたユニットに対して生成されたハッシュ関数値である。ハッシュ関数値アルゴリズムの例は、ＭＤ５ハッシュ（メッセージダイジェストアルゴリズムとも呼ばれる）、ＭＤ４ハッシュおよびＳＨＡ−１を含むが、それらに制限されない。ハッシュ関数値アルゴリズムから出力される値は、チェックサムまたは和（ｓｕｍ）と呼ばれ得る。いくつかの実施形態では、和は、６４、１２８、１６０または２５６ビットのサイズである。Ｉ／Ｏストリーム内のデータの非常に繰り返しが多い特質のために、矛盾する和、すなわち、同じであるが、異なるフラグメント化ユニットに対応する和、を生成する確率は、比較的低い。
【０１０４】
いくつかの実施形態では、各ハッシュ値は、複数の０および／または１から成り、好ましくは、同じ長さの、ビット列またはコードである。これらのハッシュ値は、非キャッシュ記録媒体上に格納するために使用され得る。
【０１０５】
一実施形態では、システムは、例えば、非キャッシュ記録媒体上にデータを格納するための方法を実行し得：（ｉ）ＮバイトのＩ／Ｏストリームを受信すること、（ｉｉ）Ｎバイトを、Ｘバイトのフラグメント化ユニットにフラグメント化すること、（ｉｉｉ）暗号化ハッシュ関数値をＸバイトの各フラグメント化ユニットと関連付けることであって、関連付けることが、相関ファイルにアクセスすることを含み、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＸバイトのシーケンスと関連付けて、（ａ）フラグメント化されたＸバイトのシーケンスが相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）フラグメント化されたＸバイトのシーケンスが相関ファイル内にない場合は、Ｙビットの新しいハッシュ関数値を生成して、Ｘバイトのフラグメント化シーケンスとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、新しいハッシュ関数値を使用する、暗号化ハッシュ関数値をＸバイトの各フラグメント化ユニットと関連付けること、を含む。
【０１０６】
前述の方法は、ＮバイトのＩ／Ｏストリームのフラグメント化を必要とする。しかし、本方法は、暗号化ハッシュ関数値アルゴリズムをＩ／Ｏストリームに適用して、それをフラグメント化しないことにより適用できる。従って、代替方法は、（ｉ）ＮバイトのＩ／Ｏストリームを受信すること、（ｉｉ）暗号化ハッシュ関数値をＮバイトの各ユニットと関連付けることであって、前記関連付けることが、相関ファイルにアクセスすることを含み、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＮバイトのシーケンスの各々と関連付けて、（ａ）Ｎバイトのシーケンスが相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）Ｎバイトのシーケンスが相関ファイル内にない場合は、Ｙビットの新しいハッシュ関数値を生成して、Ｎバイトとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、新しいハッシュ関数値を使用する、暗号化ハッシュ関数値をＮバイトの各ユニットと関連付けること、を含む。さらに、様々な方法が、例示目的で、ＮバイトまたはＸバイトのセットに適用されるとして説明されているが、当業者は、本方法はファイルの全てのＮバイトまたはＸバイトに対して好ましくは適用され得ることを理解するであろう。
【０１０７】
加えて、前述の方法は、バイト列がまだ相関ファイル内にない場合に限り、アルゴリズムを適用する。別の実施形態では、本発明は、非キャッシュ記録媒体上にデータを格納するための方法を提供し：（ｉ）ＮバイトのＩ／Ｏストリームを受信すること、（ｉｉ）暗号化ハッシュ関数値アルゴリズムをＮバイトの各ユニットに適用して、Ｎバイトの各ユニットに対して生成されたハッシュ関数値を形成すること、（ｉｉｉ）相関ファイルにアクセスすることであって、相関ファイルが、Ｙビットの格納されたハッシュ関数値を、複数の格納されたＮバイトのシーケンスの各々と相互に関連付けて、（ａ）Ｎバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にある場合は、非キャッシュ記録媒体上に格納するために、Ｙビットの格納されたハッシュ関数値を使用し、また（ｂ）Ｎバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にない場合は、Ｙビットの生成されたハッシュ関数値をＮバイトのフラグメント化ユニットとともに相関ファイル内に格納し、非キャッシュ記録媒体上に格納するために、生成されたハッシュ関数値を使用する、相関ファイルにアクセスすること、を含む。この実施形態は、Ｎバイトをフラグメント化してフラグメント化ユニットを形成し、暗号化ハッシュ関数値アルゴリズムを、Ｎバイトのユニットの代わりに、フラグメント化ユニットに適用するステップを追加するようにも修正され得る。
【０１０８】
前述したある実施形態では、各チャンクレット、フラグメント化ユニット、またはサブユニットに対してチェックサムが取得された後、相関ファイルにアクセスする。これらの方法は、先入れ先出し方式（「ＦＩＦＯ」）プロトコルに従ってチェックサムを取得して、Ｉ／Ｏストリームが受信されている間、チェックサムが生成されている間、または全てのＩ／Ｏストリームが受信されて、フラグメント化され、ハッシュ関数値アルゴリズムを適用された後のいずれかに、相関ファイルのアクセスを開始し得る。
【０１０９】
前述のように、相関ファイルは、Ｙビットの異なる格納されたハッシュ関数値を、複数の格納されたＸバイトのシーケンスの各々と関連付ける。それに応じて、生成されたハッシュ関数値があるこれらの状況では：（ａ）Ｘバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にある場合、本方法は、Ｙビットの格納されたハッシュ関数値を非キャッシュ記録媒体上に格納するために使用させ、また（ｂ）Ｘバイトのユニットに対して生成されたハッシュ関数値が相関ファイル内にない場合、本方法は、Ｙビットの生成されたハッシュ関数値を、Ｘバイトのシーケンスとともに相関ファイル内に格納させて、非キャッシュ記録媒体上に格納するために、生成されたハッシュ関数値を使用する。
【０１１０】
矛盾解決モジュール
【０１１１】
ハッシュ値アルゴリズムの適用の結果として、矛盾するハッシュ値が生成されている確率は低い。それ故、いくつかの実施形態では、本明細書で説明する方法を、矛盾解決モジュールを使わずに採用することを選択し得る。しかし、様々な実施形態では、本発明は、矛盾が生じ得る状況に対処するために、矛盾解決モジュールを適用する。
【０１１２】
図６に示すように、システムは、Ｎバイトのセットのストリームを受信し得る（６１０）。システムは、次いで、各フラグメント化ユニットに対して、ハッシュ関数を適用して、ハッシュ関数値を生成する（６３０）ために、Ｎバイトを望ましいサイズのユニットにフラグメント化させ得る（６２０）。次に、システムは、各ハッシュ値が既に相関ファイル内にあるかどうかを問い合わせる（６４０）。
【０１１３】
これらの実施形態では、Ｘバイトのフラグメント化ユニットに対して、相関ファイル内のハッシュ値と同じハッシュ値が生成されるときにはいつでも起動される（６５０）矛盾解決モジュールがある。このモジュールは次いで、Ｘバイトのフラグメント化ユニットが、そのハッシュ値に対して既に格納されたＸバイトの値と同じであるかどうかを問い合わせる。矛盾解決モジュールが、Ｘバイトのフラグメント化ユニットに対して、相関ファイル内に格納されたハッシュ関数値と同じ、ハッシュ関数値が生成されるが、Ｘバイトのフラグメント化ユニットが、格納されたハッシュ関数値と関連付けられたＸバイトと異なると判断する場合、相関ファイルを更新して、生成されたハッシュ値を、ＮＣＭに書き込むだけでなく、その中に格納する必要がある（６６０）。例えば、いくつかの実施形態では、以下で説明するように、モジュールは、格納されたハッシュ関数値および生成されたハッシュ関数値と関連付けられた異なるＺビットがあるようにさせる。
【０１１４】
生成されたハッシュ値が（存在する場合は、任意の関連付けられたＺ値とともに）一意である場合、それは、ＮＣＭ上に格納するために使用され得、相関ファイルが関連付けを含むように更新され得る（６８０）。さらに、ハッシュ値が既に相関ファイル内にあり、受信されたＮバイトが相関ファイル内のもとの同じである場合、格納されたハッシュ値が（存在する場合は、任意の関連付けられたＺ値とともに）ＮＣＭに書き込まれて、システムは相関ファイルを更新する必要がない（６７０）。従って、相関ファイルファイルがアクセスされた後、新しく生成されたハッシュ値が既に相関ファイル内にある場合に限り、矛盾モジュールがチェックとしてアクセスされ得る。矛盾モジュールは次いで、矛盾があるか、または受信したファイルからのチェックサムおよびフラグメント化ユニットの両方が、既に相関ファイル内で互いに関連付けられているかを判断するであろう。
【０１１５】
前述の実施形態は、各フラグメントのビットのユニットが、相関ファイルにアクセスする前に、暗号化ハッシュ関数値アルゴリズムを適用される方法を記述する。しかし、代替として、まず、サブユニットまたはチャンクレットの存在について相関ファイルを確認し、フラグメント化ユニットがまだテーブル内にない場合に限り、暗号化ハッシュ関数値アルゴリズムを適用できる。次いで、チャンクレットまたはサブユニットが既に相関ファイル内にある場合は、格納されたチェックサム値を使用する。サブユニットまたはチャンクレットがファイル内にない場合には、ハッシュ値アルゴリズムを適用して、矛盾をチェックするためにプロトコルに入るであろう。本当の矛盾がある、すなわち、同じハッシュ値が異なるサブユニットまたはチャンクレットと関連付けられている場合には、この問題に対処するように相関ファイルを更新するであろう。
【０１１６】
本当の矛盾の問題に対処するための一手段は、矛盾が存在しない全てのハッシュ関数値に対して、Ｚビットが関連付けられることであり、Ｚビットは、例えば、８〜１６個のゼロの均一の長さである。限定されない例として、Ｎ＝４０９６バイト（チャンクレットのサイズ）、Ｘ＝５１２バイト（サブユニットのサイズ）、Ｙ＝１２８または２５６ビット（ハッシュ値サイズ）、およびＺ＝８または１６ビット（ハッシュ値拡張サイズ）である。本方法は、例えば、チェックサムが、以前に格納されたチェックサムと矛盾しない場合、チェックサムの端部に８個のゼロを結合させ得る。矛盾を識別した際には（例えば、異なるフラグメント化ユニットが同じチェックサムと関連付けられている）、最新のチェックサムが異なるＺ値を割り当てられ得る。従って、相関ファイル内に格納された際のＺ値が００００００００の場合、第１の矛盾しているチェックサムに対するＺ値は、０００００００１であり得、別の矛盾しているチェックサムがあるとすれば、００００００１０である。さらに矛盾しているチェックサムがある場合、矛盾しているチェックサムが識別されると、各矛盾しているチェックサムは次のＺ値を割り当てられ得る。
【０１１７】
各フラグメント化ユニットに対してチェックサムが取得され、矛盾モジュール（存在する場合）の適用に続いて、複数のハッシュ関数値（および、いくつかの実施形態では、Ｚ値とともに）が、格納のために非キャッシュ記録媒体に書き込まれ得る。
【０１１８】
ハッシュ値およびビットマーカーまたは頻度変換器の併用
【０１１９】
いくつかの実施形態では、ハッシュ値を格納する代わりに、本方法は、格納のための各ハッシュ関数値を、ビットマーカーテーブルの使用を通して変換（符号化とも呼ぶ）して、格納のための各ハッシュ関数値に対してビットマーカーを生成すること、ならびにそれぞれのハッシュ関数値（および、いくつかの実施形態では、Ｚ値とともに）に対する各ビットマーカーを、非キャッシュ記録媒体内に格納することをさらに含む。ビットマーカーテーブルを使用することにより、ハッシュ値を変換またはコード化し得る。従って、ハッシュ値は、ビットマーカーテーブルをアクセスする際に入力サブユニットとして機能し得、関連付けられたマーカーが出力として機能し得る。
【０１２０】
サブユニットは、長さＡによって定義され得、Ａで割ったハッシュ値の長さは整数である。ビット列のいずれかがそのビット数を有していない、例えば、１つ以上のビット列が、変換されるように構成されているサブユニット内の数よりも少ないビット数しか有していない場合、システムは、ビット、例えば、ゼロを、全てのサブユニットが同じサイズになるまで、追加し得る。代替として、０の追加が、ハッシュ値をサブユニットに分割する前に、ハッシュ値レベルで実行され得る。さらに、ハッシュ値（および、いくつかの実施形態では、Ｚ値と結合されたとおり）がサブユニットのサイズよりも小さい場合、それらは、サブユニットを形成するように結合されるか、または適切なサイズのサブユニットを形成するために結合されてフラグメント化され得る。
【０１２１】
ハッシュ値のコード化されたデータへの変換は、アルゴリズムまたはコンピュータプログラムによって実施され得る。アルゴリズムまたはコンピュータプログラムの実行は、例えば、ハッシュ関数値アルゴリズムの適用も制御する、マネージャによって制御され得る。コード化されたデータ（変換されたデータとも呼ばれ得る）も、２値信号から成り、ファイルのハッシュ値に変換して戻すことが可能な方法で、コード化されて格納される。従って、情報を失うことなく復号を可能にする符号化プロセス中に、情報が保持される。
【０１２２】
符号化は、２つの独立した目的に役だち得る。第１に、格納のためのデータをビットマーカーテーブルを通して変換することにより、セキュリティが向上する。コードを知っている人またはエンティティだけが、それを復号して文書を再構築することができる。第２に、コードが、文書に対応するハッシュ値よりも少ないビットを使用して作成される場合、変換されたデータおよびハッシュ値の両方の使用により、必要な記憶空間が少なくなって、費用をさらに節約できる。
【０１２３】
いくつかの実施形態では、ビットマーカーテーブルを使用するのではなく、本方法は、格納のための各ハッシュ関数値を頻度変換器の使用を通して符号化することをさらに含む。これらの方法では、格納のための各ハッシュ関数値に対して、変換されたビット列が生成され、同じサイズのハッシュ値に対して、出力される変換されたビット列は異なる長さである。頻度変換器は、複数の変換されたビット列の各々を、複数のハッシュ関数値の各々と関連付け得、頻度変換器内の複数の変換されたビット列は、読み戻された際に、変換されたビット列が適切なハッシュ値と相互に関連付けることができるように、十分に区別できる。
【０１２４】
ハッシュ値アルゴリズムの使用を、（１）ビットマーカーテーブルの適用、または（２）頻度変換器の適用：のいずれかと組み合わせることにより、さらなるセキュリティおよび／または経費節減を取り入れることができる。加えて、前述のように、ハッシュ値は、ビットマーカーテーブルまたは頻度変換器に対する入力である。しかし、順序が逆転され得、チャンクレットまたはサブユニットが、マーカーを生成するためにビットマーカーテーブルまたは頻度変換器を使用するプロトコルに入り得、それらのマーカーは、矛盾解決モジュールを使用する方法を含むが、それらに限定されず、本明細書で説明する方法のいずれかに従い、ハッシュ関数アルゴリズムに対する入力として機能し得る。
【０１２５】
メディエータおよびマネージャ
【０１２６】
ビットマーカーテーブル、頻度変換器、ハッシュ値相関ファイル、ならびに前述のファイルおよびプロトコルにアクセスして使用するためのプログラムのいずれかまたは各々が、メディエータ、マネージャまたは他の場所に格納され得る。前述のプロトコルまたはファイルのいずれか１つ以上が、本発明の実施形態に関連して使用され、メディエータまたはマネージャ内に格納されない場合はいつでも、好ましくは、メディエータ、マネージャ、または両方に動作可能に結合される。ローカルまたはリモートに格納されているファイルおよびプログラムと通信するための方法およびシステムは、当業者に周知である。
【０１２７】
様々な実施形態では、マネージャは、本発明の方法を制御する。例えば、Ｉ／Ｏ（ホストからの出力、システムへの入力）がホストから受信された後、マネージャは、Ｉ／Ｏストリームの受信をホストに対して確認させ得る。
【０１２８】
ホストは、Ｉ／Ｏストリームのファイルを第１の記憶アドレスに格納されているとして記録し得る。しかし、変換されたビット列は、実際には、第２の記憶アドレスにおいて非キャッシュ記録媒体内に格納され得、第１の記憶アドレスは、第２の記憶アドレスと同じではない。さらに、第１の記憶アドレスは、ファイルを第１のファイルサイズを有するとして示し（または、その表示と関連付けられ）得、他方、第２の記憶アドレスは、第２のファイルサイズに対応し得、第１のファイルサイズは、第２のファイルサイズの、少なくとも２倍の大きさ、または少なくとも４倍の大きさである。
【０１２９】
いくつかの実施形態では、第２の記憶アドレスは、メディエータ上に格納される。メディエータ内で、第２の記憶アドレスはビットフィールド内に格納され得る。本明細書で説明するメディエータは、ビットマーカーテーブル、頻度変換器およびハッシュ値アルゴリズムの１つ以上を通してデータを翻訳するために説明した方法と無関係に、またはそれに関連して、使用され得る。
【０１３０】
いくつかの実施形態では、メディエータは、ハードウェア、ソフトウェア、またはその組合せであり：（ｉ）トラックの第１のセットであって、ファイルシステム情報、ブート可能性情報、およびパーティション情報に対応する情報を含むか、または包含する、トラックの第１のセット、（ｉｉ）トラックの第２のセットであって、トラックの第１のセットのコピーに対応する情報を含むか、または包含する、トラックの第２のセット、（ｉｉｉ）トラックの第３のセットであって、ファイルシステム情報、ブート可能性情報、およびパーティション情報以外のメタデータに対応する情報を含むか、または包含する、トラックの第３のセット、ならびに（ｉｖ）トラックの第４のセットであって、ビットフィールドに対応する情報を含むか、または包含する、トラックの第４のセット、を含む。例として、メディエータは、Ｌ２キャッシュ内に常駐し得、ビットマーカーテーブル、頻度変換器またはハッシュ値テーブルのいずれか１つ以上は、使用中、サーバーのＲＡＭ内に常駐し得、また、マーカーまたはハッシュ値が格納されているＮＣＭと同じか、または異なり得る、ソリッドステートデバイスの永続記憶装置内にも存在し得る。更新される場合、更新は、ＲＡＭ内のテーブルに対して、および永続的メモリに対しても行われる。
【０１３１】
メディエータの使用に加えて、本発明の様々な実施形態は、マネージャの使用を必要とする。マネージャは、１つ以上のモジュールを含み、ローカルコンピュータ上、ネットワーク上、またはクラウド内に常駐し得る。マネージャは、ある情報自体の受信を調整するか、またはある情報自体を受信して、この情報をメディエータに転送するか、または、情報の受信を直接メディエータによって制御するように構成されている。従って、方法は、イニシエータからの情報がマネージャからメディエータに流れるか、またはマネージャだけが情報の流れをシステムの他の構成要素に、例えば、ホストもしくはＮＣＭに向けるように、設計できる。
【０１３２】
本発明の様々な実施形態では、マネージャは、ハッシュ関数アルゴリズムまたは他のプロトコル、任意の矛盾モジュール（存在する場合）および任意の変換モジュール（存在する場合）を適用するか、または適用させ得、データの流れを直接、メディエータに向かわせ得る。マネージャはまた、メディエータの使用を通じた情報の格納、ならびに情報の取得および伝送も制御し得る。情報を格納する場合、ＬＢＡ番号が識別され得、格納されるデータが、ボトルネックを回避するか、またはそれを低減するために、バッファに送信され得る。さらに、格納中、Ｌ１および／またはＬ２キャッシュが使用され得る。
【０１３３】
同様に、データを取得する際に、本方法は、データをＮＣＭから呼び出して、バッファに充填し、チェックサム値を取得して、フラグメント化ユニットを再作成および再構成し得るか、またはフラグメント化されていない場合は、ホストが受信して再検討し得る形式に情報を形成するように直接再構築し得る。格納されたデータが変換されたデータである場合は、チェックサム値を取得する前に、データが復号され得る。これらのステップは、必要なプロトコルを実行する、マネージャを通して調整および制御され得る。
【０１３４】
いくつかの実施形態では、マネージャは、１つまたは複数のメディエータを制御し、それと通信し、かつ、その活動を調整し得る。各メディエータに対して、マネージャは、パラメータのセットを受信する（または、その受信を調整する）。これらのパラメータは、ファイルシステム情報、ブート可能性情報、およびパーティション分割情報の１つ、２つ、もしくは３つ全部を含むか、基本的にそれらから成るか、またはそれらを含み得る。マネージャは、この情報を、メディエータ上のトラックの第１のセット内に格納させ、それは、予約１またはＲ１と呼ばれ得る。ファイルシステムは、予約ブロックがどのように使用されるかを指示する。例えば、ＮＴＦＳを使用する場合、セクター１〜２がＭＢＲ（マスターブートレコード）用であり得、セクター３が＄ＭＦＴ用であり得る。任意選択で、これらのトラックが、トラックの第２のセットにコピーされ得、それは、予約２またはＲ２と呼ばれ得る。
【０１３５】
マネージャは、前のパラグラフで説明したパラメータに加えて、メタデータも受信し得る。メタデータは、メディエータ上のトラックの第３のセット内に格納される。マネージャがパラメータおよびメタデータを受信する時、またはその後に、非キャッシュ媒体上に格納するための１つ以上のファイルも受信し得る。各ファイルは、ファイル名とともに受信される。ファイル名は、ファイルを伝送するホストによって生成され、ホストのファイルシステムによって定義され得る。例えば、ＳＡＮもしくはＮＡＳもしくはそれらの組合せであるか、またはその一部であり得る、マネージャは、ファイルをファイル名とともに受信すると、自動的に、格納のための本明細書で説明したステップを実行できる。
【０１３６】
本発明のシステムは、ハッシュ関数値アルゴリズムおよび変換のためのアルゴリズムが、メディエータ、またはマネージャ、またはメディエータもしくはマネージャに動作可能に結合されている他のハードウェアおよび／もしくはソフトウェア内のいずれかに格納される。アルゴリズムのいずれかまたは両方は、ファイル名もメディエータ内に格納させ得る。メディエータが物理的にどこに置かれるかに関して制限はない。しかし、好ましくは、メディエータは、ホストまたは、好ましくは、メディエータからリモートに配置されている、ホストと通信可能なコンピュータと通信するように構成されている。メディエータは、直接的または間接的に（例えば、マネージャを通じて）、記録媒体、例えば、データのコード化セットが格納される非キャッシュ媒体（任意選択で、メディエータ、任意のマネージャおよびホストからリモートである）と、通信するようにも構成される。前述のように、メディエータは、ファイル名を識別するユーザーが、コード化されたデータのセットを非キャッシュ記憶媒体から取得するのを可能にする。
【０１３７】
キャッシュ
【０１３８】
前述のように、いくつかの実施形態では、生データを受信すると、本発明の方法は、受信の確認を自動的にホストに返させ得る。あるＱｏＳ（サービス品質）プロトコルでは、データファイルがＩ／Ｏを通して受信されて、直ちにＬ１キャッシュに送信される。受信されると、確認がＬ１キャッシュからＩ／Ｏを通して返送される。Ｌ１キャッシュから、データファイルがＬ２キャッシュに送信され得、Ｌ２キャッシュは確認をＬ１キャッシュに返送する。Ｌ２キャッシュは、データファイルを長期格納のために非キャッシュ媒体（ＮＣＭ）にも送信し得る。ＮＣＭは、同様に、確認をＬ２キャッシュに返送し得る。
【０１３９】
いくつかの実施形態では、メディエータは、Ｌ１キャッシュ内のヒープ（動的に割り当てられるメモリ）内に常駐し得るか、またはそれに動作可能に結合され得る。代替として、メディエータは、カード内に常駐し得るか、またはＬ２キャッシュの一部であり得るか、もしくはＬ２キャッシュに動作可能に結合され得る。
【０１４０】
当業者であれば分かるように、メディエータを、Ｌ２に対してＬ１内に置くという判断は、格納されたデータの使用の頻度などの要因によって影響を受けるであろう。従って、Ｌ１キャッシュは、システムまたはエンドユーザーによって頻繁に使用されるデータを格納するために使用され、他方、Ｌ２キャッシュは、幾分頻繁にアクセスされるデータに対して使用され得る。
【０１４１】
別のＱｏＳプロトコルでは、Ｉ／Ｏを通して、データファイルがＬ１キャッシュによって受信される。データファイルは、Ｌ１キャッシュからＬ２キャッシュおよびＮＣＭの両方に転送される。Ｌ２キャッシュおよびＮＣＭの各々が、確認をＬ１キャッシュに送信する。Ｌ２キャッシュおよびＮＣＭの一方または両方から確認を受信する前、または後のいずれかに、Ｌ１キャッシュはＩ／Ｏを通して確認を送信する。
【０１４２】
ファイルの相関関係
【０１４３】
本発明の様々な実施形態では、ホストは、第１の記憶アドレスにおいて格納される各ファイルを理解するであろう。第１の記憶アドレスは、ホストによって、セクターマップ内に格納されて、ＬＵＮに対応し得る。それは、ファイルに対応する、ユニット、セクターまたはブロックの開始および、暗黙的または明示的のいずれかで、終了も含み得る。第１の記憶アドレスは、そのファイルが記憶装置またはストレージエリアネットワーク内で置かれているとホストが信じる位置に対応する。ホストは、このファイルアドレスを使用して、その格納された文書またはファイルを追跡し、また、それらを取得する。第１の記憶アドレスは、仮想アドレス、すなわち、データが実際に格納されている位置に対応していない。
【０１４４】
当業者であれば認識するように、ホストがファイル記憶アドレスを生成して、それを本発明のシステムに従い、ＳＣＳＩコマンドで送信し、任意選択で、セクターまたはＬＢＡ番号（複数可）を関連付ける、方法およびシステムが使用され得る。メディエータは、ファイル名、ホストがファイルの位置として考えるもの、およびホストから受信されたときのファイルの記憶サイズ、すなわち、生データおよび任意のヘッダーもしくはフッターデータを、データの実際の記憶アドレスである、第２の記憶アドレスと相互に関連付け得、それは、ファイルがそれから再作成できるが、例えば、ハッシュ関数値アルゴリズム、ビットマーカーテーブルおよび頻度変換器の１つ以上を通して、変換されている、情報を含み得る。代替として、メディエータはファイル名のみを格納し得、任意選択で、ファイルに対する第１の記憶アドレスを受信しない可能性がある。前述のように、記憶アドレスは、データの線形構成に基づいているので、それらは、第１のユーザー認識ＬＢＡのみを列挙するか、または明示的に全ての位置を列挙することにより、格納された情報のサイズを暗黙的に含み得る。
【０１４５】
前のパラグラフでは、ホストは、それが第１の記憶アドレスであると信じるものを提供すると記述しているが、情報は、ホストがそれを通してメディエータと直接的もしくは間接的に通信するダクト、ホスト内もしくはホストに動作可能に結合されたモジュール、またはメディエータおよび／もしくはマネージャ内であるか、もしくはそれに動作可能に結合されたモジュールのいずれかである別のエンティティによって生成され得る。当業者であれば認識するように、記憶装置上のデータファイルの位置を識別する格納された情報は、ポインタと呼ばれ得る。ファイルに対して、ポインタは、ユーザーが、データが配置されていると信じるＮＣＭ上の位置よりもむしろ、異なる位置（ブロック）からのデータの取得を指示し得る。
【０１４６】
任意選択で、ファイルをファイルタイプと関連付け得る。ファイルタイプは、データの受信者に、それをオープンするためにどのオペレーティングシステムが使用されるべきかを識別するように指示する。いくつかの実施形態では、ファイルタイプとの関連付けは、イニシエータまたはクライアントまたはホストで行われる。
【０１４７】
予備トラック
【０１４８】
前述のように、メディエータは、トラックの第１の予備セット（Ｒ１）およびトラックの第２の予備セット（Ｒ２）を含み得る。いくつかの実施形態では、トラックの第２の予備セット（Ｒ２）は、トラックの第１の予備セット（Ｒ１）のコピーである。追加として、いくつかの実施形態では、トラックの第２の予備セット（Ｒ２）を使用して、トラックの第１の予備セット（Ｒ１）内のエラーをチェックし得る。
【０１４９】
Ｒ１は、ホストの開始に対する中心点として機能するように構成され得る。従って、ホストは、Ｒ１に送信するパラメータを選択し得る。メディエータは、この情報をホストから直接に、またはマネージャを通して間接的に、受信し得る。Ｒ２は、好ましくは、決してホストに公開されない。従って、メディエータ自身またはマネージャのみが情報をＲ２に格納できる。Ｒ１およびＲ２の各々は、例えば、１６のセクターを含み得、ホスト修飾子などの実際のデータで充填され得る。慣例により、番号付けは、０から始まり得る。従って、Ｒ１は、例えば、セクター（またはトラック）０〜１５を含み得、Ｒ２は、セクター（またはトラック）１６〜３１を含み得る。しかし、メディエータは、Ｒ１およびＲ２の各々が、１６トラックの初期サイズを超えて拡張するのを可能にするように構成され得る。
【０１５０】
いくつかの実施形態では、Ｒ１は、一意の予備セクター情報およびパーティション情報を含む。パーティション情報内には、ファイルシステム情報を格納し得る。
【０１５１】
限定されない例として、また、当業者であれば分かるように、ボリュームをＮＦＴＳファイルシステムでフォーマットする際に、＄ＭＦＴ（マスターファイルテーブル）、＄Ｂｉｔｍａｐ、＄Ｌｏｇ  Ｆｉｌｅおよびその他などの、メタデータファイルを作成する。このメタデータは、ＮＦＴＳボリューム上の全てのファイルおよびフォルダに関する情報を含む。ＮＴＦＳボリューム上の第１の情報は、パーティションブートセクター（＄Ｂｏｏｔメタデータファイル）であり得、セクター０に配置され得る。このファイルは、基本ＮＴＦＳボリューム情報およびメインメタデータファイル＄ＭＦＴの位置を記述し得る。
【０１５２】
フォーマットプログラムは、＄Ｂｏｏｔメタデータファイルに対して最初の１６セクターを割り当てる。最初のセクターは、ブートストラップコードを有するブートセクターであり、次の１５のセクターは、ブートセクターのＩＰＬ（初期プログラムローダー）である。
【０１５３】
Ｒ１およびＲ２のトラックに加えて、メディエータは追加のメタデータを格納し得る。このメタデータは、例えば、シンプロビジョニングストラテジの実行を可能にする情報に対応し、それは、装置が、実際に利用可能であるよりも多くの物理的資源を有しているように見えるのを可能にして、例えば、トラック３２〜３９であり得る、Ｒ２の後の８トラック内に含まれ得る。メタデータは、ＬＵＮ  ＱｏＳ、ＶＭおよびＷＯＲＭなどの特徴も提供し得る。
【０１５４】
いくつかの実施形態では、システムはＳＡＮインデクサを含み得る。ＳＡＮインデクサは、何がＲ１およびＲ２内にあるかをチェックして、その情報を抽出し得る。この情報は、例えば、テキスト検索により、容易に検索され得るデータベースに入れることができる。
【０１５５】
ビットフィールド
【０１５６】
メディエータは、ビットフィールドに対応する情報も含むか、または包含し得る。ビットフィールドは、データが記憶媒体内の物理的にどこに格納されているかを示す情報を含み、メタデータがトラック３２〜３９に置かれている場合、ビットフィールドのセクター番号はトラック４０から始まり得る。ホストのファイル名とデータの位置との間の相関関係が格納されているのはメディエータのビットフィールド内である。従って、それは、セクターマップを含むか、基本的にそれから成るか、またはそれから成り得る。メディエータのビットフィールド構成要素からのこの情報は、任意の装置上での実際の空間節約を判断するために使用され得る。例えば、節約される空間の割合＝１−［（実際に使用される空間）／（ホストによってマップされている空間）］である。いくつかの実施形態では、本発明の方法に従ったデータ変換によって節約される空間は、少なくとも５０％、少なくとも６０％、少なくとも７０％、または少なくとも８０％である。これらの節約は、ファイル当たりであるか、または装置上の全てのファイルにわたる平均値であり得る。
【０１５７】
事実上、好ましくは、メディエータは、ファイルデータが格納されているディスクまたは記録媒体上に置かれていない。加えて、好ましくは、メディエータは、対応するディスクまたは記録媒体の総メモリの約０．１〜０．２％のみを必要とする。
【０１５８】
空間の節約から経済的価値を提供することに加えて、本発明の様々な実施形態は、データの整合性を保護しようとする際に、効率の向上に対してドアを開く。その結果、本発明の様々な実施形態は、データのバックアップに対する新規で非自明の技術を提供する。
【０１５９】
多くの実施形態では、格納されたファイルは、ホストから受信したとおりの生データファイルより小さいので、それに対して必要な記憶空間が少ない。従って、ファイルの再作成に必要なデータは、ホストが使用されていると認識し、かつ第１のアドレスが示唆するよりも小さい位置に格納できる。ファイルが格納されている実際の位置は、第２の記憶アドレスと呼ばれ得る。従って、各ファイルに対して、ファイルが格納されているとホストが信じる、第１の記憶アドレス、およびコード化ファイルが実際に格納されている、第２の記憶アドレスがある。
【０１６０】
１つ以上のブロックに対応し得る、所与のファイルに対して、第１の記憶アドレスおよび第２の記憶アドレスが、記憶装置内の同じブロックまたはブロックの１つ以上の重なり合うセットに配置されることが可能である。しかし、好ましくは、ファイルの、少なくとも１つ、少なくとも５０％、少なくとも６０％、少なくとも７０％、少なくとも８０％、少なくとも９０％、または１００％に対して、第１の記憶アドレスおよび第２の記憶アドレス内に重なり合うブロックがない。加えて、たとえホストが、メディエータが認識するのと同じ記憶アドレスを認識しても、データがコード化される際に、ホストは、まずデータを復号することなく、ファイルを再作成できない。いくつかの実施形態では、ホストは、コードを認識せず、従って、格納されたデータを復号できない。
【０１６１】
いくつかの実施形態では、メディエータは、ファイルに対応するチャンクレット（複数可）を受信して、それらをＬ１またはＬ２キャッシュ内に一時的に格納し得る。Ｌ２キャッシュが存在する場合、Ｌ２キャッシュは、受信をホストに対して確認し得、任意選択で、第１の記憶アドレスをホストに提供するか、または確認し得る。当業者であれば認識するように、受信の確認および第１の記憶アドレスの伝送が、第２の記憶アドレスにおける格納の前に、かつ符号化が実行される場合は、符号化の前または後に、行われ得る。確認がいつ送信されるかに関わらず、ファイルの実際の記憶アドレスと仮想記憶アドレスの相関関係が、好ましくは、ビットフィールド内で追跡される。
【０１６２】
データのバックアップ
【０１６３】
ある実施形態では、データのバックアップを容易にするために２つのメディエータを使用し得る。例えば、第１のメディエータでは、第１のセクター内に格納されるデータファイルまたは第１の記録媒体上の第１のセクタークラスタをファイル名と相互に関連付け得る。前述のように、第１のメディエータは、ファイル名を識別するユーザーまたはエンティティがデータファイルを記録媒体から取得するのを可能にするように構成される。
【０１６４】
第２のメディエータを生成する、データ保護プロトコルが実行され得る。第２のメディエータは、時間Ｔ１における第１のメディエータの正確なコピーであろう。従って、Ｔ１において、第１のメディエータおよび第２のメディエータの両方は、第１の記録媒体上の同じセクターまたはセクタークラスタ（およびその中の位置）を指す。
【０１６５】
時間Ｔ１の後、例えばＴ２において、ホストは、所与のセクターまたはセクタークラスタ上の所与の位置内に格納されているファイルを更新しようとし得る。ホストは、第１の記憶アドレスに格納されたデータを変更しない。セクターまたはセクタークラスタ上の情報を上書きさせるのではなく、第１のメディエータは、新しい情報を、異なるセクターまたはセクタークラスタ内の位置に対応する第３の記憶アドレスに書き込ませて、ファイル名および第１の記憶アドレスをこの新しい記憶アドレスと相互に関連付け得る。
【０１６６】
このように、たとえ、情報が特定の記憶アドレスにおいて上書きされているとホストが信じても、第１のメディエータは、新しいセクターまたはセクタークラスタを指す。それに応じて、ホストは、そのアドレスをセクタークラスタに対して更新する必要がない。
【０１６７】
第２のメディエータは更新されずに、ファイル名を、そのファイルが格納された第１の位置と継続して相互に関連付ける。２つのメディエータのこの使用は、ファイルが、Ｔ１およびＴ２の両方において存在していたとおりに格納されていることを示すように、ホストに、そのファイルシステムを更新させる必要なく、データがＴ１において存在するとおりにそのデータのスナップショットを提供するのを可能にする。従って、スナップショットは、時間Ｔ１において格納されている全てのデータファイルをロックして、いずれも、それらの物理ファイルを通して削除または書込みが行われるのを防ぐ。しかし、ホストがそれらのファイルを修正したい場合、実際には新しいファイルが格納されているときに、ホストは、それを行っていると思い込んで動作できる。この方法は、セクターおよびセクタークラスタと関連して記述される。しかし、それは、セクターまたはセクタークラスタ内に配置されていない非キャッシュ媒体でも動作するであろう。例えば、それらは、ＬＵＮ内のＬＢＡによって編成され得る。
【０１６８】
上で示唆するように、この方法は、第１のメディエータ、第２のメディエータおよび非キャッシュ媒体を含むシステムによって実装され得る。第１のメディエータ、第２のメディエータおよび記録媒体の各々は、持続性媒体を含むか、基本的にそれから成るか、またはそれから成り得る、別個の装置上に格納され得るか、または別個の装置から形成され得る。前述のシステムは、同じ記録媒体の異なるセクターの使用を詳述するが、異なる記録媒体の異なるセクターに書き込むことによっても使用できる。加えて、システム内で、メディエータおよび記録媒体は、互いに、ならびに任意選択で、命令を格納する１つ以上のコンピュータまたはＣＰＵに、動作可能に結合されて、それらに、それらの意図する機能を実行させ、ネットワークを経由して、１つ以上のホストへ１つ以上のポータルを通して通信させる。さらになお、この実施形態は２つのメディエータの使用と関連して説明されているが、２つの別個のメディエータではなく、同じメディエータの２つのセクションを使用するシステムを実装できる。
【０１６９】
システムは、ロックモジュールとともにさらに構成され得る。ロックモジュールは、ある時間において書き込まれている１つ以上のブロックにおける修正、上書き、または削除を防ぎ得る。ロックモジュールは、新しいブロックの書込みおよび、ロックされていないそれらの新しいブロックの修正を可能にするように設計もされ得る。従って、ロックモジュールは、ホスト、ユーザーまたはシステム管理者が、ある時間において書き込まれているあるブロックを選択するか、またはある時間において書き込まれている全てのブロックが上書きされないように選択するのを可能にするように構成され得る。
【０１７０】
さらに、デフォルト設定により、ファイルの取得および修正、上書きまたは削除に対する全ての要求を第１のメディエータを通じて送信する選択モジュールがあり得る。選択モジュールは、ロック技術が適用された時間における１つ以上のファイルの古いバージョンであるとホストが信じ得るものの復旧を可能にするように構成もされ得る。任意選択で、選択モジュール全体へのアクセスが、権限を有する人、例えば、システム管理者に制限され得る。
【０１７１】
データをバックアップするための前述のシステムが、２つのメディエータのコンテキストで説明される。しかし、格納されたファイルの履歴またはファイルのバージョンを捕捉するために３つ以上のメディエータが使用できる。例えば、少なくとも３つ、少なくとも４つ、少なくとも５つ、または少なくとも１０のメディエータなど、が使用され得る。追加として、ホストは、メディエータに、一定の間隔で（例えば、毎週、毎月、３か月ごともしくは毎年）または不規則な間隔で（例えば、要求に応じて）、スナップショットを取らせ得る。
【０１７２】
データをバックアップするための別の方法によれば、非キャッシュ媒体のクローンが作成され得る。この方法では、第１のメディエータ内で、複数のファイル名を、非キャッシュ記憶媒体上に格納されている複数のデータ位置と相互に関連付ける。第１のメディエータは、特定のファイル名を識別するユーザーが、特定のファイル名に対応する第１の非キャッシュ記憶媒体からデータファイルを取得するのを可能にするように構成されている。特定ファイルの一部または全体が、第１のセクターまたはセクタークラスタ内に格納され得る。
【０１７３】
複数のデータファイル（または第１の非キャッシュ記憶媒体の全てのデータファイル）のコピーを第２の非キャッシュ記憶媒体および第２のメディエータに対して作成し得る。第２のメディエータは、時間Ｔ１における第１のメディエータのコピーであり、第２の非キャッシュ記憶媒体に動作可能に結合されている。Ｔ１の後である、時間Ｔ２において、システムは、第１の非キャッシュ記憶媒体上の前記第１のセクターまたはセクタークラスタ内に格納されているデータファイルに、修正を保存し得る。しかし、第２の非キャッシュ媒体上の対応する位置に対する変更は行われない。ユーザーがＴ２の後にファイルを要求すると、彼または彼女は、第１のメディエータを経由して、直前に格納されたファイルのバージョンを取得するであろう。しかし、システム管理者は、第２の非キャッシュ媒体上に格納されて、第２のメディエータを経由することにより取得し得た、前のバージョンにアクセスしていたであろう。
【０１７４】
この方法は、第１のメディエータ、第２のメディエータ、第１の非キャッシュ記憶媒体および第２の非キャッシュ記憶媒体を含む、システムによって実装され得る。第１のメディエータ、第２のメディエータならびにデータファイルを格納するための第１および第２の記録媒体の各々は、持続性媒体を含むか、基本的にそれから成るか、またはそれから成り得る、別個の装置上に格納され得る。追加として、第１のメディエータは、ホストから導出されるファイル名を、第１の記録媒体の第１のＬＵＮと相互に関連付け、第２のメディエータは、同じファイル名を、第２の記録媒体上の第２のＬＵＮと相互に関連付ける。いくつかの実施形態では、第１の非キャッシュ媒体内に格納されている、最新のファイルは、従来のファイルが第２の非キャッシュ媒体内に有するのと同じＬＵＮを有する。
【０１７５】
データ取得
【０１７６】
本発明の方法のいずれかによれば、変換された形式で格納されている任意のデータは、それをホストに返す前に、取得されて復号されることが可能である。変換されたデータを取得すること、前述の参照テーブルまたは頻度変換器にアクセスすること、ならびに均一のビット列およびチャンクレットに変換して戻すことを可能にする１つ以上のアルゴリズムの使用を通じて、ファイルがホストのために再作成できる。限定されない例として、データが変換されて、１つのマーカーがどこで終わるかの指示（例えば、一意のビット列の使用または均一サイズのマーカーの使用を通じて）を含むフォーマットで格納されている可能性がある。
【０１７７】
格納されたとおりのデータの取得は、現在知られているかまたは知られるようになり、かつ当業者が、本発明と関連して利用されるとして理解する、プロセスおよび技術を通し得る。任意選択で、マネージャは、ファイルの格納および取得を調整する。いくつかの実施形態では、マーカーなどのＮＣＭからのデータは、並列処理を通して取得される。
【０１７８】
一方法では、記録媒体にアクセスすることにより始まる。記録媒体は、複数のマーカーを順番に格納して、これらのマーカーからファイルを再作成できる。アクセスは、ファイルの取得を要求して、その要求をストレージエリアネットワークに伝送するホストによって、またはストレージエリアネットワークの管理者によって開始され得る。
【０１７９】
データが、メディエータ（存在する場合）によって識別される位置から記憶媒体から取得された後、データが変換されている場合は、複数のマーカー（または頻度変換器を通して変換されているデータ）を、Ｉ／ＯストリームまたはＩ／Ｏストリームのフラグメント化ユニットに変換して戻されるチャンクレットまたはハッシュ値を形成するために使用され得るビットに翻訳する。マーカーは、各マーカーがチャンクレットに対応するか、または各マーカーがサブユニットに対応して、複数のサブユニットが結合されてチャンクレットを形成し得るように、格納され得る。格納されたフォーマットでは、マーカーは、所望の文書またはファイルの再作成を可能にする方法で、チャンクレット（またはハッシュ値）内のビットの再作成およびチャンクレット（またはハッシュ値）の順序の再作成を可能にする順序で配置される。
【０１８０】
データが変換される場合は、マーカーをチャンクレットに翻訳するために、ビットマーカーテーブルまたは頻度変換器にアクセスし得る。ビットマーカーテーブルまたは頻度変換器内では、各一意のビット列またはファイル内の各一意のビット列と関連付けられている一意のマーカーがあり得る。テーブルが、テーブル２に類似したフォーマットで編成されている場合、翻訳後、各サブユニットおよびチャンクレットが同じサイズを有するために、ゼロが追加され得る。復号時に、ビットマーカーテーブルまたは頻度変換器を、コード化のためにこれを使用するのとは逆に使用する。任意選択で、同じテーブルを使用して、入力および出力を逆転する代わりに、別個のテーブルを使用し得る。
【０１８１】
他の実施形態と同様に、各チャンクレットはＮビット長であり得、Ｎは１よりも大きい整数であり、また、各サブユニットはＡビット長であり、Ａは整数である。マーカーをチャンクレットに翻訳するために、ビットマーカーテーブルまたは頻度変換器にアクセスし得る。
【０１８２】
チャンクレットが形成された後に、文書がそれから再構成できるバイナリデータに対応する出力を有する。任意選択で、ファイルをファイルタイプと関連付け得る。例えば、ホストはＭＩＭＥ変換器を追跡して、返す際にそれをファイルと再度関連付け得る。ファイルタイプは、データの受信者に、それをオープンするためにどのオペレーティングシステムを使用すべきかを知るように指示する。当業者であれば認識するように、ストレージエリアネットワークは、ファイルタイプを追跡する必要がなく、いくつかの実施形態では、行わない。
【０１８３】
チャンクレットが形成された後に、いくつかの実施形態では、ファイルがそれから再構成できるバイナリデータに対応する出力を有する。他の実施形態では、変換されたデータは、ハッシュ値に対応し、ハッシュ値はまず、Ｉ／Ｏストリームのフラグメント化ユニットまたはＩ／Ｏストリーム自体を作成するために使用される必要がある。
【０１８４】
切り捨てられたデータに関しては、ビットマーカーテーブルまたは頻度変換器を利用する必要がない場合でさえ、データを取得し得る。記録媒体をアクセスすることによりそれを行い得、記録媒体は、複数のデータユニットを複数の位置に格納し、各データユニットは、複数のビットを含み、データユニットの最大サイズは第１のビット数であり、少なくとも１つのデータユニットは、第２のビット数を含み、第２のビット数は第１のビット数よりも小さい。
【０１８５】
次に、データユニットを取得して、１つ以上のビット、例えば、０を、Ｎビット長よりも少ない任意のデータユニットの端部に追加して、データユニットに対応するチャンクレットのセットを生成し得、各チャンクレットは、同じビット数を含み、データユニットの順番に対応する順番にチャンクレットのセットを含む出力を生成する。切り捨てられたデータがゼロを除去することにより形成された場合には、データを取得する際に、ゼロを追加して戻すであろう。加えて、格納されたデータユニットがチャンクレットのサブユニットであった場合、システムはまず、均一サイズのサブユニットを生成するために、切り捨てられたサブユニットにゼロを追加して戻し、次いでサブユニットを結合してチャンクレットを形成し得る。
【０１８６】
ルックアップテーブルが使用される場合には、それは、好ましくは、コンピューティング装置のメモリ内に格納される。いくつかの実施形態では、ルックアップテーブルは静的であり、マーカーは事前に決められている。従って、１つ以上の異なる文書タイプの複数の文書を長期間にわたって格納している場合、同じテーブルが使用され得る。任意選択で、それは、ホストの位置に、またはストレージエリアネットワークの一部として、格納され得る。
【０１８７】
ホストからのデータの受信
【０１８８】
様々な実施形態をさらに詳しく説明するため、およびコンテキストを提供するために、以下で、使用し得る特定のハードウェアが参照されるが、ハードウェアは、組み合わされて、本発明の方法を実装するためのシステムを形成する。ハードウェアは、前述のプロセスが自動化されて、１つ以上のデータファイルをホストから受信すると、１つ以上のプロセッサによって制御されるのを可能するように構成され得る。
【０１８９】
いくつかの実施形態では、ホストは、第１の位置において任意の方法で、文書およびコンピュータファイルを生成し得る。文書は、ホストのオペレーティングシステムによって生成されて、ホストのファイルシステムによる格納のために編成される。ホストのオペレーティングシステムは、そのメモリ内にローカルに、ファイル名を格納し得る。本発明は、オペレーティングシステムのタイプまたはホストが使用するファイルシステムによって制限されない。限定されない例として、ホストは、以下のハードウェア構成要素：メモリ、記憶装置、入力装置、出力装置、グラフィックユーザーインタフェース、１つ以上の通信ポータル、および中央処理装置、の１つ以上を有する、ネットワーク内のコンピュータまたはコンピュータのセットを含み得る。
【０１９０】
その第１の位置において、ＳＡＰは、文書またはファイルと相互に関連付けるデータを格納するためのプロトコルを実行する。ＳＡＰは、データをＩ／Ｏストリームまたは、例えば、サイズが４Ｋのチャンクレットにフォーマットする。
【０１９１】
データは、ＳＡＮを経由して、１つ以上のモジュールを有するコンピュータもしくはネットワークに、またはデータを受信するように構成されているコンピュータもしくはコンピュータのセットに送信され得る。この受信コンピュータは、以下のハードウェア構成要素：メモリ、記憶装置、入力装置、出力装置、グラフィックユーザーインタフェース、中央処理装置、ならびに１つ以上のホストおよび１つ以上の記憶装置とローカルに、および／またはネットワークを経由して、情報の通信を可能にするように構成されている、１つ以上の通信ポータル、のうちの１つ以上を含み得る。
【０１９２】
加えて、実行可能コンピュータコードを、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組合せ上に格納する、コンピュータプログラム製品があり得る。コンピュータプログラム製品は、本発明の方法を実施するように構成されている１つ以上のモジュールに分割されるか、またはそれらと通信可能であり得、１つ以上の持続性媒体内に格納され得る。
【０１９３】
例えば、レベル１（Ｌ１）キャッシュおよびレベル２キャッシュ（Ｌ２）があり得る。当業者であれば承知のとおり、キャッシュ技術の使用は、慣例的に、データ格納における効率の向上を可能にしてきた。本発明では、例として、データがＳＡＮを経由してキャッシュに送信され得、データは、ハッシュ関数アルゴリズムにアクセスする前、ビットマーカーテーブルを調べる前、頻度変換器を調べる前、およびビットを切り捨てる前、ならびに／またはハッシュ関数アルゴリズムを調べた後、ビットマーカーテーブルを調べた後、頻度変換器を調べた後、およびビットを切り捨てた後に、キャッシュに送信され得る。
【０１９４】
セクターサイズが５１２Ｂであると仮定して、サイズが４Ｋである各チャンクレットに対して、ホストは、８セクターの記憶装置が使用されると予期するであろう。
【０１９５】
システム
【０１９６】
本発明の様々な実施形態は、データ記憶および取得システムを提供する。一実施形態では、システムは、非キャッシュデータ記憶媒体、メディエータおよびマネージャを含む。これらの要素間、および任意選択で、イニシエータとの通信は、有線、無線またはそれらの組合せのネットワークを経由し得る。
【０１９７】
非キャッシュデータ記憶媒体は、例えば、１つ以上のディスクまたはソリッドステートドライブを含むか、基本的にそれらから成るか、またはそれらから成り得る。使用時に、非キャッシュデータ記憶媒体は、本発明の方法の１つ以上に従って処理されていないファイルと比べて、少なくとも５０％、少なくとも６０％、少なくとも７０％、または少なくとも８０％の空間節約で、ファイルを格納し得る。
【０１９８】
メディエータは、トラックの第１のセット、トラックの第２のセット、トラックの第３のセット、およびトラックの第４のセット：のトラックの４つのセットを含むか、基本的にそれらから成るか、またはそれらから成り得る。メディエータは、好ましくは、持続性媒体上に格納されて、非キャッシュデータ記憶媒体からリモートに配置される。従って、メディエータおよび非キャッシュデータ記憶媒体は、好ましくは、同じ装置の一部ではない。
【０１９９】
システムは、マネージャも含み得る。マネージャは、受信の制御、格納および取得の処理、ならびにメディエータを通じたデータの伝送を提供し得る。それ故、マネージャは、好ましくは、ホストおよびメディエータに動作可能に結合され、任意選択で、非キャッシュデータ記憶媒体に動作可能に結合される。さらに、いくつかの実施形態では、マネージャは、メディエータ、非キャッシュ媒体およびホストの各々からリモートに配置される。
【０２００】
マネージャは、以下の機能：（ａ）ファイルシステム情報、ブート可能性情報、およびパーティション情報の１つ以上を含むデータをメディエータのトラックの第１のセット内に格納すること、（ｂ）メタデータをメディエータのトラックの第３のセット内に格納すること、（ｃ）１つ以上のファイルを非キャッシュ媒体上に格納することであって、１つ以上のファイルが非キャッシュ媒体上に、ファイルシステム情報、ブート可能性情報、およびパーティション情報のいずれもなしで保存される（従って、いくつかの実施形態では、生データのみが非キャッシュ媒体上にある）、１つ以上のファイルを非キャッシュ媒体上に格納すること、（ｄ）メディエータのトラックの第４のセット内に、非キャッシュ媒体内の各ファイルの位置を格納すること、ならびに（ｅ）非キャッシュ媒体内の各ファイルの位置の、ファイルに対するホスト名との相関関係をメディエータ上に格納すること：の１つ以上を実施するように構成され得る。好ましくは、非キャッシュ媒体内の各ファイルの位置の、ファイルに対するホスト名との相関関係が、トラックの第４のセット内に格納され、それは、ビットフィールドに対応する。加えて、マネージャは、本発明の方法の１つ以上を実行することが可能な実行可能命令を含むコンピュータプログラム製品を含むか、またはそれに動作可能に結合され得る。
【０２０１】
本発明の様々なシステム内で、ＳＡＮは、コンピュータプログラム製品内に格納された指示に従って、ビットマーカーテーブルまたは頻度変換器にアクセスし得る。これらの資源は、ビットマーカーをサブユニットの各々と相互に関連付けて、出力を生成する。ビットマーカーの、全部ではないが、ほとんどが、サブユニットよりもサイズが小さいので、出力は、ホストから受信された入力ファイルよりも小さいデータファイルである。従って、ホストから受信されたとおりのファイルがサイズＲであり得、一方、ＳＡＮによって保存されたとおりの実際のデータがＳであり得、Ｒ＞Ｓである。好ましくは、ＲはＳの少なくとも２倍の大きさであり、さらに好ましくは、ＲはＳの少なくとも３倍の大きさである。
【０２０２】
ＳＡＮは、出力ファイルを受け取って、それを持続性記憶媒体、例えば、非キャッシュ媒体内に格納する。好ましくは、ＳＡＮは、格納されたとおりのファイルを、ホストから受信されたとおりのファイルと相互に関連付けて、ホストがファイルを取得できるようにする。
【０２０３】
さらに詳細な説明のために、本発明の方法を実装するためのシステムを示す、図１が参照され得る。システム１０において、ホスト１は、メモリ４に動作可能に結合されているプロセッサ３を含む、ストレージエリアネットワーク６にファイルを送信する。任意選択で、ストレージエリアネットワークは、受信の確認をホストに返す。
【０２０４】
メモリ内に、チャンクレットを取得して、その中に含まれるデータをサブユニットに分割するように設計されているコンピュータプログラム製品が格納される。メモリは、参照テーブル５も含むか、またはそれに動作可能に結合され得る。テーブルは、ビットマーカーもしくは頻度変換器またはサブユニットの１つ以上に対する相関ファイルを含み、コンピュータプログラム製品は、元のサブユニットの代わりに１つ以上のマーカーを含む、新しいデータファイルを作成する。
【０２０５】
プロセッサは次に、ビットマーカーを、非キャッシュ媒体などの、記録媒体（例えば、ディスク２であり得る）上に格納させる。いくつかの実施形態では、当初は、マーカーの全てが同じサイズである。しかし、いくつかの実施形態では、それらを格納する前に、１つ以上、好ましくは、少なくとも２５％、少なくとも５０％、または少なくとも７５％が、格納前に切り捨てられる。
【０２０６】
図２は、Ｒ１  ４０およびＲ２  ５０、ならびに、ビットフィールド６０およびメタデータファイル３０のための空間を含む、メディエータ７０を有するシステム１００を示す。メディエータの表現は、例示のみを目的としており、メディエータの構造またはその中の編成に制限を課さない。非キャッシュ媒体（ＮＣＭ）２０も示されている。非キャッシュ媒体は、メディエータの近くに示されているが、それらは別個の構造である。いくつかの実施形態では、メディエータはＮＣＭから離れた装置に置かれ、本発明の装置の１つ以上が可搬式である。マーカーまたは他の変換された生データがＮＣＭ上に格納される。
【０２０７】
図３は、別のシステム２００を示す。このシステムでは、イニシエータ（Ｉｎ）２７０がチャンクレットをキャッシュマネージャ２３０に伝送し、キャッシュマネージャ２３０は、任意選択で、データファイルのコード化を準備して、それらをメディエータ２１０に伝送する。ホストの例は、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）  Ｓｅｒｖｅｒ  ａｎｄ  Ｄｅｓｋｔｏｐ、Ａｐｐｌｅ  ＯＳ  Ｘ、Ｌｉｎｕｘ（登録商標）  ＲＨＥＬ、およびＳＵＳＥ  Ｏｒａｃｌｅ  Ｓｏｌａｒｉｓ、ＩＢＭ  ＡＩＸ、ＨＰ  ＵＸならびにＶＭ  ＥＸＳおよびＥＳＸｉを実行するコンピュータまたはコンピュータネットワークを含むが、それらに制限されない。データファイルに対応する情報が、当初は、Ｒ１  ２４０に送信されるが、それは、以前はイニシエータが定義したパラメータが投入されていた。メディエータ自体は、ビットマーカーテーブルまたは頻度変換器（図示せず）の使用を通して情報を翻訳し得るか、またはリモート符号器（リモート変換器とも呼ばれ得、図示せず）と通信し得、また、メディエータはＲ１内ならびにＲ２  ２５０内に、ホストから受信されるファイル名のコピーを格納する。データが変換されて、もっと小さいサイズのファイルが作成された後、ビットフィールド２６０のセクターマップ内に、ファイルがディスク２２０内に格納される位置または複数の位置が記録される。コード化されたデータが位置２８５に格納され得る。データのコード化前またはデータのコード化の代わりに、ハッシュ値アルゴリズムがアクセスされ得、チェックサムが格納または変換のために使用され得る。
【０２０８】
図４は、図３のシステムの実施形態の変形形態であり、記憶装置のバックアップを提供する、別のシステム３００を示す。このシステムでは、イニシエータ３７０が、チャンクレットをキャッシュマネージャ３３０に伝送し、キャッシュマネージャ３３０は情報を、データを含む第１のメディエータ３１０に転送して、図３に対して送信された同じファイルを修正する。修正されたファイルの受信前またはその受信後のいずれかであるが、それを非キャッシュ媒体内に格納する前に、第２のメディエータ３８０が第１のメディエータ３１０から作成される。第２のメディエータは、それが作成された時における第１のメディエータの正確なコピーであり、ファイル名に対しては、その時、非キャッシュ媒体３２０内の同じセクター（またはセクタークラスタ）３８５を指す。
【０２０９】
第１の修正されたファイルが、第１のメディエータのＲ１  ３４０で受信される。第１のメディエータは、この場合もやはり、ビットマーカーテーブルまたは頻度変換器（図示せず）の使用を通して情報を翻訳するか、またはリモート符号器と通信するかのいずれかであろう。メディエータは、Ｒ１内ならびにＲ２  ３５０内に、ホストから受信されるファイル名のコピーを継続して格納する。データが変換されて、もっと小さいサイズのファイルが作成された後、第１のメディエータのビットフィールド３６０のセクターマップ内に、ファイルがディスク３２０内に格納される位置が記録される。しかし、修正されたファイルは異なるセクター３９５内に格納される。従って、第１のメディエータに対する変更は、第２のメディエータに対しては行われないであろう。
【０２１０】
ホストは、デフォルト設定により、第１のメディエータと通信する。従って、ホストがファイルを記憶装置から呼び戻したい場合、第１のメディエータが、そのデータをセクター３９５から呼び戻すであろう。ホストまたはシステム管理者がデータの以前のバージョンを取得したい場合には、ファイル名を、セクター３８５を目指す、第２のメディエータに投入し得る。
【０２１１】
本発明の別の実施形態によれば、以前にメタデータを本発明のシステムに（例えば、オペレーティングシステム情報、ブート可能性情報、パーティション情報、文書タイプ情報ＱｏＳ情報など）提供しているイニシエータは、文書に対応するビットをキャッシュマネージャに送信する。ビットは、例えば、チャンクレットに編成され得る。
【０２１２】
キャッシュマネージャは、情報をＬ１キャッシュに、Ｌ２キャッシュに、およびメディエータに送信し得る。キャッシュマネージャは受信の確認もイニシエータに送信し得る。
【０２１３】
その上に格納された関連メタデータを既に有し得る、メディエータは、文書に対応するビットを変換器に送信し、変換器は、ビットをコード化情報に変換する。変換器と関連付けられているか、またはその一部は、計算機でもあり得、それは、変換されたビットのサイズを判断する。変換は、例えば、ビットマーカーテーブルまたは頻度変換器の使用を通し得る。
【０２１４】
変換器は次いで、メディエータに、変換されたファイルのサイズを示し、メディエータは、変換されたファイルが非キャッシュ媒体内に格納される位置を判断し得る。このステップに続いて、メディエータはその位置に格納させ得る。
【０２１５】
本明細書で説明する様々な実施形態の特徴のいずれも、特別の定めのない限り、開示する任意の他の実施形態に関連して説明する特徴と併用できる。従って、様々な、または特定の実施形態に関連して説明する特徴は、かかる排他性が明記されていないか、またはコンテキストから暗黙的でない限り、本明細書で説明する他の実施形態に関連して適切でないと解釈されるべきでない。
【０２１６】
例
【０２１７】
例１：ビットマーカーテーブル（予測的）
【０２１８】
参照ロケータテーブル内で、各一意のマーカーが、一意のビット列に対応するとして識別される。テーブルは、テーブル格納用として一般に知られているか、または知られるようになり、かつコンピュータアルゴリズムが、各入力に対して割り当てられている出力を取得するのを可能にする、任意のフォーマットで格納され得る。
【０２１９】
以下のテーブルＩは、サブユニットが８ビット長である、ビットマーカーテーブルからの抜粋例を提供する。
【０２２０】
【表１】
2018152126.tif 000003
【０２２１】
例として、テーブル１で識別されたサブユニットを使用して、入力が０００００１０１  ０００００１００  ０００００１０１  ０００００１０１  ０００００００１である場合、出力は：１０１０  １０００  １０１０  １０１０  ０１０１であろう。ビットマーカー出力がサブユニット入力よりも小さい場合、それは記憶媒体上で少ない空間しか占めず、それによりビットの格納に必要な記憶空間および時間の両方を節約する。
【０２２２】
当業者であれば認識するように、テーブル１を生成するために抜粋されたものなどの所与のビットマーカーテーブルでは、ビットの全ての組合せが使用される場合、２Ｎのエントリが必要であり、Ｎは、サブユニット内のビット数に対応する。８ビットがある場合には、２５６のエントリが必要とされる。サブユニット内に１６ビットがある場合は、２１６のエントリが必要であり、それは６５，５３６のエントリに等しい。サブユニット内に３２ビットある場合は、２３２のエントリを必要とし、それは４，２９４，９６７，２９６のエントリに等しい。あるビット列がファイル内で使用されないことが分かっている場合には、テーブルは最小のものから始まるマーカーを割り当て得る。
【０２２３】
例２：前処理されたサブユニットのためのビットマーカーテーブル（予測的）
【０２２４】
サブユニットサイズが大きくなるにつれて、テーブルがより煩雑になるので、いくつかの実施形態では、テーブルは、サブユニット列の１つの端部から全てのゼロが欠落するように構成され得、テーブルにアクセスする前に、各サブユニットのその端部から全てのゼロが除去される。従って、テーブル１がそれから抜粋されるテーブルではなく、テーブル２が抜粋されるテーブルが構成され得る。
【０２２５】
【表２】
2018152126.tif 000004
【０２２６】
このように、第２行および第４行で、サブユニットが前処理された後、それらは８ビットより少ないビットを有した。しかし、ホストから受信した生データ内の実際のサブユニットは全て、８ビットを有した。方法が実装されるシステムは、桁の欠如はゼロを暗示しており、全ての桁の欠如は、任意の切り捨てられたサブユニットの同じ端部においてであると理解するように設計できるので、少ない空間を占めて、一意のマーカーを一意のサブユニットに割り当てる能力を保持するテーブルを使用できる。従って、方法は、システムが０００００００１（７つのゼロと１つの１）および００００００１（６つのゼロと１つの１）を異なるとして解釈するのを可能にする。
【０２２７】
この方法を実装するために、各サブユニット（または、サブユニットが使用されていない場合には各チャンクレット）が第１の端部および第２の端部を有すると考え得る。第１の端部は、ビット列の右側または左側のいずれかにでき、第２の端部はその反対側であろう。説明のために、第１の端部を左端の桁と、また、第２の端部を右端の桁と考え得る。この方法の下で、次いで、各チャンクレットの各サブユニット内の１つ以上のビットを分析して、第２の端部にあるビットが値０を有するかを判断する。このステップは、前処理と呼ばれ得、前処理された後のサブユニットは、テーブル２の右側の列に現れる。第２の端部におけるビットが値０を有する場合、本方法は、第２の端部におけるビットおよび値０を有して、そのビットとともに連続的なビット列を形成し得る全てのビットを除去し、それにより、元は第２の端部に０を有していた任意のサブユニットに対して、修正されたサブユニット（テーブル内の前処理されたサブユニット）を形成する。
【０２２８】
各サブユニットを再検討して第２の端部に０があるかどうかを判断し、そうである場合は０を除去して前処理されたサブユニットを形成するアルゴリズムを使用し得、前処理されたサブユニットは、サブユニットの第２の端部に隣接していた位置に、修正された第２の端部をもつ修正されたサブユニットとも呼ばれ得る。次に、アルゴリズムは、修正されたサブユニットを再検討して、その現在の修正された第２の端部において０があるかを判断し、そうである場合は０を除去して、さらに修正された第２の端部を形成する。この方法では、修正された第２の端部は、以前は、第２の端部におけるビットに隣接していた位置であろう。任意のさらに修正された第２の端部は、サブユニットの第２の端部から２つ以上離れた位置になっているであろう。従って、用語「修正された（ｒｅｖｉｓｅｄ）」は、短縮されたか、または切り捨てられた第２の端部を意味する。アルゴリズムは、この方法を、その第２の端部に１をもつ、短縮されたチャンクレットが生成されるまで、修正されたサブユニットに対して繰り返し得る。
【０２２９】
当業者であれば認識するように、前述の方法は、１が、修正された第２の端部またはさらに修正された第２の端部になるまで、ゼロを第２の端部から除去することにより、適用されていると説明されている。本方法は、０が、修正された第２の端部またはさらに修正された第２の端部になるまで、システムが１を第２の端部から除去するように、逆に設計され得る。加えて、本開示を用いて、当業者は、ビットを、第２の端部の代わりに、第１の端部から除去し、それらの修正されたサブユニットをビットマーカーに変換するために作成されたテーブルを使用し得る。
【０２３０】
例３：頻度交換（予測的）
【０２３１】
経験的分析に基づき、特定のホストから受信された文書もしくは文書のセットのタイプ内、または、所与の時間フレーム（例えば、過去１年または過去２年）内に受信されている文書のセット内からの、各サブユニットの頻度を判断できる。サブユニットが番号順に編成されているテーブル１またはテーブル２に例示するようなテーブルに頼るのではなく、この情報を用いて、さらに小さいビットマーカーが、ファイル内、文書のタイプ内、または特定のホストから受信したとおりの文書のセット内に、最も出現しそうであると予測されているサブユニットと関連付けられている頻度変換器に頼ることができる。従って、頻度変換器内で、マーカーは複数の異なるサイズであり、さらに小さいサイズのマーカーが、より高い頻度のサブユニットと相互に関連づけられる。
【０２３２】
【表３】
2018152126.tif 000005
【０２３３】
テーブル３は、テーブル１と同じサブユニットを使用する頻度変換器からの抜粋例である。しかし、ビットマーカーは順番に割り当てられておらず、代わりに、より大きなビットマーカーが低頻度のサブユニットに割り当てられていることに気付くであろう。テーブルに示すように、サブユニット００００００１１に割り当てられているマーカーは、サブユニット０００００００１に割り当てられているものよりも、２５パーセント大きく、サブユニット１１１１１１０１に対しては、高い数値であるにも関わらず、それは、特定のホストから受信したファイルのタイプ内により頻繁に出現するので、より小さいビットマーカーを受信する。従って、テーブル１を使用して、サブユニット１１１１１１０１が１０，０００箇所に出現する場合、それは１１１，１１１，０１０，０００ビットに対応するであろう。しかし、テーブル３を使用した場合には、同じ情報を格納する目的に対して使用するために、１１，０００，０００ビットが必要であろう。この方法には示していないが、サブユニットは、ゼロを一方の端部または他方から除去するために前処理でき、テーブルは相関する切り捨てられたサブユニットを含むように設計され得る。
【０２３４】
前述のように、頻度変換器は、１つ以上のホストから受信しそうなデータを代表すると考えられるファイルのセットの分析に基づき生成できる。いくつかの実施形態では、情報を処理するアルゴリズムは、それ自身の品質管理を実行して、所与の期間からの文書に対するサブユニットの実際の頻度を、頻度変換器内のマーカーの割当てが基づいているものと比較する。統計的分析を使用して、それは、次いで、将来の使用のために、どのようにマーカーがサブユニットと関連付けられているかを割り当てる、新しいテーブルが作成されるべきかを判断し得る。当業者であれば認識するように、テーブル３は、頻度変換器の単純化した抜粋である。しかし、実際には、相関関係を得るために１６進記数法を選択し得る。加えて、テーブルが基づく頻度の列挙は、読者の便宜のために含まれており、それらは、本発明の様々な実施形態によってアクセスされる際にテーブルに含まれる必要はない。
【０２３５】
例４：メディエータ内での空間の割当て（予測的）
【０２３６】
１ＭＢのサイズの仮説の記録媒体では、当業者は、セクターを次のようにマッピングし得る：
【０２３７】
１ＭＢの記録媒体は、１，０２４，０００バイトを有し、それは２５０セクターに対応する（１，０２４，０００／４０９６＝２５０）。記録媒体のジオメトリは、次のように要約され得る：ボリューム＝（ｃ＊ｈ＊ｓｐｔ＊ｓｓ）、ここで
【０２３８】
ｃ（シリンダー数）＝７；
【０２３９】
ｈ（ヘッド数）＝２５５；
【０２４０】
ｓｐｔ（トラックあたりのセクター）＝６３；および
【０２４１】
ｓｓ（バイト単位でのセクターサイズ）＝４０９６とする。
【０２４２】
メディエータ内では、セクターは次のように割り当てられ得る：
【０２４３】
【表４】
2018152126.tif 000006
【０２４４】
例５：空間の節約
【０２４５】
本発明のシステムは、４０９６バイトのＩ／Ｏストリーム内で４２５０万ブロックのデータを受信した。システムは、ＭＤ５ハッシュアルゴリズムを適用して、Ｉ／Ｏストリーム内の４２５０万ブロックに対応する７８０万ブロックのハッシュ値を生成する。
【０２４６】
これは、元の４２５０万ブロックを格納するために必要とされていた空間の１８．５％だけの使用に翻訳された。矛盾モジュールが適用されて、矛盾が存在しないことが検証された、すなわち、異なるブロックに対して、ハッシュ値の重複が生成されなかった。
【図１】
2018152126.tif 000007
【図２】
2018152126.tif 000008
【図３】
2018152126.tif 000009
【図４】
2018152126.tif 000010
【図５】
2018152126.tif 000011
【図６】
2018152126.tif 000012