3.4　云計算中的編程模型

3.4.1　分布式計算

3.4.1.1　分布式計算的概念

分布式計算是一門計算機科學，研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，并由許多相互獨立的計算機進行協同處理，以得到最終結果。分布式計算讓幾個物理上獨立的組件作為一個單獨的系統協同工作，這些組件可能指多個CPU，或者網絡中的多臺計算機。它做了如下假定：如果一臺計算機能夠在5秒鐘內完成一項任務，那么5臺計算機以并行方式協同工作時就能在1秒鐘內完成。實際上，由于協同設計的復雜性，分布式計算并不能都能滿足這一假設。對于分布式編程而言，核心的問題是如何把一個大的應用程序分解成若干可以并行處理的子程序。有兩種可能的處理方法：一種是分割計算，即把應用程序的功能分割成若干個模塊，由網絡上多臺機器協同完成；另一種是分割數據，即把數據集分割成小塊，由網絡上的多臺計算機分別計算。對于海量數據分析等數據密集型問題，通常采取分割數據的分布式計算方法，對于大規模分布式系統則可能同時采取這兩種方法。

3.4.1.2　分布式計算的基本原理

大量分布式系統通常會面臨如何把應用程序分割成若干個可并行處理的功能模塊，并解決各功能模塊間協同工作的問題。這類系統可能采用以C/S結構為基礎的三層或多層分布式對象體系結構，把表示邏輯、業務邏輯和數據邏輯分布在不同的機器上，也可能采用Web體系結構。基于C/S架構的分布式系統可借助CORBA、EJB、DCOM等中間件技術解決個模塊間的協同工作問題。基于Web體系架構或稱為Web Service的分布式系統，則通過基于標準的Internet協議支持不同平臺和不同應用程序的通信。Web Service是未來分布式體系架構的發展趨勢。對于數據密集型問題，可以采用分割數據的分布式計算模型，把需要進行大量計算的數據分割成小塊，由網絡上的多臺計算機分別計算，然后對結果進行組合得出數據結論。Map-reduce是分割數據型分布式計算模型的典范，在云計算領域被廣泛采用。

3.4.2　并行編程模型

為了使用戶能更輕松地享受云計算帶來的服務，讓用戶能利用編程模型編寫簡單的程序來實現特定的目的，云計算上的編程模型必須十分簡單，必須保證后臺復雜的并行執行和任務調度向用戶和編程人員透明。

云計算大部分采用Map-reduce的編程模型。現在大部分IT廠商提出的“云”計劃中采用的編程模型，都是基于Map-reduce的思想開發的編程工具。Map-reduce不僅僅是一種編程模型，同時也是一種高效的任務調度模型。Map-reduce這種編程模型不僅適用于云計算，在多核和多處理器、cell processor以及異構機群上同樣有良好的性能。該編程模型僅適用于編寫任務內部松耦合、能夠高度并行化的程序。如何改進該編程模型，使程序員能夠輕松地編寫緊耦合的程序，運行時能高效地調度和執行任務，是Map-reduce編程模型未來的發展方向。

3.4.2.1　何謂Map-reduce

Map-reduce是Google開發的Java、Python、C++編程模型，它是一種簡化的分布式編程模型和高效的任務調度模型，用于大規模數據集（大于1TB）的并行計算。嚴格的編程模型使云計算環境下的編程十分簡單。Map-reduce模型的思想是將要執行的問題分解成Map（映射）和Reduce（歸約）的方式，先通過Map程序將數據切割成不相關的區塊，分配（調度）給大量計算機處理，達到分布式運算的效果，再通過Reduce程序將結果匯總輸出。

Map-reduce是一種分布式編程模型，它以數據為中心，把數據分割成小塊供網絡上的多臺計算機分別計算，而后對計算結果進行匯總得出最終結論。Map-reduce提供了泛函編程的一個簡化版本，與傳統編程模型中函數參數只能代表明確的一個數或數的集合不同，泛函編程模型中函數參數能夠代表一個函數，這使得泛函編程模型的表達能力和抽象能力更高。在Map-reduce模型中，輸入數據和輸出結果都被視作有一系列key/value對組成的集合，對數據的處理過程，就是Map和Reduce過程，Map過程將一組key/value映射成另一組key/value，Reduce是一個歸約過程，把具有相同key的value值合并在一起。Map-reduce模型簡單，并能滿足絕大多數網絡數據分析工作，因此被Google、Hadoop等云計算平臺廣泛采用。基于Map-reduce的分布式系統隱藏了并行化、容錯、數據分布、負載均衡等復雜的分布式處理細節，提供簡單有力的接口來實現自動的并行化和大規模分布式計算，從而在大量普通PC上實現高性能計算。在這些系統里，用戶指定map函數對輸入的key/value集進行處理，形成中間形式的key/value集；系統按照key值把中間形式的value集中起來，傳給用戶指定的reduce函數；reduce函數把具有相同key的value值合并在一起，最終輸出一系列的key/value對作為結果。

3.4.2.2　為什么需要Map-reduce

Map-reduce是最早由Google提出的一項分布式編程模型，用以進行大數據量的計算。它借鑒了Lisp等函數編程語言的思想，把對數據的處理歸結為映射map和歸約reduce兩個操作。Google最初將其應用在內部海量的Web頁面索引上，在效率和健壯性上取得了極大的成功。實際上，Map-reduce是一種簡化的并行計算編程模型，這對開發人員而言具有重要的意義。隨著互聯網數據的急劇增長，開發人員面臨越來越多的大數據量計算問題，處理這類問題的主要方法是并行計算，然而并行計算是一個相對復雜的技術，不易掌握。Map-reduce的出現降低了并行應用開發的入門門檻，它隱藏了并行化、容錯、數據分布、負載均衡等復雜的分布式處理細節，使得開發人員可以專注于程序邏輯的編寫。Map-reduce使并行計算得以廣泛應用，是云計算的一項重要技術。

3.4.2.3　Map-reduce的執行

Map-reduce是一種處理和產生大規模數據集的編程模型，程序員在map函數中指定對各分塊數據的處理過程，在reduce函數中指定如何對分塊數據處理的中間結果進行歸約。用戶只需要指定map和reduce函數來編寫分布式的并行程序。當在集群上運行Map-reduce程序時，程序員不需要關心如何將輸入的數據分塊、分配和調度，同時系統還將處理集群內節點失敗以及節點間通信的管理等。圖3-6給出了一個Map-reduce程序的具體執行過程。

從圖3-6可以看出，執行一個Map-reduce程序需要5個步驟：輸入文件、將文件分配給多個工作機并行地執行、寫中間文件（本地寫）、多個Reduce工作機同時運行、輸出最終結果。本地寫中間文件在減少了對網絡帶寬壓力的同時減少了寫中間文件的時間耗費。執行Reduce時，根據從Master獲得的中間文件位置信息，Reduce使用遠程過程調用，從中間文件所在節點讀取所需的數據。Map-reduce模型具有很強的容錯性，當工作機節點出現錯誤時，只需將該工作機節點屏蔽在系統外等待修復，并將該工作機上執行的程序遷移到其他工作機上重新執行，同時將該遷移信息通過Master發送給需要該節點處理結果的節點。Map-reduce使用檢查點的方式來處理Master出錯失敗的問題，當Master出現錯誤時，可以根據最近的一個檢查點重新選擇一個節點作為Master并由此檢查點位置繼續運行。

Map-reduce僅為編程模型的一種，微軟提出的DryadLINQ是另外一種并行編程模型，但它局限于.NET的UNG系統的同時并不開源，這限制了它的發展前景。

Map-reduce作為一種較為流行的云計算編程模型，在云計算系統中應用廣闊。但是基于它的開發工具Hadoop并不完善。特別是其調度算法過于簡單，判斷需要進行推測執行的任務的算法造成過多任務需要推測執行，降低了整個系統的性能。改進Map-reduce的開發工具，包括任務調度器、底層數據存儲系統、輸入數據切分、監控“云”系統等方面是將來一段時間的主要發展方向。