[發明專利]一種支持局部性表達函數的大數據處理方法和系統

有效

• 申請號: 201711250255.3
• 申請日: 2017-12-01
• 公開（公告）號: CN108241472B
• 公開（公告）日: 2021-03-12
• 發明（設計）人: 汪小林;潘成;陳一峯;羅英偉
• 申請（專利權）人: 北京大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;H04L29/08
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 邱曉鋒

本發明涉及一種支持局部性表達函數的大數據處理方法和系統。該方法包括以下步驟：1)發掘大數據處理系統中所處理的數據的局部性，形成局部性表達函數；2)將局部性表達函數部署在大數據處理系統中；3)大數據處理系統按照局部性表達函數分配工作任務。所述大數據處理系統采用分布式存儲方式或集中式存儲方式；所述局部性表達函數在大數據處理系統中的部署方式分為兩種類型：內置式冷啟動模式、外置式熱插拔模式。本發明通過發掘數據中隱藏的局部性，并且使用自定義的局部性函數表達出來，最終被大數據處理系統識別，按照局部性來分配機器執行任務，從而達到優化處理效率。

技術領域

本發明涉及一種將數據的局部性表達函數與分布式處理系統結合的方法和系統，屬于分布式系統領域。

背景技術

隨著數據量越來越大，計算機需要處理的業務越來越復雜，單機已經無法滿足需求。一個有效的解決方案是把眾多廉價的計算機整合起來，共同提供服務，這就是分布式系統。

嚴格來說，分布式系統是一個硬件或軟件組件分布在不同的網絡計算機上，彼此之間僅僅通過消息傳遞進行通信和協調的系統。也就是說一個分布式系統中的計算機在空間部署上可以是隨意分布的，這些計算機可能被放在不同的機柜上，也可能在不同的機房中，甚至分布在不同的城市。這些計算機之間通過網絡來通信。

分布式系統從體量上實現了相當大的可擴展性，通過不斷加入新的計算資源，可以處理的數據量也越來越大。但是隨著任務中的數據量的不斷擴張，也會有很多問題隨之而來。比如不同機器在計算中需要傳遞的數據量會隨著機器數量、運算數據、迭代次數等等因素的增加而增加，而不同機器之間是通過網絡來傳遞數據的，網絡帶寬很容易會成為限制整體運算效率的瓶頸。又比如基于MapReduce架構的分布式系統，在多次迭代的過程中會產生大量的中間結果，這些結果沒法都存儲在內存中，只能換出到外存。大量數據在內外存的頻繁換入換出，也會導致整體運算性能的下降。

充分發掘數據中的局部性可以幫助更好的優化分布式系統的計算。比如經典的PageRank算法，每一輪迭代計算中，都需要在各個網頁鏈接之間傳送數據。如果可以將整個網頁鏈接關系的大圖劃分成幾個較為均等的子圖，并且各個網頁之間的鏈接盡可能出現在同一個子圖之內，那么在分布式迭代的過程中，可以將一個子圖中的數據都放在一個物理節點上計算，可以大大節約網絡帶寬。再比如大規模(TB甚至更高級別)的<鍵,值>數據按鍵排序，數據中的鍵可能比較長，不太可能全部加載到內存中進行排序。使用外部排序的話，會產生很大的磁盤IO；或者采用分布式的排序，又會產生相當大的網絡流量。如果此時有一種比key更簡短的值可以代表整個鍵值對，并且滿足一定的偏序關系，便可以將這個短小的值放入內存中進行預排序，預排序的結果可以對數據集進行更精確的劃分，然后使用分布式的節點對每個劃分好的子塊進行細致的排序。這樣可以降低一定程度的磁盤IO，從而達到優化整體任務的執行效果。

發明內容

本發明的目的是提出一種通用大數據處理系統和用戶可自定義局部性表達函數(本發明將該局部性表達函數稱為Locey)的結合方式，以優化數據處理效率。具體來說，大數據處理系統往往采用分布式的架構，需要多臺機器之間分工協作，在處理不同類型的數據的時候，往往會產生機器與機器、內存與磁盤之間的數據傳送。通過發掘數據中隱藏的局部性，并且使用自定義的局部性函數表達出來，最終被大數據處理系統識別，按照局部性來分配機器執行任務，從而達到優化處理效率。

本發明所述“局部性”是指程序運行時對數據訪問的“時間局部性”與“空間局部性”的總稱。時間局部性指的是“如果一個信息項正在被訪問，那么在近期它很可能還會被再次訪問”，空間局部性指的是“在最近的將來將用到的信息很可能與現在正在使用的信息在空間地址上是臨近的”。