一種負載敏感的OLAP查詢結果緩存管理技術*

陽穎燦， 張小平， 李 暉

(1. 貴州大學 計算機科學與技術學院，貴州 貴陽 550025； 2.貴州大學 貴州省先進計算與醫療信息服務工程實驗室，貴州 貴陽 550025)

一種負載敏感的OLAP查詢結果緩存管理技術*

陽穎燦1,2， 張小平1,2， 李 暉1,2

(1. 貴州大學 計算機科學與技術學院，貴州 貴陽 550025； 2.貴州大學 貴州省先進計算與醫療信息服務工程實驗室，貴州 貴陽 550025)

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

聯機分析處理；緩存策略；負載敏感；數據倉庫；查詢效率

0 引言

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

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

1 相關工作

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

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

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

(1)基于Least-Recently-Used (LRU)策略的方法：淘汰最長時間未使用的數據。

(2)基于Least-Frequently-Used (LFU)策略的方法：淘汰近期最不頻繁使用的數據。

(3)基于Size策略的方法：淘汰數據量最大的數據。

(4)基于LRU-Threshold策略的方法：使用LRU算法淘汰超過某一閾值的數據。

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

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

2 基于負載敏感的OLAP查詢結果緩存設計

2.1 ROLAP系統框架

圖1 ROLAP系統總體框架

本文設計并實現了一個ROLAP系統原型，系統總體框架如圖1所示，客戶端發送查詢語句首先經過緩存管理器，緩存管理器判斷緩存數據庫中是否有匹配的記錄，如果存在匹配的記錄，則從緩存數據庫中返回查詢結果，否則從數據倉庫中返回查詢結果，本文定義的符號和含義如表1所示。

表1 主要的符號及含義

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

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

R=a×Rate+NewRank

(1)

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

C=QueryTime/Size

(2)

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

D=Size+MaxSize/4

(3)

算法具體描述如下：當輸入查詢語句q后，算法首先判斷q是否在緩存中，如果在緩存中，則先更新q的執行頻率統計信息，然后更新q的時間戳信息，最后從緩存中返回結果。如果q不在緩存中，那么首先從數據倉庫中獲取數據集Resultdw，判斷緩存的剩余空間大小是否小于D，如果是，則按照R值從大到小排序緩存中的查詢語句，得到集合SetR，然后在集合SetR中刪除最新執行的查詢語句并得到剩余的查詢語句集合SetC，接著循環取出集合SetC中C值最小的查詢語句并在緩存中刪除，直到刪除的總數據量大于D值，循環結束。至此，緩存的剩余空間大小將大于或等于D值，然后更新q的執行頻率統計信息和q的時間戳信息，最后將q及查詢結果添加進緩存中，并返回查詢結果集Resultdw。

算法1:Workload-LRU1:begin2: if(q∈-CacheKey)3: UpdateRate(q)4: UpdateTimeStamp(q)5: ReturnResult(q)6: endif7: else8: Resultdw=GetDataFromDw(q)9: if(SizeOfCacheRemain<=D)10: SetR=SortR()11: Setdel=Del(SetR)12: SetC=SortC(Setdel)13: While(SizeOfDeleteData

3 實驗和結果分析

3.1 實驗環境

實驗時，在局域網內構建了三個節點的小型數據倉庫系統。每個節點采用64位操作系統CentOS-6.4，內核版本為3.6.32,內存20 GB，硬盤50 GB 15 000 r/m ，Intel(R) Xeon CPU E5-2630 @2.60 GHz。在本實驗中，采用4.3.5.2版本的GreenPlum Database[12]搭建一個三節點的集群。GreenPlum Database是一個大規模并行處理的數據庫，支持下一代數據倉庫并且能夠進行大規模的分析處理、對數據自動分區和并行查詢。使用GreenPlum構建數據倉庫集群，相較于傳統的基于數據構建數據倉庫的方案，其性能優勢較為明顯。

本文的實驗采用Redis[13]V3.03作為ROLAP系統的緩存數據庫， 其配置有5 GB內存，默認Redis采用Volatile-lru算法(以下簡稱LRU算法)。Redis是一個開源的、先進的Key-Value內存數據庫,支持多種數據結構，如：strings、hashes、lists、sets、sorted sets、bitmaps和hyperloglogs等。Redis可以用來提供緩存服務，并且非常適合OLAP查詢結果的語義緩存，即OLAP查詢的語句和查詢結果可以分別用key和value來存儲。Redis本身具有5種緩存替換算法，分別如下：

(1)volatile-lru，使用LRU算法淘汰過期的key；

(2)allkeys-lru,使用LRU算法隨機地淘汰key；

(3)volatile-random，隨機淘汰過期的key；

(4)volatile-ttle，淘汰快要過期的key；

(5)Noeviction，不淘汰任何key，直接返回錯誤。

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

本文采用TPC-H[14]產生10 GB數據作為實驗的數據集，TPC-H生成22條查詢語句作為實驗的OLAP查詢語句。TPC-H是一個決策支持的基準測試，集成了一系列面向業務的即席查詢和數據生成工具，其提供的查詢和生成的數據具有廣泛的行業代表性，是OLAP查詢中普遍接受的基準測試。

3.2 實驗方案

本文實驗分為兩個階段：

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

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

3.3 結果及分析

圖2 10組實驗結果對比

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

圖3 10組實驗LRU與Load-based查詢執行時間的差值

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

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

(2)Workload-LRU性能最差的一組實驗：經過仔細分析第9組實驗數據發現，二者在執行該組實驗中的100條查詢語句時的緩存策略是一樣的。每一條查詢語句的結果要么都在緩存中，要么都在數據倉庫中，只是同一條查詢語句在數據倉庫中執行的時間不同，所以，在這里視二者的查詢效率等同。

4 結束語

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

[1] 譚光瑋,武彤. 基于生產線質量控制系統的動態數據倉庫解決方案[J]. 微型機與應用,2014,33(7):7-9，12.

[2] 文篤石. 基于數據倉庫的客戶挽留系統[J]. 微型機與應用,2015,34(18):11-13.

[3] 田英愛,張志華,蔣玉茹. 基于緩存機制的ROLAP系統改進方法研究[J]. 微計算機信息,2008(3):180-182.

[4] 趙均. 解析一種數據處理中間件系統語義緩存技術[J]. 電子技術與軟件工程,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.

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

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

[9] 肖恒永. OLAP查詢優化的研究與實現[D].成都：電子科技大學,2012.

[10] 許建,馬強. ROLAP查詢優化的研究[J]. 計算機與現代化,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.

[12] 維基百科.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.

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

A cache management technology based on load sensitive OLAP query results

Yang Yingcan1,2, Zhang Xiaoping1,2, Li Hui1,2

(1. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China; 2. Guizhou Engineering Laboratory for Advanced Computing and Medical Information Service, Guizhou University, Guiyang 550025, China)

OLAP is a typical application of data warehouse. High concurrent data-intensive OLAP tasks often tend to incur large resource consumption and make the data warehouse system to be inefficient.Caching technology has been recognized as an effective method to accelerate the execution of OLAP tasks. In this paper, a workload sensitive OLAP query cache management technology, named Workload-LRU, has been proposed by carefully incorporate OLAP task’s performance metrics, such as workload characteristics, size of results set and so on. To evaluate the effectiveness of Workload-LRU, we implement it into a ROLAP prototype system, and the experimental results show that the proposed Workload-LRU technology is superior to the representative LRU based techniques.

OLAP; cache strategy; load sensitive; data warehouse; query efficiency

貴州省科技基礎條件平臺項目(黔科平臺[2015]4001)；貴州省科技計劃項目([GY[2014]3018)

TP312

A

1674- 7720(2016)03- 0031- 04

陽穎燦，張小平，李暉. 一種負載敏感的OLAP查詢結果緩存管理技術[J].微型機與應用，2016,35(3)：31- 34.

2015-11-04)

陽穎燦(1991-)，男，碩士研究生，主要研究方向：數據分析、云計算。

張小平(1956-)，男，研究員，主要研究方向：研究方向為軟件工程及數據庫技術。

李暉(1982-)，通信作者，男，博士，副教授，主要研究方向：大規模數據管理與分析、高性能數據庫、云計算。E-mail：cse.HuiLi@gzu.edu.cn。