通用缓存替换策略下的缓存强一致性研究

doi:10.19678/j.issn.1000-3428.0063848

计算机工程 ›› 2022, Vol. 48 ›› Issue (12): 180-188,195. doi: 10.19678/j.issn.1000-3428.0063848

通用缓存替换策略下的缓存强一致性研究

杨涛¹, 郑烇^1,2, 徐正欢^1,3, 施钱宝², 彭思伟¹

1. 中国科学技术大学自动化系未来网络实验室, 合肥 230026;
2. 合肥综合性国家科学中心人工智能研究院, 合肥 230088;
3. 中国科学技术大学先进技术研究院, 合肥 230031

收稿日期:2022-01-26 修回日期:2022-03-08 发布日期:2022-07-05
作者简介:杨涛（1997—），男，硕士研究生，主研方向为网络缓存与建模；郑烇，副教授、博士；徐正欢，硕士研究生；施钱宝，工程师、硕士；彭思伟，硕士研究生。
基金资助:
国家重大科技基础设施未来网络试验设施项目（2016-000052-73-01-000515）；安徽省重点研发计划“可重构高通量网络检测仪研究”（202004a05020078）。

Research on Strong Cache Consistency Under Generic Cache Replacement Strategy

YANG Tao¹, ZHENG Quan^1,2, XU Zhenghuan^1,3, SHI Qianbao², PENG Siwei¹

1. Laboratory of Future Networks, Department of Automation, University of Science and Technology of China, Hefei 230026, China;
2. Institute of Artificial Intelligence, Hefei Comprehensive National Science Center, Hefei 230088, China;
3. Institute of Advanced Technology, University of Science and Technology of China, Hefei 230031, China

Received:2022-01-26 Revised:2022-03-08 Published:2022-07-05

摘要/Abstract

摘要： 建立准确的缓存分析模型有助于更好地预测缓存行为，对于网络性能分析与规划具有重要作用。现有面向缓存强一致性研究的分析模型普遍基于最近最少使用（LRU）缓存替换策略，然而在实际环境中需要根据不同的应用场景和缓存节点能力采取LRU、q-LRU、先进先出等不同的缓存替换策略。为扩展缓存强一致性分析模型的适用范围，基于缓存建模的基本假设构建缓存强一致性通用分析模型，并给出被动查询、主动移除、主动更新3种缓存强一致性策略下缓存命中率和服务器负载的计算方法。利用模型计算结果绘制缓存参数变化曲线图找出使缓存性能达到最优的值，通过分析模型计算结果选出给定缓存参数时对应的最优缓存替换策略。实验结果表明，该模型在3种缓存强一致性策略下均具有较高的计算精确度，其中计算结果与仿真结果的最大误差和最小误差分别为6.92%和0.06%，适用于通过特征时间近似的缓存替换策略。

关键词: 缓存, 一致性, 替换策略, 特征时间, 缓存命中率, 服务器负载

Abstract: Establishing an accurate cache analysis model helps to predict the cache behavior better, which is vital for network performance analysis and planning.However, existing analysis models for cache consistency studies are based on the Least Recently Used(LRU) cache replacement strategy.However, different cache replacement strategies such as LRU, q-LRU, First In First Out(FIFO), etc, are required in real-world environments, depending on the application scenario and cache node capability.This study establishes an analysis model for generic cache strong consistency based on the basic assumptions of cache modeling to expand the scope of application of strong consistency strategies.Additionally, this study presents calculation methods for the cache hit ratio and server load under three cache strong consistency strategies(reactive invalidation, proactive invalidation with removing, and proactive invalidation with renewing). The model calculation results are used to plot the cache parameters to determine the parameters that optimize the cache performance and analyze to select the optimal cache replacement strategy for the given cache parameters.The experimental results show that the model has high computational accuracy under three cache strong consistency strategies.The maximum error between the computational and simulation results is 6.92%, and the minimum error is 0.06%.The proposed model is applicable to all cache replacement strategies that can be approximated based on the characteristic time.

Key words: cache, consistency, replacement strategy, characteristic time, cache hit ratio, server load

中图分类号:

TP393

杨涛, 郑烇, 徐正欢, 施钱宝, 彭思伟. 通用缓存替换策略下的缓存强一致性研究[J]. 计算机工程, 2022, 48(12): 180-188,195.

YANG Tao, ZHENG Quan, XU Zhenghuan, SHI Qianbao, PENG Siwei. Research on Strong Cache Consistency Under Generic Cache Replacement Strategy[J]. Computer Engineering, 2022, 48(12): 180-188,195.

https://www.ecice06.com/CN/Y2022/V48/I12/180

图/表 9

20230112183722

20230112183726

20230112183729

20230112183733

20230112183737

20230112183740

20230112183743

20230112183747

20230112183751

参考文献

[1] 张国强, 李杨, 林涛, 等.信息中心网络中的内置缓存技术研究[J].软件学报, 2014, 25(1):154-175. ZHANG G Q, LI Y, LIN T, et al.Survey of in-network caching techniques in information-centric networks[J].Journal of Software, 2014, 25(1):154-175.(in Chinese)
[2] 陈劼博, 郑烇, 王嵩.基于节点介数与边缘流行度的NDN缓存策略[J].计算机工程, 2019, 45(5):46-51. CHEN J B, ZHENG Q, WANG S.NDN caching strategy based on node median and edge popularity[J].Computer Engineering, 2019, 45(5):46-51.(in Chinese)
[3] 黄继海, 丁颖, 赵冰.基于PIT相似性的VANET混合协同缓存策略[J].计算机工程, 2019, 45(1):315-320. HUANG J H, DING Y, ZHAO B.VANET hybrid collaborative caching strategy based on PIT similarity[J].Computer Engineering, 2019, 45(1):315-320.(in Chinese)
[4] DIN I U, HASSAN S, KHAN M K, et al.Caching in information-centric networking:strategies, challenges, and future research directions[J].IEEE Communications Surveys & Tutorials, 2018, 20(2):1443-1474.
[5] HUANG S K, ZHU S, LEI K, et al.A novel strong cache consistency mechanism in ICN based on role division and lease model[C]//Proceedings of 2020 IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking(ISPA/BDCloud/SocialCom/SustainCom).Washington D.C., USA:IEEE Press, 2020:1241-1248.
[6] DETTI A, BRACCIALE L, LORETI P, et al.Modeling LRU cache with invalidation[J].Computer Networks, 2018, 134:55-65.
[7] ZHENG Q, YANG T, KAN Y Z, et al.On the analysis of cache invalidation with LRU replacement[J].IEEE Transactions on Parallel and Distributed Systems, 2022, 33(3):654-666.
[8] FRIEDLANDER E, AGGARWAL V.Generalization of LRU cache replacement policy with applications to video streaming[J].ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2019, 4(3):1-18.
[9] EINZIGER G, FRIEDMAN R, MANES B.TinyLFU:a highly efficient cache admission policy[C]//Proceedings of the 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing.New York, USA:ACM Press, 2017:1-31.
[10] GELENBE E.A unified approach to the evaluation of a class of replacement algorithms[M].Berlin, Germany:Springer, 1974.
[11] DAN A, TOWSLEY D.An approximate analysis of the LRU and FIFO buffer replacement schemes[C]//Proceedings of 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems.New York, USA:ACM Press, 1990:143-152.
[12] TSUKADA N, HIRADE R, MIYOSHI N.Fluid limit analysis of FIFO and RR caching for independent reference models[J].Performance Evaluation, 2012, 69(9):403-412.
[13] GOMAA H, MESSIER G G, WILLIAMSON C, et al.Estimating instantaneous cache hit ratio using Markov chain analysis[J].ACM Transactions on Networking, 2013, 21(5):1472-1483.
[14] CASALE G, GAST N.Performance analysis methods for list-based caches with non-uniform access[J].ACM Transactions on Networking, 2021, 29(2):651-664.
[15] CHE H, TUNG Y, WANG Z J.Hierarchical Web caching systems:modeling, design and experimental results[J].IEEE Journal on Selected Areas in Communications, 2002, 20(7):1305-1314.
[16] FRICKER C, ROBERT P, ROBERTS J.A versatile and accurate approximation for LRU cache performance[EB/OL].[2021-01-03].https://arxiv.org/abs/1202.3974.
[17] XIE T, HE T, MCDANIEL P, et al.Attack resilience of cache replacement policies[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2021:1-10.
[18] JIANG B, NAIN P, TOWSLEY D.On the convergence of the TTL approximation for an LRU cache under independent stationary request processes[J].ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2018, 3(4):1-31.
[19] AL-ABBASI A O, AGGARWAL V.TTLCache:taming latency in erasure-coded storage through TTL caching[J].IEEE Transactions on Network and Service Management, 2020, 17(3):1582-1596.
[20] CARRA D, NEGLIA G, MICHIARDI P.Elastic provisioning of cloud caches:a cost-aware TTL approach[J].ACM Transactions on Networking, 2020, 28(3):1283-1296.
[21] CARRA D, NEGLIA G, MICHIARDI P.TTL-based cloud caches[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2019:685-693.
[22] MARTINA V, GARETTO M, LEONARDI E.A unified approach to the performance analysis of caching systems[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2014:2040-2048.
[23] TANG X Y, CHI H C, CHANSON S T.Optimal replica placement under TTL-based consistency[J].IEEE Transactions on Parallel and Distributed Systems, 2007, 18(3):351-363.
[24] AMADEO M, RUGGERI G, CAMPOLO C, et al.Diversity-improved caching of popular transient contents in vehicular named data networking[J].Computer Networks, 2021, 184:107625.
[25] 赵国锋, 林欢, 段洁, 等.面向数据新鲜度的ICN-IoT缓存方案[J].计算机工程, 2020, 46(11):223-230. ZHAO G F, LIN H, DUAN J, et al.ICN-IoT caching scheme for data freshness[J].Computer Engineering, 2020, 46(11):223-230.(in Chinese)
[26] BRESLAU L, CAO P, FAN L, et al.Web caching and Zipf-like distributions:evidence and implications[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 1999:126-134.

选择文件类型/文献管理软件名称

选择包含的内容

通用缓存替换策略下的缓存强一致性研究

Research on Strong Cache Consistency Under Generic Cache Replacement Strategy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈姣, 沈艳. 面向缓存机制的移动边缘计算任务卸载研究[J]. 计算机工程, 2024, 50(7): 194-203.
[2]	周小华, 周园春, 孟珍, 王学志. 大规模开放遥感影像地图渲染与缓存优化[J]. 计算机工程, 2024, 50(7): 227-239.
[3]	胡傲然, 陈晓红. 基于多样性与一致性的单步多视图聚类[J]. 计算机工程, 2024, 50(5): 51-61.
[4]	范晓宇, 贾新春, 李彬, 谢云飞. 多率采样机制下多智能体动态事件触发二分一致性研究[J]. 计算机工程, 2024, 50(3): 114-121.
[5]	于立, 韩林, 罗有才, 商建东. 面向FT-M6678的对称矩阵特征值求解算法实现与优化[J]. 计算机工程, 2024, 50(2): 51-58.
[6]	王丽娟, 邢津萍, 尹明, 郝志峰, 蔡瑞初, 温雯. 基于一致性图的权重自适应多视角谱聚类算法[J]. 计算机工程, 2024, 50(2): 122-131.
[7]	洪犇, 钱旭升, 申明磊, 胡冀苏, 耿辰, 戴亚康, 周志勇. 基于深度学习的CT-MR图像联合配准分割方法[J]. 计算机工程, 2023, 49(9): 234-245.
[8]	石小容, 李爱萍, 牛保宁, 段利国, 赵菊敏. 兼顾个性化需求的云边协作两级内容缓存研究[J]. 计算机工程, 2023, 49(5): 223-230.
[9]	桑永宣, 魏江坡, 王博, 宋莹. 具有边缘缓存机制的混合启发式任务卸载算法[J]. 计算机工程, 2023, 49(4): 149-158.
[10]	罗少聪, 张旭东, 万乐, 谢林芳, 黎书玉. 结合图像特征迁移的光场深度估计方法[J]. 计算机工程, 2023, 49(4): 206-216.
[11]	方燕飞, 刘齐, 董恩铭, 李雁冰, 过锋, 王谛, 何王全, 漆锋滨. 面向E级超算系统的众核片上存储层次研究[J]. 计算机工程, 2023, 49(12): 10-24.
[12]	刘宇宸, 唐菀, 杨喜敏, 张艳. 引入区块链的SDN路由一致性检测[J]. 计算机工程, 2023, 49(11): 160-168.
[13]	隆腾, 杨莎莎, 王茜竹. 可变脉冲控制下的多智能体系统固定时间一致性研究[J]. 计算机工程, 2023, 49(1): 311-320.
[14]	雷洁, 饶文碧, 杨焱超, 熊盛武. 基于分类不确定性的伪标签目标检测算法[J]. 计算机工程, 2023, 49(1): 49-56.
[15]	杨周凡, 韩林, 李冰洋, 谢景明, 韩璞, 刘勇杰. 基于“嵩山”超级计算机系统的大规模管网仿真[J]. 计算机工程, 2022, 48(9): 155-161.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

通用缓存替换策略下的缓存强一致性研究

Research on Strong Cache Consistency Under Generic Cache Replacement Strategy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献

相关文章 15

编辑推荐

Metrics

本文评价