CSR: Small: Efficient Techniques for Modular Past State Systems

Brandeis University, Waltham MA

Investigators

Abstract

Retrospection is the ability of a data store to run ad-hoc programs over consistent past states of a data store as if they were the current state. Retrospection makes it easier to analyze past states providing a valuable tool for auditors, historians, economists, social scientists and others with a need to investigate historical data. Retrospection is also valuable to those who want to analyze past states to predict the future, an increasingly in-demand feature in modern data management applications. Most light-weight data stores today do not support retrospection. The key reason is that existing retrospection techniques, for performance, require invasive hard-to-adopt modifications to data store internals. Without support for retrospection, it may be hard for application developers to reconstruct the consistent states corresponding to past events of interest. This project will develop an easy-to-adopt modular method and a set of associated techniques for supporting retrospection in light-weight transactional data stores using an embedded persistent consistent past-state system. The technical challenges are: 1) How to provide consistent past states without harming data store performance? The past state system needs to be tightly integrated for efficiency but extensive modifications to the internal data store components are infeasible, requiring new modular techniques that operate at a low-level in the data store software stack. 2) How to run programs efficiently over past state that spans large time intervals? past state needs to be created incrementally to avoid disrupting the data store but running a program over incremental state can be slow, requiring new clustering and caching techniques optimized for incremental data. 3) Can one avoid slowing down programs that do not use retrospection? To evaluate any additional overhead, the project will develop an experimental prototype in an industrial strength data store, and conduct studies to answer this question experimentally and analytically.