摘要：OLAP(On Line Analysis Processing)是數(shù)據(jù)倉庫的典型應(yīng)用，在數(shù)據(jù)倉庫中頻繁并發(fā)地執(zhí)行涉及較大數(shù)據(jù)量的OLAP查詢時(shí),，其查詢處理效率易于逐漸降低,。緩存技術(shù)是一種有效降低OLAP查詢處理延時(shí)的方法。在現(xiàn)有的緩存數(shù)據(jù)存儲,、淘汰策略等研究工作的基礎(chǔ)上,，結(jié)合OLAP任務(wù)的負(fù)載特性、OLAP任務(wù)的結(jié)果集大小等因素對性能的影響,，提出了一種負(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ù)倉庫；查詢效率

0引言

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

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

1相關(guān)工作

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

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

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

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

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

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

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

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

　　上述5類緩存技術(shù)各有特點(diǎn),，均側(cè)重考慮緩存數(shù)據(jù)的一個(gè)或多個(gè)方面的特點(diǎn)（數(shù)據(jù)大小、訪問頻繁度和訪問時(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ā)送查詢語句首先經(jīng)過緩存管理器,，緩存管理器判斷緩存數(shù)據(jù)庫中是否有匹配的記錄,，如果存在匹配的記錄，則從緩存數(shù)據(jù)庫中返回查詢結(jié)果,，否則從數(shù)據(jù)倉庫中返回查詢結(jié)果,，本文定義的符號和含義如表1所示。表1主要的符號及含義符號含義R查詢語句執(zhí)行次數(shù)和訪問時(shí)間的綜合排名Rate查詢語句執(zhí)行的次數(shù)NewRank查詢語句按照時(shí)間戳新舊程度的排名C最大效益值QueryTime從數(shù)據(jù)倉庫中查詢的時(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ù)庫最大容量時(shí),，一些緩存的數(shù)據(jù)應(yīng)該刪除以容納新的（查詢語句所涉及的）結(jié)果數(shù)據(jù)。具體刪除哪些數(shù)據(jù),、保留哪些數(shù)據(jù)將直接影響OLAP的查詢效率,。OLAP查詢具有一定的數(shù)據(jù)負(fù)載穩(wěn)定性，例如,，最新執(zhí)行的查詢在后續(xù)的查詢語句序列中再次出現(xiàn)的概率較大,。用公式(1)來表示查詢語句執(zhí)行的頻繁度和新舊程度的綜合排名，R值越高,，對應(yīng)的查詢語句越應(yīng)該保留在緩存中,。

　　R=a×Rate+NewRank(1)

　　此外，具體每條查詢語句在數(shù)據(jù)倉庫中執(zhí)行之后得到的查詢執(zhí)行時(shí)間和結(jié)果集的大小也是不一樣的,，用公式(2)來表示執(zhí)行查詢得到的查詢執(zhí)行時(shí)間和結(jié)果集的大小的比值,，C值越大，對應(yīng)的查詢語句緩存的效益越高,，這意味著其結(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)輸入查詢語句q后,，算法首先判斷q是否在緩存中,，如果在緩存中，則先更新q的執(zhí)行頻率統(tǒng)計(jì)信息,，然后更新q的時(shí)間戳信息,，最后從緩存中返回結(jié)果。如果q不在緩存中,，那么首先從數(shù)據(jù)倉庫中獲取數(shù)據(jù)集Resultdw,，判斷緩存的剩余空間大小是否小于D，如果是,，則按照R值從大到小排序緩存中的查詢語句,，得到集合SetR，然后在集合SetR中刪除最新執(zhí)行的查詢語句并得到剩余的查詢語句集合SetC,，接著循環(huán)取出集合SetC中C值最小的查詢語句并在緩存中刪除,，直到刪除的總數(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ù)倉庫系統(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ù)庫，支持下一代數(shù)據(jù)倉庫并且能夠進(jìn)行大規(guī)模的分析處理,、對數(shù)據(jù)自動分區(qū)和并行查詢,。使用GreenPlum構(gòu)建數(shù)據(jù)倉庫集群，相較于傳統(tǒng)的基于數(shù)據(jù)構(gòu)建數(shù)據(jù)倉庫的方案,，其性能優(yōu)勢較為明顯,。

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

　　（1）volatilelru,，使用LRU算法淘汰過期的key,；

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

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

　?。?）volatilettle,，淘汰快要過期的key；

　?。?）Noeviction,，不淘汰任何key，直接返回錯誤,。

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

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

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

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

　?。?）查詢負(fù)載模擬階段：為了使模擬的OLAP查詢負(fù)載具有一定的穩(wěn)定性（例如：包含部分重復(fù)執(zhí)行的查詢）,，首先從22條TPCH查詢語句中隨機(jī)、不重復(fù)地抽取10條語句,，并在這10條語句中隨機(jī),、可重復(fù)地抽取50條查詢語句放入集合C1,1，然后從22條語句中隨機(jī),、可重復(fù)地抽取50條查詢語句放入集合C1,2,，最后將集合C1,1和集合C1,2融合起來，并打亂其順序放到集合C1,3,，得到順序包含一定重復(fù)率的100條查詢語句,。如此重復(fù)10次得到10個(gè)順序包含一定重復(fù)的100條查詢語句：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組查詢序列集合，以及各查詢語句及各組查詢語句的執(zhí)行統(tǒng)計(jì)信息,。

　　3.3結(jié)果及分析

　　圖210組實(shí)驗(yàn)結(jié)果對比圖2是10次實(shí)驗(yàn)中WorkloadLRU算法和LRU算法分別執(zhí)行100條查詢語句所耗時(shí)間的對比,。圖3是10次實(shí)驗(yàn)室中LRU與WorkloadLRU分別執(zhí)行100條查詢語句所耗時(shí)間的差值，其縱坐標(biāo)的正方向代表WorkloadLRU節(jié)省下來的查詢時(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算法甚至還超過了WorkloadLRU的執(zhí)行效率。下面將具體分析這兩組實(shí)驗(yàn)對比效果最好和最差的情況,。

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

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

4結(jié)束語

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

參考文獻(xiàn)

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

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

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

　　［4］ 趙均. 解析一種數(shù)據(jù)處理中間件系統(tǒng)語義緩存技術(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.

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

　?。?1］ 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.

　　［13］ 維基百科.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.