Interactive checks for coordination avoidance
- PDF / 920,307 Bytes
- 22 Pages / 595.276 x 790.866 pts Page_size
- 76 Downloads / 189 Views
SPECIAL ISSUE PAPER
Interactive checks for coordination avoidance Michael Whittaker1 · Joseph M. Hellerstein1 Received: 29 January 2020 / Revised: 11 August 2020 / Accepted: 20 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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. Keywords Consistency · Transactions · Program analysis · Invariants
1 Introduction When an application designer decides to replicate a piece of data, they have to make a fundamental choice between weak and strong consistency. Replicating the data with strong consistency using a technique like distributed transactions (e.g., [12,37]) or state machine replication (e.g., [29,34,40,43]) makes the application designer’s life very easy. To the developer, a strongly consistent system behaves exactly like a single-threaded system running on a single node, so reasoning about the behavior of the system is simple [25]. Unfortunately, strong consistency is at odds with performance. The CAP theorem and PACELC theorem tell us that strongly consistent systems suffer from higher latency at best and unavailability at worst [1,13,20]. On the other hand, weak consistency models like eventual consistency
B
Michael Whittaker [email protected] Joseph M. Hellerstein [email protected]
1
[48], PRAM consistency [33], causal consistency [2] and others [35,36] allow data to be replicated with high availability and low latency, but they put a tremendous burden
Data Loading...
