Intro

NOVA是一种为NVM+DRAM组成的混合系统设计的日志结构文件系统。与传统LFS不同的是：

  • NOVA为每个inode维护一个独立的log，保证inode内修改的原子性。对于涉及多个inode的修改，通过轻量级journaling加以保证。
  • NOVA不在log里记录文件数据，减少了log大小，从而降低了recovery和GC负担。

Design Overview

NOVA的设计考虑了3个observation：

  1. 在NVM上实现支持原子更新的log比较容易，但是实现能快速查找的数据结构（树）比较困难。
  2. NVM的随机访问不比顺序访问慢很多，因此不用像LFS那样花大代价保证log的物理连续。
  3. 机械硬盘只有一个磁头，所以LFS使用了一个全局log。NVM支持快速和高并发的随机访问，NOVA完全可以维护多个log结构。

于是，NOVA做出了以下设计决定：

  • 在NVM中（顺序）记录日志和文件数据，在DRAM中建立基数树索引，加速对日志的访问。
  • 为每个inode维护单独的log，提高并发度。
  • 涉及单个inode的操作通过log保证原子性；涉及多个inode的操作通过轻量级journaling保证原子性。轻量级journaling只记录每个inode log的尾指针，不管修改再多，记在journal里的不过是几个（rename操作最多，4个）指针而已。
  • 将log实现为单链表，链表元素是4KB页，不需要使用连续的NVM空间。这使得分配log空间变得简单，也能支持细粒度的log GC。
  • log中不记录文件数据，只记录关于每个写操作的元数据，并指向对应的数据页。数据页更新的原子性通过CoW保证。这使得log更小，GC更简单（不涉及文件数据）。

Implementation

General

NOVA将NVM分为super block、recovery inode、journal、inode table和log/data page，其中recovery inode在umount时保存DRAM中的数据结构，inode table和journal都是per cpu的结构以提高并发度。除此之外，NOVA还在DRAM中维护了用于分配空闲页的freelist（实现为红黑树），这同样是一个per cpu的结构。

Inode table是一个由若干2MB块链接成的数组，用于保存大小为128字节的inode，因此可以直接通过inode号找到inode结构。NOVA在所有cpu的inode table之间round robin分配，以保证inode分布尽量均匀。每个inode维护指向其log头尾的指针。

Journal是一个4KB的循环数组，用<enqueue, dequeue>标示，用于保证涉及多inode操作的原子性。对这类操作，NOVA先追加写入各inode的log，然后把所有（尚未更新的）log tail记录在journal的enqueue处，标志事务开始。之后NOVA更新每个log tail，完成所有更新后前移dequeue指针表示事务结束。对于create()这类新增inode的操作，journal记录的是directory inode的log tail和新inode的valid bit。在recovery时，NOVA回滚enqueue和dequeue指针之间记录的操作。

Log和文件数据不占用固定的空间，而是使用分配器分配的4KB数据页。分配器使用DRAM中的per cpu freelist（红黑树）结构追踪NVM中的空闲页，这个结构会在shutdown时保存到NVM上。但如果发生了crash，就需要扫描日志重建分配器的状态。

目录操作

NOVA中每个目录同样由NVM和DRAM中的两部分组成：NVM中保存各个dir inode的log；DRAM中保存一个radix tree结构，以文件名为key，该文件名的dentry为value，加速目录访问。

NOVA的dentry包括create和delete两类，分别表示创建和删除文件。Dentry中记录了文件名和inode号。在dir inode的log中，除了两种dentry外，还会包含一种inode update entry，它的用途是为同时修改inode中多个字段的操作（如chmod）提供原子性保证。

图中的目录曾经保存过，后来删除了"foo"文件。它还经历过一次chmod操作。

如图，对文件创建操作，NOVA首先在inode table中分配并初始化文件inode，并在父目录的log中记录一条create dentry；随后，NOVA使用journal，原子更新父目录inode的log tail指针并设置文件inode的valid bit；最后更新DRAM中的radix tree。

文件操作

NOVA中每个文件包括NVM中的inode和DRAM中的radix tree（file offset映射到file write entry）。文件inode log中的entry包括file write entry（以<pgoff, pgcnt>记录每一次写入操作，指向其写入的page）和inode update entry（作用同目录inode）。

对于读操作，NOVA原子更新文件inode中的access time字段，并利用radix tree定位需要读取的file write entry，进而获得存储文件数据的页，并将内容复制到用户buffer。

如图所示，对于写操作，NOVA首先分配NVM页并写入数据，然后将指向新页的file write entry追加到inode log；随后NOVA更新log tail指针，并更新radix tree让相应offset指向新的file write entry（CoW）；最后回收被换下来的old data page。

Atomic Mmap

Mmap为应用提供了一种直接访问文件的手段，但代价是原子更新更难保证。NOVA使用atomic-mmap，将file data拷贝到replica page再映射到地址空间。应用调用msync()写回dirty page时，NOVA像处理write请求那样，通过CoW原子更新file data，再更新log tail提交更改。

Garbage collection

NOVA中的GC主要是回收无用的log entry，实现了两种策略。Fast GC更注重性能，只将不含有任何有效log entry的page从链表中删除并回收；Through GC更注重效果，如果Fast GC后有效log entry占比小于一半就会触发。它会拷出数据紧凑放置，再回收这些页。

Shutdown and Recovery

NOVA在挂载时需要建立DRAM中的数据结构，如free page list。鉴于应用程序可能只会访问文件系统的一部分，对inode的加载是lazy的：第一次访问某个inode时，NOVA才会在DRAM中建立其radix tree。

正因如此，NOVA在故障恢复时只需要重建free page list，这需要扫描所有inode log。由于NOVA的log是per inode的，这个过程可以并发进行；此外log中不包含文件数据。这两个原因使得recovery只需要扫描NVM的一小部分，速度较快。

故障恢复时，NOVA首先扫描journal并回滚未完成的事务，使文件系统恢复到一致的状态；随后在每个CPU上起recovery线程，扫描每个inode table，找到每个有效inode并扫描inode log。对于目录inode，NOVA通过组成日志的链表获知哪些页被占用，不看日志内容；对于文件inode，NOVA通过读日志内容获知哪些页被文件数据占用。通过扫描，NOVA建立起关于哪些页正被使用的bitmap，并根据此信息重建分配器状态。

NVMM Protection

在将NVM直接映射到地址空间时，NOVA使用和PMFS相同的write window策略，利用CR0.WP位保护NVM不被来自内核的stray write破坏。

思考

  1. 对Sprite LFS而言，整个文件系统都由log构成。如果要修改一个inode中的一个字段，也要创建出一个新的inode结构和新的inode table并加入日志中。但对于NOVA，inode的log只是用来记录对文件数据的写入操作，以及保证修改多个字段的原子性，修改一个inode中的一个字段（如access time）可以直接用原子写入指令完成。
  1. Xu's Slides