[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的页。

总结

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

标签:

更新时间: