Garbage Collection for Multiversion Index in Flash-Based Embedded Databases

• Published in: ACM transactions on design automation of electronic systems 2014-06, Vol.19 (3), p.1-27
• Main Authors: Huang, Po-Chun, Chang, Yuan-Hao, Lam, Kam-Yiu, Wang, Jian-Tao, Huang, Chien-Chin
• Format: Article
• Language: English
• ISSN: 1084-4309; 1557-7309
• DOI: 10.1145/2611757

Recently, flash-based embedded databases have gained their momentum in various control and monitoring systems, such as cyber-physical systems (CPSes). To support the functionality to access the historical data, a multiversion index is adopted to simultaneously maintain multiple versions of data items, as well as their index information. However, maintaining a multiversion index on flash memory incurs considerable performance overheads on garbage collection, which is to reclaim the spaces occupied by the outdated/invalid data items and their index information on flash memory. In this work, we propose an efficient garbage collection strategy to solve the garbage collection issues of flash-based multiversion databases. In particular, a version-tracking method is proposed to accelerate the performance on the process on identifying/reclaiming the space of invalid data and their indexes, and a pre-summary method is also designed to solve the cascading update problem that is caused by the write-once nature of flash memory and is worsened when more versions refer to the same data item. The capability of the proposed strategy is then verified by analytical and experimental studies.