[Paper] 推断因果关系以改进对相关请求客户端的缓存：在 VR 中的应用

Source: arXiv - 2512.08626v1

概览

边缘缓存是实现低时延服务（如 VR）的基石，但经典策略如 LRU 和 LFU 假设客户端请求相互独立。本文指出，当请求 相关——例如用户共享同一虚拟环境时——这些常用策略可能远非最优。作者提出了一种新的分组客户端请求模型，证明了在何种情况下 LRU 或 LFU 在理论上是最佳的，并推出 LFRU，一种能够在线学习因果关系并显著提升命中率的算法。

关键贡献

• 分组客户端请求模型：在经典独立参考模型的基础上扩展，以捕获用户之间的时间和上下文相关性。
• 理论缓存规模划分：证明在小到中等规模的缓存下 LFU 最优，而只有当缓存足够大时 LRU 才能超越 LFU。
• LFRU 算法：一种轻量级、在线的缓存策略，能够推断对象之间的因果依赖并据此决定淘汰顺序。
• 接近最优的性能：在结构化相关场景中，LFRU 接近离线最优的 Belady 策略。
• 面向 VR 的评估：构建了真实的 VR 请求轨迹，展示了相较于 LRU 提升最高 2.9 倍，相较于 LFU 提升 1.9 倍。

方法论

1. 建模相关需求 – 作者定义了共享潜在上下文（例如同一 VR 场景）的客户端“组”。在同一组内，对某一对象的请求会提升随后请求相关对象的概率。
2. 缓存分析的理论推导 – 通过随机分析，推导出分组模型下 LRU 的期望未命中率，并与 LFU 进行比较，找出每种策略最优的缓存规模阈值。
3. LFRU 设计 –
   • Follow‑Score（跟随分数）：对每个缓存对象维护一个轻量计数器，记录该对象在短时间窗口内被后续请求“跟随”的次数。
   • Least Following（最少跟随）：先淘汰 Follow‑Score 最低的对象（它们不太可能出现在因果链中）。
   • Recently Used 作为平局决策：在 Follow‑Score 相同的对象之间，回退使用标准 LRU 顺序。
     该算法完全在线运行，每次请求仅需 O(1) 的更新。
4. 数据集构建 – 生成合成和基于轨迹的 VR 工作负载，模拟用户在共享虚拟空间中的移动，考虑真实的带宽和时延约束。
5. 基准测试 – 在多种缓存规模和相关强度下，将 LFRU 与 LRU、LFU 以及离线最优（Belady）进行比较。

结果与发现

• 相关性至关重要：当组内请求序列为 “场景 → 头像 → 纹理” 时，LFRU 能学习该链并将下一个可能需要的对象保留在缓存中。
• 鲁棒性：即使相关强度减弱，LFRU 也从不逊于 LRU 或 LFU。
• 开销：Follow‑Score 计数器仅增加 < 2 % 的内存占用，CPU 开销可忽略不计。

实际意义

• VR/AR 边缘服务器：部署 LFRU 可通过保留下一个最可能使用的资产（如即将加载的场景瓦片）来降低感知时延，提升用户沉浸感。
• 内容分发网络（CDN）：在直播活动或协作应用中，用户共同消费一系列共享资产，LFRU 能在不增加硬件的情况下降低回程流量。
• 物联网与协作机器人：协同群体的设备常请求相关的固件或地图更新，LFRU 可将这些更新本地化，节省带宽。
• 易于集成：LFRU 基于现有 LRU 实现，只需为每个对象添加一个小计数器并修改淘汰逻辑，即可作为大多数缓存库的即插即用升级。

局限性与未来工作

• 短期因果假设：LFRU 依赖有界时间窗口来推断跟随关系，无法捕获长期依赖（如每周的使用模式）。
• 静态组定义：模型将组视为固定不变，实际中用户加入/离开 VR 会话会导致组动态变化，影响准确性。
• 评估范围：实验主要针对 VR 工作负载，若在网页流量、视频流或边缘 AI 推理等场景进行更广泛验证，将提升通用性。
• 未来方向：将 Follow‑Score 扩展至多步链路，结合机器学习预测器捕获更长时域的需求，并在生产边缘平台上进行实测。

作者

• Agrim Bari
• Gustavo de Veciana
• Yuqi Zhou

论文信息

• arXiv ID: 2512.08626v1
• 分类: cs.NI, cs.SE
• 发布日期: 2025 年 12 月 9 日
• PDF: Download PDF