Uma Revisão Sistemática sobre Estruturas de Dados em Dispositivos Persistentes Contemporâneos
Resumo
Memória persistente (PM) é uma tecnologia emergente que combina o acesso rápido aos dados com endereçamento por byte, além de oferecer grande capacidade de armazenamento persistente. Devido a essas características, a PM tem ganhado cada vez mais atenção, com diversos estudos sendo realizados para explorar seu uso e desempenho. Paralelamente, trabalhos sobre estruturas de dados (ED) têm evoluído para maximizar o aproveitamento das PMs. Isso inclui o desenvolvimento de EDs adaptadas para a persistência e transações atômicas. Este artigo revisa os trabalhos mais relevantes na área de memória persistente com foco em estruturas de dados, destacando aqueles que desenvolvem ou adaptam tais estruturas para uso na PM. Nossos estudos identificaram as principais características necessárias para o desenvolvimento de uma estrutura de dados voltada para PM, visando aprimorar o desempenho ao reduzir o número de operações de escrita por meio de otimizações de código e do uso de memória DRAM como cache. Além disso, enfatizamos a importância da garantia de persistência, uma vez que a memória persistente mantém os dados mesmo após o desligamento do sistema.Referências
BALDASSIN, A., BARRETO, J., CASTRO, D., AND ROMANO, P. Persistent memory: A survey of programming support and implementations. ACM Comput. Surv. 54, 7 (July 2021).
COHEN, N., AKSUN, D. T., AVNI, H., AND LARUS, J. R. Fine-grain checkpointing with in-cache-line logging. In Proceedings of the 24th ASPLOS (2019), p. 441–454.
DESNOYERS, P., ADAMS, I., ESTRO, T., GANDHI, A., KUENNING, G., MESNIER, M., WALDSPURGER, C., WILDANI, A., AND ZADOK, E. Persistent memory research in the post-Optane era. In Proceedings of the 1st DIMES (2023), p. 23–30.
DHULIPALA, L., MCGUFFEY, C., KANG, H., GU, Y., BLELLOCH, G. E., GIBBONS, P. B., AND SHUN, J. Sage: Parallel semi-asymmetric graph algorithms for NVRAMs. Proceedings of the VLDB Endowment 13, 9 (2020), 1598 – 1613.
DUAN, Z., YAO, J., LIU, H., LIAO, X., JIN, H., AND ZHANG, Y. Revisiting log-structured merging for kv stores in hybrid memory systems. In Proceedings of the 28th ASPLOS (2023), p. 674–687.
FRIEDMAN, M., HERLIHY, M., MARATHE, V., AND PETRANK, E. A persistent lock-free queue for non-volatile memory. In Proceedings of the 23rd PPoPP (2018), p. 28–40.
GRAY, J., AND REUTER, A. Transaction Processing: Concepts and Techniques, 1st ed. Morgan Kaufmann, 1992.
HENNESSY, J. L., AND PATTERSON, D. A. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann, Nov. 2017.
HU, J., CHEN, J., ZHU, Y., YANG, Q., PENG, Z., AND YU, Y. Parallel multi-split extendible hashing for persistent memory. In Proceedings of the 50th ICPP (2021).
HUANG, K., YAN, Y., AND HUANG, L. Revisiting persistent hash table design for commercial non-volatile memory. Proceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020 (2020), 708 – 713.
IZADPANAH, R., PETERSON, C., SOLIHIN, Y., AND DECHEV, D. Petra: Persistent transactional non-blocking linked data structures. ACM Transactions on Architecture and Code Optimization 18, 2 (2021).
JAMIL, S., KHAN, A., BURASTALLER, B., AND KIM, Y. Towards scalable manycore-aware persistent b+- trees for efficient indexing in cloud environments. In 2021 ACSOS-C (2021), pp. 44–49.
KITCHENHAM, B. Procedures for performing systematic reviews. Keele, UK, Keele Univ. 33 (08 2004).
LAMAR, K., PETERSON, C., DECHEV, D., PEARCE, R., IWABUCHI, K., AND PIRKEL-BAUER, P. PMap: A non-volatile lock-free hash map with open addressing. In 2021 NVMSA (2021), pp. 1–7.
LAVINSKY, B., AND ZHANG, X. PM-Rtree: A highly-efficient crash-consistent r-tree for persistent memory. Proceedings of the 34th International Conference on Scientific and Statistical Database Management (2022).
LI, Y., ZENG, L., CHEN, G., GU, C., LUO, F., DING, W., SHI, Z., AND FUENTES, J. A multi-hashing index for hybrid dram-nvm memory systems. Journal of Systems Architecture 128 (2022).
LIM, S., COY, T., LU, Z., REN, B., AND ZHANG, X. NVGraph: Enforcing crash consistency of evolving network analytics in nvmm systems. IEEE Transactions on Parallel and Distributed Systems 31, 6 (2020), 1255 – 1269.
NGUYEN, B., TAN, H., DAVIS, K., AND ZHANG, X. Persistent octrees for parallel mesh refinement through non-volatile byte-addressable memory. IEEE Transactions on Parallel and Distributed Systems 30, 3 (2019), 677 – 691.
OH, H., CHO, B., KIM, C., PARK, H., AND SEO, J. Anifilter: Parallel and failure-atomic cuckoo filter for non-volatile memories. Proceedings of the 15th European Conference on Computer Systems, EuroSys 2020 (2020).
PAN, W., XIE, T., AND SONG, X. Hart: A concurrent hash-assisted radix tree for dram-pm hybrid memory systems. Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019 (2019), 921 – 931.
SRIVASTAVA, A., AND BROWN, T. Elimination (a,b)-trees with fast, durable updates. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP (2022), 416 – 430.
WANG, C., WEI, Q., WU, L., WANG, S., CHEN, C., XIAO, X., YANG, J., XUE, M., AND YANG, Y. Persisting rb-tree into nvm in a consistency perspective. ACM Transactions on Storage 14, 1 (2018).
WANG, H., LI, Z., ZHANG, X., ZHAO, X., AND JIANG, S. Wobtree: a write-optimized b+-tree for non-volatile memory. Frontiers of Computer Science 15, 5 (2021).
YAO, Z., ZHANG, J., AND FENG, J. NV-QALSH: An NVM-optimized implementation of query-aware locality-sensitive hashing. Lecture Notes in Computer Science 12924 LNCS (2021), 58 – 69.
YU, S., XIAO, N., DENG, M., XING, Y., LIU, F., AND CHEN, W. Rio: Fast b+-tree based on remote accessible non-volatile memory. In 2017 IEEE ISPA/IUCC (2017), pp. 494–496.
ZHANG, B., ZHENG, S., QI, Z., AND HUANG, L. Nbtree: a lock-free pm-friendly persistent b+-tree for eadr-enabled pm systems. Contemporary Mathematics 15, 6 (2022), 1187 – 1200.
ZHANG, X., FENG, D., HUA, Y., CHEN, J., AND FU, M. A write-efficient and consistent hashing scheme for non-volatile memory. ACM International Conference Proceeding Series (2018).
ZHONG, C., CHALLA, P., ZHAO, X., AND JIANG, S. Buffered hash table: Leveraging dram to enhance hash indexes in the persistent memory. Proceedings - 2022 IEEE 11th Non-Volatile Memory Systems and Applications Symposium, NVMSA 2022 (2022), 8 – 13.
ZHU, J., HUANG, K., ZOU, X., HUANG, C., XU, N., AND FANG, L. Hdnh: A read-efficient and write-optimized hashing scheme for hybrid dram-nvm memory. ACM International Conference Proceeding Series (2021).
ZUO, P., AND HUA, Y. A write-friendly and cache-optimized hashing scheme for non-volatile memory systems. IEEE Transactions on Parallel and Distributed Systems 29, 5 (2018), 985 – 996.
COHEN, N., AKSUN, D. T., AVNI, H., AND LARUS, J. R. Fine-grain checkpointing with in-cache-line logging. In Proceedings of the 24th ASPLOS (2019), p. 441–454.
DESNOYERS, P., ADAMS, I., ESTRO, T., GANDHI, A., KUENNING, G., MESNIER, M., WALDSPURGER, C., WILDANI, A., AND ZADOK, E. Persistent memory research in the post-Optane era. In Proceedings of the 1st DIMES (2023), p. 23–30.
DHULIPALA, L., MCGUFFEY, C., KANG, H., GU, Y., BLELLOCH, G. E., GIBBONS, P. B., AND SHUN, J. Sage: Parallel semi-asymmetric graph algorithms for NVRAMs. Proceedings of the VLDB Endowment 13, 9 (2020), 1598 – 1613.
DUAN, Z., YAO, J., LIU, H., LIAO, X., JIN, H., AND ZHANG, Y. Revisiting log-structured merging for kv stores in hybrid memory systems. In Proceedings of the 28th ASPLOS (2023), p. 674–687.
FRIEDMAN, M., HERLIHY, M., MARATHE, V., AND PETRANK, E. A persistent lock-free queue for non-volatile memory. In Proceedings of the 23rd PPoPP (2018), p. 28–40.
GRAY, J., AND REUTER, A. Transaction Processing: Concepts and Techniques, 1st ed. Morgan Kaufmann, 1992.
HENNESSY, J. L., AND PATTERSON, D. A. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann, Nov. 2017.
HU, J., CHEN, J., ZHU, Y., YANG, Q., PENG, Z., AND YU, Y. Parallel multi-split extendible hashing for persistent memory. In Proceedings of the 50th ICPP (2021).
HUANG, K., YAN, Y., AND HUANG, L. Revisiting persistent hash table design for commercial non-volatile memory. Proceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020 (2020), 708 – 713.
IZADPANAH, R., PETERSON, C., SOLIHIN, Y., AND DECHEV, D. Petra: Persistent transactional non-blocking linked data structures. ACM Transactions on Architecture and Code Optimization 18, 2 (2021).
JAMIL, S., KHAN, A., BURASTALLER, B., AND KIM, Y. Towards scalable manycore-aware persistent b+- trees for efficient indexing in cloud environments. In 2021 ACSOS-C (2021), pp. 44–49.
KITCHENHAM, B. Procedures for performing systematic reviews. Keele, UK, Keele Univ. 33 (08 2004).
LAMAR, K., PETERSON, C., DECHEV, D., PEARCE, R., IWABUCHI, K., AND PIRKEL-BAUER, P. PMap: A non-volatile lock-free hash map with open addressing. In 2021 NVMSA (2021), pp. 1–7.
LAVINSKY, B., AND ZHANG, X. PM-Rtree: A highly-efficient crash-consistent r-tree for persistent memory. Proceedings of the 34th International Conference on Scientific and Statistical Database Management (2022).
LI, Y., ZENG, L., CHEN, G., GU, C., LUO, F., DING, W., SHI, Z., AND FUENTES, J. A multi-hashing index for hybrid dram-nvm memory systems. Journal of Systems Architecture 128 (2022).
LIM, S., COY, T., LU, Z., REN, B., AND ZHANG, X. NVGraph: Enforcing crash consistency of evolving network analytics in nvmm systems. IEEE Transactions on Parallel and Distributed Systems 31, 6 (2020), 1255 – 1269.
NGUYEN, B., TAN, H., DAVIS, K., AND ZHANG, X. Persistent octrees for parallel mesh refinement through non-volatile byte-addressable memory. IEEE Transactions on Parallel and Distributed Systems 30, 3 (2019), 677 – 691.
OH, H., CHO, B., KIM, C., PARK, H., AND SEO, J. Anifilter: Parallel and failure-atomic cuckoo filter for non-volatile memories. Proceedings of the 15th European Conference on Computer Systems, EuroSys 2020 (2020).
PAN, W., XIE, T., AND SONG, X. Hart: A concurrent hash-assisted radix tree for dram-pm hybrid memory systems. Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019 (2019), 921 – 931.
SRIVASTAVA, A., AND BROWN, T. Elimination (a,b)-trees with fast, durable updates. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP (2022), 416 – 430.
WANG, C., WEI, Q., WU, L., WANG, S., CHEN, C., XIAO, X., YANG, J., XUE, M., AND YANG, Y. Persisting rb-tree into nvm in a consistency perspective. ACM Transactions on Storage 14, 1 (2018).
WANG, H., LI, Z., ZHANG, X., ZHAO, X., AND JIANG, S. Wobtree: a write-optimized b+-tree for non-volatile memory. Frontiers of Computer Science 15, 5 (2021).
YAO, Z., ZHANG, J., AND FENG, J. NV-QALSH: An NVM-optimized implementation of query-aware locality-sensitive hashing. Lecture Notes in Computer Science 12924 LNCS (2021), 58 – 69.
YU, S., XIAO, N., DENG, M., XING, Y., LIU, F., AND CHEN, W. Rio: Fast b+-tree based on remote accessible non-volatile memory. In 2017 IEEE ISPA/IUCC (2017), pp. 494–496.
ZHANG, B., ZHENG, S., QI, Z., AND HUANG, L. Nbtree: a lock-free pm-friendly persistent b+-tree for eadr-enabled pm systems. Contemporary Mathematics 15, 6 (2022), 1187 – 1200.
ZHANG, X., FENG, D., HUA, Y., CHEN, J., AND FU, M. A write-efficient and consistent hashing scheme for non-volatile memory. ACM International Conference Proceeding Series (2018).
ZHONG, C., CHALLA, P., ZHAO, X., AND JIANG, S. Buffered hash table: Leveraging dram to enhance hash indexes in the persistent memory. Proceedings - 2022 IEEE 11th Non-Volatile Memory Systems and Applications Symposium, NVMSA 2022 (2022), 8 – 13.
ZHU, J., HUANG, K., ZOU, X., HUANG, C., XU, N., AND FANG, L. Hdnh: A read-efficient and write-optimized hashing scheme for hybrid dram-nvm memory. ACM International Conference Proceeding Series (2021).
ZUO, P., AND HUA, Y. A write-friendly and cache-optimized hashing scheme for non-volatile memory systems. IEEE Transactions on Parallel and Distributed Systems 29, 5 (2018), 985 – 996.
Publicado
23/10/2024
Como Citar
SPAGNOL, Lucas; HONORIO, Bruno; BALDASSIN, Alexandro; FRANCESQUINI, Emilio.
Uma Revisão Sistemática sobre Estruturas de Dados em Dispositivos Persistentes Contemporâneos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 25. , 2024, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 109-120.
DOI: https://doi.org/10.5753/sscad.2024.244737.
