淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0609201213523100
中文論文名稱 以查核點提升Hadoop雲端計算系統容錯效能之研究
英文論文名稱 Using Checkpoints to Improve Fault Tolerance for Hadoop Cloud Computing Environment
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 陳廷豪
研究生英文姓名 Ting-Hau Chen
學號 699410121
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2012-07-10
論文頁數 80頁
口試委員 指導教授-林其誼
委員-林其誼
委員-蔡智強
委員-林振緯
中文關鍵字 Hadoop  MapReduce  查核點  中繼資料  資料在地化 
英文關鍵字 Hadoop  MapReduce  Checkpoint  Intermediate Data  Data locality 
學科別分類 學科別應用科學資訊工程
中文摘要 雲端計算中大規模數據密集型的MapReduce計算模組在近幾年來日益普及。Hadoop是用來實現MapReduce的雲端開源平台,它可以輕易且迅速的建立一個龐大的商用計算集群。在這種大型集群中,運算任務故障或運算節點故障並非是一種異常的情形,但是這些故障對於Hadoop的性能而言,這將會導致非常重大的影響。雖然Hadoop可以自動重新啟動失敗的任務並透過使用Speculative Execution來自動補償緩慢任務,但仍有許多研究人員發現了Hadoop容錯方面的缺點。在此研究中,我們探討當Hadoop在執行MapReduce運算時,如何以增加系統容錯能力的方式來減少因為錯誤恢復時所導致運算完成時間的延長與整體性能下降的問題。我們嘗試藉由設計一個簡單的Map任務查核點機制去改善這個問題,當該機制啟動時,透過雲端系統回傳的Progress與Heartbeat來獲得輸入資料區塊的執行進度,當輸入資料區塊處理進度達某特定百分比時,Mapper將會創建一個查核點來儲存Mapper執行時所產生的中繼資料。而一旦查核點建立後,若Mapper發生故障,Mapper則可以直接從查核點之後的進度開始執行而不需要將任務重頭開始執行。另外在加快錯誤恢復速度方面,在發生運算節點故障的情況下,我們利用移動TaskTracker的方式使得運算節點具有Data locality的性質,以節省輸入資料區塊搬移的時間。萬一具有輸入資料區塊的節點都在忙碌時,我們則優先選擇具有Rack locality性質的節點來執行任務的複製與移動,如此亦可加快錯誤恢復的速度。經由大量的模擬,我們發現我們提出的方法雖然需要花費更多的儲存空間與網路流量的成本,但相較於原始的Hadoop在任務完成時間方面,我們的方法表現出了更好的性能。
英文摘要 The computing paradigm of MapReduce has gained extreme popularity in the area of large-scale data-intensive applications in recent years. Hadoop, an open-source implementation of MapReduce, can be set up easily and rapidly on commodity hardware to form a massive computing cluster. In such a cluster, task failures and node failures are not an anomaly, which will cause a substantial impact on Hadoop’s performance. Although Hadoop can restart failed tasks automatically and compensate for slow tasks by enabling speculative execution, many researchers have identified the shortcomings of Hadoop’s fault tolerance. In this research, we try to improve them by designing a simple checkpointing mechanism for Map tasks. When the mechanism is enabled, a checkpoint will be created for a mapper when the progress of processing the input data block reaches a certain percentage. Once a mapper fails after the progress of the checkpoint state, it can resume from the checkpoint state without having to restart from scratch. By extensive simulations, the proposed approach shows better performance than native Hadoop in terms of job completion time, at the cost of more storage space and network traffic.
論文目次 目錄
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 5
1.3 論文架構 7
第二章 相關研究 8
2.1 將Checkpoint利用於雲端中的系統容錯 8
2.2 加快MapReduce任務執行速度 9
第三章 容錯機制設計 13
3.1 Hadoop中關於輸入處理進度與錯誤偵測 13
3.2 CKP-H & CKP-Q查核點運作機制 14
3.3 Data Location-Aware Rescheduling 25
3.4 CKP-H與CKP-Q虛擬碼 26
第四章 系統性能評估與分析 29
4.1 系統環境參數設定 29
4.2 模擬實例 30
4.2.1 Task Failure 31
4.2.2 Node Failure 45
4.2.3 Rack Failure 59
4.3 單一Task連續故障 71
4.4 Overhead分析 72
第五章 結論 74
參考文獻 75
附錄-英文論文 77

圖目錄
圖 1.1-1. 搭載大量運算節點的Rack。 2
圖 1.1-2. Hadoop備份檔配置方式。 4
圖 1.1-3. MapReduce運算過程概念圖。 5
圖 2.2-1. Data locality、Rack locality與No locality。 12
圖 3.2-1. Checkpoint儲存選擇。 17
圖 3.2-2. CKP-H的Checkpoint產生時機。 18
圖 3.2-3. CKP-H利用Checkpoint執行Task錯誤恢復。 19
圖 3.2-4. 當Node或是Rack Failure時,CKP-H的錯誤恢復選擇。 20
圖 3.2-5. CKP-H與Hadoop故障發生時,任務完成所需花費時間比較。 21
圖 3.2-6. CKP-Q的Checkpoint產生時機。 23
圖 3.2-7. 當故障發生時機恰好在任務進行的25%、50%、75%時,CKP-Q與Hadoop的任務完成所需執行的資料量。 24
圖 3.4-1. CKP-H虛擬碼。 26
圖 3.4-2. CKP-Q虛擬碼。 28
圖 4.2-1. Hadoop, CKP-H, CKP-Q的任務完成時間比較(16-Node)。 32
圖 4.2-2. Hadoop, CKP-H, CKP-Q的任務平均完成時間比較(16-Node)。 33
圖 4.2-3. Hadoop, CKP-H, CKP-Q的任務完成時間標準差(16-Node)。 34
圖 4.2-4. 輸入資料量為1TB、故障率10%時,Hadoop、CKP-H與CKP-Q的Task完成時間(16-Node)。 36
圖 4.2-5. Hadoop, CKP-H, CKP-Q的任務完成時間比較(64-Node)。 38
圖 4.2-6. Hadoop, CKP-H, CKP-Q的任務平均完成時間比較(64-Node)。 39
圖 4.2-7. Hadoop, CKP-H, CKP-Q的任務完成時間標準差比較(64-Node)。 40
圖 4.2-8. Hadoop, CKP-H, CKP-Q的任務完成時間比較(256-Node)。 42
圖 4.2-9. Hadoop, CKP-H, CKP-Q的任務平均完成時間比較(256-Node)。 43
圖 4.2-10. Hadoop, CKP-H, CKP-Q的任務完成時間標準差比較(256-Node)。 44
圖 4.2-11. Node Failure案例1 (16-Node)。 48
圖 4.2-12. Node Failure案例2 (16-Node)。 49
圖 4.2-13. Node Failure案例3 (16-Node)。 50
圖 4.2-14. Node Failure案例1 (64-Node)。 52
圖 4.2-15. Node Failure案例2 (64-Node)。 53
圖 4.2-16. Node Failure案例3 (64-Node)。 54
圖 4.2-17. Node Failure案例1 (256-Node)。 56
圖 4.2-18. Node Failure案例2 (256-Node)。 57
圖 4.2-19. Node Failure案例3 (256-Node)。 58
圖 4.2-20. Rack Failure案例1 (16-Node)。 60
圖 4.2-21. Rack Failure案例2 (16-Node)。 61
圖 4.2-22. Rack Failure案例3 (16-Node)。 62
圖 4.2-23. Rack Failure案例1 (64-Node)。 64
圖 4.2-24. Rack Failure案例2 (64-Node)。 65
圖 4.2-25. Rack Failure案例3 (64-Node)。 66
圖 4.2-26. Rack Failure案例1 (256-Node)。 68
圖 4.2-27. Rack Failure案例2 (256-Node)。 69
圖 4.2-28. Rack Failure案例3 (256-Node)。 70
圖 4.3-1. 原始Hadoop、CKP-H與CKP-Q以零故障為基礎做比較。 71

表目錄
表 3.1-1. Interface RecordReader內建功能。 13
表 4.1-1. 實驗環境設定參數。 29
表 4.2-1. 16-Node模擬實驗數據(Task Failure)。 31
表 4.2-2. 64-Node模擬實驗數據(Task Failure)。 37
表 4.2-3. 256-Node模擬實驗數據(Task Failure)。 41
表 4.2-4. 16-Node模擬實驗數據(Node Failure)。 46
表 4.2-5. 64-Node模擬實驗數據(Node Failure)。 51
表 4.2-6. 256-Node模擬實驗數據(Node Failure)。 55
表 4.2-7. 16-Node模擬實驗數據(Rack Failure)。 59
表 4.2-8. 64-Node模擬實驗數據(Rack Failure)。 63
表 4.2-9. 256-Node模擬實驗數據(Rack Failure)。 67
表 4.4-1. 不同運算節點下,同一時間所需花費最大儲存空間成本。 73
表 4.4-2. CKP-H與CKP-Q在不同資料量與運算節點下的花費成本。 73
參考文獻 [1] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on large clusters,” Proc. Usenix Symp. Opearting Systems Design &Implementation (OSDI 2004), pp.137-150, Dec. 2004.
[2] Qin Zheng, “Improving MapReduce Fault Tolerance in the Cloud,” IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), pp.1-6, 2010.
[3] SLA, http://en.wikipedia.org/wiki/Service-level_agreement
[4] Tom White, “Hadoop: The Definitive Guide,” 2nd Edition, September 2010.
[5] S.Y. Ko, I. Hoque, B. Cho, and I. Gupta, “On Availability of Intermediate Data in Cloud Computations,” the USENIX Workshop on Hot Topics in Operating Systems (HotOS), 2009.
[6] M. R. Lyu, “Handbook of Software Reliability Engineering,” McGraw-Hill, New York, 1996.
[7] W.-T. Tsai, X. Zhou, Y. Chen, and X. Bai, “On testing and evaluating service-oriented software,” IEEE Computer, vol. 41, no. 8, pp. 40-46, 2008.
[8] M. R. Lyu, “Software Fault Tolerance,” Trends in Software, Wiley, 1995.
[9] Z. Zheng and M. R. Lyu, “A distributed replication strategy evaluation and selection framework for fault tolerant web services,” International Conference on Web Services, (ICWS’08), pp. 145-152, 2008.
[10] S. S. Gokhale and K. S. Trivedi, “Reliability prediction and sensitivity analysis based on software architecture,” The 13th International Symposium on Software Reliability Engineering, (ISSRE’03), pp. 64-78, 2002.
[11] S. M. Yacoub, B. Cukic, and H. H. Ammar, “Scenario-based reliability analysis of component-based software,” The 10th International Symposium on Software Reliability Engineering, (ISSRE’99), pp. 22-31, 1999.
[12] Z. Zheng and M. R. Lyu, “Collaborative reliability prediction for service-oriented systems,” IEEE/ACM 32nd International Conference on Software Engineering (ICSE’10), pp. 35-44, 2010.
[13] Zibin Zheng, Tom Chao Zhou, Michael R. Lyu, and Irwin King, “FTCloud: A Component Ranking Framework for Fault-Tolerant Cloud Applications,” IEEE 21st International Symposium on Software Reliability Engineering (ISSRE), pp.398-407, November 2010.
[14] ’I˜nigo Goiri, Ferran Juli`a, Jordi Guitart, and Jordi Torres, “Checkpoint-based Fault-tolerant Infrastructure for Virtualized Service Providers,” Network Operations and Management Symposium(NOMS), 2010 IEEE, pp.455-462, April 2010.
[15] Jorge-Arnulfo Quian’e-Ruiz, Christoph Pinkel, J‥org Schad, and Jens Dittrich, “RAFTing MapReduce: Fast Recovery on the Raft,” Data Engineering (ICDE), 2011 IEEE 27th International Conference on, pp.589-600, April 2011.
[16] P. C. Chen, Y. L. Su, J. B. Chang, and C. K. Shieh, “Variable-Sized Map and Locality-Aware Reduce on Public-Resource Grids,” Proc. Conference on Grid and Pervasive Computing (GPC 2010), pp.234-243, May 2010.
[17] Shadi Ibrahim, Hai Jin, Lu Lu, Song Wu, Bingsheng He, and Li Qi, “LEEN: Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud,” IEEE Second International Conference on Cloud Computing Technology and Science (CloudCom), pp.17-24, 2010.
[18] D. DeWitt and M. Stonebraker, “MapReduce: A major step backwards,” http://databasecolumn.vertica.com/databaseinnovation/mapreduce-a-major-step-backwards/, 2008.
[19] J. D. DeWitt and J. Gary, “Parallel Database System: The Future of High Performance Database Systems,” Commun. ACM, Vol.35, No.6, pp.85-98, June 1992.
[20] Y. C. Kwon, M. Balazinska, B. Howe, and J. Rolia, “Skew-resistant parallel processing of feature-extracting scientific user-defined functions,” Proc. ACM Symp. Cloud Computing (SOCC 2010), ACM Press, pp.75-86, Jun. 2010.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-09-10公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-09-10起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信