(57)【要約】【課題】冗長データストレージシステムを再構成する方法を提供する。【解決手段】複数のデータセグメントが第１のグループのストレージデバイスによって冗長記憶され、第１のグループのストレージデバイスの少なくとも定足数はそれぞれ、各データセグメント又は冗長データの少なくとも一部を記憶する。第２のグループのストレージデバイスが形成され、この第２のグループは、第１のグループとは異なるメンバーシップを有する。一貫性を有するバージョンが第２のグループの少なくとも定足数によって記憶されていないデータセグメントが、複数のデータセグメントの中から特定される。この特定されたデータセグメント又は冗長データの少なくとも一部は、第２のグループのストレージデバイスの少なくとも１つに書き込まれ、それによって、第２のグループの少なくとも定足数は、特定されたデータセグメントの一貫性を有するバージョンを記憶する。【選択図】図１
2008516343.tif 000002
【特許請求の範囲】
【請求項１】
冗長データストレージシステム（１００）を再構成する方法であって、
第１のグループのストレージデバイス（１０２）によって複数のデータセグメントを冗長記憶することであって、該第１のグループのストレージデバイス（１０２）の少なくとも定足数（quorum）はそれぞれ、各データセグメント又は冗長データの少なくとも一部を記憶する、冗長記憶することと、
第２のグループのストレージデバイス（１０２）を形成することであって、該第２のグループは、前記第１のグループとは異なるメンバーシップを有する、形成することと、
前記複数のデータセグメントの中で、一貫性を有するバージョンが前記第２のグループの少なくとも定足数によって記憶されていないデータセグメントを特定することと、
前記特定されたデータセグメント又は冗長データの少なくとも一部を前記第２のグループの前記ストレージデバイス（１０２）の少なくとも１つに書き込むことであって、それによって、前記第２のグループの少なくとも定足数は、前記特定されたデータセグメントの一貫性を有するバージョンを記憶する、書き込むことと
を含む方法。
【請求項２】
前記特定されたデータセグメントはイレーシャ符号化（erasure coding）される
請求項１に記載の方法。
【請求項３】
前記特定されたデータセグメントは複製される
請求項１に記載の方法。
【請求項４】
前記特定することは、前記第２のグループの前記ストレージデバイス（１０２）に記憶されたタイムスタンプを調べることによって行われる
請求項１に記載の方法。
【請求項５】
前記セグメントに対する前の書き込みオペレーションの応答者集合（respondent set）が前記第２のグループの定足数でない場合に、前記特定することは、前記セグメントを特定することにより応答する前記第２のグループのストレージデバイス（１０２）へポーリングメッセージを送信することによって行われる
請求項１に記載の方法。
【請求項６】
前記第２のグループの前記ストレージデバイス（１０２）のすべてよりも少ないストレージデバイスが、前記書き込みの後に、前記特定されたデータセグメントの一貫性を有するバージョンを記憶する場合、前記第２のグループの前記デバイス（１０２）のすべてが一貫性を有するバージョンを記憶するまで、１つ又は複数の追加書き込みオペレーションを実行する
請求項１に記載の方法。
【請求項７】
前記第２のグループを前記形成することは、
前記ストレージデバイス（１０２）の特定の１つによって該ストレージデバイス（１０２）の候補グループを計算することと、
前記特定のストレージデバイス（１０２）から前記候補グループのメンバーへ、該候補グループを提案するためのメッセージを送信するとともに該候補グループを前記第２のグループとして容認する前記候補グループのメンバーからメッセージを受信することと
を含む
請求項１に記載の方法。
【請求項８】
前記第２のグループのメンバーではない１つ又は複数のウィットネスデバイス（witness device）（１０２）が、前記第２のグループを前記形成することに参加する
請求項１に記載の方法。
【請求項９】
前記第２のグループを前記形成することは、
前記ストレージデバイス（１０２）の特定の１つによって該ストレージデバイス（１０２）の候補グループを計算することと、
前記特定のストレージデバイス（１０２）から前記候補グループのメンバー及び前記１つ又は複数のウィットネスデバイス（１０２）へ、前記候補グループを提案するためのメッセージを送信するとともに該候補グループを前記第２のグループとして容認する前記候補グループのメンバー及び前記ウィットネスデバイス（１０２）の１つ又は複数からメッセージを受信することと
を含む
請求項８に記載の方法。
【請求項１０】
前記第２のグループは、前記第１のグループの少なくとも定足数を含む
請求項１に記載の方法。
【請求項１１】
前記第２のグループは、前記第１のグループのメンバーシップの変更に応じて形成される
請求項１に記載の方法。
【請求項１２】
冗長データストレージシステム（１００）を再構成する方法を実施するためのコンピュータコードを含むコンピュータ可読媒体であって、
前記方法は、
第１のグループのストレージデバイス（１０２）によって複数のデータセグメントを冗長記憶するステップであって、該第１のグループのストレージデバイス（１０２）の少なくとも定足数はそれぞれ、各データセグメント又は冗長データの少なくとも一部を記憶する、冗長記憶するステップと、
第２のグループのストレージデバイス（１０２）を形成するステップであって、該第２のグループは、前記第１のグループとは異なるメンバーシップを有する、形成するステップと、
前記複数のデータセグメントの中で、一貫性を有するバージョンが前記第２のグループの少なくとも定足数によって記憶されていないデータセグメントを特定するステップと、
前記特定されたデータセグメント又は冗長データの少なくとも一部を前記第２のグループの前記ストレージデバイス（１０２）の少なくとも１つに書き込むステップであって、それによって、前記第２のグループの少なくとも定足数は、前記特定されたデータセグメントの一貫性を有するバージョンを記憶する、書き込むステップと
を含む
コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、データストレージの分野に関し、より詳細には、フォールトトレラントなデータ複製に関する。
【背景技術】
【０００２】
［発明の背景］
企業クラスのデータストレージシステムは、主としてそれらストレージシステムの信頼性の要件が消費者クラスのストレージシステムとは異なっている。たとえば、企業クラスのストレージシステムに共通に望まれている機能は、ストレージシステムが、完全な惨事には達していないあらゆる状況において、データを喪失することも、データの供給を停止することもすべきでないことである。これらの要件を満たすために、このようなストレージシステムは一般に、カスタマイズされた、非常に信頼性のある、ホットスワップ可能なハードウェアコンポーネントから構築される。それらストレージシステムのソフトウェアは、オペレーティングシステムを含めて、一般に一から構築される。ハードウェアコンポーネントの設計及び構築は多くの時間と費用を要し、これは、比較的低い製造ボリュームと相まって、このようなストレージシステムの一般的に高い価格の主な要因となっている。このようなシステムのもう１つの不利な点は、単一のシステムのスケーラビリティに欠けるということである。顧客は通常、最小のディスクアレイ構成であっても、高い先行投資コストを支払うが、単一のシステムは、有限の容量及び性能しかサポートすることができない。顧客は、これらの限界を超えることができるが、その結果、システムの性能が劣ったり、複数のシステムを購入しなければならなかったりし、これらの双方とも管理コストを増加させる。
【０００３】
データ複製又はイレーシャ符号化の使用を通じて、既成ストレージシステムコンポーネント又は商品ストレージシステムコンポーネントのフォールトトレランスを増大させることが提案されている。しかしながら、この解決法には、冗長コンポーネントの調和したオペレーション及び複製データの同期が必要とされる。
【非特許文献１】ENGLERT B., SHVARTSMAN A.: 「Graceful Quorum Reconfiguration in a Robust Emulation of Shared Memory」 PROCEEDINGS 20TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, 2000年4月10日-2000年4月13日, XP002398990 Taipei, Taiwan
【非特許文献２】LYNCH N., SHVARTSMAN A.: 「RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks」 TECHNICAL REPORT MIT LABORATORY OF COMPUTER SCIENCE, 2002年8月16日, XP002398988 Cambridge, Massachusetts, USA
【非特許文献３】SAITO Y., FROLUND S., VEITCH A., MERCHANT A., SPENCE S.: 「FAB: Building Distributed Enterprise Disk Arrays from Commodity Components」 PROCEEDINGS OF THE 11TH INTERNATIONAL CONFERENCE ON ARCHITECTURAL SUPPORT FOR PROGRAMMING LANGUAGES AND OPERATING SYSTEMS, 2004年10月7日-2004年10月13日, XP002398989 Boston, Massachusetts, USA
【非特許文献４】FROLUND S., MERCHANT A., SAITO Y., SPENCE S., VEITCH A.: 「A Decentralized Algorithm for Erasure-Coded Virtual Disks」 INTERNATIONAL CONFERNCE ON DEPENDABLE SYSTEMS AND NETWORKS, 2004年6月26日-2004年7月1日 XP002398991 Florence, Italy
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、必要とされているものは、冗長デバイスが設けられるストレージ環境又はデータが複製されるストレージ環境の改善された技法である。本発明が対象とするものはこの目的である。
【課題を解決するための手段】
【０００５】
［発明の概要］
本発明は、冗長データストレージ再構成の技法を提供する。一実施の形態では、冗長データストレージシステムを再構成する方法が提供される。複数のデータセグメントが第１のグループのストレージデバイスによって冗長記憶される。第１のグループのストレージデバイスの少なくとも定足数はそれぞれ、各データセグメント又は冗長データの少なくとも一部を記憶する。第２のグループのストレージデバイスが形成される。この第２のグループは、第１のグループとは異なるメンバーシップを有する。一貫性を有するバージョンが第２のグループの少なくとも定足数によって記憶されていないデータセグメントが、複数のデータセグメントの中から特定される。この特定されたデータセグメント又は冗長データの少なくとも一部は、第２のグループのストレージデバイスの少なくとも１つに書き込まれる。それによって、第２のグループの少なくとも定足数は、特定されたデータセグメントの一貫性を有するバージョンを記憶する。
【０００６】
別の実施の形態では、データセグメントが、第１のグループのストレージデバイスによって冗長記憶される。第１のグループのストレージデバイスの少なくとも定足数はそれぞれ、データセグメント又は冗長データの少なくとも一部を記憶する。第２のグループのストレージデバイスが形成される。この第２のグループは、第１のグループとは異なるメンバーシップを有する。第２のグループの他のメンバーによって記憶されたデータと一貫性を有するデータセグメント又は冗長データの少なくとも一部を有しない、第２のグループの少なくとも１つのメンバーが特定される。データセグメント又は冗長データの少なくとも一部が、第２のグループのその少なくとも１つのメンバーに書き込まれる。
【０００７】
さらに別の実施の形態では、データセグメントが、第１のグループのストレージデバイスによって冗長記憶される。第１のグループのストレージデバイスの少なくとも定足数はそれぞれ、データセグメント又は冗長データの少なくとも一部を記憶する。第２のグループのストレージデバイスが形成される。この第２のグループは、第１のグループとは異なるメンバーシップを有する。第１のグループのストレージデバイスのあらゆる定足数が第２のグループの定足数であるとは限らない場合、データセグメント又は冗長データの少なくとも一部が、第２のグループのストレージデバイスの少なくとも１つに書き込まれる。それ以外の場合、すなわち、第１のグループのストレージデバイスのあらゆる定足数が第２のグループの定足数である場合、この書き込みは省略される。
【０００８】
データは、複製される場合もあるし、イレーシャ符号化される場合もある。したがって、冗長データは、複製データの場合もあるし、パリティデータの場合もある。コンピュータコードを含むコンピュータ可読媒体は、本明細書で開示した方法のいずれも実施することができる。本発明のこれらの実施の形態及び他の実施の形態は本明細書でさらに詳細に説明される。
【発明を実施するための最良の形態】
【０００９】
［好適な実施の形態の詳細な説明］
本発明は、冗長デバイスが設けられるストレージ環境又はデータが冗長に記憶されるストレージ環境の再構成を提供する。複数のストレージデバイスは、企業クラスのストレージシステムの信頼性及び性能を提供すると予想されるが、低コストで且つより良いスケーラビリティで提供すると予想される。各ストレージデバイスは、商品コンポーネントから構築することができる。ストレージデバイスのオペレーションは、非集中的な方法で調整することができる。
【００１０】
データは冗長に記憶されるが、ストレージデバイスを必要とするアプリケーションの観点からすれば、データの単一の高可用性コピーが提供される。ストレージデバイスを必要とするアプリケーションにほぼトランスペアレントな方法で、故障、及び故障後のデバイス廃棄やデバイス回復等の他の振る舞いに対応した技法が提供される。
【００１１】
図１は、本発明の一実施の形態による、複数のストレージデバイス１０２を含む一例示のストレージシステム１００を示している。ストレージデバイス１０２は、（たとえば、イーサネット（登録商標）上のリモートダイレクトメモリアクセス（ＲＤＭＡ）を使用して）ネットワーク等の通信媒体１０４を介して互いに通信する。１つ又は複数のクライアント１０６（たとえば、サーバ）は、読み出しオペレーション及び書き込みオペレーションを実行することにより、通信媒体１０８を介してストレージシステム１００にアクセスし、ストレージシステム１００に記憶されたデータにアクセスする。通信媒体１０８は、直接接続によって実施することもできるし、たとえば、イーサネット（登録商標）上のｉＳＣＳＩプロトコル、ファイバチャネルプロトコル、ＳＣＳＩプロトコル、又はシリアルアタッチドＳＣＳＩプロトコルを使用するネットワーク接続によって実施することもできる。通信媒体１０４及び１０８は別々のものとして示されているが、互いに結合又は接続することができる。クライアント１０６は、データを生成し且つ／又はデータへのアクセスを必要とするアプリケーションソフトウェア（たとえば、電子メールアプリケーション又はデータベースアプリケーション）を実行することができる。
【００１２】
図２は、本発明の一実施の形態による、図１のストレージシステム１００で使用される一例示のストレージデバイス１０２を示している。図２に示すように、ストレージデバイス１０２は、ネットワークインターフェース１１０、中央処理装置（ＣＰＵ）１１２、１つ又は複数のハードディスク等のマスストレージ１１４、及びメモリ１１６を含むことができる。メモリ１１６は、好ましくは、不揮発性（たとえば、ＮＶ−ＲＡＭ）である。インターフェース１１０は、ストレージデバイス１０２が、ストレージシステム１００の他のデバイス１０２、及び、サーバ１０６等のストレージシステム１００の外部のデバイスと通信することを可能にする。ＣＰＵ１１２は一般に、ストレージデバイス１０２のオペレーションを制御する。メモリ１１６は一般に、マスストレージ１１４に書き込まれるデータ及びマスストレージ１１４から読み出されたデータを一時的に記憶するためのキャッシュメモリとして動作する。また、メモリ１１６は、本明細書でより詳細に説明するように、データに関連付けられたタイムスタンプ及び他の情報を記憶することもできる。
【００１３】
好ましくは、各ストレージデバイス１０２は、コストを最小にするために既成ハードウェア又は商品ハードウェアから構成される。しかしながら、各ストレージデバイス１０２が他のものと同一である必要はない。たとえば、ストレージデバイス１０２は、まったく異なる部品から構成してもよく、性能及び／又はストレージ容量において異なってもよい。
【００１４】
フォールトトレランスを提供するために、データは、ストレージシステム内に冗長に記憶される。たとえば、ストレージシステム１００内においてデータを複製することができる。一実施の形態では、データは、固定サイズのセグメントに分割される。各データセグメントについて、システム１００の少なくとも２つの異なるストレージデバイス１０２が、データの複製を記憶するために指定される。ここで、指定される記憶デバイスの個数、したがって、複製の個数は、「Ｍ」として与えられる。書き込みオペレーションの場合、セグメントの新しい値が、指定されたデバイス１０２の過半数（たとえば、Ｍが２又は３の場合に少なくとも２つのデバイス１０２）に記憶される。読み出しオペレーションの場合、指定されたデバイスの過半数に記憶された値が発見されて返される。特定のデータセグメントを記憶するために指定されたデバイスのグループを、本明細書ではセグメントグループと呼ぶ。したがって、複製データの場合、信頼でき且つ検証可能な読み出し及び書き込みを確実にするために、セグメントグループのデバイスの過半数が、要求の処理に参加して要求の完了を成功させなければならない。複製データに関して、「定足数」という用語及び「過半数」という用語は、本明細書では同義的に使用される。また、複製データに関して、データ「セグメント」という用語及びデータ「ブロック」という用語も、本明細書では同義的に使用される。
【００１５】
データを冗長に記憶する別の例として、イレーシャ符号化に従ってデータを記憶することができる。たとえば、ｍ，ｎリードソロモンイレーシャ符号化を使用することができる。ここで、ｍ及びｎは、ｍ＜ｎとなるような、ともに正の整数である。この場合、データセグメントを、そのデータを記憶するために指定された一群のデバイス全体にわたってストライプされたブロックに分割することができる。イレーシャ符号化は、ｍ個のデータブロック及びｐ個のパリティブロックを一組のｎ個のストレージデバイス全体にわたって記憶する。ここで、ｎ＝ｍ＋ｐである。一組のｍ個のストレージデバイス全体にわたってストライプされた各一組のｍ個のデータブロックについて、一組のｐ個のパリティブロックが、一組のｐ個のストレージデバイスに記憶される。独立ストレージデバイスアレイのイレーシャ符号化技法は、定足数手法（quorum approach）を使用して、信頼でき且つ検証可能な読み出し及び書き込みが確実に行われるようにする。定足数手法は、要求を処理してその要求の完了を成功させる際に、ｎ個のデバイスの少なくとも定足数が参加することを必要とする。この定足数は、ｐが偶数である場合には少なくともｍ＋ｐ／２個のデバイスであり、ｐが奇数の場合には少なくともｍ＋（ｐ＋１）／２個である。この定足数の条件を満たすデータブロックから、任意のｍ個のデータブロック又はパリティブロックを使用して、ｍ個のデータブロックを再構築することができる。
【００１６】
指定されたストレージデバイス１０２の間の動作を調整するために、タイムスタンプが使用される。一実施の形態では、各ストレージデバイスにおける各データブロック又は各パリティブロックに関連付けられたタイムスタンプは、そのデータブロックが最後に更新された（すなわち、書き込まれた）時刻を示す。加えて、ブロックのそれぞれに対するあらゆる保留中の更新の記録が保持される。この記録は、保留中の書き込みオペレーションを示す、各データブロック又は各パリティブロックに関連付けられた別のタイムスタンプを含むことができる。書き込みオペレーションが開始されたが、まだ完了していない場合に、更新は保留中となる。したがって、各ストレージデバイスにおけるデータの各ブロックについて、２つのタイムスタンプを保持することができる。或るストレージデバイスによって記憶されたタイムスタンプは、そのストレージデバイスに一意である。
【００１７】
タイムスタンプを生成するために、各ストレージデバイス１０２は時計を含む。この時計は、システム１００におけるイベントの本来的な半順序を反映する論理時計とすることもできるし、各デバイスにおける「壁時計」の時刻を反映するリアルタイム時計とすることもできる。各タイムスタンプは好ましくは、各デバイス１０２に一意の関連した識別子も有し、その識別子を有しない場合に同一となるタイムスタンプを区別できるようにしている。たとえば、各タイムスタンプは、現在の時刻を示す８バイト値、及び、各デバイス１０２に一意の４バイト識別子を含むことができる。リアルタイム時計を使用する場合、これらの時計は好ましくは、ほぼ同じ時刻を有するように、ストレージデバイス１０２全体にわたって同期される。ただし、それらの時計は、正確に同期されている必要はない。時計の同期は、ストレージデバイス１０２が互いにメッセージを交換することによって行うこともできるし、（たとえば、サーバ１０６の１つ又は複数における）中央アプリケーションがデバイス１０２へメッセージを送信することによって行うこともできる。
【００１８】
詳細には、特定のデータブロックを記憶するように指定された各ストレージデバイス１０２は、本明細書では「ｖａｌ」として与えられる、データブロックの値を記憶する。また、データブロックについて、各ストレージデバイスは、「ｖａｌＴＳ」及び「ｏｒｄＴＳ」として与えられる２つのタイムスタンプも記憶する。タイムスタンプｖａｌＴＳは、そのデータ値がストレージデバイスにおいて最後に更新された時刻を示す。タイムスタンプｏｒｄＴｓは、最後の書き込みオペレーションが受信された時刻を示す。データへの書き込みオペレーションがストレージデバイスにおいて開始されたが完了していない場合、そのデータのタイムスタンプｏｒｄＴＳは、タイムスタンプｖａｌＴＳよりも近時の時刻となる。開始されて完了している場合、すなわち、このような保留中の書き込みオペレーションが存在しない場合、タイムスタンプｖａｌＴＳは、タイムスタンプｏｒｄＴＳ以上となる。
【００１９】
一実施の形態では、どのデバイスも、アプリケーションから読み出し要求又は書き込み要求を受信することができ、その要求にサービスを提供するためのコーディネータとして動作することができる。書き込みオペレーションは、複製データ用及びイレーシャ符号化データ用の２つのフェーズで実行される。第１のフェーズでは、セグメントグループのデバイスの定足数が、そのセグメントに対する新しい進行中の更新を示すように自身のｏｒｄＴＳタイムスタンプを更新する。第２のフェーズでは、セグメントグループのデバイスの定足数が、自身のデータ値ｖａｌ及び自身のｖａｌＴＳタイムスタンプを更新する。イレーシャ符号化データの書き込みオペレーションの場合、セグメントグループのデバイスの定足数が自身の新しい値を記憶したという確認がオプションの第３のフェーズで受信されるまで、セグメントグループのデバイスは、古い値を上書きすることなく、自身のデータブロック又はパリティブロックの更新された値のログ記録も行うことができる。
【００２０】
読み出し要求は、セグメントグループのデバイスの定足数が自身のタイムスタンプｖａｌＴｓ及びｏｒｄＴｓ並びに値ｖａｌをコーディネータに返す１つのフェーズで実行することができる。この要求は、デバイスの定足数によって返されるタイムスタンプｏｒｄＴｓ及びｖａｌＴｓがすべて同一である場合に成功する。同一でない場合、不完全な過去の書き込みが読み出しオペレーション中に検出されて、回復オペレーションが実行される。複製データの回復オペレーションの一実施の形態では、セグメントグループの定足数の中で最も近時のタイムスタンプを有するデータ値ｖａｌが発見され、セグメントグループのデバイスの少なくとも過半数に記憶される。イレーシャ符号化データの回復オペレーションの一実施の形態では、セグメントグループのログが調べられて、十分なデータがセグメントを完全に再構築するのに利用可能である最も近時のセグメントが見つけられる。このセグメントは、次に、セグメントグループの少なくとも定足数に書き込まれる。
【００２１】
複製データに使用できる読み出しオペレーション、書き込みオペレーション、及び回復オペレーションは、２００３年５月１６日に出願された「Read, Write and Recovery Operations for Replicated Data」という発明の名称の米国特許出願第１０／４４０，５４８号（この米国特許出願の全内容は、参照によって本明細書に援用される）に記載されている。イレーシャ符号化データに使用できる読み出しオペレーション、書き込みオペレーション、及び回復オペレーションは、２００３年１０月２３日に出願された「Methods of Reading and Writing Data」という発明の名称の米国特許出願第１０／６９３，７５８号（この米国特許出願の全内容は、参照によって本明細書に援用される）に記載されている。
【００２２】
ストレージデバイス１０２が故障した場合、故障後に回復した場合、廃棄された場合、システム１００に追加された場合、ネットワークの故障のためにアクセス不能である場合、又は、ストレージデバイス１０２が永続的なホットスポットに遭遇していると判断された場合、これらの状態は、影響を受けたストレージデバイス１０２がメンバーであるいずれかのセグメントグループに対して変更の必要があることを示している。本発明の一実施の形態によれば、このようなセグメントグループは、異なる定足数要件を有するように再構成される。したがって、上述した読み出しオペレーション、書き込みオペレーション、及び回復オペレーションによって、故障又は低速ストレージデバイスのマスキングが可能になる一方、セグメントグループのメンバーシップに対する変更及び付随した再構成によって、システムは、定足数要件が固定されたままである場合において通常起こり得るよりも多くの個数の故障に持ちこたえることが可能になる。
【００２３】
図３は、本発明の一実施の形態による、データストレージシステムを再構成するための方法３００の一例示のフロー図を示している。方法３００は、グループのメンバーシップの変更を反映するようにセグメントグループを再構成し、データが変更後のグループによって一貫性をもって確実に記憶されるようにする。これによって、セグメントグループによるデータトランザクションを実行するための定足数要件を、新しいグループメンバーシップに基づき変更することが可能になる。たとえば、複製データのセグメントグループが５つのメンバーを有する一実施の形態を考えると、この場合、デバイス１０２の少なくとも３つが、読み出しオペレーション及び書き込みオペレーションを実行するための過半数を形成するのに必要とされる。一方、システムが、３のグループメンバーシップについて適切に再構成されている場合、デバイス１０２の２つのみが、読み出しオペレーション及び書き込みオペレーションを実行するための過半数を形成するのに必要とされる。したがって、セグメントグループを再構成することによって、システムは、再構成のない場合よりも多くの故障に耐えることができる。
【００２４】
変更後のグループによって記憶されるデータの一貫性は、新しいグループが、グループメンバーシップ変更後に受信された読み出し要求及び書き込み要求に確実且つ検証可能にサービスを提供するのに必要とされる。複製データは、異なるストレージデバイスにより記憶されたバージョンが同一である場合に一貫性を有する。複製データは、更新がデータの或るバージョンには行われたが別のバージョンには行われず、その結果、それらのバージョンがもはや同一でない場合に一貫性を有しない。イレーシャ符号化データは、データブロック又はパリティブロックがセグメントの同じバージョンから導出されている場合に一貫性を有する。イレーシャ符号化データは、或るセグメントの或るデータブロック又はパリティ情報に対して更新が行われたが、同じセグメントの別のデータブロック又はパリティ情報に対して対応する更新が行われていない場合に一貫性を有しない。本明細書でより詳細に説明するように、データセグメントの冗長記憶されたバージョンの一貫性は、そのデータセグメントを記憶するために割り当てられたストレージデバイスで行われたデータセグメントに対する更新に関連付けられたタイムスタンプを調べることによって判断することができる。
【００２５】
セグメントグループのメンバーシップの変更を、本明細書では、「前」のグループメンバーシップ又は「第１」のグループメンバーシップから「新しい」グループメンバーシップ又は「第２」のグループメンバーシップになると呼ぶ。方法３００は、図１のシステム１００等の冗長データストレージシステムによって実行され、セグメントグループごとに独立に実行することができる。
【００２６】
ステップ３０２において、冗長データは前のグループによって記憶される。このグループのストレージデバイスの少なくとも定足数はそれぞれ、データセグメント又は冗長データの少なくとも一部を記憶する。たとえば、複製データの場合には、これは、このグループのストレージデバイスの少なくとも過半数が、データの複製（すなわち、データ又はそのデータの冗長コピー）を記憶することを意味し、イレーシャ符号化データの場合には、このグループのストレージデバイスの少なくとも定足数がそれぞれ、データブロック又は冗長パリティデータを記憶することを意味する。
【００２７】
ステップ３０４において、新しいグループが形成される。新しいセグメントグループメンバーシップは、通常、特定の「前」のグループのメンバーシップの変更が行われた時に形成される。たとえば、システムアドミニストレータは、ストレージデバイスが故障しており、回復の見込みがないものと判断することもできるし、新しいストレージデバイスが追加されると判断することもできる。別の例として、グループの特定のストレージデバイスは、グループの別のストレージデバイスが、或る期間の間、その特定のストレージデバイスが送信したメッセージに引き続き応答しない時に、そのグループの別のストレージデバイスの故障を検出することができる。さらに別の例として、グループの特定のストレージデバイスは、グループの以前故障したデバイスからメッセージを受信した時に、この以前故障したデバイスの回復を検出することができる。
【００２８】
セグメントグループのストレージデバイスの特定の１つが、ステップ３０４において、新しいグループの形成を開始することができる。このデバイスは、システムアドミニストレータによって指定される場合もあるし、前のグループのメンバーシップの変更を検出している場合もある。
【００２９】
図４は、本発明の一実施の形態による、ストレージデバイスの新しいグループを形成するための方法４００の一例示のフロー図を示している。ステップ４０２において、開始デバイスが、新しいグループの見込みメンバーへブロードキャストメッセージを送信する。各セグメントグループは、一意のセグメントグループ識別情報によって特定することができる。各データセグメントについて、複数のデバイスがセグメントグループの見込みメンバーとして機能する。ただし、どの時点においても、セグメントグループのメンバーは見込みメンバーのサブセットを含むことができる。各ストレージデバイスは、好ましくは、自身が潜在的にどのセグメントグループのメンバーとなる可能性があるかの記録、及び、見込みメンバーである他のデバイスの識別情報の記録を記憶する。ステップ３０２において送信されたブロードキャストメッセージは、好ましくは、セグメントグループの識別情報を使用して特定のセグメントグループを特定し、セグメントグループのすべての見込みメンバーへ送信される。
【００３０】
ブロードキャストメッセージを受信し且つ動作可能な見込みメンバーは、開始デバイスへ返答メッセージを送信する。開始デバイスは、ブロードキャストメッセージが送信されたデバイスの一部又は全部から返答を受信することができる。
【００３１】
ステップ４０４において、開始デバイスは、自身のブロードキャストメッセージに対する返答に基づいて候補グループを提案する。ステップ４０４で提案された候補グループは、好ましくは、開始デバイスが受信した応答の送信元のデバイスのすべてを含む。デバイスのすべてがブロードキャストメッセージを受信して返答した場合、候補グループは、好ましくは、それらデバイスのすべてを含む。一方、デバイスの一部しか所定の期間内に応答しない場合、候補グループはそれらのデバイスしか含まない。或いは、応答しているデバイスのすべてを候補グループに含めるのではなく、応答しているデバイスのすべてよりも少ないデバイスを候補グループ用に選択することができる。これは、データを安全且つセキュアに記憶するのに必要とされるものよりも多くの見込みグループメンバーが存在する場合に好都合な場合がある。開始デバイスは、候補グループのメンバーシップを特定するメッセージを候補グループのメンバーのすべてへ送信することによって候補グループを提案する。
【００３２】
候補グループを提案するメッセージを受信する各デバイスは、候補グループを容認する前に、候補グループが、前のグループの少なくとも定足数を含むかどうかを判断する。加えて、各ストレージデバイスは、好ましくは、提案された候補グループが追加される不明瞭候補グループのリストを保持する。不明瞭候補グループとは、提案されたが、容認されていない候補グループである。また、各デバイスは、候補グループを容認する前に、候補グループが、あらゆる前の不明瞭候補グループの少なくとも過半数を含むかどうかも判断する。したがって、候補グループが、前のグループの少なくとも定足数を含み、且つ、あらゆる前の不明瞭候補グループの少なくとも過半数を含む場合、その候補グループは容認される。前の不明瞭候補グループのこの追跡は、ストレージデバイスの互いに素な２つのグループが、単一のデータセグメントを記憶するように割り当てられることを防止するのに役立つ。候補グループを容認する各デバイスは、そのデバイスがその候補グループを容認することを開始デバイスへ応答する。
【００３３】
ステップ４０６において、開始デバイスは、容認された候補グループの各メンバーから応答を一旦受信すると、各メンバーデバイスへメッセージを送信して、候補グループが容認され、したがって、特定のデータセグメントの新しいグループであることを各メンバーデバイスに通知する。これに応答して、各メンバーは、そのデータセグメントについての不明瞭候補グループの自身のリストを消去又は廃棄することができる。候補グループのメンバーのすべてが候補グループを容認して応答するとは限らない場合、開始デバイスは、この方法を再開して、ステップ４０２又はステップ４０４で再度開始することができる。開始デバイスが、方法４００の実行中に故障した場合、別のデバイスがこの故障を検出して、この方法を再開する。
【００３４】
方法４００の結果として、新しいグループの各デバイスは、その新しいグループのメンバーシップについて同意しており、そのメンバーシップを記録している。この時点で、デバイスは、前のグループのメンバーシップの記録もまだ有する。したがって、各ストレージデバイスは、自身がアクティブなメンバーであるセグメントグループのリストを保持する。
【００３５】
本発明の一実施の形態によれば、方法４００の期間中に１つ又は複数のウィットネスデバイスを利用することができる。好ましくは、各セグメントグループに１つのウィットネスデバイスが割り当てられる。ただし、追加のウィットネスデバイスを割り当てることもできる。各ウィットネスデバイスは、方法４００のメッセージ交換に参加するが、データセグメントのどの部分も記憶しない。したがって、ウィットネスデバイスは、ステップ４０２においてブロードキャストメッセージを受信し、応答する。加えて、ウィットネスデバイスは、ステップ４０４において、提案された候補グループメンバーシップを受信し、この候補メンバーシップを容認するかどうかを判断する。また、ウィットネスデバイスは、候補グループメンバーシップを容認するかどうかを判断するために、前の不明瞭候補グループメンバーシップのリストも保持する。方法４００に参加するデバイスの個数を増加させることによって、メンバーシップ選択の信頼性が増加する。ウィットネスデバイスを含めることは、方法に参加する他のデバイスが少数の場合に最も有益である。特に、前のセグメントメンバーシップが２つのメンバーしか有さず、そのセグメントグループが１つのメンバーしか有しない新しいグループメンバーシップに移行する場合、たとえ１つのデバイスが前のグループメンバーシップの２つのデバイスの過半数でなくても、１つ又は複数のウィットネスデバイスが同点決選票を投じて、１つのデバイスの候補グループメンバーシップを作成することを可能にすることができる。
【００３６】
ストレージデバイスの新しいグループメンバーシップがセグメントグループについて一旦形成されると、新しいメンバーシップグループの定足数と接触することのみによって今後の要求が完了できるように、前のメンバーシップグループを除去する試みが行われる。しかしながら、前のグループを除去できるようになる前に、セグメントグループを同期させる必要がある。同期には、新しいグループに対して、セグメントの一貫性を有するバージョンを、読み出しアクセス及び書き込みアクセスに利用可能にすることが必要とされる。たとえば、ストレージデバイス１０２の前のグループメンバーシップが５つのメンバー、Ａ、Ｂ、Ｃ、Ｄ、及びＥを有し、Ａ、Ｂ、及びＣが複製データの一貫性を有するバージョンを有する過半数を形成する一実施の形態を考える（Ｄ及びＥは、最も近時の書き込みオペレーションを見逃し、したがって、それらのデータは旧いものとなっている）。デバイスＣ、Ｄ、及びＥのみを含む新しいグループメンバーシップが次に形成されるものと仮定する。この場合、新しいグループの少なくとも過半数は、データの一貫性を有するバージョンを記憶する必要がある。ただし、好ましくは、新しいグループのすべてがデータの一貫性を有するバージョンを記憶する。したがって、Ｄ及びＥの少なくとも一方、好ましくは双方を、データの最も近時のバージョンで更新して、新しいグループの少なくとも過半数がデータの一貫性を有するバージョンを確実に記憶するようにする必要がある。
【００３７】
したがって、図３を参照して、新しいグループメンバーシップがステップ３０４で形成された後、冗長データの一貫性はステップ３０６において確実にされる。これは、本明細書ではデータ同期と呼ばれ、新しいグループの少なくとも過半数（冗長データの場合）又は新しいグループの定足数（イレーシャ符号化データの場合）が冗長データを一貫性をもって確実に記憶するようにすることによって達成される。
【００３８】
図５は、ストレージデバイスの少なくとも過半数が複製データを一貫性をもって確実に記憶するようにするための方法５００の一例示のフロー図を示している。ステップ５０２において、特定のデバイスが、前のグループの各デバイスへメッセージを送信する。ポーリングメッセージを送信するこの特定のデバイスは、同期プロセスのコーディネータであり、好ましくは、図３のステップ３０４において新しいグループメンバーシップの形成を開始したのと同じデバイスである。
【００３９】
ポーリングメッセージは、特定のデータブロックを特定し、メッセージを受信した各デバイスに、そのデータの自身の現在の値ｖａｌを、及び、関連付けられた自身の２つのタイムスタンプｖａｌＴＳ及びｏｒｄＴＳを返すように指示する。上述したように、ｖａｌＴＳタイムスタンプは、データの最も近時の更新バージョンを特定し、ｏｒｄＴＳタイムスタンプは、データに対して開始されたが完了していないあらゆる書き込みオペレーションを特定する。ｏｒｄＴＳタイムスタンプは、保留中の未完了の書き込みオペレーションが再構成時に存在した場合に、最も近時のｏｒｄＴＳタイムスタンプを新しいグループに戻すことに後に使用するために収集される。そうでない場合、すなわち、保留中の書き込みオペレーションが存在しない場合には、過半数の最も近時のｏｒｄＴＳタイムスタンプは、最も近時のｖａｌＴＳタイムスタンプと同じとなる。
【００４０】
ステップ５０４において、コーディネータは、前のグループメンバーシップのデバイスの少なくとも過半数から返答を受信するまで待機する。ステップ５０６において、データの最も近時に更新されたバージョンが返答の中から選択される。データの最も近時に更新されたバージョンは、タイムスタンプによって特定され、特に、ｖａｌＴＳの最も高い値を有することによって特定される。前のグループのデバイスの過半数がステップ５０４において応答するのを待機することによって、この方法は、データの選択されたバージョンが最も近時の成功した書き込みオペレーションのバージョンであることを確実にする。
【００４１】
ステップ５０８において、コーディネータは、新しいグループメンバーシップのストレージデバイスへ書き込みメッセージを送信する。この書き込みメッセージは、特定のデータブロックを特定し、そのブロックの最も近時の値、並びに、前のグループから得られた、そのブロックの最も近時のｖａｌＴＳ及びｏｒｄＴＳタイムスタンプを含む。書き込みメッセージは、新しいグループの各ストレージデバイスへ送信することができる。ただし、好ましくは、書き込みメッセージは、データの最も近時のバージョンをすでに有すると判断された、新しいグループのストレージデバイスへは送信されない。これは、ステップ５０４で受信された返答から判断することができる。また、一定の状況では、新しいグループのストレージデバイスのすべて又は少なくとも定足数は、データの一貫性のあるバージョンをすでに有している場合がある。したがって、ステップ５０８において、書き込みメッセージは送信する必要はない。たとえば、前のグループのあらゆるデバイスがデータの最も近時のバージョンを記憶し、新しいグループが前のグループのサブセットである場合、書き込みメッセージを新しいグループへ送信する必要はない。
【００４２】
この書き込みメッセージに応答して、メッセージを受信する各デバイスは、書き込みメッセージで受信したタイムスタンプｏｒｄＴＳを、データブロックのタイムスタンプｏｒｄＴＳの自身の現在の値と比較する。書き込みメッセージで受信したｏｒｄＴＳタイムスタンプがデータブロックのタイムスタンプｏｒｄＴＳの現在の値よりも近時である場合、デバイスは、タイムスタンプｏｒｄＴＳの自身の現在の値を、書き込みメッセージで受信したタイムスタンプｏｒｄＴＳの値と取り替える。そうでない場合、デバイスは、ｏｒｄＴＳタイムスタンプの自身の現在の値を維持する。
【００４３】
また、メッセージを受信する各デバイスは、書き込みメッセージで受信したタイムスタンプｖａｌＴＳを、データブロックのタイムスタンプｖａｌＴＳの自身の現在の値と比較する。書き込みメッセージで受信したタイムスタンプｖａｌＴＳが、データブロックのタイムスタンプｖａｌＴＳの現在の値よりも近時である場合、デバイスは、タイムスタンプｖａｌＴＳの自身の現在の値を、書き込みメッセージで受信したタイムスタンプｖａｌＴＳの値と取り替え、また、データブロックの自身の現在の値も、書き込みメッセージで受信したデータブロックの値と取り替える。そうでない場合、デバイスは、タイムスタンプｖａｌＴＳ及びデータブロックの自身の現在の値を維持する。デバイスは、データブロックのどのバージョンも前に記憶していなかった場合に、書き込みメッセージで受信した、ブロックの最も近時のタイムスタンプｖａｌＴＳ及びｏｒｄＴＳと共に、ブロックの最も近時の値を単に記憶する。
【００４４】
ステップ５１０において、コーディネータは、新しいグループメンバーシップのストレージデバイスの少なくとも過半数が書き込みメッセージに対する応答に成功していること、ないしは、データの一貫性を有するバージョンをすでに有すると判断されていることを、それら少なくとも過半数が返答するまで待機する。この状態は、同期プロセスが成功したことを示し、したがって、新しいグループは、現在、データブロックに対する読み出し要求及び書き込み要求に応答する準備ができていることを示している。イニシエータは、次に、前のグループのメンバーへメッセージを送信し、それらメンバーが前のグループメンバーシップを当該メンバーのメンバーシップ記録から除去できること、ないしは、前のグループを非アクティブ化できることをそれらメンバーに通知することができる。過半数がステップ５１０においてデータの一貫性を有するバージョンを有しない場合、これは、同期プロセスの失敗を示し、この場合、方法５００を再度試みることができ、又は、異なる新しいグループメンバーシップを形成する必要があることを示す場合もあり、この場合、方法３００を再度実行することができる。別の実施の形態では、デバイスのすべてが、データの一貫性を有するバージョンをすでに有すると判断された場合にのみ、同期は成功したとみなすことができる。
【００４５】
図６は、ストレージデバイスの少なくとも定足数がイレーシャ符号化データを一貫性をもって確実に記憶するようにするための方法６００の一例示のフロー図を示している。イレーシャ符号化データの場合、セグメントグループのデバイスは、それぞれ、特定のデータセグメントに属する特定のデータブロック又はそのセグメントの冗長パリティブロックを記憶する。ステップ６０２において、特定のデバイスが、前のグループの各デバイスへポーリングメッセージを送信する。ポーリングメッセージを送信する特定のデバイスは、同期プロセスのコーディネータであり、好ましくは、図３のステップ３０４において新しいグループメンバーシップの形成を開始したのと同じデバイスである。
【００４６】
ポーリングメッセージは、特定のデータセグメント又はデータブロックを特定し、メッセージを受信する各デバイスに、データ（データブロックの場合もあるし、パリティの場合もある）の自身の現在の値ｖａｌ並びに関連付けられた自身の２つのタイムスタンプｖａｌＴＳ及びｏｒｄＴＳを返すように指示する。冗長記憶されたデータの場合と同様に、ｏｒｄＴＳタイムスタンプは、保留中の未完了の書き込みオペレーションが再構成時に存在した場合に、最も近時のｏｒｄＴＳタイムスタンプを新しいグループへ戻すことに後に使用するために収集される。
【００４７】
ステップ６０４において、コーディネータは、前のグループメンバーシップのデバイスの少なくとも定足数から返答を受信するまで待機する。ステップ６０６において、デバイスの定足数が同じ最も近時のｖａｌＴＳタイムスタンプを報告するものと仮定すると、コーディネータは、受信したデータ値を復号して、データセグメントに属するあらゆるデータブロック又はパリティブロックの値を求めるが、この値を更新する必要はない。前のグループ及び新しいグループが同じ個数のメンバーを有する場合、これは、一般に、グループに追加されたあらゆるデバイスに適切なデータを記憶することを伴う。前のグループ及び新しいグループが異なる個数のメンバーを有する場合、これは、イレーシャ符号化を再計算すること、及び、場合によってはデータボリューム全体を再構成することを含む場合がある。たとえば、データセグメントが、異なる個数のデータブロックに分割される場合もあるし、異なる個数のパリティブロックが使用される場合もある。
【００４８】
ステップ６０８において、コーディネータは、新しいグループメンバーシップのストレージデバイスへ書き込みメッセージを送信する。新しいグループの各デバイスは、新しいグループの他のデバイスにより記憶されたものとは異なる値ｖａｌを有するデータブロック又はパリティを記憶するので、ステップ６０８で送信されたどの書き込みメッセージも、新しいグループのデバイスに特有のものであり、そのデバイスに割り当てられたデータブロック値又はパリティ値を含む。また、書き込みメッセージは、前のグループから得られた、セグメントの最も近時のｖａｌＴＳタイムスタンプ及びｏｒｄＴＳタイムスタンプも含む。適切な書き込みメッセージを新しいグループの各ストレージデバイスへ送信することができる。ただし、好ましくは、書き込みメッセージは、新しいグループのストレージデバイスであって、当該ストレージデバイスのデータブロック又はパリティの最も近時のバージョンをすでに有すると判断されたストレージデバイスへは送信されない。これは、ステップ６０４で受信された返答から判断することができる。一定の状況では、前のグループのストレージデバイスのすべて又は少なくとも定足数が、データの一貫性を有するバージョンをすでに有する場合がある。この場合、ステップ６０８において書き込みメッセージを送信する必要はない。
【００４９】
この書き込みメッセージに応答して、メッセージを受信する各デバイスは、書き込みメッセージで受信したタイムスタンプｏｒｄＴＳを、データブロック又はパリティのタイムスタンプｏｒｄＴＳの自身の現在の値と比較する。書き込みメッセージで受信したｏｒｄＴＳタイムスタンプが、データのタイムスタンプｏｒｄＴＳの現在の値よりも近時である場合、デバイスは、タイムスタンプｏｒｄＴＳの自身の現在の値を、書き込みメッセージで受信したタイムスタンプｏｒｄＴＳの値と取り替える。そうでない場合、デバイスは、ｏｒｄＴＳタイムスタンプの自身の現在の値を維持する。
【００５０】
また、メッセージを受信する各デバイスは、書き込みメッセージで受信したタイムスタンプｖａｌＴＳを、データブロック又はパリティのタイムスタンプｖａｌＴＳの自身の現在の値と比較する。ｖａｌＴＳタイムスタンプが、デバイスによって保持されているログに存在しない場合、デバイスは、自身のログに、書き込みメッセージで受信したタイムスタンプｖａｌＴＳ及びデータブロック又はパリティの値を追加する。存在する場合、デバイスは、ログの自身の現在の内容を維持する。デバイスは、データブロック又はパリティのどのバージョンも前に記憶していなかった場合に、書き込みメッセージで受信した最も近時のタイムスタンプｖａｌＴＳ及びｏｒｄＴＳと共に、ブロックの最も近時の値を単に記憶する。
【００５１】
ステップ６１０において、コーディネータは、新しいグループメンバーシップのストレージデバイスの定足数が書き込みメッセージに対する応答に成功していること、ないしは、適切なデータブロック又はパリティの一貫性を有するバージョンをすでに有すると判断されていることをそれらストレージデバイスの定足数が応答するまで待機する。この状態は、同期プロセスが成功したことを示し、したがって、新しいグループが、現在、データセグメントへの読み出し要求及び書き込み要求に対して応答する準備ができていることを示している。イニシエータは、次に、前のグループメンバーシップのメンバーへメッセージを送信して、それらメンバーが自身のメンバーシップ記録から前のグループを除去できる、ないしは、前のグループを非アクティブ化できることをそれらメンバーに通知することができる。定足数が、ステップ６１０においてセグメントの一貫性を有するバージョンを有しない場合、これは同期プロセスの失敗を示し、この場合、方法６００を再度試みることができ、又は、異なる新しいグループメンバーシップを形成する必要があることを示す場合もあり、この場合、方法３００を再度実行することができる。別の実施の形態では、デバイスのすべてが、データの一貫性を有するバージョンをすでに有すると判断された場合にのみ、同期は成功したとみなすことができる。
【００５２】
同期方法５００又は６００が実行されている間で、且つ、グループが非アクティブ化されるまで、前のグループ及び新しいグループの双方が、データの特定のセグメントを記憶するように指定される。したがって、その間に実行されたあらゆる読み出しオペレーション又は書き込みオペレーションは、前のグループの定足数及び新しいグループの定足数を用いて実行する必要がある。
【００５３】
同期用のコーディネータとして動作しているデバイスが、同期プロセス中に故障に遭遇した場合、別のデバイスがそのプロセスを再開することができる。しかしながら、すでに同期されているブロックは、好ましくは、再び同期されない。
【００５４】
方法５００及び６００は、データの単一のセグメントには十分である。しかしながら、セグメントグループは、複数のデータセグメントを記憶する場合がある。したがって、メンバーシップに対する変更は、複数のデータセグメントの同期を必要とする場合がある。したがって、方法５００又は６００は、前のグループによって記憶されたデータのセグメントごとに実行される場合がある。
【００５５】
上述したように、各ストレージデバイスは、自身が記憶する各データブロックについてタイムスタンプを記憶する。これらのタイムスタンプは、各デバイスのテーブルに記憶することができる。このテーブルには、データのセグメントグループ識別情報も記憶される。したがって、新しいグループメンバーシップのデータ同期を開始するデバイスは、そのデバイス自身のタイムスタンプテーブルをチェックして、特定のセグメントグループ識別情報に関連付けられたデータブロック又はデータセグメントのすべてを特定することができる。次に、各データブロック又は各データセグメントについて、方法５００又は６００を実行することができる。
【００５６】
しかしながら、いくつかの状況では、グループメンバーシップの変更の結果として、セグメントグループに割り当てられたデータセグメントのすべてを更新する必要があるとは限らない。たとえば、方法５００又は６００を実行する前に、特定のデータセグメントの一貫性を有するバージョンが、そのセグメントのデバイスグループのすべてによってすでに記憶されている場合がある。したがって、このようなデータセグメントを不必要に更新しなければならないことを回避するために、それらデータセグメントを特定することができる。これは、たとえば、ステップ５０８又は６０８のように、一貫性を有するバージョンが定足数によって記憶されてないデータセグメントを特定することによって行うことができる。ステップ５０８及び６０８に関して上述したように、このようなセグメントについて書き込みメッセージを送信する必要はない。
【００５７】
一実施の形態では、タイムスタンプテーブルのサイズを制限するために、ストレージデバイスに割り当てられたデータの一部のみのタイムスタンプが、デバイスのタイムスタンプテーブルに記憶される。読み出しオペレーション、書き込みオペレーション、及び修復オペレーションについて、タイムスタンプは、データへの同時更新を不明瞭にしないために使用され、故障を検出してその故障の結果を修復するために使用される。したがって、データのブロック又はパリティを保持する各デバイスが更新の確認応答をした後（すなわち、ｖａｌＴＳ＝ｏｒｄＴＳの場合）、タイムスタンプは廃棄することができる。セグメントグループのデバイスは、そのセグメントグループの他のメンバーのすべてが、自身のデータの更新に成功した後、データブロック又はパリティのタイムスタンプを廃棄することができる。この場合、各ストレージデバイスは、アクティブに更新が行われているデータブロックのタイムスタンプのみを保持する。
【００５８】
この実施の形態では、新しいグループメンバーシップのデータ同期プロセスのイニシエータは、特定のセグメントグループ識別情報を含むポーリングメッセージを前のグループのメンバーへ送信することができる。このポーリングメッセージを受信する各ストレージデバイスは、自身のタイムスタンプテーブルに含まれる、セグメントグループ識別情報に関連付けられたデータブロックのすべてを特定することによって応答する。これらは、現在更新を受けているブロック又は前に行われた更新が失敗したブロックである。これらのブロックは、ポーリングメッセージを受信する各デバイスがブロック番号のリストをイニシエータへ送信することによって特定することができる。イニシエータは、次に、返答で受信されたブロックのすべての和集合を取ることによって、同期されるデータブロックを特定する。ブロックのこの集合は、同期する必要のあるデータブロックのみを含むものと予想される。前のグループメンバーシップのデバイスのすべては、現在の一貫性を有するバージョンを記憶するので、リストに現れていないセグメントグループに関連付けられたデータブロックを同期させる必要はない。また、方法３００のステップ３０４は、新しいグループメンバーシップが前のグループメンバーシップの定足数を含むことを必要とするので、これらのデバイスは新しいグループメンバーシップの定足数を含む。これは、一貫性を有するバージョンが定足数によって記憶されていないデータセグメントを特定する別の方法である。
【００５９】
一実施の形態では、各書き込みオペレーションは、オプションの第３のフェーズを含むことができる。この第３のフェーズは、新しいデータブロック（又はパリティ）の値の記憶に成功したセグメントグループの他のデバイスのリストを各ストレージデバイスに通知する。これらのデバイスは、セグメントに対する前の書き込みオペレーションの「応答者集合」と呼ばれる。応答者集合は、各デバイスのタイムスタンプテーブルと共に各デバイスに記憶することができ、前のグループメンバーシップを廃棄する前に同期させなければならないブロックと、もっと後まで待つことができるブロックとを区別するのに使用することができる。より詳細に言えば、（ステップ５０４又は６０４において送信された）ポーリングメッセージに応答して、ストレージデバイスは、応答者集合が新しいグループメンバーシップの定足数でない場合に、セグメントを、同期させなければならないものとして特定することにより応答する。このようにして特定されたブロックは、方法５００又は６００を使用して更新することができる。応答者集合が新しいグループメンバーシップの定足数であるが、新しいグループ全体よりも少ない場合、ストレージデバイスは、ブロックを、更新がオプションであるものとして特定することにより応答することができる。これは、一貫性を有するバージョンが定足数によって記憶されていないデータセグメントを特定するさらに別の方法である。
【００６０】
一定の状況では、新しいセグメントグループの同期が完全に省略される。一実施の形態では、前のセグメントグループのあらゆる定足数が、新しいセグメントグループの定足数の上位集合である場合、同期は省略される。この条件は、定足数収納条件（quorum containment condition）と呼ばれる。これは、前のグループのどの過半数も新しいグループの過半数でもあるので、前のグループメンバーシップが偶数個のデバイスを有し、且つ、新しいグループメンバーシップが１つ少ないデバイスを有するときの複製データの場合である。定足数収納は、イレーシャ符号化データの場合にも起こる可能性がある。したがって、一実施の形態では、再構成方法３００のイニシエータは、定足数収納条件が維持されているかどうかを判断することによってステップ３０６を実行し、その場合、同期方法５００又は６００は実行されない。
【００６１】
上述したように、同期は、新しいグループの定足数が、データ（又はパリティ）の一貫性を有するバージョンを記憶していると確認された場合にのみ（ステップ５１０及び６１０において）成功したものとみなすことができる。また、同期は、定足数収納条件を通じてデータ（又はパリティ）の一貫性を有するバージョンを記憶していると確認されたセグメントについては省略することができる。加えて、いくつかのデータは、（ステップ５０４及び６０４において）同期がオプションであるデータとして特定することができる。これらの場合のいずれにおいても、（たとえ少なくとも定足数が、一貫性を有するバージョンを有していても）新しいグループメンバーシップのデバイスのいくつかは、データの一貫性を有するバージョンを有しない場合がある。一実施の形態では、新しいグループのデバイスのすべてが、データの一貫性を有するバージョンを記憶するように構成される。したがって、一実施の形態では、同期が、特定のデータブロックについて完了したか又は省略され、且つ、デバイスのいくつかが、そのデータの一貫性を有するバージョンを記憶していない場合、更新オペレーションが最終的にはこれらのデバイスに対して実行され、その結果、このデータは最終的に現時点のものとされる。これは、前のグループメンバーシップが廃棄された後、他のオペレーションのバックグラウンドで比較的低速に行うことができる。
【００６２】
上記は本発明の特定の実施の形態に関して述べられているが、本発明の原理及び精神から逸脱することなく、これらの実施の形態の変更を行えることが当業者には十分理解されよう。本発明の範囲は、添付の特許請求の範囲によって規定される。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施の形態による、複数の冗長ストレージデバイスノードを含む一例示のストレージシステムを示す図である。
【図２】本発明の一実施の形態による、図１のストレージシステムで使用される一例示のストレージデバイスを示す図である。
【図３】本発明の一実施の形態による、データストレージシステムを再構成するための方法の一例示のフロー図である。
【図４】本発明の一実施の形態による、ストレージデバイスの新しいグループを形成するための方法の一例示のフロー図である。
【図５】本発明の一実施の形態による、一グループのストレージデバイスの少なくとも定足数が複製データの一貫性を有するバージョンを共同で確実に記憶するようにするための方法の一例示のフロー図である。
【図６】本発明の一実施の形態による、一グループのストレージデバイスの少なくとも定足数がイレーシャ符号化データの一貫性を有するバージョンを共同で確実に記憶するようにするための方法の一例示のフロー図である。
【符号の説明】
【００６４】
１００・・・ストレージシステム
１０２・・・ストレージデバイス
１０４・・・通信媒体
１０６・・・クライアント
１０８・・・通信媒体
１１０・・・インターフェース
１１２・・・ＣＰＵ
１１４・・・マスストレージ
１１６・・・メモリ
【図１】
2008516343.tif 000003
【図２】
2008516343.tif 000004
【図３】
2008516343.tif 000005
【図４】
2008516343.tif 000006
【図５】
2008516343.tif 000007
【図６】
2008516343.tif 000008
【国際調査報告】
2008516343.tif 000009
2008516343.tif 000010
2008516343.tif 000011