大型數據處理系統

在寬頻網際網路接入技術及智慧型終端高速普及的今天，網路數據容量以及處理數據量/數據強度的增加速度大大快於任何一個時期；大數據時代已經悄然來臨，大型數據處理系統也應運而生。

基本介紹

• 中文名：大型數據處理系統
• 外文名：Large data processing system
• 特點：處理數據量大，速度快
• 分類：負載類型和數據類型
• 套用：數據量大的情況下
• 領域：計算機

概述

網際網路的迅速發展導致數據量爆炸式增長，根據國際數據公司的統計，2011年全球產生的數據總量為1.8ZB(1ZB=1021B)，最近3年人類產生的信息量已經超過了之前產生的信息量總和。IBM用4個V，即Volume(數據體量巨大)、Velocity(數據以高速率產生)、Variety(數據類型多種多樣)和VMue(數據的價值密度低)，來描述大數據的特點，對低價值數據進行深度地分析，提煉出高價值的知識，已經成為目前普遍的共識。由於數據體量大、產生速
度快，以關係型資料庫為代表的傳統數據管理與分析工具無法應對大數據時代的挑戰，新型的海量數據處理技術應運而生。2012年，美國政府提出了“大數據研究發展計畫”，將大數據的研究與套用上升到戰略層面。毋庸置疑，我們已經處於大數據時代，並經歷這場技術變革。

大型數據處理系統的分類

大數據處理系統的種類繁多，目前還沒有公認的分類方法。為了清晰掌握技術的發展現狀，這裡從負載類型和數據類型兩個角度對代表性的系統進行分類，一方面明確了各種系統的適用範圍；另一方面可看到尚未解決的空白領域。

從負載類型上分類

從負載類型的角度，目前的系統可以劃分為批處理、流式計算和互動式查詢等三類。批處理系統強調系統的高吞吐量，例如Hadoop系統就定位於批處理。流式計算是近幾年興起的一個研究領域，很多套用場景對計算的時效性要求高，希望能夠在儘可能小的延遲內完成，例如線上廣告推薦、入侵檢測和作弊識別等。目前代表性的流式計算系統包括雅虎的s4、Twitter的Storm、Google的MillWheel、微軟的TimeStream和美國加州大學伯克利分校的DStream等。互動式查詢分析主要套用於大規模的數據倉庫，從早期的Hive到Dremel、Impala和Shark等，各種SQL-On-Ha-doop與大規模並行處理(massive parallel processing，MPP)系統不斷出現。

從數據類型上分類

從數據類型的角度，目前的系統提供了集合、表、圖和矩陣等多種數據抽象。通常一個編程框架只適合解決某類問題，無法對各種問題領域都適用。例如，MapReduce適合解決記錄之間相互獨立的集合類數據；Piccolo利用分散式記憶體存儲表格數據，能夠加快疊代計算的運行效率；MadLINQ提供大規模的矩陣運算，可簡化一大類機器學習和數據挖掘算法的開發。

研究進展

批處理編程框架種類繁多，但大部分編程框架都與數據流模型有密切關係，對數據流模型進行概括和總結可釐清一大類系統之間的差異。大規模圖計算和分散式機器學習是目前兩個非常活躍的研究方向，由於其計算特點的特殊性，數據流模型並不擅長解決此類問題，需要新式的計算模型。

基於數據流模型的編程框架

許多的編程框架都可以歸結為數據流模型，如批處理中的MapReduce、Dryad、Spark、FlumeJava，流處中的Storm等。數據流模型有相當長的研究歷史。簡單而言，數據流模型使用有向無環圖(directed acyclic graph，DAG)表達一個計算，圖中的頂點表示計算任務，而邊表示數據依賴。

(1)MapReduce：MapReduce計算為程式設計師提供了兩個簡捷的編程接口，即Map函式和Reduce函式。任務的輸入和輸出數據按照Key-Value的方式組織，框架會自動將中間結果中相同Key值的記錄聚合在一起，作為Reduce函式的輸人值。MapReduce具有非常突出的優點。首先是具有極高的可伸縮性，可以在數千台機器上並發執行；其次具有容錯性，即使集群發生了故障，一般情況下也不會影響任務的正常執行；三是簡單性，用戶只需要完成map和reduce兩個函式就可以完成大規模數據的並行處理。但MapReduce也存在一些局限性，比如map和reduce任務的啟動時間長，不適合對時效性要求高的套用場景。MapReduce模型存在多處的磁碟讀寫和網路傳輸，對於疊代機器學習套用，往往需要同一個mapreduce任務反覆執行，這就帶來了大量的磁碟讀寫和網路傳輸開銷，使運行效率非常低。MapReduce包括Map和Reduce兩個階段的任務，Map階段的任務執行完後才能執行Reduce階段的任務，無法表達任務之間複雜的拓撲結構，本質上MapReduce模型可以看作是DAG計算的一種特例。

(2)Dryad：Dryad採用了通用的DAG計算模型，能夠靈活地表達任務之間的拓撲結構，由於需要程式設計師顯式地構建拓撲結構，也帶來了一定的編程負擔。Dryad在數據傳輸方面提供了更多的機制，包括共享記憶體、TCP管道、臨時檔案和分散式檔案系統等，而MapReduce只提供了臨時檔案的方式傳輸map和reduce階段之間的中間結果。

(3)Spark：Spark的核心思想是使用數據集的轉換圖(DAG結構)來表達一個完整的數據處理過程，DAG中的頂點表示彈性分散式數據集(resilient distributed dataset，RDD)，邊表示轉換操作。RDD是對疊代計算中反覆使用的中間數據集的一種抽象，表示一個唯讀記錄組成的集合。RDD創建後其內容不能修改，但可以對RDD進行各種轉換操作，原先RDD的內容經過轉換後形成了新的RDD，Spark會維護RDD之間的依賴關係，稱為血統(Lineage)。這種鏈式操作不僅簡化了應用程式的開發，而且也讓故障恢復變得簡單了。Spark將RDD分片(partition)到多台機器上，同時執行粗粒度的轉換操作，即數據並行。一條記錄進入Spark的任務後會經歷多個轉換操作再輸出，即流水線。Spark提供RDD．Cache()的應用程式編程接口(API)，允許程式設計師將一個RDD顯式地載入並駐留在記憶體中，這樣可極大地加快後續的處理速度，對於疊代計算特別有效。隨著記憶體越來越便宜，基於記憶體計算會越來越成為系統設計上的一種選擇。

(4)高級的庫與語言：隨著Hadoop的廣泛套用，直接採用MapReduce編程面臨開發效率和性能等幾方面的問題。目前的發展趨勢是將Hadoop封裝到下層作為執行引擎，在上層系統中提供更加簡單易用的高級庫或面向領域的程式語言(domain specific language，DSL)等，由轉換層負責將更高級的抽象自動翻譯為大量的Hadoop作業。

圖計算

大規模的圖數據分析在實際套用中有廣泛的需求。例如網際網路的網頁之間形成了一個超大的圖，其頂點規模達到千億級，必須藉助於大規模的集群才能完成巨型圖的分析與挖掘。圖數據具有非規則的結構，導致圖數據訪問的局部性差。很多現實世界中的圖符合冪律分布，即圖頂點的分布極不均勻，極少的頂點通過大量的邊與其他大量頂點發生關聯，這意味著圖數據很難切分均勻，從而帶來機器負載不均衡和大量的網路通信開銷，這會嚴重影響圖計算系統的整體運行效率。

大圖的分割是圖計算中基礎性的問題之一。目前，圖數據的切分主要有兩種方法：切邊和切點。衡量圖數據的切分主要考慮兩個因素：機器的負載均衡性和網路通信量。理想的情況是機器負載儘量均衡，並且網路通信量最小。現實世界中的大多數圖的邊分布遵守冪律分布，理論和實踐均已證明，對於遵守這一特徵的圖數據，切點法比切邊法的計算效率要高一個數量級。

目前圖數據領域的相關係統可劃分為兩類：線上查詢的圖資料庫和離線圖數據分析系統。Facebook的Tao是目前代表性的大規模圖資料庫查詢系統，離線圖分析系統包括Pregel、Giraph、GraphLab和PowerGraph等，適合解決大規模圖數據的挖掘與分析類套用，如計算網頁的PageRank值、計算圖中兩個頂點之間的最短路徑等。

分散式機器學習系統

在大數據時代，傳統的單機版機器學習算法因為處理器和記憶體受限制，無法處理海量數據，分散式機器學習成為備受關注的研究領域。通常，機器學習算法使用疊代計算在巨大的參數空間中求最優解，其計算特點對分散式機器學習帶來了嚴重挑戰，主要表現在以下幾方面：

(1)單機版機器學習算法通過共享記憶體可存取全局參數，在分散式環境下需要通過網路來存取全局參數，效率比記憶體低很多，如何提高通信效率或者減少通信量，對提高分散式機器學習的運行效率至關重要。

(2)大量的並發任務由於各種原因(如機器負載或者軟硬體故障等)會導致其執行速度不統一，快任務需要等待慢任務執行完，負載的不均衡會降低任務的整體完成效率，如何避免“快等慢”現象也是需要解決的問題。

(3)當集群中的機器發生故障後，系統應當保證程式能夠容錯並運行正確。

最近幾年，大規模的深度學習在實際套用中獲得了巨大的成功，特別是在語音識別和圖像識別等領域取得了突破性進展。

根據技術路線的差異，目前分散式機器學習系統可以劃分為三類：基於Hadoop、基於Spark和參數伺服器架構。

Mahout是在Hadoop上構建的機器學習算法庫，提供了常見的聚類、分類和推薦等算法，由於底層機制受限於MapReduce提供的計算接口，算法的實現要複雜一些。此外，運算的中間結果都需要持久化到磁碟上，在疊代計算中需要頻繁地讀寫磁碟上的數據，導致運行效率低。

MLlib是在Spark上構建的機器學習系統，內置了大量成熟的機器學習算法庫，系統的最佳化器會根據參數的組合、數據特徵等信息自動地最佳化算法，降低了機器學習算法的使用門檻。由於Spark比Hadoop運行速度快幾十倍甚至上百倍，因此MLlib的運行效率要高許多。

參數伺服器是目前分散式深度學習系統的典型結構。參數伺服器包括大量並發執行的客戶端和多台參數伺服器組成的參數伺服器集群，不同的系統基本遵循上述結構，但在具體實現上有差異。從概念上講，參數伺服器可以看作是分散式共享記憶體的Key-Value存儲，用於存儲客戶端共享的全局參數，參數伺服器對全局參數進行數據分片，每個數據分片維護一部分全局參數的存儲與更新；在訓練過程中，客戶端可以讀取或更新全局參數，不同套用的全局參數可以存儲在參數伺服器的不同表格中。從結構上講，參數伺服器集群通常採用傳統的Master-slave結構，其中一台參數伺服器充當主控節點的角色，負責數據路由以及在不同的伺服器之間進行數據分片等工作。

研究熱點與趨勢

雖然大數據處理系統已取得大量的研究成果，各種工具與系統的研究方興未艾，但許多技術仍處於摸索階段，遠未達到成熟。本節歸納了三個方面的研究熱點與趨勢，並對國內的大數據處理系統的重點突破方向進行了展望。

(1)異構硬體平台的並行訓練

深度學習的計算特點是參數量巨大、更新頻繁，傳統的大數據處理技術如Hadoop，由於數據處理延遲高，並不適合需要頻繁疊代的深度學習，需要針對深度學習的模型結構和計算特徵來設計相應的專用系統。目前大規模的並行訓練是一個熱點問題，特別是如何利用CPU和GPU組成的異構並行硬體平台來加速計算值得深入研究。

(2)串列代碼的自動化並行

目前的編程框架提供了標準的數據操作接口，程式設計師編寫接口的實現函式，由底層的系統負責並行地執行用戶代碼，這種編程方式與傳統的串列編程差別大。最近，基於程式分析的自動化成為一個研究熱點，其基本思想是程式設計師編寫傳統的串列代碼，通過程式分析技術來自動獲取代碼中的並行性。這方面的代表性工作包括pydron和SDG，二者均通過分析代碼中的標註(annotation)來獲取並行性。串列代碼的自動化並行是一個具有吸引力的方向，許多問題有待進一步解決，包括最佳化的方法、減少對串列程式的限制等。

(3)混合編程

大數據處理技術的多樣化豐富了數據處理的手段，但也給實際套用帶來的困難。由於不存在全能通用的計算框架，多種編程框架需要協同工作才能完成複雜的數據處理任務。例如，典型的機器學習可以組織成數據預處理、特徵提取、訓練和評價等工作流。數據預處理和特徵提取階段可採用MapReduce來完成，而訓練階段採用PowerGraph來完成。目前實現上述處理流程需要多個獨立的作業，作業之間通過Hadoop分散式檔案系統(Hadoop distributed file system，HDFS)共享數據，造成大量的HDFS讀寫開銷，並且大量的作業也增加了資源調度的開銷。根本原因在於目前的編程框架相互獨立，計算之間只能以粗粒度的方式組合，如何打破目前編程框架之間的壁壘，讓多種計算能夠自由、高效地組合在一起完成更為複雜的處理流程，這個問題目前還沒有很好的解決方案。Transformerl提出了一種混合計算的編程系統，能夠將多種計算融合在一個程式中，並且通過分散式記憶體來加快中間數據集的訪問。