# Consistency Without Ordering

## Consistency Without Ordering

### 0x00 引言

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.


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 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基于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也不提供原子事务；还有就是对于一些情况下访问之前的验证操作可能是一个不小的开销。

## 参考

1. Consistency Without Ordering, FAST’12.