Survey–Data Structure on PM | My Note

Survey--Data Structure on PM

Updated: Aug 12th, 2021

在Persistent Memory之上设计持久数据结构需要考虑更多额外的因素，在近些年的计算机系统顶级会议中，从“单个数据结构本身在PM上的设计”到“将普通的数据结构转换成PM上的数据结构”均有大量的文章出来。本文对这些工作进行了整理，并看作者心情，对这些文章进行简短的分析。

本文工作主要分为这几类，另外考虑到2019年的时候真实的PM（傲腾持久内存，简称DCPMM)才正式开放售卖，因此这些文章都会标注（在模拟器上测试or在DCPMM上测试）：

  1. 在PM上设计实现哈希表（无序索引）。
  2. 在PM上设计实现树等支持扫描的数据结构（有序索引）。
  3. 将普通的数据结构（或索引数据结构）转换成持久数据结构。
  4. 其他。
    1. 测试类

在PM上设计实现哈希表

以2019年为分界线，2019年是在模拟PM上做的，2019年之后是在真实PM上做的。

哈希表 MSST’17: Path-Hashing[1]

OSDI’18: Level-Hashing[2]

FAST’19: CCEH[3]

VLDB’20: Dash[4]

MSST’20: HMEH[5]

USENIX ATC’20: CLevel[6]

在PM上设计实现有序索引

B/B+-Tree

FAST’11: CDDSs[7]

VLDB’15: wB+-Tree[8]

FAST’15: NV-Tree[9]

SIGMOD’16: FPTree[10]

VLDB’18: Bztree[11]

ICDE’18: Bw-Tree[12]

VLDB’20: uTree[13]

VLDB’20: LB+Tree[14]

Radix Tree

FAST’17: WORT: [15]

IPDPS’19: HART[16]

FAST’21: ROART[17]

未知： PACTree: A High Performance Persistent Range Index Using PAC Guidelines Wook-Hee Kim, R. Madhava Krishnan, Xinwei Fu, Sanidhya Kashyap, and Changwoo Min
In Proceedings of ACM Symposium on Operating Systems Principles (SOSP 2021)

数据结构的转换

USENIX ATC’18:Log-Free Concurrent Data Structures [18]

SOSP’19: RECIPE[19]

ASPLOS’20: Pronto[20]

ASPLOS’20: MOD[21]

PLDI’20 NVTraverse:[22]

OSDI’21: Nap[23]

USENIX’21: TIPS[24]

其他

测试类

索引数据结构的测试

VLDB’19: [25]

VLDB’21: [26]

相关文献

[1]
P. Zuo and Y. Hua, “A Write-friendly Hashing Scheme for Non-volatile Memory Systems,” 2017, p. 10.
[2]
P. Zuo, Y. Hua, and J. Wu, “Write-optimized and high-performance hashing index scheme for persistent memory,” in Proceedings of the 13th USENIX conference on Operating Systems Design and Implementation, Carlsbad, CA, USA, 2018, pp. 461–476.
[3]
M. Nam, H. Cha, Y.-R. Choi, S. H. Noh, and B. Nam, “Write-optimized dynamic hashing for persistent memory,” in Proceedings of the 17th USENIX Conference on File and Storage Technologies, Boston, MA, USA, 2019, pp. 31–44.
[4]
B. Lu, X. Hao, T. Wang, and E. Lo, “Dash: scalable hashing on persistent memory,” Proc. VLDB Endow., vol. 13, no. 8, pp. 1147–1161, Apr. 2020, doi: 10.14778/3389133.3389134. [Online]. Available: https://doi.org/10.14778/3389133.3389134. [Accessed: 30-Jul-2020]
[5]
X. Zou et al., “HMEH: write-optimal extendible hashing for hybrid DRAM-NVM memory,” 2020, p. 11.
[6]
Z. Chen, Y. Hua, B. Ding, and P. Zuo, “Lock-free Concurrent Level Hashing for Persistent Memory,” 2020, pp. 799–812 [Online]. Available: https://www.usenix.org/conference/atc20/presentation/chen. [Accessed: 27-Jul-2020]
[7]
S. Venkataraman, N. Tolia, P. Ranganathan, and R. H. Campbell, “Consistent and durable data structures for non-volatile byte-addressable memory,” in Proceedings of the 9th USENIX conference on File and stroage technologies, USA, 2011, p. 5.
[8]
S. Chen and Q. Jin, “Persistent B+-trees in non-volatile main memory,” Proc. VLDB Endow., vol. 8, no. 7, pp. 786–797, Feb. 2015, doi: 10.14778/2752939.2752947. [Online]. Available: https://doi.org/10.14778/2752939.2752947. [Accessed: 19-Dec-2020]
[9]
J. Yang, Q. Wei, C. Chen, C. Wang, K. L. Yong, and B. He, “NV-Tree: reducing consistency cost for NVM-based single level systems,” in Proceedings of the 13th USENIX Conference on File and Storage Technologies, USA, 2015, pp. 167–181.
[10]
I. Oukid, J. Lasperas, A. Nica, T. Willhalm, and W. Lehner, “FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory,” in Proceedings of the 2016 International Conference on Management of Data, New York, NY, USA, 2016, pp. 371–386, doi: 10.1145/2882903.2915251 [Online]. Available: https://doi.org/10.1145/2882903.2915251. [Accessed: 12-Aug-2020]
[11]
J. Arulraj, J. Levandoski, U. F. Minhas, and P.-A. Larson, “Bztree: a high-performance latch-free range index for non-volatile memory,” Proc. VLDB Endow., vol. 11, no. 5, pp. 553–565, Jan. 2018, doi: 10.1145/3164135.3164147. [Online]. Available: https://doi.org/10.1145/3164135.3164147. [Accessed: 22-Feb-2021]
[12]
T. Wang, J. Levandoski, and P. Larson, “Easy Lock-Free Indexing in Non-Volatile Memory,” in 2018 IEEE 34th International Conference on Data Engineering (ICDE), 2018, pp. 461–472, doi: 10.1109/ICDE.2018.00049.
[13]
Y. Chen, Y. Lu, K. Fang, Q. Wang, and J. Shu, “uTree: a persistent B+-tree with low tail latency,” Proc. VLDB Endow., vol. 13, no. 12, pp. 2634–2648, Jul. 2020, doi: 10.14778/3407790.3407850. [Online]. Available: https://doi.org/10.14778/3407790.3407850. [Accessed: 06-Apr-2021]
[14]
J. Liu, S. Chen, and L. Wang, “LB+Trees: optimizing persistent index performance on 3DXPoint memory,” Proc. VLDB Endow., vol. 13, no. 7, pp. 1078–1090, Mar. 2020, doi: 10.14778/3384345.3384355. [Online]. Available: https://doi.org/10.14778/3384345.3384355. [Accessed: 19-Oct-2020]
[15]
S. K. Lee, K. H. Lim, H. Song, B. Nam, and S. H. Noh, “WORT: write optimal radix tree for persistent memory storage systems,” in Proceedings of the 15th Usenix Conference on File and Storage Technologies, USA, 2017, pp. 257–270.
[16]
W. Pan, T. Xie, and X. Song, “HART: A Concurrent Hash-Assisted Radix Tree for DRAM-PM Hybrid Memory Systems,” in 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019, pp. 921–931, doi: 10.1109/IPDPS.2019.00100.
[17]
S. Ma et al., “{ROART}: Range-query Optimized Persistent {ART},” 2021, pp. 1–16 [Online]. Available: https://www.usenix.org/conference/fast21/presentation/ma. [Accessed: 24-Feb-2021]
[18]
T. David, A. Dragojević, R. Guerraoui, and I. Zablotchi, “Log-free concurrent data structures,” in Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference, USA, 2018, pp. 373–385.
[19]
S. K. Lee, J. Mohan, S. Kashyap, T. Kim, and V. Chidambaram, “Recipe: converting concurrent DRAM indexes to persistent-memory indexes,” in Proceedings of the 27th ACM Symposium on Operating Systems Principles, Huntsville, Ontario, Canada, 2019, pp. 462–477, doi: 10.1145/3341301.3359635 [Online]. Available: https://doi.org/10.1145/3341301.3359635. [Accessed: 26-Jul-2020]
[20]
A. Memaripour, J. Izraelevitz, and S. Swanson, “Pronto: Easy and Fast Persistence for Volatile Data Structures,” in Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, New York, NY, USA, 2020, pp. 789–806, doi: 10.1145/3373376.3378456 [Online]. Available: https://doi.org/10.1145/3373376.3378456. [Accessed: 13-Aug-2020]
[21]
S. Haria, M. D. Hill, and M. M. Swift, “MOD: Minimally Ordered Durable Datastructures for Persistent Memory,” in Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, Lausanne, Switzerland, 2020, pp. 775–788, doi: 10.1145/3373376.3378472 [Online]. Available: https://doi.org/10.1145/3373376.3378472. [Accessed: 04-May-2020]
[22]
M. Friedman, N. Ben-David, Y. Wei, G. E. Blelloch, and E. Petrank, “NVTraverse: in NVRAM data structures, the destination is more important than the journey,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, New York, NY, USA, 2020, pp. 377–392, doi: 10.1145/3385412.3386031 [Online]. Available: https://doi.org/10.1145/3385412.3386031. [Accessed: 12-Aug-2021]
[23]
Q. Wang, Y. Lu, J. Li, and J. Shu, “Nap: A Black-Box Approach to NUMA-Aware Persistent Memory Indexes,” 2021, pp. 93–111 [Online]. Available: https://www.usenix.org/conference/osdi21/presentation/wang-qing. [Accessed: 23-Jul-2021]
[24]
R. M. Krishnan et al., “{TIPS}: Making Volatile Index Structures Persistent with DRAM-NVMM Tiering,” 2021, pp. 773–787 [Online]. Available: https://www.usenix.org/conference/atc21/presentation/krishnan. [Accessed: 12-Aug-2021]
[25]
L. Lersch, X. Hao, I. Oukid, T. Wang, and T. Willhalm, “Evaluating persistent memory range indexes,” Proc. VLDB Endow., vol. 13, no. 4, pp. 574–587, Dec. 2019, doi: 10.14778/3372716.3372728. [Online]. Available: https://doi.org/10.14778/3372716.3372728. [Accessed: 28-Jan-2021]
[26]
D. Hu, Z. Chen, J. Wu, J. Sun, and H. Chen, “Persistent Memory Hash Indexes: An Experimental Evaluation,” Proc. VLDB Endow., 2021.

Notes mentioning this note

There are no notes linking to this note.