摘要：OLAP(On Line Analysis Processing)是數(shù)據(jù)倉(cāng)庫(kù)的典型應(yīng)用，在數(shù)據(jù)倉(cāng)庫(kù)中頻繁并發(fā)地執(zhí)行涉及較大數(shù)據(jù)量的OLAP查詢時(shí)，其查詢處理效率易于逐漸降低。緩存技術(shù)是一種有效降低OLAP查詢處理延時(shí)的方法。在現(xiàn)有的緩存數(shù)據(jù)存儲(chǔ)、淘汰策略等研究工作的基礎(chǔ)上，結(jié)合OLAP任務(wù)的負(fù)載特性、OLAP任務(wù)的結(jié)果集大小等因素對(duì)性能的影響，提出了一種負(fù)載敏感的OLAP查詢緩存管理技術(shù)WorkloadLRU，并實(shí)現(xiàn)了一個(gè)ROLAP(Relational OLAP)原型系統(tǒng)。實(shí)驗(yàn)證明，WorkloadLRU技術(shù)獲得了較好的性能提升效果。

　　關(guān)鍵詞：聯(lián)機(jī)分析處理；緩存策略；負(fù)載敏感；數(shù)據(jù)倉(cāng)庫(kù)；查詢效率

0引言

　　隨著社會(huì)信息化的快速發(fā)展，很多行業(yè)都積累了大量的數(shù)據(jù)。為了充分利用這些數(shù)據(jù)，挖掘其中的價(jià)值，數(shù)據(jù)倉(cāng)庫(kù)技術(shù)越來(lái)越受到大家的青睞，文獻(xiàn)［1、2］介紹了數(shù)據(jù)倉(cāng)庫(kù)技術(shù)在具體領(lǐng)域的應(yīng)用。OLAP(OnLine Analysis Processing)是數(shù)據(jù)倉(cāng)庫(kù)中最為重要的技術(shù)。OLAP可以通過(guò)上卷、下鉆、切片、切塊和旋轉(zhuǎn)等基本操作讓用戶從多個(gè)角度分析數(shù)據(jù)。根據(jù)存儲(chǔ)方式的不同，OLAP具體又可以分為ROLAP、MOLAP和HOLAP。 在這三種實(shí)現(xiàn)方式中，ROLAP是最為常見的一種存儲(chǔ)方式，其優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)大都支持OLAP查詢，但其查詢效率通常較低。如何更好地提升ROLAP的查詢效率一直是數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)分析領(lǐng)域的重點(diǎn)研究主題。

　　緩存是一種利用數(shù)據(jù)的局部性原理通過(guò)存儲(chǔ)常用的數(shù)據(jù)和提高數(shù)據(jù)讀取速度來(lái)降低查詢響應(yīng)時(shí)間的方法。本文提出了一種基于負(fù)載敏感的OLAP查詢緩存管理技術(shù)Workload-LRU，該緩存管理技術(shù)能夠不斷地收集用戶查詢的行為信息并統(tǒng)計(jì)緩存數(shù)據(jù)信息，包括緩存數(shù)據(jù)集的大小、各個(gè)查詢語(yǔ)句的使用頻率和數(shù)據(jù)的訪問(wèn)時(shí)間等，并將收集到的信息用于緩存數(shù)據(jù)的替換策略上，將可能有利于后續(xù)查詢的語(yǔ)句及其執(zhí)行結(jié)果保留在緩存中。WorkloadLRU技術(shù)將針對(duì)數(shù)據(jù)倉(cāng)庫(kù)應(yīng)用中那些最新的、較頻繁執(zhí)行的、結(jié)果集較小且執(zhí)行比較耗時(shí)的查詢語(yǔ)句，盡量將其保留在緩存器中。實(shí)驗(yàn)證明，WorkloadLRU技術(shù)取得了良好的效果。

1相關(guān)工作

　　緩存按不同細(xì)粒度可分為語(yǔ)義緩存、頁(yè)緩存、表緩存、數(shù)據(jù)庫(kù)緩存和元組緩存。不同細(xì)粒度的緩存各有優(yōu)勢(shì)：細(xì)粒度越小，可重復(fù)利用的概率越大，但控制越復(fù)雜；細(xì)粒度越高，查詢時(shí)連接操作、網(wǎng)絡(luò)傳輸和復(fù)雜計(jì)算所需的時(shí)間越長(zhǎng)。

　　目前，國(guó)內(nèi)外已有不少學(xué)者在具體的應(yīng)用環(huán)境中對(duì)OLAP系統(tǒng)性能提升做過(guò)較為深入的研究。文獻(xiàn)［3］總結(jié)了常用的提升ROLAP系統(tǒng)性能的方法并提出了緩存和視圖相結(jié)合的方法。文獻(xiàn)［4、5］采用了基于語(yǔ)義緩存的方法降低查詢響應(yīng)時(shí)間、提升查詢效率。文獻(xiàn)［6、7］介紹了基于數(shù)據(jù)塊的緩存方法，在一定程度上提高了緩存的重復(fù)利用率。文獻(xiàn)［8］提出了一種基于代價(jià)的緩存替換算法，提升了查詢效率。文獻(xiàn)［9、10］采用了冷啟動(dòng)和預(yù)測(cè)管理技術(shù)相結(jié)合的方式，在緩存中保留最有利于后續(xù)查詢的查詢語(yǔ)句，在一定程度上提升了OLAP查詢效率。但其使用預(yù)測(cè)管理技術(shù)來(lái)預(yù)測(cè)用戶查詢軌跡的前提是收集到足夠多的用戶查詢?nèi)罩?。收集的日志越多，其預(yù)測(cè)的準(zhǔn)確率將越準(zhǔn)。這種方式并不適用于系統(tǒng)構(gòu)建之初時(shí)的優(yōu)化，并且其沒(méi)有考慮到數(shù)據(jù)負(fù)載情況。

　　利用緩存的方法確實(shí)能在一定程度上提升OLAP的查詢效率，但緩存替換算法的好壞是直接影響OLAP查詢效率的關(guān)鍵，文獻(xiàn)［11］對(duì)常用的緩存替換算法進(jìn)行了分析總結(jié)。

　?。?）基于LeastRecentlyUsed (LRU)策略的方法：淘汰最長(zhǎng)時(shí)間未使用的數(shù)據(jù)。

　?。?）基于LeastFrequentlyUsed (LFU)策略的方法：淘汰近期最不頻繁使用的數(shù)據(jù)。

　?。?）基于Size策略的方法：淘汰數(shù)據(jù)量最大的數(shù)據(jù)。

　　（4）基于LRUThreshold策略的方法：使用LRU算法淘汰超過(guò)某一閾值的數(shù)據(jù)。

　?。?）基于Log(Size)+LRU策略的方法：使用LRU算法淘汰數(shù)據(jù)量最大的數(shù)據(jù)。

　　上述5類緩存技術(shù)各有特點(diǎn)，均側(cè)重考慮緩存數(shù)據(jù)的一個(gè)或多個(gè)方面的特點(diǎn)（數(shù)據(jù)大小、訪問(wèn)頻繁度和訪問(wèn)時(shí)間）。

2基于負(fù)載敏感的OLAP查詢結(jié)果緩存設(shè)計(jì)

　　2.1ROLAP系統(tǒng)框架

　　圖1ROLAP系統(tǒng)總體框架本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)ROLAP系統(tǒng)原型，系統(tǒng)總體框架如圖1所示，客戶端發(fā)送查詢語(yǔ)句首先經(jīng)過(guò)緩存管理器，緩存管理器判斷緩存數(shù)據(jù)庫(kù)中是否有匹配的記錄，如果存在匹配的記錄，則從緩存數(shù)據(jù)庫(kù)中返回查詢結(jié)果，否則從數(shù)據(jù)倉(cāng)庫(kù)中返回查詢結(jié)果，本文定義的符號(hào)和含義如表1所示。表1主要的符號(hào)及含義符號(hào)含義R查詢語(yǔ)句執(zhí)行次數(shù)和訪問(wèn)時(shí)間的綜合排名Rate查詢語(yǔ)句執(zhí)行的次數(shù)NewRank查詢語(yǔ)句按照時(shí)間戳新舊程度的排名C最大效益值QueryTime從數(shù)據(jù)倉(cāng)庫(kù)中查詢的時(shí)間Size查詢結(jié)果集的大小D每次刪除數(shù)據(jù)的總大小MaxSize用戶具有的最大緩存值

　　2.2負(fù)載敏感的緩存替換算法WorkloadLRU

　　本節(jié)介紹基于LRU算法優(yōu)化的負(fù)載敏感的WorkloadLRU算法設(shè)計(jì)策略。在WorkloadLRU中，當(dāng)用戶緩存的數(shù)據(jù)達(dá)到緩存數(shù)據(jù)庫(kù)最大容量時(shí)，一些緩存的數(shù)據(jù)應(yīng)該刪除以容納新的（查詢語(yǔ)句所涉及的）結(jié)果數(shù)據(jù)。具體刪除哪些數(shù)據(jù)、保留哪些數(shù)據(jù)將直接影響OLAP的查詢效率。OLAP查詢具有一定的數(shù)據(jù)負(fù)載穩(wěn)定性，例如，最新執(zhí)行的查詢?cè)诤罄m(xù)的查詢語(yǔ)句序列中再次出現(xiàn)的概率較大。用公式(1)來(lái)表示查詢語(yǔ)句執(zhí)行的頻繁度和新舊程度的綜合排名，R值越高，對(duì)應(yīng)的查詢語(yǔ)句越應(yīng)該保留在緩存中。

　　R=a×Rate+NewRank(1)

　　此外，具體每條查詢語(yǔ)句在數(shù)據(jù)倉(cāng)庫(kù)中執(zhí)行之后得到的查詢執(zhí)行時(shí)間和結(jié)果集的大小也是不一樣的，用公式(2)來(lái)表示執(zhí)行查詢得到的查詢執(zhí)行時(shí)間和結(jié)果集的大小的比值，C值越大，對(duì)應(yīng)的查詢語(yǔ)句緩存的效益越高，這意味著其結(jié)果數(shù)據(jù)越應(yīng)該保留在緩存中。

　　C=QueryTime/Size(2)

　　當(dāng)緩存的數(shù)據(jù)達(dá)到MaxSize時(shí)，以公式(3)中的D值為限定條件，當(dāng)刪除的總數(shù)據(jù)大于或等于D值時(shí)，刪除停止。

　　D=Size+MaxSize/4(3)

　　算法具體描述如下：當(dāng)輸入查詢語(yǔ)句q后，算法首先判斷q是否在緩存中，如果在緩存中，則先更新q的執(zhí)行頻率統(tǒng)計(jì)信息，然后更新q的時(shí)間戳信息，最后從緩存中返回結(jié)果。如果q不在緩存中，那么首先從數(shù)據(jù)倉(cāng)庫(kù)中獲取數(shù)據(jù)集Resultdw，判斷緩存的剩余空間大小是否小于D，如果是，則按照R值從大到小排序緩存中的查詢語(yǔ)句，得到集合SetR，然后在集合SetR中刪除最新執(zhí)行的查詢語(yǔ)句并得到剩余的查詢語(yǔ)句集合SetC，接著循環(huán)取出集合SetC中C值最小的查詢語(yǔ)句并在緩存中刪除，直到刪除的總數(shù)據(jù)量大于D值，循環(huán)結(jié)束。至此，緩存的剩余空間大小將大于或等于D值，然后更新q的執(zhí)行頻率統(tǒng)計(jì)信息和q的時(shí)間戳信息，最后將q及查詢結(jié)果添加進(jìn)緩存中，并返回查詢結(jié)果集Resultdw。算法1: WorkloadLRU1: begin

　　2:if(q ∈ CacheKey)

　　3:UpdateRate(q)

　　4:UpdateTimeStamp(q)

　　5:Return Result(q)

　　6:end if

　　7:else

　　8:Resultdw= GetDataFromDw(q)

　　9:if(SizeOfCacheRemain<=D)

　　10:  SetR=SortR()

　　11:Setdel=Del(SetR)

　　12:  SetC = SortC(Setdel)

　　13:While(SizeOfDeleteData<D)

　　14:qdel = Del(SetC)

　　15: DelFromCache(qdel)

　　16: end while

　　18:end if

　　17: end else

　　18: UpdateRate(q)

　　19: UpdateTimeStamp(q)

　　20: Add(q, Resultdw)

　　21: return Resultdw

　　22: end

3實(shí)驗(yàn)和結(jié)果分析

　　3.1實(shí)驗(yàn)環(huán)境

　　實(shí)驗(yàn)時(shí)，在局域網(wǎng)內(nèi)構(gòu)建了三個(gè)節(jié)點(diǎn)的小型數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)。每個(gè)節(jié)點(diǎn)采用64位操作系統(tǒng)CentOS6.4，內(nèi)核版本為3.6.32,內(nèi)存20 GB，硬盤50 GB 15 000 r/m ，Intel(R) Xeon CPU E52630 @2.60 GHz。在本實(shí)驗(yàn)中，采用4.3.5.2版本的GreenPlum Database［12］搭建一個(gè)三節(jié)點(diǎn)的集群。GreenPlum Database是一個(gè)大規(guī)模并行處理的數(shù)據(jù)庫(kù)，支持下一代數(shù)據(jù)倉(cāng)庫(kù)并且能夠進(jìn)行大規(guī)模的分析處理、對(duì)數(shù)據(jù)自動(dòng)分區(qū)和并行查詢。使用GreenPlum構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)集群，相較于傳統(tǒng)的基于數(shù)據(jù)構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)的方案，其性能優(yōu)勢(shì)較為明顯。

　　本文的實(shí)驗(yàn)采用Redis［13］ V3.03作為ROLAP系統(tǒng)的緩存數(shù)據(jù)庫(kù)， 其配置有5 GB內(nèi)存，默認(rèn)Redis采用Volatilelru算法（以下簡(jiǎn)稱LRU算法）。Redis是一個(gè)開源的、先進(jìn)的KeyValue內(nèi)存數(shù)據(jù)庫(kù),支持多種數(shù)據(jù)結(jié)構(gòu)，如：strings、hashes、lists、sets、sorted sets、bitmaps和hyperloglogs等。Redis可以用來(lái)提供緩存服務(wù)，并且非常適合OLAP查詢結(jié)果的語(yǔ)義緩存，即OLAP查詢的語(yǔ)句和查詢結(jié)果可以分別用key和value來(lái)存儲(chǔ)。Redis本身具有5種緩存替換算法，分別如下：

　?。?）volatilelru，使用LRU算法淘汰過(guò)期的key；

　　（2）allkeyslru,使用LRU算法隨機(jī)地淘汰key；

　?。?）volatilerandom，隨機(jī)淘汰過(guò)期的key；

　?。?）volatilettle，淘汰快要過(guò)期的key；

　?。?）Noeviction，不淘汰任何key，直接返回錯(cuò)誤。

　　Redis的5種替換算法都沒(méi)有考慮到數(shù)據(jù)負(fù)載情況、返回結(jié)果集大小和不用緩存時(shí)直接從數(shù)據(jù)倉(cāng)庫(kù)中查詢所需的時(shí)間。

　　本文采用TPCH［14］產(chǎn)生10 GB數(shù)據(jù)作為實(shí)驗(yàn)的數(shù)據(jù)集，TPCH生成22條查詢語(yǔ)句作為實(shí)驗(yàn)的OLAP查詢語(yǔ)句。TPCH是一個(gè)決策支持的基準(zhǔn)測(cè)試，集成了一系列面向業(yè)務(wù)的即席查詢和數(shù)據(jù)生成工具，其提供的查詢和生成的數(shù)據(jù)具有廣泛的行業(yè)代表性，是OLAP查詢中普遍接受的基準(zhǔn)測(cè)試。

　　3.2實(shí)驗(yàn)方案

　　本文實(shí)驗(yàn)分為兩個(gè)階段：

　?。?）查詢負(fù)載模擬階段：為了使模擬的OLAP查詢負(fù)載具有一定的穩(wěn)定性（例如：包含部分重復(fù)執(zhí)行的查詢），首先從22條TPCH查詢語(yǔ)句中隨機(jī)、不重復(fù)地抽取10條語(yǔ)句，并在這10條語(yǔ)句中隨機(jī)、可重復(fù)地抽取50條查詢語(yǔ)句放入集合C1,1，然后從22條語(yǔ)句中隨機(jī)、可重復(fù)地抽取50條查詢語(yǔ)句放入集合C1,2，最后將集合C1,1和集合C1,2融合起來(lái)，并打亂其順序放到集合C1,3，得到順序包含一定重復(fù)率的100條查詢語(yǔ)句。如此重復(fù)10次得到10個(gè)順序包含一定重復(fù)的100條查詢語(yǔ)句：C1,3, C2,3, C3,3, C4,3, C5,3, C6,3, C7,3, C8,3, C9,3, C10,3 。

　?。?）查詢執(zhí)行階段：在采用WorkloadLRU和LRU算法的原型系統(tǒng)執(zhí)行查詢負(fù)載模擬階段，得到10組查詢序列集合，以及各查詢語(yǔ)句及各組查詢語(yǔ)句的執(zhí)行統(tǒng)計(jì)信息。

　　3.3結(jié)果及分析

　　圖210組實(shí)驗(yàn)結(jié)果對(duì)比圖2是10次實(shí)驗(yàn)中WorkloadLRU算法和LRU算法分別執(zhí)行100條查詢語(yǔ)句所耗時(shí)間的對(duì)比。圖3是10次實(shí)驗(yàn)室中LRU與WorkloadLRU分別執(zhí)行100條查詢語(yǔ)句所耗時(shí)間的差值，其縱坐標(biāo)的正方向代表WorkloadLRU節(jié)省下來(lái)的查詢時(shí)間，負(fù)方向代表LRU算法節(jié)省的時(shí)間。從以上兩圖可以看出，采用WorkloadLRU算法后，查詢響應(yīng)時(shí)間在大部分情況下比采用LRU時(shí)要短，查詢效率得到較為顯著的提升。

　　從圖3中可以看出，WorkloadLRU和LRU算法在第4組實(shí)驗(yàn)上的查詢時(shí)間差距最大，在第9組實(shí)驗(yàn)上的查詢時(shí)間差距最小，LRU算法甚至還超過(guò)了WorkloadLRU的執(zhí)行效率。下面將具體分析這兩組實(shí)驗(yàn)對(duì)比效果最好和最差的情況。

　　（1）WorkloadLRU性能最好的一組實(shí)驗(yàn)：通過(guò)深入分析第4組實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)WorkloadLRU算法在替換數(shù)據(jù)時(shí)，替換的是那些使用頻率不高、C值較小的數(shù)據(jù)，其他的都保留在緩存中。而LRU算法只是考慮查詢語(yǔ)句的新舊程度，替換掉那些最不常用的數(shù)據(jù)，沒(méi)有考慮到查詢語(yǔ)句的Size和QueryTime。由此可看出，WorkloadLRU算法在緩存中保留的是最有利于提升后續(xù)OLAP查詢執(zhí)行效率的數(shù)據(jù)。所以在后續(xù)的查詢中，對(duì)于C值較大的查詢語(yǔ)句，WorkloadLRU算法的做法是直接從緩存數(shù)據(jù)中獲取查詢結(jié)果集，而LRU算法很可能要從數(shù)據(jù)倉(cāng)庫(kù)中獲取查詢結(jié)果集。上述區(qū)別使得WorkloadLRU算法的查詢執(zhí)行效率要比LRU高。

　?。?）WorkloadLRU性能最差的一組實(shí)驗(yàn)：經(jīng)過(guò)仔細(xì)分析第9組實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，二者在執(zhí)行該組實(shí)驗(yàn)中的100條查詢語(yǔ)句時(shí)的緩存策略是一樣的。每一條查詢語(yǔ)句的結(jié)果要么都在緩存中，要么都在數(shù)據(jù)倉(cāng)庫(kù)中，只是同一條查詢語(yǔ)句在數(shù)據(jù)倉(cāng)庫(kù)中執(zhí)行的時(shí)間不同，所以，在這里視二者的查詢效率等同。

4結(jié)束語(yǔ)

　　本文提出的WorkloadLRU是一種負(fù)載敏感的OLAP結(jié)果緩存算法。此方法通過(guò)獲取用戶的查詢行為模式，將常用的、計(jì)算比較耗時(shí)但結(jié)果集比較小的OLAP查詢結(jié)果盡可能長(zhǎng)時(shí)間地保留在緩存中，從而使得緩存中保留了盡可能多的有利于提升后續(xù)查詢執(zhí)行效率的數(shù)據(jù)。本文的實(shí)驗(yàn)結(jié)果證明，WorkloadLRU技術(shù)在80%的應(yīng)用用例中都會(huì)獲得優(yōu)于LRU算法的結(jié)果。即使在效果最差時(shí)的應(yīng)用用例下，其執(zhí)行效率都能保持與LRU算法基本持平。

參考文獻(xiàn)

　　［1］ 譚光瑋,武彤. 基于生產(chǎn)線質(zhì)量控制系統(tǒng)的動(dòng)態(tài)數(shù)據(jù)倉(cāng)庫(kù)解決方案［J］. 微型機(jī)與應(yīng)用,2014,33（7）:79，12.

　?。?］ 文篤石. 基于數(shù)據(jù)倉(cāng)庫(kù)的客戶挽留系統(tǒng)［J］. 微型機(jī)與應(yīng)用,2015,34（18）:1113.

　　［3］ 田英愛,張志華,蔣玉茹. 基于緩存機(jī)制的ROLAP系統(tǒng)改進(jìn)方法研究［J］. 微計(jì)算機(jī)信息,2008（3）:180182.

　?。?］ 趙均. 解析一種數(shù)據(jù)處理中間件系統(tǒng)語(yǔ)義緩存技術(shù)［J］. 電子技術(shù)與軟件工程,2015(1):216217.

　?。?］ PEREZ L L, JERMAINE C M. Historyaware query optimization with materialized intermediate views［C］.Data Engineering (ICDE), 2014 IEEE 30th International Conference on. IEEE, 2014: 520531.

　?。?］ MOUDANI W, HUSSEIN M, MOUKHTAR M, et al. An intelligent approach to improve the performance of a data warehouse cache based on association rules［J］. Journal of Information and Optimization Sciences, 2012, 33(6): 601621.

　　［7］ KHARBUTLI M, SHEIKH R. LACS: a localityaware costsensitive cache replacement algorithm［J］. Computers, IEEE Transactions on, 2014, 63(8): 19751987.

　?。?］ HE J, ZHANG S, HE B. Incache query coprocessing on coupled CPUGPU architectures［J］. Proceedings of the VLDB Endowment, 2014, 8(4): 329340.

　?。?］ 肖恒永. OLAP查詢優(yōu)化的研究與實(shí)現(xiàn)［D］.成都：電子科技大學(xué),2012.

　?。?0］ 許建,馬強(qiáng). ROLAP查詢優(yōu)化的研究［J］. 計(jì)算機(jī)與現(xiàn)代化,2008（7）:2932.

　　［11］ CAO P, IRANI S. Costaware WWW proxy caching algorithms［C］. Usenix Symposium on Internet Technologies and Systems, 1997, 12(97): 193206.

　?。?2］ 維基百科.Greeplum［EB/OL］.(20150901)［20151104］https://en.wikipedia.org/wiki/greenplum.

　?。?3］ 維基百科.Redis［EB/OL］.(20151001) ［20151104］http://zh.wikipedia.org/wiki/Redis.

　?。?4］ Transaction Processing Performance Council（TPC）.TPC BENCHMARKTMH（decision support）standard specification revision2.3.0.［EB/OL］.(20150910)［20151104］http://www.tpc.org/tpch/default.asp.