[發明專利]一種MapReduce系統中的數據采樣和劃分方法

有效

• 申請號: 201210205841.7
• 申請日: 2012-06-18
• 公開（公告）號: CN102799486A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 姚金宇;陳琪;肖臻
• 申請（專利權）人: 北京大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;H04L29/08
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 余長江

技術領域

本發明涉及分布式計算框架MapReduce系統中的數據采樣和劃分方法，屬于計算機應用技術領域。

背景技術

云計算是當前工業界和學術界關注的熱點，它改變了傳統上由用戶提供和維護計算資源的模式，改由云計算廠商集中化管理計算資源，用戶可以根據不同的應用場景，按需獲取相應的資源。如何利用資源集中化帶來的并行性、容錯性等特性，高效的提供云計算服務，成為了云計算模式最重要的研究問題之一。

MapReduce分布式計算框架是Google公司提出的軟件架構，借鑒了函數式編程的思想，高效地進行大規模數據集的分布式計算。MapReduce框架以其優異的容錯性、計算的高效性和使用的便捷性，迅速成為云計算環境下應用最廣泛的分布式計算架構。尤其是2005年Apache?Software?Foundation引入基于MapReduce框架開發的Hadoop開源系統以來，MapReduce架構得到了更大的發展，利用MapReduce思想構建的分布式計算系統已經被Google、微軟、Facebook、Yahoo!以及國內的騰訊、百度、阿里云等軟件公司和互聯網公司在各自的私有云集群中深度采用，并且也成為了當前部署云計算集群進行分布式計算的首選軟件架構，在科學計算、人工智能、數據挖掘、信息處理等各個領域都得到了廣泛的應用。

MapReduce框架將一個計算任務劃分成若干個Map任務和Reduce任務。首先，輸入數據集通過Map任務，映射成為若干（Key，Value）二元組。然后，鍵值Key相同的二元組被集中起來傳輸給Reduce任務，并處理成最終的輸出數據。MapReduce任務通過將數據分塊并行化實現了高效并行；并且計算節點周期性報告計算進度，保證了可靠性和容錯性。大量的實際應用都可以很方便地轉化成MapReduce模式并行執行。

在上述處理過程中，處理Map任務大多數情況下可以實現高度并行化；但Reduce任務受到相同鍵值Key的二元組數目的制約（MapReduce原始架構要求同一個鍵值的二元組必須在同一個Reduce計算節點上完成），在輸入數據中即包含某一些鍵值的二元組數量特別大的時候，并行度會受到影響。當前最常用的Reduce負載均衡的算法是采用Hash劃分（Hadoop?MapReduce中的默認方法就是Hash劃分），即鍵值的Hash值（取模后）相同的所有二元組分配給同一個Reduce任務執行。在真實應用環境下，由于本身存在嚴重的數據傾斜（Data?Skew），例如英文單詞的分布、互聯網網頁的訪問量分布、經濟學中帕累托法則的數據分布等，這種盲目的負載均衡方法都會造成Reduce負載分布不均，使得整個任務執行效率很低。如果能夠在MapReduce任務執行的過程中估測數據的分布，進而實現更加精準的Reduce負載均衡策略，無疑會很大程度上提高MapReduce任務的執行效率，從而對云計算服務的提供者和使用者都帶來很大的好處。

發明內容

鑒于現有技術存在的不足，本發明提供了一種MapReduce系統中的實時數據采樣、分布估測和區間劃分方法，能夠在MapReduce任務執行過程中對輸入數據的分布進行預測，進而實現Reduce任務負載均衡，使得整個系統效率得到較大提升。

為了實現上述目的，本發明采用的技術方案概述如下：

一種在MapReduce系統中的數據采樣和劃分方法，其步驟包括：

1）客戶端向MapReduce系統中提交任務請求，所述MapReduce系統中的主控節點將Map任務劃分成采樣和普通任務，所述主控節點Master將采樣任務優先下發到各個分節點Worker進行執行；

2）根據各個分節點Worker上的Map采樣任務篩選出樣本集合，并將樣本上傳至主控節點Master進行合并；

3）所述主控節點Master根據Map采樣任務結果得到Reduce任務工作量，對Reduce任務劃分鍵值區間，實現負載均衡，完成采樣和劃分。

鍵值區間的劃分方法是:

2-1)在合并的樣本集合中，篩選出包含二元組最多的樣本鍵值，以此劃分初步鍵值域；

2-2）根據每一個鍵值區間中其它樣本鍵值的個數，按樣本的鍵值落在每個區間的比例將收集總鍵值數K_tot和收集總二元組數R_tot分配到每一個區間，得到待計算的二元組在鍵值域上分布；