Given its pervasive use in smart mobile platforms, there is a compelling need to optimize the performance of sluggish SQLite databases. Popular mobile applications such as messenger, email and social network services rely on SQLite for their data management need. Those mobile applications tend to execute relatively short transactions in the autocommit mode for transactional consistency in databases.
SQLite-PPL Paper (219 downloads)
This often has adverse effect on the flash memory storage in mobile devices because the small random updates cause high write amplification and high write latency. In order to address this problem, we propose a new optimization strategy, called per-page logging (PPL), for mobile data management, and have implemented the key functions in SQLite/PPL. The hardware component of SQLite/PPL includes phase change memory (PCM) with a byte-addressable, persistent memory abstraction. By capturing an update in a physiological log record and adding it to the PCM log sector, SQLite/PPL can replace a multitude of successive page writes made to the same logical page with much smaller log writes done to PCM much more efficiently. We have observed that SQLite/PPL would potentially improve the performance of mobile applications by an order of magnitude while supporting transactional atomicity and durability.
Write Amplification in SQLite
Since many mobile applications utilize SQLite running in the autocommit mode, each record inserted into a table requires force-writing multiple pages including the one in the table and several pages in the secondary indexes. SQLite provides users with six different options for database journaling Among those, Delete and WAL journaling are most commonly used. If SQLite runs in the Delete (by default) or WAL journaling mode, each update incurs two physical page writes, one for database update and another for journaling. 1 That is, if a record is inserted into a table with k secondary indexes, a total of 2 × (k + 1) pages will be written physically to storage. The amount of write amplification caused by an individual insertion would be quite significant, particularly when the inserted record is very small. In our own traces, we have observed that a single message sent or received often incurs more than ten physical page writes. More importantly, the difference in content between two consecutive writes requested against the same logical page is very small, rarely more than 100 bytes. (See Figure 2 for the distribution of page differences of the traces from mobile applications.) The write amplification of the traces (measured by the amount of data written physically divided by the aggregate sum of messages in bytes) was more than 100. The negative impact will be aggravated as the page size increases in eMMC and SD cards commonly used for mobile devices. The same trend was also observed in the mobile benchmark.
PCM Unified with DRAM
Non-charge-based non-volatile memory technologies have been under active development and commercialization by leading industry manufacturers for quite some time. Among those memory technologies, phase-change memory (PCM) is considered one of the promising candidates for the next generation byte-addressable non-volatile memory. It is a few years ago when a major semiconductor manufacturer started volume production of PCM and offered it for mobile devices in 1Gb packages. Unlike DRAM and flash memory, PCM provides memory states without electric charges. PCM devices use phase change material for a cell to remember a bit. The phase change material can exist in two different states, amorphous and crystalline, which can be used to represent zero and one. Switching between the two states can be done by application of heat at different temperature ranges for different durations. PCM can be programmed in place without having to erase the previous state. Although PCM has a limited number of programming cycles due to repeated heat stress applied to the phase change material, it is considered to be more scalable and has greater write endurance than flash memory by a few orders of magnitude. Furthermore, in contrast to NAND type flash memory, PCM need not operate in 1455 page mode and allows random accesses to individual bytes like DRAM does. It is reported in the literature that the read and write latency of PCM are only an order of magnitude greater than those of DRAM. As is shown in Table 1, however, contemporary PCM products do not deliver the promised performance as yet particularly for write operations. While PCM takes only about 408ns to read 4 bytes, it takes as long as 7.5 us to write 4 bytes. A similar disparity in read and write speeds has been observed in other PCM products as well. A recent study confirms that some of the reported performance measurements are misleading especially for write latency. The study also reports that while PCM read latency is about 16 times shorter than that of flash memory, PCM write latency is actually 3.5 times longer than that of flash memory.
Design of SQLite/PPL
SQLite is a software library that implements a serverless, transactional SQL database engine . Mobile applications are linked to the SQLite library to utilize its database management functions. SQLite stores databases as separate files in flash memory. Concurrent transactions can access the same database but only one transaction can update the database at any moment in time, because the entire database file is locked by the writer transaction until it finishes. The pager module is in charge of managing the DRAM buffer pool and the B +-tree module processes select and update statements. These components of SQLite remain unchanged in the SQLite/PPL.
SQLite/PPL differs from the vanilla SQLite in the way transactional atomicity and durability are supported. SQLite relies on the costly journaling, usually in either Delete or WAL mode, to ensure that both the before and after images of an updated page are saved until the updating transaction commits or aborts. Journaling is also commonly used for a multi-page write, which is not guaranteed to be atomic on most storage media, disk or flash memory. This is the major cause of sluggish performance of SQLite, since every page update requires two physical page writes.
On the other hand, SQLite/PPL relies on per-page logging instead of journaling as well as the non-volatility of PCM for the transactional support. Instead of writing a page twice – in thedatabase and its journal – for each update, SQLite/-PPL captures the change in a physiological log record and adds it to the PCM sector of the page being updated. The page itself remains unchanged in the flash memory until its log records are merged to it later. Therefore, SQLite/PPL can replace a multitude of successive page writes against the same logical page by writing potentially much smaller log records into the PCM sector much more quickly. Furthermore, SQLite/PPL can avoid redundant page writes by turning off journaling without giving up the atomicity and durability of transactions.
However, leaving log records in the PCM sector of each page alone is not sufficient for transactional atomicity and durability. The log records in the PCM sector represent changes made by a transaction whose state changes over time from active to either committed or aborted. When a transaction commits, all of its log records become permanent and can be merged (or applied) to the data page in flash memory immediately or lazily. When a transaction aborts, all the log records become invalidated and can be discarded immediately or simply ignored. While a transaction is still active, all of its log records must be kept in the PCM sector at least until the transaction commits or aborts. That way it will be feasible to determine the visibility of the log records (or their changes) to other concurrent transactions depending on their end mark.
In order to keep track of transaction states, SQLite/PPL maintains a single transaction log, which is shared by all transactions accessing the same database. The transaction log stores only three types of records: transaction begin, commit, or abort. Since the transaction log stores no update log records, it is expected to be kept small and subject to very light I/O activities.
The key data structures we have added to SQLite/PPL, namely, per-page log and transaction log are stored in the PCM area of UMS, while data pages are stored in flash memory. Thus, data pages are accessed via the standard I/O stack, but the per-page log and transaction log are accessed by mmap system calls through the DIMM interface, hence avoiding the overhead of I/O stack.