缓存是计算机科学中一种普遍存在的概念，它通过根据请求模式将一部分热门项目存储到离客户端更近的地方，显著提高存储和检索系统的性能。缓存管理的一个重要算法是用于动态更新存储项目集的决策策略，该策略经过了几十年的广泛优化，产生了几种高效、鲁棒的启发式方法。虽然近年来将机器学习应用于缓存策略已显示出有希望的结果（例如LRB、LHD、存储应用程序），但以一种可以可靠地从基准测试推广到生产设置的方式超越鲁棒的启发式方法仍然是一个挑战，同时保持有竞争力的计算和内存开销。
在NSDI 2023上发表的 “ HALP：YouTube 内容交付网络的启发式辅助学习偏好驱逐策略”中，我们介绍了一种可扩展的先进缓存驱逐框架，该框架基于学习到的奖励并使用带有自动反馈的偏好学习。启发式辅助学习偏好 (HALP) 框架是一种元算法，它使用随机化将轻量级启发式基线驱逐规则与学习到的奖励模型合并。奖励模型是一个轻量级神经网络，它通过对偏好比较的持续自动反馈不断进行训练，旨在模仿离线预言机。我们讨论了 HALP 如何提高 YouTube内容交付网络的基础设施效率和用户视频播放延迟。
缓存驱逐决策的学习偏好
HALP 框架基于两个组件来计算缓存驱逐决策：(1) 通过偏好学习使用自动反馈训练的神经奖励模型，以及 (2) 将学习到的奖励模型与快速启发式算法相结合的元算法。当缓存观察到传入请求时，HALP 会不断训练一个小型神经网络，该网络通过成对偏好反馈将其制定为偏好学习方法，从而预测每个项目的标量奖励。HALP的这个方面类似于从人类反馈 (RLHF) 系统中进行的强化学习，但有两个重要区别：
反馈是自动化的，并利用有关离线最佳缓存驱逐策略 结构的众所周知的结果。
该模型使用由自动反馈过程构建的训练示例的临时缓冲区 不断进行学习。
驱逐决策依赖于一个包含两个步骤的过滤机制。首先，使用一种高效但性能欠佳的启发式方法选择一小部分候选者。然后，重新排序步骤通过谨慎使用神经网络评分函数从基线候选者中进行优化，以“提高”最终决策的质量。
作为可用于生产的缓存策略实现，HALP 不仅可以做出驱逐决策，而且还包含用于有效构建相关反馈并更新模型以支持驱逐决策的成对偏好查询的端到端采样过程。
神经奖励模型
HALP 使用轻量级两层多层感知器(MLP) 作为其奖励模型，以选择性地对缓存中的各个项目进行评分。这些特征被构建和管理为仅限元数据的“幽灵缓存”（类似于ARC等传统策略）。在任何给定的查找请求之后，除了常规的缓存操作之外，HALP 还会进行更新动态内部表示所需的簿记（例如，在容量受限的键值存储中跟踪和更新特征元数据）。这包括：（1）用户作为输入提供的外部标记特征，以及缓存查找请求，以及（2）根据在每个项目上观察到的查找时间构建的内部构建的动态特征（例如，自上次访问以来的时间、两次访问之间的平均时间）。
HALP 从随机权重初始化开始完全在线学习其奖励模型。这似乎不是一个好主意，特别是如果决策专门用于优化奖励模型的话。然而，驱逐决策既依赖于学习到的奖励模型，也依赖于次优但简单而稳健的启发式方法，如LRU。当奖励模型完全泛化时，这可以实现最佳性能，同时对于尚未泛化的暂时不具信息量的奖励模型或正在赶上不断变化的环境的奖励模型保持稳健。
在线训练的另一个优势是专业化。每个缓存服务器都运行在可能不同的环境中（例如地理位置），这会影响本地网络条件以及哪些内容在本地受欢迎等。与单一的离线训练解决方案相比，在线训练会自动捕获这些信息，同时减轻泛化的负担。
从随机优先级队列中对样本进行评分
由于两个原因，仅使用学习目标来优化驱逐决策的质量是不切实际的。
计算效率限制：使用学习网络进行推理的成本可能比在大规模运行的实际缓存策略中执行的计算成本高得多。这不仅限制了网络和特征的表现力，还限制了每次驱逐决策期间调用这些的频率。
概括分布外的鲁棒性：HALP 部署在涉及持续学习的设置中，其中快速变化的工作负载可能会生成相对于先前看到的数据暂时分布外的请求模式。
为了解决这些问题，HALP 首先应用一种对应于驱逐优先级的廉价启发式评分规则来识别小的候选样本。此过程基于近似于精确优先级队列的有效随机抽样。用于生成候选样本的优先级函数旨在使用现有的手动调整算法（例如 LRU）快速计算。但是，这可以通过编辑简单的成本函数来配置为近似其他缓存替换启发式方法。与之前的工作（其中随机化用于权衡近似值和效率）不同，HALP 还依赖于跨时间步骤的采样候选中的固有随机化，以提供采样候选中必要的探索性多样性，以供训练和推理使用。
最终被驱逐的项目是从提供的候选项目中选出的，相当于从n 个重新排序的样本中选出的最佳样本，相当于 根据神经奖励模型最大化预测的偏好分数。用于驱逐决策的同一候选池也用于构建成对偏好查询以进行自动反馈，这有助于最大限度地减少样本之间的训练和推理偏差。
每次驱逐决定所调用的两阶段过程的概述。
通过自动反馈进行在线偏好学习
奖励模型是使用在线反馈来学习的，该反馈基于自动分配的偏好标签，这些标签在可行的情况下指示接收未来重新访问所花费时间的排名偏好顺序，从每个查询项目样本中的给定时间快照开始。这类似于 oracle 最优策略，该策略在任何给定时间从缓存中的所有项目中逐出未来访问时间最远的项目。
生成用于学习奖励模型的自动反馈。
为了使此反馈过程具有参考价值，HALP 构建了最有可能与驱逐决策相关的成对偏好查询。与通常的缓存操作同步，HALP 在做出每个驱逐决策时都会发出少量成对偏好查询，并将它们附加到一组待处理比较中。这些待处理比较的标签只能在未来的随机时间解决。为了在线操作，HALP 还会在每次查找请求后执行一些额外的簿记，以处理在当前请求之后可以逐步标记的任何待处理比较。HALP 使用比较中涉及的每个元素对待处理比较缓冲区进行索引，并回收陈旧比较（两者都可能永远不会被重新访问）所消耗的内存，以确保与反馈生成相关的内存开销随着时间的推移保持在有限范围内。
HALP 中所有主要组件的概述。
结果：对 YouTube CDN 的影响
通过实证分析，我们发现 HALP 在缓存未命中率方面优于公共基准测试中最先进的缓存策略。然而，虽然公共基准测试是一个有用的工具，但它们很少足以捕捉世界各地随时间推移的所有使用模式，更不用说我们已经部署的各种硬件配置了。
直到最近，YouTube 服务器还在使用优化的 LRU 变体来清除内存缓存。HALP 可将 YouTube 的内存出站/入站（即 CDN 提供的总带宽出站量与因缓存未命中而导致的检索（入站）所消耗的带宽之比）提高约 12%，并将内存命中率提高 6%。这可减少用户的延迟，因为内存读取速度比磁盘读取速度快，并且还可通过将磁盘与流量隔离开来，提高磁盘受限机器的出站容量。
下图显示了HALP 在 YouTube CDN 上最终推出后的几天内字节缺失率显著下降，现在 YouTube CDN 可以从缓存中提供更多内容，并且向最终用户提供更低的延迟，而无需采取更昂贵的检索方式来增加运营成本。
推出前后全球 YouTube 字节缺失率总计（垂直虚线）。
总体性能改进可能仍会隐藏重要的回归。除了衡量总体影响之外，我们还在本文中进行了分析，以使用机器级分析了解其对不同机架的影响，并发现其具有压倒性的积极影响。
结论
我们引入了一种可扩展的先进缓存驱逐框架，该框架基于学习奖励并使用带有自动反馈的偏好学习。由于其设计选择，HALP 可以以类似于任何其他缓存策略的方式部署，而无需单独管理标记示例、训练过程和模型版本作为大多数机器学习系统常见的额外离线管道的运营开销。因此，与其他经典算法相比，它只会产生少量额外开销，但具有能够利用其他功能做出驱逐决策并不断适应不断变化的访问模式的额外好处。
这是首次在广泛使用和流量巨大的 CDN 中大规模部署学习缓存策略，显著提高了 CDN 基础设施的效率，同时也为用户带来了更好的体验质量。
致谢
Ramki Gummadi 现在是 Google DeepMind 的一员。我们感谢 John Guilyard 对插图的帮助以及 Richard Schooler 对本文的反馈。
评论