(57)【要約】  コンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理するための方法及びシステムが提供される。ユーザコンテンツが、コンテンツアドレス可能オブジェクトストアにおけるアドレスに関連付けられたコンテンツハッシュを含むレコードに関連付けられる。コンテンツハッシュは、ユーザコンテンツの関数であり、ファイルをデータオブジェクトに分割することと、データオブジェクト上にハッシュのポインタツリーを生成することと、ポインタツリーのルートのハッシュを算出することとによって決定される。レコード、ポインタツリー、及びファイルが、オブジェクトストアに記憶される。オブジェクトストアからユーザコンテンツを読み出すことが、レコードを読み出すことと、コンテンツハッシュを取り出してポインタツリーのルートを発見することと、ポインタツリーのリーフを下降して、ユーザコンテンツに関連付けられたデータオブジェクトのハッシュを読み出すことと、データオブジェクトを順次ファイルデータにおいて再組立することとを含む。
2017504924.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理する、コンピュータにより実施される方法であって、
レコードをユーザコンテンツに関連付けるステップであって、前記レコードは、前記ユーザコンテンツに関連付けられた属性を含み、前記属性は、前記コンテンツアドレス可能オブジェクトストアにおけるアドレスに関連付けられたコンテンツハッシュを少なくとも含む、ステップと、
前記ユーザコンテンツを複数のデータオブジェクトに分割するステップであって、各データオブジェクトは所定の最小サイズを有する、ステップと、
前記複数のデータオブジェクトの各データオブジェクトについて、それぞれのデータオブジェクトハッシュを生成するステップであって、前記データオブジェクトハッシュは、前記データオブジェクトに関連付けられたそれぞれのデータオブジェクトコンテンツの関数である、ステップと、
前記データオブジェクトハッシュに基づいて、前記コンテンツハッシュを決定するステップと、
を含む方法。
【請求項２】
前記コンテンツハッシュを決定するステップは、
前記複数のデータオブジェクトの中のオブジェクトの数を算出することと、
前記オブジェクトの数が１である場合、前記コンテンツハッシュを前記データオブジェクトハッシュに設定することと、
前記オブジェクトの数が２以上である場合、前記データオブジェクトハッシュに基づいてポインタツリーを生成することであって、前記ポインタツリーを生成することは、
前記データオブジェクトハッシュを複数のポインタオブジェクトにグループ化することと、
前記ポインタオブジェクトを前記ポインタツリーにおけるレイヤのリーフとして割り当てることと、
前記レイヤが２つ以上のリーフを含む場合、前記ポインタツリーの次レイヤを構築することであり、前記次レイヤを構築することは、
前記ポインタオブジェクトの各々について、ポインタハッシュを生成することであり、前記ポインタハッシュは、前記ポインタオブジェクトに関連付けられたそれぞれのポインタオブジェクトコンテンツの関数である、こと、
前記ポインタハッシュを複数のさらなるポインタオブジェクトにグループ化することであり、前記さらなるポインタオブジェクトの各々は前記所定の最小サイズを有する、こと、
前記さらなるポインタオブジェクトを、前記ポインタツリーにおけるさらなるレイヤのリーフとして割り当てること、並びに、
前記ポインタハッシュを生成すること、前記ポインタハッシュをグループ化すること、及び前記さらなるポインタオブジェクトを割り当てることを、１つのリーフを有する最終レイヤが受信されるまで繰り返すこと、
を含む、ことと、
前記最終レイヤのリーフを、前記ポインタツリーのルートとして割り当てることと、
前記ポインタツリーのルートのコンテンツに基づいて、ルートポインタハッシュを計算することと、
を含む、ことと、
前記レコードの前記コンテンツハッシュを前記ルートポインタハッシュに設定することと、
を含む、請求項１に記載の方法。
【請求項３】
前記ポインタツリーの深さが、下記の式：MaxFileSize  =  BLKSZ  x  (truncate(BLKSZ÷SMASHSZ))depthにより決定され、MaxFileSizeはコンテンツエンティティのサイズであり、BLKSZは前記所定の最小サイズであり、SMASHSZは前記コンテンツハッシュのサイズであり、前記truncateは、実数のうちの整数部分を返す、実数の関数である、請求項２に記載の方法。
【請求項４】
前記ユーザコンテンツは、データファイルとフォルダとのうち１つ以上を含む、請求項２に記載の方法。
【請求項５】
前記フォルダは、さらなるレコードに関連付けられた少なくとも１つのフォルダエントリを含み、前記さらなるレコードは、さらなるユーザコンテンツに関連付けられ、前記少なくとも１つのフォルダエントリは、
前記さらなるユーザコンテンツのタイプに関連付けられた、エントリのタイプと、
前記さらなるユーザコンテンツの長さに関連付けられた、エントリの長さと、
前記さらなるユーザコンテンツの名前に関連付けられた、エントリの名前と、
さらなるコンテンツハッシュに関連付けられた、エントリの属性であって、前記さらなるコンテンツハッシュは、前記さらなるレコードの属性に基づいて生成される、エントリの属性と、
のうち少なくとも１つを含む、請求項４に記載の方法。
【請求項６】
前記フォルダは、さらなるレコードに関連付けられた１つ以上のエントリを含み、前記さらなるレコードの各々は、前記ユーザコンテンツの一意の時間バージョンに関連付けられる、請求項５に記載の方法。
【請求項７】
前記レコードの前記属性は、前のコンテンツハッシュを含み、前記前のコンテンツハッシュは、前のレコードの属性に関連付けられたコンテンツに基づいて生成され、前記前のレコードは、前記ユーザコンテンツのそれぞれの前のバージョンに関連付けられる、請求項４に記載の方法。
【請求項８】
前記ユーザコンテンツにおける変更に応答して、
前記ユーザコンテンツに関連付けられた前記ポインタツリーを少なくとも部分的に再生成するステップと、
さらなるレコードを生成するステップと、
前記さらなるレコードのコンテンツハッシュを、前記の再生成されたポインタツリーのルートに関連付けられたポインタハッシュに設定するステップと、
前記レコードの前記属性に関連付けられたコンテンツに基づいて、レコードコンテンツハッシュを計算するステップと、
前記新しいレコードの前のコンテンツハッシュを、前記レコードコンテンツハッシュに設定するステップと、
をさらに含む請求項７に記載の方法。
【請求項９】
前記データオブジェクトをクラスタストレージに書き込むステップ、をさらに含み、前記データオブジェクトを書き込むステップは、
前記データオブジェクトと前記データオブジェクトのタイプとを受信することと、
前記データオブジェクトハッシュを計算することと、
前記クラスタストレージの物理ノードを決定することであって、前記物理ノードは前記データオブジェクトのコピーを含む、ことと、
前記の決定された物理ノードの各々において、下記のステップ：
前記コンテンツアドレス可能オブジェクトストアにおける前記データオブジェクトハッシュをルックアップして、データオブジェクトメタデータを取得することであり、前記メタデータは少なくともディスク識別子とディスク内の場所とを含む、こと、並びに、
前記データオブジェクトハッシュが発見されない場合、
前記物理ノードに前記データオブジェクトのコピーを書き込むこと、及び
前記コンテンツアドレス可能オブジェクトストアを、前記データオブジェクトに関連付けられた新しいメタデータで更新すること、
を実行することと、
を含む、請求項２に記載の方法。
【請求項１０】
前記クラスタストレージにファイルを書き込むステップ、をさらに含み、前記ファイルを書き込むステップは、
前記ファイルを受信することと、
前記ファイルをファイルデータオブジェクトに分けることと、
前記ファイルデータオブジェクトのファイルデータオブジェクトハッシュを計算することと、
ファイルポインタツリーを、
前記ファイルデータオブジェクトハッシュを、前記ファイルポインタツリーのリーフに関連付けられたファイルポインタオブジェクトに挿入すること、
前記ファイルポインタオブジェクトがフルであり、あるいはすべてのファイルデータオブジェクトが処理されている場合、前記ファイルポインタオブジェクトのファイルポインタハッシュを計算すること、及び、前記ファイルポインタハッシュを親ファイルポインタオブジェクトに挿入すること、並びに、
前記ファイルポインタオブジェクトのファイルポインタハッシュを計算することを、前記ファイルポインタツリーが構築されるまで繰り返すこと、
により生成することと、
前記ファイルポインタツリーのルートのファイルポインタハッシュを、ファイルレコードのコンテンツハッシュに挿入することであって、前記ファイルレコードは前記ファイルに関連付けられる、ことと、
前記ファイルレコードの属性を、少なくともファイルサイズ及びタイムスタンプで更新することと、
前記ファイルレコードの属性に基づいて、レコードコンテンツハッシュを計算することと、
集合からの各オブジェクトを前記クラスタストレージに書き込むことであって、前記集合は、前記ファイルデータオブジェクト、前記ファイルポインタオブジェクト、及び前記ファイルレコードを含む、ことと、
前記書き込みの成功と失敗とのうち一方の指標を返すことと、
を含む、請求項９に記載の方法。
【請求項１１】
クラスタストレージから前記データオブジェクトを読み出すステップ、をさらに含み、前記データオブジェクトを読み出すステップは、
前記データオブジェクトハッシュを受信することと、
前記クラスタストレージの物理ノードのセットを決定することであって、前記物理ノードは、前記データオブジェクトのコピーを有する可能性の最大から可能性の最小に順序付けられる、ことと、
各々の順序付けられた物理ノードについて、前記コンテンツアドレス可能オブジェクトストアにおける前記データオブジェクトハッシュをルックアップすることと、
前記データオブジェクトハッシュが発見される場合及びとき、
前記データオブジェクトハッシュに基づいて、ディスク識別子とディスク内の場所とを含むデータオブジェクトメタデータを受信することと、
前記データオブジェクトメタデータを用いて、前記物理ノードから前記データオブジェクトのコピーを読み出すことと、
を含む、請求項２に記載の方法。
【請求項１２】
前記クラスタストレージからファイルを読み出すステップ、をさらに含み、前記ファイルを読み出すステップは、
前記ファイルに関連付けられたファイルレコードのレコードコンテンツハッシュを受信することと、
前記データオブジェクトを読み出すステップを適用することによって、前記クラスタストレージから前記ファイルレコードを読み出すことと、
前記ファイルレコードの前記コンテンツハッシュを取り出すことによって、ファイルポインタツリーのルートに関連付けられたルートポインタハッシュを決定することと、
前記ファイルポインタツリーを前記ルートから始めて下降して、前記ファイルポインタツリーの子リーフの中のファイルポインタハッシュを取り出すこと、及び、前記データオブジェクトを読み出すステップを適用することによって、前記ファイルポインタハッシュに関連付けられたファイルデータオブジェクトを読み出すことと、
前記ファイルデータオブジェクトを順次ファイルデータに再組立てすることと、
前記順次ファイルデータを返すことと、
を含む、請求項１１に記載の方法。
【請求項１３】
コンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理するシステムであって、
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサに通信可能に結合されたメモリと、
を含み、
前記メモリは、前記少なくとも１つのプロセッサにより実行されるときに方法を実行する命令を記憶し、前記方法は、
レコードをユーザコンテンツに関連付けるステップであって、前記レコードは、前記ユーザコンテンツに関連付けられた属性を含み、前記属性は、前記コンテンツアドレス可能オブジェクトストアにおけるアドレスに関連付けられたコンテンツハッシュを少なくとも含む、ステップと、
前記ユーザコンテンツを複数のデータオブジェクトに分割するステップであって、各データオブジェクトは所定の最小サイズを有する、ステップと、
前記複数のデータオブジェクトの各データオブジェクトについて、それぞれのデータオブジェクトハッシュを生成するステップであって、前記データオブジェクトハッシュは、前記データオブジェクトに関連付けられたそれぞれのデータオブジェクトコンテンツの関数である、ステップと、
前記データオブジェクトハッシュに基づいて、前記コンテンツハッシュを決定するステップと、
を含む、システム。
【請求項１４】
前記コンテンツハッシュを決定するステップは、
前記複数のデータオブジェクトの中のオブジェクトの数を算出することと、
前記オブジェクトの数が１である場合、前記コンテンツハッシュを前記データオブジェクトハッシュに設定することと、
前記オブジェクトの数が２以上である場合、前記データオブジェクトハッシュに基づいてポインタツリーを生成することであって、前記ポインタツリーを生成することは、
前記データオブジェクトハッシュを複数のポインタオブジェクトにグループ化することと、
前記ポインタオブジェクトを前記ポインタツリーにおけるレイヤのリーフとして割り当てることと、
前記レイヤが２つ以上のリーフを含む場合、前記ポインタツリーの次レイヤを構築することであり、前記次レイヤを構築することは、
前記ポインタオブジェクトの各々について、ポインタハッシュを生成することであり、前記ポインタハッシュは、前記ポインタオブジェクトに関連付けられたそれぞれのポインタオブジェクトコンテンツの関数である、こと、
前記ポインタハッシュを複数のさらなるポインタオブジェクトにグループ化することであり、前記さらなるポインタオブジェクトは前記所定の最小サイズを有する、こと、
前記さらなるポインタオブジェクトを、前記ポインタツリーにおけるさらなるレイヤのリーフとして割り当てること、並びに、
前記ポインタハッシュを生成すること、前記ポインタハッシュをグループ化すること、及び前記さらなるポインタオブジェクトを割り当てることを、１つのリーフを有する最終レイヤが受信されるまで繰り返すこと、
を含む、ことと、
前記最終レイヤのリーフを、前記ポインタツリーのルートとして割り当てることと、
前記ポインタツリーのルートのコンテンツに基づいて、ルートポインタハッシュを計算することと、
を含む、ことと、
前記レコードの前記コンテンツハッシュを前記ルートポインタハッシュに設定することと、
を含む、請求項１３に記載のシステム。
【請求項１５】
前記ポインタツリーの深さが、下記の式：MaxFileSize  =  BLKSZ  x  (truncate(BLKSZ÷SMASHSZ))depthにより決定され、MaxFileSizeはコンテンツエンティティのサイズであり、BLKSZは前記所定の最小サイズであり、SMASHSZは前記コンテンツハッシュのサイズであり、前記truncateは、実数のうちの整数部分を返す、実数の関数である、請求項１４に記載のシステム。
【請求項１６】
前記ユーザコンテンツは、データファイルとフォルダとのうち１つ以上を含む、請求項１４に記載のシステム。
【請求項１７】
前記フォルダは、さらなるレコードに関連付けられた少なくとも１つのフォルダエントリを含み、前記さらなるレコードは、さらなるユーザコンテンツに関連付けられ、前記少なくとも１つのフォルダエントリは、
前記さらなるユーザコンテンツのタイプに関連付けられた、エントリのタイプと、
前記さらなるユーザコンテンツの長さに関連付けられた、エントリの長さと、
前記さらなるユーザコンテンツの名前に関連付けられた、エントリの名前と、
さらなるコンテンツハッシュに関連付けられた、エントリの属性であって、前記さらなるコンテンツハッシュは、前記さらなるレコードの属性に基づいて生成される、エントリの属性と、
のうち少なくとも１つを含む、請求項１６に記載のシステム。
【請求項１８】
前記フォルダは、さらなるレコードに関連付けられた１つ以上のエントリを含み、前記さらなるレコードの各々は、前記ユーザコンテンツの一意の時間バージョンに関連付けられる、請求項１７に記載のシステム。
【請求項１９】
前記レコードの前記属性は、前のコンテンツハッシュを含み、前記前のコンテンツハッシュは、前のレコードの属性に関連付けられたコンテンツに基づいて生成され、前記前のレコードは、前記ユーザコンテンツのそれぞれの前のバージョンに関連付けられる、請求項１６に記載のシステム。
【請求項２０】
前記ユーザコンテンツにおける変更に応答して、
前記ユーザコンテンツに関連付けられた前記ポインタツリーを少なくとも部分的に再生成するステップと、
さらなるレコードを生成するステップと、
前記さらなるレコードのコンテンツハッシュを、前記の再生成されたポインタツリーのルートに関連付けられたポインタハッシュに設定するステップと、
前記レコードの前記属性に関連付けられたコンテンツに基づいて、レコードコンテンツハッシュを計算するステップと、
前記新しいレコードの前のコンテンツハッシュを、前記レコードコンテンツハッシュに設定するステップと、
をさらに含む請求項１９に記載のシステム。
【請求項２１】
前記データオブジェクトをクラスタストレージに書き込むステップ、をさらに含み、前記データオブジェクトを書き込むステップは、
前記データオブジェクトと前記データオブジェクトのタイプとを受信することと、
前記データオブジェクトハッシュを計算することと、
前記クラスタストレージの物理ノードを決定することであって、前記物理ノードは前記データオブジェクトのコピーを含む、ことと、
前記の決定された物理ノードの各々において、下記のステップ：
前記コンテンツアドレス可能オブジェクトストアにおける前記データオブジェクトハッシュをルックアップして、データオブジェクトメタデータを取得することであり、前記メタデータは少なくともディスク識別子とディスク内の場所とを含む、こと、並びに、
前記データオブジェクトハッシュが発見されない場合、
前記物理ノードに前記データオブジェクトのコピーを書き込むこと、及び
前記コンテンツアドレス可能オブジェクトストアを、前記データオブジェクトに関連付けられた新しいメタデータで更新すること、
を実行することと、
を含む、請求項１４に記載のシステム。
【請求項２２】
前記クラスタストレージにファイルを書き込むステップ、をさらに含み、前記ファイルを書き込むステップは、
前記ファイルを受信することと、
前記ファイルをファイルデータオブジェクトに分けることと、
前記ファイルデータオブジェクトのファイルデータオブジェクトハッシュを計算することと、
ファイルポインタツリーを、
前記ファイルデータオブジェクトハッシュを、前記ファイルポインタツリーのリーフに関連付けられたファイルポインタオブジェクトに挿入すること、
前記ファイルポインタオブジェクトがフルであり、あるいはすべてのファイルデータオブジェクトが処理されている場合、前記ファイルポインタオブジェクトのファイルポインタハッシュを計算すること、及び、前記ファイルポインタハッシュを親ファイルポインタオブジェクトに挿入すること、並びに、
前記ファイルポインタオブジェクトのファイルポインタハッシュを計算することを、前記ファイルポインタツリーが構築されるまで繰り返すこと、
により生成することと、
前記ファイルポインタツリーのルートのファイルポインタハッシュを、ファイルレコードのコンテンツハッシュに挿入することであって、前記ファイルレコードは前記ファイルに関連付けられる、ことと、
前記ファイルレコードの属性を、少なくともファイルサイズ及びタイムスタンプで更新することと、
前記ファイルレコードの属性に基づいて、レコードコンテンツハッシュを計算することと、
集合からの各オブジェクトを前記クラスタストレージに書き込むことであって、前記集合は、前記ファイルデータオブジェクト、前記ファイルポインタオブジェクト、及び前記ファイルレコードを含む、ことと、
前記書き込みの成功と失敗とのうち一方の指標を返すことと、
を含む、請求項２１に記載のシステム。
【請求項２３】
クラスタストレージから前記データオブジェクトを読み出すステップ、をさらに含み、前記データオブジェクトを読み出すステップは、
前記データオブジェクトハッシュを受信することと、
前記クラスタストレージの物理ノードのセットを決定することであって、前記物理ノードは、前記データオブジェクトのコピーを有する可能性の最大から可能性の最小に順序付けられる、ことと、
各々の順序付けられた物理ノードについて、前記コンテンツアドレス可能オブジェクトストアにおける前記データオブジェクトハッシュをルックアップすることと、
前記データオブジェクトハッシュが発見される場合及びとき、
前記データオブジェクトハッシュに基づいて、ディスク識別子とディスク内の場所とを含むデータオブジェクトメタデータを受信することと、
前記データオブジェクトメタデータを用いて、前記物理ノードから前記データオブジェクトのコピーを読み出すことと、
を含む、請求項１４に記載のシステム。
【請求項２４】
前記クラスタストレージからファイルを読み出すステップ、をさらに含み、前記ファイルを読み出すステップは、
前記ファイルに関連付けられたファイルレコードのレコードコンテンツハッシュを受信することと、
前記データオブジェクトを読み出すステップを適用することによって、前記クラスタストレージから前記ファイルレコードを読み出すことと、
前記ファイルレコードの前記コンテンツハッシュを取り出すことによって、ファイルポインタツリーのルートに関連付けられたルートポインタハッシュを決定することと、
前記ファイルポインタツリーを前記ルートから始めて下降して、前記ファイルポインタツリーの子リーフの中のファイルポインタハッシュを取り出し、前記データオブジェクトを読み出すステップを適用することによって、前記ファイルポインタハッシュに関連付けられたファイルデータオブジェクトを読み出すことと、
前記ファイルデータオブジェクトを順次ファイルデータに再組立てすることと、
前記順次ファイルデータを返すことと、
を含む、請求項２３に記載のシステム。
【請求項２５】
１つ以上のプロセッサにより実行されるときにコンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理する方法を実行する命令を具現化させた非一時的コンピュータ可読記憶媒体であって、前記方法は、
レコードをユーザコンテンツに関連付けるステップであって、前記レコードは、前記ユーザコンテンツに関連付けられた属性を含み、前記属性は、前記コンテンツアドレス可能オブジェクトストアにおけるアドレスに関連付けられたコンテンツハッシュを少なくとも含む、ステップと、
前記ユーザコンテンツを複数のデータオブジェクトに分割するステップであって、データオブジェクトの各々は所定の最小サイズを有する、ステップと、
前記複数のデータオブジェクトの各データオブジェクトについて、それぞれのデータオブジェクトハッシュを生成するステップであって、前記データオブジェクトハッシュは、前記データオブジェクトに関連付けられたそれぞれのデータオブジェクトコンテンツの関数である、ステップと、
前記データオブジェクトハッシュに基づいて、前記コンテンツハッシュを決定するステップと、
を含む、非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2014年2月4日に申請された米国仮出願第61/935,618号の利益を主張する。前述された出願の開示は、すべての目的について、本明細書において参照により援用される。
【０００２】
本開示は、概してデータ処理に関し、より具体的には、コンピュータファイルシステムの編成及び管理のための方法及びシステムに関する。
【背景技術】
【０００３】
本セクションに説明されるアプローチは、追求されたことがある可能性があるが、必ずしもこれまでに着想され、あるいは追求されてきたアプローチではない。それゆえに、他に示されない限り、本セクションに説明されるアプローチのいずれも、単に本セクションに含まれるという理由で従来技術と見なすと仮定されるべきではない。
【０００４】
コンピュータシステムにおいて、ハードディスクなどの記憶装置上に保有されるデータは、ファイルシステムとして編成される。大抵、ファイルシステムはツリー構造を有し、ルートディレクトリ、ディレクトリ、サブディレクトリ、及びファイルから成る。ファイルシステム内の各オブジェクト、すなわち、ファイル又はディレクトリは、オブジェクト識別子（ＩＤ）と、“Ｉノード”と呼ばれる特別なレコードとを有し、上記Ｉノードは、オブジェクトに関連付けられた属性、例えば、バイト単位のファイルサイズ、ブロック割り振り、所有者ユーザＩＤ、所有者のグループＩＤ、最後の修正の時間などを保持する。
【０００５】
コンテンツアドレス可能ファイルシステムにおいて、オブジェクトＩＤは、ユーザ又はメタデータコンテンツ上で数学的関数を実行することによって作成される。伝統的なファイルシステムにおいて、オブジェクトＩＤは、典型的に、使用されていない識別子のリストから選ばれる。
【０００６】
大抵のファイルシステムは、ファイルの最新バージョンのみ保有する。ユーザがより古いバージョンのファイル又はディレクトリを保有したい場合、ユーザはこれらを手動で保存し、あるいは特別なバージョニングソフトウェアを使用して異なるバージョンから成る複数のバージョンの記録をつけなければならない。データのバックアップが管理者によって定期的に実行されることがあり、ユーザは、より古いバージョンのファイルを得るためには、管理者にコンタクトをとる必要がある。
【発明の概要】
【０００７】
本発明の概要は、以下に詳細な説明においてさらに説明される概念のうち選択されたものを簡素化された形式において導入するために提供される。本発明の概要は、請求される対象事項の重要な特徴又は必須の特徴を識別するものではなく、請求される対象事項の範囲を決定することの助けとして用いられるべきものでもない。
【０００８】
本明細書に説明されるテクノロジーは、コンピュータ記憶装置におけるファイルシステムの編成及び管理の方法である。ファイルシステムは、コンテンツアドレス可能分散オブジェクトストアの上に構築される。
【０００９】
一例示的な実施形態に従い、方法が、レコードをユーザコンテンツに関連付けることを含む。レコードは、ユーザコンテンツに関連付けられた属性を含むことができる。属性は、コンテンツアドレス可能オブジェクトストア内のオブジェクトに関連付けられたコンテンツハッシュを少なくとも含むことができる。方法は、ユーザコンテンツを複数のデータオブジェクトに分割することを可能にすることができる。各データオブジェクトは、所定の最小サイズを有する。方法は、複数のデータオブジェクトのうちの各データオブジェクトについて、それぞれのデータオブジェクトハッシュを生成することを含む。データオブジェクトハッシュは、データオブジェクトに関連付けられたそれぞれのデータオブジェクトコンテンツの関数である。方法は、データオブジェクトハッシュに基づいて、コンテンツハッシュを決定することをさらに含む。
【００１０】
いくつかの実施形態において、コンテンツハッシュを決定することは、複数のデータオブジェクトの中のオブジェクトの数を算出することを含む。オブジェクトの数が１である場合、コンテンツハッシュはデータオブジェクトハッシュに設定される。オブジェクトの数が２以上である場合、データオブジェクトハッシュに基づいて、ポインタツリーが生成される。ポインタツリーの生成は、データオブジェクトハッシュを複数のポインタオブジェクトにグループ化することを含む。ポインタオブジェクトは、ポインタツリーにおけるレイヤのリーフとして割り当てられる。レイヤが２つ以上のリーフを含む場合、ポインタツリーの次レイヤが構築される。次レイヤの構築は、ポインタオブジェクトの各々について、ポインタハッシュを生成することを含む。ポインタハッシュは、ポインタオブジェクトに関連付けられたそれぞれのポインタオブジェクトコンテンツの関数である。次レイヤの構築は、ポインタハッシュを複数のさらなるポインタオブジェクトにグループ化することを含む。次レイヤの構築は、さらなるポインタオブジェクトをポインタツリーにおけるさらなるレイヤのリーフとして割り当てることを含む。ポインタハッシュの生成、ポインタハッシュのグループ化、及びさらなるポインタオブジェクトの割り当ては、１つのリーフを有する最終レイヤが受信されるまで繰り返される。最終レイヤのリーフは、ポインタツリーのルートとして割り当てられる。ルートハッシュが、ポインタツリーのルートのコンテンツに基づいて計算され、レコードのコンテンツハッシュは、ルートポインタハッシュに設定される。
【００１１】
いくつかの実施形態において、ポインタツリーの深さは、下記の式：MaxFileSize  =  BLKSZ  x  (truncate(BLKSZ÷SMASHSZ))depthによって決定される。MaxFileSizeは、コンテンツエンティティのサイズである。BLKSZは、所定の最小サイズである。SMASHSZは、コンテンツハッシュのサイズである。truncateは、実数の関数であり、実数の整数部分を返す。
【００１２】
いくつかの実施形態において、ユーザコンテンツは、下記のうち１つ以上を含む：データファイル、及びフォルダ。
【００１３】
いくつかの実施形態において、フォルダは、さらなるレコードに関連付けられた少なくとも１つのフォルダエントリを含む。上記さらなるレコードは、さらなるユーザコンテンツに関連付けられる。フォルダエントリは、下記のうち少なくとも１つを含む：さらなるユーザコンテンツのタイプに関連付けられた、エントリのタイプ、さらなるユーザコンテンツに関連付けられた名前、さらなるユーザコンテンツに関連付けられた名前の長さ、及びさらなるレコードに関連付けられた、エントリの属性。さらなるレコードハッシュが、さらなるレコードの属性に基づいて生成される。
【００１４】
いくつかの実施形態において、フォルダは、さらなるレコードに関連付けられた１つ以上のエントリを含み、さらなるレコードの各々は、ユーザコンテンツについての一意の時間バージョンに関連付けられる。
【００１５】
いくつかの実施形態において、レコードの属性は、前のレコードハッシュを含む。前のレコードハッシュは、前のレコードの属性に関連付けられたコンテンツに基づいて生成される。前のレコードは、ユーザコンテンツのそれぞれの前のバージョンに関連付けられる。
【００１６】
いくつかの実施形態において、上記方法は、ユーザコンテンツの変更に応答して、ユーザコンテンツに関連付けられたポインタツリーを少なくとも部分的に再生成することをさらに含む。方法は、さらなるレコードを生成することと、さらなるレコードのコンテンツハッシュを、上記の再生成されたポインタツリーのルートに関連付けられたポインタハッシュに設定することとを含む。方法は、さらに、レコードの属性に関連付けられたコンテンツに基づいて、レコードコンテンツハッシュを計算することを含む。方法は、この新しいレコードについての前のレコードハッシュを、レコードコンテンツハッシュに設定することを含む。
【００１７】
いくつかの実施形態において、方法は、さらに、データオブジェクトをクラスタストレージに書き込むことを含む。データオブジェクトの書き込みは、データオブジェクトとデータオブジェクトのタイプとを受信することを含む。データオブジェクトハッシュが計算される。データオブジェクトのコピーを記憶すべきクラスタストレージの物理ノードが決定される。上記の決定された物理ノードの各々において、データオブジェクトハッシュがコンテンツアドレス可能オブジェクトストア内でルックアップされて、データオブジェクトメタデータが取得される。メタデータは、少なくともディスク識別子とディスク内の場所とを含む。データオブジェクトハッシュが発見されない場合、データオブジェクトのコピーがノードに書き込まれ、コンテンツアドレス可能オブジェクトストアは、データオブジェクトに関連付けられた新しいメタデータで更新される。
【００１８】
いくつかの実施形態において、方法は、クラスタストレージにファイルを書き込むことをさらに含む。ファイルの書き込みは、ファイルをファイルデータオブジェクト分けることと、ファイルデータオブジェクトのためのファイルデータオブジェクトハッシュを計算することとを含む。ファイルポインタツリーが、ファイルポインタツリーのリーフに関連付けられたファイルポインタオブジェクトにファイルデータオブジェクトハッシュを挿入することによって、生成される。ファイルポインタオブジェクトがフルであるか、あるいはすべてのファイルデータオブジェクトが処理されている場合、ファイルポインタオブジェクトのためのファイルポインタハッシュが計算され、このファイルポインタハッシュは親ファイルポインタオブジェクトに挿入される。ファイルポインタオブジェクトのためのファイルポインタハッシュの計算は、ファイルポインタツリーが構築されるまで繰り返される。ファイルの書き込みは、さらに、ファイルポインタツリーのルートのファイルポインタハッシュをファイルレコードのコンテンツハッシュ属性に挿入することを含む。ゆえに、ファイルレコードは、ファイルに関連付けられる。ファイルレコードの属性は、少なくともファイルサイズとタイムスタンプとで更新される。レコードコンテンツハッシュが、ファイルレコードの属性に基づいて計算される。ファイルデータオブジェクト、ファイルポインタオブジェクト、及びファイルレコードは、クラスタストレージに書き込まれる。書き込みの成功及び失敗のうち一方の指標が返される。
【００１９】
いくつかの実施形態において、コンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理する方法が、クラスタストレージからデータオブジェクトを読み出すことを含む。データオブジェクトの読み出しは、データオブジェクトハッシュを受信することを含む。データオブジェクトの読み出しは、さらに、クラスタストレージの物理ノードのセットを決定することを含む。物理ノードは、データオブジェクトのコピーを含む可能性の最大から可能性の最小へ順序付けられる。各々の順序付けされた物理ノードについて、コンテンツアドレス可能オブジェクトストアにおけるデータオブジェクトハッシュがルックアップされる。データオブジェクトハッシュが発見される場合及びとき、データオブジェクトの読み出しは、データオブジェクトハッシュに基づいて、データオブジェクトメタデータを受信することをさらに含む。オブジェクトメタデータは、ディスク識別子とディスク内の場所とを含む。それから、データオブジェクトのコピーが、データオブジェクトメタデータを用いてノードから読み出される。
【００２０】
いくつかの実施形態において、方法は、クラスタストレージからファイルを読み出すことをさらに含むことができる。ファイルの読み出しは、ファイルに関連付けられたファイルレコードのレコードコンテンツハッシュを受信することを含む。ファイルレコードは、読み出し処理を適用することによって、クラスタストレージから読み出される。上記処理は、ファイルレコードのコンテンツハッシュを取り出すことによって、ファイルポインタツリーのルートに関連付けられたルートポインタハッシュを決定することを含む。上記読み出しは、ファイルポインタツリーをルートから始めて下降して、ファイルポインタツリーの子リーフの中のファイルポインタハッシュを取り出すことを含む。ファイルポインタハッシュに関連付けられたファイルデータオブジェクトが、上記読み出し処理を適用することによって読み出されることができる。ファイルデータオブジェクトは、順次ファイルデータへと再組立てされる。クラスタストレージからファイルを読み出すことは、上記順次ファイルデータを返すことで完結する。
【００２１】
本開示の別の例示的な実施形態に従い、コンテンツアドレス可能オブジェクトストア上のファイルシステムを編成し及び管理する方法のステップが、命令を含むマシン可読媒体上に記憶され、上記命令は、１つ以上のプロセッサにより実施されると、列挙されたステップを実行する。
【００２２】
本願方法の他の特徴には、実行中の（on  the  fly）すべてのファイル及びディレクトリについてのバージョンの追跡の履歴を提供することが含まれる。ゆえに、より古いバージョンのファイル及びディレクトリが、ルートディレクトリを含め、任意のときにユーザに対して利用可能である。
【図面の簡単な説明】
【００２３】
実施形態は、添付図面の図において限定ではなく例として例示され、同様の参照は類似の要素を示す。
【図１】ファイルシステムにおけるコンテンツの一例を示す。
【図２】所与のファイルのデータオブジェクトのためのスマートハッシュの生成を例示する。
【図３】ファイルシステム内のＩノードエントリを説明する属性のテーブルを表示する。
【図４】Ichdataパラメータの属性の集合を表示する。
【図５】ファイルデータを直接指し示すＩノードを例示する。
【図６】ファイル又はディレクトリを表現する１レイヤポインタツリーを例示する。
【図７Ａ】ファイル又はディレクトリを表現する２レイヤポインタツリーを例示する。
【図７Ｂ】ファイル又はディレクトリを表現する３レイヤポインタツリーを例示する。
【図８】ファイルのバージョンに関連付けられた、リンクされたＩノードのチェーンを例示する。
【図９】ディレクトリデータオブジェクトの構造、及び、Ｉノードと対応するファイルデータオブジェクトとに対するディレクトリエントリの接続を例示する。
【図１０】タイプ１のディレクトリエンティティを有するディレクトリデータの一例を示す。
【図１１】より古いバージョンのファイル又はディレクトリに対するアクセスをユーザが有することを可能にするメカニズム及びスナップショットのための仮想ディレクトリのスキームを例示する。
【図１２】オブジェクトを書き込む方法を示す処理フロー図である。
【図１３】オブジェクトを読み出す方法を示す処理フロー図である。
【図１４】ファイルを書き込む方法を示す処理フロー図である。
【図１５】ファイルを読み出す方法を示す処理フロー図である。
【図１６】コンピュータシステムの例示的な電子形態におけるマシンのコンピューティング装置の概略表現を示し、これにおいて、本明細書に論じられる方法論のうち任意の１つ以上をマシンに実行させる命令セットが実行されることができる。
【発明を実施するための形態】
【００２４】
下記の詳細な説明は添付図面に対する参照を含み、添付図面は本詳細な説明の一部を形成する。図面は、例示的な実施形態に従い例示を示す。こうした例示的な実施形態は、本明細書において「例」とさらに呼ばれ、十分詳細に説明されて、当業者が本対象事項を実施することを可能にする。実施形態は組み合わせられてもよく、他の実施形態が利用されてもよく、あるいは、構造的、論理的、及び電気的な変更が、請求されるものの範囲から逸脱することなく行われてもよい。ゆえに、下記の詳細な説明は、限定的な意味においてとられるべきではなく、その範囲は、別記の請求項及びその均等物によって定義される。
【００２５】
本明細書に説明されるテクノロジーは、コンテンツアドレス可能分散オブジェクトストア（content  addressable  distributed  object  store）の上に築かれるファイルシステムの編成及び管理を可能にする。ファイルシステム内の各可視オブジェクトが、オブジェクトＩＤのチェーンに関連付けられることができ、上記オブジェクトＩＤの各々は、所与の時点におけるオブジェクトのバージョンに対応する。ゆえに、オブジェクトストアは、様々な時点におけるファイルシステムの「スナップショット」を提供すると言われ得る。ファイルシステムは、すべてのファイルのすべてのバージョンを保有し、ガーベッジコレクション処理を実行して、もはや必要とされないバージョンを廃棄することができる。
【００２６】
一例示的な実施形態に従い、上記方法は、レコード（さらに、ｉノード（inode）オブジェクトとして参照される）をユーザコンテンツに関連付けることを含む。レコードは、ユーザコンテンツに関連付けられた属性を含むことができる。属性は、コンテンツアドレス可能オブジェクトストア（content  addressable  object  store）内のオブジェクトに関連付けられたコンテンツハッシュを少なくとも含むことができる。この例示的な方法は、ユーザコンテンツを複数のデータオブジェクトに分割することを可能にすることができる。各データオブジェクトは、所定の最小サイズを有する。方法は、複数のデータオブジェクトの各データオブジェクトについて、それぞれのデータオブジェクトハッシュを生成することを含むことができる。データオブジェクトハッシュは、対応するデータオブジェクトに関連付けられたそれぞれのデータオブジェクトコンテンツの関数である。方法は、データオブジェクトハッシュに基づいて、コンテンツハッシュを決定することを含むことができる。
【００２７】
ファイルシステム１００の一例が図１に示されている。ファイルシステムは階層ツリーとして見られ得る。ツリーのルートノードは、ルートディレクトリ１１０、すなわち、ファイルシステムのルートフォルダ、いかなる他のフォルダの子でもない唯一のフォルダに対応する。所与のノードである子ノード１２０、１３０、１４０、１５０、１６０はファイル又はフォルダであり得る。ファイルシステムはＰＯＳＩＸセマンティック（semantic）を利用することができる。
【００２８】
すべてのオブジェクトＩＤがオブジェクトの内容に基づいて計算される。オブジェクト内容が変わる場合、オブジェクトＩＤがさらに変わり、新しいオブジェクトＩＤを有し得る。オブジェクトの変更は、さらに、その親のオブジェクトＩＤの変更を引き起こし得る。上記変更は、ファイルシステム１００を表現するツリーのルートまでずっと伝播する。こうして、一意のオブジェクトＩＤがファイルシステム１００の各バージョンについて生成されることができる。
【００２９】
各オブジェクトＩＤのキー属性はタイプSmashのパラメータであり、Smashはスマートハッシュ（smart  hash）を表す。スマートハッシュは、さらに、オブジェクト識別子として参照される。図２は、ファイルのSmashオブジェクトＩＤを算出する一例示的な表現２００を示している。
【００３０】
ファイル２１０は、BLKSZサイズのオブジェクト２２０に分けられる。これらオブジェクト２２０の各々は、Smashタイプのパラメータを返すハッシュ関数のための入力オブジェクトである。
【００３１】
ハッシュ関数はいくつかの要件を有し得る。この関数は、あらゆるとり得る入力オブジェクトに対して出力される一意のSmashを生成しなければならない。２つの入力オブジェクトがちょうど１ビットだけ異なる場合、ハッシュ関数は、高い確率で、２つの異なるSmash値を生成しなければならない。
【００３２】
ハッシュ関数は、常に、同じ長さのバイトのものであるSmash２３０を生成する。Smash２３０の長さは、SMASHSZとして知られている。データオブジェクトの最大長は、BLKSZとして知られている。これらは、ファイルシステムのための所定のパラメータである。例えば、長さ２０バイトの複数のSmashと３２ＫＢのBLKSZ値とが使用されることができる。３２ＫＢ長の２つの異なる入力オブジェクトが長さ２０バイトの同じSmash値を結果としてもたらし得る確率は、非常に小さくなければならない。
【００３３】
ハッシュ関数の出力は、ハッシュ空間において公平に均等に分散されるべきである。ハッシュ関数は、毎回同じ入力を与えられるたび、同じ出力を生成しなければならない。
【００３４】
zzhashと呼ばれる特別なSmash値がある。この値は、存在しない何かを表現することに使用される。
【００３５】
ファイルシステム内の、ユーザに対して可視の各オブジェクトについて、Ｉノード（Inode）と呼ばれる少なくとも１つのエンティティが存在する。Ｉノードは、ファイルシステム内のファイル又はディレクトリを表現するのに必要とされるすべての情報を保持する。図３は、Ｉノード３００の構造を示している。Ｉノードの属性３１０の多くが、ＰＯＳＩＸ標準により定義される通常のパラメータ、例えば、所有者ＩＤ、グループＩＤ、バイト単位でのファイルのサイズなどである。いくつかのカスタム属性が追加されることができ、例えば、chash、xhash、及びichdataなどである。
【００３６】
chashは、コンテンツハッシュを表す。chashはSmashタイプのパラメータであり、ディレクトリデータオブジェクト、ディレクトリポインタオブジェクト、データオブジェクト、ポインタツリーオブジェクト、又はzzhashのSmashを含み得る。
【００３７】
xhashは、拡張された属性ハッシュである。このハッシュは、拡張された属性データオブジェクト、拡張された属性ポインタオブジェクト、又はzzhashのSmashパラメータを含み得る。
【００３８】
意図的チェーン化ヒストリデータ（Intentional  Chained  History  Data）（ichdata）４００の構造が図４に示されている。これは、データストア内の変えられない（immutable）オブジェクトの中から変えられる（mutable）オブジェクトの履歴を作成すること及び追跡することについて責任を負うメカニズムにおいて利用される属性４１０のセットである。このパラメータのセットは、generation、revgen、snaptime、及びsnaptagを含む。generationは、スナップショット生成カウントであり、revgenは、スナップショット内における改訂（revision）カウントであり、snaptimeは、スナップショットが作成された時間であり、snaptagは、いずれのファイルシステム動作がスナップショットを引き起こしたかを示す列挙値であり、例えば、作成、削除、ファイルに対する書き込み、ファイルの名前変更などである。
【００３９】
ichdata４００は、Smashタイプの３つのパラメータ４２０をさらに含み得る。
ａ．ohashは、古いハッシュ（old  hash）を表し、このＩノードの前のバージョンのためのSmashを保持する。ohashは、このオブジェクトの前のバージョンがない場合、zzhashに等しい。
ｂ．Mhash又はマージハッシュ（merge  hash）は、このノードが由来する代替の履歴を表現する。Mhashは、こうした代替の履歴がない場合、zzhashに等しくなり得る。
ｃ．Uuid又はユニバーサル一意識別子（Universally  Unique  Identifier）は、このオブジェクトのすべてのバージョンによって、その履歴の全体を通して継承されるパラメータである。uuidパラメータは、この特定のファイル又はディレクトリのためのＩノードが最初に作成されるとき、生成される。
【００４０】
Ｉノードは、ただ１つのchashパラメータを有する。ファイルサイズがBLKSZの予め定義されたシステムパラメータより小さいか又は等しいとき、必要なことは、ハッシュ関数をファイルに単に適用して、対応するSmashを生成することである。しかしながら、ファイルシステム内のファイルの大多数と、同様にディレクトリとは、BLKSZより大きく成長する可能性がある。ファイル又はディレクトリのサイズがBLKSZより大きいとき、ファイル又はディレクトリはポインタツリーを介して表現される。
【００４１】
図５は、Ｉノード３００についての表現５００を示しており、Ｉノード３００は、データオブジェクト５２０として示されるBLKSZより小さいか又は等しいサイズのファイルを指し示している。Ｉノード内のchashパラメータは、このファイルについて算出されたSmashである。
【００４２】
図６は、BLKSZより大きいサイズのファイルに対応するＩノード６１０と、上記ファイルを表現する対応した１レイヤポインタツリーとの表現６００を示している。Ｉノード３００内のchashパラメータは、今度はSmash６４０のレイヤ１を含むオブジェクトのSmashである。レイヤ１のSmash６４０は、ファイルデータ５２０のオブジェクトについて算出され、ファイルデータ５２０は、ポインタツリーにおけるリーフとして見られ得る。各データオブジェクト５２０は、サイズBLKSZのものである。最後のデータオブジェクト５２０は、サイズBLKSZか又はより小さいものであり得る。オブジェクトハッシュを含むオブジェクトが、ポインタオブジェクト６２０として参照される。
【００４３】
各ポインタオブジェクト６２０は、ゆえに、最大で、N=truncate(BLKSZ÷SMASHSZ)ハッシュまで保持し得る。例えば、BLKSZが３２ＫＢであり、SMASHSZが２０バイトであるとき、１レイヤのSmashを有するポインタツリーは、サイズにおいて最大53,673,984バイトまでのファイルを表現することができる。
【００４４】
図７Ａは、２レイヤポインタツリー７００を例示している。レイヤ１のポインタオブジェクト６２０は、他のポインタオブジェクトのSmashを保持する。第２のレイヤの各ポインタオブジェクトは、データオブジェクト５２０のためのSmash６４０を含む。例えば、BLKSZが３２ＫＢであり、SMASHSZが２０バイトであるとき、２レイヤポインタツリーは、サイズにおいて最大約８３ＧＢまでのファイルを表現することができる。
【００４５】
図７Ｂは、３レイヤポインタツリー７５０を示している。図７Ａの２レイヤポインタツリー７００とは対照的に、３レイヤポインタツリー７５０は、さらなるレイヤのポインタオブジェクト６２０を含む。例えば、BLKSZが３２ＫＢであり、SMASHSZが２０バイトであるとき、３レイヤポインタツリー７５０は、サイズにおいて最大約１３４ＴＢまでのファイルに対処することができる。
【００４６】
ポインタオブジェクトツリーの任意の与えられた深さに対するファイルの最大サイズは、下記のとおり算出されることができる：MaxFileSize  =  BLKSZ  x  (truncate(BLKSZ÷SMASHSZ))depth。
【００４７】
ポインタツリーを用いたデータの表現は、ファイルデータからSmashを通してＩノードの後ろのレイヤに変更を迅速に伝播することに役立つ。ポインタツリーの同じメカニズムが、大きいディレクトリを表現することに使用されることができる。
【００４８】
図８は、接続されたＩノード３００のリスト８００を例示しており、Ｉノード３００は、ファイル８２０として示される１つのエンティティ、ファイル、又はディレクトリを説明している。Ｉノード３００は、エンティティに対する修正が行われた時点Ｔ０、Ｔ１、Ｔ２などに対応する。新しいＩノードが、対応するコンテンツが毎回修正されるたび、作成され、チェーンの上部に追加される。新しいＩノードのgeneration属性８５０は、１ずつ増加し得る。
【００４９】
各Ｉノード３００のchashパラメータ８３０は、所与の時点におけるエンティティ又はエンティティのポインタツリーについてのSmashを含む。ohashパラメータは、前の時点に対応するＩノード３００のSmashである。第１の時点のＩノード３００のohashパラメータは、このエンティティについて前のバージョンがないので、zzhashに向けられる。ohashパラメータ８４０は、所与のエンティティの「スナップショット」の時間逆行チェーン（back  in  time  chain）を構築する、所与のエンティティのＩノード３００をリンクしている。チェーンの中の各Ｉノード３００のchashパラメータ８３０は、そのバージョンのデータを指し示す。このタイプの接続は、データの異なるバージョンを通した検索を可能にする。ガーベッジコレクタが、このチェーンを歩いて行く（walk  down）ように設定され、上記バージョンのうちいずれが削除されることができるかを決めることができる。ガーベッジコレクションを実行する方法の一例が、2013年6月12日に申請され“Hybrid  Garbage  Collection”と題された米国仮特許出願第61/834,097号に説明されており、該出願は本明細書において参照により援用される。
【００５０】
図９は、ディレクトリ９１０の内容の一例示的な表現９００を示している。ディレクトリデータは、ディレクトリエントリ９２０のセットから成る。ディレクトリエントリ９２０は、下記の属性を含む可変サイズのレコードである：エントリのタイプ、エントリの名前の長さ、エントリの名前、及びタイプにより指定される属性。ディレクトリエントリのタイプは、少なくとも２つのとり得る値：０及び１を有することができる。
【００５１】
タイプ０のディレクトリエントリは、Ｉノード３００を識別する。ディレクトリエントリ９２０の中の名前フィールドは、Ｉノードが表現するファイル９４０又はディレクトリの、名前を保持する。ディレクトリエントリの中の指定された属性が、Ｉノード３００のSmashである。
【００５２】
タイプ１のディレクトリエンティティについて、名前ファイルは、仮想スナップショットツリーのルートを識別する。ディレクトリエントリの特定属性は、この場合には使用されない。ユーザは、仮想スナップショットツリーの名前をサブディレクトリとして見ることができる。図１０は、タイプ１のディレクトリエンティティ１０１０を有するディレクトリデータ１０００の一例を示している。
【００５３】
仮想ディレクトリが、ユーザがファイルシステムのスナップショットを調べたいとき、生成される。図１１は、仮想ディレクトリの構造１１００を示している。仮想ディレクトリの仮想ディレクトリデータ１１１０は、タイプ０のディレクトリエントリ１１２０を含むことができ、名前１１３０は、スナップショットの作成に関連付けられたタイムスタンプによって表現されることができる。ディレクトリエントリのハッシュ属性１１４０は、タイムスタンプに対応するＩノード１１５０のSmashを含むことができる。上記Ｉノード１１５０を通して、ユーザは、対応するより古いバージョンに対するアクセスを有することができる。ファイルシステムのスナップショットを調べる方法のさらなる詳細は、2014年10月10日に申請され“Hierarchical  Data  Archiving”と題された米国特許出願第14/512,299号に説明されており、該出願は本明細書において参照により援用される。
【００５４】
図１２は、ストレージクラスタにオブジェクトを書き込む方法１２００を示す「ライトオブジェクト」処理フロー図である。方法１２００は、ステップ１２１０において、書き込むべきオブジェクト及びオブジェクトタイプを受信することから始まる。ステップ１２２０において、オブジェクトのSmashが計算される。ステップ１２３０において、オブジェクトのコピーを有するべき物理ノードが、一貫したハッシングアルゴリズム（Consistent  Hashing  Algorithm）を適用することによって発見される。一貫したハッシングアルゴリズムは、2012年4月6日に申請され“Consistent  Ring  Namespaces  Facilitating  Data  Storage  and  Organization  in  Network  Infrastructures”と題された米国特許出願第13/441,592号において説明されており、該出願は本明細書において参照により援用される。ステップ１２４０において、オブジェクト及びSmashが、前のステップ１２３０において決定された各物理ノードに対して送信される。各ノードは、そのハッシュデータベース（ＨＤＢ）内でSmashのルックアップを実行する。ルックアップは、2012年4月6日に申請され“Cryptographic  Hash  Database”と題された米国特許出願第13/441,715号において説明される方法を用いて実行されてもよく、該出願は本明細書において参照により援用される。ルックアップはオブジェクトメタデータを返し、オブジェクトメタデータは、このSmashを有するオブジェクトについてのディスク識別子とディスク上の場所とを含む。ステップ１２５０において、ルックアップが成功する場合、オブジェクトが既に存在するので、オブジェクトの新しいコピーは書き込まれない。ルックアップが失敗する場合、ステップ１２６０において、オブジェクトの新しいコピーが、ステップ１２３０において一貫したハッシングアルゴリズムにより決定されたとおりのクラスタの中のノード及びディスクに書き込まれる。オブジェクトをディスクに書き込む方法は、2013年10月16日に申請され“Forward-Only  Page  Data  Storage  Management”と題された米国特許出願第14/055,662号において説明されており、該出願は本明細書において参照により援用される。ステップ１２７０において、オブジェクトを書き込んだ各ノードは、そのＨＤＢを、オブジェクトの新しい属性を用いて更新する。ＨＤＢを更新する方法は、米国特許出願第13/441,715号（完全な引用文は上記）において説明されている。ステップ１２８０において、成功又は失敗の指標がライタ（writer）に返される。
【００５５】
図１３は、一例示的な実施形態に従う、ストレージクラスタからオブジェクトを読み出す方法１３００を示す「リードオブジェクト」処理フロー図である。方法１３００は、ステップ１３１０において、オブジェクトのSmashを受信することから始まる。ステップ１３２０において、2012年4月6日に申請され“Consistent  Ring  Namespaces  Facilitating  Data  Storage  and  Organization  in  Network  Infrastructures”と題された、本明細書において参照により援用される米国特許出願第13/441,592号に説明されるとおりの一貫したハッシングアルゴリズムが適用されて、オブジェクトのコピーを保持する可能性の最大から可能性の最小にソートされたノードのセットを発見する。ステップ１３３０において、各ノードにおいて、オブジェクトのSmashが、ノードに属するＨＤＢ内でルックアップされる。ＨＤＢを検索する方法は、米国特許出願第13/441,715号（完全な引用文は上記）において説明されている。Smashのレコードが発見される場合、方法１３００のステップ１３４０に進む。Smashが発見されない場合、ステップ１３３０におけるルックアップが、次に最も可能性のあるノード上で繰り返される。オブジェクトを発見することなく、すべてのノードが検索された場合、「発見されない（not  found）」の指標が要求元に返される。ステップ１３４０において、オブジェクトは、ステップ１３３０におけるルックアップにより受信されるデータから取得されるディスク識別子とディスク上の場所とを用いて、ディスクから読み出される。ディスクからオブジェクトを読み出す方法は、米国特許出願第14/055,662号（完全な引用文は上記）において説明されている。ステップ１３５０において、オブジェクトデータ及びメタデータが要求元に返される。このアルゴリズムは、１つ以上のノード上で同時的に実行され得ることが留意されるべきである。
【００５６】
図１４は、ストレージクラスタにファイルを書き込む一例示的な方法１４００を示す処理フロー図である。方法１４００は、ステップ１４１０において、ライタからファイルデータを受信することから始まる。ステップ１４１５において、ファイルデータはデータオブジェクトに分けられ、各データオブジェクトは最後のチャンクを除いてサイズBLKSZのものであり、最後のチャンクはBLKSZより小さい可能性がある。ステップ１４２０において、Smashが各データオブジェクトについて計算される。ステップ１４２５において、ポインタツリーが、図５、図６、図７Ａ、及び図７Ｂに示されるとおり、データオブジェクトSmashをリーフポインタノードに挿入することによって構築される。ステップ１４３０において、ポインタオブジェクトがフル（full）であるか、あるいはすべてのデータオブジェクトが処理されている場合、ポインタオブジェクトのSmashが計算され、親ポインタオブジェクトに挿入される。ステップ１４３５において、ポインタオブジェクトの完全なツリーが構築されるまでステップ１４３０が繰り返される。ステップ１４４０において、ポインタオブジェクトツリーのルートのSmashが、Ｉノードオブジェクトのchashフィールドに挿入される。ステップ１４４５において、他のＩノード属性、例えばファイルサイズ、タイムスタンプなどが、更新される。ステップ１４５０において、ＩノードオブジェクトのSmashが計算される。ステップ１４５５において、本処理により作成され又は修正された各オブジェクトについて、図１２に説明されるとおりの「ライトオブジェクト」処理が呼び出される。最後、ステップ１４６０において、成功又は失敗がライタに返される。
【００５７】
図１５は、ストレージクラスタからファイルを読み出す方法１５００を示す処理フロー図である。方法１５００は、ステップ１５１０において、リーダ（reader）からＩノードオブジェクトのSmashを受信することから始まる。ステップ１５２０において、図１３に説明される「リードオブジェクト」処理が使用されて、Ｉノードオブジェクトを読み出す。ステップ１５３０において、ポインタツリーのルートが、Ｉノードオブジェクトのchash属性からSmashを取り出すことによって発見される。ステップ１５４０において、ポインタツリーが、chashから始め、子のSmashを取り出すことと図１３に説明される「リードオブジェクト」処理を適用してオブジェクトを読み出すこととによって、リーフノードへ下降される。ステップ１５５０において、データオブジェクトが、順次（sequential）ファイルデータへと再組立てされる。ステップ１５６０において、ファイルデータがリーダに返される。
【００５８】
図１６は、コンピュータシステム１６００の例示的な電子形態におけるマシンのコンピューティング装置の概略表現を示しており、これにおいて、本明細書に論じられる方法論のうち任意の１つ以上をマシンに実行させる命令セットが実行されることができる。様々な例示的な実施形態において、マシンはスタンドアロン装置として動作し、あるいは他のマシンに接続され（例えば、ネットワーク化され）てもよい。ネットワーク化された展開において、マシンは、サーバクライアントネットワーク環境の中でサーバ又はクライアントマシンの能力において、又は、ピアツーピア（又は、分散型）ネットワーク環境においてピアマシンとして動作し得る。マシンは、サーバ、パーソナルコンピュータ（ＰＣ）、タブレットＰＣ、セットトップボックス（ＳＴＢ）、ＰＤＡ、セルラー電話、デジタルカメラ、ポータブル音楽プレーヤ（例えば、ＭＰ３（Moving  Picture  Experts  Group  Audio  Layer  3）プレーヤなどのポータブルハードドライブオーディオ装置）、ウェブ家電製品、ネットワークルータ、スイッチ、ブリッジ、又は、マシンにより行われるべきアクションを指定する命令セット（順次の、又はその他の）を実行することができる任意のマシンであり得る。さらに、単一のマシンだけが例示されているが、用語「マシン」は、さらに、命令の一セット（又は、複数のセット）を個々に又は共同で実行して本明細書に論じられる方法論のうち任意の１つ以上を遂行するマシンの任意の集合を含むものとみなされるべきである。
【００５９】
例示的なコンピュータシステム１６００は、一のプロセッサ又は複数のプロセッサ１６０２、ハードディスクドライブ１６０４、メインメモリ１６０６、及びスタティックメモリ１６０８を含み、これらは、バス１６１０を介して互いに通信する。コンピュータシステム１６００は、ネットワークインターフェース装置１６１２をさらに含み得る。ハードディスクドライブ１６０４は、コンピュータ可読媒体１６２０を含み、コンピュータ可読媒体１６２０は、本明細書に説明される方法論又は機能のうち任意の１つ以上を具現化し又は該１つ以上により利用される１つ以上の命令セット１６２２を記憶する。命令１６２２は、さらに、コンピュータシステム１６００による命令１６２２の実行の間、メインメモリ１６０６内及び／又はプロセッサ１６０２内に、完全に又は少なくとも部分的に存在し得る。メインメモリ１６０６及びプロセッサ１６０２もまた、マシン可読媒体を構成する。
【００６０】
コンピュータ可読媒体１６２０が、一例示的な実施形態において単一の媒体であるように図示されているが、用語「コンピュータ可読媒体」は、１つ以上の命令セットを記憶する単一の媒体又は複数の媒体（例えば、集中型又は分散型のデータベース及び／又は関連付けられたキャッシュ及びサーバ）を含むようにみなされるべきである。用語「コンピュータ可読媒体」は、さらに、マシンによる実行のための命令セットを記憶し、エンコードし、又は運ぶことができて、本出願の方法論のうち任意の１つ以上をマシンに実行させ、あるいは上記の命令セットにより利用され又はこれに関連付けられたデータ構造を記憶し、エンコードし、又は運ぶことができる任意の媒体を含むようにみなされるべきである。用語「コンピュータ可読媒体」は、したがって、これらに限られないが、ソリッドステートメモリ並びに光及び磁気媒体を含むようにみなされるべきである。こうした媒体には、さらに、限定でなく、ハードディスク、フロッピーディスク、ＮＡＮＤ又はＮＯＲフラッシュメモリ、デジタルビデオディスク、ＲＡＭ、ＲＯＭなどが含まれ得る。
【００６１】
本明細書に説明される例示的な実施形態は、コンピュータ上にインストールされるコンピュータ実行可能命令（例えば、ソフトウェア）を含む動作環境において、ハードウェアにおいて、又はソフトウェアとハードウェアとの組み合わせにおいて実装され得る。コンピュータ実行可能命令は、コンピュータプログラミング言語において書かれてもよく、あるいはファームウェアロジックにおいて具現化されてもよい。認識されている標準に合うプログラミング言語において書かれる場合、上記の命令は、様々なハードウェアプラットフォーム上で、及び、様々なオペレーティングシステムに対するインターフェースのために実行されることができる。これらに限定されないが、本願方法を実施するコンピュータソフトウェアプログラムは、任意数の適切なプログラミング言語、例えば、Ｃ、Ｐｙｔｈｏｎ、Ｊａｖａｓｃｒｉｐｔ（登録商標）、Ｇｏ、又は、他のコンパイラ、アセンブラ、インタプリタ、若しくは他のコンピュータの言語若しくはプラットフォームにおいて書かれることができる。
【００６２】
こうして、ファイルシステムのコンテンツベースの編成のためのシステム及び方法が開示されている。実施形態が、特定の例示的な実施形態を参照して説明されたが、本出願のより広い主旨及び範囲から逸脱することなく、上記の例示的な実施形態に対して様々な修正及び変更がなされ得ることが明らかであり得る。したがって、明細書及び図面は、限定的ではなく例示的な意味において考慮されるべきである。
【図１】
2017504924.tif 000003
【図２】
2017504924.tif 000004
【図３】
2017504924.tif 000005
【図４】
2017504924.tif 000006
【図５】
2017504924.tif 000007
【図６】
2017504924.tif 000008
【図７Ａ】
2017504924.tif 000009
【図７Ｂ】
2017504924.tif 000010
【図８】
2017504924.tif 000011
【図９】
2017504924.tif 000012
【図１０】
2017504924.tif 000013
【図１１】
2017504924.tif 000014
【図１２】
2017504924.tif 000015
【図１３】
2017504924.tif 000016
【図１４】
2017504924.tif 000017
【図１５】
2017504924.tif 000018
【図１６】
2017504924.tif 000019
【国際調査報告】
2017504924.tif 000020