Crash Consistency: Rethinking the Fundamental Abstractions of the File System

Abstract

The reading and writing of data, one of the most fundamental aspects of any Von Neumann computer, is surprisingly subtle and full of nuance. For example, consider access to a shared memory in a system with multiple processors. While a simple and intuitive approach known as strong consistency is easiest for programmers to understand, many weaker models are in widespread use (e.g., x86 total store ordering); such approaches improve system performance, but at the cost of making reasoning about system behavior more complex and error-prone. Fortunately, a great deal of time and effort has gone into thinking about such memory models, and, as a result, most multiprocessor applications are not caught unaware.

References

1. Alagappan, R., Chidambaram, V., Sankaranarayana Pillai, T., Arpaci-Dusseau, A. C., Arpaci-Dusseau, R. H. 2015. Beyond storage APIs: provable semantics for storage stacks. In the 15th Workshop on Hot Topics in Operating Systems, Kartause Ittingen, Switzerland (May).
2. Al-Kiswany, S. 2014. Namenode fails to boot if the file system reorders rename operations; http://issues.apache.org/jira/browse/HDFS-6820.
3. Aurora, V. 2009. POSIX v. reality: a position on O_PONIES; http://lwn.net/Articles/351422/.
4. Austin Group Defect Tracker. 2013. 0000672: Necessary step(s) to synchronize filename operations on disk; http://austingroupbugs.net/view.php?id=672.
5. Chen, H., Ziegler, D., Chlipala, A., Kaashoek, M. F., Kohler, E., Zeldovich, N. 2015. Specifying crash safety for storage systems. In the 15th Workshop on Hot Topics in Operating Systems, Kartause Ittingen, Switzerland (May).
6. Corbet, J. 2009. Ext4 and data loss; https://lwn.net/Articles/322823/.
7. Corbet, J. 2009. That massive filesystem thread; http://lwn.net/Articles/326471/.
8. Davies, C. 2011. Fake hard drive has short-term memory not 500GB. SlashGear; http://www.slashgear.com/fake-hard-drive-has-short-term-memory-not-500gb-08145144/.
9. Edge, J. 2015. Testing power failures; https://lwn.net/Articles/637079/.
10. Ganger, G. R., Patt, Y. N. 1994. Metadata update performance in file systems. In Proceedings of the 1st Symposium on Operating Systems Design and Implementation: 49-60, Monterey, California (November).
11. Garcia-Molina, H., Ullman, J. D., Widom, J. 2008. Database Systems: The Complete Book. Prentice Hall Press.
12. Hagmann, R. 1987. Reimplementing the Cedar file system using logging and group commit. In Proceedings of the 11th ACM Symposium on Operating Systems Principles, Austin, Texas (November).
13. Kim, H., Agrawal, N., Ungureanu, C. 2012. Revisiting storage for smartphones. In Proceedings of the 10th Usenix Symposium on File and Storage Technologies, San Jose, California (February).
14. Lamport, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers 28(9): 690-691.
15. Mercurial. 2014. Dealing with repository and dirstate corruption; http://mercurial.selenic.com/wiki/RepositoryCorruption.
16. Microsoft. Alternatives to using transactional NTFS; https://msdn.microsoft.com/en-us/library/windows/desktop/hh802690(v=vs.85).aspx.
17. Open Group Base Specifications. 2013. POSIX.1-2008 IEEE Std 1003.1; http://pubs.opengroup.org/onlinepubs/9699919799/.
18. Sankaranarayana Pillai, T. 2013. Possible bug: fsync() required after calling rename(); https://code.google.com/p/leveldb/issues/detail?id=189.
19. Sankaranarayana Pillai, T. 2013. Possible bug: Missing a fsync() on the log file before compaction; https://code.google.com/p/leveldb/issues/detail?id=187.
20. Sankaranarayana Pillai, T., Chidambaram, V. Alagappan, R., Al-Kiswany, S., Arpaci-Dusseau, A. C., and Arpaci-Dusseau, R. H. ALICE: Application-Level Intelligent Crash Explorer; http://research.cs.wisc.edu/adsl/Software/alice/.
21. Sankaranarayana Pillai, T., Chidambaram, V., Alagappan, R., Al-Kiswany, S., Arpaci-Dusseau, A. C., Arpaci-Dusseau, R. H. 2014. All file systems are not created equal: on the complexity of crafting crash-consistent applications. In Proceedings of the 11th Symposium on Operating Systems Design and Implementation, Broomfield, Colorado (October).
22. Sewell, P., Sarkar, S., Owens, S., Nardelli, F. Z., Myreen, M. O. 2010. x86-TSO: a rigorous and usable programmer's model for x86 multiprocessors. Communications of the ACM 53(7): 89-97.
23. Shvachko, K., Kuang, H., Radia, S., Chansler, R. 2010. The Hadoop Distributed File System. In Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies, Incline Village, Nevada (May).
24. Sorin, D. J., Hill, M. D., Wood, D. A. 2011. A Primer on Memory Consistency and Cache Coherence. Morgan & Claypool Publishers.
25. Terry, D. 2011. Replicated data consistency explained through baseball. MSR Technical Report (October).
26. Verma, R., Mendez, A. A., Park, S., Mannarswamy, S. S., Kelly, T. P., Morrey, C. B., III. 2015. Failure-atomic updates of application data in a Linux file system. In Proceedings of the 13th Usenix Symposium on File and Storage Technologies, Santa Clara, California (February).
27. VMWare. Software-defined storage (SDS) and storage virtualization; http://www.vmware.com/software-defined-datacenter/storage.
28. VMWare. The VMware perspective on software-defined storage; http://www.vmware.com/files/pdf/solutions/VMware-Perspective-on-software-defined-storage-white-paper.pdf.
29. Zheng, M., Tucek, J., Huang, D., Qin, F., Lillibridge, M., Yang, E. S., Zhao, B. W., Singh, S. 2014. Torturing databases for fun and profit. In Proceedings of the 11th Symposium on Operating Systems Design and Implementation, Broomfield, Colorado (October).

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles