AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory

Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai 200240, China
Show Author Information

Abstract

Persistent indexing structures are proposed in response to emerging non-volatile memory (NVM) to provide high performance yet durable indexes. However, due to the lack of real NVM hardware, many prior persistent indexing structures were evaluated via emulation, which varies a lot across different setups and differs from the real deployment. Recently, Intel has released its Optane DC Persistent Memory Module (PMM), which is the first production-ready NVM. In this paper, we revisit popular persistent indexing structures on PMM and conduct comprehensive evaluations to study the performance differences among persistent indexing structures, including persistent hash tables and persistent trees. According to the evaluation results, we find that Cacheline-Conscious Extendible Hashing (CCEH) achieves the best performance among all evaluated persistent hash tables, and Failure-Atomic ShifT B+-Tree (FAST) and Write Optimal Radix Tree (WORT) perform better than other trees. Besides, we find that the insertion performance of hash tables is heavily influenced by data locality, while the insertion latency of trees is dominated by the flush instructions. We also uncover that no existing emulation methods accurately simulate PMM for all the studied data structures. Finally, we provide three suggestions on how to fully utilize PMM for better performance, including using clflushopt/clwb with sfence instead of clflush, flushing continuous data in a batch, and avoiding data access immediately after it is flushed to PMM.

Keywords

persistent memorydata structureperformanceIntel Optane DC persistent memory module (PMM)

Electronic Supplementary Material

Download File(s)
jcst-36-1-140-Highlights.pdf (129.6 KB)

References

[1]
Kannan S, Bhat N, Gavrilovska A, Arpaci-Dusseau A, Arpaci-Dusseau R. Redesigning LSMs for nonvolatile memory with NoveLSM. In Proc. the 2018 USENIX Annual Technical Conference, July 2018, pp.993-1005.
[2]
Liu S, Wei Y, Zhao J, Kolli A, Khan S. PMTest: A fast and flexible testing framework for persistent memory programs. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.411-425. DOI: 10.1145/3297858.3304015.
Crossref
[3]
Xu J, Kim J, Memaripour A, Swanson S. Finding and fixing performance pathologies in persistent memory software stacks. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.427-439. DOI: 10.1145/3297858.3304077.
Crossref
[4]

Xia F, Jiang D J, Xiong J, Sun N H. A survey of phase change memory systems. Journal of Computer Science and Technology, 2015, 30(1): 121-144. DOI: 10.1007/s11390-015-1509-2.
Crossref Google Scholar
[5]
Zuo P, Hua Y. A write-friendly hashing scheme for non-volatile memory systems. In Proc. the 33rd International Conference on Massive Storage Systems and Technology, May 2017.
[6]
Zuo P, Hua Y, Wu J. Write-optimized and high-performance hashing index scheme for persistent memory. In Proc. the 13th USENIX Symposium on Operating Systems Design and Implementation, Oct. 2018, pp.461-476.
[7]
Nam M, Cha H, Choi Y R, Noh S H, Nam B. Write-optimized dynamic hashing for persistent memory. In Proc. the 17th USENIX Conference on File and Storage Technologies, Feb. 2019, pp.31-44. DOI: 10.5555/3323298.3323302.
[8]
Yang J, Wei Q, Chen C, Wang C, Yong K L, He B. NV-Tree: Reducing consistency cost for NVM-based single level systems. In Proc. the 13th USENIX Conference on File and Storage Technologies, Feb. 2015, pp.167-181. DOI: 10.5555/2750482.2750495.
[9]

Chen S Jin Q. Persistent B+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 2015, 8(7): 786-797. DOI: 10.14778/2752939.2752947.
Crossref Google Scholar
[10]
Lee S K, Lim K H, Song H, Nam B, Noh S H. WORT: Write optimal radix tree for persistent memory storage systems. In Proc. the 15th USENIX Conference on File and Storage Technologies, Feb. 2017, pp.257-270.
[11]
Hwang D, Kim W H, Won Y, Nam B. Endurable transient inconsistency in byte-addressable persistent B+-tree. In Proc. the 16th USENIX Conference on File and Storage Technologies, Feb. 2018, pp.187-200.
[12]

Burr G W, Breitwisch M J, Franceschini M et al. Phase change memory technology. Journal of Vacuum Science & Technology B, 2010, 28(2): 223-262. DOI: 10.1116/1.3301579.
Crossref Google Scholar
[13]

Apalkov D, Khvalkovskiy A, Watts S et al. Spin-transfer torque magnetic random access memory (STT-MRAM). ACM Journal on Emerging Technologies in Computing Systems, 2013, 9(2): Article No. 13. DOI: 10.1145/2463585.2463589.
Crossref Google Scholar
[14]

Yang J J, Williams R S. Memristive devices in computing system: Promises and challenges. ACM Journal on Emerging Technologies in Computing Systems, 2013, 9(2): Article No. 11. DOI: 10.1145/2463585.2463587.
Crossref Google Scholar
[15]
Zuo P, Hua Y, Zhao M, Zhou W, Guo Y. Improving the performance and endurance of encrypted non-volatile main memory through deduplicating writes. In Proc. the 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct. 2018, pp.442-454. DOI: 10.1109/MI-CRO.2018.00043.
Crossref
[16]

Rudoff A. Persistent memory programming. Login, 2017, 42(2): 34-40.
Crossref Google Scholar
[17]
Xu J, Swanson S. NOVA: A log-structured file system for hybrid volatile/non-volatile main memories. In Proc. the 14th USENIX Conference on File and Storage Technologies, Feb. 2016, pp.323-338.
[18]
Rao D S, Kumar S, Keshavamurthy A, Lantz P, Reddy D, Sankaran R, Jackson J. System software for persistent memory. In Proc. the 9th European Conference on Computer Systems, Apr. 2014, Article No. 15. DOI: 10.1145/2592798.2592814.
Crossref
[19]
Dong M, Chen H. Soft updates made simple and fast on non-volatile memory. In Proc. the 2017 USENIX Annual Technical Conference, Jul. 2017, pp.719-731.
[20]
Kwon Y, Fingler H, Hunt T, Peter S, Witchel E, Anderson T. Strata: A cross media file system. In Proc. the 26th Symposium on Operating Systems Principles, Oct. 2017, pp.460-477. DOI: 10.1145/3132747.3132770.
Crossref
[21]
Volos H, Nalli S, Panneerselvam S, Varadarajan V, Saxena P, Swift M M. Aerie: Flexible file-system interfaces to storage-class memory. In Proc. the 9th European Conference on Computer Systems, Apr. 2014, Article No. 14. DOI: 10.1145/2592798.2592810.
Crossref
[22]
Dong M, Bu H, Yi J, Dong B, Chen H. Performance and protection in the ZoFS user-space NVM file system. In Proc. the 27th ACM Symposium on Operating Systems Principles, Oct. 2019, pp.478-493. DOI: 10.1145/3341301.3359637.
Crossref
[23]

Bhandari K, Chakrabarti D R, Boehm H J. Makalu: Fast recoverable allocation of non-volatile memory. ACM SIGPLAN Notices, 2016, 51(10): 677-694. DOI: 10.1145/3022671.2984019.
Crossref Google Scholar
[24]

Flajolet P, Poblete P, Viola A. On the analysis of linear probing hashing. Algorithmica, 1998, 22(4): 490-515. DOI: 10.1007/PL00009236.
Crossref Google Scholar
[25]

Pagh R, Rodler F F. Cuckoo hashing. Journal of Algorithms, 2004, 51(2): 122-144. DOI: 10.1016/j.jalgor.20-03.12.002.
Crossref Google Scholar
[26]
Ellis C S. Extendible hashing for concurrent operations and distributed data. In Proc. the 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 1983, pp.106-116. DOI: 10.1145/588058.588072.
Crossref
[27]
Oukid I, Lasperas J, Nica A, Willhalm T, Lehner W. FP-Tree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In Proc. the 2016 International Conference on Management of Data, June 2016, pp.371-386. DOI: 10.1145/2882903.2915251.
Crossref
[28]

Sha E H M, Jiang W, Dong H, Ma Z, Zhang R, Chen X, Zhuge Q. Towards the design of efficient and consistent index structure with minimal write activities for non-volatile memory. IEEE Transactions on Computers, 2017, 67(3): 432-448. DOI: 10.1109/TC.2017.2754381.
Crossref Google Scholar
[29]
Volos H, Magalhaes G, Cherkasova L, Li J. Quartz: A lightweight performance emulator for persistent memory software. In Proc. the 16th Annual Middleware Conference, Nov. 2015, pp.37-49. DOI: 10.1145/2814576.2814806.
Crossref
[30]
Leis V, Kemper A, Neumann T. The adaptive radix tree: ARTful indexing for main-memory databases. In Proc. the 29th International Conference on Data Engineering, April 2013, pp.38-49. DOI: 10.1109/ICDE.2013.6544812.
Crossref
[31]
Evans J. A scalable concurrent malloc (3) implementation for FreeBSD. In Proc. the 2006 BSDCan Conference, May 2006.
[32]
Viswanathan K. Intel corporation. Intel memory latency checker v3.7. https://software.intel.com/en-us/articles/int-elr-memory-latency-checker, Feb. 2020.
[33]
Izraelevitz J, Yang J, Zhang L et al. Basic performance measurements of the Intel Optane DC persistent memory module. arXiv: 1903.05714, 2019. https://ar-xiv.org/pdf/1903.05714v3.pdf, Oct. 2020.
Journal of Computer Science and Technology
Volume 36 Issue 1,
January 2021
Pages 140-157
DOI: 10.1007/s11390-020-9871-0
Cite this article:
Bu H, Dong M-K, Yi J-F, et al. Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory. Journal of Computer Science and Technology, 2021, 36(1): 140-157. https://doi.org/10.1007/s11390-020-9871-0

416

Views

3

Crossref

2

Web of Science

5

Scopus

0

CSCD

Altmetrics
Received: 21 July 2019
Accepted: 15 February 2020
Published: 05 January 2021
© Institute of Computing Technology, Chinese Academy of Sciences 2021
Return