史椸，耿晨，齊勇

（1.西安交通大學(xué)電子與信息工程學(xué)院，710049，西安；2.中航工業(yè)西安飛行自動(dòng)控制研究所，710065，西安）

MapReduce［1］編程模型在任務(wù)處理的過(guò)程中，個(gè)別節(jié)點(diǎn)容易出現(xiàn)錯(cuò)誤，出錯(cuò)節(jié)點(diǎn)對(duì)整個(gè)系統(tǒng)性能的影響較大。傳統(tǒng)MapReduce模型的容錯(cuò)機(jī)制較為簡(jiǎn)單，對(duì)錯(cuò)誤的處理容易產(chǎn)生重復(fù)計(jì)算，造成計(jì)算資源的浪費(fèi)。在容錯(cuò)時(shí)如果使用傳統(tǒng)的進(jìn)程檢查點(diǎn)機(jī)制，則開銷較大并且難以保證恢復(fù)數(shù)據(jù)的安全性。

隨著多核技術(shù)［2-3］的發(fā)展，多核資源越來(lái)越豐富，且呈現(xiàn)分布式的趨勢(shì)。如何能夠充分利用多核服務(wù)器的計(jì)算能力和硬件資源是一個(gè)隨之而來(lái)的問(wèn)題?，F(xiàn)代操作系統(tǒng)通過(guò)不斷增加系統(tǒng)的復(fù)雜性［4-5］來(lái)適應(yīng)持續(xù)發(fā)展的硬件資源，虛擬化技術(shù)的出現(xiàn)在一定程度上解決了現(xiàn)有系統(tǒng)眾多影響計(jì)算機(jī)性能的問(wèn)題。虛擬化技術(shù)可以提高服務(wù)器資源利用率，同時(shí)減少服務(wù)器數(shù)量，以降低管理和維護(hù)的開銷，降低能源消耗［6］。同時(shí)，虛擬化技術(shù)提供了很好的隔離性，使得虛擬機(jī)之間互不干擾，提高了系統(tǒng)的安全性和可靠性。

基于上述問(wèn)題，本文通過(guò)分析現(xiàn)有MapReduce的實(shí)現(xiàn)方式，將多核平臺(tái)與虛擬機(jī)技術(shù)相結(jié)合，提出了一種基于多核虛擬機(jī)的MapReduce模型（Virtual Machine Based Fault-Tolerant Mechanism，VMBFTM）。

1 任務(wù)分配模型

1.1 系統(tǒng)狀態(tài)模型與分析

基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce，其系統(tǒng)狀態(tài)模型如圖1所示。

通過(guò)虛擬機(jī)監(jiān)控器的虛擬化，在多核服務(wù)器上形成多個(gè)操作系統(tǒng)。其中一個(gè)操作系統(tǒng)叫做控制域，這個(gè)控制域把必要的接口暴露給用戶，以便用戶進(jìn)行編程和數(shù)據(jù)處理。服務(wù)器管理員通過(guò)這個(gè)控制域?qū)φ麄€(gè)多核服務(wù)器進(jìn)行維護(hù)，提交計(jì)算任務(wù)，調(diào)節(jié)整個(gè)系統(tǒng)負(fù)載，并對(duì)安全問(wèn)題進(jìn)行處理。其他操作系統(tǒng)受到控制域的監(jiān)控，對(duì)網(wǎng)絡(luò)或者外設(shè)的訪問(wèn)需要受到控制節(jié)點(diǎn)的限制。MapReduce模型中調(diào)度節(jié)點(diǎn)Master進(jìn)程運(yùn)行在控制域OS0。首先，用戶在控制節(jié)點(diǎn)提交需要處理的數(shù)據(jù)，Master進(jìn)程對(duì)數(shù)據(jù)進(jìn)行Split分割操作，劃分成N個(gè)數(shù)據(jù)塊。數(shù)據(jù)塊的個(gè)數(shù)和整個(gè)多核服務(wù)器中Worker工作節(jié)點(diǎn)個(gè)數(shù)相同。然后Master和每個(gè)操作系統(tǒng)中的守護(hù)進(jìn)程監(jiān)控者進(jìn)行通信，發(fā)出啟動(dòng) Worker的命令。監(jiān)控者收到命令之后，啟動(dòng) Worker，然后每個(gè) Worker創(chuàng)建指定個(gè)數(shù)的線程，對(duì)分配給它的數(shù)據(jù)進(jìn)行Map映射操作。Map操作處理待處理數(shù)據(jù)中每個(gè)記錄，產(chǎn)生中間結(jié)果的鍵值對(duì)＜key，value＞，然后在相同key的結(jié)果上執(zhí)行Reduce操作。在執(zhí)行Map操作的過(guò)程中，根據(jù)用戶指定或者系統(tǒng)默認(rèn)的策略，進(jìn)行檢查點(diǎn)的設(shè)置。設(shè)置檢查點(diǎn)時(shí)，需要陷入虛擬機(jī)，把Map當(dāng)前的中間結(jié)果保存在虛擬機(jī)維護(hù)的Map結(jié)果存儲(chǔ)區(qū)中，并記錄相關(guān)控制信息，例如當(dāng)前節(jié)點(diǎn)已經(jīng)完成的任務(wù)量等。設(shè)置完檢查點(diǎn)之后，返回操作系統(tǒng)，繼續(xù)進(jìn)行 Map操作。完成Map任務(wù)之后，Map產(chǎn)生的全部中間結(jié)果保存在共享內(nèi)存中，接著關(guān)閉Worker進(jìn)程，監(jiān)控者通知 Master本階段完成，請(qǐng)求進(jìn)行Reduce化簡(jiǎn)階段的處理。Master收到這個(gè)消息之后，重復(fù)上面的過(guò)程，進(jìn)入Reduce階段。Reduce過(guò)程中，每個(gè)Worker需要讀取Map的結(jié)果作為自己的輸入。每個(gè)Worker通過(guò)訪問(wèn)共享內(nèi)存中Map結(jié)果存儲(chǔ)區(qū)，讀取屬于自己節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行Reduce操作，通過(guò)共享內(nèi)存減少了傳遞大量中間結(jié)果帶來(lái)的時(shí)間開銷。在Reduce過(guò)程中，Reduce的結(jié)果也被不斷保存，以便在發(fā)生錯(cuò)誤之后通過(guò)這些保存的數(shù)據(jù)進(jìn)行恢復(fù)。

錯(cuò)誤恢復(fù)模型如圖2所示。接收到Master向監(jiān)控者發(fā)出的命令之后，啟動(dòng)本節(jié)點(diǎn)內(nèi)的Worker，Worker會(huì)創(chuàng)建多個(gè)線程進(jìn)行Map或者Reduce操作。在此過(guò)程中，根據(jù)一定策略進(jìn)行檢查點(diǎn)的設(shè)置，通過(guò)增量方式把當(dāng)前Map或者Reduce執(zhí)行的任務(wù)保存在由虛擬機(jī)維護(hù)的內(nèi)存區(qū)域內(nèi)。如果Worker檢測(cè)到錯(cuò)誤發(fā)生則會(huì)通知監(jiān)控者，監(jiān)控者隨即關(guān)閉本節(jié)點(diǎn)內(nèi)的Worker，并向Master發(fā)送消息，請(qǐng)求在本節(jié)點(diǎn)內(nèi)重新啟動(dòng)一個(gè)Worker。當(dāng)Master發(fā)出啟動(dòng)命令之后，監(jiān)控者重啟Worker，先從虛擬機(jī)維護(hù)的內(nèi)存中讀取已經(jīng)做好的中間結(jié)果和原始分配的任務(wù)以及相應(yīng)的控制信息等，然后對(duì)Worker進(jìn)行初始化操作，完成錯(cuò)誤恢復(fù)。系統(tǒng)就像沒(méi)有發(fā)生錯(cuò)誤一樣，繼續(xù)執(zhí)行Map或者Reduce操作。如果本節(jié)點(diǎn)內(nèi)分配的任務(wù)已經(jīng)做完，監(jiān)控者關(guān)閉Worker。

圖2 錯(cuò)誤恢復(fù)過(guò)程模型

1.2 錯(cuò)誤恢復(fù)開銷研究

基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce在Worker運(yùn)行時(shí)通過(guò)對(duì)中間結(jié)果設(shè)置檢查點(diǎn)達(dá)到錯(cuò)誤恢復(fù)的效果。假設(shè)在 Worker運(yùn)行中，檢查點(diǎn)是均勻分布的，設(shè)每個(gè)檢查點(diǎn)間隔計(jì)算任務(wù)消耗的時(shí)間為ti，并且由于（key，val）的處理過(guò)程，每個(gè)檢查點(diǎn)之間的計(jì)算任務(wù)消耗的時(shí)間大致相等，即ti=TPA，TPA表示每?jī)蓚€(gè)檢查點(diǎn)間隔計(jì)算任務(wù)消耗時(shí)間的平均值，TSA表示第1個(gè)檢查點(diǎn)，即單位時(shí)間內(nèi)保存中間結(jié)果的時(shí)間，且TPA≈TSA，TRA表示對(duì)單位時(shí)間內(nèi)生成的中間結(jié)果進(jìn)行恢復(fù)需要的時(shí)間。FK是第K 次發(fā)生錯(cuò)誤，n表示程序運(yùn)行完成過(guò)程中需要建立n個(gè)檢查點(diǎn)。因此不設(shè)檢查點(diǎn)的Map或者Reduce的執(zhí)行時(shí)間為

設(shè)置檢查點(diǎn)后，程序執(zhí)行時(shí)間為

式中：TE表示每次進(jìn)行檢查點(diǎn)時(shí)陷入和返回虛擬機(jī)的時(shí)間，每次都相等，共有n次；TiS表示每次保存中間結(jié)果所需要的時(shí)間。

不設(shè)檢查點(diǎn)出錯(cuò)之后，程序直接終止，所消耗的時(shí)間為

不設(shè)檢查點(diǎn)出錯(cuò)后進(jìn)行恢復(fù)時(shí)，出錯(cuò)節(jié)點(diǎn)需要從頭開始計(jì)算，由于可能在運(yùn)行過(guò)程中多次產(chǎn)生錯(cuò)誤，設(shè)每次錯(cuò)誤之后運(yùn)行到tFi，因此整個(gè)過(guò)程消耗的時(shí)間為

式中：當(dāng)i＞j時(shí)，F(xiàn)i＞Fj。進(jìn)行檢查后，在F處出錯(cuò)之后整個(gè)進(jìn)程消耗時(shí)間為

檢查點(diǎn)出錯(cuò)后進(jìn)行恢復(fù)時(shí)，發(fā)生錯(cuò)誤次數(shù)為K，錯(cuò)誤發(fā)生點(diǎn)為tFi，每次只要從最近的檢查點(diǎn)繼續(xù)執(zhí)行即可，從最近檢查點(diǎn)進(jìn)行恢復(fù)的時(shí)間為TFiR，所消耗時(shí)間為

式中：TFiR表示從最近的檢查點(diǎn)進(jìn)行恢復(fù)數(shù)據(jù)所需要的時(shí)間，TFiR和保存最近檢查點(diǎn)的數(shù)據(jù)所花費(fèi)的時(shí)間大致相等。

為了比較不設(shè)置檢查點(diǎn)和設(shè)置檢查點(diǎn)之后恢復(fù)的效果，比較TNFR和TCFR，即

如前所述，ti=TPA，且每次檢查點(diǎn)保存和恢復(fù)的時(shí)間隨著中間結(jié)果的增長(zhǎng)而線性增加，因此TiS=iTSA，所以可以進(jìn)一步得出

由于是輕量級(jí)虛擬機(jī)，虛擬機(jī)每次陷入和返回的時(shí)間和較短，因此nTE可以忽略。而且對(duì)使用MapReduce模型進(jìn)行處理的應(yīng)用來(lái)說(shuō)，計(jì)算產(chǎn)生中間結(jié)果花費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)大于把這些中間結(jié)果保存在內(nèi)存中花費(fèi)的時(shí)間，即TPA?TSA。進(jìn)一步分析式（8）后，發(fā)現(xiàn)當(dāng)n不太大的時(shí)候，TPA／TSA＜5即可保證TNFR＞TCFR成立，即本文設(shè)計(jì)的容錯(cuò)機(jī)制相比傳統(tǒng)的MapReduce容錯(cuò)機(jī)制更有優(yōu)勢(shì)。

2 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

本文所設(shè)計(jì)的系統(tǒng)需要3個(gè)部分支持：具有容錯(cuò)機(jī)制的MapReduce引擎、用戶定制程序以及虛擬化的多核服務(wù)器。三者關(guān)系如圖3所示。前兩者是軟件支持，第3個(gè)是硬件平臺(tái)支持。具有容錯(cuò)機(jī)制的MapReduce引擎是對(duì)MapReduce過(guò)程進(jìn)行統(tǒng)一管理，對(duì)底層硬件平臺(tái)進(jìn)行抽象，提供良好的通信機(jī)制和數(shù)據(jù)管理能力，包括Master端、Worker端以及監(jiān)控者程序。用戶定制程序是用戶自己編寫的對(duì)不同的應(yīng)用案例進(jìn)行特定處理的程序，主要是用戶自定義的Split，Map和Reduce函數(shù)。虛擬化的多核服務(wù)器是運(yùn)行系統(tǒng)的硬件平臺(tái)，為具有容錯(cuò)功能的MapReduce系統(tǒng)提供硬件支持，這里是通過(guò)輕量級(jí)虛擬機(jī)監(jiān)控器對(duì)多核服務(wù)器進(jìn)行虛擬化，把多個(gè)隔離的操作系統(tǒng)作為隔離的節(jié)點(diǎn)，運(yùn)行一個(gè)Master或若干Worker。為完成系統(tǒng)功能要求，需要解決3個(gè)問(wèn)題：一是如何進(jìn)行數(shù)據(jù)處理；二是任務(wù)調(diào)度和通信效率；三是容錯(cuò)機(jī)制的建立。

2.1 數(shù)據(jù)處理過(guò)程

數(shù)據(jù)處理的前提是建立域間共享內(nèi)存，它是整個(gè)系統(tǒng)的核心，也是其他模塊運(yùn)行的基礎(chǔ)和前提條件。共享內(nèi)存為多核系統(tǒng)SMM［7］提供簡(jiǎn)單編程模型，并且可以兼容大部分當(dāng)前已有的應(yīng)用程序和操作系統(tǒng)。共享內(nèi)存系統(tǒng)［8］可使各個(gè)模塊平等地訪問(wèn)系統(tǒng)中的物理內(nèi)存。

圖3 基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce

在OS內(nèi)核中需要建立共享內(nèi)存到內(nèi)核空間的映射，然后建立用戶地址空間和內(nèi)核地址空間的映射，這樣OS中的Master和Worker進(jìn)程就可以自由地使用共享內(nèi)存在不同OS之間通信。

數(shù)據(jù)處理模塊把系統(tǒng)的控制信息等敏感數(shù)據(jù)保存在共享內(nèi)存中；任務(wù)調(diào)度模塊根據(jù)共享內(nèi)存中的控制進(jìn)行任務(wù)調(diào)度；節(jié)點(diǎn)通信模塊使用共享內(nèi)存進(jìn)行節(jié)點(diǎn)之間的通信和交互；檢查點(diǎn)模塊把恢復(fù)數(shù)據(jù)保存在各個(gè)節(jié)點(diǎn)都能訪問(wèn)到的共享內(nèi)存中，便于在出錯(cuò)后使用錯(cuò)誤恢復(fù)模塊進(jìn)行恢復(fù)。

在數(shù)據(jù)輸入階段，對(duì)于Master節(jié)點(diǎn)，計(jì)算任務(wù)的數(shù)據(jù)一般以文件的形式提供，先存放在Master節(jié)點(diǎn)硬盤中。數(shù)據(jù)處理模塊需要把計(jì)算任務(wù)文件讀入內(nèi)存，然后根據(jù)一定的規(guī)則進(jìn)行分割，把這些數(shù)據(jù)存放在虛擬機(jī)維護(hù)的內(nèi)存區(qū)域中。對(duì)于Worker節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的輸入數(shù)據(jù)是本節(jié)點(diǎn)需要處理的數(shù)據(jù)，由虛擬機(jī)調(diào)用。通過(guò)虛擬機(jī)維護(hù)的共享內(nèi)存，Worker進(jìn)程可以對(duì)本節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行操作。由于每個(gè)節(jié)點(diǎn)只映射自己所要處理的數(shù)據(jù)的內(nèi)存，不會(huì)對(duì)其他節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行影響和破壞。Map階段和Reduce階段類似，從共享內(nèi)存中讀入本節(jié)點(diǎn)需要處理的數(shù)據(jù)，通過(guò)任務(wù)調(diào)度分發(fā)給每個(gè)線程，進(jìn)行計(jì)算后輸出到共享內(nèi)存中，中途需要根據(jù)一定策略對(duì)中間結(jié)果進(jìn)行必要的保存。

2.2 任務(wù)調(diào)度和通信

任務(wù)調(diào)度模塊是在系統(tǒng)運(yùn)行時(shí)，完成任務(wù)調(diào)度和負(fù)載均衡的功能。任務(wù)調(diào)度的過(guò)程包括監(jiān)控者開啟和關(guān)閉Worker進(jìn)程，Worker進(jìn)程開創(chuàng)多個(gè)線程進(jìn)行Map或者Reduce操作，操作完畢之后通知完成工作。通過(guò)使用進(jìn)程和線程結(jié)合的方式，在每個(gè)子域的操作系統(tǒng)上運(yùn)行一個(gè) Worker，然后每個(gè)Worker又創(chuàng)建多個(gè)線程，每個(gè)線程處理一塊數(shù)據(jù)。這樣能夠很好的利用多進(jìn)程和多線程的優(yōu)勢(shì)。

節(jié)點(diǎn)通信模塊主要負(fù)責(zé)節(jié)點(diǎn)之間的通信，保證Master能夠準(zhǔn)確地控制Worker節(jié)點(diǎn)的執(zhí)行，并在Worker節(jié)點(diǎn)的任務(wù)執(zhí)行的過(guò)程中和完成任務(wù)之后，Master節(jié)點(diǎn)能夠及時(shí)了解此Worker節(jié)點(diǎn)的任務(wù)狀態(tài)信息。

Master進(jìn)程直接和子域中的監(jiān)控者進(jìn)程進(jìn)行通信。監(jiān)控者是守護(hù)進(jìn)程，一直運(yùn)行在子域中，負(fù)責(zé)監(jiān)聽Master信號(hào)，在收到Master發(fā)過(guò)來(lái)的啟動(dòng)命令之后，啟動(dòng)本節(jié)點(diǎn)中Worker進(jìn)程。在節(jié)點(diǎn)內(nèi)部多線程執(zhí)行任務(wù)的過(guò)程中，如果發(fā)生錯(cuò)誤，Worker進(jìn)程崩潰，監(jiān)控者進(jìn)程發(fā)現(xiàn)Worker崩潰后，需要在全局任務(wù)控制表中屬于本節(jié)點(diǎn)的表項(xiàng)中注明錯(cuò)誤發(fā)生，同時(shí)Master進(jìn)程會(huì)不斷掃描全局任務(wù)控制表項(xiàng)。由于全局任務(wù)控制表是存放在各個(gè)域之間的共享內(nèi)存中，因此Master通過(guò)定時(shí)掃描就可以及時(shí)發(fā)現(xiàn)狀態(tài)的改變，并有效地對(duì) Worker進(jìn)行監(jiān)控和管理。

2.3 建立容錯(cuò)機(jī)制

本文給出的MapReduce的容錯(cuò)機(jī)制包括兩方面：檢查點(diǎn)設(shè)置和錯(cuò)誤恢復(fù)。

在檢查點(diǎn)時(shí)刻把當(dāng)前線程的計(jì)算結(jié)果保存在虛擬機(jī)指定的隔離內(nèi)存空間，出錯(cuò)之后在出錯(cuò)節(jié)點(diǎn)重新啟動(dòng)Worker進(jìn)程，從最近的檢查點(diǎn)讀取中間結(jié)果數(shù)據(jù)和本節(jié)點(diǎn)任務(wù)的進(jìn)度信息繼續(xù)運(yùn)行。由于（key，val）的特點(diǎn)，key和產(chǎn)生它的進(jìn)程以及所在的節(jié)點(diǎn)無(wú)關(guān)，因此可以由任意的線程繼續(xù)對(duì)它進(jìn)行處理。

這些恢復(fù)數(shù)據(jù)存放在由VMM指定內(nèi)存中，OS系統(tǒng)是無(wú)法感知和訪問(wèn)的，這樣就形成了隔離屏障，保證當(dāng)Worker進(jìn)程甚至整個(gè)OS異常終止或者崩潰之后，這些恢復(fù)數(shù)據(jù)不會(huì)受到破壞和影響。VMM接受虛擬機(jī)調(diào)用之后，在虛擬機(jī)里把線程已經(jīng)處理好的數(shù)據(jù)保存在指定的專門存放中間結(jié)果的內(nèi)存中，這塊內(nèi)存通過(guò)資源的隔離性保證了恢復(fù)數(shù)據(jù)的安全性。

在恢復(fù)的過(guò)程中，通過(guò)讀取存放在全局任務(wù)控制表中的任務(wù)進(jìn)度信息，Worker進(jìn)程創(chuàng)建線程并讀取任務(wù)進(jìn)度信息從而使每個(gè)線程恢復(fù)到設(shè)置檢查點(diǎn)時(shí)的狀態(tài)。由于（key，val）和線程狀態(tài)無(wú)關(guān)，因此新的線程可以繼續(xù)執(zhí)行出錯(cuò)前任意一個(gè)線程的任務(wù)。由于檢查點(diǎn)時(shí)刻的任務(wù)都保存在VMM維護(hù)的隔離內(nèi)存中，因此需要陷入虛擬機(jī)，用保存的中間結(jié)果恢復(fù)OS中的所有線程共同操作的中間結(jié)果池。

3 實(shí)驗(yàn)結(jié)果與分析

測(cè)試的硬件平臺(tái)是基于SUN的32核、主頻為2.38GHz、內(nèi)存為128GB的服務(wù)器。硬件之上運(yùn)行著本課題組設(shè)計(jì)實(shí)現(xiàn)的虛擬機(jī)監(jiān)控器OSV。相比于傳統(tǒng)的虛擬機(jī)監(jiān)控器，我們?cè)O(shè)計(jì)的OSV虛擬機(jī)監(jiān)控器是輕量級(jí)的，易于維護(hù)，并且性能更高。虛擬機(jī)監(jiān)控器對(duì)其上的操作系統(tǒng)分配資源，并且阻止其他操作系統(tǒng)未授權(quán)的訪問(wèn)，形成了資源的隔離。節(jié)點(diǎn)之間可以通過(guò)一般的TCP／IP進(jìn)行通信，而對(duì)于大量的數(shù)據(jù)，通過(guò)虛擬機(jī)維護(hù)的共享內(nèi)存進(jìn)行數(shù)據(jù)交流在一定程度上提高了數(shù)據(jù)交互的性能。為了降低虛擬化對(duì)系統(tǒng)帶來(lái)性能上的影響，虛擬機(jī)只是對(duì)資源進(jìn)行訪問(wèn)控制，而沒(méi)有對(duì)資源進(jìn)行虛擬化。由于VMM在OS運(yùn)行時(shí)處于掛起狀態(tài)，并且OS對(duì)授權(quán)的硬件資源直接進(jìn)行訪問(wèn)，因此相比于沒(méi)有虛擬機(jī)的多核服務(wù)器，性能損耗很小。

3.1 MapReduce應(yīng)用性能測(cè)試

wordcount應(yīng)用是用來(lái)測(cè)試MapReduce性能的一個(gè)比較普遍的測(cè)試用例，其功能是對(duì)一個(gè)存放英文單詞的大文件進(jìn)行處理，統(tǒng)計(jì)其中的英文單詞出現(xiàn)的頻率，得出出現(xiàn)單詞的種類和各個(gè)單詞出現(xiàn)的次數(shù)。使用wordcount應(yīng)用對(duì)基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce在多核平臺(tái)上進(jìn)行測(cè)試，并和兩種不同模式的多線程實(shí)現(xiàn)方式以及Phoenix系統(tǒng)進(jìn)行對(duì)比。

斯坦福大學(xué)在多核服務(wù)器上實(shí)現(xiàn)了Phoenix［9］系統(tǒng)，直接運(yùn)行在多核服務(wù)器上的一個(gè)操作系統(tǒng)，它是基于共享內(nèi)存的MapReduce，使用多個(gè)線程完成Worker的任務(wù)。

第一種多線程方式運(yùn)行在多核服務(wù)器上唯一的操作系統(tǒng)中，這個(gè)操作系統(tǒng)完全掌控所有的硬件資源，即單操作系統(tǒng)多線程方式，通過(guò)使用Pthread多線程進(jìn)行wordcount應(yīng)用的處理。第二種多線程方式是在多核平臺(tái)上使用虛擬機(jī)監(jiān)控器進(jìn)行資源隔離，運(yùn)行多個(gè)操作系統(tǒng)，每個(gè)操作系統(tǒng)上運(yùn)行一個(gè)Worker進(jìn)程，每個(gè) Worker進(jìn)程創(chuàng)建4個(gè)線程，即多操作系統(tǒng)多線程方式。每個(gè)操作系統(tǒng)相當(dāng)于分布式環(huán)境下單獨(dú)的一個(gè)計(jì)算節(jié)點(diǎn)，借助MapReduce思想進(jìn)行wordcount處理。

對(duì)4線程、8線程、12線程、16線程4種情況測(cè)試1GB大小的wordcount文件的計(jì)算時(shí)間，結(jié)果如圖4所示?？梢钥闯?，Pheonix性能略高，而單操作系統(tǒng)多線程方式和基于多核的具有容錯(cuò)機(jī)制的MapReduce性能類似，并且性能與Pheonix相差不大，而多操作系統(tǒng)多線程方式的性能最差。

圖4 4種方式進(jìn)行wordcount計(jì)算的執(zhí)行時(shí)間

基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce和Phoenix性能差距較小。由于通過(guò)使用節(jié)點(diǎn)之間的共享內(nèi)存進(jìn)行數(shù)據(jù)傳遞比通過(guò)網(wǎng)絡(luò)傳輸速度更快，而且作為Reduce輸入數(shù)據(jù)的中間結(jié)果保存在節(jié)點(diǎn)之間的共享內(nèi)存中，執(zhí)行Reduce的Worker可以直接對(duì)這塊內(nèi)存進(jìn)行操作，避免了對(duì)硬盤訪問(wèn)帶來(lái)的開銷。

3.2 錯(cuò)誤恢復(fù)測(cè)試與評(píng)價(jià)

由圖5可見，當(dāng)錯(cuò)誤發(fā)生之后，監(jiān)控者進(jìn)程迅速發(fā)現(xiàn)Worker進(jìn)程出錯(cuò)，提示出錯(cuò) Worker進(jìn)程的PID，并重啟 Worker進(jìn)程繼續(xù)執(zhí)行；如果 Worker進(jìn)程發(fā)生多次錯(cuò)誤，每次出錯(cuò)之后監(jiān)控者進(jìn)程可以立即感知，啟動(dòng)新的Worker進(jìn)程繼續(xù)計(jì)算，直到完成整個(gè)任務(wù)。相比發(fā)生一次錯(cuò)誤的情況，出現(xiàn)兩次錯(cuò)誤的執(zhí)行過(guò)程所耗費(fèi)的時(shí)間沒(méi)有明顯增加。

圖5 錯(cuò)誤恢復(fù)過(guò)程

圖6為不同出錯(cuò)次數(shù)情況下各種并行計(jì)算方式出錯(cuò)后重啟并完成計(jì)算所耗費(fèi)的時(shí)間。

圖6 不同出錯(cuò)次數(shù)的恢復(fù)時(shí)間比較

基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce在出錯(cuò)之后可以立即重啟并繼續(xù)執(zhí)行，已完成的結(jié)果沒(méi)有丟失，不會(huì)造成計(jì)算任務(wù)的浪費(fèi)。由圖6可見，多次恢復(fù)之后，本模型相對(duì)于其他3種方式，完成計(jì)算任務(wù)的時(shí)間最短，性能最優(yōu)。

3.3 安全隔離功能測(cè)試與評(píng)價(jià)

通過(guò)對(duì)中間結(jié)果進(jìn)行檢查點(diǎn)設(shè)置，可以在錯(cuò)誤恢復(fù)的過(guò)程中通過(guò)讀取保存的數(shù)據(jù)進(jìn)行恢復(fù)。傳統(tǒng)使用檢查點(diǎn)的保存方式是把數(shù)據(jù)保存在內(nèi)存或者磁盤中，恢復(fù)的時(shí)候啟動(dòng)恢復(fù)策略將已經(jīng)保存的數(shù)據(jù)恢復(fù)出來(lái)，然而由于操作系統(tǒng)受到攻擊或者其他惡意程序，保存的數(shù)據(jù)受到污染，因此恢復(fù)之后的結(jié)果是錯(cuò)誤的，如圖7a所示，而基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce系統(tǒng)可以進(jìn)行正確的恢復(fù)，如圖7b所示。

圖7 恢復(fù)數(shù)據(jù)區(qū)對(duì)比圖

虛擬機(jī)監(jiān)控器可以完全控制和管理多核平臺(tái)的內(nèi)存，使操作系統(tǒng)無(wú)法直接訪問(wèn)隔離的內(nèi)存，因此需要恢復(fù)的數(shù)據(jù)不會(huì)受到操作系統(tǒng)內(nèi)部各種錯(cuò)誤的影響，保證了恢復(fù)數(shù)據(jù)的安全性。

4 結(jié) 論

本文充分利用了多核服務(wù)器架構(gòu)和虛擬化技術(shù)的特點(diǎn)，設(shè)計(jì)并實(shí)現(xiàn)了基于多核虛擬機(jī)的具有容錯(cuò)機(jī)制的MapReduce，通過(guò)虛擬機(jī)監(jiān)控器進(jìn)行安全數(shù)據(jù)隔離和恢復(fù)，對(duì)中間結(jié)果進(jìn)行保存以提高錯(cuò)誤恢復(fù)的性能，降低了節(jié)點(diǎn)之間的數(shù)據(jù)傳輸開銷。測(cè)試了系統(tǒng)的性能、錯(cuò)誤恢復(fù)的能力以及安全數(shù)據(jù)隔離的效果，并與其他并行程序的性能進(jìn)行相應(yīng)的對(duì)比。結(jié)果表明，本文所提出的改進(jìn)的MapReduce模型提高了錯(cuò)誤恢復(fù)的性能，保證了恢復(fù)數(shù)據(jù)的安全性。下一步將優(yōu)化檢查點(diǎn)策略，完善錯(cuò)誤感知機(jī)制，減小保存和恢復(fù)過(guò)程中的性能損耗。

［1］ DEAN J，GHEMAWAT S.MapReduce：a flexible data processing tool ［J］.Communications of the ACM，2010，53（1）：72-77.

［2］ MOHANTY R P，TURUK A K，SAHOO B.Analysing the performance of multi-core architecture［C］∥Proceedings of the first International Conference on Computing，Communication and Sensor Networks.New York，USA：IJCA，2013：28-33.

［3］ MERRITT R.CPU designers debate multi-core future［EB／OL］.（2008-02-06）［2012-10-02］.http：∥www.eetimes.com／document.asp？doc＿id=1167932.

［4］ DESNOYERS M，MCKENNEY P E，STEM A S，et al.User-level implementations of read-copy update［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23（2）：375-382.

［5］ Receive-side scaling enhancements in windows server［EB／OL］.（2008-11-05）［2012-10-15］.http：∥www.microsoft.com／whdc／device／network／ndis＿rss.mspx.

［6］ MATTHEWS J N，DOW E M，DESHANE T，et al.Running Xen：a hands-on guide to the art of virtualization［M］.New Jersey，USA：Prentice Hall，2008：56-59.

［7］ CHAPMAN M.HEISER G.vNUMA：a virtual sharedmemory multiprocessor［C］∥Proceedings of the 2009 USENIX Annual Technical Conference.San Diego，USA：USENIX Association，2009：349-362.

［8］ GULATI A，MERCHANT A，VARMAN P J.MClock：handling throughput variability for hypervisor I／O scheduling［C］∥Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation.Berkeley，CA，USA：USENIX Association，2010：1-7.

［9］ TALBOT J，YOO R M，KOZYRAKIS C.Phoenix++：modular MapReduce for shared-memory systems ［C］∥Proceedings of the Second International Workshop on MapReduce and Its Applications.New York，USA：ACM，2011：9-16.