PARALLEL PROCESSING IN DYNAMIC HASH STRUCTURES AND MODELING THEIR PERFORMANCE
DOI:
https://doi.org/10.28925/2663-4023.2025.31.1015Keywords:
extendible hashing, parallel data processing, dynamic directory, concurrent access, verification mechanism, simulation modeling, transaction blocking, operational databases, high-performance databases, scalabilityAbstract
This paper presents a new algorithm for concurrent access to extendible hashing with cautious waiting (Extendible Hashing with Cautious Waiting, EHCW), which combines two-phase locking and optimistic verification mechanisms to reduce overhead under high load. The proposed approach ensures data consistency during parallel access to dynamic hash structures without the need for full locking, addressing the challenge of efficient synchronized access under high parallelism. The algorithm enables adaptive reconfiguration of the directory structure, enhancing scalability and performance under varying loads. To evaluate the effectiveness, a simulation model of the system's operation in an environment with limited computational resources (single-core processor and disk) and a memory page buffer pool for simulating page splitting operations and dynamic directory restructuring was implemented. The developed simulation model demonstrated that the proposed algorithm outperforms traditional static hashing schemes in terms of throughput and blocking frequency, making it promising for use in operational databases, cloud computing environments, and distributed information systems, where ensuring high performance and data integrity under high transactional loads is crucial. The task of high-performance data processing with dynamic hash structures is important for scalable systems, particularly for databases and cloud computing, where providing fast parallel data access is critical.
Downloads
References
Li, W., Cheng, Z., Chen, Y., Li, A., & Deng, L. (2023). Lock-free bucketized cuckoo hashing. In J. Cano, M. D. Dikaiakos, G. A. Papadopoulos, M. Pericàs, & R. Sakellariou (Eds.), Euro-Par 2023: Parallel Processing (Lecture Notes in Computer Science, Vol. 14100, pp. 290–305). Springer. https://doi.org/10.1007/978-3-031-39698-4_19
Ren, Z., Gu, Y., Li, C., Wang, Q., & Zhao, X. (2021). GPU-based dynamic hyperspace hash with full concurrency. Data Science and Engineering, 6, (pp. 265–279). https://doi.org/10.1007/s41019-021-00161-5
Jünger, D., Teich, J., & Hannig, F. (2020). WarpCore: A library for fast hash tables on GPUs. In Proceedings of the 27th IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC) (pp. 11–20). https://doi.org/10.1109/HiPC50609.2020.00015
Wu, H., Wang, S., Jin, Z., Zhang, Y., Ma, R., Fan, S., & Chao, R. (2023). CostCounter: A better method for collision mitigation in cuckoo hashing. ACM Transactions on Storage, 19(3), Article 28, p. 24. https://doi.org/10.1145/3596910
Bender, M. A., Farach-Colton, M., Kuszmaul, J., Kuszmaul, W., & Liu, M. (2022). On the optimal time/space tradeoff for hash tables. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1284–1297). ACM. https://doi.org/10.1145/3519935.3519969
Tapia-Fernández, S., García-García, D., & García-Hernandez, P. (2022). Key concepts, weaknesses and benchmark on hash table data structures. Algorithms, 15(3), 100. https://doi.org/10.3390/a15030100
Hu, J., Chen, J., Zhu, Y., Yang, Q., Peng, Z., & Yu, Y. (2023). PMEH: A parallel and write-optimized extendible hashing for persistent memory. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(11), (pp. 3801–3814). https://doi.org/10.1109/TCAD.2023.3271579
Zuo, P., & Hua, Y. (2018). A write-friendly and cache-optimized hashing scheme for non-volatile memory systems. IEEE Transactions on Parallel and Distributed Systems, 29(5), (pp. 985–998). https://doi.org/10.1109/TPDS.2017.2782251
Wang, J., Huo, Z., Xiao, L., Yang, J., Huo, J., & Guo, M. (2025). Hierarchical hashing: A dynamic hashing method with low write amplification and high performance for non-volatile memory. IEEE Transactions on Computers, 74(4), (pp. 1138–1151). https://doi.org/10.1109/TC.2024.3517737
Dong, J., Lu, S., Zhang, P., Zheng, F., & Xiao, F. (2023). G-SM3: High-performance implementation of GPU-based SM3 hash function. In Proceedings of the 28th IEEE International Conference on Parallel and Distributed Systems (ICPADS) (pp. 201–208). https://doi.org/10.1109/ICPADS56603.2022.00034
Kostiuk, Y., Dovzhenko, N., Mazur, N., Skladannyi, P., & Rzaeva, S. (2025). The methodology for protecting grid environments from malicious code during the execution of computational tasks. Cybersecurity: Education, Science, Technique, 3(27), (pp. 22–40). https://doi.org/10.28925/2663-4023.2025.27.710
Mancini, T., Melatti, I., & Tronci, E. (2023). Optimizing highly-parallel simulation-based verification of cyber-physical systems. IEEE Transactions on Software Engineering, 49(9), (pp. 4443–4455). https://doi.org/10.1109/TSE.2023.3298432
Kostiuk, Y., Skladannyi, P., Sokolov, V., Hulak, H., & Korshun, N. (2025). Models and algorithms for analyzing information risks during the security audit of personal data information system. In Proceedings of the Third International Conference on Cyber Hygiene & Conflict Management in Global Information Networks (CH&CMiGIN’24) (Vol. 3925, pp. 155–171).
Khorasani, F., Belviranli, M. E., Gupta, R., & Bhuyan, L. N. (2015). Stadium hashing: Scalable and flexible hashing on GPUs. In 2015 International Conference on Parallel Architecture and Compilation (PACT) (pp. 63–74). https://doi.org/10.1109/PACT.2015.13
Kostiuk, Y., Skladannyi, P., Korshun, N., Bebeshko, B., & Khorolska, K. (2024). Integrated protection strategies and adaptive resource distribution for secure video streaming over a Bluetooth network. Information Technology, 4(6), 14–33.
Cheng, L., Kotoulas, S., Ward, T. E., & Theodoropoulos, G. (2014). Design and evaluation of parallel hashing over large-scale data. In 2014 21st International Conference on High Performance Computing (HiPC) (pp. 1–10). https://doi.org/10.1109/HiPC.2014.7116909
Kostiuk, Y., Skladannyi, P., Samoilenko, Y., Khorolska, K., Bebeshko, B., & Sokolov, V. (2025). A system for assessing the interdependencies of information system agents in information security risk management using cognitive maps. In Proceedings of the Third International Conference on Cyber Hygiene & Conflict Management in Global Information Networks (CH&CMiGIN’24) (Vol. 3925, pp. 249–264).
Ashkiani, S., Farach-Colton, M., & Owens, J. D. (2018). A dynamic hash table for the GPU. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 419–429). https://doi.org/10.1109/IPDPS.2018.00052
Kostiuk, Y., Skladannyi, P., Samoilenko, Y., Khorolska, K., Bebeshko, B., & Sokolov, V. (2025). A system for assessing the interdependencies of information system agents in information security risk management using cognitive maps. In Cyber Hygiene & Conflict Management in Global Information Networks (Vol. 3925, pp. 249–264).
Wang, J., Huo, Z., Xiao, L., Yang, J., Huo, J., & Guo, M. (2025). Hierarchical hashing: A dynamic hashing method with low write amplification and high performance for non-volatile memory. IEEE Transactions on Computers, 74(4), (pp. 1138–1151). https://doi.org/10.1109/TC.2024.3517737
Dong, J., Lu, S., Zhang, P., Zheng, F., & Xiao, F. (2023). G-SM3: High-performance implementation of GPU-based SM3 hash function. In 2022 IEEE 28th International Conference on Parallel and Distributed Systems (ICPADS) (pp. 201–208). https://doi.org/10.1109/ICPADS56603.2022.00034
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Юлія Костюк, Павло Складанний, Світлана Рзаєва, Наталія Мазур
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
