在随机延迟环境下优化TTL缓存层次结构：直接方法与基于图变换的学习

TTL缓存层次结构在随机网络延迟下的非线性优化与机器学习方法研究，提出基于α公平性的解析解和exTTL策略补偿存储不匹配，并开发图神经网络解决大规模系统优化问题。

　　

Karim S. Elsayed|Fabien Geyer|Amr Rizk

德国汉诺威莱布尼茨大学通信技术研究所

摘要

我们在网络延迟的情况下优化了TTL（生存时间）缓存层次结构。TTL缓存为缓存的对象分配了单独的驱逐计时器，这些对象通常在命中时会被刷新；而在未命中时，需要从父缓存中随机获取该对象。由于TTL缓存具有对象解耦的特性，因此对其进行优化特别重要，因为可以实现对服务的差异化。然而，现有的基于精确TTL缓存效用的优化方法仅适用于单个TTL缓存，尤其是在网络延迟的情况下。

在本文中，我们利用对象解耦效应，根据随机网络延迟下的精确对象命中概率来构建TTL缓存层次结构的非线性效用最大化问题。我们通过迭代求解该效用最大化问题来找到每个对象的最优TTL值。此外，我们提出了一种称为exTTL的TTL策略变体，以抵消实际TTL缓存实现与其理想无限存储假设之间的存储不匹配对最优效用的影响。进一步地，我们展示了对于大型层次结构，精确模型存在可处理性问题，并提出了一种机器学习方法来估计大型系统的最优TTL值。最后，我们提供了基于数值和数据中心追踪的评估结果，显示了考虑到网络延迟后TTL优化所带来的显著卸载改进。

引言

缓存通过将频繁请求的数据对象放置在更接近请求源的位置，从而在减少响应时间和带宽消耗方面发挥着重要作用[1]、[2]。随着对象需求的动态变化，服务差异化成为缓存系统的一个核心组成部分。这是通过缓存效用抽象[3]实现的，它引出了缓存公平性和缓存资源分配等概念。细粒度缓存优化的一个关键方法在于控制每个对象所获得的效用。这要求围绕独立调整特定对象的缓存性能指标来构建系统。

传统的和现代的缓存使用固定或数据驱动的、学习得到的策略[4]、[5]、[6]，通常运行一个或多个决策规则来关联缓存中所有对象的占用情况。例如，最近最少使用（LRU）是一种通用且流行的缓存策略，它基于这种关联。相比之下，生存时间（TTL）缓存通过为每个对象分配独立的过期/驱逐时间标签来解耦缓存中的对象占用情况[7]。在单个TTL缓存中，通过推导出特定对象的最优TTL值来最大化对象的总体效用[3]。尽管[3]中的工作具有开创性，但它仅限于在一系列限制性假设下的单个缓存，包括零网络延迟和泊松请求。

缓存系统通常由多个缓存组成，形成一个层次结构[1]。我们考虑了表示内容分发网络（CDN）和数据中心缓存等系统的树状层次结构。我们注意到，优化缓存层次结构是具有挑战性的，因为它涉及到在随机网络延迟下联合建模和优化多个互连的缓存。同时，也已知单独优化缓存会因允许冗余并忽略请求过程的相关性而未能充分利用存储资源[8]。

之前关于TTL缓存层次结构建模和性能评估的工作提供了可计算的模型，这些模型要么是精确的但速度较慢[9]、[10]，要么是近似的但速度较快[11]、[12]。[9]中的工作首次提供了在零网络延迟下的TTL缓存树的精确马尔可夫到达过程（MAP）模型。正如[13]中经验观察到的，对于广泛的缓存系统而言，网络延迟显著影响缓存性能。作者观察到网络延迟的范围从请求间隔时间的一个数量级到多个数量级不等。最近，[10]中的工作扩展了[9]中的MAP模型，以模拟层次结构内的随机网络延迟，并推导出层次结构的命中概率。此外，后续的工作[14]推导出了[10]中缓存层次结构的响应时间。

在本文中，我们优化了在非零网络延迟下的TTL缓存层次结构的总体效用。我们的贡献包括：

•

我们提出了一个α-公平性效用最大化问题，用于在网络延迟下优化TTL缓存层次结构，以充分利用TTL缓存的对象解耦效应。我们使用[10]中得出的精确MAP模型的分析性能指标，为非线性效用最大化问题提供了分析解（第3-4.2节）。

•

我们展示了给定平均命中概率的效用优化是一个$0?1$

多背包问题，适用于具有递增危险率的更新请求到达过程。

•

我们提出了exTTL，这是一种TTL策略的变体，用于在实际实现中保持最优效用，同时实现理想的TTL策略。

•

我们提供了一个图神经网络（GNN）模型，用于最大化大型层次结构的缓存系统效用（第6节）。

•

我们提供了分析和GNN效用最大化方法的数值评估（第7节）。

部分摘录

TTL缓存建模和优化方法

在网络资源分配[15]、[16]的背景下广泛使用的效用函数最近被采纳到缓存模型中，作为实现服务差异化的手段[3]。由于TTL策略解耦了缓存中的对象，因此它特别适合于控制单个对象性能指标（如对象命中概率和占用率）的效用最大化问题。需要注意的是，容量驱动的缓存策略（如最近最少使用（LRU）

系统模型和问题陈述

在本节中，我们为随机延迟下的TTL缓存层次结构制定了效用最大化问题，并讨论了不同的效用函数概念。我们考虑了一个包含n_c个缓存的TTL缓存树，其中n_l个是叶子缓存，系统中的对象数量为N，如图4所示。外部对象请求仅通过叶子节点接收。从父缓存检索对象需要不可忽视的随机下载延迟。回想一下第2.2.1节的内容，不可忽视的延迟

凸效用最大化问题的解决方案

在本节中，我们推导了第3节中定义的效用最大化问题的解决方案，考虑了凸效用函数，即$\alpha ?$对于α?≠?0的情况。我们首先在第4.1节中为单个缓存提出了解决方案，其中展示了最优TTL值的分析封闭形式表达式示例，并说明了分析解决缓存层次结构优化问题的难度。在第4.2节中，我们介绍了我们的内点优化方法

非凸平均命中概率最大化问题的解决方案

在本节中，我们为缓存层次结构的平均命中概率最大化（最常见的效用函数）制定了公式，即（7）中的α-公平效用，对于$\alpha =0$情况，将其视为一个$0?1$多背包问题。需要为这种情况提出不同的公式，是因为预期命中概率作为效用函数是非凸的，这与α?>?0时的其他形式的α-公平效用不同。这依赖于第

近似图神经网络TTL缓存层次结构效用最大化

与第4.2节中提出的封闭形式解决方案相比，我们接下来提出了一种基于学习的方法来预测最优TTL值。我们使用GNN的理由是它们可以处理大规模图，从而规避了封闭形式优化的扩展限制。我们在第7节中评估了两种方法的执行时间。

接下来，我们介绍了用于优化缓存层次结构TTL配置的神经网络架构和数据转换。目标是

评估和经验教训

接下来，我们展示了所提出的缓存效用最大化方法的数值性能评估。除非另有说明，我们考虑图4中的两级缓存树，并使用效用函数（7）的比例公平参数化（$\alpha =1$）。叶子缓存处的请求率遵循Zipf分布，即索引j的比率是${\lambda }_j=\frac{1}{j^s}$和$s=0.8$，如[36]中所观察到的。注意，对于给定的对象，叶子之间的请求率是不均匀的，即对象i

结论

我们研究了在随机网络延迟下TTL缓存层次的优化。通过利用精确TTL缓存模型中的对象解耦，我们分析了缓存层次结构的非线性效用最大化问题，并找到了每个对象的最优TTL值。此外，我们证明了对于非凸平均命中概率最大化问题，这是一个使用LP算法解决的