OptFS: Optimistic Crash Consistency

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

1. Introduction

2. Pessimistic Crash Consistency

   1. Disk Interface

   2. Pessimistic Journaling

   3. Flushing Performance Impact

3. Probabilistic Crash Consistency

   1. Quantifying Probabilistic Consistency

   2. Factors affecting P_inc (probability of inconsistency)

      1. Workload

      2. Queue Size

   3. Summary

4. Optimistic Crash Consistency

   1. Asynchronous Durability Notification

   2. Optimistic Consistency Properties

   3. Optimistic Techniques

      1. In-Order Journal Recovery

      2. In-Order Journal Release

      3. Checksums

      4. Background Write after Notification

      5. Reuse after Notification

      6. Selective Data Journaling

   4. Durability vs. Consistency

5. Implementation of OptFS

   1. Asynchronous Durability Notifications

   2. Handling Data Blocks

   3. Optimistic Techniques

6. Evaluation

   1. Reliability

   2. Performance

   3. Resource consumption

   4. Journal size

7. Case Studies

   1. Atomic Update within Gedit

   2. Temporary Logging in SQLite

8. Related Work

9. Conclusion

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.

Types of re-ordering

• D: Data write

• J_M: Loggin Metadata

• J_C: Logging Commit

• M: Checkpointing

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

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

Implementation

OptFS is implemented as a variant of the ext4 file system inside Linux 3.2.

Evaluation

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}.

New Vocabulary

• Optimistic concurrency control (OCC)

• Checksums

Links

• Paper PDF

• Presentation video at SOSP '13

• Source code for OptFS (Linux ext4 implementation)

• Thanks to Guanzhou Hu & Pei-Hsuan Wu for the paper review notes!

4MB

OptFS+Alice.pptx

Prof. Andrea's CS 736 course slides on ALICE and OptFS