Write-Optimized and Consistent Skiplists for Non-Volatile Memory
Autor: | Xiaomin Zou, Xiao Renzhi, Dan Feng, Fang Wang, Yuchong Hu, Wei Xueliang, Mengya Lei |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: |
010302 applied physics
Random access memory Skip list General Computer Science consistency Computer science General Engineering 020206 networking & telecommunications 02 engineering and technology Parallel computing 01 natural sciences Memory controller TK1-9971 Non-volatile memory Consistency (database systems) Memory management write efficiency 0103 physical sciences 0202 electrical engineering electronic engineering information engineering General Materials Science skiplist Electrical engineering. Electronics. Nuclear engineering Latency (engineering) Throughput (business) |
Zdroj: | IEEE Access, Vol 9, Pp 69850-69859 (2021) |
ISSN: | 2169-3536 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |