(57)【要約】  オンライントランザクション処理システムで実装される方法が開示されている。方法は、トランザクション処理からの読み出し要求に応じて、トランザクションログを読み出すことと、トランザクションログにアクセスせずにストレージ内に記憶されたデータを読み出すことと、ストレージ内のデータおよびトランザクションログを用いて現在のスナップショットを構成することとを含む。方法は、トランザクション処理からの書き込み要求に応じて、トランザクションログにアクセスすることによってトランザクションをコミットすることをさらに含む。方法は、コミットにおける更新をストレージ内のデータに非同期に伝搬することをさらに含む。トランザクションコミットは、コミットをトランザクションログに適用することで、成功となる。他の方法およびシステムもまた開示されている。
2014532919.tif 000002
【特許請求の範囲】
【請求項１】
オンライントランザクション処理システムにおいて実行される方法であって、
トランザクション処理からの読み出し要求に応じて、トランザクションログを読み出し、前記トランザクションログにアクセスせずにストレージ内に記憶されたデータを読み出し、前記ストレージ内のデータおよび前記トランザクションログを用いて、現在のスナップショットを構成し、
前記トランザクション処理からの書き込み要求に応じて、前記トランザクションログにアクセスすることによってトランザクションをコミットし、
前記コミットにおける更新を前記ストレージ中の前記データに非同期的に伝搬し、
前記トランザクションコミットは、前記コミットを前記トランザクションログに適用することで、成功とすることを含む方法。
【請求項２】
請求項１に記載の方法において、
前記ストレージ内の前記データに伝搬された前記更新と対応するトランザクションログデータを破棄することをさらに含み、
前記トランザクションログのサイズは、前記ストレージ内の前記データのサイズよりも十分に小さく保たれる、方法。
【請求項３】
請求項１または２に記載の方法において、
トランザクションログマネージャは、
前記トランザクションログを管理し、
キーバリューオブジェクトのセットを含むデータコレクションと、
コミットの全オーダーを与える値を含むタイムスタンプと、
前記タイムスタンプと関連付けられた、１または複数の書き込み動作のシーケンスを含むログエントリーと、
同期時間と、
前記同期時間の後に開始して特定の時間に終了する、１または複数の書き込み動作のシーケンスを含むスナップショットと、
チェック述語との少なくとも１つを使用し、
前記ストレージは、タイムスタンプが前記同期時間と等しいかまたは古い、１または複数の書き込み動作を導入し、前記チェックは、競合するログエントリがない場合に成功とされることを特徴とする、方法。
【請求項４】
請求項１ないし３のいずれか１項に記載の方法において、
前記オンライントランザクション処理システムは、トランザクションログマネージャと、クエリ実行エンジンと、データアップデータとを含み、
前記トランザクションログマネージャは、前記トランザクションログを管理し、
前記クエリ実行エンジンは、前記読み出し要求および書き込み要求のそれぞれに従って、前記トランザクションログの読み出しを開始し、前記トランザクションをコミットし、
前記データアップデータは、書き込み動作を取得し、前記書き込み動作を前記ストレージ内の前記データに適用することを特徴とする、方法。
【請求項５】
請求項４に記載の方法において、
前記データアップデータは、前記トランザクションログマネージャに、前記書き込み動作が適用されることを通知し、
前記トランザクションログマネージャは、前記情報を受信すると、前記トランザクションログを破棄することを特徴とする、方法。
【請求項６】
オンライントランザクション処理のためのシステムであって、
トランザクションログと、
ストレージ内に記憶されたデータとを含み、
トランザクション処理からの読み出し要求に応じて、前記システムは、トランザクションログを読み出し、前記トランザクションログにアクセスせずにストレージ内に記憶されたデータヲ読み出し、前記ストレージ内の前記データと前記トランザクションログとを用いて現在のスナップショットを構成し、
前記トランザクション処理からの書き込み要求に応じて、前記システムは、前記トランザクションログにアクセスすることでトランザクションをコミットし、前記システムは、前記コミットにおける前記ストレージ内の前記データに更新を非同期的に伝搬し、
前記トランザクションコミットは、前記コミットが前記トランザクションログに適用されると、成功とされることを特徴とするシステム。
【請求項７】
請求項６に記載のシステムにおいて、
前記システムは、前記ストレージ内の前記データに伝搬された前記更新と対応するトランザクションログデータを破棄し、
前記トランザクションログのサイズは、前記ストレージ内の前記データのサイズよりも十分小さく保たれることを特徴とする、システム。
【請求項８】
請求項６または７に記載のシステムにおいて、
トランザクションログマネージャは、
前記トランザクションログを管理し、
キーバリューオブジェクトのセットを含むデータコレクションと、
コミットの全オーダーを与える値を含むタイムスタンプと、
前記タイムスタンプと関連付けられた、１または複数の書き込み動作のシーケンスを含むログエントリーと、
同期時間と、
前記同期時間の後に開始して特定の時間に終了する、１または複数の書き込み動作のシーケンスを含むスナップショットと、
チェック述語との少なくとも１つを使用し、
前記ストレージは、タイムスタンプが前記同期時間と等しいかまたは古い、１または複数の書き込み動作を導入し、前記チェックは、競合するログエントリがない場合に成功とされることを特徴とするシステム。
【請求項９】
請求項６ないし８のいずれか１項に記載のシステムにおいて、
前記システムは、トランザクションログマネージャと、クエリ実行エンジンと、データアップデータとを含み、
前記トランザクションログマネージャは、前記トランザクションログを管理し、
前記クエリ実行エンジンは、前記読み出しおよび書き込み要求のそれぞれに従って、前記トランザクションログの読み出しを開始し、前記トランザクションをコミットし、
前記データアップデータは、書き込み動作を取得し、前記書き込み動作を前記ストレージ内の前記データに適用することを特徴とするシステム。
【請求項１０】
請求項９に記載のシステムにおいて、
前記データアップデータは、前記書き込み動作が適用されることを前記トランザクションログマネージャに通知し、
前記トランザクションログマネージャは、情報を受信すると、前記トランザクションログを破棄することを特徴とするシステム。
【請求項１１】
オンライントランザクション処理システム中で用いられる、トランザクションログマネージャ内で実行される方法であって、
トランザクション処理からの読み出し要求に応じて、トランザクションログを読み出すことと、
前記トランザクション処理からの書き込み要求に応じて、前記トランザクションログにアクセスすることによってトランザクションをコミットすることと、
前記コミット内で前記ストレージ内の前記データに更新を非同期的に伝搬することと、を含み、
前記オンライントランザクション処理システムは、ストレージ内に記憶されたデータを、前記トランザクションログにアクセスせずに読み出し、前記ストレージ内の前記データと前記トランザクションログとを用いて現在のスナップショットを構築し、
前記トランザクションコミットは、前記トランザクションログに前記コミットを適用すると成功とされることを特徴とする、方法。
【請求項１２】
請求項１１に記載の方法であって、
前記ストレージ内の前記データに伝搬された前記更新に対応するトランザクションログデータを破棄することをさらに含み、
前記トランザクションログのサイズは、前記ストレージ内の前記データよりも十分小さいことを特徴とする、方法。
【請求項１３】
請求項１１または１２に記載の方法であって、
前記トランザクションログマネージャは、
キーバリューオブジェクトのセットを含むデータコレクションと、
コミットの全オーダーを与える値を含むタイムスタンプと、
前記タイムスタンプと関連付けられた、１または複数の書き込み動作のシーケンスを含むログエントリーと、
同期時間と、
前記同期時間の後に開始して特定の時間に終了する、１または複数の書き込み動作のシーケンスを含むスナップショットと、
チェック述語との少なくとも１つを使用することによって前記トランザクションログを管理し、
前記ストレージは、タイムスタンプが前記同期時間と等しいかまたは古い、１または複数の書き込み動作を導入し、前記チェックは、競合するログエントリがない場合に成功とされることを特徴とする方法。
【請求項１４】
請求項１１ないし１３のいずれか１項に記載の方法であって、
前記オンライントランザクション処理システムは、クエリ実行エンジンおよびデータアップデータを含み、
前記クエリ実行エンジンは、前記読み出しおよび書き込み要求のそれぞれに従って、前記トランザクションログの読み出しを開始し、前記トランザクションをコミットし、
前記データアップデータは、書き込み動作を読み出し、前記ストレージ内の前記データに前記書き込み動作を適用することを特徴とする、方法。
【請求項１５】
請求項１４に記載の方法であって、
前記データアップデータは、前記トランザクションマネージャに前記書き込み動作が適用されることを通知し、
前記トランザクションマネージャは、情報を受信すると、前記トランザクションログを破棄することを特徴とする、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２０１１年１０月２６日に出願され、「トランザクションログ管理に基づく弾性トランザクションサービス」というタイトルの米国仮出願第６１／５５１５０２号の利益を主張し、この内容は参照によって本出願に取り込まれる。
【０００２】
本発明は、オンライントランザクション処理（ＯＬＴＰ：ＯｎＬｉｎｅ  Ｔｒａｎｓａｃｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ）に関し、より具体的には、ＯＬＴＰの弾性に関する。
【背景技術】
【０００３】
ＯＬＴＰワークロードの弾性を達成するために、下記の問題を解決することは有益であるだろう。
【０００４】
一貫性保証に関する柔軟性：従来のリレーショナルデータベース管理システム（ＲＤＢＭＳ：Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ）は、完全な原子性（Ａｔｏｍｉｃｉｔｙ）、一貫性（Ｃｏｎｓｉｓｔｅｎｃｙ）、独立性（Ｉｓｏｌａｔｉｏｎ）、および永続性（Ｄｕｒａｂｉｌｉｔｙ）（ＡＣＩＤ）特性をデータセット全体で提供する。このグローバルＡＣＩＤは非常に強力であるのに対し、システムを拡張することは困難になり、そしてそれは多くの場合、ほとんどのＯＬＴＰアプリケーションについてやりすぎである。例えば、典型的なウェブアプリケーションは、多数のユーザにサービスを提供するが、限られた方法においてＡＣＩＤ特性を必要とする。
【０００５】
異なるスケーリング係数に対する弾性：システムは、拡張したり縮小したり（例えばサーバリソースの追加や削除）することによって、変化するワークロードに適合することができる。ＯＬＴＰワークロードは、３つのスケーリングの要素：（１）データサイズ、（２）１秒当たりのクエリーの数、および（３）１秒当たりのトランザクションの数を有している。これらは密接に関連しているけれども、異なるワークロードは、これらの要素について異なる増大パターンを示している。全てのクエリーが１つのトランザクションの方法で実行されるわけではないので、クエリースループットの増大は、必ずしもトランザクションスループットの増大を意味するとは言えない。様々なワークロードの挙動に適応するため、これらの３つの要素の１つ以上に弾性を有することが望ましい。
【０００６】
キー（ｋｅｙ）−バリュー（ｖａｌｕｅ）ストアは、上記の問題に取り組むための最先端のアプローチである。データは、キー−バリューオブジェクトのセットに分割されて、サーバのクラスタ上でキーによって分配される。様々なキー−バリューストアが、単一のキー−バリューオブジェクトを読み書きするための、様々な一貫性保証を提供する。いくつかのシステムでは、単一のキー（例えば、それらが単一のキー−バリューオブジェクト上のトランザクションをサポートする）上でＡＣＩＤ特性を保証する。そのようなキー−バリューストアは、一貫性の保証の柔軟性と、ある程度の弾性を達成している。しかしながら、トランザクションとデータは密接に結合されるという制約がある。データおよびトランザクションは、同じキーに関連づけられ、高価な分散トランザクションプロトコルを用いることなくトランザクションがローカルに発生するように、共に分配される。
【０００７】
階層型アーキテクチャ
【０００８】
通常、トランザクションは、次に説明する階層型アーキテクチャの結果、トランザクション処理からの全ての読み出し／書き込み動作を制御するために、クエリの実行とストレージとの間で管理されている。
【０００９】
このアーキテクチャ内でトランザクションの弾性とデータの弾性とを分離する関連技術がある。例えば、Ｄｅｕｔｅｒｏｎｏｍｙ［１］は、クラウド中におけるデータ管理を、トランザクションコンポーネントとデータコンポーネントとに切り離す。しかしながら、階層型アーキテクチャは、全ての読み出し／書き込み要求がトランザクションマネージャを経由していることを前提としている。我々のアプローチは、トランザクションログと呼ばれるコンポーネントを提供し、その結果、トランザクションコンポーネントを用いて、クエリー実行エンジンのための柔軟性を達成する。
【００１０】
その他の典型的なアーキテクチャは、マスターとスレーブのレプリカを持つことであり、クエリー実行エンジンに一貫性の要求に基づいて選択させることである。
【００１１】
伝統的なＲＥＢＭＳｓの非同期レプリケーションは、限られた方法で弾性を支援するために使用されている。システムは、新たなスレーブノードを動的に追加する（すなわち、スケールアウト）ことができる。しかしながら、スレーブは、リードオンリーのトランザクションのために用いられるかもしれず、読み出し書き込みトランザクションのためには弾性がない。
【００１２】
ＰＮＵＴＳ［３］は、マスター−スレーブアプローチを採用するキー−バリューストアである。マスターデータは、キー−バリューオブジェクトとして分配され、それらが非同期で複製される。クライアントは、要求される整合性に応じて、レプリカを選択することができる。しかしながら、キー−バリューオブジェクト上のトランザクションは、データと密接に結合されている。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】［１］Justin J. Levandoski, David B. Lomet, Mohamed F. Mokbel, Kevin Zhao, Deuteronomy: Transaction Support for Cloud Data, CIDR 2011, Fifth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 9-12, 2011
【非特許文献２】［２］Sudipto Das, Divyakant Agrawal, Amr El Abbadi, ElasTraS: An Elastic Transactional Data Store in the Cloud, USENIX HotCloud 2009.
【非特許文献３】［３］B. F. Cooper et al. PNUTS: Yahool's hosted Data Serving Platform. PVLDB, 1(2): 1277-1288, Aug. 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
我々は、（１）トランザクションログを用いるトランザクションプロトコルおよび（２）トランザクションログをそれらのキーにより分配するトランザクションログマネージャとのうち少なくとも１つを提案する。
【００１５】
本発明の目的は、オンライントランザクション処理（ＯＬＴＰ）における弾性を達成することである。
【課題を解決するための手段】
【００１６】
本発明の１つの観点は、オンライントランザクション処理システムにおいて実装される方法を含む。方法は、トランザクション処理からの読み込み要求に応じて、トランザクションログを読み出すことと、トランザクションログにアクセスすることなくストレージに格納されたデータを読み出すことと、ストレージ中のデータおよびトランザクションログを用いて現在のスナップショットを構成することとを含む。この方法は、トランザクション処理からの書き込み要求に応じて、トランザクションログにアクセスすることでトランザクションをコミットすることをまた含む。この方法は、ストレージ内のデータへのコミットにおける、非同期に更新を反映（ｐｒｏｐａｇａｔｅ）することをまた含む。トランザクションコミットは、トランザクションログにコミットを適用することで成功となる。
【００１７】
本発明の他の観点は、オンライントランザクション処理のためのシステムを含む。システムは、トランザクションログと、データを格納するストレージとを含む。トランザクション処理からの読み込み要求に応じて、システムはトランザクションログを読み込み、トランザクションログにアクセスせずにストレージに格納されたデータを読み込み、ストレージ内のデータおよびトランザクションログを用いて、現在のスナップショットを構築する。トランザクション処理からの書き込み要求に応じて、システムは、トランザクションログにアクセスすることによって、トランザクションをコミットする。システムは、ストレージ内のデータへのコミットにおける更新を非同期に反映する。トランザクションコミットは、トランザクションログにコミットを適用することで成功となる。
【００１８】
本発明の他の観点は、オンライントランザクション処理システム中で用いられるトランザクションログマネージャにおいて実装される方法を含む。この方法は、トランザクション処理からの読み込み要求に応じて、トランザクションログを読み込むことを含む。方法は、トランザクション処理からの書き込み要求に応じて、トランザクションログにアクセスすることで、トランザクションをコミットすることをまた含む。この方法はまた、ストレージ内のデータへのコミットにおける更新を非同期に反映することをまた含む。オンライントランザクション処理システムは、トランザクションログにアクセスせずにストレージ内のデータを読み込み、ストレージ内のデータおよびトランザクションログを用いて、現在のスナップショットを構築する。トランザクションコミットは、トランザクションログにコミットを適用することで成功となる。
【図面の簡単な説明】
【００１９】
【図１】弾性トランザクション管理システムを示している。
【図２】トランザクションに対する提案するアプローチを示している。
【図３】マスタースレーブレプリケーションを用いる、関連するアプローチを示している。
【図４】システムコンポーネントを示している。
【図５】トランザクションログマネージャのクラスターを示している。
【図６】ＳＹＮＣ時間を示している。
【図７】ＳＮＡＰＳＨＯＴ時間を示している。
【図８】コミット中の検査述語（ｐｒｅｄｉｃａｔｅｓ）を示している。
【図９】パーティションを同期するための相互作用を示している。
【図１０】ログ検索（ｒｅｔｒｉｅｖａｌ）を示している。
【図１１】パーティションマッピングの独立性を示している。
【図１２】メッセージ処理アーキテクチャを示している。
【図１３】送信メッセージバッファを示している。
【図１４】受信メッセージバッファを示している。
【図１５】保証されたメッセージ配信を示している。
【図１６】Ｂ−ｌｉｎｋツリーインデックスおよび相反する書き込みの例を示している。
【図１７】ツリー毎の単一のトランザクションログを示している。
【図１８】ノードを分割する場合の分割トランザクションを示している。
【図１９】ノード分割のシーケンスを示している。
【図２０】異常な書き込みに起因する一時的な不一致を示している。
【図２１】繰り返された書き込みに起因する異常（ａｎｏｍａｌｙ）を示している。
【図２２】トランザクションログのデータ構造を示している。
【発明を実施するための形態】
【００２０】
我々は、トランザクションログを利用したデータ上で、トランザクションを管理する新たな方法を開示している。図１を参照。
【００２１】
システムは、トランザクションログと呼ばれる一連の動作のセットを生成するために、同時トランザクションを管理する。各トランザクションログは、ストレージ内のデータの互いに素な集合を更新するために適用される。ストレージが更新される前に書き込まれ、永続的なものとされるため、トランザクションログは、ＷＡＬ（Ｗｒｉｔｅ−Ａｈｅａｄ  Ｌｏｇ）としてみることができる。しかしながら、典型的なＷＡＬからの主な違いは、ログと共にストレージが更新される前に、トランザクションログに適用された場合、トランザクションコミットが成功となることである。トランザクションがコミットされたとき、クライアント（クエリー実行エンジン）は、ストレージ内に最新の値が見当たらない場合がある。「現在の（ｃｕｒｒｅｎｔ）」データのスナップショットを見るために、クライアントは、ストレージ中のデータだけでなくトランザクションログの状態も見る必要がある。
【００２２】
違いは、トランザクションを達成するためにトランザクションログを使用することである。トランザクション処理の流れ（プロトコル）は、図２に描かれている。
【００２３】
（１）トランザクション処理は、トランザクションログなしでデータに直セスアクセスすることができる。そして（２）トランザクション処理は、関係するデータストアなしでトランザクションをコミットすることができる。コミット中の更新は、非同期にデータに反映される。
【００２４】
ある意味では、トランザクションログは、データベースのマスターであり、ストレージは、非同期なレプリカであると見ることができる。この解釈は、概念的に正しい。しかしながら、実際のシステムアーキテクチャは、このマスター−スレーブ関係とは異なる。トランザクションログは、ストレージに適用されない更新に対する耐久性に寄与する。我々は、マスターデータの耐久性の責任でなく、トランザクションログをより計量な方法で実装することができるため、トランザクションログとマスターデータとの間のこの差異は重要である。多くの用途では、保存することができるトランザクションログのサイズは、データセットのサイズよりもずっと小さい。トランザクションログデータのサイズは、例えば、ストレージに反映されたトランザクションログデータを破棄することにより、小さく抑えることができる。キーに関連するデータが小さい場合、拡張／縮小（データマイグレーションを含む）がより効果的であることに注意されたい。図２および３を参照。
【００２５】
システムは、キー−バリューストア上に分布しているデータセットと同様に、ノードのクラスター上に分布している、多くのトランザクションログを管理している。図４（Ａ）を参照。
【００２６】
クエリー実行エンジンは、ストレージおよびトランザクションログマネージャにアクセスすることで、アプリケーションのクエリーを実行する。実行中、主にストレージからデータ（例えば、テーブルレコード、インデックス、またはディスクページ）を読み込む（ｒｅａｄ）。コミットするとき、トランザクションログマネージャに、トランザクション中の全ての書き込み（ｗｒｉｔｅ）動作を提供する。これらの書き込み動作は、データアップデータによって、非同期でストレージに適用される。
【００２７】
クエリー実行エンジンの１つのタイプは、リレーショナルワークロードのＳＱＬエンジンである。我々は、ＯＬＴＰワークロードのための弾性を達成するための宣言型のアプローチを提供するマイクロシャーディング（ｍｉｃｒｏｓｈａｒｄｉｎｇ）と呼ばれる技術を提案した。このモデルにおいて、マイクロシャーディングは、データベースがＡＣＩＤ特性を提供する論理データパーティションである。各マイクロシャードについてのトランザクションログを用いることによって、我々は、我々がこの文書で提案しているシステム上で効率的にマイクロシャーディングを実装することができる。
【００２８】
さらに、このアーキテクチャは、非リレーショナルクエリー実行エンジンに適用することも可能である。トランザクションマネージャは、一般的に、キーバリューストア上で、トランザクションを非リレーショナルワークロードに導入するために用いるのに十分である。
【００２９】
トランザクションログは、図６、７、および８において可視化されている。このトランザクションログは、次の２つのステップ（トランザクションスタートおよびコミット）を可能にする。
Snapshot start(LogId id); 
Boolean commit(LogId id, Check check, Write[]writes)
【００３０】
１．実装
【００３１】
（１）トランザクションログマネージャ
【００３２】
トランザクションログマネージャは、所定の割り当て（ｄｉｓｔｒｉｂｕｔｅ）方法でトランザクションログを処理するサーバのクラスターを有する。クラスターは、トランザクションログのキーから対応するクラスターノードのＩＤへのマッピングを保持するキーバリューストアの技術を採用する。図５を参照。
【００３３】
具体的には、ダイナモ（またはそのオープンソース実装ヴォルデモート）と同じマッピング方式を採用している。キーは、特定のハッシュ関数によって小さなパーティションに分割され、一次元空間にマッピングされる。パーティションからクラスタノードへのマッピングは、弾性的に維持されている。パーティションは、あるノードから別のノードに移動することができる。
【００３４】
ダイナモとは異なり、我々は、単一のマスターのパーティションを許容する。全てのトランザクション処理は、マスターパーティションを有する１つのノードで処理されてもよい。
【００３５】
Ｐａｘｏｓプロトコルを拡張することによって、効率的に一貫性のあるレプリケーションを維持する技術が提案されている。例えば、我々は、そのような技術を、ノード間のパーティションのオンラインリバランスを達成するために用いることができる。
【００３６】
（２）メッセージングをサポートする拡張アーキテクチャ
【００３７】
単一のトランザクションの外部で非同期アップデートを実施するために、我々は、メッセージングの仕組みが必要になる場合がある。例えば、マイクロシャーディングモデルにおいて、我々が非トランザクションキーにインデックスを維持したい場合、このインデックスと対応するテーブルの更新は、単一のトランザクションで実行することができないため、メッセージングを通じて維持され得る。
【００３８】
この特許出願において、我々は、まず簡単のため、メッセージングのないシステムについて議論する。次に我々はメッセージングをサポートするシステムへの拡張について説明する。
【００３９】
２．クライアントＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）概要
【００４０】
以下は、トランザクションログマネージャによって提供されるクライアントＡＰＩのインタフェースである。このセクションでは、我々はこのインタフェースの背景にある高レベルのアイデアを説明する。我々は、詳細については後のセクションで議論するだろう。我々はまた、後に、非同期メッセージングをサポートするためにこのインタフェースを拡張するだろう。
interface TransactionLogManager {
// Transaction start and commit
Snapshot start(logId id);
long starTime(LogId id);
boolean commit(LogId id, Check check, Write[] writes);
// Storage synchronization
void sync(LogId id, long timestamp);
Node[] getNodesQ;
Iterable<Entry<LogId, LogEntry[]>> getLog(int partitionId);
}
【００４１】
（１）クエリ実行エンジンのためのＡＰＩ
【００４２】
トランザクションマネージャは、起動し、トランザクションをコミットするための動作を有するクエリ実行エンジンを提供している。
【００４３】
実際、トランザクションを開始することは、トランザクションログの現在の状態を取得するだけであって、状態を変更しない（例えば、トランザクションログマネージャは、トランザクションの開始を覚えていない）。
【００４４】
コミット動作は、例えば、オプティミスティック並行制御を可能にするアトミックチェックアンドプット動作である。
【００４５】
開始およびコミットの両方は、他のプロセス（例えば他のクエリ実行エンジン）が動作をブロックしないことを意味する非ブロッキング動作である。
【００４６】
（２）データアップデータのためのＡＰＩ
【００４７】
アップデータは、継続的にログデータを取得し（書き込み動作）、それらをストレージに適用することができる。トランザクションログが適切な場合はいつでも切り捨てられることができるように、それらの動作が適用されていることをトランザクションログマネージャに知らせることができる。
【００４８】
アップデータは、クエリ実行エンジンに対して、非同期にこのタスクを実行することができる。トランザクションログのサイズが無制限である場合、アップデータは、クエリ実行エンジンをブロックすることはない。ログサイズに制限があり、トランザクションログが満杯になった場合、トランザクションコミットは（ブロックされずに）失敗する。アップデータの動作もまた非ブロッキングである。空のトランザクションログを読むと、書き込み動作を待たずに、すぐに空の結果を返す。
【００４９】
３．データタイプ
【００５０】
このセクションは、トランザクションログマネージャが用いるデータ構造について説明する。
【００５１】
（１）キーバリューデータコレクション
【００５２】
データは、データコレクションのセットとして示される。データコレクションは、キーバリューオブジェクトのセットであり、固有の名称を有する。トランザクションマネージャがそれを意識する必要はないが、データコレクションは、データベースまたはインデックスのテーブルを示すかもしれない。
【００５３】
キーは個々のコレクション内で固有である。このように、キーバリューオブジェクトを識別するために、我々は、名称とキーのペアを指定する必要がある。キーは、トランザクションマネージャに与えられたときに、バイト配列としてシリアライズされる。
【００５４】
値もまた、バイト配列として与えられる。トランザクションマネージャは、値の内容を解釈する必要はない。
【００５５】
（２）トランザクションログ
【００５６】
トランザクションログは、名称とキーのペアで識別される。
【００５７】
名称は、同じポリシーで管理されるトランザクションログのコレクション（クエリ実行エンジンPartigleはこれをトランザクションクラスネームとして用いる。）を識別する。名称の型は、Stringである。将来的には、トランザクションログマネージャは、この名称を特定のトランザクションログのセット（例えば、コミットを選択的に有効化または無効化）にアクセスするために用いるマネジメント動作を提供するかもしれない。
【００５８】
キーは、トランザクションログの名称付られたコレクション内で固有なトランザクションログの識別子である。このように、トランザクションログを識別するために、我々は、名称およびキーのペアを指定する必要がある。キーの型はバイト配列である。クエリエンジンは、様々なデータタイプをこのバイト配列にエンコードするが、トランザクションマネージャは、それを意識する必要はない。
interface Log Id{
String getNameO;
byte[] getKey();
}
【００５９】
このログＩＤからパーティションＩＤへのマッピングは、トランザクションログマネージャの内部ロジックにより実行される。我々は、与えられたログＩＤに対するパーティションＩＤを調べるために、追加のＡＰＩを考慮することができるが、これはこのドキュメントでカバーする機能を実装する必要はない。
【００６０】
タイムスタンプ
【００６１】
タイムスタンプは、コミットの全オーダーを与える値である。タイムスタンプは、各トランザクションログについて定義され、維持されており、各コミットごとにインクリメントされる。タイムスタンプを異なるトランザクションログ間で比較することは何の意味もない。
【００６２】
現在の設計では、タイムスタンプは、長整数（ｌｏｎｇ  ｉｎｔｅｇｅｒ）として表されている。値は最大値に達した場合、トランザクションマネージャは、トランザクションログを再起動（このトランザクションログをオフラインにしてタイムスタンプをリセット）する必要がある。トランザクションログをオフラインにするために、まず新たなコミットを無効化し（読み取り専用コミットを除く）、アップデータがログ内の全ての書き込み動作を同期させるのを待つ。
【００６３】
ログエントリー
【００６４】
トランザクションログは、タイムスタンプと関連した書き込み、一連の動作を維持する。書き込みトランザクションのコミットのそれぞれについて、新たなログエントリーがシーケンスに追加される。アップデータは、ログエントリーのこのシーケンスをスキャンし、書き込み動作をストレージに適用する。
interface LogEntry {
long getTimestampO;
Write getWrite();
}
【００６５】
ログエントリーは、タイムスタンプに関連する書き込み動作である。タイムスタンプは、各トランザクションログについて維持されている論理値である。
interface Write{
byte[] getNameO;
byte[] getKey();
byte[] getValue();
}
【００６６】
書き込み動作は、３つのアイテムから成っている。（１）データコレクションの名称、（２）データオブジェクトのキー、および（３）データオブジェクトの値
【００６７】
我々は、キーバリューオブジェクトの状態は、最新の書き込み動作によって決定されるものと仮定する。これは、キーバリューオブジェクトの全値を上書きする書き込み動作について当てはまる。
【００６８】
ＳＹＮＣ時間
【００６９】
トランザクションログは、ＳＹＮＣ（同期）と呼ばれるように、タイムスタンプを維持する。これは、タイムスタンプが等しいかＳＹＮＣよりも古い全ての書き込み動作がストレージに組み込まれていることを意味する。
【００７０】
トランザクションログマネージャは、ＳＹＮＣの後の書き込み動作の耐久性に責任がある。ＳＹＮＣよりも古いログエントリーを破棄することもできるが、いくつかの期間において、古いエントリーを覚えている可能性がある。検査述語のセクションでわかるように、古いエントリーを覚えていることは、コンフリクト検出の偽陽性の可能性を低減し、それは正確性には影響しないが、パフォーマンスを低下させる。図６を参照。
【００７１】
スナップショット
【００７２】
スナップショットは、ＳＹＮＣの次に開始して特定の時間に終了する書き込みのシーケンスである。我々はこの終了時間をスナップショットのタイムスタンプとして定義する。このスナップショット時間は、ＳＹＮＣからＣＵＲＲＥＮＴの間のいつでもよい（ＳＮＡＰＳＨＯＴ  ｅ［ＳＹＮＣ，  ＣＵＲＲＥＮＴ］）。書き込みのシーケンスが空である場合（例えば、ＳＹＮＣ＝ＣＵＲＲＥＮＴのとき）、スナップショット時間は、ＳＹＮＣと等しくなる。図７を参照。
interface Snapshot {
long getTimestampO;
Write [] getWritesO;
}
【００７３】
トランザクションがトランザクションログ上で起動すると、クエリ実行エンジンは、最近の書き込み動作を知るために、スナップショットを取得することができる。
Snapshot start(LogId id);
【００７４】
トランザクションログマネージャは、ＳＹＮＣとＣＵＲＲＥＮＴの間の全ての書き込み動作を与えるためにその時点でＣＵＲＲＥＮＴ時間を用いることができる。しかしながら、この動作は、新たな書き込み動作をコミットするために、他のトランザクションプロセスをブロックしないことに注意せよ。そしてスナップショット時間は、クエリ実行エンジンがその結果を受信したときには、もはやＣＵＲＲＥＮＴ時間ではない。
【００７５】
実際、トランザクションログマネージャは、スマップショット時間としてＳＹＮＣからＣＵＲＲＥＮＴの間のどの時間を用いることもできる。ＳＹＮＣおよび空の書き込みシーケンスを返すことさえできる。返されるスナップショットのサイズを制限することができる。選択は、トランザクションログマネージャのために、パフォーマンスチューニングパラメータとして残されている。
【００７６】
オプションの重複排除：同じキーバリューオブジェクトについて複数の動作がある場合、トランザクションログマネージャは、古い動作を排除して最新の１つを維持することができる。この重複排除はオプションであることに注意せよ。クエリ実行エンジンは、スナップショットを同じキーバリューオブジェクトに対する複数の動作を含むことができる（年代順に）シーケンスとして解釈することができる。トランザクションログマネージャが重複を排除できるかどうかは、パフォーマンスチューニング（ＣＰＵ時間対メッセージサイズ）の問題である。
【００７７】
検査述語
【００７８】
検査は、ログエントリーの競合がない場合、成功である。トランザクションがそれを読み込んだ後、キーバリューオブジェクトを書き込む場合、ログエントリーは、コミットしているトランザクションと競合する。
【００７９】
検査は、タイムスタンプとリードセットの集合として表される。タイムスタンプの値は、トランザクションが起動されたとき（ＳＹＮＣ時間またはスナップショット時間）に与えられる。
interface Check{
long getTimestampO;
Read[] getReadSetsQ;
}
【００８０】
リードセットは、同じコレクション中のキーのセットからなる。
interface ReadSet {
byte[] getNameO;
byte[] [] getKeys();
}
【００８１】
検査を考慮すると、トランザクションマネージャは、Ｔｃが検査のタイムスタンプである場合、リードセットと競合する、ＴｃとＣＵＲＲＥＮＴの間に書き込み動作があるか否かを検査する。
【００８２】
ＴｃがＯＬＤＥＳＴよりも古い場合、トランザクションマネージャは、競合がないことを確認することができない。検査の結果は、このケースでは誤り（ｆａｌｓｅ）となる。図８を参照。
【００８３】
再起動の影響：トランザクションが再起動された場合、トランザクションログマネージャは、ＣＵＲＲＥＮＴよりも新しい検査を観察することができる。これは、トランザクションが再起動の間に生じた場合に発生することがある。このケースでは、このタイムスタンプは、ＯＬＤＥＳＴよりも古いと考えることができる。コミットの結果は、したがって、誤りである。
【００８４】
（３）ノード情報
【００８５】
トランザクションログマージャは、パーティションおよびクラスターノード間のマッピングの現在の情報を提供する。ノードは、ノードＩＤ、ノードのＵＲＬ、およびパーティションＩＤのセットを含む、各クラスターノード上の情報のコンテナである。
interface Node{
int getID();
String getUrlQ;
int[] getPartitionIdsQ;
}
【００８６】
４．トランザクション管理
【００８７】
このセクションでは、我々は、トランザクションを実行するためのクエリ実行マネージャのトランザクションログマネージャのインタフェースを説明する。
【００８８】
（１）トランザクション開始
【００８９】
クエリ実行エンジンがトランザクションを開始したとき、次の動作によって、ＳＹＮＣ時間を取得することができる。
long startTime(LogId id);
【００９０】
ＳＹＮＣ時間の前に書き込むことを保証されたストレージは、データに適用され、新しい値がクライアント（クエリ実行エンジン）で使用できる。このように、このトランザクション開始後に読み込まれるキーバリューオブジェクトについて、我々は、それらの値がＳＹＮＣよりも古くないことを保証することができる。このため、コミット要求における検査のために使用されるこのタイムスタンプをＴｃと呼ぶことにする。
【００９１】
或いはその代わりに、クエリ実行エンジンは、トランザクションを以下の動作によって開始することができる。
Snapshot start(LogId id);
【００９２】
結果として、タイムスタンプ（これをＴｓと呼ぶことにする）と、ＳＹＮＣおよびＴｓの間にある書き込み動作のシーケンスとを取得する。（トランザクションが開始した後）これらの動作をストレージから検索されたデータに適用することによって、我々は、これらの値がＴｓよりも古くないことを保証することができる。このケースでは、我々は、このタイムスタンプをＴｃとして用いる。
【００９３】
我々がキーバリューオブジェクトの状態と仮定するリコールは、最新の書き込み動作により決定される。スナップショットは、データアップデータによって既にデータに適用された動作を含む。しかし、同じ動作を再び更新されたデータに適用することは、この仮定のために安全である。
【００９４】
（２）コミット要求
【００９５】
トランザクションの実行中は、クエリ実行エンジンは、全ての書き込み動作をバッファリングして、潜在的に他のトランザクションと競合する全ての読み込みセットを覚えることができる。クエリ実行エンジンは、読み込みセットから読み込み動作のいくつかを除外することによって、非分離読み込み（例えば、コミットされた読み込み）を許容して、（直列可能から）トランザクション分離を緩和することを決定することができる。この自由は、責任が伴う。望ましい分離のための適切な検査（タイムスタンプおよび読み込みセット）を準備することは、クエリ実行エンジンの責任である。
【００９６】
コミットが要求される場合、覚えている読み込みセットおよびタイムスタンプＴｓを用いる検査が準備される。コミット要求がｔｒｕｅを返す場合、トランザクションは正常にコミットされる。それ以外の場合は、トランザクションはリジェクトされる。クエリ実行エンジンは、もう一度やり直すか、またはトランザクションを中止する。
boolean commit(LogId id, Check check, Write[] writes);
【００９７】
５．ストレージ同期
【００９８】
このセクションでは、我々は、ストレージをトランザクションログ中のコミットされた書き込み動作に同期させるために、アップデータがどのようにしてトランザクションログマネージャのインタフェースを用いるか説明する。
【００９９】
（１）ログ取得
【０１００】
ログ取得は、トランザクションログのパーティションごとに行われる。パーティションＩＤのセットを取得するために、アップデータは、パーティション情報を提供するトランザクションログマネージャのＡＰＩを用いることができる。
Node[] getNodes();
【０１０１】
各ノードオブジェクトについて、我々は、現在ノードに割り当てられているパーティションＩＤのセットを取得することができる。
int[] partitionIDs = node.getPartitionIdsQ;
【０１０２】
パーティションとノードの間のマッピングは、ストレージ同期を正確に動作するためには要求されず、パフォーマンスチューニングのために用いられ得る。我々が求めているものは、パーティションＩＤのセットの全てである。
【０１０３】
各パーティションＩＤについて、更新は、パーティション中のログのセットをスキャンすることができる。図９を参照。
lterable<Entry<LogId, LogEntry[]>> getLog(int partitionId);
【０１０４】
（２）ｇｅｔＬｏｇ動作の要件
【０１０５】
ログ情報は、ＳＹＮＣ後のログエントリーのシーケンスである。それはスナップショットと似ているかもしれない。スナップショットが全ての書き込み動作について１つのタイムスタンプを有するのに対して、各ログエントリーがタイムスタンプと関連している点において、それらは意味が異なる。
【０１０６】
トランザクションマネージャは、ＳＹＮＣおよびＣＵＲＲＥＮＴの間で終了時刻を選択することができる。
【０１０７】
トランザクションログがＳＹＮＣ後に書き込み動作を含まない場合、トランザクションログマネージャは、（空のシーケンスを送信する代わりに）このログを結果から除外する。
【０１０８】
ＡＰＩは、ログのセット上のイテレータを提供する。ここで、トランザクションログマネージャは、パーティション中の全てのログをスキャンする必要はない。トランザクションログは、いつでもスキャンを中止して、イテレーションを終了（hasNextがｆａｌｓｅ）することができる。例えば、トランザクションログマネージャは、イテレーションの数をパフォーマンスのために制限することを要求することができる。図１０を参照。
【０１０９】
重複排除：スナップショットとのその他の重要な違いは、トランザクションログマネージャが書き込みの重複（同じキーバリューオブジェクト上の複数の書き込み動作）を排除しないことである。アップデータ（またはその他の可能なログのユーザ）がその動作シーケンスを再生し、ログ中のいかなるタイムスタンプにおける状態を生成することができるように、全ての動作はそれら自身のタイムスタンプでログに保存される。
【０１１０】
（３）ログ同期
【０１１１】
アップデータが書き込み動作を実行して、リーダ（例えば、クエリ実行エンジン）が新たな値を利用可能であることを確認した後、タイムスタンプがＴｓと等しいかまたはＴｓよりも古い全ての書き込みが実行されるトランザクションログマネージャにタイムスタンプＴｓを与える。
void sync(LogId id, long ti mesta m p);
【０１１２】
同期を実行するためにストレージに適用される通常の「同期」動作（例えば、オペレーティングシステムの）とは異なり、この同期動作は、ストレージ側（アップデータ）により、「同期」が実行されたことを通知するために開始されることに留意されたい。
【０１１３】
この動作は、トランザクションログマネージャに、ストレージが与えられたタイムスタンプ（例えば、新たなＳＹＮＣ）まで同期したことを知らせる。それ以降は、トランザクションログは、このタイムスタンプよりも古いデータおよび動作について耐久性の責任を負わない。
【０１１４】
（４）アップデータの実装の問題
【０１１５】
ストレージの一貫性の要件：我々が、ヴォルデモートまたはカサンドラのような一貫性のあるキーバリューストアを使用すると、要求される条件は、Ｗ＋Ｒ＞Ｎである。ここでＮは各キーのレプリカの総数であり、Ｗは、書き込むレプリカの数であり、Ｒは読み込むレプリカの数である。
【０１１６】
アップデータがＷのレプリカを正常に書き込んだ場合、ストレージは、クライアントがＲのレプリカからアップデータが書き込んだ最新の値を読み込むことができることを保証する。書き込みに失敗した場合、クライアントは、非決定的な方法で、新たな値または古い値を読み込むことができる。アップデータが書き込もうとしている新たな値は、ＳＹＮＣ後のログ中の書き込みに基づいているため、これは安全な動作である。非決定論的状態における値を用いるトランザクションについては、検査述語が、この読み込みと共に、ＳＹＮＣと等しいまたはＳＹＮＣより古いタイムスタンプと関連付けられているため、コミット要求は失敗するだろう。
【０１１７】
アップデータが正常に値を書き込むと、トランザクションログのＳＹＮＣを更新することができる。
【０１１８】
同時更新：同じキーの値は、連続して書き込むことができる。複数の書き込み要求が同じキーに同時に発行されている場合、ストレージは、トランザクションの正当性を保証することができない。
【０１１９】
一方、アップデータは、異なるキーの値を同時に書き込むことができる。（正常な）トランザクションは、これらの値に独立した方法でアクセスすることができる。後のセクションにおいて、我々は、非トランザクション（非分離）クエリ実行のためのよりより一貫性を提供するために、異なるキーの値を連続して書き込みたいケースについて議論するだろう。
【０１２０】
リカバリ：キーバリューオブジェクトの値が最新の書き込み動作により決定されると仮定すると、リカバリは簡単である。アップデータがアップデートおよびリスタートの間にダウンした場合、現在のトランザクションログのＳＹＮＣからアップデートを再開することができる。既に適用された書き込みを繰り返すことは、それらはＳＹＮＣ後の動作であり、これらの値を読み込むトランザクションは失敗するかもしれないため、トランザクションの分離保証の面で安全である。
【０１２１】
非分離型の読み取り（例えば、コミット時に検査せずにデータを読み取ること）のために、コミットされた値のうちの１つを読み取る。このため、非分離型読み取りは、“コミットされた読み取り”（例えば、ダーティーな読み取りでない）である。後のセクションにおいて、我々は、非分離読み込みについて（上記の同時更新に関して示したように）、我々がさらなる一貫性の保証を求めるケースについて議論する。そのためには、我々は、アップデータとトランザクションログマネージャと間の、同期のタイミングを制御する方法を紹介する。
【０１２２】
アップデータへのパーティションの弾性マッピング：我々は、１つのアップデータが同じキーにおける同時更新を避けるために、１つのパーティションを処理することを確認することができる。パーティションの所有権（同期を処理する権利）を変更することは、フェールオーバーと複数のアップデータの拡張／縮小を可能にするために、トランザクションログマネージャと同じ方法で取り扱うことができる。
【０１２３】
我々がパーティションを１つのアップデータに割り当てるとき、我々は、トランザクションログマネージャノードへのパーティションの現在のマッピングを利用することができる。
Node[] getNodesQ;
【０１２４】
我々は、通信コストを低減するために、アップデータのマッピングを決定することができる。例えば、我々は、１つのアップデータが、トランザクションログマネージャノードを実行し、トランザクションログマネージャおよびアップデータ間で、全ての通信をローカルにするために、同じマッピングを用いる物理的なサーバのそれぞれの上で実行される設定を検討することができる。
【０１２５】
しかしながら、パーティションは、トランザクションログマネージャないの１つのノードから他のノードへ移動することができることを思い出されたい。図１１を参照。
【０１２６】
（同期動作を含む）トランザクションログ上のいかなる動作も、マスターパーティションでいつでも処理されるため、トランザクションログマネージャ側において、アップデータがパーティションのマイグレーションを認識していない場合であっても、システムは、まだ正しく動いている。
【０１２７】
しかしながら、パフォーマンスの理由のために、アップデータはまた、パーティションの所有権を１つのアップデータノードから他に移動させることができる。アップデータは、定期的にトランザクションログマネージャのマッピング情報を確認し、パーティション所有権のマッピングを絞り込むことができる。
【０１２８】
一般的に、パーティション所有権のマッピングは、トランザクションログマネージャのマッピングから独立している。アップデータノードの数もまた、独立して選択することができる。
【０１２９】
６．拡張：メッセージング
【０１３０】
このセクションでは、トランザクション内で非同期メッセージングをサポートするために、トランザクションログマネージャを拡張する。
【０１３１】
（１）メッセージを含むトランザクション
【０１３２】
クエリ実行プロセッサは、メッセージおよび要求トランザクションがメッセージに共にコミットするように、トランザクションがメッセージと動作のシーケンスを異なるトランザクションログ上にまとめる。
【０１３３】
メッセージ
【０１３４】
メッセージは、動作のシーケンスを含み、メッセージの宛先として特定されるトランザクションログに送信される。メッセージは、動作を開始するメッセージプロセッサを特定するために用いられるメッセージタイプを有する。
interface Message{
LogId getDestinationQ;
String getTypeO;
Operation[] getOperationsQ;
}
【０１３５】
トランザクションログマネージャは、動作の内容を解釈せず、それらをバイト配列として扱う。
interface Operation{
byte [] toByte();
}
【０１３６】
宛先において、トランザクションログマネージャは、メッセージタイプ（message. getType()）によりメッセージプロセッサを特定する。メッセージプロセッサは、これらのバイト配列をデシリアライズして、適切な動作として解釈することができる。
【０１３７】
メッセージでのコミット
【０１３８】
コミット要求動作は、追加の因数を指摘して拡張される。：メッセージのシーケンス。これらのメッセージは、コミットが成功している場合、原子的な方法でキューイングされる。
boolean commit(LogId id, Check check,
Write[] writes, Message[] messages);
【０１３９】
クエリ実行マネージャは、それらを原子的な分離された方法で処理させるために、同じタイプの動作及び同じ宛先を１つのメッセージにまとめることができる。
【０１４０】
（２）要求された保証
【０１４１】
書き込み動作を管理しているメイントランザクションログプロセッシングに対して、我々は、一般的なメッセージングの動作を扱う。繰り返された書き込み動作がもはや一般的な動作のために有効ではなく、動作が重複するという仮定は、間違った結果を引き起こすかもしれない。
【０１４２】
メッセージは一度配信させることができ、１つのトランザクションログから他へのメッセージの順序は、保存することができる。
【０１４３】
一連の動作は、原子性および分離性を保証する目的で単一のトランザクション内で処理されることができる。しかしながら、同じ宛先の複数の動作シーケンスは、組み合わされて、１つのトランザクション内でまとめて処理されることができる。トランザクションをまとめることは、メッセージプロセッサのパフォーマンスチューニングの決定である。メッセージプロセッサは、動作の意味に基づいて、正確性が保たれる限り、まとめられた動作のセットを再スケジューリングすることができる。
【０１４４】
（３）拡張アーキテクチャ
【０１４５】
トランザクションログは、２つのメッセージバッファ（送信および受信）と、追加のＡＰＩとを用いて拡張される。トランザクションは、書き込み動作だけでなく、送信メッセージもコミットすることができる。これらのメッセージは、宛先トランザクションログに運ばれて、受信バッファに入れられる。メッセージプロセッサは、これらの受信バッファ内のメッセージを操作して、同一のトランザクションログ上でトランザクションを実行する。このトランザクションは、書き込み動作だけでなく、受信バッファからのメッセージの削除もまたコミットするだろう。図１２を参照。
【０１４６】
（４）メッセージバッファ
【０１４７】
送信メッセージ
【０１４８】
拡張アーキテクチャに関する図１３において、送信バッファは、各トランザクションログと関連づけられている。しかしながら、実際の実装では、パーティション中のトランザクションログと送信バッファとは一貫性が保たれ、共にマイグレーションされるため、我々はパーティション毎に１つの送信バッファを有している。
【０１４９】
後述するように、メッセージは、パーティション間で交換される。送信側および受信側は、パーティションＩＤで識別される。このため、マイグレーションが起きたとしても配信が保証される。このようにして、パーティション毎に、１つのバッファ内に送信メッセージを置くことは合理的なデザインである。
【０１５０】
受信メッセージ
【０１５１】
我々は、パーティション毎に１つの共有送信バッファを用いることができるのに対して、我々は、個々の受信バッファをトランザクションログ毎に割り当てることができる。メッセージプロセッサは、トランザクションログ毎にバッファ中の受信メッセージを消費（ｃｏｎｓｕｍｅ）し、トランザクションをその上で実行する。異なるトランザクションログは、バッファ消費の異なる進行状況を示す。図１４を参照。
【０１５２】
（５）メッセージ処理
【０１５３】
メッセージは、宛先トランザクションログ上でトランザクションとして処理される。メッセージプロセッサは、メッセージを解釈し、ストレージからデータを読み出し、ログへの書き込み動作をコミットする。（１）メッセージ中の動作のシーケンスは、単一のトランザクション内で処理されてもよい。（２）受信バッファ中の処理されたメッセージの削除は、アトミックな方法でトランザクションの一部として行われてよい。
【０１５４】
これをサポートするために、受信メッセージは、下記のトランザクションオブジェクトとしてメッセージプロセッサに示される。
interface Transaction{
LogId getLogId();
long getTimestamp();
String getType();
byte[][] getOperations();
}
【０１５５】
メッセージとの重要な違いは、受信メッセージの順番を示すタイムスタンプと関連づけられていることである。メッセージプロセッサがトランザクションをコミットするとき、進行状況を示すために、このタイムスタンプを与えることができ、トランザクションログマネージャに受信バッファ内のメッセージを削除させる。
【０１５６】
メッセージの取得
【０１５７】
不要な衝突を避けるために、トランザクションログ毎の受信メッセージのストリームは排他的に処理することができることに注意せよ。そのために、我々は、データアップデータのためのメカニズム（パーティションからメッセージプロセッサへのマッピング）と同じメカニズムを用いることができる。トランザクションログマネージャは、特定のパーティション内の受信メッセージ（またはトランザクションオブジェクト）を取得するために、メッセージ処理のためのインタフェースを提供する。
Iterable<Transaction>getTransactions(int partitionId);
【０１５８】
トランザクションコミット
【０１５９】
メッセージプロセッサは、トランザクションログマネージャに、コミット要求に応じてトランザクション内で消費されるメッセージを知らせることができる。メッセージプロセッサは、受信バッファ内のメッセージの連続シーケンスを処理することができるので、APIは、２つの値（ｓｔａｒｔ：最も古いメッセージのタイムスタンプ、およびｅｎｄ：最新のメッセージのタイムスタンプ）を提供する。
Result commit(LogId id, long start, long end.
Check check,
Write[] writes, Message[] messages);
【０１６０】
メッセージプロセッサのコミット要求は、障害の２つの異なる原因を知らせるために、複雑な値を返す。（１）衝突に起因した検査の失敗、および（２）メッセージ処理の同期がずれている。後者は、この特別なコミット要求のために導入される。
【０１６１】
１のケースにおいて、メッセージプロセッサは、トランザクション処理を同じメッセージのセット（［start，end］で識別される）を用いてやり直すことができるのに対して、ケース２では、メッセージプロセッサは、無効な順序でメッセージを処理していることを示す。
interface Result{
boolean isSuccessful();
long currentTimestamp();
}
【０１６２】
Result  rとr.isSuccessful()がfalseであると仮定すると、メッセージプロセッサは、コミット要求中の「start」の値と、r.currentTimestamp()の値とを比較することができる。これらが等しい場合、メッセージ処理は同期されていて、トランザクションは、検査失敗に起因した失敗である。startが現在のタイムスタンプよりも古い場合、メッセージ処理は、既に処理されたメッセージを処理しようとしている。メッセージプロセッサは、現在のタイムスタンプをフィードフォワードすることができる。startが現在のタイムスタンプよりも新しい場合、メッセージプロセッサが何等かの理由によりメッセージをドロップしたことを示している。それは再び受信メッセージをスキャンすることができる。
【０１６３】
メッセージ処理の失敗
【０１６４】
メッセージは、トランザクションがデータに対して実行される一般的な動作であるため、動作の意味に特別である無効な動作に起因したメッセージ処理の失敗があり得る。メッセージプロセッサは、これを恒久的な（非一時的な）失敗としてレポートし、（無効な）メッセージを受信バッファから削除し、トランザクションをコミットすることができる。レポートは、ロギングされてもよいし、適切などこかに送信してもよい。これらのレポートの使用方法（例えば、それらをアプリケーションレベルに返す方法）は、アプリケーションに特有である。
【０１６５】
（６）メッセージ交換
【０１６６】
このセクションでは、我々は、オンラインの方法でノード間でトランザクションログを再配布することができる、順次配信保証付のメッセージ交換を、トランザクションログマネージャに組み込む方法について説明する。
【０１６７】
トランザクションログは、パーティションのセットを管理されている。パーティションは、クラスタノードへのデータ割り当ての単位である（このケースでは、パーティションは、ＴＡＭインスタンスとして実装される）。（マスター）パーティションは、パーティションの内容の一貫性を保ちながら、オンラインで、１つのノードから他のノードに移行することができる。
【０１６８】
我々がトランザクションログから他のログへのメッセージの配信を考慮するとき、我々は、パーティションを送信側および受信側として考えることができる。ログに関する同じ宛先パーティションへのメッセージは、宛先パーティションを担当するノードに運ばれる、パーティションに関するメッセージに纏められる。
【０１６９】
１つのアプローチは、ＭＱ（Ｍｅｓｓａｇｅ  Ｑｕｅｕｅ）を用いることである。図１５を参照。
【０１７０】
我々がＭＱを用いるとき、我々は、メッセージが、元の順序でパーティションに一度だけ配信されていることを確認することができる。ほとんどのＭＱは、単一の消費者が各キューにアクセスするとき（どんな時も１つのマスターパーティションが存在する場合ため、このような場合は）順番通りの配信をサポートしている。残りの問題は、一度だけの配信を保証することである。１つのアプローチは、トランザクションの方法で、パーティションおよびキューを更新するために、ＸＡを実装することである。しかしながら、このアプローチは、実装が複雑であるかもしれない。代替のアプローチは、以下に説明する重複排除を可能にすることである。
【０１７１】
ＸＡを用いなければ、我々は、受信メッセージをパーティションに書き込むことや、キュー（例えばＪＭＳコミット）をアトミックな方法でコミットすることを実行することはできない。したがって、メッセージが再び配信されることが可能である。受信メッセージが１つずつコミットされる場合、受信側（例えば、パーティション）は、受信メッセージバッファに書き込まれた最新のメッセージを覚えている。そのためには、送信側は、グローバルに固有のメッセージＩＤを生成してもよい。我々は、送信側パーティションＩＤおよびローカルに固有なＩＤ（例えば、論理的タイムスタンプ）のペアをそのために用いることができる。
【０１７２】
（７）アプリケーション：キー−バリュー（ハッシュ）インデックス
【０１７３】
メッセージングのメカニズムを考えると、キー−バリューインデックスを維持することは、むしろ簡単である。
【０１７４】
プライマリーキーがＲ．Ａ．である関係Ｒ（Ａ，Ｂ，Ｃ）を考える。我々は、Ｒ．Ｂ．にインデックスを持つようにしたい。このインデックスは、キーがＲ．Ｂ．の値と、値Ｒ．Ａ．のセットを示す値とを示す、１つのキー−バリューコレクションとして実装され得る。インデックスを更新することは、これらのキー−バリューオブジェクトを更新することを含む。我々は、このコレクション内の各キー−バリューオブジェクトに対してトランアクションログを関連づけることができる。
【０１７５】
我々は、２つの動作put(b,a)およびdelete(b,a)を導入することができる。新たなレコード(al,bl,cl)がＲに挿入されるとき、クエリ実行エンジンは、put(bl,al)を、インデックスおよびR.b（例えばbl）の値という名前により識別される、トランザクションログに送信することができる。同じレコードが削除されるとき、エンジンは、delete(bl,al)を送信することができる。ｂの値が更新されると、２つのメッセージdelete(bl,al)およびput(b2al)が、ｂｌおよびｂ２によりそれぞれ識別される異なる宛先に送信されることになる。我々は、これらのインデックス動作を実装するために、下記のインタフェースを用いることができる。
interface KeyIndex extends Operation{
Command getCommand();
byte[] getValue();
}
enum Command{PUT,DELETE}
【０１７６】
値は、挿入されるプライマリキー（例えば、上記の例ではR.A）である。この動作は、ログＩＤがインデックス名およびインデックスキー（例えば、Ｒ．Ｂ）を示すトランザクションログに送信される。
【０１７７】
メッセージプロセッサは、与えられたログＩＤ（名前とキーのペア）で識別されるキー−バリューオブジェクトを取得する。ログの名前は、コレクションの名前を識別するために用いられ、ログのキーは、コレクション内でのオブジェクトのキーとして用いられる。
【０１７８】
取得されたキー−バリューオブジェクトは、値のセットを示す。メッセージプロセッサは、更新されたセットを生成し、このキー−バリューオブジェクト上における書き込み動作を生成するために、与えられた値を追加または削除する。
【０１７９】
（８）アプリケーション：Ｂ−リンクツリー（レンジ）インデックス
【０１８０】
残念ながら、キー−バリューインデックスの場合と異なり、メッセージプロセッサ間の更新の競合を避けるために、インデックス動作を配布するのは容易ではない。
【０１８１】
図１３は、各ツリーノードが個別のキー−バリューオブジェクトとして実装された、Ｂ−リンクツリーインデックスを示している。我々が値１をポイントaに、値５をポイントｂに挿入したとする。もしわれわれがこれらの動作を、キー−バリューインデックスの場合と同様に、ａおよびｂに送信した場合、これらは、同じキー−バリューオブジェクトに適用されるだろう。
【０１８２】
ベースラインアプローチは、このインデックス上の全ての動作をルートノードに送信することである。図１７を参照。
【０１８３】
以下では、我々は、パフォーマンスを改善するための可能な拡張について説明する。
【０１８４】
バッチ更新
【０１８５】
インデックス動作をひとつずつ処理する代わりに、メッセージプロセッサは、複数のインデックス動作を一緒に更新して、キー−バリューオブジェクトへの書き込みの数を減らすことができる。そうするために、我々は、耐久性と、大規模なデータのバッチ更新のために最適化された安全なリカバリとを確保するための、様々なメカニズムを導入することができる。
【０１８６】
メッセージルーティング
【０１８７】
別のアプローチは、ノード間のレンジ（例えば、対応するメッセージプロセッサ）の所有権を変更するためのプロトコルを導入することである。我々は、このノードがそのサブツリーを更新する権利を有していることを示す、「所有権」フラグをノードデータ構造中に導入する。初期状態では、ルートノードは、全ての所有権を有している。ノードが分割されると、所有権が配布される。我々は、安全に分割された所有権を移譲するプロトコルを持つことができる。
【０１８８】
インデックス動作の送信側は、先ず、Ｂリンクツリーを詳しく検討し（ｔｒａｖｅｒｓｅ）、現在の所有者を識別する。ノードを分割すると、もはや所有者ではないノードへのメッセージを引き起こす可能性がある。対応するメッセージプロセッサは、同じメッセージングメカニズムを使用して、このメッセージを新たな所有者にルーティングすることができる。図１８を参照。
【０１８９】
７．拡張：キー−バリューの書き込み順序
【０１９０】
上記のアーキテクチャにおいて、我々は、トランザクションに関するシリアル化可能なスケジュール、つまり、正常にコミットしたトランザクションが、データの一貫性のあるスナップショットを、独立した方法で、生成することを保証する。実行中のトランザクションは、一貫性のないスナップショット（例えば、チェックタイムスタンプＴｃの後値を観察することができる）を参照することができる。トランザクションが成功することはないので、これは正しい挙動であると考えられる。
【０１９１】
もう１つの懸念は、非トランザクション処理に対する保証である。トランザクションログマネージャと関わることなく、ストレージのリーダのために何を保証することができるか。ストレージは、アップデータがコミットされていない値を書き込むことがないため、リーダがコミットされていない値を参照することがないことを保証する。しかしながら、それぞれのキー−バリューオブジェクトは独立して更新されるので、複数のキー−バリューオブジェクトの値間の保証はない。そのような緩和が合理的である多くのケースがある。
【０１９２】
しかしながら、データレイアウトの将来的な拡張において、我々がストレージのリーダに対して追加の保証を持つケースがある。Ｂ−リンクツリーのようなツリー構造のデータを維持することは、下記に説明される動作（motivating）例である。
【０１９３】
この将来的な問題に対処するために、トランザクションログの拡張を導入して、異なるキー−バリューオブジェクト上の書き込みスケジュールを保証する。
【０１９４】
（１）モチベーション：ツリー構造データの維持
【０１９５】
図１３は、ツリーノードごとにキー−バリューオブジェクトを用いることによって、キー−バリューストア上で実行されるときのＢリンクツリーの挙動を描いている。最初は、我々は、レンジ［ａ，ｃ］および［ｃ，ｅ］のそれぞれを処理する２つの葉（leaves）を有している。書き込み動作（ｗ１，ｗ２，ｗ３）のシーケンスは、ノード［ａ，ｃ］を２つのノード［ａ，ｂ］および［ｂ，ｃ］に分割することである。
【０１９６】
ｗ２は、ｗｉ以前にリーダにとって利用可能であるとすると、リーダは、一貫性のない（壊れた）ツリーを発見するだろう。この一貫性のなさは、一時的な状態であり、ツリーは、最終的には再び一貫性のある状態になる。１つの解決策は、リーダに一貫性のある状態を期待するツリーに再びアクセスを試みさせることである。しかしながら、これは、リーダに追加のコストを課す。一般的に、ライタの数と比較して、非独立リーダの数が多数であり、これらのリーダは、パフォーマンスのために非独立モードを選択する。このため、ライタにこの一時的に一貫性のない状態を回避するために、余分なコストを払わせることが合理的である。図２０を参照。
【０１９７】
（２）ログ命令（directives）
【０１９８】
アップデータ側において、書き込みスケジューリングをさらに制御することを可能にするために、我々は、ログ命令のセットを導入する。命令は、ログ（書き込み動作のシーケンス）中に挿入され、アップデータは、この命令を解釈して、命令されたようにふるまうことができる。
【０１９９】
命令を適切に挿入することは、クエリ実行エンジンの責任である。トランザクションマネージャは、命令の意味を知っている必要はない。
【０２００】
インタフェースは、命令を含むように拡張される。書き込みオブジェクトの配列を与える代わりに、我々は、LogOperationオブジェクトの配列を用いる。書き込みおよび命令は、LogOperationのサブクラス（サブインタフェース）である。
interface LogOpertaion{
}
interface Write extends LogOperation{
//… same as before
}
interface Directive extends LogOperation{
byte[] getCommand();
}
【０２０１】
シーケンシャル書き込み命令
【０２０２】
順番が狂った適切でない書き込みを避けるために、アップデータは、複数のキー−バリューオブジェクト上の特定の書き込みシーケンスが同時に実行できないことを知りたがっている。我々は、２つの命令ｓｔａｒｔおよびｅｎｄを、シーケンシャルセグメントをグループ分けするために導入することができる。上記の例において、我々は、ｗ１，ｗ２，およびｗ３をグループにするために、（…,start,w1,w2,w3,end,w4,…）のようなシーケンスを有することができる。
【０２０３】
シーケンシャルな書き込みのために、アップデータは、書き込み動作の結果を、次の書き込み動作を開始する前に利用可能にすることを確認することができる。
【０２０４】
同期命令
【０２０５】
リカバリ後に書き込みをやり直すことに起因する、一時的な一貫性のなさを引き起こす異なるタイプの異常がある。
【０２０６】
ｗ０がノード[a,c]へのデータの挿入であり、シーケンスｗ１−ｗ３がノード［ａ，ｃ］の分割であるＢ−リンクツリー(w0,w1,w2,w3)上のログを検討する。アップデータは、ログをストレージに書き込んだ後、新たなSYNC時間をトランザクションログマネージャに報告する前に死亡したとする。リカバリ後、アップデータは、ｗ０から書き込みを開始し、書き込みのシーケンスは、（ｗ０，ｗ１，ｗ２，ｗ３，ｗ０，ｗ１，ｗ２，ｓ３）となる。ｗ０を２回目のストレージに適用する場合、Ｂ−リンクツリーの状態は、図２１のようである。
【０２０７】
このＢ−リンクツリーが一貫しているということは、議論の余地がある。リーダは、クエリ範囲に応じて、タイムスタンプの異なるミックスの値を見て、失敗することなく、ツリーを走査することができる。
【０２０８】
一般的に、我々が、アップデータがやり直しの間に角に戻ることを望まない場合がある。これを制御するために、我々は、同期命令をログシーケンスに挿入することができる。例えば、上記の例では、我々は、“ｓｙｎｃ”命令をノード分割の直前に挿入することができる（ｗ０，ｓｙｎｃ，ｗ１，ｗ２，ｗ３）。
【０２０９】
アップデータは、同期命令を検出すると、それが現在のＳＹＮＣをトランザクションログと同期することに成功する前に、さらなる書き込み動作を適用されない場合がある。
【０２１０】
８．拡張：様々なチェック述語
【０２１１】
（１）複数のチェック述語
【０２１２】
上記の議論では、我々は、１つのタイムスタンプを有する１つのチェック述語を持っている。我々は、様々なタイムスタンプを有する複数の読み出しセットを表現するために、複数のチェック述語を持つように拡張することができる。
【０２１３】
例えば、この拡張は、クエリ実行がデータのキャッシングを利用する場合に有用である。
【０２１４】
先ず、我々は、（ちょうどメッセージプロセッサのコミット要求に対する結果のように）現在のタイムスタンプを含む複雑な値を返すために、コミット要求を拡張する。
interface Result{
boolean isSuccessful();
long currentTimestamp();
}
【０２１５】
返されたタイムスタンプがＴｃであるとする。コミットが成功である場合、チェック述語中の読み出しセットが全て時刻Ｔｃにおいて現在のものであることを意味する。また、ちょうど今コミットされた書き込み動作は、タイムスタンプＴｃを持つ。クエリ実行エンジンは、この知識を将来のトランザクションコミットのために用いることができる。例えば、それはタイムスタンプＴｃと関連づけられたこれらのキー−バリューオブジェクトをキャッシュすることができる。
【０２１６】
結果として、クエリ実行エンジンは、様々なタイムスタンプを有するキー−バリューオブジェクトを維持する。そしてコミット要求は、これらのキャッシュされた値に読み出し動作を含むために、複数のチェック述語を持つ。
Result commit(LogId id, Check[] checks, Write[] writes);
【０２１７】
（２）拡張された述語タイプ
【０２１８】
さらに、我々は、可能なパフォーマンス最適化のためにチェック述語を拡張することができる。下記は、いくつかの設定において効率的であるチェック述語の例である。
【０２１９】
キー署名（signature）
【０２２０】
キーのセットを有する代わりに、我々は、このキーセットの署名を考慮することができる。例えば、我々は、ブルームフィルタを用いることができる。署名を用いることによって、我々は、競合検出における偽陽性を犠牲にして（例えば、競合が無い場合であってもチェックが失敗することがある）、コンパクトに読み出しセットを表すことができる。このスキームは、更新が非常に頻繁ではなく（例えば、（SYNC,CURRENT）におけるログデータが大きくない）、トランザクションが比較的多くのキーを読み出す場合に機能する。
【０２２１】
キー範囲
【０２２２】
読み出しセットを表現する別の方法は、キー範囲のセットを表すことである。これは、このトランザクションログによって管理されるデータセットがインデックス範囲である場合、実行可能な選択肢である。
【０２２３】
９．拡張：より大きなトランザクションログのための実装
【０２２４】
このセクションでは、我々は、ブルームフィルタに基づいてトランザクションログを実装するための１つのアプローチを説明する。図２２を参照。
【０２２５】
データ構造は、Ｂリンクツリーと似ているかもしれないが、我々は、データがＦＩＦＯ方式で更新される性質を利用して、それを簡素化することができる。これはメモリ内において実装されるとき、我々は、最大ツリーの大きさを設定し、各層（シブリング：きょうだい）のツリーを配列（リングバッファ）として実装する。このようなケースでは、我々は、シブリング間にリンクを実装する必要がない。
【０２２６】
子ノードへの各ポインタは、対応する範囲でキーのセットを表すブルームフィルタと関連づけられる。
【０２２７】
データ挿入およびノード分割
【０２２８】
データは、常にCURRENTに加えられることに留意せよ。ノード分割は、実際、新たな空ノードを左端（頭）に加えている。挿入のコスト（データの葉への挿入、必要に応じた新たな空ノードの追加、ブルームフィルタの更新）は、０（ｌｏｇKＮ）である。ここでＮはログエントリのサイズであり、Ｋは、ツリーのファンアウトである。
【０２２９】
ログ切り捨て
【０２３０】
ログを切り捨ててメモリを開放するために、削除が必要とされるだろう。例えば、我々は、ログの１／Ｋを削除するために、最も古い（最も右の）ルートの子を削除することができる。このコスト（ルートブルームフィルタおよび各層の最も右のノードの更新）は０（Ｋ＋ｌｏｇｉＮ）である。
【０２３１】
チェック
【０２３２】
与えられた（ｋｅｙ，ｔｉｍｅ）の正確なチェックの最悪なケースは０（Ｎ）である。我々は、ブルームフィルタが、スキャンされるサブツリーを選択するために、チェック手順を手助けすることを期待している。また、チェックは、競合検出の偽陽性を犠牲にして、ブルームフィルタを使用することにより、いつでもより早期に終了することができる。
【０２３３】
弾性（例えば、ワークロードに自動的に適合するために、サーバリソースを追加および除去する可能性）を達成することは、（１）データセンタ（クラウド）運用コスト、（２）データセンタ（クラウド）サーバコスト、または（３）アプリケーション開発コストを含むコストを低減するだろう。
【０２３４】
上記は、全ての観点において、説明に役立ち例示的であるものとして理解されるべきであり、限定的に理解されるべきでない。そして、ここで開示される本発明の範囲は、詳細な説明から特定されるべきでなく、むしろ全幅に渡って、特許法により許可された、特許請求の範囲から特定される。なお、ここに図示され、説明された実施形態は、本発明の原理を説明するための例示であり、当業者であれば、本発明の範囲および精神から逸脱することなく、様々な変更をすることができることを理解されたい。当業者は、本発明の範囲および精神から逸脱することなく、他の様々な特徴の組み合わせを実装することができる。
【図１】
2014532919.tif 000003
【図２】
2014532919.tif 000004
【図３】
2014532919.tif 000005
【図４】
2014532919.tif 000006
【図５】
2014532919.tif 000007
【図６】
2014532919.tif 000008
【図７】
2014532919.tif 000009
【図８】
2014532919.tif 000010
【図９】
2014532919.tif 000011
【図１０】
2014532919.tif 000012
【図１１】
2014532919.tif 000013
【図１２】
2014532919.tif 000014
【図１３】
2014532919.tif 000015
【図１４】
2014532919.tif 000016
【図１５】
2014532919.tif 000017
【図１６】
2014532919.tif 000018
【図１７】
2014532919.tif 000019
【図１８】
2014532919.tif 000020
【図１９】
2014532919.tif 000021
【図２０】
2014532919.tif 000022
【図２１】
2014532919.tif 000023
【図２２】
2014532919.tif 000024
【国際調査報告】
2014532919.tif 000025
2014532919.tif 000026
2014532919.tif 000027