在Hadoop分散式運算架構底下，根據系統所使用排程策略的不同，將會直接影響到整體的系統效能。Hadoop架構中系統所預設的排程策略為先進先出(FIFO)，但先進先出排程策略並沒有考慮到不同任務間可能會需要相同的檔案，或是檔案過大時使用網路傳輸檔案導致系統效能降低的影響。本研究提出了FSSL排程策略，以先進先出排程策略為基礎，再加上考慮需求共享與區域感知的因素並在演算法中加入所需要的調整參數，並以此演算法制定新的排程策略進行任務排程以減少網路的負載。實驗結果顯示，我們所提出的FSSL排程策略相較於FIFO排程策略，在多數任務擁有相同需求檔案或是需求檔案較大的執行環境下能夠進一步地改善系統效能，平均系統效能的改善比率約為65%。

Using different scheduling polices can affect the system performance in Hadoop architecture. In Hadoop architecture, the default scheduling policy is First-In-First-Out (FIFO). However, the FIFO scheduler simply schedule jobs according to their arrival time and does not consider any other factors that may have great impact on system performance. As a result, using FIFO cannot achieve good enough performance in Hadoop.
In this paper, we propose a novel scheduling algorithm, called FSSL (FIFO with Shared-Scan and Locality-aware). FSSL is a scheduling policy based on FIFO and take locality of required data and data sharing probability between jobs into account. Such that the jobs which need the same data can be gathered and easily batch processed, and thus reduce the overhead of transferring data between data nodes and computations nodes. The results show that FSSL scheduling polity can improve system performance about 65% compared to FIFO scheduling policy.

目錄
目錄	III
圖目錄	V
表目錄	VI
1	緒論	1
1.1	研究背景與動機	1
1.2	研究目的	2
2	文獻探討	4
2.1	分散式運算	4
2.1.1	MapReduce	4
2.1.2	Hadoop	5
2.2	效能改善	6
2.2.1	Blocking Operators	6
2.2.2	I/O最佳化	7
2.2.3	排程系統	8
2.3	排程策略探討	9
2.3.1	Shared-scan	9
2.3.2	Location-aware	10
3	FSSL排程系統策略與流程	11
3.1	任務資訊的計算	11
3.1.1	檔案傳輸時間	12
3.1.2	預估任務數量	13
3.1.3	判斷是否需要等待	14
3.1.4	計算等待時間限制	15
3.2	任務進入系統	16
3.3	系統有機器閒置	18
4	實驗	22
4.1	實驗設計	22
4.2	效能評估標準	22
4.3	排程模擬系統架構	23
4.4	排程模擬系統簡介	23
4.4.1	機房設定及檔案放置系統	23
4.4.2	測試任務產生系統	24
4.4.3	排程系統	25
4.5	資料集	27
4.5.1	檔案資料集	27
4.5.2	機房資料集	27
4.5.3	任務資料集	29
4.6	實驗環境	30
4.7	實驗結果	30
4.7.1	任務數量	31
4.7.2	任務到達率	32
4.7.3	平均檔案大小	34
4.7.4	資料共用可能性	35
4.7.5	任務在本機執行的比率(Locality-ratio)	37
5	結論	40
5.1	結論	40
5.2	未來展望	40
6	參考文獻	42
附錄一 判斷是否需要等待的算式推導過程	44
附錄二 計算等待時間最適值的算式推導過程	45
 
圖目錄
圖 1 MapReduce架構圖	5
圖 2 HDFS架構圖	6
圖 3 排程系統架構	9
圖 4 佇列示意圖	11
圖 5 任務進到系統流程圖	18
圖 6 系統機器閒置流程圖	20
圖 7 排程模擬系統運作流程圖	23
圖 8 機房設定及檔案放置系統使用者介面	24
圖 9 測試任務產生系統使用者介面	25
圖 10 排程模擬系統使用者介面	26
圖 11不同的任務數量模擬排程結果	31
圖 12不同的任務數量效能改善比率	32
圖 13不同任務到達率模擬排程結果	33
圖 14不同任務到達率效能改善比率	33
圖 15不同平均檔案大小模擬排程結果	34
圖 16不同平均檔案大小效能改善比率	35
圖 17不同平均資料共用可能性模擬排程結果	36
圖 18不同平均資料共用可能性效能改善比率	36
圖 19不同任務數量的Locality-ratio	37
圖 20不同任務到達率的Locality-ratio	38
圖 21不同平均檔案大小的Locality-ratio	38
圖 22不同平均資料共用可能性的Locality-ratio	39

表目錄
表 1 符號對照表一	12
表 2 符號對照表二	16
表 3 任務進入系統時的演算法	17
表 4 系統有機器閒置時的演算法	19
表 5 機房資料集範例	28
表 6 任務資料集範例	29

[1]	Agrawal, P., Kifer, D., & Olston, C. (2008). Scheduling shared scans of large data files. Proceedings of the VLDB Endowment, 1(1), 958-969.
[2]	Apache hadoop NextGen MapReduce (YARN). Retrieved, 2013, from http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yarn-site/YARN.html
[3]	Chen, T., Wei, H., Wei, M., Chen, Y., Hsu, T., & Shih, W. (2013). LaSA: A locality-aware scheduling algorithm for hadoop-MapReduce resource assignment. Paper presented at the Collaboration Technologies and Systems (CTS), 2013 International Conference on, 342-346.
[4]	Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1), 107-113.
[5]	Kozuch, M. A., Ryan, M. P., Gass, R., Schlosser, S. W., O'Hallaron, D., Cipar, J., . . . Ganger, G. R. (2009). Tashi: Location-aware cluster management. Paper presented at the Proceedings of the 1st Workshop on Automated Control for Datacenters and Clouds, 43-48.
[6]	Lee, K., Lee, Y., Choi, H., Chung, Y. D., & Moon, B. (2012). Parallel data processing with MapReduce: A survey. AcM sIGMoD Record, 40(4), 11-20.
[7]	Welcome to apache™ hadoopR!. Retrieved, 2013, from http://hadoop.apache.org/
[8]	Zaharia, M., Borthakur, D., Sen Sarma, J., Elmeleegy, K., Shenker, S., & Stoica, I. (2010). Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling. Paper presented at theProceedings of the 5th European Conference on Computer Systems, 265-278.
[9]	Zaharia, M. (2009). Hadoop Fair Scheduler Design Document,
[10]	Condie, T., Conway, N., Alvaro, P., Hellerstein, J. M., Elmeleegy, K., & Sears, R. (2010). MapReduce online. Paper presented at the Nsdi, , 10(4) 20.
[11]	Jiang, D., Ooi, B. C., Shi, L., & Wu, S. (2010). The performance of MapReduce: An in-depth study. Proceedings of the VLDB Endowment, 3(1-2), 472-483.
[12]	Li, B., Mazur, E., Diao, Y., McGregor, A., & Shenoy, P. (2011). A platform for scalable one-pass analytics using MapReduce. Paper presented at the Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 985-996.
[13]	Dittrich, J., Quiane-Ruiz, J., Jindal, A., Kargin, Y., Setty, V., & Schad, J. (2010). Hadoop++ : Making a yellow elephant run like a cheetah (without it even noticing). Proceedings of the VLDB Endowment, 3(1-2), 515-529.
[14]	Floratou, A., Patel, J. M., Shekita, E. J., & Tata, S. (2011). Column-oriented storage techniques for MapReduce. Proceedings of the VLDB Endowment, 4(7), 419-429.
[15]	Pavlo, A., Paulson, E., Rasin, A., Abadi, D. J., DeWitt, D. J., Madden, S., & Stonebraker, M. (2009). A comparison of approaches to large-scale data analysis. Paper presented at the Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, 165-178.
[16]	Dean, J., & Ghemawat, S. (2010). MapReduce: A flexible data processing tool. Communications of the ACM, 53(1), 72-77.
[17]	Lang, W., & Patel, J. M. (2010). Energy management for mapreduce clusters. Proceedings of the VLDB Endowment, 3(1-2), 129-139.