Research on Strong Cache Consistency Under Generic Cache Replacement Strategy

doi:10.19678/j.issn.1000-3428.0063848

Abstract

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

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

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

CLC Number:

TP393

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.

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0063848

http://www.ecice06.com/EN/Y2022/V48/I12/180

Figures/Tables 9

References

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

Please choose a citation manager

Content to export