Yiying Zhang

“All problems in computer science can be solved by another level of indirection” – often attributed to Butler Lampson, who gives credit to David Wheeler

“... but that usually will create another problem” – David Wheeler

De-Indirection in Storage Systems

Indirection is a fundamental technique in computer systems. New generations of storage devices often use an indirection layer to provide the conventional block I/O interfaces or to hide their internal operations.

However, multiple layers of indirection can result in excess indirection, causing performance overhead and memory consumption. For example, running a file system on top of a virtualized device creates two levels of (excess) virtualization; a block is first mapped from a file offset to its logical address and then from the logical address to its physical address in the device.

De-indirection is a method to remove excess level of indirection. We propose several techniques to perform de-indirection in flash-based SSDs.

Nameless Writes

Nameless Writes are a new device interface that removes the need for indirection in modern solid-state storage devices (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. Doing so allows the device to control block-allocation decisions, thus enabling it to execute critical tasks such as garbage collection and wear leveling, while removing the need for large and costly indirection tables. The resulting system significantly reduces space and time overheads and improves SSD performance over current solutions, thus making for simpler, less costly, and higher-performance SSD-based storage.

SSD Emulator

A large body of research work on flash-based SSDs has been conducted in the recent years. Most work uses simulation as an evaluation method. Simulation is easy to use but lacks real system interaction and cannot be used to run real workloads or applications directly.

FlashEm is a real-time flash-based SSD emulator. We expose the emulated device to the system as a block device, so it can run real workloads and applications. We used several techniques to reduce the computational overhead of FlashEm. Our evaluation results show that it is accurate to use FlashEm to evaluate important metrics with common types of flash-based SSDs.

Hardware Prototype of Nameless Writes

Due to the closed nature of commercial devices, most research on SSDs is performed using simulation or emulation. Without implementation in real devices, it can be difficult to judge the true benefit of the proposed designs. With hardware prototyping, we can evaluate both the difficulty in implementing new designs and the performance of such designs. We built a hardware prototype of the Nameless Write SSD using the OpenSSD Jasmine board. While the flash-translation layer changes were straightforward, we discovered unexpected complexities in implementing extensions to the storage interface.

File System De-Virtualizer

The File System De-Virtualizer (FSDV) is a system to dynamically remove a layer of indirection common in modern storage stacks, thus decreasing the indirection space and performance costs. FSDV is a light-weight and flexible tool that de-virtualizes data by changing file system pointers to use device physical addresses. When FSDV is not running, the file system and the device both maintain their virtualization layers and perform normal I/O operations. We implemented FSDV with the ext3 file system and an emulated flash-based SSDs.

Our evaluation results show that FSDV can dynamically reduce indirection mapping table space while preserving the foreground I/O performance. We also demonstrate that with our design of FSDV, the changes needed in file system, flash devices, and device interface are small.

Related Publications

Removing the Costs and Retaining the Benefits of Flash-Based SSD Virtualization with FSDV
Yiying Zhang, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau
Proceedings of the 31st IEEE Conference on Massive Data Storage (MSST '15)

De-indirection for Flash-based Solid State Drives
Yiying Zhang
Ph.D. Thesis, University of Wisconsin-Madison

De-indirection for Flash-based SSDs with Nameless Writes
Yiying Zhang, Leo Prasath Arulraj, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau
Proceedings of the 10th Conference on File and Storage Technologies (FAST'12)

Getting Real: Lessons in Transitioning Research Simulations into Hardware Systems
Mohit Saxena, Yiying Zhang, Michael M. Swift, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau
Proceedings of the 11th Conference on File and Storage Technologies (FAST '13)