ビザンチン故障耐性データ複製を行う方法およびシステム

 

本発明は、複数2f+1個のデータサーバおよび1個以上のクライアントによるビザンチン故障耐性データ複製を行う方法に関する。データが、前記2f+1個のデータサーバのうちの少なくともf+1個の相異なるデータサーバに保存され、前記保存されたデータのメタデータが、故障耐性のあるメタデータサービスにメタデータ識別子の下に保存され、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含む。また、本発明は、ビザンチン故障耐性データ複製を行うシステムに関する。

 

 

本発明は、複数2f+1個のデータサーバおよび1個以上のクライアントによるビザンチン故障耐性データ複製を行う方法に関する。
また、本発明は、複数2f+1個のデータサーバおよび1個以上のクライアントを有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項1ないし11のいずれか1項に記載の方法を実行するシステムに関する。
データ複製(レプリケーション)は、一般に、障害の存在下で可用性およびデータ耐久性を提供する。例えば、複製されたデータストアは、操作が順次実行される複製されていないデータストアの挙動を示す場合に、強い意味の一貫性を有する。しかし、パフォーマンスおよびスケーラビリティが主要な問題となる。
データサーバシステムの複雑さの増大、および、保存されたデータの重要性の増大とともに、ビザンチン故障耐性(ビザンチン・フォールトトレランス)が、クラッシュ故障耐性に対する代替案として確立した。というのは、単純な停電、ソフトウェアのバグ、誤設定から、侵入およびマルウェアまでの幅広い問題を、「任意障害」あるいは「ビザンチン障害」という用語の下に包括することができるからである。
非同期性、同時並行性および障害の存在下で堅牢な複製データストアを実現するため、すなわち、任意障害の下で正確性を保証するため、クォーラム型(quorum-based)複製が使用される。非特許文献1には、f個の任意障害のビザンチン障害耐性のために3f+1個のサーバが使用されなければならないことが示されている。正しい値を読み出すためには、読み出し操作によって問合せを受けるクォーラムQr、すなわち、サーバの集合Qrが、f+1個のサーバにおける書き込み操作によって更新されるクォーラムQwと交わる必要がある。この場合、交わり(共通部分)の中に少なくとも1つの正しいサーバがあることが保証される。というのは、ビザンチン障害の可能性があるのは高々f個だからである。これを言い換えれば次の条件となる。
1)|Qr|+|Qw|−n≧f+1。ただし、nは使用されるサーバの総数である。
さらに、読み出しまたは書き込みの操作中にクラッシュしたサーバを無期限に待機することを避けるため、サーバのクォーラムQrおよびQwは、高々n−f個のサーバからなればよい。高々f個のサーバが故障する可能性があるので、n−f個のサーバは最終的に応答することが保証される。これを言い換えれば次の条件となる。
2)|Qr|=|Qw|≦n−f
2つの条件1)および2)を組み合わせることにより、次のようになる。
2n−2f−n≧f+1 ⇒ n≧3f+1
したがって、従来のシステムは、ビザンチン故障耐性ストレージで3f+1個のサーバを使用する。
例えば、非特許文献2では、ビザンチン・クォーラム型データ複製を用いてf個までのサーバの障害を許容するために、3f+1個のサーバあるいはクラウドが使用されている。
また、非特許文献3および非特許文献4には、他の従来のビザンチン故障耐性システムが示されている。
ビザンチン故障を許容するには、クラッシュ障害のみを許容するのに必要なよりもさらにf個のサーバを必要とするので、ビザンチン・クォーラム型データ複製の課題の1つは、クラッシュ耐性システムに比べて追加のコストがかかることである。例えば、非特許文献5に示されているように、f個のクラッシュを許容するには2f+1個のサーバが使用されるが、これではビザンチン故障を1つも許容することはできない。
Jean-Philippe Martin, Lorenzo Alvisi, Michael Dahlin: Minimal Byzantine Storage, DISC 2002: 311-325
Alysson Neves Bessani, Miguel P. Correia, Bruno Quaresma, Fernando Andre, Paulo Sousa: DepSky: dependable and secure storage in a cloud-of-clouds. EuroSys 2011: 31-46
Miguel Castro, Barbara Liskov: Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20(4): 398-461 (2002)
Dahlia Malkhi, Michael K. Reiter: Byzantine Quorum Systems. Distributed Computing 11(4): 203-213 (1998)
Rui Fan, Nancy A. Lynch: Efficient Replication of Large Data Objects. DISC 2003: 75-91

したがって、本発明の目的は、特にストレージサーバ取得コストおよび保守コストに関して、さらにストレージ容量に関して、より効率的なビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
具体的には、1つの目的は、3f+1個未満のデータサーバでビザンチン故障耐性データ複製を行う方法を提供することである。
本発明のもう1つの目的は、読み出しパフォーマンスが改善され、ストレージサーバ数に関して線形の読み出しスケーラビリティを有するビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
本発明のさらにもう1つの目的は、トランザクション型データアクセスが可能なビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
上記の目的は、請求項1の方法および請求項12のシステムによって達成される。
請求項1には、複数2f+1個のデータサーバおよび1個以上のクライアントによるビザンチン故障耐性データ複製を行う方法が規定される。
請求項1に記載の通り、本方法は、データが、前記2f+1個のデータサーバのうちの少なくともf+1個の相異なるデータサーバに保存され、前記保存されたデータのメタデータが、好ましくは故障耐性のある、メタデータサービスにメタデータ識別子の下に保存され、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含むことを特徴とする。
請求項12には、複数2f+1個のデータサーバおよび1個以上のクライアントを有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項1ないし11のいずれか1項に記載の方法を実行するシステムが規定される。
請求項12に記載の通り、本システムは、それぞれデータを保存するように動作可能な、前記2f+1個のデータサーバのうちの少なくともf+1個の相異なるデータサーバと、前記保存されたデータのメタデータをメタデータ識別子の下に保存するように動作可能な、好ましくは故障耐性のある、メタデータサービスとを備え、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含むことを特徴とする。
「フィンガープリント」という用語は最も広義に理解されるべきであり、例えば識別のための特徴的な適切に定義されたストリングを意味し、特に暗号学的ハッシュを含む。
本発明によって認識されたこととして、メタデータサービスが、2f+1個のデータサーバの集合とともに利用される。そのうちのf個は任意障害を起こす可能性がある。データサーバが実データを保存する一方、メタデータサービスは、関連するメタデータを追跡する。メタデータは、例えばデータコピーの位置やフィンガープリント(例えば完全性検証のためのデータの暗号学的ハッシュ)等を含むが、これらに限定されない。
また、本発明によって認識されたこととして、特に、データオブジェクトがメタデータに比べて大規模であるためにデータ操作のコストが帯域幅およびレイテンシに関して支配的なコストとなる場合には、効率が大幅に向上し、複製コストが低減される。結果として、メタデータサービスが対応して設計されれば、メタデータアクセスはデータアクセスよりも大幅に安価となる。
本発明によって認識されたこととして、スケーラビリティが提供される。
本発明によって認識されたこととして、複製されるデータあるいはメタデータの正確性、ウェイトフリー性(wait-freedom)、および線形化可能性(linearizability)が実現される。
その他の特徴、利点および好ましい実施形態は後続の従属請求項に記載される。
好ましい実施形態によれば、前記f+1個のデータサーバへの前記データの保存が成功した場合にのみ前記メタデータが保存される。これにより、f+1個のデータサーバすべてに対する保存が成功した場合にのみメタデータが保存されるので、信頼性が向上する。その場合、f+1個のデータサーバのリストは、メタデータサービスにとって容易な方法で提供することができる。
さらなる好ましい実施形態によれば、クライアントがデータを読み出す場合、
a)メタデータ識別子による問合せに応じて前記メタデータサービスによって提供されるメタデータに基づいて、前記データの前記一意識別子によって、前記データサーバのリストのデータサーバに問合せを行い、
b)前記一意識別子に従って前記保存されたデータが提供され、
c)前記保存されたデータおよび前記保存されたメタデータのフィンガープリントどうしが一致した場合、前記保存されたデータが前記クライアントに提供される。
これにより、データを読み出す場合、メタデータサービスに問合せを行い、メタデータサービスは、問合せされた値とともに、例えば、データのタグ、保存されたデータの暗号学的ダイジェスト、およびサーバのリストを返す。その後、問合せ側クライアントは、リストのサーバのうちの1つから、タグによって、対応するデータを取得することが可能である。返値がダイジェストと一致する場合、読み出し操作は正しい値を返し、読み出し操作は完了する。したがって、高速、容易で信頼性のある読み出し操作が提供される。
さらなる好ましい実施形態によれば、前記フィンガープリントどうしが不一致の場合、少なくとも1つの一致が達成されるまで、前記データサーバのリストの1個以上の他のデータサーバについてステップa)〜c)が反復される。これにより、リストのf個のデータサーバのビザンチン障害またはクラッシュ障害の場合であっても、クライアントは、1つの正しいデータサーバから保存データの正しい値を取得することができる。したがって、データの読み出しの信頼性がさらに向上する。
さらなる好ましい実施形態によれば、ステップa)〜c)の反復は、1回の反復ごとに前記データサーバのリストのただ1つのデータサーバについて順次実行される。これにより、データを提供するためのただ1つのサーバが問合せを受け、リストの他のサーバは例えば他の書き込み操作に対してブロックされない。他のサーバは、現在問合せを受けているサーバが正しいフィンガープリントを、したがって正しいデータを提供しない場合にのみ、問合せを受ける。
さらなる好ましい実施形態によれば、前記データのバージョン情報が前記メタデータサービスに保存され、問合せ時に前記クライアントに提供される。バージョン情報が保存される場合、トランザクションが可能となる。例えば、基本的な上書きを超える操作をサポートすることができる。例えば、対応する操作をメタデータサービスが提供すれば、条件付き更新や条件付き多重更新等の操作をサポートすることができる。
さらなる好ましい実施形態によれば、前記メタデータサービスがクラウドサービスとして提供される。これにより、容易な方法で、メタデータサービスを提供するコスト、すなわち保守コスト等を削減することができる。また、クラウドデータは通常、故障耐性(フォールトトレランス)があるように提供されるので、信頼性がさらに向上する。
さらなる好ましい実施形態によれば、前記データサーバのうちの少なくとも2個、好ましくは前記f+1個のデータサーバのうちの少なくとも2個が、データを保存するための相異なるファイルストレージサービスを提供する。相異なるファイルストレージサービス(例えば相異なるデータベース)を使用することにより、セキュリティおよび信頼性が向上する。というのは、例えば、ストレージサービスのうちの1つがオフラインである場合や攻撃またはハッキングされている場合であっても、データを読み出すことができるからである。
さらなる好ましい実施形態によれば、複数のデータを同時に保存するため、各データが前記f+1個のデータサーバのそれぞれに保存される。これにより、容易な方法で、多重更新等の高度な操作を提供することができ、フレキシビリティがさらに向上する。
さらなる好ましい実施形態によれば、前記メタデータサービスが故障耐性のためにクォーラム型プロトコルを使用する。これにより、障害に対する堅牢性が実現され、容易な実施が可能となる。
さらなる好ましい実施形態によれば、前記メタデータサービスが前記メタデータに対する操作を線形化する。これにより、例えば読み出しおよび/または書き込みの操作が、メタデータに対する(低レベルの)読み出しおよび書き込みの操作の実行順序で実行されることが可能となる。したがって、メタデータに対する操作の実時間順序を守ることができる。
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項1に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
本発明の第1の実施形態による方法のステップを模式的に示す図である。 本発明の第2の実施形態による方法のステップを模式的に示す図である。 本発明の第3の実施形態による方法のステップを模式的に示す図である。
図1〜図3において、データサーバの集合S={s,s,...,s}およびクライアントの集合C={c,...,c}を含む分散システムを仮定する。データサーバの少数派は、ビザンチン障害を被る可能性がある(|S|≧2f+1、ただしfは障害しきい値)。また、任意個のクライアントがクラッシュにより故障する可能性がある。また、故障のないメタデータサービスが、メタデータの読み出しおよび更新のサポートを提供すると仮定する。また、Hは衝突耐性のある暗号学的ハッシュ関数を示し、メタデータに対する操作はメタデータサービスMDSによって線形化される。
図1は、本発明の第1の実施形態による方法のステップを模式的に示している。
図1には、f=1、すなわち、ビザンチン障害が起こる可能性があるサーバの個数fが1であり、|S|=3、すなわち、データサーバの個数|S|が3の場合を示している。具体的には、図1には、値Vを有するデータオブジェクトkを更新する書き込み操作が示されている。まず、第1のステップ1で、クライアントCが、サーバsおよびsに、値Vとともに対応するタグ(tag)を保存する。データの保存に成功した場合、第2のステップ2で、f+1個のサーバSのそれぞれ、すなわちsおよびsは、クライアントCへ確認応答メッセージを送信する。
次に、クライアントCは、暗号学的ハッシュ関数H(V)を用いて、保存された値Vのダイジェストを計算した後、第3のステップ3で、キーkと、タグ、ダイジェストおよびデータサーバ(すなわちsおよびs)のリストを含む値とをメタデータmdとして与えてメタデータサービスMDSを呼び出す。また、クライアントCは、例えば条件付き更新の場合(図3参照)、値Vに対するバージョン情報を与えてもよい。
f+1個のサーバ(図1ではsおよびs)に値のコピーを書き込むことにより、書き込み操作によって更新された後にf個のサーバ(図1ではサーバsまたはsのいずれか)が故障しても、後続の読み出しで値Vを取得できることが保証される。f個のサーバが故障した場合に、書き込み操作がf+1個までのサーバs,sを更新しようと試行してブロックされることを防ぐために、追加的なf個のデータサーバ(図1ではサーバs)が使用される。最適な場合、クラッシュ耐性のプロトコルを含めて、任意のデータ複製プロトコルに対して、fまたはf+1が下限となる。
第4のステップ4で、メタデータサービスMDSが、クライアントCに、対応する確認応答メッセージを提供する。これは、メタデータサービスMDSにおいてメタデータの保存が成功したことも示す。
図2は、本発明の第2の実施形態による方法のステップを模式的に示している。
図2には、キーkに対する値を読み出す読み出し操作が示されている。第1のステップ5で、クライアントCは、メタデータサービスMDSと通信し、キーkを用いてメタデータサービスMDSに対して問合せを行う。次に、第2のステップ6で、メタデータサービスMDSは、メタデータmdおよび(トランザクションがサポートされる場合には)バージョン情報verをクライアントCに返す。次に、第7のステップ7で、クライアントCは、メタデータmdに含まれるリスト内のサーバs,sのうちの1つから、タグによって、対応するデータを取得する。そして、次のステップ8で、通信先のサーバ(すなわち図2ではサーバs)は、タグに対応する値V′であって、このタグの下にサーバsに保存されている値V′をクライアントCに返送する。次に、クライアントCは、返値V′がダイジェストと一致するかどうか比較する。すなわち、クライアントCは、値V′のフィンガープリントH(V′)を計算し、それを、取得したメタデータmdと比較する。メタデータmdは、値Vの保存されたフィンガープリントH(V)を含んでいる。したがって、返値V′がダイジェストと一致する場合、すなわちH(V)=H(V′)の場合、読み出し操作は、正しい値Vとして値V′を返し、操作は完了する。
そうでない場合、クライアントCは、サーバs,sのいずれかが、一致する値で応答するまで、サーバ(図2ではサーバsおよびs)のリストで反復動作する。例えば、値V′がダイジェストと一致しない場合、クライアントCは、f+1個のサーバs,sのリストのうちの第2のサーバsにタグを用いて問合せを行う。するとサーバsは、値V″により応答する。次に、クライアントCは、再び、メタデータmdに含まれるダイジェストと、返値V″のフィンガープリントH(V)とを比較する。一致した場合、すなわち、H(V)=H(V″)の場合、読み出し操作は完了する。
図3は、本発明の第3の実施形態による方法のステップを模式的に示している。
図3には、多重更新操作のステップが示されている。多重更新操作により、相異なるキーに対して全か無かでアトミック(不可分)に更新操作を実行することが可能となる。
図3において、クライアントCは、複数の値V,...,Vを、対応するタグtag,...,tagとともに、f+1個のサーバs,sのそれぞれに保存する。値V,Vを保存した確認メッセージをサーバs,sから受信した後、クライアントCは、メタデータmdを、それぞれの値についてmd=(tag,H(V),{s,s})と計算する。次のステップ11で、クライアントCは、メタデータサービスMDSと通信し、操作識別子opと、対応するキーk、メタデータmdおよびバージョンデータverを、値V,...,Vのすべてのインデックス1,...,nについて保存する。これらの情報の保存が成功した場合、次のステップ12で、メタデータサービスMDSは、対応する確認応答メッセージをクライアントCに返送する。
例えば、対応する操作opは、条件付き書き込み操作や条件付き削除操作等を含むことが可能である。条件付き書き込みの場合、対応するバージョン情報verがメタデータmdに含められるか、または、保存されるデータに対応するメタデータmdにリンクされてメタデータサービスMDSに保存される。その後、図1に関して、値は書き込み操作においてアトミックに保存される。あるバージョンverがデータの現在のバージョンと一致しない場合、いずれのデータオブジェクト(すなわち値V)にも変更は行われない。そして、例えばエラー情報が返されてもよい。
条件付き更新の場合には、与えられたバージョンがデータの現在のバージョンと一致する場合にのみ、値Vがキーkの下で保存される。そうでない場合には変更は行われない。そして、エラー情報がクライアントCに返されてもよい。条件付き削除操作は、与えられたバージョンがデータの値の現在のバージョンと一致する場合にのみキーkを削除する。そうでない場合には変更は行われない。そして、エラー情報が返されてもよい。削除操作は、削除のための値として値{ヌル}を書き込む書き込み操作によって実施されてもよい。
ビザンチン故障耐性データ複製の方法およびシステムは正確である。以下で正確性を証明するため、本発明による操作はウェイトフリーかつ線形化可能とする。ウェイトフリーとは、正しいクライアントによる操作が、他のクライアントの挙動にかかわらず常に完了することを意味する。本発明によれば、メタデータサービスがウェイトフリー操作をエクスポートし、故障するデータサーバがf個を超えない場合に、ウェイトフリー性が保証される。また、線形化可能性は、アトミック性としても知られており、操作が、呼び出しステップと応答ステップとの間の1時点に瞬時に行われるように見えることを意味する。本発明によれば、メタデータ操作が線形化可能である場合に線形化可能性が実現される。その場合、線形化可能性は、故障したサーバ数fとは独立である。
メタデータサービスMDSに対して呼び出される低レベルの操作がウェイトフリーであると仮定すると、データサーバのうちの1つにアクセスする際に、どの操作もブロックされないことを示す必要がある。故障するのは高々f個のデータサーバであるので、それぞれの更新操作は最終的にf+1個の正しいサーバから応答を受信する。したがって、データサーバからの応答を待機しながら更新操作がブロックされることはない。更新操作を実行するとき、メタデータは、対応するデータをデータサーバに保存した後にのみ書き込まれ、読み出し側がメタデータを取得するときまでに、対応する更新操作は対応するタグの下でf+1個のサーバのすべてにおいて、一致する値を保存している。これらのサーバのうちビザンチン故障になるのは高々f個であるので、これらのf+1個のサーバのうちに、対応するタグの下で一致する値Vを保存し最終的に読み出し側(すなわちクライアント)に応答する正しいサーバが少なくとも1つ存在する。H(V)がダイジェストに一致していることをチェックした後、読み出し操作は完了する。障害を伴う非同期実行が最悪の場合であり、その場合、一致する応答を受信する前に、読み出しはf+1個のデータサーバに問合せを行う必要がある。これに対して、故障のない同期実行が通常の場合であり、その場合、ただ1つのデータサーバが読み出しによって問合せを受ける。
上記のように、メタデータサービスMDSは、メタデータに対するすべての操作を線形化する。具体的には、読み出しおよび書き込みの操作は、メタデータへの対応する低レベルの書き込みおよび読み出しの操作の実行順序に従って線形化される。メタデータ操作の線形化可能性により、低レベル操作の履歴が、メタデータサービスMDSの順序仕様を満たし、メタデータ操作の実時間順序を守る。メタデータサービスの順序仕様はシステム全体の順序仕様と等価であり、メタデータサービスは高レベル操作間の実時間先行関係を維持するので、高レベル操作が線形化可能であると結論することができる。
要約すると、本発明によれば、ビザンチン的にデータからメタデータを分離することにより、データサーバ数を3f+1から2f+1に削減することが可能となる。また、本発明は、2f+1個のデータサーバの集合とともにメタデータサービスを利用することにより、強い意味で一貫性のあるデータ複製を実現する。また、本発明によれば、データサーバに問合せを行う前にメタデータサービスを参照する通常の場合に、ただ1つのデータサーバを問い合わせるだけとすることが可能である。さらに、本発明によれば、等価なメタデータ操作がメタデータサービスによって公開される場合には、データ操作のエクスポートが可能である。
本発明は、特に以下の利点を有する。本発明によれば、ストレージサーバ取得コストおよび保守コスト、さらにストレージ容量が削減される。また、本発明によれば、読み出しパフォーマンスが改善され、ストレージサーバ数に関して線形の読み出しスケーラビリティが実現され、トランザクション型のデータアクセスが可能となる。さらに、本発明によれば、複製コストが3f+1個のサーバから2f+1個だけのデータサーバへと実質的に削減可能であり、上記のような読み出しスケーラビリティが得られる。通常は読み出し操作中にアクセスされるデータサーバは1つだけであるので、保存されるデータオブジェクトがサーバ間で均等に分配される場合には、各サーバが被る負荷は1/|S|となる。その結果、容量は|S|(すなわちデータサーバ数)倍になる。
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。



  1. 複数2f+1個のデータサーバ(S)および1個以上のクライアント(C)によるビザンチン故障耐性データ複製を行う方法において、
    データ(V)が、前記2f+1個のデータサーバ(S)のうちの少なくともf+1個の相異なるデータサーバ(S)に保存され(1)、
    前記保存されたデータのメタデータ(md)が、好ましくは故障耐性のある、メタデータサービス(MDS)にメタデータ識別子(k)の下に保存され、保存されるメタデータ(md)は、前記保存されたデータ(V)の一意識別子(tag)と、前記保存されたデータ(V)のフィンガープリント(H(V))と、前記データ(V)を保存したデータサーバのリスト({s,s,...})とを含むことを特徴とする、ビザンチン故障耐性データ複製を行う方法。

  2. 前記f+1個のデータサーバ(S)への前記データ(V)の保存が成功した場合にのみ前記メタデータ(md)が保存されることを特徴とする請求項1に記載の方法。

  3. クライアント(C)がデータ(V)を読み出す場合、
    a)メタデータ識別子(k)による問合せに応じて前記メタデータサービス(MDS)によって提供されるメタデータに基づいて、前記データ(V)の前記一意識別子(tag)によって、前記データサーバのリストのデータサーバに問合せを行い、
    b)前記一意識別子(tag)に従って前記保存されたデータ(V)が提供され、
    c)前記保存されたデータ(V′)および前記保存されたメタデータのフィンガープリント(H(V),H(V′))どうしが一致した場合、前記保存されたデータ(V)が前記クライアント(C)に提供される
    ことを特徴とする請求項1または2に記載の方法。

  4. 前記フィンガープリント(H(V),H(V′))どうしが不一致の場合、少なくとも1つの一致が達成されるまで、前記データサーバのリスト({s,s,...})の1個以上の他のデータサーバ({s,...})についてステップa)〜c)が反復されることを特徴とする請求項3に記載の方法。

  5. ステップa)〜c)の反復は、1回の反復ごとに前記データサーバのリスト({s,s,...})のただ1つのデータサーバ(S)について順次実行されることを特徴とする請求項4に記載の方法。

  6. 前記データ(V)のバージョン情報(ver)が前記メタデータサービス(MDS)に保存され、問合せ時に前記クライアント(C)に提供されることを特徴とする請求項1ないし5のいずれか1項に記載の方法。

  7. 前記メタデータサービス(MDS)がクラウドサービスとして提供されることを特徴とする請求項1ないし6のいずれか1項に記載の方法。

  8. 前記データサーバ(S)のうちの少なくとも2個、好ましくは前記f+1個のデータサーバ({s,s,...})のうちの少なくとも2個が、データ(V)を保存するための相異なるファイルストレージサービスを提供することを特徴とする請求項1ないし7のいずれか1項に記載の方法。

  9. 複数のデータ(V)を同時に保存するため、各データ(V)が前記f+1個のデータサーバ({s,s,...})のそれぞれに保存されることを特徴とする請求項1ないし8のいずれか1項に記載の方法。

  10. 前記メタデータサービス(MDS)が故障耐性のためにクォーラム型プロトコルを使用することを特徴とする請求項1ないし9のいずれか1項に記載の方法。

  11. 前記メタデータサービス(MDS)が前記メタデータ(md)に対する操作を線形化することを特徴とする請求項1ないし10のいずれか1項に記載の方法。

  12. 複数2f+1個のデータサーバ(S)および1個以上のクライアント(C)を有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項1ないし11のいずれか1項に記載の方法を実行するシステムにおいて、
    それぞれデータ(V)を保存するように動作可能な、前記2f+1個のデータサーバ(S)のうちの少なくともf+1個の相異なるデータサーバ({s,...})と、
    前記保存されたデータ(V)のメタデータ(md)をメタデータ識別子(k)の下に保存するように動作可能な、故障耐性のあるメタデータサービス(MDS)と
    を備え、保存されるメタデータ(md)は、前記保存されたデータ(V)の一意識別子(tag)と、前記保存されたデータ(V)のフィンガープリント(H(V))と、前記データ(V)を保存したデータサーバのリスト({s,s,...})とを含むことを特徴とする、ビザンチン故障耐性データ複製を行うシステム。

 

 

Patent trol of patentswamp
類似の特許
複製書き込みのためのトークンベースの承認制御のための方法及び装置が開示される。データオブジェクトは、区画に分けられ、各区画に対応して、少なくともマスター複製とスレーブ複製とが記憶される。区画に向けられる書き込み要求を承諾するべきかどうかについての決定は、(a)マスター複製で利用可能なスループット容量、及び(b)スレーブ複製で利用可能なスループット容量のトークンベースのプロトコルを使用して取得される指標のうちの1つ以上に少なくとも部分的に基づく。書き込み要求が承諾されると、1つ以上のデータ修正動作が開始される。
分散型データベースシステムは、高速クラッシュ回復を実装してよい。データベースヘッドノード故障からの回復時、データベースヘッドノードによって実装されるデータベースのためのデータを記憶する分散型ストレージシステムの1つまたは複数のストレージノードとの接続が確立されてよい。ストレージノードとの接続の確立時、そのデータベースは、多様なアクセス要求等アクセスのために利用可能にされてよい。多様な実施形態では、リドゥログレコードはデータベースへのアクセスを提供するためにリプレイされないことがある。少なくともいくつかの実施形態では、ストレージノードは、要求に応えてデータベースのために記憶されるデータの現在の状態を提供してよい。
【選択図】図8
本発明の実施形態は、データ格納方法、データストレージ装置、及びストレージデバイスを提供する。前記方法は、ファイル処理要求し、前記ファイル処理要求を複数のファイル操作に分割し、それぞれのファイル操作に対して別々にファイル処理を実行し、複数のファイル操作情報を生成するステップと、前記複数のファイル操作情報のすべてをキャッシュ保護領域に書き込むステップと、第1コントローラに障害が生じた後、再び電源が入った場合、前記キャッシュ保護領域から前記複数のファイル操作情報を復元するステップと、ホストが前記データ情報にアクセスできるように、前記複数のファイル操作情報に従って、データ情報を取得し、前記データ情報を第1ライトキャッシュに書き込むステップと、を含む。これにより、前記ホストのデータアクセス効率性が改善可能となる。
本発明の実施形態は、メモリデータを移行するための方法、コンピュータ、および装置を提供する。第1のトリガ命令を受信した後に、プロセッサは、オペレーティングシステムを終了し、基本入出力システムのメモリデータ移行命令を実行することができ、基本入出力システムのメモリデータ移行命令は、プロセッサが移行されるべきメモリデータのソースメモリカードを決定し、ソースメモリカードに対するバックアップメモリカードを決定し、ソースメモリカードのメモリコントローラに、メモリデータを移行することを命令することを可能にし、これにより、ソースメモリカードのメモリコントローラが、プロセッサの命令に従って、ソースメモリカードのメモリデータを読み出し、ソースメモリカードの読み出されたメモリデータをバックアップメモリカードに書き込むことを可能にし、これにより、ソースメモリカードのメモリデータは、コンピュータの電源が切られていない場合に移行することができ、これにより、障害のあるメモリカードのオンラインメンテナンスを実現し、障害のあるメモリカードは、コンピュータ全体の電源が切られているときしか交換またはメンテナンスを行えないという従来技術における問題点を解決することができる。
データストレージシステムにおけるソースファイルシステムからターゲットファイルシステムへのクローンオブジェクトのオブジェクトレベルでの複製は、上記ターゲットファイルシステムにおけるストレージ要求が、上記ソースファイルシステムのストレージ要求と一致する様に、共有されたデータブロックを含む関連オブジェクト間の関係を維持する。特定の処理は、複製を要求するオブジェクトが、チェックポイント番号に基づいて増分ベースで特定可能な様に、他のファイルシステムオブジェクトを参照する間接オブジェクトをスキャンするために実行することができる。上記ターゲットファイルシステム内のチェックポイントは、複製されたクローンオブジェクトに対するチェックポイント番号の要件が、上記ターゲットファイルシステムにおいて満たされる様に、管理される。
第1のデータは、第1の非対称メモリデバイスに格納するために受信される。第1の書き込みフェーズは、現在の書き込みフェーズとして特定される。第1の非対称メモリデバイスに含まれる第1のセグメントは、データを書き込むために利用可能な次のセグメントとして特定される。第1のデータは第1のセグメントに書き込まれる。第1のセグメントに関連する情報は、第1のセグメントが第1の書き込みフェーズにおいて書き込まれることを示す情報と共に、格納される。第2のデータは、非対称メモリに格納するために受信される。第1の非対称メモリデバイスに含まれる第2のセグメントは、データを書き込むために利用可能な次のセグメントとして特定される。第2のデータは第2のセグメントに書き込まれる。第2のセグメントおよび第2のメモリブロックに関連する情報は、第2のセグメントが第2の書き込みフェーズにおいて書き込まれることを示す情報と共に、格納される。
データベースシステムはデータベースサービス及び別個の分散型ストレージサービスを含んでよい。データベースサービス(またはデータベースサービスのデータベースエンジンヘッドノード)は、クエリーパーシング、最適化、及び実行、トランザクション性、並びに一貫性に対して責任を負ってよい。一方、ストレージサービスは、リドゥログレコードからデータページを生成すること、及びそれらのデータページの耐久性に責任を負ってよい。例えば、特定のデータページに向けられる書込み要求に応えて、データベースエンジンヘッドノードはストレージサービスノードに、リドゥログレコードを生成し、リドゥログレコードを送信してよいが、データページを送信しないことがある。ストレージサービスノードはリドゥログレコードを記憶し、リドゥログレコードを適用する前に、データベースサービスに書込み肯定応答を返してよい。サーバノードは、カレントバージョンを生成するために、データページの以前に記憶されたバージョンに、リドゥログレコード及び他のリドゥログレコードを適用してよい。
【選択図】図7
ラックマウント型ストレージエンクロージャは、シャーシを含む。シャーシは、1つ又は複数の電源及び複数の引き出しを含み、各引き出しは、シャーシの前面から引き出し可能である。複数の引き出しにおける各引き出しは、1つ又は複数のストレージデバイス用の取り付け台を提供する。複数の引き出しの任意の引き出しにおける全てのストレージデバイスは、引き出しの共通の側部から挿入されるか又は取り外される。たとえシャーシの側面が、それぞれ、壁と平行で壁に接し、且つ壁のそれぞれが、少なくとも任意の引き出しの完全に引き出された長さまで前方に延びている場合であっても、任意のストレージデバイスが、複数の引き出しにおける任意の引き出しから挿入されるか又は取り外される。いずれか1つの引き出しにおける電気的故障は、複数の引き出しにおける他の引き出しのいずれかに影響を及ぼすことが防止される。1つ又は複数の電源は、複数の引き出しにDC電力を供給する。
データを記憶するための方法。方法は、データを書込む要求を受信することと、データのための記憶モードがミラードモードであると判断することと、記憶モードに基づいて独立装置冗長アレイ(RAID)グリッド中のRAIDグリッド場所を選択してデータを書込むことと、データをメモリに書込むことと、データ構造を更新して、RAIDグリッド場所が埋まっていると示すことと、データグリッドが埋まっていると判断することとを含む。判断に基づいて、RAIDグリッド場所に対応する永続性記憶装置中の第1の物理アドレスおよび第2の物理アドレスを判断し、第1の物理アドレスに対応する永続性記憶装置中の第1の物理的場所にデータを書込み、第2の物理アドレスに対応する永続性記憶装置中の第2の物理的場所にデータを書込み、データグリッドに関連付けられるパリティ値を永続性記憶装置に書込む。
【課題】ソースシステムと宛先システムとの間のデータの複製を最適化する。
【解決手段】ソースシステムは複製されるデータのフラグメントのシグネチャを計算してシグネチャを宛先システムへ送信し、宛先システムはシグネチャが既知であるかどうかを判定し、既知であれば複製データを再構成するために使用し、そうでなければシグネチャが未知であるメッセージをソースシステムに送信し、次いでソースシステムは未知のシグネチャに対応するフラグメントを宛先システムに送信し、宛先システムは送信されたフラグメントを使用して複製データを再構成する。
【選択図】図2b
To top