(57)【要約】  本発明は、複数２ｆ＋１個のデータサーバおよび１個以上のクライアントによるビザンチン故障耐性データ複製を行う方法に関する。データが、前記２ｆ＋１個のデータサーバのうちの少なくともｆ＋１個の相異なるデータサーバに保存され、前記保存されたデータのメタデータが、故障耐性のあるメタデータサービスにメタデータ識別子の下に保存され、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含む。また、本発明は、ビザンチン故障耐性データ複製を行うシステムに関する。
2016517605.tif 000002
【特許請求の範囲】
【請求項１】
複数２ｆ＋１個のデータサーバ（Ｓ）および１個以上のクライアント（Ｃ）によるビザンチン故障耐性データ複製を行う方法において、
データ（Ｖ）が、前記２ｆ＋１個のデータサーバ（Ｓ）のうちの少なくともｆ＋１個の相異なるデータサーバ（Ｓ）に保存され（１）、
前記保存されたデータのメタデータ（ｍｄ）が、好ましくは故障耐性のある、メタデータサービス（ＭＤＳ）にメタデータ識別子（ｋ）の下に保存され、保存されるメタデータ（ｍｄ）は、前記保存されたデータ（Ｖ）の一意識別子（ｔａｇ）と、前記保存されたデータ（Ｖ）のフィンガープリント（Ｈ（Ｖ））と、前記データ（Ｖ）を保存したデータサーバのリスト（｛ｓ１，ｓ２，...｝）とを含むことを特徴とする、ビザンチン故障耐性データ複製を行う方法。
【請求項２】
前記ｆ＋１個のデータサーバ（Ｓ）への前記データ（Ｖ）の保存が成功した場合にのみ前記メタデータ（ｍｄ）が保存されることを特徴とする請求項１に記載の方法。
【請求項３】
クライアント（Ｃ）がデータ（Ｖ）を読み出す場合、
ａ）メタデータ識別子（ｋ）による問合せに応じて前記メタデータサービス（ＭＤＳ）によって提供されるメタデータに基づいて、前記データ（Ｖ）の前記一意識別子（ｔａｇ）によって、前記データサーバのリストのデータサーバに問合せを行い、
ｂ）前記一意識別子（ｔａｇ）に従って前記保存されたデータ（Ｖ）が提供され、
ｃ）前記保存されたデータ（Ｖ′）および前記保存されたメタデータのフィンガープリント（Ｈ（Ｖ），Ｈ（Ｖ′））どうしが一致した場合、前記保存されたデータ（Ｖ）が前記クライアント（Ｃ）に提供される
ことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記フィンガープリント（Ｈ（Ｖ），Ｈ（Ｖ′））どうしが不一致の場合、少なくとも１つの一致が達成されるまで、前記データサーバのリスト（｛ｓ１，ｓ２，...｝）の１個以上の他のデータサーバ（｛ｓ２，...｝）についてステップａ）〜ｃ）が反復されることを特徴とする請求項３に記載の方法。
【請求項５】
ステップａ）〜ｃ）の反復は、１回の反復ごとに前記データサーバのリスト（｛ｓ１，ｓ２，...｝）のただ１つのデータサーバ（Ｓ）について順次実行されることを特徴とする請求項４に記載の方法。
【請求項６】
前記データ（Ｖ）のバージョン情報（ｖｅｒ）が前記メタデータサービス（ＭＤＳ）に保存され、問合せ時に前記クライアント（Ｃ）に提供されることを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
前記メタデータサービス（ＭＤＳ）がクラウドサービスとして提供されることを特徴とする請求項１ないし６のいずれか１項に記載の方法。
【請求項８】
前記データサーバ（Ｓ）のうちの少なくとも２個、好ましくは前記ｆ＋１個のデータサーバ（｛ｓ１，ｓ２，...｝）のうちの少なくとも２個が、データ（Ｖ）を保存するための相異なるファイルストレージサービスを提供することを特徴とする請求項１ないし７のいずれか１項に記載の方法。
【請求項９】
複数のデータ（Ｖ）を同時に保存するため、各データ（Ｖ）が前記ｆ＋１個のデータサーバ（｛ｓ１，ｓ２，...｝）のそれぞれに保存されることを特徴とする請求項１ないし８のいずれか１項に記載の方法。
【請求項１０】
前記メタデータサービス（ＭＤＳ）が故障耐性のためにクォーラム型プロトコルを使用することを特徴とする請求項１ないし９のいずれか１項に記載の方法。
【請求項１１】
前記メタデータサービス（ＭＤＳ）が前記メタデータ（ｍｄ）に対する操作を線形化することを特徴とする請求項１ないし１０のいずれか１項に記載の方法。
【請求項１２】
複数２ｆ＋１個のデータサーバ（Ｓ）および１個以上のクライアント（Ｃ）を有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項１ないし１１のいずれか１項に記載の方法を実行するシステムにおいて、
それぞれデータ（Ｖ）を保存するように動作可能な、前記２ｆ＋１個のデータサーバ（Ｓ）のうちの少なくともｆ＋１個の相異なるデータサーバ（｛ｓ１，...｝）と、
前記保存されたデータ（Ｖ）のメタデータ（ｍｄ）をメタデータ識別子（ｋ）の下に保存するように動作可能な、故障耐性のあるメタデータサービス（ＭＤＳ）と
を備え、保存されるメタデータ（ｍｄ）は、前記保存されたデータ（Ｖ）の一意識別子（ｔａｇ）と、前記保存されたデータ（Ｖ）のフィンガープリント（Ｈ（Ｖ））と、前記データ（Ｖ）を保存したデータサーバのリスト（｛ｓ１，ｓ２，...｝）とを含むことを特徴とする、ビザンチン故障耐性データ複製を行うシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数２ｆ＋１個のデータサーバおよび１個以上のクライアントによるビザンチン故障耐性データ複製を行う方法に関する。
【０００２】
また、本発明は、複数２ｆ＋１個のデータサーバおよび１個以上のクライアントを有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項１ないし１１のいずれか１項に記載の方法を実行するシステムに関する。
【背景技術】
【０００３】
データ複製（レプリケーション）は、一般に、障害の存在下で可用性およびデータ耐久性を提供する。例えば、複製されたデータストアは、操作が順次実行される複製されていないデータストアの挙動を示す場合に、強い意味の一貫性を有する。しかし、パフォーマンスおよびスケーラビリティが主要な問題となる。
【０００４】
データサーバシステムの複雑さの増大、および、保存されたデータの重要性の増大とともに、ビザンチン故障耐性（ビザンチン・フォールトトレランス）が、クラッシュ故障耐性に対する代替案として確立した。というのは、単純な停電、ソフトウェアのバグ、誤設定から、侵入およびマルウェアまでの幅広い問題を、「任意障害」あるいは「ビザンチン障害」という用語の下に包括することができるからである。
【０００５】
非同期性、同時並行性および障害の存在下で堅牢な複製データストアを実現するため、すなわち、任意障害の下で正確性を保証するため、クォーラム型（quorum-based）複製が使用される。非特許文献１には、ｆ個の任意障害のビザンチン障害耐性のために３ｆ＋１個のサーバが使用されなければならないことが示されている。正しい値を読み出すためには、読み出し操作によって問合せを受けるクォーラムＱｒ、すなわち、サーバの集合Ｑｒが、ｆ＋１個のサーバにおける書き込み操作によって更新されるクォーラムＱｗと交わる必要がある。この場合、交わり（共通部分）の中に少なくとも１つの正しいサーバがあることが保証される。というのは、ビザンチン障害の可能性があるのは高々ｆ個だからである。これを言い換えれば次の条件となる。
１）｜Ｑｒ｜＋｜Ｑｗ｜−ｎ≧ｆ＋１。ただし、ｎは使用されるサーバの総数である。
【０００６】
さらに、読み出しまたは書き込みの操作中にクラッシュしたサーバを無期限に待機することを避けるため、サーバのクォーラムＱｒおよびＱｗは、高々ｎ−ｆ個のサーバからなればよい。高々ｆ個のサーバが故障する可能性があるので、ｎ−ｆ個のサーバは最終的に応答することが保証される。これを言い換えれば次の条件となる。
２）｜Ｑｒ｜＝｜Ｑｗ｜≦ｎ−ｆ
【０００７】
２つの条件１）および２）を組み合わせることにより、次のようになる。
２ｎ−２ｆ−ｎ≧ｆ＋１  ⇒  ｎ≧３ｆ＋１
【０００８】
したがって、従来のシステムは、ビザンチン故障耐性ストレージで３ｆ＋１個のサーバを使用する。
【０００９】
例えば、非特許文献２では、ビザンチン・クォーラム型データ複製を用いてｆ個までのサーバの障害を許容するために、３ｆ＋１個のサーバあるいはクラウドが使用されている。
【００１０】
また、非特許文献３および非特許文献４には、他の従来のビザンチン故障耐性システムが示されている。
【００１１】
ビザンチン故障を許容するには、クラッシュ障害のみを許容するのに必要なよりもさらにｆ個のサーバを必要とするので、ビザンチン・クォーラム型データ複製の課題の１つは、クラッシュ耐性システムに比べて追加のコストがかかることである。例えば、非特許文献５に示されているように、ｆ個のクラッシュを許容するには２ｆ＋１個のサーバが使用されるが、これではビザンチン故障を１つも許容することはできない。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【００１３】
したがって、本発明の目的は、特にストレージサーバ取得コストおよび保守コストに関して、さらにストレージ容量に関して、より効率的なビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
【００１４】
具体的には、１つの目的は、３ｆ＋１個未満のデータサーバでビザンチン故障耐性データ複製を行う方法を提供することである。
【００１５】
本発明のもう１つの目的は、読み出しパフォーマンスが改善され、ストレージサーバ数に関して線形の読み出しスケーラビリティを有するビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
【００１６】
本発明のさらにもう１つの目的は、トランザクション型データアクセスが可能なビザンチン故障耐性データ複製を行う方法およびシステムを提供することである。
【課題を解決するための手段】
【００１７】
上記の目的は、請求項１の方法および請求項１２のシステムによって達成される。
【００１８】
請求項１には、複数２ｆ＋１個のデータサーバおよび１個以上のクライアントによるビザンチン故障耐性データ複製を行う方法が規定される。
【００１９】
請求項１に記載の通り、本方法は、データが、前記２ｆ＋１個のデータサーバのうちの少なくともｆ＋１個の相異なるデータサーバに保存され、前記保存されたデータのメタデータが、好ましくは故障耐性のある、メタデータサービスにメタデータ識別子の下に保存され、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含むことを特徴とする。
【００２０】
請求項１２には、複数２ｆ＋１個のデータサーバおよび１個以上のクライアントを有するビザンチン故障耐性データ複製を行うシステムであって、好ましくは請求項１ないし１１のいずれか１項に記載の方法を実行するシステムが規定される。
【００２１】
請求項１２に記載の通り、本システムは、それぞれデータを保存するように動作可能な、前記２ｆ＋１個のデータサーバのうちの少なくともｆ＋１個の相異なるデータサーバと、前記保存されたデータのメタデータをメタデータ識別子の下に保存するように動作可能な、好ましくは故障耐性のある、メタデータサービスとを備え、保存されるメタデータは、前記保存されたデータの一意識別子と、前記保存されたデータのフィンガープリントと、前記データを保存したデータサーバのリストとを含むことを特徴とする。
【００２２】
「フィンガープリント」という用語は最も広義に理解されるべきであり、例えば識別のための特徴的な適切に定義されたストリングを意味し、特に暗号学的ハッシュを含む。
【００２３】
本発明によって認識されたこととして、メタデータサービスが、２ｆ＋１個のデータサーバの集合とともに利用される。そのうちのｆ個は任意障害を起こす可能性がある。データサーバが実データを保存する一方、メタデータサービスは、関連するメタデータを追跡する。メタデータは、例えばデータコピーの位置やフィンガープリント（例えば完全性検証のためのデータの暗号学的ハッシュ）等を含むが、これらに限定されない。
【００２４】
また、本発明によって認識されたこととして、特に、データオブジェクトがメタデータに比べて大規模であるためにデータ操作のコストが帯域幅およびレイテンシに関して支配的なコストとなる場合には、効率が大幅に向上し、複製コストが低減される。結果として、メタデータサービスが対応して設計されれば、メタデータアクセスはデータアクセスよりも大幅に安価となる。
【００２５】
本発明によって認識されたこととして、スケーラビリティが提供される。
【００２６】
本発明によって認識されたこととして、複製されるデータあるいはメタデータの正確性、ウェイトフリー性（wait-freedom）、および線形化可能性（linearizability）が実現される。
【００２７】
その他の特徴、利点および好ましい実施形態は後続の従属請求項に記載される。
【００２８】
好ましい実施形態によれば、前記ｆ＋１個のデータサーバへの前記データの保存が成功した場合にのみ前記メタデータが保存される。これにより、ｆ＋１個のデータサーバすべてに対する保存が成功した場合にのみメタデータが保存されるので、信頼性が向上する。その場合、ｆ＋１個のデータサーバのリストは、メタデータサービスにとって容易な方法で提供することができる。
【００２９】
さらなる好ましい実施形態によれば、クライアントがデータを読み出す場合、
ａ）メタデータ識別子による問合せに応じて前記メタデータサービスによって提供されるメタデータに基づいて、前記データの前記一意識別子によって、前記データサーバのリストのデータサーバに問合せを行い、
ｂ）前記一意識別子に従って前記保存されたデータが提供され、
ｃ）前記保存されたデータおよび前記保存されたメタデータのフィンガープリントどうしが一致した場合、前記保存されたデータが前記クライアントに提供される。
【００３０】
これにより、データを読み出す場合、メタデータサービスに問合せを行い、メタデータサービスは、問合せされた値とともに、例えば、データのタグ、保存されたデータの暗号学的ダイジェスト、およびサーバのリストを返す。その後、問合せ側クライアントは、リストのサーバのうちの１つから、タグによって、対応するデータを取得することが可能である。返値がダイジェストと一致する場合、読み出し操作は正しい値を返し、読み出し操作は完了する。したがって、高速、容易で信頼性のある読み出し操作が提供される。
【００３１】
さらなる好ましい実施形態によれば、前記フィンガープリントどうしが不一致の場合、少なくとも１つの一致が達成されるまで、前記データサーバのリストの１個以上の他のデータサーバについてステップａ）〜ｃ）が反復される。これにより、リストのｆ個のデータサーバのビザンチン障害またはクラッシュ障害の場合であっても、クライアントは、１つの正しいデータサーバから保存データの正しい値を取得することができる。したがって、データの読み出しの信頼性がさらに向上する。
【００３２】
さらなる好ましい実施形態によれば、ステップａ）〜ｃ）の反復は、１回の反復ごとに前記データサーバのリストのただ１つのデータサーバについて順次実行される。これにより、データを提供するためのただ１つのサーバが問合せを受け、リストの他のサーバは例えば他の書き込み操作に対してブロックされない。他のサーバは、現在問合せを受けているサーバが正しいフィンガープリントを、したがって正しいデータを提供しない場合にのみ、問合せを受ける。
【００３３】
さらなる好ましい実施形態によれば、前記データのバージョン情報が前記メタデータサービスに保存され、問合せ時に前記クライアントに提供される。バージョン情報が保存される場合、トランザクションが可能となる。例えば、基本的な上書きを超える操作をサポートすることができる。例えば、対応する操作をメタデータサービスが提供すれば、条件付き更新や条件付き多重更新等の操作をサポートすることができる。
【００３４】
さらなる好ましい実施形態によれば、前記メタデータサービスがクラウドサービスとして提供される。これにより、容易な方法で、メタデータサービスを提供するコスト、すなわち保守コスト等を削減することができる。また、クラウドデータは通常、故障耐性（フォールトトレランス）があるように提供されるので、信頼性がさらに向上する。
【００３５】
さらなる好ましい実施形態によれば、前記データサーバのうちの少なくとも２個、好ましくは前記ｆ＋１個のデータサーバのうちの少なくとも２個が、データを保存するための相異なるファイルストレージサービスを提供する。相異なるファイルストレージサービス（例えば相異なるデータベース）を使用することにより、セキュリティおよび信頼性が向上する。というのは、例えば、ストレージサービスのうちの１つがオフラインである場合や攻撃またはハッキングされている場合であっても、データを読み出すことができるからである。
【００３６】
さらなる好ましい実施形態によれば、複数のデータを同時に保存するため、各データが前記ｆ＋１個のデータサーバのそれぞれに保存される。これにより、容易な方法で、多重更新等の高度な操作を提供することができ、フレキシビリティがさらに向上する。
【００３７】
さらなる好ましい実施形態によれば、前記メタデータサービスが故障耐性のためにクォーラム型プロトコルを使用する。これにより、障害に対する堅牢性が実現され、容易な実施が可能となる。
【００３８】
さらなる好ましい実施形態によれば、前記メタデータサービスが前記メタデータに対する操作を線形化する。これにより、例えば読み出しおよび／または書き込みの操作が、メタデータに対する（低レベルの）読み出しおよび書き込みの操作の実行順序で実行されることが可能となる。したがって、メタデータに対する操作の実時間順序を守ることができる。
【００３９】
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００４０】
【図１】本発明の第１の実施形態による方法のステップを模式的に示す図である。
【図２】本発明の第２の実施形態による方法のステップを模式的に示す図である。
【図３】本発明の第３の実施形態による方法のステップを模式的に示す図である。
【発明を実施するための形態】
【００４１】
図１〜図３において、データサーバの集合Ｓ＝｛ｓ１，ｓ２，...，ｓＳ｝およびクライアントの集合Ｃ＝｛ｃ１，...，ｃＣ｝を含む分散システムを仮定する。データサーバの少数派は、ビザンチン障害を被る可能性がある（｜Ｓ｜≧２ｆ＋１、ただしｆは障害しきい値）。また、任意個のクライアントがクラッシュにより故障する可能性がある。また、故障のないメタデータサービスが、メタデータの読み出しおよび更新のサポートを提供すると仮定する。また、Ｈは衝突耐性のある暗号学的ハッシュ関数を示し、メタデータに対する操作はメタデータサービスＭＤＳによって線形化される。
【００４２】
図１は、本発明の第１の実施形態による方法のステップを模式的に示している。
【００４３】
図１には、ｆ＝１、すなわち、ビザンチン障害が起こる可能性があるサーバの個数ｆが１であり、｜Ｓ｜＝３、すなわち、データサーバの個数｜Ｓ｜が３の場合を示している。具体的には、図１には、値Ｖを有するデータオブジェクトｋを更新する書き込み操作が示されている。まず、第１のステップ１で、クライアントＣが、サーバｓ１およびｓ２に、値Ｖとともに対応するタグ（ｔａｇ）を保存する。データの保存に成功した場合、第２のステップ２で、ｆ＋１個のサーバＳのそれぞれ、すなわちｓ１およびｓ２は、クライアントＣへ確認応答メッセージを送信する。
【００４４】
次に、クライアントＣは、暗号学的ハッシュ関数Ｈ（Ｖ）を用いて、保存された値Ｖのダイジェストを計算した後、第３のステップ３で、キーｋと、タグ、ダイジェストおよびデータサーバ（すなわちｓ１およびｓ２）のリストを含む値とをメタデータｍｄとして与えてメタデータサービスＭＤＳを呼び出す。また、クライアントＣは、例えば条件付き更新の場合（図３参照）、値Ｖに対するバージョン情報を与えてもよい。
【００４５】
ｆ＋１個のサーバ（図１ではｓ１およびｓ２）に値のコピーを書き込むことにより、書き込み操作によって更新された後にｆ個のサーバ（図１ではサーバｓ１またはｓ２のいずれか）が故障しても、後続の読み出しで値Ｖを取得できることが保証される。ｆ個のサーバが故障した場合に、書き込み操作がｆ＋１個までのサーバｓ１，ｓ２を更新しようと試行してブロックされることを防ぐために、追加的なｆ個のデータサーバ（図１ではサーバｓ３）が使用される。最適な場合、クラッシュ耐性のプロトコルを含めて、任意のデータ複製プロトコルに対して、ｆまたはｆ＋１が下限となる。
【００４６】
第４のステップ４で、メタデータサービスＭＤＳが、クライアントＣに、対応する確認応答メッセージを提供する。これは、メタデータサービスＭＤＳにおいてメタデータの保存が成功したことも示す。
【００４７】
図２は、本発明の第２の実施形態による方法のステップを模式的に示している。
【００４８】
図２には、キーｋに対する値を読み出す読み出し操作が示されている。第１のステップ５で、クライアントＣは、メタデータサービスＭＤＳと通信し、キーｋを用いてメタデータサービスＭＤＳに対して問合せを行う。次に、第２のステップ６で、メタデータサービスＭＤＳは、メタデータｍｄおよび（トランザクションがサポートされる場合には）バージョン情報ｖｅｒをクライアントＣに返す。次に、第７のステップ７で、クライアントＣは、メタデータｍｄに含まれるリスト内のサーバｓ１，ｓ２のうちの１つから、タグによって、対応するデータを取得する。そして、次のステップ８で、通信先のサーバ（すなわち図２ではサーバｓ１）は、タグに対応する値Ｖ′であって、このタグの下にサーバｓ１に保存されている値Ｖ′をクライアントＣに返送する。次に、クライアントＣは、返値Ｖ′がダイジェストと一致するかどうか比較する。すなわち、クライアントＣは、値Ｖ′のフィンガープリントＨ（Ｖ′）を計算し、それを、取得したメタデータｍｄと比較する。メタデータｍｄは、値Ｖの保存されたフィンガープリントＨ（Ｖ）を含んでいる。したがって、返値Ｖ′がダイジェストと一致する場合、すなわちＨ（Ｖ）＝Ｈ（Ｖ′）の場合、読み出し操作は、正しい値Ｖとして値Ｖ′を返し、操作は完了する。
【００４９】
そうでない場合、クライアントＣは、サーバｓ１，ｓ２のいずれかが、一致する値で応答するまで、サーバ（図２ではサーバｓ１およびｓ２）のリストで反復動作する。例えば、値Ｖ′がダイジェストと一致しない場合、クライアントＣは、ｆ＋１個のサーバｓ１，ｓ２のリストのうちの第２のサーバｓ２にタグを用いて問合せを行う。するとサーバｓ２は、値Ｖ″により応答する。次に、クライアントＣは、再び、メタデータｍｄに含まれるダイジェストと、返値Ｖ″のフィンガープリントＨ（Ｖ）とを比較する。一致した場合、すなわち、Ｈ（Ｖ）＝Ｈ（Ｖ″）の場合、読み出し操作は完了する。
【００５０】
図３は、本発明の第３の実施形態による方法のステップを模式的に示している。
【００５１】
図３には、多重更新操作のステップが示されている。多重更新操作により、相異なるキーに対して全か無かでアトミック（不可分）に更新操作を実行することが可能となる。
【００５２】
図３において、クライアントＣは、複数の値Ｖ１，...，Ｖｎを、対応するタグｔａｇ１，...，ｔａｇｎとともに、ｆ＋１個のサーバｓ１，ｓ２のそれぞれに保存する。値Ｖ１，Ｖｎを保存した確認メッセージをサーバｓ１，ｓ２から受信した後、クライアントＣは、メタデータｍｄを、それぞれの値についてｍｄｉ＝（ｔａｇｉ，Ｈ（Ｖｉ），｛ｓ１，ｓ２｝）と計算する。次のステップ１１で、クライアントＣは、メタデータサービスＭＤＳと通信し、操作識別子ｏｐｉと、対応するキーｋｉ、メタデータｍｄｉおよびバージョンデータｖｅｒｉを、値Ｖ１，...，Ｖｎのすべてのインデックス１，...，ｎについて保存する。これらの情報の保存が成功した場合、次のステップ１２で、メタデータサービスＭＤＳは、対応する確認応答メッセージをクライアントＣに返送する。
【００５３】
例えば、対応する操作ｏｐｉは、条件付き書き込み操作や条件付き削除操作等を含むことが可能である。条件付き書き込みの場合、対応するバージョン情報ｖｅｒｉがメタデータｍｄｉに含められるか、または、保存されるデータに対応するメタデータｍｄｉにリンクされてメタデータサービスＭＤＳに保存される。その後、図１に関して、値は書き込み操作においてアトミックに保存される。あるバージョンｖｅｒｉがデータの現在のバージョンと一致しない場合、いずれのデータオブジェクト（すなわち値Ｖｉ）にも変更は行われない。そして、例えばエラー情報が返されてもよい。
【００５４】
条件付き更新の場合には、与えられたバージョンがデータの現在のバージョンと一致する場合にのみ、値Ｖがキーｋの下で保存される。そうでない場合には変更は行われない。そして、エラー情報がクライアントＣに返されてもよい。条件付き削除操作は、与えられたバージョンがデータの値の現在のバージョンと一致する場合にのみキーｋを削除する。そうでない場合には変更は行われない。そして、エラー情報が返されてもよい。削除操作は、削除のための値として値｛ヌル｝を書き込む書き込み操作によって実施されてもよい。
【００５５】
ビザンチン故障耐性データ複製の方法およびシステムは正確である。以下で正確性を証明するため、本発明による操作はウェイトフリーかつ線形化可能とする。ウェイトフリーとは、正しいクライアントによる操作が、他のクライアントの挙動にかかわらず常に完了することを意味する。本発明によれば、メタデータサービスがウェイトフリー操作をエクスポートし、故障するデータサーバがｆ個を超えない場合に、ウェイトフリー性が保証される。また、線形化可能性は、アトミック性としても知られており、操作が、呼び出しステップと応答ステップとの間の１時点に瞬時に行われるように見えることを意味する。本発明によれば、メタデータ操作が線形化可能である場合に線形化可能性が実現される。その場合、線形化可能性は、故障したサーバ数ｆとは独立である。
【００５６】
メタデータサービスＭＤＳに対して呼び出される低レベルの操作がウェイトフリーであると仮定すると、データサーバのうちの１つにアクセスする際に、どの操作もブロックされないことを示す必要がある。故障するのは高々ｆ個のデータサーバであるので、それぞれの更新操作は最終的にｆ＋１個の正しいサーバから応答を受信する。したがって、データサーバからの応答を待機しながら更新操作がブロックされることはない。更新操作を実行するとき、メタデータは、対応するデータをデータサーバに保存した後にのみ書き込まれ、読み出し側がメタデータを取得するときまでに、対応する更新操作は対応するタグの下でｆ＋１個のサーバのすべてにおいて、一致する値を保存している。これらのサーバのうちビザンチン故障になるのは高々ｆ個であるので、これらのｆ＋１個のサーバのうちに、対応するタグの下で一致する値Ｖを保存し最終的に読み出し側（すなわちクライアント）に応答する正しいサーバが少なくとも１つ存在する。Ｈ（Ｖ）がダイジェストに一致していることをチェックした後、読み出し操作は完了する。障害を伴う非同期実行が最悪の場合であり、その場合、一致する応答を受信する前に、読み出しはｆ＋１個のデータサーバに問合せを行う必要がある。これに対して、故障のない同期実行が通常の場合であり、その場合、ただ１つのデータサーバが読み出しによって問合せを受ける。
【００５７】
上記のように、メタデータサービスＭＤＳは、メタデータに対するすべての操作を線形化する。具体的には、読み出しおよび書き込みの操作は、メタデータへの対応する低レベルの書き込みおよび読み出しの操作の実行順序に従って線形化される。メタデータ操作の線形化可能性により、低レベル操作の履歴が、メタデータサービスＭＤＳの順序仕様を満たし、メタデータ操作の実時間順序を守る。メタデータサービスの順序仕様はシステム全体の順序仕様と等価であり、メタデータサービスは高レベル操作間の実時間先行関係を維持するので、高レベル操作が線形化可能であると結論することができる。
【００５８】
要約すると、本発明によれば、ビザンチン的にデータからメタデータを分離することにより、データサーバ数を３ｆ＋１から２ｆ＋１に削減することが可能となる。また、本発明は、２ｆ＋１個のデータサーバの集合とともにメタデータサービスを利用することにより、強い意味で一貫性のあるデータ複製を実現する。また、本発明によれば、データサーバに問合せを行う前にメタデータサービスを参照する通常の場合に、ただ１つのデータサーバを問い合わせるだけとすることが可能である。さらに、本発明によれば、等価なメタデータ操作がメタデータサービスによって公開される場合には、データ操作のエクスポートが可能である。
【００５９】
本発明は、特に以下の利点を有する。本発明によれば、ストレージサーバ取得コストおよび保守コスト、さらにストレージ容量が削減される。また、本発明によれば、読み出しパフォーマンスが改善され、ストレージサーバ数に関して線形の読み出しスケーラビリティが実現され、トランザクション型のデータアクセスが可能となる。さらに、本発明によれば、複製コストが３ｆ＋１個のサーバから２ｆ＋１個だけのデータサーバへと実質的に削減可能であり、上記のような読み出しスケーラビリティが得られる。通常は読み出し操作中にアクセスされるデータサーバは１つだけであるので、保存されるデータオブジェクトがサーバ間で均等に分配される場合には、各サーバが被る負荷は１／｜Ｓ｜となる。その結果、容量は｜Ｓ｜（すなわちデータサーバ数）倍になる。
【００６０】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
2016517605.tif 000003
【図２】
2016517605.tif 000004
【図３】
2016517605.tif 000005
【国際調査報告】
2016517605.tif 000006
2016517605.tif 000007