【畢業(yè)學位論文】（Word原稿）MapReduce的系統(tǒng)性能評估與Backup調度策略

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