学术研究报告：LEI：一种基于强化学习的多对象缓存准入策略
本研究报告旨在向中国学术界介绍一篇发表于2025年的前沿计算机科学研究论文。该论文由Hexuan Lv, Yuhai Zhao, 以及Sice Wang共同完成，其中Yuhai Zhao为通讯作者。Hexuan Lv和Yuhai Zhao来自东北大学计算机科学与工程学院、医学影像智能计算教育部重点实验室（沈阳，辽宁），Sice Wang来自沈阳工业大学（沈阳，辽宁）。这项研究以“LEI: Reinforced Multi-Object Cache Admission”为题，发表于第34届ACM信息与知识管理国际会议（CIKM ‘25）的会议论文集，该会议于2025年11月10日至14日在韩国首尔举行。论文已通过开放获取方式发布，DOI为10.1145⁄3746252.3761119。
一、 研究的学术背景
本研究属于计算机网络与信息系统领域，具体聚焦于内容分发网络（Content Delivery Network, CDN）中的缓存管理技术。CDN通过在全球边缘节点部署服务器缓存热门内容，旨在减轻源站负载、降低用户访问延迟。热对象缓存（Hot Object Cache, HOC）管理是CDN的核心功能，其性能直接关系到用户体验和运营成本。HOC管理主要包含两大策略：替换策略（Eviction Policy）和准入策略（Admission Policy）。替换策略决定当缓存满时淘汰哪个对象，已得到广泛研究；而准入策略则决定哪些新请求的对象应被载入HOC，其研究相对滞后。
当前主流的HOC准入策略主要分为三类：1）启发式策略（如LRU、FIFO、LFU），逻辑简单但无法捕捉复杂的请求模式；2）基于信息预测的策略（如POPCache、CACA），利用AI预测对象流行度，但依赖高维特征，泛化能力差；3）基于阈值的策略（如AdaptSize、Darwin），通过设定对象大小、访问频率等阈值来做决策，虽有一定智能，但仍无法学习请求序列中复杂的时序依赖关系。
CDN的请求模式具有两个显著特征：动态性（每个时刻请求的对象数量可变）和时序依赖性（短时间内请求的对象之间存在关联）。这构成了一个两级序列结构：时刻间序列（不同时刻请求事件的顺序）和时刻内序列（同一时刻内多个请求对象的顺序）。现有的方法，包括Transformer模型中的传统位置编码（Positional Encoding, PE）或时间编码（Time Encoding, TE），均难以有效建模这种不规则的、多对象的时序序列。此外，将强化学习应用于HOC准入决策面临奖励延迟的严峻挑战：一个准入决策（接纳或拒绝一个对象）的好坏，需要等到未来该对象是否被再次请求（命中）或是否被错误淘汰（缺失）时才能评估，无法获得即时奖励反馈。
因此，本研究旨在解决上述核心问题。其目标是：设计一种新型的、基于强化学习的HOC准入策略，该策略能够有效建模不规则的多对象请求序列的时序依赖，克服奖励延迟问题，并在长期运行中保持稳定和高效，最终提升CDN的缓存命中率并降低后端负载。
二、 研究的详细工作流程
本研究提出了一种名为LEI的强化学习框架。其工作流程可概括为三大核心组件的设计与整合，以及一个两阶段的训练策略。
1. 多对象时间编码机制 为了建模CDN请求中不规则的两级时序序列，论文创新性地提出了多对象时间编码机制。传统的时间编码方法在处理图2所示的不规则请求时面临两难：若仅按对象请求顺序编码，会忽略时间间隔；若仅按时间戳编码，会丢失同一时刻内对象的顺序信息。LEI的解决方案是将两级序列重新表述为一个基于密度的线性化序列。具体而言，在序列轴上，将每个时间戳置于等间隔的位置；对于每个时间戳区间，则根据该时刻内请求对象的原始顺序，将它们均匀地分布在该区间内。这样，请求密集的时刻，其对象嵌入在序列中排列紧密；请求稀疏的时刻，对象嵌入则排列稀疏。由此，一个密度变化的序列既能体现时刻间的顺序，又能体现时刻内对象的顺序。
基于此密度序列，论文设计了MO-TE的数学公式。该编码保证了唯一性（任何两个请求的编码向量唯一）和密度-邻近相关性（两个编码向量的相似度与其在密度序列中的接近程度正相关）。通过可视化热图对比（图5）显示，MO-TE相比传统的位置编码，能更准确地反映请求对象间的距离关系，从而为模型学习时序特征提供了更有效的基础。
2. 缓冲区机制与强化学习建模 为了解决HOC准入决策中的奖励延迟问题，LEI引入了一个缓冲区机制。其核心思想是：为每一个因缓存缺失而需要做出准入决策的对象（无论是实际被接纳的，还是被拒绝的）创建一个决策元组，并暂存于缓冲区中。对于被拒绝的对象，系统会创建一个不占用实际存储空间的“影子对象”放入HOC，以模拟其若被接纳后的缓存生命周期。所有缓冲区中的元组，其初始奖励值均为空。
随后，系统根据未来实际发生的请求动态更新这些元组的奖励。规则如下： * 若一个被接纳的对象在HOC存留期间被命中，其对应元组奖励+1；若直至被淘汰都未命中，则奖励-1。 * 若一个影子对象在存留期间被请求（意味着发生了本可避免的缓存缺失），其对应元组奖励-1；若从未被请求直至淘汰，则奖励+1。
一旦奖励被确定，该元组就会被复制并加入经验回放池，用于训练强化学习智能体。原始元组则继续留在缓冲区，直至其关联对象从HOC中淘汰。
在此机制基础上，研究将HOC准入过程形式化为一个马尔可夫决策过程： * 状态：包含当前请求信息（对象ID、大小、时间戳）以及过去n个请求的历史信息（ID序列、大小序列、时间戳序列）。 * 动作：当缓存缺失时，智能体选择“拒绝”或“接纳”。 * 状态转移：由未来的请求模式和缓存替换策略驱动，简化为仅依赖当前状态。 * 奖励函数：如上文缓冲区机制所述，根据对象在HOC存续期内的命中情况给出数值化奖励（如+1， -1， 或命中k次则+k）。
3. LEI模型架构与两阶段训练策略 LEI模型采用双头网络架构，灵感来源于中国古代神话中的双头四足神鸟“鸓”，寓意其双头设计和在突发高负载下的稳定学习能力。模型架构如图7所示，主要包括嵌入层、LSTM层、注意力层、预测模块和强化学习决策模块。
处理流程如下：首先，嵌入层将当前请求的对象ID和大小映射为向量。接着，LSTM层处理这些嵌入，生成当前隐藏状态。同时，模型维护过去m个隐藏状态，并与经过MO-TE编码的时间戳信息结合，形成注意力机制中的键和值。当前请求的ID和大小嵌入拼接后作为查询。注意力层计算查询与历史键值之间的相关性，输出一个上下文表征向量。该向量随后被送入两个并行的全连接层： * 预测头：通过Softmax函数，预测当前对象的重用距离和栈距离（监督学习任务）。 * 决策头：通过Sigmoid函数，输出接纳当前对象的概率（强化学习任务）。
训练采用两阶段策略： * 阶段一：监督预训练。使用Belady最优算法在部分追踪数据上离线生成标签（栈距离和请求距离），训练模型的预测头以及共享的LSTM和注意力层参数。此阶段使用均方误差损失函数，目的是让模型初步学习请求模式，缓解后续强化学习的冷启动问题。 * 阶段二：半在线强化学习。模型加载预训练参数后，部署到模拟的CDN环境中进行在线交互。智能体根据当前状态做出准入决策，环境（包含HOC、DC、缓冲区）执行决策并产生新状态。奖励由缓冲区机制异步更新并存入经验回放池。每处理一定数量的请求后，模型从回放池中采样一批数据，使用软演员-评论家算法更新决策头的参数，以最大化长期累积奖励。这种“半在线”方式使得模型能持续适应请求模式的变化。
三、 研究的主要结果
研究在四个真实世界的大规模数据集上进行了评估：WikipediaA, WikipediaB, TwitterA, TwitterB。基线方法包括LRU、FIFO、LFU、AdaptSize、HillClimbing、Percentile以及一个优化版的Darwin。
1. 综合性能 针对研究问题RQ1，图8至图11展示了LEI在长达24-48小时模拟实验中的全面性能。结果表明： * 请求命中率：在所有数据集上，LEI均显著优于所有基线方法，相比每个数据集上的最佳基线，提升了5%至12%（图8）。 * 字节命中率：提升幅度更为显著，达到了5%至42%（图9）。即使在基线方法表现已经很好的TwitterB数据集上，LEI仍能取得小幅增益。 * 磁盘缓存读写率：LEI有效降低了DC的读取和写入流量（图10， 图11）。论文指出，对于大型CDN提供商，命中率的微小提升也能转化为每年数千万美元的后端流量和带宽成本节约。
2. 各组件有效性分析 针对研究问题RQ2，研究通过消融实验验证了三个核心组件的贡献： * 多对象时间编码的有效性：在图12和图13中，对比了使用PE和MO-TE的模型在预测请求距离和栈距离任务上的准确性。结果显示，在大多数误差容忍阈值下，MO-TE的预测准确率 consistently优于PE，证明了其在建模不规则多对象时序序列方面的优越性。 * 缓冲区机制的必要性：图14和图15对比了完整版LEI与去掉缓冲区、直接使用当前命中率作为奖励的变体。结果显示，没有缓冲区的变体性能显著下降，因为它无法建立决策与延迟奖励之间的因果关系，导致学习到次优策略。 * 两阶段训练策略的重要性：图16和图17对比了完整版LEI与没有监督预训练、直接从零开始进行强化学习的变体。后者在初始阶段性能极低，虽然后续通过在线学习有所提升，但始终无法追上经过预训练的LEI，凸显了预训练对于稳定启动和最终性能的关键作用。
3. 长期稳定性与系统开销 针对研究问题RQ3，研究在一个持续10天的长周期Wikipedia追踪数据上测试了LEI的稳定性。图18和图19显示，LEI的请求命中率和字节命中率在整个半在线训练期间保持稳定，未出现性能衰减，证明了其长期部署的可行性。 针对研究问题RQ4，论文评估了LEI的系统开销： * 延迟与吞吐量：LEI的平均推理延迟仅为0.02毫秒，最大延迟0.131毫秒，理论最大吞吐量可达每秒50,000个请求，远高于数据集中观测到的峰值请求率（最高约3,466 req/s），满足实际CDN场景需求。 * CPU与内存使用：推理时，LEI平均增加约20MB内存，在强化学习更新步骤时峰值可达400MB，属于可接受范围。CPU利用率在大部分时间保持低位，仅在模型更新时达到约16%的峰值（图20）。
四、 研究的结论与价值
本研究成功提出并验证了LEI——一种用于CDN多对象缓存准入的、基于强化学习的新型框架。其核心贡献在于： 1. 科学价值：首次系统地将不规则多对象时序序列的建模问题（通过MO-TE）、强化学习中的奖励延迟问题（通过缓冲区机制）以及模型训练的稳定性问题（通过双头架构与两阶段训练）在CDN缓存准入这一具体场景中综合解决，为序列决策问题在复杂、异步奖励环境中的应用提供了新的方法论框架。 2. 应用价值：LEI显著提升了CDN缓存性能，在多个真实数据集上全面超越了现有主流方法。其低延迟、高吞吐、可控的资源开销以及长期稳定性，证明了其在实际生产环境中部署的潜力，能够为CDN运营商带来可观的成本节约和用户体验提升。 3. 重要观点：研究强调了直接利用请求序列中固有的、细粒度的时序依赖关系进行智能决策的重要性，而非仅仅依赖手工设计的启发式规则或静态阈值。
五、 研究的亮点
方法创新性：
实验全面性：研究在四个大规模真实数据集上进行了详尽实验，不仅评估了最终性能，还通过系统的消融实验验证了每个核心组件的贡献，并考察了长期稳定性和系统开销，论证严谨，说服力强。
性能卓越性：LEI在请求命中率和字节命中率等关键指标上取得了显著且一致的提升，同时降低了后端磁盘负载，展示了其强大的优化能力。
六、 其他有价值的内容
论文在“致谢”部分声明，本研究未使用任何生成式人工智能工具。此外，论文获得了中国国家自然科学基金的资助。这些信息增加了研究的可信度和透明度。