(57)【要約】      （修正有）【課題】分散ストレージシステムにおいて一部がメンテナンス期間中であってもユーザが利用可能なデータ分散方法を提供する。【解決手段】データを分散させる方法は、非一時的なメモリ内にファイルを受取るステップ（８０２）と、非一時的なメモリと通信するコンピュータプロセッサを用いて、受取られたファイルをチャンクに分割するステップ（８０４）と、分散ストレージシステムのメンテナンス階層に基づいて、チャンクを分散ストレージシステムのストレージデバイスに分散させるステップ（８０６）を含む。メンテナンス階層は、各々がアクティブ状態と非アクティブ状態とを有するメンテナンスユニットを含む。さらに、各ストレージデバイスは、メンテナンスユニットに関連付けられる。メンテナンスユニットが非アクティブ状態にあるときにファイルのアクセス性を維持するために、チャンクは、複数のメンテナンスユニットにわたって分散される。【選択図】図８
2018110008.tif 000002
【特許請求の範囲】
【請求項１】
分散ストレージシステム（１００）においてデータを分散させる方法であって、
非一時的なメモリ（２０４）内にファイル（３１０）を受取るステップと、
前記非一時的なメモリ（２０４）と通信するコンピュータプロセッサ（２０２）を用いて、前記受取られたファイル（３１０）をチャンク（３３０）に分割するステップと、
前記分散ストレージシステム（１００）のメンテナンス階層（４００）に基づいて、前記チャンク（３３０）を前記分散ストレージシステム（１００）のストレージデバイス（１１４）に分散させるステップとを備え、前記メンテナンス階層（４００）は、アクティブ状態と非アクティブ状態とを有するメンテナンスユニット（４０２）を備え、各ストレージデバイス（１１４）は、メンテナンスユニット（４０２）に関連付けられ、メンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ファイル（３１０）のアクセス性を維持するために、前記チャンク（３３０）は、複数のメンテナンスユニット（４０２）にわたって分散される、方法。
【請求項２】
いずれか１つのメンテナンスユニット（４０２）のストレージデバイス（１１４）に分散されるチャンク（３３０）の数を制限するステップをさらに備える、請求項１に記載の方法。
【請求項３】
前記ストレージデバイス（１１４）の間での前記チャンク（３３０）の分散を決定するステップをさらに備え、前記決定するステップは、
前記ファイル（３１０）のチャンク（３３０）の数に一致するストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を決定することによって、および
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の選択群が前記ファイル（３１０）のアクセス性を維持することができるか否かを判断することによって、行われる、請求項１に記載の方法。
【請求項４】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）が前記ファイル（３１０）のアクセス性を維持することができない場合、前記ファイル（３１０）のチャンク（３３０）の数に一致するストレージデバイス（１１４）の第２の無作為選択群（１５０ｂ）を決定する、請求項３に記載の方法。
【請求項５】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）が前記ファイル（３１０）のアクセス性を維持することができない場合、１つ以上の無作為に選択されたストレージデバイス（１１４）を追加および除去することによって前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を修正する、請求項３に記載の方法。
【請求項６】
単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を決定する、請求項３に記載の方法。
【請求項７】
前記分散ストレージシステム（１００）の前記ストレージデバイス（１１４）の順序付き循環リスト（１６０）から前記ファイル（３１０）のチャンク（３３０）の数に等しい連続的な数のストレージデバイス（１１４）を選択することによって、前記ストレージデバイス（１１４）の間での前記チャンク（３３０）の分散を決定するステップをさらに備える、請求項１に記載の方法。
【請求項８】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記選択されたストレージデバイス（１１４）が全体として前記ファイル（３１０）のアクセス性
を維持することができない場合、前記順序付き循環リスト（１６０）から前記ファイル（３１０）のチャンク（３３０）の数に等しい別の連続的な数のストレージデバイス（１１４）を選択するステップをさらに備える、請求項７に記載の方法。
【請求項９】
前記分散ストレージシステム（１００）のストレージデバイス（１１４）の前記順序付き循環リスト（１６０）を決定するステップをさらに備え、前記順序付き循環リスト（１６０）上の隣接するストレージデバイスは、異なるメンテナンスユニット（４０２）に関連付けられる、請求項７に記載の方法。
【請求項１０】
前記順序付き循環リスト（１６０）上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニット（４０２）に関連付けられる、請求項９に記載の方法。
【請求項１１】
前記順序付き循環リスト（１６０）上の閾値数の連続的なストレージデバイス（１１４）は、各々が異なる地理的場所にある、請求項９に記載の方法。
【請求項１２】
前記コンピュータプロセッサ（２０２）を用いてメンテナンスユニット（４０２）のメンテナンス階層（４００）を決定するステップをさらに備え、前記メンテナンス階層（４００）は、メンテナンスレベル（４０１）を有し、各メンテナンスレベル（４０１）は、１つ以上のメンテナンスユニット（４０２）を備え、
各メンテナンスユニット（４０２）を少なくとも１つのストレージデバイス（１１４）にマッピングするステップをさらに備える、請求項１に記載の方法。
【請求項１３】
各メンテナンスユニット（４０２）は、単一の配電ユニットまたは単一の電力バスダクト（４３０）によって電力を供給されるストレージデバイス（１１４）を備える、請求項１２に記載の方法。
【請求項１４】
前記受取られたファイル（３１０）をストライプ（３２０）に分割するステップをさらに備え、各ファイル（３１０）は、レプリケーションコード（３１１）および／またはエラー修正コード（３１３）を含み、
前記ファイル（３１０）がレプリケーションコード（３１１）を含む場合、少なくとも１つのストライプ（３２０）をレプリケーションチャンク（３３０）としてレプリケートするステップと、
前記ファイル（３１０）がエラー修正コード（３１３）を含む場合、少なくとも１つのストライプ（３２０）をデータチャンク（３３０ｎｄｋ）およびコードチャンク（３３０ｎｃｍ）に分割するステップとをさらに備える、請求項１に記載の方法。
【請求項１５】
前記ストレージデバイス（１１４）の間で前記データチャンク（３３０ｎｄｋ）および前記コードチャンク（３３０ｎｃｍ）を分散させるのとは異なって、前記ストレージデバイス（１１４）の間でレプリケーションチャンク（３３０）を分散させるステップをさらに備える、請求項１４に記載の方法。
【請求項１６】
分散ストレージシステム（１００）においてデータを分散させるためのシステムであって、
ファイル（３１０）を受取る非一時的なメモリ（２０４）と、
前記非一時的なメモリ（２０４）と通信するコンピュータプロセッサ（２０２）とを備え、前記コンピュータプロセッサ（２０２）は、前記受取られたファイル（３１０）をチャンク（３３０）に分割し、前記システムはさらに、
前記コンピュータプロセッサ（２０２）および前記非一時的なメモリ（２０４）と通信するストレージデバイス（１１４）を備え、前記コンピュータプロセッサ（２０２）は、前記分散ストレージシステム（１００）のメンテナンス階層（４００）に基づいて前記チ
ャンク（３３０）を前記ストレージデバイス（１１４）に格納し、前記メンテナンス階層（４００）は、アクティブ状態と非アクティブ状態とを有するメンテナンスユニット（４０２）を備え、各ストレージデバイス（１１４）は、メンテナンスユニット（４０２）に関連付けられ、前記コンピュータプロセッサ（２０２）は、メンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ファイル（３１０）のアクセス性を維持するために前記チャンク（３３０）を複数のメンテナンスユニット（４０２）にわたって分散させる、システム。
【請求項１７】
前記コンピュータプロセッサ（２０２）は、いずれか１つのメンテナンスユニット（４０２）のストレージデバイス（１１４）に分散されるチャンク（３３０）の数を制限する、請求項１６に記載のシステム。
【請求項１８】
前記コンピュータプロセッサ（２０２）は、前記ストレージデバイス（１１４）の間での前記チャンク（３３０）の分散を決定し、前記決定は、
前記ファイル（３１０）のチャンク（３３０）の数に一致するストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を決定することによって、および
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の選択群が前記ファイル（３１０）のアクセス性を維持することができるか否かを判断することによって、行われる、請求項１６に記載のシステム。
【請求項１９】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）が前記ファイル（３１０）のアクセス性を維持することができない場合、前記コンピュータプロセッサ（２０２）は、前記ファイル（３１０）のチャンク（３３０）の数に一致するストレージデバイス（１１４）の第２の無作為選択群（１５０ｂ）を決定する、請求項１８に記載のシステム。
【請求項２０】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）が前記ファイル（３１０）のアクセス性を維持することができない場合、前記コンピュータプロセッサ（２０２）は、１つ以上の無作為に選択されたストレージデバイス（１１４）を追加および除去することによって前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を修正する、請求項１８に記載のシステム。
【請求項２１】
前記コンピュータプロセッサ（２０２）は、単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて前記ストレージデバイス（１１４）の第１の無作為選択群（１５０ａ）を決定する、請求項１８に記載のシステム。
【請求項２２】
前記コンピュータプロセッサ（２０２）は、前記分散ストレージシステム（１００）の前記ストレージデバイス（１１４）の順序付き循環リスト（１６０）から前記ファイル（３１０）のチャンク（３３０）の数に等しい連続的な数のストレージデバイス（１１４）を選択することによって、前記ストレージデバイス（１１４）の間での前記チャンク（３３０）の分散を決定する、請求項１６に記載のシステム。
【請求項２３】
１つ以上のメンテナンスユニット（４０２）が非アクティブ状態にあるときに前記選択されたストレージデバイス（１１４）が全体として前記ファイル（３１０）のアクセス性を維持することができない場合、前記コンピュータプロセッサ（２０２）は、前記順序付き循環リスト（１６０）から前記ファイル（３１０）のチャンク（３３０）の数に等しい別の連続的な数のストレージデバイス（１１４）を選択する、請求項２２に記載のシステム。
【請求項２４】
前記コンピュータプロセッサ（２０２）は、前記分散ストレージシステム（１００）のストレージデバイス（１１４）の前記順序付き循環リスト（１６０）を決定し、前記順序付き循環リスト（１６０）上の隣接するストレージデバイスは、異なるメンテナンスユニット（４０２）に関連付けられる、請求項２２に記載のシステム。
【請求項２５】
前記順序付き循環リスト（１６０）上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニット（４０２）に関連付けられる、請求項２４に記載のシステム。
【請求項２６】
前記順序付き循環リスト（１６０）上の閾値数の連続的なストレージデバイスは、各々が異なる地理的場所にある、請求項２４に記載のシステム。
【請求項２７】
前記コンピュータプロセッサ（２０２）は、メンテナンスユニット（４０２）のメンテナンス階層（４００）を決定し、前記メンテナンス階層（４００）は、メンテナンスレベル（４０１）を有し、各メンテナンスレベル（４０１）は、１つ以上のメンテナンスユニット（４０２）を備え、
前記コンピュータプロセッサ（２０２）は、各メンテナンスユニット（４０２）を少なくとも１つのストレージデバイス（１１４）にマッピングする、請求項１６に記載のシステム。
【請求項２８】
各メンテナンスユニット（４０２）は、単一の配電ユニットまたは単一の電力バスダクト（４３０）によって電力を供給されるストレージデバイス（１１４）を備える、請求項２７に記載のシステム。
【請求項２９】
前記コンピュータプロセッサ（２０２）は、
前記受取られたファイル（３１０）をストライプ（３２０）に分割し、各ファイル（３１０）は、レプリケーションコード（３１１）および／またはエラー修正コード（３１３）を含み、前記コンピュータプロセッサ（２０２）はさらに、
前記ファイル（３１０）がレプリケーションコード（３１１）を含む場合、少なくとも１つのストライプ（３２０）をレプリケーションチャンク（３３０）としてレプリケートし、
前記ファイル（３１０）がエラー修正コード（３１３）を含む場合、少なくとも１つのストライプ（３２０）をデータチャンク（３３０ｎｄｋ）およびコードチャンク（３３０ｎｃｍ）に分割する、請求項１６に記載のシステム。
【請求項３０】
前記コンピュータプロセッサ（２０２）は、前記ストレージデバイス（１１４）の間で前記データチャンク（３３０ｎｄｋ）および前記コードチャンク（３３０ｎｃｍ）を分散させるのとは異なって、前記ストレージデバイス（１１４）の間でチャンク（３３０）をレプリケートする、請求項２９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本開示は、分散ストレージシステム上でデータを分散させることに関する。
【背景技術】
【０００２】
背景
一般に、分散システムは、多数のゆるく結合されたコンピュータを含んでおり、当該コンピュータの各々は、典型的には、コンピューティングリソース（例えば１つ以上のプロセッサ）および／またはストレージリソース（例えばメモリ、フラッシュメモリおよび／またはディスク）を含んでいる。分散ストレージシステムは、ストレージアブストラクション（例えばキー／値格納またはファイルシステム）を分散システムのストレージリソースに重ね合わせる。分散ストレージシステムでは、一方のコンピュータで実行されるサーバプロセスは、当該コンピュータのストレージリソースを、他方のコンピュータで実行されるクライアントプロセスにエクスポートし得る。リモートプロシージャコール（remote
procedure calls：ＲＰＣ）は、サーバプロセスからクライアントプロセスにデータを転送し得る。代替的に、サーバハードウェアからクライアントプロセスにデータを転送するために、リモートダイレクトメモリアクセス（Remote Direct Memory Access：ＲＤＭＡ
）プリミティブが使用されてもよい。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
本開示の一局面は、分散ストレージシステムにおいてデータを分散させる方法を提供する。上記方法は、非一時的なメモリ内にファイルを受取るステップと、上記非一時的なメモリと通信するコンピュータプロセッサを用いて、上記受取られたファイルをチャンクに分割するステップとを含む。また、上記方法は、上記分散ストレージシステムのメンテナンス階層に基づいて、チャンクを上記分散ストレージシステムのストレージデバイスに分散させるステップを含む。上記メンテナンス階層は、各々がアクティブ状態と非アクティブ状態とを有するメンテナンスユニットを含む。さらに、各ストレージデバイスは、メンテナンスユニットに関連付けられる。メンテナンスユニットが非アクティブ状態にあるときに上記ファイルのアクセス性を維持するために、上記チャンクは、複数のメンテナンスユニットにわたって分散される。
【０００４】
本開示の実現例は、以下の特徴のうちの１つ以上を含み得る。いくつかの実現例では、上記方法は、いずれか１つのメンテナンスユニットのストレージデバイスに分散されるチャンクの数を制限するステップをさらに含む。
【０００５】
いくつかの実現例では、上記方法は、上記ストレージデバイスの間での上記チャンクの分散を決定するステップをさらに含み、上記決定するステップは、上記ファイルのチャンクの数に一致するストレージデバイスの第１の無作為選択群を決定することによって、および、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記ストレージデバイスの選択群が上記ファイルのアクセス性を維持することができるか否かを判断することによって、行われる。いくつかの例では、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記ストレージデバイスの第１の無作為選択群が上記ファイルのアクセス性を維持することができない場合、上記方法は、上記ファイルのチャンクの数に一致するストレージデバイスの第２の無作為選択群を決定するステップ、または、１つ以上の無作為に選択されたストレージデバイスを追
加または除去することによって上記ストレージデバイスの第１の無作為選択群を修正するステップをさらに含む。上記方法は、単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて上記ストレージデバイスの第１の無作為選択群を決定するステップをさらに含み得る。
【０００６】
いくつかの実現例では、上記方法は、上記分散ストレージの上記ストレージデバイスの順序付き循環リストから上記ファイルのチャンクの数に等しい連続的な数のストレージデバイスを選択することによって、上記ストレージデバイスの間での上記チャンクの分散を決定するステップをさらに含む。１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記選択されたストレージデバイスが集合的に上記ファイルのアクセス性を維持することができない場合、上記方法は、上記順序付き循環リストから上記ファイルのチャンクの数に等しい別の連続的な数のストレージデバイスを選択するステップをさらに含む。さらにまたは代替的に、上記方法は、上記分散ストレージシステムのストレージデバイスの上記順序付き循環リストを決定するステップをさらに含む。上記順序付き循環リスト上の隣接するストレージデバイスは、異なるメンテナンスユニットに関連付けられる。いくつかの例では、上記順序付き循環リスト上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニットに関連付けられるか、または、各々が異なる地理的場所にある。
【０００７】
いくつかの実現例では、上記方法は、（例えば上記コンピュータプロセッサを用いて）メンテナンスユニットのメンテナンス階層を決定するステップをさらに含み、上記メンテナンス階層は、メンテナンスレベルを有し、各メンテナンスレベルは、１つ以上のメンテナンスユニットを含む。また、上記方法は、各メンテナンスユニットを少なくとも１つのストレージデバイスにマッピングするステップを含む。いくつかの例では、各メンテナンスユニットは、単一の配電ユニットまたは単一の電力バスダクトによって電力を供給されるストレージデバイスを含む。さらにまたは代替的に、メンテナンスユニットは、（散発的にまたは定期的に）メンテナンスを必要とする冷却ユニットまたはその他の１つの機器に関連付けられるストレージデバイスを含み得る。
【０００８】
上記方法は、上記受取られたファイルをストライプに分割するステップをさらに含み得る。各ファイルは、レプリケーションコードまたは誤り訂正符号を含む。上記ファイルがレプリケーションコードを含む場合、上記方法は、少なくとも１つのストライプをレプリケーションチャンクとしてレプリケートするステップを含む。上記ファイルが誤り訂正符号を含む場合、上記方法は、少なくとも１つのストライプをデータチャンクおよびコードチャンクに分割するステップを含む。また、上記方法は、上記ストレージデバイスの間で上記データチャンクおよび上記コードチャンクを分散させるのとは異なって、上記ストレージデバイスの間でレプリケーションチャンクを分散させるステップを含み得る。
【０００９】
本開示の別の局面は、分散ストレージシステムにおいてデータを分散させるためのシステムを提供する。上記システムは、非一時的なメモリと、コンピュータプロセッサと、ストレージデバイスとを含む。上記非一時的なメモリは、１つ以上のファイルをユーザから受取る。上記コンピュータプロセッサは、上記非一時的なメモリと通信し、上記受取られたファイルをチャンクに分割する。上記ストレージデバイスは、上記コンピュータプロセッサおよび上記非一時的なメモリと通信する。上記コンピュータプロセッサは、上記分散ストレージシステムのメンテナンス階層に基づいて上記チャンクを上記ストレージデバイスに格納する。上記メンテナンス階層は、アクティブ状態と非アクティブ状態とを有するメンテナンスユニットを含む。各ストレージデバイスは、メンテナンスユニットに関連付けられる。上記コンピュータプロセッサは、メンテナンスユニットが非アクティブ状態にあるときに上記ファイルのアクセス性を維持するために上記チャンクを複数のメンテナンスユニットにわたって分散させる。
【００１０】
いくつかの例では、上記コンピュータプロセッサは、いずれか１つのメンテナンスユニットのストレージデバイスに分散されるチャンクの数を制限する。上記コンピュータプロセッサは、上記ストレージデバイスの間での上記チャンクの分散を決定し得て、上記決定は、上記ファイルのチャンクの数に一致するストレージデバイスの第１の無作為選択群を決定することによって、および、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記ストレージデバイスの選択群が上記ファイルのアクセス性を維持することができるか否かを判断することによって、行われる。さらにまたは代替的に、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記ストレージデバイスの第１の無作為選択群が上記ファイルのアクセス性を維持することができない場合、上記コンピュータプロセッサは、上記ファイルのチャンクの数に一致するストレージデバイスの第２の無作為選択群を決定し得る。
【００１１】
いくつかの実現例では、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記ストレージデバイスの第１の無作為選択群が上記ファイルのアクセス性を維持することができない場合、上記コンピュータプロセッサは、１つ以上の無作為に選択されたストレージデバイスを追加および除去することによって上記ストレージデバイスの第１の無作為選択群を修正する。さらにまたは代替的に、上記コンピュータプロセッサは、単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて上記ストレージデバイスの第１の無作為選択群を決定し得る。
【００１２】
いくつかの例では、上記コンピュータプロセッサは、上記分散ストレージシステムの上記ストレージデバイスの順序付き循環リストから上記ファイルのチャンクの数に等しい連続的な数のストレージデバイスを選択することによって、上記ストレージデバイスの間での上記チャンクの分散を決定する。さらにまたは代替的に、１つ以上の（または閾値数の）メンテナンスユニットが非アクティブ状態にあるときに上記選択されたストレージデバイスが集合的に上記ファイルのアクセス性を維持することができない場合、上記コンピュータプロセッサは、上記順序付き循環リストから上記ファイルのチャンクの数に等しい別の連続的な数のストレージデバイスを選択し得る。
【００１３】
いくつかの実現例では、上記コンピュータプロセッサは、上記分散ストレージシステムのストレージデバイスの上記順序付き循環リストを決定し、上記順序付き循環リスト上の隣接するストレージデバイスは、異なるメンテナンスユニットに関連付けられる。さらにまたは代替的に、上記順序付き循環リスト上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニットに関連付けられ得る。さらにまたは代替的に、上記順序付き循環リスト上の閾値数の連続的なストレージデバイスは、各々が異なる地理的場所にあり得る。
【００１４】
いくつかの例では、上記コンピュータプロセッサは、メンテナンスユニットのメンテナンス階層を決定し、各メンテナンスユニットを少なくとも１つのストレージデバイスにマッピングする。上記メンテナンス階層は、メンテナンスレベルを有し、各メンテナンスレベルは、１つ以上のメンテナンスユニットを含む。さらにまたは代替的に、各メンテナンスユニットは、単一の配電ユニットまたは単一の電力バスダクトによって電力を供給されるストレージデバイスを含み得る。
【００１５】
いくつかの実現例では、上記コンピュータプロセッサは、上記受取られたファイルをストライプに分割し、各ファイルは、レプリケーションコードおよび／または誤り訂正符号を含む。上記ファイルがレプリケーションコードを含む場合、上記コンピュータプロセッサは、少なくとも１つのストライプをレプリケーションチャンクとしてレプリケートする。上記ファイルが誤り訂正符号を含む場合、上記コンピュータプロセッサは、少なくとも
１つのストライプをデータチャンクおよびコードチャンクに分割する。さらにまたは代替的に、上記コンピュータプロセッサは、上記ストレージデバイスの間で上記データチャンクおよび上記コードチャンクを分散させるのとは異なって、上記ストレージデバイスの間でチャンクをレプリケートし得る。
【００１６】
本開示の１つ以上の実現例の詳細は、添付の図面および以下の説明に記載されている。他の局面、特徴および利点は、説明および図面ならびに特許請求の範囲から明らかになるであろう。
【００１７】
さまざまな図面中の同様の参照符号は、同様の要素を示す。
【図面の簡単な説明】
【００１８】
【図１Ａ】例示的な分散ストレージシステムの概略図である。
【図１Ｂ】キュレータによって管理されるメモリホストのセルを有する例示的な分散ストレージシステムの概略図である。
【図１Ｃ】分散ストレージシステムの例示的なセルの概略図である。
【図２】分散ストレージシステムのための例示的なキュレータの概略図である。
【図３Ａ】レプリケートされたストライプに分割される例示的なファイルの概略図である。
【図３Ｂ】データチャンクおよびコードチャンクに分割される例示的なファイルの概略図である。
【図４Ａ】例示的なメンテナンス階層の概略図である。
【図４Ｂ】例示的なメンテナンス階層の概略図である。
【図４Ｃ】例示的なメンテナンス階層の概略図である。
【図５Ａ】ストレージリソースの群を無作為に選択するためのオペレーションの例示的な構成のフローチャートである。
【図５Ｂ】ストレージデバイスの例示的な無作為選択群の概略図である。
【図６Ａ】ストレージリソースの群を無作為に選択し、次いで当該群内のストレージデバイスを無作為に更新するためのオペレーションの例示的な構成のフローチャートである。
【図６Ｂ】ストレージデバイスの例示的な無作為選択群の概略図である。
【図７Ａ】循環リストからストレージリソースの群を選択するためのオペレーションの例示的な構成のフローチャートである。
【図７Ｂ】順序付きリストからのストレージデバイスの例示的な選択の概略図である。
【図８】ストレージシステムにおいてデータを分散させるためのオペレーションの例示的な構成の概略図である。
【発明を実施するための形態】
【００１９】
詳細な説明
ストレージシステムは、冗長性を有する複数の層を含み、当該層において、データはレプリケートされて複数のデータセンタに格納される。データセンタは、電気通信およびストレージシステム１００（図１Ａ〜図１Ｃ）などのコンピュータシステムおよびそれらの関連のコンポーネントを収容している。データセンタは、通常、バックアップ電源と、冗長な通信接続部と、（一定の温度を維持するための）環境制御部と、セキュリティデバイスとを含んでいる。データセンタは、（例えば小さな町と同じぐらいの）大量の電気を使用する大産業規模オペレーションであり得る。データは、さまざまな地理的場所（例えばさまざまな都市、さまざまな国およびさまざまな大陸）に位置し得る。いくつかの例では、（例えば、停電もしくは部品を交換するためのストレージシステムの一部の切離し、またはシステム故障、またはそれらの組み合わせのために）データセンタまたはその一部は
、メンテナンスを必要とする。これらのデータセンタに格納されたデータは、メンテナンス期間中はユーザが利用することはできない可能性があり、その結果、ユーザのオペレーションが損なわれるまたは停止することになる。したがって、ストレージシステム１００またはその一部がメンテナンスを受けているにもかかわらずユーザが格納されたデータを検索することができる分散ストレージシステム１００を提供することが望ましい。
【００２０】
図１Ａ〜図１Ｃを参照して、いくつかの実現例では、分散ストレージシステム１００は、ゆるく結合されたメモリホスト１１０，１１０ａ〜１１０ｎ（例えばコンピュータまたはサーバ）を含み、各々は、データのキャッシングに使用され得るストレージリソース１１４（例えばメモリ、フラッシュメモリ、ダイナミックランダムアクセスメモリ（dynamic random access memory：ＤＲＡＭ）、相変化メモリ（phase change memory：ＰＣＭ）
、および／またはディスク）と通信するコンピューティングリソース１１２（例えば１つ以上のプロセッサまたは中央処理装置（central processing unit：ＣＰＵ））を有する
。ストレージリソース１１４に重ね合わせられるストレージアブストラクション（例えばキー／値格納またはファイルシステム）は、１つ以上のクライアント１２０，１２０ａ〜１２０ｎによるストレージリソース１１４のスケーラブルな使用を可能にする。クライアント１２０は、（例えばＲＰＣによって）ネットワーク１３０を介してメモリホスト１１０と通信し得る。
【００２１】
いくつかの実現例では、分散ストレージシステム１００は「一方向」であり、いかなるサーバジョブもクライアント１２０からのリモートプロシージャコール（ＲＰＣ）に応答してそれらの対応するメモリホスト１１０上でデータ３１２を格納または検索することを不要にし、その代わりにリモート要求１２２を処理するために専用のハードウェアに依拠し得る。「一方向」とは、メモリホスト１１０上での要求処理の大半が、メモリホスト１１０のＣＰＵ１１２で実行されるソフトウェアによってではなく、ハードウェアにおいてなされることができる方法を指す。クライアント１２０で実行されるクライアントプロセス１２８への対応するストレージリソース１１４（例えば非一時的なメモリ）のアクセスをエクスポートするサーバプロセス１１８をメモリホスト１１０（例えばサーバ）のプロセッサ１１２に実行させるのではなく、クライアント１２０は、メモリホスト１１０のネットワークインターフェースコントローラ（network interface controller：ＮＩＣ）１１６を介してストレージリソース１１４に直接アクセスすることができる。換言すれば、クライアント１２０で実行されるクライアントプロセス１２８は、コンピューティングリソース１１２で実行されるいかなるサーバプロセス１１８のルーチンも実行する必要なしに、１つ以上のストレージリソース１１４と直接接続することができる。この一方向分散ストレージアーキテクチャは、比較的高いスループットおよび低い遅延を提供する。なぜなら、クライアント１２０は、メモリホスト１１０のコンピューティングリソース１１２と接続することなく、ストレージリソース１１４にアクセスできるからである。これは、ストレージ１１４の要件と典型的な二方向分散ストレージシステム１００が保持するＣＰＵサイクルとを分離する効果がある。一方向分散ストレージシステム１００は、メモリホスト１１０上に予備のＣＰＵサイクルがあるか否かにかかわらずリモートストレージリソース１１４を利用することができる。さらに、一方向オペレーションは、サーバＣＰＵリソース１１２を取り合わないので、メモリホスト１１０が高いＣＰＵ使用率で動作していても、一方向システムは、非常に予測可能な低遅延でキャッシュ要求１２２を供給することができる。したがって、一方向分散ストレージシステム１００は、予測可能な低遅延を提供しながら、従来の二方向システムよりも高いクラスタストレージ１１４およびＣＰＵリソース１１２の使用率を可能にする。
【００２２】
いくつかの実現例では、分散ストレージシステム１００は、ストレージロジック部１０２と、データ制御部１０４と、データストレージ部１０６とを含む。ストレージロジック部１０２は、例えばＲＰＣまたは一方向オペレーションを介して基本的なデータにアクセ
スすることを担うトランザクション・アプリケーション・プログラミング・インターフェース（application programming interface：ＡＰＩ）３５０（例えば一方向トランザク
ションシステムクライアントライブラリ）を含み得る。データ制御部１０４は、ストレージリソース１１４の割当て、対応するネットワークインターフェースコントローラ１１６へのストレージリソース１１４の登録、クライアント１２０とメモリホスト１１０との間の接続のセットアップ、マシンが故障した場合のエラーへの対処などのタスクにより、ストレージリソース１１４への割当ておよびアクセスを管理し得る。データストレージ部１０６は、ゆるく結合されたメモリホスト１１０，１１０ａ〜１１０ｎを含み得る。
【００２３】
分散ストレージシステム１００は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）１１４にデータ３１２を格納し、リモートダイレクトメモリアクセス（ＲＤＭＡ）対応のネットワークインターフェースコントローラ１１６を介して当該データ３１２をリモートホスト１１０から供給し得る。ネットワークインターフェースコントローラ１１６（ネットワークインターフェースカード、ネットワークアダプタまたはＬＡＮアダプタとしても知られている）は、コンピューティングリソース１１２をネットワーク１３０に接続するコンピュータハードウェアコンポーネントであり得る。メモリホスト１１０ａ〜１１０ｎもクライアント１２０も、各々、ネットワーク通信のためにネットワークインターフェースコントローラ１１６を有し得る。メモリホスト１１０のコンピューティングプロセッサ１１２で実行されるホストプロセス１１８は、メモリ１１４のリモートダイレクトメモリアクセス可能領域１１５ａ〜１１５ｎの組をネットワークインターフェースコントローラ１１６に登録する。ホストプロセス１１８は、読取り専用または読取り／書込みの許可により、メモリ１１４のリモートダイレクトメモリアクセス可能領域１１５ａ〜１１５ｎを登録し得る。メモリホスト１１０のネットワークインターフェースコントローラ１１６は、各々の登録されたメモリ領域１１５ａ〜１１５ｎについてクライアントキー３２１を作成する。
【００２４】
ネットワークインターフェースコントローラ１１６によって実行される一方向オペレーションは、単純な読取り、書込み、ならびに、比較およびスワップオペレーションに限定され得て、それらのうちどれも、キャッシュ要求を実行してキャッシュポリシを管理するために従来のキャッシュサーバジョブによって実行されるソフトウェアロジックの完全互換品の機能を果たすのに十分に精巧ではない可能性がある。トランザクションＡＰＩ３５０は、ルックアップまたは挿入データコマンドなどのコマンドを基本的なネットワークインターフェースコントローラオペレーションのシーケンスに変換する。トランザクションＡＰＩ３５０は、分散ストレージシステム１００のデータ制御部１０４およびデータストレージ部１０６と接続する。
【００２５】
分散ストレージシステム１００は、ネットワークインターフェースコントローラ１１６とのリモートアクセスのためにメモリ１１４を登録して、クライアントプロセス１２８との接続をセットアップするために、同一場所で実行されるソフトウェアプロセスを含み得る。一旦接続がセットアップされると、クライアントプロセス１２８は、対応するメモリホスト１１０のローカルＣＰＵ１１２上のソフトウェアからのいかなる関与もなしに、ネットワークインターフェースコントローラ１１６のハードウェア内のエンジンを介して、登録されたメモリ１１４にアクセスすることができる。
【００２６】
図１Ｂおよび図１Ｃを参照して、いくつかの実現例では、分散ストレージシステム１００は、複数のセル２００を含み、各セル２００は、メモリホスト１１０と、メモリホスト１１０と通信するキュレータ２１０とを含む。キュレータ２１０（例えばプロセス）は、ネットワーク１３０に接続されたコンピューティングプロセッサ２０２（例えば非一時的なメモリ２０４を有するサーバ）で実行され、データストレージを管理し（例えばメモリホスト１１０に格納されたファイルシステムを管理し）、データ配置を制御し、および／
または、データ復旧を開始させ得る。さらに、キュレータ２１０は、メモリホスト１１０上のデータ３１２の存在および格納場所を追跡し得る。冗長なキュレータ２１０が可能である。いくつかの実現例では、キュレータ２１０は、冗長性および／または性能のために、複数のメモリホスト１１０にわたるデータ３１２のストライピング、ならびに、所与のストライプの複数のコピーの存在および／または場所を追跡する。コンピュータデータストレージにおいて、データストライピングは、シーケンシャルなセグメントのアクセスが異なる物理的ストレージデバイス１１４（例えばセル２００および／またはメモリホスト１１０）に対してなされるように、ファイル３１０（図２）などの論理的にシーケンシャルなデータ３１２をセグメント化する技術である。ストライピングは、ストレージデバイス１１４がアクセスを提供できるよりも速く処理装置がデータ３１２へのアクセスを要求する場合に有用である。複数のデバイスでセグメントアクセスを実行することによって、複数のセグメントに同時にアクセスすることができる。これにより、データアクセススループットが多くなり、プロセッサが無駄にデータアクセスを待つことが回避される。
【００２７】
いくつかの実現例では、トランザクションＡＰＩ３５０は、（例えばクライアントプロセス１２８を有する）クライアント１２０とキュレータ２１０との間を接続する。いくつかの例では、クライアント１２０は、１つ以上のリモートプロシージャコール（ＲＰＣ）を介してキュレータ２１０と通信する。クライアント要求１２２に応答して、トランザクションＡＰＩ３５０は、メモリホスト１１０上の特定のデータ３１２の格納場所を突き止め、データ３１２へのアクセスを可能にするキー３０２を取得し得る。トランザクションＡＰＩ３５０は、（例えばリモートダイレクトメモリアクセスを用いて）データ３１２を読取るまたは書込むために、（ネットワークインターフェースコントローラ１１６を介して）適切なメモリホスト１１０と直接通信する。メモリホスト１１０が動作しない場合、またはデータ３１２が異なるメモリホスト１１０に移動された場合には、クライアント要求１２２は失敗し、クライアント１２０がキュレータ２１０に再照会するよう促す。
【００２８】
図２を参照して、いくつかの実現例では、キュレータ２１０は、ファイルシステムメタデータ２１２を格納および管理する。メタデータ２１２は、ファイル３１０１〜３１０ｎをファイル記述子３００１〜３００ｎにマッピングするファイルマップ２１４を含み得る。キュレータ２１０は、その永続的なメタデータ２１２の表現を調べて修正し得る。キュレータ２１０は、メタデータ２１２のための３つの異なるアクセスパターン、すなわち読取り専用、ファイルトランザクションおよびストライプトランザクション、を使用し得る。
【００２９】
図３Ａおよび図３Ｂを参照して、データ３１２は、１つ以上のファイル３１０であり得て、各ファイル３１０は、指定のレプリケーションレベル３１１および／または誤り訂正符号３１３を有する。キュレータ２１０は、各ファイル３１０をストライプ３２０ａ〜３２０ｎのコレクションに分割し得て、各ストライプ３２０ａ〜３２０ｎは、残りのストライプ３２０ａ〜３２０ｎから独立してレプリケートまたは符号化される。レプリケートされたファイル３１０では、各ストライプ３２０ａ〜３２０ｎは、キュレータ２１０がストライプレプリカ３３０ｎｋとしてレプリケートして複数のストレージリソース１１４に格納する単一の論理チャンクである。当該シナリオでは、ストライプレプリカ３３０ｎｋは、チャンク３３０ｎｋとも呼ばれる。符号化されたファイル３１０では、各ストライプ３２０ａ〜３２０ｎは、キュレータ２１０が複数のストレージリソース１１４に配置する複数のデータチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍからなり、データチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍのコレクションは、単一の符号語を形成する。一般に、キュレータ２１０は、ファイル３１０内の他のストライプ３２０ａ〜３２０ｎがいかにストレージリソース１１４に配置されるかから独立して、各ストライプ３２０ａ〜３２０ｎをストレージリソース１１４に配置し得る。誤り訂正符号３１３は、冗長なデータまたはパリティデータをファイルに付加し、その結果、（使用されている
コードの性能までの）いくつかのエラーが導入されたとしても、当該ファイルは、後に受け手によって復旧されることができる。誤り訂正符号は、ストレージデバイスにおけるデータの完全性を維持するため、性能（遅延）のためにデータを再構築するため、またはより素早くマシンを使い果たすために使用される。
【００３０】
図２に戻って、いくつかの実現例では、キュレータ２１０によって格納されるファイル記述子３００１〜３００ｎは、ファイルマップ２１４などのメタデータ２１２を含み、当該ファイルマップ２１４は、ストライプ３２０ａ〜３２０ｎを、メモリホスト１１０に格納されたストライプレプリカ３２０ｎｋまたはデータチャンク３２０ｎｄｋおよびコードチャンク３２０ｎｃｍに適宜マッピングする。ファイル３１０を開くために、クライアント１２０は、要求１２２をキュレータ２１０に送り、キュレータ２１０は、ファイル記述子３００を返す。クライアント１２０は、ファイル記述子３００を使用して、ファイルチャンクオフセットを遠隔記憶場所１１５ａ〜１１５へ変換する。ファイル記述子３００は、クライアントキー３０２（例えば３２ビットキー）を含み得て、当該クライアントキー３０２は、メモリホスト１１０上のチャンク３２０ｎｋ、３２０ｎｄｋ、３２０ｎｃｍに固有であり、当該チャンク３２０ｎｋ、３２０ｎｄｋ、３２０ｎｃｍをＲＤＭＡ読取するために使用される。クライアント１２０がファイル記述子３００をロードした後、クライアント１２０は、ＲＤＭＡまたは別のデータ検索方法によってファイル３１０のデータ３１２にアクセスし得る。
【００３１】
キュレータ２１０は、セル２００の一部である全てのメモリホスト１１０のためのステータス情報を維持し得る。ステータス情報は、容量、空き領域、メモリホスト１１０に対する負荷、クライアントの視点からのメモリホスト１１０の遅延、および現在の状態を含み得る。キュレータ２１０は、セル２００内のメモリホスト１１０に直接照会することによって、および／または、クライアントの視点からの遅延統計を収集するためにクライアント１２０に照会することによって、この情報を取得し得る。いくつかの例では、キュレータ２１０は、メモリホストステータス情報を使用して、リバランシング、ドレイニング（draining）、復旧決定および割当て決定を行う。
【００３２】
キュレータ２１０は、ファイル３１０内の格納空間を多くするためのクライアント要求１２２、ならびにリバランシングおよび復旧のためのクライアント要求１２２を処理するために、チャンク３３０を割当て得る。いくつかの例では、プロセッサ２０２は、ストレージデバイス１１４の間でデータチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍを分散させるのとは異なって、ストレージデバイス１１４の間でチャンク３３０ｎｋをレプリケートする。キュレータ２１０は、メモリホスト負荷および活性の負荷マップ２１６を維持し得る。いくつかの実現例では、キュレータ２１０は、候補メモリホスト１１０のリストを生成することによってチャンク３３０を割当て、チャンク割当て要求を候補メモリホスト１１０の各々に送る。メモリホスト１１０に過負荷がかかっているか、またはメモリホスト１１０が利用可能な空間を有していない場合には、メモリホスト１１０は、当該要求を拒絶し得る。この場合、キュレータ２１０は、異なるメモリホスト１１０を選択する。各キュレータ２１０は、ファイル名前空間の指定部分を絶えずスキャンし得て、およそ時々刻々全てのメタデータ２１２を調べる。キュレータ２１０は、メタデータ２１２の完全性を確認するため、実行される必要がある作業を決定するため、および／または、統計を生成するために、ファイルスキャンを使用し得る。ファイルスキャンは、キュレータ２１０の他のオペレーションと同時に動作し得る。スキャン自体は、メタデータ２１２を修正することはできず、システムの他のコンポーネントによってなされる作業をスケジューリングし、統計を算出する。
【００３３】
図４Ａ〜図４Ｃを参照して、キュレータ２１０は、格納されたデータへのユーザのアクセスに影響を及ぼすことなくメンテナンスを行うことができるレベル４０１（例えばレベ
ル１  ４０１ａ〜レベル５  ４０１ｅ）を特定するために、分散ストレージシステム１００のメンテナンス階層４００を決定し得る。メンテナンスは、電力メンテナンス、冷却システムメンテナンス（図４Ｃ）、ネットワーキングメンテナンス、部品の更新もしくは交換、または分散ストレージシステム１００に影響を及ぼす他のメンテナンスもしくは停電を含み得る。
【００３４】
メンテナンス階層４００は、メンテナンスユニット４０２のレベル４０１（例えばレベル１  ４０１ａ〜レベル５  ４０１ｅ）を特定し、各メンテナンスユニット４０２は、アクティブ状態にある場合もあれば非アクティブ状態にある場合もある。分散ストレージシステム１００の各ストレージデバイス１１４は、１つ以上のメンテナンスユニット４０２に関連付けられる。さらに、プロセッサ２０２は、メンテナンスユニット４０２およびそれらのコンポーネント４１０，４２０，４３０，４４０，１１４とのストレージデバイス１１４の関連付けをマッピングする。図４Ａは、各コンポーネント４１０，４２０，４３０，４４０，１１４が１つの他のコンポーネント４１０，４２０，４３０，４４０，１１４に依存する厳格な階層４００ａを示している。一方、図４Ｂは、１つのコンポーネント４１０，４２０，４３０，４４０，１１４が２つ以上の入力フィードを有する厳格でない階層４００ｂを示している。いくつかの例では、プロセッサ２０２は、プロセッサ２０２の非一時的なメモリ２０４にメンテナンス階層４００を格納する。例えば、ストレージリソース１１４ａはラック４４０ａにマッピングされ、当該ラック４４０ａはバスダクト４３０ａにマッピングされ、当該バスダクト４３０ａはさらにパワーモジュール分配センタ４２０ａにマッピングされ、当該パワーモジュール分配センタ４２０ａはさらにパワープラント４１０ａにマッピングされる。コンポーネント４１０，４２０，４３０，４４０，１１４のマッピングに基づいて、プロセッサ２０２は、コンポーネント４１０，４２０，４３０，４４０，１１４がメンテナンスを受けているときにどのストレージデバイス１１４が非アクティブであるかを判断する。一旦システム１００がメンテナンスユニット４０２をストレージリソース１１４にマッピングすると、システム１００は、データ可用性を維持しながらメンテナンスを実行することができる最高レベル４０１（例えばレベル１〜５）を決定する。
【００３５】
メンテナンスユニット４０２は、メンテナンスを受けるコンポーネント４１０，４２０，４３０，４４０，１１４と、当該コンポーネント４１０，４２０，４３０，４４０，１１４に依存する任意のコンポーネントとを含む。したがって、１つのコンポーネント４１０，４２０，４３０，４４０，１１４がメンテナンスを受けているとき、当該コンポーネント４１０，４２０，４３０，４４０，１１４は非アクティブであり、当該コンポーネント４１０，４２０，４３０，４４０，１１４のメンテナンスユニット４０２内の任意のコンポーネント４１０，４２０，４３０，４４０，１１４も非アクティブである。図４に示されるように、レベル１  ４０１ａのコンポーネントは、レベル２〜５  ４０１ｂ，４０１ｃ，４０１ｄ，４０１ｅのコンポーネントに電力を供給するパワープラント４１０であってもよく、レベル２  ４０１ｂのコンポーネントは、パワーモジュール分配センタ４２０ａ〜４２０ｎを含んでいてもよく、レベル３  ４０１ｃのコンポーネントは、バスダクト４３０ａ〜４３０ｎを含んでいてもよく、レベル４  ４０１ｄのコンポーネントは、ラック４４０ａ〜４４０ｎを含んでいてもよく、レベル５  ４０１ｅのコンポーネントは、ストレージリソース１１４ａ〜１１４ｎを含んでいてもよい。他のコンポーネント分散も利用可能であり得る。パワープラント４１０がメンテナンスを受けているときには、パワープラント４１０に依存する任意のパワーモジュール分配センタ４２０、バスダクト４３０、ラック４４０およびストレージデバイス１１４を含むレベル１のメンテナンスユニット４０２は、非アクティブであるため、ユーザは、レベル１のメンテナンスユニット内に位置するデータにアクセスすることができない。パワーモジュール分配センタ４２０ａがメンテナンスを受けているときには、パワーモジュール分配センタ４２０ａおよびパワーモジュール分配センタ４２０ａに依存するレベル３〜５の任意のコンポーネントを含むレ
ベル２のメンテナンスユニット４０２ａは、非アクティブ状態にある。バスダクト４３０ａがメンテナンスを受けているときには、バスダクト４３０ａおよびバスダクト４３０ａに依存するレベル４および５の任意のコンポーネントを含むレベル３のメンテナンスユニット４０２ｂは、非アクティブ状態にある。ラック４４０ａがメンテナンスを受けているときには、ラック４４０ａおよびラック４４０ａに依存するストレージデバイス１１４を含むレベル４のメンテナンスユニット４０２は、非アクティブ状態にある。最後に、ストレージデバイス１１４ａがメンテナンスを受けているときには、レベル５のメンテナンスユニット４０２ｄは、ストレージデバイス１１４を含み、当該ストレージデバイスが非アクティブである。
【００３６】
いくつかの例では、図４Ｂに示されるように、厳格でない階層４００ｂのコンポーネント４１０，４２０，４３０，４４０，１１４は、二重フィードを有し得る。すなわち、コンポーネント４１０，４２０，４３０，４４０，１１４は、２つ以上の他のコンポーネント４１０，４２０，４３０，４４０，１１４に依存する。例えば、バスダクト４３０ｎは、２つのパワーモジュール４２０からのフィードを有し得て、および／または、ラック４４０は、２つのバスダクト４３０からの二重フィードを有し得る。示されているように、第１のメンテナンスユニット４０２ｂは、２つのラック４４０ａおよび４４０ｎを含み得て、第２のラック４４０ｎは、２つのバスダクト４３０ａ，４３０ｎからの２つのフィードを含む。したがって、第２のラック４４０ｎは、２つのメンテナンスユニット４０２ｂａおよび４０２ｂｂの一部である。したがって、メンテナンス階層４００の下位レベル４０１の喪失を引き起こすことなく、メンテナンス階層４００の上位レベル４０１が維持される。これにより、システムに冗長性がもたらされ、データアクセス性が可能になる。特に、パワーモジュール分配センタ４２０に依存するいずれのバスダクト４３０も喪失することなくパワーモジュール分配センタ４２０を整備することができる。いくつかの例では、ラック４４０は、バスダクト４３０に依存する二重動力ラック４４０に対する電力を喪失することなくバスダクト４３０のメンテナンスを可能にする二重動力ラックを含む。いくつかの例では、機能停止を引き起こすことなく整備され得るメンテナンスユニット４０２は、チャンク３３０を分散させるときには無視され、メンテナンスを可能にする。しかし、予期せぬ機能停止は依然としてチャンク３３０を喪失させる可能性があるので、当該無視されるメンテナンスユニット４０２は、チャンク３３０を分散させるときに含まれていてもよい。
【００３７】
いくつかの例では、メンテナンス階層４００は、冷却階層４００ｃ（または電力階層４００ａ，４００ｂの組み合わせであってもよい）および冷却階層４００ｃである。冷却階層４００ｃは、冷却装置４４２を、冷却装置４４２が冷却しているラック４４０にマッピングする。示されているように、冷却装置４４２は、１つ以上のラック４４０を冷却し得る。プロセッサ２０２は、冷却メンテナンスユニット４０２とのストレージデバイス１１４の関連付けを格納する。いくつかの実現例では、プロセッサ２０２は、階層４００または階層４００ａ，４００ｂ，４００ｃの組み合わせを決定するために、ストレージシステム１００内で行われ得るメンテナンスの全ての可能な組み合わせを考慮に入れる。
【００３８】
したがって、ストレージシステム１００内のコンポーネント４１０，４２０，４３０，４４０，１１４が整備されているときには、当該コンポーネント４１０，４２０，４３０，４４０，１１４および当該コンポーネント４１０，４２０，４３０，４４０，１１４にマッピングされるまたは依存する任意のコンポーネント４１０，４２０，４３０，４４０，１１４は、非アクティブ状態にある。非アクティブ状態のコンポーネント４１０，４２０，４３０，４４０，１１４は、ユーザがアクセスすることができない一方、アクティブ状態のコンポーネント４１０，４２０，４３０，４４０，１１４は、ユーザがアクセスすることができ、当該コンポーネント４１０，４２０，４３０，４４０，１１４または当該コンポーネント４１０，４２０，４３０，４４０，１１４にマッピングされるストレージ
デバイス１１４に格納されたデータにユーザがアクセスすることを可能にする。上記のように、非アクティブ状態の間は、ユーザは、メンテナンスを受けているメンテナンスユニット４０２に関連付けられるストレージデバイス１１４にアクセスすることができないため、ユーザは、ファイル（すなわち、ストライプレプリカ３３０ｎｋおよびデータチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍを含むチャンク３３０）にアクセスすることができない。
【００３９】
いくつかの実現例では、プロセッサ２０２は、例えばコンポーネント４１０，４２０，４３０，４４０，１１４のマッピングに基づいて、いずれか１つのメンテナンスユニット４０２のストレージデバイス１１４に分散されるチャンク３３０の数を制限する。したがって、レベル１のメンテナンスユニット４０２が非アクティブである場合、いくつかのチャンク３３０がアクセス不可能である可能性があるにもかかわらず、プロセッサ２０２は、ファイル３１０（またはストライプ３２０）へのアクセス性を維持する。いくつかの例では、各ファイル３１０（またはストライプ３２０）について、プロセッサ２０２は、単一のメンテナンスユニット４０２内の任意のストレージデバイス１１４内に配置され得るチャンク３３０の最大数を決定し、その結果、ファイル３１０のためのチャンク３３０を格納するストレージデバイス１１４に関連付けられるメンテナンスユニット４０２がメンテナンスを受けている場合に、プロセッサ２０２は、依然としてファイル３１０を検索することができる。チャンク３３０の最大数は、いくつかのチャンク３３０が利用不可能である可能性があるにもかかわらずプロセッサ２０２がファイル３１０を再構築することができることを確実にする。いくつかの例では、チャンク３３０の最大数は、依然としてチャンク３３０からファイル３１０を再構築することができながらいかなるシステム故障も吸収するように下方閾値に設定される。プロセッサ２０２がチャンク３３０をストレージデバイス１１４に配置すると、プロセッサ２０２は、単一のメンテナンスユニット４０２がメンテナンスを受けるときにストライプ３２０内ではせいぜい最大数のチャンク３３０が非アクティブであることを確実にする。
【００４０】
図５〜図７Ｂを参照して、いくつかの実現例では、プロセッサ２０２は、ストレージデバイス１１４の間でのチャンク３３０の分散を決定する。いくつかの例では、プロセッサ２０２は、ファイル３１０のチャンク３３０を格納するためにストレージデバイス１４０の利用可能なプールからストレージデバイス１１４の第１の無作為選択群１５０を作成する。プロセッサ２０２は、ストライプ３２０内のチャンク３３０の数に等しい数のストレージデバイス１１４（例えば選択されたストレージデバイス１１４Ｓ）を選択する。次に、プロセッサ２０２は、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの選択群１５０がファイル３１０のアクセス性を維持することができる（すなわちファイル３１０のチャンク３３０が利用可能である）か否かを判断する。無作為選択群１５０は、メンテナンスコンポーネント４１０，４２０，４３０，４４０，１１４のうちの１つでメンテナンスが行われる場合にストライプ３２０の再構築を可能にするという目的を有する。
【００４１】
図５Ａおよび図５Ｂを参照して、いくつかの例では、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの第１の無作為選択群１５０ａがファイル３１０のアクセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２は、ファイル３１０のチャンク３３０の数に一致する選択されたストレージデバイス１１４Ｓの第２の無作為選択群１５０ｂを決定する。次いで、プロセッサ２０２は、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの第２の無作為選択群１５０ｂがファイル３１０のアクセス性を維持することができるか否かを判断する。１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに第２の無作為選択群１５０ｂがファイル３１０のア
クセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２がファイル３１０のアクセス性を維持することができる選択されたストレージデバイス１１４Ｓの無作為選択群１５０ｎを特定するまで、プロセッサ２０２は、選択されたストレージデバイス１１４Ｓの無作為選択群１５０ｎを作成し続ける。
【００４２】
図６Ａおよび図６Ｂを参照して、いくつかの実現例では、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの第１の無作為選択群１５０ａがファイル３１０のアクセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２は、１つ以上の無作為に選択されたストレージデバイス１１４Ｓを追加し、対応する数の異なるストレージデバイス１１４Ｓを除去することによって、選択されたストレージデバイス１１４Ｓの第１の無作為選択群１５０ａを修正する。次いで、プロセッサ２０２は、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、更新された第１の無作為選択群１５０ａがファイル３１０のアクセス性を維持することができるか否かを判断する。１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、更新された第１の無作為選択群１５０ａがストライプ３２０のアクセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２は、１つ以上の無作為に選択されたストレージデバイス１１４Ｓを追加および除去することによって、選択されたストレージデバイス１１４Ｓの選択群１５０ａを更新する。分散ストレージシステム１００のメンテナンス中に選択されたストレージデバイス１１４Ｓがストライプ３２０のアクセス性を維持することができるとプロセッサ２０２が判断するまで、プロセッサ２０２は、ストレージデバイス１１４の無作為選択群１５０ａを更新し続ける。一旦プロセッサ２０２が当該判断を行うと、プロセッサ２０２は、次のストライプ３２０（またはファイル３１０）に移動して、次のストライプ３２０の分散を決定する。
【００４３】
いくつかの実現例では、プロセッサ２０２は、確率抽出法、単純抽出法、層別抽出法、集落抽出法、またはそれらの組み合わせを用いて、選択されたストレージデバイス１１４Ｓの無作為選択群１５０を決定する。確率抽出法では、母集団の中の全てのユニットは、サンプルにおいて選択される確率がゼロよりも大きく、この確率は、正確に求められることができる。確率抽出法は、抽出されたユニットをそれらの確率選択に従って重み付けすることによって、母集団全体のバイアスのない推定値を提供する。所与の数のサンプルの単純無作為抽出法（simple random sampling：ＳＲＳ）では、抽出枠の全てのサブセットは、等しい確率を付与される。また、要素の任意の所与の対は、その他のこのような対と同じ選択の確率を有する（三つ組、四つ組などについても同様）。ＳＲＳは、バイアスを最小化し、結果の分析を単純化する。サンプル内の結果間の分散は、母集団における分散の良い指標であり、結果の精度の推定を容易にする。層別抽出法では、母集団は、いくつかの別個のカテゴリを含み、これらのカテゴリによって枠は別々の「層」に編成される。各層は、独立した亜集団として抽出され、当該亜集団から個々の要素が無作為に選択される。層別抽出法は、他の抽出方法に対していくつかの利点を有する。層別抽出法は、重要な亜集団に注目し、無関係のものを無視し、異なる亜集団に対して異なる抽出技術を使用することを可能にし、推定の精度および効率を向上させ、サイズが大きく異なる層から等しい数を抽出することによって層間の相違の試験の検出力のより良いバランシングを可能にする。集落抽出法は、地形または期間によってグループ分けされたクラスタにおけるレスポンデントの選択を可能にする。集落抽出法は、目標母集団における全ての要素を列挙する抽出枠を必要とせず、それどころか、クラスタは、クラスタレベルの枠から選択され得て、要素レベルの枠は、選択されたクラスタについてのみ作成される。
【００４４】
図７Ａおよび図７Ｂを参照して、いくつかの実現例では、プロセッサ２０２は、ストライプ３２０内のチャンク３３０の数を判断する。次いで、プロセッサ２０２は、分散ストレージシステム１００のストレージデバイス１１４の順序付き循環リスト１６０からファ
イルのチャンク３３０の数に等しい連続的な数のストレージデバイス１１４ａ〜１１４ｎを有する選択されたリスト１６２を選択し、順序付き循環リスト１６０は、第１のストレージデバイス１１４ａから開始する。リスト１６０は、プロセッサ２０２の非一時的なメモリ２０４に格納され得る。次いで、プロセッサ２０２は、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたリスト１６２からの選択されたストレージデバイス１１４ａ〜１１４ｎが集合的にファイル３１０（すなわちストライプ３２０）のアクセス性を維持することができないか否かを判断する。１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４ａ〜１１４ｎが集合的にファイル３１０（またはストライプ３２０）のアクセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２は、ストライプ３２０またはファイル３１０のチャンク３３０の数に等しい連続的な数のストレージデバイス１１４ａ〜１１４ｎを有する別の選択されたリスト１６２を、順序付き循環リスト１６０から選択する。いくつかの例では、選択されたリスト１６２のストレージデバイス１１４ａ〜１１４ｎが集合的にファイル３１０（またはストライプ３２０）のアクセス性を維持することができないとプロセッサ２０２が判断すると、プロセッサ２０２は、順序付き循環リスト１６０における第１のストレージデバイス１１４ｎの後の第２のストレージデバイス１１４（ｎ＋１）に移動する。他の例では、プロセッサ２０２は、順序付き循環リスト１６０において予め定められた数の位置を下方に移動させる。いくつかの実現例では、プロセッサ２０２は、ストレージシステム１００のストレージデバイス１１４の順序付き循環リスト１６０を決定し、順序付き循環リスト上の隣接するストレージデバイス１１４または閾値数の連続的なストレージデバイス１１４は、異なるメンテナンスユニット４０２に関連付けられる。さらにまたは代替的に、プロセッサ２０２は、ストレージシステム１００のストレージデバイス１１４の順序付き循環リスト１６０を決定し、順序付き循環リスト上の隣接するストレージデバイス１１４または閾値数の連続的なストレージデバイス１１４は、各々が異なる地理的場所にある。いくつかの例では、順序付き循環リスト１６０上のストレージデバイス１１４は、異なるメンテナンスユニット４０２が順序付きリスト１６０に沿ってシーケンシャルにデータのばらつきを生じさせるように配置される。例えば、図４Ａに示されるように、リストは、同一のバスダクト４３０ａに依存するストレージデバイス１１４をシーケンシャルに含むことはできない。その代わりに、リスト１６０上の２つのシーケンシャルなストレージデバイス１１４は、異なるメンテナンスユニット４０２からのものであり、データアクセス性が確実に維持される。
【００４５】
図８を参照して、いくつかの実現例では、分散ストレージシステムにおいてデータを分散させる方法８００は、非一時的なメモリ２０４内にファイル３１０を受取るステップ８０２と、非一時的なメモリ２０４と通信するコンピュータプロセッサ２０２を用いて、受取られたファイル３１０をチャンク３３０に分割するステップ８０４とを含む。また、方法８００は、分散ストレージシステム１００のメンテナンス階層４００に基づいて、チャンク３３０を分散ストレージシステム１００のストレージデバイス１１４に分散させるステップを含む。メンテナンス階層４００は、各々がアクティブ状態と非アクティブ状態とを有するメンテナンスユニット４０２を含む。さらに、各ストレージデバイス１１４は、メンテナンスユニット４０２に関連付けられる。メンテナンスユニット４０２が非アクティブ状態にあるときにファイル３１０（またはストライプ３２０）のアクセス性を維持するために、チャンク３３０は、複数のメンテナンスユニット４０２にわたって分散される。いくつかの例では、方法８００は、いずれか１つのメンテナンスユニット４０２のストレージデバイス１１４に分散されるチャンク３３０の数を制限するステップを含む。
【００４６】
いくつかの実現例では、方法８００は、ストレージデバイス１１４の間でのチャンク３３０の分散を決定するステップをさらに含み、当該決定するステップは、ファイル３１０のチャンク３３０の数に一致する選択されたストレージデバイス１１４Ｓの第１の無作為
選択群１５０ａを決定することによって、および、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの選択群１５０ａがファイル３１０（またはストライプ３２０）のアクセス性を維持することができるか否かを判断することによって、行われる。いくつかの例では、１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４Ｓの第１の無作為選択群１５０ａがファイル３１０（またはストライプ３２０）のアクセス性を維持することができない場合、方法８００は、ファイル３１０（またはストライプ３２０）のチャンク３３０の数に一致する選択されたストレージデバイス１１４Ｓの第２の無作為選択群１５０ｂを決定するステップ、または、１つ以上の無作為に選択されたストレージデバイス１１４を追加および除去することによってストレージデバイス１１４Ｓの第１の無作為選択群１５０ａを修正するステップをさらに含む。方法８００は、単純抽出法、確率抽出法、層別抽出法、または集落抽出法（上記で説明）を用いてストレージデバイス１１４の無作為選択群１５０を決定するステップをさらに含み得る。いくつかの例では、方法８００は、１つ以上のまたは閾値数のメンテナンスユニット４０２が非アクティブ状態にあるときにストレージデバイス１１４の選択された無作為選択群１５０がファイル３１０（またはストライプ３２０）のアクセス性を維持することができるまで、選択されたストレージデバイス１１４Ｓの第３、第４、第５…などの無作為選択群を決定する。
【００４７】
いくつかの実現例では、方法８００は、分散ストレージシステム１００のストレージデバイス１１４の順序付き循環リスト１６０からファイル３１０のチャンク３３０の数に等しい連続的な数のストレージデバイス１１４ａ〜１１４ｎを有するリスト１６２を選択することによって、ストレージデバイス１１４の間でのチャンク３３０の分散を決定するステップをさらに含む。１つ以上の（または閾値数の）メンテナンスユニット４０２が非アクティブ状態にあるときに、選択されたストレージデバイス１１４が集合的にファイル３１０のアクセス性を維持することができない場合、方法８００は、ファイル３１０（またはストライプ３２０）のチャンク３３０の数に等しい連続的な数のストレージデバイス１１４ａ〜１１４ｎを有する別のリスト１６２を、順序付き循環リスト１６０から選択するステップをさらに含む。さらにまたは代替的に、方法８００は、分散ストレージシステム１００のストレージデバイス１１４の順序付き循環リスト１６０を決定するステップをさらに含み、順序付き循環リスト１６０上の隣接するストレージデバイス１１４は、異なるメンテナンスユニット４０２に関連付けられる。いくつかの例では、順序付き循環リスト１６０上の閾値数の連続的なストレージデバイス１１４は、各々が異なるメンテナンスユニット４０２に関連付けられるか、または各々が異なる地理的場所にある。
【００４８】
いくつかの実現例では、方法８００は、（例えばコンピュータプロセッサ２０２を用いて）メンテナンスユニット４０２のメンテナンス階層４００を決定するステップをさらに含み、メンテナンス階層４００は、メンテナンスレベル４０１（例えばレベル１  ４０１ａ〜レベル５  ４０１ｅ）を有し、各メンテナンスレベル４０１は、１つ以上のメンテナンスユニット４０２を含む。また、方法８００は、各メンテナンスユニット４０２を少なくとも１つのストレージデバイス１１４にマッピングするステップを含む。各メンテナンスユニット４０２は、単一の配電ユニットまたは単一の電力バスダクト４３０によって電力を供給されるストレージデバイス１１４を含む。
【００４９】
方法８００は、受取られたファイル３１０をストライプ３２０ａ〜３２０ｎに分割するステップをさらに含み得る。各ファイル３１０は、レプリケーションコード３１１または誤り訂正符号３１３を含む。ファイル３１０がレプリケーションコード３１１を含む場合、方法８００は、少なくとも１つのストライプ３２０ａ〜３２０ｎをレプリケーションチャンク３３０としてレプリケートするステップを含む。ファイル３１０が誤り訂正符号３１３を含む場合、方法８００は、少なくとも１つのストライプ３２０ａ〜３２０ｎをデー
タチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍに分割するステップを含む。また、方法８００は、ストレージデバイス１１４の間でデータチャンク３３０ｎｄｋおよびコードチャンク３３０ｎｃｍを分散させるのとは異なって、ストレージデバイス１１４の間でレプリケーションチャンク３３０を分散させるステップを含み得る。
【００５０】
ここに記載されているシステムおよび技術のさまざまな実現例は、デジタル電子回路、集積回路、特別に設計されたＡＳＩＣ（特定用途向け集積回路）、コンピュータハードウェア、ファームウェア、ソフトウェア、および／または、それらの組み合わせで実現可能である。これらのさまざまな実現例は、プログラム可能なシステム上で実行可能および／または解釈可能な１つ以上のコンピュータプログラムでの実現例を含み得て、当該プログラム可能なシステムは、ストレージシステム、少なくとも１つの入力装置および少なくとも１つの出力装置からデータおよび命令を受信し、ストレージシステム、少なくとも１つの入力装置および少なくとも１つの出力装置にデータおよび命令を送信するように結合された、特殊用途または汎用であり得る少なくとも１つのプログラム可能なプロセッサを含む。
【００５１】
これらのコンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーションまたはコードとしても知られている）は、プログラム可能なプロセッサのためのマシン命令を含み、高級手続き型プログラミング言語および／もしくはオブジェクト指向プログラミング言語で実現されてもよく、ならびに／または、アセンブリ／マシン言語で実現されてもよい。本明細書で用いられる「マシン読取可能な媒体」および「コンピュータ読取可能な媒体」という表現は、マシン命令および／またはデータをプログラム可能なプロセッサに提供するために使用される任意のコンピュータプログラム製品、装置および／またはデバイス（例えば磁気ディスク、光ディスク、メモリ、プログラマブルロジックデバイス（Programmable Logic Device：ＰＬＤ））を指し、マシン命令をマシン読取可
能な信号として受信するマシン読取可能な媒体を含む。「マシン読取可能な信号」という表現は、マシン命令および／またはデータをプログラム可能なプロセッサに提供するために使用される任意の信号を指す。
【００５２】
本明細書に記載されている主題および機能的動作の実現例は、デジタル電子回路で実現されてもよく、または本明細書に開示されている構造およびそれらの構造的等価物を含むコンピュータソフトウェア、ファームウェアまたはハードウェアで実現されてもよく、またはそれらのうちの１つ以上の組み合わせで実現されてもよい。さらに、本明細書に記載されている主題は、１つ以上のコンピュータプログラム製品として、すなわちデータ処理装置によって実行するため、またはデータ処理装置の動作を制御するためにコンピュータ読取可能な媒体上で符号化されるコンピュータプログラム命令の１つ以上のモジュールとして実現されてもよい。コンピュータ読取可能な媒体は、マシン読取可能な記憶装置、マシン読取可能な記憶基板、メモリ装置、マシン読取可能な伝播信号に影響を及ぼす組成物、またはそれらのうちの１つ以上の組み合わせであってもよい。「データ処理装置」、「コンピューティング装置」および「コンピューティングプロセッサ」という表現は、データを処理するための全ての装置、デバイスおよびマシンを包含し、一例として、プログラム可能なプロセッサ、コンピュータ、または複数のプロセッサもしくはコンピュータを含む。当該装置は、ハードウェアに加えて、当該コンピュータプログラムのための実行環境を作り出すコード、例えばプロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの１つ以上の組み合わせを構成するコードを含み得る。伝播信号は、人工的に生成される信号、例えば好適な受信機装置に送信される情報を符号化するために生成されるマシン生成電気信号、光信号または電磁信号である。
【００５３】
コンピュータプログラム（アプリケーション、プログラム、ソフトウェア、ソフトウェ
アアプリケーション、スクリプトまたはコードとしても知られている）は、コンパイラ型言語またはインタープリタ型言語を含む任意の形態のプログラミング言語で書込まれてもよく、スタンドアロンのプログラムとして、またはコンピューティング環境での使用に適したモジュール、コンポーネント、サブルーチンまたは他のユニットとしてなどの任意の形態で配備されてもよい。コンピュータプログラムは、必ずしもファイルシステム内のファイルに対応していない。プログラムは、他のプログラムまたはデータ（例えばマークアップ言語文書に格納された１つ以上のスクリプト）を保持するファイルの一部に格納されてもよく、当該プログラムに専用の単一のファイルに格納されてもよく、または複数の調整されたファイル（例えば１つ以上のモジュール、サブプログラム、またはコードの一部を格納するファイル）に格納されてもよい。コンピュータプログラムは、１つのコンピュータ、または、一箇所に位置するかもしくは複数の箇所にわたって分散されて通信ネットワークによって相互接続されている複数のコンピュータ上で実行されるように配備されてもよい。
【００５４】
本明細書に記載されているプロセスおよび論理フローは、入力データ上で動作して出力を生成することによって機能を実行するように１つ以上のコンピュータプログラムを実行する１つ以上のプログラム可能なプロセッサによって実行され得る。また、プロセスおよび論理フローは、特殊用途論理回路、例えばＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）またはＡＳＩＣ（特定用途向け集積回路）によって実行されてもよく、装置も、特殊用途論理回路、例えばＦＰＧＡまたはＡＳＩＣとして実現されてもよい。
【００５５】
コンピュータプログラムの実行に適したプロセッサは、一例として、汎用マイクロプロセッサおよび特殊用途マイクロプロセッサを両方とも含み、任意の種類のデジタルコンピュータの任意の１つ以上のプロセッサを含む。一般に、プロセッサは、リードオンリメモリまたはランダムアクセスメモリまたはそれら両方から命令およびデータを受信するであろう。コンピュータの必須の要素は、命令を実行するためのプロセッサと、命令およびデータを格納するための１つ以上のメモリ装置とである。一般に、コンピュータは、データを格納するための１つ以上の大容量記憶装置、例えば磁気ディスク、光磁気ディスクまたは光ディスクも含み、または、当該１つ以上の大容量記憶装置からデータを受信するもしくは当該１つ以上の大容量記憶装置にデータを転送するように、もしくは受信も転送もするように動作可能に結合されるであろう。しかし、コンピュータは、このような装置を有する必要はない。さらに、コンピュータは、別の装置、例えば数例を挙げると、携帯電話、パーソナルデジタルアシスタント（personal digital assistant：ＰＤＡ）、携帯型オーディオプレーヤ、グローバル・ポジショニング・システム（Global Positioning System：ＧＰＳ）受信機に組み込まれてもよい。コンピュータプログラム命令およびデータを
格納するのに適したコンピュータ読取可能な媒体は、全ての形態の不揮発性メモリ、媒体およびメモリ装置を含み、一例として例えばＥＰＲＯＭ、ＥＥＰＲＯＭおよびフラッシュメモリ装置といった半導体メモリ装置、例えば内蔵ハードディスクまたは取外し可能なディスクといった磁気ディスク、光磁気ディスク、ならびにＣＤ  ＲＯＭおよびＤＶＤ−ＲＯＭディスクを含む。プロセッサおよびメモリは、特殊用途論理回路によって補完されてもよく、または特殊用途論理回路に組み入れられてもよい。
【００５６】
ユーザとの対話を提供するために、本開示の１つ以上の局面は、情報をユーザに表示するための表示装置、例えばＣＲＴ（陰極線管）、ＬＣＤ（液晶表示）モニタまたはタッチスクリーンと、任意にユーザが入力をコンピュータに提供することができるキーボードおよびポインティング装置、例えばマウスまたはトラックボールとを有するコンピュータ上で実現され得る。ユーザとの対話を提供するために他の種類の装置も使用されてもよく、例えば、ユーザに提供されるフィードバックは、任意の形態の感覚フィードバック、例えば視覚フィードバック、聴覚フィードバックまたは触覚フィードバックであってもよく、ユーザからの入力は、音響入力、音声入力または触知入力を含む任意の形態で受信されて
もよい。また、コンピュータは、ユーザによって使用される装置にドキュメントを送り、ユーザによって使用される装置からドキュメントを受信することによって、例えばウェブブラウザから受信された要求に応答してユーザのクライアント装置上でウェブブラウザにウェブページを送ることによって、ユーザと対話し得る。
【００５７】
本開示の１つ以上の局面は、例えばデータサーバとしてのバックエンドコンポーネントを含むコンピューティングシステムにおいて実現されてもよく、またはミドルウェアコンポーネント、例えばアプリケーションサーバを含むコンピューティングシステムにおいて実現されてもよく、またはフロントエンドコンポーネント、例えばユーザが本明細書に記載されている主題の実現例と対話できるようにするグラフィカルユーザインターフェースまたはウェブブラウザを有するクライアントコンピュータを含むコンピューティングシステムにおいて実現されてもよく、または１つ以上のこのようなバックエンド、ミドルウェアまたはフロントエンドコンポーネントの任意の組み合わせを含むコンピューティングシステムにおいて実現されてもよい。システムの構成要素は、デジタルデータ通信の任意の形態または媒体、例えば通信ネットワークによって相互接続され得る。通信ネットワークの例としては、ローカルエリアネットワーク（local area network：「ＬＡＮ」）およびワイドエリアネットワーク（wide area network：「ＷＡＮ」）、インターネットワーク
（例えばインターネット）、ならびにピアツーピアネットワーク（例えばアドホックピアツーピアネットワーク）が挙げられる。
【００５８】
コンピューティングシステムは、クライアントと、サーバとを含み得る。クライアントおよびサーバは、一般に互いに離れており、典型的には通信ネットワークを介して相互作用する。クライアントおよびサーバの関係は、それぞれのコンピュータで実行されて互いに対してクライアント−サーバ関係を有するコンピュータプログラムによって生じる。いくつかの実現例では、サーバは、（例えば、クライアント装置と対話するユーザにデータを表示して、クライアント装置と対話するユーザからユーザ入力を受信する目的で）データ（例えばＨＴＭＬページ）をクライアント装置に送信する。クライアント装置において生成されたデータ（例えばユーザ対話の結果）は、サーバにおけるクライアント装置から受信され得る。
【００５９】
本明細書は多くの具体例を含んでいるが、これらは、本開示またはクレームされ得るものの範囲を限定するものとして解釈されるべきではなく、むしろ本開示の特定の実現例に特有の特徴の説明であると解釈されるべきである。また、別々の実現例の文脈において本明細書に記載されている特定の特徴は、単一の実現例において組み合わせて実現されてもよい。また、逆に、単一の実現例の文脈において記載されているさまざまな特徴は、複数の実現例において別々に、または任意の好適なサブコンビネーションで実現されてもよい。さらに、特徴は特定の組み合わせで作用するものとして上記され、さらにはそのようなものとして最初はクレームされ得るが、クレームされている組み合わせからの１つ以上の特徴は、場合によっては、当該組み合わせから削除されてもよく、クレームされている組み合わせは、サブコンビネーションまたはサブコンビネーションの変形例を対象にしてもよい。
【００６０】
同様に、動作は特定の順序で図面に示されているが、これは、このような動作が、望ましい結果を達成するために、示されている特定の順序もしくはシーケンシャルな順序で実行されなければならないと理解されるべきではなく、または、望ましい結果を達成するために、全ての示されている動作が実行されなければならないと理解されるべきではない。特定の状況では、マルチタスクおよび並列処理が有利である場合がある。さらに、上記の実施例におけるさまざまなシステム構成要素の分離は、全ての実施例においてこのような分離が必要であるものとして理解されるべきではなく、記載されているプログラムコンポーネントおよびシステムは、一般に単一のソフトウェア製品に一体化されてもよく、また
は複数のソフトウェア製品にパッケージングされてもよいということが理解されるべきである。
【００６１】
多数の実現例が記載されてきた。しかし、本開示の精神および範囲から逸脱することなくさまざまな変形がなされ得ることが理解されるであろう。したがって、他の実現例は、以下の特許請求の範囲の範囲内である。例えば、特許請求の範囲に記載されている動作は、異なる順序で実行されて、依然として望ましい結果を達成することができる。
【図１Ａ】
2018110008.tif 000003
【図１Ｂ】
2018110008.tif 000004
【図１Ｃ】
2018110008.tif 000005
【図２】
2018110008.tif 000006
【図３Ａ】
2018110008.tif 000007
【図３Ｂ】
2018110008.tif 000008
【図４Ａ】
2018110008.tif 000009
【図４Ｂ】
2018110008.tif 000010
【図４Ｃ】
2018110008.tif 000011
【図５Ａ】
2018110008.tif 000012
【図５Ｂ】
2018110008.tif 000013
【図６Ａ】
2018110008.tif 000014
【図６Ｂ】
2018110008.tif 000015
【図７Ａ】
2018110008.tif 000016
【図７Ｂ】
2018110008.tif 000017
【図８】
2018110008.tif 000018
【手続補正書】
【提出日】平成30年3月8日(2018.3.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
分散ストレージシステムにおいてデータを分散させる方法であって、
データ処理ハードウェアでファイルを受取るステップと、
前記データ処理ハードウェアによって、前記受取られたファイルをチャンクに分割するステップと、
前記データ処理ハードウェアによって、前記分散ストレージシステムのメンテナンス階層に基づいて前記分散ストレージシステムのストレージデバイス間での前記チャンクの分散を決定するステップとを備え、前記メンテナンス階層は、メンテナンスレベルを備え、各メンテナンスレベルは、１つ以上のメンテナンスユニットを備え、各メンテナンスユニットは、アクティブ動作状態と非アクティブ動作状態とを有し、各ストレージデバイスは、メンテナンスユニットに関連付けられ、前記チャンクの前記分散を決定するステップは、前記ファイルのチャンクの数に一致し、かつ、１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記ファイルのアクセス性を維持することができる前記ストレージデバイスの無作為選択群を特定するステップを備え、前記方法はさらに、
前記データ処理ハードウェアによって、前記決定された分散に従って前記チャンクを前記分散ストレージシステムのストレージデバイスに分散させるステップを備える、方法。
【請求項２】
いずれか１つのメンテナンスユニットのストレージデバイスに分散されるチャンクの数を制限するステップをさらに備える、請求項１に記載の方法。
【請求項３】
前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記ストレージデバイスの前記無作為選択群が前記ファイルの前記アクセス性を維持することができない場合、前記ファイルのチャンクの数に一致するストレージデバイスの別の無作為選択群を決定する、請求項１に記載の方法。
【請求項４】
前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記ストレージデバイスの無作為選択群が前記ファイルのアクセス性を維持することができない場合、１つ以上の無作為に選択されたストレージデバイスを追加および除去することによって前記ストレージデバイスの無作為選択群を修正する、請求項１に記載の方法。
【請求項５】
単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて前記ストレージデバイスの無作為選択群を決定するステップをさらに備える、請求項１に記載の方法。
【請求項６】
前記分散ストレージシステムの前記ストレージデバイスの順序付き循環リストから前記ファイルのチャンクの数に等しい連続的な数のストレージデバイスを選択することによって、前記ストレージデバイス間での前記チャンクの前記分散を決定するステップをさらに備える、請求項１に記載の方法。
【請求項７】
前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記選択されたストレージデバイスが全体として前記ファイルの前記アクセス性を維持することができない場合、前記順序付き循環リストから前記ファイルのチャンクの数に等しい別の連続的な数のストレージデバイスを選択するステップをさらに備える、請求項６に記載の方法。
【請求項８】
前記順序付き循環リスト上の隣接するストレージデバイスは、異なるメンテナンスユニットに関連付けられる、請求項６に記載の方法。
【請求項９】
前記順序付き循環リスト上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニットに関連付けられるか、または異なる地理的場所にある、請求項８に記載の方法。
【請求項１０】
前記受取られたファイルをストライプに分割するステップをさらに備え、各ファイルは、レプリケーションコードおよび／またはエラー修正コードを含み、
前記ファイルがレプリケーションコードを含む場合、少なくとも１つのストライプをレプリケーションチャンクとしてレプリケートするステップと、
前記ファイルがエラー修正コードを含む場合、少なくとも１つのストライプをデータチャンクおよびコードチャンクに分割するステップと、
前記ストレージデバイス間で前記データチャンクおよび前記コードチャンクを分散させるのとは異なって、前記ストレージデバイス間でレプリケーションチャンクを分散させるステップとをさらに備える、請求項１に記載の方法。
【請求項１１】
分散ストレージシステムにおいてデータを分散させるためのシステムであって、
データ処理ハードウェアと、
前記データ処理ハードウェアと通信するメモリハードウェアとを備え、前記メモリハードウェアは、命令を格納し、前記命令は、前記データ処理ハードウェアで実行されたときに前記データ処理ハードウェアにオペレーションを実行させ、前記オペレーションは、
ファイルを受取ることと、
前記受取られたファイルをチャンクに分割することと、
前記分散ストレージシステムのメンテナンス階層に基づいて前記分散ストレージシステムのストレージデバイス間での前記チャンクの分散を決定することとを備え、前記メンテナンス階層は、メンテナンスレベルを備え、各メンテナンスレベルは、１つ以上のメンテナンスユニットを備え、各メンテナンスユニットは、アクティブ動作状態と非アクティブ動作状態とを有し、各ストレージデバイスは、メンテナンスユニットに関連付けられ、前記チャンクの前記分散を決定することは、前記ファイルのチャンクの数に一致し、かつ、１つ以上のメンテナンスユニットが非アクティブ動作状態にあるときに前記ファイルのアクセス性を維持することができる前記ストレージデバイスの無作為選択群を特定することを備え、前記オペレーションはさらに、
前記決定された分散に従って前記チャンクを前記分散ストレージシステムのストレージデバイスに分散させることを備える、システム。
【請求項１２】
前記オペレーションは、いずれか１つのメンテナンスユニットのストレージデバイスに分散されるチャンクの数を制限することをさらに備える、請求項１１に記載のシステム。
【請求項１３】
前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記ストレージデバイスの前記無作為選択群が前記ファイルの前記アクセス性を維持することができない場合、前記ファイルのチャンクの数に一致するストレージデバイスの別の無作為選択群を決定する、請求項１１に記載のシステム。
【請求項１４】
前記オペレーションは、前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記ストレージデバイスの無作為選択群が前記ファイルのアクセス性を維持することができない場合、１つ以上の無作為に選択されたストレージデバイスを追加および除去することによって前記ストレージデバイスの無作為選択群を修正することをさらに備える、請求項１１に記載のシステム。
【請求項１５】
前記オペレーションは、単純抽出法、確率抽出法、層別抽出法、または集落抽出法を用いて前記ストレージデバイスの無作為選択群を決定することをさらに備える、請求項１１に記載のシステム。
【請求項１６】
前記オペレーションは、前記分散ストレージシステムの前記ストレージデバイスの順序付き循環リストから前記ファイルのチャンクの数に等しい連続的な数のストレージデバイスを選択することによって、前記ストレージデバイス間での前記チャンクの前記分散を決定することをさらに備える、請求項１１に記載のシステム。
【請求項１７】
前記オペレーションは、前記１つ以上のメンテナンスユニットが前記非アクティブ動作状態にあるときに前記選択されたストレージデバイスが全体として前記ファイルの前記アクセス性を維持することができない場合、前記順序付き循環リストから前記ファイルのチャンクの数に等しい別の連続的な数のストレージデバイスを選択することをさらに備える、請求項１６に記載のシステム。
【請求項１８】
前記順序付き循環リスト上の隣接するストレージデバイスは、異なるメンテナンスユニットに関連付けられる、請求項１６に記載のシステム。
【請求項１９】
前記順序付き循環リスト上の閾値数の連続的なストレージデバイスは、各々が異なるメンテナンスユニットに関連付けられるか、または異なる地理的場所にある、請求項１８に記載のシステム。
【請求項２０】
前記オペレーションは、
前記受取られたファイルをストライプに分割することをさらに備え、各ファイルは、レプリケーションコードおよび／またはエラー修正コードを含み、前記オペレーションはさらに、
前記ファイルがレプリケーションコードを含む場合、少なくとも１つのストライプをレプリケーションチャンクとしてレプリケートすることと、
前記ファイルがエラー修正コードを含む場合、少なくとも１つのストライプをデータチャンクおよびコードチャンクに分割することと、
前記ストレージデバイス間で前記データチャンクおよび前記コードチャンクを分散させるのとは異なって、前記ストレージデバイス間でレプリケーションチャンクを分散させることとを備える、請求項１１に記載のシステム。
【外国語明細書】
2018110008000001.pdf