Garbage Collection for Multiversion Index in Flash-Based Embedded Databases

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

  • PO-CHUN HUANG
  • YUAN-HAO CHANG
  • KAM-YIU LAM
  • JIAN-TAO WANG
  • CHIEN-CHIN HUANG

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number25
Journal / PublicationACM Transactions on Design Automation of Electronic Systems
Volume19
Issue number3
Publication statusPublished - Jun 2014

Abstract

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.

Research Area(s)

  • Cyber-physical systems (CPSes), Database systems, Flash memory, Garbage collection

Citation Format(s)

Garbage Collection for Multiversion Index in Flash-Based Embedded Databases. / HUANG, PO-CHUN; CHANG, YUAN-HAO; LAM, KAM-YIU; WANG, JIAN-TAO; HUANG, CHIEN-CHIN.

In: ACM Transactions on Design Automation of Electronic Systems, Vol. 19, No. 3, 25, 06.2014.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review