UW-Madison Logo

The ADvanced Systems Laboratory (ADSL)
Publication abstract

Orderless and Eventually Durable File Systems

Vijay Chidambaram
Department of Computer Sciences ,
University of Wisconsin-Madison


Critical data from different fields such as health-care, finance, and governance is being stored digitally. Given that even well prepared events such as Super Bowls and large data-centers experience power-loss, it is important to protect storage systems against the threat of power loss and system crashes.

Current solutions for maintaining file-system crash consistency, such as journaling and copy-on-write, cause significant performance degradation. As a result, practitioners disable these solutions to increase performance. In this dissertation, we present crash-consistency solutions that offer both excellent performance and strong guarantees after a crash.

In the first part of this dissertation, we analyze the factors that lead to file-system inconsistency in the event of a crash. We show that for certain workloads, a crash will rarely leave the file-system inconsistent. Other workloads such as database update queries have a significant risk of file-system inconsistency upon crash. We define persistence properties, aspects of file-system behavior that affect application-level crash consistency. We build a tool named the Block-Order Breaker, and study how persistence properties vary across sixteen file-system configurations.

In the second part of this dissertation, we design two new crash-consistency protocols: backpointer-based consistency and optimistic crash consistency. Backpointer-Based Consistency is the first protocol to provide strong crash-consistency guarantees without flushing the disk cache. Optimistic Crash Consistency eliminates flushes in the common case, and decouples ordering from durability. Both protocols increase performance significantly. We also introduce a new primitive, osync(), that applications can use to order writes.

Our dissertation shows that is possible to build crash-consistent systems that obtain excellent performance. The techniques introduced in this dissertation can be applied broadly in various contexts. The principles of Optimistic Crash Consistency have already been applied in distributed systems. With new storage technologies around the corner, existing crash-consistency solutions will prove too expensive: we show that orderless, asynchronous writes can be used as foundation to build storage systems that offer high performance and strong guarantees.

Full Paper: PDF   BibTeX