A Low Latency Non-blocking Skip List with Retrial-Free Synchronization
Eunji Lee · Journal of Computing Science and Engineering · 2019
The underlying technology trend stresses the design of the software. With increasing use of many-core computers that equip a large number of independent processor units, enhancing scalability and concurrency of commercial software is of crucial importance. To fulfill this demand, non-blocking implementations of the popular data structures are extensively explored both in academia and industry to effectively harness the massive parallelism in a many-core system. This paper presents a new non-blocking skip list that is not only scalable but also provides low latency even under high-concurrency pressure. Existing techniques for parallelizing skip lists rely on retrying insertion operations which fail because one thread interferes with another. This approach can introduce long-tail latency when multiple threads compete for access to the same links. We address this issue by exploiting the probabilistic nature of the skip list by allowing insertion operations to terminate after a failure, even if all the links from a node have not been updated. The resulting reduction in the heights of many nodes changes the statistical properties of the links, on which the efficiency of the skip list depends. We compensate this side-effect by recording reductions in node height and recompense for them when new nodes are created. To demonstrate the effectiveness of our approach, we implement a prototype of our low-latency non-blocking skip list, and the measurement study with various workloads shows that our skip list provides more scalable performance and lower tail latency compared to existing skip lists.