基于數(shù)據(jù)分組方法的數(shù)據(jù)倉(cāng)庫(kù)并行預(yù)計(jì)算和查詢（三）

基于數(shù)據(jù)分組方法的數(shù)據(jù)倉(cāng)庫(kù)并行預(yù)計(jì)算和查詢（三）

第六章并行化算法的實(shí)現(xiàn)6.1串行預(yù)計(jì)算程序結(jié)構(gòu)

在串行預(yù)計(jì)算程序中，一共有Cubing、DFHandle、QuotientCube和TupleHandle4個(gè)類，其中DFHandle和TupleHandle兩個(gè)類是輔助功能類。它們的類圖如圖6.1所示。DFHandle的主要功能是打開關(guān)閉數(shù)據(jù)文件，將數(shù)據(jù)文件中的元組一條一條地讀進(jìn)來(lái)，然后將該條元組交給TupleHandle處理，TupleHandle將元組的各維數(shù)據(jù)分割開來(lái)，每次處理一維，并將該維數(shù)據(jù)存在程序指定的一個(gè)內(nèi)存區(qū)域中。關(guān)于Cubing類和QuotientCube類的詳細(xì)介紹，將在以下的章節(jié)中給出。圖6.1

DFHandle類和TupleHandle類6.1.1Cubing類

Cubing類的類圖如圖6.2所示，其中l(wèi)oadData()的作用是使用DFHandle類，打開指定的數(shù)據(jù)文件，將元組讀出之后，使用TupleHandle來(lái)將各個(gè)維度和度量值的數(shù)據(jù)拆分開來(lái)，然后對(duì)所有的維度做映射操作，寫入映射文件，同時(shí)將映射后的維度數(shù)據(jù)存在data這個(gè)二維數(shù)組里，度量值存在msrdata中，直到把所有數(shù)據(jù)文件都讀入data和msrdata中。在讀數(shù)據(jù)之前，loadData還會(huì)先統(tǒng)計(jì)基表中有多少條元組，元組有多少維和多少個(gè)度量值，某度量值上的聚集操作分別是哪種，這些數(shù)據(jù)分別存在tuplesNum，dimsNum，msrsNum和aggFunOrder中。avgFun()、maxFun()、minFun()、sumFun()和countFun()里面分別是平均、最大值、最小值、和、計(jì)數(shù)等聚集操作的實(shí)現(xiàn)。圖6.2

Cubing類Cubing類的工作主要是完成預(yù)計(jì)算真正開始之前的準(zhǔn)備工作，把所有數(shù)據(jù)都讀入內(nèi)存之后，QuotientCube類便可以使用這些數(shù)據(jù)來(lái)進(jìn)行預(yù)計(jì)算工作。Cubing類的preCompute()函數(shù)是一個(gè)虛函數(shù)，它的具體實(shí)現(xiàn)在QuotientCube中。QuotientCube類是Cubing類的一個(gè)子類。6.1.2QuotientCube類

QuotientCube類public繼承于Cubing。它的類圖如圖6.3所示。通過(guò)調(diào)用preCompute()開始預(yù)計(jì)算工作。圖6.3

QuotientCube類程序首先會(huì)創(chuàng)建dimsNum+1個(gè)aggDimDataX文件，用來(lái)存放不同層次的上界，同時(shí)也創(chuàng)建同樣多個(gè)的aggMsrDataX文件，用來(lái)存放相對(duì)應(yīng)的度量值。data[0]中存放Cubing從數(shù)據(jù)文件讀出的data內(nèi)容，同樣msrData[0]中存放相應(yīng)的度量值，data[1]和msrdata[1]中將存放的是將data[0]、msrdata[0]里數(shù)據(jù)排序后的結(jié)果，用來(lái)排序的算法在Partition()中實(shí)現(xiàn)。preCompute()接下來(lái)便會(huì)調(diào)用DFS()開始計(jì)算上界并將上界與其所對(duì)應(yīng)的度量值寫入相應(yīng)層次的文件中。DFS()的具體算法詳見本文4.2節(jié)。預(yù)計(jì)算程序的數(shù)據(jù)流圖如圖6.4所示。圖6.4

串行預(yù)計(jì)算程序中的數(shù)據(jù)流6.2預(yù)計(jì)算并行化

并行預(yù)計(jì)算程序中，在串行程序的基礎(chǔ)上增加了兩個(gè)類：分別是DispatchManager類和DispatchWorker類。顧名思義，DispatchManager類中的方法是為主從模式中的主進(jìn)程所調(diào)用，DispatchWorker類中的方法是在從進(jìn)程中調(diào)用。根據(jù)本文5.1節(jié)中的描述，DispatchManger類主要的工作是完成數(shù)據(jù)讀入、映射和數(shù)據(jù)分發(fā)工作。DispatchWorker的工作是接收主進(jìn)程發(fā)送過(guò)來(lái)的數(shù)據(jù)。6.2.1DispatchManager類和DispatchWorker類

DispatchManager類和DispatchWorker類的類圖如圖6.5所示。數(shù)據(jù)的讀入工作將由Cubing類轉(zhuǎn)移到DispatchManager類中，但由于從進(jìn)程無(wú)法接觸到文件信息，因此，主進(jìn)程必須將與數(shù)據(jù)文件相關(guān)的數(shù)據(jù)預(yù)先得出并發(fā)送給每個(gè)從進(jìn)程。DispatchManager在初始化時(shí)便會(huì)調(diào)用getDataFileNum()和getConfig()。getDataFileNum函數(shù)使用DFHandle和TupleHandle來(lái)完成工作。首先打開數(shù)據(jù)文件，將第一行讀出。數(shù)據(jù)文件的第一行是用來(lái)寫明基表有多少個(gè)維度和度量值，每個(gè)維度和度量值的名稱分別是什么。getDataFileNum里會(huì)根據(jù)里面的信息分辨出哪些是維度數(shù)據(jù)，哪些是度量值，分別有多少個(gè)，度量值以何種方式進(jìn)行聚集操作等，然后把這些數(shù)據(jù)保存下來(lái)。最后是統(tǒng)計(jì)整個(gè)數(shù)據(jù)文件有多少條元組。這些操作基本和Cubing::loadData中前面部分的操作相同。圖6.5

DispatchManager和DispatchWorker類圖getConfig函數(shù)的作用是將保存著各個(gè)進(jìn)程數(shù)據(jù)分配比例的配置文件內(nèi)容讀出，并根據(jù)getDataFileNum中得到的元組條數(shù)，計(jì)算出每個(gè)進(jìn)程應(yīng)當(dāng)接收的元組條數(shù)。計(jì)算完之后，將這些信息保存在pConfig中。接下來(lái)，DispatchManager便會(huì)將pConfig里的數(shù)據(jù)連同度量值操作方式和文件夾名稱發(fā)送到每個(gè)相應(yīng)的進(jìn)程中，如圖6.6所示。同時(shí)，在從進(jìn)程中運(yùn)行的DispatchWorker也調(diào)用了recvConfig()。主從進(jìn)程間通過(guò)MPI的點(diǎn)對(duì)點(diǎn)通信，完成配置數(shù)據(jù)的發(fā)送和接收。DispatchWorker接收完配置數(shù)據(jù)之后，將配置數(shù)據(jù)存如pConfig里。在完成配置數(shù)據(jù)的交互之后，DispatchWorker將會(huì)利用收到的數(shù)據(jù)，如元組條數(shù)、維度數(shù)和度量值數(shù)來(lái)決定該分配多大的內(nèi)存空間以存下將要收到的數(shù)據(jù)，并開始等待接收數(shù)據(jù)。而DispatchManager則會(huì)調(diào)用loadData()來(lái)將數(shù)據(jù)文件載入內(nèi)存。DispatchManager在loadData()時(shí)是將數(shù)據(jù)存入兩個(gè)長(zhǎng)度分別為iDimNum*iTupleNum和iMsrNum*iTupleNum的一維數(shù)組中，它們分別是pDimData和pMsrData。與串行預(yù)計(jì)算程序中的Cubing作用類似，DispatchManager會(huì)在載入數(shù)據(jù)的同時(shí)完成映射的工作。但當(dāng)DispatchManager準(zhǔn)備好要發(fā)送到其中一個(gè)從進(jìn)程的數(shù)據(jù)之后，它便會(huì)調(diào)用sendData()，指明將要發(fā)送的進(jìn)程號(hào)，將數(shù)據(jù)發(fā)送出去。如圖6.7所示。圖6.6

發(fā)送和接收配置數(shù)據(jù)示意圖圖6.7

發(fā)送和接收數(shù)據(jù)示意圖在每個(gè)從進(jìn)程都接收完數(shù)據(jù)和主進(jìn)程完成loadData之后，每個(gè)進(jìn)程都會(huì)有裝著維度數(shù)據(jù)和度量值的兩個(gè)一維數(shù)組。在并行程序的Cubing中，由于不再需要與文件打交道，所以將Cubing::loadData()重載，將它的輸入?yún)?shù)由數(shù)據(jù)文件名改為文件夾名稱、pDimData、pMsrData和pAggFun。在這個(gè)函數(shù)中，Cubing將會(huì)把pDimData和pMsrData這兩個(gè)一維數(shù)組的數(shù)據(jù)讀出，存成二維數(shù)組。這樣，數(shù)據(jù)發(fā)送過(guò)程已經(jīng)完結(jié)，預(yù)計(jì)算開始之前的數(shù)據(jù)準(zhǔn)備工作已經(jīng)完成，接下來(lái)便是各個(gè)進(jìn)程調(diào)用QuotientCube里的preCompute()函數(shù)，開始預(yù)計(jì)算工作。接下來(lái)在每個(gè)進(jìn)程中的工作情況，和串行環(huán)境下的情況一致。6.3串行查詢程序結(jié)構(gòu)

在串行查詢程序中，同樣也有DFHandle和TupleHandle這兩個(gè)輔助類。實(shí)現(xiàn)查詢功能主要由以下三個(gè)類完成：AggStorage、CloseCubeQuery、QueryComputation。它們的類圖如圖6.8所示。圖6.8

查詢程序類AggStorage類的主要功能是面向立方體數(shù)據(jù)的操作。它封裝了讀入預(yù)計(jì)算所產(chǎn)生文件的方法，如loadMapData是將map文件讀入，用來(lái)映射查詢語(yǔ)句。loadAggData用來(lái)將某一層立方體文件內(nèi)容讀進(jìn)內(nèi)存。串行查詢程序首先會(huì)通過(guò)QueryComputation::getQueryRecord()將查詢語(yǔ)句批量地讀入，存在QueryRecords里，然后調(diào)用CloseCubeQuery::Query()。在CloseCubeQuery::Query()中，程序通過(guò)aggStorage所實(shí)例化的AggStorage對(duì)象將映射關(guān)系文件讀入，并調(diào)用MapStoI()將查詢語(yǔ)句映射為整型數(shù)組。映射后的查詢語(yǔ)句存在tqryobj中，然后將tqryobj中的內(nèi)容，一次一條地遞交給pointQuery()進(jìn)行查詢。大致的流程如圖6.9所示。圖6.9串行查詢流程pointQuery首先會(huì)確定該條查詢語(yǔ)句的層次，然后判斷該層次的數(shù)據(jù)是否已經(jīng)載入內(nèi)存，如果沒(méi)，則調(diào)用AggStorage::loadAggData()將其載到內(nèi)存中。然后開始順序掃描各條上界，使用isCovered來(lái)判斷該上界是否被查詢語(yǔ)句所覆蓋。如果掃描完一層還找不到所覆蓋的上界，則繼續(xù)掃描下一層文件。具體流程在本文4.3節(jié)。6.4并行查詢

在并行查詢程序中，增加了兩個(gè)類，分別是QueryManager類和QueryWorker類。串行程序中的QueryComputation類被取消，它的功能將在QueryManager類中實(shí)現(xiàn)，CloseCubeQuery中的MapStoI()函數(shù)也放在QueryManager類中實(shí)現(xiàn)。圖6.10中所示為QueryManager類和QueryWorker類的類圖。6.4.1QueryManager類和QueryWorker類

并行查詢程序首先會(huì)在主進(jìn)程中調(diào)用QueryManager::loadQuery()來(lái)將查詢語(yǔ)句全部存入內(nèi)存queryRecords二維數(shù)組中。接著就是調(diào)用QueryManager::mapQuery()將查詢語(yǔ)句映射成整型數(shù)組，存入QueryManager::pQuery中。與并行預(yù)計(jì)算程序類似，并行查詢程序中，主進(jìn)程也會(huì)預(yù)先將一些配置數(shù)據(jù)發(fā)送給從進(jìn)程，其中包括了查詢語(yǔ)句的條數(shù)、數(shù)據(jù)的維度和度量值數(shù)。從進(jìn)程在接收完這些數(shù)據(jù)之后，做一些初始化工作，為即將發(fā)送過(guò)來(lái)的查詢數(shù)據(jù)做準(zhǔn)備。實(shí)現(xiàn)這個(gè)功能的是QueryManager::broadcastConfig()和QueryWorker::receiveConfig()。在配置數(shù)據(jù)發(fā)送完畢之后，便是開始發(fā)送查詢數(shù)據(jù)，主進(jìn)程調(diào)用QueryManager::broadcastQuery()將查詢數(shù)據(jù)分發(fā)到各個(gè)從進(jìn)程上，從進(jìn)程接收完之后，將查詢語(yǔ)句存入QueryWorker::pQuery中。結(jié)果的指針。主進(jìn)程與從進(jìn)程分別調(diào)用CloseCubeQuery::Query(QueryManager::pQuery，QueryManager::pQueryResults[0])和CloseCubeQuery::Query(QueryWorker::pQuery，QueryWorker::pQueryResult)開始進(jìn)行查詢工作。圖6.10

QueryManager類和QueryWorker類查詢的流程如圖6.11所示，在Query()中的實(shí)現(xiàn)過(guò)程基本與串行程序過(guò)程一致。在查詢完畢之后，各個(gè)從進(jìn)程將會(huì)把存放著查詢結(jié)果的數(shù)組，