雲端運算近年來十分火紅，從IBM、Microsoft到Amazon每家廠商都推出雲端服務，在雲端運算迅速崛起的同時也出現些許問題。將資料存放在雲端上，利用雲端做龐大資料分析與處理的同時，如果出現錯誤或是網路斷線該如何解決？本篇論文主要探討主題為雲端運算上容錯議題，主要著眼在如何在MapReduce中有效且正確判定節點中的緩慢任務，在判定之後能夠使用較有效率的方法做重新分配處理緩慢任務，以避免整體工作時間被緩慢任務所拖慢進而影響到工作完成時間。本文主要以Hadoop作為開發實驗環境，利用模擬比較Hadoop、LATE以及本篇所提出之方法並分析其優劣。

Cloud computing is gaining popularity in recent years. Many renowned companies such as IBM, Microsoft, Amazon, are providing services over the cloud. It is inevitable that failures may occur in the cloud, so how to make a cloud computing system fault-tolerant is very important. In this research, we try to identify true slow tasks in Hadoop MapReduce’s jobs and migrate them to other compute nodes before failures occur. Specifically, we modify the LATE algorithm to make MapReduce scheduler adapt to tasks with variable progress rates. We also study three rescheduling methods and compare their performances.

目錄
第一章 緒論	1
1.1 研究背景和動機	1
1.2 論文架構	4
第二章 相關研究	6
2.1 LATE與SAMR演算法	6
2.2 Hadoop API與Progress Score取得方法	8
第三章 緩慢任務判定方法與容錯機制	10
3.1 定義緩慢任務	10
3.2 LATE-VPR概要	11
3.3 緩慢任務之判定方法	14
3.4 緩慢任務重新分配與處理	16
3.5 Data Locality之備份分配與錯誤後處理	18
第四章 系統實作與分析	20
4.1 數據分析	21
4.2 性能比較	35
4.3 性能分析	37
4.4 綜合比較	39
4.5 Data Locality機制比較	44
第五章 結論	60
參考文獻	61
附錄-英文論文	62

圖目錄
圖3-1 任務進度示意圖 10
圖4-1-(a) 隨機-97%-工作完成時間 22
圖4-1-(b) 隨機-98%-工作完成時間 22
圖4-1-(c) 隨機-99%-工作完成時間 23
圖4-2-(a) 隨機-97%-平均任務完成時間 23
圖4-2-(b) 隨機-98%-平均任務完成時間 24
圖4-2-(c) 隨機-99%-平均任務完成時間 24
圖4-3-(a) 隨機-97%-錯誤前經過時間 25
圖4-3-(b) 隨機-98%-錯誤前經過時間 25
圖4-3-(c) 隨機-99%-錯誤前經過時間 26
圖4-4-(a) 輪流-97%-工作完成時間 26
圖4-4-(b) 輪流-98%-工作完成時間 27
圖4-4-(c) 輪流-99%-工作完成時間 27
圖4-5-(a) 輪流-97%-平均任務完成時間 28
圖4-5-(b) 輪流-98%-平均任務完成時間 28
圖4-5-(c) 輪流-99%-平均任務完成時間 29
圖4-6-(a) 輪流-97%-錯誤前經過時間 29
圖4-6-(b) 輪流-98%-錯誤前經過時間 30
圖4-6-(c) 輪流-99%-錯誤前經過時間 30
圖4-7-(a) 閒置任務優先-97%-工作完成時間 31
圖4-7-(b) 閒置任務優先-98%-工作完成時間 31
圖4-7-(c) 閒置任務優先-99%-工作完成時間 32
圖4-8-(a) 閒置任務優先-97%-平均任務完成時間 32
圖4-8-(b) 閒置任務優先-98%-平均任務完成時間 33
圖4-8-(c) 閒置任務優先-99%-平均任務完成時間 33
圖4-9-(a) 閒置任務優先-97%-錯誤前經過時間 34
圖4-9-(b) 閒置任務優先-98%-錯誤前經過時間 34
圖4-9-(c) 閒置任務優先-99%-錯誤前經過時間 35
圖4-10-(a) 三者比較-97%-工作完成時間 39
圖4-10-(b) 三者比較-97%-工作完成時間 39
圖4-11-(a) Hadoop各判定方法之工作完成時間比較 40
圖4-11-(b) Hadoop各判定方法之工作完成時間比較 41
圖4-12-(a) LATE各判定方法之工作完成時間比較 42
圖4-12-(b) LATE各判定方法之工作完成時間比較 42
圖4-13-(a) LATE-VPR各判定方法之工作完成時間比較 43
圖4-13-(b) LATE-VPR各判定方法之工作完成時間比較 43
圖4-14-(a) 隨機Data Locality-97%-工作完成時間 44
圖4-14-(b) 隨機Data Locality-98%-工作完成時間 45
圖4-14-(c) 隨機Data Locality-99%-工作完成時間 45
圖4-15-(a) 隨機Data Locality-97%-平均任務完成時間 46
圖4-15-(b) 隨機Data Locality-98%-平均任務完成時間 47
圖4-15-(c) 隨機Data Locality-99%-平均任務完成時間 47
圖4-16-(a) 輪流Data Locality-97%-工作完成時間 48
圖4-16-(b) 輪流Data Locality-98%-工作完成時間 49
圖4-16-(c) 輪流Data Locality-99%-工作完成時間 49
圖4-17-(a) 輪流Data Locality-97%-平均任務完成時間 50
圖4-17-(b) 輪流Data Locality-98%-平均任務完成時間 51
圖4-17-(c) 輪流Data Locality-99%-平均任務完成時間 51
圖4-18-(a) 閒置任務優先Data Locality-97%-工作完成時間 52
圖4-18-(b) 閒置任務優先Data Locality-98%-工作完成時間 53
圖4-18-(c) 閒置任務優先Data Locality-99%-工作完成時間 53
圖4-19-(a) 閒置任務優先Data Locality-97%-平均任務完成時間 54
圖4-19-(b) 閒置任務優先Data Locality-98%-平均任務完成時間 55
圖4-19-(c) 閒置任務優先Data Locality-99%-平均任務完成時間 55
圖4-20-(a) 有無Data Locality隨機法工作完成時間比較 56
圖4-20-(b) 有無Data Locality隨機法工作完成時間比較 56
圖4-20-(c) 有無Data Locality隨機法工作完成時間比較 57
圖4-21-(a) 有無Data Locality隨機法平均任務完成時間比較 57
圖4-21-(b) 有無Data Locality隨機法平均任務完成時間比較 58
圖4-21-(c) 有無Data Locality隨機法平均任務完成時間比較 58

[1] 	Matei Zaharia, Andy Konwinski, Anthony D.Joseph, Randy Katz, Ion Stoica, “Improving MapReduce Performance in Heterogeneous Enviroments,” USENIX pp.29-42 ,2008
[2] 	Steven Y.ko,Imranul Hoque,Brian Cho,Indranil Gupta,”Making Cloud Intermediate Data Fault-Tolerant,” AMC, 2010.
[3] 	I˜nigo Goiri, Ferran Juli`a, Jordi Guitart, and Jordi Torres,“Checkpointpoint-based Fault-tolerant Infrastructure for Virtualized Service Providers,” IEEE pp.455 – 462, 2010.
[4] 	Quiane-Ruiz, J.-A., ” RAFTing MapReduce: Fast recovery on the RAFT,” IEEE pp.589 - 600, 2011.
[5] 	Thilina Gunarathne, Tak-Lon Wu, Judy Qiu, Geoffrey Fox, “MapReduce in the Clouds for Science,” IEEE pp.565-572, 2010
[6] 	Richard A. Brown, “Hadoop at Home: Large-Scale Computing at a Small College,” SIGCSE pp.106-110, 2009
[7] 	Tom White, “hadoop:the Definitive Guide,” 2nd Edition, September 2010
[8] 	Hadoop, http://hadoop.apache.org/
[9] 	Amazon Elastic Compute Clode, http://aws.amazon.com/ec2/
[10] 	Christer A. Hansen, “Optimizing Hadoop for the cluster,” 2008
[11] 	Yahoo! Developer Network, http://developer.yahoo.com/hadoop
[12] 	J. Dean, S. Ghemawat, “MapReduce: Simplified Data Processing on   Large Clusters,” In Communications of theACM, 51 pp.107-113, 2008
[13] 	Quan Chen, Daqiang Zhang, Minyi Guo, Qianni Deng, Song Guo, “SAMR: A Self-adaptive MapReduce Scheduling Algorithm In Heterogeneous Environment,” IEEE pp.2736-2743, 2010