面向非易失性存储介质的文件系统设计、实现与形式化验证

主讲人：陈海波老师（上海交通大学教授， IPAD 小组导师，华为鸿蒙系统研发）

Background：How to Climb Up the Memory Hierarchy

Jim Gray 对于存储层次（Memory Hierarchy）演进的经典论断：Tape is Dead, Disk is Tape, Flash is Disk, RAM Locality is King.

JG 论断提出的背景是 06 年 SSD 刚刚出来，那么随着硬件技术的发展，JG 的论断也该有新的诠释。

Non-volatile Memory(NVM) Revolution

产品化元年

非易失性存储硬件的出现，Non-volatile Memory（NVM），带来的数据可持久化是颠覆性的改变。从体系结构的角度，CPU 内部整合内存虽然还没有实际上发生，但是今年发生的一件事是，放了许多年鸽子的 NVM Memory 终于产品化了，今年三月份 Intel 开始对外出售，中文名傲腾系列。3D XPoint 维基百科

先前为了实现 Persistence（持久化），NVDIM 技术是附加电容，在断电时通过电容，将 RAM 的数据刷到硬盘中，从而达到持久化的效果。

抉择：Performance vs. Persistence，以传统结构来说，选择 Performance，我们减少写回磁盘的次数，而主要在 RAM 上操作，但是这就面临掉电丢失数据的风险，难以持久化，而若选择 Persistence，频繁写入磁盘，则在 IO 上就要耗费更多的时间，效率降低。

Intel Optane DC Persistent Memory 性能表现

在 NVM 产品化元年，真正的 Persistent Memory 到来时，如果针对其特性构建系统？

改变 Memory Hierarchy

改变了其中的易失/持久的边界

不成比例扩展效应 Incommensurate scaling

如果计算机体系结构某个部分突然快 10 倍，便会使人们重新审视整个系统，调度、Storage 管理

As a system increases in size or speed, not all parts of it (&human factors) follow the same scaling rules. -- Saltzer & Kaashoek

考虑 NVM 带来的影响，如下图，非易失性设备访问速度提升了 1000-10000 倍，不仅系统本身，评测系统的 Benchmark，思考问题的角度，都需要重新调整。

启发

Tape is Dead, Disk is Tape, Flash is Disk,

RAM is Flash, Cache Locality/Parallelism is King?

从硬件革新，重新审视系统的软件栈。

SoupFS

An NVM file system in Kernel(USENIX ATC'17)

为什么在乎文件系统

文件系统储存我们所有的数据
文件系统的表现是系统整体表现得关键
文件系统是解决 Performance 和 Persistence 矛盾得关键

现有得 NVMFS 使用日志（journaling）或者边复制边写（copy-on-write）的方式来实现崩溃时保持一致性（crash consistency），但由于 CPU cache 仍然是易失的，由此引发出明显的性能问题：

同步 cache 和 NVM 导致 cache flushes 是必要的
cache flushes 代价很大

思考：不适用这两种方式，其他方式实现 crash consistency？

有的，前人也做过研究：1999 年 Marshall 和 Gregory R. Ganger 在 USENIX 上发表论文介绍的方法：Soft Updates

Soft Updates

What Is Soft Updates

主要思想：在磁盘中维护一个元数据，不和 DRAM 实时同步，但保证与 DRAM 的元数据的依赖关系相同（两地元数据都需要增加依赖关系的标识，这是新的要求）。

带来的好处：异步操作、依赖关系保证一致性、无需磁盘检查。

Soft Updates is Complicated

这一理念在学术界有所影响，但工业界影响微乎其微：依赖关系复杂，实现太过困难。

Soft updates are, simply put, too hard to understand, implement,and maintain to be part of the mainstream of file system development -- Valerie Aurora, Linux Kernel Developer

海波老师的团队研究认为，这种复杂性的根本是：细粒度的 Cache 记录跟踪（Byte 级别）和粗粒度的磁盘读写（512K 或以上）接口之间的不匹配

Soft Updates Meets NVM

Soft Updates

没有同步 cache flushes 的消耗
崩溃可即时恢复可用

NVM

Byte 级别且快速，原有粒度不匹配问题改善
直写 NVM 没有延迟
没有伪共享（false sharing） => no rolling back/forward
简化了跟踪依赖的操作

新的挑战：由于 NVM 是 M，Memory，那就存在着用户未预料的 CPU 将 Cache 数据刷回 NVM 的过程（cache eviction），这就带来了不一致性。

SoupFS

A simple and fast NVMFS derived from soft updates.

哈希表目录（解决 false sharing）
依赖指针的双视图（解决同步 cache flushes 开销）
语义感知以来跟踪

着重讲双视图一块的设计

Dual Views

哪两个视图

Latest view in page cache（在 DRAM 中）
Consistent view in disks

为了避免两个视图两份拷贝的额外开销，进一步提高效率，通过 Pointer 指向，来复用元数据的数据结构来避免不必要的重复和刷新。

具体的数据结构设计不再赘述，可以参考 SoupFS 论文

一个例子，从图示看很像 Data structure 中每个结点实现了一个双指针分别指向下一个 Consistent 节点（NVM View 中）和 Latest 节点（RAM View 中）。

Q&A

Q1. 使用 NVM 为什么还要使用 File System，数据库方式可以跳过直接操作底层的 metadata？ A1. 当然对于 NVM 下还要不要做 File System 业界是有争论的，我的看法是系统发展要有演化路径，File System 是一个通用的“范型”，可以利用 File System 实现更多基于 File System 的上层技术。

Q2. NVMFS 有没有对垃圾回收机制带来新的要求和挑战？ A2. 之前学术界有相关研究比如 NV Allocate，主要研究在 NVM 上如何分配和管理空间，这样必然会涉及垃圾回收这一问题。我们这边也有涉及 Garbage Collector 的相关工作，主要关心掉电后数据流有/没有被分配

Q3. 为什么考虑文件目录使用 HashTable 而非红黑树、B+树，这样的话范围查询效率不会很低吗？ A3. 首先考虑到实现简单，而且对于 NVM 来说，相较于之前的 Disk 访问速度已经很快了，范围查询拆成单点查询可能都要比原有设备的范围查询快，就是拖到内存里扫一遍的过程。