F two F S: A New File System for Flash Storage

F two F S: A New File System for Flash Storage F two F S: A New File System for Flash Storage

Abstract

F two F S is a Linux file system designed to perform well on modern flash storage devices. The file system builds on append-only logging and its key design decisions were made with the characteristics of flash storage in mind. This paper describes the main design ideas, data structures, algorithms and the resulting performance of F two F S.

Experimental results highlight the desirable performance of F two F S; on a state-of-the-art mobile system, it outperforms E X T four under synthetic workloads by up to three point one times iozone and two times SQLite. It reduces elapsed time of several realistic workloads by up to forty percent. On a server system, F two F S is shown to perform better than E X T four by up to two point five times SATA S S D and one point eight times PCIe S S D.

One Introduction

NAND flash memory has been used widely in various mobile devices like smartphones, tablets and M P three players. Furthermore, server systems started utilizing flash devices as their primary storage. Despite its broad use, flash memory has several limitations, like erase-before-write requirement, the need to write on erased blocks sequentially and limited write cycles per erase block.

In early days, many consumer electronic devices directly utilized "bare" NAND flash memory put on a platform. With the growth of storage needs, however, it is increasingly common to use a "solution" that has multiple flash chips connected through a dedicated controller. The firmware running on the controller, commonly called F T L flash translation layer, addresses the NAND flash memory's limitations and provides a generic block device abstraction. Examples of such a flash storage solution include e M C C embedded multimedia card, U F S universal flash storage and S S D solid-state drive. Typically, these modern flash storage devices show much lower access latency than a hard disk drive, their mechanical counterpart. When it comes to random I O, S S Ds perform orders of magnitude better than hard drives.

However, under certain usage conditions of flash storage devices, the idiosyncrasy of the NAND flash media manifests. For example, Min et al. observe that frequent random writes to an S S D would incur internal fragmentation of the underlying media and degrade the sustained S S D performance. Studies indicate that random write patterns are quite common and even more taxing to resource-constrained flash solutions on mobile devices. Kim et al. quantified that the Facebook mobile application issues one hundred fifty percent and WebBench register seventy percent more random writes than sequential writes. Furthermore, over eighty percent of total I O s are random and more than seventy percent of the random writes are triggered with f sync by applications such as Facebook and Twitter. This specific I O pattern comes from the dominant use of SQLite in those applications. Unless handled carefully, frequent random writes and flush operations in modern workloads can seriously increase a flash device's I O latency and reduce the device lifetime.

The detrimental effects of random writes could be reduced by the log-structured file system approach and/or the copy-on-write strategy. For example, one might anticipate file systems like B T R F S and N I L F S two would perform well on NAND flash S S Ds; unfortunately, they do not consider the characteristics of flash storage devices and are inevitably sub-optimal in terms of performance and device lifetime. We argue that traditional file system design strategies for hard drives-albeit beneficial-fall short of fully leveraging and optimizing the usage of the NAND flash media.

In this paper, we present the design and implementation of F two F S, a new file system optimized for modern flash storage devices. As far as we know, F two F S is the first publicly and widely available file system that is designed from scratch to optimize performance and lifetime of flash devices with a generic block interface. This paper describes its design and implementation.

Listed in the following are the main considerations for the design of F two F S:

· Flash-friendly on-disk layout. F two F S employs three configurable units: segment, section and zone. It allocates storage blocks in the unit of segments from a number of individual zones. It performs "cleaning" in the unit of section. These units are introduced to align with the underlying F T L's operational units to avoid unnecessary (yet costly) data copying.

· Cost-effective index structure. L F S writes data and index blocks to newly allocated free space. If a leaf data block is updated (and written to somewhere), its direct index block should be updated, too. Once the direct index block is written, again its indirect index block should be updated. Such recursive updates result in a chain of writes, creating the "wandering tree" problem. In order to attack this problem, we propose a novel index table called node address table.

· Multi-head logging. We devise an effective hot/cold data separation scheme applied during logging time (i.e., block allocation time). It runs multiple active log segments concurrently and appends data and metadata to separate log segments based on their anticipated update frequency. Since the flash storage devices exploit media parallelism, multiple active segments can run simultaneously without frequent management operations, making performance degradation due to multiple logging (vs. single-segment logging) insignificant.

· Adaptive logging. F two F S builds basically on append-only logging to turn random writes into sequential ones. At high storage utilization, however, it changes the logging strategy to threaded logging to avoid long write latency. In essence, threaded logging writes new data to free space in a dirty segment without cleaning it in the foreground. This strategy works well on modern flash devices but may not do so on hard drives.

· fsync acceleration with roll-forward recovery. F two F S optimizes small synchronous writes to reduce the latency of f sync requests, by minimizing required metadata writes and recovering synchronized data with an efficient roll-forward mechanism.

In a nutshell, F two F S builds on the concept of L F S but deviates significantly from the original L F S proposal with new design considerations. We have implemented F two F S as a Linux file system and compare it with two state-of-the-art Linux file systems-EXT four and B T R F S. We also evaluate N I L F S two, an alternative implementation of L F S in Linux. Our evaluation considers two generally categorized target systems: mobile system and server system. In the case of the server system, we study the file systems on a SATA S S D and a PCIe S S D. The results we obtain and present in this work highlight the overall desirable performance characteristics of F two F S.

In the remainder of this paper, Section two first describes the design and implementation of F two F S. Section three provides performance results and discussions. We describe related work in Section four and conclude in Section five.