UW-Madison Logo

The ADvanced Systems Laboratory (ADSL)
Publication abstract

De-indirection for Flash-based Solid State Drives

Yiying Zhang
Department of Computer Sciences ,
University of Wisconsin-Madison


Flash-based solid-state drives (SSDs) have revolutionized storage with their high performance. Modern flash-based SSDs virtualize their physical resources with {\em indirection} to provide the traditional block interface and hide their internal operations and structures. When using a file system on top of a flash-based SSD, the device indirection layer becomes redundant. Moreover, such indirection comes with a cost both in memory space and in performance. Given that flash-based devices are likely to continue to grow in their sizes and in their markets, we are faced with a terrific challenge: How can we remove the excess indirection and its cost in flash-based SSDs?

We propose the technique of de-indirection to remove the indirection in flash-based SSDs. With de-indirection, the need for device address mappings is removed and physical addresses are stored directly in file system metadata. By doing so the need for large and costly indirect tables is removed, while the device still has its freedom to control block-allocation decisions, enabling it to execute critical tasks such as garbage collection and wear leveling.

In this dissertation, we first discuss our efforts to build an accurate SSD emulator. The emulator works as a Linux pseudo block device and can be used to run real system workloads. The major challenge we found in building the SSD emulator is to accurately model SSDs with parallel planes. We leveraged several techniques to reduce the computational overhead of the emulator. Our evaluation results show that the emulator can accurately model important metrics for common types of SSDs, which is sufficient for the evaluation of various designs in this dissertation and in SSD-related research.

Next, we present Nameless Writes, a new device interface that removes the need for indirection in flash-based SSDs. Nameless writes allow the device to choose the location of a write; only then is the client informed of the name (i.e., address) where the block now resides. We demonstrate the effectiveness of nameless writes by porting the Linux ext3 file system to use an emulated nameless-writing device and show that doing so both reduces space and time overheads, thus making for simpler, less costly, and higher-performance SSD-based storage.

We then describe our efforts to implement nameless writes on real hardware. Most research on flash-based SSDs including our initial evaluation of nameless writes rely on simulation or emulation. However, nameless writes require fundamental changes in the internal workings of the device, its interface to the host operating system, and the host OS. Without implementation in real devices, it can be difficult to judge the true benefit of the nameless writes design. Using the OpenSSD Jasmine board, we develop a prototype of the Nameless Write SSD. While the flash-translation layer changes were straightforward, we discovered unexpected complexities in implementing extensions to the storage interface.

Finally, we discuss a new solution to perform de-indirection, the File System De-Virtualizer ( FSDV), which can dynamically remove the cost of indirection in flash-based SSDs. FSDV is a light-weight tool that de-virtualizes data by changing file system pointers to use device physical addresses. Our evaluation results show that FSDV can dynamically reduce indirection mapping table space with only small performance overhead. We also demonstrate that with our design of FSDV, the changes needed in file system, flash devices, and device interface are small.

Full Paper: PDF   BibTeX