The No-Order File System

Modern file systems use ordering points to maintain consistency in the face of system crashes. However, such ordering leads to lower performance, higher complexity, and a strong and perhaps naive dependence on lower layers to correctly enforce the ordering of writes. Lower layers such as the hypervisor in virtual machine systems, and the disk in baremetal systems often fail to propagate or act on flushes correctly, thereby failing to enforce ordering.
An excerpt from the MAC OSX Manual Page for fsync:
F_FULLFSYNC: Does the same thing as fsync(2) then asks the drive to flush all buffered data to the permanent storage device (arg is ignored). This is currently implemented on HFS, MS-DOS (FAT), and Universal Disk Format (UDF) file systems. The operation may take quite a while to complete. Certain FireWire drives have also been known to ignore the request to flush their buffered data.
From VirtualBox's Troubleshooting manual Responding to guest IDE/SATA flush requests:
If desired, the virtual disk images can be flushed when the guest issues the IDE FLUSH CACHE command. Normally these requests are ignored for improved performance.

In this paper, we introduce the No-Order File System (NoFS), a simple, lightweight file system that employs a novel technique called backpointer based consistency to provide crash consistency without ordering writes as they go to disk. A backpointer is added to each object in the file system, and the forward and backward pointers allows us to determine consistency by cross-checking the pointers. This simple inclusion surprisingly allows us to guarantee consistency in a wide range of crash scenarios.

We utilize a formal model to prove that NoFS provides data consistency in the event of system crashes; 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.

You can take a look at the source code for the project by browsing our repository on Github.

Related Publications

Consistency Without Ordering
Vijay Chidambaram, Tushar Sharma, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau
FAST 2012
Abstract   PDF   BibTex   Talk PPT   Talk slides   Talk video  Code

Consistency Without Ordering (Extended version)
Vijay Chidambaram, Tushar Sharma, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau

Is Ordering of Disk Updates Required to Maintain File-System Crash-Consistency?
Vijay Chidambaram
Tiny Transactions on Computer Science (TinyToCS) Volume 2, 2013

Back to the home page