[發明專利]簡化并行計算系統中的傳輸的系統與方法

有效

• 申請號: 201010104978.4
• 申請日: 2010-01-29
• 公開（公告）號: CN102141995A
• 公開（公告）日: 2011-08-03
• 發明（設計）人: 趙邑新;林海波;向哲;溫嘉佳
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市中咨律師事務所 11247
• 代理人: 于靜;周良玉

技術領域

本發明涉及分布式并行計算系統，更具體而言，涉及分布式并行計算系統中傳輸的簡化。

背景技術

信息技術的發展為人們提供了越來越豐富和強大的應用和服務，同時也對處理設備的運算能力提出了越來越高的要求。盡管處理器的運行速度也在不斷提高，但是面對海量信息和數據，分布式并行計算成為一種實用的解決方式。

例如，在各種統計方法中都會涉及海量數據的處理。網頁排名是一項基本的也是廣泛采用的方法，用來評價網站或特定內容的狀態。詞頻統計是示出人們關心的熱門話題的另一個例子。此外，各種智能分析，包括用戶行為分析、關系分析、推薦系統以及內容定制等等，都是基于大量的數據和信息。在以上這些例子中，處理系統的輸入通常是一系列文件，例如web日志文件，其輸出是從這些輸入中提取出來的信息。對于商業網站來說，一天之中產生的日志文件就會超過1T字節(1000G)。這樣的數據量幾乎不可能通過傳統方式進行處理。

為了進行大量數據的處理，提出了分布式并行計算，將一個處理任務分散到多個處理器中同時并行執行。目前，已經存在多種大規模并行計算的執行方式，其中最為重要和常用的是Google提出的MapReduce模型和Microsoft提出的Dryad模型。

MapReduce是一種簡潔的并行計算模型，其名字源于這個模型中的兩項核心操作：映射(Map)和規約(Reduce)，這兩個概念來自于函數式編程語言(Function?Programming)。簡單地說，Map是把一組數據一對一地映射為另外的一組數據，其映射的規則由用戶定義的一個函數來指定。Reduce是根據用戶定義的函數對一組數據進行合并和規約。在Map過程中，我們將數據并行，也就是將數據分開，而Reduce則把分開的數據合到了一起。換句話說，Map是一個分的過程，Reduce則對應著合，利用這一分一合，就可以將一個復雜龐大的任務分拆成許多個作業并行執行運算，然后對并行運算的結果進行綜合，從而得到期望的結果。

圖1示出現有技術MapReduce模型的基本架構的示意圖。在圖1所示的映射規約模型中，每個映射單元從對應的數據源讀取鍵值(key，value)對形式的輸入數據，根據用戶定義的函數，將輸入鍵值對映射為一組新的鍵值對，即圖1中包含鍵1，鍵2，鍵3的鍵值對，稱為中間鍵值對。映射單元通常將產生的中間鍵值對存儲在其本地。之后，在規約階段，將具有相同鍵的中間鍵值對發往相同的規約單元，由規約單元對結果進行綜合。

下面結合一個例子說明映射和規約的過程。在這個例子中，需要完成的任務是在一個文檔集合中統計每個單詞出現的次數。對于這樣的任務，可以將文檔集合中的每個文檔分配給一個映射單元。映射操作的輸入是鍵值對形式的每一篇文檔，映射內容可以是將輸入文檔中每一個單詞的出現輸出到中間文件中去。更具體地，可以如下設置輸入鍵值對，其中鍵(key)對應于文檔名稱，值(value)對應于文檔內容。進一步地，可以將映射函數定義為，對于值中的每個單詞w，產生中間鍵值對(w，1)。基于此，如果某篇文檔的內容是：“hello?beijing，hello?world”，那么得到的中間鍵值對就是(hello，1)，(beijing，1)，(hello，1)，(world?1)。之后，在規約階段，規約單元對單詞和出現次數的序列進行處理和綜合，得到最后的統計結果：(hello，2)，(beijing，1)，(world，1)。

與MapReduce相似，Dryad模型同樣將一項任務分散到多個處理單元中進行運算。圖2示出現有技術Dryad模型的基本架構的示意圖。如圖所示，輸入文檔被分散到多個計算單元，經過多個階段的層層分拆，以及反向地層層合并，得到最后的處理結果。與圖1的MapReduce模型相比，兩者最大的不同在于，MapReduce模型是典型的兩階段處理過程，即映射階段與規約階段，而Dryad作業構建的執行流程圖包含多個處理階段。