{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:14Z","timestamp":1750306034459,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T00:00:00Z","timestamp":1519603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>\n            Byte-addressable non-volatile memory (NVM) is going to reshape conventional computer systems. With advantages of low latency, byte-addressability, and non-volatility, NVM can be directly put on the memory bus to replace DRAM. As a result, both system and application softwares have to be adjusted to perceive the fact that the persistent layer moves up to the memory. However, most of the current in-memory data structures will be problematic with consistency issues if not well tuned with NVM. This article places emphasis on an important in-memory structure that is widely used in computer systems, i.e., the Red\/Black-tree (RB-tree). Since it has a long and complicated update process, the RB-tree is prone to inconsistency problems with NVM. This article presents an NVM-compatible consistent RB-tree with a new technique named\n            <jats:italic>cascade-versioning<\/jats:italic>\n            . The proposed RB-tree (i) is all-time consistent and scalable and (ii) needs no recovery procedure after system crashes. Experiment results show that the RB-tree for NVM not only achieves the aim of consistency with insignificant spatial overhead but also yields comparable performance to an ordinary volatile RB-tree.\n          <\/jats:p>","DOI":"10.1145\/3177915","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T18:25:15Z","timestamp":1519669515000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Persisting RB-Tree into NVM in a Consistency Perspective"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9069-2650","authenticated-orcid":false,"given":"Chundong","family":"Wang","sequence":"first","affiliation":[{"name":"Singapore University of Technology and Design and Data Storage Institute, A*STAR"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingsong","family":"Wei","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR, Fusionopolis Way, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lingkun","family":"Wu","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR, Fusionopolis Way, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of Queensland and Nanyang Technological University, Brisbane, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Chen","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR and National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR, Fusionopolis Way, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingdi","family":"Xue","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR, Fusionopolis Way, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yechao","family":"Yang","sequence":"additional","affiliation":[{"name":"Data Storage Institute, A*STAR, Fusionopolis Way, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699831"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2905364"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2016.7897077"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950380"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629589"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630086"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1870926.1871147"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089733.1089735"},{"key":"e_1_2_1_12_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2006","unstructured":"John L. Hennessy and David A . Patterson . 2006 . Computer Architecture, Fourth Edition : A Quantitative Approach. Morgan Kaufmann , San Francisco, CA. John L. Hennessy and David A. Patterson. 2006. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_13_1","first-page":"4","article-title":"Low overhead software wear leveling for hybrid PCM + DRAM main memory on embedded systems","volume":"23","author":"Hu J.","year":"2015","unstructured":"J. Hu , M. Xie , C. Pan , C. J. Xue , Q. Zhuge , and E. H. M. Sha . 2015 . Low overhead software wear leveling for hybrid PCM + DRAM main memory on embedded systems . IEEE Trans. VLSI Syst. 23 , 4 (April 2015), 654--663. J. Hu, M. Xie, C. Pan, C. J. Xue, Q. Zhuge, and E. H. M. Sha. 2015. Low overhead software wear leveling for hybrid PCM + DRAM main memory on embedded systems. IEEE Trans. VLSI Syst. 23, 4 (April 2015), 654--663.","journal-title":"IEEE Trans. VLSI Syst."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555758"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC\u201913)","author":"Liu Duo","year":"2013","unstructured":"Duo Liu , Tianzheng Wang , Yi Wang , Zili Shao , Qingfeng Zhuge , and Edwin Sha . 2013 . Curling-PCM: Application-specific wear leveling for phase change memory based embedded systems . In Proceedings of the 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC\u201913) . IEEE Computer Society, Washington, DC, 279--284. Duo Liu, Tianzheng Wang, Yi Wang, Zili Shao, Qingfeng Zhuge, and Edwin Sha. 2013. Curling-PCM: Application-specific wear leveling for phase change memory based embedded systems. In Proceedings of the 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC\u201913). IEEE Computer Society, Washington, DC, 279--284."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898106"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.462.0187"},{"key":"e_1_2_1_19_1","unstructured":"Micron and Intel. 2015. 3D XPoint Technology. Retrieved from http:\/\/www.micron.com\/about\/innovations\/3d-xpoint-technology. (2015).  Micron and Intel. 2015. 3D XPoint Technology. Retrieved from http:\/\/www.micron.com\/about\/innovations\/3d-xpoint-technology. (2015)."},{"volume-title":"Proceedings of the IEEE International Electron Devices Meeting (IEDM\u201905)","author":"Mueller W.","key":"e_1_2_1_21_1","unstructured":"W. Mueller , G. Aichmayr , W. Bergner , E. Erben , T. Hecht , C. Kapteyn , A. Kersch , S. Kudelka , F. Lau , J. Luetzen , A. Orth , J. Nuetzel , T. Schloesser , A. Scholz , U. Schroeder , A. Sieck , A. Spitzer , M. Strasser , P. F. Wang , S. Wege , and R. Weis . 2005. Challenges for the DRAM cell scaling to 40nm . In Proceedings of the IEEE International Electron Devices Meeting (IEDM\u201905) . IEEE, New York, NY. 339. W. Mueller, G. Aichmayr, W. Bergner, E. Erben, T. Hecht, C. Kapteyn, A. Kersch, S. Kudelka, F. Lau, J. Luetzen, A. Orth, J. Nuetzel, T. Schloesser, A. Scholz, U. Schroeder, A. Sieck, A. Spitzer, M. Strasser, P. F. Wang, S. Wege, and R. Weis. 2005. Challenges for the DRAM cell scaling to 40nm. In Proceedings of the IEEE International Electron Devices Meeting (IEDM\u201905). IEEE, New York, NY. 339."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037730"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151018"},{"volume-title":"Proceeding of the 41st Annual International Symposium on Computer Architecuture (ISCA\u201914)","author":"Pelley Steven","key":"e_1_2_1_24_1","unstructured":"Steven Pelley , Peter M. Chen , and Thomas F. Wenisch . 2014. Memory persistency . In Proceeding of the 41st Annual International Symposium on Computer Architecuture (ISCA\u201914) . IEEE Press, Piscataway, NJ, 265--276. Steven Pelley, Peter M. Chen, and Thomas F. Wenisch. 2014. Memory persistency. In Proceeding of the 41st Annual International Symposium on Computer Architecuture (ISCA\u201914). IEEE Press, Piscataway, NJ, 265--276."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855752"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2479605"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669117"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555760"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2155620.2155659"},{"key":"e_1_2_1_30_1","unstructured":"Viking Technology. 2015. ArxCis-NV DIMM. Retrieved from http:\/\/www.vikingtechnology.com\/arxcis-nv.  Viking Technology. 2015. ArxCis-NV DIMM. Retrieved from http:\/\/www.vikingtechnology.com\/arxcis-nv."},{"volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201911)","author":"Venkataraman Shivaram","key":"e_1_2_1_31_1","unstructured":"Shivaram Venkataraman , Niraj Tolia , Parthasarathy Ranganathan , and Roy H. Campbell . 2011. Consistent and durable data structures for non-volatile byte-addressable memory . In Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201911) . USENIX, Berkeley, CA, USA, 61--75. Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and durable data structures for non-volatile byte-addressable memory. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201911). USENIX, Berkeley, CA, USA, 61--75."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814576.2814806"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950379"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2697394"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766453"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126940"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/195473.195506"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063436"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488867"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Yang Jun","year":"2015","unstructured":"Jun Yang , Qingsong Wei , Cheng Chen , Chundong Wang , Khai Leong Yong , and Bingsheng He . 2015 . NV-Tree: Reducing consistency cost for NVM-based single level systems . In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915) . USENIX Association, Berkeley, CA, 167--181. Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. 2015. NV-Tree: Reducing consistency cost for NVM-based single level systems. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915). USENIX Association, Berkeley, CA, 167--181."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2014.6974656"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3177915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,26]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3177915"],"URL":"https:\/\/doi.org\/10.1145\/3177915","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2018,2,26]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}