Efficient Data Management with Flexible File Address Space

Data management applications store their data using structured files in which data are usually sorted to serve indexing and queries. In order to insert or remove a record in a sorted file, the positions of existing data need to be shifted. To this end, the existing data after the insertion or removal point must be rewritten to admit the change in place, which can be unaffordable for applications that make frequent updates. As a result, applications often employ extra layers of indirections to admit changes out-of-place. However, it causes increased access costs and excessive complexity. This paper presents a novel file abstraction, FlexFile, that provides a flexible file address space where in-place updates of arbitrary-sized data, such as insertions and removals, can be performed efficiently. With FlexFile, applications can manage their data in a linear file address space with minimal complexity. Extensive evaluation results show that a simple key-value store built on top of this abstraction can achieve high performance for both reads and writes.