[FAST-21] Learning Cache Replacement With CacheUS

传统的缓存替换策略有 LRU，LFU 等，不过这些策略在具有某些特征的负载下可能不会有很好的表现。因此也衍生出了一些能够自适应地调节缓存策略的算法，比如 ARC, LIRS。

这篇文章出自 Florida International University，他们实验室在 18 年提出了一个名叫 LeCaR 的策略，用强化学习来自适应地调整缓存中使用 LRU, LFU 策略的数据大小。我大概略读了一下这篇前作，只有寥寥几页，其实他们的策略本质上和 ARC 差不太多，不过加了强化学习之后能够对策略调整的速度做一个控制，强化学习中一些随机化的过程也可能使 LeCaR 在某些数据集上有更好的表现。而本作提出的 CacheUS 策略则在前作基础上做了大幅度的改进，并被 2021 年的 FAST 接收。

背景知识

在介绍 CacheUS 算法前，首先要了解一些关于缓存的背景知识。

过去，大家一般都是针对某些特定的负载设计缓存算法。本文认为负载可以主要分为四类：

LRU-Friendly: 总之就是非常适合 LRU 的负载
LFU-Friendluy: 同上，非常适合 LFU 的负载
Scan: 顺序访问存储数据中的一个子集，子集中的每个元素只访问一次
Churn: 同样是不断访问存储数据中的一个子集，不过每次随机访问子集中的任一数据。

本文使用的数据集、访问记录，大都同时包含了这四种负载类型。但本文想对标的几种 Cache 算法(LeCaR, LIRS, DLIRS, ARC)，只能比较好地处理一到三种负载类型。下图说明了各个算法在不同负载上的表现，越绿说明对应的算法在这一负载上表现越好。

LeCaR: 回顾

文章接下来用了很大篇幅分析了一下同样采用了强化学习的 LeCaR 算法。

LeCaR 用类似 ARC 的方法同时使用了 LRU, LFU 两种策略，简要来说本文认为它存在两个比较大的问题。第一点是它不能处理好 Scan 和 Churn；第二点是 LeCaR 要用户手动配好强化学习里的 learning rate 和 discount rate，对于同一个数据集而言，不同的 learning rate 和 discount rate 表现差异可能会非常大，也很难指望用户一下子就蒙到效果非常好的参数。

CacheUS 要做的事情就是改进参数的设置方式，尽量不让用户自己手动调参。还有想办法让自适应缓存算法也能处理 Scan 和 Churn 类型的负载。

改进参数

在对 LeCaR 的各种实验中发现 discount rate 的变化对实验结果影响不大，因此 CacheUS 去掉了这一参数，另外考虑使用一些自适应的方法动态调整 learning rate。那么，不同数据集下，不同的 learning rate 都有何表现呢？本文做了一点实验，如下图所示

learning_rates

嗯……似乎 learning rate 的变化和 hit rates 之间是没什么规律的，起起伏伏，变化很大。如果硬要说有规律的话，就是特别小的 learning rate 一般不会有很好的表现。因此初始化 learning rate 时，随机从 [10^-3, 1] 中找一个值。

初始化完成后，CacheUS 以每 i 次查询为窗口更新 learning rate。如果上一个窗口由于改变 learning rate 而出现了命中率的上升（或下降），那么要对应地再增大（或减小）learning rate。如果命中率长期没什么变化，可能是当前的 learning rate 陷入了局部最优，那么就要对 learning rate 重新进行一次初始化。

CacheUS 其余的部分和 LeCaR 大同小异。他们学习两个 expert (LRU, LFU) 的缓存策略，通过一个 history records 记录两个 expert 逐出的缓存，进而采用强化学习的方法确定要更多地把缓存空间分配给哪个 expert。如果一个 expert 表现得差，用一些随机化的方法减小使用它的权重；反之增加权重。

Scan Resistance

接下来讨论的就是设计新的 expert 应用到 CacheUS 中，以让 CacheUS 可以适应 Scan 和 Churn 负载。

针对 Scan 类型负载，CacheUS 设计了一个新的 expert: SR-LRU。一般来说，MRU 在 Scan 上有更好的表现。SR-LRU 和 ARC 的核心思路也是大差不差，自适应地调整 MRU, LRU 两个缓存替换算法占的空间。

这个算法中总共有三个队列，其中包括两个缓存队列SR和R，和一个历史队列H。SR对应A1，R对应Am，这里出现了一个 demotion 操作，就是 R 的 LRU 元素进入 SR 的 MRU 元素的操作，SR-LRU 只会从 SR 中淘汰元素，因此 R 中的元素需要通过 demotion 来间接地被替换。

当requested page q在R中被命中，直接提到MRU位置；当在SR中被命中时，会进入R，如果这个元素还是从R中demote下来的，那么SR的理想大小会被减少；

miss 时，如果在H中被命中，这个元素会进入SR的MRU位置，但是如果这个元素有一个“new”的记号，我们就会增加SR的理想大小；如果没有在任何一个队列中命中，这个元素会进入SR的MRU位置，并且会被添加一个“new”标记，这个“new”标记不管当页在SR还是H中都一直保持，直到被命中或者被移除；如果缓存已满，那么就将SR的LRU元素移出缓存，并记录在H的MRU位置，（如果H满那当然也是移除其LRU位置）如果SR的大小小于理想大小，那么就从R中demote一些页，使SR回到理想大小，这些页都会带有“demoted”标记，以便于和从未被命中而处于SR中的页作区分。但如果SR超过了理想大小，我们并不会在这里进行什么调节。

实际表现中，SR-LRU 在从 Scan 切换到 Churn 时表现得会比 ARC 更好。

Churn Resistance

Churn 类型的处理比较简单，文章也只用了两小段话描述了一下，其实就是当有多个页的访问频率同样低的时候，我们优先淘汰MRU的页。

总结

这篇文章我比较关注的是它怎么应用强化学习去处理缓存策略的。系统领域应用的其实都是些比较“弱”的机器学习方法，本文也不例外。比较大的亮点还是在怎么做动态调参这件事上。