【畢業(yè)學(xué)位論文】（Word原稿）MapReduce的系統(tǒng)性能評(píng)估與Backup調(diào)度策略-計(jì)算機(jī)科學(xué)與技術(shù)網(wǎng)絡(luò)與分布式系統(tǒng)

本科生畢業(yè)論文 題目： (中文 ) 系統(tǒng)性能評(píng)估與( 英文 ) 名： 學(xué) 號(hào)： 00548179 院 系： 信息科學(xué)技術(shù)學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 指導(dǎo)教師 ： 彭波 二一六年七月九日 北京大學(xué)本科生學(xué)位論文 2 北京大學(xué)本科畢業(yè)論文導(dǎo)師評(píng)閱表 學(xué)生姓名 陳日閃 學(xué)生學(xué)號(hào) 00548179 論文成績(jī) 學(xué)院（系） 信息科學(xué)技術(shù)學(xué)院 學(xué)生所在專業(yè) 計(jì)算機(jī) 導(dǎo)師 姓名 彭波 導(dǎo)師單位 / 所在研究所 網(wǎng)絡(luò)與信息系統(tǒng) 導(dǎo)師職稱 講師 論文題目 （中、英文） 系統(tǒng)性能評(píng)估與 度策略 師評(píng)語(yǔ) （ 包含對(duì)論文的性質(zhì)、難度、分量、綜合訓(xùn)練等是否符合培養(yǎng)目標(biāo)的目的等評(píng)價(jià) ） 陳日閃同學(xué)的論文選題是海量數(shù)據(jù)處理基礎(chǔ)設(shè)施中的 布式計(jì)算平臺(tái)的性能評(píng)估和優(yōu)化。這個(gè)方向是目前云計(jì)算熱潮中重要的技術(shù)問(wèn)題之一，也是本實(shí)驗(yàn)室在研究和開(kāi)發(fā) 現(xiàn)環(huán)境 面臨亟需解決的問(wèn)題，是進(jìn)一步工作的基礎(chǔ)。其選題合理，是一個(gè)探索和工程結(jié)合的工作，其難度和工作量適中。 陳日閃以系統(tǒng)性能分析，尋找系統(tǒng)性能優(yōu)化點(diǎn)為目標(biāo)，討論了 行系統(tǒng)的性能評(píng)估指標(biāo)和方法，設(shè)計(jì) 了 基準(zhǔn) 測(cè)試程序集 ， 在 統(tǒng)上開(kāi)展了若干評(píng)估實(shí)驗(yàn)。通過(guò)實(shí)驗(yàn)結(jié)果分析，給出了若干系統(tǒng)改進(jìn)的建議，并在落后者問(wèn)題上，具體通過(guò)修改任務(wù)調(diào)度算法來(lái)實(shí)現(xiàn)了一個(gè)優(yōu)化改進(jìn)。這一系列工作連貫，工作內(nèi)容包括論文閱讀，查考文獻(xiàn)，系統(tǒng)和算法設(shè)計(jì)，性能評(píng)估實(shí)驗(yàn)，編碼調(diào)試，分布式系統(tǒng)運(yùn)行和部署等。本論文工作，作為一個(gè)科研綜合訓(xùn)練完成得很好，符合培養(yǎng)目標(biāo)。同時(shí)，本論文工作也存在一些不足，在深度和系統(tǒng)性上還可以更加深入，比如加入相關(guān)系統(tǒng)的對(duì)比實(shí)驗(yàn)，擴(kuò)展更多的實(shí)驗(yàn)設(shè)計(jì)和分析等，這些可以在 陳日閃同學(xué)進(jìn)一步工作中來(lái)完善。 導(dǎo)師簽名： 年 月 日 北京大學(xué)本科生學(xué)位論文 i 摘要 一個(gè)在海量數(shù)據(jù)上進(jìn)行數(shù)據(jù)處理的并行編程模型，它特別適合于海量非結(jié)構(gòu)化和結(jié)構(gòu)化數(shù)據(jù)的搜索、分析和挖掘任務(wù)，已經(jīng)開(kāi)始被人們廣泛使用。對(duì)于興起的眾多類似 統(tǒng)來(lái)說(shuō)，如何有效地評(píng)估和分析對(duì)比這些系統(tǒng)，成為當(dāng)前一個(gè)需要解決的問(wèn)題。 本文詳細(xì)討論了針對(duì) 行系統(tǒng)的性能評(píng)估指標(biāo)和方法，設(shè)計(jì)和選擇一系列具有代表性的程序和數(shù)據(jù)作為基準(zhǔn)，用來(lái)評(píng)估和分析 統(tǒng)。在這一評(píng)估方法指導(dǎo)下，本文在我們自己實(shí)現(xiàn)的 行系統(tǒng) 臺(tái)上擴(kuò)展了 能，然后進(jìn)行了一系列評(píng)估實(shí)驗(yàn)，來(lái)分析和尋找系統(tǒng)性能瓶頸，為未來(lái)系統(tǒng)優(yōu)化提供依據(jù)。通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)了我們系統(tǒng)的一些可改進(jìn)的問(wèn)題如任務(wù)調(diào)度、落后者問(wèn)題等等。我們選擇了針對(duì)導(dǎo)致提交任務(wù)延遲增加的落后者問(wèn)題，通過(guò)實(shí)現(xiàn)后備任務(wù)策略來(lái)嘗試改進(jìn)。經(jīng)模 擬實(shí)驗(yàn)結(jié)果顯示，我們提出的改進(jìn)策略能夠有效地改進(jìn)落后者問(wèn)題的性能問(wèn)題。 關(guān)鍵詞： 能評(píng)估， 落后者問(wèn)題，后備任務(wù)策略 北京大學(xué)本科生學(xué)位論文 i is an It is to as on It is a to in We a of as we in We of we as We by we 京大學(xué)本科生學(xué)位論文 錄 第 1 章 引言 . 4 第 2 章 架 . 6 型介紹 . 6 統(tǒng)實(shí)現(xiàn) . 6 實(shí)現(xiàn) . 8 第 3 章 系統(tǒng)評(píng)估 . 10 估目標(biāo) . 10 準(zhǔn)程序和數(shù)據(jù) . 10 準(zhǔn)程序集合 . 11 估目標(biāo) . 13 第 4 章 系統(tǒng)監(jiān)控和程序概要分析 . 15 現(xiàn)細(xì)節(jié) . 15 第 5 章 評(píng)估實(shí) 驗(yàn) . 17 群配置 . 17 驗(yàn)結(jié)果 . 17 任務(wù)延遲和總機(jī)器時(shí)間 . 17 均結(jié)束時(shí)間 . 18 速比 . 18 平性 . 20 障恢復(fù)穩(wěn)定性 . 20 驗(yàn)結(jié)果和性能問(wèn)題分析 . 20 銷分析 . 22 第 6 章 后備任務(wù)調(diào)度策略 . 24 題描述 . 24 關(guān)工作 . 24 . 24 . 25 構(gòu)環(huán)境中后備任務(wù)調(diào)度 . 25 現(xiàn)細(xì)節(jié) . 26 體框架 . 26 后者判定策略 . 26 統(tǒng)處理過(guò)程 . 28 據(jù)結(jié)構(gòu)細(xì)節(jié) . 28 備任務(wù)策略評(píng)估實(shí)驗(yàn) . 29 群配置和任務(wù)準(zhǔn)備 . 29 務(wù)耗時(shí)趨同性分析 . 29 北京大學(xué)本科生學(xué)位論文 后備任務(wù)策略評(píng)估 . 30 第 7 章 系統(tǒng)優(yōu)化方向 . 33 絡(luò)傳輸問(wèn)題 . 33 加用戶和系統(tǒng)的交互 . 33 數(shù)據(jù)庫(kù)領(lǐng)域看系統(tǒng)性能的其他提升空間 . 34 統(tǒng)易用性 . 34 第 8 章 總結(jié) . 35 北京大學(xué)本科生學(xué)位論文 4 第 1 章 引言 在成為人們?cè)诤Ａ繑?shù)據(jù)上進(jìn)行并行計(jì)算的重要編程模型，比如為大規(guī)模的網(wǎng)頁(yè)做索引、在海量的數(shù)據(jù)中進(jìn)行挖掘、龐大的科學(xué)計(jì)算任務(wù)等等。 人們開(kāi)始關(guān)注在普通計(jì)算機(jī)上實(shí)現(xiàn)大規(guī)模的并行計(jì)算以提供各種服務(wù)，無(wú)疑是這 方面的先驅(qū)者。 用 為日常計(jì)算的引擎，將 每天處理 20數(shù)據(jù) 1存在底層的存儲(chǔ)系統(tǒng)如 誤 !未定義書簽。 、誤 !未定義書簽。 中 。很多重要的搜索引擎服務(wù)，如索引、網(wǎng)頁(yè)排序、網(wǎng)頁(yè)消重與去噪、用戶日志分析、用戶行為預(yù)測(cè)等等，都可以使用 此外， 是一個(gè)如今很受歡迎的并行計(jì)算模型。 好的可擴(kuò)展性使得并行處理變得很容易，人們可以很方便地把 署到大規(guī)模的廉價(jià)機(jī)群上使用。它的開(kāi)源實(shí)現(xiàn)版本 今很多公司如 及部分研究機(jī)構(gòu)和大學(xué)如 等都開(kāi)始使用 行研究和開(kāi)發(fā)。 為了更好和方便地讓程序員使用 者類似的并行處理計(jì)算框架如 誤 !未定義書簽。 ，人們?cè)谄渖霞茉O(shè)了一系列的編譯系統(tǒng)，并通過(guò)高層的語(yǔ)言把計(jì)算任務(wù)映射為底層的 務(wù)。這方面的工作如在 實(shí)現(xiàn)的 現(xiàn)的 類似系統(tǒng)的開(kāi)發(fā)和研究也層出不窮，如微軟有自己的 誤 !未定義書簽。 /統(tǒng) 。擁有這樣的處理能力無(wú)疑成為一個(gè)互聯(lián)網(wǎng)公司的核心競(jìng)爭(zhēng)力，可以預(yù)見(jiàn)在未來(lái)的一段時(shí)間里面，還有類似的很多系統(tǒng)和研究出現(xiàn)。 人們?cè)谑褂?者類似的其他并行處理計(jì)算框架及其上層語(yǔ)言時(shí)，眾多的使用者對(duì)底層大規(guī)模并行處理計(jì)算框架有自己的需求。比如大學(xué)或研究機(jī)構(gòu)使用此類框架進(jìn)行科學(xué)計(jì)算時(shí)，系統(tǒng)的工作負(fù)載可能是偏向計(jì)算密集型，人們也關(guān)心系統(tǒng)對(duì)于計(jì)算任務(wù)的延遲反應(yīng)；而大型因特網(wǎng)公司如 的數(shù)據(jù)中心中，有若干程序員在同時(shí)提交計(jì)算任務(wù)，程序員不但關(guān)心計(jì)算任務(wù)的延遲，還關(guān)心整個(gè)中心中負(fù)載的調(diào)度公平性；而對(duì)于此類系統(tǒng)的開(kāi)發(fā)和研究人員來(lái)說(shuō)，他們關(guān)心系統(tǒng)的吞吐量、系統(tǒng)中各機(jī)器的狀態(tài)和使用情況等等。所以考慮此類并行處理計(jì)算框架特別是 統(tǒng)的各項(xiàng)系統(tǒng)指標(biāo)，并確定評(píng)估的程序和方法，對(duì)評(píng)估類似系統(tǒng)、基于用戶希望的系統(tǒng)設(shè)計(jì)折衷進(jìn)行系統(tǒng)之間的比較、改進(jìn)系統(tǒng)等等有很重要的意義。 在這個(gè)基礎(chǔ)上如有一些系統(tǒng)測(cè)試的工作如分析網(wǎng)絡(luò)的性能 ，以及對(duì)統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)性能評(píng)估的討論 16。 我們基于 現(xiàn)了自己的并行處理計(jì)算框架，并在其之上進(jìn)行了北京大學(xué)本科生學(xué)位論文 5 系統(tǒng)的測(cè)試和評(píng)估。我們提出了測(cè)試程序和數(shù)據(jù)，并基于此在系統(tǒng)中實(shí)現(xiàn)了監(jiān)控和程序性能概要分析框架。通過(guò)測(cè)試和評(píng)估實(shí)驗(yàn)，我們總結(jié)了系統(tǒng)的性能指標(biāo)和觀察到的問(wèn)題。我們針對(duì)其中的單機(jī)落后問(wèn)題，實(shí)現(xiàn)并驗(yàn)證了 后備任務(wù) 策略，并基于此改進(jìn)系統(tǒng)性能。最后，我們總結(jié)并給出了其他工作方向。 論文的剩余部分按如下方式進(jìn)行組織。 第二章對(duì) 模型和體系結(jié)構(gòu)進(jìn)行概述 ， 而第三章列出了需要評(píng)估的系統(tǒng)目標(biāo)和 我們?cè)O(shè)計(jì)的基準(zhǔn)程序和數(shù)據(jù)集合。 為了分析和評(píng)估系統(tǒng)，我們?cè)诘谒恼玛U述了系統(tǒng)監(jiān)控框架和程序概要分析的設(shè)計(jì)和實(shí)現(xiàn)細(xì)節(jié)。 之后我們?cè)诘谖逭轮辛谐隽藢?shí)驗(yàn)結(jié)果和給出了實(shí)驗(yàn)的分析，并在針對(duì)其中的落后者問(wèn)題實(shí)現(xiàn)了后備任務(wù)策略，在第六章中詳細(xì)闡述了后備任務(wù)策略的實(shí)現(xiàn)和實(shí)驗(yàn)評(píng)估。 我們?cè)诘谄哒轮袑?duì) 系統(tǒng)可能的優(yōu)化方向進(jìn)行了展望并在第八章中進(jìn)行了總結(jié) ， 最后是致謝 。 北京大學(xué)本科生學(xué)位論文 6 第 2 章 在這一章里面，我們將簡(jiǎn)單介紹 架的模型和 我們的系統(tǒng)實(shí)現(xiàn)。 研究人員受到函數(shù)式編程語(yǔ)言（ 啟發(fā)，在總結(jié)大量的大規(guī)模分布式處理程序共同特征的基礎(chǔ)上，提出了 行程序框架。 一大類大規(guī)模并行數(shù)據(jù)處理程序的抽象。這類計(jì)算的輸入是一個(gè)（鍵，值）對(duì)的集合，輸出也是一個(gè)（鍵，值）對(duì)的集合。用戶只需要提供兩個(gè)操作 實(shí)現(xiàn)， 行時(shí)庫(kù)就可以自動(dòng)把用戶程序并行化。 用戶提供 數(shù)的實(shí)現(xiàn)，它接收一個(gè)輸入對(duì)，產(chǎn)生一組 中間結(jié)果對(duì)。他們傳給 戶提供的 數(shù)，接收中間結(jié)果的一個(gè)鍵和具有此鍵的一組值，處理這些值，產(chǎn)生若干個(gè)（鍵，值）對(duì)做為輸出。它們的一般形式如下： 7 - - 型的最大好處是簡(jiǎn)便性，用戶只需要提供這兩個(gè)接口就可以處理大規(guī)模的數(shù)據(jù)，而不需要太多分布式計(jì)算的實(shí)現(xiàn)細(xì)節(jié)。 統(tǒng) 實(shí)現(xiàn) 實(shí)時(shí)運(yùn)行主要是為并行化和并發(fā)執(zhí)行服務(wù)的。 為了盡可能的并行化和擴(kuò)展系統(tǒng)， 輸入的數(shù)據(jù)分割到多個(gè)機(jī)器上。 中間數(shù)據(jù)的傳輸和序列化處理等由系統(tǒng)來(lái)控制。分割的數(shù)據(jù)由多個(gè) 處理。 這兩個(gè)步驟中 務(wù)和 可以同時(shí)執(zhí)行，且它們都具有良好的可擴(kuò)展性，也即可以方便地增加機(jī)器增加并發(fā)度。 而在系統(tǒng)實(shí)現(xiàn)的層面上，系統(tǒng)需要決定底層的各個(gè)細(xì)節(jié)如數(shù)據(jù)單元的大小、中間數(shù)據(jù)的處理、內(nèi)存的緩存多大、 排序的方式、 各個(gè)任務(wù)的調(diào)度、 機(jī)器的失敗和容錯(cuò)處理等等。 系統(tǒng)自動(dòng)的把這些細(xì)節(jié)都掩蓋，所以對(duì) 程序員來(lái)說(shuō)，他只需要知道這個(gè)編程模型并編寫 程序即可。 論文中描述了他們?cè)诜植际綑C(jī)群系統(tǒng)上對(duì) 實(shí)現(xiàn)。系統(tǒng)把輸入數(shù)據(jù)劃分為 M 份數(shù)據(jù)片，這些輸入數(shù)據(jù)片可以在不同的機(jī)器上并發(fā)的北京大學(xué)本科生學(xué)位論文 7 被 數(shù)處理。所有的中間結(jié)果對(duì)使用一個(gè)分區(qū)函數(shù)（ 為 R 份。然后，對(duì)于每個(gè)分區(qū)，通過(guò)排序把具有相同鍵的所有（鍵，值）對(duì)聚合到一起，用 數(shù)處理，最后產(chǎn)生 R 個(gè)輸出文件。 R 的值和分區(qū)函數(shù)可以由用戶指定，系統(tǒng)默認(rèn)的分區(qū)函數(shù)是 1。 現(xiàn)是構(gòu)建在 上的，所有的 序的輸入和輸出都是存儲(chǔ)在 的文件。由于 的數(shù)據(jù)都有多個(gè)副本，當(dāng)執(zhí)行 機(jī)群和運(yùn)行 機(jī)群是同一個(gè)時(shí)， 的調(diào)度模塊會(huì)盡量把 務(wù)分配到存儲(chǔ)數(shù)據(jù)的機(jī)器上本地運(yùn)行，這樣可以避免輸入數(shù)據(jù)的網(wǎng)絡(luò)傳輸，極大的提高性能。此外，用戶可以指定函數(shù)用來(lái)把原始輸入數(shù)據(jù)轉(zhuǎn)換為 數(shù) 的輸入，用戶也可以指定函數(shù)用來(lái)把 輸出結(jié)果序列化為輸出數(shù)據(jù)。 體系結(jié)構(gòu)圖 1如下 ： 數(shù)據(jù)的流圖 8如下， 別執(zhí)行本地的任務(wù)，可能是 務(wù)、 務(wù)。整個(gè)過(guò)程由 制和協(xié)調(diào)調(diào)度。 圖表 1 北京大學(xué)本科生學(xué)位論文 8 我們實(shí)現(xiàn)的類似平臺(tái)是 我們 自己也實(shí)現(xiàn)了一個(gè)自制 的立在 似的 分布式文件 系統(tǒng) 9。 設(shè)計(jì)上與 小的設(shè)置 9。 與 供運(yùn)行時(shí)庫(kù)然后通過(guò)一個(gè)二進(jìn)制程序的多個(gè)副本扮演不同角色的方式不同，我們的實(shí)現(xiàn)提供的是一個(gè)執(zhí)行 業(yè)的服務(wù)，用戶把編寫好的實(shí)現(xiàn)指定接口的動(dòng)態(tài)鏈接庫(kù)用系統(tǒng)提供的 交上來(lái)， 統(tǒng)就會(huì)自動(dòng)調(diào)度和運(yùn)行相關(guān)的任務(wù)。服務(wù)由一臺(tái)主控（ 器和若干臺(tái)工作機(jī)（ 成， 責(zé)把用戶提交的作業(yè)（ 分為若干個(gè)任務(wù)，然后調(diào)度他們?cè)诟髋_(tái)工作機(jī)上執(zhí)行。相比提供運(yùn)行時(shí)庫(kù)由用戶編譯為一個(gè)程序的方式，這樣做的好處是，系統(tǒng)的改進(jìn)升級(jí)對(duì)用戶是不可見(jiàn)的。如果系統(tǒng)的實(shí)現(xiàn)改變了，只要 改變，用戶無(wú)需改變代碼甚至不需要重新編譯生成動(dòng)態(tài)鏈接庫(kù)就可以執(zhí)行 給我們未來(lái)系統(tǒng)的升級(jí)優(yōu)化帶來(lái)了極大的便利。不僅如此，在 果同一個(gè)機(jī)群有多個(gè)作業(yè)在同時(shí)運(yùn)行，因?yàn)樽鳂I(yè)由主控程序負(fù)責(zé)調(diào)度但一個(gè)作業(yè)的主控程序是不知道另一個(gè)作業(yè)的存在的，所以多個(gè)作業(yè)之 間可能產(chǎn)生資源的互相搶占。而在我們的系統(tǒng)中，一個(gè)機(jī)群只有一個(gè)主控程序，主控程序 可以綜合各個(gè)作業(yè)的情況對(duì)所有任務(wù)整體進(jìn)行調(diào)度。 這里需要詳細(xì)說(shuō)明我們?nèi)蝿?wù)設(shè)計(jì)的細(xì)節(jié)。 我們把 要做的任務(wù)分成三個(gè)類型： 們圖表 2 北京大學(xué)本科生學(xué)位論文 9 把傳輸任務(wù)從原來(lái)的 在這里我們對(duì)此設(shè)計(jì)有如下的分析。 在原來(lái)的 務(wù)的執(zhí)行流程和設(shè)計(jì)下，對(duì)于 行完生成的中間數(shù)據(jù)，是由 到 器上通過(guò)遠(yuǎn)程調(diào)用取得 。這些 有可能出現(xiàn)的場(chǎng)景是很多 時(shí)來(lái)一臺(tái) 器上進(jìn)行取數(shù)據(jù)操作，造成 器對(duì)硬盤的隨機(jī)寫，而隨機(jī)寫對(duì)性能的影響是很大的 ，這樣的數(shù)據(jù)傳輸模型可以稱之為 “拉 ”。 而我們把傳輸任務(wù)獨(dú)立開(kāi)來(lái)，由 度控制，可以控制 輸?shù)臅r(shí)間，同時(shí) 同時(shí)接到多個(gè)傳輸任務(wù)的數(shù)據(jù)時(shí)可以做緩存，避免隨機(jī)寫的出現(xiàn)。 此外，我們?cè)?通過(guò)心跳線程和 信， 在執(zhí)行分配的任務(wù)時(shí)用 式啟動(dòng)一個(gè)新的進(jìn)程來(lái)執(zhí)行具體的 務(wù)。而傳輸任務(wù)使用啟動(dòng)線程用 行傳輸。 我們 在此基礎(chǔ)上， 實(shí)現(xiàn)了 系統(tǒng) ，我們的設(shè)計(jì)在實(shí)現(xiàn)上有很多和 同之處，也不同于開(kāi)源的 完成原型的開(kāi)發(fā)和測(cè)試后，針對(duì)性能和系統(tǒng)的評(píng)估成為了我們亟待解決的關(guān)鍵問(wèn)題。 我們由此開(kāi)始系統(tǒng)地對(duì)類似相關(guān)系統(tǒng)進(jìn)行分析和評(píng)估，我們相信對(duì)于 類似系統(tǒng)的研究 工作 的下一步 將 是對(duì)此類系統(tǒng)的優(yōu)化。 所以對(duì)當(dāng)前系統(tǒng)的分析和評(píng)估成為關(guān)鍵，找到系統(tǒng)使用中 的瓶頸所在，針對(duì)用戶需求的目標(biāo)進(jìn)行改進(jìn)，都是實(shí)際應(yīng)用中的重要問(wèn)題。我們?cè)?實(shí)現(xiàn)基礎(chǔ)上，開(kāi)發(fā)了一系列的基準(zhǔn)程序，細(xì)致地分析了系統(tǒng)中可能出現(xiàn)的問(wèn)題。 北京大學(xué)本科生學(xué)位論文 10 第 3 章 系統(tǒng)評(píng)估 我們總結(jié)了如下的一系列標(biāo)準(zhǔn)，用以衡量并行計(jì)算框架系統(tǒng)的各方面性能表現(xiàn)。 估目標(biāo) 1） 單任務(wù)延遲 2） 總機(jī)器時(shí)間 3） 平均結(jié)束時(shí)間 4） 加速比 5） 公平性 6） 故障恢復(fù)穩(wěn)定性 單任務(wù)延遲主要衡量單個(gè)任務(wù)在提交到得到響應(yīng)（成功、失敗或者取消）的時(shí)間，考慮的是系統(tǒng)和用戶的交互能力。低延遲可以提高系統(tǒng)和用戶的交互能力，有利于用戶更快地知道提交任務(wù)后的結(jié)果。 總機(jī)器 時(shí)間主要衡量在系統(tǒng)運(yùn)行過(guò)程中所有機(jī)器的用時(shí)，考慮的是整個(gè)系統(tǒng)的計(jì)算能力。對(duì)于同樣的任務(wù)和數(shù)據(jù)，更少的總機(jī)器時(shí)間說(shuō)明了系統(tǒng)能有更少的計(jì)算資源（機(jī)器和時(shí)間）去完成同樣的事情。 平均結(jié)束時(shí)間主要從多個(gè)任務(wù)的完成情況來(lái)考慮系統(tǒng)的性能。由于系統(tǒng)的目標(biāo)在于統(tǒng)籌整個(gè)數(shù)據(jù)中心的計(jì)算資源，所以在多個(gè)任務(wù)的并行運(yùn)行的情況下系統(tǒng)的吞吐量是值得關(guān)注的對(duì)象。 加速比考慮系統(tǒng)對(duì)計(jì)算任務(wù)的加速比，主要衡量系統(tǒng)的擴(kuò)展性能力，計(jì)算不同規(guī)模的機(jī)群節(jié)點(diǎn)下對(duì)任務(wù)完成情況的提高比率。 公平性考慮在多任務(wù)同時(shí)運(yùn)行的情況下，衡量系統(tǒng)對(duì)待各 個(gè) 任務(wù)的公平性 。對(duì)于一些任務(wù)系統(tǒng)理應(yīng)優(yōu)先執(zhí)行，而對(duì)于一些任務(wù)系統(tǒng)應(yīng)該延后執(zhí)行。 由于公平性是一個(gè)比較寬泛且見(jiàn)仁見(jiàn)智的問(wèn)題，我們只是針對(duì)此問(wèn)題提出了一些基本的任務(wù)執(zhí)行場(chǎng)景和評(píng)估方法。 故障恢復(fù)穩(wěn)定性衡量的是系統(tǒng)的故障恢復(fù)能力和穩(wěn)定性。眾所周知的是，樣的系統(tǒng)通常需要運(yùn)行在超大規(guī)模的集群上，故障是同種類型的系統(tǒng)需要處理的正常問(wèn)題，所以在故障下的恢復(fù)和穩(wěn)定性應(yīng)該成為此類系統(tǒng)的評(píng)估目標(biāo)。 準(zhǔn)程序和數(shù)據(jù) 數(shù)據(jù)庫(kù)領(lǐng)域中設(shè)計(jì)了非常成功的 序作為測(cè)試和調(diào)優(yōu)的基準(zhǔn)程序，但北京大學(xué)本科生學(xué)位論文 11 是在分布式計(jì)算引擎中，并沒(méi)有公認(rèn)的代表程 序集作為基準(zhǔn)程序。一個(gè)優(yōu)秀的基準(zhǔn)程序集合對(duì)于系統(tǒng)的性能調(diào)優(yōu)、不同系統(tǒng)的對(duì)比、調(diào)度的決策、機(jī)群的管理和資源的利用等等都應(yīng)該給出統(tǒng)一和明確有效的衡量標(biāo)準(zhǔn)。 基于如上考慮和系統(tǒng)調(diào)優(yōu)的現(xiàn)實(shí)需求，同時(shí)考察了同類系統(tǒng)的測(cè)量程序集，我們初步給出如下程序集作為基準(zhǔn)程序，并設(shè)計(jì)了一系列的指標(biāo)作為衡量參數(shù)。 準(zhǔn)程序集合 基準(zhǔn)程序集合應(yīng)該是以能夠代表系統(tǒng)的應(yīng)用程序?yàn)槟繕?biāo)，最有代表性的是真正運(yùn)行于實(shí)際系統(tǒng)的程序集合。但是選擇基準(zhǔn)程序集合卻只能盡量挑選關(guān)鍵程序，使得它們?cè)诟鞣矫娴闹笜?biāo)上都具有代表性。 我們選取了下列的程序作為基準(zhǔn)程 序，它們主要涵蓋了應(yīng)用程序的關(guān)鍵領(lǐng)域：搜索引擎的重要應(yīng)用（ 日常分析和統(tǒng)計(jì)（ 科學(xué)計(jì)算（矩陣乘法）、 衛(wèi)星圖像處理（ 及典型的 階段處理的計(jì)算（ 同時(shí)我們使用不同大小的數(shù)據(jù)集 來(lái)考慮系統(tǒng)的數(shù)據(jù)局部性和擴(kuò)展性的能力，并 考慮把單機(jī)的性能結(jié)果作為加速比測(cè)試的基準(zhǔn)線。 是一個(gè) 典型處理過(guò)程，它對(duì)在一些數(shù)據(jù)中出現(xiàn)的詞匯進(jìn)行計(jì)數(shù) 。在我們的測(cè)試中，我們?cè)?文網(wǎng)頁(yè)數(shù)據(jù)集上做詞頻統(tǒng)計(jì)計(jì)算，此實(shí)驗(yàn)用來(lái)測(cè)試系統(tǒng)處理大規(guī)模數(shù)據(jù)時(shí)的可靠性和穩(wěn)定性。 數(shù)分析每個(gè) 頁(yè)，去除 簽，進(jìn)行中文分詞，以每個(gè)中文詞為鍵，值為 1 輸出鍵值對(duì)。 數(shù)把聚合到一起的各個(gè)值加起來(lái)得到總的詞頻。程序允許是要做本地合并（ 這樣可以極大的減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量。 出來(lái)的一個(gè) 序 10。實(shí)驗(yàn)中隨機(jī)生成長(zhǎng)度為 100 字節(jié)的記錄，要求對(duì)其進(jìn)行排序。 用一個(gè) 完成，其程序的處理過(guò)程也是 典型處理。先由 數(shù)提取記錄的前 10 個(gè)字節(jié)作為鍵，剩余記錄作為值輸出鍵值對(duì)。而 數(shù)接受分割后的數(shù)據(jù)作為輸入，進(jìn)行排序。而分區(qū)函數(shù)根據(jù)鍵的范圍進(jìn)行分區(qū)，可以進(jìn)行區(qū)段分割，從而在各個(gè) 成后完成了整個(gè)數(shù)據(jù)的排序過(guò)程。 所以這個(gè)排序程序也可以作為 統(tǒng)的基準(zhǔn)測(cè)試程序。 北京大學(xué)本科生學(xué)位論文 12 很多鏈接分析技術(shù)用來(lái)對(duì) 絡(luò)結(jié)構(gòu)進(jìn)行分析。 其中最重要的一個(gè)，它描述了一個(gè)網(wǎng)頁(yè)的重要程度 11，它被認(rèn)為可以極大的提高搜索引擎檢索結(jié)果的精度。一個(gè)網(wǎng)頁(yè)的 計(jì)算公式如下： )=(1d(1)/C(.+n)/C( 其中，假設(shè)網(wǎng)頁(yè) A 有 n 個(gè)網(wǎng)頁(yè) 向它， $C(A)$表示網(wǎng)頁(yè) A 向外的鏈接的數(shù)量。 d 是一個(gè)取值在 0 到 1 之間的阻尼因子，一般取 據(jù)這個(gè)公式，網(wǎng)頁(yè)的 以通過(guò)若干輪迭代得到，并且可 以證明迭代會(huì)收斂。 使用 算 過(guò)程分為兩個(gè)階段。第一階段，構(gòu)建鏈接圖。 數(shù)分析一個(gè)網(wǎng)頁(yè)，把網(wǎng)頁(yè) 為鍵，改網(wǎng)頁(yè)初始 ，以及 它 所 包 含 所 有 指 出 的 為 值 輸 出 ， 即 (.,這個(gè)過(guò)程可以和前面所述的任何網(wǎng)頁(yè)分析的 程結(jié)合到一起進(jìn)行。 數(shù)不做處理，把輸入直接作為輸出。 第二個(gè)階段，以第一階段得到的鏈接圖作為輸入，以下 算迭代若干次直到收斂。 數(shù)把 輸入記錄映射為 (., (C(, (C(等。在照公式把同一個(gè) 按照原輸入的格式輸出。之后，用一個(gè)串行程序比較上一輪得到的 果未收斂，則進(jìn)入下一輪迭代。 在我們的實(shí)驗(yàn)中，我們使用的數(shù)據(jù)模擬 鏈接分布，我們生成若干個(gè)出 個(gè)數(shù)依 布。 序是數(shù)據(jù)挖掘中的基礎(chǔ)算法。 它要求把一個(gè)點(diǎn)集聚合成若干個(gè)簇，簇間的點(diǎn)盡可能的聚合在一起。 對(duì)于是用 處理此程序，需要多次的迭代過(guò)程 ，所以 序也可以代表需要不斷迭代的程序集合。 在每一次的迭代過(guò)程中， 務(wù)讀入點(diǎn)集 數(shù)據(jù)中 的一個(gè)子集，并把中心點(diǎn)向量讀入，以中心點(diǎn)向量來(lái)判斷每一個(gè)點(diǎn)是否應(yīng)該輸入那個(gè)中心下的簇。 它計(jì)算出每個(gè)點(diǎn)和中心點(diǎn)向量中的距離并把點(diǎn)分派給最近的簇。 而 務(wù)把相同簇的點(diǎn)都聚合到一起，然后重新計(jì)算它們的中心點(diǎn)，然后更新中心點(diǎn) 向量。 一輪迭代結(jié)束后， 序會(huì)繼續(xù)迭代直到滿足收斂條件為止。收斂的條件一般為兩輪對(duì)比各個(gè)簇沒(méi)有大的變化就可以停止迭代。 北京大學(xué)本科生學(xué)位論文 13 陣乘法 是一個(gè) 計(jì)算密集型的任務(wù)。 務(wù) 計(jì)算輸出矩陣中的一個(gè)行，然后對(duì)矩陣中的每個(gè)元素返回位置和值 。 集數(shù)據(jù)并輸出。 估目標(biāo) 對(duì)于 上述選定的基準(zhǔn)程序集合，我們從 模型和系統(tǒng)實(shí)現(xiàn)出發(fā)，考慮它們的各項(xiàng)屬性。從而可以通過(guò)這些屬性來(lái)對(duì)基準(zhǔn)程序進(jìn)行評(píng)估，知道它們對(duì) 統(tǒng)的影響是什么類型的。 從另 一方面來(lái)說(shuō)，如果有新的基準(zhǔn)程序加入，同樣考慮對(duì)這些數(shù)據(jù)屬性進(jìn)行評(píng)估，就可以知道此程序的性質(zhì)，如是否是數(shù)據(jù)密集型，是否導(dǎo)致 我們考慮這些指標(biāo)，如果有特殊領(lǐng)域的應(yīng)用程序，那可以根據(jù)這些屬性值 集合 建立對(duì)應(yīng)的基準(zhǔn)程序，從而 方便 地對(duì)系統(tǒng)進(jìn)行評(píng)估。 基準(zhǔn)程序的 衡量指標(biāo) 如下 12： 1） 任務(wù)大?。狠斎氲臄?shù)據(jù)字節(jié)數(shù)， 務(wù)的數(shù)目。 2） 務(wù)的選擇度：在平均的 務(wù)中，輸出的字節(jié)數(shù)除以輸入的字節(jié)數(shù) 3） 務(wù)的選擇度：在平均的 務(wù)中，輸出的字節(jié)數(shù)除以 輸入的字節(jié)數(shù) 4） 務(wù)的平均字節(jié)計(jì)算時(shí)間 ： 在 務(wù)中計(jì)算一個(gè)字節(jié)需要的平均時(shí)間 5） 務(wù)的平均字節(jié)計(jì)算時(shí)間：在 務(wù)中計(jì)算一個(gè)字節(jié)需要的平均時(shí)間 6） 數(shù)據(jù)的壓縮率 ： 分布式文件系統(tǒng)中該基準(zhǔn)程序的數(shù)據(jù)壓縮率。（注：在我們的實(shí)驗(yàn)中暫不考慮此項(xiàng)屬性） 7） 方式： 是選擇一部分?jǐn)?shù)據(jù)還是對(duì) 所有數(shù)據(jù)進(jìn)行順序讀 入 。 8） 傳輸?shù)姆绞?： 在進(jìn)行傳輸任務(wù)時(shí)時(shí)候有偏移 ，對(duì)數(shù)據(jù)的分割狀況是怎么樣的 ，是否做到分割上的負(fù)債均衡。 9） 中間數(shù)據(jù)大?。?傳輸?shù)臅r(shí)候中間數(shù)據(jù)的字節(jié)數(shù)。 10） 參數(shù)：是否需要數(shù)據(jù)做外 排。 11） 務(wù)的復(fù)雜度：比如，為 O(n) 12） 務(wù)的復(fù)雜度：比如，為 O(n) 我們選擇能夠代表典型 程的 實(shí)例說(shuō)明基準(zhǔn)程序在我們的實(shí)驗(yàn)系統(tǒng)上各指標(biāo)的值。 實(shí)驗(yàn)數(shù)據(jù)是 50M 條記錄的 據(jù)量為 北京大學(xué)本科生學(xué)位論文 14 表格 1任務(wù)大小 輸入 務(wù) 75 個(gè)， 務(wù)的選擇度 1 務(wù)的選擇度 1 務(wù)的平均字節(jié)計(jì)算時(shí)間 務(wù)的平均字節(jié)計(jì)算時(shí)間 據(jù)的壓縮率 暫不考慮 方式 對(duì) 有數(shù)據(jù)順序讀入 傳輸?shù)?方式 均勻分布 中間數(shù)據(jù)大小 參數(shù) 不需要外排 務(wù)的復(fù)雜度 O(n) 務(wù)的復(fù)雜度 nO(我們說(shuō)明和分析 表中的 數(shù)值。 首先， 任務(wù)的選擇度都是 1，因?yàn)閷?duì)于 說(shuō)，的是把數(shù)據(jù)簡(jiǎn)單地讀入，然后進(jìn)行傳輸和分 割，而對(duì) 說(shuō)，進(jìn)行完數(shù)據(jù)的排序后也只需要把數(shù)據(jù)簡(jiǎn)單地輸出，所以選擇度都是 1. 然后，對(duì)于 傳輸 的方式，按記錄的生成原則，可以均稱地進(jìn)行 割。中間數(shù)據(jù)比初始讀入的數(shù)據(jù)反而小是因?yàn)楹芏鄶?shù)據(jù) 務(wù)做完后可以在本地直接進(jìn)行 用的數(shù)據(jù)的空間數(shù)據(jù)性，所以傳輸數(shù)據(jù)變小。 最后 務(wù)需要進(jìn)行排序，系統(tǒng)實(shí)現(xiàn)使用快排，復(fù)雜度為 nO( 北京大學(xué)本科生學(xué)位論文 15 第 4 章 系統(tǒng)監(jiān)控和程序概要分析 更好地理解和監(jiān)控云計(jì)算的基礎(chǔ)設(shè)施系統(tǒng)如 一個(gè)煩人且亟待解決的問(wèn)題。現(xiàn)有的實(shí)現(xiàn)都是比較簡(jiǎn)單地記錄 系統(tǒng)的相關(guān)性能信息，而且并沒(méi)有太多關(guān)于在此類系統(tǒng)中如何監(jiān)控和評(píng)估的工作。但是在我們的開(kāi)發(fā)和使用過(guò)程中，我們發(fā)現(xiàn)了系統(tǒng)的性能概要分析很重要，或者說(shuō)通過(guò)更好地理解底層系統(tǒng)，能夠更好地改善和優(yōu)化現(xiàn)有的系統(tǒng)。例如如下的幾個(gè)場(chǎng)景中，我們將說(shuō)明這一點(diǎn) : 數(shù)據(jù)中心中的一個(gè)程序員向系統(tǒng)提交了一個(gè)用高層語(yǔ)言如 述的任務(wù)后，他 /她可能想知道他的任務(wù)做到什么程度。從性能概要分析的角度來(lái)考慮任務(wù)監(jiān)控這個(gè)問(wèn)題，任務(wù)在多個(gè)機(jī)器上的性能分布很重要。這樣可以知道任務(wù)中最耗時(shí)的函數(shù)，從來(lái)讓程序員可以針對(duì)此考慮改進(jìn)自己的程序 ，或者在系統(tǒng)對(duì)任務(wù)的編譯中進(jìn)行優(yōu)化。 失效在數(shù)據(jù)中心里面是正常的 1。 樣的系統(tǒng)對(duì)用戶掩蓋機(jī)器的失效，如果機(jī)器發(fā)生宕機(jī)，系統(tǒng)將處理并調(diào)度計(jì)算重執(zhí)行；而對(duì)于計(jì)算任務(wù)的失效，處理方式是重新執(zhí)行，如果多次失效超過(guò)一定次數(shù)，將放棄執(zhí)行。這是因?yàn)樵跀?shù)據(jù)中心中， 很有可能是用戶提交的任務(wù)的程序中存在 者是數(shù)據(jù)有不滿足格式而導(dǎo)致無(wú)法讀入等等。對(duì)于需要進(jìn)行長(zhǎng)任務(wù)處理的工作來(lái)說(shuō)，在現(xiàn)有系統(tǒng)的實(shí)現(xiàn)下，可能是 一件極消耗用戶程序員精力的事情。可能的情形是，執(zhí)行了很久到快結(jié)束的時(shí)候由于 者存儲(chǔ)的問(wèn)題導(dǎo)致失敗而最終放棄。 而實(shí)時(shí)的監(jiān)控和交互可以部分地解決這個(gè)問(wèn)題，讓用戶及時(shí)地知道系統(tǒng)里面發(fā)生的情況，對(duì)于系統(tǒng)無(wú)法做出判斷的事情（程序有錯(cuò)），交給用戶去解決不失為一個(gè)可行的方案。 分布式系統(tǒng)中的一個(gè)很重要的措施就是要保證負(fù)載均衡，這對(duì)于并行計(jì)算的框架來(lái)說(shuō)，同樣意義重大。在計(jì)算的過(guò)程中記錄性能信息和進(jìn)行監(jiān)控，可以通知用戶或者系統(tǒng)。通過(guò)重新的調(diào)度或者其他手段使得負(fù)載盡可能均衡。 總之，通過(guò)監(jiān)控和程序的性能概要分析，我們可 以讓系統(tǒng)和用戶之間有更多交互。同時(shí)給出的數(shù)據(jù)可以幫助用以評(píng)估系統(tǒng)，提供給不同的人如用戶或者系統(tǒng)開(kāi)發(fā)人員分析。 現(xiàn)細(xì)節(jié) 我們需要記錄一個(gè)子任務(wù)的運(yùn)行時(shí)性能概要信息，通過(guò)以下的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。 / 京大學(xué)本科生學(xué)位論文 16 ; ; , by ; 對(duì)于 段，分別記錄扇入扇出的數(shù)據(jù)大小、 記錄個(gè)數(shù)；以及做扇入扇出、記錄個(gè)數(shù)；對(duì)于 段，記錄扇入扇出的數(shù)據(jù)大小、 記錄個(gè)數(shù)；還有傳輸任務(wù)的傳輸數(shù)據(jù)量；最后是各個(gè)任務(wù)的花費(fèi)時(shí)間。 通過(guò)在 執(zhí)行任務(wù)后記錄下任務(wù)的性能概要情況，然后通過(guò)文件管道傳遞給 心跳進(jìn)程，然后通過(guò)心跳捎帶給 供分析。 進(jìn)行捎帶處理的心跳使用 現(xiàn)，具體實(shí)現(xiàn)如下。 先使用 述 接口。 /* * to is * * ( 然后經(jīng)過(guò) 編譯后生成服務(wù)器端和客戶端的 C+代碼，然后把任務(wù)的性能概要信息發(fā)送給 。 北京大學(xué)本科生學(xué)位論文 17 第 5 章 評(píng)估實(shí)驗(yàn) 在這一章 中，我們將對(duì)上一章中設(shè)定的系統(tǒng)性能指標(biāo)進(jìn)行評(píng)估。 并闡述每一項(xiàng)實(shí)驗(yàn)的環(huán)境、應(yīng)用程序和結(jié)果分析。 群配置 我們的機(jī)群配置如下。 我們?cè)诤?