Consistency Without Ordering

0x00 引言

这篇Paper讲的是如何利用backpointer-based consistency的技术来实现不依赖于操作顺序的Crash一致性,

we show through experiments that NoFS is robust to such crashes, and delivers excellent performance across a range of workloads. Backpointer-based consistency thus allows NoFS to provide crash consistency without resorting to the heavyweight machinery of traditional approaches.

0x01 基本思路

NoFS的基本思路还是很简单的，如下面的图所示，NoFS通过在一些文件系统的元数据和数据后面添加了一个Breakpointer指针来实现一致性的检查，

Paper中对一致性的一个理解就是：

Data consistency provides the guarantee that all the data accessed by a file belongs to that file; it may not be garbage data or belong to another file.  This guarantee is obtained when a backpointer is added to a data block.

简而言之就是访问一个文件的数据的时候能够保证访问的数据确实是这个文件的。基于这个思想，NoFS通过添加一个Breakpointer指针来执行从属关系的一个检查。从从文件的元数据获取到这个文件的一个数据块的信息之后，去读取这个数据，检查这个数据块的Breakpointer，如果将检查通过就可以确定这个数据库是这个文件的一部分。对于文件夹来说也是同样的道理。当一个数据块被一个文件删除然后分配给另外的文件之后，在这个Breakpointer上面就会反映出来。

但是这里Breakpointer也存在这样一个问题，它会不会保证它现在确实是属于这个文件，因为可能是曾经属于，而现在已经被这个文件删除了，也就是说它属于的是这个文件的旧的版本。在Breakpointer说明是不会保持这种版本上面的信息的。为了解决这个问题，这里可以采用了添加时间戳检查的方式，

Each data block has a timestamp indicating when it was last updated. This timestamp is also stored in the inode containing the data block. When a block is accessed, the timestamp in the inode and data block must match. Since timestamps are a way to track versions, the versions in the inode and data block can be verified to be the same, thereby providing version consistency.

但是，这里也只是可以通过这种方式解决而是，NoFS并没有采用这种方式，因为这种方式带来的维持这个版本的开销很大，对性能有比较大的影响。所以NoFS并不提供version consistency。在NoFS中，检查不一致性和在Crash之后恢复是通过检查数据、元数据和Breakpointer的对应关系是否是一致的。另外，在无序的文件系统中，一些表示空间分配的结构是不可性的，如标记Block是否被分配的bitmap。所有的分配的信息在使用之前都需要被验证。所以NoFS旧直接将这些信息保存在内存中，

NoFS can verify whether a block is in use by checking the file that it has a backpointer to; if the file refers to the data block, the data block is considered to be in use. Similarly, NoFS can verify whether a file exists or not by checking the directories in its backpointers. 

0x02 实现

几点关于NoFS实现的内容：

• NoFS基于ext2文件系统来实现的；
• 子NoFS中，包含了3中不同类型的Breakpointer，Block backpointers是 {inode number, block offset}这样的一个元组，迎来数据追踪到所属的inode，而Directory backpointer 是用来目录块回溯追踪到所属的inode，另外的Back links则是当前inode追踪到所属的父inode的。

• 恢复，上面三种Breakpointer的存在使得恢复并不是一个很复杂的工作，但是也是包含了不少的内容。下面的图中就表示了如何利用Breakpointer来处理Crash。

• 非持久化的分配结构，因为这些类似块分配的bitmap的结构都是非持久化的。一个问题就是如果构建这个结构，NoFS使用的方式是扫描：metadata scanner 和 data scanner，

   Since every block and inode has a backpointer, it can be determined to be in use by examin- ing its backlink or backpointer, and cross-checking with the inode mentioned in the backpointer. As every object is examined, consistent file-system state is built up and eventually complete knowledge of the system is achieved.
  

• 限制，NoFS这种方式很轻量级，但也是存在不少缺陷的。一个问题就如下面的所说的，Breadkpointer没有版本信息。另外，NoFS也不提供原子事务；还有就是对于一些情况下访问之前的验证操作可能是一个不小的开销。

0x03 评估

参考

1. Consistency Without Ordering, FAST’12.