JellyFish
- 7 December 2020
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 21st International Middleware Conference
Abstract
Multi-version concurrency control is a widely employed concurrency control mechanism, as it allows non-blocking accesses while providing isolation among transactions. However, maintaining multiple versions increases the latency for both point lookups and ranged retrievals because of the overhead in finding the right version. In particular, the append-only skip list---widely used in the state-of-the-art key-value stores (KVS)---shows a significant performance degradation due to its append-only nature. This paper presents a novel skip list implementation called JellyFish. JellyFish reduces the overhead of multi-version concurrency control by separating the per-key updates from the key indexing. We implement our design on top of RocksDB and compare it against a wide variety of data structures. Our evaluation with micro-benchmarks and real-world workloads show that we not only improve the throughput by up to 93%, but also reduce the latency of update operations by up to 42%.Keywords
Funding Information
- National Research Foundation of Korea (NRF 2019R1A2C1090337)
This publication has 26 references indexed in Scilit:
- Fast Serializable Multi-Version Concurrency Control for Main-Memory Database SystemsPublished by Association for Computing Machinery (ACM) ,2015
- Scaling concurrent log-structured data storesPublished by Association for Computing Machinery (ACM) ,2015
- A scalable distributed skip list for range queriesPublished by Association for Computing Machinery (ACM) ,2014
- High-performance concurrency control mechanisms for main-memory databasesProceedings of the VLDB Endowment, 2011
- Serializable isolation for snapshot databasesACM Transactions on Database Systems, 2009
- Lock-free linked lists and skip listsPublished by Association for Computing Machinery (ACM) ,2004
- The log-structured merge-tree (LSM-tree)Acta Informatica, 1996
- A critique of ANSI SQL isolation levelsPublished by Association for Computing Machinery (ACM) ,1995
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Concurrency Control in Distributed Database SystemsACM Computing Surveys, 1981