[發明專利]一種分布式大數據處理方法

有效

• 申請號: 201611258710.X
• 申請日: 2016-12-30
• 公開（公告）號: CN106790620B
• 公開（公告）日: 2020-02-11
• 發明（設計）人: 張全友;寇瓊潔;陶戰剛;錢和平;吳俊紅
• 申請（專利權）人: 許昌學院
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 61223 西安銘澤知識產權代理事務所(普通合伙)
• 代理人: 潘宏偉

本發明提供了一種分布式大數據處理方法，涉及數據處理技術領域。將超立方體數據模型中的節點劃分為兩個子超立方體，然后分別對每個子超立方體中的數據進行處理，隨著規模n的變化，超立方體模型分布式算法的時間復雜度明顯低于時戳分布式算法和DFS最小生成樹分布式算法的時間復雜度。當n>k時，超立方體模型分布式算法的效率明顯高于時戳分布式算法和DFS最小生成樹分布式算法的效率。

技術領域

本發明涉及數據處理技術領域，特別涉及一種分布式大數據處理方法。

背景技術

大數據是指需要新處理模式才能具有更強的決策力、洞察力和流程優化能力的海量、高增長率和多樣化的信息資產。在維克托·邁爾-舍恩伯格及肯尼斯·庫克耶編寫的《大數據時代》書中，大數據處理是指不用隨機分析法、統計方法，而是采用所有數據同時進行分析處理。這樣大數據分析工作如果采用分布式計算架構將會比單臺計算機花費時間短。它的特色是利用云存儲技術、分布式數據庫、分布式處理，在海量數據中挖掘出有價值的信息。從海量數據中“提煉”出有價值的信息，這對數據處理能力和網絡架構而言也是巨大的挑戰。

目前對大數據的處理有時戳分布式算法和DFS最小生成樹分布式算法兩種處理方式。對于前者，對于一個全序對事件S，系統中的事件為接受消息后，取較大者作為新時戳。節點共有m個，節點的啟動時間為t，則算法的消息復雜度為O(mn²)，時間復雜度為O(t+L)。在最壞情況下，每個節點順序依次操作，總復雜度至多是：O(m*mn²)+O(t+L)。該算法的問題是不同事件可能有相同時戳(并發事件)，雖然可以選擇節點地址作為時戳的低位，但是不能通過事件的時戳判定兩事件之間是否是因果相關。而基于DFS生成樹分布算法可以判斷兩個事件之間的因果關系。

DFS生成樹分布算法，基于DFS生成樹分布算法的思想是每個節點均可自發喚醒，構造一棵以自己為根的DFS生成樹。若兩棵DFS樹試圖鏈接同一節點時，該節點將加入根的id較大的DFS樹。對于一個具有m條邊和n個節點的網絡，自發啟動的節點共有p個，其中id值最大者的啟動時間為t，則算法的消息復雜度為O(pn²)，時間復雜度為O(t+m)。最壞情況下，每個節點均試圖以自己為根構造一棵DFS樹，總復雜度至多是O(pn²)+O(m*n)。以上兩種梳理方法均存在數據處理效率不高的問題。

發明內容

本發明實施例提供了一種分布式大數據處理方法，用以解決現有技術中存在的問題。

一種分布式大數據處理方法，所述方法包括：

超立方體數據模型中具有n個節點，在該數據模型中隨機選擇一個節點作為中心元，然后將該中心元廣播到其他節點，每個節點中的數據與該中心元的數據進行比較，其中數據量大于所述中心元的數據的節點組成第一子超立方體，數據量小于或等于所述中心元的數據的節點組成第二子超立方體；

所述第一子超立方體與所述第二子超立方體之間互聯的兩個節點之間形成通信鏈路，將所述第一子超立方體和第二子超立方體之間沿第q條通信鏈路互聯的節點彼此互換數據，則節點標號的第i位為0的節點組成的i-1維子超立方體包含的數據都大于所述中心元中的數據，節點標號的第i位為1的節點組成的i-1維子超立方體包含剩余的數據；

對每個子超立方體中的數據進行數據處理；

對以上方法執行d次迭代，獲得最終數據處理結果。

優選地，所述數據處理為串行快速排序或數據查詢。

本發明的有益效果在于：隨著規模n的變化，超立方體模型分布式算法的時間復雜度明顯低于時戳分布式算法和DFS最小生成樹分布式算法的時間復雜度。當n>k時，超立方體模型分布式算法的效率明顯高于時戳分布式算法和DFS最小生成樹分布式算法的效率。

附圖說明