Jellyfish: A fast skip list with MVCC

Jeseong Yeon, Hyeon Gyu Lee, Leeju Kim, Eunji Lee, Youil Han, Bryan S. Kim

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

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%.

Original languageEnglish (US)
Title of host publicationMiddleware 2020 - Proceedings of the 2020 21st International Middleware Conference
PublisherAssociation for Computing Machinery, Inc
Pages134-148
Number of pages15
ISBN (Electronic)9781450381536
DOIs
StatePublished - Dec 7 2020
Event21st International Middleware Conference, Middleware 2020 - Virtual, Online, Netherlands
Duration: Dec 7 2020Dec 11 2020

Publication series

NameMiddleware 2020 - Proceedings of the 2020 21st International Middleware Conference

Conference

Conference21st International Middleware Conference, Middleware 2020
Country/TerritoryNetherlands
CityVirtual, Online
Period12/7/2012/11/20

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Software

Fingerprint

Dive into the research topics of 'Jellyfish: A fast skip list with MVCC'. Together they form a unique fingerprint.

Cite this