在我們實(shí)際生活中，事務(wù)型數(shù)據(jù)處理需求非常常見，例如：淘寶網(wǎng)站交易系統(tǒng)、12306網(wǎng)站火車票交易系統(tǒng)、超市POS系統(tǒng)等都屬于事務(wù)型數(shù)據(jù)處理系統(tǒng)。

這類系統(tǒng)數(shù)據(jù)處理特點(diǎn)包括以下幾點(diǎn)：

一是事務(wù)處理型操作都是細(xì)粒度操作，每次事務(wù)處理涉及數(shù)據(jù)量都很小。

二是計算相對簡單，一般只有少數(shù)幾步操作組成，比如修改某行的某列;

三是事務(wù)型處理操作涉及數(shù)據(jù)的增、刪、改、查，對事務(wù)完整性和數(shù)據(jù)一致性要求非常高。

四是事務(wù)性操作都是實(shí)時交互式操作，至少能在幾秒內(nèi)執(zhí)行完成;

五是基于以上特點(diǎn)，索引是支撐事務(wù)型處理一個非常重要的技術(shù)。

在數(shù)據(jù)量和并發(fā)交易量不大情況下，一般依托單機(jī)版關(guān)系型數(shù)據(jù)庫，例如ORACLE、MYSQL、SQLSERVER，再加數(shù)據(jù)復(fù)制(DataGurad、 RMAN、MySQL數(shù)據(jù)復(fù)制等)等高可用措施即可滿足業(yè)務(wù)需求。

在數(shù)據(jù)量和并發(fā)交易量增加情況下，一般可以采用ORALCE RAC集群方式或者是通過硬件升級(采用小型機(jī)、大型機(jī)等，如銀行系統(tǒng)、運(yùn)營商計費(fèi)系統(tǒng)、證卷系統(tǒng))來支撐。

事務(wù)型操作在淘寶、12306等互聯(lián)網(wǎng)企業(yè)中，由于數(shù)據(jù)量大、訪問并發(fā)量高，必然采用分布式技術(shù)來應(yīng)對，這樣就帶來了分布式事務(wù)處理問題，而分布式事務(wù)處理很難做到高效，因此一般采用根據(jù)業(yè)務(wù)應(yīng)用特點(diǎn)來開發(fā)專用的系統(tǒng)來解決本問題。

數(shù)據(jù)統(tǒng)計主要是被各類企業(yè)通過分析自己的銷售記錄等企業(yè)日常的運(yùn)營數(shù)據(jù)，以輔助企業(yè)管理層來進(jìn)行運(yùn)營決策。典型的使用場景有：周報表、月報表等固定時間提供給領(lǐng)導(dǎo)的各類統(tǒng)計報表;市場營銷部門，通過各種維度組合進(jìn)行統(tǒng)計分析，以制定相應(yīng)的營銷策略等。

數(shù)據(jù)統(tǒng)計分析特點(diǎn)包括以下幾點(diǎn)：

一是數(shù)據(jù)統(tǒng)計一般涉及大量數(shù)據(jù)的聚合運(yùn)算，每次統(tǒng)計涉及數(shù)據(jù)量會比較大。

二是數(shù)據(jù)統(tǒng)計分析計算相對復(fù)雜，例如會涉及大量goupby、 子查詢、嵌套查詢、窗口函數(shù)、聚合函數(shù)、排序等;有些復(fù)雜統(tǒng)計可能需要編寫SQL腳本才能實(shí)現(xiàn)。

三是數(shù)據(jù)統(tǒng)計分析實(shí)時性相對沒有事務(wù)型操作要求高。但除固定報表外，目前越來越多的用戶希望能做做到交互式實(shí)時統(tǒng)計;

傳統(tǒng)的數(shù)據(jù)統(tǒng)計分析主要采用基于MPP并行數(shù)據(jù)庫的數(shù)據(jù)倉庫技術(shù)。主要采用維度模型，通過預(yù)計算等方法，把數(shù)據(jù)整理成適合統(tǒng)計分析的結(jié)構(gòu)來實(shí)現(xiàn)高性能的數(shù)據(jù)統(tǒng)計分析，以支持可以通過下鉆和上卷操作，實(shí)現(xiàn)各種維度組合以及各種粒度的統(tǒng)計分析。

另外目前在數(shù)據(jù)統(tǒng)計分析領(lǐng)域，為了滿足交互式統(tǒng)計分析需求，基于內(nèi)存計算的數(shù)據(jù)庫倉庫系統(tǒng)也成為一個發(fā)展趨勢，例如SAP的HANA平臺。

數(shù)據(jù)挖掘主要是根據(jù)商業(yè)目標(biāo)，采用數(shù)據(jù)挖掘算法自動從海量數(shù)據(jù)中發(fā)現(xiàn)隱含在海量數(shù)據(jù)中的規(guī)律和知識。

數(shù)據(jù)挖掘主要過程是：根據(jù)分析挖掘目標(biāo)，從數(shù)據(jù)庫中把數(shù)據(jù)提取出來，然后經(jīng)過ETL組織成適合分析挖掘算法使用寬表，然后利用數(shù)據(jù)挖掘軟件進(jìn)行挖掘。傳統(tǒng)的數(shù)據(jù)挖掘軟件，一般只能支持在單機(jī)上進(jìn)行小規(guī)模數(shù)據(jù)處理,受此限制傳統(tǒng)數(shù)據(jù)分析挖掘一般會采用抽樣方式來減少數(shù)據(jù)分析規(guī)模。

數(shù)據(jù)挖掘的計算復(fù)雜度和靈活度遠(yuǎn)遠(yuǎn)超過前兩類需求。一是由于數(shù)據(jù)挖掘問題開放性，導(dǎo)致數(shù)據(jù)挖掘會涉及大量衍生變量計算，衍生變量多變導(dǎo)致數(shù)據(jù)預(yù)處理計算復(fù)雜性;二是很多數(shù)據(jù)挖掘算法本身就比較復(fù)雜，計算量就很大，特別是大量機(jī)器學(xué)習(xí)算法，都是迭代計算，需要通過多次迭代來求最優(yōu)解，例如K-means聚類算法、PageRank算法等。

因此總體來講，數(shù)據(jù)分析挖掘的特點(diǎn)是:

1、數(shù)據(jù)挖掘的整個計算更復(fù)雜，一般是由多個步驟組成計算流，多個計算步驟之間存在數(shù)據(jù)交換，也就是會產(chǎn)生大量中間結(jié)果，難以用一條sql語句來表達(dá)。

2、計算應(yīng)該能夠非常靈活表達(dá)，很多需要利用高級語言編程實(shí)現(xiàn)。

在google、facebook、taobao等大互聯(lián)網(wǎng)公司出現(xiàn)之后，這些公司注冊和在線用戶數(shù)量都非長大，因此該公司交易系統(tǒng)需要解決“海量數(shù)據(jù)+高并發(fā)+數(shù)據(jù)一致性+高可用性”的問題。

為了解決該問題，從目前資料來看，其實(shí)沒有一個通用的解決方案，各大公司都會根據(jù)自己業(yè)務(wù)特點(diǎn)定制開發(fā)相應(yīng)的系統(tǒng),但是常用的思路主要包括以下幾點(diǎn)：

(1)數(shù)據(jù)庫分片，結(jié)合業(yè)務(wù)和數(shù)據(jù)特點(diǎn)將數(shù)據(jù)分布在多臺機(jī)器上。

(2)利用緩存等機(jī)制，盡量利用內(nèi)存，解決高并發(fā)時遇到的隨機(jī)IO效率問題。

(3)結(jié)合數(shù)據(jù)復(fù)制等技術(shù)實(shí)現(xiàn)讀寫分離，以及提高系統(tǒng)可用性。

(4)大量采用異步處理機(jī)制，對應(yīng)高并發(fā)沖擊。

(5)根據(jù)實(shí)際業(yè)務(wù)需求，盡量避免分布式事務(wù)。

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)(以前調(diào)研過)，由于陳思儒離開阿里去了盛大，阿里當(dāng)心“變形蟲”穩(wěn)定性等問題，重新開發(fā)該項(xiàng)目。

該系統(tǒng)主要采用數(shù)據(jù)庫分片思路，實(shí)現(xiàn)了：數(shù)據(jù)拆分、讀寫分離、復(fù)制等功能。由于此系統(tǒng)由于只需要滿足事務(wù)型操作即可，因此相對真正并行數(shù)據(jù)庫集群(例如TeraData等)，此類系統(tǒng)提供操作沒有也不需要提供一些復(fù)雜跨庫處理，因此該系統(tǒng)存在以下限制：

(1)不支持跨庫的join、分頁、排序、子查詢。

(2)insert等變更語句必須包括拆分字段等。

(3)應(yīng)該不支持跨機(jī)事務(wù)(以前變形蟲不支持)。

說白了此類系統(tǒng)不具備并行計算能力,基本上相當(dāng)于數(shù)據(jù)庫路由器!

另外此類系統(tǒng)的在實(shí)際應(yīng)用的關(guān)鍵問題是，根據(jù)什么對數(shù)據(jù)進(jìn)行切分，因?yàn)榍蟹植缓脮?dǎo)致分布式的事務(wù)問題。

2) 阿里OceanBase系統(tǒng)

該系統(tǒng)也是淘寶為了解決高并發(fā)、大數(shù)據(jù)環(huán)境下事務(wù)型處理而定制開發(fā)的一個系統(tǒng)。該系統(tǒng)主要思路和特點(diǎn)如下：

(1)他們發(fā)現(xiàn)在實(shí)際生成環(huán)境中，每天更新的數(shù)據(jù)只占總體數(shù)據(jù)的1%不到，因此他們把數(shù)據(jù)分為：基線數(shù)據(jù)和增量更新數(shù)據(jù)。

(2)基線數(shù)據(jù)是靜態(tài)數(shù)據(jù)，采用分布式存儲方式進(jìn)行存儲。

(3)只在一臺服務(wù)器上存儲和處理增量更新數(shù)據(jù)，并且是在內(nèi)存中存儲和處理更新數(shù)據(jù)。

(4)在系統(tǒng)負(fù)載輕的時候，把增量更新批量合并到基線數(shù)據(jù)中。

(5)數(shù)據(jù)訪問時同時訪問基線數(shù)據(jù)和增量更新數(shù)據(jù)并合并。

因此這樣好處是：

(1)讀事務(wù)和寫事務(wù)分離
(2)通過犧牲一點(diǎn)擴(kuò)展性(寫是一個單點(diǎn))，來避免分布式事務(wù)處理。

說明：該系統(tǒng)雖然能處理高并發(fā)的事務(wù)型處理，號稱很牛逼，但其實(shí)也只是根據(jù)電商的事務(wù)處理來定制開發(fā)的專用系統(tǒng)，個人認(rèn)為其技術(shù)難度小于oracle等通用型的數(shù)據(jù)庫。該系統(tǒng)無法應(yīng)用到銀行或者12306等，因?yàn)槠涫聞?wù)處理的邏輯遠(yuǎn)遠(yuǎn)比電商商品買賣處理邏輯復(fù)雜。

在目前的大數(shù)據(jù)時代，一定是基于應(yīng)用定制才能找到好的解決方案!

3) 基于Hbase的交易系統(tǒng)

在hadoop平臺下，HBASE數(shù)據(jù)庫是一個分布式KV數(shù)據(jù)庫，屬于實(shí)時數(shù)據(jù)庫范疇。支付寶目前支付記錄就是存儲在HBASE數(shù)據(jù)庫中。

HBASE數(shù)據(jù)庫接口是非SQL接口，而是KV操作接口(基于Key的訪問和基于key范圍的scan操作)，因此HBASE數(shù)據(jù)庫雖然可擴(kuò)展性非常好，但是由于其接口限制導(dǎo)致該數(shù)據(jù)庫能支持上層應(yīng)用很窄?；贖BASE應(yīng)用的設(shè)計中，關(guān)鍵點(diǎn)是key的設(shè)計，要根據(jù)需要支持的應(yīng)用來設(shè)計key的組成。

可以認(rèn)為HBASE數(shù)據(jù)庫只支持作為KEY的這一列的索引。雖然目前HBASE有支持二級索引的方案，二級索引維護(hù)將會比較麻煩。

并發(fā)是指同時執(zhí)行通常不相關(guān)的各種任務(wù)，例如交易型系統(tǒng)典型屬于高并發(fā)系統(tǒng)。

并行是通過將一個很大的計算任務(wù)，劃分為多個小的計算任務(wù)，然后多個小計算任務(wù)的并行執(zhí)行，來縮短該計算任務(wù)計算時間。

兩者主要區(qū)別在于：

(1)通訊與協(xié)調(diào)方面：在并行計算中，由于多個小任務(wù)同屬一個大的計算任務(wù)，因此小任務(wù)之間存在依賴關(guān)系，小任務(wù)之間需要大量通訊和協(xié)調(diào);相反，并發(fā)中的多個任務(wù)之間基本相互獨(dú)立，任務(wù)與任務(wù)之間相關(guān)性很小。

(2)容錯處理方面：由于并發(fā)任務(wù)之間相互獨(dú)立，某個任務(wù)執(zhí)行失敗并不會影響其它的任務(wù)。但是并行計算中的多個任務(wù)屬于一個大任務(wù)，因此某個子任務(wù)的失敗，如果不能恢復(fù)(粗粒度容錯與細(xì)粒度容錯)，則整個任務(wù)都會失敗。

數(shù)據(jù)量大不一定需要并行計算，雖然數(shù)據(jù)量大，數(shù)據(jù)是分布存儲，但是如果每次操作基本上還是針對少量數(shù)據(jù)，因此每次操作基本上都是在一臺服務(wù)器上完成，不涉及并行計算。只是需要通過數(shù)據(jù)復(fù)制、數(shù)據(jù)緩存、異步處理等方式來支撐高并發(fā)訪問量

隨數(shù)據(jù)量變大，和事務(wù)處理不同的是，單個統(tǒng)計分析涉及數(shù)據(jù)量會非常大，單個統(tǒng)計分析任務(wù)涉及數(shù)據(jù)會分散在多臺服務(wù)器上，且由于計算量大，采用單臺服務(wù)器進(jìn)行計算，會導(dǎo)致計算時間非常長，單個統(tǒng)計分析任務(wù)必須采用并行計算方式來加快單個統(tǒng)計分析任務(wù)執(zhí)行速度。

在大數(shù)據(jù)背景下的數(shù)據(jù)統(tǒng)計分析技術(shù)門類很多，常見的有：

·  MPP并行數(shù)據(jù)庫 : TeraData、GreenPlum、Vertica等。
·  基于MapReduce并行計算框架的數(shù)據(jù)倉庫：HIVE(Hadoop平臺) 、Tenzing（Google公司）
·  基于Hbase的Phoenix系統(tǒng)
·   HadoopDB系統(tǒng)
·  EMC公司的hapt系統(tǒng)
·   MPP分布式查詢引擎： Dremel、Impala、Presto、Shard query、Citusdb。
·  基于SPARK的Shark、基于Dryad的SCOPE、基于Tez的stinger。
·  基于hadoop+index的JethroData系統(tǒng)
·  基于內(nèi)存計算的Druid系統(tǒng)

這些系統(tǒng)都解決了海量數(shù)據(jù)下的數(shù)據(jù)統(tǒng)計分析的問題，并且這些系統(tǒng)另外一個共同特點(diǎn)是都提供了SQL或者類SQL接口。

為了能夠較好研究這些系統(tǒng)，我們需要對并行查詢與并行計算的相關(guān)技術(shù)做一個簡要的介紹。

首先所有的系統(tǒng)都可以分為三個層次: 語義層、并行計算引擎層、分布式存儲層。語義層提供一個編程接口讓用戶表達(dá)所需要計算，并負(fù)責(zé)把該計算翻譯成底層并行計算引擎可以執(zhí)行的執(zhí)行計劃，并由并行計算引擎來執(zhí)行，最下面一層是分布式存儲層。

對于提供類SQL接口并行計算系統(tǒng)，語義層可以認(rèn)為是SQL解析層。

1) 語義層

SQL語言是一種聲名式語言，SQL只是表達(dá)了要做什么，而沒有表達(dá)怎么做。為此，SQL解析層主要作用是：將用戶提交的基于SQL的統(tǒng)計分析請求，轉(zhuǎn)化為底層計算引擎層可以執(zhí)行的執(zhí)行計劃。也就是解決“怎么做”的問題。

SQL解析層工作主要包括兩個大方面:

(1) 通過語法分析技術(shù)來理解要做什么。在關(guān)系數(shù)據(jù)庫中，一般會把SQL語言分析后，形成樹型結(jié)構(gòu)的執(zhí)行計劃。

(2) 在語法分析技術(shù)上，利用各種優(yōu)化技術(shù)和算法，找出一種最經(jīng)濟(jì)物理執(zhí)行計劃。

優(yōu)化可以分為兩個方面：一是邏輯層面優(yōu)化、二是物理執(zhí)行層面優(yōu)化。

(1) 邏輯層優(yōu)化

邏輯層面?zhèn)€人認(rèn)為主要是因?yàn)橥瑯颖磉_(dá)一個分析請求，有的人SQL寫的好，有的人SQL寫的爛，因此在邏輯層面可以通過一些等價關(guān)系代數(shù)變換，實(shí)現(xiàn)查詢重寫，將寫的比較爛的sql變換為好的寫法。

比較典型優(yōu)化是：“把投影和過濾下沉，先執(zhí)行過濾和投影操作”，減少中間結(jié)果。

(2) 物理層優(yōu)化

物理層面優(yōu)化是在邏輯優(yōu)化后，結(jié)合實(shí)際物理執(zhí)行過程，找出最優(yōu)的物理執(zhí)行計劃。生成物理查詢計劃的工作包括:

·  增加一些操作符： 包括掃描和排序等。

·  確定各個操作符實(shí)現(xiàn)算法。例如掃描是全表掃描還是利用索引;Join是采用HASH連接、索引連接、合并排序等實(shí)現(xiàn)算法中的那一種。

·   確定操作符之間的數(shù)據(jù)流轉(zhuǎn)方法：物化還是流水線方式。

·  采用基于代價估算方法確定最優(yōu)的物理執(zhí)行計劃，目前代價估算主要是以估算該物理計劃需要的IO量。另外對于并行數(shù)據(jù)庫，則還要考慮通訊代價，即盡量減少數(shù)據(jù)在各個機(jī)器之間的傳遞。

在物理層優(yōu)化的代價估算過程中，代價估算需要依靠很多統(tǒng)計信息，如表有多大，表中相關(guān)列的值分布是什么樣子等。傳統(tǒng)數(shù)據(jù)庫在數(shù)據(jù)Load過程中會事先計算好這些統(tǒng)計信息。并行計算中還需要考慮通訊代價。

需要指出是，由于imapla、Presto、HIVE等系統(tǒng)只是一個查詢引擎，它們可以直接查詢以普通文件方式存儲在HDFS系統(tǒng)上的文件，因此這些系統(tǒng)一般無法使用索引和各種統(tǒng)計信息來進(jìn)行物理執(zhí)行計劃的優(yōu)化，這些系統(tǒng)一般只能在邏輯層進(jìn)行一些基于規(guī)則靜態(tài)優(yōu)化。根據(jù)SHARK論文，SHARK系統(tǒng)支持根據(jù)前面一些節(jié)點(diǎn)計算獲得的信息，來動態(tài)優(yōu)化后面執(zhí)行計劃。

(3) 物化與流水線執(zhí)行方法

一條SQL語句對開發(fā)人員而言，感覺只是一次調(diào)用，但是實(shí)際上在數(shù)據(jù)庫內(nèi)部，一條SQL語句執(zhí)行其實(shí)是有多個操作符組合而成的的樹型結(jié)構(gòu)計算流。如下圖：

針對該計算流有兩種執(zhí)行方式：一是基于物化或者是實(shí)體化執(zhí)行方式，另外一種是基于數(shù)據(jù)流的執(zhí)行方式。

第一種方法的過程是： 把各個操作運(yùn)算排序，并把每個操作運(yùn)算的輸出的中間結(jié)果存儲在磁盤上，直到被另外一個操作運(yùn)算所讀取。

另外一種方法是同時交錯進(jìn)行多個運(yùn)算，由一個運(yùn)算產(chǎn)生每個元組直接傳遞給下一個運(yùn)算，而不將中間結(jié)果存儲到磁盤，也不用等到前一個運(yùn)算全部運(yùn)算完畢。

例如： 兩個表連接后，再進(jìn)行投影操作。如果采用第一種方法，則需要

把兩表連接中間結(jié)果臨時寫入磁盤，然后再讀取該結(jié)果執(zhí)行投影操作。而如果采用第二種方法，則連接操作一旦產(chǎn)生一個元組就可以立刻送到投影操作去進(jìn)行投影操作。

流水線方法可以極大避免大量的中間結(jié)果磁盤IO。因此數(shù)據(jù)庫一般會采取流水線方法來執(zhí)行。流水執(zhí)行方法有兩種模式：一種是需求驅(qū)動流水線，也就是從上層主動向下層要求元組，另外一種是生產(chǎn)者驅(qū)動流水線執(zhí)行方式，由低層主動產(chǎn)生元組，由下層向上層推。

目前大部分?jǐn)?shù)據(jù)庫引擎采用的是需求驅(qū)動流水線，實(shí)現(xiàn)方式采用基于Graefe提出的迭代器模型。該模型把每個操作都表達(dá)為由三個接口： open() , getnext(), close()。每個操作被調(diào)用open() 進(jìn)行準(zhǔn)備工作，然后通過反復(fù)迭代被調(diào)用getnext來獲取下一個元組，最后被調(diào)用close來進(jìn)行清理工作。 通過構(gòu)建迭代器網(wǎng)絡(luò)，也就是迭代器之間的互相調(diào)用，就可以實(shí)現(xiàn)需求驅(qū)動流水線。

當(dāng)然不是任何操作都可以流水執(zhí)行，流水執(zhí)行條件是：操作要滿足在接收輸入元組時可以輸出元組。例如排序操作就無法進(jìn)行流水操作，在執(zhí)行排序操作前都必須進(jìn)行實(shí)體化。

(4) SQL解析層與并行計算引擎層

由于不同并行計算引擎層的執(zhí)行計劃表達(dá)不同，因此不同系統(tǒng)需要將SQL解析成不同的形式物理執(zhí)行計劃，例如：

·  MPP關(guān)系數(shù)據(jù)庫一般是把SQL解析成樹狀結(jié)構(gòu)的物理執(zhí)行計劃。

·  HIVE、Tezning數(shù)據(jù)庫是把SQL解析成DAG結(jié)構(gòu)的多個MAPREDUCE組合。

·  DRemel等則類似MPP關(guān)系數(shù)據(jù)庫，把SQL解析成一個樹狀結(jié)構(gòu)執(zhí)行計劃。

·  微軟SCOPE則需要把類SQL解析成DAG結(jié)構(gòu)的Dryad可執(zhí)行的執(zhí)行計劃。

·  SHARK則需要把SQL解析成基于scala語言的DAG結(jié)構(gòu)執(zhí)行計劃。

并行

2) 并行計算引擎層

(1) 并行計算形式

并行化可以分為水平并行(無依賴并行)與垂直并行(流水線并行)兩類。如下圖：

如果兩個操作OP1、OP2 無相互依賴關(guān)系，則稱這兩個操作相互獨(dú)立。水平并行化指的是互相獨(dú)立的多個操作或者一個操作內(nèi)互相獨(dú)立的多個子操作分別由不同的處理機(jī)并行執(zhí)行的形式。例如，排序操作、掃描操作由不同處理機(jī)并行執(zhí)行就是水平并行化的實(shí)例。

水平并行中一個非常常見的就是基于數(shù)據(jù)劃分的并行，例如MAPREDUCE，就是通過將數(shù)據(jù)劃分到多臺服務(wù)器上，并行執(zhí)行MAP和Reduce來進(jìn)行并行運(yùn)算。也有人把這種基于數(shù)據(jù)劃分并行與操作獨(dú)立并行區(qū)分開。

垂直并行化則是指存在流水線方式依賴關(guān)系的操作分別由不同處理機(jī)并行執(zhí)行的形式。流水線方式依賴：如果OP2無需等待OP1執(zhí)行完畢即可在另一處理機(jī)上開始執(zhí)行。由于一般情況下，流水的級數(shù)遠(yuǎn)小于處理的數(shù)據(jù)條目，因此流水并行主要意義是在可以避免中間結(jié)果磁盤IO操作，對并行度的貢獻(xiàn)相對較小。

(2) 并行計算面臨的問題與并行計算框架

并行計算需要解決的問題主要包括幾下幾個方面：自動并行化、通訊、任務(wù)調(diào)度、并發(fā)控制、容錯、資源管理。由于并行計算面向上述一系列問題，因?yàn)闃I(yè)界為了簡化并行程序開發(fā)，提供了一系列的并行計算底層庫或者框架。

在高性能計算領(lǐng)域，最常用于并行計算編程的庫是MPI庫，但是該庫主要只是解決通訊問題。這導(dǎo)致容錯、資源管理、任務(wù)調(diào)度、并行化等方面問題需要程序員來解決，因此利用MPI開發(fā)并行程序相對比較困難。

最近一些年，各大型互聯(lián)網(wǎng)公司開發(fā)開發(fā)了一系列的通用并行計算框架。包括谷歌公司的MAPREDUCE框架、微軟公司的Dryad框架(目前微軟已經(jīng)停止該項(xiàng)目開發(fā)，轉(zhuǎn)而支持hadoop)、谷歌公司基于BSP模型的Pregel框架、Twitter公司的Storm框架、Yahoo公司S4框架、HortonWorks公司的Tez框架、Berkeley大學(xué)的spark框架等通用并行計算框架。

有了這些框架了，程序開發(fā)時只需要編寫串行執(zhí)行程序即可，而且也不用考慮任務(wù)與任務(wù)之間的并發(fā)控制以及通訊等問題，其它所有問題都有框架來解決 ，這樣就大大簡化并行程序開發(fā)難度。例如采用MAPREDUCE框架，我們只需要提供MAP函數(shù)和Reduce函數(shù)，這些函數(shù)對程序員而言，都只是對本地數(shù)據(jù)操作。

目前雖然并行計算框架很多，但是可以把它們分成幾個大類(基于BSP并行圖計算引擎請參考第四章)：

·  流數(shù)據(jù)并行計算框架

Storm、S4是屬于流數(shù)據(jù)并行計算框架，適合對流數(shù)據(jù)實(shí)時處理，也就是在數(shù)據(jù)寫入磁盤前對數(shù)據(jù)進(jìn)行實(shí)時并發(fā)運(yùn)算。這類特點(diǎn)是計算不變，數(shù)據(jù)一直在變化。在上一個文檔中，對此框架做過詳細(xì)介紹，這里不再詳細(xì)介紹。

·  基于DAG通用批處理并行計算框架

MapReduce、Tez、Dryad、Spark等屬于基于DAG(有向無環(huán)圖)的通用批處理并行計算框架。這類框架是針對存儲在存儲設(shè)備上的一批數(shù)據(jù)進(jìn)行分析處理，而且把分析處理流程利用DAG模型來表達(dá)。

在這些框架中MAPREDUCE是最早出現(xiàn)的框架，而后面出現(xiàn)的一系列框架都為了改進(jìn)MR框架不足而出現(xiàn)的升級版本。

·  MR框架主要不足是兩個方面：

一是編程接口太簡單，表現(xiàn)在單個MAPREDUCE無法表達(dá)復(fù)雜運(yùn)算，所以在實(shí)際應(yīng)用環(huán)境中都是通過多個MR作業(yè)組合來完成一個任務(wù)。為了簡化MR作業(yè)組合，在早期出現(xiàn)了一系列項(xiàng)目來執(zhí)行組和式MR作業(yè)，例如Cascading項(xiàng)目。另外一個方面所有問題都必須轉(zhuǎn)換為MAP和REDUCE模式，導(dǎo)致程序編寫比較麻煩。

二是MR只支持基于數(shù)據(jù)分區(qū)并行方式，不支持流水線并行，采用是步步物化策略來提高可靠性，當(dāng)是這種導(dǎo)致大量中間結(jié)果物化，IO開銷非常大。

因此Tez、Dryad、Spark等后續(xù)框架改進(jìn)主要針對以下兩點(diǎn)進(jìn)行改進(jìn)：

一是直接支持基于DAG結(jié)構(gòu)表達(dá)方法，DAG使得用戶能夠非常清晰地寫出非常復(fù)雜的業(yè)務(wù)邏輯;

二是通過支持流水線并性方式或者是盡量將中間結(jié)果放內(nèi)存等方式，解決中間結(jié)果物化導(dǎo)致的IO開銷問題。Dryad和Spark框架在執(zhí)行運(yùn)算時，都會自動識別可以采取流水線方式執(zhí)行的計算步驟，并盡量采用流水線執(zhí)行方式來執(zhí)行。

容錯：由于支持流水線并行或者采取把中間結(jié)果放內(nèi)存的方式，因此要必須考慮容錯的問題。由于這些框架都采用的是DAG結(jié)構(gòu)，DAG中一個節(jié)點(diǎn)所代表計算的執(zhí)行是不會對輸入進(jìn)行修改(所謂函數(shù)式編程)，因此可以多次重復(fù)執(zhí)行不會影響計算。因此如果某個節(jié)點(diǎn)計算失敗，它可以根據(jù)輸入重復(fù)計算，而如果輸入數(shù)據(jù)也消失了，則讓前一個節(jié)點(diǎn)重新計算。所有這一切都是由框架自動執(zhí)行。

當(dāng)然需要指出的是對一些流水線執(zhí)行的多個計算步驟，如果某個計算節(jié)點(diǎn)失敗，則只能整個流水線整體失敗。

·  基于Tree結(jié)構(gòu)的MPP并行查詢引擎

MPP并行數(shù)據(jù)庫與Dremel、impala、Presto、Shard query、Citusdb都采用的是基于Tree結(jié)構(gòu)并行查詢引擎。此類并行計算引擎共同特點(diǎn)是：

一是針對SQL專用并行計算引擎，只支持SQL或者類SQL語義。

二是執(zhí)行計劃都是樹狀結(jié)構(gòu);

三是以流水線或者將中間結(jié)果放入內(nèi)存方式來實(shí)現(xiàn)快速計算。

四是粗粒度容錯機(jī)制。

它們之間不同點(diǎn)：

一 MPP并行數(shù)據(jù)庫中并行查詢引擎與底層存儲是緊耦合的，導(dǎo)致如果采用MPP并行數(shù)據(jù)庫，則只能通過SQL來訪問數(shù)據(jù)，無法采用其他計算引擎直接處理存儲在數(shù)據(jù)庫中的數(shù)據(jù)。

二 Impala、Presto都只是一個并行查詢引擎，它們可以直接查詢以文件方式存儲在HDFS上的數(shù)據(jù),這樣同一份數(shù)據(jù)既可以利用這些引擎來實(shí)現(xiàn)交互式查詢，也可以支持利用其他計算框架進(jìn)行更深入分析。

三 Dremel 只支持Google自己的基于嵌套結(jié)構(gòu)列式存儲(Column IO)。該引擎也主要適合于聚合型計算，不支持join操作。

四 上述引擎中只有MPP并行數(shù)據(jù)庫可以利用索引以及各種統(tǒng)計信息來優(yōu)化物理執(zhí)行過程，因此該系統(tǒng)執(zhí)行效率應(yīng)該是最高。

五 Dremel、impala都只適合中間結(jié)果越來越小的查詢，因?yàn)檫@些系統(tǒng)都是把中間結(jié)果放在內(nèi)存，一旦某個中間節(jié)點(diǎn)輸出結(jié)果超過內(nèi)存，則整個任務(wù)會失敗，例如大表之間Join。

六 shard query和citusdb 都是在單機(jī)版本關(guān)系數(shù)據(jù)庫基礎(chǔ)上，采用增加一層中間件方式來支持并行查詢。

·  基于Tree并行計算引擎與基于DAG并行計算引擎本質(zhì)區(qū)別

基于Tree結(jié)構(gòu)并行計算引擎與基于DAG并行計算引擎從表面上看，它們之間的主要區(qū)別是在于語義層面：前者主要專用與SQL類，而后者更通用。

但是MPP并行關(guān)系數(shù)據(jù)庫引擎、Imapla等都會支持通過UDF來擴(kuò)展和解決標(biāo)準(zhǔn)SQL語言表達(dá)能力，另外SQL語言本身可以通過嵌套查詢、子查詢、union等各種方法表達(dá)很復(fù)雜的計算過程，因此從語義表達(dá)層面來講他們之間不存在本質(zhì)區(qū)別。

這兩者之間主要區(qū)別還是在于表達(dá)執(zhí)行計劃結(jié)構(gòu)方面：樹結(jié)構(gòu)是一個逐步匯聚的一個計算過程，無法表達(dá)split結(jié)構(gòu)，因此基于DAG表達(dá)結(jié)構(gòu)更靈活和通用。個人認(rèn)為：樹型結(jié)構(gòu)可能更加適合采用迭代器模型來實(shí)現(xiàn)流水線式的操作(只有樹結(jié)構(gòu)才有上下層的關(guān)系，因此方便實(shí)現(xiàn)上層操作符嵌套調(diào)用下層操作符)。

所以不是所有計算都可以通過一個復(fù)雜SQL語句來表達(dá)!

(5) 自動并行化、數(shù)據(jù)重分布、本地調(diào)度

并行計算引擎最重要的一個職責(zé)是自動并行。根據(jù)前面的并行計算基礎(chǔ)知識，并行計算的形式主要包括：基于數(shù)據(jù)劃分水平并行、基于流水線垂直并行、基于無依賴水平并行三種方式。

大數(shù)據(jù)屬于數(shù)據(jù)密集型計算，數(shù)據(jù)數(shù)量遠(yuǎn)遠(yuǎn)超過計算步驟數(shù)量。因此基于數(shù)據(jù)劃分并行方式是最有效的一種并行計算方法。在整個并行計算過程中，基于數(shù)據(jù)劃分中涉及數(shù)據(jù)可以分為兩大類：原始數(shù)據(jù)與中間結(jié)果數(shù)據(jù)。

·   原始數(shù)據(jù)劃分以及SN、SD架構(gòu)討論

原始數(shù)據(jù)則可能存在兩種情況：一是在Shared-nothing架構(gòu)中，原始數(shù)據(jù)本身就已經(jīng)劃分好了，例如HDFS或者SN架構(gòu) MPP數(shù)據(jù)庫;另外一種情況如shared-disk結(jié)構(gòu)中，原始數(shù)據(jù)沒有劃分。

第一種情況下針對原始數(shù)據(jù)劃分并行計算，就要受該劃分的限制。例如在MAPREDUCE中，map輸入是存儲在HDFS上的數(shù)據(jù)文件，因此MAP實(shí)例個數(shù)一是不能少于該數(shù)據(jù)文件分片數(shù)，二是MAP實(shí)例最好運(yùn)行在該數(shù)據(jù)文件所在機(jī)器，也就是要求任務(wù)調(diào)度時，能把該任務(wù)調(diào)度到特定機(jī)器上，即所謂“本地調(diào)度”，將計算盡量移動到數(shù)據(jù)。

第二種情況下，由于所有計算節(jié)點(diǎn)都可以看到所有數(shù)據(jù)，因此此時可以根據(jù)計算特點(diǎn)靈活選擇：數(shù)據(jù)劃分粒度、并行度、參與計算的節(jié)點(diǎn)。例如在ORALCE并性機(jī)制中，ORALCE可以針對某張表，按block或者partition 為單位進(jìn)行劃分。

根據(jù)上述分析我們可以發(fā)現(xiàn)SD架構(gòu)相對SN架構(gòu)，在針對原始數(shù)據(jù)第一級并性計算時，SD架構(gòu)更靈活，SN架構(gòu)面臨的一個缺陷就是如果原始數(shù)據(jù)分布不均衡，則存在計算傾斜問題。

但是現(xiàn)在大部分大的數(shù)據(jù)庫廠商的MPP數(shù)據(jù)庫還是采用了SN架構(gòu)。根據(jù)網(wǎng)上所查資料來看,主要原因有兩點(diǎn)：

一是SD架構(gòu)下，磁盤是一個共享資源，計算節(jié)點(diǎn)越多磁盤爭搶概率越大(和RAID隨機(jī)IO沖突道理一樣)，導(dǎo)致該架構(gòu)可擴(kuò)展性不夠好，也就是可能計算節(jié)點(diǎn)越多，效率相反不會提高。

二是從緩存角度來看，SD架構(gòu)下每個機(jī)器緩存都要面向全數(shù)據(jù)庫，會導(dǎo)致命中概率底下;目前ORACLE-RAC開發(fā)一個fusion cache技術(shù)，實(shí)現(xiàn)了一個全局共享緩存來解決上述問題，但是可想而知這會影響系統(tǒng)可擴(kuò)展性。

因此超過一定規(guī)模數(shù)據(jù)分析系統(tǒng)，都是采用SN架構(gòu)。

中間結(jié)果數(shù)據(jù)劃分與數(shù)據(jù)重分布

中間結(jié)果是由各個計算節(jié)點(diǎn)產(chǎn)生的，因此中間結(jié)果生成是就是分布在各個參與計算節(jié)點(diǎn)之上的，因此：

一 ：SD架構(gòu)下數(shù)據(jù)共享好處，對中間結(jié)果無效。

二 ：如果由于計算任務(wù)之間需要，需要在任務(wù)之間傳遞中間結(jié)果，則即使是SD架構(gòu)也存在數(shù)據(jù)重分布的問題，主要是中間結(jié)果重分布，也就是中間結(jié)果傳輸。

另外從該過程我們還可以得出另外一個結(jié)論：

一： 對于復(fù)雜的數(shù)據(jù)處理，索引只能影響第一級計算，對于中間結(jié)果，由于只使用一次，因此沒有必要去針對中間結(jié)果建立索引。也就是即使我們將數(shù)據(jù)存儲在關(guān)系型數(shù)據(jù)庫中，也只有第一級計算能有效利用數(shù)據(jù)庫索引。

二：即使采用并行數(shù)據(jù)庫，如果我們的整個計算過程不能用一個SQL語句來表達(dá)，則我們必須自己解決中間結(jié)果的劃分與并性計算的問題。

(6)并行計算引擎架構(gòu)與資源管理

所有并行計算引擎實(shí)現(xiàn)基本上都是主從結(jié)構(gòu)，即一個MASTER + 多個slave節(jié)點(diǎn)的結(jié)構(gòu)。由client向MASTER提交一個job,然后由Master負(fù)責(zé)將邏輯執(zhí)行計劃變成實(shí)際執(zhí)行計劃，并由Master負(fù)責(zé)將各個任務(wù)分發(fā)到各個slave中，并負(fù)責(zé)各個任務(wù)的調(diào)度。

MPP數(shù)據(jù)庫查詢引擎架構(gòu)

MAPREDUCE架構(gòu)和該架構(gòu)缺點(diǎn)

Mapreduce框架中，JobTracker承當(dāng)MASTER的職責(zé)，一般和HDFS中的NadeNode節(jié)點(diǎn)安裝在一個服務(wù)器上。TaskTracker安裝在各個DataNode上，承擔(dān)Slave的角色。

流程如下：

(1)首先用戶程序(Client Program)提交了一個job，job的信息會發(fā)送到Job Tracker中，Job Tracker是Map-reduce框架的中心，他需要與集群中的機(jī)器定時通信(heartbeat), 需要管理哪些程序應(yīng)該跑在哪些機(jī)器上，需要管理所有job失敗、重啟等操作。

(2)TaskTracker是Map-reduce集群中每臺機(jī)器都有的一個部分，他做的事情主要是監(jiān)視自己所在機(jī)器的資源情況(資源的表示是“本機(jī)還能起多少個map-task，多少個reduce-task”，每臺機(jī)器起map/reduce task的上限是在建立集群的時候配置的)，另外TaskTracker也會監(jiān)視當(dāng)前機(jī)器的tasks運(yùn)行狀況。

(3)TaskTracker需要把這些信息通過heartbeat發(fā)送給JobTracker，JobTracker會搜集這些信息以給新提交的job分配運(yùn)行在哪些機(jī)器上。

MAPREDUCE結(jié)構(gòu)存在以下缺點(diǎn)：

(1) jobtracker只能安裝在一臺服務(wù)器上，集中式作業(yè)控制導(dǎo)致可擴(kuò)展性不好，另外JobTracker負(fù)責(zé)事情太多，容易成為性能瓶頸。

(2) 資源調(diào)度與編程模型緊耦合，只支持MAPREDUCE一種編程模型。

(3) 資源劃分太簡單，每個TaskTracker只是簡單把整個機(jī)器資源按map task slot和reduce task slot來劃分，而沒有考慮不通任務(wù)所需的內(nèi)存和CPU等的資源不同。

針對上述特點(diǎn)，hadoop平臺開發(fā)通用的資源管理器yarn，只負(fù)責(zé)資源管理和分配，即通過把jobtrack中的資源管理分配自和并行應(yīng)用程序調(diào)度與控制分離，從而實(shí)現(xiàn)雙層調(diào)度框架：由yarn把資源分配給各計算引擎MASTER，再由MASTER分配給各個TASK。

資源管理器YARN

流程如下：

1) client 通過一個CLC (container launch context )向ResourceManager提交一個應(yīng)用

2)RM 啟動該應(yīng)用的 AplicationMaster。 AplicationMaster啟動后先向ResourceManager注冊，并利用心跳信息，定期向ResourceManager報告自己存活性和資源分配請求

3)ResourceManager分配一個container(container包括CPU個數(shù)和所需內(nèi)存數(shù)量)時， AplicationMaster構(gòu)造一個CLC,并在該container對應(yīng)機(jī)器上Nodemanager上啟動該container。AplicationMaster 監(jiān)控該container的運(yùn)行狀態(tài)，并且該資源需要被回收時，由AplicationMaster停止該container。 監(jiān)控container內(nèi)部的作業(yè)的執(zhí)行進(jìn)度是AplicationMaster的職責(zé)。

4)一旦整個運(yùn)行完畢，AM從RM中解除注冊，并且干凈退出。

這種架構(gòu)優(yōu)點(diǎn)是：

優(yōu)點(diǎn)一：減小了JobTracker(也就是現(xiàn)在的ResourceManager)的資源消耗，并且讓監(jiān)測每一個Job子任務(wù)(tasks)狀態(tài)的程序分布式化了，更安全、更優(yōu)美。也就是ApplicationMaster是每個應(yīng)用一個，并且不通應(yīng)用對應(yīng)的ApplicationMaster的實(shí)例可以運(yùn)行在不同服務(wù)器上。

優(yōu)點(diǎn)二：能夠支持不同的編程模型ApplicationMaster是一個可變更的部分，用戶可以對不同的編程模型寫自己的ApplicationMaster，讓更多類型的編程模型能夠跑在Hadoop集群中。

優(yōu)點(diǎn)三：對于資源的表示比之前以剩余slot數(shù)目更合理。

3) 存儲層

數(shù)據(jù)存儲層主要包括以下幾類：

一類是基于MPP數(shù)據(jù)庫集群，這類系統(tǒng)特點(diǎn)是存儲層與上層并型計算引擎是緊耦合，屬于封閉性的系統(tǒng)。

二是采用分布式文件系統(tǒng)，例如SharK、Stinger、HIVE、Impala、Scope等。Shark、Stinger、Hive、Imapla都采用HDFS文件系統(tǒng)作為存儲層，Scope采用微軟自己開發(fā)的分布式文件系統(tǒng)。此類系統(tǒng)特點(diǎn)是存儲層與上層計算引擎層之間是松耦合關(guān)系。

三是存儲層基于單機(jī)版本關(guān)系數(shù)據(jù)庫，例如CitusDB采用PostSQL數(shù)據(jù)庫系統(tǒng)、shardquery采用Mysql數(shù)據(jù)庫系統(tǒng)。此類系統(tǒng)類似于一個中間件，也可以認(rèn)為上層和底層存儲層屬于松耦合關(guān)系。

四是可以支持各種異構(gòu)的存儲系統(tǒng)，例如Presto、Tenzing。Presto設(shè)計即支持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ù)不會垮機(jī)器存儲，然后再按劣存儲)，shark系統(tǒng)開發(fā)了內(nèi)存中的列式存儲格式，citusDB開發(fā)了專用postSQL數(shù)據(jù)庫的列式存儲引擎。

1) JethroData系統(tǒng)

JethroData的特點(diǎn)是hadoop+index。該系統(tǒng)對存儲在HDFS上的結(jié)構(gòu)化數(shù)據(jù)建立索引，并把索引文件也以普通文件方式存儲在HDFS系統(tǒng)，并在查詢處理時采取以下過程：

(1) 查詢主節(jié)點(diǎn)負(fù)責(zé)分析SQL語句后，針對sql中的where條件部分，利用索引文件來得到符合where過濾條件后的rowid集合。

(2) 該rowid集合涉及各datanode節(jié)點(diǎn)，采用并發(fā)方式來讀取數(shù)據(jù)。

(3) 所有數(shù)據(jù)匯總到查詢主節(jié)點(diǎn)，進(jìn)行匯總與計算，并將最終結(jié)果返回給客戶端。

可以看出，由于該系統(tǒng)設(shè)計思路是希望通過索引來加速數(shù)據(jù)選擇，因此只適合每次查詢處理只涉及少量一部分?jǐn)?shù)據(jù)。

2) Druid系統(tǒng)

本系統(tǒng)是美國metamarket公司開發(fā)的面向海量數(shù)據(jù)的實(shí)時統(tǒng)計分析系統(tǒng)，以實(shí)現(xiàn)針對上億級別海量數(shù)據(jù)統(tǒng)計分析的延遲在1秒以內(nèi)。該系統(tǒng)于2012年10月開源。該系統(tǒng)可以認(rèn)為是一個分布式的內(nèi)存OLAP系統(tǒng)。

該系統(tǒng)主要分析的數(shù)據(jù)為交易記錄，每條交易記錄包括三個部分：交易發(fā)生的時間點(diǎn)、多個維度屬性、多個數(shù)值型度量屬性。例如：

該系統(tǒng)設(shè)計用來可以回答以下問題“有多少個針對Justin Bieber的編輯來自San Francisco? ”、“一個月內(nèi)來自Calgary的增加編輯字?jǐn)?shù)的平均數(shù)是多少?”。而且要求：能夠在高并發(fā)環(huán)境下，在1秒以內(nèi)完成任意維度組合的統(tǒng)計，且保證系統(tǒng)高可用;還系統(tǒng)還要能夠具備實(shí)時數(shù)據(jù)分析能力，也就是能夠查詢分析到最新的數(shù)據(jù)，延時時間為秒級。

為了達(dá)到上述目標(biāo)，該公司先后通過測試發(fā)現(xiàn)關(guān)系數(shù)據(jù)庫技術(shù)和NOSQL數(shù)據(jù)庫都無法滿足其需求。關(guān)系型數(shù)據(jù)庫由于磁盤io瓶頸導(dǎo)致性能無法滿足需求，而NOSQL數(shù)據(jù)庫雖然可以采用預(yù)計算方法來達(dá)到高性能，但是預(yù)計算無法滿足分析需求靈活多變。

為解決該問題，該公司自己開發(fā)DRUID系統(tǒng)，主要技術(shù)思路如下：

(1)將原始數(shù)據(jù)(alpha數(shù)據(jù))進(jìn)行一定粒度合并，合并成beta數(shù)據(jù)。

(2)將beta數(shù)據(jù)全部放入內(nèi)存，并通過分布式內(nèi)存方式解決單臺服務(wù)器內(nèi)存

上限問題。

(3) 針對緯度屬性建立索引，以加速數(shù)據(jù)的選取。

(4) 采用分布式方式進(jìn)行并行統(tǒng)計，為了保證分布式統(tǒng)計高效，該系統(tǒng)不支持join，而且對聚合計算不支持中位數(shù)等無法分布計算的聚合計算函數(shù)。

(5) 利用數(shù)據(jù)復(fù)制解決系統(tǒng)高可靠性問題。

1) MPP并行數(shù)據(jù)庫得益于流水線的執(zhí)行以及基于統(tǒng)計優(yōu)化等方面，使得MPP并行數(shù)據(jù)庫的執(zhí)行效率是最高的。但缺點(diǎn)包括：

·  數(shù)據(jù)導(dǎo)入時間長，導(dǎo)入時要做各種預(yù)處理，例如一些統(tǒng)計信息;

·  執(zhí)行引擎和存儲緊耦合導(dǎo)致數(shù)據(jù)難以被其他分析引擎進(jìn)行分析;

·  基于樹型結(jié)構(gòu)執(zhí)行計劃，導(dǎo)致MPP并行數(shù)據(jù)庫表達(dá)能力有限，更適合做統(tǒng)計與查詢，而不適合數(shù)據(jù)分析處理;

·  容錯性差，特別是一個任務(wù)涉及數(shù)據(jù)量越大，該缺陷越明顯。

2)HIVE、Tenzing、Shark、SCOPE、Stinger等系統(tǒng)可以認(rèn)為基本屬于同一類系統(tǒng)。這類系統(tǒng)共同特點(diǎn)是：”通用并行計算引擎框架+SQL解析層”。并且可以將HIVE、Tenzing看成是基于第一代系統(tǒng)，而Shark、Scope、Stinger是第二代系統(tǒng)。這一類系統(tǒng)特點(diǎn)如下：

·  存儲層、執(zhí)行引擎層、SQL解析層三者分離，可以方便替換執(zhí)行引擎，對使用者而言，同一份數(shù)據(jù)可以采用不同并行執(zhí)行引擎來分析。

·  在執(zhí)行效率方面，由于存儲和上層分離因此一半只能具備邏輯優(yōu)化能力，另外由于Tree結(jié)構(gòu)執(zhí)行計劃更容易采用流水線執(zhí)行方式，因此這類系統(tǒng)執(zhí)行效率總體來講不如MPP關(guān)系數(shù)據(jù)庫，它們之間排序是MPP數(shù)據(jù)庫 > 第二代系統(tǒng) > 第一代系統(tǒng)。

·   在執(zhí)行效率方面，另外一點(diǎn)是這類系統(tǒng)一般內(nèi)置對索引的支持不是太好或者不支持。

·  在大規(guī)模計算容錯方面，這類系統(tǒng)要優(yōu)于MPP關(guān)系數(shù)據(jù)庫。

3)Impala、Dremel等可以認(rèn)為屬于同一類系統(tǒng)，此類系統(tǒng)介于前兩者系統(tǒng)之間。這類系統(tǒng)特點(diǎn)是：

·   和MPP數(shù)據(jù)庫類似，基于Tree結(jié)構(gòu)執(zhí)行計劃，專注于查詢統(tǒng)計，因此效率高于第二類系統(tǒng)，但是可能和第二類系統(tǒng)的第二代相當(dāng)。

·   與MPP數(shù)據(jù)庫不同的是這類系統(tǒng)只是一個引擎，與存儲系統(tǒng)松耦合。也就是SQL解析層與執(zhí)行層緊偶合，然后和存儲層松藕合。

·  只適合做中間結(jié)果越來越小查詢分析，中間結(jié)果都放內(nèi)存，對內(nèi)存要求較高，例如無法實(shí)現(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)過一部分預(yù)處理，經(jīng)過部分提煉后，把提煉后數(shù)據(jù)進(jìn)行長期存儲和分析。也就是如下流程:

例如淘寶，把每天數(shù)據(jù)直接寫入Hadoop平臺，然后通過每天運(yùn)行相對固定mapreduce作業(yè)來做ETL，然后在計算結(jié)果基礎(chǔ)上為提供各種分析功能。其中海量原始數(shù)據(jù)經(jīng)過固定ETL后被刪除，由于只使用一次，因此沒有必要花很大精力把這些數(shù)據(jù)整理成適合分析與挖掘格式。例如在這種場景下，索引也沒有太大的價值，因此沒有必要花費(fèi)大量代價來建立索引。

MPP并行數(shù)據(jù)庫，適合存儲高密度價值數(shù)據(jù)，并且是長期存儲和多次使用，所以MPP并行數(shù)據(jù)庫會花大量經(jīng)歷在Load階段，把數(shù)據(jù)處理成適合分析格式 。

通過上述系統(tǒng)地介紹與比較，我們可以得出一個這樣結(jié)論：在大數(shù)據(jù)領(lǐng)域，沒有一個通用的解決方案，而需要根據(jù)具體業(yè)務(wù)場景，選擇合適的技術(shù)!

4)通過上述系統(tǒng)研究，我們可以發(fā)現(xiàn)一點(diǎn)就是Join操作，特別是大表之間join操作是最消耗資源，也是最優(yōu)化難度較高的操作，特別是在并行join的實(shí)現(xiàn)難度較大。例如Druid和Dremel等都基本放棄了join操作。

因此個人認(rèn)為應(yīng)該從業(yè)務(wù)上和從數(shù)據(jù)預(yù)處理方面，通過適當(dāng)數(shù)據(jù)冗余來盡量避免在分析過程過程中執(zhí)行join操作。

數(shù)據(jù)分析挖掘主要涉及兩個方面：一是數(shù)據(jù)預(yù)處理;二是數(shù)據(jù)挖掘。

在數(shù)據(jù)預(yù)處理方面，根據(jù)掌握資料來看，大型互聯(lián)網(wǎng)公司主要以MapReduce、Storm等計算框架為主，這些平臺可以較好解決大數(shù)據(jù)預(yù)處理面臨并行計算和處理靈活性的問題。但是個人認(rèn)為spark、tez等屬于MapReduce升級版本，因此后面這些計算框架在這方面的應(yīng)用會越來越廣泛。

在數(shù)據(jù)挖掘算法執(zhí)行方面，主要問題解決數(shù)據(jù)挖掘算法并行計算問題。早期在數(shù)據(jù)挖掘算法并行化方面項(xiàng)目主要是Mahout項(xiàng)目，該項(xiàng)目基于MAPREDUC 并行計算框架實(shí)現(xiàn)了推薦、分類等常用數(shù)據(jù)挖掘算法的并行化。

但由于數(shù)據(jù)挖掘算法存在以下兩個方面特點(diǎn)導(dǎo)致基于MAPREDUCE框架來做數(shù)據(jù)數(shù)據(jù)挖掘算法執(zhí)行引擎效率不高：一是機(jī)器學(xué)習(xí)算法一般比較復(fù)雜，通常需要多次迭代計算，而MapReduce框架的步步物化導(dǎo)致中間結(jié)果會反復(fù)的序列化和反序列化導(dǎo)致效率不高;二是數(shù)據(jù)與數(shù)據(jù)之間依賴特別多，在計算過程中機(jī)器與機(jī)器之間的通訊非常多，而MapReduce框架下Map與Reduce之間存在路障同步, 導(dǎo)致大量時間被消耗在同步等待上面，效率不高。

因此目前Mahout項(xiàng)目在2014年1月份在0.9版本發(fā)布后，該項(xiàng)目拋棄了MAPREDUCE框架，轉(zhuǎn)而采用SPARK作為底層計算框架。

除Mahout項(xiàng)目外，SPARK自己采用SPARK專門針對機(jī)器學(xué)習(xí)領(lǐng)域開發(fā)MLlib項(xiàng)目。但是MLlib項(xiàng)目出現(xiàn)時間比較晚，因此在成熟度方面不如Mahout。

Mahout項(xiàng)目目前支持的數(shù)據(jù)挖掘算法如下：

MLLib支持的數(shù)據(jù)挖掘算法包括：

在數(shù)據(jù)分析處理領(lǐng)域，隨社交網(wǎng)絡(luò)興起，對圖數(shù)據(jù)處理的需求越來越多。例如像Facebook和Twitter這樣的社交網(wǎng)絡(luò)，其數(shù)據(jù)天生就適合于圖表示法。對圖數(shù)據(jù)的處理和傳統(tǒng)數(shù)據(jù)庫處理一樣，也可以分為兩種類型的需求：

4 本章總結(jié)OLTP工作負(fù)載，能夠快速低延遲訪問小部分圖數(shù)據(jù)。

4 本章總結(jié)OLAP工作負(fù)載，能夠?qū)D對象中的大部分?jǐn)?shù)據(jù)進(jìn)行批量分析與處理。

1) 圖數(shù)據(jù)OLTP處理

(1) 圖數(shù)據(jù)庫分類

適合圖書據(jù)OLTP處理的系統(tǒng)，主要是各種圖數(shù)據(jù)庫。從目前來看圖數(shù)據(jù)庫主要可以分為兩類：

一是基于圖存儲模型的專用圖數(shù)據(jù)庫，如Neo4j、OrientDB、Infinite Graph等;

二是以通用KV存儲系統(tǒng)或者關(guān)系數(shù)據(jù)庫系統(tǒng)開發(fā)的圖數(shù)據(jù)庫，例如Titan系統(tǒng)(2013年推出)可以后端存儲可以基于HBASE或者是Cassandra，Twitter公司的FlockDB圖形數(shù)據(jù)庫和facebook公司Tao圖形數(shù)據(jù)庫是基于mysql來進(jìn)行開發(fā)。根據(jù)報道美國NSA就是利用2011年開源的Apache Accumulo(屬于分布式KV數(shù)據(jù)庫)來存儲社會關(guān)系網(wǎng)絡(luò)數(shù)據(jù)。

(2) 圖數(shù)據(jù)查詢

圖數(shù)據(jù)查詢其實(shí)就是”遍歷”圖(Traverse)。圖數(shù)據(jù)庫查詢語言可以使用Gremlin、Cypher等查詢語言來查詢圖。例如Neo4j就支持Cypher查詢語言。

Cyper查詢語言需要以一個節(jié)點(diǎn)來啟動(START)查詢，然后使用MATCH關(guān)鍵詞以WHERE關(guān)鍵字過濾節(jié)點(diǎn)或者關(guān)系的屬性，最后以RETRUN關(guān)鍵詞來指定查詢所返回的數(shù)據(jù)是節(jié)點(diǎn)、關(guān)系還是節(jié)點(diǎn)或者關(guān)系的屬性字段。例如：

START barbara = node:nodeindex(name=”Barbara”);
MATCH(barbara)—(connected_node)
RETURNconnected_node.

(3) 兩類圖數(shù)據(jù)庫區(qū)別

第一類與第二類圖數(shù)據(jù)庫區(qū)別在于以下幾點(diǎn)：

查詢功能方面

第一類圖數(shù)據(jù)庫可以以非常高效率方式支持復(fù)雜查詢，既支持從指定起點(diǎn)開始，以任意深度來遍歷圖，并且還可以支持各種過濾。這樣就可以很方便的執(zhí)行各種圖專用查詢?nèi)蝿?wù)，例如“查找兩個節(jié)點(diǎn)間所有路徑或者最短路徑”等。相反第二類數(shù)據(jù)庫則只能支持較為簡單查詢，如FlockDB就只支持深度為1的關(guān)系遍歷(個人認(rèn)為也可以實(shí)現(xiàn)，只是效率不高)。

可擴(kuò)展性方面

大部分第一種圖形數(shù)據(jù)庫都不支持分布，個人認(rèn)為可能分布后這種復(fù)雜查詢難以做到高效，因此可擴(kuò)展性不好。而第二種由于只支持簡單的圖便歷，一般通過采取按“邊”切分的方法來進(jìn)行分布存儲，因此可擴(kuò)展性較好。

2) 圖數(shù)據(jù)OLAP處理

對圖數(shù)據(jù)進(jìn)行復(fù)雜分析，就需要分布式的批處理框架。例如大規(guī)模的PageRank計算。在這個領(lǐng)域出現(xiàn)并行圖計算框架常見有Apache Giraph、Apache Hama、GraphLab、Pregel、GraphX等。

Pregel是Google根據(jù)BSP并行計算模型開發(fā)的圖計算引擎，目前該系統(tǒng)沒有開源。GraphX是Spark項(xiàng)目組基于Spark框架開發(fā)的圖計算引擎;而GraphLab則是直接在MPI框架基礎(chǔ)上開發(fā)的專用圖計算引擎。

下面簡單介紹幾種主流并行圖計算引擎。

1) 基于BSP模型的Pregel引擎

簡介

Pregel是Google公司開發(fā)的并行圖計算引擎，主要用于實(shí)現(xiàn)各種機(jī)器學(xué)習(xí)算法。Pregel的輸入是一個有向圖，該有向圖每一個頂點(diǎn)都有一個相應(yīng)由String描述的頂點(diǎn)標(biāo)識符。每一個頂點(diǎn)都有一個與之對應(yīng)可修改用戶自定義值。每一條有向邊都和其源頂點(diǎn)關(guān)聯(lián)，并且也擁有一個可修改的用戶自定義值，并同時還記錄了其目標(biāo)頂點(diǎn)的標(biāo)識符。

Pregel可以采用多種文件格式進(jìn)行圖的保存，比如可以用text文件、關(guān)系數(shù)據(jù)庫、Bigtable。為了避免規(guī)定死一種特定文件格式，Pregel將從輸入中解析出圖結(jié)構(gòu)的任務(wù)從圖的計算過程中進(jìn)行了分離。計算結(jié)果可以以任何一種格式輸出并根據(jù)應(yīng)用程序選擇最適合的存儲方式。Pregel library本身提供了很多常用文件格式的readers和writers，但是用戶可以通過繼承Reader和Writer類來定義他們自己的讀寫方式。

編寫一個Pregel程序需要繼承Pregel中已預(yù)定義好的一個基類——Vertex類。

用戶覆寫Vertex類的虛函數(shù)Compute()，該函數(shù)會在每一個超級步中對每一個頂點(diǎn)進(jìn)行調(diào)用。預(yù)定義的Vertex類方法允許Compute()方法查詢當(dāng)前頂點(diǎn)及其邊的信息，以及發(fā)送消息到其他的頂點(diǎn)。Compute()方法可以通過調(diào)用GetValue()方法來得到當(dāng)前頂點(diǎn)的值，或者通過調(diào)用MutableValue()方法來修改當(dāng)前頂點(diǎn)的值。同時還可以通過由出邊的迭代器提供的方法來查看修改出邊對應(yīng)的值。

基于BSP的執(zhí)行模型

讀取輸入初始化該圖，當(dāng)圖被初始化好后，運(yùn)行一系列的超級步直到整個計算結(jié)束，這些超級步之間通過一些全局的同步點(diǎn)分隔，輸出結(jié)果結(jié)束計算。

在每個超級步中，頂點(diǎn)的計算都是并行的，每個頂點(diǎn)執(zhí)行相同的用于表達(dá)給定算法邏輯的用戶自定義函數(shù)。每個頂點(diǎn)可以修改其自身及其出邊的狀態(tài)，接收前一個超級步(S-1)中發(fā)送給它的消息，并發(fā)送消息給其他頂點(diǎn)(這些消息將會在下一個超級步中被接收)，甚至是修改整個圖的拓?fù)浣Y(jié)構(gòu)。邊，在這種計算模式中并不是核心對象，沒有相應(yīng)的計算運(yùn)行在其上。

算法是否能夠結(jié)束取決于是否所有的頂點(diǎn)都已經(jīng)“vote”標(biāo)識其自身已經(jīng)達(dá)到“halt”狀態(tài)了。在第0個超級步，所有頂點(diǎn)都處于active狀態(tài)，所有的active頂點(diǎn)都會參與所有對應(yīng)superstep中的計算。頂點(diǎn)通過將其自身的status設(shè)置成“halt”來表示它已經(jīng)不再active。這就表示該頂點(diǎn)沒有進(jìn)一步的計算需要執(zhí)行，除非被再次被外部觸發(fā)，而Pregel框架將不會在接下來的superstep中執(zhí)行該頂點(diǎn)，除非該頂點(diǎn)收到其它頂點(diǎn)傳送的消息。如果頂點(diǎn)接收到消息被喚醒進(jìn)入active狀態(tài)，那么在隨后的計算中該頂點(diǎn)必須顯式的deactive。整個計算在所有頂點(diǎn)都達(dá)到“inactive”狀態(tài)，并且沒有message在傳送的時候宣告結(jié)束。

2) graphLab

(1) 簡介

GraphLab一套基于c++的開源圖計算庫，提供了在共享內(nèi)存情況下的異步、動態(tài)和并行圖計算的高層抽象API。該庫采用MPI和TCPIP來實(shí)現(xiàn)進(jìn)程間通訊，采用Pthreads實(shí)現(xiàn)進(jìn)程內(nèi)的多線程并發(fā)計算，支持從HDFS和標(biāo)準(zhǔn)文件系統(tǒng)中讀取數(shù)據(jù)。GraphLab定義了多種用于存儲圖的文件格式，包括'tsv','snap', 'adj' 'bintsv4'。

(2) 與Pregel的不同

GraphLab不是采用BSP的嚴(yán)格執(zhí)行模型，GraphLab的基于BSP的Pregel的典型的改進(jìn)是在更好的“異步迭代計算”和“動態(tài)計算”。因此該框架計算效率比Pregel更好。

異步計算：很多重要的MLDM算法迭代更新一大批參數(shù)，圖結(jié)構(gòu)導(dǎo)致參數(shù)更新依賴其它的參數(shù)。同步系統(tǒng)會以上一次更新的參數(shù)基礎(chǔ)上一次更新所有的參數(shù)(BSP模型中超級步之間市全局路障同步)，而異步系統(tǒng)則以最近的參數(shù)作為輸入來更新參數(shù)。異步迭代更新可以極大加 快MLDM算法的計算速度。因?yàn)槿绻捎猛接嬎?，則存在木桶效應(yīng)，整體速度取決于最慢的那臺機(jī)器。在大規(guī)模云計算環(huán)境下，負(fù)載不均衡、網(wǎng)絡(luò)不均衡、硬件差異和多租戶等會導(dǎo)致不同 機(jī)器之間的速度存在差異。另外由于圖分割不均衡，以及計算復(fù)雜性等導(dǎo)致各個節(jié)點(diǎn)計算量也不均衡。

動態(tài)計算：很多MLDM算法的迭代計算收斂都不對稱，例如在參數(shù)優(yōu)化是，通常很多參數(shù)在很少幾次迭代中就會快速收斂，而剩下少數(shù)參數(shù)則即使經(jīng)過多次迭代也會收斂很慢。因此如果我們等同更新所有的參數(shù)，則會浪費(fèi)大量的時間在重復(fù)計算那些已近收斂的參數(shù)上。最近的一些計算框架部分支持動態(tài)計算，例如Pregel可以通過讓某些節(jié)點(diǎn)跳過一些超級步來部分支持動態(tài)計算。

(3) GraphLab的計算模型

graphLab包括三個部分：數(shù)據(jù)圖、更新函數(shù)、同步操作。數(shù)據(jù)圖表達(dá)用戶可修改 的程序狀態(tài)，存儲可變的用戶自定義數(shù)據(jù)和計算之間依賴。更新函數(shù)通過一個scope的數(shù)據(jù)變換來表達(dá)用戶對數(shù)據(jù)圖的計算和操作。同步操作并發(fā)維護(hù)全局匯總。

一個點(diǎn)的scope代表存儲在這個點(diǎn)上的數(shù)據(jù) 和所有與這個點(diǎn)相鄰的點(diǎn)和邊上的所有數(shù)據(jù)。update f (v ,s(v) ) ---> (s(v) , 邊集合) 。經(jīng)過一個更新函數(shù)后，新計算出 的s(v) 會被寫回圖，并返回一個定點(diǎn)集合，針對該集合的每個點(diǎn)再執(zhí)行 f(u ,s(u))

為了更高效的并行執(zhí)行，GraphLab容許GraphLab框架動態(tài)的選擇執(zhí)行順序，即RemoveNext(T)的返回值。因?yàn)楹芏郙LDM算法需要執(zhí)行優(yōu)先級別，因此也可以指定點(diǎn)的優(yōu)先級，這樣GraphLab會綜合考慮優(yōu)先級以及網(wǎng)絡(luò)情況來調(diào)度。

(3) GraphLab的并行計算

根據(jù)領(lǐng)域知識，將圖分割為K份，K值遠(yuǎn)大于機(jī)器數(shù)量。每個分區(qū)被稱為atom, 以一個文件形式存儲類似HDFS的分布式文件系統(tǒng)上。Atom中存儲的是增加點(diǎn)和變的操作記錄，可以通過回放的方式來重構(gòu)圖。

采取把點(diǎn)著色的方法，先保證每個點(diǎn)和相鄰點(diǎn)之間的顏色都不相同。通過一個顏色一個顏色的并發(fā)執(zhí)行，來實(shí)現(xiàn)邊一致性。把這種成為顏色步，與BSP的超步模型相對應(yīng)。該引擎保證在執(zhí)行下一個顏色步之前，所有的修改都被傳遞，實(shí)現(xiàn)顏色步之間的路障同步。

由Master根據(jù)atom索引來計算atom的位置，并負(fù)責(zé)機(jī)器與atom之間的分配關(guān)系。然后每個機(jī)器讀取atom文件來加載圖。每個機(jī)器上有一個調(diào)度器負(fù)責(zé)調(diào)度屬于自己的子圖的點(diǎn)的計算。調(diào)度器負(fù)責(zé)把每個需要執(zhí)行update 函數(shù)之前所需要的數(shù)據(jù)和鎖準(zhǔn)備好后，放入一個流水處理隊(duì)列中，再由一個worker線程池來執(zhí)行，通過一個分布式算法來確定所有機(jī)器上的調(diào)度器中的T為空，也就是整個計算結(jié)束。

3)graphX

基于SPARK圖形計算引擎，GraphX提供的API可以很方便的表達(dá)各種針對的轉(zhuǎn)換、過濾和查詢操作，但是GraphX不能直接實(shí)現(xiàn)迭代并行圖計算算法，但是可以基于這些API用來實(shí)現(xiàn)各種并行圖計算算法。在GraphX論文中描述了利用GraphX來實(shí)現(xiàn)Pregel、PowerGraph的方法。

GraphX的優(yōu)勢是可以很方便的與shark等進(jìn)行集成，例如直接對shark查詢后的結(jié)果進(jìn)行圖計算。

4) 總結(jié)

(1)上述計算引擎都可以以靈活方式來存儲圖，基本上都可以以文件方式來存儲圖數(shù)據(jù)，實(shí)現(xiàn)計算引擎與存儲分離。

(2)圖計算引擎都根據(jù)MDML算法特點(diǎn)采用專用計算模型，以提高效率。

(3) 所有圖計算引擎在計算時，基本都是需要把數(shù)據(jù)都加載到內(nèi)存中。(來自preglel論文：當(dāng)前整個的計算狀態(tài)都是駐留在內(nèi)存中的。我們已經(jīng)開始將一些數(shù)據(jù)存到本地磁盤，同時我們會繼續(xù)在這個方向進(jìn)行深入的研究，希望可以支持規(guī)模太大以至于內(nèi)存無法完全存下的情況。