作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

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

• 移动互联与通信技术 • 上一篇    下一篇

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

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

  1. 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 Tao1, ZHENG Quan1,2, XU Zhenghuan1,3, SHI Qianbao2, PENG Siwei1   

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

摘要: 建立准确的缓存分析模型有助于更好地预测缓存行为,对于网络性能分析与规划具有重要作用。现有面向缓存强一致性研究的分析模型普遍基于最近最少使用(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

中图分类号: