Write-Optimized and Consistent Skiplists for Non-Volatile Memory

Skiplist as an in-memory index performs pretty well on rapid insertions because there are no rotations or reallocations for rebalancing. The emerging non-volatile memory (NVM) technologies have spurred a deep interest in designing efficient NVM-based skiplist. Because the data written to NVM may be partially updated or reordered by the memory controller, write operations in NVM-based persistent skiplist may suffer data inconsistency in the face of system failures. Moreover, a traditional Redo-Logging-based consistent Skiplist (RLS for short) guarantees data consistency but introduces double NVM writes, which can significantly degrade the lifetime of NVM. In this paper, we propose two write-optimized and consistent skiplists for NVM, called Atomic Skiplist (AS for short) and Atomic and Selective Consistency Skiplist (ASCS for short). AS exploits log-free failure-atomic writes for both the 0th and internal levels of skiplist to avoid double NVM writes of redo-logging. ASCS leverages selective consistency and log-free failure-atomic writes to further reduce NVM writes from index pointers. Compared with RLS, experimental results show that AS and ASCS reduce the number of cache-line flushes by 67.5% and 75%, decrease the insertion latency by 32.3% - 40.9% and 36.2% - 54.2%, degrade the deletion latency by 38.7% - 47.1% and 44.9% - 57.8%, as well as increase insertion throughput by 49.1% and 65.0% and deletion throughput by 65.1% and 80.5%, respectively.