Published: 7 December 2020
Proceedings of the 21st International Middleware Conference ; https://doi.org/10.1145/3423211.3425672
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: list / append / skip / concurrency control / version / structures / JellyFish / latency / overhead
Scifeed alert for new publicationsNever miss any articles matching your research from any publisher
- Get alerts for new papers matching your research
- Find out the new papers from selected authors
- Updated daily for 49'000+ journals and 6000+ publishers
- Define your Scifeed now
Click here to see the statistics on "Proceedings of the 21st International Middleware Conference" .