Paxosお勉強メモ
Paxosのお勉強メモです（以下、分散システムとか無知なのですごく勘違いしてる可能性ありますので要注意）
Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures.
- Paxosは、信頼性の低い複数の処理ノードによるネットワークで「コンセンサス」を得るための各種手順
- コンセンサスとは、グループの参加者間で1つの結果について同意を得るプロセス
- 各参加者やそれらの間の通信手段に障害が発生しうるケースでは、コンセンサスの確立が難しい
- （PaxosのLeslie LamportはDECにいたらしい。やっぱクラスタと言えばDECか）
Paxos自体は汎用的なアルゴリズムでさまざまな問題に適用できますが、最近のNoSQLの文脈で語られるのは「データストアをマルチマスター構成にしたときに、どうやってデータの整合性を効率的に確保するか」って問題へのPaxos応用です。伝統的には、全マスター間で保存する内容について同期的に同意を得てからコミットする二相コミット（2PC／XA）が用いられてきました。ではPaxosはどう働くのでしょうか。NOSQL PatternsはNoSQLにおけるデザインパターンが簡潔にまとめられててたいへんありがたいページですが、ここにPaxosの簡単な説明がありました。
Quorum Based 2PC A more efficient way is to use the quorum based 2PC (e.g. PAXOS). In this model, the coordinator only need to update W replicas (rather than all N replicas) synchronously. The coordinator still write to all the N replicas but only wait for positive acknowledgment for any W of the N to confirm. This is much more efficient from a probabilistic standpoint. However, since no all replicas are update, we need to be careful when reading the data to make sure the read can reach at least one replica that has been previously updated successful. When reading the data, we need to read R replicas and return the one with the latest timestamp. For "strict consistency", the important condition is to make sure the read set and the write set overlap. ie: W + R > N As you can see, the quorum based 2PC can be considered as a general 2PC protocol where the traditional 2PC is a special case where W = N and R = 1. The general quorum-based model allow us to pick W and R according to our tradeoff decisions between read and write workload ratio. If the user cannot afford to pick W, R large enough, ie: W + R <= N, then the client is relaxing its consistency model to a weaker one.
- （伝統的な2PCよりも）効率的な方法として、quorum based 2PC（PAXOS）がある
- N個のレプリカ全体を更新するが、そのすべての更新確認を同期的に待つのではなく、うちW個からの返事だけを待ってOKとする
- データを読むときは、R個のレプリカからデータを取得し、最新のタイムスタンプを持つものを採用する
- 「厳密な整合性」が必要な場合は、W + R > Nである必要がある。従来の2PCは、W = NかつR = 1のケースに相当する
- W + R <= Nの場合は、より低い整合性となる（可用性やパフォーマンスとのトレードオフ）
もひとつ、kuenishiさんによるPaxos説明から引用：
What is PAXOS? -Distributed Consensus/Coordination Algorithm --Masterless (No SPOF) --Robust to split brain environment such as network separation --Proved to converge within infinite time period[9] --Works iff majority of fixed group actors is alive and communicable
- Paxos＝分散合意／コーディネーションアルゴリズム
俺様解釈：
- Chubbyロックやquorumサーバーみたいなタイブレーカーがなくても、対等なノード間で話し合ってさくっと結論だせるよ
- 2PCみたいに全ノードで同期する必要ないからパフォーマンスと可用性が高いよ
- （こんな解釈でいいのかな。。。？いまいちわからん）
過半数のノードでコンセンサスを取ってグループ全体の結果を集約するという仕組みは、HAクラスタソフトであるHP Serviceguardを多数ノードで運用したときのフェイルオーバー手順によく似てるなと思いました。80年代からある手法みたい。
Bigtable?
ちなみに、Bigtableではデータが複数のGFSチャンクサーバーにコピーされますが、マルチマスターじゃないので（ツッコミ歓迎）、分散ロックサービスChubbyを使って更新処理はひとつのマスターに対して同期的に実施されるようです。
The Chubby lock service for loosely-coupled distributed systems
We expected Chubby to help developers deal with coarse-grained synchronization within their systems, and in particular to deal with the problem of electing a leader from among a set of otherwise equivalent servers. For example, the Google File System [7] uses a Chubby lock to appoint a GFS master server, and Bigtable [3] uses Chubby in several ways: to elect a master, to allow the master to discover the servers it controls, and to permit clients to find the master. In addition, both GFS and Bigtable use Chubby as a well-known and available location to store a small amount of meta-data; in effect they use Chubby as the root of their distributed data structures. Some services use locks to partition work (at a coarse grain) between several servers.
- Chubbyは、開発者が各種システム内で粒度の大きな同期処理を扱う際のサポートを想定して提供されている（特に複数の同等のサーバー間でリーダーを決める問題への対処）
- 例えば、GFSではChubbyロックを使ってGFSマスターを指名している。
- BigtableではChubbyをいくつかの目的で使用している：
- マスターの選択
- マスターが管理する各サーバーの発見
- クライアントによるマスターの検索
- また、GFSとBigtableではChubbyを小規模なメタデータを保存する置き場所として使っており、それらの分散データ構造のルートとなっている
- いくつかのサービスでは、処理を複数のサーバーに（大きな粒度で）分割するためにChubbyロックを使っている
以下想像：
- Bigtableの各行（もしくはDatastoreのエンティティグループ）は1つのマスター（となるタブレットサーバーやGFSチャンクサーバー）に対してのみ更新処理されてる（マスターがダウンするとスレーブがマスターになる？）
- だから1行や1EGへの更新処理では2PCやPaxosをやってるわけではない。Chubbyがタイブレーカーとなってマスターを管理してるからsplit brainは発生しない（Chubbyサービスや通信の障害時はどうなる？）
- 複数のBigtable行やDatastore EGをまとめてひとつのtxを実装しようとすると、マルチマスターとなり、PaxosとかBASEが必要になる。。？（←このあたりで脳みそパンクしてます）
結論：よくわかりません
追記
ちなみに、Bigtable論文には「Chubby uses the Paxos algorithm [9, 23] to keep its replicas consistent in the face of failure.」とあり、Chubby内部の冗長化にはPaxosを使っているようです。
あわせて読みたい、@kibayosさんによるPaxosじゃんけん：
P2Pジャンケン解いてみた
あとこれも見つけた：
分散システムにおける信頼性と総意（クォーラム・コンセンサス）
2PC は調整役が落ちると他の参加者がブロックするという弱点がある。で、ロックを掛けてブロックしてるわけだから、このリソースを誰かが読み込もうとした場合そいつもブロックされる。で、調整役が帰ってこないと参加者全員がブロックされたままという状態になる。 問題点 - 2PC をどうやって耐故障にするか - 複製の一つが到達できない場合にオブジェクトをどうやって書き込みするか
2PCの問題点、な〜るほどね。
あと、Chubby論文の日本語まとめも見つけた：
http://dspace.info.gscc.osaka-cu.ac.jp/~fujita/RESEARCH/KANSAIP2P/chubby.txt
Paxosの元論文（解読不能です）：
http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf
