文章內容

多IDC的數(shù)據(jù)分布設計(一)

發(fā)布時間: 2012/9/16 0:52:40

上個月跟某個朋友談及多IDC數(shù)據(jù)同時讀寫訪問的問題(tweet)，當時覺得有不少解決方案，但覺得思路還不夠清晰。最近看了Google App Engine工程師Ryan Barrett介紹GAE后端數(shù)據(jù)服務的演講稿Transactions Across Datacenters(視頻)，用Ryan的方法來分析這個問題后就豁然開朗。

按Ryan的方法，多IDC實現(xiàn)有以下幾種思路。

一、Master/slave

這個是多機房數(shù)據(jù)訪問最常用的方案，一般的需求用此方案即可。因此大家也經(jīng)常提到“premature optimization is the root of all evil”。
優(yōu)點：利用mysql replication即可實現(xiàn)，成熟穩(wěn)定。
缺點：寫操作存在單點故障，master壞掉之后slave不能寫。另外slave的延遲也是個困擾人的小問題。

二、Multi-master

Multi-master指一個系統(tǒng)存在多個master, 每個master都具有read-write能力，需根據(jù)時間戳或業(yè)務邏輯合并版本。比如分布式版本管理系統(tǒng)git可以理解成multi-master模式。具備最終一致性。多版本數(shù)據(jù)修改可以借鑒Dynamo的vector clock等方法。

優(yōu)點：解決了單點故障。
缺點：不易實現(xiàn)一致性，合并版本的邏輯復雜。

三、Two-phase commit(2PC)

Two-phase commit是一個比較簡單的一致性算法。由于一致性算法通常用神話(如Paxos的The Part-Time Parliament論文)來比喻容易理解，下面也舉個類似神話的例子。

某班要組織一個同學聚會，前提條件是所有參與者同意則活動舉行，任意一人拒絕則活動取消。用2PC算法來執(zhí)行過程如下

Phase 1

Prepare: 組織者(coordinator)打電話給所有參與者(participant) ，同時告知參與者列表。
Proposal: 提出周六2pm-5pm舉辦活動。
Vote: participant需vote結果給coordinator：accept or reject。
Block: 如果accept, participant鎖住周六2pm-5pm的時間，不再接受其他請求。

Phase 2

Commit: 如果所有參與者都同意，組織者coodinator通知所有參與者commit, 否則通知abort，participant解除鎖定。

Failure 典型失敗情況分析

Participant failure:
任一參與者無響應，coordinator直接執(zhí)行abort
Coordinator failure:
Takeover: 如果participant一段時間沒收到cooridnator確認(commit/abort)，則認為coordinator不在了。這時候可自動成為Coordinator備份(watchdog)
Query: watchdog根據(jù)phase 1接收的participant列表發(fā)起query
Vote: 所有participant回復vote結果給watchdog, accept or reject
Commit: 如果所有都同意，則commit, 否則abort。

優(yōu)點：實現(xiàn)簡單。
缺點：所有參與者需要阻塞(block)，throughput低；無容錯機制，一節(jié)點失敗則整個事務失敗。

四、Three-phase commit (3PC)

Three-phase commit是一個2PC的改進版。2PC有一些很明顯的缺點，比如在coordinator做出commit決策并開始發(fā)送commit之后，某個participant突然crash，這時候沒法abort transaction, 這時候集群內實際上就存在不一致的情況，crash恢復后的節(jié)點跟其他節(jié)點數(shù)據(jù)是不同的。因此3PC將2PC的commit的過程1分為2,分成preCommit及commit, 如圖。

(圖片來源：http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png)

從圖來看，cohorts(participant)收到preCommit之后，如果沒收到commit, 默認也執(zhí)行commit, 即圖上的timeout cause commit。

如果coodinator發(fā)送了一半preCommit crash, watchdog接管之后通過query, 如果有任一節(jié)點收到commit, 或者全部節(jié)點收到preCommit, 則可繼續(xù)commit, 否則abort。

優(yōu)點：允許發(fā)生單點故障后繼續(xù)達成一致。
缺點：網(wǎng)絡分離問題，比如preCommit消息發(fā)送后突然兩個機房斷開，這時候coodinator所在機房會abort, 另外剩余replicas機房會commit。

五、Paxos

Google Chubby的作者Mike Burrows說過， “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一種一致性算法，那就是Paxos”，所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改進

P1a. 每次Paxos實例執(zhí)行都分配一個編號，編號需要遞增，每個replica不接受比當前最大編號小的提案
P2. 一旦一個 value v 被replica通過，那么之后任何再批準的 value 必須是 v，即沒有拜占庭將軍(Byzantine)問題。拿上面請客的比喻來說，就是一個參與者一旦accept周六2pm-5pm的proposal, 就不能改變主意。以后不管誰來問都是accept這個value。
一個proposal只需要多數(shù)派同意即可通過。因此比2PC/3PC更靈活，在一個2f+1個節(jié)點的集群中，允許有f個節(jié)點不可用。

另外Paxos還有很多約束的細節(jié)，特別是Google的chubby從工程實現(xiàn)的角度將Paxos的細節(jié)補充得非常完整。比如如何避免Byzantine問題，由于節(jié)點的持久存儲可能會發(fā)生故障，Byzantine問題會導致Paxos算法P2約束失效。

以上幾種方式原理比較如下