一种负载敏感的OLAP查询结果缓存管理技术

摘要：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.1ROLAP系统框架

图1ROLAP系统总体框架本文设计并实现了一个ROLAP系统原型，系统总体框架如图1所示，客户端发送查询语句首先经过缓存管理器，缓存管理器判断缓存数据库中是否有匹配的记录，如果存在匹配的记录，则从缓存数据库中返回查询结果，否则从数据仓库中返回查询结果，本文定义的符号和含义如表1所示。表1主要的符号及含义符号含义R查询语句执行次数和访问时间的综合排名Rate查询语句执行的次数NewRank查询语句按照时间戳新旧程度的排名C最大效益值QueryTime从数据仓库中查询的时间Size查询结果集的大小D每次删除数据的总大小MaxSize用户具有的最大缓存值

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: 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实验和结果分析

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结果及分析

图210组实验结果对比图2是10次实验中WorkloadLRU算法和LRU算法分别执行100条查询语句所耗时间的对比。图3是10次实验室中LRU与WorkloadLRU分别执行100条查询语句所耗时间的差值，其纵坐标的正方向代表WorkloadLRU节省下来的查询时间，负方向代表LRU算法节省的时间。从以上两图可以看出，采用WorkloadLRU算法后，查询响应时间在大部分情况下比采用LRU时要短，查询效率得到较为显著的提升。

从图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.