Kamino [OSDI'25]

【Title】Kamino: Efficient VM Allocation at Scale with Latency-Driven Cache-Aware Scheduling

Kamino是一个在前端网关/负载均衡服务分配完请求到节点之后具体考虑将请求映射到哪个分配器代理（AA）的框架，核心目标是在实现可忽略的计算和内存开销的同时，最小化整体请求延迟并提高 AA 的资源利用效率。Kamino的idea其实是简单的，但是所有的细节都是non-trivial的,不那么简单的。

Abstract

在虚拟机（VM）分配系统中，缓存重复及相似的虚拟机分配请求及相关解析规则对降低计算成本、满足严格延迟要求至关重要。虽然现代分配系统通过将请求分发给多个分配器代理并利用缓存提升性能，但当前调度器在为新请求分配代理时往往忽略缓存状态与延迟考量。由于缓存命中与未命中的成本差异巨大，且缓存更新涉及较高处理开销，简单的负载均衡与缓存感知机制会导致高延迟。我们推出Kamino——一个高性能、延迟驱动且具备缓存感知能力的请求调度系统，旨在最小化端到端延迟。Kamino采用基于理论的新型调度算法，通过缓存状态的部分指标将每个新请求分配给预估延迟最低的代理。基于大规模生产工作负载的高保真模拟器评估显示，Kamino可实现42%的平均请求延迟降低。我们在大型公有云控制平面中部署Kamino后证实了这些改进：缓存未命中率下降33%，内存使用量减少17%。

Introduction

大型云服务提供商投入数十亿美元建设基础设施，以满足日益增长的各类虚拟机（VM）需求[16]。因此，虚拟机分配系统——负责将VM请求分配至物理硬件的核心组件——被视为云技术栈中的关键环节。

这些系统的设计旨在实现两个主要目标：

• 在严格的延迟上限内（通常在几十毫秒量级）完成虚拟机分配；

• 实现"高质量"的资源分配，这需要综合考虑云服务提供商和客户的多方面偏好；

其中一个典型范例是通过优化虚拟机布局实现服务器高利用率，从而提升基础设施投资回报率（ROI）[16]。

然而这两个设计目标本质上存在矛盾：高质量的资源分配需要综合考虑大量目标与约束条件，这些条件必须基于庞大规模的基础设施（例如数十万台服务器）进行评估。这通常会导致计算密集型处理过程[13, 31, 36]，并在高负载场景下形成潜在瓶颈[6, 16]。

云服务提供商已投入大量精力在保持足够分配质量的同时维持较低的虚拟机分配延迟。标准解决方案之一是在相同硬件基础设施（如可用区）上部署多个分配代理（或称实例）。常见的设计方案是在单个节点（物理服务器）内部署多个此类分配器代理（下文简称AA, allocator agents），并通过多节点部署实现横向扩展[16, 36, 41]。节点内AA扩展充分利用多核并行能力，有效减少了跨节点扩展AA时产生的通信、一致性及资源使用开销。本文重点研究如何为每个传入请求分配合适AA的决策机制。

为了解决这个矛盾，行业普遍采用的方法是使用多个分配器代理（AA）。这就像开设多个“服务窗口”来处理请求，以避免单个窗口排长队，从而降低整体延迟。具体实现分为两个层次：

• 单个节点内：在一台物理服务器上运行多个AA实例。这类似于在一个银行网点里开设多个柜台。

• 跨节点扩展：当单个服务器能力不足时，就使用多台服务器（多个节点）来部署更多的AA。这类似于开设多家银行网点来服务更多客户。

除了采用多分配器代理（AA）之外，另一种降低延迟并提升分配请求处理吞吐量的补充方案是运用in-memory caching。

先进的虚拟机分配器（例如Azure采用的系统）都配备了领域专用的缓存层[16, 41, 43]。然而与传统仅存储数据对象的缓存不同，虚拟机分配器缓存的是结合了完全或部分计算后的资源库存状态（inventory state）、以及针对每种分配请求类型的优选服务器集合的规则组合（a preferred set of servers for each allocation request type）。此外，每个缓存条目大小可能从10MB到100MB不等，这对内存缓存槽的数量形成了严格限制。缓存命中过程包含缓存查找与少量计算的组合操作。相比之下，缓存未命中可能将延迟增加至数百毫秒，这是因为计算和数据访问成本会随分配请求类型的复杂程度产生显著波动。最后，部分虚拟机分配器采用私有AA缓存架构，以此避免并发控制与同步开销[16]。

computational and data access costs

Computational Costs

• 分配算法需要考虑无数因素：客户偏好（如需要特定型号的CPU或GPU）、供应商目标（如提高服务器利用率、降低能耗）、硬件约束（如服务器剩余资源）、软亲和性（如将有关联的VM尽量放在靠近的服务器上）等等。

  • 需要在庞大的服务器库存（“huge inventories”）中进行搜索、排序和优化计算，是典型的NP难问题，非常消耗CPU资源。

data access costs

• 为了执行上述计算，分配器需要获取最新的服务器资源库存数据。这些数据通常存储在分布式系统中（如数据库或其它服务）。

  • 访问这些数据会产生网络通信延迟和磁盘I/O延迟（如果数据不在内存中）。

  • 更重要的是，为了保证分配决策基于的是最新数据（避免把两个VM分配到同一台服务器的同一个核心上），系统可能需要强一致性协议，这又会引入额外的同步和锁开销。

基于分配请求类型的复杂性而有显著变化

• 这是理解延迟差异巨大的关键。不是所有的缓存未命中代价都一样。

• 简单请求：例如，请求一个标准规格的VM，且约束条件很少。分配器可能很快就能在库存中找到一台符合要求的服务器。计算成本相对较低。

• 复杂请求：例如，请求一个大型集群（几十上百台VM），并要求这些VM分布在不同的故障域（Fault Domains）以保障高可用性，同时还要满足特定的网络带宽和低延迟要求。为这种请求寻找一个最优的分配方案需要在庞大的库存中进行极其复杂的搜索和计算，成本极高，耗时自然更长。

现有虚拟机分配器设计的一个关键局限在于请求调度机制与底层缓存机制之间缺乏协同。具体而言，当前最先进的虚拟机分配器仍采用标准负载均衡技术[16, 43]——即使某AA的缓存中并未存储相应请求类型，调度器仍会将请求分配至该AA。这些调度器使用

• 轮询

• 工作窃取

• 均匀随机分配

等简单策略，或

• 采用更复杂的基于哈希的方法在AA间平衡请求

遗憾的是，在生产环境中（需处理数千种请求类型且库存服务器规模达数十万台的情况下），这些策略会导致缓存未命中和计算开销激增，最终造成超额分配延迟。

传统的负载均衡器（如轮询、随机、基于哈希）其核心目标是均匀地分发请求，以防止某些AA过载而其他AA空闲。它们追求的是计算负载的均衡。

• 它们不关心（也不知道）每个AA的缓存里有什么。一个请求可能被随机地扔给一个完全没有处理过此类请求、因此缓存中也没有相关数据的AA。对于这个AA来说，这必然是一次缓存未命中，它必须进行昂贵的全流程计算。

  • 类比：这就像有10个专家（AA），每个专家只记得自己最近处理过的几类问题（缓存）。现在来了一个新问题，调度员（负载均衡器）不看哪个专家擅长这类问题，而是随机抽签决定由谁解答。被抽中的专家如果没遇到过这类问题，就只能从头开始研究。

• 缓存内容的“局部性”与“特异性”

  • 缓存是局部的：每个AA都有自己的私有缓存（如文中所述，为避免同步开销）。AA1的缓存内容与AA2的缓存内容完全不同，它们只包含自己之前处理过的请求类型和解决方案。

  • 缓存是特定的：缓存的内容与AA处理过的请求历史强相关。一个长期处理大型数据库VM请求的AA，其缓存中可能都是相关规则和服务器列表；而另一个处理AI计算VM请求的AA，其缓存内容则完全不同。

  • 传统的负载均衡策略破坏了这种局部性。它无法保证将相同或相似类型的新请求持续地发送给之前处理过该类型请求的同一个AA。

• 有些系统可能会使用更“智能”的基于哈希的策略，例如对“请求类型”进行哈希，将相同类型的请求总是发送给同一个AA。

  这听起来不错，但问题在于：

  • 缓存容量有限：文中提到每个缓存条目很大（10-100MB），因此每个AA只能缓存有限数量的请求类型。

  • 请求类型爆炸：生产环境中有数千种请求类型（不同配置、约束、需求的组合）。

  • 哈希冲突不可避免：当数千种请求类型通过哈希函数映射到有限数量的AA上时，多个不同的请求类型必然会被哈希到同一个AA。这会导致该AA的缓存被频繁地换入换出（Cache Eviction），因为缓存空间不足以同时容纳所有映射到它的请求类型。你刚刚缓存了类型A，下一个来的类型B（也哈希到这个AA）可能就把类型A的缓存挤出去了。当类型A的请求再来时，依然会发生缓存未命中。

另一种思路是借鉴其他领域的设计理念，例如处理器缓存processor caches[26]、内容分发网络（CDN）[48]和storage caching[4]，来为AA设计缓存感知型请求调度方案。一种可行的缓存感知调度策略是将相同类型的请求发送至同一组AA。然而，这种简单的缓存感知调度会引发以下关键挑战：

• 热点集中风险：在某些工作负载中，热门请求若被持续调度至同一AA，会形成处理热点，从而增加队列延迟并推升平均延迟与尾部延迟。

• 虚拟机分配器的特有挑战：其缓存通常采用分层结构——较小的高层缓存存储请求类型信息，而底层缓存内容可能被不同请求类型共享使用。这种架构导致难以预先评估将请求分配给特定AA的最终效果：例如部分命中现象普遍存在，延迟水平会随请求类型、缓存状态及系统负载剧烈波动，且缓存中不同部分的数据更新所需处理时间也存在显著差异

鉴于上述挑战，我们设计并实现了Kamino——一种融合延迟与缓存感知的混合型虚拟机分配请求调度框架，旨在最小化端到端请求延迟。

从宏观架构看，我们为每个AA增设了请求队列，Kamino基于延迟考量将请求分配至特定队列。其底层算法问题可归结为经典延迟最小化在线作业调度问题[5]的广义形式，该问题在理论上以求解难度极高而著称[5,7]。直观而言，我们的问题比经典版本更具挑战性：请求处理时间并非固定值，而是取决于缓存中的信息状态，而这些信息又依赖于调度器先前做出的决策。尽管如此，理论层面的概念化仍使我们能够基于第一性原理设计调度算法。我们提出了一种名为LatCache的新型混合算法，这种延迟驱动的请求调度算法即使仅通过访问部分指标（如各队列中的请求类型及其缓存命中预测），也能实现延迟预估。

第一性原理（First Principles） 指的是从事物的最基本定律、规则或事实出发进行推理，而不是依赖于类比、经验假设或现有惯例。它要求你抛开所有表面的假设和成见，直击问题的本质，然后从这些不可否认的“真理”开始，一步步构建出解决方案。

• 我觉得依然是看成状态机，基于状态机的状态建立算法

LatCache算法的核心关键在于：基于各目标AA队列中请求的预估处理时间，来估算其队列内的请求延迟，并将新请求分配给端到端延迟（排队时间+处理时间）最小的队列。处理时间的估算是通过高效分析当前缓存状态、以及已排队请求在处理过程中对缓存状态的影响而得出的。这使得Kamino能够动态适应任何请求到达模式，同时充分利用AA缓存。

尽管缓存感知的负载均衡在已有研究中已有应用（参见§7），我们方法的关键创新在于：将缓存状态（尤其是缓存命中率）仅视为影响端到端请求延迟的要素之一，而延迟才是我们真正关注的终极指标。因此，我们需要综合不同组件（如缓存和队列）的状态，并充分考虑分层缓存结构的特点，以动态高效地估算请求延迟。

我们通过高保真仿真实验和在Azure生产控制平面的实际部署，对Kamino及LatCache的有效性进行了验证与实现。Kamino的架构保持了虚拟机物理机分配内部逻辑与LatCache调度器的清晰分离，以此隔离前者的频繁修改需求。为维持高吞吐量，我们采用流水线化设计处理Kamino的各阶段操作（如请求分类与队列分配）。

我们将Kamino与当前最先进技术进行对比，包括Azure现役虚拟机分配系统Protean以及广泛应用于其他分布式系统工作负载均衡的一致性哈希方案[47]。基于多区域生产分配轨迹的仿真结果表明：相较于无延迟感知调度器，Kamino实现了平均42%的延迟降低。作为附加效益，LatCache还能支撑高达2倍的吞吐量提升，这一优势在突发负载时段尤为显著。

更具体而言，这些改进的实际意义体现在：

• 尾部延迟的降低确保了资源供给的可靠性，尤其对于数据分析平台、在线游戏和虚拟桌面等延迟敏感型工作负载至关重要。虚拟机分配中的高尾部延迟会阻碍自动扩展流程，导致实例可用性不可预测并降低应用程序性能。

• 缓存未命中率的改善减少了对AA节点的资源需求，这不仅降低了资源争用与通信开销，也减少了分配系统中的冲突与重试操作，从而提升请求处理效率并增强整体系统稳定性。

AA运行于隔离的控制平面节点（与非通用云服务器分离），以此提升可预测性与安全性，并与数百个其他控制平面微服务共享资源。因此，实现资源效率优化（特别是内存效率）具有至关重要的意义。延迟、吞吐量与资源消耗的综合改善使Azure能够在一个可用区内持续处理数十万个虚拟机请求，同时为日益增多的其他控制平面服务释放计算资源。

除虚拟机分配器外，我们相信该方法可扩展至具有可变请求延迟的其他系统，包括日志结构合并树（LSM）、分布式数据库、内容分发网络（CDN）以及微服务架构。我们已在LSM键值存储中开展了初步实验：通过采用以延迟和缓存为核心的管理机制（如Kamino那样考量多层级请求延迟与局部性感知），实验结果显示整体请求延迟得到显著降低（§A.1）。

总结而言，我们的研究成果主要包括以下四个方面：

• 大规模虚拟机分配挑战深度剖析：我们详细分析了海量虚拟机分配请求处理中的核心难题，重点聚焦于延迟与资源消耗相关的关键问题。

• 新型延迟与缓存感知算法（LatCache）：提出了理论严谨的新型请求调度算法，该算法基于对缓存和队列状态的精细化分析实现延迟预估。

• Kamino框架的完整实现：通过设计与实现Kamino框架，我们首先开发了高保真请求调度模拟器，随后在生产可用区成功部署了该调度框架。

• 多维度实证评估：通过 exhaustive 的模拟研究对比多种算法方案，并结合大规模生产可用区的实测数据，全面评估了Kamino的优势与影响。

Background & Motivation

我们首先阐述虚拟机分配的背景知识，进而深入分析在降低虚拟机分配请求延迟、提升资源利用效率以及扩展分配器代理（AA）规模过程中所面临的核心挑战。

Background on VM allocation systems

设计低延迟虚拟机（或容器）分配器对于缩短应用服务实例化时间至关重要。在满足多样化虚拟机/容器部署需求的同时实现这一目标具有决定性意义。当前最先进的虚拟机分配系统（如Protean）与资源管理器（如Omega [36]、Kubernetes [27]、Twine [41]和VMWare DRS [15]）通过以下方式实现该目标：采用过滤谓词或策略来封装分配约束条件，从而将可用资源库存缩减为符合特定请求的候选机器集合。随后，这些系统通过实施指定的偏好规则与优先级策略对候选机器进行排序，最终建立可从中选择目标机器的优选资源池。

基于规则的计算密集型分配方案。Protean等虚拟机分配系统采用基于规则的分配机制，其中每条规则都定义了根据特定分配约束或偏好来筛选和排序可用资源库存的逻辑。这些约束与偏好既可以是用户定义的（如虚拟机类型），也可以是系统内部定义以优化分配策略的。随着平台服务范围的扩展和分配策略的演进，可通过添加新规则来适应额外的约束条件与偏好需求。评估并满足分配请求及其约束条件是一个计算密集型过程，包含以下步骤：

• 首先根据优先级筛选和排序相关规则（其中约束性规则优先处理）；

• 随后将每条规则应用于资源库存，生成满足特定约束的机器集合；

• 接着计算这些集合的交集，并运用偏好规则进行排序，最终得到按质量与偏好联合排序的候选机器集合，从中选择排名最高的机器完成分配。

问题求解：输入 - 推理 - 输出

分层缓存的优势。为加速分配过程并降低计算成本，最先进的集群管理系统普遍采用缓存技术[16, 36, 41, 43]。其缓存设计的核心依据是：时间相近的提交请求在约束条件层面呈现局部性特征。以Protean为代表的现代虚拟机分配器使用缓存槽（逻辑缓存条目）来最小化重复计算。

• 具体而言，Protean采用二级分层缓存架构：顶级缓存（快速路径）用于处理完全相同的分配请求，底层缓存（慢速路径）则用于处理非完全相同但具有部分相同特征或约束的请求（例如请求相同规格的虚拟机但优先级不同）；具体示例参见表1，详细机制见§4.2.3。快速路径缓存命中的规则计算成本显著低于慢速路径命中。最终，快速路径降低了相同请求的命中延迟，而慢速路径降低了非相同请求的未命中延迟。此外，每个缓存槽的内存大小可变（通常从10MB到数百MB不等），其容量取决于规则复杂度，这也限制了单个AA可预留的缓存槽 (cache slot) 数量。

表1：采用R1、R2双规则系统的分层缓存机制示例（其中R2规则仅依赖请求的a属性）。每个请求包含a、b两个属性，cons(·) 函数表示给定请求对应的整合节点列表。当新请求到达时，若其整合节点列表及R1、R2规则的评估结果未存在于缓存中，系统会将其载入缓存。

分配器代理(AA)的集群级与节点级扩展。要实现每秒处理数千个分配请求的大规模运营，扩展分配器数量至关重要。扩展既能提升吞吐量，更能通过增加缓存命中率和减少请求等待时间来降低延迟。

Protean采用两级扩展机制：

• (1) 在跨多个集群分布的节点上部署多个分配器代理(AA)；

• (2) 在单个节点内运行多个AA以利用多核并行能力。

对于多节点AA部署，前端负载均衡器会将请求分发至包含一个或多个AA的特定节点。在节点内部，多个AA形成资源池，池中的代理在空闲时会从全局队列头部拉取并处理请求。

这些分布式AA采用乐观并发机制运行，无需频繁同步。然而并发操作可能导致资源分配冲突，因此AA在完成请求评估后，会以事务形式将分配结果提交至全局资源库存存储以确立库存状态(inventory store)。库存存储会检测冲突，促使失败请求返回AA进行快速重评估。成功分配的结果将通过资源库存发布订阅服务进行广播，更新所有AA的状态。

Q? What is "inventory store" ?

尽管采取这些措施，跨节点部署AA仍会增加通信开销、冲突解决成本，并导致单节点资源利用率不足。因此，在单个系统内增加AA数量对充分利用多核CPU等资源、降低分布式AA带来的通信与同步成本具有关键意义。单个节点内可部署的AA数量取决于可用CPU核心数、缓存专用内存容量以及其他管理服务所占用的资源。

在扩展分配器代理(AA)规模时，共享缓存的管理成为关键挑战。虽然跨AA共享缓存能提升总容量并减少冗余，但会带来显著缺陷：

• 首先，共享缓存会产生沉重的锁竞争与同步开销，限制多核CPU效率并抵消扩展优势。

• 这些挑战在分层缓存架构中更为严峻——快速路径与慢速路径的不同操作特性（二者缓存命中/未命中成本差异显著）会进一步加剧资源争用。

• 第三，共享缓存需与共享数据库定期同步，增加延迟与通信成本。相较于私有缓存，这些问题导致共享缓存在高吞吐场景下效率更低且更易阻塞，最终制约系统扩展性与性能。

  据我们所知，当前最先进系统均未采用跨AA共享缓存方案。例如Protean将缓存内存划分为槽位并分区分配给各AA以实现最大并发度，但减少单AA缓存槽数量以增加AA实例数会导致缓存未命中率上升和请求扩展能力下降（参见§2.2节）。

  并发往往带来一致性问题，所以需要锁和同步。但如果把缓存分区slot就可以避免这个问题。但这个的背景是扩展AAs,共享缓存容量不变的情况下，每个AA能够分到的cache slot会减少，从而miss rate上升。

   

请求分配与调度算法。请求调度策略在将传入请求分配给各分配器代理(AA)以实现延迟降低、吞吐最大化或资源利用效率等目标方面起着关键作用。尽管大型云服务商通常缺乏虚拟机分配请求调度方法的公开文档，但诸如Protean等系统采用轮询等无缓存感知的调度策略。虽然这种方案能以简单通用的方式分发请求，但其缺乏缓存感知的特性可能导致次优性能。类似策略也被Kubernetes等广泛部署的系统用于容器Pod分配器调度[27,29]。缓存感知型调度策略可利用各AA缓存状态与请求类型信息，将特定请求类型分配给对应AA以最大化缓存命中率并降低请求延迟。先前在处理器缓存、内容分发网络、网页缓存及分布式数据缓存等领域的研究[9,25,47]，通过依赖缓存亲和性及采用动态机制来处理潜在负载不均与适应工作负载变化以优化性能。然而对于虚拟机分配场景，此类策略可能导致显著更高的延迟（参见§6.2）。相较之下，我们的设计主要采用融合缓存感知的延迟中心化方案，通过延迟预估来实现更低延迟。

• 直观而言，该方法可视为基于各分配代理总"工作量"的负载均衡（而非传统基于队列长度或请求类型的负载均衡）。

  • 基于队列长度： 将请求分配给当前待处理请求最少的AA；缺陷：忽略不同请求的计算复杂度差异。

  • 基于请求类型：固定将某类请求绑定到特定AA（如Kubernetes的Pod亲和性调度）；缺陷：无法动态应对突发负载变化（见原文§6.2实验数据）

Evidence from production

为剖析当前最先进虚拟机分配器的技术挑战与局限，我们首先对Protean系统的延迟特性进行量化表征，继而评估其资源利用效率缺陷。本项研究基于50余个分配器节点的生产环境追踪数据（每个节点包含24小时完整请求记录）开展分析。

2.2.1 Need for latency-driven scheduling

我们对大规模生产环境追踪数据中延迟特性的综合研究，充分证明了构建延迟驱动型调度框架的必要性。

• 【Observation 1】缓存命中与未命中的延迟时间在不同类型的请求间存在显著差异。

与传统数据缓存系统不同，虚拟机分配查询中缓存命中与未命中的延迟会随不同请求类型的复杂度呈现显著差异。图1展示了单个分配器节点观测到的命中/未命中延迟分布（此处的命中与未命中均指缓存顶层）。某些请求类型的缓存命中延迟甚至高于其他请求的未命中延迟，这与"命中必然快于未命中"的传统假设相悖。这种波动性主要源于两个原因：

• 其一，如前所述，缓存采用分层架构，请求的约束条件和偏好规则可能导致命中时仍需部分重计算，或未命中时需全量重计算。我们的分析显示不同请求类型的命中/未命中延迟差异最高可达5倍。

• 其二，分配请求的突发性会因库存更新而阻塞并延长请求处理时间（无论命中与否），进一步加剧延迟波动。

2.2.2 Need for cache-aware, latency-driven scheduling

缓存感知机制对于通过将相似请求分配到相同AA以利用局部性至关重要。假设一个场景中存在两种请求类型（类型1与类型2）和两个AA，每个AA的缓存槽仅能存储一种请求类型，且缓存策略规定AA只保留最后处理的请求类型。若采用轮询等无缓存感知的调度算法，在请求序列为1, 2, 2, 1, 1, 2, 2,...时可能产生0%的缓存命中率；而将特定请求类型固定分配给对应AA的缓存感知调度，则能实现100%缓存命中率、最小化队列长度并显著降低总延迟。

实际上，如§6.2中的图6所示，简单调度策略的效果明显不足：轮询分配和随机分配的尾部延迟分别比Protean（本质上是纯工作窃取策略）高出约30%和约60%。

• 【Observation 2】延迟驱动型缓存感知调度对处理动态工作负载至关重要。

遗憾的是，仅依靠请求固定绑定或一致性哈希等缓存感知策略并不足够。如§2.2.1所述，在高负载场景下，纯缓存感知方法会因特定请求的突发流量显著影响各AA间的请求类型分布。相比之下，有效的延迟驱动型调度器能动态适应延迟变化，并在必要时将请求分流至其他AA（即使这会牺牲局部性优势）。

2.2.3 Allocator scalability challenges

增加分配器代理(AA)的数量可通过利用多核CPU和可用内存来降低请求等待时间与延迟，同时确保足够的吞吐量。然而，跨节点甚至节点内部扩展AA可能导致资源效率下降或延迟增加。

• 【Observation 3】内存与CPU使用之间的资源失衡限制了AA的数量。

增加分配器代理(AA)数量以降低延迟并提升吞吐量的方案，面临着资源利用率失衡的挑战。如表2所示，多数节点呈现内存使用率高而CPU资源利用率不足的特征。这种失衡主要源于两个因素：首先，分层式请求评估缓存需要占用大量内存——顶层缓存槽需存储特定请求类型的完整可行资源清单，底层缓存槽则需保存各约束条件的可行集；其次，如前文所述，为最大化并行性并避免同步瓶颈，每个AA都维护私有缓存而非共享缓存。基于这些限制，我们的分析系统即使在最大规模可用区内，也将单节点AA数量上限设为四个以避免内存超限。虽然跨节点扩展AA数量是潜在解决方案，但这会加剧CPU资源浪费及通信与同步开销。

• 【Observation 4】单纯通过分割缓存槽来增加分配器代理(AA)数量的方案会影响延迟性能。

在节点内部增加分配器代理(AA)数量的另一种方案是进一步划分缓存内存总量。然而，减少单个AA的缓存容量会导致更多缓存未命中，进而增加延迟。为验证这一点，我们通过模拟Protean系统，采用全天请求数据对比不同AA数量下的性能表现。实验从基准配置（4个AA）开始，在保持总缓存容量不变的前提下增加AA数量（相应缩减各AA私有缓存空间）。如图2所示，当AA数量增至6-8个时，队列等待时间缩短，平均延迟较基准配置有所改善；但继续增加AA数量会因单个缓存过小导致命中率下降，加之缺乏缓存感知调度机制（AA indiscriminately pull requests off the node queue, failing to exploit locality across the AAs’ caches），使得处理时间显著增加。

上述四项观察结论共同驱动了Kamino延迟驱动型缓存感知算法及其支撑系统的设计实现。

Kamino Overview

接下来我们将从高层次概述虚拟机分配系统，重点聚焦于分配路径的设计逻辑。关于具体架构实现的详细说明，将在第5章节展开阐述。

系统概述。Kamino旨在通过"并发执行"及"延迟与缓存感知调度机制"实现虚拟机请求延迟最小化（参见图3）。每个分配节点部署多个并行运行的分配器代理(AA)，其核心职责包括

• 规则评估

• 虚拟机至物理机的分配决策。

AA采用分层式私有缓存架构进行规则评估，并维护待处理请求队列。此外，AA可实时访问资源库存中物理机的动态数据（包括CPU核心数、内存等可用资源）。

请求分配路径。当请求进入系统时，网关/负载均衡器将其路由至分配器节点。

• 节点内部基于历史延迟数据及各AA的当前队列与缓存状态计算请求的预估延迟，

• 随后将请求分配给预估处理完成时间最早的AA。

• 被选中的代理根据请求特征运行规则链，并尽可能利用其分层缓存进行评估，最终生成按规则优先级排序的候选机器列表。

• 该VM请求将被发送至列表中最优先级的机器之一，分配决策将提交至中央部署存储库，并通过更新操作同步至所有AA。

LatCache Agent Assignment Algorithm

我们现在将聚焦于核心研究工作：通过最优利用内存（即缓存）与计算资源，以降低平均及尾部请求延迟为目标，将传入的虚拟机请求导向各分配器代理(AA)。由于每个分配器节点均独立运作，我们重点关注单节点内如何选择AA代理来处理特定VM请求，即代理分配器算法的设计。

Agent Assignment Task

我们引入以下任务描述，该描述囊括了当前场景的核心要素，并将作为设计分配算法时的指导框架。

一个任务实例包含多个分配器代理(AA)以及待处理的异构请求序列。所有AA配置相同且并行运行，每个AA仅能同时处理一个请求且不允许抢占式操作。请求不可丢弃，每个AA均拥有容纳待处理请求的充足队列空间，队列中的请求按先进先出(FIFO)顺序处理。

每个分配器代理(AA)均配备容量受限的私有缓存，该缓存会显著影响请求处理时间。在高层次上，缓存的当前状态以一种非平凡的方式影响处理时间：它会部分减少处理时间，其程度取决于请求中有多少内容被缓存（即哪些规则计算被缓存，参见 §2.1），并且缓存的相同部分（即规则）可能对不同的请求都有帮助。此外，即使在相同的缓存状态下，请求的处理时间也可能随时间发生变化。这是因为对缓存规则的计算依赖于自上次更新以来库存的变化，而库存变化又取决于系统的负载。在这里，我们对其中一些细节进行了抽象，并将读者引导至 §4.2.3，其中提供了关于分层缓存的更低层次的细节，以及缓存状态如何精确地影响处理时间。每个 AA 还运行一个独立的缓存策略，用于决定当缓存已满时哪些数据会被驱逐。通常，在请求被 AA 处理后，它会被放入该 AA 的缓存，但这并不是一个必须的假设。

当一个新请求到达时，它需要立即被分配给某个 AA。目标是将到达的请求分配给 AAs，以最小化请求的平均延迟，即完成时间（包括等待时间）减去释放时间。

图 4 给出了代理分配任务的示例。在这个例子中，有两个 AA，每个都有一个简化的单槽缓存，以及两种请求类型（绿色和橙色）。左图显示了在时间点 t1 时 AAs 的缓存、队列以及 AA 2 的当前执行状态，此时一个新请求到达，它需要被分配给某个 AA；在这种情况下，它被分配给 AA 1。中图显示了在时间点 t2 的状态，此时 AA 2 完成了它的第一个请求，并将开始处理队列中的请求；在这个例子中，AA 2 的缓存已在第一个请求完成后更新。右图显示了在更晚的时间点 t3 的状态。需要注意的是，AA 2 的第二个请求处理时间更短，因为在它开始处理时（时间 t2），其类型已存在于缓存中。同时还要注意，AA 1 的缓存由于完成了绿色请求而得到了更新。

直接这么看其实有点抽象的，下面会更具体一点

Latency-driven Cache-aware Assignment

Basic algorithm

我们现在描述 LatCache，这是我们为该代理分配任务提出的算法。由于其以延迟为驱动，做出决策的主要组成部分是对传入请求如果被分配给某个 AA 时将产生的延迟进行仔细估计。

为了进行这种估计，我们首先将延迟分为三个独立的组成部分：处理时间、排队时间和剩余处理时间。处理时间是指在某个 AA 上开始处理后，预计处理传入请求所需的时间。排队时间是指预计处理该 AA 队列中所有请求所需的时间。剩余处理时间是指该 AA 完成当前正在处理的请求所需的剩余时间。某个请求在一个 AA 上的预计延迟是通过将这三个部分的估计值相加得到的。

需要注意的是，这三个组成部分都以非平凡的方式依赖于所考虑 AA 的缓存动态。

• 例如，请求的处理时间并不取决于它当前是否（完全或部分）存在于该 AA 的缓存中，而是取决于在它开始处理时是否会存在于缓存中。而这又取决于该 AA 当前的缓存、其队列中的请求以及它所使用的缓存策略。

• 同样需要注意的是，AA 的排队时间也存在类似的影响，它取决于队列中请求的处理时间，而这些处理时间又取决于每个请求在被处理时其信息在缓存中存在的程度。因此，该算法的关键步骤是获得对这三个延迟组成部分的合理的、基于缓存感知的估计。我们将如何估计这些组成部分的描述推迟到 §4.2.2。

一旦完成了对每个 AA 上请求延迟的估计，LatCache 就会将该请求分配给具有最低预计延迟的 AA；

LatCache 的设计解决了前一节中强调的挑战。首先，由于其以延迟为驱动，它对请求到 AAs 的分配执行自适应负载均衡，而不考虑传入请求的身份（与 §2.2.2 中讨论的请求固定策略形成对比）。实际上，我们证明了该算法几乎能够完美地保持 AAs 的队列等待时间平衡；直观地说，如果某个 AA 的队列变得过长，这一情况会被纳入算法的延迟估计中，从而在未来的请求中选择另一个 AA。

定理 1（LatCache 的负载均衡）。考虑具有完美延迟估计的 LatCache 算法。那么，在任何时刻，它都能保证任意一对 AAs 的队列等待时间之差不超过 maxProcTime，其中 maxProcTime 是最大的请求处理时间。此外，没有任何调度器能够保证在所有时刻，对于任意一对 AAs a,a′a, a′a,a′，它们的队列等待时间差严格小于 maxProcTime。

我们注意到，完美延迟估计这一假设是可以放宽的，其提出仅是为了简化界限。此外，通过合理的、具备缓存感知的延迟估计，LatCache 还能够促进相似请求的共同定位，这应当会带来更高的缓存命中率，从而降低处理时间：在设计上，LatCache 只有在后者具有更差延迟（例如由于显著更长的排队时间）的情况下，才会倾向于选择一个在缓存中没有（或较少有）该请求的 AA，而不是选择一个缓存中已有该请求的 AA。

Cache-aware latency estimation

LatCache 的这一理想行为依赖于算法能够对三个延迟组成部分进行合理估计，我们现在来讨论这一点。延续之前的讨论，这里有两个关键挑战：（1）由于缓存状态在每个请求被处理时可能发生变化，因此尚不清楚当前请求和排队请求是否会（完全或部分）存在于某个 AA 的缓存中；（2）命中和未命中延迟的估计误差可能会累积（例如在排队时间的估计中），并导致极度次优的决策。考虑到这些因素，延迟组成部分的估计方法如下：

• Processing time

  • 这是需要估计的主要组成部分，并用于计算其他组成部分。为了估计传入请求在 AA a 上的 processingTime(a)，我们采用乐观假设，认为当该请求在 a 上被处理时（如果被分配给它），缓存仍将包含其当前的所有内容（即没有任何内容被驱逐），并且还将完全包含当前在 a 队列中的所有请求（我们称之为“增强缓存状态”）。然后，估计的 processingTime(a) 是这个“增强缓存状态”和当前请求特征的函数（在我们的场景中如何计算的具体细节见 §4.2.3，算法 2）。

  • 我们注意到，只要 AA 队列中不同类型请求的数量相对于缓存能够容纳的类型数量较少（在实际的虚拟机分配中正是如此），这种乐观的缓存状态预测就相当准确。特别是，我们测试了一种模拟未来缓存状态的替代估计方法，但并未发现估计质量有显著提升。

• Queuing time

  • 接下来，某个 AA 的 queueTime(a) 是通过对其队列中每个请求的处理时间进行估计得到的，采用上述策略。这个过程不需要遍历整个队列：当一个请求被加入 AA a 的队列时，该请求的估计 processingTime 会被加到当前的 queueTime(a) 上；当一个请求出队时，其估计 processingTime 会被减去。需要注意的是，通过在出队时减去估计的处理时间，而非实际处理时间，可以限制误差的累积：一旦请求出队，其处理时间估计误差对队列时间的影响就被消除。

    • 简单来说，即增量更新 队列时间：每当请求入队就加上它的估计处理时间，出队就减去它的估计处理时间。这种方法天然适合处理缓存依赖的动态处理时间，而且不会累积长期误差，非常适合实时调度和 LatCache 的延迟驱动策略。

  • Q : 为什么这里不用 Little's Law ?

    • 队列时间依赖于缓存状态: Little’s Law 假设系统在统计意义上是稳定的（平均到达率 λ 和平均排队时间 W 是稳定的），并且请求处理时间是独立的。但在这里，每个请求的处理时间取决于 AA 的缓存状态，而且缓存状态会随时间和队列内容变化。这导致队列时间不能简单地通过平均到达率和平均处理时间计算得到。

    • 请求处理时间动态变化: 每个请求在队列中的等待时间不仅取决于它前面的请求数，还取决于每个请求在被处理时的实际缓存命中情况。由于缓存命中率随队列和缓存策略动态变化，单纯用 W=L/λ 很难准确预测每个请求的等待时间。

    • 系统非平稳、请求到达可能不均匀

    总结来说，Little’s Law 更适合长期平均分析和独立同分布的处理时间，而这里的 AA 系统具有缓存依赖的动态处理时间和非平稳队列，所以作者选择了基于每个请求的增量估计方法，而不是使用 Little’s Law。

• Remaining processing time

  • 最后，某个 AA 的 remainingProcTime(a) 的估计基于 AA 更新的 start 和 proc_time 信息：每当 AA 开始处理一个请求时，它将 start 设置为当前时间，将 proc_time 设置为基于当前缓存状态（而非“增强缓存状态”）的估计处理时间。利用这些信息，如果 AA a 当前正在忙碌，则在时间 t 的 remainingProcTime(a) 估计为 $max(0,start+proc\mathrm{\_}time-t)$$max(0,start+proc\_time-t)$​否则，估计为 0。图 5 展示了这些估计方法。

Fig.5 LatCache 延迟估计示意图。一个新的绿色请求（用绿色方格标记）被考虑分配到两个 AA 中的一个，每个 AA 只有一个缓存槽。非实心颜色表示估计值。

 

Hierarchical cache structure and processing time computation

接下来我们讨论基于规则的分配和缓存结构，这对于在 Kamino 中计算预计处理时间至关重要。

• 基于规则的分配

  • 我们的系统使用基于规则的分配，如 §2.1 所讨论的那样。对请求进行规则评估会根据指定的约束或偏好返回当前库存的过滤（排序）列表（例如，有足够空闲内存来容纳请求的机器列表）。每条规则仅依赖于请求的部分特征；在这些特征上具有相同值的请求会产生相同的评估，因此在该规则下被视为等价。为了完成一个请求，需要评估所有规则并合并列表，然后将请求放置在最终列表中排名靠前的某台机器上。这些步骤由处理该请求的 AA 执行。

  • 过滤 排序 TopK 再选一个

• 缓存结构。

  • AA 中的缓存用于加速这些步骤。我们采用了两级分层缓存：顶层（快速路径）存储（等价）请求的合并机器列表，底层（慢速路径）存储等价请求的规则评估结果（相对于具体规则）。后者允许“部分缓存命中”，可以惠及更多请求，因为相对于单条规则，更多请求是等价的，而相对于合并评估则不然。示意见表 1。

  • 由于规则评估及其合并结果依赖于当前的库存状态，即使存在于缓存中也需要进行更新；也就是说，缓存命中和未命中都会增加处理请求的延迟。未缓存的规则评估（规则未命中）需要从头计算，而缓存的规则评估（规则命中）只需根据自上次更新以来库存的变化进行增量更新；这种增量更新比从头计算要快得多。如果某个请求的合并评估存在于顶层缓存中（命中），那么它所依赖的所有规则都会被更新，更新结果会插入到合并结果中或从中移除。我们注意到，当一个合并结果存在于顶层缓存中时，它所依赖的所有规则都会固定在底层缓存中，即全部为规则命中。

• 处理时间计算

  • 给定此缓存结构，算法 2 描述了我们对某个请求 req 在指定 AA 上处理时间的估计。该过程接收的输入包括 AA 的“增强缓存状态” augCache（如 §4.2.2 所定义）、用于顶层缓存命中处理时间的估计值 estimate hit，以及包含每条规则的规则命中和规则未命中时间估计的向量 rule-hits 和 rule-misses。这些输入估计可以例如通过历史数据计算，详见 §5。如果请求在 augCache 中顶层命中，其估计延迟仅为 hit。在顶层未命中的情况下，我们会基于 augCache 底层存在的规则考虑“部分命中”。

Supplement

System Implementation

我们描述了在 Protean 系统中实现的 Kamino 请求调度框架的详细内容，并强调了实现过程中的一些实际挑战。

Overall system organization ：Protean 系统的一个逻辑实例负责处理某个zone or region的所有请求。该系统由一组无状态 AA 组成，这些 AA 依托持久化的放置存储来做虚拟机放置决策。每个 AA 使用独立的线程和私有的内存状态及缓存，将虚拟机请求分配到库存中合适的服务器上。它使用指定数量的缓存槽来限制内存使用。多个 AA 被分组在分配节点的一个进程中，并且可以部署多个节点以满足系统的峰值需求。

AA 遵循乐观并发模型：代理基于其（可能过时的）库存视图做出放置决策，并将每个放置结果持久化到放置存储中。由于 AA 的视图可能过时，放置存储会拒绝无效的结果，以便请求可以重试。虚拟机删除操作也会持久化到放置存储中。AA 通过发布-订阅平台了解放置存储的更新以及其他相关库存更新，例如与服务器健康状况和能耗相关的更新。作为一种优化，在分配节点内由 AA 做出的放置决策会通过快速内存传输在它们之间共享。图 3 展示了整体系统架构。

Kamino 请求调度框架。前端网关/负载均衡服务接收请求并将其路由到分配节点，但 Kamino 负责将请求映射到节点内的 AA。Kamino 的目标是在实现可忽略的计算和内存开销的同时，最小化整体请求延迟并提高 AA 的资源利用效率。为此，Kamino 被实现为 AA 自身运行的进程的一部分，从而避免了任何进程间通信开销。此外，我们以计算高效的方式设计了调度逻辑，使每个请求的开销仅为微秒级，远低于请求延迟（几十到数百毫秒）的数量级；因此，调度器对总延迟的开销可以忽略不计。另外，为做出调度决策所需的较慢时间尺度的计算在请求处理关键路径之外进行，因此不会引入任何相关的计算开销。

Kamino 由

• 请求分类器（Request classifier）

• 代理选择器（Agent selector）

• 延迟估计器（Latency estimator）模块组成。

  请求分类器和代理选择器在关键路径中处理每个请求，而延迟估计器则在关键路径之外运行。下面我们将描述这些模块。

• 请求分类器（Request classifier）

  • 到达节点的请求会在队列中等待，直到请求分类器的一个实例可用以处理它。请求分类器根据与请求相关的规则以及这些规则依赖的请求特征（参见 §2.1）计算请求的等价类键（equivalence class key）。该键唯一标识一类在分配逻辑上彼此等价的请求。换句话说，每个键表示一种请求类型，并确定某个 AA 是否对该类型具有缓存的合并结果。请求分类器将计算得到的键附加到请求元数据中，并将请求排入队列以供进一步处理。该框架允许请求分类器（以及代理选择器）模块存在多个实例，以便并发处理请求，但在实际中仅需一到两个实例即可，因为这些模块的处理延迟与 AA 的处理延迟相比可忽略不计。

• 代理选择器（Agent selector）

  • 代理选择器。每个 AA 都有自己的私有队列，用于存放待处理的请求。代理选择器将每个请求分配到某个 AA 的队列中。一旦请求被分配到队列，该分配就不会更改。该模块实现了核心请求调度算法 LatCache。如 §4.2 所述，该算法需要几个输入：

    • 它需要顶层缓存命中时间以及规则的命中和未命中时间的估计值。这些由延迟估计器模块提供。

    • 它需要检查传入请求类型是否已缓存于某个 AA，或是否已经在其私有队列中排队。代理选择器通过请求类型的键探查 AA 的缓存以检查其是否被缓存。作为每个代理队列元数据的一部分，它维护了一个 <请求类型键, 数量> 的映射，用于队列中的请求。该映射用于检查某个请求类型是否已存在于队列中，并在请求入队或出队时更新。

    • 它需要检查代理是否忙碌。代理选择器保存每个代理最近出队的工作项的引用，并通过该工作项探查代理是否忙碌。

• 延迟估计器（Latency estimator）

  • 延迟估计器。该模块负责估计命中时间和未命中时间。在最简单的形式下，它可以根据预设的服务配置提供命中或未命中的估计时间。然而，更实际的实现是在每个分配节点上作为后台任务运行，跟踪命中和未命中时间，并定期生成它们平均值的更新估计。最新的估计不仅会发送给代理选择器，还会被持久化，以便在进程重启时有一个良好的初始估计。虽然我们仅使用命中和未命中时间的粗略集中趋势估计，但 LatCache 仍然能够做出良好的分配，并在相关指标上带来显著改进（见 §6.4）。

• 缓存管理策略

  • AA 采用混合缓存驱逐策略——当缓存已满时，使用标准的 LRU 替换策略驱逐对象，或者当对象达到一定年龄时进行驱逐。基于年龄的驱逐使我们能够在低负载期间减少代理的内存占用。

Evaluation

我们进行了大量实验，通过高保真模拟器和生产系统评估 Kamino。模拟器实验使用来自生产环境的真实追踪数据，涵盖不同的地理区域。我们的实验旨在解决以下问题：

• Kamino 及其以延迟为驱动的 LatCache 算法是否能够相较于标准且广为人知的算法基线降低虚拟机分配请求的延迟？

• LatCache 在减少缓存未命中和整体缓存内存消耗方面的效果如何？

• LatCache 在不同负载、缓存大小和 AA 数量下的表现如何？

• LatCache 算法的优势是否能够在生产规模的系统中得到体现？

Workloads and Methodology

我们的模拟使用了六个来自不同区域高流量分配节点的真实追踪数据。这些追踪涵盖了多样化的唯一请求类型，数量在 500 到 1700 之间。此外，某些区域的请求率和突发性明显高于其他区域。每个追踪覆盖 24 小时的时间范围，包括所有虚拟机请求，并提供诸如请求 ID、到达时间和请求特征等信息。追踪还包含每个请求的实际处理时间信息，用于模拟命中和未命中时间。我们还在所有生产区域部署了包含 LatCache 的 Kamino，并在部分具有代表性的区域中测量性能。

Effectiveness of LatCache on Latency

我们首先使用模拟器来分析 LatCache 对降低平均和尾部虚拟机分配请求延迟的影响。我们将其与最先进的虚拟机分配器 Protean 所使用的负载均衡算法进行比较。同时，我们还将其与经典的无缓存感知负载均衡算法（随机分配和轮询）进行比较。最后，我们将其与一种缓存感知解决方案进行比较，该方案使用一致性哈希分配，并辅以工作窃取以减少热点 [47]。因此，我们将 LatCache 与以下方案进行比较：

• Protean with a shared queue.

  • 这在每个分配节点上包含一个单独的 FIFO 队列，用于接收所有请求，当 AA 空闲时从该队列中获取请求。这是 Protean 之前使用的算法.

• Random assignment (Random).

  • 将传入请求均匀随机地分配给其中一个 AA。

• Round-Robin. Assign the incoming requests to the AAs in a Round-Robin fashion.

• Hash+WS.

  • 该方法使用一致性哈希加工作窃取策略（consistent hashing + work stealing），在其他系统中用于确定数据位置和任务执行 [47]。请求被分配到某个 AA 的方式是对请求特征进行哈希计算，确保具有相同缓存对象的请求被分配到同一个 AA [21, 32]，从而促进数据局部性并减少缓存复制。此外，当某个 AA 空闲时，它会从队列最长的 AA 中窃取一个待处理请求（如果有的话），这有助于减少由请求分布不均引起的热点问题。

不幸的是，其他大规模虚拟机分配器 [36, 41] 的调度算法未公开文档化，这使我们无法重现和评估它们。我们还评估了 LatCache 的两个版本：除了 §4 中描述的 LatCache-rule 算法外，我们还考虑了变体 LatCache-request，该算法对请求的处理时间进行更简单的估计，仅基于该请求是否存在于指定 AA 的顶层缓存中，即在顶层未命中的情况下，不像算法 2 那样查询底层缓存中各个规则的存在情况，而是假设它们都不存在于底层缓存中。其主要优势在于，它需要的缓存查询更少且更简单（即仅查询单层缓存）。在此分析中，我们将每个节点上的 AA 数量固定为 4，以匹配当前的生产系统。我们还根据生产配置预留总缓存内存（最多占节点总内存的 58%）；在 §6.6 中，我们将在模拟环境中改变这些参数。

图 6 展示了不同算法相比基线 Protean 在平均延迟和第 90 百分位尾部延迟上的百分比改进情况。标准负载均衡算法 Random 和 Round-Robin 的平均性能比基线差约 20%。缓存感知的 Hash+WS 算法，通过促进请求的共同定位加上简单负载均衡，平均延迟仅提高 4.4%，且方差较高，而尾部延迟提高 9.1%。相比之下，我们的 LatCache-request 和 LatCache-rule 算法在平均延迟和尾部延迟上相较于其他所有算法均有显著提升，相比基线 Protean 尾部延迟提高超过 50%。

值得注意的是，轻量级的 LatCache-request 与 LatCache-rule 的表现相当，尽管在处理时间估计过程中忽略了底层缓存内容。

虽然请求分配延迟是我们的主要指标，但我们的算法在吞吐量方面也表现出优势，尽管不如延迟改善那么显著。然而，在请求突发期间，我们始终观察到相比 Protean 吞吐量提升约 2 倍。图 7 绘制了在请求突发窗口中各算法的吞吐量曲线（为清晰起见，Random、Round-Robin 和 LatCache-request 被省略）。

Explaining why LatCache works well

表 3（第二列）显示了各算法的顶层缓存命中率。LatCache-rule 和 LatCache-request 达到最高的命中率（约 94%），显著高于缓存友好的 Hash+WS（约 87%）以及无缓存感知的 Protean、Random 和 Round-Robin（约 81%）。这验证了 LatCache 在促进数据局部性方面的优越能力，这是利用当前和预测缓存状态进行精确延迟预测的结果。

接下来，图 8 展示了各算法平均请求延迟的分解，包括在 AA 队列中的等待时间和请求处理时间。LatCache 算法的处理时间最短，这归功于其高缓存命中率。然而，LatCache 延迟改进的主要部分来自等待时间的大幅减少。等待时间降低的两个主要原因是：1）较高的命中率对队列中的多个请求产生叠加效应，从而加快了处理周转；2）通过精确延迟预测实现的延迟驱动设计，在各 AA 之间实现了有效的请求负载均衡，如定理 1 所支持。这突显了将延迟驱动调度与缓存感知结合的优势。

Estimation accuracy and its impact

如前所述，可能影响总延迟估计质量的两个主要不准确来源是：(1)（顶层）命中和未命中事件的预测；(2) 对请求的单个命中和未命中时间的估计。我们现在量化这些估计的准确性及其对 LatCache-rule 分配质量的影响。

首先，我们使用增强缓存状态对命中/未命中事件进行的乐观预测非常准确（在两个缓存层级上的准确率为 99.1%）。鉴于命中时间显著低于未命中时间（平均未命中/命中时间比：5–10）且命中/未命中预测直接影响队列延迟估计，这一准确度对于实现有效分配至关重要。

关于命中和未命中时间的估计，我们的平均预测误差为 29%。虽然误差不小，但将这些估计与准确的命中/未命中事件预测结合使用，仍然能做出良好的分配决策：LatCache-rule 为 91.9% 的请求选择了最佳分配器（最佳分配器 = 对该请求实际总延迟最低的分配器）。即使未选择最佳分配器，调度决策也几乎是最优的——所选分配器与最佳分配器的总延迟百分比差异平均仅为 2.3%。为了更好地理解这些数字，一个naive的 LatCache-rule 版本，如果忽略规则级缓存、未来命中预测以及分配器的剩余处理时间，仅能在 65.4% 的情况下选择最佳分配器，其导致的总延迟甚至可能是最佳分配器的 2 倍。

我们注意到，确实可以使用更复杂的方法来估计命中和未命中时间，例如应用机器学习技术 [12]。然而，我们观察到其附加价值并不显著。为了量化可能的收益，我们运行了使用完美命中/未命中时间预测的 LatCache-rule，观察到尾部分配延迟仅额外改善了 1.1%（相比之下，我们算法的两个版本相较基线均改善了约 50%）。我们得出的结论是，相对绝对的命中和未命中时间预测，更重要的是预测实际的命中/未命中事件，以及捕捉分配过程中的关键元素，特别是分层缓存的动态（参见 §4.2.2-4.2.3）。最终结果是，Kamino 的调度器具备简单而高效、稳健的延迟估计能力，从而做出接近最优的分配决策。

"相对绝对的命中和未命中时间预测，更重要的是预测实际的命中/未命中事件，以及捕捉分配过程中的关键元素，特别是分层缓存的动态（参见 §4.2.2-4.2.3）"

Reduction in Memory Footprint

表 3 显示了各算法使用的平均缓存内存大小，并相对于基线 Protean 进行了归一化。所有无缓存感知算法（Protean、Random 和 Round-Robin）的内存占用非常相似。相比之下，缓存友好的 Hash+WS 内存使用有所降低（为 Protean 的 94%），而我们的缓存感知算法 LatCache-request 和 LatCache-rule 的内存使用明显更低（分别为 Protean 的 85% 和 77%）。这种减少归因于 LatCache 算法，它通过在 AA 上将相似请求共同定位，提高缓存命中率并促进缓存规则对象的更好复用。值得注意的是，LatCache-rule 通过在规则级别促进此类共同定位，并利用底层缓存中对象的信息，实现了最小的内存使用量。总体而言，LatCache 的内存开销可以忽略不计：缓存状态在运行时被探查，命中/未命中延迟已经被用于监控。内存使用的减少有效地允许在同一节点上增加 AA 的数量，因为每个 AA 所需的缓存量减少，从而存储必要的对象，这在我们的生产系统中尤为重要（参见 §2.2.3）。

Sensitivity to System Parameters

接下来，我们分析各算法在不同系统参数下的性能。为了简洁起见，由于之前观察到 Round-Robin 和 Random 的性能极为次优，我们在分析中省略它们。

对 AA 数量的敏感性：我们在固定总缓存内存（M）的情况下，改变节点上 AA 的数量（R），从而改变每个 AA 的缓存内存（M/R）。如图 9a 所示，Protean 和 Hash+WS 算法随着 AA 数量增加表现出较差的扩展性。额外 AA 带来的并行性优势被缓存碎片化抵消，因为更小的私有缓存降低了效果。相比之下，LatCache-request 和 LatCache-rule 算法能够维持其性能，减少的每个代理缓存对性能的影响较小，这与它们较低的内存使用一致。

对分配请求负载的敏感性：我们评估了算法在高负载下的性能。我们通过将每个请求的到达时间乘以参数 ε ≤ 1 来缩短请求的到达间隔时间。ε 参数越低，请求频率越高。在分析中，我们选择 ε 值，使请求频率分别增加 25%、50%、75% 和 100%。图 9b 显示了相较于 Protean 基线的尾部延迟改进。如图所示，随着负载增加，缓存感知算法相对于 Protean 的优势也增加，而 LatCache 算法在所有负载下均表现出可扩展性，并在性能上持续优于 Hash+WS。

对缓存大小的敏感性：我们评估了算法在 AA 缓存系统内存大小变化下的性能。图 9c 显示了每种缓存大小下相较于 Protean 的尾部延迟改进，其中 100% 代表前述实验中使用的缓存大小。首先，即使在较小的缓存下，缓存友好的算法如 Hash+WS、LatCache-request 和 LatCache-rule 仍优于无缓存感知的 Protean。此外，LatCache 算法即使在有限缓存内存下，也持续优于 Protean 和 Hash+WS。其次，对于较大的预留缓存，LatCache-request 和 LatCache-rule 仍然优于 Protean 和 Hash+WS，尽管性能提升较为有限。随着缓存增大能够容纳更多对象，数据局部性的重要性降低，因此性能提升幅度减小。

Performance on Production Zones

我们在部分生产区域评估了 Kamino 搭配 LatCache 的性能影响。由于 LatCache-request 与当前缓存 API 集成更为简便，我们先部署该算法，并计划后续推广 LatCache-rule。我们在 5 个生产区域收集了性能指标，这些区域包含数万个节点，数据覆盖 LatCache-request 部署前后的 15 天（Kamino-LatCache）。

• 对延迟的影响

  • 我们比较了部署 Kamino-LatCache 前（Protean）和部署后分配延迟的差异。表 4 显示了平均延迟和第 90 百分位延迟及其标准差。我们观察到平均延迟降低了 21.1%，第 90 百分位延迟降低了 11.9%，与模拟结果一致。然而，性能提升有限的原因包括模拟器未建模的因素，例如多个 AA 在同一物理机器上分配虚拟机时产生的冲突和重试，导致无法实现的分配。图 10 展示了 Protean 和 Kamino 的延迟分解性能，凸显出在所有区域中均有一致的性能提升。

• 对缓存命中率的影响。

  • 为了展示 Kamino-LatCache 对缓存命中率的影响，我们将五个区域的测量结果进行汇总，并在图 11 中绘制了两个月的命中率曲线；虚线（2 月初）标示了 Kamino-LatCache 取代 Protean 的时间点。总体来看，五个区域的平均缓存命中率从 80% 提升至 86.6%，因此总缓存未命中量减少了 33%。模拟与生产系统中缓存命中率提升差异的两个主要原因是：(a) 整个系统中缓存大小存在差异；(b) 生产环境中 15 天的动态工作负载变化，与 24 小时的模拟追踪数据相比。

我们还观察到，缓存未命中的显著减少降低了 AA 节点的数量，减少了争用和通信开销，并将分配重试次数降至最小，从而实现更高效的请求处理并提升系统稳定性。

• CPU 和内存资源使用的减少。

  • 我们评估了 Kamino-LatCache 对分配器节点资源效率的影响，重点关注每个节点上所有 AA 的总工作内存和 CPU 使用情况。平均来看，Kamino-LatCache 将内存使用量降低了 17%，CPU 使用量降低了 18.6%，与模拟结果一致（表 3）。通过在 AA 上将相似请求共同定位以促进数据局部性，Kamino-LatCache 减少了缓存内容的重复存储，从而节省了内存。这一减少也降低了 CPU 使用，因为缓存更新所需的计算量减少。测量结果证实了这一点，显示每分钟缓存更新次数下降了 10–20%。

Related Work

除了之前对分配器系统的概述之外，我们还对资源管理相关工作进行了综述。

• 请求调度与缓存感知。

  • 以往的研究主要集中在高效的请求调度和负载均衡，以最小化延迟，尤其是亚秒级延迟。这些研究包括使用操作系统技术，如每 CPU 缓存、优化应用线程的 CPU 分配、减少队列等待时间和调度开销 [20, 33, 34]。Web 服务研究探索了静态和自适应调度策略，以应对延迟和吞吐量的挑战 [23, 28, 39]。然而，像抢占式工作挂起和网络队列轮询等技术并不适用于虚拟机请求调度。缓存感知调度也已有研究探索，例如 Google 的搜索系统使用超图划分进行负载均衡 [4]，而 [37] 提出了类似方法用于 Facebook 的网页流量和存储分片。其他研究通过共享缓存的动态分区或调整缓存策略来改善延迟，通常使用命中率作为延迟的代理指标 [10, 48]。据我们所知，Kamino 是首个公开报道的将缓存感知与延迟考虑集成到调度中的虚拟机分配框架。

• 集群与资源调度。

  • 大量研究关注在计算任务间共享分布式资源。像 Omega [36]、Twine [41] 以及其他研究 [13, 14, 17, 18, 31, 44, 46] 优化了作业或任务的资源利用率。类似的方法也应用于容器调度（如 Kubernetes [27, 29]）和虚拟机部署（如 Protean [16]）。还有一些研究关注基于服务级目标（SLO）的资源分配 [19]，以及利用预测和持续优化的动态分配策略 [6, 11, 12, 22, 24, 30, 35, 38, 40, 50]。然而，以前的研究中没有将缓存机制与虚拟机或容器分配的资源效率相结合。

• 调度与页面置换算法。关于单缓存系统的页面置换算法已有大量理论研究 [3, 8, 26]，以及针对延迟最小化的调度算法研究，尽管大多数研究集中于无缓存的系统（例如作业调度模型）[5, 7]。这些领域的交叉仍然未被充分探索。[45] 研究了多缓存系统中的调度问题，但重点是最小化缓存未命中。