title: Efficient cache resource aggregation using adaptive multi-level exclusive caching policiesdate: 2018-10-23 12:10:36
tags: 缓存替换策略

使用自适应的多级独占缓存策略高效的缓存资源聚合

1.存在的问题

到目前为止部署的多级缓存策略通常在每个级别使用独立的缓存替换算法，这有两个主要的缺点：

  1. 底层缓存中弱化的位置。缓存是基于数据的时间位置原则。只有第一级缓存可以看到原始的访问模式，低层缓存只能在更高级别的缓存中看到遗漏。因此，应用程序的访问请求，如低级缓存所看到的，是由更高级别的缓存过滤的。其结果是传统的单级缓存算法管理。每个缓存级别是独立的，不能有效地管理多级缓存层次结构中的原始位置。
  2. 数据冗余。在级别独立的缓存中，数据可以被多个cache层缓存。这导致了多层缓存层次结构中的聚合缓存资源的实际可用度变得更小，特别是当每个级别都有类似的缓存大小时。存储在低级缓存中的数据块的很大比例将不会被访问。例如，在一个具有第一层DRAM（128 GB）的多级缓存中，第二层是高级pci-e SSD（500 GB），第三层数据SSD（1 TB）。
  3. 访问频率带来的差异。其使得原始的LRU算法位于混合存储系统中不再适用。

2.相关工作

单级缓存替换策略：

LRU-K[7]、2Q[8]、LRFU[9]、LIRS[10]、ARC[11]、Sopa[14]

LIRS：使用了基于重用距离的算法，而保存幽灵缓存的成本很高。

ARC：利用自适应技术，在考虑很少重用距离度量的情况下，用两个动态列表调整频繁访问的区块。

二级缓存替换策略：

MultiQueue：合理的遵循了三准则。

Minimal Lifetime:对于一个给定的负载，缓存中的热数据块应该保持最少minDist时间；

Frequency-based priority:数据块的优先级应该基于它们的访问频率；

Temporal frequency:过去访问频繁但现在很少被访问的数据块应该被替换掉；

注:变量minDist是对多种实际环境下的负载进行统计后得出的结论，它描述进入二级缓存的数据块在缓存中应该常驻的最小时间量。

多级缓存替换策略：

基于迁移的缓存替换策略[17]：为了减少网络资源的使用而设计的。

基于迁移的缓存替换策略使用客户端内容跟踪（CCT）表来保存客户端的（高水平缓存）驱逐信息，并定期将信息发送到较低的缓存，并将被逐出的区块重新加载到内存缓存中。这种基于驱逐的策略会导致额外的输入/输出操作，因此可能会增加平均延迟时间。

ULC[18]：统一的、层次感知的缓存替换策略算法。

通过发送检索和降级操作，多层缓存由最高缓存的客户端控制。客户端负责保存所有底层缓存的元数据，但这可能增加客户端的开销，并导致客户实际实现的复杂性。

Karma[19]：一种基于应用程序的多层缓存层次结构的管理策略。

利用应用提示并引入边际增益来实现精确的分配和替换策略。因此，该政策是特定于应用程序的，不适合通用的应用程序场景。

独占缓存替换策略：

PROMOTE[20]：使用一种概率过滤技术，确定哪个块应当被升级到更高级的缓存。需要记录缓存块时间戳，在缓存级别之间定期发送adaptHint消息。

3.设计动机

在算法中使用的显式频率信息通常会导致更高的时间复杂度。

块的重用距离比最近访问过这一判别方式更有效。

4.详细介绍算法

自适应的多级独立缓存策略由两个主要部分组成：

  1. 基于重用距离的自适应替换缓存算法（ReDARC）。
  2. 自适应的单向概率推送算法（ALACA）。

ReDARC

ReDARC根据块重用距离位置测量动态地将块划分为两组：小重用距离（SRD）和大重用距离（LRD）。

ALACA

ALACA使用单向推送操作，只允许较低的缓存将块推送到更高的缓存，并实现多级独占缓存属性。ALACA可以根据在线缓存状态动态调整不同缓存级别中的块的位置。

重用距离：

最近的重用距离是在给定区块的最后一个和倒数第二个（倒数第二个）引用之间访问的其他不同块的数量

例如，有一系列被访问的块[a，b，c，d，b，a]，块 b最近的重用距离是2，block b的近距离是1

ReDARC的数据结构组成：

  1. 类似于LRU-like的堆栈S
  2. 一个驱逐列表EL
  3. 一个列表Q

EL有两种类型的区块：LRD常驻块和LRD非常驻块。Q中只保留LRD的常驻块。ReDARC维护一个虚拟缓存，它的大小等于实际缓存大小。虚拟缓存中的虚拟块只在内存中缓存了它们的元数据。S和EL都保存有虚拟块，它们是LRD非常驻块。S和EL的总数等于实际缓存大小的两倍。

CACHE_使用自适应的多级独占缓存策略高效的缓存资源聚合 - 图1

(L, R)：LRD常驻块、(L, N)：LRD非常驻块、(S, R)：SRD常驻块

具体算法过程在paper中通过伪代码和讲解的方式给出，这里不做搬运。

5.实验评估性能

  1. 提出了一个单一的客户端多层缓存模型用于测试。

  2. 在多种模拟环境下搜集测试数据。

Zipf：类似于web应用程序中常见的访问模式，即经常访问几个街区，而其他的访问模式则要少得多。

Glimpse：用于搜索文本字符串的索引和查询系统。

TPC-R和TPC-H：对数据库文件进行随机存取。访问一些大型数据文件，其中一些文件具有多个并发访问模式。

Multi1：代码开发环境中的工作负载。

Financial1：大型金融机构的OLTP应用程序。

Websearch1：搜索引擎场景。

  1. 比较其他的缓存替换策略（同时介绍了这些缓存替换策略的特性）
    四个单级缓存替换策略：LRU、ARC、LIRS、ReDARC
    六个多级缓存替换策略：

    1. 三个多级独占缓存替换策略：Global LRU、Promote LRU 和 REAL（(该paper)
    2. 三个多级非独占缓存替换策略：Independent LRU、Independent ARC 和 LRU-MQ

  2. 图表对比：

    1. 单级缓存：单通过ReDARC实现的单级缓存，展现出比当前最优算法更好的效果。

    2. 多级缓存：

      1. 引入三个性能指标：

        aggregate hit ratio(聚合命中率)

inter cache traffic(内部缓存流量)

average response time(平均响应时间)<关键>

  1.   2.

在平均响应时间方面REAL更优。REAL利用了独占缓存的优势，使得内部缓存流量使用更少。

6.总结工作

缓存层次结构的性能可以通过新的存储介质进一步改进，比如SSD（固态驱动器）和PCM（相变内存）等等。作者相信REAL可以将这些存储介质作为额外的缓存级别进行管理。