Google App EngineのDatastoreは良く使っているのだが、
実際理解しているかと言われると、なんとも微妙なので、
自分なりに反芻してみることにした。の第一回。

Datastore HRDの特徴について

• （予期しない）ダウンタイムがない
• トランザクションをサポート
• 読み込み書き込みに対して高い可用性
• 先祖クエリに対する強い一貫性
• 他のクエリーに対しては結果整合性

AppEngineは高レプリケーションデータストアを採用していて、データはPaxosアルゴリズムに基づいて複数のデータセンターに格納されている。
※Master/Slaveデータストアのオプションも使えるがこちらは現在非推奨となっている。
まず、高レプリケーションデータストア(HRD)についてだが、これによってDatastoreの高可用性を提供している。データのコピーを保持するデータセンターの数を増やし、リアルタイムに Paxosアルゴリズムを使用してデータセンター間におけるデータの同期を行っている。（トラブルや計画的なデータセンターの停止などで、従来のMaster/Slaveデータストアでは、一時的に使用できなくなっていた）
ただし、複数のデータセンターに書き込みが行われるために、CPU消費と書き込み遅延が発生する。また、整合性においてMaster/SlaveデータストアとHRDの違いは前者が強い整合性を提供するが、後者はほとんどのクエリーで結果整合性となる。

Paxosアルゴリズムについて

筆者はPaxosアルゴリズムについて全く無知なので、「Paxos Made Simple」という論文を読んでみた。
ありがたい事に翻訳して頂いていたので、翻訳：Paxos Made Simple読んでみた。非常に要約すると、proposer(提案者)とacceptor(受容者)とlearner(学習者)のロールがあり、ただ１つのみがproposerを演じ、残りはacceptorとなる。proposerが提案を行うとacceptorで承認する。その承認が過半数に達した時点で、他のacceptorに対しては認証したと見なす(learner)。
こちらの記事が分かりやすかった。Henry Robinsonによる優しいPaxosの解説

このPaxosアルゴリズムを適用しているChubbyという分散ロックサービスがある。Chubbyは通常５台のマシンから構成されていて、「Chubbyセル」と呼ばれる。各マシンはどれもマスターになれる。ロックサービスとして利用できる理由は、Chubbyはノードのディレクトリ、ファイルにロック機構をもっているからである。
ロックの実装にはシーケンサー(ロックの情報をもったバイト列)を仮想同期が用いられている。
マスタは各レプリカの投票により選定される。このコンセンサスアルゴリズム（合意アルゴリズム）にPaxosを適用している。
ただし、Paxosのプロトコルはそのまま用いることはなくマスタリースという一定時間が与えられ、
受託から始めることができる。
BigtableやGFSにもChubbyが利用されている。Bigtableにはマスターの選択、マスターによる探索可能なサーバーの探索に使われ、GFSには、マスターサーバーの予約の為にロックが用いられている。おそらくDatastoreにもBigtable同等なかたちでメタデータの管理にChubbyが使われているのではないかと想像した。

Datastoreの結果整合性について

結果整合性とは、高い可用性を実現する為に一貫性は弱い物でよいとするが、結果を返すというもので、しばらく更新が無ければレプリケーションも含めて結果的に整合性が取れたデータを取得できる
というデータ一貫性に於けるモデルの一つである。
結果整合性に関連してCAP定理やらBASEやらACIDとか出てくるが、まず、CAPのPを分散と勘違いしてはいけない。
また、ACIDとCAPに於けるConsistencyの違いはCAPのCとACIDのCここが参考になる。
また最近このCAP定理についても見直されていて、CAP定理すなわちC：Consistency（一貫性） A：Availability（可用性） P：Tolerance to network Paritions（ネットワーク分断への耐性）のうち２つしか達成できないという公式だが、この認識を覆す諸説も出ている。12年後のCAP定理: “法則”はどのように変わったか

また、NoSQLではほとんどが結果整合性をとっているのだが、
Google App EnigineのDatastoreでもそうであるように、強一貫性をQueryによって選べるデータベースも
増えている。SimpleDBやOracle NoSQLデータベースがそうだ。

今回はここまで。
引き続きDatastoreについて反芻していく。