For years data access rate and capacity growth for storage devices were directly correlated as putting more number of bits in tracks would increase both. This correlation, however, was changed a few years ago with the introduction of write out-of-place technologies such as NAND flash and Shingled Magnetic Recording (SMR). NAND flash devices offer orders of magnitude faster data access by replacing the magnetic technology with CMOS. Shingled magnetic recording increases the capacity of conventional HDDs by partially overlapping adjacent tracks in them.
Despite the benefits that each of these technologies offers, they both suffer from the fact that data updates (writes) in these devices can not be done in-place. A data page in a flash-based storage device must be in a clean state before an update can be applied to it. On the other hand, random writes in an SMR drive corrupt the data on the next track(s) in shingling direction. Due to these limitations in writes, drives from both technologies need translation layers to move valid data around inside the drive in order to prevent such service interrupts or data corruptions.
In this thesis I study these two technologies from the translation layer perspective to 1) model their performance characteristics and 2) to provide better algorithms to improve their performance:
Modeling SMR drives is a challenge, requiring an array of approaches including both existing disk modeling techniques as well as new techniques for inferring internal translation layer algorithms. I present the first predictive simulation model of a generally-available drive-managed SMR disk which is derived from external measurements. The available model can predict mean latency within a few percent, and with an RMS cumulative latency error of 25% or less for most workloads tested. These variations, although not small, are in most cases less than three times the drive-to- drive variation seen among seemingly identical drives. I also propose a track-based static mapping translation layer for these drives, called Virtual Guard (Vguard). Vguard writes updates in-place by caching data from the next track in the shingling direction. This allows direct overwrite of sectors in the target track and enables Vguard to take advantage of track-level locality, nearly eliminating cleaning for many workloads. My evaluations show that Vguard reduces the 99.9% latency by 15X for real-world traces, and maximum latency by 32% for synthetic random write workloads compared to the available (and modeled) drive-managed SMR drive.
Translation layers are a better studied subject in flash-based SSD domain.
I present the first description of offline optimal solutions for flash translation layer and log-structure file system cleaning, focusing on the single-write- frontier demand-clean case. I describe an approximate solution to this problem, based on tree pruning and Monte Carlo Tree Search. My evaluation results show that efficient cleaning for real workloads is not a matter of deciding which blocks to select for cleaning, but rather of deciding where to place incoming data, and then collecting the free space generated by these decisions. As a matter of fact, an online two write frontier translation layer with hot/cold data segregation outperforms optimal offline cleaning in a single write-frontier device. I finally propose an extent-based clustering technique to the problem of identifying hot or frequently-written data in an SSD, allowing such data to be segregated for improved cleaning performance. My evaluations show up to 20% less write amplifications over traditional hashing and bloom filter based schemes with only 10KB of memory needed from the DRAM inside the drive.
- Professor Peter Desnoyers (Advisor)
- Professor David Kaeli
- Professor Ningfang Mi
- Professor Devesh Tiwari