《Paxos的通俗理解以及在數(shù)據(jù)庫高可用上的使用》要點：
本文介紹了Paxos的通俗理解以及在數(shù)據(jù)庫高可用上的使用，希望對您有用。如果有疑問，可以聯(lián)系我們。

近期大家都在討論Paxos算法,我看了很多網(wǎng)上的文章,總覺得有些晦澀難懂,經(jīng)過一段時間研究,對Paxos有了一些理解,在這里總結(jié)一下,希望能拋磚引玉.

1、為什么需要Paxos

Paxos要解決的問題,是分布式系統(tǒng)中的一致性問題.那么到底什么是“分布式系統(tǒng)中的一致性問題”呢?在分布式系統(tǒng)中,為了保證數(shù)據(jù)的高可用,通常,我們會將數(shù)據(jù)保留多個副本(replica),這些副本會放置在不同的物理的機器上.副本要保持一致,那么,所有副本的更新序列就要保持一致.因為數(shù)據(jù)的增刪改查操作一般都存在多個客戶端并發(fā)操作,到底哪個客戶端先做,哪個客戶端后做,更新順序要保證.如果不是分布式,那么可以通過加鎖的方法,誰先申請到鎖誰就先操作,但這就存在單點問題.Paxos協(xié)議主要有兩種用法：一種用法是用來實現(xiàn)全局的鎖服務或者命名和配置服務,例如Google Chubby以及Apache ZooKeeper.另外一種用法是用它來將用戶數(shù)據(jù)復制到多個數(shù)據(jù)中心,例如Google Megastore以及Google Spanner.

以一個分布式的KV數(shù)據(jù)庫為例,假設數(shù)據(jù)庫對外提供2種操作Put和Get,具體架構(gòu)如下：

在這樣一個架構(gòu)下,可以通過多臺server組成集群來避免單點問題.我們需要解決的是3臺server必須保持同步,也就是說,如果向集群發(fā)送請求Put(“a”,1)并成功,那么整個集群任意一臺server必須含有(“a”,1).另外假設此時多個client并發(fā)訪問集群,不同客戶端的請求可能會落入到不同的server機器上,比如并發(fā)有Put(“b”,2)和Put(“c”,3),我們需要保證哪個客戶端請求先做,哪個后做,保證更新順序,這就是Paxos算法需要解決的問題.

2、Paxos算法

我們先來簡單描述一下Paxos算法,對算法本身有一個直觀的認識,然后再結(jié)合后面的例子來進一步理解.

在Paxos算法中,主要有3種角色：

• Proposer：提議者
• Acceptor：決策者
• Learner：最終決策學習者

實現(xiàn)的時候往往采用一組固定數(shù)目的Server,每個Server同時擔任上述三個角色.

Paxos算法分為以下三個階段：

1、Prepare階段

(1)Proposer向大多數(shù)Acceptor發(fā)起Proposal(epochNo,value)的Prepare請求.

(2)Acceptor收到Prepare請求,如果epochNo比之前接收到的小,直接拒絕；如果epochNo比之前已經(jīng)接收的大,就將已經(jīng)接收到的epochNo最大的Proposal返回到Proposer.

(3)Proposer發(fā)起的Proposal至少要收到大多數(shù)以上的Acceptor的Prepare應答后,才能進入接下來的Accept階段,否則需要重新進行Prepare階段向大多數(shù)Acceptor發(fā)起Prepare請求.

2、Accept階段：

(1)Proposer收到大多數(shù)的Acceptor的Prepare應答后,看Acceptor是否已經(jīng)有被接受的Proposal.如果沒有已經(jīng)接受的Proposal,就自己提出一個Proposal,發(fā)起Accept請求；如果已經(jīng)有被接受的Proposal,就從中選出epochNo最大的Proposal,發(fā)起對該Proposal的Accept請求.

(2)Acceptor收到請求后,如果該Proposal的epochNo比它最后一次應答Prepare請求的epochNo要大,那么就接受該請求；否則拒絕該請求.

3、Learn階段：

所有Acceptor接受的Proposal要不斷通知Learner,或者Learner主動去查詢,一旦Learner確認Proposal被大多數(shù)的Acceptor接受,那么表示這個Proposal的Value被Chosen,Learner就可以學習這個Proposal的Value,同時自己的Sever上就不再受理Proposor的請求.

我喜歡通過例子來理解理論,理論源于生活,下面我以生活中的例子來進行該算法的描述.

假設一群驢友決定端午去旅游,驢友遍布全國各地,一共10人,為了能達成一致,這10個人另外找5個作為隊長.5個隊長之間相互不通信,只跟10個驢友發(fā)短信.

第一階段(申請階段),驢友發(fā)短信給5個隊長,申請與隊長進行溝通.隊長在任何時刻只能與一個驢友溝通.發(fā)送的每條短信都帶有時間,隊長采用的原則是同意與短信發(fā)送時間最新的驢友溝通,如果出現(xiàn)更新的短信,則與短信更新的驢友溝通.至少大多數(shù)隊長同意溝通了,這個驢友才能進入第二階段實質(zhì)性溝通.

第二階段(溝通階段),獲得溝通權(quán)的驢友A收到隊長們給他發(fā)的旅游地,可能有幾種情況.

• 第一種情況：溝通的隊長們?nèi)慷歼€沒有決定到底去哪里旅游,此刻驢友A會把自己想去的旅游地發(fā)給隊長們(比如馬爾代夫),結(jié)果可能大多數(shù)隊長同意了,整個過程執(zhí)行完畢,就是去馬爾代夫旅游了,其他的驢友遲早會知道.除此之外就表明失敗了,可能隊長沒有回復(跟女友打電話去了),可能被其他驢友搶占溝通權(quán)了(上面說過隊長只跟最新的短信的人進行溝通).如果失敗了,A需要重新開始第一階段申請,重新給隊長們發(fā)短信申請溝通權(quán).
• 第二種情況：至少有一個隊長已經(jīng)決定旅游地了,這個時候A會收到不同隊長決定的多個旅游地,這些旅游地是不同隊長跟不同驢友在不同時間做的決定.A會先看看有的旅游地是不是被大多數(shù)(半數(shù)以上)隊長同意了,如果有(這里假設3個隊長決定去三亞,一個去拉薩,另外可能某種原因沒搭理),那證明整個決定過程已經(jīng)達成一致了,A收拾收拾去三亞吧,結(jié)束!
• 如果都沒有達到半數(shù)(比如2個去三亞,1個去拉薩,1個去昆明,1個沒搭理),這時候A可能想去馬爾代夫,但也不按照自己意愿亂來了(這里是Paxos的關鍵所在,后者認可前者,否則整個過程無止境了),A會根據(jù)收到隊長的所有旅游地中找到最新的那個決定地(比如去昆明是那個隊長是1分鐘前決定的,去拉薩的隊長是半小時前決定的,去三亞的隊長是1小時前決定的),于是A頂最新的決定,去昆明.這時候去昆明的決定又更新了,這樣下一個搶到溝通權(quán)的驢友也很大可能會頂去昆明,這樣決定去昆明的隊長會越來越多.
• 一旦某個時刻大多數(shù)(半數(shù)以上)隊長都同意了去某個地點,比如去昆明,后續(xù)獲得溝通權(quán)的驢友B會發(fā)現(xiàn)大多數(shù)隊長都決定去昆明了,它也會服從,最終所有的驢友都達成一致去昆明.

Paxos的基本思想大致就是上面過程,Paxos利用的是選舉,少數(shù)服從多數(shù)的思想,只要N個(N為奇數(shù),至少大于等于3)節(jié)點中,有[N/2]+1(這里N/2為向下取整)或以上個節(jié)點同意了某個決定,則認為系統(tǒng)達到了一致,這樣的話,客戶端不必與所有服務器通信,選擇與大部分通信即可；也無需服務器都全部處于工作狀態(tài),有一些服務器掛掉,只有保證半數(shù)以上存活著,整個過程也能持續(xù)下去,容錯性相當好.

Paxos中的Acceptor相當于上面的隊長,Proposer相當于上面的驢友,epochNo號就相當于例子中申請短信的發(fā)送時間.Paxos最消耗時間的地方就在于需要半數(shù)以上同意溝通了才能進入第二步,試想一下,一開始,所有驢友就給隊長狂發(fā)短信,每個隊長收到的最新短信的是不同驢友,這樣,就難以達到半數(shù)以上都同意與某個驢友溝通的狀態(tài),為了減小這個時間,Paxos還有Fast Paxos的改進等等,這里不再細說.另外,paxos并不指代一個協(xié)議,而是一類協(xié)議的統(tǒng)稱,比較常見的paxos類協(xié)議有：basic paxos和multi-paxos,這里的例子說的是basic paxos,basic paxos協(xié)議較復雜,且相對效率較低,所以現(xiàn)在所有和paxos有關的協(xié)議的系統(tǒng),一般都是基于multi-paxos來實現(xiàn)的,有興趣了解可以參考文章https://zhuanlan.zhihu.com/p/25664121

3、Paxos在數(shù)據(jù)庫高可用上的使用

作為dba,為了實現(xiàn)高可用,最常用的高可用方式是主從模式,以mysql為例,主要有幾種

(1)強同步復制,binlog同步到從庫之后,從庫返回給主庫ok之后才能返回給客戶端提交成功,這就有個問題,一旦主從之間網(wǎng)絡出現(xiàn)抖動,甚至從庫宕機,則主庫就無法再繼續(xù)提供服務,這種模式實現(xiàn)了數(shù)據(jù)的強一致,但是犧牲了服務的可用性.

(2)異步復制,主庫寫本地成功后,立刻返回給客戶端說成功,無需等待從庫應答,這樣一旦主庫宕機,可能會有少量的日志沒有同步到從庫造成部分數(shù)據(jù)丟失,這種模式可用性很好,但是犧牲了數(shù)據(jù)的一致性.

(3)半同步復制,這種模式是一個折中,主要指至少有一個從庫節(jié)點收到日志返回給主庫ok之后,這是就可以返回給客戶端提交成功,當網(wǎng)絡環(huán)境不好的時候可能退化為異步復制.

另外主從模式還有一個無法繞過的問題,就是選主,為了主從模式的選主,長期以來也誕生了很多種高可用方案,MMM,MHA,中間層等等,但顯然理論和思路都不是最先進的.

總結(jié)一下,針對主從方式處理數(shù)據(jù)庫高可用有諸多缺陷,要想改進這種數(shù)據(jù)同步方式,可以梳理數(shù)據(jù)庫高可用的幾點需求：

1. 數(shù)據(jù)不丟失
2. 服務持續(xù)可用性
3. 自動選主
4. 自動容錯

使用paxos協(xié)議的日志同步就可以實現(xiàn)以上的三個需求,當然paxos協(xié)議需要依賴一個基本假設,主備之間有多數(shù)派機器(N/2+1)是存活且它們之間的網(wǎng)絡通訊正常,如果不滿足這個條件,則無法啟動服務,數(shù)據(jù)也無法寫入和讀取.

所以我們可以使用paxos進行redolog或者binlog的復制,從而保證高可用強一致的集群,主從的切換也不需要擔心,只需要有個vip,后端映射后面數(shù)據(jù)庫的多點就行,paxos會自動保證多點的一致性寫入,業(yè)界阿里云使用paxos或者raft來做的企業(yè)三節(jié)點的mysql集群.

原文來自微信公眾號：Qunar技術沙龍

轉(zhuǎn)載請注明本頁網(wǎng)址：
http://www.snjht.com/jiaocheng/2712.html