optfs-optimistic-crash-consistency.md

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

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.

{% hint style="info" %}

• D: Data write
• J_M: Loggin Metadata
• J_C: Logging Commit
• M: Checkpointing {% endhint %}

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

Implementation

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

Evaluation

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!

{% file src="../../.gitbook/assets/OptFS+Alice.pptx" %} Prof. Andrea's CS 736 course slides on ALICE and OptFS {% endfile %}