NAND flash memory (hereafter, flash memory) has been intensively employed in a wide spectrum of computing systems from mobile devices like smartphones to personal computers to enterprise servers due to its high performance, low power consumption, and shock resistance. However, the further deployment of flash memory is impeded because it also possesses several inherent disadvantages such as limited programming/erase cycles and asymmetrical I/O performance. Besides, the existing frameworks for storage systems are originally designed for block devices (e.g., hard disk drives), which have totally different characteristics from flash memory. In order to utilize flash memory in current storage systems, an extra software layer between a traditional storage system interface and flash memory is needed to mimic the behavior of a block device. Unfortunately, using a flash-based storage system as a traditional HDD noticeably neutralizes the benefits of flash memory.In this dissertation, we holistically examine current flash-based storage systems in different computing platforms ranging from embedded systems to enterprise servers. Firstly, we empirically characterize a representative collection of flash memory devices and then model their raw I/O performance and reliability. Our results demonstrate that flash memory performance and reliability are correlated to programmed data patterns. Further, we propose multiple approaches to improving the performance and reliability of flash-based storage systems at device level. Secondly, we study flash translation layer (FTL) in flash-based solid-state drives (SSDs) for desktops. A plane-centric FTL and a workload-aware MLC/SLC (multi-level cell/single-level cell) partitioning scheme are implemented to boost the performance of a single SSD. Thirdly, the employment of SSD arrays in enterprise servers is investigated. We propose a load-balancing scheme at disk array level to prolong the lifetime of SSD arrays for server applications like OLTP (online transaction processing). Finally, an MTD (memory technology device) array based storage framework will be developed to meet the performance and reliability requirements demanded by emerging and future data-intensive and mission-critical mobile applications.

NAND flash memory is playing a key role in the revolution of storage systems due to its desirable features such as fast random read and high energy-efficiency. It has been extensively applied in mobile devices like smart phones and PDAs. With increasing capacity, throughput and durability, NAND flash memory based solid state disk (hereafter, flash SSD) has started replacing hard disk drive (HDD) in laptops and desktop systems. Employing high-end flash SSDs in server applications, however, is promising yet challenging. One of the challenges is that currently flash SSD cannot fully meet heavy random write requirements demanded by data-intensive enterprise applications like online transaction processing (OLTP) because of flash memory's inherent update/erasure mechanisms. In this thesis, to boost flash SSD random write performance, we develop a new cache management scheme called element-level parallel optimization (EPO), which buffers and reorders write requests so that element-level parallelism within the architecture of a flash SSD can be mostly utilized. Further, we evaluate the performance of the EPO scheme using a validated disk simulator with both synthetic benchmarks and real-world server-class traces. Experimental results demonstrate that EPO noticeably outperforms traditional least recently used (LRU) and a state-of-the-art flash write buffer management scheme block padding least recently used (BPLRU).

In the third part of this dissertation, we explore the approaches to collapsing logs. While there are several popular ways that utilize the nature of flash memory translation layer to eliminate multiple layers of logs in the entire system, we focus on the benefit we can obtain from a log-less object-based flash aware system. We show from simulation experiments that advanced features could be embedded to improve overall performance for object-based flash system with low overhead through a rich interface.

"Modern computing has matured into a data-intensive, service-oriented activity, leading to increasing storage and I/O demands. However, current storage systems are built on slow, failure-prone, mechanical disks. These systems already face limitations of deployment scale, power consumption and performance. In order to meet current and future storage needs, systems need to incorporate new storage media. NAND Flash is steadily maturing as a mass storage device, and Flash-based storage systems are a promising solution for the new demands of data-driven computing. Flash-based storage promises better performance than mechanical disks. However, existing system software is ill-suited to properly manage the performance characteristics of Flash-based storage. The combination of inappropriate system support and Flash characteristics can lead to the breakdown of service guarantees like fairness and performance isolation. On the other hand, in developing appropriate system support for Flash-based storage, the opportunity to develop mechanisms for additional, stronger service guarantees arises. This dissertation approaches system support for Flash-based storage from two perspectives. First, understanding and managing Flash performance is necessary in order to provide reliable service to applications. In particular, an I/O scheduler based on Flash-oriented principles can provide better fairness and efficiency than traditional I/O schedulers. Second, Flash-based storage provides unique characteristics and high performance that can enable more powerful I/O capabilities that a properly designed system can provide to users. Flash-based storage can efficiently support a new I/O primitive, failure-atomic msync(), that allows application programmers to failure-atomically evolve durable application state in a straightforward manner"--Page v-vi.

This dissertation proposes mathematical algorithms for improving Flash-based storage system's four key performance metrics: lifetime, reliability, latency and throughput. The first part of the dissertation presents the novel concept of dynamically voltage allocation (DVA) for Flash memory. Flash memory suffers reduced reliability as the number of program/erase (P/E) cycles increases, thus has a limited lifetime. DVA scales the write threshold voltages of Flash memory adaptively, using lower voltages at the beginning of the lifetime, and gradually increases the scaling to combat the effect of accumulated wear-out from P/E cycling. The proposed algorithm significantly increases the lifetime of the device. The second part of the dissertation introduces the novel design of error correction using incremental redundancy without feedback. Modern storage systems often require high throughput, high reliability and low latency. Traditional variable-length (VL) codes with feedback have demonstrated to provide high throughput and reliability. The new design reinterprets the results for VL codes with feedback using ergodicity, by encoding the incremental redundancy of multiple VL codewords to a common pool of redundancy. The removal of feedback allows storage systems to benefit from the performance of a feedback scheme with a feedforward design. The decoder of the new design exploits the low complexity of short-blocklength decoders and the parallelization structure to reduce latency. The proposed error correction scheme approaches the throughput of corresponding VL codes with feedback. Relying on information theory and coding theory, the proposed algorithms provide new approaches to optimize the Flash-based storage systems.