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.
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.
R
Many
Data management
A
in which data are usually sorted to serve indexing and queries
R
the middle of a structured
a sorted
D
application needs to shift the
A
need to be shifted
R
Alternatively, the
As a result, applications often employ extra layers of indirections to admit changes
D
update approach can admit changes with reduced rewrites
R
leads to
causes
R
mechanism for managing file address space, named
file abstraction,
R
enables fast insertion and removal of arbitrary-sized data in a file. Based on FlexFile, applications can perform
provides a flexible file address space where
R
to a file without rewriting existing data, and efficiently manage data on
of arbitrary-sized data, such as insertions and removals, can be performed efficiently. With FlexFile, applications can manage their data in
R
layout
address space
R
Evaluation
Extensive evaluation
R
FlexFile
this abstraction