Flexible File Address Space Management

Many applications store their data using structured files. In order to insert or remove a record in the middle of a structured file, the application needs to shift the positions of existing data. 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. Alternatively, the out-of-place update approach can admit changes with reduced rewrites. However, it leads to increased access costs and excessive complexity. This paper presents a novel mechanism for managing file address space, named FlexFile, that enables fast insertion and removal of arbitrary-sized data in a file. Based on FlexFile, applications can perform in-place updates to a file without rewriting existing data, and efficiently manage data on a linear file layout with minimal complexity. Evaluation results show that a simple key-value store built on top of FlexFile can achieve high performance for both reads and writes.