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

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

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

一、Master/slave

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

二、Multi-master

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

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

三、Two-phase commit(2PC)

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

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

Phase 1

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

Phase 2

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

Failure 典型失敗情況分析

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

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單。
缺點(diǎn)：所有參與者需要阻塞(block)，throughput低；無(wú)容錯(cuò)機(jī)制，一節(jié)點(diǎn)失敗則整個(gè)事務(wù)失敗。

四、Three-phase commit (3PC)

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

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

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

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

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

五、Paxos

Google Chubby的作者M(jìn)ike 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算法的改進(jìn)

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

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

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

(圖片來源：http://snarfed.org/space/transactions_across_datacenters_io.html)

后文會(huì)繼續(xù)比較實(shí)踐環(huán)境選取何種策略合適。

（PS: 寫完后在Google Reader上發(fā)現(xiàn)本文跟王建碩最近發(fā)表的《關(guān)于兩個(gè)機(jī)房的討論》文章有點(diǎn)類似，特別是本文一、二方式。不過他的文章偏MySQL的實(shí)現(xiàn)，我的重點(diǎn)是一致性算法，大家可以有選擇性的閱讀。）

億恩-天使(QQ:530997) 電話 037160135991 服務(wù)器租用，托管歡迎咨詢。

服務(wù)器租用/服務(wù)器托管中國(guó)五強(qiáng)！虛擬主機(jī)域名注冊(cè)頂級(jí)提供商！15年品質(zhì)保障！--億恩科技[ENKJ.COM]