在眾多雲端技術中，MapReduce是Google在雲端技術上所提供出來使用在許多高運算、高儲存量的資料上的一個處理機制。MapReduce所提供的Map和Reduce兩個function，可以讓使用者輕易的將待處理的大量資料自動的完成。因此再藉由Hadoop依據 MapReduce這個架構將概念變成實際的產物，就可以方便使用者來使用。
目前Hadoop的應用絕大部分都還是用在複雜度較低且運算密度較高的程序上如搜尋(Sort)、資料統計等等。
在先前的文獻研究中，有許多是針對改善MapReduce效率這部份的研究，其中有針對於Reduce function的演算法提出了Dynamic Switch of Reduce Function (DSRF)Algorithm的改善方案，因此減少了Reduce function的閒置時間，但此排程機制會因為系統的負載數量增加到一定數量以上的時候，因為切換的頻率過多，反而造成系統效能的降低,甚至無法達到原本Hadoop MapReduce所提供出來的效能品質。本論文研究提出透過一個斜率公式的計算來提供預測系統效能最大工作負載量的方法，因此可以提前增加伺服器的數量，藉此避免系統因負載過多後造成效率的降低。

Among the many cloud technologies, MapReduce is provided by Google that is technically out of use in many high computing, high data storage capacity on a handling mechanism in the cloud system. MapReduce provided Map and Reduce two function, allows the user to easily handle large amounts of data will be done automatically. So then based on Hadoop MapReduce by this architecture will become the actual concept of the product, the user can easily use.
Currently Hadoop applications are still used in the vast majority of low complexity and high density computing procedures such as search (Sort), statistics and so on.
In previous studies in the literature, many of which are aimed at improving the efficiency of this part of MapReduce. Reduce function for which the algorithm proposed in a Dynamic Switch of Reduce Function (DSRF) Algorithm improvement plan, thus reducing the Reduce function of idle time. However, this scheduling mechanism because the system load increased to more than a certain amount of time. Because excessive switching frequency, but cause system performance degradation. Can not even reach out Hadoop MapReduce provide quality performance. This thesis put forward by a slope formula calculation to predict system performance to provide maximum working load approach. So you can increase the number of servers in advance, thereby avoiding excessive system due to the load, resulting in reduced efficiency.

第一章	緒論	1
1.1	前言	1
1.2	研究動機與目的	4
1.3	論文章節架構	4
第二章	背景知識與相關研究	6
2.1	MapReduce的介紹	6
2.1.1	Map function	6
2.1.2	Reduce function	7
2.1.3	Master端	7
2.1.4	Google file system	7
2.2	Hadoop MapReduce介紹	10
2.3	DSRF介紹	12
2.3.1	DSRF Algorithm	12
2.3.2	DSRF MapReduce	12
第三章	預測機制的研究	17
3.1	系統問題的說明	19
3.2	解決方法及預測機制的研究	19
2.3.1	動態偵測並預測系統負載量的機制	19
2.3.2	機率公式的介紹	28
2.3.2	機率比例参數的介紹	29
第四章	數據分析與比較	31
4.1	斜率分析的結果	31
4.2	機率参數的分析結果	36
第五章  結論與未來展望	38
参考文獻	40

圖1.1  DSRF in Hadroop MapReduce架構圖	3
圖2.1  MapReduce架構圖	9
圖2.2  Hadoop MapReduce架構圖	11
圖2.3  傳統使用FIFO架構圖	14
圖2.4  使用DSRF架構圖	16
圖3.1  系統負載量對平均運算時間的影響	18
圖3.2  負載量61時所預測系統最大負載量的示意圖	20
圖3.3  負載量62時所預測系統最大負載量的示意圖	21
圖3.4  負載量63時所預測系統最大負載量的示意圖	22
圖3.5  負載量64時所預測系統最大負載量的示意圖	23
圖3.6  負載量65時所預測系統最大負載量的示意圖	24
圖3.7  負載量66時所預測系統最大負載量的示意圖	25
圖3.8  負載量67時所預測系統最大負載量的示意圖	26
圖3.9  負載量68時所預測系統最大負載量的示意圖	27

表4.1  負載量與系統運行時間	32
表4.2  各負載量間的斜率與所預測的最大負載量	35
表4.3  負載量與p值的運算結果	37

[1]NovQinlu He,Zhanhuai Li’Xiao Zhang, “Study on Cloud Storage System based on Distributed Storage Systems”, Computational and Information Sciences( ICCIS), 17-19 Dec 2010, pp. 1332 - 1335 
[2]Kevin D.Bowers,Ari Juels, and Alina Oprea., “HAIL: A HighAvailability and Integrity Layer for Cloud Storage”, Computer and communications security (CCS), Nov 2009, pp. 187-198 
[3]Mingyue Luo,Gang Liu, “Distributed log information processing with Map-Reduce: A case study from raw data to final models”, Information Theory and Information Security(ICITIS), 17-19 Dec. 2010, pp.1143-1146 
[4]Afrati, Foto N. Ullman, Jeffrey D., “Optimizing Multiway Joins in a Map-Reduce Environment”, IEEE Transactions on Knowledge and Data Engineering, vol. 23, Issue. 9, Sept. 2011, pp. 1282-1298 
[5]Chen Zhang ,De Sterck, H.,”CloudBATCH: A Batch Job Queuing System on Clouds with Hadoop and HBase”, Cloud Computing Technology and Science (CloudCom), Nov. 30 2010-Dec. 3 2010, pp. 368-375
[6]Jorda Polo, David Carrera, Yolanda Becerra, Malgorzata Steinder, and Ian Whalley., “Performance-driven task co-scheduling for mapreduce environments”,Network Operations and Management Symposium (NOMS) , 19-23 Apr 2010, pp.373 –380
[7]Thomas Sandholm and Kevin Lai., “Dynamic proportional share scheduling in hadoop”, Job Scheduling Stragies For Parallel Processing (JSSPP), vol. 6253, 2010, pp. 110-131
[8]郭玲裳,“基於MapReduce的影像處理系統加入DSRF優先排程機制,”淡江大學電機工程學系碩士論文,中華民國一百零一年六月. 
[9]Jeffrey Dean, Sanjay Ghemawat, “MapReduce:Simplied Data Processing on Large Clusters” Google, Inc.
[10]Apache Software Foundation, Hadoop on demand. URL:http://hadoop.apache.org/core/docs/r0.20.0/hod_user_guide.html