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

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

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

DFHandle類和TupleHandle類6.1.1Cubing類

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

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

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

QuotientCube類程序首先會創(chuàng)建dimsNum+1個aggDimDataX文件，用來存放不同層次的上界，同時也創(chuàng)建同樣多個的aggMsrDataX文件，用來存放相對應(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é)果，用來排序的算法在Partition()中實現(xiàn)。preCompute()接下來便會調(diào)用DFS()開始計算上界并將上界與其所對應(yīng)的度量值寫入相應(yīng)層次的文件中。DFS()的具體算法詳見本文4.2節(jié)。預計算程序的數(shù)據(jù)流圖如圖6.4所示。圖6.4

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

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

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

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

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

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

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

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

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

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

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