[發明專利]一種Internet環境下MapReduce計算方法

無效

• 申請號: 201310026425.5
• 申請日: 2013-01-24
• 公開（公告）號: CN103116525A
• 公開（公告）日: 2013-05-22
• 發明（設計）人: 賀海武;唐兵
• 申請（專利權）人: 賀海武;唐兵
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于分布式計算模型領域，具體涉及Internet環境下一種新的MapReduce計算方法及系統，以及系統中的Map和Reduce任務調度方法。

背景技術

繼高性能集群計算﹑網格計算之后，在大規模計算領域，云計算正受到人們的強烈關注。作為云計算的核心技術，MapReduce也受到了廣泛關注。MapReduce是Google在2004年提出來的一種處理大規模數據集的并行編程模型，以此來簡化分布式系統的編程。應用程序編寫人員只需將精力放在應用程序本身，而關于集群的處理問題，包括可靠性、可擴展性、任務并行化、數據分布存儲、負載均衡、節點通信等復雜過程被屏蔽，用戶不需要關心如何將輸入的數據分塊，分配和調度。這使得那些沒有多少并行計算經驗的程序員也可以開發并行應用來處理和分析海量數據。

MapReduce系統通過Map（映射）和Reduce（化簡）這樣兩個簡單的概念來構成運算基本單元。用戶只需編寫Map函數和Reduce函數即可實現對大規模海量數據集的并行處理。MapReduce系統可以根據輸入數據的大小及作業的配置等信息，自動將該作業初始化為多個相同的Map任務和Reduce任務，分別讀取不同的輸入數據塊并調用Map函數和Reduce函數進行處理。在Map函數中指定對各分塊數據的處理過程，在Reduce函數中指定如何對分塊數據處理的中間結果進行化簡。映射-化簡過程如下：

映射（Map）過程：????Map(key1,value1)?---->?list(key2,value2)

化簡（Reduce）過程：?Reduce(key2,list(value2))?---->?list(value3)

此外，在Reduce過程之前，一般還包括排序（Sort）過程和合并（Merge）過程。

如圖1所示，在Map階段，Map任務讀取一個輸入（key1,value1）對，由程序員定義的Map函數對其處理產生一個中間（key2,value2）結果集，并保存在本地。在Reduce階段，Reduce任務從所有執行Map任務的節點讀取中間關鍵字key2和相關的一個value2集，由程序員定義的Reduce函數對其進行處理，并得到計算結果。

在現有技術中，MapReduce系統通常和分布式文件系統相耦合，如Yahoo提出的Hadoop是一種基于Java的MapReduce開源實現，實現了一個分布式文件系統HDFS（Hadoop?Distributed?File?System）和MapReduce任務調度框架，大數據經過分片，存儲在由工作節點（Worker）所組成的分布式文件系統中。Hadoop通常部署在高可靠集群環境下，用戶通過Master提交作業；Master進行任務調度，同時接收Worker的狀態匯報；Worker執行Map任務或Reduce任務；Map任務從分布式文件系統讀數據分片，執行任務，最后在本地寫中間結果；Reduce任務讀Map輸出的中間結果，執行任務，最后在分布式文件系統上寫輸出數據。

另一方面，自上世紀九十年代以來，人們目睹了志愿計算的強大計算能力。目前，志愿計算也吸引了越來越多的關注。志愿計算是通過互聯網讓全球的普通大眾自愿捐獻個人PC空閑的CPU周期，參與科學計算或數據分析的一種計算方式，實現分散的志愿資源的集成。這種方式為解決基礎科學運算規模較大、計算資源需求較多的難題提供了一種行之有效的解決途徑。它將許多單獨的計算機連接在一起，從而建立一個具有海量計算能力的大系統，這種系統遠遠超過幾臺超級計算機的能力。

在生物信息學﹑高能物理﹑氣候預測等多個領域已開始使用這一模式來解決大規模的科學計算問題。最著名的BOINC（伯克利開放網絡計算平臺）提供了一個志愿計算運行環境。目前全球最大的志愿計算項目SETIhome就運行在BOINC平臺上。該項目注冊用戶達200多萬，活躍用戶有20多萬，24小時的平均吞吐量達到了驚人的7?PetaFLOPS。此外知名的志愿計算項目還包括FOLDINGhome﹑LHChome﹑Einsteinhome﹑IBM?World?Community?Grid﹑ClimatePrediction.net等。