VM in the Cloud

关于云计算的虚拟机背景知识

主要参考文献 ”Protean: VM Allocation Service at Scale （OSDI'20）“

Inventory

Inventory 的中文翻译是库存或资源池。但其含义远比字面意思丰富。核心内涵包括：

• 资源的集合：它不是一个单一的东西，而是所有可用资源的总和。包括：

  • 物理服务器：最核心的资产。

  • 计算资源：服务器提供的CPU核心数、内存大小。

  • 特殊硬件：GPU、FPGA、高性能SSD存储等。

  • 网络资源：IP地址、带宽、虚拟交换机等。

  • 软件许可：某些需要特定许可的操作系统或软件。

• 动态的状态：Inventory 不是静态的。它随时都在变化，因为：

  • 资源被消耗：客户创建虚拟机（VM），资源就被分配出去。

  • 资源被释放：客户删除VM，资源就回归库存池。

  • 硬件维护：服务器下线维修或上新服务器，库存随之增减。

• 可管理的数据：在云平台中，Inventory 是一个被精密追踪和管理的数据库。调度系统（如Protean）需要实时知道：

  • 总容量：一共有多少资源？

  • 已用量：已经分配了多少？

  • 可用量：还剩多少可以分配？

  • 资源属性：每台服务器的具体配置（CPU型号、内存大小、所在位置等）。

一个global inventory 通常是层次结构的，以Azure为例，就包含了region, zone, datacenter, cluster, rack, machine的层级，如下图所示：

zone和datacenter的规模通常没有严格上限，从小到大都有。

但也有一些特征：

• zone里的inventory通常是异构的（多个硬件代次等等），cluster里的通常是同构的服务器。

  • 利用集群同构性，可以优化请求延迟

Tenant

仍然以Azure为例，用户以服务请求（Service Request）的形式指定其需求。一个服务请求由一个或多个 VM 请求组成，这些 VM 请求被归为同一个租户 (tenant)。

租户服务模型（the tenant service model） 表达了这些 VM 之间的关系和所施加的约束。只有当租户中所有请求的 VM 都成功分配时，分配才算成功（即 成组调度 / gang-scheduling）。

• 一个服务模型会指定每个 VM 的类型（该类型决定了 VM 的核心数、内存、磁盘或网络需求）、故障域 (fault domain) 要求，以及服务的优先级。

  • 默认情况下，租户的 VM 可以分布在整个区域中。然而，租户可以要求将其所有 VM 共同放置 在特定的资源范围内（如某个数据中心或机架行），或者相反，禁止过多的 VM 被放置在同一台机器或同一个机架上。租户甚至可以指定：在承载其 VM 的机器上，不能放置来自任何其他租户的 VM。

Workload in the Cloud

• 需求是异构的

  • Azure的各个zone呈现出相当多样化的工作负载。有大量不同类型的 VM，其分布通常是不均匀的。

    • 某些 VM 类型可能占到工作负载的 50%，而其他类型则非常少见

    • 大多数 VM 只需要少量核心，但也有一些 VM 需要半台甚至整台服务器的资源

• 后续请求的特性类似

  • 这个特性指的是两次请求同一个类型的VM之间，被请求过的不同VM类型的数量（重用距离）

    • 超过 80% 的请求的重用距离为 0，而大多数请求的重用距离小于 5。

    • 这种行为可以归因于多种因素的共同作用

      • 大型服务请求往往会要求相同类型的 VM

      • 存在一个相对较小的热门 VM 类型集合

• VM 生命周期差异显著

  • 大多数 VM 的生命周期较短，仅有几分钟左右。然而，也有一些 VM 可以在系统中“长期存在”——持续数周甚至数月

  

• 需求存在峰值和昼夜周期模式

  • 通常在夜间使用量较低

  • 需求在一天中也可能出现大幅度的峰值

    • 需要注意的是，需求峰值可超过每秒 2000 个请求

    • 这种行为迫使云服务厂商必须为峰值做好资源准备

      • Azure中为每个 Protean 实例部署多个 分配代理（AAs）

      • 也利用低峰期来更好地准备 AAs，以应对未来的分配请求

• 租户规模通常较小，但也可能很大

  • 94% 的请求仅包含一个 VM，99% 的请求包含五个或更少的 VM。同时，我们也观察到少量请求包含数百个 VM；显然，这类请求会带来额外的挑战，例如需要将 VM 分散到不同的故障域中。

Takeaway

• 缓存的机会

  • 上述第二点的”后续请求随时间表现出相似性“，激发了Protean对放置评估逻辑进行缓存的想法，并在多个请求之间重用该逻辑。

    • 这一思路至关重要，并有助于系统在大规模区域中实现扩展。

• Machine Packing Chanllenge

  • 存在多种不同类型和尺寸的 VM，生命周期差异大且不可预知

  • 从算法角度看，我们打包问题的简化版本已经可以映射到 动态装箱问题（dynamic bin packing),在离线情况下（即假设所有 VM 到达时间已知）该问题是 NP-hard 。而在在线场景下 [6] 的竞争比率也相当糟糕。在Azure的实际环境中，还存在其他因素使问题更加复杂，例如多优先级、故障域要求等。

Protean AA

Protean是微软在OSDI'20上发布的论文，并服役于Azure，其本质是一个调度器。Protean 的主要职责是：在满足底层服务模型中明确指定的需求和约束条件，以及其他内部运营考量的前提下，为分配请求中的每个 VM 找到一个物理位置（机器）。

为了应对大量请求负载，Protean 使用了多个 分配代理（Allocation Agents, AAs） 并行运行。每个代理都能感知整个资源库存（inventory），并可以从中选择任意符合条件的机器来承载一个 VM。资源库存的权威状态存放在持久化存储中。每个 AA 维护着自己的库存视图，该视图会通过周期性更新，以及在分配或库存相关事件发生时进行更新。

Metrics and Constraints

Protean 关注多个与性能和分配质量相关的指标。关键指标包括：

• 延迟（Latency）：单个 VM 的分配应能及时完成，通常在 20 毫秒内。

• 吞吐量（Throughput）：Protean 应能够应对峰值需求，而不延迟或限流请求。

• 接受率（Acceptance）：Protean 应尽量降低拒绝率。当一个 VM 请求无法满足时，即视为一次拒绝。

需要注意的是，延迟本身并非独立关键指标（尽管对于大型租户可能会变得过高）。然而，更低的延迟有助于提高吞吐量。直观上，当延迟较低时，请求可以由较少的分配代理（AAs）处理，从而减少冲突，可能获得更高的吞吐量。此外，更低的延迟还降低了单个 AA 与库存真实状态偏离的概率，从而提高分配质量。

当然，上述三个指标都依赖于库存规模。库存越大，延迟和吞吐量的挑战越大，但接受请求变得相对容易。我们也关注计算资源的高效利用；在 §6 中，我们将正式定义与利用率相关的指标。

Requirements and Constraints

• 兼顾多重考量

  • 首先，Protean 必须做出正确的分配；例如，分配不能违反机器的容量限制。此外，请求可能包含必须满足的特定约束。例如，某些 VM 可能需要特定类型的硬件（如 GPU）。此外，一个包含多个 VM 的服务请求可能要求这些 VM 分布在多个故障域中（通常是跨不同机架）。

• 租户体验

  • 应避免将 VM 分配到不处于“就绪”状态的机器上；避免分配到尚未更新至最新宿主环境的机器，或可能在近期发生故障的机器上。如果一台机器发生故障，其承载的 VM 必须重新分配到其他机器上。低优先级 VM 由 Azure 提供的服务使用，例如 Batch [1] 和 Spot 虚拟机 [2]。尽管这些 VM 允许被抢占，Protean 仍力求尽量降低它们的驱逐率。

• 适应性

  • Protean 必须允许灵活配置分配逻辑，并能根据不同条件进行调整。

• 可扩展性与可解释性

  • Protean 应易于、安全地扩展，以便工程师能够集成新的分配逻辑。相应地，分配逻辑应允许增量修改，并支持在生产环境中进行 A/B 测试。此外，Protean 应使操作人员能够解释分配决策（例如，“为什么请求失败？”，“为什么选择机器 x 承载 VM 请求 v？”）；解释分配结果被认为是大规模云调度中的主要挑战之一 。

Allocation Rules

如上所述，Protean 必须同时考虑多种因素：

• 首先，严格的分配约束必须被强制执行（例如，某个 VM 必须分配到特定类型的硬件）

  • 而其他分配考虑可以被视为“偏好”，例如，将 VM 分配到被认为健康的服务器上，或具有特定磁盘配置的服务器上会更好。

• 除此之外，Protean 还追求 “高质量”分配

  • 例如，通过最小化碎片化来高效打包服务器、在机架之间平衡分配、避免驱逐低优先级 VM 等

由于涉及的维度众多，Protean 的分配逻辑被组织为一套 规则（rules）。这些规则决定了每个 VM 将被分配到哪台机器。对于包含 k 个 VM 的服务请求，规则逻辑将被调用 k 次。

规则被分为 验证规则（validator rules） 和 偏好规则（preference rules）。

• 验证规则用于处理硬性约束，

• 而偏好规则可视为软性约束。

规则被组织为 两级层次结构——先是集群选择规则（cluster selection rules），然后是机器选择规则（machine selection rules）。截至2020年，系统中总共有大约一百条规则。

集群选择规则 通过将机器选择规则的作用范围限制在区域内的少量集群，从而有效降低了选择过程的时间复杂度。由于集群是同质的（见 §2），我们实现了若干集群 验证规则（cluster validator rules），用于筛选出与 VM 请求无关的集群（例如，需要 GPU 的 VM 只能部署在包含 GPU 的集群上）。此外，还使用了一些集群 偏好规则（cluster preference rules） 来对有效集群进行排序（例如，为了平衡集群间的可用容量，我们倾向于选择空闲更多的集群）。

筛选 + 排序 + Top-K

基于这些规则，Protean 会选择 质量最高的 k 个集群，其中 k ∈ [8, 16] 是可配置参数；用于机器选择规则的库存（inventory）将由这些集群中的机器组成。参数 k 的设定基于一个权衡：在提供足够多的机器以做出高质量决策与保持合理延迟之间进行折中。

接下来，机器选择规则 同样由验证规则和偏好规则组成：

• 验证规则排除不符合条件的机器；

• 偏好规则最终选出少量最匹配该 VM 的机器。

当有多个机器同样符合条件时，会通过随机化的 平局打破规则（randomized tie-breaking rule） 从中选择一台机器用于 VM 的物理分配。

验证规则（Validator rules）

每条验证规则实现一个布尔方法 $\mathtt{\text{IsValid(x, v)}}$$\texttt{IsValid(x, v)}$，用于判断对象 $x$$x$ 是否是放置 VM $v$$v$ 的有效候选对象；根据具体规则，对象可以是 集群（cluster） 或 机器（machine）。验证规则用于将库存（inventory）中的对象集合剪枝为仅包含 有效候选对象 的子集。

示例：

1. $\mathtt{\text{AreNodeResourcesValid(x, v)}}$$\texttt{AreNodeResourcesValid(x, v)}$：检查机器 $x$$x$ 是否有足够的可用资源以容纳 VM $v$$v$。如果所有资源维度（CPU、内存、磁盘等）都能满足，则方法返回$\mathtt{\text{true}}$$\texttt{true}$。

2. $\mathtt{\text{IsTypeSupported(x, v)}}$$\texttt{IsTypeSupported(x, v)}$：检查集群 $x$$x$ 是否兼容 VM $v$$v$ 对应的类型。

偏好规则（Preference rules）

偏好规则用于量化每个候选对象 $x$$x$（根据具体规则可以是 集群 或 机器）与 VM 的匹配程度。每条偏好规则 $r$$r$ 针对特定考量（例如打包质量、负载均衡、集群/机器质量等）通过数值评分 $S_r(x,v)$$S_r(x, v)$ 来评估。我们使用的约定是：分数越低越好。

示例：

1. $\mathtt{\text{BestFit(x, v)}}$$\texttt{BestFit(x, v)}$：分配一个分数

$Sr(x,v)=\sum iwi(ai(x)-di(v))S_r(x,v)=\sum _i{w}_i(a_i(x)-d_i(v))Sr(x,v)=i\sum wi(ai(x)-di(v))$$Sr(x,v)=∑iwi(ai(x)−di(v))S_r(x, v) = \sum_i w_i \big(a_i(x) - d_i(v)\big)Sr(x,v)=i∑wi(ai(x)−di(v))$

其中 $a_i(x)$$a_i(x)$ 表示机器 $x$$x$ 在“资源” $i$$i$（例如 CPU 核心数、内存、SSD）上的可用量，$d_i(v)$$d_i(v)$ 表示 VM 在该资源上的需求，$w_i$$w_i$ 是该资源的权重，用于量化其稀缺性（直观上，$w_i$$w_i$ 越高，资源越稀缺）。分数越低表示机器越适合该 VM，因为资源被更合理地打包；类似的打包启发式方法在文献 [39] 中也有提出。

1. $\mathtt{\text{PreferNonEmptyMachines(x, v)}}$$\texttt{PreferNonEmptyMachines(x, v)}$：该规则偏好使用非空的机器，主要目的是提高打包质量。

2. $\mathtt{\text{PreferEmptierClusters(x, v)}}$$\texttt{PreferEmptierClusters(x, v)}$：该规则量化集群 $x$$x$ 中空闲核心的数量。其核心思想是平衡集群之间的可用容量，从而降低集群容量被耗尽的概率。这在多个方面都很重要，例如，某些客户要求集群内亲和性，如果集群已满，则无法进行横向扩展。

Accounting for Multiple Rules

验证规则（validator rules） 的序列会筛选掉不适合该 VM 的对象（集群或机器）。Protean 设计中的一个主要挑战是：如何处理多个偏好规则（preference rules）？

这里的固有问题在于，不同规则表示不同且难以直接比较的偏好:

• Compare 方法

  • 每条偏好规则 $r$$r$ 实现$\mathtt{\text{Compare(x, y | v)}}$$\texttt{Compare(x, y | v)}$方法，用于根据评分比较两个对象 $x$$x$ 和 $y$$y$；如果分数相等，方法返回 0；如果 $S_r(x,v)<S_r(y,v)$$S_r(x, v) < S_r(y, v)$，返回 1；否则返回 −1。

• 比较与排序

  • 每条偏好规则通过一个权重（或增益值）表达其相对重要性。两个对象根据一个综合分数（aggregate score）进行比较，该分数由每条规则的 $\mathtt{\text{Compare}}$$\texttt{Compare}$方法返回值乘以权重后的总和计算得出。利用成对比较，Protean 根据综合偏好分数对整个对象集合进行排序。

• 权重分配

  • 虽然系统允许对规则权重设置任意正值，但我们选择了一种 在偏好规则间建立严格顺序 的方式分配权重。规则按照顺序保持编码（order-preserving encoding）分配权重，即权重呈指数差距，使得实际上任何规则只能在前一条规则偏好的对象之间表达偏好。因此，整个规则集（包括验证规则）可视为一个 过滤过程：随着更多规则的应用，优选对象集合不断缩小；详见 §3.4。

• 量化（Quantization）

  • 在偏好规则之间建立严格优先级时，需要对偏好规则进行“平滑处理”，以便所有规则都能发挥作用。我们通过将部分规则的分数量化为少数几个桶（buckets）来实现，例如对连续分数的规则（如 $\mathtt{\text{BestFit}}$$\texttt{BestFit}$）进行处理。举例来说，可以应用变换$dS\cdot N$$dS⋅N$

    其中 $S\in [0,1]$$S \in [0, 1]$ 是原始（连续）分数，$N$$N$ 为桶的数量。规则顺序和具体量化值的设定依赖于领域知识以及对业务需求和偏好的理解，其设置基于模拟结果与生产环境遥测的反复试验。

Architecture

运行机制

Protean 采用多个同时运行的 分配代理（AAs），遵循乐观并发模型。

• AAs 被组织在多台机器上运行。每台机器运行一个进程，每个进程创建多个工作线程，每个线程对应一个 AA。

• 来自客户端的分配请求通过负载均衡器路由到这些进程。在进程内部，请求被存储在共享工作队列中，直到空闲的 AA 取出并处理它们。

AAs 的数量根据区域内瞬时峰值需求确定，而每台机器上的 AAs 数量取决于每个 AA 的内存占用。每个 AA 基于自身的（可能是过时的）库存视图做出分配决策，在成功处理请求后，会尝试将结果提交到 复制存储（replicated store）。复制存储负责冲突检测，并将提交序列化到同一节点（不同节点的提交可以并行处理）。此外，它存储所有由 AA 的 VM 分配决策修改的库存信息。复制存储是最新分配相关库存状态的权威来源，并通过 发布-订阅（pub/sub）服务 发布所有变化。库存中不受分配决策影响的变化（如机器健康状况或能力变化）也通过 pub/sub 服务发布。AAs 主要通过 pub/sub 服务产生的更新来获知库存变化。此外，在提交因冲突失败时，它们还会在失败通知中获知冲突机器的最新分配相关信息。

服务分配工作流程

一个服务请求可能包含多个 VM 请求，这些请求由单个 AA 按顺序处理。算法 1 总结了 Protean 如何处理服务请求。

• ORDER 确定 VM 请求的处理顺序。其目标是最小化由于故障域限制导致请求被拒绝的风险。

• ASSIGN_MACHINE_TO_VM 通过应用规则逻辑尝试为单个 VM 分配机器；对于每个请求的 VM，该步骤按顺序执行（实现细节见 §5）。

• 如果 AA 成功为所有请求的 VM 分配了机器，COMMIT 会尝试将服务分配结果提交到权威存储。如果任何 VM-机器分配因其他 AA 的冲突分配而被作废，则提交失败。

• 提交失败时，分配器状态会回滚，并将整个请求重新排入队列以重试。重试次数是可配置的。我们允许相对较高的重试次数（超过 10 次）以避免不必要的分配失败；在生产环境中，这几乎不会产生影响（例如，99.9 百分位的分配在三次重试后成功）。

提交阶段与前面的阶段流水线并行进行，这样 AA 可以在提交过程中继续处理下一个请求。

Implementation

在本节中，我们将介绍 缓存框架（caching framework），它显著加速了 ASSIGN_MACHINE_TO_VM 过程（见 §5.1–5.2）。我们还将讨论 灵活的冲突检测与减少机制（见 §5.3）。

预备知识

为了做出高质量的分配，AA 最初将库存中的所有机器都视为候选对象。

集群选择（Cluster selection） 如 §3.2 所述，AA 在选择过程中首先对 集群 进行筛选和排序，而不是直接对机器操作。由于一个区域（zone）最多只有几百个集群，因此对集群的筛选和排序非常快（通常只需几毫秒）。因此，集群选择阶段不需要额外的优化（例如缓存过去的选择结果）。该阶段的输出是 最佳的 8 到 16 个集群；这些集群中的机器（通常约 10–15k 台）将成为机器选择阶段的候选对象。

机器选择 —— 基本复杂度（Machine selection – basic complexity） 回顾一下，机器选择逻辑首先通过对每台机器评估所有 验证规则（validator rules），将候选机器集合裁剪为有效机器集合。然后，它根据每台机器承载 VM 的适合度（§3.3）构建基于比较的全序排序。最后，从最佳机器集合中随机选择一台机器。

构建评估结果（即有效机器的有序列表）所需的运行时复杂度为：

$\text{Complexity}=N\sum _{i=1}^{K_1}{T}_v(i)+N\log N(\sum _{i=1}^{K_2}{T}_p(i))$$\text{Complexity} = N \sum_{i=1}^{K_1} T_v(i) + N \log N \left( \sum_{i=1}^{K_2} T_p(i) \right)$

其中：

• N 为候选机器数量

• $K_1$$K_{1}$ 为验证规则数量

• $K_2$$K_{2}$为偏好规则数量

• $Tv(i)$$Tv(i)$为计算第 i 条验证规则 $\mathtt{\text{IsValid}}$$\texttt{IsValid}$ 的时间

• $Tp(i)$$Tp(i)$ 为计算第 i 条偏好规则 $\mathtt{\text{Compare}}$$\texttt{Compare}$ 的时间

如果 AA 对每个请求都从头构建评估结果，对于几千台机器以上的情况，会超出所需的延迟限制。

先筛选（验证），再比较排序（偏好）。因此是串行累加的复杂度。

缓存动机（Motivation for caching） （1）首先，我们观察到 请求具有局部性（Locality in requests）。

• 每个 VM 请求由一组特征向量（trait vector）描述。

  • 示例特征包括：

    • VM 类型、

    • 优先级、

    • 是否需要独占（RequireIsolation，即 VM 应部署在独立机器上）等。

  • 特征总数为几十个，每个特征可以取多个值（包括“无关”或空值选项）。

  • 在 §2.2 中，我们展示了在单个维度（如 VM 类型）上请求表现出“局部性”。我们注意到，这种现象延伸到整个特征向量：在多个请求中，尤其是时间上相近的请求中，有少数特征向量被频繁使用。

（2）第二个观察是 库存状态变化缓慢。

• 机器状态可能因分配相关事件（VM 的添加、挂起或删除）或机器/VM 健康状况变化而改变。

• 然而，分配相关事件是导致状态变化的主要原因。因此，在 AA 连续执行之间发生变化的机器，主要是因为其他并行运行的 AA 做出的分配决策所导致状态改变的机器。由于并行 AA 数量相对较少，这类变化通常不多。

这些特性表明，我们可以通过 缓存和重用上一次执行的评估状态，大幅减少机器选择逻辑的计算量。直观上，唯一需要的计算是 更新状态以反映自上一次执行以来库存变化的影响。

Caching for Efficient Machine Selection

每个 AA 都维护一组 缓存对象，这些对象共同保存了机器选择所需的信息。

Caching Rule State

• 为了高效执行而缓存规则的内部状态

  • 规则是选择过程的基本构建模块。因此，首先我们使用缓存来提高规则中$\mathtt{\text{IsValid}}$$\texttt{IsValid}$ 和 $\mathtt{\text{Compare}}$$\texttt{Compare}$方法的执行速度（分别对应 $Tv(i)$$Tv(i)$ 和 $Tp(i)$$Tp(i)$）。具体来说，每种规则类型都会实现这些方法。每种规则类型的实例称为 规则对象（rule objects），并被缓存以供重复使用。新创建的规则对象会计算并存储执行 $\mathtt{\text{IsValid}}$$\texttt{IsValid}$ 或 $\mathtt{\text{Compare}}$$\texttt{Compare}$方法所需的所有信息，从而在常数时间内完成调用。通常，这些信息按每台机器存储。例如，$\mathtt{\text{PreferNonEmptyMachines}}$$\texttt{PreferNonEmptyMachines}$ 规则（见 §3.2）会维护一个 $<MachineID,Boolean>$$<MachineID, Boolean>$ 字典，用于跟踪每台机器是否为空。

• 规则状态的即时更新（Just-in-time updates of rule state）

  • 每次使用缓存的规则对象时，都必须先将其内部状态更新到最新，才能调用其$\mathtt{\text{IsValid}}$$\texttt{IsValid}$ 或 $\mathtt{\text{Compare}}$$\texttt{Compare}$方法。为此，每条规则除了实现 $\mathtt{\text{IsValid}}$$\texttt{IsValid}$ 或$\mathtt{\text{Compare}}$$\texttt{Compare}$ 方法外，还实现了 $Update(x_1,...,x_m)$$Update(x_{1}, ..., x_{m})$​ 方法，用于更新其存储的状态。

  • $\mathtt{\text{Update}}$$\texttt{Update}$ 方法在规则对象被使用前立即调用。其参数$(x_1,...,x_m)$$(x_{1}, ..., x_{m})$表示自上次更新以来状态发生变化的机器的最新状态。一旦规则对象用最新变化更新了状态，它就可以在常数时间内执行 $\mathtt{\text{IsValid}}$$\texttt{IsValid}$或 $\mathtt{\text{Compare}}$$\texttt{Compare}$​函数。

• 将规则状态拆分为多个对象

  • 规则对象存储的状态可能依赖于一个或多个请求特征。例如，$\mathtt{\text{AreNodeResourcesValid}}$$\texttt{AreNodeResourcesValid}$ 规则依赖于请求的 VM 类型（VM-Type），因此必须缓存每个 $<Machine,VM-Type>$$<Machine, VM-Type>$​ 对应的布尔值，以表示机器是否具有足够容量。然而，我们观察到，对于处理特定 VM 请求，规则对象仅需要该请求的 VM-Type 对应的信息。更新其他 VM-Type 的状态会增加即时更新时间，从而增加请求处理时间。

  • 因此，不再为所有请求创建单一规则对象，而是针对每个 VM-Type 值按需创建规则对象。针对特定 VM-Type 值的规则对象会被用于所有请求该值的请求。实际上，请求根据相关特征值被划分为等价类（equivalence class），每个规则对象处理一个等价类中的所有请求。对于依赖多个请求特征的规则，每种特征值的唯一组合定义了该规则的一类新等价请求。

• 缓存规则对象

  • 规则对象的引用存储在一个 固定大小的对象池 中。池的大小通过反复试验确定，综合考虑内存占用和命中率。规则对象由其类型以及与之关联的请求特征值组合唯一标识。当对象池已满时，规则对象会被驱逐（遵循标准的 LRU 驱逐策略），或者当对象达到一定的年龄时也会被驱逐。基于年龄的驱逐策略允许我们在低负载期间减少内存占用。

Caching Rule Evaluation State

缓存规则对象有助于显著降低 $Tv(i)$$Tv(i)$和 $Tp(i)$$Tp(i)$的开销。然而，如果没有其他优化，我们仍然需要承担 $NlogN$$NlogN$ 的排序复杂度。因此，我们引入了额外的对象，称为 RuleEvaluation 对象。

一个 $RuleEvaluation$$RuleEvaluation$ 对象本质上保存了针对特定特征值向量（$traitvector$$trait vector$，见 §5.1）的完整评估状态。该状态包括评估结果（已排序的机器列表）以及与评估相关的规则对象的引用，这些规则对象的特征值与整个向量中的对应值匹配。

在为新的特征值向量计算评估结果后，会创建一个 $RuleEvaluation$$RuleEvaluation$ 对象（该特征值向量用作对象的标识符）。随后，该对象将被重用于所有映射到该标识符的请求。

更新 RuleEvaluation 对象

与规则对象类似，缓存的 RuleEvaluation 对象在使用前也需要更新到最新状态。然而，与规则对象不同的是，$RuleEvaluation$$RuleEvaluation$ 对象使用一个通用的 Update 方法，其目标是根据状态变化的机器更新评估结果。该方法执行流程如下：

1. 调用缓存规则对象的 Update 方法，将它们更新到最新状态；

2. 将状态发生变化的机器从评估结果中移除；

3. 对这些机器运行 validator rules，以确定哪些机器是有效的；

4. 将有效机器重新插入到有序列表中，并更新其位置。

由于每次插入操作的时间复杂度为 $NlogN$$NlogN$，因此 Update 方法的运行时复杂度为 $MlogN$$Mlog⁡N$，其中 M 是状态发生变化的机器数量。这显著降低了复杂度，因为通常 $M\ll N$$M≪N$（$M$$M$ 大约为几十台）。

$RuleEvaluation$$RuleEvaluation$ 对象被缓存于另一个固定大小的内存池中，并遵循 LRU 驱逐策略。

示例

考虑一个示例场景，其中每个请求可以有两个特征：$X\in \{x1,x2\}$$X∈\{x1,x2\}$ 和 $Y\in \{y1,y2\}$$Y∈\{y1,y2\}$；分配逻辑通过两个规则表示：$R_1$$R_{1}$ 依赖于特征$X$$X$ 和 $Y$$Y$，$R_2$$R_{2}$ 依赖于 $X$$X$​。

• 时间点 $T_1$$T_{1}$ 的第一个请求具有特征值 $X=x_1$$X=x_{1}$ 和 $Y=y_1$$Y=y_{1}$，因此创建了两个新的规则对象 $R_1(x_1,y_1)$$R_{1}(x_{1},y_{1})$ 和 $R_2(x_1)$$R_{2}(x_{1})$，以及一个评估对象 $Eval(x_1,y_1)$$Eval(x_{1},y_{1})$​。

• 时间点 $T_2$$T_{2}$ 的第二个请求对特征 $Y$$Y$ 使用了不同的值 $y_2$$y_{2}$, 因此无法复用 $Eval(x_1,y_1)$$Eval(x_{1},y_{1})$ 或 $R_1(x_1,y_1)$$R_{1}(x_{1},y_{1})$对象。但可以复用$R_2(x_1)$$R_{2}(x_{1})$，因为 $X$$X$ 的特征值未变化，同时创建新的对象 $R_1(x_1,y_2)$$R_{1}(x_{1},y_{2})$ 和 $Eval(x_1,y_2)$$Eval(x_{1},y_{2})$。

• 时间点$T_3$$T_{3}$ 的第三个请求与第一个请求具有相同的特征值，因此可以复用在处理第一个请求时创建的三个对象。

总体而言，共创建了两个 $RuleEvaluation$$RuleEvaluation$ 对象，分别对应两个特征值向量$\{x_1,y_1\}$$\{x_{1},y_{1}\}$,$\{x_1,y_2\}$$\{x_{1},y_{2}\}$。它们共用一个规则 $R_2$$R_{2}$ 的对象，但规则$R_1$$R_{1}$ 使用两个独立对象。

Additional Cache Hierarchies

多个规则往往依赖于状态的相同部分。例如，多个规则需要跟踪机器是否为空（例如，BestFit 规则以及一个尝试在机架之间平衡容量的规则）。对于这种情况，我们将状态的共享部分封装在一种 Shared-Cache（共享缓存） 类型中，多个规则可以引用它。

与 Rule 类似，Shared-Cache 也实现了 Update 方法，并声明它所依赖的任何请求特征。Shared-Cache 在减少内存使用方面发挥了重要作用。这些对象被缓存到它们自己的固定大小的内存池中。

如前所述，一个缓存对象可能依赖于其他缓存对象。因此，规则选择引擎会确保在更新某个对象之前，先更新其所有依赖项。

我们的缓存层次结构嵌入了一些理想特性。例如，当一个新的 RuleEvaluation 对象被创建时，它通常可以依赖于已有的规则对象和 Shared-Cache 对象。

Efficiently Updating the Cache

跟踪与更新机制

回顾一下，每个 AA 都维护着自己私有的缓存。由于每个缓存对象在原则上都可以在使用之前更新，因此对象可能会处于不同程度的陈旧状态。为了实现无缝更新，每个 AA 都维护一个 日志（journal），用于跟踪库存中任何机器的变化。该日志维护一个全局修订号，每次更新时都会递增。此外，日志只存储每台机器的最新状态。每个缓存对象都会记录它所见过的最高修订号，该修订号对应于该对象已消费的最新库存更新。对象通过读取日志中修订号更高的记录来自行更新。因此，更新操作的运行时复杂度与被修改的机器数量成正比，而不是整个库存规模。在进行评估时，AA 会更新日志，记录其正在做出的每个 VM 放置决策。此外，AA 还会在评估之间更新日志，方法是处理从 发布/订阅服务（pub/sub service） 或 放置存储（placement store） 入队的传入更改。

后台更新

一个最新的缓存可以在几毫秒内处理完一个请求，只需提取出最佳机器即可。然而，如果缓存不是最新的，那么 即时缓存更新 的时间可能会占据 VM 请求总延迟中的很大一部分。尽管如此，由于系统中存在多个 AA，它们的配置足以应对少数峰值负载时期，因此大多数时间处于空闲状态。因此，当某个 AA 没有请求需要处理时，它会被 用来机会性地更新缓存（从 RuleEvaluation 缓存对象开始，并递归地向下进行）。