Serverless computing has become increasingly popular in the last few years because it simplifies the developer's experience of constructing and deploying applications. Simultaneously, it enables cloud providers to pack multiple users' workloads into shared physical resources at a fine granularity, achieving higher resource efficiency. However, existing serverless Function-as-a-Service (FaaS) systems have significant shortcomings around state management—notably, high-latency IO, disabled point-to-point communication, and high function invocation overheads.

In this dissertation, we present a line of work in which we redesign serverless infrastructure to natively support efficient, consistent, and fault-tolerant state management. We first explore the architecture of a stateful FaaS system we designed called Cloudburst, which overcomes many of the limitations of commercial FaaS systems. We then turn to consistency and fault-tolerance, describing how we provide read atomic transactions in the context of FaaS applications. Finally, we describe the design and implementation of a serverless dataflow API and optimization framework specifically designed to support machine learning prediction serving workloads.

Serverless computing has gained significant attention over the last few years. The core advantage of serverless is that it abstracts away low-level operational concerns and opens up opportunities for developers without sophisticated systems expertise to harness the power of the cloud and build scalable distributed applications. However, there are three main challenges that limit the capability and prevent the adoption of serverless infrastructure. First, serverless systems need to deliver high performance at any scale, from a single multicore machine to a geo-distributed deployment. Second, serverless systems need to dynamically respond to workload shifts and autoscale to meet performance goals while minimizing cost. Third, serverless systems need to offer robust consistency guarantees to support a wide variety of applications while maintaining high performance.

This dissertation presents a line of research that addresses these challenges. We first introduce Anna, a high-performance key-value store that employs a lattice-based coordination-free execution model. The design of Anna achieves seamless scaling while offering rich consistency guarantees. We then discuss how we extend Anna to become a serverless, tiered storage system. Anna's autoscaling mechanisms and policies enable intelligent trade-off between latency and cost under dynamic workloads. Finally, we present HydroCache, a caching layer that sits in between a function-as-a-service platform and the underlying storage system. HydroCache maintains the benefit of resource disaggregation offered by existing serverless computing platforms while delivering low-latency request handling and transactional causal consistency, the strongest consistency model that can be achieved without coordination.

Building system software is a notoriously complex and arduous endeavor.

Developing tools and methodologies for practical system software engineering

has long been an active area of research. This thesis explores system software

development through the lens of a declarative, data-centric programming

language that can succinctly express high-level system specifications and be

directly compiled to executable code. By unifying specification and

implementation, our approach avoids the common problem of implementations

diverging from specifications over time. In addition, we show that using a

declarative language often results in drastic reductions in code size (100× and

more) relative to procedural languages like Java and C++. We demonstrate these

advantages by implementing a host of functionalities at various levels of the

system hierarchy, including network protocols, query optimizers, and scheduling

policies. In addition to providing a compact and optimized implementation, we

demonstrate that our declarative implementations often map very naturally to

traditional specifications: in many cases they are line-by-line translations of

published pseudcode.

We started this work with the hypothesis that declarative languages --

originally developed for the purposes of data management and querying -- could

be fruitfully adapted to the specification and implementation of core system

infrastructure. A similar argument had been made for networking protocols a

few years earlier [61]. However, our goals were quite different: we wanted to

explore a broader range of algorithms and functionalities (dynamic programming,

scheduling, program rewriting, and system auditing) that were part of complex,

real-world software systems. We identified two existing system components --

query optimizers in a DBMS and task schedulers in a cloud computing system --

that we felt would be better specified via a declarative language. Given our

interest in delivering real-world software, a key challenge was identifying the

right system boundary that would permit meaningful declarative implementations

to coexist within existing imperative system architectures. We found that

relations were a natural boundary for maintaining the ongoing system state on

which the imperative and declarative code was based, and provided an elegant

way to model system architectures.

This thesis explores the boundaries of declarative systems via two projects.

We begin with Evita Raced; an extensible compiler for the Overlog language used

in our declarative networking system, P2. Evita Raced is a metacompiler -- an

Overlog compiler written in Overlog -- that integrates seamlessly with the P2

dataflow architecture. We first describe the minimalist design of Evita Raced,

including its extensibility interfaces and its reuse of the P2 data model and

runtime engine. We then demonstrate that a declarative language like Overlog

is well-suited to expressing traditional and novel query optimizations as well

as other program manipulations, in a compact and natural fashion. Following

Evita Raced, we describe the initial work in BOOM Analytics, which began as a

large-scale experiment at building "cloud" software in a declarative language.

Specifically, we used the Overlog language to implement a "Big Data" analytics

stack that is API-compatible with the Hadoop MapReduce architecture and

provides comparable performance. We extended our declarative version of Hadoop

with complex distributed features that remain absent in the stock Hadoop Java

implementation, including alternative scheduling policies, online aggregation,

continuous queries, and unique monitoring and debugging facilities. We present

quantitative and anecdotal results from our experience, providing concrete

evidence that both data-centric design and declarative languages can

substantially simplify systems programming.

History provides context for the present. In the same way, past user interactions provide context for present explorations. This thesis investigates ways to reify user interaction history to address emerging challenges in the design and programming of human-data interfaces.

We leverage interaction history in three different but connected designs. The first is to enhance the design of interactions that suffer from delays, such as when working with remote databases. We use interaction history as a visual anchor to facilitate concurrent interactions, which ameliorate the cognitive burdens caused by delays. The second is to facilitate the programming of interactive visualizations involving asynchronous communication with remote databases. We capture event histories as a first-class programming construct, allowing the developer to declaratively specify what data to compute and how to update the state of the user interface. This way, developers avoid the low-level details of accessing remote data and coordinating events. The third and last design is to use interaction history to create a bridge between interaction design and programming. We capture and reify interaction history in both computational notebooks and interactive visualizations. Affordances on these reified histories help data scientists move fluidly between the two mediums.

We present novel techniques and systems for managing data context within the machine learning (ML) lifecycle. Drawing from a vision laid out in 2018, we present Flor and its evolutions, FlorDB and FlorDB with Build extensions, designed for comprehensive metadata capture and version control in the ML lifecycle. A cornerstone of our approach is the use of an interview study to understand what the ML lifecycle is, and how engineers operationalize machine learning, focusing on MLOps and the iterative model development process. Through the implementation of these systems and their use in real-world applications for lawyers and journalists, we demonstrate the tangible benefits of rich data context in agile model development. In sum, we show how the integration of Application, Build, and Change contexts—The ABCs of Context—enables MLEs to close the loop in the ML lifecycle.

Distributed systems are difficult to reason about and program because of fundamental uncertainty in their executions, arising from sources of nondeterminism such as asynchrony and partial failure. Until relatively recently, responsibility for managing these complexities was relegated to a small group of experts, who hid them behind infrastructure-backed abstractions such as distributed transactions. As a consequence of technology trends including the rise of cloud computing, the proliferation of open-source storage and processing technologies, and the ubiquity of personal mobile devices, today nearly all non-trivial applications are physically distributed and combine a variety of heterogeneous technologies, including "NoSQL" stores, message queues and caches. Application developers and analysts must now (alongside infrastructure engineers) take on the challenges of distributed programming, with only the meager assistance provided by legacy languages and tools which reflect a single-site, sequential model of computation.

This thesis presents an attempt to avert this crisis by rethinking both the languages we use to implement distributed systems and the analyses and tools we use to understand them. We begin by studying both large-scale storage systems and the coordination protocols they require for correct behavior through the lens of declarative, query-based programming languages. We then use these experiences to guide the design of a new class of "disorderly" programming languages, which enable the succinct expression of common distributed systems patterns while capturing uncertainty in their semantics. We first present Dedalus, a language that extends Datalog with a small set of temporal operators that intuitively capture change and temporal uncertainty, and devise a model- theoretic semantics that allows us to formally study the relationship between programs and their outcomes. We then develop Bloom, which provides—in addition to a programmer-friendly syntax and mechanisms for structuring and reuse—powerful analysis capabilities that identify when distributed programs produce deterministic outcomes despite widespread nondeterminism in their executions.

On this foundation we develop a collection of program analyses that help programmers to reason about whether their distributed programs produce correct outcomes in the face of asynchrony and partial failure. Blazes addresses the challenge of asynchrony, providing assurances that distributed systems (implemented in Bloom or in parallel dataflow frameworks such as Apache Storm) produce consistent outcomes in all executions. When it cannot provide this assurance, Blazes augments the system with carefully-chosen synchronization code that ensures deterministic outcomes while minimizing global coordination. Lineage-driven fault injection (LDFI)—which addresses the challenge of partial failure—uses data lineage to reason about whether programs written in Dedalus or Bloom provide adequate redundancy to overcome a variety of failures that can occur during execution, including component failure, message loss and network partitions. LDFI can find fault-tolerance bugs using an order of magnitude fewer executions than random fault injection strategies, and can provide guarantees that programs are bug-free for given configurations and execution bounds.

Driven by the widespread adoption of both cloud computing and mobile devices,

distributed computing is increasingly commonplace. As a result, a growing

proportion of developers must tackle the complexity of distributed

programming---that is, they must ensure correct application behavior in the

face of asynchrony, concurrency, and partial failure.

To help address these difficulties, developers have traditionally relied upon

system infrastructure that provides strong consistency guarantees

(e.g., consensus protocols and distributed transactions). These mechanisms

hide much of the complexity of distributed computing---for example, by

allowing programmers to assume that all nodes observe the same set of events

in the same order. Unfortunately, providing such strong guarantees becomes

increasingly expensive as the scale of the system grows, resulting in

availability and latency costs that are unacceptable for many modern

applications.

Hence, many developers have explored building applications that only require

loose consistency guarantees---for example, storage systems that only

guarantee that all replicas eventually converge to the same state, meaning

that a replica might exhibit an arbitrary state at any particular

time. Adopting loose consistency involves making a well-known tradeoff:

developers can avoid paying the latency and availability costs incurred by

mechanisms for achieving strong consistency, but in exchange they must deal

with the full complexity of distributed computing. As a result, achieving

correct application behavior in this environment is very difficult.

This thesis explores how to aid developers of loosely consistent applications

by providing programming language support for the difficulties they

face. The language level is a natural place to tackle this problem: because

developers that use loose consistency have fewer system facilities that they

can depend on, consistency concerns are naturally pushed into application

logic. In part, our goal has been to recognize, formalize, and automate

application-level consistency patterns.

We describe three language variants that each tackle a different challenge in

distributed programming. Each variant is a modification of Bloom, a

declarative language for distributed programming we have developed at UC

Berkeley. The first variant of Bloom, Bloom^L, enables

deterministic distributed programming without the need for distributed

coordination. Second, Edelweiss allows distributed storage reclamation

protocols to be generated in a safe and automatic fashion. Finally,

Bloom^PO adds sophisticated ordering constraints that

we use to develop a declarative, high-level implementation of concurrent

editing, a particularly difficult class of loosely consistent programs.

The past few years have seen a wave of enthusiasm for serverless computing, and we begin this work by analyzing the marketplace trends and underlying technical factors that have shaped the movement. We find that serverless computing addresses programming challenges in the same class as those that high-level programming languages address, suggesting that serverless computing may be viewed as high-level programming for distributed systems.

We next turn our attention to one of the key shortcomings of serverless: the lack of integration between compute and state. We develop FaaSFS, a distributed file system that is compatible with POSIX applications but uses a novel consistency model with relaxed real-time ordering constraints. We call this model externally consistent sequential consistency (ECSC) and use it to scale a pre-existing single-server application to 10,000 serverless processes. We also show that under reasonable assumptions ECSC is indistinguishable from linearizability, a widely accepted strong form of consistency.

Lastly, we explore whether serverless computing might lead to the demise of server hardware. By applying Amdahl's law and scaling rules for interconnect costs, we show that applications that rely on coordination protocols are particularly dependent on large servers for scalability. In contrast, those implemented with coordination-free protocols can run well on collections of small, low-cost servers or on disaggregated hardware. These approaches will likely continue to coexist, suggesting that a need for underlying server hardware will remain even as serverless abstractions thrive.

Sensor networks are progressively becoming a standard in applications that require the monitoring of physical phenomena. Measurements like temperature, humidity, light, and acceleration are gathered at various locations and can be used to extract information on the phenomenon observed.

Sensor networks are naturally distributed, and they display strong resource restrictions. Moreover, the gathered data comes in various degrees of uncertainty, due to noisy and dropped measurements, interference, and the unavoidable discretization of the examined domain. A basic task in sensor networks is to interactively gather data from a subset of nodes in the network. Surprisingly, this problem is non-trivial to implement efficiently and robustly, even for relatively static networks

In this thesis we address the traditional database problem of query optimization in this new setting. We identify the characteristics of sensor network environments and the requirements of applications that are relevant to querying. We focus on making queries more energy efficient by means of minimizing the communication and sensing that is required to provide sufficient answers. Our contributions include theoretical, algorithmic and empirical results. We provide complexity analysis for common data gathering tasks, develop algorithms that approximate the optimal query plans, and apply our techniques to a prototype implementation that tests our theory and algorithms over real world data, demonstrating the feasibility of our approach.

Low-resource organizations worldwide work to improve health, education, infrastructure, and economic opportunity in disadvantaged communities. These organizations must collect data in order to inform service delivery and performance monitoring. In such settings, data collection can be laborious and expensive due to challenges in the physical and digital infrastructure, in capacity and retention of technical staff, and in poor performance incentives. Governments, donors, and non-governmental organizations (NGOs) large and small are demanding more accountability and transparency, resulting in increased data collection workloads. Despite continued emphasis and investment, countless data collection efforts continue to experience delayed and low-quality results. Existing tools and capabilities for data collection have not kept pace with increased reporting requirements.

This dissertation addresses data collection in low-resource settings by algorithmically shepherding human attention at three different scales: (1) by redirecting workers' attention at the moment of entry, (2) by reformulating the data collection instrument in its design and use, and (3) by reorganizing the flow and composition of data entry tasks within and between organizations. These three different granularities of intervention map to the three major parts of this dissertation.

First, the Usher system learns probabilistic models from previous form responses, supplementing the lack of expertise and quality control. The models are a principled foundation for data in forms, and are applied at every step of the data collection process: form design, form filling, and answer verification. Simulated experiments demonstrate that Usher can improve data quality and reduce quality-control effort considerably.

Next, a number of dynamic user-interface mechanisms improve accuracy and efficiency during the act of data entry, powered by Usher. Based on a cognitive model, these interface adaptations can be applied as interventions before, during, and after input. An evaluation with professional data entry clerks in rural Uganda reduced error by up to 78\%.

Finally, the Shreddr system transforms paper form images into structured data on-demand. Shreddr reformulates data entry work-flows with pipeline and batching optimizations at the organizational level. It combines emergent techniques from computer vision, database systems, and machine learning, with newly-available infrastructure - on-line workers and mobile connectivity - into a hosted data entry web-service. It is a framework for data digitization that can deliver Usher and other optimizations at scale. Shreddr's impact on digitization efficiency and quality is illustrated in a one-million-value case study in Mali.

The main contributions of this dissertation are (1) a probabilistic foundation for data collection, which effectively guides form design, form filling, and value verification; (2) dynamic data entry interface adaptations, which significantly improve data entry accuracy and efficiency; and (3) the design and large-scale evaluation of a hosted-service architecture for data entry.