Spache: Accelerating Ubiquitous Web Browsing via Schedule-Driven Space Caching

这篇是新鲜出炉的WWW25卫星网络论文，笔者在从家返回学校的高铁上，闲的无聊索性读一篇论文。

高铁人多嘈杂，实在不方便精耕细作整理，因此这里并不像其他论文一样逐模块翻译并整理，直接上读后感！

13:45合肥南出发 -> 笔者无聊 -> 直接上原文阅读 -> 整理并直接写读后感 -> 19:15到西安北

Abstract and Intro

提出背景

现在ISN和LSN都在高速发展，演化出这样的情景:

陆地上，随着CDN的兴起，很多运营商会在不同的地区建立自己的服务设施（云服务器），这些云服务器里用户更近（物理意义上），自己的源服务器将内容分发到云服务器上，然后用户进行fetch，更新操作也是如此。

随着低轨卫星网络的兴起，卫星本身就可以作为远端的Cache进行数据存储，并且用卫星链路中继/转发等操作也是可以的。

在这个情景下，很显然可以想到将陆地的网络服务器/存储 与 卫星对应的存储等服务相关联。

挑战

现在的陆地CDN效率还是可待提高的，原因有三点:

1. CDN云服务器地理位置分布不均衡，存在大量农村/偏远地区无服务
2. “蜿蜒的供应路径”
   • BGP固有的特点: 不同AS之间采取类似于BGP的商用协议，并不是依据最短路径，因此时延等问题存在
   • Gateway设施不全
3. “最后一公里”的堵车问题: 当前大多数都是采用“SRLA”模式，大部分流量转发还是依靠陆地网络，卫星本质只起“最后一跳”的中继，因此存在拥塞问题

SRLA

这个概念在 NSDI2023 StarryNet 论文中提到过

使用卫星作为Cache存储系统可以的，但是存在问题 (拜“高移动性”所赐):

1. 分给用户的Cache在卫星上，卫星“跑路”了
2. 一个卫星服务的地区总是在变化

Spache可以解决上述问题，这要感谢LSNs的特有属性，它们能够给出卫星运行的参数、运动规律、变化情况（甚至是预测）

具体来说，Spache解决上述问题的方式是:

1. 基于事件预测并prefetch，这样有利于warm cache
2. 采取cache-partition策略，缓解cache污染问题

Background and Motivation

卫星-云 Cache一体化结构

注意这里面的概念:

UT / PoPs / USL / ISL / GSL / Bent-Pipe Routing / ISL-based Routing / LSN RDS

看图即可，论文里也有描述，不多说了

当前陆地Web Cache的问题

1. 覆盖地区不均衡，大量农村/偏远地区无服务
2. “蜿蜒的访问路径”
   • BGP自身商业协议的缘故（并不是基于最短路径）
   • Gateway数量少，配置不全
3. 只要走LSN路径，访存速度就会受LSN的钳制 (不稳定、丢包率高... -> RTT波动且上涨)

Spache Overview

A bold idea: integrating web cache into LEO satellites to serve terrestrial users.

将Cache放在太空里

1. 这完全可行，目前甚至有团队在LEO上部署数据中心
2. 好处
   • 任意处可达，解决“偏远地区无服务”问题
   • 同一个AS处理，规避“蜿蜒的路径”问题
   • 解决“最后一公里”问题，直接从卫星路可达

Spache 结构

关键要素:

• Control Center
• Controller
• Satellite Node (Node)

步骤:

1. Web Provider 在Controller注册
2. Web Provider分发网页内容
3. Satellite进行Cache缓存
4. 根据Cache Replacement进行update

Satellite Cache的显著问题

TL;DR 都是高速移动性惹的祸

1. Cache刚warm up，就走了
2. 现存的Cache替换算法不能解决问题，甚至加剧

如何解决这两个问题:

1. communication schedule in LSNs
2. schedule-driven cache management

Schedule-driven Cache Management

Communication Schedule in LSNs

主体思想: 运营商将参数信息告诉Controller, 此时它就“全知”了

Satellite Operators (SpaceX等科技商家): 它们什么都知道，谁跟谁连接、什么时候连接等信息都在它们的眼皮之下

Satellite Operators 将信息传递给 Spache Controller，此时Controller什么都知道了

Spache Controller跟响应的nodes进行交互

Schedule-Driven Cache Prefetching

主体思想: 在UT访问之前先把内容“预存”在相应的cache里

机制比较复杂，用Perplexity帮助分析了一下:

1) 核心问题：为什么需要基于调度的缓存预取？

在空间网络中，用户终端（UT）会频繁切换到不同的低地轨道（LEO）卫星节点。

如果用户终端访问的缓存是“冷缓存”（cold cache，指没有预加载所需内容的缓存），就会导致低命中率和长延迟。这种情况会降低用户体验。

为了避免这种情况，Spache提出了一种机制，在用户终端切换到新的LEO节点之前，提前将可能需要的数据加载到目标节点的缓存中。

这种方法被称为“基于调度的预取”。

2）关键问题：如何实现基于调度的缓存预取？

预取什么内容？

通过分析调度信息，系统决定需要加载哪些内容。具体步骤如下：

• 监控内容的流行度（Popularity）：
  • 每个内容\(C_i\)的流行度\(Pop_i\)是通过统计该内容在目标区域\(r_{new}\)的请求比例计算得出
• 选择合适的内容集合\(\Phi_{new}\)**：从流行度最高的内容开始，逐步添加到集合中，直到满足一个阈值\(\beta\)，即： $$ |\Phi| = \arg\min_k \sum_{i=1}^k Pop_i \geq \beta $$

简单来说，这一步是 挑选出最受欢迎的一批内容进行预加载 。

从哪里获取这些内容？

目标节点\(r_{new}\)会 从以下来源获取数据 ：

• 本地已有缓存
• 其他LEO节点中已经存储这些内容的位置（称为\(Src_{r_{new}}\)）

每个来源都带有一个“获取延迟”（\(T_{fetching}\)），表示从该位置获取数据所需时间。

什么时候进行预取？

预取操作需要在合适的时间点进行，以平衡延迟和资源消耗：

• 决策时刻\(t_{decision}\)：系统根据调度信息，在用户终端切换到新节点之前做出预取决策。
• 持续评估是否值得预取：LEO节点会逐一检查\(\Phi_{new}\)中的每个内容\(C_i\)， 计算其潜在收益和成本。如果收益大于成本，就执行预取 。

如何计算收益和成本？

收益（Latency Benefit）

提前预取可以减少未来用户请求时的等待时间，其公式为：

\[ LatencyBenefit_{prefetching\ C_i} = \frac{T_{fetching}^2}{2\Delta t} \times \sum_j RN_{c_j}^{new} \times Pop_j \]

• \(T_{fetching}^2 / 2\Delta t\)：衡量减少延迟的效果
• \(RN_{c_j}^{new}\)：区域\(r_{new}\)内请求数量
• \(Pop_j\)：内容流行度

记住就行，这是收益公式

成本（Latency Cost）

预取占用了缓存空间，可能导致其他有价值的数据被驱逐，其公式为：

\[ LatencyCost_{prefetching\ C_i} = \frac{T_{cost}}{\Delta t} \times \sum_j RN_{c_j}^{evict} \times SA-LR_{evict} \]

• \(T_{cost} / \Delta t\)：驱逐数据带来的时间成本
• \(RN_{c_j}^{evict}\)：被驱逐区域内的数据请求量
• \(SA-LR_{evict}\)：被驱逐数据的重要性，基于调度分区策略计算

如果某个内容的收益大于成本，就执行预取，否则跳过。

3）总结与形象化解释

可以把 Spache 的机制比作一个“太空快递员”：

1. 快递员知道用户即将搬家（切换到新节点）。
2. 他提前根据用户的喜好清单（流行度）打包好最有可能需要的物品（数据）。
3. 他从最近的仓库（LEO 节点）挑选物品，但要确保不占用太多空间，以免丢掉其他重要物品。
4. 在搬家前，他会权衡提前送货（预取）的好处和成本。如果好处大，就行动，否则等待。

这种机制确保了用户搬家后能立即用上需要的数据，大幅提升了访问效率，同时避免了不必要的资源浪费。

Schedule-Driven Cache Partition

机制比较复杂，用Perplexity帮助分析了一下:

背景：缓存污染问题

在LEO卫星网络中，不同地区的用户请求会共享同一个缓存空间。由于不同地区的请求内容可能完全不同，这种共享可能导致 缓存污染 ：

什么是缓存污染？

比如， 区域A的热门内容被区域B的请求替换掉，但区域A仍然需要这些内容 。这会导致缓存中存储了对区域A无用的数据，降低了缓存效率。

为了解决这个问题，Spache提出了一种 “基于调度的缓存分区” 策略。

1）缓存分区是什么

缓存分区是一种技术，将整个缓存空间划分为多个子缓存（sub-cache）， 每个子缓存专门用于特定的内容组或服务区域=。

• 防止不同区域间的请求相互干扰
• 减少有用内容被无关请求替换（即减少污染）

这种技术最初用于CPU共享缓存，后来被应用到CDN（内容分发网络）中。

2）LEO卫星中的新挑战

相比传统地面系统，LEO卫星面临以下独特挑战：

• 服务区域快速变化：卫星在轨道上移动，服务区域会频繁切换
• 高计算开销：缓存分区需要动态调整，但LEO卫星上的内容规模比CPU程序大得多，调整难度更高
• 延迟问题：当服务区域切换时，旧数据可能无法及时清除，新数据加载速度跟不上

这导致传统方法无法很好地适应LEO卫星环境。

3）Spache 的解决方案：基于调度的缓存分区

Spache 提出了一个创新的方法，通过利用卫星的调度信息来优化缓存分区：

1. 多级子缓存划分：
   • 缓存被划分为多个子缓存，每个子缓存绑定到一个服务区域 。
   • 每个子缓存使用独立的替换算法 来管理内容。
2. 按需处理请求：
   • 当 用户请求某个区域的内容时，只访问该区域对应的子缓存 。
   • 这样可以避免其他区域的数据被替换掉，从而减少污染。

如何衡量优化效果, 用SA-LR

为了衡量优化效果，Spache 定义了一个新的指标：基于调度的平均延迟减少（SA-LR）

核心衡量指标: SA-LR 衡量的是通过优化后，用户请求延迟减少了多少

公式如下：

\[ SA - LR_{ri}^t = \frac{LR_{ri}^{t-1}}{p_{ri}^{t-1}} \times \frac{RN_{ri}}{\sum_{j=1}^N RN_{rj}} \]

• \(LR_{ri}^{t-1}\)：上一时间片中，某区域 \(r_i\) 的延迟减少值
• \(p_{ri}^{t-1}\)：上一时间片中该区域的总请求数
• \(RN_{ri}\)：当前时间片中该区域的请求率
• \(\sum RN_{rj}\)：所有区域的总请求率

通过这个公式，可以动态评估每个服务区域在不同时间片中的优化效果。

基于调度的自适应调整

在每个时间片开始时，Spache 会根据 SA-LR 动态调整各子缓存大小：

1. 排名调整：
   • 根据 SA-LR 对所有服务区域进行排名。
   • 排名靠后的区域，其对应子缓存会缩小一定比例 \(D\) ；
   • 排名靠前的区域，其子缓存会扩大 \(D\)。
2. 动态调整幅度 \(D\)：
   • \(D\) 的大小取决于各服务区域请求率变化幅度（\(\Delta RN\)）。
   • 如果某些区域请求波动较大，系统会更快地重新分配其对应子缓存大小。
3. 快速重分配：
   • 如果某个服务区域突然退出，其子缓存空间会迅速重新分配给其他活跃区域，从而最大限度地减少污染和浪费。

4）总结与形象化理解

可以将 Spache 的方法比喻成一个“动态货架管理系统”：

• 货架划分： 将超市货架划分为多个小货架，每个货架专门存放某类商品（即特定服务区域的数据）。
• 需求预测： 根据顾客购买习惯预测哪些商品需求高，将更多空间分配给这些商品。
• 实时调整： 如果某类商品需求突然增加，就从需求低的货架腾出空间给它。

通过这种方式，Spache 实现了对 LEO 卫星有限资源的高效管理，同时提升了用户体验（降低延迟）。

Evaluation

实验结果表明:

1. cache hit rate 变高了
2. 弹性好，稳定，抗干扰
3. 用户感知体验变好: RTT (round trip time) 变小 / PLT (page load time) 变小
4. GSL traffic 变小很多
   • 减小卫星链路压力，从而缓解“最后一公里”问题

Related Work

有团队分析了 远端服务器的反馈 / 5G或无线网络 的情景，但这篇论文专注于LEO（高度移动性是最本质的区别）

有很多团队都为Cache替换算法贡献了思考，但是这篇论文最大的特色还是LEO Cache具有高速移动性

有团队做了“在轨计算/在轨存储”的努力，但是针对的不是CDN Cache问题

Conclusion

略