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

楊立君 郭林

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

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

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

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

0引言

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

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

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

1一致性問題

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

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

2Paxos算法工作原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1場景1實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

（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ù)，因?yàn)榇饛?fù)為已接收作戰(zhàn)參謀1的提案，作戰(zhàn)參謀2則不再提出新的進(jìn)攻時(shí)間，并接受作戰(zhàn)參謀1提議的時(shí)間。

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

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

3.2場景2實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

（10）作戰(zhàn)參謀1只接收1名指揮官的（Accepted）答復(fù)，同時(shí)接收到一個(gè)（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走錯(cuò)道路后自行返回指揮部，因此指揮官丙未收到作戰(zhàn)參謀1的提案。

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

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

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

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

4結(jié)語

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