One-line Summary
The authors present the optimistic crash consistency and an optimistic journaling system (OptFS) which implements optimistic crash consistency and maintains consistency to the same extent as pessimistic journaling while achieving the same performance as with probabilistic consistency.
Paper Structure Outline
Pessimistic Crash Consistency
Flushing Performance Impact
Probabilistic Crash Consistency
Quantifying Probabilistic Consistency
Factors affecting P_inc (probability of inconsistency)
Optimistic Crash Consistency
Asynchronous Durability Notification
Optimistic Consistency Properties
Optimistic Techniques
In-Order Journal Recovery
Background Write after Notification
Selective Data Journaling
Durability vs. Consistency
Implementation of OptFS
Asynchronous Durability Notifications
Case Studies
Atomic Update within Gedit
Temporary Logging in SQLite
Background & Motivation
~5x performance difference based on flushing! In file system journaling, pessimistic journaling (default) incurs extra work due to unnecessary flushing (assuming crash does not happen). In probabilistic journaling, typical operations may or may not result in much reordering, so the disk is only sometimes in an inconsistent state and thus flushes can be disabled. Although probabilistic crash consistency does not guarantee consistency after a crash, many practitioners use it due to performance degradation from flushes.
The authors define crash inconsistency probability as the proportion of vulnerability window (due to re-ordering) length. P_inc = Time in window(s) / Total I/O time. If a workload is mostly read oriented, there is little chance of inconsistency, as the FS state is not update frequently. Early commit is the largest contributor to P_inc, accounting for over 90% of inconsistency across all workloads. The idea of optimistic crash consistency comes from the optimistic concurrency control (OCC) from distributed transaction systems.
Design and Implementation
OptFS decouples fsync() into two novel primitives: dsync() for immediate durability as well as ordering, and osync() for write ordering/atomic updates but only eventual durability.
Optimistic techniques
A number of techniques are used: In-order journal recovery and release, checksums, background writes after notification, reuse after notification, selective data journaling.
Checksums (over D and J_M into J_C) remove the need for ordering writes. Optimistic crash consistency eliminates the need for ordering during transaction commit by generalizing metadata transactional checksums to include data blocks. During recovery, transactions are discarded upon checksum mismatch.
Asynchronous Durability Notifications (ADN)
ADNs are used to delay checkpointing a transaction until it has been committed durably (M is only written when D, J_M and J_C are all written). Fortunately, this delay does not affect application performance, as applications block until the transaction is committed, not until it is checkpointed. Additional techniques are required for correctness in scenarios such as block reuse and overwrite. ADNs improve performance because:
The disk can schedule blocks from the cache to platter in the best order
The file system can do other work while waiting for ADN
(Main) The user applications do not have to wait for ADN
Selective data journaling
Selective data journaling places both data and metadata in the journal to keep locality OptFS is implemented as a variant of the ext4 file system inside Linux 3.2.
OptFS achieves good reliability OptFS has a good performance when crashes are rare and I/Os are infrequent. However, overwrites have a bad performance The FS needs to consume more CPU & memory for maintaining extra information like for delayed checkpointing. Among the many techniques for ensuring consistency, OptFS is the only one that is flexible enough to accomodate all circumstances and has the best {consistency, performance, availability, durability}. Thanks to Guanzhou Hu & Pei-Hsuan Wu for the paper review notes!
Prof. Andrea's CS 736 course slides on ALICE and OptFS
