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

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

0引言

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

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

1相關(guān)工作

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

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

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

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

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

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

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

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

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

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

　　2.1ROLAP系統(tǒng)框架

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

　　2.2負載敏感的緩存替換算法WorkloadLRU

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

　　R=a×Rate+NewRank(1)

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

　　C=QueryTime/Size(2)

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

　　D=Size+MaxSize/4(3)

　　算法具體描述如下：當(dāng)輸入查詢語句q后，算法首先判斷q是否在緩存中,，如果在緩存中,，則先更新q的執(zhí)行頻率統(tǒng)計信息，然后更新q的時間戳信息,，最后從緩存中返回結(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)計信息和q的時間戳信息，最后將q及查詢結(jié)果添加進緩存中,，并返回查詢結(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實驗和結(jié)果分析

　　3.1實驗環(huán)境

　　實驗時，在局域網(wǎng)內(nèi)構(gòu)建了三個節(jié)點的小型數(shù)據(jù)倉庫系統(tǒng),。每個節(jié)點采用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,。在本實驗中，采用4.3.5.2版本的GreenPlum Database［12］搭建一個三節(jié)點的集群,。GreenPlum Database是一個大規(guī)模并行處理的數(shù)據(jù)庫,，支持下一代數(shù)據(jù)倉庫并且能夠進行大規(guī)模的分析處理、對數(shù)據(jù)自動分區(qū)和并行查詢,。使用GreenPlum構(gòu)建數(shù)據(jù)倉庫集群,，相較于傳統(tǒng)的基于數(shù)據(jù)構(gòu)建數(shù)據(jù)倉庫的方案,，其性能優(yōu)勢較為明顯。

　　本文的實驗采用Redis［13］ V3.03作為ROLAP系統(tǒng)的緩存數(shù)據(jù)庫,， 其配置有5 GB內(nèi)存,，默認(rèn)Redis采用Volatilelru算法（以下簡稱LRU算法）。Redis是一個開源的,、先進的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種緩存替換算法，分別如下：

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

　?。?）allkeyslru,使用LRU算法隨機地淘汰key,；

　　（3）volatilerandom,，隨機淘汰過期的key,；

　　（4）volatilettle,，淘汰快要過期的key,；

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

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

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

　　3.2實驗方案

　　本文實驗分為兩個階段：

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

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

　　3.3結(jié)果及分析

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

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

　?。?）WorkloadLRU性能最好的一組實驗：通過深入分析第4組實驗數(shù)據(jù)，發(fā)現(xiàn)WorkloadLRU算法在替換數(shù)據(jù)時,，替換的是那些使用頻率不高,、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性能最差的一組實驗：經(jīng)過仔細分析第9組實驗數(shù)據(jù)發(fā)現(xiàn)，二者在執(zhí)行該組實驗中的100條查詢語句時的緩存策略是一樣的,。每一條查詢語句的結(jié)果要么都在緩存中,，要么都在數(shù)據(jù)倉庫中，只是同一條查詢語句在數(shù)據(jù)倉庫中執(zhí)行的時間不同,，所以,，在這里視二者的查詢效率等同。

4結(jié)束語

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

參考文獻

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

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

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

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

　　［5］ 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.

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

　　［8］ 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)化的研究與實現(xiàn)［D］.成都：電子科技大學(xué),2012.

　?。?0］ 許建,馬強. ROLAP查詢優(yōu)化的研究［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.