面向云計算基礎(chǔ)課程的Paxos算法教學(xué)設(shè)計研究

楊立君 郭林

摘要：云計算作為一種新型計算模型，自誕生以來受到了業(yè)界與學(xué)術(shù)界廣泛關(guān)注，市場規(guī)模迅速擴大，國內(nèi)許多大學(xué)的計算機專業(yè)都開始關(guān)注云計算課程教學(xué)。針對云計算課程技術(shù)內(nèi)容新、涉及理論多、應(yīng)用范圍廣，以及與商業(yè)運營模式結(jié)合緊密等特點，以谷歌公司的云計算核心技術(shù)分布式鎖服務(wù)Chubby所采用的Paxos算法為例，對云計算教學(xué)內(nèi)容與教學(xué)方法進(jìn)行設(shè)計探究。詳細(xì)闡述了Paxos算法工作原理，并設(shè)計了具體教學(xué)案例，該教學(xué)方案在實際教學(xué)實踐中獲得了良好的教學(xué)效果，加深了學(xué)生對Paxos算法的理解。

關(guān)鍵詞：云計算;教學(xué)設(shè)計;Chubby;Paxos算法

DOI：10.11907/ejdk.191376開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：G434文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）010-0191-04

0引言

隨著計算機網(wǎng)絡(luò)技術(shù)的發(fā)展以及Web 2.0網(wǎng)絡(luò)革命的到來，谷歌首席執(zhí)行官埃里克施密特于2006年8月在搜索引擎大會上首次提出了“云計算”概念，并將其闡述為谷歌公司的戰(zhàn)略核心，同時作出預(yù)言：“在未來10-15年，當(dāng)前以PC為核心的時代將被云計算時代所取代。”

云計算概念一經(jīng)提出，由于其具有低成本、高性能、易于擴展及按需服務(wù)的特性，很快吸引了工業(yè)界與學(xué)術(shù)界的廣泛關(guān)注，并在海量、高速增長、多樣性大數(shù)據(jù)等傳統(tǒng)單服務(wù)器環(huán)境下數(shù)據(jù)存儲和計算模式難以處理的應(yīng)用場景中顯示出獨特優(yōu)勢。如何充分利用云計算技術(shù)特性對大規(guī)模數(shù)據(jù)集進(jìn)行高效的分布式計算、存儲及分析已成為當(dāng)前計算機科學(xué)領(lǐng)域最受關(guān)注的研究與應(yīng)用方向之一。

為了滿足業(yè)界對云計算技術(shù)開發(fā)與大數(shù)據(jù)處理領(lǐng)域高素質(zhì)人才的迫切需求，目前很多大學(xué)的計算機相關(guān)專業(yè)都已在本科及研究生培養(yǎng)階段開設(shè)了云計算技術(shù)與大數(shù)據(jù)處理相關(guān)課程，以培養(yǎng)學(xué)生掌握該領(lǐng)域理論知識與應(yīng)用開發(fā)技術(shù)。授課教師針對云計算課程技術(shù)跨越度大、覆蓋面廣、對計算機算法等方面知識基礎(chǔ)要求較高的特點，設(shè)計了很多針對性的教學(xué)方案，使學(xué)生對云計算包含的各項技術(shù)有更深入的了解。本文針對谷歌云計算集群用來解決分布式一致性問題的Paxos算法的教學(xué)重點與難點展開討論，以期對云計算基礎(chǔ)技術(shù)的教學(xué)及科研提供支持與幫助。

1一致性問題

對于傳統(tǒng)單服務(wù)器計算模式，執(zhí)行程序與目標(biāo)數(shù)據(jù)都存儲在同一個節(jié)點上，一致性機制非常直觀。但云計算平臺通常運行于大規(guī)模計算集群之上，需要調(diào)動成千上萬的節(jié)點協(xié)同工作。要保證系統(tǒng)中初始狀態(tài)相同的節(jié)點在執(zhí)行相關(guān)操作時能看到完全一致的指令隊列，并得到完全一致的執(zhí)行結(jié)果，此類分布式系統(tǒng)的一致性機制實現(xiàn)則非常復(fù)雜。解決一致性問題有兩種方法：消息傳遞與共享內(nèi)存，Paxos算法是Leslie Lamport提出的一種基于消息傳遞的一致性算法，也是目前已知的一致性算法中最常用的一種。Paxos算法輸入是各個計算機的全局請求（整個集群知道的消息），輸出是請求的全局執(zhí)行順序。假如各個計算機內(nèi)對各消息的解釋代碼都相同，通過執(zhí)行帶編號的全局請求，各機器則可以得到同樣的結(jié)果。

分布式一致性問題與一致性算法是云計算集群分布式計算及傳統(tǒng)服務(wù)器計算最重要的區(qū)別之一，也是云計算技術(shù)研究的核心問題之一，以及云計算教學(xué)過程中一個非常抽象、難以理解的知識模塊。通過對Paxos一致性算法工作原理與教學(xué)案例的探討，將為教師開展分布式鎖服務(wù)Chubby教學(xué)建立一個堅實的算法知識基礎(chǔ)。

2Paxos算法工作原理

在分布式系統(tǒng)中，采用消息傳遞方式提供通信服務(wù)，不可避免地會出現(xiàn)以下情況：系統(tǒng)進(jìn)程可能遇到異常情況，例如運行緩慢、進(jìn)程阻塞及重新啟動等，消息傳遞過程中也可能產(chǎn)生延遲、丟失以及重復(fù)發(fā)送等異常。在可能發(fā)生上述異常的分布式系統(tǒng)中，如何就某個值達(dá)成一致，以確保上述任何異常不會損害系統(tǒng)一致性，則需要引入“一致性算法”。

在集群中設(shè)置一個決策節(jié)點，所有部分操作都要先向其發(fā)起請求，由該節(jié)點接受第一個到達(dá)的請求內(nèi)容作為接下來的操作，從而確保該系統(tǒng)只有唯一的一個操作序列。但該機制在運行中存在單點失效問題，一旦唯一的決策節(jié)點失效，整個系統(tǒng)則可能出現(xiàn)不一致的情況。因此，Lamp-ort提出了Paxos算法，該算法在集群中設(shè)置多個節(jié)點以確定操作順序。

為了更直觀地描述Paxos算法，Lamport假想了一個名為Paxos的小島。該島通過民主議會制度頒布法律，但每個人都非常忙碌，隨時都會離開眾議院。因此，無法保證其他人在需要時能夠為自己提供服務(wù)，也無法保證他們會及時傳遞消息或批準(zhǔn)決議。假設(shè)島上沒有拜占庭指揮官的問題，也即是說，每個人經(jīng)手的消息不會被篡改，只要時間足夠長，消息則會正確傳遞，但不能保證即時性。此外，Paxos島的成員非常聰明，他們提出的決議不會被其他成員拒絕。在這里，議員等同于系統(tǒng)中的節(jié)點，議員制定法律的行為等同于系統(tǒng)狀態(tài)轉(zhuǎn)換條件。系統(tǒng)中的節(jié)點之間需要一致性，即只有一個版本的法律規(guī)定，議員和信使的兼職性質(zhì)對應(yīng)于節(jié)點與渠道的可用性。

Paxos算法將節(jié)點分成3類：Proposers、Aeceptors和Learners。Proposers提出決議（也即系統(tǒng)下一步執(zhí)行操作value），Aceeptors批準(zhǔn)決議，Learners接收并執(zhí)行已批準(zhǔn)的決議。

算法需要滿足3個條件才能保證一致性：①決議只有被Proposers提出后才能批準(zhǔn);②每次只批準(zhǔn)一個決議;③只有決議確定被批準(zhǔn)后，Learners才能獲取該決議。由此推導(dǎo)出以下約束條件：

P1：Acceptor必須接受其接收到的第一個提議。

P2：如果選擇了某個value為v的提議，則Acceptor接受的每個較高編號提議的value也必須為v。

P2a：如果選擇了某個value為v的提議，則Aeceptor接受的每個較高編號提議的value也必須為v。

P2b：如果選擇了某個value為v的提案，則Proposer提議的任何更高編號提案的value也必須是v。

P2c：對于任何N和v，如果提議為[N，V]，則存在一個超過Acceptor半數(shù)的集合S，滿足以下兩個條件之一：①S中每個Acceptor都沒有接受編號小于N的提議;②S中Acceptor接受過最大編號提案的value為V。

完整的Paxos算法執(zhí)行過程如下：

（1）準(zhǔn)備階段（prepare）：①Proposer選擇一個提案編號n，并向全體Aeeeptors發(fā)出Prepare請求;②如果一個Ac-ceptor收到的prepare請求編號n大于任何其已響應(yīng)的prepare請求，則Acceptor將自己已接受編號最大的提案反饋給Proposer，并向其承諾不會再接受任何編號小于n的提案請求。

（2）批準(zhǔn)階段（chosen）：①如果某個Proposer收到多數(shù)Acceptor的prepare請求響應(yīng)，其需要向這些Acceptor發(fā)出接受（accept）請求，包括編號n和根據(jù)P2c約束確定的val-ue（如果系統(tǒng)尚無已接受的value，則Proposer可自由決定提案的Value）;②如果某個Aeeeptor收到的提案接受請求包含編號n，只要不違反其對其它Proposer的承諾，Aeeep-tor將立即接受該提案。

一個Proposer可以提出多個提案，并且可以隨時中斷提案。當(dāng)某個Aceeptor接收到更大編號的prepare請求時，應(yīng)當(dāng)立即通知該Proposer中斷本次提案，以優(yōu)化整個算法流程。該實現(xiàn)過程不影響系統(tǒng)的正確性。

3Paxos算法教學(xué)案例

由于Paxos算法的數(shù)學(xué)證明與執(zhí)行過程非常復(fù)雜，通常情況下高年級本科生難以充分理解，需要精心設(shè)計教學(xué)內(nèi)容和方法。首先假設(shè)一個3節(jié)點的計算機集群，各節(jié)點首先作為Client產(chǎn)生操作請求，再作為Proposer提出操作請求，然后作為Acceptor批準(zhǔn)操作請求，最后作為Learner執(zhí)行被批準(zhǔn)的操作，則算法執(zhí)行邏輯如圖1所示。

這里每個Acceptors的數(shù)量必須為奇數(shù)，才能確保在每次投票過程中產(chǎn)生“多數(shù)派”并生成決議，而Proposers的數(shù)量則是靈活的，一個Proposer也不需要每次都把提案發(fā)送給所有的Acceptors，只需讓Acceptors中的“多數(shù)派”接收并批準(zhǔn)決議即可交由Learners執(zhí)行。

接下來通過設(shè)計一個讓學(xué)生親自參與的案例，可以將原本較抽象的計算機算法轉(zhuǎn)化為較為直接、具體的現(xiàn)實場景，以幫助學(xué)生理解Paxos算法。假設(shè)山谷中有一個恐怖分子營地，因地形復(fù)雜，營地有3條道路通向外界，反恐指揮部派出甲、乙、丙3個反恐分隊前去反恐作戰(zhàn)。為完成作戰(zhàn)目標(biāo)，將恐怖分子一網(wǎng)打盡，3支分隊需要同時向山谷發(fā)起進(jìn)攻，如圖2所示。

為協(xié)同3支隊伍發(fā)起進(jìn)攻的時間，總指揮部兩位作戰(zhàn)參謀1和2制定并提出最佳進(jìn)攻時間計劃，編號分別為1、2，每隊的指揮官甲、乙、丙接收指揮部計劃并批準(zhǔn)進(jìn)攻時間。為保證行動隱蔽，整個行動過程實行無線電靜默，由指揮部派出通訊員傳達(dá)參謀作戰(zhàn)計劃。通訊員A、B、C、D、E、F分別攜帶指揮部編號1和編號2的計劃上路，經(jīng)過不同路徑找到指揮官傳達(dá)計劃。為幫助學(xué)生理解Paxos算法工作原理，可以選擇一些學(xué)生分別扮演作戰(zhàn)參謀、指揮官和通訊員進(jìn)行模擬實驗。本文按照作戰(zhàn)參謀發(fā)起提案的先后順序不同分為兩種場景。

3.1場景1實驗設(shè)計

首先假設(shè)作戰(zhàn)參謀1和作戰(zhàn)參謀2先后發(fā)起提案的場景，設(shè)計實驗流程如下：

（1）作戰(zhàn)參謀1發(fā)起提案，派通訊員A、B、C送信給3名指揮官，內(nèi)容為（number 1）。

（2）3名指揮官收到作戰(zhàn)參謀1的提案，由于沒有已保存的編號，因此保存（number 1），同時讓通訊員帶消息回去，內(nèi)容為（ok）。

（3）作戰(zhàn)參謀1收到不少于兩名指揮官的回復(fù)，再次派通訊員送信給3名指揮官，內(nèi)容為（number 1，attack time 1）。

（4）3名指揮官收到作戰(zhàn)參謀1發(fā)來的進(jìn)攻時間，保存（number 1，attack time 1），同時讓通訊員送信回去，內(nèi)容為（Accepted）。

（5）作戰(zhàn)參謀1收到至少2名指揮官的（Accepted）回復(fù)，確認(rèn)大家都收到了攻擊時間。

（6）作戰(zhàn)參謀2發(fā)起提案，派通訊員D、E、F送信給3名指揮官，內(nèi)容為（number 2）。

（7）3名指揮官收到作戰(zhàn)參謀2的提案，由于2>1，因此每人都保存（number 2），又由于已接受了作戰(zhàn)參謀1的提案，則讓通訊員送信回去，內(nèi)容為（number 1，attacktime 1）。

（8）作戰(zhàn)參謀2收到至少兩名指揮官的回復(fù)，因為答復(fù)為已接收作戰(zhàn)參謀1的提案，作戰(zhàn)參謀2則不再提出新的進(jìn)攻時間，并接受作戰(zhàn)參謀1提議的時間。

最終批準(zhǔn)的“多數(shù)派”提案為（number 1，attack time 1），投票過程如圖3所示。

在兩位作戰(zhàn)參謀先后發(fā)起提案的場景中，由于指揮官必須批準(zhǔn)最先收到的決議，整個投票過程較為簡單、清晰。

3.2場景2實驗設(shè)計

接下來模擬兩位作戰(zhàn)參謀同時發(fā)起提案的場景，設(shè)計實驗流程如下：

（1）作戰(zhàn)參謀1發(fā)起提案，派通訊員A、B、C送信給3名指揮官，內(nèi)容為（number 1）。

（2）3名指揮官情況如下：①指揮官甲和指揮官乙都收到作戰(zhàn)參謀1的提案，指揮官甲和指揮官乙將（number1）記錄下來，并直接拒絕其他作戰(zhàn)參謀提出的更小編號，同時讓通訊員送信回去，內(nèi)容為（ok）;②負(fù)責(zé)通知指揮官丙的通訊員C走錯道路后自行返回指揮部，因此指揮官丙未收到作戰(zhàn)參謀1的提案。

（3）作戰(zhàn)參謀2也在同一時間發(fā)起提案，派通訊員D、E、F送信給3名指揮官，內(nèi)容為（number 2）。

（4）3名指揮官情況如下：①指揮官乙和指揮官丙都收到作戰(zhàn)參謀2的提案，指揮官乙和指揮官丙將（number2）記錄下來，并直接拒絕其他作戰(zhàn)參謀提出的更小編號，同時讓通訊員帶信回去，內(nèi)容為（ok）;②負(fù)責(zé)通知指揮官甲的通訊員D走錯道路后自行返回指揮部，因此指揮官甲未收到作戰(zhàn)參謀2的提案。

（5）作戰(zhàn)參謀1收到不少于兩名指揮官的答復(fù)，再派通訊員送信給有答復(fù)的兩名指揮官，內(nèi)容為（number 1，at-tack time 1）。

（6）兩名指揮官情況如下：①指揮官甲收到（number1，attack time 1），該編號與其已保存的編號相同，因此將（number 1，attack time 1）保存下來，同時讓通訊員A帶信回去，內(nèi)容為（Accepted）;②指揮官乙收到（number 1，at-tack time 1），由于乙處已保存編號2，1<2，則讓通訊員B送信回去，內(nèi)容為（Rejected，number2）。

（7）作戰(zhàn)參謀2收到不少于兩名指揮官的答復(fù)，再派通訊員送信給這兩名指揮官，內(nèi)容為（number2，attacktime2）。

（8）指揮官乙和丙收到（number 2，attack time 2），與已保存的編號相同，則保存（number 2，attack time 2），并讓通訊員送信回去，內(nèi)容為（Accepted）。

（9）作戰(zhàn)參謀2收到不少于兩名指揮官的（Accepted）答復(fù)，確認(rèn)多數(shù)派已接受了提議的進(jìn)攻時間。

（10）作戰(zhàn)參謀1只接收1名指揮官的（Accepted）答復(fù)，同時接收到一個（Rejected，number2）的答復(fù)。作戰(zhàn)參謀1再次發(fā)起提案，派通訊員A、B、C送信給3名指揮官，內(nèi)容為（number 3）。

（11）3名指揮官情況如下：①指揮官甲接收作戰(zhàn)參謀l的提案，由于之前保存了（number 1），3>1，因此保存（number 3），而指揮官甲已回復(fù)接受作戰(zhàn)參謀1之前的提案，則讓通訊員A送信回去，內(nèi)容為（number 1，attack time1）;②指揮官乙接收作戰(zhàn)參謀1的提案，由于之前已保存（number 2），3>2，因此保存（number 3），而指揮官乙已回復(fù)接受作戰(zhàn)參謀2之前的提案，則讓通訊員B送信回去，內(nèi)容為（number 2，attack time 2）;③負(fù)責(zé)通知指揮官丙的通訊員C走錯道路后自行返回指揮部，因此指揮官丙未收到作戰(zhàn)參謀1的提案。

（12）作戰(zhàn)參謀1接收了不少于兩名指揮官的答復(fù)，比較其編號大小，選擇較大編號對應(yīng)的進(jìn)攻時間并發(fā)起新的提案。因此，作戰(zhàn)參謀1派通訊員A、B送信給這兩名指揮官，內(nèi)容為（number 3，attack time 2）。

（13）指揮官甲和乙接收（number 3，attack time 2），與已保存的編號相同，因此保存（number 3，attack time 2），并讓通訊員送信回去，內(nèi)容為（Accepted）。

（14）作戰(zhàn)參謀1接收不少于兩名指揮官的（Accepted）回復(fù)，確認(rèn)提案的進(jìn)攻時間已被多數(shù)派接受。

最終指揮部和3支作戰(zhàn)部隊利用Paxos算法統(tǒng)一了發(fā)起進(jìn)攻的時間，實現(xiàn)了分布式系統(tǒng)的指令一致性。投票過程如圖4所示。

4結(jié)語

云計算作為一種新型計算模式，為了使大規(guī)模計算機集群能夠有效協(xié)同工作，針對海量數(shù)據(jù)實現(xiàn)高性能計算，采用了向量時鐘技術(shù)、改進(jìn)的一致性哈希算法等較為復(fù)雜的關(guān)鍵技術(shù)。其中谷歌云計算集群用來解決分布式一致性問題的Paxos算法既是云計算課程教學(xué)中的重點又是難點。在本學(xué)院的云計算課程教學(xué)過程中試行本文給出的設(shè)計方案，之后進(jìn)行的測試表明，學(xué)生們對原本難以理解的Paxos算法工作原理有了較為清晰的認(rèn)識。該設(shè)計得到了學(xué)生的廣泛認(rèn)同，在教學(xué)實踐中取得了很好的效果，并為其它部分的知識難點教學(xué)提供了有益借鑒。