內(nèi)存數(shù)據(jù)倉庫集群技術(shù)研究

張延松， 王 珊， 周 烜

（1.中國人民大學(xué)DEKE實(shí)驗(yàn)室，北京 100872；2.中國人民大學(xué) 信息學(xué)院，北京 100872；3.中國人民大學(xué) 中國調(diào)查與數(shù)據(jù)中心，北京 100872）

0 引 言

數(shù)據(jù)倉庫是企業(yè)級(jí)大數(shù)據(jù)應(yīng)用重要的平臺(tái)，長期以來一直受性能問題的制約而難以在企業(yè)級(jí)實(shí)時(shí)分析處理（Real Time Analytics）領(lǐng)域發(fā)揮出其應(yīng)有的作用.隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展，多核處理器和大內(nèi)存成為主流配置，如最新的Intel？Xeon？Processor E7－8890

v2處理器擁有15個(gè)處理內(nèi)核、30線程，每插槽最大支持1.5TB內(nèi)存，而DRAM的價(jià)格每12個(gè)月下降32%，內(nèi)存計(jì)算技術(shù)在內(nèi)存容量支持、硬件成本和計(jì)算性能等幾個(gè)方面已經(jīng)能夠滿足企業(yè)級(jí)大數(shù)據(jù)計(jì)算的需求，內(nèi)存計(jì)算平臺(tái)逐漸成為大數(shù)據(jù)計(jì)算新興的高性能平臺(tái).Gartner公司在2013年IT行業(yè)十大技術(shù)發(fā)展趨勢(shì)中指出內(nèi)存計(jì)算將成為主流［1］，內(nèi)存數(shù)據(jù)庫技術(shù)，已經(jīng)被越來越多的傳統(tǒng)和新興的數(shù)據(jù)庫廠商所采納，如MonetDB［2］、Vectorwise［3］、HANA［4］、IWA［5］、Oracle Exadata X3［6］、SQL server2014［7］等，并成為主流產(chǎn)品，內(nèi)存數(shù)據(jù)庫不僅能夠提供傳統(tǒng)數(shù)據(jù)庫無法實(shí)現(xiàn)的實(shí)時(shí)分析處理性能，由于內(nèi)存相對(duì)于磁盤能耗更低，內(nèi)存數(shù)據(jù)庫技術(shù)的引入還能夠更好地降低數(shù)據(jù)中心總成本（TCO）［8］.同時(shí)，由于內(nèi)存計(jì)算性能更高，不需要依賴存儲(chǔ)代價(jià)極大的物化視圖及索引機(jī)制，在列存儲(chǔ)和壓縮技術(shù)的支持下，內(nèi)存存儲(chǔ)相對(duì)于傳統(tǒng)的磁盤存儲(chǔ)具有更高的效率.

在軟、硬件技術(shù)的支持下，內(nèi)存數(shù)據(jù)倉庫將會(huì)成為新的大數(shù)據(jù)實(shí)時(shí)分析處理平臺(tái).內(nèi)存數(shù)據(jù)倉庫需要解決的關(guān)鍵問題主要包括性能和擴(kuò)展性.內(nèi)存相對(duì)于傳統(tǒng)的磁盤，其數(shù)據(jù)訪問性能得到了極大的提升，但內(nèi)存訪問延遲和帶寬性能的緩慢提升使大內(nèi)存相對(duì)于高性能多核處理器成為“新硬盤”，仍然是內(nèi)存數(shù)據(jù)倉庫大數(shù)據(jù)處理性能的瓶頸因素.性能問題，一方面需要采用多核CPU、GPU、Phi協(xié)處理器等新硬件提升數(shù)據(jù)處理性能；另一方面需要面向Flash、PCM（相變存儲(chǔ)）等新的存儲(chǔ)硬件技術(shù)提高性價(jià)比和綜合性能.在當(dāng)前硬件水平下，內(nèi)存數(shù)據(jù)倉庫集群仍然是擴(kuò)展內(nèi)存數(shù)據(jù)倉庫處理能力和性能的有效技術(shù)手段，通過中低端內(nèi)存計(jì)算集群構(gòu)建高性能內(nèi)存數(shù)據(jù)倉庫平臺(tái)，降低內(nèi)存數(shù)據(jù)倉庫的成本并提供高可擴(kuò)展的并行內(nèi)存計(jì)算能力.

內(nèi)存數(shù)據(jù)倉庫集需要解決兩類關(guān)鍵技術(shù)問題：數(shù)據(jù)分布模型和集群計(jì)算模型.數(shù)據(jù)分布模型需要考慮模式和關(guān)系兩個(gè)層面的分布策略：模式層面的分布策略需要考慮數(shù)據(jù)倉庫中不同類型的表，如維表和事實(shí)表，如何在集群中分布存儲(chǔ)，分布模型所帶來的數(shù)據(jù)存儲(chǔ)代價(jià)以及數(shù)據(jù)更新代價(jià)；關(guān)系層面的分布模型需要考慮采用基于行還是基于列的分布存儲(chǔ)模型等問題.集群計(jì)算模型則以數(shù)據(jù)分布式存儲(chǔ)模型為基礎(chǔ)，針對(duì)不同計(jì)算類型實(shí)現(xiàn)不同的并行計(jì)算.

本文以內(nèi)存數(shù)據(jù)倉庫集群技術(shù)為中心，概要地介紹了我們?cè)趦?nèi)存數(shù)據(jù)倉庫集群技術(shù)方面的研究技術(shù)、方法和手段，探討在不同的應(yīng)用需求和硬件支持下的內(nèi)存數(shù)據(jù)倉庫集群不同的實(shí)現(xiàn)技術(shù)及其特點(diǎn).大體結(jié)構(gòu)是第1節(jié)介紹以列相關(guān)分布模型和列計(jì)算服務(wù)為基礎(chǔ)的內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng)ScaMMDB的設(shè)計(jì)思想和系統(tǒng)實(shí)現(xiàn)技術(shù)路線；第2節(jié)介紹基于水平分片的內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng)ScaMMDBⅡ及其面向不同類型聚集函數(shù)的并行查詢處理技術(shù)；第3節(jié)介紹基于reverse－star schema數(shù)據(jù)分布模型和向量處理技術(shù)的內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng)MiNT－OLAPCluster系統(tǒng)的實(shí)現(xiàn)技術(shù)；第4節(jié)總結(jié)全文并對(duì)內(nèi)存數(shù)據(jù)倉庫集群技術(shù)的技術(shù)發(fā)展趨勢(shì)進(jìn)行展望和分析.

1 基于列相關(guān)分布模型和列計(jì)算服務(wù)的ScaMMDB系統(tǒng)

MonetDB是一種基于列存儲(chǔ)和BAT algebra列計(jì)算的開源數(shù)據(jù)庫系統(tǒng)，是分析型內(nèi)存數(shù)據(jù)庫最具代表性的系統(tǒng).MonetDB的高性能構(gòu)建在充足內(nèi)存空間的基礎(chǔ)上，當(dāng)數(shù)據(jù)量超過內(nèi)存容量時(shí)，MonetDB通過虛擬內(nèi)存進(jìn)行I／O交換，查詢處理性能受到極大的影響.ScaMMDB系統(tǒng)根據(jù)網(wǎng)絡(luò)技術(shù)的發(fā)展趨勢(shì)構(gòu)建了一個(gè)基于高速網(wǎng)絡(luò)平臺(tái)的可擴(kuò)展內(nèi)存數(shù)據(jù)庫集群系統(tǒng)，將數(shù)據(jù)和計(jì)算分布在不同的節(jié)點(diǎn)上，通過集群擴(kuò)展技術(shù)保證內(nèi)存存儲(chǔ)和內(nèi)存計(jì)算，其關(guān)鍵技術(shù)包括：基于網(wǎng)絡(luò)傳輸代價(jià)的列分布策略、基于內(nèi)存塊的節(jié)點(diǎn)間列復(fù)制技術(shù)、分布式列計(jì)算技術(shù)等.

1.1 ScaMMDB系統(tǒng)結(jié)構(gòu)

ScaMMDB是一種協(xié)同計(jì)算模式的內(nèi)存數(shù)據(jù)庫集群，如圖1所示，數(shù)據(jù)庫以列為單位在集群節(jié)點(diǎn)的內(nèi)存上進(jìn)行數(shù)據(jù)分布.每個(gè)節(jié)點(diǎn)均可以訪問本地內(nèi)存和其他節(jié)點(diǎn)的網(wǎng)絡(luò)虛擬內(nèi)存NetMemory，通過輕量數(shù)據(jù)字典表獲取每個(gè)列的存儲(chǔ)位置信息，將計(jì)算下推到列存儲(chǔ)節(jié)點(diǎn)，完成協(xié)同計(jì)算任務(wù)，只將列操作結(jié)果傳回查詢發(fā)起節(jié)點(diǎn).在并發(fā)查詢處理時(shí)，查詢?nèi)蝿?wù)可以均衡地分布在集群中的所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)負(fù)責(zé)完成本節(jié)點(diǎn)和其他節(jié)點(diǎn)的協(xié)同式列計(jì)算任務(wù).數(shù)據(jù)列作為存儲(chǔ)的基本單位提供列上的計(jì)算服務(wù)，可以由本地節(jié)點(diǎn)調(diào)用列計(jì)算API，也可以由集群其他節(jié)點(diǎn)遠(yuǎn)程調(diào)用，每個(gè)節(jié)點(diǎn)既是查詢服務(wù)的提供者又是查詢服務(wù)的消費(fèi)者，集群節(jié)點(diǎn)通過協(xié)同計(jì)算完成整個(gè)查詢?nèi)蝿?wù).當(dāng)集群規(guī)模變化時(shí)，即增加或減少集群節(jié)點(diǎn)時(shí)，通過數(shù)據(jù)列在節(jié)點(diǎn)間的遷移和對(duì)輕量數(shù)據(jù)字典的更新重置列計(jì)算API調(diào)用的服務(wù)位置.

圖1 ScaMMDB系統(tǒng)結(jié)構(gòu)Fig.1 Architecture of ScaMMDB

1.2 ScaMMDB的關(guān)鍵技術(shù)

ScaMMDB的目標(biāo)是構(gòu)建一個(gè)可擴(kuò)展的虛擬內(nèi)存以支持大數(shù)據(jù)內(nèi)存分析，基礎(chǔ)的技術(shù)假設(shè)是高速網(wǎng)絡(luò)技術(shù)的發(fā)展使網(wǎng)絡(luò)帶寬的增長速度大大優(yōu)于磁盤I／O的增長速度.世界超級(jí)計(jì)算機(jī)500強(qiáng)系統(tǒng)中主要采用InfiniBand和千兆以太網(wǎng)技術(shù)，這兩種技術(shù)都能夠提供超過100Gbps的數(shù)據(jù)傳輸性能.基于高速互聯(lián)網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)內(nèi)存NetMemory可以作為本地內(nèi)存的下一級(jí)存儲(chǔ)，共享集群中節(jié)點(diǎn)內(nèi)存存儲(chǔ)資源.Oracle RAC的內(nèi)存融合技術(shù)（Cache Fusion）實(shí)現(xiàn)共享內(nèi)存訪問，將集群節(jié)點(diǎn)的內(nèi)存融合為一個(gè)虛擬的大內(nèi)存.分布式內(nèi)存技術(shù)（distributed shared memory，DSM）是一種將本地和遠(yuǎn)程節(jié)點(diǎn)內(nèi)存通過虛擬內(nèi)存地址來訪問和處理的技術(shù)，也是一種構(gòu)建集群虛擬內(nèi)存的技術(shù).與這兩種虛擬內(nèi)存技術(shù)不同，ScaMMDB的NetMemory的存儲(chǔ)單位是數(shù)據(jù)列，通過MonetDB底層的BAT訪問API將遠(yuǎn)程數(shù)據(jù)列上的操作下推到列存儲(chǔ)節(jié)點(diǎn)，通過遠(yuǎn)程BAT操作API的調(diào)用實(shí)現(xiàn)數(shù)據(jù)列的本地計(jì)算，只將較小的列處理結(jié)果返回?cái)?shù)據(jù)請(qǐng)求節(jié)點(diǎn).相對(duì)于Cache Fusion和DSM技術(shù)，NetMemory提供的不僅僅是虛擬內(nèi)存上的存儲(chǔ)訪問服務(wù)，還包括遠(yuǎn)程節(jié)點(diǎn)的列計(jì)算服務(wù).

ScaMMDB系統(tǒng)的關(guān)鍵技術(shù)包括如何實(shí)現(xiàn)基于集群節(jié)點(diǎn)協(xié)同計(jì)算模式的查詢重寫，如何優(yōu)化數(shù)據(jù)列的網(wǎng)絡(luò)傳輸性能，如何根據(jù)查詢負(fù)載特征實(shí)現(xiàn)數(shù)據(jù)列的關(guān)聯(lián)分布等.

1.2.1 基于集群節(jié)點(diǎn)協(xié)同計(jì)算模式的查詢重寫

SQL命令在MonetDB內(nèi)部被轉(zhuǎn)換為MAL命令集，由查詢引擎執(zhí)行.我們通過客戶端獲得SQL命令，根據(jù)MAL命令轉(zhuǎn)換規(guī)則將其重寫并由MAL引擎執(zhí)行，完成ExMAL的執(zhí)行.在將MAL命令序列轉(zhuǎn)換為ExMAL命令執(zhí)行序列時(shí)，我們通過擴(kuò)展MonetDB底層的mserver.connect（）函數(shù)實(shí)現(xiàn)集群節(jié)點(diǎn)間的遠(yuǎn)程列計(jì)算調(diào)用，并開發(fā)了節(jié)點(diǎn)間列復(fù)制接口mserver.PutBat（）和mserver.GetBat（），實(shí)現(xiàn)從遠(yuǎn)程節(jié)點(diǎn)中獲取BAT和將當(dāng)前BAT推送到遠(yuǎn)程節(jié)點(diǎn)的操作，通過MonetDB的BBP緩沖池機(jī)制實(shí)現(xiàn)不同線程之間的列數(shù)據(jù)共享訪問.在擴(kuò)展的底層BAT接口的支持下，SQL命令能夠被改寫為面向集群分布式列存儲(chǔ)模型的協(xié)同計(jì)算ExMAL命令集.

如圖2所示的TPC－H的Q1測(cè)試查詢對(duì)應(yīng)的MAL命令序列中，兩條MAL命令分別在場(chǎng)地：node1和node2上執(zhí)行，其中，在node2上執(zhí)行的MAL命令需要node1上的BAT作為操作數(shù)BAT，需要通過線程間數(shù)據(jù)共享訪問機(jī)制和GetBAT完成BAT遠(yuǎn)程復(fù)制.

圖2所示的例子中，遠(yuǎn)程MAL命令執(zhí)行步驟如下：

（1）在主控節(jié)點(diǎn)node0上建立與node1的連接；

（2）通過與node1的連接，將BAT的bind命令發(fā)送到node1節(jié)點(diǎn)上運(yùn)行；（3）在主控節(jié)點(diǎn)node0上建立與node2的連接；

（4）通過與node2的連接，在node2上執(zhí)行與node1的連接；

（5）node0與node1的連接與node2與node1的連接對(duì)應(yīng)不同的處理線程，通過將node1連接中的BAT變量＿56裝入BBP，然后在node2的連接中訪問BBP中的共享變量＿56；

（6）通過node1與node2的連接，在node2上執(zhí)行遠(yuǎn)程復(fù)制node1上的BAT＿56；

（7）通過GetBAT（RemoteBind）在本地生成遠(yuǎn)程BAT復(fù)本；

（8）通過與node2的連接，在node2上執(zhí)行連接操作.

圖2 ScaMMDB的協(xié)同計(jì)算［9］Fig.2 Co－computing in ScaMMDB［9］

當(dāng)MAL命令中涉及不同節(jié)點(diǎn)上的BAT時(shí)，需要通過對(duì)BAT大小和數(shù)量的估算評(píng)估網(wǎng)絡(luò)傳輸代價(jià)，選擇網(wǎng)絡(luò)傳輸代價(jià)最低的節(jié)點(diǎn)作為當(dāng)前MAL命令的執(zhí)行節(jié)點(diǎn).

1.2.2 數(shù)據(jù)列的網(wǎng)絡(luò)傳輸優(yōu)化技術(shù)

集群節(jié)點(diǎn)間進(jìn)行列數(shù)據(jù)傳輸時(shí)，我們?cè)谀繕?biāo)節(jié)點(diǎn)根據(jù)源節(jié)點(diǎn)BAT結(jié)構(gòu)通過BAT.new（）函數(shù)構(gòu)造相同結(jié)構(gòu)的BAT，在發(fā)送端PutBat（）函數(shù)調(diào)用時(shí)根據(jù)BAT的內(nèi)存結(jié)構(gòu)直接復(fù)制列數(shù)據(jù)塊，如圖3所示，varchar類型的列需要復(fù)制BAT列和數(shù)據(jù)實(shí)際存儲(chǔ)內(nèi)存塊，以提高網(wǎng)絡(luò)傳輸效率，并在接收端克隆出與源BAT相同的目標(biāo)BAT，完成BAT在節(jié)點(diǎn)間的復(fù)制.通過基于內(nèi)存塊的傳輸優(yōu)化技術(shù)，在千兆以太網(wǎng)中我們能夠獲得80 MB／s左右的傳輸速度，接近千兆以太網(wǎng)理論的傳輸速度.

圖3 基于BAT存儲(chǔ)結(jié)構(gòu)的網(wǎng)絡(luò)傳輸Fig.3 BAT structure oriented BAT transmission

1.2.3 基于查詢負(fù)載特征的數(shù)據(jù)列關(guān)聯(lián)分布

ScaMMDB系統(tǒng)的協(xié)同計(jì)算模式能夠?qū)LAP查詢中選擇率低的操作下推到列存儲(chǔ)節(jié)點(diǎn)執(zhí)行，降低網(wǎng)絡(luò)數(shù)據(jù)傳輸代價(jià)，但在普通的千兆以太網(wǎng)環(huán)境下，網(wǎng)絡(luò)數(shù)據(jù)傳輸代價(jià)仍然占較高的比例.圖4列出了TPC－H中部分測(cè)試查詢?cè)谇д滓蕴W(wǎng)中的列傳輸代價(jià)占查詢總代價(jià)的比例，以及模擬10 Gbps和Tbps以太網(wǎng)的數(shù)據(jù)傳輸代價(jià).我們可以看到，在未來的Tbps高速網(wǎng)絡(luò)傳輸技術(shù)的支持下，BAT傳輸延遲將低于0.5%，能夠更好地發(fā)揮ScaMMDB的可擴(kuò)展查詢處理性能.

圖4 不同網(wǎng)絡(luò)性能下的網(wǎng)絡(luò)傳輸代價(jià)比例Fig.4 Network transmission cost ratio in different networks

除了依賴高速網(wǎng)絡(luò)技術(shù)的發(fā)展來降低虛擬內(nèi)存訪問延遲之外，我們進(jìn)一步通過提高列分布的關(guān)聯(lián)性減少協(xié)同計(jì)算時(shí)的數(shù)據(jù)傳輸.我們采用屬性距離矩陣（Attribute Distance Matrix，ADM）來評(píng)估并量化分析出屬性之間相關(guān)性的強(qiáng)弱，優(yōu)先分布相關(guān)性高的屬性集合.系統(tǒng)數(shù)據(jù)分布策略分為三個(gè)階段：① 根據(jù)相對(duì)固定的OLAP查詢命令集和統(tǒng)計(jì)信息生成ADM；② 根據(jù)屬性相關(guān)性度量值進(jìn)行屬性聚類，根據(jù)節(jié)點(diǎn)數(shù)量將相關(guān)性強(qiáng)的屬性集聚類為節(jié)點(diǎn)數(shù)量個(gè)相關(guān)屬性集合，確定高訪問頻率的屬性的分布策略；③ 根據(jù)第二階段的部分?jǐn)?shù)據(jù)分布策略和節(jié)點(diǎn)內(nèi)存容量（內(nèi)存占用低于75%時(shí)性能較優(yōu)）調(diào)整其余屬性的分布策略，保證全部屬性分布在系統(tǒng)節(jié)點(diǎn)上并保證每個(gè)節(jié)點(diǎn)上的數(shù)據(jù)負(fù)載相對(duì)均衡.

在列存儲(chǔ)數(shù)據(jù)庫中，查詢處理的最小單位是屬性列，即任何查詢都最終被分解為一系列的列操作，關(guān)聯(lián)性體現(xiàn)在屬性列之間的協(xié)同訪問關(guān)系上，所以在列存儲(chǔ)數(shù)據(jù)庫中，關(guān)聯(lián)性定義為屬性與屬性之間是否存在關(guān)聯(lián)訪問關(guān)系，如在MAL命令“＿21｛rows＝4：lng｝：＝algebra.join（＿18，＿19）；”中，BAT ＿18、＿19對(duì)應(yīng)的屬性存在關(guān)聯(lián)性.根據(jù) BAT 代數(shù)的特點(diǎn)，我們確定了屬性關(guān)聯(lián)性規(guī)則：① 出現(xiàn)在同一謂詞表達(dá)式中的屬性具有屬性關(guān)聯(lián)性；②GROUP BY、ORDER BY屬性為關(guān)聯(lián)性屬性；③ 代數(shù)表達(dá)式中的屬性為關(guān)聯(lián)性屬性；④ 邏輯運(yùn)算符連接的所有屬性具有關(guān)聯(lián)性.通過屬性關(guān)聯(lián)性的定義，我們將MAL命令中BAT操作的多元操作數(shù)盡量集中在相同節(jié)點(diǎn)上，減少BAT操作時(shí)的網(wǎng)絡(luò)傳輸代價(jià).我們通過關(guān)聯(lián)矩陣聚類算法將TPC－H的列聚類到n個(gè)節(jié)點(diǎn)上，并通過節(jié)點(diǎn)內(nèi)存容量進(jìn)行調(diào)整，生成最優(yōu)數(shù)據(jù)分布策略.圖5（b）圖為不同數(shù)據(jù)分布策略在TPC－H查詢中所產(chǎn)生的網(wǎng)絡(luò)傳輸數(shù)據(jù)量，基于統(tǒng)計(jì)和聚類算法的分布策略能夠有效地降低查詢處理時(shí)的網(wǎng)絡(luò)傳輸代價(jià).圖5（a）顯示了ScaMMDB集群計(jì)算模式相對(duì)于集中式計(jì)算模式的性能提升，內(nèi)存數(shù)據(jù)庫集群能夠有效地消除I／O代價(jià)，發(fā)揮出內(nèi)存計(jì)算的優(yōu)越性能.

ScaMMDB是一個(gè)可擴(kuò)展的內(nèi)存數(shù)據(jù)庫系統(tǒng)，系統(tǒng)的各個(gè)節(jié)點(diǎn)可以同時(shí)接受用戶的查詢請(qǐng)求并在各個(gè)節(jié)點(diǎn)的協(xié)同下輸出最終的結(jié)果，系統(tǒng)吞吐量將大于單節(jié)點(diǎn)內(nèi)存數(shù)據(jù)庫系統(tǒng).

我們?cè)?007—2008年期間開展內(nèi)存數(shù)據(jù)庫集群ScaMMDB的研究工作，當(dāng)時(shí)還沒有內(nèi)存數(shù)據(jù)庫集群系統(tǒng)和產(chǎn)品，2012年，Vectorwise系統(tǒng)上進(jìn)行了一些集群并行的研究工作［18］，但并沒有形成獨(dú)立的產(chǎn)品.我們?cè)赟caMMDB性能測(cè)試時(shí)沒有可對(duì)比的內(nèi)存數(shù)據(jù)庫系統(tǒng)，因此我們采用了通過TPC－H測(cè)試基準(zhǔn)中的吞吐量指標(biāo)Throughput＠Size來衡量ScaMMDB的吞吐量的方法來測(cè)量ScaMMDB系統(tǒng)的加速比指標(biāo)，在一個(gè)3節(jié)點(diǎn)的內(nèi)存數(shù)據(jù)庫集群中，ScaMMDB的吞吐量是單節(jié)點(diǎn)MonetDB的近3倍.

1.3 ScaMMDB的應(yīng)用場(chǎng)景

圖5 數(shù)據(jù)傳輸性能和查詢性能［10］Fig.5 Network transmission and query processing performance［10］

ScaMMDB是一種以列存儲(chǔ)和列計(jì)算為中心的集群協(xié)同計(jì)算模型，它實(shí)現(xiàn)簡單，能夠在MonetDB底層API的基礎(chǔ)上通過擴(kuò)展網(wǎng)絡(luò)傳輸與遠(yuǎn)程計(jì)算調(diào)用API實(shí)現(xiàn)系統(tǒng)功能，能夠支持全部復(fù)雜的TPC－H查詢處理任務(wù).在數(shù)據(jù)分布策略上，基于列的聚類分布策略相對(duì)于基于表的數(shù)據(jù)分布策略更加細(xì)粒度且操作性更強(qiáng)，結(jié)合數(shù)據(jù)挖掘的功能能夠自動(dòng)對(duì)系統(tǒng)負(fù)載進(jìn)行監(jiān)測(cè)并更好地實(shí)現(xiàn)負(fù)載均衡.

ScaMMDB不適用于訪問負(fù)載集中于少數(shù)列的應(yīng)用場(chǎng)景，也不適合較大的集群規(guī)模.ScaMMDB的每個(gè)節(jié)點(diǎn)都能夠獨(dú)立地接受查詢請(qǐng)求，適合于并發(fā)查詢處理場(chǎng)景.ScaMMDB依賴于對(duì)MonetDB底層API的擴(kuò)展，隨著MonetDB版本的升級(jí)和MAL命令集的不斷擴(kuò)充，增加了ScaMMDB系統(tǒng)實(shí)現(xiàn)的成本.

2 基于水平分片的內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng)ScaMMDBⅡ

TPC－H是一個(gè)用3NF實(shí)現(xiàn)的數(shù)據(jù)倉庫，是一個(gè)雙事實(shí)表雪花形結(jié)構(gòu)，其中事實(shí)表lineitem和orders表構(gòu)成訂單事實(shí)數(shù)據(jù)集，事實(shí)表lineitem和partsupp表構(gòu)成訂單零件供應(yīng)事實(shí).這兩部分事實(shí)數(shù)據(jù)集占整個(gè)TPC－H數(shù)據(jù)量的95%以上（如SF＝100時(shí)，linteitem：68.24%；orders：14.74%；partsupp：12.28%，而其余5個(gè)維表數(shù)據(jù)量僅占4.74%），而這些巨大的事實(shí)表之間的連接操作代價(jià)成為影響TPC－H性能的關(guān)鍵因素，當(dāng)采用集群處理模式時(shí)，跨節(jié)點(diǎn)的查詢處理任務(wù)產(chǎn)生巨大的網(wǎng)絡(luò)數(shù)據(jù)訪問延遲.

數(shù)據(jù)倉庫在存儲(chǔ)模式設(shè)計(jì)時(shí)需要考慮其查詢處理的類型和未來計(jì)算平臺(tái)上的性能問題，現(xiàn)實(shí)中數(shù)據(jù)倉庫通常采用星形或雪花形模型，使用一個(gè)巨大的事實(shí)表和多個(gè)較小的維表，消除龐大事實(shí)表之間的連接操作，簡化集群并行處理.圖6所示的SSB基準(zhǔn)是對(duì)TPC－H基準(zhǔn)面向OLAP的多維處理特性而進(jìn)行的模式優(yōu)化，數(shù)據(jù)倉庫中只有一個(gè)事實(shí)表，在SF＝100時(shí)事實(shí)表數(shù)據(jù)量占整個(gè)數(shù)據(jù)庫98%以上，較小的維表使多維OLAP查詢優(yōu)化更加簡單，也適合大數(shù)據(jù)集群處理模式.圖6所示的HANA技術(shù)白皮書中示例的星形模型數(shù)據(jù)倉庫是一個(gè)高維結(jié)構(gòu)，維表數(shù)量眾多但非常小，位于中心的事實(shí)表非常龐大，這種數(shù)據(jù)量極端傾斜的多／高維星形結(jié)構(gòu)能夠采用多種優(yōu)化技術(shù)，并且能夠簡化集群分布模型和集群計(jì)算模型，提高大數(shù)據(jù)分析處理效率.

圖 6 星 形模型數(shù)據(jù) 倉庫［11－12］Fig.6 Star schema data warehouses［11－12］

ScaMMDBⅡ針對(duì)星形模型為特征的數(shù)據(jù)倉庫集群技術(shù)而設(shè)計(jì)，根據(jù)維表數(shù)據(jù)量極小和OLAP查詢結(jié)果集極小（在SSB中結(jié)果集為1－800行）的特征采用事實(shí)表水平分片，維表全復(fù)制的簡單數(shù)據(jù)分布策略，集群的任意節(jié)點(diǎn)可以充當(dāng)動(dòng)態(tài)的協(xié)調(diào)者（coordinator），將查詢?nèi)蝿?wù)分派給各個(gè)工作節(jié)點(diǎn)并行執(zhí)行，并對(duì)各執(zhí)行節(jié)點(diǎn)返回的OLAP查詢結(jié)果集進(jìn)行聚集歸并.

2.1 ScaMMDBⅡ系統(tǒng)結(jié)構(gòu)

我們提出了基于sibling cube的可擴(kuò)展內(nèi)存數(shù)據(jù)庫系統(tǒng)ScaMMDBⅡ（ParaCube），如圖7所示，數(shù)據(jù)倉庫的完整數(shù)據(jù)集被劃分為多個(gè)數(shù)據(jù)倉庫子集，其中事實(shí)表被劃分為不相交的n個(gè)數(shù)據(jù)子集分布在n個(gè)MMDB節(jié)點(diǎn)上，維表在n個(gè)數(shù)據(jù)節(jié)點(diǎn)上被全復(fù)制，每個(gè)節(jié)點(diǎn)上運(yùn)行一個(gè)middle ware（ParaCube mediator）作為OLAP客戶端軟件，各個(gè)數(shù)據(jù)庫節(jié)點(diǎn)中數(shù)據(jù)是同構(gòu)的但各節(jié)點(diǎn)上的數(shù)據(jù)庫可以是異構(gòu)的，可以根據(jù)應(yīng)用的需要選擇不同的數(shù)據(jù)庫，對(duì)節(jié)點(diǎn)上的數(shù)據(jù)訪問通過標(biāo)準(zhǔn)的數(shù)據(jù)庫訪問接口JDBC來實(shí)現(xiàn)，屏蔽系統(tǒng)之間的差異，在ParaCube mediator上需要記錄每個(gè)數(shù)據(jù)節(jié)點(diǎn)的元數(shù)據(jù).ParaCube mediator的功能是接受用戶的查詢請(qǐng)求，根據(jù)查詢內(nèi)容完成查詢重寫，通過JDBC將查詢?nèi)蝿?wù)下推并返回查詢處理結(jié)果子集，然后通過多路歸并算法將聚集結(jié)果子集歸并為最終的查詢結(jié)果.系統(tǒng)中可以有唯一的ParaCube mediator也可以維護(hù)多個(gè)ParaCube mediator來提高系統(tǒng)的并發(fā)查詢處理能力.

圖7 基于ParaCube mediator的ScaMMDBⅡ系統(tǒng)Fig.7 ParaCube mediator oriented ScaMMDBⅡsystem

2.2 ScaMMDBⅡ關(guān)鍵技術(shù)

ScaMMDBⅡ是以數(shù)據(jù)為中心的并行OLAP查詢處理模型，根據(jù)OLAP查詢處理中數(shù)據(jù)量大、數(shù)據(jù)粒度大、查詢復(fù)雜度高、查詢目標(biāo)為聚集結(jié)果、高輸入低輸出的特點(diǎn)，優(yōu)化傳統(tǒng)的并行查詢處理技術(shù)，提高并行查詢處理過程中的并行性，優(yōu)化OLAP性能.ScaMMDBⅡ是一種開放的結(jié)構(gòu)，支持異構(gòu)數(shù)據(jù)庫的集成，因此系統(tǒng)能夠根據(jù)應(yīng)用中數(shù)據(jù)量和查詢負(fù)載的變化動(dòng)態(tài)擴(kuò)展系統(tǒng)處理規(guī)模，同時(shí)也支持不同類型系統(tǒng)的集成，支持將事務(wù)型數(shù)據(jù)庫與分析型數(shù)據(jù)庫從邏輯上組織為統(tǒng)一的系統(tǒng)，支持操作型BI（Operational Business Intelligence）的應(yīng)用需求.

2.2.1 數(shù)據(jù)分布策略

如圖8所示，在SF＝100的TPC－H中5個(gè)維表數(shù)據(jù)量低于5%，SSB中4個(gè)維表數(shù)據(jù)量僅占1%左右，當(dāng)集群規(guī)模較小時(shí)，維表全復(fù)制策略能夠最大化本地計(jì)算，最小化網(wǎng)絡(luò)數(shù)據(jù)傳輸代價(jià)，維表全復(fù)制所帶來的存儲(chǔ)空間開銷能夠控制在可接受的范圍之內(nèi)，維表全復(fù)制策略或者維表廣播策略是面向數(shù)據(jù)倉庫模式特征而廣泛采用的簡單有效的數(shù)據(jù)分布技術(shù).從數(shù)據(jù)量分布特征我們也可以看到，將TPC－H滿足3NF的模式設(shè)計(jì)轉(zhuǎn)換為星形模式設(shè)計(jì)能夠使其更加適合集群并行計(jì)算，簡化并行計(jì)算模型.

圖8 TPC－H和SSB測(cè)試集事實(shí)表、維表數(shù)據(jù)分布Fig.8 Data distribution of fact tables and dimension tables in TPC－H and SSB

2.2.2 并行聚集計(jì)算技術(shù)

OLAP計(jì)算的特征是聚集計(jì)算，即將連接后的記錄按維層次分組后計(jì)算出聚集值.聚集計(jì)算是一個(gè)數(shù)據(jù)收斂的過程，在人機(jī)交互的ad－h(huán)oc OLAP應(yīng)用中，用戶通常以低勢(shì)集的多維數(shù)據(jù)集為目標(biāo)，因此，當(dāng)聚集計(jì)算可以在集群節(jié)點(diǎn)間并行處理時(shí)，每個(gè)節(jié)點(diǎn)只產(chǎn)生非常小的聚集結(jié)果集，網(wǎng)絡(luò)傳輸代價(jià)能夠被極大地降低.

對(duì)于滿足結(jié)合律的可分布式聚集函數(shù)（SUM、COUNT、MAX、MIN、FIRST、LAST等），以SUM為例，即若A＝A1∪A2∪…An并且φ＝A1∩A2∩…An則有SUM （A）＝SUM（SUM （A1），SUM （A2），…，SUM （An））.將數(shù)據(jù)集劃分為多個(gè)不相交的數(shù)據(jù)子集后，使用聚集函數(shù)的OLAP查詢可以直接下推到數(shù)據(jù)子集上獨(dú)立執(zhí)行，最后將查詢結(jié)果子集合并.對(duì)于代數(shù)可分布聚集函數(shù)，如AVERAGE可以通過SUM和COUNT聚集結(jié)果計(jì)算得出，方差函數(shù)可通過如下公式轉(zhuǎn)換為SUM（A）、SUM（A2）、COUNT（A）三個(gè)聚集函數(shù)的代數(shù)表達(dá)式計(jì)算得出.

對(duì)于不可分布式聚集函數(shù)，如MEDIAN、PERCENTILE等則需要將集群中的數(shù)據(jù)傳輸?shù)揭粋€(gè)節(jié)點(diǎn)上集中處理，增加了網(wǎng)絡(luò)傳輸代價(jià).我們?cè)谖墨I(xiàn)［13］中提出了一種迭代式中值計(jì)算技術(shù)，如圖9所示.通過在集群節(jié)點(diǎn)本地排序數(shù)據(jù)集上求出各自的中值，然后通過網(wǎng)絡(luò)匯集各節(jié)點(diǎn)邊界值并根據(jù)最小邊界值在各節(jié)點(diǎn)上對(duì)排序數(shù)據(jù)集進(jìn)行剪枝，逐漸縮減中值候選窗口，最后只對(duì)較小候選窗口中的數(shù)據(jù)進(jìn)行集中式的中值處理以得到全局中值結(jié)果.實(shí)驗(yàn)結(jié)果表明，由于事實(shí)表數(shù)據(jù)的分布具有數(shù)據(jù)隨機(jī)性，而且group－by屬性隨著查詢而動(dòng)態(tài)變化，因此排序記錄子集一般分布較為均勻，迭代剪裁能夠有效縮減并行中值計(jì)算的網(wǎng)絡(luò)傳輸代價(jià).

2.2.3 面向Operational BI需求的ScaMMDBⅡ模型

現(xiàn)代大型企業(yè)每天產(chǎn)生大量的事務(wù)數(shù)據(jù)，用戶的決策支持越來越多地依賴于對(duì)及時(shí)性數(shù)據(jù)的分析結(jié)果，需要數(shù)據(jù)倉庫支持更短的更新周期.我們提出在事務(wù)型系統(tǒng)和分析型數(shù)據(jù)倉庫系統(tǒng)之間建立一個(gè)中等規(guī)模的分析型數(shù)據(jù)緩存層，提供高性能的ad－h(huán)oc查詢處理能力.為保證查詢處理的性能，采用MMDB查詢處理引擎的ScaMMDBⅡ（ParaCube）來實(shí)現(xiàn)高性能OLAP查詢處理.如圖10所示，全部的數(shù)據(jù)被分為三個(gè)層次：Fresh data表示前端OLTP數(shù)據(jù)，數(shù)據(jù)量較小，支持?jǐn)?shù)據(jù)的更新操作，采用OLTP引擎，OLAP查詢處理性能的保證是較小的數(shù)據(jù)集；Buffer data是OLTP和OLAP系統(tǒng)之間的緩存數(shù)據(jù)，它接受來自O(shè)LTP系統(tǒng)的較短時(shí)間間隔的更新操作，一般是批量的追加和數(shù)據(jù)遷移，緩存數(shù)據(jù)量的大小取決于數(shù)據(jù)倉庫的更新策略和物化cube的更新代價(jià).一般來說，從OLTP系統(tǒng)向緩存數(shù)據(jù)層的更新以天為單位，從緩存數(shù)據(jù)層向數(shù)據(jù)倉庫的更新以月或年為單位.在數(shù)據(jù)分析時(shí)，最近的數(shù)據(jù)往往具有更高的分析權(quán)重，因此OLTP系統(tǒng)和數(shù)據(jù)緩存層的查詢負(fù)載相對(duì)較高，數(shù)據(jù)緩存層的數(shù)據(jù)量動(dòng)態(tài)變化，因此需要ScaMMDBⅡ的可擴(kuò)展性提供支持.對(duì)于可分布聚集計(jì)算函數(shù)來說，將OLAP查詢?nèi)蝿?wù)下推到OLTP系統(tǒng)、Buffer data（ParaCube）和數(shù)據(jù)倉庫層，各個(gè)層次獨(dú)立完成在其數(shù)據(jù)集上的OLAP查詢處理任務(wù)，生成查詢處理結(jié)果子集并由系統(tǒng)進(jìn)行查詢結(jié)果子集歸并，產(chǎn)生最終的查詢結(jié)果.通過可分布聚集計(jì)算OLAP的并行處理，能夠構(gòu)建一個(gè)異構(gòu)的OLAP系統(tǒng)，并且將OLTP系統(tǒng)與OLAP系統(tǒng)從邏輯上組織為統(tǒng)一的系統(tǒng)，提高分析數(shù)據(jù)的及時(shí)性，增加分析結(jié)果的操作性，提高系統(tǒng)分析任務(wù)的有效性.

圖9 迭代式中值計(jì)算Fig.9 Iterative Median computing

圖10 Operational BI三層模型Fig.10 3－level operational BI model

相對(duì)于Vertica的WOS和ROS機(jī)制以及SAP的OLTP＆OLAP技術(shù)，我們采用的是一種異構(gòu)數(shù)據(jù)庫平臺(tái)上的邏輯集成技術(shù)，降低系統(tǒng)的復(fù)雜性.我們同時(shí)提出異步更新通道模型以實(shí)現(xiàn)將OLTP系統(tǒng)中的數(shù)據(jù)在后臺(tái)以異步方式增量更新到內(nèi)存OLAP數(shù)據(jù)庫集群，減少集群節(jié)點(diǎn)間的數(shù)據(jù)更新代價(jià).

2.3 ScaMMDBⅡ的應(yīng)用場(chǎng)景

ScaMMDB采用基于列的數(shù)據(jù)分布策略，面向只讀型的數(shù)據(jù)倉庫應(yīng)用.ScaMMDBⅡ采用的維表全復(fù)制機(jī)制和事實(shí)表異步更新通道機(jī)制支持insert－only更新類型的數(shù)據(jù)倉庫應(yīng)用，維表的存儲(chǔ)和更新的代價(jià)較大.

基于水平分片的并行OLAP機(jī)制對(duì)于基礎(chǔ)的SPJGA（S：選擇，P：投影，J：連接，G：分組，A：聚集）操作只需要簡單的查詢重寫和查詢結(jié)果歸并處理，非常適合SSB數(shù)據(jù)集上的OLAP應(yīng)用.對(duì)于帶有復(fù)雜子查詢的TPC－H查詢則需要將查詢轉(zhuǎn)換為SPJGA查詢樹才能實(shí)現(xiàn)并行處理，系統(tǒng)實(shí)現(xiàn)復(fù)雜度較高.

3 基于向量技術(shù)的內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng)MiNT－OLAPCluster

ScaMMDB采用與Oracle RAC的Cache Fusion技術(shù)類似的NetMemory擴(kuò)展內(nèi)存數(shù)據(jù)倉庫的內(nèi)存容量以支持大數(shù)據(jù)內(nèi)存計(jì)算.ScaMMDBⅡ采用與HadoopDB類似的集群并行計(jì)算技術(shù)構(gòu)建基于SQL的異構(gòu)內(nèi)存數(shù)據(jù)倉庫集群.系統(tǒng)實(shí)現(xiàn)技術(shù)以MonetDB為基礎(chǔ)，雖然能夠利用MonetDB優(yōu)秀的性能和豐富的API支持，但受MonetDB系統(tǒng)設(shè)計(jì)的限制，難以對(duì)內(nèi)存數(shù)據(jù)倉庫集群進(jìn)行更加深入的優(yōu)化.

當(dāng)前數(shù)據(jù)倉庫技術(shù)的發(fā)展趨勢(shì)是及時(shí)性（just－in－time）分析處理需求越來越高，甚至將前端業(yè)務(wù)系統(tǒng)與后端分析系統(tǒng)相結(jié)合，將OLTP與OLAP系統(tǒng)融合在一起，代表性技術(shù)包括SAP HANA、ScyPer［14］等系統(tǒng).因此，在內(nèi)存數(shù)據(jù)倉庫集群的設(shè)計(jì)中需要將數(shù)據(jù)更新代價(jià)作為一個(gè)重要的設(shè)計(jì)因素.MiNT－OLAPCluster系統(tǒng)根據(jù)數(shù)據(jù)倉庫模型和負(fù)載特征采用反星形（reverse－star schema）模式存儲(chǔ)策略，即將較小的維表集中存儲(chǔ)，消除冗余副本的存儲(chǔ)代價(jià)和網(wǎng)絡(luò)更新代價(jià)，事實(shí)表則采用水平分片存儲(chǔ)于集群節(jié)點(diǎn)，形成以維表為中心，事實(shí)表分片為分支的星形分布式存儲(chǔ).在OLAP查詢處理中我們采用基于位圖或向量的星形過濾技術(shù)，在維表上生成較小的向量數(shù)據(jù)結(jié)構(gòu)并廣播到各工作節(jié)點(diǎn)，在事實(shí)表分片上完成本地化SPJGA計(jì)算，并將各工作節(jié)點(diǎn)的OLAP結(jié)果集在中心節(jié)點(diǎn)進(jìn)行全局聚集歸并，生成最終的查詢處理結(jié)果.

3.1 MiNT－OLAPCluster系統(tǒng)結(jié)構(gòu)和關(guān)鍵技術(shù)

與ScaMMDB、ScaMMDBⅡ采用 MonetDB查詢處理引擎不同，MiNT－OLAPCluster系統(tǒng)的OLAP查詢處理以我們自己設(shè)計(jì)的DDTA－JOIN算法為核心，通過向量計(jì)算模型簡化OLAP查詢處理過程，將OLAP查詢處理中維表與事實(shí)表之間的數(shù)據(jù)傳輸最小化為位圖或向量，從而最小化集群計(jì)算時(shí)的網(wǎng)絡(luò)傳輸代價(jià).

圖11顯示了DDTA－JOIN（Directly Dimensional Tuple Accessing，DDTA）算法對(duì)于典型SPJGA模式的OLAP查詢處理過程.首先SQL命令中維表上的過濾操作按維表進(jìn)行劃分，在維表上過濾后生成與維表等長的過濾位圖；通過事實(shí)表外鍵與維表主鍵之間的地址映射（address mapping）在事實(shí)表掃描時(shí)將維表外鍵映射到維表過濾位圖進(jìn)行過濾操作，滿足星形過濾（star－filtering）的記錄通過外鍵映射到維表分組屬性列中抽取分組屬性，與事實(shí)表度量屬性組合為輸出記錄進(jìn)行哈希分組聚集計(jì)算.

Oracle Exadata X3采用的SmartScan技術(shù)通過where謂詞篩選和JOIN聯(lián)接篩選在存儲(chǔ)服務(wù)器節(jié)點(diǎn)上過濾掉大部分不符合查詢條件的記錄，只將少量記錄返回給數(shù)據(jù)庫服務(wù)器完成查詢處理.類似的Bloom filter過濾技術(shù)也大量被數(shù)據(jù)庫系統(tǒng)所采用，通過增加額外的連接過濾處理消減連接操作的記錄數(shù)量，從而降低連接計(jì)算代價(jià).數(shù)據(jù)倉庫的星形模型中維表較小且增長緩慢，以SSB數(shù)據(jù)集為例，即使SF＝1 000時(shí)，4個(gè)維表過濾位圖總大小為4.08 MB，過濾位圖的存儲(chǔ)和網(wǎng)絡(luò)廣播代價(jià)極小.對(duì)于低選擇率的維表過濾操作，位圖還可以進(jìn)一步通過壓縮技術(shù)減少位圖存儲(chǔ)和網(wǎng)絡(luò)廣播代價(jià).

圖11 DDTA－JOIN 算法示例［15］Fig.11 Example of DDTA－JOIN algorithm［15］

當(dāng)OLAP查詢的選擇率較高時(shí)（如SSB中選擇率最高為3.4%），SmartScan技術(shù)仍然需要傳輸大量的數(shù)據(jù)到數(shù)據(jù)庫節(jié)點(diǎn)進(jìn)行查詢處理，而這些數(shù)據(jù)本地分組聚集后的結(jié)果集非常小，因此在OLAP集群計(jì)算時(shí)，將分組聚集計(jì)算下推到存儲(chǔ)節(jié)點(diǎn)能夠極大地提高集群并行計(jì)算性能.如圖12所示，我們進(jìn)一步將SQL中維表上的謂詞和分組操作整合，即根據(jù)維表謂詞條件投影出維表分組屬性組（可以是單一分組屬性，也可以是維表上多個(gè)分組屬性的組合值）并對(duì)其進(jìn)行編碼，然后生成基于分組屬性編碼的維表過濾分組向量（predicate vector），雖然相對(duì)于維表過濾位圖，維表過濾分組向量增加了向量寬度，但由于能夠通過維表過濾分組向量在事實(shí)表分片節(jié)點(diǎn)完成完整的SPJGA操作，只需要返回非常小的分組聚集結(jié)果集，能夠進(jìn)一步降低集群OLAP并行處理時(shí)的網(wǎng)絡(luò)傳輸代價(jià).

圖12 謂詞向量Fig.12 Predicate vector

基于DDTA－JOIN算法的MiNT－OLAPCluster系統(tǒng)結(jié)構(gòu)如圖13所示，整個(gè)內(nèi)存數(shù)據(jù)倉庫集群由一個(gè)中心節(jié)點(diǎn)和若干個(gè)處理節(jié)點(diǎn)組成，維表集存儲(chǔ)于中心節(jié)點(diǎn)，支持維表上的實(shí)時(shí)更新操作，事實(shí)表水平分片均衡分布于各工作節(jié)點(diǎn)以保證負(fù)載均衡，事實(shí)表是歷史數(shù)據(jù)，其特征決定了主要支持insert－only類型的更新操作.在星形模型數(shù)據(jù)倉庫中，事實(shí)表分片以數(shù)據(jù)量為主要考慮因素，簡化數(shù)據(jù)分布模型.

圖13 MiNT－OLAPCluster系統(tǒng)結(jié)構(gòu)［16］Fig.13 Architecture of MiNT－OLAPCluster［16］

MiNT－OLAPCluster的集群OLAP處理分為三種不同的方式.

（1）star－filtering only.中心節(jié)點(diǎn)僅將維表過濾位圖廣播到工作節(jié)點(diǎn)，工作節(jié)點(diǎn)完成事實(shí)表謂詞過濾和維表連接過濾后將篩選的事實(shí)表記錄傳輸給中心節(jié)點(diǎn)完成OLAP查詢處理.此種處理方式類似于SmartScan技術(shù)，但采用維表位圖過濾能夠準(zhǔn)確地過濾出所有滿足條件的記錄，不存在bloom filter過濾的誤判斷問題.當(dāng)OLAP查詢的選擇率很低且查詢處理任務(wù)難以并行處理（如不可分布的聚集計(jì)算或復(fù)雜子查詢處理）時(shí)，各工作節(jié)點(diǎn)提供分布式的記錄篩選功能，中心節(jié)點(diǎn)負(fù)責(zé)集中式的復(fù)雜查詢處理任務(wù).

（2）位圖廣播和分組屬性緩存.當(dāng)維表上的分組屬性更新率較低時(shí)，我們可以將查詢中常用的維表分組屬性列緩存于工作節(jié)點(diǎn)內(nèi)存，OLAP查詢處理時(shí)只廣播維表過濾位圖，在工作節(jié)點(diǎn)與維表分組屬性列共同完成本地化的分組聚集計(jì)算.當(dāng)中心節(jié)點(diǎn)的維表分組屬性列更新時(shí)，工作節(jié)點(diǎn)上緩存的分組屬性列需要重新加載或更新.

（3）維表過濾分組向量廣播.查詢處理時(shí)在中心節(jié)點(diǎn)實(shí)時(shí)生成維表過濾分組向量，并廣播到各工作節(jié)點(diǎn)完成分布式的分組聚集計(jì)算.維表過濾分組向量廣播的網(wǎng)絡(luò)傳輸代價(jià)有所提高，但由于維表行數(shù)較少，其網(wǎng)絡(luò)傳輸代價(jià)有限，而且這種機(jī)制能夠支持維表上的實(shí)時(shí)更新.

DDTA－JOIN算法將維表上的查詢處理與事實(shí)表上的計(jì)算劃分為獨(dú)立的兩個(gè)階段，OLAP查詢?cè)谥行墓?jié)點(diǎn)上的處理過程和工作節(jié)點(diǎn)上的分組聚集計(jì)算可以流水并行，即當(dāng)查詢Q1在中心節(jié)點(diǎn)生成維表過濾分組向量并廣播給工作節(jié)點(diǎn)進(jìn)行集群并行處理時(shí)，中心節(jié)點(diǎn)可以繼續(xù)執(zhí)行查詢Q2在維表上的處理任務(wù).由于維表較小且生成維表過濾分組向量的操作比較簡單，我們可以在工作節(jié)點(diǎn)進(jìn)行OLAP查詢處理時(shí)創(chuàng)建查詢組Q的維表過濾分組向量組，在下一個(gè)工作節(jié)點(diǎn)OLAP查詢處理時(shí)執(zhí)行查詢組Q上的并發(fā)查詢處理任務(wù)，進(jìn)一步提高查詢吞吐性能.

進(jìn)一步地，我們將內(nèi)存數(shù)據(jù)倉庫集群技術(shù)擴(kuò)展到Hadoop平臺(tái)，如圖14所示.我們?cè)贖adoop多復(fù)本機(jī)制的基礎(chǔ)上將一個(gè)副本升級(jí)為內(nèi)存列存儲(chǔ)副本，支持內(nèi)存副本上的集群并行內(nèi)存OLAP查詢處理，其余復(fù)本作為容錯(cuò)副本，將內(nèi)存OLAP集群技術(shù)與Hadoop集群技術(shù)相結(jié)合，發(fā)揮內(nèi)存OLAP集群的高性能和Hadoop集群的高可擴(kuò)展性和高可靠性.

圖14 基于Hadoop平臺(tái)的內(nèi)存OLAP集群［17］Fig.14 In－memory OLAP cluster on Hadoop［17］

3.2 MiNT－OLAPCluster性能驗(yàn)證

我們?cè)诤烁呋卮髮ｍ?xiàng)“大型通用數(shù)據(jù)庫管理系統(tǒng)與套件研發(fā)及產(chǎn)業(yè)化”的子課題“國產(chǎn)數(shù)據(jù)庫高性能高安全關(guān)鍵技術(shù)研究（2010ZX01042－001－002－002）”中采用 MiNT－OLAPCluster技術(shù)實(shí)現(xiàn)內(nèi)存數(shù)據(jù)倉庫集群系統(tǒng).我們?cè)诩簻y(cè)試中使用14個(gè)節(jié)點(diǎn)（每節(jié)點(diǎn)2個(gè)6核處理器，48GB內(nèi)存，SSB測(cè)試集在SF＝100時(shí)內(nèi)存占用45.8GB），一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)，用于查詢解析、任務(wù)調(diào)度和查詢結(jié)果歸并，13個(gè)工作節(jié)點(diǎn)用于并行查詢處理.整個(gè)集群測(cè)試數(shù)據(jù)集大小SF＝100×13，事實(shí)表分片均勻分布到13個(gè)工作節(jié)點(diǎn)上.由于我們沒有SF＝1 300的內(nèi)存做集中式的內(nèi)存OLAP性能基準(zhǔn)測(cè)試，因此采用通過單個(gè)數(shù)據(jù)分片查詢處理時(shí)間×節(jié)點(diǎn)數(shù)來近似獲得（由DDTA－JOIN算法的線性特征決定），集群并行查詢處理時(shí)間為系統(tǒng)實(shí)際執(zhí)行測(cè)試時(shí)間，集群的并行處理加速比SR≈13×單分片執(zhí)行時(shí)間／集群并行執(zhí)行時(shí)間，實(shí)驗(yàn)中平均并行加速比為12.64.見圖15所示.

圖15 內(nèi)存數(shù)據(jù)倉庫系統(tǒng)集群并行性能Fig.15 In－memory Data Warehouse cluster parallel performance

3.3 MiNT－OLAPCluster的應(yīng)用場(chǎng)景

我們當(dāng)前的研究工作以圖6所示的星形模型為目標(biāo)，以基礎(chǔ)的SPJGA操作符的集群并行處理技術(shù)為對(duì)象，提供一個(gè)內(nèi)存數(shù)據(jù)倉庫的基礎(chǔ)平臺(tái)，在此基礎(chǔ)上可以構(gòu)建以SPJGA操作符樹為基礎(chǔ)的更加復(fù)雜的查詢處理任務(wù).也就是說，我們的實(shí)現(xiàn)技術(shù)能夠完全解決SSB測(cè)試基準(zhǔn)類型的OLAP負(fù)載，也可以作為內(nèi)存數(shù)據(jù)倉庫集群的SPJGA操作API提供給更加復(fù)雜的OLAP查詢處理任務(wù)調(diào)用.

多事實(shí)表的TPC－H數(shù)據(jù)集也可以采用 MiNT－OLAPCluster的實(shí)現(xiàn)技術(shù).事實(shí)表lineitem與orders表存在主外鍵參照完整性引用約束關(guān)系，而且lineitem表的orderkey與orders表的orderkey存在偏序關(guān)系，我們可以采用orders（orderkey）→lineitem（orderkey）的分片策略將lineitem表和orders表按orderkey劃分為不相交的數(shù)據(jù)分片存儲(chǔ)于不同的集群節(jié)點(diǎn)上.Partsupp事實(shí)表在集群上獨(dú)立進(jìn)行水平分片，TPC－H查詢中Q2、Q11、Q16、Q20查詢中，part表、supplier表和partsupp事實(shí)表之間的星形OLAP操作遵循MiNTOLAPCluster實(shí)現(xiàn)技術(shù).TPC－H查詢中包含lineitem？orders？partsupp操作的查詢Q9中，partsupp表上的查詢子集在經(jīng)過集群并行生成后需要廣播到各工作節(jié)點(diǎn)參與連接操作.因此，TPC－H數(shù)據(jù)集在事實(shí)表協(xié)同分片策略下也可以使用MiNT－OLAPCluster實(shí)現(xiàn)技術(shù)，但相對(duì)于SSB標(biāo)準(zhǔn)的SPJGA查詢，TPC－H需要將更為復(fù)雜的查詢轉(zhuǎn)換為SPJGA查詢樹并對(duì)MiNT－OLAPCluster的集群SPJGA操作API進(jìn)行調(diào)用.表1對(duì)三種內(nèi)存數(shù)據(jù)倉庫集群技術(shù)進(jìn)行了綜合對(duì)比.

表1 內(nèi)存數(shù)據(jù)倉庫集群技術(shù)對(duì)比Tab.1 Comparison for different in－memory data warehouse cluster technologies

4 結(jié) 論

本文概括地描述了我們?cè)趦?nèi)存數(shù)據(jù)倉庫集群研究上的技術(shù)路線，不同原型系統(tǒng)所面對(duì)的問題及解決方案.在三個(gè)原型系統(tǒng)的研究過程中，我們最大的感受是需要建立自己的內(nèi)存OLAP查詢執(zhí)行框架，并使之平臺(tái)化，掌握自己的關(guān)鍵技術(shù)，提高對(duì)系統(tǒng)實(shí)現(xiàn)的掌控能力.

本文給出了當(dāng)前大內(nèi)存發(fā)展趨勢(shì)下內(nèi)存數(shù)據(jù)倉庫集群實(shí)現(xiàn)技術(shù)的框架結(jié)構(gòu).與具有高可擴(kuò)展性的key／value存儲(chǔ)類似，當(dāng)采用極大事實(shí)表、多個(gè)極小維表的星形或雪花形模型時(shí)，數(shù)據(jù)倉庫具有良好的可擴(kuò)展性.在事實(shí)表－維表地址映射技術(shù)和向量計(jì)算技術(shù)的支持下，多維／高維OLAP查詢處理具有較高的效率，通過對(duì)OLAP查詢命令在維表和事實(shí)表上的分而治之處理技術(shù)，數(shù)據(jù)倉庫能夠較好地支持OLTP任務(wù)，實(shí)現(xiàn)實(shí)時(shí)分析處理.

隨著CPU和內(nèi)存技術(shù)的發(fā)展，大數(shù)據(jù)內(nèi)存實(shí)時(shí)分析相對(duì)于傳統(tǒng)的數(shù)據(jù)倉庫技術(shù)具有更高的性能和性價(jià)比，隨著實(shí)時(shí)分析性能的提升，OLAP的應(yīng)用將逐漸從少數(shù)決策管理用戶層擴(kuò)展到大量業(yè)務(wù)處理的普通用戶層，因此實(shí)時(shí)OLAP查詢響應(yīng)性能和高并發(fā)查詢吞吐性能將成為未來內(nèi)存數(shù)據(jù)倉庫重要的性能指標(biāo)，需要結(jié)合多核／眾核并行處理技術(shù)及新的存儲(chǔ)硬件技術(shù)方面的最新成果不斷提高大數(shù)據(jù)實(shí)時(shí)OLAP分析處理性能.數(shù)據(jù)倉庫也將逐漸從只讀型分析處理向OLTP＆OLAP相結(jié)合的需求發(fā)展，需要提高OLTP負(fù)載與OLAP負(fù)載并發(fā)時(shí)的綜合性能.大數(shù)據(jù)處理對(duì)集群技術(shù)的需求需要重新考慮和設(shè)計(jì)面向集群處理特征的數(shù)據(jù)倉庫模式設(shè)計(jì)，高密度事實(shí)表（事實(shí)表數(shù)據(jù)量占比高）和高維模式設(shè)計(jì)將簡化集群并行計(jì)算模型并且提高數(shù)據(jù)倉庫的擴(kuò)展性能.基于SPJGA操作符的OLAP查詢樹優(yōu)化技術(shù)能夠?qū)⒏呤諗啃缘木奂?jì)算下推到數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，相對(duì)于傳統(tǒng)的基于關(guān)系操作符的查詢樹優(yōu)化技術(shù)能夠更好地適應(yīng)數(shù)據(jù)倉庫集群計(jì)算.

［1］ Gartner Identifies the Top 10 Strategic Technology Trends for 2013［EB／OL］.（2012－10－23）［2013－04－12］.http：／／www.gartner.com／newsroom／id／2209615.

［2］ BONCZ P A，KERSTEN M L，MANEGOLD S.Breaking the memory wall in MonetDB.Commun［J］.ACM51，2008（12）：77－85.

［3］ ZUKOWSKI M，BONCA P A.Vectorwise：Beyond Column Stores［J］.IEEE Data Eng Bull，2012，35（1）：21－27.

［4］ SIKKA V，F(xiàn)?RBER F，LEHNER W，et al.Efficient transaction processing in SAP HANA database：the end of a column store myth［C］／／SIGMOD Conference.2012：731－742.

［5］ IBM Informix Warehouse Accelerator－Performance is everything http：／／public.dhe.ibm.com／common／ssi／ecm／en／imw14587usen／IMW14587USEN.PDF.

［6］ Overview of ExaData.http：／／www.oracle.com／us／products／database／exadata／overview／index.html.

［7］ DIACONU C，F(xiàn)REEDMAN C，ISMERT E，et al.Hekaton：SQL server＇s memory－optimized OLTP engine［C］／／SIGMOD，2013：1243－1254.

［8］ ELLIOTT T.Why In－Memory Computing Is Cheaper And Changes Everything［EB／OL］.（2013－04－17）［2014－06－18］.http：／／timoelliott.com／blog／2013／04／why－in－memory－computing－is－cheaper－and－changes－everything.html.

［9］ 張延松.大規(guī)?？蓴U(kuò)展數(shù)據(jù)分析技術(shù)研究［D］.北京：中國人民大學(xué)信息學(xué)院，2010.

［10］ 黃云奎.可擴(kuò)展內(nèi)存數(shù)據(jù)庫ScaMMDB數(shù)據(jù)分布策略研究［D］.北京：中國人民大學(xué)信息學(xué)院，2009.

［11］ RABL T，POESS M，JACOBSEN H A，et al.Variations of the star schema benchmark to test the effects of data skew on query performance［C］／／ICPE，2013：361－372.

［12］ HANA S.Performance Efficient Speed and Scale－Out for Real－Time Business Intelligence［EB／OL］.（2012－4－28）［2013－04－12］http：／／www.saphana.com／docs／DOC－1647.

［13］ ZHANG Y，WANG S，HUANG W.ParaCube：a scalable OLAP model based on distributed aggregate computing with Sibling Cubes［C］／／APWEB，2010：323－329.

［14］ MüHLBAUER T，R?DIGER W，REISER A，et al.ScyPer：A Hybrid OLTP＆OLAP Distributed Main Memory Database System for Scalable Real－Time Analytics［C］／／BTW，Magdeburg，Germany，2013.

［15］ 張延松，焦敏，王占偉，等.海量數(shù)據(jù)分析的 One－size－fits－all OLAP技術(shù)［J］.計(jì)算機(jī)學(xué)報(bào)，2011（10）：1936－1947.

［16］ JIAO M，ZHANG Y S，WANG Z W，et al.MiNT－OLAP cluster：minimizing network transmission cost in OLAP cluster for main memory analytical database［J］.Frontiers of Computer Science，2012，6（6）：668－676.

［l7］ 張延松，王珊.面向數(shù)據(jù)庫與 Hadoop混合平臺(tái)的OLAP查詢處理方法：中國，201210114112.0.2［P］.2013－11－20.

［l8］ Costea A，Ionescu A.Query Optimization and Execution in Vectorwise MPP［D］.Amsterdam：Vrije Universiteit Amsterdam（＠VectorWise），2012.