Kite: Efficient and Available Release Consistency for the Datacenter

Vasileios Gavrielatos, Antonis Katsarakis, Vijay Nagarajan, Boris Grot, Arpit Joshi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Key-Value Stores (KVSs) came into prominence as highly-available, eventually consistent (EC), “NoSQL” Databases, but have quickly transformed into general-purpose, programmable storage systems. Thus, EC, while relevant, is no longer sufficient. Complying with the emerging requirements for stronger consistency, researchers have proposed KVSs with multiple consistency levels (MCL) that expose the consistency/performance trade-off to the programmer. We argue that this approach falls short in both programmability and performance. For instance, the MCL APIs proposed thus far, fail to capture the ordering relationship between strongly- and weakly-consistent accesses that naturally occur in programs.

Taking inspiration from shared memory, we advocate Release Consistency (RC) for KVSs. 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, the first highly-available, replicated KVS that offers a linearizable variant of RC for the asynchronous setting with individual process and network failures. Kiteen forces RC barriers 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. Our evaluation shows that the RDMA-enabled and heavily-multithreaded Kite achieves orders of magnitude better performance than Derecho (a state-of-the-art RDMA-enabled state machine replication system) and significantly outperforms ZAB (the protocol at the heart of Zookeeper).We demonstrate the efficacy of Kite by porting three lock-free shared memory data structures, and showing that Kite outperforms the competition.
Original languageEnglish
Title of host publicationProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
PublisherAssociation for Computing Machinery (ACM)
Number of pages16
ISBN (Print)9781450368186
Publication statusPublished - 19 Feb 2020
Event25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - Sam Diego, United States
Duration: 22 Feb 202026 Feb 2020


Symposium25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Abbreviated titlePPoPP 2020
Country/TerritoryUnited States
CitySam Diego
Internet address

Keywords / Materials (for Non-textual outputs)

  • Consistency
  • Availability
  • Fault tolerance
  • Replication
  • RDMA


Dive into the research topics of 'Kite: Efficient and Available Release Consistency for the Datacenter'. Together they form a unique fingerprint.

Cite this