用户行为选择参与的五层十五级瓦片缓存置换策略研究

2016-07-01蔡阳军杜震洪刘仁义王炼刚

浙江大学学报（理学版） 2016年4期

褚信, 蔡阳军, 杜震洪*, 张丰, 刘仁义, 王炼刚, 何敬

(1.浙江大学浙江省资源与环境信息系统重点实验室, 浙江杭州 310028； 2.浙江大学地理信息科学研究所,浙江杭州 310027; 3.杭州市住房保障办公室，浙江杭州 310006)

褚信1,2, 蔡阳军3, 杜震洪1,2*, 张丰1,2, 刘仁义2, 王炼刚1,2, 何敬1,2

FIFO、LRU、LFU、GDLVF等传统瓦片缓存置换算法侧重于瓦片访问时间和频率、瓦片大小、空间位置关系,不适合具有多源、异构特点的五层十五级瓦片数据,在五层十五级瓦片数据缓存的应用上存在局限性.提出了用户行为参与的缓存置换算法UPBA(User Preference Based Tile Cache Replacement Algorithm),并从用户行为、瓦片访问的时间和频率、瓦片大小、空间位置关系等方面分析了UPBA算法，提出了提高置换效率的方法.并对最高分辨率为100和250 m、生产时间为2014年11月、2015年1～3月的高分一号、高分二号、资源三号影像数据集进行日志驱动仿真实验.结果表明：相较传统的缓存置换算法,UPBA提高了瓦片请求的命中率和字节命中率,降低了客户端流量消耗和服务器端负载.

五层十五级；瓦片缓存置换；空间数据

瓦片数据的实时快速加载是提高网络GIS服务质量的重要内容,客户端缓存瓦片数据则是提高GIS服务质量的重要途径.五层十五级瓦片数据组织模型按比例对瓦片数据进行切分并重采样成1 000×1 000标准分辨率切片数据,将多源异构遥感影像数据标准化后统一于金字塔数据组织模型下[1].

缓存算法，将所需要的数据存储在本地,以减少数据的请求频率和网络传输量,快速响应请求,进而提升客户端的用户体验[2].并且当客户端缓存存储区快饱和时,可通过缓存置换算法选择并删除部分瓦片[3],以缓存从服务器端响应请求所返回的新瓦片.

目前，缓存置换算法已从FIFO、LRU、LRU等单因子算法演进到MIX、GD-Size等多因子算法,各种算法结合数据访问的时间或空间局部性,在不同的访问模型下表现各自的优越性[4-6].笔者在研究几种传统算法的基础上,结合五层十五级瓦片数据的特点,提出了用户行为选择参与的五层十五级瓦片缓存置换算法UPBA(User Preference Based Tile Cache Replacement Algorithm).

1 基于五层十五级的瓦片数据缓存索引

五层十五级瓦片数据组织模型摒弃了四叉树切分标准,将瓦片数据划分为5层,每一层3个级别，总共15级.如表1所示,每一层内的级别按照5∶2.5∶1的比例进行排列,上层的最后一级与下层的第一级之间的比例为2∶1,按此比例对瓦片数据进行切分，重采样成1 000×1 000的标准分辨率瓦片数据[7-8].

瓦片数据的命名，采用五层十五级标准命名方式,

表1 五层十五级划分标准表Table 1 Five-layer Fifteen-level division standard

瓦片的名称是由原始数据的卫星、传感器、采集时间这些基本数据属性结合分块数据所属的级数和瓦片的地理信息(左下角的行列号)拼接而成.例如命名为HJ1A_CCD2_20110513_4_254_587.tif的数据就表示原始数据卫星是HJ星，传感器是CCD2,原始影像的采集时间是2011年5月13日,瓦片数据在五层十五级中的第4级,瓦片数据左下角的行号是254,列号是587.

本文根据五层十五级空间数据组织模型,以瓦片为粒度,构造了瓦片缓存索引.瓦片数据的缓存索引与瓦片数据分开存储,被缓存的瓦片数据单独存放

图1 基于R树的瓦片缓存索引Fig.1 Tile cache index based on R-tree

在缓存文件区域.如图1所示,缓存索引使用R树构建,索引项采用Key-value结构,row_num是该瓦片所在行号,column_num是列号,level_num是层级,product是产品类型,tile_size是文件大小,data_time是生产时间,create_time是首次存储时间,last_access_time是最后一次访问时间,access_times是访问总次数,geometry是覆盖的地理范围.

2 用户行为参与的空间数据缓存置换算法

2.1 几种传统的空间数据缓存置换算法

传统的缓存置换算法，如FIFO、LFU、 LRU等侧重于对瓦片的时间和频率特征进行分析：FIFO算法认为缓存瓦片中瓦片再次访问的概率p反比于当前时刻与瓦片首次存储于缓存中的时刻的时间间隔,有p～1/△t=1/current_system_time-create_time, FIFO算法总是置换p最小(create_time最小)的瓦片；LFU算法认为瓦片再次被访问的概率与瓦片被访问的次数成正比,有p～ access_times,该算法总是将访问次数最少的瓦片移除；LRU算法认为瓦片再次被访问的概率与瓦片被访问时刻与当前时刻的时间间隔成反比,有p～1/△t=1/current_system_time-last_access_time,该算法总是将许久未访问(last_access_time最小)的瓦片移除[2-3,9].

综合分析以上几种传统瓦片置换算法,FIFO算法忽略了某一用户对特定区域长时间、高频度的访问,可能删除用户感兴趣的某一区域；LFU算法可能将前期经常访问但是以后并不经常访问的瓦片长期保留在缓存中,LRU算法可能将用户偶发访问的瓦片保留在缓存中,造成缓存污染.

2.2 面向网络GIS的最小价值空间数据缓存置换算法

涂振发等[3]综合考虑上述传统空间数据缓存置换算法的优缺点,提出了面向网络GIS的最小价值空间数据缓存置换算法GDLVF,该算法除了考虑传统缓存置换算法的时间、访问频率、文件大小等因素外,还兼顾了空间数据的空间位置特征,并依据这些因素使用特定的价值函数计算数据价值,移除其中数据价值最小的数据集:

V(i)=Vspatial(i)×Vtime(i)×Vsize(i)，

(1)

式(1)中,V(i)为瓦片i的数据价值,Vspatial(i)为空间位置价值,Vtime(i)为时间价值,Vsize(i)为数据大小价值.

2.2.1 空间位置价值

GDLVF算法认为数据距离和有效范围区域是影响缓存置换算法的重要因素,有效范围区域是落在当前可视窗口范围内的区域,数据距离是瓦片数据的中心点距离当前可视窗口中心点的距离,有效区域范围越大、数据距离越小的数据被再次访问的可能性越大[3,10],并以此提出瓦片空间位置价值的计算公式：

(2)

式(2)中Vspatial(i)为瓦片数据的空间位置价值,Area(i)为瓦片数据有效范围的面积,D(i)为瓦片的数据距离,并且规定0≤Area(i)<1时,设定Area(i)=1,当0≤D(i)<1时,设定D(i)=1.

2.2.2 时间价值

GDLVF算法认为,越久未被访问的数据其再次被访问的概率越小,最近越被频繁访问的数据其再次被访问的概率越大,并以此提出了瓦片时间价值的计算公式：

(3)

式(3)中,Vtime(i)为瓦片数据的时间价值,avg_access_time(i)为瓦片数据的平均访问间隔时间.

(4)

式(4)中,avg_access_time(i)为瓦片的平均访问间隔时间,current_time为系统当前时间,store_time(i)为瓦片首次存储时间,access_count(i)为瓦片被访问次数.

2.2.3 数据大小价值

GDLF算法认为数据值能够影响缓存数据的个数,通常移除那些较大的数据以容纳更多的小数据,并认为较大的数据拥有较高的数据价值,较小的数据拥有较低的数据价值,考虑到栅格影像金字塔瓦片的数据从几kB到几百kB不等,GDLVF算法使用加权数据大小代替数据大小计算,并以此提出瓦片数据大小价值的计算公式：

(5)

式(5)中,Vsize(i)为瓦片数据大小价值,WDZ(i)为瓦片数据的加权数据大小.

(6)

式(6)中,WDZ(i)为瓦片的加权数据大小,size(i)为瓦片数据大小,benchmark_size为基准数据,基准数据为缓存瓦片数据的平均值.

2.3 用户行为选择参与的空间数据缓存置换算法

为研究用户在一定时间范围内对五层十五级瓦片数据中产品类型和生产时间的请求分布情况,本文采集了五层十五级瓦片系统的用户日志,日志中详细记录了用户名、请求瓦片名称、产品类型、瓦片生产时间,并抽取其中2份日志进行处理分析,结果如表2所示.以用户1为例,在日志收集时间范围内,共发送了15 485次瓦片请求,其中GF-1瓦片数据的请求数量占总请求数量的78%,生产日期为2015年7月的瓦片数据请求总数占所有瓦片请求总数的72%.由此可见，在日志搜集时间范围内,用户1的瓦片请求主要集中在某一特定产品类型和生产时间上.

由表2可知,在某种特定需求的驱动下,用户在一定的时间周期内会对某一产品类型或生产时间的瓦片数据进行持续性关注,对该产品类型或生产时间的瓦片产生了明显的倾向性(偏好)行为,即为用户倾向的瓦片数据,其被用户再次请求的概率要大于非倾向瓦片数据.

表2 用户请求分布表Table 2 User request distribution

GDLVF算法面向传统的金字塔模型设计产生,对传统的金字塔模型瓦片数据的缓存效率要高于以FIFO、LFU为代表的传统缓存置换算法,但是GDLVF算法在缓存五层十五级瓦片数据时存在以下局限.

(1)GDLVF算法考虑了瓦片的访问频率、空间位置、数据大小对瓦片数据缓存效率的影响,但是该算法在缓存五层十五级瓦片数据时,可能会出现在多个价值相等或相差不大的瓦片数据中同时存有用户倾向瓦片数据的情况.此种情况发生时,GDLVF算法会同等对待这些瓦片,导致用户倾向的瓦片数据可能会被置换删除.然而，根据上文分析,用户倾向的瓦片数据被再次访问的概率要大于非倾向瓦片数据,前者的实际数据价值大于后者,应优先置换删除用户非倾向瓦片数据.综上所述,GDLVF无法体现五层十五级用户行为选择对缓存效率的影响,不符合五层十五级瓦片对象访问的局部性规律.

(2)GDLVF算法将影响瓦片缓存效率的3个因子相乘得到瓦片的数据价值,从而使得3个因子对瓦片缓存效率的影响权重相等.

基于以上分析,用户行为选择参与的空间数据缓存置换算法认为：影响五层十五级瓦片缓存效率的主要因素包括瓦片的空间位置、访问时间频率、数据大小和用户行为选择(即用户对不同产品类型和生产时间的瓦片的选择倾向),且用户行为选择过程中产生的倾向瓦片的价值大于非倾向瓦片的价值.以此提出用户行为选择参与的五层十五级空间数据缓存置换算法UPBA：

V(i)=WDspa×Vspatial(i)+WDtm×Vtime(i)+

WDsz×Vsize(i)+WDpro×Vproduct(i)+

WDdt×Vdata_time(i),

(7)

式(7)中,V(i)代表瓦片的空间数据价值,Vspatial(i)、Vtime(i)、Vsize(i)分别代表瓦片的空间价值、时间价值、文件大小价值,三者的计算方法与式(2)、(3)、(5)相同,Vproduct(i)代表瓦片的产品类型价值,Vdata_time(i)代表瓦片的生产时间价值.WDspa、WDtm、WDsz、WDpro、WDdt表示各个影响因子对缓存效率影响的权重,且有WDspa+WDtm+WDsz+WDpro+WDdt=1.

(8)

式(8)中,Vproduct(i)代表瓦片的产品类型价值,count代表瓦片缓存总个数,count(p)代表该产品类型在缓存中的总个数.

(9)

式(9)中,Vdata_time(i)为瓦片的生产时间价值,count为瓦片缓存总个数,count(d)为同一生产时间的瓦片在缓存中的总个数.

3 实验过程与分析

实验采用日志驱动模式,首先通过大量实验确定每个因子的影响权重值,在确定每个因子影响权重后,着重考察UPBA算法在请求命中率、字节命中率、客户端流量消耗、服务器端处理请求个数4个方面的表现,并与FIFO、LRU、LFU、GDLVF算法做对比分析.实验数据最高分辨率100和250 m、生产时间为2014年11月、2015年1、3月的高分一号、高分二号、资源三号影像数据,瓦片大小均为1 000 pixel×1 000 pixel,以png格式存储,单个瓦片大小在30～3 072 kB,用日志记录实验结果,采用Android平板客户端,客户端与服务器端使用Http协议进行通信,客户端漫游路径根据随机方法生成.

本研究最大的难点在于确定式(7)中每个影响因子的权重值.目前常用的因子权重确定方法如统计平均法、层次分析法都有一定的主观性,为减少主观因素对结果的影响,本文采用实验方法确定权重因子值,大量实验表明，当WDspa=0.03,WDtm=0.03,WDsz=0.7,WDpro=0.12,WDdt=0.12时,缓存置换效率最高.

图2、图3分别为FIFO、LFU、LRU、GDLVF、UPBA 5种缓存置换算法的请求命中率和字节命中率,实验设定客户端最大缓存空间为500 MB,命中率取客户端发送200次请求的命中率的平均值,由图2可见,UPBA在所有情况下命中率都要大于其他4类缓存置换算法,并且优势明显,在相对缓存为20%时,UPBA算法相较其他缓存置换算法命中率提高超过100%.在相对缓存50%以内,FIFO、LFU、LRU、GDLVF对五层十五级瓦片数据的请求命中率和字节命中率基本相同,在相对缓存50%以上,LFU命中率要高于FIFO、LRU、GDLVF,但是几种算法相差不大.

图2 相对缓存与请求命中率的关系Fig.2 Relationship between the request hit rate and relative cache size

图3 相对缓存与字节命中率的关系Fig.3 Relationship between the byte hit rate and relative cache size

图4 相对缓存与客户端流量消耗关系Fig.4 Relationship between client traffic consumption and relative cache size

图4为在不同的相对缓存下,发送200次瓦片请求后,客户端的流量消耗.随着相对缓存的不断增加,客户端200次瓦片请求的流量消耗不断下降,在不使用缓存的情况下即相对缓存为0时,客户端发送200次瓦片请求需要消耗1 955.257 MB流量,流量消耗巨大,当相对缓存为100%即客户端可以缓存500 MB瓦片时,200次请求所消耗的流量为763.262 MB,仅为不开启缓存时的39%,节省流量近1 191.995 MB,效果显著.

图5 相对缓存与服务器端处理瓦片效率关系Fig.5 Relationship between tile handled efficiency and relative cache size

图5给出了服务器端处理瓦片效率与相对缓存的关系,在不使用UPBA算法的情况下,服务器平均每秒处理1.21个(1 000个请求需要826 s)瓦片请求,在使用UPBA算法后,等相对缓存为100%时服务器平均每秒处理0.465个瓦片,仅为不使用UPBA算法时的38.4%,降低了服务器端的负载,从而可以支持更高的用户并发数.

4 结论

分析了现有缓存置换算法FIFO、LFU、LRU、GDLVF的优缺点,考虑五层十五级瓦片数据多源、异构的特点,提出了用户行为选择参与的五层十五级瓦片数据的缓存置换算法UPBA.实验表明,相较于传统缓存置换算法和GDLVF算法，UPBA算法在请求命中率和字节命中率上的表现具有明显优势,同时降低了客户端的流量消耗以及服务器端的负载.UPBA算法目前使用文件缓存以提高瓦片数据加载显示的效率,下一步工作可尝试在内存中加入缓存，以进一步提高瓦片数据加载显示的效率.

[1] 段龙方.面向遥感数据的云数据库技术研究与应用[D].开封：河南大学,2014.

DUAN Longfang. The Research and Application of Cloud Database Technology for Remote Sensing Data[D]. Kaifeng: Henan University,2014.

[2] 王浩,俞占武,曾武,等.网络地理信息服务中的空间数据缓存算法研究[J].测绘学报,2009,38(4)：348-355.

WANG Hao, YU Zhanwu, ZENG Wu, et al. The research on the algorithm of spatial data cache in network geographic information service[J]. Acta Geodaetica et Cartographics Sinica,2009,38(4):348-355.

[3] 涂振发,孟令奎,张文,等.面向网络GIS的最小价值空间数据缓存替换算法研究[J].华中师范大学学报：自然科学版,2012,46(2)：230-234.

TU Zhengfa, MENG Lingkui, ZHANG Wen, et al. Research on the lowest-value cache replacement algorithm of geospatial data in Network GIS[J]. Journal of Huazhong Normal University: Natural Sciences,2012,46(2):230-234.

[4] 刘磊,熊小鹏.最小驻留价值缓存替换算法[J].计算机应用,2013,33(4)：1018-1022.

LIU Lei, XIONG Xiaopeng. Least cache value replacement algorithm[J]. Journal of Computer Applications,2013,33(4):1018-1022.

[5] 石磊,叶海琴,卫琳,等.Web缓存命中率与字节命中率关系[J].计算机工程,2007,44(13)：84-86.

SHI Lei, YE Haiqin, WEI Lin, et al. Relationship between hit ratio and byte hit ratio of web caching[J]. Computer Engineering,2007,44(13):84-86.

[6] 王小燕.一种高效的流媒体代理缓存替换算法[J].计算机工程,2009,35(14)：72-74.

WANG Xiaoyan. High effective stream media proxy cache replacement algorithm[J]. Computer Engineering,2009,35(14):72-74.

[7] 王栋,郑逢斌,赖包积,等.基于五层十五级遥感数据结构的并行算法研究[J].微计算机信息,2012,28(1)：166-167.

WANG Dong, ZHENG Fengbin, LAI Baoji, et al. A new parallel algorithm based on Five-layer Fifteen-level remote sensing data[J]. Microcomputer Information,2012,28(1):166-167.

[8] 王啸.基于新技术的海量遥感影像并行切分方法研究[D].开封：河南大学,2012.

WANG Xiao. Research of Remote Sensing Image Parallel Segmentation Method Based on the New Technology[D]. Kaifeng: Henan University,2012.

[9] PODLIPNIG S, BOSZORMENYI L. A survey of web cache replacement strategies[J]. ACM Computing Surveys,2003,35(4):374-398.

[10] 卢秉亮,梅义博,刘娜.位置相关查询中基于最小访问代价的缓存替换算法[J].计算机应用,2011,31(3):690-693.

LU Bingliang, MEI Yibo, LIU Na. Cache replacement method based on lowest access cost for location dependent query[J]. Journal of Computer Applications,2011,31(3):690-693.

Research on the user preference based cache replacement algorithm of the Five-layer Fifteen-level tile.

CHU Xin1,2, CAI Yangjun3, DU Zhenhong1,2, ZHANG Feng1,2, LIU Renyi2, WANG Liangang1,2, HE Jing1,2

(1.ZhejiangProvincialKeyLabofGIS,ZhejiangUniversity,Hangzhou310028,China; 2.DepartmentofGeographicInformationScience,ZhejiangUniversity,Hangzhou310027,China; 3.HangzhouHousingSecurityoffice,Hangzhou310006,China)

Traditional tile cache replacement algorithms such as FIFO, LRU, LFU, GDLVF focusing on tile’s access time, access frequency, size, and spatial location relationship, have limitations in practice of caching the Five-layer Fifteen-level tile, and are not suitable for the Five-layer Fifteen-level tile which is multi-source heterogeneous. In this paper, a tile cache replacement algorithm for Five-layer Fifteen-level named UPBA (User Preference Based Tile Cache Replacement Algorithm) was proposed, and its features including user preference, tile access time and frequency, tile size, and spatial location relationship were analyzed. And then, the enhanced tile replacement method of UPBA was presented. The image datasets of GF-1, GF-2 and ZY-3 with resolution of 100 and 250 m, and production time in November of 2014 and January, February, March of 2015 were used in log-driven simulations of UPBA. The result showed that the UPBA had improved the request hit rate and byte hit rate, meanwhile reduced the client traffic consumption and the server load compared to the traditional cache replacement algorithm.

Five-layer Fifteen-level; tile cache replacement; spatial data

2015-12-21.

国家自然科学基金资助项目(41471313，41101356，41101371，41171321)；国家科技基础性工作专项(2012FY112300);国家海洋公益性行业科研专项经费资助项目(2015418003，201305012)；浙江省科技攻关计划项目(2014C33G20,2013C33051)；中央高校基本科研业务费专项资金资助项目(2016XZZX004-02,2016QNA3015).

禇信(1991-)，ORCID:http://orcid.org/0000-0001-8883-8728,男，硕士研究生，主要从事移动GIS、GIS及其应用研究.

*通信作者，ORCID:http://orcid.org/0000-0001-9449-0415,E-mail:duzhenhong@zju.edu.cn.

10.3785/j.issn.1008-9497.2016.04.012

TN 433

1008-9497(2016)04-452-06

Journal of Zhejiang University(Science Edition), 2016,43(4):452-457