1. 主要内容

FAST 21‘ Learning Cache Replacement with CACHEUS

机器学习的发展为解决计算机系统中的经典问题开辟了一条新的途径，在存储领域，缓存替换策略就是问题之一。

本文使用机器学习算法改进缓存替换策略，主要内容如下：

1. 定义了四种工作负载原语类型，任何工作负载均有这四种原语组合而成。

• LFU-friendly：由访问序列定义，该序列由最近使用的最少的（LRU）缓存算法处理最优。
• LRU-friendly：由访问序列定义，该序列由最不经常使用（LFU）缓存算法处理最优。
• scan：由访问序列定义，每个项只被访问一次。
• churn：定义为对存储项子集的重复访问，每个项被访问的概率相等。

2. 改进了LeCaR，提出CACHEUS。
   • LFU→CR-LFU，LRU→SR-LRU
   • 采用动态的学习速率

2. 研究动机

2.1 缓存替换策略存在的问题

现有的缓存替换策略存在以下两个问题：

1. 不同的工作负载、乃至同一个工作负载在不同的时间段会表现出不同的访存特性，对于特定工作负载缓存替换策略不一定适合另一些。
2. 缓存块的大小会影响缓存替换策略的效果。

★ How TO Do?

利用机器学习算法决定使用哪一种缓存替换策略

2.2 缓存替换策略的分类

2.3 别人是如何做的：LeCaR

2.3.1 特性

• 使用强化学习和遗憾最小化来控制对**LRU** 和 LFU 的动态使用
• 通过历史预测信息更新 LRU 和 LFU 的权重
• 在 small cache size 上的表现胜过最先进的技术

2.3.2 不足

• 学习速率是手动输入的，不同的应用适合不同的学习速率，而LeCaR通过实验选择了固定的学习速率：0.45

• 不能处理 scan 型负载

3. CACHEUS的设计

一句话：对LeCaR进行了改进

3.1 改进1：采用自适应的机器学习速率，η表示学习速率，机器学习模型如下：

$$
W_t = W_{t-1}e^{ηγ}
$$

对于每一轮迭代，采取如下操作：

• 若学习速率改变
  • 性能改变
    • 变优，强化变化趋势
    • 变差，反转变化趋势
• 若学习速率未改变
  • 性能改变
    • 变优，不更新
    • 变差，随机条约
• 如果学习速率不变，并且连续10个窗口大小性能持续下降或变为零，将学习速率重置为初始值

3.2 改进2：将LeCaR中的 LRU 替换为 SR-LRU，将LeCaR中的 LFU 替换为 CR-LFU

• 通过历史预测信息更新 LRU 和 LFU 的权重，控制对**SR-LRU** 和 CR-LFU 的动态使用

• SR-LRU

  • LRU Problem：scan型负载会替换掉cache中被访问多次的page

  • 它将缓存分为两部分：一部分仅包含具有多个访问权限的项（R），另一部分用于单访问项以及具有多个访问权限的旧项（SR）。SR分区允许SR-LRU具有抗扫描性；一个用于容纳新项目的分区，以便它们不会影响R中的重要项目。SR-LRU仅从SR分区逐出-当缓存已满时，它在缓存未命中时逐出SR的LRU项目。R中较旧的项被降级为SR，以便只保留在R中重用的重要项。此外，SR-LRU维护的历史列表的大小与包含最近逐出的项的缓存的大小相同。

  • 当缓存遗漏时，x不在历史列表中，x会被插入到SR的MRU位置，如果缓存满了，SR的LRU项会被驱逐到HLU。如果缓存满了，SR的LRU项会被驱逐到H，如果H满了，算法会删除H的LRU项以腾出空间。缓存遗漏时，x在H中，x被移到R的MRU位置；缓存命中时，x在SR中，x被移到R的MRU位置；缓存命中时，x在R中，x被移到R的MRU位置。

• CR-LFU

  • LFU Problem：如果要访问的项目数大于缓存的大小，则LRU风格的算法将导致缓存内容的搅动，从而重复地将项目插入缓存并从缓存中逐出
  • 抗搅扰LFU（CR-LFU）修改了纯LFU中的替换机制，当多个缓存项的访问频率最低时，选择MRU（Most Recently Used）项来打破束缚。通过选择MRU项，CR-LFU有效地将频率最低的项目子集 “锁定 “到缓存中，使 缓存算法产生命中。

4. 实验结果