Better I/O Through Byte-Addressable, Persistent Memory

现代的计算机系统一般是通过基于块的接口来缓慢地访问持久性存储的，但近年来，像Phase-Change Memory这种基于字节寻址的持久性存储技术提供了更快速、和更细粒度的访问方式。本论文介绍了新的文件系统和硬件体系结构，具备基于字节寻址持久性内存的属性。

INTRODUCTION

新的基于字节寻址的持久性存储技术（BPRAM）消除了volatile和non- volatile存储之间的许多传统差异，尤其是随着Phase-Change Memory和memristors等技术的发展，也可像DRAM一样按字节寻址，同时能够像磁盘一样持久化。

本文通过研究文件系统来探索BPRAM的好处，并为BPRAM线了一个新的文件系统BPFS，提供了远快于传统基于块存储设备的文件系统的速度。此外，与现有系统相比，BPFS通过一种short-circuit shadow paging的新技术来提供了强大的安全性和一致性保证。

BPFS的存储方法在一些重要方面与传统文件系统也存在不同，包括不将DRAM缓冲区高速缓存用于文件系统数据，针对小型随机写入进行优化，减小了尚未持久的数据漏洞窗口。

DESIGN PRINCIPLES

论文主要关注两个目标：

设计对BPRAM的体系结构支持；
设计一个文件系统，以利用BPRAM的属性来提高性能和可靠性；

Expose BPRAM Directly to the CPU

传统的永久性存储位于总线控制器和存储控制器的后面，由于对这些控制器的访问带来的性能损耗，即使是最快的NAND闪存SSD，延迟也要几十微秒。

论文的做法是，将BPRAM直接与DRAM并排放置在内存总线上，使得CPU能够在BPRAM的地址上加载和存储，降低访问延迟。另外，BPRAM的可寻址还能够利用高速缓存的层次结构来提高对持久性存储器的写入性能。

但将BPRAM放在内存总线上也是有一些缺点：

BPRAM的流量有可能会干扰易失性存储器的访问并进一步损害整体系统性能；
系统中可用的BPRAM数量受BPRAM密度和计算机中可用DIMM插槽数量的限制；
若应用或驱动程序存在缺陷，则可能导致杂散写入，即stray write；

因此不建议用BPRAM完全替代DRAM，虽然论文也提到一些论据证明这几个缺点不是很大问题的。

Enforce Ordering and Atomicity in Hardware

为了保证安全性和一致性，文件系统需要清楚写入持久性存储的顺序和时间。但执行强制性的排序约束会对性能有一定的影响。文中提出了一种软件机制来声明对硬件的排序约束，软件可以发出特殊的写屏障，以分隔一组epoch的写操作，而硬件将保证每个epoch都按顺序写回到主存器中。

除了对顺序的限制外，文件系统还考虑对应对故障原子性的问题，如果由于电源故障而中断对持久性存储的写操作，则该存储器可能会处于中间状态，从而破坏了一致性。借助BPRAM，可以直接在硬件中提供一个简单的原子写入基元。

Use Short-Circuit Shadow Paging

大多数存储系统都使用以下两种方式来确保可靠性：WAL预写日志和影子分页shadow paging。WAL会使得大多数写入需要进行两次操作，而shadow paging则是实用写时复制来执行所有更新。由于shadow paging每次写入都会因为传播到文件系统根目录树而输出多个块，shadow paging的副本成本远超日志记录，因此目前应用都是使用前者。

但BPRAM的字节寻址能力和快速的随机写入使影子分页成为文件系统设计的一种高效方法，BPFS通过实现一种称为短路影子寻呼（SCSP）的新技术，允许BPFS在文件系统树中的任何位置提交更新，从而避免了将副本传播到文件系统根目录所产生的开销。

BPFS DESIGN AND IMPLEMENTATION

File System Layout

BPFS的持久数据结构组织成了一个具备固定大小的块的树，使得能够原子更新树的任意部分，并且块大小固定使得释放和分配都比较方便。

BPFS数据结构由三种文件组成，每种文件都由相同的树数据结构表示。

索引节点文件是一个包含固定大小的索引节点数组的单个文件，每个索引节点表示文件系统中的某个文件或目录；
目录文件包含目录项数组，该目录项数组由inumber（即inode文件中inode的索引）和相应文件的名称组成；
数据文件仅包含用户数据；

所有文件都是由相同的数据结构组成的，即一棵全由4K块组成的树。树的叶节点代表文件的数据（即用户数据，目录条目或索引节点），每棵树的内部节点包含了指向树的下一级的512个64位指针。文件系统的根结点就是inode文件。

每个树的高度由树的根指针的低位所表示，这使得BPFS可以通过记住从中获取的数来确定给定的块是内部节点还是叶子节点。对于高度为0的树，根指针直接指向一个数据块，该数据块最多可以包含4KB的文件数据。在高度树为1的情况下，根指针指向512个指针的内部块，每个指针指向4KB数据块，总共2 MB。以此类推。内部节点没有存储文件数据。

为了简化将数据写入文件中间的任务，我们在树的任何级别使用空指针，以此表示该指针跨越的文件某个范围内的零数据。例如，如果文件的根指针是高度为5的空指针，则它表示一个空的256TB文件。空指针也可以出现在内部节点上，此文件就可以实现大型的稀疏文件的紧凑表示形式。另外，还会存储每个文件的大小以及每个根指针，若文件较大，则假定文件的尾部为零；若文件较小，则忽略文件末尾在树中的任何数据。这样能够在不更新树本身的情况下更改文件大小。

Persistent Data Updates

Short-circuit shadow paging通过三种不同的方法来更新持久性数据：

就地更新：由于硬件能保证这些更新是原子的，因此能对64位或更少位数的写入执行就地更新。
就地追加：就地追加利用了每个文件的根指针附带着文件大小变量。由于超出文件大小的所有数据都将被忽略，因此可以安全地就地写入这些位置，并且一旦写入了所有数据，我们就可以自动更新文件大小来扩展有效数据范围；
写时复制：在将受此操作影响的树的所有部分上执行写时复制，直到可以通过一次写操作可以提交变更的最少部分。

对于所有这些操作，必须要在提交该操作的原子写入之前和之后发出epoch barriers。这些屏障确保了提交之前所有写操作都先将被刷新到BPRAM，并且任何后续的文件系统操作都将在提交之后进行。

Volatile Data Structures

该文件系统布局允许对持久状态进行高效可靠的更新，因此暂不允许将诸如哈希表之类的复杂数据结构存储在持久内存中。但考虑到这些复杂数据结构可以提高性能，因此在易失性内存中维护一些派生的数据结构。这里介绍了三个：

在DRAM中存储的空闲BPRAM块列表以及释放或者分配的inumber列表，这些数据结构在每次启动时都从文件系统元数据初始化。
正在进行的写时复制操作中已释放和已分配的块列表。
第三个数据结构存储用户打开的每个目录中目录条目的缓存。

File System Operations

由于所有BPFS文件类型都使用BPFS树数据结构，因此的论文实现了一组核心routines——crawler，它们可以遍历这些树并可以对三种文件执行读写操作。为了执行这些操作，需要为crawler提供根指针，树的高度，文件偏移范围和回调函数。crawler到达叶节点后，它将使用适当的地址调用回调。

crawler负责更新树的高度和内部指针。更新高度的操作：先查看请求的文件偏移量是否超出当前文件树所覆盖的偏移量，如果超过了，则以原子操作使树的高度增加适当的数量。

在叶节点上，crawler将调用一个回调，如果该回调希望执行写时复制操作，它将分配一个新块，执行任何必要的更新，然后必须适当地更新任何内部节点。如果回调未进行任何修改，则crawler将返回未触及的现有指针块。如果回调仅修改了一个指针，那么crawler将就地提交该操作。如果修改了多个指针，crawler将对该指针块进行完整复制，将提交推迟到树中的高层节点。

下面是单个的文件系统操作：

Open：打开文件后，BPFS会解析路径并使用目录项缓存来查找目标文件或目录；如果该文件不存在，并且请求创建，则从可用列表中声明一个新的inumber，然后以适当的偏移量将一个新的inode写入inode文件。写完后，将一个新目录项写入包含文件的目录中，最后更新易失性存储器中的目录条目缓存；
Read：读取文件时，BPFS在文件的适当范围内调用crawler。读取的回调将数据块中的数据复制到用户提供的缓冲区中，然后使用就地原子写入来更新访问时间；读取目录则是将目录加载到目录条目缓存（如果尚未缓存）中；
Write：写入文件时，可能需要对inode本身执行写时复制操作。顶层crawler对inode文件进行操作，并找到目标文件的inode，然后在此文件的适当范围上调用写crawler，并确定是否可以就地更新，如果不可以则使用写时复制。如果需要同时更新文件大小和inode内文件的根指针，将对inode块本身执行写时复制，然后将新版本返回给inode文件；
Close：关闭文件或目录后，BPFS会检查该文件或目录是否已标记为删除。如果是，crawler则到目录条目的位置写入inumber为0来表示删除。最后则更新易失性数据结构，包括空闲块列表和空闲inumber列表；

Multiprocessor Operation

BPFS保证将更新按顺序提交给BPRAM。在单处理器系统上，epoch barrier通过按照创建它们的顺序将从缓存子系统中拿到epoch来强制执行此保证。

对于多处理器的情况，硬件修改可确保如果在两个不同的CPU上发出了共享状态的两个epoch，那么这些epoch将被序列化。但如果进程或线程在两个不同的CPU上执行时更新了两个不同的状态，则可以按任何顺序将更新写回PCM。为了正确实现这些更新，必须考虑三种情况：

可以在单个文件系统操作期间在多个CPU上调度线程；
可以在两个不同的文件系统操作之间将线程切换到新的CPU；
两个进程可以在两个不同的CPU中更新文件系统中的两个不同位置；

BPFS的当前实现尚未强制执行前两个约束。

Limitations

BPFS也存在一些局限性：

其一是写入时间不像写入本身进行原子更新，这是基于性能的折衷考虑；
另一个局限性是跨越树一大块的原子操作可能需要大量额外的副本；
还有一个局限是BPRAM的整体接口实现了新的文件系统，并没有提供持久化的用户级堆；

HARDWARE SUPPORT

Phase Change Memory

Phase change memory即PCM是一种非易失性且基于字节寻址的新型存储技术，能提供与DRAM相近的访问速度，也可以组织成类似于DRAM的阵列结构。本论文的假设是基于PCM的存储系统被组织成放置在与DDR兼容的DIMM中一组PCM芯片。

Wear Leveling and Write Failures

尽管PCM比一般的NAND闪存的写耐久性更高，但考虑到PCM放置在存储器总线上而不是I/O总线上，单元将暴露于更大更多的写入活动，因此需要进行耗损均衡：

最小化写入的方式设计PCM阵列，延长使用寿命；
在每个页面内，通过旋转内存控制器级别的位来使损耗均匀；
在页面之间，可以通过定期交换虚拟页面到物理页面来使损耗均匀映射；

Enforcing Atomicity

为了对8字节的写入保证原子性，必须要确保在电源故障的情况下，写入要么完全完成（所有位适当更新），要么完全失败（所有位都处于原始状态）。论文建议通过增加DIMM的容量来增强原子性，使得该电容器具有足够的能量来完成PCM子系统中正在进行的最大写入事务数。

Enforcing Ordering

现代的高速缓存和内存控制器可以重新排列从CPU到内存的写入顺序。考虑到使用BPRAM代替DRAM，写回发生的顺序会变的很重要，例如如果高速缓存控制器在选择在写回缓冲区之前先写回指针更新，则BPRAM中的文件系统将不一致，这种不一致性一般会因为高速缓存一致性和内存屏障机制变得不可见。但如果在所有数据都写回到BPRAM之前发生电源故障，则重新引导计算机时文件系统将变得不一致。为了避免这种情况，需要遵守任何排序约束。

强制排序有多种选择。一种可能是使用直写式缓存；第二种是在每个内存屏障处刷新整个缓存，以确保所有数据都以正确的顺序到达非易失性内存中；第三种是跟踪在操作期间已修改的所有高速缓存行，以便仅刷新包含脏文件系统数据的行。

这几种方法都有明显的问题，论文的解决方法是允许软件将排序约束明确地传达给硬件，即epoch barrier。epoch是从同一线程向持久性存储器进行写入的序列，由软件发出的新型存储器屏障来界定。

CONCLUSION

本文主要介绍了一种文件系统，支持按字节寻址和持久化内存，同时也介绍了一种硬件体系来确保原子性和顺序保证。新型文件系统使用了short-circuit shadow paging的技术来提供较强的安全性和一致性保证。