Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2022, Vol. 49 Issue (2): 210-218    DOI: 10.3785/j.issn.1008-9497.2022.02.010
地球科学     
基于时空老化模型的服务端瓦片缓存置换算法
汤求毅1,2,王超1,2,杜震洪1,2(),张丰1,2,刘仁义1,2
1.浙江大学 浙江省资源与环境信息系统重点实验室，浙江 杭州 310028
2.浙江大学 地理信息科学研究所，浙江 杭州 310027
Server-side cache replacement algorithm based on spatiotemporal aging model for tiles
Qiuyi TANG1,2,Chao WANG1,2,Zhenhong DU1,2(),Feng ZHANG1,2,Renyi LIU1,2
1.Zhejiang Provincial Key Lab of GIS，Zhejiang University，Hangzhou 310028，China
2.Department of Geographic Information Science，Zhejiang University，Hangzhou 310027，China
 全文: PDF(882 KB)   HTML( 6 )
摘要：

随着网络地理信息服务（network geographic information service，NGIS）向云服务演进，客户端瓦片缓存架构的应用局限性逐渐体现。为提升瓦片服务的性能，在老化算法的基础上，综合分析了瓦片访问长短期流行度和瓦片大小特征，设计了基于时空老化模型的服务端瓦片缓存置换算法（server-side cache replacement algorithm based on spatiotemporal aging model for tiles，SSAT），并利用谷歌全球底图瓦片和瓦片访问日志进行了仿真实验。结果表明，在不同缓存空间下，SSAT的缓存命中率均高于传统算法，缓存空间每增加1 MB，最多可以提高0.24%的请求命中率和0.23%的字节命中率；当缓存空间为500 MB时，SSAT能达到73%的请求命中率和76%的字节命中率，平均访问时长可缩短35%以上。SSAT能兼顾性能与资源消耗，具备高效性和扩展性。
关键词： 网络地理信息服务;  瓦片服务;  瓦片缓存置换算法;  老化算法;  时空老化模型    
Abstract:

As network geographic information service (NGIS) is developing towards cloud services, the client-side tiles cache architecture has already demonstrated its limitations in applications. To improve the efficiency of tile service, this paper designs a server-side cache replacement algorithm based on spatiotemporal aging model for tiles (SSAT). The SSAT algorithm is based on the aging algorithm and comprehensively analysis on the long-term and short-term popularity of tile access pattern as well as the characteristics of tile size. A series of Google global base map tiles and access logs of tiles are used for simulation experiment. The experimental results show that the SSAT algorithm outperforms traditional algorithms when using different cache sizes. With the increasing of cache size, the SSAT algorithm can increase the request hit rate by 0.24% and the byte hit rate by 0.23% for every additional 1 MB of cache. When the cache space is 500 MB, SSAT algorithm can achieve 73% cache hit rate and 76% byte hit rate, and reduce the average access time by more than 35%. In summary, the SSAT algorithm considers both performance and resource consumption, and has high efficiency and scalability.
Key words: NGIS    tile service    tile cache replacement algorithm    aging algorithm    spatiotemporal aging model
收稿日期: 2021-01-21 出版日期: 2022-03-22
CLC:  P 208  
基金资助: 国家自然科学基金资助项目(41922043);国家重点研发计划项目(2018YFB0505000)
通讯作者: 杜震洪     E-mail: duzhenhong@zju.edu.cn
作者简介: 汤求毅（1996—），ORCID：https：//orcid.org/0000-0002-4674-4975，男，硕士研究生，主要从事海量遥感影像管理研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
汤求毅
王超
杜震洪
张丰
刘仁义

引用本文:

汤求毅,王超,杜震洪,张丰,刘仁义. 基于时空老化模型的服务端瓦片缓存置换算法[J]. 浙江大学学报（理学版）, 2022, 49(2): 210-218.

Qiuyi TANG,Chao WANG,Zhenhong DU,Feng ZHANG,Renyi LIU. Server-side cache replacement algorithm based on spatiotemporal aging model for tiles. Journal of Zhejiang University (Science Edition), 2022, 49(2): 210-218.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2022.02.010    或    https://www.zjujournals.com/sci/CN/Y2022/V49/I2/210

图1  老化算法工作流程
图2  瓦片水平邻域和瓦片垂直邻域
图3  服务端瓦片缓存索引结构
图4  瓦片时钟周期和瓦片空间访问热度权重值对SSAT缓存命中率的影响（a） 瓦片时钟周期 （b）瓦片空间访问热度权重
图5  在3种条件下SSAT的请求命中率和字节命中率随缓存空间的变化（a） 请求命中率 （b） 字节命中率
图6  4种算法的缓存命中率及命中增长率随缓存空间的变化
图7  4种算法的平均访问时长和平均访问时长节省率随缓存空间的变化
图8  4种算法的CPU占用率和累计占用率
1 BREUNIG M， BRADLEY P E， JAHN M， et al. Geospatial data management research： Progress and future directions［J］. ISPRS International Journal of Geo-Information， 2020， 9（2）： 95-115. DOI：10.3390/ijgi9020095
doi: 10.3390/ijgi9020095
2 GOMES V C F， QUEIROZ G R， FERREIRA K R. An overview of platforms for big earth observation data management and analysis［J］. Remote Sensing， 2020， 12（8）： 1253. DOI：10.3390/rs12081253
doi: 10.3390/rs12081253
3 GUO H D. Big earth data： A new frontier in earth and information sciences［J］. Big Earth Data， 2017， 1（1/2）： 4-20. DOI：10.1080/20964471.2017.1403062
doi: 10.1080/20964471.2017.1403062
4 陆晔， 张伟， 李飞， 等. 一种基于主题时空价值的服务器端瓦片缓存算法［J］. 浙江大学学报（理学版）， 2020， 47（1）： 12-19. DOI：10.3785/j.issn.1008-9497.2020.01.002
LU Y， ZHANG W， LI F， et al. A server-side tile caching algorithm based on theme temporal and spatial value［J］. Journal of Zhejiang University（Science Edition）， 2020， 47（1）： 12-19. DOI：10.3785/j.issn.1008-9497.2020.01.002
doi: 10.3785/j.issn.1008-9497.2020.01.002
5 GUO D D， ZOU Y J， WANG S. An Effective tile caching mechanism of UAV remote sensing map based on hilbert coding index［C］// 2019 IEEE 11th International Conference on Communication Software and Networks （ICCSN）. Piscataway： IEEE， 2019： 535-541. DOI：10.1109/ICCSN.2019. 8905357
doi: 10.1109/ICCSN.2019. 8905357
6 周扬发. Web代理服务器的缓存技术研究［D］. 北京： 北京邮电大学， 2014.
ZHOU Y F. Research on Caching Technology of Web Proxy Server［D］. Beijing： Beijing University of Posts and Telecommunications， 2014.
7 LI R， FAN J P， WANG X X， et al. Distributed cache replacement method for geospatial data using spatiotemporal locality-based sequence［J］. Geospatial Information Science， 2015， 18（4）： 171-182. DOI：10.1080/10095020.2015.1123427
doi: 10.1080/10095020.2015.1123427
8 LI R， FENG W， WU H Y， et al. A replication strategy for a distributed high-speed caching system based on spatiotemporal access patterns of geospatial data［J］. Computers， Environment and Urban Systems， 2017， 61（B）： 163-171. DOI：10.1016/j.compenvurbsys.2014.02.009
doi: 10.1016/j.compenvurbsys.2014.02.009
9 CHENG Y Y， ZHOU K F， WANG J L， et al. Big earth observation data integration in remote sensing based on a distributed spatial framework［J］. Remote Sensing， 2020， 12（6）： 972-988. DOI：10.3390/rs12060972
doi: 10.3390/rs12060972
10 KANG Y K， KIM K C， KIM Y S. Probability-based tile pre-fetching and cache replacement algorithms for web geographical information systems［C］// East European Conference on Advances in Databases and Information Systems. Berlin： Springer， 2001： 127-140. DOI：10.1007/3-540-44803-9_11
doi: 10.1007/3-540-44803-9_11
11 王浩， 喻占武， 曾武， 等. 网络地理信息服务中的空间数据缓存算法研究［J］. 测绘学报， 2009， 38（4）： 348-355. DOI：10.3321/j.issn：1001-1595.2009.04.011
WANG H， YU Z W， ZENG W， et al. The research on the algorithm of spatial data cache in network geographic information service［J］. Acta Geodaetica et Cartographica Sinica， 2009， 38（4）： 348-355. DOI：10.3321/j.issn：1001-1595.2009.04.011
doi: 10.3321/j.issn：1001-1595.2009.04.011
12 王浩， 潘少明， 彭敏， 等. 数字地球中影像数据的Zipf-like访问分布及应用分析［J］. 武汉大学学报（信息科学版）， 2010， 35（3）： 356-359. doi:10.3724/SP.J.1084.2010.00199
WANG H， PAN S M， PENG M， et al. Zipf-like distribution and its application to image data tile request in digital earth［J］. Geomatics and Information Science of Wuhan University， 2010， 35（3）： 356-359. doi:10.3724/SP.J.1084.2010.00199
doi: 10.3724/SP.J.1084.2010.00199
13 LI R， WANG X X， WANG J J， et al. Simulation and Analysis of Cluster-Based Caching Replacement Based on Temporal and Spatial Locality of Tiles Access［M］. Boston： Springer， 2013： 169-181. DOI：10.1007/978-1-4614-8745-6_13
doi: 10.1007/978-1-4614-8745-6_13
14 王浩， 喻占武， 曾武， 等. 基于瓦片寿命和访问热度的海量空间数据缓存置换策略［J］. 武汉大学学报（信息科学版）， 2009， 34（6）： 667-670. doi:10.1109/itcs.2009.114
WANG H， YU Z W， ZENG W， et al. Massive spatial data cache replacement policy based on tile lifetime and popularity［J］. Geomatics and Information Science of Wuhan University， 2009， 34（6）： 667-670. doi:10.1109/itcs.2009.114
doi: 10.1109/itcs.2009.114
15 刘佳星， 陈飞翔， 陈星涵. 一种基于地理单元热度的瓦片缓存策略［J］. 计算机工程与应用， 2017， 53（5）： 90-96. DOI：10.3778/j.issn.1002-331.1608-0530
LIU J X， CHEN F X， CHEN X H. Tile cache strategy based on geographic unit heat［J］. Computer Engineering and Applications， 2017， 53（5）： 90-96. DOI：10.3778/j.issn.1002-8331.1608-0530
doi: 10.3778/j.issn.1002-8331.1608-0530
16 CAO P， IRANI S. Cost-aware WWW proxy caching algorithms［C］// Proceedings of the USENIX Symposium on Internet Technologies and Systems. Monterey， CA： USENIX， 1997： 193-206.
17 LEE D H， KIM J S， KIM S D， et al. Adaptation of a neighbor selection markov chain for prefetching tiled web GIS data［C］// International Conference on Advances in Information Systems. Heidelberg： Springer， 2002： 213-222. doi:10.1007/3-540-36077-8_21
doi: 10.1007/3-540-36077-8_21
18 涂振发， 孟令奎， 张文， 等. 面向网络GIS的最小价值空间数据缓存替换算法研究［J］. 华中师范大学学报（自然科学版）， 2012， 46（2）： 230-234. DOI：10. 3969/j.issn.1000-1190.2012.02.023
TU Z F， MENG L K， ZHANG W， et al. Research on the lowest-value cache replacement algorithm of geospatial data in network GIS［J］. Journal of Central China Normal University （Natural Sciences）， 2012， 46（2）： 230-234. DOI：10.3969/j.issn.1000-1190.2012.02.023
doi: 10.3969/j.issn.1000-1190.2012.02.023
19 ULUAT M F， ??LER V. Ensemble adaptive tile prefetching using fuzzy logic［J］. International Journal of Geographical Information Science， 2016， 30（6）： 1117-1136. DOI：10.1080/13658816. 2015.1108420
doi: 10.1080/13658816. 2015.1108420
20 LI R， FAN J P， JIANG J， et al. Spatiotemporal correlation in WebGIS group-user intensive access patterns［J］. International Journal of Geographical Information Science， 2017， 31（1）： 36-55. DOI：10. 1080/13658816.2016.1170133
doi: 10. 1080/13658816.2016.1170133
21 SAXENA A. A study of page replacement algorithms［J］. International Journal of Engineering Research and General Science， 2014， 2（4）： 385-388.
22 刘敏， 房至一， 王红斌， 等. 基于老化算法的分布式文件缓存算法［J］. 吉林大学学报（理学版）， 2011， 49（5）： 895-900. doi:10.1007/978-3-642-26001-8_69
LIU M， FANG Z Y， WANG H B， et al. Distributed file caching algorithm based on aging algorithm［J］. Journal of Jilin University （Science Edition）， 2011， 49（5）： 895-900. doi:10.1007/978-3-642-26001-8_69
doi: 10.1007/978-3-642-26001-8_69
23 FAROOQUI M Z， SHOAIB M， KHAN M Z. A comprehensive survey of page replacement algorithms［J］. International Journal of Advanced Research in Computer Engineering & Technology， 2014， 3（1）： 52-58. doi:10.7763/ijet.2011.v3.218
doi: 10.7763/ijet.2011.v3.218
[1] 李悦艺,张丰,杜震洪,刘仁义. 基于LSM-OCTree的时空流分布式调度和存储方案[J]. 浙江大学学报（理学版）, 2023, 50(2): 204-212.
[2] 王昱文,杜震洪,戴震,刘仁义,张丰. 基于复合神经网络的多元水质指标预测模型[J]. 浙江大学学报（理学版）, 2022, 49(3): 354-362.