Resolving journaling of journal anomaly in android I/O: multi-version B-tree with lazy split
Wook-Hee Kim, Beomseok Nam, Dongil Park, Youjip Won · Scholarworks@UNIST (Ulsan National Institute of Science and Technology) · 2014
Misaligned interaction between SQLite and EXT4 of the 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 the Journaling of Journal anomaly in Android I/O. LS-MVBT is carefully crafted to minimize the write traffic caused by fsync() call 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 the crash recovery information within the 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 the 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, the 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.