一 核心内容

论文作者提出了一种名为 NOn- Volatile memory Accelerated (NOVA) 的日志结构文件系统 (log- structured file system, LFS) 以最大化 NVMM 和 DRAM 同时存在的混合存储系统的效率。

  • NOVA 充分利用 NVMM 的随机访问特性，从传统 LFS 中放宽了局部性限制，从而实现了日志数据分离、日志链表来避免传统 LFS 的垃圾回收开销
  • NOVA 通过将空闲链表索引和 Inode 索引建立在 DRAM 中，规避了在 NVMM 中由于一致性难以保证造成的数据结构难以实现的问题
  • 除了本身是 log-structured 之外，NOVA 还在需要同时修改多个 inode 的操作(如对路径相关的操作)中采用了 journaling 技术，同时依赖 VFS 的目录锁，规避了影子分页系统的级联开销和因此强顺序数据依赖造成的性能损失

NOVA 适配了 NVMM 以及 NVMM + DRAM 混合存储系统的特点，解决了传统 LFS 中 GC 开销大的痛点，尤其在写密集的场景下表现极其优秀。

二 研究动机

2016 年恰恰是 NVMM 较为火热的一年，但纯 NVMM 的存储系统也有一些弊端。现有的软件技术栈几乎都是为了慢速磁盘设计的，对于几乎所有传统计算机科学学者而言，文件I/O 要比内存访存慢几个数量级几乎是常识。此时 NVMM 的出现就显得不合时宜，需要绕过内核(如 Direct Access, DAX 模式来绕过操作系统的 Page Cache)，重写数据结构等

  • 优势未利用：为传统文件系统而生的软件技术栈如驱动程序并不能很好地利用 NVMM 支持按字节寻址的特性，仍然读 4KB 修改再写回。此外，NVMM 还有更好的随机访问性能，不必太过纠结空间局部性，这也为 NOVA 对传统 LFS 的改造奠定了基础
  • 假设不成立：从访存上来看，NVMM 更类似 DRAM，硬件层面只支持到 8 Byte 的原子读写（CPU指令决定的)，而传统存储设备能保持扇区或闪存块的原子性的假设是不成立的
  • 此外，内存重排也会影响 NVMM 的数据一致性

一些相关研究在 NVMM 上颇有局限性。影子分页在处理文件系统的树形结构时需要从叶子级联影子到根，这是强顺序要求的，导致 CPU 无法进行乱序执行等优化降低并行度。传统 LFS 则基于传统存储器的局部性，在尾部追加日志和数据，导致垃圾回收操作开销太大。

三 NOVA 系统设计

日志和文件数据分离。首先，NOVA 本身是 log-structure 的，这意味着它需要 1存放实际数据 2记录日志。传统 LFS 会将日志和数据放在一起直接追加到已用空间尾部，这是基于空间局部性考虑的。而 NOVA 考虑到 NVMM 可以放宽局部性限制，几乎想跳到哪个地址就跳到哪个地址，所以分离了日志和实际文件数据。这样，可以实现数据的 copy-on-write (COW), 在更改数据时可以找个空闲页写入，然后原子单纯追加日志记录那个空闲页的地址。

数据和索引分离。无论日志还是数据都有可持久化需求，必须在非易失性存储器上，但是索引很多时候是可以用完就丢的，反正重建速度也快。基于这一点，NOVA 将空闲页索引 (RB Tree) 和 Inode 索引 (Radix Tree) 放在 DRAM 上。DRAM 还是要比 NVMM 快一些的，无论是数据结构实现还是效率上都比较有优势。此外，NOVA 还有 Per CPU 的空闲列表作为每个 CPU 独立的页分配器以防止对全局空闲页索引的锁竞争。

日志链表。日志被实现为作为一个 4KB 页的链表，在某个页都是无效日志（如都是“删除xxx”的记录）时，可以单纯只进行链表删除 (Unlink), 指针操作效率极高，不需要像传统 LFS 那样读取实际数据并且移动。

Journaling 技术。在面对多个 inode 的更改操作时，需要用到每个 CPU 独立的 journal。若要进行 mv A/file.txt B/file.txt，首先对 A 和 B 的 inode log 进行追加 ADD file.txt 和 DEL file.txt，但此时还没有更新 log tail 指针，此时这两条数据都是对文件系统不可见的。随后在 journaling 中记录 “我要原子性地同时把 A inode log 的 tail pointer 向后移动一条记录，B inode log 的 tail pointer 向后移动一条记录”，若操作成功则 mv 顺利完成，若断电故障失败则查 journaling 恢复。

细粒度锁。由于每个 inode 都有单独的 log，这允许 NOVA 为每个 inode 上单独的锁，从而支持并发修改。

四 NOVA 实现细节

一致性保证

将 NVMM 为每个 CPU 划分一个池 (pool)。对于每个 pool，将索引数据结构（通常是内存友好的数据结构）存在 DRAM 中，而 Journal 和 Inode table 存在 NVMM 中，其中每个 Inode 有自己的锁和 log 指针。Inode 的 Head, Tail 指针分别指向 log 链表的第一页首地址和最后一页已提交的地址，在 Tail 指针之后的均为无效数据，等待被原子地 commit，即 Tail 向后移动。一个文件的 Inode 仅仅存在于一个 CPU 核心的 Inode Table 中，因此所有修改都是共享的，靠 CAS 的 log tail 更新处理并发问题。

NOVA 将 Inode table 设计为初始 2MB，128 字节对齐的块数组。每个 CPU 有独立的 Inode 分配器，它们可以自由无锁地分配 Inode 空间并填充数据，然后再获取 Inode 锁把刚分配空间的地址信息记入 Inode 日志。Again，这里又是随机访问的优势。如果 NVMM 的随机访问很糟糕，那任意分配 Inode 显然会造成很差的空间局部性。值得注意的是，传统 LFS 由于垃圾回收，除了带来开销之外还会导致数据的位置（地址）被频繁移动，而 NOVA 分离日志和数据使得数据在通常情况下物理地址固定，为之后的 mmap 语义打下基础。

Journal 被设计为 4KB 的环形缓冲区，由队首和队尾指针控制，在其之间的就是还未被提交的事务。Journal 的一条记录通常包含多次修改，如 (Inode A: DEL file, Inode B: ADD file), 并且记录旧数据以用于恢复。

综合以上，NOVA 有三种原子性保证：

  • CPU 的 8 字节（64位）指令原子性保证
  • 日志结构（log-structured）实现的单个 Inode 原子性保证
  • Journaling 技术实现的多个 Inode 原子性保证

如何应对内存重排

CPU 为了避免在访存时的空等待，有时会重排一些看上去没有相关性的指令。但是在我们的例子中，log 的 tail pointer 必须在所有操作确实完成后进行，否则就失去了其事务提交和回滚的意义。

1
2
3
4
5
6
new_tail = append_to_log(inode->tail, entry); // writes back the log entry
cachelines clwb(inode->tail, entry->length);  
sfence(); // orders subsequent
PCOMMIT PCOMMIT(); // commits entry to NVMM
sfence(); // orders subsequent store
inode->tail = new_tail;

其中 clwb 用于把数据从 CPU 缓存写回到内存控制器； sfence() 用于保证其前面的指令一定比其后面的指令先可见（防止重排或乱序执行）；PCOMMIT() 用于清空内存控制器写队列保证数据被写入 NVMM 芯片上。

读写操作

对于 write 操作，NOVA 绕过 DAX，沿袭传统 LFS 的 Copy-on-Write (CoW) 方案，先在空闲页写入更改后的数据，再追加 log entry 并原子更改元数据指向的位置，旧页变为垃圾等待回收（或被作为一个版本的快照管理）。

回顾经典的 mmap：最初，操作系统只是在虚拟内存区域中分配一片地址并标记为属于对应的文件，但不分配物理地址更不加载数据。当访问到这片地址时触发内核 Page Fault，内核检查对应文件数据是否在页缓存中，如果不在就将文件数据写入 DRAM 页缓存并更改页表映射把相应物理地址映射到之前的虚拟地址上。此后的读写都只操作内存里这片页缓存，内核会异步地将脏页写回磁盘。

而在 NVMM 中，Page Cache 多此一举，因为 NVMM 本来就能够作为内存使用，所以 NOVA 是 Direct Access (DAX) 模式。NOVA 对 mmap 采用原地更新而不是像 write() 或传统 LFS 那样先写空闲页再添加日志的 CoW 方案，这使得 NOVA 的文件数据不像传统 LFS 那样频繁变动位置（NOVA 的垃圾回收只需要单纯 Unlink 掉日志链表节点并修改 bitmap），NOVA 的 mmap 不必频繁修改页表的 VPN 到 PPN 映射，提高了性能。当然，原地写入并不是原子的，但 mmap 本身也不保证原子性，要保持强一致性的话，仍然需要 CoW，并且在 msync() 时才会更改日志指针。

另外，在需要快照时，由于必须分为多个版本的页面快照、不能原地更新，也仍然需要 CoW 的方案。

初始化内存保护、恢复时懒加载与并行

野指针对 DRAM 危害较小，易失性存储器重启后就是新数据了；而一旦在野指针访问到了 NVMM 中的地址（NVMM 同样会在内核地址空间中！），可能会对本应持久化的数据造成破坏，所以通常在初始化阶段 NVMM 的区域被标记为只读，在需要操作时临时禁用 CPU 的 Write Protect, 看上去并非特别优雅的方案。

在重启恢复时，主要恢复空闲页索引和 Inode 索引。对于后者，NOVA 只会在有需要时（如某个目录或文件的 Inode 被访问）才对其进行懒加载建立索引；同时由于每个 Inode 日志有独立的锁，NOVA 允许并行读取所有 Inode 日志进行恢复。 而对于前者，则必须进行恢复，否则懒加载会导致页分配器没有足够的信息。

五 性能评估

对于微基准测试，作者测试了简单的 create append 和 delete 操作在 STT-RAM 和 PCM（相变内存，二者均为 NVMM）上，其中 create 和 append 操作，NOVA 本身的逻辑仅占总 latency 的 21%-28%，而 delete 操作中 NOVA 逻辑的 latency 占比较大由于释放数据和日志需要读取 Inode 日志。

对于宏基准测试，作则测试了文件服务器、Web 代理、Web服务器、邮件服务器四种情况，NOVA 在文件服务器和邮件服务器这样写密集业务上的吞吐量均领先（NVMM 的特性规避了写放大），而在 Web Server 和 Web Proxy 这样读密集的业务上表现一般。

作者还通过高负载写入测试 GC 压力，发现 NOVA 吞吐量平稳，几乎不受 GC 影响。同样，恢复速度也在毫秒甚至微秒级别。

六 阅读总结

NOVA 似乎目前只在学术界地位很高， 没有被 Linux 内核合并。我之前在初学的时候就有在想是否存在可持久化内存之类的东西，后来了解到好像被 Intel 玩崩了，这么看 NOVA 也是生不逢时了。不过似乎后面还有非易失性的 CXL 内存，待我往下读。为什么三天只读了一篇啊。