|
在我們實際生活中，事務型數(shù)據(jù)處理需求非常常見，例如：淘寶網(wǎng)站交易系統(tǒng)、12306網(wǎng)站火車票交易系統(tǒng)、超市POS系統(tǒng)等都屬于事務型數(shù)據(jù)處理系統(tǒng)。 這類系統(tǒng)數(shù)據(jù)處理特點包括以下幾點： 一是事務處理型操作都是細粒度操作，每次事務處理涉及數(shù)據(jù)量都很小。 二是計算相對簡單，一般只有少數(shù)幾步操作組成，比如修改某行的某列; 三是事務型處理操作涉及數(shù)據(jù)的增、刪、改、查，對事務完整性和數(shù)據(jù)一致性要求非常高。 四是事務性操作都是實時交互式操作，至少能在幾秒內(nèi)執(zhí)行完成; 五是基于以上特點，索引是支撐事務型處理一個非常重要的技術。 在數(shù)據(jù)量和并發(fā)交易量不大情況下，一般依托單機版關系型數(shù)據(jù)庫，例如ORACLE、MYSQL、SQLSERVER，再加數(shù)據(jù)復制(DataGurad、 RMAN、MySQL數(shù)據(jù)復制等)等高可用措施即可滿足業(yè)務需求。 在數(shù)據(jù)量和并發(fā)交易量增加情況下，一般可以采用ORALCE RAC集群方式或者是通過硬件升級(采用小型機、大型機等，如銀行系統(tǒng)、運營商計費系統(tǒng)、證卷系統(tǒng))來支撐。 事務型操作在淘寶、12306等互聯(lián)網(wǎng)企業(yè)中，由于數(shù)據(jù)量大、訪問并發(fā)量高，必然采用分布式技術來應對，這樣就帶來了分布式事務處理問題，而分布式事務處理很難做到高效，因此一般采用根據(jù)業(yè)務應用特點來開發(fā)專用的系統(tǒng)來解決本問題。 數(shù)據(jù)統(tǒng)計主要是被各類企業(yè)通過分析自己的銷售記錄等企業(yè)日常的運營數(shù)據(jù)，以輔助企業(yè)管理層來進行運營決策。典型的使用場景有：周報表、月報表等固定時間提供給領導的各類統(tǒng)計報表;市場營銷部門，通過各種維度組合進行統(tǒng)計分析，以制定相應的營銷策略等。 數(shù)據(jù)統(tǒng)計分析特點包括以下幾點： 一是數(shù)據(jù)統(tǒng)計一般涉及大量數(shù)據(jù)的聚合運算，每次統(tǒng)計涉及數(shù)據(jù)量會比較大。 二是數(shù)據(jù)統(tǒng)計分析計算相對復雜，例如會涉及大量goupby、 子查詢、嵌套查詢、窗口函數(shù)、聚合函數(shù)、排序等;有些復雜統(tǒng)計可能需要編寫SQL腳本才能實現(xiàn)。 三是數(shù)據(jù)統(tǒng)計分析實時性相對沒有事務型操作要求高。但除固定報表外，目前越來越多的用戶希望能做做到交互式實時統(tǒng)計; 傳統(tǒng)的數(shù)據(jù)統(tǒng)計分析主要采用基于MPP并行數(shù)據(jù)庫的數(shù)據(jù)倉庫技術。主要采用維度模型，通過預計算等方法，把數(shù)據(jù)整理成適合統(tǒng)計分析的結構來實現(xiàn)高性能的數(shù)據(jù)統(tǒng)計分析，以支持可以通過下鉆和上卷操作，實現(xiàn)各種維度組合以及各種粒度的統(tǒng)計分析。 另外目前在數(shù)據(jù)統(tǒng)計分析領域，為了滿足交互式統(tǒng)計分析需求，基于內(nèi)存計算的數(shù)據(jù)庫倉庫系統(tǒng)也成為一個發(fā)展趨勢，例如SAP的HANA平臺。 數(shù)據(jù)挖掘主要是根據(jù)商業(yè)目標，采用數(shù)據(jù)挖掘算法自動從海量數(shù)據(jù)中發(fā)現(xiàn)隱含在海量數(shù)據(jù)中的規(guī)律和知識。 數(shù)據(jù)挖掘主要過程是：根據(jù)分析挖掘目標，從數(shù)據(jù)庫中把數(shù)據(jù)提取出來，然后經(jīng)過ETL組織成適合分析挖掘算法使用寬表，然后利用數(shù)據(jù)挖掘軟件進行挖掘。傳統(tǒng)的數(shù)據(jù)挖掘軟件，一般只能支持在單機上進行小規(guī)模數(shù)據(jù)處理,受此限制傳統(tǒng)數(shù)據(jù)分析挖掘一般會采用抽樣方式來減少數(shù)據(jù)分析規(guī)模。 數(shù)據(jù)挖掘的計算復雜度和靈活度遠遠超過前兩類需求。一是由于數(shù)據(jù)挖掘問題開放性，導致數(shù)據(jù)挖掘會涉及大量衍生變量計算，衍生變量多變導致數(shù)據(jù)預處理計算復雜性;二是很多數(shù)據(jù)挖掘算法本身就比較復雜，計算量就很大，特別是大量機器學習算法，都是迭代計算，需要通過多次迭代來求最優(yōu)解，例如K-means聚類算法、PageRank算法等。 因此總體來講，數(shù)據(jù)分析挖掘的特點是: 1、數(shù)據(jù)挖掘的整個計算更復雜，一般是由多個步驟組成計算流，多個計算步驟之間存在數(shù)據(jù)交換，也就是會產(chǎn)生大量中間結果，難以用一條sql語句來表達。 2、計算應該能夠非常靈活表達，很多需要利用高級語言編程實現(xiàn)。 在google、facebook、taobao等大互聯(lián)網(wǎng)公司出現(xiàn)之后，這些公司注冊和在線用戶數(shù)量都非長大，因此該公司交易系統(tǒng)需要解決“海量數(shù)據(jù)+高并發(fā)+數(shù)據(jù)一致性+高可用性”的問題。 為了解決該問題，從目前資料來看，其實沒有一個通用的解決方案，各大公司都會根據(jù)自己業(yè)務特點定制開發(fā)相應的系統(tǒng),但是常用的思路主要包括以下幾點： (1)數(shù)據(jù)庫分片，結合業(yè)務和數(shù)據(jù)特點將數(shù)據(jù)分布在多臺機器上。 (2)利用緩存等機制，盡量利用內(nèi)存，解決高并發(fā)時遇到的隨機IO效率問題。 (3)結合數(shù)據(jù)復制等技術實現(xiàn)讀寫分離，以及提高系統(tǒng)可用性。 (4)大量采用異步處理機制，對應高并發(fā)沖擊。 (5)根據(jù)實際業(yè)務需求，盡量避免分布式事務。 1) 阿里CORBAR系統(tǒng) 阿里COBAR系統(tǒng)是一個基于MYSQL數(shù)據(jù)庫的分布式數(shù)據(jù)庫系統(tǒng)，屬于基于分布式數(shù)據(jù)庫中間件的分布式數(shù)據(jù)庫系統(tǒng)。該系統(tǒng)是前身是陳思儒開發(fā)的“變形蟲”系統(tǒng)(以前調研過)，由于陳思儒離開阿里去了盛大，阿里當心“變形蟲”穩(wěn)定性等問題，重新開發(fā)該項目。 該系統(tǒng)主要采用數(shù)據(jù)庫分片思路，實現(xiàn)了：數(shù)據(jù)拆分、讀寫分離、復制等功能。由于此系統(tǒng)由于只需要滿足事務型操作即可，因此相對真正并行數(shù)據(jù)庫集群(例如TeraData等)，此類系統(tǒng)提供操作沒有也不需要提供一些復雜跨庫處理，因此該系統(tǒng)存在以下限制： (1)不支持跨庫的join、分頁、排序、子查詢。 (2)insert等變更語句必須包括拆分字段等。 (3)應該不支持跨機事務(以前變形蟲不支持)。 說白了此類系統(tǒng)不具備并行計算能力,基本上相當于數(shù)據(jù)庫路由器! 另外此類系統(tǒng)的在實際應用的關鍵問題是，根據(jù)什么對數(shù)據(jù)進行切分，因為切分不好會導致分布式的事務問題。 2) 阿里OceanBase系統(tǒng) 該系統(tǒng)也是淘寶為了解決高并發(fā)、大數(shù)據(jù)環(huán)境下事務型處理而定制開發(fā)的一個系統(tǒng)。該系統(tǒng)主要思路和特點如下： (1)他們發(fā)現(xiàn)在實際生成環(huán)境中，每天更新的數(shù)據(jù)只占總體數(shù)據(jù)的1%不到，因此他們把數(shù)據(jù)分為：基線數(shù)據(jù)和增量更新數(shù)據(jù)。 (2)基線數(shù)據(jù)是靜態(tài)數(shù)據(jù)，采用分布式存儲方式進行存儲。 (3)只在一臺服務器上存儲和處理增量更新數(shù)據(jù)，并且是在內(nèi)存中存儲和處理更新數(shù)據(jù)。 (4)在系統(tǒng)負載輕的時候，把增量更新批量合并到基線數(shù)據(jù)中。 (5)數(shù)據(jù)訪問時同時訪問基線數(shù)據(jù)和增量更新數(shù)據(jù)并合并。 因此這樣好處是： (1)讀事務和寫事務分離 說明：該系統(tǒng)雖然能處理高并發(fā)的事務型處理，號稱很牛逼，但其實也只是根據(jù)電商的事務處理來定制開發(fā)的專用系統(tǒng)，個人認為其技術難度小于oracle等通用型的數(shù)據(jù)庫。該系統(tǒng)無法應用到銀行或者12306等，因為其事務處理的邏輯遠遠比電商商品買賣處理邏輯復雜。 在目前的大數(shù)據(jù)時代，一定是基于應用定制才能找到好的解決方案! 3) 基于Hbase的交易系統(tǒng) 在hadoop平臺下，HBASE數(shù)據(jù)庫是一個分布式KV數(shù)據(jù)庫，屬于實時數(shù)據(jù)庫范疇。支付寶目前支付記錄就是存儲在HBASE數(shù)據(jù)庫中。 HBASE數(shù)據(jù)庫接口是非SQL接口，而是KV操作接口(基于Key的訪問和基于key范圍的scan操作)，因此HBASE數(shù)據(jù)庫雖然可擴展性非常好，但是由于其接口限制導致該數(shù)據(jù)庫能支持上層應用很窄?；贖BASE應用的設計中，關鍵點是key的設計，要根據(jù)需要支持的應用來設計key的組成。 可以認為HBASE數(shù)據(jù)庫只支持作為KEY的這一列的索引。雖然目前HBASE有支持二級索引的方案，二級索引維護將會比較麻煩。 并發(fā)是指同時執(zhí)行通常不相關的各種任務，例如交易型系統(tǒng)典型屬于高并發(fā)系統(tǒng)。 并行是通過將一個很大的計算任務，劃分為多個小的計算任務，然后多個小計算任務的并行執(zhí)行，來縮短該計算任務計算時間。 兩者主要區(qū)別在于： (1)通訊與協(xié)調方面：在并行計算中，由于多個小任務同屬一個大的計算任務，因此小任務之間存在依賴關系，小任務之間需要大量通訊和協(xié)調;相反，并發(fā)中的多個任務之間基本相互獨立，任務與任務之間相關性很小。 (2)容錯處理方面：由于并發(fā)任務之間相互獨立，某個任務執(zhí)行失敗并不會影響其它的任務。但是并行計算中的多個任務屬于一個大任務，因此某個子任務的失敗，如果不能恢復(粗粒度容錯與細粒度容錯)，則整個任務都會失敗。 數(shù)據(jù)量大不一定需要并行計算，雖然數(shù)據(jù)量大，數(shù)據(jù)是分布存儲，但是如果每次操作基本上還是針對少量數(shù)據(jù)，因此每次操作基本上都是在一臺服務器上完成，不涉及并行計算。只是需要通過數(shù)據(jù)復制、數(shù)據(jù)緩存、異步處理等方式來支撐高并發(fā)訪問量 隨數(shù)據(jù)量變大，和事務處理不同的是，單個統(tǒng)計分析涉及數(shù)據(jù)量會非常大，單個統(tǒng)計分析任務涉及數(shù)據(jù)會分散在多臺服務器上，且由于計算量大，采用單臺服務器進行計算，會導致計算時間非常長，單個統(tǒng)計分析任務必須采用并行計算方式來加快單個統(tǒng)計分析任務執(zhí)行速度。 在大數(shù)據(jù)背景下的數(shù)據(jù)統(tǒng)計分析技術門類很多，常見的有： · MPP并行數(shù)據(jù)庫 : TeraData、GreenPlum、Vertica等。 這些系統(tǒng)都解決了海量數(shù)據(jù)下的數(shù)據(jù)統(tǒng)計分析的問題，并且這些系統(tǒng)另外一個共同特點是都提供了SQL或者類SQL接口。 為了能夠較好研究這些系統(tǒng)，我們需要對并行查詢與并行計算的相關技術做一個簡要的介紹。 首先所有的系統(tǒng)都可以分為三個層次: 語義層、并行計算引擎層、分布式存儲層。語義層提供一個編程接口讓用戶表達所需要計算，并負責把該計算翻譯成底層并行計算引擎可以執(zhí)行的執(zhí)行計劃，并由并行計算引擎來執(zhí)行，最下面一層是分布式存儲層。 對于提供類SQL接口并行計算系統(tǒng)，語義層可以認為是SQL解析層。 1) 語義層 SQL語言是一種聲名式語言，SQL只是表達了要做什么，而沒有表達怎么做。為此，SQL解析層主要作用是：將用戶提交的基于SQL的統(tǒng)計分析請求，轉化為底層計算引擎層可以執(zhí)行的執(zhí)行計劃。也就是解決“怎么做”的問題。 SQL解析層工作主要包括兩個大方面: (1) 通過語法分析技術來理解要做什么。在關系數(shù)據(jù)庫中，一般會把SQL語言分析后，形成樹型結構的執(zhí)行計劃。 (2) 在語法分析技術上，利用各種優(yōu)化技術和算法，找出一種最經(jīng)濟物理執(zhí)行計劃。 優(yōu)化可以分為兩個方面：一是邏輯層面優(yōu)化、二是物理執(zhí)行層面優(yōu)化。 (1) 邏輯層優(yōu)化 邏輯層面?zhèn)€人認為主要是因為同樣表達一個分析請求，有的人SQL寫的好，有的人SQL寫的爛，因此在邏輯層面可以通過一些等價關系代數(shù)變換，實現(xiàn)查詢重寫，將寫的比較爛的sql變換為好的寫法。 比較典型優(yōu)化是：“把投影和過濾下沉，先執(zhí)行過濾和投影操作”，減少中間結果。 (2) 物理層優(yōu)化 物理層面優(yōu)化是在邏輯優(yōu)化后，結合實際物理執(zhí)行過程，找出最優(yōu)的物理執(zhí)行計劃。生成物理查詢計劃的工作包括: · 增加一些操作符： 包括掃描和排序等。 · 確定各個操作符實現(xiàn)算法。例如掃描是全表掃描還是利用索引;Join是采用HASH連接、索引連接、合并排序等實現(xiàn)算法中的那一種。 · 確定操作符之間的數(shù)據(jù)流轉方法：物化還是流水線方式。 · 采用基于代價估算方法確定最優(yōu)的物理執(zhí)行計劃，目前代價估算主要是以估算該物理計劃需要的IO量。另外對于并行數(shù)據(jù)庫，則還要考慮通訊代價，即盡量減少數(shù)據(jù)在各個機器之間的傳遞。 在物理層優(yōu)化的代價估算過程中，代價估算需要依靠很多統(tǒng)計信息，如表有多大，表中相關列的值分布是什么樣子等。傳統(tǒng)數(shù)據(jù)庫在數(shù)據(jù)Load過程中會事先計算好這些統(tǒng)計信息。并行計算中還需要考慮通訊代價。 需要指出是，由于imapla、Presto、HIVE等系統(tǒng)只是一個查詢引擎，它們可以直接查詢以普通文件方式存儲在HDFS系統(tǒng)上的文件，因此這些系統(tǒng)一般無法使用索引和各種統(tǒng)計信息來進行物理執(zhí)行計劃的優(yōu)化，這些系統(tǒng)一般只能在邏輯層進行一些基于規(guī)則靜態(tài)優(yōu)化。根據(jù)SHARK論文，SHARK系統(tǒng)支持根據(jù)前面一些節(jié)點計算獲得的信息，來動態(tài)優(yōu)化后面執(zhí)行計劃。 (3) 物化與流水線執(zhí)行方法 一條SQL語句對開發(fā)人員而言，感覺只是一次調用，但是實際上在數(shù)據(jù)庫內(nèi)部，一條SQL語句執(zhí)行其實是有多個操作符組合而成的的樹型結構計算流。如下圖： 針對該計算流有兩種執(zhí)行方式：一是基于物化或者是實體化執(zhí)行方式，另外一種是基于數(shù)據(jù)流的執(zhí)行方式。 第一種方法的過程是： 把各個操作運算排序，并把每個操作運算的輸出的中間結果存儲在磁盤上，直到被另外一個操作運算所讀取。 另外一種方法是同時交錯進行多個運算，由一個運算產(chǎn)生每個元組直接傳遞給下一個運算，而不將中間結果存儲到磁盤，也不用等到前一個運算全部運算完畢。 例如： 兩個表連接后，再進行投影操作。如果采用第一種方法，則需要 把兩表連接中間結果臨時寫入磁盤，然后再讀取該結果執(zhí)行投影操作。而如果采用第二種方法，則連接操作一旦產(chǎn)生一個元組就可以立刻送到投影操作去進行投影操作。 流水線方法可以極大避免大量的中間結果磁盤IO。因此數(shù)據(jù)庫一般會采取流水線方法來執(zhí)行。流水執(zhí)行方法有兩種模式：一種是需求驅動流水線，也就是從上層主動向下層要求元組，另外一種是生產(chǎn)者驅動流水線執(zhí)行方式，由低層主動產(chǎn)生元組，由下層向上層推。 目前大部分數(shù)據(jù)庫引擎采用的是需求驅動流水線，實現(xiàn)方式采用基于Graefe提出的迭代器模型。該模型把每個操作都表達為由三個接口： open() , getnext(), close()。每個操作被調用open() 進行準備工作，然后通過反復迭代被調用getnext來獲取下一個元組，最后被調用close來進行清理工作。 通過構建迭代器網(wǎng)絡，也就是迭代器之間的互相調用，就可以實現(xiàn)需求驅動流水線。 當然不是任何操作都可以流水執(zhí)行，流水執(zhí)行條件是：操作要滿足在接收輸入元組時可以輸出元組。例如排序操作就無法進行流水操作，在執(zhí)行排序操作前都必須進行實體化。 (4) SQL解析層與并行計算引擎層 由于不同并行計算引擎層的執(zhí)行計劃表達不同，因此不同系統(tǒng)需要將SQL解析成不同的形式物理執(zhí)行計劃，例如： · MPP關系數(shù)據(jù)庫一般是把SQL解析成樹狀結構的物理執(zhí)行計劃。 · HIVE、Tezning數(shù)據(jù)庫是把SQL解析成DAG結構的多個MAPREDUCE組合。 · DRemel等則類似MPP關系數(shù)據(jù)庫，把SQL解析成一個樹狀結構執(zhí)行計劃。 · 微軟SCOPE則需要把類SQL解析成DAG結構的Dryad可執(zhí)行的執(zhí)行計劃。 · SHARK則需要把SQL解析成基于scala語言的DAG結構執(zhí)行計劃。 并行 2) 并行計算引擎層 (1) 并行計算形式 并行化可以分為水平并行(無依賴并行)與垂直并行(流水線并行)兩類。如下圖： 如果兩個操作OP1、OP2 無相互依賴關系，則稱這兩個操作相互獨立。水平并行化指的是互相獨立的多個操作或者一個操作內(nèi)互相獨立的多個子操作分別由不同的處理機并行執(zhí)行的形式。例如，排序操作、掃描操作由不同處理機并行執(zhí)行就是水平并行化的實例。 水平并行中一個非常常見的就是基于數(shù)據(jù)劃分的并行，例如MAPREDUCE，就是通過將數(shù)據(jù)劃分到多臺服務器上，并行執(zhí)行MAP和Reduce來進行并行運算。也有人把這種基于數(shù)據(jù)劃分并行與操作獨立并行區(qū)分開。 垂直并行化則是指存在流水線方式依賴關系的操作分別由不同處理機并行執(zhí)行的形式。流水線方式依賴：如果OP2無需等待OP1執(zhí)行完畢即可在另一處理機上開始執(zhí)行。由于一般情況下，流水的級數(shù)遠小于處理的數(shù)據(jù)條目，因此流水并行主要意義是在可以避免中間結果磁盤IO操作，對并行度的貢獻相對較小。 (2) 并行計算面臨的問題與并行計算框架 并行計算需要解決的問題主要包括幾下幾個方面：自動并行化、通訊、任務調度、并發(fā)控制、容錯、資源管理。由于并行計算面向上述一系列問題，因為業(yè)界為了簡化并行程序開發(fā)，提供了一系列的并行計算底層庫或者框架。 在高性能計算領域，最常用于并行計算編程的庫是MPI庫，但是該庫主要只是解決通訊問題。這導致容錯、資源管理、任務調度、并行化等方面問題需要程序員來解決，因此利用MPI開發(fā)并行程序相對比較困難。 最近一些年，各大型互聯(lián)網(wǎng)公司開發(fā)開發(fā)了一系列的通用并行計算框架。包括谷歌公司的MAPREDUCE框架、微軟公司的Dryad框架(目前微軟已經(jīng)停止該項目開發(fā)，轉而支持hadoop)、谷歌公司基于BSP模型的Pregel框架、Twitter公司的Storm框架、Yahoo公司S4框架、HortonWorks公司的Tez框架、Berkeley大學的spark框架等通用并行計算框架。 有了這些框架了，程序開發(fā)時只需要編寫串行執(zhí)行程序即可，而且也不用考慮任務與任務之間的并發(fā)控制以及通訊等問題，其它所有問題都有框架來解決 ，這樣就大大簡化并行程序開發(fā)難度。例如采用MAPREDUCE框架，我們只需要提供MAP函數(shù)和Reduce函數(shù)，這些函數(shù)對程序員而言，都只是對本地數(shù)據(jù)操作。 目前雖然并行計算框架很多，但是可以把它們分成幾個大類(基于BSP并行圖計算引擎請參考第四章)： · 流數(shù)據(jù)并行計算框架 Storm、S4是屬于流數(shù)據(jù)并行計算框架，適合對流數(shù)據(jù)實時處理，也就是在數(shù)據(jù)寫入磁盤前對數(shù)據(jù)進行實時并發(fā)運算。這類特點是計算不變，數(shù)據(jù)一直在變化。在上一個文檔中，對此框架做過詳細介紹，這里不再詳細介紹。 · 基于DAG通用批處理并行計算框架 MapReduce、Tez、Dryad、Spark等屬于基于DAG(有向無環(huán)圖)的通用批處理并行計算框架。這類框架是針對存儲在存儲設備上的一批數(shù)據(jù)進行分析處理，而且把分析處理流程利用DAG模型來表達。 在這些框架中MAPREDUCE是最早出現(xiàn)的框架，而后面出現(xiàn)的一系列框架都為了改進MR框架不足而出現(xiàn)的升級版本。 · MR框架主要不足是兩個方面： 一是編程接口太簡單，表現(xiàn)在單個MAPREDUCE無法表達復雜運算，所以在實際應用環(huán)境中都是通過多個MR作業(yè)組合來完成一個任務。為了簡化MR作業(yè)組合，在早期出現(xiàn)了一系列項目來執(zhí)行組和式MR作業(yè)，例如Cascading項目。另外一個方面所有問題都必須轉換為MAP和REDUCE模式，導致程序編寫比較麻煩。 二是MR只支持基于數(shù)據(jù)分區(qū)并行方式，不支持流水線并行，采用是步步物化策略來提高可靠性，當是這種導致大量中間結果物化，IO開銷非常大。 因此Tez、Dryad、Spark等后續(xù)框架改進主要針對以下兩點進行改進： 一是直接支持基于DAG結構表達方法，DAG使得用戶能夠非常清晰地寫出非常復雜的業(yè)務邏輯; 二是通過支持流水線并性方式或者是盡量將中間結果放內(nèi)存等方式，解決中間結果物化導致的IO開銷問題。Dryad和Spark框架在執(zhí)行運算時，都會自動識別可以采取流水線方式執(zhí)行的計算步驟，并盡量采用流水線執(zhí)行方式來執(zhí)行。 容錯：由于支持流水線并行或者采取把中間結果放內(nèi)存的方式，因此要必須考慮容錯的問題。由于這些框架都采用的是DAG結構，DAG中一個節(jié)點所代表計算的執(zhí)行是不會對輸入進行修改(所謂函數(shù)式編程)，因此可以多次重復執(zhí)行不會影響計算。因此如果某個節(jié)點計算失敗，它可以根據(jù)輸入重復計算，而如果輸入數(shù)據(jù)也消失了，則讓前一個節(jié)點重新計算。所有這一切都是由框架自動執(zhí)行。 當然需要指出的是對一些流水線執(zhí)行的多個計算步驟，如果某個計算節(jié)點失敗，則只能整個流水線整體失敗。 · 基于Tree結構的MPP并行查詢引擎 MPP并行數(shù)據(jù)庫與Dremel、impala、Presto、Shard query、Citusdb都采用的是基于Tree結構并行查詢引擎。此類并行計算引擎共同特點是： 一是針對SQL專用并行計算引擎，只支持SQL或者類SQL語義。 二是執(zhí)行計劃都是樹狀結構; 三是以流水線或者將中間結果放入內(nèi)存方式來實現(xiàn)快速計算。 四是粗粒度容錯機制。 它們之間不同點： 一 MPP并行數(shù)據(jù)庫中并行查詢引擎與底層存儲是緊耦合的，導致如果采用MPP并行數(shù)據(jù)庫，則只能通過SQL來訪問數(shù)據(jù)，無法采用其他計算引擎直接處理存儲在數(shù)據(jù)庫中的數(shù)據(jù)。 二 Impala、Presto都只是一個并行查詢引擎，它們可以直接查詢以文件方式存儲在HDFS上的數(shù)據(jù),這樣同一份數(shù)據(jù)既可以利用這些引擎來實現(xiàn)交互式查詢，也可以支持利用其他計算框架進行更深入分析。 三 Dremel 只支持Google自己的基于嵌套結構列式存儲(Column IO)。該引擎也主要適合于聚合型計算，不支持join操作。 四 上述引擎中只有MPP并行數(shù)據(jù)庫可以利用索引以及各種統(tǒng)計信息來優(yōu)化物理執(zhí)行過程，因此該系統(tǒng)執(zhí)行效率應該是最高。 五 Dremel、impala都只適合中間結果越來越小的查詢，因為這些系統(tǒng)都是把中間結果放在內(nèi)存，一旦某個中間節(jié)點輸出結果超過內(nèi)存，則整個任務會失敗，例如大表之間Join。 六 shard query和citusdb 都是在單機版本關系數(shù)據(jù)庫基礎上，采用增加一層中間件方式來支持并行查詢。 · 基于Tree并行計算引擎與基于DAG并行計算引擎本質區(qū)別 基于Tree結構并行計算引擎與基于DAG并行計算引擎從表面上看，它們之間的主要區(qū)別是在于語義層面：前者主要專用與SQL類，而后者更通用。 但是MPP并行關系數(shù)據(jù)庫引擎、Imapla等都會支持通過UDF來擴展和解決標準SQL語言表達能力，另外SQL語言本身可以通過嵌套查詢、子查詢、union等各種方法表達很復雜的計算過程，因此從語義表達層面來講他們之間不存在本質區(qū)別。 這兩者之間主要區(qū)別還是在于表達執(zhí)行計劃結構方面：樹結構是一個逐步匯聚的一個計算過程，無法表達split結構，因此基于DAG表達結構更靈活和通用。個人認為：樹型結構可能更加適合采用迭代器模型來實現(xiàn)流水線式的操作(只有樹結構才有上下層的關系，因此方便實現(xiàn)上層操作符嵌套調用下層操作符)。 所以不是所有計算都可以通過一個復雜SQL語句來表達! (5) 自動并行化、數(shù)據(jù)重分布、本地調度 并行計算引擎最重要的一個職責是自動并行。根據(jù)前面的并行計算基礎知識，并行計算的形式主要包括：基于數(shù)據(jù)劃分水平并行、基于流水線垂直并行、基于無依賴水平并行三種方式。 大數(shù)據(jù)屬于數(shù)據(jù)密集型計算，數(shù)據(jù)數(shù)量遠遠超過計算步驟數(shù)量。因此基于數(shù)據(jù)劃分并行方式是最有效的一種并行計算方法。在整個并行計算過程中，基于數(shù)據(jù)劃分中涉及數(shù)據(jù)可以分為兩大類：原始數(shù)據(jù)與中間結果數(shù)據(jù)。 · 原始數(shù)據(jù)劃分以及SN、SD架構討論 原始數(shù)據(jù)則可能存在兩種情況：一是在Shared-nothing架構中，原始數(shù)據(jù)本身就已經(jīng)劃分好了，例如HDFS或者SN架構 MPP數(shù)據(jù)庫;另外一種情況如shared-disk結構中，原始數(shù)據(jù)沒有劃分。 第一種情況下針對原始數(shù)據(jù)劃分并行計算，就要受該劃分的限制。例如在MAPREDUCE中，map輸入是存儲在HDFS上的數(shù)據(jù)文件，因此MAP實例個數(shù)一是不能少于該數(shù)據(jù)文件分片數(shù)，二是MAP實例最好運行在該數(shù)據(jù)文件所在機器，也就是要求任務調度時，能把該任務調度到特定機器上，即所謂“本地調度”，將計算盡量移動到數(shù)據(jù)。 第二種情況下，由于所有計算節(jié)點都可以看到所有數(shù)據(jù)，因此此時可以根據(jù)計算特點靈活選擇：數(shù)據(jù)劃分粒度、并行度、參與計算的節(jié)點。例如在ORALCE并性機制中，ORALCE可以針對某張表，按block或者partition 為單位進行劃分。 根據(jù)上述分析我們可以發(fā)現(xiàn)SD架構相對SN架構，在針對原始數(shù)據(jù)第一級并性計算時，SD架構更靈活，SN架構面臨的一個缺陷就是如果原始數(shù)據(jù)分布不均衡，則存在計算傾斜問題。 但是現(xiàn)在大部分大的數(shù)據(jù)庫廠商的MPP數(shù)據(jù)庫還是采用了SN架構。根據(jù)網(wǎng)上所查資料來看,主要原因有兩點： 一是SD架構下，磁盤是一個共享資源，計算節(jié)點越多磁盤爭搶概率越大(和RAID隨機IO沖突道理一樣)，導致該架構可擴展性不夠好，也就是可能計算節(jié)點越多，效率相反不會提高。 二是從緩存角度來看，SD架構下每個機器緩存都要面向全數(shù)據(jù)庫，會導致命中概率底下;目前ORACLE-RAC開發(fā)一個fusion cache技術，實現(xiàn)了一個全局共享緩存來解決上述問題，但是可想而知這會影響系統(tǒng)可擴展性。 因此超過一定規(guī)模數(shù)據(jù)分析系統(tǒng)，都是采用SN架構。 中間結果數(shù)據(jù)劃分與數(shù)據(jù)重分布 中間結果是由各個計算節(jié)點產(chǎn)生的，因此中間結果生成是就是分布在各個參與計算節(jié)點之上的，因此： 一 ：SD架構下數(shù)據(jù)共享好處，對中間結果無效。 二 ：如果由于計算任務之間需要，需要在任務之間傳遞中間結果，則即使是SD架構也存在數(shù)據(jù)重分布的問題，主要是中間結果重分布，也就是中間結果傳輸。 另外從該過程我們還可以得出另外一個結論： 一： 對于復雜的數(shù)據(jù)處理，索引只能影響第一級計算，對于中間結果，由于只使用一次，因此沒有必要去針對中間結果建立索引。也就是即使我們將數(shù)據(jù)存儲在關系型數(shù)據(jù)庫中，也只有第一級計算能有效利用數(shù)據(jù)庫索引。 二：即使采用并行數(shù)據(jù)庫，如果我們的整個計算過程不能用一個SQL語句來表達，則我們必須自己解決中間結果的劃分與并性計算的問題。
(6)并行計算引擎架構與資源管理 所有并行計算引擎實現(xiàn)基本上都是主從結構，即一個MASTER + 多個slave節(jié)點的結構。由client向MASTER提交一個job,然后由Master負責將邏輯執(zhí)行計劃變成實際執(zhí)行計劃，并由Master負責將各個任務分發(fā)到各個slave中，并負責各個任務的調度。 MPP數(shù)據(jù)庫查詢引擎架構
MAPREDUCE架構和該架構缺點 Mapreduce框架中，JobTracker承當MASTER的職責，一般和HDFS中的NadeNode節(jié)點安裝在一個服務器上。TaskTracker安裝在各個DataNode上，承擔Slave的角色。
流程如下： (1)首先用戶程序(Client Program)提交了一個job，job的信息會發(fā)送到Job Tracker中，Job Tracker是Map-reduce框架的中心，他需要與集群中的機器定時通信(heartbeat), 需要管理哪些程序應該跑在哪些機器上，需要管理所有job失敗、重啟等操作。 (2)TaskTracker是Map-reduce集群中每臺機器都有的一個部分，他做的事情主要是監(jiān)視自己所在機器的資源情況(資源的表示是“本機還能起多少個map-task，多少個reduce-task”，每臺機器起map/reduce task的上限是在建立集群的時候配置的)，另外TaskTracker也會監(jiān)視當前機器的tasks運行狀況。 (3)TaskTracker需要把這些信息通過heartbeat發(fā)送給JobTracker，JobTracker會搜集這些信息以給新提交的job分配運行在哪些機器上。 MAPREDUCE結構存在以下缺點： (1) jobtracker只能安裝在一臺服務器上，集中式作業(yè)控制導致可擴展性不好，另外JobTracker負責事情太多，容易成為性能瓶頸。 (2) 資源調度與編程模型緊耦合，只支持MAPREDUCE一種編程模型。 (3) 資源劃分太簡單，每個TaskTracker只是簡單把整個機器資源按map task slot和reduce task slot來劃分，而沒有考慮不通任務所需的內(nèi)存和CPU等的資源不同。 針對上述特點，hadoop平臺開發(fā)通用的資源管理器yarn，只負責資源管理和分配，即通過把jobtrack中的資源管理分配自和并行應用程序調度與控制分離，從而實現(xiàn)雙層調度框架：由yarn把資源分配給各計算引擎MASTER，再由MASTER分配給各個TASK。
資源管理器YARN
流程如下： 1) client 通過一個CLC (container launch context )向ResourceManager提交一個應用 2)RM 啟動該應用的 AplicationMaster。 AplicationMaster啟動后先向ResourceManager注冊，并利用心跳信息，定期向ResourceManager報告自己存活性和資源分配請求 3)ResourceManager分配一個container(container包括CPU個數(shù)和所需內(nèi)存數(shù)量)時， AplicationMaster構造一個CLC,并在該container對應機器上Nodemanager上啟動該container。AplicationMaster 監(jiān)控該container的運行狀態(tài)，并且該資源需要被回收時，由AplicationMaster停止該container。 監(jiān)控container內(nèi)部的作業(yè)的執(zhí)行進度是AplicationMaster的職責。 4)一旦整個運行完畢，AM從RM中解除注冊，并且干凈退出。 這種架構優(yōu)點是： 優(yōu)點一：減小了JobTracker(也就是現(xiàn)在的ResourceManager)的資源消耗，并且讓監(jiān)測每一個Job子任務(tasks)狀態(tài)的程序分布式化了，更安全、更優(yōu)美。也就是ApplicationMaster是每個應用一個，并且不通應用對應的ApplicationMaster的實例可以運行在不同服務器上。 優(yōu)點二：能夠支持不同的編程模型ApplicationMaster是一個可變更的部分，用戶可以對不同的編程模型寫自己的ApplicationMaster，讓更多類型的編程模型能夠跑在Hadoop集群中。 優(yōu)點三：對于資源的表示比之前以剩余slot數(shù)目更合理。 3) 存儲層 數(shù)據(jù)存儲層主要包括以下幾類： 一類是基于MPP數(shù)據(jù)庫集群，這類系統(tǒng)特點是存儲層與上層并型計算引擎是緊耦合，屬于封閉性的系統(tǒng)。 二是采用分布式文件系統(tǒng)，例如SharK、Stinger、HIVE、Impala、Scope等。Shark、Stinger、Hive、Imapla都采用HDFS文件系統(tǒng)作為存儲層，Scope采用微軟自己開發(fā)的分布式文件系統(tǒng)。此類系統(tǒng)特點是存儲層與上層計算引擎層之間是松耦合關系。 三是存儲層基于單機版本關系數(shù)據(jù)庫，例如CitusDB采用PostSQL數(shù)據(jù)庫系統(tǒng)、shardquery采用Mysql數(shù)據(jù)庫系統(tǒng)。此類系統(tǒng)類似于一個中間件，也可以認為上層和底層存儲層屬于松耦合關系。 四是可以支持各種異構的存儲系統(tǒng)，例如Presto、Tenzing。Presto設計即支持HDFS也支持存儲在Mysql中的數(shù)據(jù)，但是目前只支持HDFS;Tenzing底層支持：Google File System、MySQL、Bigtable。 不同存儲系統(tǒng)對上層計算有一些影響，典型如Tenzing系統(tǒng)會利用底層存儲系統(tǒng)的一些特性： (1)例如如果低層是mysql數(shù)據(jù)庫，則可以直接利用mysql索引來過濾 (2)如果底層是bigtable數(shù)據(jù)庫，則可以直接利用bigtable 范圍scan來過濾 (3)如果底層是列存儲系統(tǒng)，則可以只掃描需要掃描的列。 (4)如果底層是列存儲系統(tǒng)，且頭文件里面有該列最大值和最小值，則可以利用該信息直接跳過某些文件的掃描。 另外需要指出的是，目前已上所有系統(tǒng)都有一個趨勢就是采用列式存儲。例如HIVE開發(fā)了行列混合的RCFILE文件格式(先按行劃分，保證每行的數(shù)據(jù)不會垮機器存儲，然后再按劣存儲)，shark系統(tǒng)開發(fā)了內(nèi)存中的列式存儲格式，citusDB開發(fā)了專用postSQL數(shù)據(jù)庫的列式存儲引擎。 1) JethroData系統(tǒng) JethroData的特點是hadoop+index。該系統(tǒng)對存儲在HDFS上的結構化數(shù)據(jù)建立索引，并把索引文件也以普通文件方式存儲在HDFS系統(tǒng)，并在查詢處理時采取以下過程： (1) 查詢主節(jié)點負責分析SQL語句后，針對sql中的where條件部分，利用索引文件來得到符合where過濾條件后的rowid集合。 (2) 該rowid集合涉及各datanode節(jié)點，采用并發(fā)方式來讀取數(shù)據(jù)。 (3) 所有數(shù)據(jù)匯總到查詢主節(jié)點，進行匯總與計算，并將最終結果返回給客戶端。 可以看出，由于該系統(tǒng)設計思路是希望通過索引來加速數(shù)據(jù)選擇，因此只適合每次查詢處理只涉及少量一部分數(shù)據(jù)。 2) Druid系統(tǒng) 本系統(tǒng)是美國metamarket公司開發(fā)的面向海量數(shù)據(jù)的實時統(tǒng)計分析系統(tǒng)，以實現(xiàn)針對上億級別海量數(shù)據(jù)統(tǒng)計分析的延遲在1秒以內(nèi)。該系統(tǒng)于2012年10月開源。該系統(tǒng)可以認為是一個分布式的內(nèi)存OLAP系統(tǒng)。 該系統(tǒng)主要分析的數(shù)據(jù)為交易記錄，每條交易記錄包括三個部分：交易發(fā)生的時間點、多個維度屬性、多個數(shù)值型度量屬性。例如：
該系統(tǒng)設計用來可以回答以下問題“有多少個針對Justin Bieber的編輯來自San Francisco? ”、“一個月內(nèi)來自Calgary的增加編輯字數(shù)的平均數(shù)是多少?”。而且要求：能夠在高并發(fā)環(huán)境下，在1秒以內(nèi)完成任意維度組合的統(tǒng)計，且保證系統(tǒng)高可用;還系統(tǒng)還要能夠具備實時數(shù)據(jù)分析能力，也就是能夠查詢分析到最新的數(shù)據(jù)，延時時間為秒級。 為了達到上述目標，該公司先后通過測試發(fā)現(xiàn)關系數(shù)據(jù)庫技術和NOSQL數(shù)據(jù)庫都無法滿足其需求。關系型數(shù)據(jù)庫由于磁盤io瓶頸導致性能無法滿足需求，而NOSQL數(shù)據(jù)庫雖然可以采用預計算方法來達到高性能，但是預計算無法滿足分析需求靈活多變。 為解決該問題，該公司自己開發(fā)DRUID系統(tǒng)，主要技術思路如下： (1)將原始數(shù)據(jù)(alpha數(shù)據(jù))進行一定粒度合并，合并成beta數(shù)據(jù)。 (2)將beta數(shù)據(jù)全部放入內(nèi)存，并通過分布式內(nèi)存方式解決單臺服務器內(nèi)存 上限問題。 (3) 針對緯度屬性建立索引，以加速數(shù)據(jù)的選取。 (4) 采用分布式方式進行并行統(tǒng)計，為了保證分布式統(tǒng)計高效，該系統(tǒng)不支持join，而且對聚合計算不支持中位數(shù)等無法分布計算的聚合計算函數(shù)。 (5) 利用數(shù)據(jù)復制解決系統(tǒng)高可靠性問題。 1) MPP并行數(shù)據(jù)庫得益于流水線的執(zhí)行以及基于統(tǒng)計優(yōu)化等方面，使得MPP并行數(shù)據(jù)庫的執(zhí)行效率是最高的。但缺點包括： · 數(shù)據(jù)導入時間長，導入時要做各種預處理，例如一些統(tǒng)計信息; · 執(zhí)行引擎和存儲緊耦合導致數(shù)據(jù)難以被其他分析引擎進行分析; · 基于樹型結構執(zhí)行計劃，導致MPP并行數(shù)據(jù)庫表達能力有限，更適合做統(tǒng)計與查詢，而不適合數(shù)據(jù)分析處理; · 容錯性差，特別是一個任務涉及數(shù)據(jù)量越大，該缺陷越明顯。 2)HIVE、Tenzing、Shark、SCOPE、Stinger等系統(tǒng)可以認為基本屬于同一類系統(tǒng)。這類系統(tǒng)共同特點是：”通用并行計算引擎框架+SQL解析層”。并且可以將HIVE、Tenzing看成是基于第一代系統(tǒng)，而Shark、Scope、Stinger是第二代系統(tǒng)。這一類系統(tǒng)特點如下： · 存儲層、執(zhí)行引擎層、SQL解析層三者分離，可以方便替換執(zhí)行引擎，對使用者而言，同一份數(shù)據(jù)可以采用不同并行執(zhí)行引擎來分析。 · 在執(zhí)行效率方面，由于存儲和上層分離因此一半只能具備邏輯優(yōu)化能力，另外由于Tree結構執(zhí)行計劃更容易采用流水線執(zhí)行方式，因此這類系統(tǒng)執(zhí)行效率總體來講不如MPP關系數(shù)據(jù)庫，它們之間排序是MPP數(shù)據(jù)庫 > 第二代系統(tǒng) > 第一代系統(tǒng)。 · 在執(zhí)行效率方面，另外一點是這類系統(tǒng)一般內(nèi)置對索引的支持不是太好或者不支持。 · 在大規(guī)模計算容錯方面，這類系統(tǒng)要優(yōu)于MPP關系數(shù)據(jù)庫。 3)Impala、Dremel等可以認為屬于同一類系統(tǒng)，此類系統(tǒng)介于前兩者系統(tǒng)之間。這類系統(tǒng)特點是： · 和MPP數(shù)據(jù)庫類似，基于Tree結構執(zhí)行計劃，專注于查詢統(tǒng)計，因此效率高于第二類系統(tǒng)，但是可能和第二類系統(tǒng)的第二代相當。 · 與MPP數(shù)據(jù)庫不同的是這類系統(tǒng)只是一個引擎，與存儲系統(tǒng)松耦合。也就是SQL解析層與執(zhí)行層緊偶合，然后和存儲層松藕合。 · 只適合做中間結果越來越小查詢分析，中間結果都放內(nèi)存，對內(nèi)存要求較高，例如無法實現(xiàn)大表之間的join。 因此，在大型互聯(lián)網(wǎng)企業(yè)中，數(shù)據(jù)量太大，就會出現(xiàn)所謂“高價值、低密度”情況，反映到數(shù)據(jù)處理上，互聯(lián)網(wǎng)企業(yè)不會長期存儲原始數(shù)據(jù)，而是會把原始數(shù)據(jù)先經(jīng)過一部分預處理，經(jīng)過部分提煉后，把提煉后數(shù)據(jù)進行長期存儲和分析。也就是如下流程:
例如淘寶，把每天數(shù)據(jù)直接寫入Hadoop平臺，然后通過每天運行相對固定mapreduce作業(yè)來做ETL，然后在計算結果基礎上為提供各種分析功能。其中海量原始數(shù)據(jù)經(jīng)過固定ETL后被刪除，由于只使用一次，因此沒有必要花很大精力把這些數(shù)據(jù)整理成適合分析與挖掘格式。例如在這種場景下，索引也沒有太大的價值，因此沒有必要花費大量代價來建立索引。 MPP并行數(shù)據(jù)庫，適合存儲高密度價值數(shù)據(jù)，并且是長期存儲和多次使用，所以MPP并行數(shù)據(jù)庫會花大量經(jīng)歷在Load階段，把數(shù)據(jù)處理成適合分析格式 。 通過上述系統(tǒng)地介紹與比較，我們可以得出一個這樣結論：在大數(shù)據(jù)領域，沒有一個通用的解決方案，而需要根據(jù)具體業(yè)務場景，選擇合適的技術! 4)通過上述系統(tǒng)研究，我們可以發(fā)現(xiàn)一點就是Join操作，特別是大表之間join操作是最消耗資源，也是最優(yōu)化難度較高的操作，特別是在并行join的實現(xiàn)難度較大。例如Druid和Dremel等都基本放棄了join操作。 因此個人認為應該從業(yè)務上和從數(shù)據(jù)預處理方面，通過適當數(shù)據(jù)冗余來盡量避免在分析過程過程中執(zhí)行join操作。 數(shù)據(jù)分析挖掘主要涉及兩個方面：一是數(shù)據(jù)預處理;二是數(shù)據(jù)挖掘。 在數(shù)據(jù)預處理方面，根據(jù)掌握資料來看，大型互聯(lián)網(wǎng)公司主要以MapReduce、Storm等計算框架為主，這些平臺可以較好解決大數(shù)據(jù)預處理面臨并行計算和處理靈活性的問題。但是個人認為spark、tez等屬于MapReduce升級版本，因此后面這些計算框架在這方面的應用會越來越廣泛。 在數(shù)據(jù)挖掘算法執(zhí)行方面，主要問題解決數(shù)據(jù)挖掘算法并行計算問題。早期在數(shù)據(jù)挖掘算法并行化方面項目主要是Mahout項目，該項目基于MAPREDUC 并行計算框架實現(xiàn)了推薦、分類等常用數(shù)據(jù)挖掘算法的并行化。 但由于數(shù)據(jù)挖掘算法存在以下兩個方面特點導致基于MAPREDUCE框架來做數(shù)據(jù)數(shù)據(jù)挖掘算法執(zhí)行引擎效率不高：一是機器學習算法一般比較復雜，通常需要多次迭代計算，而MapReduce框架的步步物化導致中間結果會反復的序列化和反序列化導致效率不高;二是數(shù)據(jù)與數(shù)據(jù)之間依賴特別多，在計算過程中機器與機器之間的通訊非常多，而MapReduce框架下Map與Reduce之間存在路障同步, 導致大量時間被消耗在同步等待上面，效率不高。 因此目前Mahout項目在2014年1月份在0.9版本發(fā)布后，該項目拋棄了MAPREDUCE框架，轉而采用SPARK作為底層計算框架。
除Mahout項目外，SPARK自己采用SPARK專門針對機器學習領域開發(fā)MLlib項目。但是MLlib項目出現(xiàn)時間比較晚，因此在成熟度方面不如Mahout。 Mahout項目目前支持的數(shù)據(jù)挖掘算法如下：
MLLib支持的數(shù)據(jù)挖掘算法包括：
在數(shù)據(jù)分析處理領域，隨社交網(wǎng)絡興起，對圖數(shù)據(jù)處理的需求越來越多。例如像Facebook和Twitter這樣的社交網(wǎng)絡，其數(shù)據(jù)天生就適合于圖表示法。對圖數(shù)據(jù)的處理和傳統(tǒng)數(shù)據(jù)庫處理一樣，也可以分為兩種類型的需求： 4 本章總結OLTP工作負載，能夠快速低延遲訪問小部分圖數(shù)據(jù)。 4 本章總結OLAP工作負載，能夠對圖對象中的大部分數(shù)據(jù)進行批量分析與處理。 1) 圖數(shù)據(jù)OLTP處理 (1) 圖數(shù)據(jù)庫分類 適合圖書據(jù)OLTP處理的系統(tǒng)，主要是各種圖數(shù)據(jù)庫。從目前來看圖數(shù)據(jù)庫主要可以分為兩類： 一是基于圖存儲模型的專用圖數(shù)據(jù)庫，如Neo4j、OrientDB、Infinite Graph等; 二是以通用KV存儲系統(tǒng)或者關系數(shù)據(jù)庫系統(tǒng)開發(fā)的圖數(shù)據(jù)庫，例如Titan系統(tǒng)(2013年推出)可以后端存儲可以基于HBASE或者是Cassandra，Twitter公司的FlockDB圖形數(shù)據(jù)庫和facebook公司Tao圖形數(shù)據(jù)庫是基于mysql來進行開發(fā)。根據(jù)報道美國NSA就是利用2011年開源的Apache Accumulo(屬于分布式KV數(shù)據(jù)庫)來存儲社會關系網(wǎng)絡數(shù)據(jù)。 (2) 圖數(shù)據(jù)查詢 圖數(shù)據(jù)查詢其實就是”遍歷”圖(Traverse)。圖數(shù)據(jù)庫查詢語言可以使用Gremlin、Cypher等查詢語言來查詢圖。例如Neo4j就支持Cypher查詢語言。 Cyper查詢語言需要以一個節(jié)點來啟動(START)查詢，然后使用MATCH關鍵詞以WHERE關鍵字過濾節(jié)點或者關系的屬性，最后以RETRUN關鍵詞來指定查詢所返回的數(shù)據(jù)是節(jié)點、關系還是節(jié)點或者關系的屬性字段。例如： START barbara = node:nodeindex(name=”Barbara”); (3) 兩類圖數(shù)據(jù)庫區(qū)別 第一類與第二類圖數(shù)據(jù)庫區(qū)別在于以下幾點： 查詢功能方面 第一類圖數(shù)據(jù)庫可以以非常高效率方式支持復雜查詢，既支持從指定起點開始，以任意深度來遍歷圖，并且還可以支持各種過濾。這樣就可以很方便的執(zhí)行各種圖專用查詢?nèi)蝿眨纭安檎覂蓚€節(jié)點間所有路徑或者最短路徑”等。相反第二類數(shù)據(jù)庫則只能支持較為簡單查詢，如FlockDB就只支持深度為1的關系遍歷(個人認為也可以實現(xiàn)，只是效率不高)。 可擴展性方面 大部分第一種圖形數(shù)據(jù)庫都不支持分布，個人認為可能分布后這種復雜查詢難以做到高效，因此可擴展性不好。而第二種由于只支持簡單的圖便歷，一般通過采取按“邊”切分的方法來進行分布存儲，因此可擴展性較好。 2) 圖數(shù)據(jù)OLAP處理 對圖數(shù)據(jù)進行復雜分析，就需要分布式的批處理框架。例如大規(guī)模的PageRank計算。在這個領域出現(xiàn)并行圖計算框架常見有Apache Giraph、Apache Hama、GraphLab、Pregel、GraphX等。 Pregel是Google根據(jù)BSP并行計算模型開發(fā)的圖計算引擎，目前該系統(tǒng)沒有開源。GraphX是Spark項目組基于Spark框架開發(fā)的圖計算引擎;而GraphLab則是直接在MPI框架基礎上開發(fā)的專用圖計算引擎。 下面簡單介紹幾種主流并行圖計算引擎。 1) 基于BSP模型的Pregel引擎 簡介 Pregel是Google公司開發(fā)的并行圖計算引擎，主要用于實現(xiàn)各種機器學習算法。Pregel的輸入是一個有向圖，該有向圖每一個頂點都有一個相應由String描述的頂點標識符。每一個頂點都有一個與之對應可修改用戶自定義值。每一條有向邊都和其源頂點關聯(lián)，并且也擁有一個可修改的用戶自定義值，并同時還記錄了其目標頂點的標識符。 Pregel可以采用多種文件格式進行圖的保存，比如可以用text文件、關系數(shù)據(jù)庫、Bigtable。為了避免規(guī)定死一種特定文件格式，Pregel將從輸入中解析出圖結構的任務從圖的計算過程中進行了分離。計算結果可以以任何一種格式輸出并根據(jù)應用程序選擇最適合的存儲方式。Pregel library本身提供了很多常用文件格式的readers和writers，但是用戶可以通過繼承Reader和Writer類來定義他們自己的讀寫方式。 編寫一個Pregel程序需要繼承Pregel中已預定義好的一個基類——Vertex類。
用戶覆寫Vertex類的虛函數(shù)Compute()，該函數(shù)會在每一個超級步中對每一個頂點進行調用。預定義的Vertex類方法允許Compute()方法查詢當前頂點及其邊的信息，以及發(fā)送消息到其他的頂點。Compute()方法可以通過調用GetValue()方法來得到當前頂點的值，或者通過調用MutableValue()方法來修改當前頂點的值。同時還可以通過由出邊的迭代器提供的方法來查看修改出邊對應的值。 基于BSP的執(zhí)行模型 讀取輸入初始化該圖，當圖被初始化好后，運行一系列的超級步直到整個計算結束，這些超級步之間通過一些全局的同步點分隔，輸出結果結束計算。 在每個超級步中，頂點的計算都是并行的，每個頂點執(zhí)行相同的用于表達給定算法邏輯的用戶自定義函數(shù)。每個頂點可以修改其自身及其出邊的狀態(tài)，接收前一個超級步(S-1)中發(fā)送給它的消息，并發(fā)送消息給其他頂點(這些消息將會在下一個超級步中被接收)，甚至是修改整個圖的拓撲結構。邊，在這種計算模式中并不是核心對象，沒有相應的計算運行在其上。 算法是否能夠結束取決于是否所有的頂點都已經(jīng)“vote”標識其自身已經(jīng)達到“halt”狀態(tài)了。在第0個超級步，所有頂點都處于active狀態(tài)，所有的active頂點都會參與所有對應superstep中的計算。頂點通過將其自身的status設置成“halt”來表示它已經(jīng)不再active。這就表示該頂點沒有進一步的計算需要執(zhí)行，除非被再次被外部觸發(fā)，而Pregel框架將不會在接下來的superstep中執(zhí)行該頂點，除非該頂點收到其它頂點傳送的消息。如果頂點接收到消息被喚醒進入active狀態(tài)，那么在隨后的計算中該頂點必須顯式的deactive。整個計算在所有頂點都達到“inactive”狀態(tài)，并且沒有message在傳送的時候宣告結束。
2) graphLab (1) 簡介 GraphLab一套基于c++的開源圖計算庫，提供了在共享內(nèi)存情況下的異步、動態(tài)和并行圖計算的高層抽象API。該庫采用MPI和TCPIP來實現(xiàn)進程間通訊，采用Pthreads實現(xiàn)進程內(nèi)的多線程并發(fā)計算，支持從HDFS和標準文件系統(tǒng)中讀取數(shù)據(jù)。GraphLab定義了多種用于存儲圖的文件格式，包括'tsv','snap', 'adj' 'bintsv4'。
(2) 與Pregel的不同 GraphLab不是采用BSP的嚴格執(zhí)行模型，GraphLab的基于BSP的Pregel的典型的改進是在更好的“異步迭代計算”和“動態(tài)計算”。因此該框架計算效率比Pregel更好。 異步計算：很多重要的MLDM算法迭代更新一大批參數(shù)，圖結構導致參數(shù)更新依賴其它的參數(shù)。同步系統(tǒng)會以上一次更新的參數(shù)基礎上一次更新所有的參數(shù)(BSP模型中超級步之間市全局路障同步)，而異步系統(tǒng)則以最近的參數(shù)作為輸入來更新參數(shù)。異步迭代更新可以極大加 快MLDM算法的計算速度。因為如果采用同步計算，則存在木桶效應，整體速度取決于最慢的那臺機器。在大規(guī)模云計算環(huán)境下，負載不均衡、網(wǎng)絡不均衡、硬件差異和多租戶等會導致不同 機器之間的速度存在差異。另外由于圖分割不均衡，以及計算復雜性等導致各個節(jié)點計算量也不均衡。 動態(tài)計算：很多MLDM算法的迭代計算收斂都不對稱，例如在參數(shù)優(yōu)化是，通常很多參數(shù)在很少幾次迭代中就會快速收斂，而剩下少數(shù)參數(shù)則即使經(jīng)過多次迭代也會收斂很慢。因此如果我們等同更新所有的參數(shù)，則會浪費大量的時間在重復計算那些已近收斂的參數(shù)上。最近的一些計算框架部分支持動態(tài)計算，例如Pregel可以通過讓某些節(jié)點跳過一些超級步來部分支持動態(tài)計算。 (3) GraphLab的計算模型 graphLab包括三個部分：數(shù)據(jù)圖、更新函數(shù)、同步操作。數(shù)據(jù)圖表達用戶可修改 的程序狀態(tài)，存儲可變的用戶自定義數(shù)據(jù)和計算之間依賴。更新函數(shù)通過一個scope的數(shù)據(jù)變換來表達用戶對數(shù)據(jù)圖的計算和操作。同步操作并發(fā)維護全局匯總。 一個點的scope代表存儲在這個點上的數(shù)據(jù) 和所有與這個點相鄰的點和邊上的所有數(shù)據(jù)。update f (v ,s(v) ) ---> (s(v) , 邊集合) 。經(jīng)過一個更新函數(shù)后，新計算出 的s(v) 會被寫回圖，并返回一個定點集合，針對該集合的每個點再執(zhí)行 f(u ,s(u))
為了更高效的并行執(zhí)行，GraphLab容許GraphLab框架動態(tài)的選擇執(zhí)行順序，即RemoveNext(T)的返回值。因為很多MLDM算法需要執(zhí)行優(yōu)先級別，因此也可以指定點的優(yōu)先級，這樣GraphLab會綜合考慮優(yōu)先級以及網(wǎng)絡情況來調度。 (3) GraphLab的并行計算 根據(jù)領域知識，將圖分割為K份，K值遠大于機器數(shù)量。每個分區(qū)被稱為atom, 以一個文件形式存儲類似HDFS的分布式文件系統(tǒng)上。Atom中存儲的是增加點和變的操作記錄，可以通過回放的方式來重構圖。 采取把點著色的方法，先保證每個點和相鄰點之間的顏色都不相同。通過一個顏色一個顏色的并發(fā)執(zhí)行，來實現(xiàn)邊一致性。把這種成為顏色步，與BSP的超步模型相對應。該引擎保證在執(zhí)行下一個顏色步之前，所有的修改都被傳遞，實現(xiàn)顏色步之間的路障同步。 由Master根據(jù)atom索引來計算atom的位置，并負責機器與atom之間的分配關系。然后每個機器讀取atom文件來加載圖。每個機器上有一個調度器負責調度屬于自己的子圖的點的計算。調度器負責把每個需要執(zhí)行update 函數(shù)之前所需要的數(shù)據(jù)和鎖準備好后，放入一個流水處理隊列中，再由一個worker線程池來執(zhí)行，通過一個分布式算法來確定所有機器上的調度器中的T為空，也就是整個計算結束。 3)graphX
基于SPARK圖形計算引擎，GraphX提供的API可以很方便的表達各種針對的轉換、過濾和查詢操作，但是GraphX不能直接實現(xiàn)迭代并行圖計算算法，但是可以基于這些API用來實現(xiàn)各種并行圖計算算法。在GraphX論文中描述了利用GraphX來實現(xiàn)Pregel、PowerGraph的方法。 GraphX的優(yōu)勢是可以很方便的與shark等進行集成，例如直接對shark查詢后的結果進行圖計算。
4) 總結 (1)上述計算引擎都可以以靈活方式來存儲圖，基本上都可以以文件方式來存儲圖數(shù)據(jù)，實現(xiàn)計算引擎與存儲分離。 (2)圖計算引擎都根據(jù)MDML算法特點采用專用計算模型，以提高效率。 (3) 所有圖計算引擎在計算時，基本都是需要把數(shù)據(jù)都加載到內(nèi)存中。(來自preglel論文：當前整個的計算狀態(tài)都是駐留在內(nèi)存中的。我們已經(jīng)開始將一些數(shù)據(jù)存到本地磁盤，同時我們會繼續(xù)在這個方向進行深入的研究，希望可以支持規(guī)模太大以至于內(nèi)存無法完全存下的情況。 |
|
|
