Space-efficient multiversion index scheme for PCM-based embedded database systems

Embedded database systems are widely adopted in various control and motoring systems, e.g., cyber-physical systems (CPSes). To support the functionality to access the historical data, a multiversion index is adopted to maintain multiple versions of data items and their index information. However, CPSes are usually battery-powered embedded systems that have limited energy, computing power, and storage space. In this work, we consider the systems with phase-change memory (PCM) as their storage due to its non-volatility and low energy consumption. In order to resolve the problem of the limited storage space and the fact that existing multiversion index designs are lack of space efficiency, we propose a space-efficient multiversion index scheme to enhance the space utilization and access performance of embedded multiversion database systems on PCM by utilizing the byte-addressability and write asymmetry of PCM. A series of experiments was conducted to evaluate the efficacy of the proposed scheme. The results show that the proposed scheme achieves very high space utilization and has good performance on serving update transactions and range queries.

1. Introduction

Embedded database systems are widely adopted in cyber-physical systems (CPSes) to monitor the update status of various entities in their deployed environments. In CPSes, the number of various entities of an operation environment is usually limited, but there might be an increasingly large number of update versions generated for each entity. To facilitate accesses to the current and the previous versions of data items, B+ -tree-like multiversion index designs based on block-oriented storages, e.g., hard disk or flash memory, were proposed to efficiently manage data versions, each of which is a non-overlapping version range to indicate its validity according to the update transactions that create or update the data version. Such multiversion index designs often create new tree roots as snapshots by duplicating valid index information when the number of versions increases, so as to accelerate the performance on querying old versions of data items. However, such a strategy is lack of space efficiency and has poor performance on querying a range of versions for the same data item, but embedded computing systems in CPSes usually have limited storage space, computing power, and battery energy. Due to its byte-addressability and low energy consumption of PCM, PCM became a popular candidate as a storage device in embedded systems [2], [4]. Such observations motivate this work on proposing a new multiversion index design for PCM-based embedded databases to improve the space utilization of the embedded database, as well as the performance on reclaiming the space for old data versions and on serving the queries for version ranges of data items.