Enabling Efficient Random Data Insertion/Deletion on Block-Based File Systems

Yi-Han Lien

doi:10.1109/TC.2021.3092178

Enabling Efficient Random Data Insertion/Deletion on Block-Based File Systems

2021-01-01

0

PRE

AI

DOI：10.1109/TC.2021.3092178

原文链接

原文求助

摘要

En 中文

The file model based on character streams is widely used by most file systems today. However, such a model is originally designed for the storage media that are friendly for sequential accesses, such as mechanical hard disk. Although data can be updated (/overwritten) in the midway of files or appended to the end of files, they cannot be efficiently inserted or deleted. In particular, the random insertion/deletion of data in the midway of a file in a block-based file system often results in the updating of all subsequent chunks of the file, which seriously amplifies the write traffic and degrades the performance of the file system. In some application scenarios such as virtualized computing platforms with potentially very large files, the performance overheads due to the write amplification of a random insert/delete request might be ridiculously high. The observation therefore motivates this work in proposing the data compaction strategies to manage the data and storage space of each file, so as to enhance the performance of random insert/delete requests and the space utilization of file systems. The proposed data compaction strategies effectively relax the limitation of the space utilization guarantees provided by existing data/space management schemes, such as the buddy memory allocator. Besides, we propose a chunk anonymization scheme which can be applied to existing search trees to efficiently manage the indexing information of the chunks of a file. When working on a self-balancing search tree such as red-black tree, the chunk anonymization scheme can efficiently locate the chunk that contains the data of a given logical offset within the file in logarithmic time with respect to the file size. Moreover, a search tree with the chunk anonymization scheme can be efficiently maintained in logarithmic time when serving a random insert or delete request. Evaluation results show that the proposed data compaction strategies and chunk anonymization scheme can balance space utilization guarantees and random insert/delete performance.

Keyword:

Compaction

Nonvolatile memory

Aerospace electronics

Media

Space debris

Real-time systems

Hard disks

Random insert

delete requests

block-based file system

space utilization guarantee

data compaction

chunk anonymization

Enabling Efficient Random Data Insertion/Deletion on Block-Based File Systems

摘要

期刊

机构

引用论文