Search

Strongly consistent distributed systems are easy to reason about but face fundamental limitations in availability and performance. Weakly consistent systems can be implemented with very high performance but place a burden on the application developer to reason about complex interleavings of execution. Invariant confluence provides a formal framework for understanding when we can get the best of both worlds. An invariant confluent object can be efficiently replicated with no coordination needed to preserve its invariants. However, actually determining whether or not an object is invariant confluent is challenging. In this paper, we establish conditions under which a commonly used sufficient condition for invariant confluence is both necessary and sufficient, and we use this condition to design (a) a general-purpose interactive invariant confluence decision procedure and (b) a novel sufficient condition that can be checked automatically. We then take a step beyond invariant confluence and introduce a generalization of invariant confluence, called segmented invariant confluence, that allows us to replicate non-invariant confluent objects with a small amount of coordination. We implemented these formalisms in a prototype called Lucy and found that our decision procedures efficiently handle common real-world workloads including foreign keys, rollups, escrow transactions, and more. We also found that segmented invariant confluent replication can deliver up to an order of magnitude more throughput than linearizable replication for low contention workloads and comparable throughput for medium to high contention workloads.

In emails, information abounds. Whether it be a bill reminder, a hotel confirmation, or a shipping notification, our emails contain useful bits of information that enable a number of applications. Most of this email traffic is machine-generated, sent from a business to a human. These business-to-consumer emails are typically instantiated from a set of email templates, and discovering these templates is a key step in enabling a variety of intelligent experiences. Existing email information extraction systems typically separate information extraction into two steps: an offline template discovery process (called template induction) that is periodically run on a sample of emails, and an online email annotation process that applies discovered templates to emails as they arrive. Since information extraction requires an email's template to be known, any delay in discovering a newly created template causes missed extractions, lowering the overall extraction coverage. In this paper, we present a novel system called Crusher that discovers templates completely online, reducing template discovery delay from a week (for the existing MapReduce-based batch system) to minutes. Furthermore, Crusher has a resource consumption footprint that is significantly smaller than the existing batch system. We also report on the surprising lesson we learned that conventional stream processing systems do not present a good framework on which to build Crusher. Crusher delivers an order of magnitude more throughput than a prototype built using a stream processing engine. We hope that these lessons help designers of stream processing systems accommodate a broader range of applications like online template induction in the future.

Quorum systems are a powerful mechanism for ensuring the consistency of replicated data. Production systems usually opt for majority quorums due to their simplicity and fault tolerance, but majority quorum systems provide poor throughput and scalability. Alternatively, researchers have invented a number of theoretically "optimal" quorum systems, but the underlying theory ignores many practical complexities such as machine heterogeneity and workload skew. In this paper, we conduct a pragmatic re-examination of quorum systems. We enrich the current theory on quorum systems with a number of practical refinements to find quorum systems that provide higher throughput, lower latency, and lower network load. We also develop a library Quoracle that precisely quantifies the available trade-offs between quorum systems to empower engineers to find optimal quorum systems, given a set of objectives for specific deployments and workloads. Our tool is available online at: https://github.com/mwhittaker/quoracle., To be published in PaPoC 2021 (https://papoc-workshop.github.io/2021/)

Traditionally, the high cost of network communication between servers has hidden the impact of cross-core coordination in replicated systems. However, new technologies, like kernel-bypass networking and faster network links, have exposed hidden bottlenecks in distributed systems. This paper explores how to build multicore-scalable, replicated storage systems. We introduce a new guideline for their design, called the Zero-Coordination Principle. We use this principle to design a new multicore-scalable, in-memory, replicated, key-value store, called Meerkat. Unlike existing systems, Meerkat eliminates all cross-core and cross-replica coordination, both of which pose a scalability bottleneck. Our experiments found that Meerkat is able to scale up to 80 hyper-threads and execute 8.3 million transactions per second. Meerkat represents an improvement of 12X on state-of-the-art, fault-tolerant, in-memory, transactional storage systems built using leader-based replication and a shared transaction log.

Interaktive Webanwendungen, mit tausenden von Nutzern, erfordern den adaquaten Einsatz von geeigneten Datenbanktechnologien zur Verwaltung und Bereitstellung der ausgetauschten Daten. Am Beispiel des Open Source-Projektes PINGO wird aufgezeigt, wie sich die dokumentenorientierte NoSQL-Datenbank MongoDB in eine Webanwendungsarchitektur integrieren lasst, sodass die Datenbank skaliert und alle Datenbankzugriffe unmittelbar ausgefuhrt werden konnen. Ein Lasttest-Szenario belegt, dass die Geschwindigkeit der Gesamtanwendung nicht durch die genutzte MongoDB-Instanz, sondern durch die Ausstattung des eingesetzten Webservers limitiert wird. Im Szenario war es nicht moglich eine Lastobergrenze von MongoDB zu identifizieren, da sich die Netzwerkverbindung mit einer Ubertragungsbandbreite von 400 Mbit/s als limitierender Faktor erwies. Daruber hinaus werden die mehr als funfjahrigen Projekterfahrungen genutzt, um die Entwicklung mit MongoDB kritisch zu reflektieren. Im Anwendungskontext zeigt sich MongoDB als flexible Datenbanktechnologie, welche sich einfach in das verwendete Web-Framework Ruby on Rails integrieren lasst. Die Konzepte der Schemalosigkeit und die Moglichkeit zur Bildung von logischen Einheiten zwischen Datenspeicherung und Darstellung erlauben zudem eine agile Weiterentwicklung der Webanwendung. Die grosten Herausforderungen im Projektkontext resultierten aus der Tendenz vieler Entwickler relationale Modellierungskonzepte auf MongoDB zu ubertragen.

Systematically reasoning about the fine-grained causes of events in a real-world distributed system is challenging. Causality, from the distributed systems literature, can be used to compute the causal history of an arbitrary event in a distributed system, but the event's causal history is an over-approximation of the true causes. Data provenance, from the database literature, precisely describes why a particular tuple appears in the output of a relational query, but data provenance is limited to the domain of static relational databases. In this paper, we present wat-provenance: a novel form of provenance that provides the benefits of causality and data provenance. Given an arbitrary state machine, wat-provenance describes why the state machine produces a particular output when given a particular input. This enables system developers to reason about the causes of events in real-world distributed systems. We observe that automatically extracting the wat-provenance of a state machine is often infeasible. Fortunately, many distributed systems components have simple interfaces from which a developer can directly specify wat-provenance using a technique we call wat-provenance specifications. Leveraging the theoretical foundations of wat-provenance, we implement a prototype distributed debugging framework called Watermelon.

Network measurement is an essential component of many SDN applications, but most existing controller platforms force programmers to implement measurement tasks by installing fine-grained forwarding rules on switches---an approach that significantly increases configuration and management complexity. This paper proposes a radically different approach: rather than implementing measurement tasks directly on network switches, we argue for pushing measurement to the edge and utilizing the abundant resources available on end hosts. At a technical level, our approach is based on two key ideas: (i) we express measurement tasks using programs in a high-level, declarative query language, and (ii) we use program analysis to calculate predicates that can be used to answer queries at the edge of the network. We present an implementation of our approach on top of the NetKAT framework, we develop case studies illustrating the benefits of our approach, and we conduct experiments that quantify performance on realistic benchmarks.