NOVA：一个支持混合 DRAM 和 NVMM 的结构化日志文件

前言

前段时间有幸跟 NOVA 的作者 Jian Xu 博士深入交流了一番，受益颇多，决定趁热打铁，好好研究一下 NOVA，一方面可以知道在 Linux 下面如何开发一个文件系统，而另一方面，则是想了解下当前硬件的发展水平，以及为了更好的发回硬件性能，我们需要做什么，算是对未来做一些技术调研和储备工作。

NOVA 是一个支持混合 Volatile/Non-volatile main memories 的文件系统，volatile main memory 其实 我们很容易理解，就是我们通常说的 DRAM。而 Non-volatile main memory （NVM） 则可以认为是跟 DRAM 有一样的性能（可能还是稍微比 DRAM 慢一点），但能进行数据持久化的技术，譬如我司现在就有十块基于 NVM 技术的 3D XPoint 盘，如果有同学对这块感兴趣，想尝试下为最近硬件设计程序，欢迎联系我。

NVM 预计很快就会跟 DRAM 一样，出现在处理器内存总线上面，所以融合 DRAM 和 NVMM 的特性，设计出一套更好的存储系统，我认为是有必要的。现阶段，传统的文件系统，譬如 XFS，ext4 并不能和好的工作于这种混存架构上面，所以徐博士他们就设计了一个 Non-Volatile memory Accelerated (NOVA) 的文件系统。

这里，再说一点小插曲，我开始以为 NVMM 和 NVMe 是一样的东西，于是问了徐博士这个问题，结果他告诉我两个是不一样的，真的是差之毫厘谬以千里，看来我在硬件上面的知识积累不足，后面需要多跟徐博士他们这些牛人请教。

NVMM

在开始讨论 NOVA 之前，我们可以先说说 NVMM，NVMM 这种新的硬件体系给文件系统的设计带来了新的挑战，主要有几个方面：

• 性能：NVMM 的性能非常的好，延迟非常的低。NVMM 甚至提供了 Direct Access (DAX) 或者其他方式来直接操作数据，不需要将数据拷贝到 DRAM 上面。之前的存储系统，会认为延迟的主要开销在于硬件，但现在，很可能主要开销会出现在软件层面上面。
• 写入重排：现代的处理器和它们的缓存可能会为了性能将存储指令重新排列。而对于 DRAM 来说，CPU 是能够保证一致性的，但对于 NVMM 却没有这样的保证。虽然我们可以强制 flush 缓存以及是所有内存屏障来保证写入顺序，但 clflush 会极大的降低性能，而 mfence 并不能保证写回到 NVMM 的顺序。幸运的是，Intel 已经开发了新的指令集 clfushopt， clwb，PCOMMIT，而 NOVA 就是基于这些新的指令集的。（跟徐博士聊天顺带问了下 AMD 是否也有了类似的指令集，他回答『不确定，不过应该是有了』）。
• 原子性：POSIX 类型的文件系统在很多操作上面都需要保证原子性，譬如 rename 这些，但这些操作很多会涉及到多个数据的修改，譬如 append file 这种的既要更改文件数据，也需要更改文件元信息，而 NVMM 只能提供 64 bits 的原子性保证，这对于原子性的设计是一个很大的挑战。

通常文件系统实现原子性有几种方式：

• Journaling：这个应该算是最常见的做法了，不光是传统的文件系统还有很多数据库，很多都采用的是这种做法。任何更新操作先写到 log，然后在写到实际的位置，当然这种写两份的策略并不高效，所以也有很多的优化方法，譬如只在 journaling 上面更新 metadata。
• Shadow paging：还有一些文件系统使用的是 Copy-On-Write 机制，对于更新操作不是直接写到之前的 page 上面，而是先写到另一个 page 上面，在将这个新的 page 加入到文件系统的 tree 里面，这里就需要涉及到对 tree 上面的 node 的更新，而有时候，我们需要将新 page 到 root 的所有 node 都更新一遍，这个开销还是挺大的。
• Log-structuring：虽然结构化日志很早就有，但我第一次被震撼到还是遇到了 LevelDB 的时候，它通过这种方式将随机写变成了文件的顺序追加。对于文件系统来说，其实也是一样的原理，但这些文件系统为了保证顺序追加，可能需要连续的可用存储空间，同时也需要定期的去清理过期的数据，释放空间，这些都可能造成开销。

设计

现阶段，基于 NVMM 的文件系统已经有不少了，譬如 Ext4-DAX（感觉原生的 Ext4 应该是不适用与 NVMM 的），它采用的是 Journaling 的方式，但只保证 metadata 的更新原子性，并没有保证数据的。

而 NOVA 是一个使用 log-structuring 的文件系统，但为了更好的利用 NVMM，NOVA 并没有直接使用传统的 log-structuring 的方式，而且做了改进。徐博士他们在做 NOVA 的时候，发现几个现象：

1. 支持原子更新的 log 很容易实现，但要高效的查出相关的操作其实并不容易。而要在 NVMM 里面实现一个支持高效搜索的数据结构，也是比较困难的。
2. 传统的 log-structuring 文件系统连续的存储空间，但这个对于 NVMM 来说没有这个必要，因为它的随机访问速度太快了。
3. 传统的 log-structuring 会采用单一 log 的方式，虽然会影响并发性能，但考虑到 disk 仍然是性能主要瓶颈，其实也无所谓。但在 NVMM 上面，快速，高并发的随机存取操作是完全没问题了，所以我们可以使用多个 log。

观察到以上现象之后，NOVA 就做了如下设计：

1. 将 Log 保存在 NVMM 里面，而索引则保存在 DRAM。索引使用的是 radix tree 来实现的，这个我问过徐博士，为啥选择这个数据结果，给我的答复是 kernel 里面就没几个数据结构，他们又不想自己写，就拿了一个现成可用的。
2. 每一个 inode 有一个 log。这个就是充分利用 NVMM 的随机存取高效的特性了，而且每个 inode 一个 log，不会存在并发的问题。
3. 使用 logging 和轻量级的 journaling 来进行复杂的原子更新。譬如一个文件从一个目录 move 到另一个目录，这设计到多个 inode 的修改，NOVA 会首先将操作记录到 inode 的 log 上面，然后在 journal 上面记录对应的 log tail 的改动，最后在将 log tail 更新。NOVA 的 journaling 只会记录 log tail，并且任何 POSIX 的文件操作涉及到的 inode 不会超过 4 个，所以 journaling 是非常轻量的。这里，我同时问了徐博士，这已经涉及到了几个 inode，如何保证并发，他回答道 Linux VFS 其实已经保证了，所以他们不需要做。
4. 使用链表的方式实现了 log，NOVA 使用的是 4 KB 的 page，并且在每个 page 的最后面会有一个指向下个 page 的指针。这种方式不需要分配大量的连续存储空间，同时对于 log 的清理也比较友好，回收过期的 page 只需要一些指针的操作。
5. 不记录 file data。Inode 里面只记录了 file metadata，没有记录 file data。NOVA 使用了 COW 的机制更新 file data，然后在将 metadata 追加到 log 上面。

架构

DraggedImage.png

上图是 NOVA 的整体架构，NOVA 将 NVMM 分成了四块，superblock 和 recovery inode，inode tables， journals，最后就是 log / data pages。Superblock 包含了全局的文件系统信息，而 recovery inode 则存放了用于下一次启动加速 NOVA remount 的恢复信息，inode tables 则包含 inodes，而 journals 则是为目录操作提供了原子支持，剩下的就是实际的 log 和 data 的 pages。

NOVA 为每个 CPU 设置了自己的 inode table，journal，page list，这样就能避免不同的 CPU 之间的 lock 问题。这个优化其实在 RocksDB 的 statistics 上面也有体现，它也使用了 per-CPU 模型，每个 CPU 负责自己的统计信息。

Inode Table

NOVA 首先会 为每一个 inode table 初始化一个 2 MB 的 inodes array，每一个 inode 都是 128 byte 字节，所以给定一个 inode number，NOVA 会很容易就定位到对应的 inode。

对于新增的 inode，NOVA 会使用 round-robin 算法，依次添加到各个 inode table 上面，保证整个 inodes 的均匀分布。如果一个 inode table 满了，NOVA 会再分配一个 2 MB 的 sub-table，并用链表串联起来。为了减少 inode table 的大小，每个 inode 上面有一个 bit 来表示是否 invalid，NOVA 就能重用这些 inode 给新的文件或者目录了。

一个 inode 包含指向 log 的 head 和 tail 指针，log 是一个由 4 KB page 串联的链表，tail 一直指向的是最后一个提交的 log entry，当系统第一次访问 NOVA 的时候，NOVA 会通过遍历 head 到 tail 的所有 log 去重建 DRAM 里面的数据结构。

Journal

NOVA 的 journal 是一个 4 KB 的环形 buffer，使用一对 <enqueue, dequeue> 指针来操作这个 buffer。Journal 主要是为了保证操作多个 inode 的原子性，首先 NOVA 会将更新追加到 inode 的各自 log 上面，然后开启一个事务，将涉及到的 log tail 写入当前 CPU 的 journal enqueue，并且更新 enqueue 指针，当 各个 inode 完成了自己的更新，NOVA 就更新 dequeue 指针到 enqueue，完成事务的提交。

空间管理

NOVA 将 NVMM 给每个 CPU 分了一个 pool，然后将空闲的 page list 保存在了 DRAM 里面。如果当前 CPU pool 里面没有可用的 page，就从最大的 pool 里面拿。NOVA 使用 red-black tree 按照 address 来存放空闲的 pages，正常关机下面，NOVA 会将分配好的 page 状态保存到 recovery inode 的 log 里面，但如果是非正常关机，则会遍历所有 inode 的 log 并重建。

最开始，一个 inode 的 log 只有一个 page，当需要更多 page 的时候，NOVA 直接使用 x 2 的方式，但如果 log 的长度超过了一定阈值，就每次只新分配固定数量的 pages 了。

实现

前面简单的介绍了一些 NOVA 的架构以及基本的数据结构，下面介绍下一些常用功能的大概实现。

目录操作

NOVA 的目录包括两块，一个是保存到 NVMM 里面的 inode log，另一个则是放到 DRAM 里面的 radix tree。目录的 log 包括 directory entires （也就是通常的 dentry） 和 inode update entires。Dentry 包括目录名，子目录，子文件，inode 个数，还有 timestamp 这些信息。对于改目录下面的文件操作，譬如 create，delete，rename 这些，NOVA 都会在 log 里面追加一个 dentry。 对于 delete 操作来说，NOVA 会将 dentry 的 inode number 设置为 0，用以跟 create 区分。

为了加快 dentry 的查询速度，NOVA 在 DRAM 里面维护了一个 radix tree，key 就是 dentry 的名字，而 tree 的子节点则指向 log 中对应的 dentry。

DraggedImage-1.png

上面是一个 create 的例子，我们要创建一个 zoo 的目录，会有如下几个操作：

1. 在 inode table 里面为 zoo 选择并初始化一个未使用的 inode
2. 将 zoo 的 dentry 添加到目录的 log 里面
3. 使用当前 CPU journal 更新 dir 目录的 log tail 和给新的 inode 设置一个 valid 位。
4. 将 zoo 添加到 radix tee 上面。

文件操作

NOVA 的文件 log 包含两种，一个是 inode update entries，另一个 write entries，write entry 里面会描述 write operation 以及指向实际的 data page。如果一次写入太大，NOVA 会使用多个 write entries，并将它们全部追加到 log 后面，然后最后更新 log tail。

DraggedImage-2.png

上面是一个文件写入例子，上面的 <0, 1> 这种的表示 <filepageoff, num pages>，也就是 page 的 offset 和有多少个 page。譬如 <0, 1> 就表示这个 page 的 offset 是 0， 有一个 page，也就是 4 KB。当我们要进行一次 <2, 2> 写入（也就是在 offset 为 2 的地方重新写入 2 pages），流程如下：

1. 使用 COW 技术将数据写入到 data page 上面
2. 将 <2, 2> 追加到 inode log 上面
3. 原子更新 log tail，提交这次写入
4. 更新 DRAM 里面的 radix tree，这样 offset 2 就指向了新的 page
5. 将之前旧的两个 page 放到 free list 里面

上面需要注意，虽然我们更新 log tail 是原子的，但并没有保证原子更新 log tail 和 radix tree，这里跟徐博士讨论的时候他说到，使用了一个 read-write lock，其实他觉得并不高效，后面考虑优化。

Atomic mmap

我们可以使用 DAX-mmap 技术将 NVMM 的数据直接映射到用户空间，采用这种方式，我们能直接绕过文件系统的 page cache，虽然能降低开销，但对于程序员来说还是有很大的挑战，上面说了，NVMM 只有 64 位的原子操作支持，而且一些 fence 和 flush 指令还需要依赖处理器，所以先基于这些初级的机制构造健壮的 non-volatile 的数据结构，其实是非常困难的。

为了解决这个问题，NOVA 使用了一种 atomic-mmap 的机制，它其实是使用了一个 replica pages，然后将实际修改的数据放到了 replica pages 上面，当用户调用了 msync 操作，NOVA 就会将相关的修改当做一次 write 操作处理，它会使用 movntq 指令将 replica pages 的数据拷贝到 data pages，然后在原子性的提交。

虽然采用这种方式能保证数据强一致，但并没有 DAX-mmap 高效。而对于通常 DRAM 的 mmap，NOVA 现在并不支持，未来可能有计划。

GC

NOVA 将文件的 metadata 和实际 data 不同存放，这样对于 GC 来说其实是很高效的。对于 data 来说，只要 write 操作产生了 stale data pages（就譬如我们前面说的那个例子），NOVA 就直接对 data pages 进行回收。

但回收 inode logs 就比较复杂了。我们需要确认一个 log entry 是 dead 的，首先这个 entry 不能是 log 的最后一个 entry，并且需要满足以下任意一个条件，就可以认为是 dead 了：

1. 对于 file write entry ，没有指向任何 valid 的 data page
2. 对于包含更新 inode metadata 的 entry，后面有一个新的更新同样 metadata 的 entry
3. 对于一个包含 dentry update 的 entry，已经被标记为 invalid

NOVA 使用两种 GC 方式，Fast GC 和 Thorough GC。

DraggedImage-3.png

当 NOVA 发现一个 log page 里面所有的 entries 都是 dead，那么就可以直接回收这个 page，这个仅仅需要更新 page 的指针就可以了。譬如上面流程 a 就是 Fast GC 的例子，2 这个 page 只有 dead entries 了，我们只需要将 page 1 的 next pointer 指针指向 page 3 就可以了。

如果一个 log page 里面 live entries 的数量小于一半了，NOVA 就会开始进行 Thorough GC，就是将 live entries 拷贝到另一个新的 log 上面，指向新的 log，并且回收旧的 log。上面的流程 b 就是 Through GC 的例子，NOVA 将 page 1 和 3 的 entries 拷贝到 page 5 上面，然后链接 page 5 和 page 4，并且回收 page 1 和 3。这里 NOVA 并没有处理 page 4 的 live entries，这样就用原子更新 log head，从而避免同时更新 log head 和 tail，这个没法保证原子性。

Recovery

当系统关闭并重新启动之后，NOVA 就会重现去 mount，它使用了一种延迟重建的机制，也就是只有第一次访问的时候才会去重建 radix tree 这些。对于正常关机来说，因为 NOVA 会将所有的 page 分配状态都保存到 recovery inode log 里面，所以 remount 的时候只需要从 recovery inode log 恢复就可以了。

但对于异常关机（譬如掉电）来说，NOVA 就必须重建 page 分配状态，NOVA 就需要遍历所有的 inode logs 了。但这个速度也是很快的，因为首先能每个 CPU 并发去恢复，另外，因为 log 里面不包含 data，所以 log 比较短，恢复速度自然就很快。在恢复的时候，NOVA 需要处理：

1. 检查 journal，并且回滚所有没有提交的事务
2. 每个 CPU 开启一个 recovery 线程去并发的访问 inode tables，为每个 valid 的 inode 扫描 log。对于目录 inode 来说，NOVA 只需要遍历它覆盖的 pages，并不需要读取 log 的内容。而对于文件 inode，NOVA 则需要读取 write entries 并遍历所有的 data pages。

小结

NOVA 的源码在 GitHub ，大家如果感兴趣，可以去学习一下，毕竟对于如何在新硬件体系上面做一个文件系统这种事情，还是非常酷的。这篇文章也算是我对 NOVA 的一些探究，里面如果有不对的地方，如果徐博士看到了，麻烦指正出来。

对于新硬件体系的研究，以及如何基于这些硬件体系更好的设计数据库的存储引擎，是我们未来重点会跟进的一个方向，欢迎各位对这方面感兴趣的同学加入我们 PingCAP，你可以直接给我发邮件 tl@pingcap.com。毕竟从头开始打造一个未来的存储引擎，我觉得是一件非常有意思，有挑战的事情。