Introduction
内容分发网络承担了绝大部分的网络流量；
字节缺失率是内容分发网络的关键性能指标；
CDN 场景下，缓存策略对于实现低缺失率起着关键作用，但是，CDN 场景下的缓存策略大多使用启发式算法，随着工作负载的变化，缓存策略的效果可能会很差。最关键的是，作者在很多 trace 中观察到：SOTA缓存替换算法和 MIN 算法之间存在巨大差距；
作者提出 LRB 算法，使用机器学习近似 MIN 算法。但是，如果完全模仿 MIN 算法驱逐前向重用距离最大的对象，那么计算成本就太大了。退而求其次，只要某个对象的前向重用距离超过某一阈值，它就可以被驱逐。
阈值—— Belady 边界，定义为从开始到现在，MIN 算法驱逐对象中前向重用距离最小的值。Relaxed Belady 带来了两个好处：
- 允许系统在小的采样集中进行预测，比如大小为64，减少计算开销；
- 允许系统实时获取训练数据（只需在后面实时跟踪驱逐对象的重用距离是否大于阈值，而无需跟踪驱逐对象是否前向重用距离最大，大大节省了内存开销）从而快速适应工作负载变化；
端到端的评估指标，例如字节缺失率，模拟起来非常花费时间。因此，作者提出使用 good decision ratio 指标来评价 ML 架构（包括特征、模型、预测目标和损失函数）的好坏，定义为驱逐对象的前向重用距离实际上是否超过了 Belady 边界。使用该指标，就可以在一次模拟中，收集训练数据、预测数据、学习 Belady 边界。
作者抛出的设计问题：
控制 ML 训练和预测的计算开销；
限制训练和预测过程中的内存开销；
- 如何在线获取训练数据；
- 如何选择替换候选集；
Background and Motivation
- CDN 缓存缺失，将花费高额带宽代价去后端存储中获取原数据，因此需要最小化缓存的字节命中率；
- CDN 缓存的工作集比容量大很多；
- 作者观察到现有 SOTA 缓存替换算法和 MIN 算法之间仍存在巨大差距（这点不存在的话，就没有做的必要了）；
- 启发式算法难以适应工作负载的变化；
- 实际 CDN 服务器的 CPU 占用率很低，
Approximating Belady’s MIN Algorithm
Relaxed Belady Algorithm
完全模仿 MIN 算法存在以下问题：
- 需要对所有缓存对象进行预测；
- ML 预测器需要准确地预测每个对象的前向重用距离；
近似 Belady 则是对上面两个问题的开销进行了妥协，从驱逐候选集前向重用距离预测结果大于 Belady 边界的对象中随机驱逐，如果没有，则继续对其余所有对象进行预测，变成完全模拟 Belady。
对于 Belady 边界来说，越小则跟踪的开销越小；越大则使 relaxed belady 的字节缺失率越接近 MIN。
Belady Boundary
预热阶段更新 Belady 边界，而在实际运行中，假设边界近似静止。
Good Decision Ratio
为了使算法做出更好的决策，需要一个指标来衡量单个决策的好坏，而端到端的指标，例如字节缺失率，只能反映大量决策的聚合好坏。
作者发现，# good decisions / # total eviction decisions 与字节缺失率密切相关。
Design of Learning Relaxed Belady Cache
Past information
使用更多数据可以提高训练质量，但会带来更多的内存开销。
对于小缓存，使用尽可能长的滑动窗口包含足够多的最近请求以做出更好的决策；对于大缓存，使用最小二乘法回归线拟合小缓存大小与其最佳滑动窗口大小的关系，从而得到大缓存对应的滑动窗口大小。（在论文后面有说，滑动窗口的长度近似于 Belady 边界，在实现中也是这样做的）
Training Data
获取训练数据这一部分细节挺多。
- 数据的特征在第一次访问时就可以得到，但是数据的标签只有在重用时才能知道；
- 需要从请求滑动窗口中随机采样不同对象获取训练数据；
- 不能随机采样请求，否则会导致偏向流行对象；
- 不能采样缓存中的对象，否则也会导致偏向流行对象；
- 只需后向重用距离大于 Belady 边界就可以安全地打标签了。有些对象重用距离太长，持续跟踪会导致过多的内存开销，甚至有些对象永远不会被重用，然而这些对象对于训练的质量起着非常重要的作用，将它们的重用距离设置为 2*Belady边界 的值。
ML Architecture
三种类型的特征：
- Deltas：delta1 表示对象的后向重用距离，delta2 表示对象最近两次重用之间的距离，… 。Deltas 在启发式中广泛应用，例如 LRU，LRU-K 和 S4LRU；（新近度）
- Exponentially decayed counters (EDCs)：每个 EDC 计数器近似该对象一段时间内的流行度。（频率）
- Static features：对象大小、对象类型
模型：对比了逻辑回归，线性回归，SVM，轻量级神经网络，发现 GBM 最好，且无需特征归一化，能够有效处理缺失值（Deltas）以及训练和测试效率都很高。
预测目标：log (time-to-next-request)
损失函数：L2
训练集大小：128K。一旦积累了 128K 带标签的数据，就会训练一个新的模型。128K 是决策率向训练时间和开销的权衡。
以上指标的确定，基本都是实验佐证再加以启发式的直觉解释。
Eviction Candidate Selection
候选集大小为 64，从缓存中随机选择 64 个对象进行批量预测，如果最大值超过 Belady 边界，驱逐它；否则，变成对所有缓存对象进行预测并驱逐预测最大值的对象。
Evaluation
与 ATS 生产系统进行比较，LRB 降低了多少网络流量；
与 ATS 相比，LRB 的开销；
与 SOTA 算法比较
