OceanVista 再読

OceanVista

http://www.vldb.org/pvldb/vol12/p1471-fan.pdf

基本的アーキテクチャは、DC間クラスターをインフラにおいて、高遅延・耐障害性を前提にした分散transactionの仕組みになっている。

どう見てもAlibabaのOceanBaseそのものではない。が、同じAlibabaグループでかつ、Oceanの名前をつけているので、関係はなくはないと思う。少なくとも同じグループまたは情報交換はしているのではないか。技術的な方向性を模索するプロトタイプに見える。

バックグラウンド的な与太話をすると、Alibabaは、というか中国的には、ITでの米国からの依存脱却（ポーズだけなのか、実際なのかは置いておいて）を目標として掲げているのは周知の通り。んで具体的な話としては、Alibaba的には脱Oracleが一つの目標になっている。この目線で見たときには、この手のコア技術としての、transaction技術の習熟度や練成度はDB技術の独自性のよいタッチストーンになる。そういう意味で眺めてみてもよい。・・・まぁ、あの、残念ながらすでに少なくとも極東の某国よりは全然上です。（遠い白目

このレベルであればまだまだ追いつけると個人的に思えるのですが、はぁ、なんというか、そんなに難しいことはやってないんですけどね。

DBについては、世界的には3極になっていて、Oracle・SAP・中国だと思う。GAFAはちょっとwhaleすぎて違う感じですね。面白いのは普通にMSです。ただ例のSQLServerが(ry

OceanVistaについての個人的なインプレッションは以下

1. まずatomicな単純な処理「のみ」について、一貫性を担保する分散transactionでは、相当優位だとは思う。quorumとMV組み合わせは「アリ」で、今後のこの手の話では普通に検討されるフレームだと思う。個人的には高く評価したい。アイデアの筋は悪くない。詳細は訳出の方を読んでもらうとして、ざっくり言うとMVで非同期に書き込んでいき、version orderを利用してviewの整合性（順序）を確保し、そのプロトコルに分散合意を利用している。このためcommit protocolとreplication protocolが統合されており、なにかと効率がよい。なお、合意はgossipの上で割とシンプルなfast paxosを利用している。

2. ベンチマークはほとんど参考にならない。単純なPoCレベルで特に問題がないという話でしかなく、そもそも環境がpoor過ぎるように見える。特にある程度分散合意が前提であるのであれば、もう少し障害よりに振らないと参考値にもならないだろう。ただし趣旨としてtransaction処理よりの話であればわからないでもない。

3. TPC-Cをやっていないのは理由は明確で、全然パフォーマンスが出ないからだと思われる。これは理由は簡単で、いわゆるACIDなtransactionではない。（ただ間違いなく本人はACIDって言い張ると思う。）ACID transactionの原理原則のview equivalent（を保証するHerbrand semantics）を意図的に無視している。言い訳的にdependent transactionという言い方をしているが・・・当然、TPC-C“ですら“結果がでないのは火を見るより明らかなので、当然ベンチマークはしない。同業的には、「まぁそうだよな～」という気もする。とはいえ、NoSQLのナントカ・コンシステンシーよりは全然ましですが。

4. 要するにdeterministicな仕組みであるので、通常のSQLは普通に難しい。OceanBase自体は楽勝でSQLは使えているはずなので、その意味でもOceanVistaとOceanBaseはまったくの別物だろう。

5. 技術的な発展性については、いろいろ意見はあるとは思うが、肯定的にみている。特に、今後はDBの“バックアップ”は、普通に分散クラスターを立てて、そのままActｘNインスタンスですべてを進めるというのが基本になると個人的には思っている。従前のバックアップ・耐障害系と正常系を分けるアーキテクチャは存在意義がない。理論においても、たとえばTx処理は正常処理/リカバリーという図式は基本的にもうないと思う。その意味では、MV(というか分散処理でのorderingだよねこれ)＋gossip+quorumは有望だ。

6.そもそも何ために大陸間の分散transactionが必要か？ということと、その結果どのようなプロトコルが必要なのか？という点は考慮する必要があるとは思う。グローバルにサービスを展開するところはいちいちローカルにやっていてはいろんなコストが高い（特にソフト）はずなので、その意味から考える必要がある。

 ただ日本ローカルでみた場合はまちがいなくDRが大きいとは思う。要はサイトダウンなんだが、そのコンテクストでどのような分散transactionのプロトコルが必要かは、考える必要はある。その意味ではある程度の遅延前提でのDR的な高可用性の確保として、OceanVista的プロトコルを一部適当に利用するのはありではないかと思う。

 まずは低遅延サイト内での分散処理が基本になるが、その組み合わせとして高可用性を考えるのであれば、おそらくはPrimary-BackupをDR的に構築するのではなく、普通にPartitioned-Master/Master構成で、Over-DCではX-HTAP的なものになると思う。この時のlog転送のcommit/replicaプロトコルはそのままOceanVista方式もありだと思う

7. 余談だけど、今のTsurugiのread-only -anomaly対策の実装にこれを組み合わせるのはとても「興味深い」

8. 今後の技術動向としては、transactionとdistributedは基本的な基礎技術としてmustだと思う。片手落ちはだめで、両者をマスターすることがインフラ・ミドルウェア・エンジニアとしては必須になりつつある。これはなかなかハードルが高い。（・・・クラウドは使う分には便利だが、この辺は完全に隠蔽されるので、まったくわからないし、ノウハウもたまらない気がする。）

以下、ベンチは除いた本論の全訳になる。いろいろ微妙なニュアンスや表現の違いはあると思うが、原則として本論文の方が正しいので、そちらを参照のこと。もともと以下は自分用のものなので。

Ocean Vista

http://www.vldb.org/pvldb/vol12/p1471-fan.pdf

ABSTRACT

　グローバルな分散データについて、conflict下でのACID transactionの提供は、transaction処理プロトコルのエベレストといえる。このシナリオでの、transaction処理では、concurrency control（以下CC）とレプリケーションのオーバーヘッドを増大させる大陸間ネットワークの高遅延が特に高くつく。この問題を緩和するために、OceanVista（以下OV）を導入する、これはすなわち、最新の分散プロトコルであり、strict serializabilityを保証する。

　CCとレプリケーションはtransactionのvisibilityの問題を様々な側面から解決する、すなわちversionのwater markを利用してvisibilityを管理するmulti-version(以下MV)プロトコルと、効率的な(efficient)なgossipを利用した適切なviewの決定の配布を利用して、これらの問題を解決する。

　watermarkのgossipはバッチ単位での非同期transaction処理とtransactionのvisibilityの通知を可能にする。また、このCCとレプリケーション・プロトコルによりデータセンター間の高遅延ネットワーク下での効率性が改善される。特にOceanVistaはconflictを起こして並列競合しているtransactionを処理することができ、効率的なwrite-quorum / read-oneなアクセスをサポートして、たいていのケースで、1 roundトリップで処理を完了する。実証実験ではマルチDCのクラウド環境で、現状最速の分散TxエンジンのTAPIRの、ピーク・スループットで10倍のパフォーマンスをgossipの追加的な遅延コストだけで実現した。追加の遅延コストはWANでのRTTの1ラウンド分で、ワークロードが低い最良条件の場合はその一ラウンドでTAPIRとほとんど同じ性能でtransactionがコミットできる。

1. INTRODUCTION

　クラウドにより、耐障害性保証、スケーラビリティ、サービスのローカライゼーション、コスト効率性のために、アプリケーションとデータを地理的な分散DCにわたって配備することがより簡単になっている。そのようなインフラにより、中小規模の企業が世界中の顧客に対してグローバルな分散ストレージシステムを構築することも可能になっている。地理的に分散したデータベースシステムにおける分散Transactionは、ACIDセマンティクスを利用することによりアプリケーションを便利にする一方で、そのオーバーヘッド、特にグローバルな分散データに対すると高いコンテンションに対する、高いオーバヘッドが悪名名高い。

　地理分散transactionのオーバーヘッドは、異なったシャードに対する単一性と分離性のコーディネートを行うコミットと同時性制御のプロトコルからだけではなく、単一シャードでの複数レプリカの状態をコーディネートする（たとえばPaxosのような）レプリケーション・プロトコルからも発生する。地理分散transactionでのネットワーク遅延の増大は、ローカルでの処理よりもよりずっと高いコンテンションをもたらす。たとえば、分散DBのベンチマークのワークロード（キー空間やターゲットスループットの固定）は単一リージョンで多数のサーバ下での分散DBでは低いコンテンションが低くなることがあるが、逆にデータセットがグローバルに分散した場合は高いコンテンションになることもある。[注:要するに、うまく分散させれば効率がいいこと当然あるが、そのままそれを地理分散にもっていくと崩壊するということ]

　伝統的なCCメカニズム（たとえばOCCとか2PL）は分散transactionを同期的に処理する。transactionのロジックの実行中にtransaction orderを決定し、そのtransactionが排他的に最新のversionにアクセスできる時間の間だけデータオブジェクトの更新ができる。そのような排他アクセスは悲観ロックや楽観的な後追いでのvalidationの利用により保証され、結果、大抵の場合はすべてのread-write transactionにおいて、すくなくともWANでのRTT一回分の時間がかかる。ここでは、この排他的アクセスの時間をtransactionのserialization windowと呼ぶ。長いserialization windowはconflictしているtransaction並列実行の妨げになり、ハイパフォーマンスなCCプロトコル設計の大きな課題になっている。

　他方、WANで接続されたシステムでのレプリケーション・プロトコルの設計は特に困難であり、これは地理的に分散したDC間を結合するN/Wが遅く（遅延は数百msecになる）かつ予測不能であることによる。結果として、Write-All(WA)はアプローチは、遅延するwriteの競合が厳しい。他方、Write-Quorum（WQ）のアプリーチは普通、専用のleaderか、またはquorumから読み込むを行うが、これは別の問題を引き起こす。leaderは潜在的にパフォーマンス・ボトルネックになるし、Reading-Quorum(RQ)は大抵のリードドミナントなワークロードでは、Reading-One(RO)よりもずっとコスト[注：workだが、quorum的な言い方だと多分load]がかかる。

　TAPIRとかMDCCのような以前の研究は、CCとレプリケーションを効率のために単一のプロトコルにまとめている。TAPIRはWQROを許容し、結果inconsistent-readが起きる。が、これはCCとレプリケーションの両者のために、レプリカのquorumに対して”アプリケーションレイヤーでのvalidation”を利用することで対応している。結果、validation済みのリードは基本的にRQに一致することになる、とはいえconflictがないという特殊なケースにおいてCCプロトコルに部分的にそのオーバーヘッドが隠されるということになるが。それ以上に、TAPIRとMDCCプロトコルにおいては、conflictはより早いパスから実行を遠ざけ、別のより遅いパスにより、メッセージのラウンドを追加的に増えることになってしまう。[注：早いパス・遅いパス(fast path / slow path)というのはもうちょっと他の言い方があるとは思うが、単純にturn aroundとか実行stepでの想定実行時間のことでいいかと]

　この論文では、OceanVistaと呼ばれる、最新のプロトコルを提案する。これにより、地理分散下のtransaction処理について、strictly serializableな分離レベルを提供する。OVはCCとtransactionコミットとレプリケーションを単一のプロトコルに統合し、その機能はviewのコントロール(visibility control)として見なすことができる。我々の考えでは他のtransactionに対するあるtransactionのvisibilityを維持することが一貫した分散transactionの主たるミッションである。multi-versioning(MV)に基づいて、OVは、version watermarkを利用することでvisibilityのトラッキングを、そして、効率的なgossipを利用することで適切なviewの決定の配付(到着か)(arrives at correct visibility decisions)を行う。watermarkはvisibilityのバウンダリーである：watermarkより下(below the watermark)のversionのtransactionは可読であり、watermarkより上(above the watermark)のversionのtransactionは読むことができない。OVは非同期かつ分散的に、集権的なleaderノードを“介さずに”watermarkを生成・gossipさせる。[注：このwatermarkの上下（above/below）ってのは、たいていの場合は単調増加なので、前・後（before/after）でいいのだけど、多軸・多層で判断しないといけないときに不便なのでabove/belowを使うという感じか。または単純にboundaryとして使っているので、そういう言い方になっているかもしれない。わかりづらいときには普通にbelow=before / above=afterで順序として理解してもいいと思う。]

　visibilityコントロールはwatermarkを利用し、conflictするtransactionを並列処理することができる最新の非同期CC(Asynchronous CC=ACC)スキームを可能にする。ACCはtransactionの実行ロジックからtransaction orderを分離する：transactionは同期クロックに基づいて生成されたグローバルなversionによりtotal orderになる。並列性を最適化するために、ACCはread-write transactionを以下の三つの処理に変形する。

-write-onlyの処理　MVストレージのプレイス・ホルダー（すなわちファンクタ(注というかどう見てもFutureです。)）のwrite

-read-onlyの処理　

-特定versionの非同期書き込み

[注：ということで普通にHerbrand sematics的なアレは、実は後述のDependent transactionになっていて、ネタをバラすとこれは件のdeterministic DBの流儀。この辺で読む気力がなくなりますが、まぁCommitプロトコルとReplicationプロトコルの統合はそれなりに見事なので、言いたいことは一旦留保して読み続けるのが吉かと。]

visibilityのwatermark（Vwatermark）は特別なversion numberで、それより下のすべてのtransactionはそのwrite-onlyの処理は完了していなければならない（S-phase）。OVではVisibilityコントロールとMVにより、この処理の大半はたとえconflict transactionであっても並列実行できる。加えて、watermarkのgossipはtransactionのvisibilityをバッチ的に通知することができ、write-onlyの処理に対する効率的なatomicな複合キーでの書き込みにつながる。というのは、Vwatermarkよりも下のすべてのversionはすべてのキーがvisibleになるからだ [注：キー云々の話は、要はPhantomがない、という話だと思われる。]

　レプリカ watermark(Rwatermark)、これより下のtransactionのversionは完全に対応するレプリカにコピーされているが、(このwatermark）は効率的なquorumレプリケーションを可能にする。OVでは書き込みはノードの競合と失敗を自動的に回避するためにWQ（それから非同期のWA）を利用する。書き込みはconflictがあっても早いパスでの1ラウンドトリップで行うことができる。あまりの大量のノードで失敗したときは遅いパスで2ラウンドトリップが必要になる。OVは大抵の場合、Rwatermarkより低いtransactionに対してRO（すなわちどのレプリカから読んでもよい）を利用することで一貫性のあるリードを提供することができる。読み込むversionは、完全にレプリケーションされていないものでvisibleな場合でのみ、RQを要求する。

　OVプロトコルは分散transactionの通常ケース、すなわちストプロとキーがわかっているwrite-setを想定している。このtransactionモデルはいくつかの先行事例（16:H-store 24: Janus 29: Calvin）で使われている。

　加えて、事前に宣言のwrite-setなしでのtransactionを、よく知られたテクニック、すなわちreconnaissance query (Sec 3.4)を利用することでサポートしている。注：要するにdeterministicな話なんだが・・・OceanVistaがOceanBaseで採用されていないだろうという理由がこれである。普通に考えてnon-deterministicでないとアプリケーションに著しく不便をかけることになる。Alibabaの基幹であるのであれば、ちょっとありえないのでは。他方、スケールさせて、ある程度の大陸間ベースを考えるのであれば、ブリッジ的なアプリを別途かまして、deterministicに処理するというのは可能で、その限りでこの種のアイデアが使われていてもおかしくはないと思う。）

　OVはOV-DBと呼ばれるストレージシステム上で実装されておりAWSのEC2上でグローバルに分散transactionを評価している。OV-DBと地理分散transactionプロトコルのTAPIRを比較したところ、結果、OV-DBは中盤から高いコンテンション・同時性においてスループットでTAPIRを凌駕し、一方でwatermarkのgossipについては高い遅延を引き起こすことになった。特に、OV-DBは低いpairwiseなconflict rateですら一桁高いピークパフォーマンスを達成し、そしてgossipプロトコルは総じて追加的な一回のWAN-RTTの遅延コストがかかった。実証実験はOVが一回のWAN-RTTというもっともよいケースを達成したことを示す。これはTAPIRと同等である。

2. ARCHITECTURE

　Fig1にOV-DBのアーキテクチャを示す。それぞれのDCに少なくとも一つのgossiperがあり、複数ある場合は単にFTのためであり、よって独立かつredundantに働く。

 Gossiper

gossiperはDC内のvisibilityの情報をwatermarkの形で集め、他の gossipersとそのwatermarkを交換する。グローバルなvisibilityの状態のviewから、gossiperはそのDC内部のwatermarkを生成し配布する。

 DB Server

OV-DBはシャードにパーティショニングされている。各シャードはDBサーバのレプリカのグループ単位で管理されている。DBサーバは以下の三つの機能の責任をもつ

1. Transaction coordinator

クライアントからtransaction要求を受けたときに、各サーバはグローバルなユニークversion：tsをローカルクロック(注：たぶんロジカル)に基づいて、その要求に割り当てる。（例えば、timestampとサーバIDと単調増加のカウンターの組み合わせとか）サーバはそのtsに紐づいたtransactionを各participantにレプリケーションする。それから、transactionの結果(decide)を最初のサーバが返した段階で、クライアントに通知し、値を返す。

2. Multi-version(MV)ストレージ

各サーバはMVストレージのシャードのデータを保持する。各シャードは複製され、consistent hashingでアクセスされる。

3. Transaction execution

transaction ロジックは、各transactionのversion numberであるtsがVwatermarkを下回ったとき(when below)に実行される、各DBのストプロで実行される。

OVプロトコルは以下の原則を実行(enforce)する

P1 transactionはそのversionのorderに従ってeffectする

P2 各coordinatorは単調増加のversion numberのtsをそれぞれのtransactionに割り当て、visibleであるべきでないもっとも低いアサインされたversion number（すなわちSvw Sec3.3参照）を記録しておく

P3 VwatermarkはすべてのDbサーバの最小のSvwよりも大きくてはいけない（注？largeじゃなくてhigh？だと思う）

 上記のプロパティが与えられると、Vwatermarkよりも下のすべてのtransactionは安全にvisibleにすることができる。かつ、より下のversionをもつtransactionが作られる恐れがないのでtransaction orderが固定できる。かように、OVはVwatermarkを利用することで、効率的に多数のtransactionのvisibilityをコントロールすることができる。

 サーバのクロックは同期、たとえばNTPの利用、を想定している。クロックの異常はOVのパフォーマンスにのみ影響し、GoogleSpannerのTrueTimeサービスとは異なり、一貫性保証には影響しない。ネットワークはメッセージについて低品質、順序保証なし、遅延を想定するが、送り手が繰り返しリトライするのであれば結果として正常なサーバにはデリバリーされる。OVプロトコルはどのDC内でも完全な全部のレプリケーションは要求されない。ただし、この論文では分析を簡単にするために完全なレプリケーションを想定している。

3. CONCURRENCY CONTROL AND TRANSACTION COMMITMENT

 OVにおけるtransaction visibilityの管理は非同期かつまとめた（batch）transaction処理を可能にする。ACCはconflictするtransactionを並列に処理するが可能であり、従来のシステムよりも高い並列性を提供することができ、abortまたはブロックによりconflictするtransactionを解決することができる。transaction commitmentはOVプロトコルのvisibility管理に統合され、2PCは必要ない。OVは多くのtransactionのvisibilityの情報を一つのwatermarkにまとめることが可能で、個々にtransactionのvisibilityを管理する（たとえば2PCのような）プロトコルよりも高い効率性を可能にする。プロトコルをより詳しく調べると、OVにおけるread-write transactionのもっともよいレイテンシーはTAPIRと同じということが分かる。すなわち1WAN-RTTになる。また、OVがstrict serializableを提供することの証明をスケッチすることにもなる。

3.1 Asynchronous Concurrency Control

最初に非同期並行性制御（ACC）の手法を提示する。事前にわかっているwrite-setに対するread-write transactionのテクニックになる。その他のtransactionのタイプについてSec3.4に詳細がある。OVは非同期にtransactionを処理する。すなわち：read-write transactionの処理をwrite-onlyとread-onlyと非同期のwriteのシーケンスに変形する。ACCはtransaction orderの決定をtransactionロジックから分離する、これはグローバルなwrite-setのキーの記録により達成される、その後でread-onlyの処理と非同期write-onlyが続く。

Write-only operation

ACCはversionがtsであるtransactionのwrite-setのキーを、Store-phase（S-phase）のversionの値にたいするプレース・ホルダーを利用して記録する。プレース・ホルダーはfunctorであり（注：何度も言うけど普通にFutureだと思う）transaction全体を処理するために必要とされる全部の情報をもつ（たとえば、read-set全体・write-set、パラメータ等）そのようなfunctorが、一般的なマルチ・パーティションのtransaction、当該transactionにおいて、あるパーティションから読まれる値が別のパーティションに書かれる値に影響するようなtransactionをサポートする。S-phaseのtransactionはvisibleでなく、かつそれぞれが別のversionを書き込む、そしてアトミックなマルチキーへのCCを単純化する。MVを利用することで、各transactionはユニークなversionを書き込み、Vwatermarkをgossipすることでvisibleになり、これは２PCでの2round目のメッセージをまとめることと似たような効果がある。

Read-only operationと非同期書き込み

ACCではtransactionはそのversionがVwatermarkよりも下になったときにのみ実行される。これは、tsよりも下にあるversionのtransaction orderが決定されたあとで、Execution-phase（E-phase）で記録されたfunctorが実行されることにより達成される。version tsのfunctorの実行は、まずread-onlyのoperationがtsの直前のversionのread-setのキーを読み（注：そういうreadプロトコルになっているということ）、つぎにtransactionの決定を計算し、クライアントに値を返し、そののちwrite-setのキーに対する最終的な値を計算し、最後に、非同期書き込みで、S-phaseにストアされたfunctorをその最終の値でリプレースする。もし読まれたversionが(値ではなく)functorであれば、DBサーバは再帰的にfunctorを最初に計算し、それから、計算された最終の値を利用してread-onlyのoperationを解決する

 Fig2がACCにおけるtransaction処理のメッセージフローになり、Algorithm1 が（疑似コードでの）手続きになる。ここでは丸でマークされた数字（①）をメッセージフローと疑似コードを結びつけるために利用している。

 まず、transactionがどこかのDbサーバ（ローカルなDCなものがあればそれ）にクライアントから送り付けられる。んで、transaction coordinatorが起動。coordinatorがTidMgr（Tx_Id_manager）をつかって、自分のローカルクロックに基づいて、グローバルにユニークなversion number tsをアサインする。コードブロックだと①、coordinatorがtransactionをそのtransactionのすべてのparticipantシャードにWrite(Sec4.1)する。これを受けたレプリカは、transaction全体をplaceholder(functor)として、そのversion tsの値として保存する。(注：place_holderに値じゃなくて関数（transaction処理、そのもの）をセットする。値を呼び出すときに実行される)　んでその“値”はE-phaseでwrite setの最終的な値にリプレースされる。DBサーバはtsの保存にMV（Sec3.2）を利用し、S-phaseではtransaction間での順序付けを強制はしない。ということで、S-phaseではconflictによるtransactionのabortは決して発生しない。tsがすべてのshardに保存したときにcoordinatorはTidMgrに保存されたtransactionにマークをつける、そうでなければ（注：すなわち「すべてのシャード」の保存できないとき、これはquorumがとれなかったときになるが、その時は要はその順序の場所の合意が取れなかったということになるが、そのときに）abortされる。AbortTxnについてはSec4.1参照のこと。Algorithm 1の9-11行目はレプリケーションの非同期処理になっている。これはnon-blocking(詳細はSec4.2)

 各DBサーバは継続的に最新のVwatermarkをgossiperから受け取り続け、Vwatermarkよりも低いversionをもつtransactionはすべて実行可能な状態にある。transactionはversion番号で順序づけされる。functorの実行は②の、そのversion番号のtsの直前のversionのread-setのキーを読むことで始まる。それから読まれた値に基づいてtransactionが実行される。読み込みは、tsがRwatermark（Sec4.3参照）のよりも下にある場合はもっとも近いレプリカに排他的に行われるかもしれない。③において、実行結果はcoordinatorに送られる。そののち④で、write-setのすべてのレプリカに非同期に書き込まれる。OVは、ストプロのtransactionのロジックはdeterministicなものを想定している。

：すなわち　同じ値を読んだ場合、functorの実行の結果は、同じ結果を出す。また、version tsのfunctorの実行は並列かつ独立に行われる。リプレースされたfunctorの重複実行を避けるために、最初の実行でversion tsのそれぞれのfunctorを最終の値にリプレースする。determinismは同じtransactionの、functorの同時実行が同じ結果を出すことを保証する。なので、coordinatorはfunctor実行の最初レスポンスを受け取るや否やすぐにクライアントに完了を通知する。(注：ここで言っているdeterministicという言い方はもっぱら分散処理のコンテクストでの言い方で、Tx用語でのdeterministicという言い方ではない。ただしOceanVista自体はdeterministic DBに分類される。)

議論：並列性について

read-writeまたはwrite-writeのconflictがconcurrentなtransaction間で発生するときは常に、従来からの同期CC(たとえば2PLとかOCC)はconcurrentに実行することができない[注：かなり乱暴な議論です]　このことは、conflictしているデータへのアクセスに対して、最低でも一回の1WAN-RTTの排他的な”serialize windows”につながる。対照的に、ACCはconflictしている大抵の処理を並列に実行することができる。

 Table１で二つのconcurrentなtransactionのACCのステップの組み合わせに対する挙動、共通のキー上での二つの操作について、並列に実行可能かどうか、を記述している。

二つのtransactionのwrite（すなわち、write-onlyと非同期書き込み）のステップはwrite-setが被っていても並列に書き込むことができる。なぜなら異なったversionを書くことになるだけなので。同様に、write-onlyとread-onlyの並列処理も異なったversionをアクセスすることになる。すなわち、一つがVwatermarkの上であり、他方が下になる。

 ACCの二つのステップが完全に平行に処理できない唯一のケースは、read-onlyオペレーションが、他のtransactionの非同期書き込みと、特定のversionへのconflict(すなわちread dependentな場合)を持つ場合になる。しかし、この場合はたいてい、同期CCのread-writeよりも“contention footprint”で小さいで、かつ持続時間は1-WAN RTTになる。これは以下による

1) 最初のreplicaが非同期書き込み経由で最後の値にリプレースされてしまえば、(たとえば、ローカルDCのレプリカからの読み込み）readは成功する

2) このconflictするversionは他のversionの実行を妨げない。たとえば、ACCは複数のそのような同じキーに対するread-dependentなconflictを異なったversionで同時に解決することができる。

議論：遅延について

TAPIRはWANにまたがるストリームラインのcoordinationに対するプロトコルを利用する。結果として、TAPIRは最良のケースで、（ローカルのメッセージRTTは無視するとして）DCローカルのレプリカを読み、かつ読みも書きもconflictがない場合、1回のWANRTTの遅延が起きる。この遅延は、conflictからのリトライによりcontentionが増加するにつれ、ずっと増加していく。にもかかわらず、この遅延はwriteをvisibleにする非同期のコミットメッセージを含まない。(注：つまりコミットのメッセージは別にまた必要になる)　OVプロトコルでもまた、1WANRTTで最良の遅延を達成する。Fig2からわかるとおり、S-phaseはWANは一つあれば十分で、DC内でレプリカが利用可能な場合は、すべてのE-phaseのメッセージは非同期書き込み、これは遅延に含まれないが、を除き、DCローカルになる。gossipメッセージがDC間にわたりgossipされる。しかし、gossiper (たとえばGとすると)は、仮にGがすでにtsよりも高いwatermarkを受け取っているのであれば、リモートなgossiperからのメッセージを待つ必要はない。Fig2の例でいうと、クロックが同期しているとし、WAN-RTTをTwanとすると、時刻tにおいて、DC2は頻繁に活動しないcoordinatorをもっているとして、gossiper_dc2はgossiper_dc1にtに一致するDvwを送る。gossiper_dc1はgossipメッセージをt+Twan/2で受け取る。また時刻tにgossiper_dc1はtransaction txnに対してtを割り当てる。そのtransactionは時刻t+TwanにS-phaseを完了する。ここで、時刻t+Twanにはgossiper_dc1はすでにDC2のDvwを受け取っている。んで、これはtよりも大きい。結果、gossiper_dc1はgossiper_dc2とのラウンドトリップのメッセージ交換なしで、即時にversion tがvisibleであることが決定できる。

3.2 Multi-version Storage

 DBサーバはMVを利用してデータベースのデータを格納する。APIは他のMVシステムと似ている。すなわちPut(key, version, value)でversionに対する値を保存し、Get（key, version）でversionよりも大きくない最新のversion番号と値を返す。Abort(key, version)はversionをリムーブし、同じversionを二度と受け取らないようにする。ACCで利用するために、我々のMVは二つの追加的な特徴をもっている。一つは、Putする値は、functorでも最終の値のどちらでもよい。保存される最終の値はimmutableで、保存されるfunctorはあとで、最終の値にリプレースされる。Getは常に最終の値を返す、というのはアクセスしたversionが最終の値ではなくfunctorだった場合は、まず、DBサーバはそのfunctorを解決し、それから値を返すから。もう一つは、ACCではGetはVwatermarkより低いversionのみを対象にし、versionの挿入はVwatermarkよりも高いversionを対象にする。我々のMVストレージでは、データをversionでソートして、Getでは素早くversionの取得ができるようにし、時刻の基準値よりも古い不要なversionをGCする。

3.3 Gossip of Visibility Watermarks

　単純に、P3の属性を満たすために、全部のDBサーバにアクセスし、S-phaseにおける最小のversionによりVwatermarkを取得することができる。しかし、Algorithm 2にあるように、DC内部のメッセージ交換を行うサーバ-gossiperと、DC間のメッセージ交換を行うgossiper-gossiperを利用することで、より効率的で分散処理のVwatermarkを生成するプロトコルがある。

Server visibility watermark (Svw)

 SvwはあるDBサーバにおけるS-phaseでの最小のversion番号になる。それぞれのDBサーバは、S-phaseにおける全部のversionを記録することで、　TidMgrにおけるセット、すなわちTSsetとして、自分のSvwを保持している。TidMgrのcreateTS()が単調増加の番号tsを生成し(Algo1の2行目)、そのときにTidMgrはtsをTSsetに加える。transaction tsがTidMgr.store(ts)をコールし(Algo1の8行目)、自身のS-phaseを完了したときに、TidMgrはTSsetからtsを取り除く。もし仮にTSsetが空でなければ、セットの中の最小のversionがSvwになる。さもなければ、TidMgrがcreateTS()をコールしてtsをSvwtとして生成する。結果、先で生成されるversion番号はすべてより高いものになる。

 DC visibility watermark (Dvw)

 DvwはこのDCにおける最小のSvwに等しいversion番号になる。すなわちDCの内部ではDvwより低いversionはすべてS-phaseを完了している。おのおののgossiperはDC内部のすべてのDBサーバの最新のSvwのスナップショットを保持することでDvwを生成する。gossiperは継続的にSvwのためにDBサーバをポーリングし、一方、DC内のすべてのDBサーバに対して最新のVwatermarkを発行する。それぞれのDBサーバは減少しないVwatermarkを保持し、別のgossiperが発行した別のwatermarkを受け取った場合は一番高いwatermarkを常に採用する。

 同様に、それぞれのgossiperもまたそれぞれのDCの最新のDvwのスナップショットを、他のgossiperと自分のDvwを定期的に交換する保持する。gossiperは常にそれぞれのDCでもっとも高いDvwを保持するが、これはSvwとDvwが減少しないことによる。Vwatermarkは単純にすべてのDCにわたる最小のDvwのスナップショットとして生成される。

3.4 Other Transactions

 read-only transactionとwrite-only transactionはより一般的なread-write transactionに要求されるACCのいくつかのステップを飛ばすことができる。これによりパフォーマンスが向上する。また、事前にwrite-setがわからないdependent transactionの実行についてもこのサブセクションで説明する。

Read-only transaction

 ACCはコンテンションにも関わらず、1ラウンドのメッセージにより read-only transactionのstrictly serializableを達成することができる。オーバーヘッドはスナップショットの読み込みに似ている。read-only transactionのプロトコルはread-write transactionのそれに似ているが、S-phaseにおいてDBサーバのcoordinatorにfunctorを保存するだけ、というところが異なる。ゆえに、S-phase全体とfunctor-to-coordinatorの通知はcoordinatorサーバのローカルな操作になる。E-phaseはtransactionにアサインされたtsについてread-only transactionを実行するだけである。特に、tsがRwatermarkよりも小さい場合は、read-only transactionを最寄りのレプリカに対して実行することができる。（Sec4.3参照）

Write-only transaction

 write-only transactionのプロトコルはS-phaseで終わる。最終の値をMVストレージに書き込むだけである。coordinatorはクライアントにVwatermarkがtransactionのversionよりも高い限りは通知することが可能である。

Dependent transaction

 すべてのread-set/write-setを決定するためにデータベースの値を読む必要のあるdependent transactionは基本的なプロトコルとしてはサポートされない。しかしながら、よく知られたテクニックである、認識クエリー(reconnaissance query)がこの種のtransactionをサポートできる。reconnaissance queryはdependent transactionのread-set/ write-setを一時的に見つけるために使われるread-only transactionである。dependent transactionはこの一時的なデータセットに基づいて実行されるが、E-phaseの最初にreconnaissance queryで生成された一時的なread-set/write-setがまだ有効かどうか値を再リードすることによって確認される。もしベリファイが失敗すれば、transactionの実行結果は”abort transaction”になる。そうでなければ当該transactionは基本的なプロトコルと同じように実行される。[注：ということで、RMWな処理が多発する大規模な書き込み処理を一斉に投げこむときわめてパフォーマンスが落ちる]

3.5 Strict Serializability

 ここではOVがすべてのコミットされたtransactionについてstrict serializabilityを保証することの証明のスケッチを提示する。定式的でない言い方をすると、そのようなtransactionのスケジュールがserializableであるのは、そのスケジュールがいくつかのserialなスケジュールと等価であるときである。Strict serializabilityは、それに加えてserialization orderが、オーバーラップしない（注：Txの実行が重ならないという意味）transactionでのリアルタイム（実時間）での事前のorderと互換であることを要求する。[注：これは合ってます]後者の属性はconcurrent data structureの文脈ではlinearizabilityとして参照される。[注：これは言い方として不十分という意味で正確ではない。個人的にはこの手の言い方は背後にCSR・full-schedule前提のドグマがあるように見える。もちろん、その前提であればlinearizableとserializableのintersectとしてstrictは正しいとは思う。]

 定式化せずに言うと、それぞれのtransactionが、実行と結果をかえすまでの間の、ある時点で効果を発現する(appear to take effect)のであれば(if)、コミットされたスケジュールがstrictly serializableとなる。このある時点をあるtransactionのserialization point(SP)と参照する。[注：この言い方だとtransactionごとにSPがあるということになる]

Serializability

 OVで実行されるtransactionはP１の原則によりversion番号の順に効果を発現する。transactionは常に自身のversionの直前versionのキーを読む(Algo1 16行目)かつその更新はより高いversionのtransactionにしか見ることができない。

 Strict ordering

 それぞれのtransactionのSPを以下のように組みあげる：version tsをもつ、あるtransactionのSP(以下sp_i)はシステム内の最初のレプリカサーバがts_iよりも大きいVwatermark を受け取ったその時間になる。別の言い方をすると、sp_iはTiが別のサーバから見えるもっとも早い時間になる。我々は、ある一つの時刻で一つのtransactionだけが見えるようになる、ことを想定している、すなわち、SPは二つのtransactionについて同一であることはない。また、sp_iがtransaction Tiの実行開始と結果返却（invocation /  response）の間にあることも簡単にわかる。というのはsp_iはTiのE-phaseの中になければならないから。また、OVにおけるTiの実行はsp_iで効果(take effect)を現す、以下。

1.Tiの更新はsp_iよりも前にはvisibleではない。これはsp_iより前にはどのサーバもts_iよりも大きなVwatermarkを持たないからだ。さもなければsp_iの定義に矛盾する。

2.Tiの更新はsp_i以降、他のtransactionに対してvisibleになる。Algo1により、sp_i以降、より高いversion番号をもつtransaction Tj (ts_j > ts_i)のみがTjのE-phaseにおいてVwatermarkがts_iよりも大きい、すなわちTiがvisibleであるとき、そのときにTiの更新を読むことができる。

Serializable order matches strict order

 OVのスケジュールにおいて、どのふたつのコミットされたtransaction TjとTiについても、そのversion 番号がts_j>ts_i（serializable order）を満たすのであれば、sp_j>sp_i(strict order)であることの証明を簡単に示す。これはtransactionがSPとまったく同じようにversion番号によって順序されるということを意味する。これは背理法で証明できる。

 sp_jにおいて、レプリカRはVwatermark>ts_jなるVwatermarkをsp_jの定義よりもたなければならない。議論のために、sp_i>sp_jか、さもなければsp_j>sp_iとし、strict orderはserializable orderと一致するとする。これはレプリカRにおいてはTiはvisibleではないということを意味する。よって、Vwatermark<=ts_iとなる。よって、ts_i>=Vwatermark>ts_jであり、これはts_j>ts_iに矛盾する。よって、OVはstrict serializabilityを保証する。(注：特に異論はないと思う)

3.6 On Clock Skew

 coordinatorは同期のとれた（NTP）ローカルクロックからのtimestampを利用して、グローバルなユニークtransaction versionを生成する。SvwとDvwが単調増加する限り、我々のプロトコルではtimestampと実時間との乖離については、なんら要求はない。よってクロック異常はACCの正しさには影響を及ぼさない。

 クロック異常にもかかわらずwatermarkの単調性属性を保証するには、プロトコルで以下のルールを適用する。まず第一に、coordinatorはもっとも高い割り当てられたtimestampすなわち lastTSを記録し、生成されたtimestampがlastTSよりも低いときは常に再生成するようにする。次に、初期化中は、coordinatorはDCのすべてのgossiperで新しいcoordinatorがアクセプトされるまで(後述)、クライアントの要求は受け付けない。最後にDvwの単調性属性を強制するために、gossiperはcoordinatorからのSvwがDvwよりも高いときに限り、新しいcoordinatorを受け入れる。

 しかしながら、クロック異常はシステムのパフォーマンスに影響を与える。transactionはそのversion番号で順序付けられるので、より“早い時計”で割り当てられたtransaction番号は、transaction処理が不当に遅らせられ、遅延ペナルティを引きおこす。この副作用は以下の戦略により軽減することができる。まず、同じDC内部のサーバはLANで接続された同一のローカルタイムソースを利用し、単一のDC内部でのクロック異常を小さくする。次に、coordinatorは新しいクライアントの要求を、自身のクロックが異常な場合は、受け付けない。クロック異常はいくつかの方法により検出される、すなわち、タイムソースや対になっている（たとえば、他のDBサーバやgossiper）の時刻と大きな差を検出したり、または、ローカルクロックとVwatermarkとの大きな時刻ギャップを検出したりする方法による。

4. REPLICATION PROTOCOL

 OVはCCとレプリケーションを単一のgossipベースのvisibilityコントロールに統合している。統合プロトコルのアイデアは以前研究（[18/24/25]）から借りてきたものだ、とはいえ、我々のgossipベースの、watermarkを利用することでコンパクトに表現されるvisibility情報を利用するアプローチは、地理分散データにより効率的なレプリケーションを可能にしている。我々のレプリケーションスキーマは、レプリカのスーパー・クオーラム（super quorum：Fast paxosで定義されているもの　[注：しかしながらFastPaxosでは”super quorum”という言い方はない。後述にあるように|2/3f|+1)のことだと思われる。そもそもFastPaxos自体が複数のquorumを利用するスタイルなので、そういうやり方をしているよ、という程度の意味しかないような気がする]が利用できる限りにおいて、conflictにかかわらず、書き込みは１RTTで成功し、また、ひとたびmajority quorumが利用できれば、2RTTで完了する。これはどちらが先にきてもよい。read-onlyの操作に関しては、ACCにおいてこれらは常に対象versionにタグ付けされる。 

 watermarkのgossipにより、読み込みは常に対象versionがRwatermarkよりも低い時はどのレプリカからも行うことができる。これは通常の要求に対するWQRO(Write-quorum, read-one)を達成している。対象のversionがRwatermarkとVwatermarkの間にあるときは、読み込みは適合するversionのquorumを見つけために追加的レプリカにアクセスする必要がある。

4.1 Write-Only Operations

 S-phaseでのtransactionは排他的にwrite-onlyの操作を行う。すなわちWriteとAbortTxnである。Fast PaxosとTAPIRの合意手順をまねて（inspired）Writeは特定のversionが保存されたかどうかについて合意をとる。これは早い手順（fast path）の場合は1RTTで十分で、遅い手順（slow path）の場合は2RTTが必要になる。Fast PaxosやTAPIRと違って、これらはconflictが検出された場合は遅い手順になるというパフォーマンスペナルティがあるが、OVでのWriteはほとんどconflictフリーであり、これはMVを利用して単にグローバルなユニークversionを挿入するだけ（S-phaseではリードしていないことを思いだすこと）だから。我々の場合で遅い手順が必要な場合は、障害(failure)と調停が必要な場合（stragglers）の時のみである。2f+1レプリカ配下でのfのレプリカ障害を許容するために、FastPaxosと同様に、早い手順では利用可能なレプリカのsuper quorum(3/2f+1)が必要になる。また、遅い手順では単に利用可能レプリカのmajority quorum（f+1）が必要になる。単純に比較するために、TAPIRでの用語を利用して以下にプロトコルを説明する。

 1.coordinatorが[key,ts,value]をシャード内部の全部のレプリカに送る。んで、一時データとしてそれぞれのレプリカが保存する。んで、まずはレプリカは成功を返す

 2.Fast path(早い手順)

タイムアウト前にレプリカのsuper quorumが返れば、coordinatorにはfast pathを選択して、呼び出し側に成功を通知する。それから、非同期にすべてのレプリカに[FINALIZE, ts]を送る。

 3.そうでない場合は、すなわちmajority quorumが返ってきた場合、slow pathをとる。coordinatorはすべてのレプリカに[FINALIZE, ts]を送る

 4.FINALIZEを受け取った場合、各レプリカはversionにFINALIZEDをマークして、CONFIRMをcoordinatorに返す。

 5.Slow path(遅い手順)

coordinatorはf+1のCONFIRMが返ってきたときに呼び出し側に成功を返す。そうでない場合、もしレプリカのmajorityが利用できない場合はfailを返す

 AbortTxnはそれぞれのシャード上で、（abort）判断がフォールトトレーランスにレプリケートされた時に成功する。シャードはそれぞれレプリカのmajority quorumが返る限り成功する、というのは、Writeの一時的な状態とは異なり、abort判断は決して再実行されないからだ。AbortTxnのプロトコルは以下になる

 1.coordinatorは参加しているシャードのすべてのレプリカに[ABORT, key, ts]を送る。それぞれのシャードからレプリカのmajority quorumがひとたび返れば、呼び出し側に通知する。

 2.リクエストを受けたときに、シャードはそれぞれAbort(key, ts)をコールして、coordinatorに成功を返す。

  AbortTxnはalgo1の9-11行目にあるような非同期実行を必要とし、これはすべてのレプリカがabortに成功したことを示すために利用される。

4.2 Replica Watermarks: Rwatermark

 replica watermark (Rwatermark)は特殊なversion番号で、それ以下のtransactionはすべての参加しているレプリカにwrite-onlyの処理はリプレケートを完了して居なければならない。Rwatermark以下のversionへのread-onlyの処理はすべてのレプリカ（例えばローカルのDCのレプリカ）の値に直接アクセスできる。Rwatermarkのgossipプロトコルは単純にSec3.3になるVwatermarkの生成プロトコルを拡張したもので、追加的なフィールドすなわち、server replica watermark(Srw), DC replica watermark(Drw), Rwatermearkを加えている。

 gossipされた情報は以下にように利用される。Vwatermarkは、transactionのversionがほかのtransactionにvisibleかどうかを決定するCCとコミットに利用され、Rwatermarkは、レプリケーション・プロトコルにおいて、どのレプリカ（たとえばもっとも近いレプリカ）でも読めるように設計されている。特に、gossiperは最小のDCワイドのSrw利用してDrwを生成し、すべてのDCのなかの最小のDrwを利用してRwatermarkを生成する。それぞれのDBサーバでは、TidMgrが、完全にレプリケートされていないwrite-onlyの操作のすべてのversion番号を記録することでSrwを保持する。また、DBサーバでは自動的にRwatermark以下のすべてのversionをFINALIZEDとしてセットする。Alog1の9行目で、tsの完全なレプリケーションについての通知をTidMgrに行う非同期の手続きを開始することに留意すること。この手続きはwrite-onlyの操作（WriteとAbortTxn）が全部のレスポンスが返った段階で実行され、trasactionのE-phaseの最中かその終了後に行われる。Rwatermarkのgossipのプロトコルの詳細はVwatermarkのそれと似ているので、ここでは省略する。

 Rwatermarkのプロトコルはシャード・Rwatermarkやホスト・Rwatermarkに拡張できる。言い方を変えると、gossiperとDBサーバは、シャードやホストについてのSrw・Drw・Rwatermarkをそれぞれ別の塊として持つことできる。

4.3 The Read-Only Operation

 Read-onlyの処理、すなわちRead(key, ts)(ただし、ts<Vwatermark)は、keyについてts以下の最新のversionを取得する。ts<Vwatermarkの場合は、ReadはGet(key,ts)をどのレプリカに対しても直接コールすることができる。ということで、以下はRwatermarkとVwatermarkの間にあるversionのリードについて集中して述べる。

 Get(key,ts)はSec3.2にあるように、versionと値を返すだけではなく、レプリケーションのタグであるTENTATIVEかFINALIZED (Sec4.1参照)も返す。シャードにおいて2f+1のレプリカを想定するのであれば、

versionがtsであるtransactionでVwatermarkよりも低いものは以下のふたつのケースのどちらかでなければならない。さもなければ、visibleではない。

1. tsのWriteが成功している。すなわち、少なくともf+1のFINALIZEDなレプリカか、または、3/2fを越える最小の整数＋1のTENTATIVEかFINALIZEDなレプリカがある

2. tsのAbortTxnが成功している。すなわち、最大でもfのTENTATIVEなレプリカ、かつ、FINALIZEDなレプリカがない。

TENTATIVEまたはFINALIZEDな場合は、Writeが早い手順で成功した場合で、TEANTATIVEなレプリカのいくつかは非同期の確認(confirmation)でのFINALIZEDのタグを採用する場合になる。

　ということで、read(key, ts)はすべてのレプリカに要求を送り、最速のsuper quorumが返る（またはタイムアウトでのリトライ）のを待つか、ts以下の最大のversionで最低でも一つのレプリカがFINALIZEDかまたはf+1のレプリカがTENTATIVEであるものを見つけることになる。これをreadのためのMATCH CONDITIONと呼び、最大のversionをMATACHED VERSIONと呼ぶ。アボートされたversionはMATCH CONDITIONは満たさない。最大のコミット済みのversionはレプリカのsuper quorumにあるのであればMATCH CONDITIONを満たす。このread(key,ts)のプロトコルはAlog3になる。 

5. FAULT TOLERANCE

 レプリケーションはOVに保存されたデータを恒久的な喪失から防ぐ。しかし、coordinatorとgossiperの失敗は、gossipベースのvisibilityコントロール・プロトコルのwatermarkの伝播を止めることになる。結果、可用性が損なわれる。この章では、サーバ・gossiper・DCワイドでの失敗からリカバリーのためのプロトコルを提示する。これらのプロトコルはデータベースがリカバブルであることを想定している。すなわち、2f+1までのレプリカでのfまでの失敗を許容するには、すくなくともすべてのシャードについてレプリカのsuper quorumが利用可能であるということを意味する。この前提において、リカバリープロトコルはSec4.3のreadを利用して、versionをリカバリーすべきか破棄するべきか決定することができる。

5.1 Membership Representation

 シャードとサーバのロケーションを記録するために、OVはcoordinationサービスとして、RaftかZKを利用する。ぞれぞれのシャードは自分のメンバーシップを保持し、状態の変更（view）は単調増加の番号により区別さえる。それぞれのサーバはすべてのシャードの最新のviewをキャッシュしており、これはサーバ間の通信により、対象となるシャードのview番号が含まれている。サーバは通信によりそのviewが古いかどうか判断し、自身のviewを更新する。TAPIRと同じように、VIEW-CHAINGINGな状態にあるサーバは、リカバリーを除き新たな要求は処理しない。

Corfuのように、transaction versionのレンジにより異なったmembershipをもつことができる。たとえば、version[0, ∞]をカバーしているmembership<A,B,C>のシャードは、失敗したサーバCをversion1000から始まるサーバDに置き換えることが許される。すなわち、membershipの新しいviewは<A,B>で、[0,1000]をカバーし、かつ<A,B,D>で[1001, ∞]をカバーする。またその間、サーバDは1000以下のversionをリカバリーする。

5.2 Coordinator Failure

 visibilityコントロールはcoordinatorからのwatermarkの集合に依存している。ということで、素早いcoordinatorの失敗の検出とリカバリーは重要である。coordinatorの失敗検出はgossiper-coordinatorの通信と統合されており、というのはすでにこれらがwatermarkを頻繁に発行・集約しているからである。それ以上に、gossiperとcoordinatorは常に同じDCにいるし、WANよりもネットワークの挙動が予測可能である。加えて、coordinatorは高負荷によるレスポンスの遅れを防ぐために、load shedding(高負荷時に新しいクライアントからの要求を撥ねる)や資源分離（CPUへの排他アクセス）を利用する。

　各々のcoordinatorは自身の失敗のときに処理中のtransactionを完了させるために代替になるバックアップのcoordinatorをローカルのDC内部にもっている。なお、write-onlyの処理（WriteとAbort）の実行だけがgossiperのvisibilityコントロールに影響することに留意すること。ということで、coordinatorは（実行前の）writ-only処理と（実行後の）処理決定については、同期レプリケーションをバックアップcoordinatorと行う。これは、バックアップcoordinatorがすべての実行中のtransactionをもつことを保証する。gossiperが失敗したcoordinatorを疑って、リプレースを実行する場合は、バックアップcoordinatorにメッセージを送る。gossiperはwatermarkを生成するためにバックアップcoordinatorのステータスを利用する。フェイルオーバーの最中は、バックアップcoordinatorはオリジナルのcoordinatorからのレプリケーションのリクエストを受けることを停止する。これはオリジナルのcoordinatorは実際には失敗してなかった場合に（いったん）機能停止にしておくことによる。バックアップのcoordinatorは単純にすべての実行中のwrite-onlyの処理を再実行する。すでにabortされたすべてのtransactionは、abortされたversionをレプリカのmajorityが受け入れないように（promised）失敗しなければならない（Sec3.2参照）。coordinatorとそのバックアップの両者が失敗するような場合でも、いかなるコミットされたtransactionも失われない、というのは、どのtransactionもDCにわたってレプリケーションされるからだ。解決されないfunctorは次回アクセスされたときに最終の値にリプレースされるからだ。

5.3 Replica Node Failure

 レプリカのノード失敗は、quorumが利用できる限り、シャードの機能を損なうものではない。というのは、レプリケーション・プロトコルがすでにフォールト・トレランスを提供しているからだ。ということで、レプリカノード失敗の検出と回復はより長い通信遅延を許容できる。メンバーシップ構成のプロトコルは、失敗したレプリカノードを新しいノードに置き換えるが、詳細は次に記述する。

 シャード内のリーダ選出は手続きの再構成を行うためにRaftかZKでの利用を想定している。まず、リーダはVIEW-CHANGINGメッセージを全部のメンバーに送り、生き残っているメンバーは記録している最大のtransactionのversionを返す。次に、リーダは新しいメンバーシップに対して、新規にスタートするversionであるnewTSを選択する。これは生き残っているメンバーから返ってくる記録された最大のtransactionのversionになる。新しいメンバーシップは2つのレンジで構成される。一つはversion[0,newTS]でquorumサイズを変更せずに生き残っているメンバーで利用される。もう一つはversion[newTS, ∞]でこれは生き残ったメンバーに新しいノードを加えて利用される。リーダはメンバーシップのviewタグを更新して、新しいメンバーに送る。その次に、新しいノードは直ちにnewTSの上のversionを利用することを始め、newTSがVwatermarkよりも下にある場合は、newTSよりしたのversionをリカバリーする。versionのうちの失われた範囲については、生き残っているメンバーからバルクで引っ張ってくる。Sec4.3でのReadと同じように、MATCH CONDITIONを満たすversionはFINALIZEDとして保存されるべきで、そうでなければ破棄されるべきだ。最後に、新しいノードがnewTSに追いついたときに、リーダはメンバーシップを更新し、二つのversionのレンジ（＜＝newTSとnewTS<）を一つにマージする。

5.4 Gossiper Failure and Datacenter Failure

 単一のgossiperの失敗はwatermarkの進行に影響はない、というのは、どのDCにも独立かつ冗長的に動く複数のgossiperがあるからだ。しかし、一つのDC全体から更新が失われた場合、watermarkの進展の妨げになる。というのはDCワイドのwatermarkが失敗したDCによりリフレッシュされないからだ。これは、あるDCのすべてのgossiperが、DSCワイドの災害により利用できないときに起こりうる。

 プロトコルは、サーバがそれぞれのDCのメンバーシップのviewをキャッシュしていることを想定している。まず最初に、失敗したDCが取り除かれ、新しいメンバーシップがそれぞれのシャードの、失敗からのリカバリーリーダに送られ（Sec5.3の第二パラグラフ参照）、次に、それぞれのリーダが新しいメンバーシップをそれぞれのシャードレプリカに送り、レプリカは、失敗したDCからcoordinatedされたtransactionを受け入れないように、最大の記録されたtransaction versionを返す。それから、リカバリーのプロセスは、シャードの全部のリーダから最大の記録されたversion番号、maxRecordedTSを集計する。失敗したDCはVwatermwarkとmaxRecordedTSの間になるversionのvisibilityコントロールにのみ影響があることに留意すること。というのは、Vwatermarkより小さいversionはvisibleであることが確認されていて、maxRecordedTSよりも上のすべてのversionは失敗したDCからはcoordinateされていない。その後、リカバリープロセスはVwatermarkとmaxRecordedTSの間のtransactionの状態を収集し、Alog1になるCoordinateの手続きに従って、transactionの決定を計算する。最後に、maxRecordedTSより下位のversionの状態が解決されたあと、リカバリープロセルは新しいDCのメンバーシップとmaxRecordedTSを新しいVwatermarkとして、すべての残っているgossiperに送る。