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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2507201420593700
中文論文名稱 在Hadoop架構中需求共享及區域感知的排程研究
英文論文名稱 Shared-scan and Locality-aware Scheduling Algorithm in Hadoop Architecture
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 102
學期 2
出版年 103
研究生中文姓名 許哲瑋
研究生英文姓名 Che-Wei Hsu
學號 600631088
學位類別 碩士
語文別 中文
口試日期 2014-06-21
論文頁數 45頁
口試委員 指導教授-衛信文
委員-呂政修
委員-蘇維宗
中文關鍵字 MapReduce  Shared-scan  Location-aware  Scheduling  Hadoop 
英文關鍵字 MapReduce  Shared-scan  Location-aware  Scheduling  Hadoop 
學科別分類
中文摘要 在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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-08-05公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-08-05起公開。


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