The Buddy Allocator: Exploring the Relationship Between Fragmentation and Filesystem Performance on Fxfs

Abstract

In this paper, we provide an overview of the key concepts and data structures that underly Fxfs, one of Google’s newest open-source filesystems. Compared to traditional filesystems such as ext4, Fxfs has an unconventional design as it relies heavily on log-structured merge (LSM) trees to store its metadata. Every filesystem needs an allocator to determine where and how to store files on a device. The existing Fxfs allocator takes a partial fit approach and returns the first free gap that it finds on the device. There is a potential opportunity to improve the performance of the filesystem by designing an allocator that reduces fragmentation. The hypothesis is that with less fragmentation, an allocator will issue fewer disk IOs, which could lead to performance benefits. To test this hypothesis, we implement four new allocators and run them all on a sqlite benchmark. The results suggest that the time spent allocating is a significant driver of performance and should be considered as one of the key factors while designing a strong allocator.