Journal
APPLIED SCIENCES-BASEL
Volume 13, Issue 17, Pages -Publisher
MDPI
DOI: 10.3390/app13179925
Keywords
skiplist; in-memory data structure; in-memory database; scalability; index structure
Ask authors/readers for more resources
In this work, ESL, a high-performance and scalable skiplist, is proposed to optimize index levels for CPU cache and improve traverse operation performance. ESL reduces synchronization overhead by asynchronously updating index levels and tolerating inconsistencies. Experimental evaluations show that ESL outperforms other skiplists with a 2.8x improvement in throughput, lower tail latency, and consistently higher throughput in real-world workload evaluation.
With the increasing capacity and cost-efficiency of DRAM in multi-core environments, in-memory databases have emerged as fundamental solutions for delivering high performance. The index structure is a crucial component of the in-memory database, which, leveraging fast access to DRAM, plays an important role in the performance improvement and scalability of in-memory databases. A skiplist is one of the most widely used in-memory index structures and it has been adopted by popular databases. However, skiplists suffer from poor performance due to their structural limitations. In this work, we propose ESL, a high-performance and scalable skiplist. ESL efficiently enhances the performance of traverse operations by optimizing index levels for the CPU cache. With CPU cache-optimized index levels, we synergistically leverage a combination of exponential and linear searches. In addition, ESL reduces synchronization overhead by updating the index levels asynchronously, while tolerating inconsistencies. In our YCSB evaluation, ESL improves throughput by up to 2.8x over other skiplists in high-level evaluations. ESL also shows lower tail latency than other skiplists by up to 35x. Also, ESL consistently shows higher throughput in our real-world workload evaluation.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available