Heterogeneity in cloud environments is a fact of life—from workload skews and network path changes, to the diversity of server hardware components, these are all factors that impact the performance of distributed storage. In this dissertation, we identify that heterogeneity can in fact be one of the primary causes of service degradation for storage systems. We then tackle this challenge by building next-generation distributed storage systems that can operate amidst heterogeneity while providing fast and predictable response times. First, we study skews in cloud workloads and propose scheduling strategies for key-value stores that seek to optimize latency. We then conduct a measurements study in one of the largest cloud provider networks to quantify variations in network latencies, and possible implications for storage services. Next, with fast non-volatile RAM (NVRAM) now becoming commercially available, we look into how storage systems can deal with the increasing diversity of storage technologies. We design and evaluate a distributed file system that can manage data across NVRAM and other types of storage, while providing low latency and high scalability. Lastly, we build a framework that transforms commodity Remote Direct Memory Access (RDMA) NICs into Turing machines—capable of performing arbitrary computations. This provides yet another compute resource on server machines, and we show how we can leverage it to accelerate common storage tasks as well as real storage applications.

Heterogenitet i molnmiljöer är ett livsfaktum—allt från skevheter i arbetsbelastningen och nätverksvägsförändringar till diversitet av serverhårdvarukomponenter, dessa är faktorer som påverkar prestanda för distribuerad lagring. I denna avhandling identifierar vi att heterogenitet faktiskt kan vara en av de främsta orsakerna till tjänste-degradering för lagringssystem. Vi tacklar sedan denna utmaning genom att bygga nästa generations distribuerade lagringssystem som kan fungera mitt i heterogenitet medan de ger snabba och förutsägbara svarstider. Först studerar vi skevheter i molnarbetsbelastningar och föreslår schemaläggningsstrategier för nyckelvärdelagring som försöker optimera latens. Vi utför sedan en mätstudie i ett av de största molnleverantörsnätverken för att kvantifiera variationer i nätverkslatenser och möjliga implikationer för lagringstjänster. Därefter, i och med att snabbt non-volatile RAM (NVRAM) nu blir kommersiellt tillgängligt, undersöker vi hur lagringssystem kan hantera den ökande diversiteten av lagringsteknik. Vi designar och utvärderar ett distribuerat filsystem som kan hantera data tvärs över NVRAM och andra typer av lagring, medan det ger låg latens och hög skalbarhet. Slutligen bygger vi ett ramverk som transformerar lättillgänglig Remote Direct Memory Access (RDMA) NICs till Turingmaskiner—som kan utföra godtyckliga beräkningar. Detta ger ännu en beräkningsresurs på servrar, och vi visar hur vi kan utnyttja den för att accelerera gemensamma lagringsuppgifter såväl som verkliga lagringsapplikationer.

It is becoming increasingly popular for distributed systems to exploit offload to reduce load on the CPU. Remote Direct Memory Access (RDMA) offload, in particular, has become popular. However, RDMA still requires CPU intervention for complex offloads that go beyond simple remote memory access. As such, the offload potential is limited and RDMA-based systems usually have to work around such limitations.

We present RedN, a principled, practical approach to implementing complex RDMA offloads, without requiring any hardware modifications. Using self-modifying RDMA chains, we lift the existing RDMA verbs interface to a Turing complete set of programming abstractions. We explore what is possible in terms of offload complexity and performance with a commodity RDMA NIC. We show how to integrate these RDMA chains into applications, such as the Memcached key-value store, allowing us to offload complex tasks such as key lookups. RedN can reduce the latency of key-value get operations by up to 2.6× compared to state-of-the-art KV designs that use one-sided RDMA primitives (e.g., FaRM-KV), as well as traditional RPC-over-RDMA approaches. Moreover, compared to these baselines, RedN provides performance isolation and, in the presence of contention,can reduce latency by up to 35× while providing applications with failure resiliency to OS and process crashes.

In multi-tenant systems, the CPU overhead of distributed file systems (DFSes) is increasingly a burden to application performance. CPU and memory interference cause degraded and unstable application and storage performance, in particular for operation latency. Recent client-local DFSes for persistent memory (PM) accelerate this trend. DFS offload to SmartNICs is a promising solution to these problems, but it is challenging to fit the complex demands of a DFS onto simple SmartNIC processors located across PCIe.

We present LineFS, a SmartNIC-offloaded, high-performance DFS with support for client-local PM. To fully leverage the SmartNIC architecture, we decompose DFS operations into execution stages that can be offloaded to a parallel datapath execution pipeline on the SmartNIC. LineFS offloads CPU-intensive DFS tasks, like replication, compression, data publication, index and consistency management to a Smart-NIC. We implement LineFS on the Mellanox BlueField Smart-NIC and compare it to Assise, a state-of-the-art PM DFS. LineFS improves latency in LevelDB up to 80% and throughput in Filebench up to 79%, while providing extended DFS availability during host system failures.

The adoption of low latency persistent memory modules (PMMs) upends the long-established model of remote storage for distributed file systems. Instead, by colocating computation with PMM storage, we can provide applications with much higher IO performance, sub-second application failover, and strong consistency. To demonstrate this, we built the Assise distributed file system, based on a persistent, replicated coherence protocol that manages client-local PMM as a linearizable and crash-recoverable cache between applications and slower (and possibly remote) storage. Assise maximizes locality for all file IO by carrying out IO on process-local, socket-local, and client-local PMM whenever possible. Assise minimizes coherence overhead by maintaining consistency at IO operation granularity, rather than at fixed block sizes.

We compare Assise to Ceph/BlueStore, NFS, and Octopus on a cluster with Intel Optane DC PMMs and SSDs for common cloud applications and benchmarks, such as LevelDB, Postfix, and FileBench. We find that Assise improves write latency up to 22x, throughput up to 56x, fail-over time up to 103x, and scales up to 6x better than its counterparts, while providing stronger consistency semantics.

A commonly held belief is that traffic engineering and routing changes are infrequent. However, based on our measurements over a number of years of traffic between data centers in one of the largest cloud provider's networks, we found that it is common for flows to change paths at ten-second intervals or even faster. These frequent path and, consequently, latency variations can negatively impact the performance of cloud applications, specifically, latency-sensitive and geo-distributed applications.

Our recent measurements and analysis focused on observing path changes and latency variations between different Amazon aws regions. To this end, we devised a path change detector that we validated using both ad hoc experiments and feedback from cloud networking experts. The results provide three main insights: (1) Traffic Engineering (TE) frequently moves (TCP and UDP) flows among network paths of different latency, (2) Flows experience unfair performance, where a subset of flows between two machines can suffer large latency penalties (up to 32% at the 95th percentile) or excessive number of latency changes, and (3) Tenants may have incentives to selfishly move traffic to low latency classes (to boost the performance of their applications). We showcase this third insight with an example using rsync synchronization.

To the best of our knowledge, this is the first paper to reveal the high frequency of TE activity within a large cloud provider's network. Based on these observations, we expect our paper to spur discussions and future research on how cloud providers and their tenants can ultimately reconcile their independent and possibly conflicting objectives. Our data is publicly available for reproducibility and further analysis at http://goo.gl/25BKte.

The increasing density of globally distributed datacenters reduces the network latency between neighboring datacenters and allows replicated services deployed across neighboring locations to share workload when necessary, without violating strict Service Level Objectives (SLOs). We present Kurma, a practical implementation of a fast and accurate load balancer for geo-distributed storage systems. At run-time, Kurma integrates network latency and service time distributions to accurately estimate the rate of SLO violations for requests redirected across geo-distributed datacenters. Using these estimates, Kurma solves a decentralized rate-based performance model enabling fast load balancing (in the order of seconds) while taming global SLO violations. We integrate Kurma with Cassandra, a popular storage system. Using real-world traces along with a geo-distributed deployment across Amazon EC2, we demonstrate Kurma’s ability to effectively share load among datacenters while reducing SLO violations by up to a factor of 3 in high load settings or reducing the cost of running the service by up to 17%.

This report provides an extended evaluation of Kurma, a practical implementation of a geo-distributed load balancer for backend storage systems. In this report we demonstrate the ability of distributed Kurma instances to accurately converge to the same solutions within 1% of the total datacenter’s capacity and the ability of Kurma to scale up to 8 datacenters using a single CPU core at each datacenter.

We tackle the problem of reducing tail latencies in distributed key-value stores, such as the popular Cassandra database. We focus on workloads of multiget requests, which batch together access to several data elements and parallelize read operations across the data store machines. We first analyze a production trace of a real system and quantify the skew due to multiget sizes, key popularity, and other factors. We then proceed to identify opportunities for reduction of tail latencies by recognizing the composition of aggregate requests and by carefully scheduling bottleneck operations that can otherwise create excessive queues. We design and implement a system called Rein, which reduces latency via inter-multiget scheduling using low overhead techniques. We extensively evaluate Rein via experiments in Amazon Web Services (AWS) and simulations. Our scheduling algorithms reduce the median, 95th, and 99th percentile latencies by factors of 1.5, 1.5, and 1.9, respectively.