Nagarajan, Vijayanand

Grot, Boris

Gavrielatos, Vasilis

Engineering and Physical Sciences Research Council (EPSRC)

2022-02-01T14:25:11Z

2022-02-01T14:25:11Z

2021-11-30

Online services and cloud applications such as graph applications, messaging systems, coordination services, HPC applications, social networks and deep learning rely on key-value stores (KVSes), in order to reliably store and quickly retrieve data. KVSes are NoSQL Databases with a read/write/read-modify-write API. KVSes replicate their dataset in a few servers, such that the KVS can continue operating in the presence of faults (availability). To allow programmers to reason about replication, KVSes specify a set of rules (consistency), which are enforced through the use of replication protocols. These rules must be intuitive to facilitate programmer productivity (programmability). A general-purpose KVS must maximize the number of operations executed per unit of time within a predetermined latency (performance) without compromising on consistency, availability or programmability. However, all three of these guarantees are at odds with performance. In this thesis, we explore the design of the replication layer of a general-purpose KVS, which is responsible for navigating this trade-off, by specifying and enforcing the consistency and availability guarantees of the KVS. We start the exploration by observing that modern, server-grade hardware with manycore servers and RDMA-capable networks, challenges conventional wisdom in protocol design. In order to investigate the impact of these advances on protocols and their design, we first create an informal taxonomy of strongly-consistent replication protocols. We focus on strong consistency semantics because they are necessary for a general-purpose KVS and they are at odds with performance. Based on this taxonomy we carefully select 10 protocols for analysis. Secondly, we present Odyssey, a frame-work tailored towards protocol implementation for multi-threaded, RDMA-enabled, in-memory, replicated KVSes. Using Odyssey, we characterize the design space of strongly-consistent replication protocols, by building, evaluating and comparing the 10 protocols. Our evaluation demonstrates that some of the protocols that were efficient in yesterday’s hardware are not so today because they cannot take advantage of the abundant parallelism and fast networking present in modern hardware. Conversely, some protocols that were inefficient in yesterday’s hardware are very attractive today. We distil our findings in a concise set of general guidelines and recommendations for protocol selection and design in the era of modern hardware. The second step of our exploration focuses on the tension between consistency and performance. The problem is that expensive strongly-consistent primitives are necessary to achieve synchronization, but in typical applications only a small fraction of accesses is actually used for synchronization. To navigate this trade-off, we advocate the adoption of Release Consistency (RC) for KVSes. We argue that RC’s one-sided barriers are ideal for capturing the ordering relationship between synchronization and non-synchronization accesses while enabling high performance. We present Kite, a general-purpose, replicated KVS that enforces RC through a novel fast/slow path mechanism that leverages the absence of failures in the typical case to maximize performance, while relying on the slow path for progress. In ad dition, Kite leverages our study of replication protocols to select the most suitable protocols for its primitives and is implemented over Odyssey to make the most out of modern hardware. Finally, Kite does not compromise on consistency, availability or programmability, as it provides sufficient primitives to implement any algorithm (consistency), does not interrupt its operation on a failure (availability), and offers the RC API that programmers are already familiar with (programmability).

https://hdl.handle.net/1842/38508

http://dx.doi.org/10.7488/era/1772

en

The University of Edinburgh

Vasilis Gavrielatos, Antonios Katsarakis and Vijay Nagarajan. “Odyssey: The Impact of Modern Hardware on Strongly-Consistent Replication Protocols.” In Proceedings of the Sixteenth European Conference on Computer Systems (EuroSys), pp. 245–260. 2021

Vasilis Gavrielatos, Antonios Katsarakis, Vijay Nagarajan, Boris Grot, and Arpit Joshi. “Kite: Efficient and Available Release Consistency for the Datacenter.” In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp 1–16. 2020.

M. Dananjaya, V. Gavrielatos, A. Joshi, and V. Nagarajan. Lazy release persistency. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’20, page 1173–1186, New York, NY, USA, 2020. Association for Computing Machinery.

V. Gavrielatos, A. Katsarakis, A. Joshi, N. Oswald, B. Grot, and V. Nagarajan. Scale-out ccNUMA: Exploiting Skew with Strongly Consistent Caching. In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18, pages 21:1– 21:15, New York, NY, USA, 2018. ACM.

V. Gavrielatos, A. Katsarakis, and V. Nagarajan. Extending Classic Paxos for High-performance Read-Modify-Write Registers, 2021.

V. Gavrielatos, V. Nagarajan, and P. Fatourou. Towards the synthesis of coherence/replication protocols from consistency models via real-time orderings. In Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC ’21, New York, NY, USA, 2021. Association for Computing Machinery

A. Katsarakis, V. Gavrielatos, M. S. Katebzadeh, A. Joshi, A. Dragojevic, B. Grot, and V. Nagarajan. Hermes: A Fast, Fault-Tolerant and Linearizable Replication Protocol. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’20, page 201–217, New York, NY, USA, 2020. Association for Computing Machinery.

key-value store

KVS

consistency model

performance maximization

Release consistency

Designing the replication layer of a general-purpose datacenter key-value store

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy