(57)【特許請求の範囲】
【請求項１】
ストレージプールにデータを書き込むための方法であって、
前記ストレージプールにおける第１のストレージサーバーによってグローバルネームスペースレイアウト（ＧＬ）を作成することを備え、前記ＧＬは、前記ストレージプールにおける前記第１のストレージサーバーに対する第１のサーバーエントリと、前記ストレージプールにおける第２のストレージサーバーからの第２のサーバーエントリとを備え、前記第１のサーバーエントリは、前記第１のストレージサーバーを識別するノード識別子（ＩＤ）を備え、ノードポイントを用いて、どの書き込みリクエストが前記第１のストレージサーバーによって処理されるかを決定し、前記方法はさらに、
前記第１のストレージサーバーによって前記ＧＬをクライアントに提供することと、
前記ＧＬを前記クライアントに提供したあとに、
前記クライアントから、前記第１のストレージサーバーによるオブジェクトレイアウト（ＯＬ）に対するリクエストを受信することと、
前記第１のストレージサーバーによって前記クライアントに前記ＯＬを提供することと、
前記クライアントに前記ＯＬを提供したあとに、
前記第２のストレージサーバー内においてオブジェクトにデータを書き込むための書き込みリクエストを前記第２のストレージサーバーによって受信することとを備え、前記書き込みリクエストはオブジェクトＩＤおよびオフセットを備え、前記方法はさらに、
前記書き込みリクエストに応答して、前記第２のストレージサーバー上において前記オブジェクトに前記データを書き込むことを備え、
前記ＯＬは、ＯＬシーケンス番号を含み、前記ＯＬシーケンス番号は前記オブジェクトが作成されるときに設定され、前記ＯＬシーケンス番号は前記オブジェクトが作成されたときの前記ＧＬのＧＬシーケンス番号に対応する、ストレージプールにデータを書き込むための方法。
【請求項２】
前記ストレージプールは複数のストレージサーバーを備え、前記ＧＬは各ＧＬシーケンス番号に対して前記複数のストレージサーバーのどれが書き込み可能であったかということと、各ＧＬシーケンス番号に対して書き込み可能な前記複数のストレージサーバーにどのように書き込みが分散されたかということとを特定する、請求項１に記載の方法。
【請求項３】
前記ＯＬに対する前記リクエストは、前記オブジェクトと関連付けられる仮想識別子（ＩＤ）を用いて生成される値を備える、請求項１に記載の方法。
【請求項４】
前記ＯＬは前記仮想ＩＤとストライプ幅とをさらに備える、請求項３に記載の方法。
【請求項５】
前記ＧＬは、前記第１のストレージサーバーが前記ストレージプールに追加されたときのＧＬシーケンス番号に対応する第１のノードシーケンス番号をさらに備える、請求項１に記載の方法。
【請求項６】
前記第２のストレージサーバー内において前記ＯＬを格納するためのリクエストを前記第２のストレージサーバーによって受信することをさらに備え、前記ＯＬを格納するための前記リクエストは仮想ＩＤおよび特別なオフセットを特定し、前記方法はさらに、
前記第２のストレージサーバーによって、前記第２のストレージサーバーにおいて前記ＯＬを格納することを備える、請求項１に記載の方法。
【請求項７】
前記第１のストレージサーバーによって前記ＧＬを第２のクライアントに提供することと、
前記ＧＬを前記第２のクライアントに提供したあとに、
前記第１のストレージサーバーによって、前記第２のクライアントからの第２のＧＬを受信することとをさらに備え、前記第２のＧＬは、前記ＧＬと関連付けられる第１のＧＬシーケンス番号よりも大きい第２のＧＬシーケンス番号と関連付けられ、前記方法はさらに、
前記第１のストレージサーバー内に前記第２のＧＬを格納することを備える、請求項１に記載の方法。
【請求項８】
前記第２のストレージサーバーによって、前記オブジェクトを削除するリクエストを受信することと、
前記オブジェクトを削除する前記リクエストを受信することに応答して、
前記第２のストレージサーバーにおける前記オブジェクトに対応するエントリに対して削除フラグをセットすることと、
前記ストレージプールにおける他のすべてのストレージサーバーにおける前記オブジェクトに対応する他のすべてのエントリを無効にすることと、
前記ストレージプールにおける他のすべてのストレージサーバーにおける前記オブジェクトに対応する他のすべてのエントリを無効にしたあとで、前記第２のストレージサーバーにおける前記オブジェクトに対応する前記エントリを無効にすることとをさらに備える、請求項１に記載の方法。
【請求項９】
プロセッサによって実行されるとある方法を実行する命令を備える、非一時的なコンピュータ読取可能媒体であって、前記方法は、
ストレージプールにおける第１のストレージサーバーによってグローバルネームスペースレイアウト（ＧＬ）を作成することを備え、前記ＧＬは、前記ストレージプールにおける前記第１のストレージサーバーに対する第１のサーバーエントリと、前記ストレージプールにおける第２のストレージサーバーからの第２のサーバーエントリとを備え、前記第１のサーバーエントリは、前記第１のストレージサーバーを識別するノード識別子（ＩＤ）を備え、ノードポイントを用いて、どの書き込みリクエストが前記第１のストレージサーバーによって処理されるかを決定し、前記方法はさらに、
前記第１のストレージサーバーによって前記ＧＬをクライアントに提供することと、
前記ＧＬを前記クライアントに提供したあとに、
前記クライアントから、前記第１のストレージサーバーによるオブジェクトレイアウト（ＯＬ）に対するリクエストを受信することと、
前記第１のストレージサーバーによって前記クライアントに前記ＯＬを提供することと、
前記クライアントに前記ＯＬを提供したあとに、
前記第２のストレージサーバー内においてオブジェクトにデータを書き込むための書き込みリクエストを前記第２のストレージサーバーによって受信することとを備え、前記書き込みリクエストはオブジェクトＩＤおよびオフセットを備え、前記方法はさらに、
前記書き込みリクエストに応答して、前記第２のストレージサーバー上において前記オブジェクトに前記データを書き込むことを備え、
前記ＯＬは、ＯＬシーケンス番号を含み、前記ＯＬシーケンス番号は前記オブジェクトが作成されるときに設定され、前記ＯＬシーケンス番号は前記オブジェクトが作成されたときの前記ＧＬのＧＬシーケンス番号に対応する、非一時的なコンピュータ読取可能媒体。
【請求項１０】
前記ストレージプールは複数のストレージサーバーを備え、前記ＧＬは各ＧＬシーケンス番号に対して前記複数のストレージサーバーのどれが書き込み可能であったかということと、各ＧＬシーケンス番号に対して書き込み可能な前記複数のストレージサーバーにどのように書き込みが分散されたかということとを特定する、請求項９に記載の非一時的なコンピュータ読取可能媒体。
【請求項１１】
前記ＯＬに対する前記リクエストは、前記オブジェクトと関連付けられる仮想識別子（ＩＤ）を用いて生成される値を備える、請求項９に記載の非一時的なコンピュータ読取可能媒体。
【請求項１２】
前記ＯＬは前記仮想ＩＤとストライプ幅とをさらに備える、請求項１１に記載の非一時的なコンピュータ読取可能媒体。
【請求項１３】
前記ＧＬは、前記第１のストレージサーバーが前記ストレージプールに追加されたときのＧＬシーケンス番号に対応する第１のノードシーケンス番号をさらに備える、請求項９に記載の非一時的なコンピュータ読取可能媒体。
【請求項１４】
前記方法はさらに、前記第２のストレージサーバー内において前記ＯＬを格納するためのリクエストを前記第２のストレージサーバーによって受信することを備え、前記ＯＬを格納するための前記リクエストは仮想ＩＤおよび特別なオフセットを特定し、前記方法はさらに、
前記第２のストレージサーバーによって、前記第２のストレージサーバーにおいて前記ＯＬを格納することを備える、請求項９に記載の非一時的なコンピュータ読取可能媒体。
【請求項１５】
前記方法はさらに、
前記第１のストレージサーバーによって前記ＧＬを第２のクライアントに提供することと、
前記ＧＬを前記第２のクライアントに提供したあとに、
前記第１のストレージサーバーによって、前記第２のクライアントからの第２のＧＬを受信することとを備え、前記第２のＧＬは、前記ＧＬと関連付けられる第１のＧＬシーケンス番号よりも大きい第２のＧＬシーケンス番号と関連付けられ、前記方法はさらに、
前記第１のストレージサーバー内に前記第２のＧＬを格納することを備える、請求項１０に記載の非一時的なコンピュータ読取可能媒体。
【請求項１６】
前記方法はさらに、
前記第２のストレージサーバーによって、前記オブジェクトを削除するリクエストを受信することと、
前記オブジェクトを削除する前記リクエストを受信することに応答して、
前記第２のストレージサーバーにおける前記オブジェクトに対応するエントリに対して削除フラグをセットすることと、
前記ストレージプールにおける他のすべてのストレージサーバーにおける前記オブジェクトに対応する他のすべてのエントリを無効にすることと、
前記ストレージプールにおける他のすべてのストレージサーバーにおける前記オブジェクトに対応する他のすべてのエントリを無効にしたあとで、前記第２のストレージサーバーにおける前記オブジェクトに対応する前記エントリを無効にすることとを備える、請求項１０に記載の非一時的なコンピュータ読取可能媒体。
【請求項１７】
第１の持続的なストレージを備える第１のストレージサーバーと、
第２の持続的なストレージを備える第２のストレージサーバーとを備え、
前記第１のストレージサーバーは、
グローバルネームスペースレイアウト（ＧＬ）を作成するようプログラミングされ、前記ＧＬは、ストレージプールにおける第１のストレージサーバーに対する第１のサーバーエントリと、前記ストレージプールにおける第２のストレージサーバーからの第２のサーバーエントリとを備え、前記第１のサーバーエントリは、前記第１のストレージサーバーを識別するノード識別子（ＩＤ）を備え、ノードポイントを用いて、どの書き込みリクエストが前記第１のストレージサーバーによって処理されるかを決定し、前記第１のストレージサーバーはさらに、
前記ＧＬをクライアントに提供するようプログラミングされ、
前記ＧＬを前記クライアントに提供したあとに、
前記クライアントから、前記第１のストレージサーバーによるオブジェクトレイアウト（ＯＬ）に対するリクエストを受信するようプログラミングされ、
前記クライアントに前記ＯＬを提供するようプログラミングされ、
前記第２のストレージサーバーは、
前記クライアントに前記ＯＬを送信したあと、前記第２のストレージサーバー内においてオブジェクトにデータを書き込むための書き込みリクエストを前記第２のストレージサーバーによって受信するようプログラミングされ、前記書き込みリクエストはオブジェクトＩＤおよびオフセットを備え、前記第２のストレージサーバーはさらに、
前記書き込みリクエストに応答して、前記第２の持続的なストレージ内の前記オブジェクトに前記データを書き込むようプログラミングされ、
前記ＯＬは、ＯＬシーケンス番号を含み、前記ＯＬシーケンス番号は前記オブジェクトが作成されるときに設定され、前記ＯＬシーケンス番号は前記オブジェクトが作成されたときの前記ＧＬのＧＬシーケンス番号に対応する、システム。
【請求項１８】
前記第１のストレージサーバーは、さらに、第２のクライアントに前記ＧＬを提供するようにプログラミングされ、
前記ＧＬを前記第２のクライアントに提供したあとに、
前記第２のクライアントから第２のＧＬを受信するようにプログラミングされ、前記第２のＧＬは、前記ＧＬと関連付けられる第１のＧＬシーケンス番号よりも大きい第２のＧＬシーケンス番号と関連付けられ、前記第１のストレージサーバーはさらに、
前記第２のＧＬを格納するようにプログラミングされる、請求項１７に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
背景
ストレージシステムは、大量のデータを保存し、記憶容量を経時的に拡張することを可能にすることが必要とされる。記憶容量を拡張するための従来のアプローチは、ストレージプール内の１つまたは複数のストレージサーバーと組み合わせて、１つまたは複数の専用メタデータサーバーを含むことである。ストレージサーバーは、クライアントデータを格納し、メタデータサーバーは、ストレージサーバー内のクライアントデータの場所に関するメタデータ（クライアントデータを含まない。）を格納する。記憶容量の要件が増加すると、ストレージサーバーの数が増加し、メタデータサーバーに格納されるメタデータの量が増加し得る。
【０００２】
このようなシナリオでは、メタデータサーバーは、Ｉ／Ｏリクエストの処理におけるボトルネックとなる。このため、前述の従来のアプローチは、Ｉ／Ｏリクエストの処理に関連するパフォーマンス、すなわち待ち時間に影響を与えることなく、効率的にストレージプールを拡張することができない。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
一般に、一態様において、本発明は、ストレージプールにデータを書き込むための方法に関する。この方法はオブジェクトの仮想識別子（ＩＤ）およびオフセットを受信することと、仮想ＩＤから、ストレージプール内の第１のストレージサーバーを識別するノード識別子（ＩＤ）を抽出することと、第１のストレージサーバーからオブジェクトのためのオブジェクトレイアウト（ＯＬ）を得ることと、ハッシュ値を得るためにオブジェクトＩＤおよびオフセットＩＤをハッシュすることとを含み、仮想ＩＤはオブジェクトＩＤを含み、オフセットＩＤはオフセットから生成され、方法は、グローバルネームスペースレイアウト（ＧＬ）とＯＬとハッシュ値とを使用してストレージプール内の第２のストレージサーバーを識別することと、第２のストレージサーバー内のオブジェクトにデータを書き込むための書き込みリクエストを発行することと、をさらに含み、書き込みリクエストは、オブジェクトＩＤおよびオフセットを含む。
【０００４】
一般に、一態様において、本発明は、ストレージプールにデータを読み出すための方法に関する。方法は、オブジェクトのための仮想ＩＤを受信することと、仮想ＩＤから、ストレージプール内の第１のストレージサーバーを識別するノード識別子（ＩＤ）を抽出することと、第１のストレージサーバーからオブジェクトのためのオブジェクトレイアウト（ＯＬ）を得ることと、ハッシュ値を得るためにオブジェクトＩＤおよびオフセットＩＤをハッシュすることとを含み、仮想ＩＤはオブジェクトＩＤを含み、オフセットＩＤはオフセットから生成され、方法は、コンシステントハッシュ法を用いて、グローバルネームスペースレイアウト（ＧＬ）とＯＬとハッシュ値とを使用してストレージプール内の第２のストレージサーバーを識別することと、第２のストレージサーバー内のオブジェクトからデータを読み込むための読み込みリクエストを発行することと、をさらに含み、書き込みリクエストは、オブジェクトＩＤおよびオフセットを含む。
【０００５】
一般に、一態様において、本発明は、ストレージプールにデータを書き込むための方法に関する。方法は、新しいオブジェクトのためのリクエストを受信することと、ストレージプールからストレージサーバーを選択することとを含み、ストレージサーバーはノード
ＩＤを使用して識別され、方法は、ストレージサーバーに仮想ＩＤを生成するようリクエストすることとをさらに含み、仮想ＩＤはオブジェクトのノードＩＤおよびオブジェクトＩＤを備え、方法は、仮想ＩＤを使用してオブジェクトのためのオブジェクトレイアウト（ＯＬ）を生成することと、ストレージサーバーにＯＬを格納することと、オブジェクトにデータを書き込むための書き込みリクエストを受信することと、をさらに含み、書き込みリクエストはオフセットを備え、方法は、オフセットからオフセットＩＤを生成することと、ハッシュ値を得るためにオブジェクトＩＤおよびオフセットＩＤをハッシュすることと、グローバルネームスペースレイアウト（ＧＬ）とＯＬとハッシュ値とを使用して、ストレージプール内の第２のストレージサーバーを識別することと、第２のストレージサーバー内のオブジェクトにデータを書き込むための書き込みリクエストを発行することと、をさらに含み、書き込みリクエストはオブジェクトＩＤおよびオフセットを備える。
【０００６】
他の態様は、本発明は、以下の説明および添付の特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００７】
【図１】本発明の一つまたは複数の実施形態による、システムを示す。
【図２Ａ】本発明の一つまたは複数の実施形態による、データ構造と、データ構造間の関係とを示す。
【図２Ｂ】本発明の一つまたは複数の実施形態による、データ構造と、データ構造間の関係とを示す。
【図２Ｃ】本発明の一つまたは複数の実施形態による、データ構造と、データ構造間の関係とを示す。
【図３】本発明の一つまたは複数の実施形態による、ストレージプールを初期化するためのフローチャートを示す。
【図４】本発明の一つまたは複数の実施形態による、ストレージプールにストレージサーバーを追加するためのフローチャートを示す。
【図５】本発明の一つまたは複数の実施形態による、ストレージプールにクライアントを接続するためのフローチャートを示す。
【図６】本発明の一つまたは複数の実施形態による、オブジェクトを作成し、オブジェクトにデータを格納するためのフローチャートを示す。
【図７】本発明の一つまたは複数の実施形態による、ストレージプール内に前に作成されたオブジェクトにデータを書き込むためのフローチャートを示す。
【図８】本発明の一つまたは複数の実施形態による、ストレージプール内のオブジェクトからデータを読み出すためのフローチャートを示す。
【図９】本発明の一つまたは複数の実施形態による、ストレージプール内のオブジェクトを削除するためのフローチャートを示す。
【図１０Ａ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｂ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｃ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｄ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｅ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｆ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｇ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｈ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｉ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【図１０Ｊ】本発明の１つまたは複数の実施形態を実現するシステムの例を示す。
【発明を実施するための形態】
【０００８】
詳細な説明
本発明の特定の実施形態は、添付の図面を参照して詳細に説明される。本発明の実施形態の以下の詳細な説明において、多数の具体的な詳細が本発明のより完全な理解を提供するために記載される。しかしながら、本発明はこれらの具体的な詳細なしに実施できることは当業者には明らかであろう。他の例において、周知の特徴は、不必要に記述を複雑化させるのを避けるために詳細には説明していない。
【０００９】
以下の図１〜ｌ０Ｊの説明では、図に関して記載される任意の要素は、本発明の種々の実施形態において、他のいずれの図に関して説明される１つまたは複数の同じような名前の要素と等価でもよい。簡潔にするために、これらの構成要素の説明は、各図に関して繰り返されることはない。したがって、各図の構成要素の各々およびすべての実施形態は、参照により組み込まれ、１つまたは複数の同じ名前の構成要素を有する他のすべての図内に任意に存在することが想定される。さらに、本発明の様々な実施形態による図の構成要素のいずれの説明も、任意の実施形態のように解釈されるべきであり、対応する他のいずれの図の同様の名前の要素に関して説明された実施形態に追加してまたは一体にまたは代替として実現されてもよい。
【００１０】
一般に、本発明の実施形態は、ストレージプールにデータを格納するための方法およびシステムに関する。より具体的には、本発明の実施形態は、ストレージプール内のオブジェクトの位置（複数可）を決定するために、ストレージプールのグローバルネームスペースレイアウト（ＧＬ）およびオブジェクトごとのオブジェクトレイアウト（ＯＬ）（複数可）の組み合わせでコンシステントハッシュ法を使用する、ストレージプールのためのグローバルネームスペースを提供する。
【００１１】
本発明の一実施形態では、システムは、専用のメタデータサーバーを含まない。むしろ、オブジェクトのためのＯＬは、ストレージプールに分散される。言い換えると、各ストレージサーバーは、ＯＬおよびクライアントデータを含むオブジェクトの組み合わせを含み、ＯＬはストレージサーバーに格納される特定のオブジェクトに関連しても、しなくてもよい。本発明の実施形態は、専用のメタデータサーバーを含まないので、本発明の実施形態は、待ち時間のペナルティとメタデータサーバーに関連するスケーリング制限なしに、ストレージプールの無制限のスケーリングを可能にする。
【００１２】
本発明の目的のために、Ｉ／Ｏリクエストは、クライアントに格納されたオブジェクト（すなわち、データ）の論理アドレスまたはクライアントに動作可能に接続されるメモリまたは永続ストレージに格納されるオブジェクトの論理アドレスを特定するリクエストである。Ｉ／Ｏリクエストは、また、オブジェクトの大きさなどの他の情報を含んでもよい。本発明の一実施形態では、論理アドレスは、ｎタプル、すなわち＜オブジェクトＩＤ、オフセット＞であってもよい。任意の種類の論理アドレスが、本発明から逸脱することなく使用されることができる。Ｉ／Ｏリクエストの例としては、読み取りリクエスト（すなわち、ストレージプールに格納されたオブジェクトからデータを取得するためのリクエスト）および書き込みリクエスト（すなわち、ストレージプール内のオブジェクトにデータを書き込むためのリクエスト）を含むが、これらに限定されない。
【００１３】
図１は、本発明の一つまたは複数の実施形態によるシステムを示す。システムは、１つまたは複数のクライアント（１００Ａ、１００Ｂ）と、通信ファブリック（１０４）と、１つまたは複数のストレージサーバー（１０６Ａ、１０６Ｂ）を含むストレージプール（１１２）とを含む。これらのコンポーネントのそれぞれについて以下に説明する。
【００１４】
本発明の一実施形態では、クライアント（１００Ａ、１００Ｂ）はＩ／Ｏリクエストをストレージサーバー（１０６Ａ、１０６Ｂ）に発行する機能を含む任意の物理的なシステムである。本発明の一実施形態では、クライアントは、プロセッサ（図示せず）と、メモ
リ（図示せず）と、永続ストレージ（図示せず）とを含んでもよい。クライアントは、１つまたは複数のアプリケーション（図示せず）を実行するための機能をさらに含む。アプリケーションは、ユーザレベルのアプリケーションおよび／またはカーネルレベルのアプリケーションであってもよい。アプリケーションは、Ｉ／Ｏリクエストを発行するように構成されており、アプリケーションによって発行されたＩ／Ｏリクエストは、ストレージコントローラデバイスドライバ（ＳＣＤＤ）（１０２Ａ、１０２Ｂ）によって受信され、処理される。
【００１５】
ストレージコントローラデバイスドライバ（ＳＣＤＤ）（１０２Ａ、１０２Ｂ）は、図５〜９に示す実施形態に従ってＩ／Ｏリクエストを受信し処理するように構成される。本発明の一実施形態では、ＳＣＤＤは、クライアントの（カーネルレベルでは対照的な）ユーザレベルで実行される。
【００１６】
本発明の一実施形態では、ストレージプール（１１２）は、１つまたは複数のストレージサーバー（１０６Ａ、１０６Ｂ）を含む。各ストレージサーバーは、ストレージコントローラ（１０８Ａ、１０８Ｂ）とストレージ（１１０Ａ、１１０Ｂ）とを含む。
【００１７】
ストレージコントローラ（１０８Ａ、１０８Ｂ）は、図３〜９に係る本発明の様々な実施形態を実現するように構成される。本発明の一実施形態において、ストレージコントローラは、本発明の１つまたは複数の実施形態を実現するための命令を実行するように構成されたプロセッサ（図示せず）を備える。命令は、ストレージコントローラ内に位置するか、または、ストレージコントローラに動作可能に接続される非一時的なコンピュータ可読媒体（図示せず）に格納される。代替的に、ストレージコントローラは、前述の機能を提供するように構成された集積回路を使用して実現されてもよい。代替的に、ストレージコントローラは、ＦＰＧＡ、ＡＳＩＣ、他の専用ハードウェアまたはそれらの任意の組み合わせを使用して実現されてもよい。ストレージコントローラは、本発明から逸脱することなく、ソフトウェアおよび／またはハードウェアの任意の組み合わせを使用して実現されてもよい。
【００１８】
本発明の一実施形態では、ストレージ（１１０Ａ、１１０Ｂ）においては、磁気記憶デバイス、光記憶デバイス、固体メモリデバイス、相変化メモリデバイス、任意の他の適切なタイプの永続的な記憶デバイス、またはそれらの任意の組み合わせを含む１つまたは複数の永続的な記憶デバイスを含むが、これらに限定されない。
【００１９】
本発明の一実施形態では、通信ファブリック（１０４）は、クライアント（１００Ａ、１００Ｂ）とストレージプール（１１２）との間の通信を可能にする。通信ファブリックは、クライアント（１００Ａ、１００Ｂ）とストレージプール（１１２）との間の通信を、任意の有線、無線、または、ハイブリッド（有線および無線）接続を使用して可能にしてもよい。
【００２０】
通信ファブリックは、単一のスイッチまたは複数の相互接続されたスイッチ（図示せず）を含んでもよい。通信ファブリックが複数のスイッチを含む場合、各スイッチは、すべての他のスイッチに接続されてもよく、スイッチファブリック内のスイッチのサブセットに接続されていてもよく、または１つの他のスイッチに接続されてもよい。本発明の一実施形態では、スイッチの各々は、クライアント（１００Ａ、１００Ｂ）とストレージプール（１１２）と間の通信を可能にするように構成される（通信ファブリックが実施するプロトコル（複数可）によって定義されるような）ハードウェアと（たとえば、集積回路を使用して実装された）ロジックの組み合わせである。
【００２１】
通信ファブリックは、任意の通信プロトコルを使用して通信を容易にしてもよい。この
ような通信プロトコルの例は、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）、ＰＣＩエクスプレス（ＰＣＩｅ）、ＰＣＩ拡張（ＰＣＩ−Ｘ）、不揮発性メモリエクスプレス（ＮＶＭｅ）、ＰＣＩ−Ｅｘｐｒｅｓｓのファブリック上の不揮発性メモリエクスプレス（ＮＶＭｅ）、イーサネット（登録商標）ファブリック上の不揮発性メモリエクスプレス（ＮＶＭｅ）、およびＩｎｆｉｎｉＢａｎｄファブリック上の不揮発性メモリエクスプレス（ＮＶＭｅ）を含んでもよいが、これに限定されない。本発明は、上記のプロトコルに限定されるものではない。
【００２２】
図１に示したもの以外のシステム構成を本発明から逸脱することなく使用してもよい。
図２Ａ〜２Ｄは、本発明の一つまたは複数の実施形態によるデータ構造とデータ構造間の関係を示す。
【００２３】
グローバルネームスペースレイアウト（ＧＬ）は、ストレージプール（またはその一部）の寿命にわたってストレージプール（またはその一部）の状態を特定する。所与の時刻に、ストレージプールの状態は、（ｉ）どのストレージサーバーがストレージプール内で書き込み可能であるかということと、（ｉｉ）ストレージプール内で書き込み可能であるストレージサーバーへの書き込み分散とを特定する。具体的には、ストレージサーバーは、データがストレージサーバー上のオブジェクトに書き込み得るとき、「書き込み可能」であるとみなされる。このため、ストレージプール内のストレージサーバーの数がＮであり、Ｍ＜ＮであるＭ台のストレージサーバーのみが「書き込み可能」である状況があり得る。ストレージサーバーが「書き込み可能」であるか否かに関係なく、ストレージサーバーは、たとえば図８に従って、読み出しリクエストを処理してもよい。書き込み可能であるストレージサーバー間での書き込み分散に関して、書き込み可能であるストレージサーバー間での書き込み分散は、どの書き込み可能なストレージサーバーに与えられたオブジェクトのデータが格納され得るかを決定する。言い換えると、書き込みリクエストが受信されたとき、書き込み可能であるストレージサーバー間の書き込み分散は、データが最終的にどのストレージサーバーに格納されるかを決定する。
【００２４】
再び図２Ａを参照して、ＧＬ（２００）は、ＧＬシーケンス番号（２０２）と、ノード数（２０４）と、１つまたは複数のサーバーエントリ（２０６Ａ、２０６Ｂ）とを含む。これらのコンポーネントのそれぞれについて以下に説明する。
【００２５】
ＧＬシーケンス番号（２０２）は、ストレージプールの存続期間にわたってＧＬのバージョンを一意に識別する。ノード数（２０４）は、ストレージプール内のストレージサーバーの数を特定する。しかし、上述したように、すべてのストレージサーバーが、「書き込み可能」でなくてもよい。
【００２６】
各サーバーエントリ（２０６Ａ、２０６Ｂ）は、所定の時間における特定のサーバーの書き込み分散を特定する。具体的には、サーバーエントリは（ｉ）ストレージプール（またはＧＬに関連付けられるストレージプールの一部）内のストレージサーバーを一意に識別するノード識別子（ＩＤ）（２０８Ａ、２０８Ｂ）と、（ｉｉ）（後述する）１つまたは複数のノードポイント（２１０Ａ、２１０Ｂ）と、（ｉｉｉ）このサーバーエントリが適用されるＧＬシーケンス番号を特定するノードシーケンス番号（２１２Ａ、２１２Ｂ）とを含んでもよいが、これらに限定されない。
【００２７】
ノードポイントに関して、ハッシュ関数が各ノードＩＤに適用され、これにより［０、．．．、Ｎ］の数値範囲にマッピングされる１つまたは複数の値が生成される。値は、その後Ｎで割られ、これにより、［０、．．．、１］の数値範囲にマッピングされるノードポイントが得られる。これは、概念的に単位円（すなわち、半径１を有する円）と見てもよい。すべてのストレージサーバーに対する数値範囲［０、．．．、１］内のノードポイ
ントの数と分散は、特定のＧＬシーケンス番号でのストレージサーバーの書き込み分散を表す。特定のストレージサーバーが、所与のＧＬシーケンス番号のノードポイントを有していない場合、その特定のストレージサーバーは、そのＧＬシーケンス番号において「書き込み可能」ではない。書き込み分散は、本発明から逸脱することなく他の有限の数値範囲（すなわち、［０、．．．、１］以外の数値範囲）を使用して特定されてもよい。
【００２８】
本発明の一実施形態では、ＧＬシーケンス番号は、（ｉ）ストレージプール（またはその一部）内のストレージサーバーのいずれかに対するノードポイント（複数可）が変更されたとき、または（ｉｉ）新しいストレージサーバーがストレージプールへ追加されたとき（たとえば、図４参照。）のいずれかに更新される。１つまたは複数のストレージサーバーに対するノードポイント（複数可）は、各ストレージサーバーの空き記憶容量に基づいて１つまたは複数のストレージサーバーに向かっておよび／または１つまたは複数のストレージサーバーから離れて書き込みをバイアスするために修正されてもよい。代替的に、１つまたは複数のストレージサーバーに対するノードポイント（複数可）は、新しいストレージサーバーがストレージプールに追加される際にストレージプール内のストレージサーバー間でのデータの均一な分散を確実にするために修正されてもよい。代替的に、１つまたは複数のストレージサーバーのノードポイント（複数可）は、個々のサーバーの帯域幅および／またはＩ／Ｏリクエストの処理能力を考慮するために修正されてもよい。
【００２９】
図２Ｂは、本発明の一実施形態によるオブジェクトレイアウト（ＯＬ）を示す。ＯＬ（２１４）は、ＯＬシーケンス番号（２１６）と、仮想ＩＤ（ＶＩＤ）（２１８）と、ストライプ幅（２２４）とを含む。これらのコンポーネントのそれぞれについて以下に説明する。
【００３０】
ＯＬシーケンス番号（２１６）は、ＯＬ（２１４）に対応するオブジェクトが最初に作成された時のＧＬ（２００）のＧＬシーケンス番号（２０２）に対応する。仮想ＩＤ（２１８）は、ノードＩＤ（２２０）とオブジェクトＩＤ（２２２）とを含む。ノードＩＤ（２２０）は、ＶＩＤ（２１８）を生成し、ＶＩＤ（２１８）のコピー（例示的には適切なＯＬに格納される。たとえば図６を参照。）を含むストレージサーバーを識別する。オブジェクトＩＤ（２２２）は、グローバルネームスペース内のオブジェクトを一意に識別する（すなわち、オブジェクトＩＤは、グローバルネームスペースが及ぶストレージサーバー内の他のすべてのオブジェクトＩＤに関して一意である）。ストライプ幅（２２４）は、ＧＬ内の次のストレージサーバーポイントに進む前に、（ＧＬによって識別される）ストレージサーバーに順次転送されるデータの単位に相当する。たとえば、ストライプ幅（ＳＷ）が６４Ｋｂであり、ストレージプールに書き込まれるオブジェクトがオブジェクトＩＤとオフセット（Ｏ）＝２５６Ｋによって識別され、オブジェクトに書き込まれるデータのサイズが１２８Ｋｂである場合、それぞれ６４Ｋｂのデータを含む２つのリクエストが発行され、各書き込みリクエストは異なるストレージサーバーによって処理されてもよい。具体的には、オブジェクトのためのＯＬは、ハッシュ＜ＶＩＤ、−１＞を使用して識別される。第１の６４Ｋｂのための第１の書き込みリクエストは、ハッシュ＜オブジェクトＩＤ、２５６＞およびＧＬを使用して識別されたストレージサーバーに発行され、第２の６４Ｋｂのための第２の書き込みリクエストは、ハッシュ＜オブジェクトＩＤ、２５６＋６４＞とＧＬとを使用して識別されたストレージサーバーに発行される。上記のハッシュ値を使用する特定のストレージサーバーの選択については以下に説明する。本発明の一実施形態では、ストライプ幅は、ストレージサーバーおよび／または通信ファブリックによってサポートされる最大伝送単位（ＭＴＵ）と等しくなるように設定される。
【００３１】
ストレージプール内の各オブジェクトに対し単一のＯＬがある。本発明の一実施形態では、一度作成されるとオブジェクトのＯＬは変更されない。ＯＬは、ＯＬに対応するオブジェクトが作成された時点でＧＬの状態を識別するために使用される。この情報を使用し
て、オブジェクト（またはその一部）は、ストレージプール内に配置されてもよい（たとえば、図７および図８を参照。）。
【００３２】
図２Ｃは、本発明の１つまたは複数の実施形態によるハッシュ値と物理的な格納場所との関係を示す。各ＯＬは、一意のＶＩＤを有し、ＶＩＤで特定されたノードＩＤによって識別されるストレージサーバー内の少なくとも一つの物理的な位置に格納される（たとえば図２Ｂ、２１８を参照。）。本発明の一実施形態では、物理的な記憶場所（２２８）（すなわち、ＯＬが格納された物理的な位置）は、ノードＩＤによって識別されるストレージサーバー内のハッシュテーブルエントリにマッピングされる。ハッシュテーブルのエントリは、＜ＶＩＤ、−１＞（２２６）をハッシュすることによって生成されたハッシュ値に関連付けられる。ハッシュテーブルエントリは、ストレージサーバーの揮発性メモリにＯＬのコピーの場所を含んでもよい。任意のハッシュ関数と特別なオフセット（−１だけでなく）を、本発明から逸脱することなく使用してもよい。
【００３３】
図３〜９は、本発明の１つまたは複数の実施形態によるフローチャートを示す。各フローチャートにおける様々なステップを提示して順次説明するが、当業者は、ステップの一部または全部が、異なる順序で実行されても、組み合わされても、または省略されてもよく、ステップの一部または全部が並列に実行されてもよいことを理解する。本発明の一実施形態では、図３〜９に示す１つまたは複数のステップは、図３〜９に示される１つまたは複数の他のステップと並行して実行されてもよい。
【００３４】
図３は、本発明の一つまたは複数の実施形態によるストレージプールを初期化するためのフローチャートを示す。図３に示される処理は、ストレージプール内のストレージサーバーのいずれかよって、またはシステム内のクライアントのいずれかよって行われてもよい。ステップ３００において、ストレージプールに含まれるべきストレージサーバーが、識別される。ステップ３０２では、ステップ３００で識別されたストレージサーバーの１つが選択される。ステップ３０４において、ステップ３０２で選択されたストレージサーバーのノードＩＤが得られる。ノードＩＤは、ＩＤを取得および／または生成するための任意の公知のメカニズムを使用して取得および／または生成されてもよい。
【００３５】
ステップ３０６において、ハッシュ関数は、１つまたは複数のノードポイントを取得するためにノードＩＤに適用される。特定のストレージサーバーに割り当てられたノードポイントの数は、クライアントによって特定されたポリシーに基づいて、または１つまたは複数のストレージサーバーによって特定されたポリシーに基づいて、またはストレージプールに関連付けられたデフォルトのポリシーに基づいて決定されてもよい。ステップ３０８では、ステップ３０２で識別されたストレージサーバーに対応するサーバーエントリは、ノードＩＤとノードポイント（複数可）とノードシーケンス番号とを使用して作成され、投入される。ノードシーケンス番号は、現在のＧＬシーケンス番号に対応する。たとえば、ＧＬシーケンス番号が０であるときにサーバーエントリが作成される場合、ノードシーケンス番号は０に設定される。図３は、初期ＧＬの生成を示す。したがって、ＧＬにおけるＧＬシーケンス番号が正式にこの段階でＧＬに設定し得ない場合でも、ＧＬシーケンス番号は、たとえば１など、初期ＧＬシーケンス番号の値になるだろう。したがってノードシーケンス番号は正式に初期ＧＬを設定する前に設定されてもよい。
【００３６】
ステップ３１０では、処理すべき追加のストレージサーバーがあるかどうかについて決定が行われる。処理すべき追加のストレージサーバーが存在する場合、処理はステップ３０２に進む。そうでなければ、処理はステップ３１２に進む。ステップ３１２で、ＧＬシーケンス番号はＧＬに設定される。図３は、初期ＧＬの生成を示す。このため、ＧＬシーケンス番号は、初期ＧＬシーケンス番号の値、たとえば１に設定される。ステップ３１４では、ノード数が設定される。ノード数は、ストレージプール内のストレージサーバーの
数に対応する。ステップ３１６で、ＧＬは、ストレージプール内の各サーバーに格納される。
【００３７】
図４は、本発明の一つまたは複数の実施形態によるストレージプールにストレージサーバーを追加するためのフローチャートを示す。ステップ４００では、ストレージプールに追加する追加のストレージサーバーが識別される。例示的には、このステップは、図３に示す処理が行われた後のある時点、たとえば、追加のストレージサーバーがストレージプールのストレージ容量を増加させるために追加されたときに発生する。
【００３８】
ステップ４０２では、ノードＩＤは、追加のストレージサーバー用に取得される。ノードＩＤは、ＩＤを取得および／または生成するための任意の公知のメカニズムを使用して取得および／または生成されてもよい。ステップ４０４において、ハッシュ関数は、１つまたは複数のノードポイントを取得するためにノードＩＤに適用される。ノードポイント（複数可）が生成されてもよく、これにより新たな書き込みリクエストは、追加のストレージサーバーに向けてバイアスされる。ステップ４０６では、ステップ４００で識別された追加のストレージサーバーに対応するサーバーエントリがノードＩＤとノードポイント（複数可）とノードシーケンス番号とを使用して作成され、投入される。現在のＧＬシーケンス番号は、１だけ増分したノードシーケンス番号に対応する。サーバーエントリは、更新されたＧＬを得るためにＧＬに追加される。
【００３９】
ステップ４０８では、ＧＬシーケンス番号は、更新されたＧＬ内で更新される。たとえば、ＧＬシーケンス番号が１だけ増分される。ステップ４０６で作成されたサーバーエントリのためのノードシーケンス番号は、更新されたＧＬシーケンス番号に等しい。ステップ４１０では、ノード数は、ストレージプール内の追加のストレージサーバーを反映するように更新される。ステップ４１２では、更新されたＧＬは、ストレージプール内の各サーバーに格納される。本発明の一実施形態では、各ストレージサーバーに１つのＧＬのみが格納される。このため、更新されたＧＬがストレージサーバーによって受信されたとき、前のＧＬは削除されるか、そうでなければ、ストレージサーバーから除去される。本発明の一実施形態では、更新されたＧＬは、図５に記載された方法に従って、ストレージサーバーによって得られてもよい。
【００４０】
図５は、本発明の一つまたは複数の実施形態によるストレージプールにクライアントを接続するためのフローチャートを示す。本発明の一実施形態では、図５に示される処理は、ＳＣＤＤ（図１では１０２Ａ、１０２Ｂ）によって行われる。
【００４１】
ステップ５００では、ストレージプール内のストレージサーバーのいずれかが、クライアントからの接続リクエストを受信する。ステップ５０２では、接続リクエストに応答して、ストレージサーバーは、クライアントに、現在のＧＬを提供する。ステップ５０４では、クライアントは、既にＧＬを有するかどうかを決定する。本発明の一実施形態ではクライアントが前にストレージプール内の他のストレージサーバーに接続している場合、クライアントは既にＧＬを含む（ステップ５０２で得られた現在のＧＬと同じかもしれないし、違うかもしれない。）。クライアントが既に別のＧＬを持つ場合、処理は５０６に進む。そうでなければ処理を終了する。
【００４２】
ステップ５０６では、ステップ５０２で得られたＧＬがストレージプールの最新のＧＬであるかどうかについて決定が行われる。具体的には、ステップ５０２で得られたＧＬシーケンス番号が前にクライアントによって得られたＧＬシーケンス番号よりも大きいかどうかについて決定が行われる。ステップ５０２で得られたＧＬシーケンス番号が前にクライアントによって得られたＧＬシーケンス番号よりも大きい場合、処理は５０８に進む。そうでなければ処理を終了する。ステップ５０８では、クライアントは、前に保存された
ＧＬ（すなわち、クライアントに提供したＧＬのＧＬシーケンス番号よりも大きいＧＬシーケンス番号のＧＬ）をストレージサーバーに送信する。
【００４３】
図６は、本発明の一つまたは複数の実施形態による、オブジェクトを作成しオブジェクトにデータを格納するためのフローチャートを示す。本発明の一実施形態では、図６に示す処理は、ＳＣＤＤ（図１の１０２Ａ、１０２Ｂ）によって行われる。
【００４４】
ステップ６００では、新しいオブジェクトを作成するためのリクエストが受信される。本発明の一実施形態において、リクエストは、クライアント上で実行するアプリケーションによって発行され、ＳＣＤＤによって受信される。
【００４５】
ステップ６０２では、ストレージサーバーが選択される。本発明の一実施形態では、ストレージサーバーは、ストレージプールからランダムに選択され、またはラウンドロビンアルゴリズムを使用して選択される。ストレージプールからストレージサーバーを選択する任意の方法を、本発明から逸脱することなく使用してもよい。
【００４６】
ステップ６０４において、リクエストは、新しい仮想ＩＤ（ＶＩＤ）を生成するために、ステップ６０２で識別されたストレージサーバーに送信される。ＶＩＤは、ストレージサーバーおよびオブジェクトＩＤを識別するノードＩＤを含み、ストレージプール内の新しいオブジェクトを識別する。
【００４７】
ステップ６０６では、オブジェクトのためのオブジェクトレイアウト（ＯＬ）が作成される。ＯＬは、ストレージサーバーによって、またはＳＣＤＤによって作成されてもよい。具体的には、ストレージサーバーとＳＣＤＤの両方が、オブジェクトのためのＯＬを投入するために必要な情報を含む。
【００４８】
ステップ６０８では、＜ＶＩＤ、−１＞は、第１のハッシュ値を取得するためにハッシュされる。上述のように、特別なオフセット（−１以外）が、本発明から逸脱して使用されてもよい。ステップ６１０では、オブジェクトのためのＯＬは、第１のハッシュ値を使用してストレージサーバーに格納される。上述したように、第１のハッシュ値はストレージサーバー上のハッシュテーブルエントリに関連付けられ、ハッシュテーブルエントリはＯＬが格納されたストレージサーバーのストレージ内の少なくとも１つの物理的な場所に関連付けられる。この段階で、オブジェクトとそれに対応するＯＬが作成される。しかしながら、いずれのデータもオブジェクトに格納されていない。以下のステップは、データが最初にオブジェクトに格納される方法について説明する。
【００４９】
ステップ６１２では、＜オブジェクトＩＤ、オフセットＩＤ＞は、第２のハッシュ値を得るためにハッシュされる。具体的には、クライアント上のアプリケーションは、オブジェクトに格納されるＶＩＤおよびオフセットに関連付けられるデータをリクエストする。これに応答して、ＳＣＤＤはＶＩＤからオブジェクトＩＤを取得し、オフセットＩＤはオフセットのストライプ幅に基づいてビットマスクを適用することによって得られる。
【００５０】
ステップ６１４では、ストレージプール内のターゲットストレージサーバーは、第２のハッシュ値と、ＧＬと、オブジェクトのためのＯＬとを使用して識別される。具体的には、ＯＬシーケンス番号はＯＬから抽出され、ＯＬが作成されたときにどのストレージサーバーが「書き込み可能」であったかを決定するために使用される。本発明の一実施形態では、どのストレージサーバーが「書き込み可能」であったかの決定は、（ｉ）ＯＬシーケンス番号以下のノードシーケンス番号を持つすべてのサーバーエントリを識別することと、（ｉｉ）ＯＬが作成されたときに書き込み可能であった１つまたは複数のノードポイントを決定するために同じノードＩＤを持つすべてのサーバーエントリを分析することと、
（ｉｉｉ）（ｉ）および（ｉｉ）からのノードポイントの最終的な組を生成することと、（ｉｖ）ターゲットサーバーを識別するために第２のハッシュ値およびノードポイントにコンシステントハッシュ法を使用することと、を含む。コンシステントハッシュ法は、さらに、図１０Ａ〜１０Ｊを参照して説明される。
【００５１】
以下は、ＯＬが作成されたときにどのストレージサーバーが「書き込み可能」だったかを決定する例である。この実施例は、本発明の範囲を限定するものではない。
【００５２】
ＧＬが次のサーバーエントリを持つシナリオを考える。
Ｅ１：［ノードＡ、［Ａ１、Ａ２］、Ｓ１］
Ｅ２：［ノードＡ、［Ａ３］、Ｓ２］
Ｅ３：［ノードＢ、［Ｂ１］、Ｓ１］
Ｅ４：［ノードＣ、［Ｃ１、Ｃ２］、Ｓ２］
Ｅ５：［ノードＤ、［Ｄ１］、Ｓ３］
また、オブジェクトのＯＬは、次のとおりである。
【００５３】
ＯＬ：［Ｓ２、ＶＩＤ、ＳＷ］
これにより、ＯＬシーケンス番号以下のノードシーケンス番号を持つサーバーエントリは、Ｅ１、Ｅ２、Ｅ３、Ｅ４である。また、Ｅ１およびＥ２は、同じノードＩＤ、すなわち、ノードＡを持つが、別のノードシーケンス番号で別のノードポイントを持ち、それに応じて、Ｅ１およびＥ２は、Ｓ２でノードＡとして識別されるストレージサーバーに関連付けられるべきであるノードポイントを決定するために分析される。この例では、Ｓ２では唯一のノードポイントＡ３がある。したがって、ノードポイントの最終組は、Ａ３、Ｂ１、Ｃ１、Ｃ２である。
【００５４】
図６を続けて参照して、ステップ６１６で、オブジェクトにデータを格納するための書き込みリクエストはターゲットサーバーに送信される。リクエストは、オブジェクトＩＤおよびオフセットを特定する。上記のリクエストは、本発明から逸脱することなく、任意の論理アドレスを使用してもよい。
【００５５】
図７は、本発明の一つまたは複数の実施形態による、ストレージプール内に前に作成されたオブジェクトにデータを書き込むためのフローチャートを示す。本発明の一実施形態では、図７に示される処理は、ＳＣＤＤ（図１の１０２Ａ、１０２Ｂ）によって行われる。
【００５６】
ステップ７００では、＜ＶＩＤ、オフセット＞が受信される。ステップ７０２において、ノードＩＤは、ＶＩＤから抽出される。ステップ７０４では、＜ＶＩＤ、−１＞は、第１のハッシュ値を得るためハッシュされる。上述のように、（−１以外）のいずれの特別なオフセットを、本発明から逸脱して使用してもよい。ステップ７０６において、ノードＩＤによって識別されるストレージサーバーからのＯＬは、第１のハッシュ値を使用して得られる。ＳＣＤＤが前にＯＬを取得していた場合（たとえば、図６中の様々なステップを実行したとき）には、ステップ７０２〜７０６は実行されなくてもよく、代わりに、クライアントは前にキャッシュされたＯＬを使用してもよい。
【００５７】
ステップ７０８では、＜オブジェクトＩＤ、オフセットＩＤ＞は、第２のハッシュ値を得るためにハッシュされる。本発明の一実施形態では、オブジェクトＩＤはＶＩＤから取得され、オフセットＩＤはオフセットのストライプ幅に基づいてビットマスクを適用することによって得られる。ステップ７１０では、ストレージプール内のターゲットストレージサーバーは、第２のハッシュ値とＧＬとオブジェクトのためのＯＬとを使用して識別される。ターゲットサーバーは、図６のステップ６１４で説明したのと同じ処理を使用して
識別される。ステップ７１２では、オブジェクトにデータを格納するためのリクエストは、ターゲットサーバーに送信され、リクエストは、オブジェクトＩＤおよびオフセットを特定する。上記のリクエストは、本発明から逸脱することなく、任意の論理アドレスを使用してもよい。ステップ７１４では、ターゲットストレージサーバーがＯＬを含むかどうかについて決定が行われる。ターゲットストレージサーバーがＯＬを含む場合は処理を終了する。そうでなければ、処理はステップ７１６に進む。ステップ７１６で、ＯＬは第１のハッシュ値を使用してターゲットストレージサーバーに保存される。このように、与えられたＯＬの追加のコピーは、ストレージプール内の様々なストレージサーバーに格納される。これにより、クライアントはハッシュ＜ＶＩＤ、−１＞を使用してノードＩＤによって識別されるサーバー以外のサーバーのためのＯＬを得ることができる。
【００５８】
図８は、本発明の一つまたは複数の実施形態による、ストレージプール内のオブジェクトからのデータ読み出しのためのフローチャートを示す。本発明の一実施形態では、図８に示される処理は、ＳＣＤＤ（図１の１０２Ａ、１０２Ｂ）によって行われる。
【００５９】
ステップ８００では、＜ＶＩＤ、オフセット＞が受信される。ステップ８０２では、ノードＩＤは、ＶＩＤから抽出される。ステップ８０４では、＜ＶＩＤ、−１＞は第１のハッシュ値を得るためにハッシュされる。上述のように、特別なオフセット（−１以外）を、本発明から逸脱して使用してもよい。ステップ８０６において、ノードＩＤによって識別されるストレージサーバーからのＯＬは、第１のハッシュ値を使用して得られる。ＳＣＤＤが前にＯＬを取得していた場合は、処理８０２〜８０６が実行される必要はない。代わりに、ＳＣＤＤはＯＬを取得するためにクライアントを検索してもよい。
【００６０】
ステップ８０８では、＜オブジェクトＩＤ、オフセットＩＤ＞は、第２のハッシュ値を得るためにハッシュされる。本発明の一実施形態では、オブジェクトＩＤは、ＶＩＤから取得され、オフセットＩＤはオフセットのストライプ幅に基づいてビットマスクを適用することによって得られる。ステップ８１０では、ストレージプール内のターゲットストレージサーバーは、第２のハッシュ値とＧＬとオブジェクトのＯＬとを使用して識別される。ターゲットサーバーは、図６のステップ６１４で説明したのと同じ処理を使用して識別される。ステップ８１２では、オブジェクトの読み出しリクエストは、ターゲットサーバーに送信され、リクエストは、オブジェクトＩＤおよびオフセットを特定する。上記のリクエストは、本発明から逸脱することなく、任意の論理アドレスを使用してもよい。
【００６１】
図９は、本発明の一つまたは複数の実施形態による、ストレージプール内のオブジェクトを削除するためのフローチャートを示す。本発明の一実施形態では、図９に示す処理はＳＣＤＤ（図１の１０２Ａ、１０２Ｂ）によって実行および／または開始される。
【００６２】
ステップ９００では、ＶＩＤが得られ、ＶＩＤはストレージプールから削除されるべきオブジェクトに対応する。ステップ９０２では、ノードＩＤはＶＩＤから抽出される。ステップ９０４では、＜ＶＩＤ、−１＞は第１のハッシュ値を得るためにハッシュされる。上述のように、特別なオフセット（−１以外）を、本発明から逸脱して使用してもよい。ステップ９０６では、削除フラグは、ノードＩＤで識別されるストレージサーバーの第１のハッシュ値に対応するハッシュテーブルエントリに書き込まれる。ステップ９０８では、ストレージプール内の他のすべてのストレージサーバーの第１のハッシュ値に対応するすべてのハッシュテーブルエントリが無効化される。ステップ９１０において、ノードＩＤで識別されるストレージサーバーの第１のハッシュ値に対応するハッシュテーブルエントリが無効化される。この段階では、今無効化されるオブジェクトおよび／またはＯＬを格納するために前に割り当てられた物理ストレージは、任意の既知のストレージ再利用アルゴリズムを使用して再利用されることができる。
【００６３】
図１０Ａ〜１０Ｊは、本発明の一つまたは複数の実施形態による例を示す。実施例は、本発明の範囲を限定するものではない。また、クライアントとストレージサーバー内の様々な構成要素は、図１０Ａ〜１０Ｊを明確にするために省略されている。
【００６４】
初期に２つのストレージサーバーを含むストレージプールに接続されたクライアントを含むシステムのシナリオを考える。図１０Ａは、ストレージプールの初期ＧＬを示す。図１０Ａを参照して、ＧＬは、ストレージサーバーのそれぞれに対してサーバーエントリ（サーバーエントリＡ、サーバーエントリＢ）を含む。具体的には、サーバーエントリＡはストレージサーバーＡに対応し（図１０Ｂを参照。）、（ｉ）ストレージプール内でストレージサーバーＡを一意に識別するノードＩＤ  Ａと、（ｉｉ）ノードポイントＡ１、Ａ２（図１０Ｄを参照。）と、（ｉｉｉ）ＧＬシーケンス番号が１に等しいときにサーバーエントリＡがＧＬに追加されたことを示すノードシーケンス番号Ａ：１とを特定する。同様に、サーバーエントリＢはストレージサーバーＢに対応し（図１０Ｂを参照。）（ｉ）ストレージプール内のストレージサーバーＢを一意に識別するノードＩＤ  Ｂと、（ｉｉ）ノードポイント：Ｂ１（図１０Ｄを参照。）と、（ｉｉｉ）ＧＬシーケンス番号が１に等しいときにサーバーエントリＢがＧＬに追加されたされたことを示すノードシーケンス番号Ｂ：１とを特定する。ＧＬもまた１に設定されたＧＬシーケンス番号を含み、これは初期ＧＬであり、２つのストレージサーバーがストレージプール内に存在するためノード数が２に設定される。
【００６５】
図１０Ｂを参照して、時間的にいくらか後の点で、クライアントＡは、サーバーＡに新しいオブジェクトをリクエストする。上述したように、クライアントＡは、ストレージプール内の書き込み可能であるストレージサーバーのいずれかに新しいオブジェクトのリクエストを送信してもよい。リクエストに応じて、ストレージサーバーＡは、ノードＩＤ  Ａおよびストレージプール内の新しいオブジェクトのためのオブジェクトＩＤを含むＶＩＤを生成する。ストレージサーバーＡは、その後、新しいオブジェクトのためのオブジェクトレイアウト（ＯＬ）を生成する。図１０ＣはストレージサーバーＡによって生成されたＯＬを示す。図１０Ｃを参照して、ＯＬは、（ｉ）ＧＬシーケンス番号が１に等しかったときにＯＬエントリが作成されたことを示すＯＬシーケンス番号：１と、（ｉｉ）前にストレージサーバーＡによって生成されたＶＩＤと、（ｉｉｉ）ストライプ幅：６４Ｋｂとの情報を含む。
【００６６】
図１０Ｂを再び参照して、ＯＬを生成した後、ストレージサーバーＡはハッシュ＜ＶＩＤ、−１＞を使用してＯＬを格納し、クライアントＡにＯＬのコピーを送信する。しばらくしてクライアントＡ上で実行するアプリケーション（図示せず）は、＜オブジェクトＩＤ、オフセット１＞にデータを書き込むことをリクエストする。そのリクエストに応答して、クライアントＡは、ＯＬ（図１０Ｃを参照。）とＧＬ（図１０Ａ参照。）とハッシュ＜オブジェクトＩＤ、オフセットＩＤ１＞とを使用してターゲットサーバーを識別する。オフセットＩＤ１は、ＯＬから得られたストライプ幅でオフセット１をマスキングすることによって生成される（図１０Ｃを参照。）。
【００６７】
先に述べたように、ＯＬは、ＯＬが作成された時点でのグローバルネームスペース内でどのストレージサーバーが「書き込み可能」であったかを決定するために使用される。この例では、ＯＬシーケンス番号が１である。このため、ＯＬが作成された時点でグローバルネームスペース内で書き込み可能であったストレージサーバーは、１以下のノードシーケンス番号を持つＧＬ内のサーバーエントリを持つ。図１０ＡのＧＬを参照して、サーバーエントリＡとサーバーエントリＢの両方は、１に等しいノードシーケンス番号を持ち、このためＯＬが作成された時点でグローバルネームスペースに書き込み可能であった。ストレージサーバーのそれぞれのノードポイント（すなわち、Ａ１とＡ２とＢ１）は、対応するサーバーエントリから得られる。
【００６８】
ターゲットサーバーは、その後、ノードポイント（すなわち、Ａ１とＡ２とＢ１）およびハッシュ＜オブジェクトＩＤ、オフセットＩＤ１＞を使用して識別される。具体的には、図１０Ｄを参照して、ノードポイント（すなわち、Ａ１とＡ２とＢ１）のそれぞれは、ノードポイント（すなわち、Ａ１とＡ２とＢ１）の値が、単位円上のノードポイントのそれぞれの位置を決定する単位円上の点と概念的に見てもよい。さらに、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ１＞もまた単位円上の点として概念的に見てもよい。コンシステントハッシュ法の原理を適用し、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ１＞によって定義された点で開始し、時計回りに移動し、遭遇した第１のノードポイントは、ターゲットサーバーを識別するために使用される。この例では、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ１＞は、Ａ１とＢ１との間に位置する。時計回り方向に移動すると、遭遇する第１のノードポイントはＢ１である。Ｂ１は、ストレージサーバーＢに関連付けられたノードポイントである。これにより、ストレージサーバーＢは、ターゲットサーバーとして識別される。
【００６９】
図１０Ｂを参照すると、クライアントＡはその後、ストレージサーバーＢに（ハッシュ＜オブジェクトＩＤ、オフセット１＞、データ）を特定する書き込みリクエストを送信する。ストレージサーバーＢはその後、データを格納する。ストレージサーバーＢがＯＬのコピーを含まないため、クライアントＡはまたストレージサーバーＢにＯＬのコピーを送信する。受信すると、ストレージサーバーＢはハッシュ＜ＶＩＤ、−１＞を使用して、ＯＬを格納する。
【００７０】
図１０Ｅを参照すると、いくらか後の時点で、ストレージサーバーＣはストレージプールに追加される。その結果、ＧＬは、新しいストレージサーバーの追加を反映するように更新される。更新されたＧＬはサーバーエントリＣを含む。サーバーエントリＣは、ストレージサーバーＣに対応し（図１０Ｆを参照。）、（ｉ）ストレージプール内のストレージサーバーＣを一意に特定するノードＩＤ  Ｃと、（ｉｉ）ノードポイントＣ１（図１０Ｇを参照。）と、（ｉｉｉ）ＧＬシーケンス番号が２に等しいときにサーバーエントリＣがＧＬに追加されたことを示すノードシーケンス番号Ｃ：２とを特定する。ＧＬもまた、ＧＬが更新されたことを示すために２に設定されたＧＬシーケンス番号と、ストレージプール内に３つのストレージサーバーが存在するとして３に設定されたノード数とを含む。
【００７１】
図１０Ｆを参照して、ＧＬが更新された後（図１０Ｅを参照。）、クライアントＡは、＜ＶＩＤ、オフセット２＞からデータを読み出すためのリクエストを受信する。前にクライアントに提供されたＶＩＤ（図１０Ｂを参照。）によって識別されるオブジェクトにＯＬが対応するため、ストレージプールからＯＬをリクエストする必要はない。
【００７２】
クライアントＡはＯＬ（図１０Ｃを参照。）とＧＬ（図１０Ｅを参照。）とハッシュ＜オブジェクトＩＤ、オフセットＩＤ２＞とを使用してターゲットサーバーを識別する。オフセットＩＤ２は、ＯＬから得られたストライプ幅にオフセット２をマスキングすることによって、生成される（図１０Ｃを参照。）。
【００７３】
前述したように、ＯＬは、ＯＬが作成された時点でグローバルネームスペース内でどのストレージサーバーが「書き込み可能」であったかを決定するために使用される。この例では、ＯＬシーケンス番号は１である。したがって、ＯＬが作成された時点で、グローバルネームスペースで書き込み可能であったストレージサーバーは、１以下のノードシーケンス番号を持つＧＬ内のサーバーエントリを持つことになる。図１０ＥのＧＬを参照して、サーバーエントリＡおよびサーバーエントリＢの両方が１に等しいノードシーケンス番号を持ち、このためＯＬが作成されたときにグローバルネームスペースで書き込み可能であった。ＧＬはサーバーエントリＣを含むが、ノードシーケンスＣが２であるため、スト
レージサーバーＣはＯＬが作成された時点で書き込み可能ではなく、このためターゲットサーバーを識別するために使用されない。ストレージサーバーＡおよびＢに対するノードポイント（すなわち、Ａ１、Ａ２、Ｂ１）は、対応するサーバーエントリから取得される。
【００７４】
ターゲットサーバーは、その後、ノードポイント（すなわち、Ａ１、Ａ２、Ｂ１）およびハッシュ＜オブジェクトＩＤ、オフセットＩＤ２＞を使用して識別される。具体的には、図１０Ｇを参照して、ノードポイント（すなわち、Ａ１、Ａ２、Ｂ１）のそれぞれは、概念的に単位円上の点として見てもよく、ノードポイント（すなわち、Ａ１、Ａ２、Ｂ１）の値は、単位円上のノードポイントのそれぞれの位置を決定する。また、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ２＞も概念的に単位円上の点として見てもよい。コンシステントハッシュ法の原理を適用し、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ２＞によって定義された点から始めて時計回りに移動し、遭遇した第１のノードポイントは、ターゲットサーバーを識別するために使用される。この例では、ハッシュ＜オブジェクトＩＤ、オフセットＩＤ２＞はＢ１とＡ２との間に位置する。時計回り方向に移動すると、遭遇する第１のノードポイントはＡ２である。Ａ２は、ストレージサーバーＡに関連するノードポイントである。そのため、ストレージサーバーＡは、ターゲットサーバーとして識別される。
【００７５】
図１０Ｆを参照して、クライアントＡは、その後＜オブジェクトＩＤ、オフセット２＞を特定する読み出しリクエストをストレージサーバーＡに送信する。ストレージサーバーＡはその後、リクエストされたデータを取得し、クライアントＡに送り返す。
【００７６】
図１０Ｈを参照して、ＧＬが更新された後（図１０Ｅを参照。）、クライアントＡは、＜ＶＩＤ２、オフセット３＞のデータを読み出すためのリクエストを受信する。クライアントＡは、ＶＩＤ２から（ストレージサーバーＢを特定する）ノードＩＤ  Ｂを抽出し（図１０Ｉを参照。）、続いてハッシュ＜ＶＩＤ２、−１＞を使用してストレージサーバーＢにＯＬ２のためのリクエストを送信する。リクエストに応じて、ストレージサーバーＢは、ＯＬ２を取得し、クライアントＡに送り返す。
【００７７】
クライアントＡはその後、ＯＬ２（図１０Ｊを参照。）とＧＬ（図１０Ｅを参照。）とハッシュ＜オブジェクトＩＤ２、オフセットＩＤ３＞とを使用してターゲットサーバーを識別するが、オフセットＩＤ３はＯＬ２から得られたストライプ幅でオフセット３をマスキングすることによって生成される（図１０Ｊ参照。）。
【００７８】
前述したように、ＯＬは、ＯＬが作成された時点でグローバルネームスペースでどのストレージサーバーが「書き込み可能」であったかを決定するために使用される。この例では、ＯＬシーケンス番号は２である（図１０Ｊを参照。）。したがって、ＯＬ２を作成した時点で、グローバルネームスペースで書き込み可能だったストレージサーバーは、２以下のノードシーケンス番号を持つＧＬ内のサーバーエントリを持つことになる。図１０ＥのＧＬを参照して、サーバーエントリＡとサーバーエントリＢとサーバーエントリＣのすべてが２以下のノードシーケンス番号を持ち、このためＯＬ２が作成されたときにグローバルネームスペースで書き込み可能であった。ストレージサーバーのそれぞれためのノードポイント（すなわち、Ａ１、Ａ２、Ｂ１、Ｃ１）は、対応するサーバーエントリから取得される。
【００７９】
ターゲットサーバーは、その後、ノードポイント（すなわち、Ａ１、Ａ２、Ｂ１、Ｃ１）およびハッシュ＜オブジェクトＩＤ２、オフセットＩＤ３＞を使用して識別される。具体的には、図１０Ｊを参照して、ノードポイント（すなわち、Ａ１、Ａ２、Ｂ１、Ｃ１）のそれぞれは、概念的に単位円上の点として見てもよく、ノードポイント（すなわち、Ａ
１、Ａ２、Ｂ１、Ｃ１）の値は、単位円上のノードポイントのそれぞれの位置を決定する。また、ハッシュ＜オブジェクトＩＤ２、オフセットＩＤ３＞もまた、概念的に単位円上の点として見てもよい。コンシステントハッシュ法の原理を適用し、ハッシュ＜オブジェクトＩＤ２、オフセットＩＤ３＞によって定義されたポイントから始めて時計回りに移動し、遭遇した第１のノードポイントは、ターゲットサーバーを識別するために使用される。この例では、ハッシュ＜オブジェクトＩＤ２、オフセットＩＤ３＞は、Ｂ１とＣ１との間に位置する。時計回り方向に移動すると、遭遇する第１のノードポイントはＣ１である。Ｃ１は、ストレージサーバーＣに関連付けられるノードポイントである。これにより、ストレージサーバーＣは、ターゲットサーバーとして識別される。
【００８０】
図１０Ｈを参照して、クライアントＡはその後、ストレージサーバーＣに（＜オブジェクトＩＤ２、オフセット３＞）を特定した読み出しリクエストを送信する。ストレージサーバーＣはその後、リクエストされたデータを取得し、クライアントＡに送り返す。
【００８１】
本発明は、限られた数の実施形態に関して説明してきたが、この開示の利益を有する当業者は、本明細書に開示されるような本発明の範囲から逸脱しない他の実施形態を考案してもよいことを理解するであろう。したがって、本発明の範囲は添付の特許請求の範囲によってのみ限定されるべきである。
【図１】
0006302951.tif 000002
【図２Ａ】
0006302951.tif 000003
【図２Ｂ】
0006302951.tif 000004
【図２Ｃ】
0006302951.tif 000005
【図３】
0006302951.tif 000006
【図４】
0006302951.tif 000007
【図５】
0006302951.tif 000008
【図６】
0006302951.tif 000009
【図７】
0006302951.tif 000010
【図８】
0006302951.tif 000011
【図９】
0006302951.tif 000012
【図１０Ａ】
0006302951.tif 000013
【図１０Ｂ】
0006302951.tif 000014
【図１０Ｃ】
0006302951.tif 000015
【図１０Ｄ】
0006302951.tif 000016
【図１０Ｅ】
0006302951.tif 000017
【図１０Ｆ】
0006302951.tif 000018
【図１０Ｇ】
0006302951.tif 000019
【図１０Ｈ】
0006302951.tif 000020
【図１０Ｉ】
0006302951.tif 000021
【図１０Ｊ】
0006302951.tif 000022