"Big Data" is one of the most prominent buzzwords of our age, and for good reason. From genetics to supercomputers to Facebook, big data is everywhere, and managing this data is going to be essential in the years to come.

One of the most basic interactions between a user and a storage system is the ability to retrieve data quickly and reliably. My thesis centers around the use of statistical properties of I/O traces to identify sets of data that are accessed together in order to store big data reliably and efficiently. We begin by showing that data can be assigned to predictive groups scalably with minimal domain knowledge and system impact. We then show how these groupings spur a variety of substantial improvements in areas including power management, performance, reliability, and resource allocation.

The areal density growth of hard disk drives is hindered by the limits imposed by the laws of physics and any further significant growth to the density demands some major changes to the currently employed recording techniques. Shingled Magnetic Recording (SMR) is leading next generation disk technology. SMR disks employ a shingled write process that overlaps the data tracks on the disk surface like the shingles on a roof, thereby increasing disk areal density with minimal manufacturing changes. While these disks have the same read behavior as current disks, random writes and in-place data updates are no longer possible, since a write to a track must overwrite and destroy data on all tracks that it overlaps.

Given this change in write behavior, we argue that the best way to utilize these disks is not by masquerading them as traditional disks, but by using approaches that leverage their proclivity for sequential writes. We hypothesize that using a smarter interface and an efficiently designed SMR-aware data management solution that over- comes the unique data management challenges faced by these disks, they could fit into more traditional roles. This thesis proposes a key-value object interface for SMR disks, and presents SMRDB, a Log-Structured Merge (LSM) tree based key-value data store for SMR disks, demonstrating that SMR disks can be effectively used to replace conventional disks for many applications. We evaluate SMRDB against a state-of-the-art LSM-tree based key-value database engine, LevelDB, on conventional disks. Our Yahoo! Cloud Serving Benchmark (YCSB) results show that, despite being restricted to sequential writes, SMRDB outperforms LevelDB by 8.8–123.6%.

A workload generator that generates loads with realistic temporal characteristics is required to measure the realistic impact compaction has on incoming requests and to measure the effectiveness of compaction overhead mitigation techniques. Though YCSB has emerged as the standard benchmark for evaluating key-value systems, and provides a variety of options to generate realistic workloads, like most benchmarks it has ignored the temporal characteristics of generated workloads. YCSB’s constant-rate request arrival process is unrealistic and fails to capture the real world arrival patterns. Existing workload studies on disk, filesystem, key-value system, network, and web traffic all show that they all exhibit some common temporal properties such as burstiness, self similarity, long range dependence, and diurnal activity. In the second part of this thesis, we show that the commonly observed traffic patterns can be modeled using the three categories of arrival processes: a)Poisson, b)Self similar, and c)Envelope-guided processes, and have incorporated all three models into YCSB.

Finally, we hypothesize that the negative impact that compaction would have on performance can be mitigated in a hybrid drive configuration, by write-offloading to the NVRAM component of the hybrid drive when compaction is in progress. In the final part of this thesis, we have created a version of SMRDB with design improvements made possible by write-offloading, and a compaction overhead more representative of other proposed SMR data management schemes, to evaluate the effectiveness of write- offloading. We show that write-offloading not only hides the compaction overhead and improves write performance, but also makes room for more compaction-induced data rearrangements.

In distributed high-performance computing storage systems, contention is a problem that usually occurs when the volume of client I/O requests exceeds the capability of storage servers; it degrades the whole system’s performance. The Storage Traffic Control System (STCS) is a critical component of a large system, which reduces the contention between clients, alleviates congestions in the system, and improves network and storage system efficiency. In a rule-based STCS, the building process for an optimal Storage Traffic Control Rule Set (STCRS) usually requires repetitious and lengthy benchmarking and tweaking cycles. Furthermore, most STCRSs are workload-specific and the established rule sets only matches to a limited subset of the actual workloads a storage system needs to handle. To add adaptiveness to the rule-based STCS, we present a performance prediction approach to help choosing existing STCRS for new workloads. This approach simplifies the traffic management for large-scale systems: instead of redesigning traffic control rules for each new workload the system receives, the proposed method extracts and measures the features of new workload and uses a regression tree pipeline to predict the performance improvement each control rule set bring to the new workload. The rule set that can best improve the performance of a workload will be chosen and applied to the new workload. Evaluation results show that most of the regression models we build have a high correlation coefficient (0.87) and low mean absolute error (3.8%). Using these performance prediction models, the suggested approach added adaptability to a rule based STCS by greatly increasing the amount of workloads that STCRSs can deal with.

Non-volatile memory (NVRAM) storage devices are increasingly used in both consumer and enterprise systems, providing high performance and low energy consumption compared to hard drives. Unfortunately, an inflexible block interface and multiple I/O subsystems designed for slow hard drives make it difficult to utilize NVRAMs in a portable and efficient manner. For example, in the OS storage stack, I/O workloads are reshaped and throttled to generate a small number of concurrent I/O requests, though NVRAMs can handle much higher workloads, and unnecessary address mapping is performed in a file system. Using NVRAM as memory can be difficult with a block interface because of small reads and writes that are common in mem- ory workloads. At a device level, NVRAM devices need to perform a number of heuristics to attempt to recover filesystem-level semantics lost during the transmission through a block interface. As a result of these legacy interfaces, the current architecture is limited in achieving portability, efficiency, and extensibility, leaving behind more complicated problems, such as supporting heterogeneous NVRAM devices and utilizing device features.

This thesis proposes the use of the object-based storage model as a way of addressing the shortfalls of the current NVRAM architecture. More specifically, we show that the on- device NVRAM management layer can be as efficient as that of a native file system designed for a specific type of NVRAM while providing tightly coupled hardware optimizations and drop-in replacement for new types of NVRAMs. To explore the design flexibility given by this model, we investigate several data placement policies for flash memory exploiting the rich metadata coming from an object-interface. We also design an object-based byte-addressable NVRAM device to demonstrate that the object model allows more reliable, efficient NVRAM management by integrating its core data structures and a wear-leveling policy together. Our wear-leveling policy enables a low overhead, multi-granularity wear-level tracking for byte- addressable memories by exploiting the uniformity of a random function. We also investigate its extensibility and efficiency by designing Muninn, a object-based versioning key-value store for flash memory.

Realizing the object storage model requires changes in several subsystems of oper- ating systems and hardware components, but no further system changes will be required to support new types of NVRAM. Even with the current storage stack, we hypothesize that some of the features of this model can be adopted to better utilize device hardware and improve over- all efficiency of the storage system. To demonstrate these capabilities, we introduce Smart SSD, which pairs in-device processing with a powerful host system capable of handling data-oriented tasks without modifying operating system code. Our system is built on a real SATA-based SSD and extends the Hadoop MapReduce framework to support in-storage processing. Our experi- ments show that total energy consumption is reduced by 50% due to the low-power processing inside a Smart SSD. Moreover, a system with a Smart SSD can outperform host-side processing by a factor of two or three by efficiently utilizing internal parallelism when applications have light traffic to the device DRAM under the current architecture.

In archival systems, storage media are often replaced much earlier than their expected service life in exchange for other benefits of new media, such as higher capacity, bandwidth, and I/O operations per second, or lower costs. In an era of decreasing media density growth rates, retiring media early by considering only short-term benefits while discarding potential long-term cost benefits could have a negative long-term impact on an archival system's economics. To extend an archival system's life, at low cost, while limiting performance degradation, we suggest extending media lifetime past manufacturer recommendations as well as increasing the horizon for planning and provisioning future media purchases.

We present a cost-benefit analysis of the impact of prolonged media usage and long-term planning. Through Monte Carlo simulation, we simulate the behavior of an archival system using tapes, hard disk drives (HDDs), solid state devices (SSDs), and Blu-ray discs. We show that leaving older media in the archival system makes economic sense for SSDs without significantly affecting reliability; we show cost improvements of approximately 10% for SSDs for a low annual media density growth rate, such as 5%, which would have been a loss of 35%, for a high annual media density rate, such as 20%. We show that, for SSDs and hard disks, the optimal planning time of an archival system is at least as long as the media service life. Combining prolonged media usage with an extended planning horizon reduced costs by 15% for a system using SSDs.

The importance of archival storage has increased with the growing demand for cost-effective long term data storage. Existing storage technologies like tape, hard disk drives, and solid state disks can meet today's demand for archival capacity and performance, but recently their pace of development has decelerated below their historical norms. In order to meet the ever-growing demand for archival storage, novel storage technologies are in development that will contend for their own place in archival storage systems.

The long-term viability of existing and novel storage technologies depends on how well suited they are for the demands of archival systems in the long term. We have created a simulation model to examine the relationships between different candidate storage technologies for archival systems and to define each technology's role within the competitive archival storage market over the long term. We enumerate the economic advantages of each storage technology relative to capacity, reliability, and workload for archival storage systems, and we describe how each technology can preserve its advantages and defend is position relative to other candidate archival storage technologies. We argue that novel storage technologies like synthetic DNA and glass will deliver decisive advantages in terms of cost, reliability, and scalability. Novel technologies will therefore dominate existing and traditional storage technologies for archival storage systems. Nevertheless, existing storage technologies will each retain a niche role for archival storage systems that suits their design.

The emerging use of the Internet for remote storage and backup has led to the problem of verifying that storage sites in a distributed system indeed store the data; this must often be done in the absence of knowledge of what the data should be. We use m/n erasure-correcting coding to safeguard the stored data and use algebraic signatures—hash functions with algebraic properties—for verification. Our scheme primarily utilizes one such algebraic property: taking a signature of parity gives the same result as taking the parity of the signatures. To make our scheme collusion-resistant, we blind data and parity by XORing them with a pseudo-random stream. Our scheme has three advantages over existing techniques. First, it uses only small messages for verification, an attractive property in a P2P setting where the storing peers often only have a small upstream pipe. Second, it allows verification of challenges across random data without the need for the challenger to compare against the original data. Third, it is highly resistant to coordinated attempts to undetectably modify data. These signature techniques are very fast, running at tens to hundreds of megabytes per second. Because of these properties, the use of algebraic signatures will permit the construction of large-scale distributed storage systems in which large amounts of storage can be verified with minimal network bandwidth.

Operating systems are built and designed around two driving forces: the capabilities of hardware, and the demands of software. Yet traditional (read: old) operating systems and programming models have inertia, resulting in interfaces for new hardware following the designs of existing interfaces. As a result, programmers are limited in their ability to express the important parts of their programs due to the layers of compatibility and overhead thrust upon them, despite their persistent demands for higher throughput and lower latency. Operating system abstractions must evolve into the modern day. Merely relying on decades old abstractions and incremental change will relegate novel hardware of the last decade to a fate of access via interfaces designed for tape and spinning rust.

We stand before an opportunity to study how a confluence of trends may shift programming models away from a traditional, process-centric view point towards a data-centric one, in which data is the primary citizen of the system. This opportunity arises from trends in hardware that directly impact how we view the data access path and the responsibilities ofthe operating system and the kernel. The increasing speed of interconnect technologies draws computing nodes closer together in latency space, increasing the efficiency and useability of shared memory. Persistence, traditionally trapped low in the memory hierarchy, is leaking upward, as access speeds for persistent devices increase (sidenote: this includes new technologies like byte-addressible non-volatile memory DIMMs, but also improvements in SSD performance and interfaces). As a result, the overhead of the traditional kernel-driven data access path begins to dominate the cost of accessing persistent data. Finally, the increasing heterogeneity and disaggregation of compute and memory devices demands increased data and compute mobility, as software demands continued scalability, distribution, and raw speed.

This dissertation presents a new, data-centric operating system and programming model designed around the trends above. The data-centric approach reframes the goals of the operating system and enables us to re-imagine classic systems programming techniques into a model that facilitates data sharing instead of hindering it. For example, classical systems programming models and techniques tend to involve significant complexity and overhead in dealing with data persistence and sharing, such as expensive coarse-grained persistence operations, rigid RPC data models, and serialization. In contrast, our data-centric approach gets the kernel out of the way of the data access path, makes data mobile through invariant references whose meaning does not change depending on address space or machine (in contrast to virtual memory, whose references only have meaning inside a single address space), and thus removes the need for serialization.

We will cover the motivation and hardware trends that lead to our design, define a design space based on those trends, and finally discuss Twizzler, a point in that design space that exemplifies the ideals we will discuss. We will evaluate Twizzler with case-studies that demonstrate system behavior, and efficacy and useability of our programming models, by building several new pieces of software for Twizzler. These, along with ported larger applications, will be used to demonstrate the performanceof Twizzler and its programming model, often showing performance increase just due to simplification of software layers.