[發明專利]一種基于Spark的抗偏斜的數據分片方法

有效

• 申請號: 201810584637.8
• 申請日: 2018-06-08
• 公開（公告）號: CN108776698B
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 唐卓;呂葳;李肯立;李克勤;付仲明;肖偉
• 申請（專利權）人: 湖南大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 長沙市融智專利事務所(普通合伙) 43114
• 代理人: 龔燕妮

本發明公開了一種基于Spark的抗偏斜的數據分片方法，包括：步驟A：獲取預估的中間數據的鍵簇分布以及Spark應用類型，再基于獲取的鍵簇分布生成與Spark應用類型相匹配的分片策略；鍵簇為鍵相同的鍵值對集合，分片策略包括分別與無需排序、需排序的應用類型相對應的基于鍵簇重分配的哈希算法策略和基于鍵簇分割的范圍分片算法策略；步驟B：利用生成的分片策略計算出Map輸出數據中每個鍵值對的reduce索引號，再基于reduce索引號的大小順序將鍵值對依次寫入中間數據文件中。通過上述方法解決了Spark本身的抗偏斜機制問題，解決現有的Hash方法和Range方法無法處理分片偏斜的問題。

技術領域

本發明屬于數據引擎技術領域，具體涉及一種基于Spark的抗偏斜的數據分片方法。

背景技術

作為一個快速的大數據處理通用引擎，Spark可以將大規模的數據切分成多個分片并且在集群中的多臺機器分發運行任務來處理這些數據。Spark強大的計算能力得益于它先進的DAG運算引擎，其支持異步的數據流動和內存計算能力。

Shuffle是劃分DAG圖中stage的依據，它是Spark進行數據處理的一個重要又復雜的過程。正是因為shuffle過程很好地連接了前后兩個Stage的數據讀寫關系，才能使得多臺機器協同處理數據。在這個過程中，每個Map任務輸出的中間數據將會按鍵(key)重新分配到指定的redcue分片。如果不同reduce分片間的數據分布不平衡，這將導致一系列的問題：

1)遠程讀取(fetch)數據的時間增加以及數據傳輸失敗的可能性增大。Map任務通常將輸出的中間數據存在本地節點，一個reduce任務執行時將需要從不同的節點讀取數據。這意味著傳輸散落在不同節點的中間數據將耗費大量的通信時間，甚至引起傳輸數據失敗。

2)作業執行時間增加以及執行性能下降。重新分區難以保證分區間的數據平衡。當一些分區的數據遠多于其他分區時，這個分區的執行時間將大大延長整個Stage的執行時間，從而影響作業的執行時間。

為了處理數據偏斜的問題，目前的解決方案主要包括以下幾個方面：提高數據本地性；減少通信代價；提高資源利用率；減輕分片偏斜。在上述方法中，最直接的方法是實現高效均衡的分片算法使得每個reduce分片數據量相近，因為分片負載不均衡是偏斜問題的根本原因。

哈希分片算法(Hash)和范圍分片算法(Range)是Spark框架的兩種默認方法。Range方法主要用于處理需要排序的操作，而Hash方法則用于無需排序的其他操作。但是，兩種分片算法都無法處理分片偏斜的問題。Hash方法僅根據key的哈希值計算鍵值對的分片索引，雖然簡單快速，但這種方法對待分配數據的分布沒有任何預先了解，沒有任何抵御數據偏斜的能力。Range方法雖然將key按區間劃分，但是，當存在高頻key時，依然無法做出妥善的調節，無法抵御偏斜導致的問題。因此，Spark本身的抗偏斜機制并不完美，Hash方法需要偏斜預測和處理機制，Range方法需要鍵簇(key cluster)分割機制以加強偏斜處理能力。

發明內容

本發明的目的是提供一種基于Spark的抗偏斜的數據分片方法，解決Spark本身的抗偏斜機制問題，解決現有的Hash方法和Range方法無法處理分片偏斜的問題。

本發明提供一種基于Spark的抗偏斜的數據分片方法，包括如下步驟：

步驟A：獲取預估的中間數據的鍵簇分布以及Spark應用類型，再基于獲取的鍵簇分布生成與Spark應用類型相匹配的分片策略；

其中，所述鍵簇為鍵相同的鍵值對集合，Spark應用類型包括無需排序的應用類型和需排序的應用類型，所述分片策略包括分別與無需排序、需排序的應用類型相對應的基于鍵簇重分配的哈希算法策略和基于鍵簇分割的范圍分片算法策略；