11.disco

这篇论文是 VMware 的基石论文

历史背景和硬件

在上世纪 90 年代, 硬件设计已经非常厉害了, 但是多个商业系统跑在一个硬件机器上非常困难, 因此这篇论文设计了一个模式:
在 hardware 和 os 之间添加一个中间层, 类似于一个 vmm 来进行隔离

这里的硬件背景:

Stanford FLASH shared memory multiprocessor
experimental cache coherent non-uniform memory architecture (ccNUMA)

传统的不足

硬件的革新需要 significant OS changes
OS 本体代码量过大并不适合修改来适配硬件
buggy/incompatible system software can significantly impact the success of such machines
commodity OS system software 具有 constraints + inflexibility 的缺点

关键词

scalable: 设计的系统可以适配不同的(未来的)硬件
- 意味着系统设计能随着处理器数量的增加(几十到几百个 CPU)依然保持良好性能
- 传统系统只有少量 cpu 并且用一条总线通信, 但是随着 cpu 数量增加, 总线会成为瓶颈
- UMA: 统一内存访问, 所有 cpu 访问内存的速度相同, 也就是用上文的总线通信, 随着 cpu 数量增加, 总线压力增大, 性能下降
- NUMA: 非统一内存访问, 每个 cpu 有自己的本地内存, 访问本地内存速度快, 访问其他 cpu 的内存速度慢, 这样随着 cpu 数量增加, 性能下降不明显
- ccNUMA 的 cc: cache-coherent, 每个 cpu 有自己的缓存, 但是缓存之间需要保持一致性, 这样可以提高性能,但是也增加了复杂度
  - 常见方式是 目录协议 (directory-based coherence), 每个内存块有一个目录记录谁缓存了它, 当有更新时通知或失效这些缓存
flexible: 可以适配不同的 OS (注意 scalable 强调的是硬件的多样性, flexible 强调的是软件的多样性)
- 系统能支持多样化的使用场景, 工作负载和配置, 而不是只能针对单一情况优化
- 这里着重强调对 variety of workloads 的支持, 例如 cpu 密集型, io 密集型, 内存密集型等
- commodity OS: 现成的, 广泛使用的操作系统, 例如 Linux, Windows, 能应对各种应用场景, 但缺乏针对特定硬件的优化
- specialized OS: 针对特定硬件或应用场景优化的操作系统, 例如实时操作系统, 嵌入式系统, 但缺乏通用性
shared memory multiprocessor: 多个处理器可以访问同一块内存
- 所有处理器访问同一个全局内存地址空间(不像分布式系统那样各有独立内存);
  - 好处: 编程模型更简单(多个 CPU 看起来就像在同一个大内存上操作);
  - 问题: 容易出现内存访问冲突和一致性问题;
FLASH 硬件: 多个节点, 每个节点有 CPU, 内存和 I/O, 通过高速互连组成; 采用目录协议保持缓存一致性, 因此对软件呈现的是一个共享内存多处理器, 带有 NUMA 特性

VM 方案的缺点

Overheads(性能开销)

需要软件模拟特权指令, 虚拟化 I/O, 带来额外异常处理和执行开销;
每个 VM 都要复制 OS 和应用的代码/数据, 还会重复维护大内存结构(如文件系统 buffer cache), 导致内存浪费;

Resource Management (资源管理问题)

VMM 缺乏操作系统的高层语义, 只能"盲目"调度;
例如无法区分 idle loop (busy waiting 对 vmm 层透明) 与有效计算, 可能浪费 CPU 时间; 也无法知道某页内存是否已不再使用, 导致内存分配效率低;

Communication and Sharing(通信与共享困难)

不同 VM 之间的文件, 磁盘, 应用难以共享;
例如在 VM/370 上, 一个用户的虚拟磁盘若被一个 VM 占用, 另一个 VM 无法访问;

作者观点: 虽然这些缺点依然存在, 但通过结合现代操作系统对分布式环境的支持, 以及 VMM 的新设计技巧, 它们的影响可以大大减轻;

Disco 设计

Disco’s Interface(Disco 提供的接口抽象)

Disco 通过虚拟化硬件, 为每个 VM 提供标准的抽象:

Processor(虚拟 CPU)

对外表现为 MIPS R10000 处理器, 支持所有指令, MMU 和 trap;
对 OS 无需修改即可运行, 但 R10000 在内核虚拟地址空间上的限制需要额外 OS 修改;
优化: Disco 还扩展了接口, 让一些频繁的内核操作 (如开关中断, 访问寄存器) 通过特殊地址 load/store 实现, 从而减少陷入 vmm 的开销;

Physical Memory(物理内存)

向 VM 提供连续地址空间 (从 0 开始);
底层通过动态页迁移 (dynamic migration) 与复制 (replication), 将 NUMA 内存管理对上层 OS 屏蔽, 表现出对软件层近似 UMA 的一致延迟;
这样即便 commodity OS 没有 NUMA 优化, 也能高效运行;

I/O 设备虚拟化

为什么需要虚拟化: 大多数 OS 默认认为自己独占硬件 I/O, 因此 Disco 必须对 I/O 设备进行虚拟化, 拦截并翻译所有 I/O 操作;
虚拟磁盘 (Virtual Disks):
每个 VM 可以挂载虚拟磁盘;
支持不同的共享模式(写入对其他 VM 可见/不可见)和持久化模式(写入在关机后保留/不保留);
虚拟网络接口 (Virtual Network):
每个 VM 在内部虚拟子网有独立地址;
支持标准接口(Ethernet, FDDI)和一个能处理大数据块的特殊接口;
与外界通信时, Disco 作为网关负责转发;

Disco 的实现特点

整体实现: 多线程共享内存程序, 规模小(约 13,000 行代码);
优化重点: 针对 NUMA 架构和缓存行为进行高度调优;
代码段(72KB)在每个节点内存中复制, 保证指令缓存命中在本地完成;
全局数据结构按访问模式分区: 单核常用数据放在本地内存, 多核共享数据采用 cache-friendly 设计;
大量使用 wait-free 同步(MIPS LL/SC 指令对), 尽量减少锁;
通信机制:
多数场景通过共享内存通信;
使用处理器间中断 (IPI) 处理特殊操作(如 TLB shootdown, 虚拟 CPU 中断投递);

Virtual CPUs

Direct Execution(直接执行)

Disco 的虚拟 CPU (vCPU) 通过直接执行 (direct execution) 在真实 CPU 上运行;
方法: 把真实机器寄存器设置为 vCPU 的状态 $\rightarrow$ 跳转到 vCPU 的 PC 继续运行;
优点: 绝大多数指令能以接近原生速度执行;
挑战: 遇到特权指令(如 TLB 修改, 物理内存或 I/O 访问)不能直接执行, 必须由 Disco 拦截并模拟;

vCPU 状态管理

每个 vCPU 在 Disco 中有一个数据结构, 类似 OS 的进程表项:
保存 (privileged) regs, TLB contents 等状态;
当 vCPU 没有被调度时, 这些状态保存在结构里; 切换回来时恢复;

执行模式(Mode Switching)

Disco monitor 本身: 运行在 kernel mode, 有完整硬件访问权限;
Guest OS: 运行在 supervisor mode
- Supervisor mode 是一种介于用户态和内核态之间的特权级别;
- 在 Disco 中, guest OS 被放在 supervisor mode, 以保证它能运行, 可以访问 supervisor segment, 但不能直接执行特权指令或直接操作物理内存;
- 真正的完全控制权只属于 Disco monitor 的 kernel mode;
- 特权操作由 Disco 捕获并模拟;
Guest Applications: 运行在 user mode, 照常执行;
当出现异常或系统调用(page fault, syscall, bus error):
CPU trap 到 Disco $\rightarrow$ Disco 更新 vCPU 的寄存器状态 $\rightarrow$ 跳转到 guest OS 的 trap handler;

调度 (Scheduling)

Disco 有一个简单调度器, 允许 vCPU 在物理 CPU 上分时运行 (time-sharing);
调度器与内存管理协同, 支持 affinity scheduling(尽量把 vCPU 调度到它内存所在的物理节点), 提高数据局部性;

vPhysMem

物理内存虚拟化机制

虚拟机看到的内存: 从 0 地址开始的一块"物理地址空间";
真实机器内存: FLASH 机器使用 40 位物理地址;
Disco 的工作:
- 维护虚拟机物理地址 $\rightarrow$ 机器物理地址的映射关系 (以下简称 VP 转换);
- 使用 MIPS 的_软件_填充 TLB 机制: 当 guest OS 往 TLB 插入映射时, Disco 拦截, 把 guest 的物理地址转换为机器物理地址, 再写入 TLB;
- 一旦 TLB entry 建立后, 后续访问无需额外开销(直接走硬件);

数据结构支持 (快速计算 TLB entry)

pmap (per-VM page map): 每个虚拟机都有自己的 pmap 表
- 它的功能类似一个"页表", 但存的不是虚拟地址到物理地址的映射, 而是: guest-physical page $\rightarrow$ machine-physical page 的映射关系
每个 pmap entry 对应一个预先计算好的 TLB entry, 指向真实机器内存页;
包含回溯指针(backmap) 指向对应的 VM virtual address, 用于当页面被回收时从 TLB 中失效相关映射;
protection bits: 读/写/执行权限, 在 VM 试图写入一个 TLB 项的时候 Disco 会将这个请求加入其 page 的 protection bit 再进行保存到真的 TLB 里;

pmap entry structure	Description
guest-physical page	虚拟机看到的物理页号
machine-physical page	真实机器的物理页号
TLB entry data	预计算好的 TLB entry (PFN, ASID)
backmap pointer	指向该页在 TLB 中的所有映射

MIPS 架构的特殊问题

在 MIPS 上, KSEG0 段的内核代码和数据是直接访问物理内存的(不经过 TLB);
- 这里指对于 MIPS TLB 而言, 内核中有一段 unmapped segmeng of kernel virtual address space, 会被用作 TLB 绕过, 直接映射到物理内存;
这让 Disco 无法拦截和重定向这个内存的访问 (就是已经放到内核的未映射地址, 但是由于 Disco 看不见, 这是硬件层优化, 所以 Disco 无法将其 remap 放入对应的 TLB) $\rightarrow$ $\to$ 如果靠 trap to monitor 来模拟, 性能太差;
- 注意上文 2. 我们提到过, guest OS 在填充 TLB 时会被 Disco 拦截并转换地址, 但这里的 unmapped segment 访问不会触发 TLB 填充, 因此无法被拦截;
解决办法: 重新链接 (re-link) guest OS, 把内核代码和数据放到需要经过 TLB 的地址段(mapped segment);
这个问题是 MIPS 特有的, 其他架构 (Alpha, x86, SPARC, PowerPC) 可以直接用 TLB remap;

ASID 处理策略

ASID (Address Space ID): MIPS 给每个 TLB entry 打标签, 避免进程切换时清空整个 TLB;
Disco 的选择: 不虚拟化 ASID 以对应各个虚拟机内部的所有进程 (太复杂, 需要新加入一层虚拟转换), 而是在切换 vCPU $\rightarrow$ $\to$ pCPU 时直接 flush 整个 TLB (切换 cpu 的时间片大致是 ms 级别, 比一般的进程切换慢很多, 因为我们上面提及过在调度的时候会优先把进程调度到有自己内存存储的 processor 上, 说明这里能基于前面的设计优化这里的 TLB flush 周期);
- 这里的意思是: TLB 一般是指存在于 pCPU 上的 buffer, 也就是说 VM1, VM2 可能都会有一个 ASID=4 的进程但是实际指向的 pCPU TLB 的 entry 是不同的, 且其 bit 不应该太长 (TLB 查表要非常快, 长了就慢了), 因此只能做虚拟化, 但是这样又比较复杂, 因此直接 flush;

MIPS 架构的特殊问题

在 MIPS 上, KSEG0 段的内核代码和数据是直接访问物理内存的(不经过 TLB);
- 这里指对于 MIPS TLB 而言, 内核中有一段 unmapped segmeng of kernel virtual address space, 会被用作 TLB 绕过, 直接映射到物理内存;
这让 Disco 无法拦截和重定向这个内存的访问 (就是已经放到内核的未映射地址, 但是由于 Disco 看不见, 这是硬件层优化, 所以 Disco 无法将其 remap 放入对应的 TLB) $\rightarrow$ 如果靠 trap to monitor 来模拟, 性能太差;
解决办法: 重新链接 (re-link) guest OS, 把内核代码和数据放到需要经过 TLB 的地址段(mapped segment);
- 这个问题是 MIPS 特有的, 其他架构 (Alpha, x86, SPARC, PowerPC) 可以直接用 TLB remap;
- 好处: 实现简单, guest OS 提供的 ASID 可以直接用;
- 代价: 切换时更多的 TLB miss;

性能优化: TLB miss

问题:
- 由于所有 OS 内核访问都必须通过 TLB, $\rightarrow$ TLB miss 增加;
- 每次 miss 成本更高: 需要 trap, 模拟 TLB miss handler, 做地址 remap;
优化:
- Disco 引入二级软件 TLB (software TLB cache);
- 在 TLB miss 时, 先查二级缓存 $\rightarrow$ 命中则快速恢复映射, 不命中才交给 guest OS;
- 效果: 对 guest 来说, 好像拥有比硬件更大的 TLB;

透明页复制(Transparent Page Replication)

Disco 能把同一个虚拟物理页, 在不同节点上创建副本;
例如, vCPU0 和 vCPU1 属于同一个 VM, 它们共享一块虚拟页; Disco 会在各自节点上放置副本, 提高访问局部性, 减少远程访问延迟;
这里是 processor 级别/粒度的复制而不是我们后面会提及的 page 级别的, 也就是这里更多依赖于硬件的 cache coherence 来保证一致性和高效;

NUMA memory management

问题背景

在 ccNUMA 机器上, 内存访问延迟不均匀: 访问本地内存快, 访问远程节点内存慢;
绝大多数 commodity OS(如 IRIX, Linux)不具备 NUMA 优化能力, 所以 Disco 需要代替 OS 来处理这一层问题;
目标: 尽量让 vCPU 的 cache miss 访问本地内存, 而不是远程节点;

Disco 的解决方案

动态页迁移 (migration) 和页复制 (replication):
迁移: 当一个页主要被某个节点频繁访问 $\rightarrow$ 把它迁移到该节点的本地内存;
复制: 当一个页主要是只读共享 $\rightarrow$ 在多个节点上复制副本, 减少远程访问;
不移动: 如果一个页是多节点频繁写共享 $\rightarrow$ 不迁移也不复制, 因为无法优化;
策略上比较保守: 只迁移/复制能带来长期性能收益的页, 并限制迁移次数避免过度开销;

依赖的硬件支持

FLASH 硬件能统计每个物理页的 cache miss 计数, 并且按 CPU 分布;
Disco 利用这个计数来判断哪些页是 “hot page”, 决定是迁移还是复制;

具体操作

迁移:

失效所有 TLB 中旧页的映射;
把数据复制到新的本地物理页;
更新映射到新的 machine page;

复制:

把所有相关 TLB entry 设置为只读;
把页复制到目标节点本地内存;
更新 TLB entry, 使读请求可以从本地副本获取;
数据结构支持

memmap: 为每个机器物理页维护元信息:
哪些 VM 在使用它;
对应的虚拟地址;
是否存在副本及副本位置;
用于在迁移/复制时高效地做 TLB shootdown 和一致性维护;