Resolving journaling of journal anomaly in android I/O: multi-version B-tree with lazy split

Abstract

Misaligned interaction between SQLite and EXT4 of Android I/O stack yields excessive random writes. In this work, we developed multi-version B-tree with lazy split (LS-MVBT) to effectively address Journaling of Journal anomaly in Android I/O. LS-MVBT is carefully crafted to minimize write traffic caused by fsync() of SQLite. The contribution of LS-MVBT consists of two key elements: (i) Multi-version B-tree effectively reduces the number of fsync() calls via weaving crash recovery information within database itself instead of maintaining a separate file, and (ii) it significantly reduces the number of dirty pages to be synchronized in a single fsync() call via optimizing multi-version B-tree for Android I/O. The optimization of multi-version B-tree consists of three elements: lazy split, metadata embedding, and disabling sibling redistribution. We implemented LS-MVBT in Samsung Galaxy S4 with Android 4.3 Jelly Bean. The results are impressive. For SQLite, LS-MVBT exhibits 70% (704 insertions/sec vs. 416 insertions/sec), and 1,220% performance improvement against WAL mode and TRUNCATE mode (704 insertions/sec vs. 55 insertions/sec), respectively.