臺灣博碩士論文加值系統

MapReduce雲在現今已經是常見的雲端計算平台。藉由許多遵循MapReduce設計規範的應用程式，MapReduce雲可以利用雲中的高計算能力來處理很多問題。但來源的輸入資料並不完全都一樣，且應用程式可能用不同的邏輯來處理這些輸入資料來產生中間資料。因此，就會造成中間資料分配不均在各台電腦上，而造成中間資料偏斜。當發生中間資料偏斜問題時，有些電腦是空閒，而另一些電腦可能是忙碌，進而造成整體效能嚴重下降。假設我們可以分配出較適合每台電腦的行程數來處理輸入資料與中間資料，就可以避免這些空閒電腦浪費資源。我們這篇論文提出一個以預測中間資料量為基礎之行程數量動態調變策略(Dynamic Task Amount Adjustment Policy，縮寫DTAAP)來改善小規模MapReduce雲之效能。此外，我們也實驗常用的應用程式來實測DTAAP與其兩種對照系統來比較效能。

A MapReduce cloud is a general cloud computing platform nowadays. Through many applications based on the MapReduce design principle, a MapReduce cloud can utilize the high computation power in a cloud to resolve many problems. However, input data is not arranged and distributed averagely and a different application may have a different algorithm to process the input data. As a result, intermediate data may be unaveragely distributed over computations to incur the intermediate data skew. When the intermediate data skew happens to a cloud, the overall performance degrades because some computers are idle, others are busy. If we can allocate a suitable amount of tasks to each computation to process input data and intermediate data, we can avoid wasting computation power in idle computations. In the thesis, we propose a Dynamic Task Amount Adjustment Policy (DTAAP) based on intermediate data quantity prediction in order to improveperformance of a small-scale MapReduce cloud. Besides, we use popular applications to observe performance of DTAAP and compare it with two different MapReduce platforms.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章緒論 1
1.1 介紹 1
第二章背景知識 4
2.1 MapReduce原理 4
2.2 Straggler落後者 7
第三章相關工作 9
第四章Dynamic Task Amount Adjustment Policy(DTAAP) 15
4.1 DTAAP運作概觀 15
4.2 DTAAP之「預測中間資料量演算法」 20
4.3 DTAAP之「行程數量調變演算法」 22
第五章系統實作 26
5.1 MapReduce之系統組成 26
5.2 DTAAP之系統組成 31
第六章實驗與結果呈現 36
6.1實驗設定 36
6.2應用程式Word Count的實驗結果 37
6.3應用程式All Unique Combinations的實驗結果 45
6.4應用程式Inverted Index的實驗結果 53
6.5應用程式Radix Sort的實驗結果 60
6.6應用程式Session Mean Value的實驗結果 67
第七章結論 75
參考文獻 81

[1] J. Dean and S. Ghemawat, "MapReduce: simplified data processing on large clusters," Communications of the ACM - 50th anniversary issue: 1958 - 2008, Vol. 51, Issue 1, 2008, pp. 107-113.
[2] FANYuanquan, WU Weiguo, XUYunlong,CHEN Heng, "Improving MapReduce Performance by Balancing Skewed Loads," Journals of China Communications, Vol.11, Issue8, 2014, pp. 85-108.
[3] Zhuo Tang, Wen Ma, Kenli Li, Keqin Li,"A Data Skew Oriented Reduce Placement Algorithm Based on Sampling," IEEE Transactions on Cloud Computing,Volume: 8, Issue: 4, Oct.-Dec. 2020, pp. 4-14.
[4] Yanfei Guo, Jia Rao, Changjun Jiang, Xiaobo Zhou,"Moving Hadoop into the Cloud with Flexible Slot Management and Speculative Execution," IEEE Transactions on Parallel and Distributed Systems,Volume: 28, Issue: 3, March 2017, pp. 3-14.
[5] 大上丈彥 (2013)，「3小時讀通統計：通往假設檢定之路」，新北市：世茂出版社，第44-76頁。
[6] Qi Chen, Jinyu Yao, and Zhen Xiao, Senior Member,"LIBRA: Lightweight Data Skew Mitigation inMapReduce," IEEE Transactions on Parallel and Distributed Systems,Volume: 26, Issue: 9, Sept. 2015, pp.1-14
[7] Jia-Chun Lin, Ming-Chang Lee, RaminYahyapour, "Scheduling MapReduce Tasks on Virtual MapReduce Clusters from a Tenant’s Perspective," IEEE International Conference on Big Data, Oct. 2014, pp. 1-6.
[8] Zhenhua Guo, Marlon Pierce, Geoffrey Fox, Mo Zhou "Automatic Task Re-organization in MapReduce," IEEE International Conference on Cluster Computing, Sept. 2011, pp. 1-9.
[9] Peng Lu, Young Choon Lee, Vincent Gramoli, Luke M. Leslie, Albert Y. Zomaya, "Local Resource Shaper for MapReduce," IEEE 6th International Conference on Cloud Computing Technology and Science, Dec. 2014, pp. 1-8.
[10] Qi Zhang, Mohamed FatenZhani, YukeYang;RaoufBoutaba, Bernard Wong, "PRISM: Fine-Grained Resource-Aware Scheduling for MapReduce," IEEE Transactions on Cloud Computing,Volume: 3, Issue: 2, April-June 2015, pp. 2-13
[11] D C Vinutha, G T Raju,"Node Performance Load Balancing Algorithm for Hadoop Cluster," 2019 International Conference on Intelligent Sustainable Systems, 21-22 Feb. 2019, pp. 1-6.