Page 343 - 《软件学报》2021年第9期

刘嘉琦 等:一种基于两级缓存的协同缓存机制 2967

式、替换策略、热度筛选方法及路由策略,是一种可应用于实际部署环境的缓存机制.

2 CSTC 运行机制
CSTC 通过引入两级缓存机制,实现了不同热度内容的分级缓存,一方面降低了缓存的冗余;一方面,利用内
容热度对缓存位置进行了合理的规划,使得缓存分布更接近理想分布状态.每个节点的缓存空间被分为
RawCache 和 HashCache 两部分:针对 RawCache,各节点基于本地热度感知进行独立缓存决策;针对 HashCache,
则通过哈希机制构成域内多节点间协作,实现了域内热度的分布感知及决策,为不同层次的热度内容提供不同
的缓存策略.通过所设计的热度筛选机制与路由策略,达到了内容热度筛选的目的,优化了缓存位置,降低了缓
存的冗余,增大了域内稳定缓存内容的数量.本节将阐述 CSTC 的详细过程.

2.1 CSTC基本框架
研究表明:网络中内容的热度服从 Zipf 分布 [10] ,不同内容的请求频率相差巨大,多数请求仅仅集中在少数热
门内容上.Li 等人 [24] 通过构建模型,分析如何配置单个路由节点的缓存空间,以达到整体网络性能与成本的最
优;Chang 等人 [25] 在 Li 等人研究的基础上提出一种确定节点缓存空间比例以及如何放置内容的方法,证明将缓
存空间基于内容热度分块——一部分采用 On-path 来缓存最热门的内容,另一部分参与全局协作,缓存次热门
内容,可以在保持缓存命中率的同时,有效降低请求的平均时延.
然而,上述方法仅仅是对最优缓存策略的数学量化与理论建模.缓存策略也是基于所有内容热度已知的先
决条件下完成的,同时,各节点的缓存依赖于集中式的决策控制,并不适用于实际环境的部署要求.CSTC 基于以
下考虑.
1) 最热门内容应在网络边缘适度冗余,减少用户请求跳数.Fayazbakhsh 等人 [26] 通过大量仿真实验证明:
仅仅简单地在网络边缘部署足够大的缓存,就能达到可观的网络性能提升.这正是热门内容在网络边
缘冗余带来的效果.让用户的多数请求在网络边缘节点得到满足,不仅减少了用户的请求时间,也极
大降低了网络负载;
2) 次热门内容应稳定缓存,尽量避免非热门内容占据缓存空间.最热门内容只占网络中内容的极少部
分,网络中存在着大量的次热门和非热门内容.为有效提高请求命中率,我们希望可以选定合理的存
储位置,通过请求重定向汇聚次热门内容的热度,使得次热门内容能在指定节点稳定缓存,进而提高
次热门内容缓存多样性,降低非热门内容对缓存空间的占用;
3) 节点间较小的信息交换开销与线性算法复杂度.现有的各种全局节点协作的内容热度感知方案 [8,27]
需要不同节点间频繁的信息交流与计算开销,同时会给集中控制节点带来较大的流量负担与计算压
力,这会给以线性速度为要求的高速信息中心网络带来新的性能瓶颈.
CSTC 中,节点缓存空间被分为 RawCache 和 HashCache 两部分,如图 1 所示.RawCache 上采用 On-path 缓
存策略,对途经的内容进行缓存,同时对缓存下来的内容进行基于单节点热度统计.通过这种方式,最热门内容
被拉取到网络边缘稳定缓存,而次热门与非热门内容则会在 RawCache 中频繁替换,难以稳定缓存.当 RawCache
中缓存内容发生替换时,若为非热门内容,则直接替换出缓存空间,否则根据哈希映射找到其匹配节点,并将其
发往对应节点的 HashCache.不同节点的 HashCache 构成一个协作整体,一方面,每块 HashCache 通过哈希机制
缓存不同的内容,有效避免了缓存冗余;另一方面,域内被替换出的不同内容会被汇聚到不同节点,内容会依照
其全局热度在该节点展开缓存空间的二次竞争.通过这种两级缓存机制,最热门的内容会留在 RawCache 中,次
热门内容会稳定缓存在 HashCache 中.不同节点的 HashCache 被分配以不同的缓存任务,这些节点的 HashCache
通过哈希机制构成一个协作整体.
节点上相互关联两部分的缓存可以采用 LRU 或 LFU 缓存替换策略.初始阶段,两部分缓存都为空,当内容
经过节点时,节点的 RawCache 部分执行 On-path 缓存策略对内容进行存储.当 RawCache 剩余缓存空间大小为
0 时,若仍需缓存新内容,则会通过缓存替换决策替换掉原有的缓存内容.这时,节点先依照所统计的内容命中次
数判断将被替换出的内容的热度:若为热门内容,则查找哈希映射表,将内容发往对应节点的 HashCache,再执行