《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計應(yīng)用 > 一種負載敏感的OLAP查詢結(jié)果緩存管理技術(shù)
一種負載敏感的OLAP查詢結(jié)果緩存管理技術(shù)
2016年微型機與應(yīng)用第3期
陽穎燦1,2, 張小平1,2, 李暉1,2
(1. 貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025; 2.貴州大學(xué) 貴州省先進計算與醫(yī)療信息服務(wù)工程實驗室,貴州 貴陽 550025)
摘要: 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ù)獲得了較好的性能提升效果。
Abstract:
Key words :

  摘要: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ù)測的準確率將越準。這種方式并不適用于系統(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ù)。

 ?。?)基于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)框架

001.jpg

  圖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用戶具有的最大緩存值

002.jpg

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

  本節(jié)介紹基于LRU算法優(yōu)化的負載敏感的WorkloadLRU算法設(shè)計策略。在WorkloadLRU中,當用戶緩存的數(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)

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

  D=Size+MaxSize/4(3)

  算法具體描述如下:當輸入查詢語句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)存,默認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種緩存替換算法,分別如下:

  (1)volatilelru,使用LRU算法淘汰過期的key;

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

 ?。?)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是一個決策支持的基準測試,集成了一系列面向業(yè)務(wù)的即席查詢和數(shù)據(jù)生成工具,其提供的查詢和生成的數(shù)據(jù)具有廣泛的行業(yè)代表性,是OLAP查詢中普遍接受的基準測試。

  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 。

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

  3.3結(jié)果及分析

003.jpg

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

004.jpg

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

  (1)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算法基本持平。

參考文獻

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

 ?。?] 文篤石. 基于數(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.

 ?。?] 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.

  [6] 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.

 ?。?] 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.

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

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


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。