ПАРАЛЕЛЬНА ОБРОБКА ДАНИХ У РОЗШИРЮВАНИХ ХЕШ-СТРУКТУРАХ ТА ОЦІНКА ЇХ ПРОДУКТИВНОСТІ
DOI:
https://doi.org/10.28925/2663-4023.2025.31.1015Ключові слова:
розширюване хешування, паралельна обробка даних, динамічна директорія, конкурентний доступ, верифікаційний механізм, симуляційне моделювання, блокування транзакцій, оперативні бази даних, високопродуктивні бази даних, масштабованістьАнотація
У статті новий алгоритм конкурентного доступу до розширюваного хешування з обережним очікуванням (Extendible Hashing with Cautious Waiting, EHCW), який поєднує механізми двофазного блокування та оптимістичної верифікації для зниження накладних витрат при високому навантаженні. Запропонований підхід дозволяє забезпечити збереження узгодженості даних при паралельному доступі до динамічних хеш-структур без потреби у повному блокуванні, що вирішує проблему ефективного синхронізованого доступу при високому паралелізмі. Алгоритм забезпечує адаптивну реконфігурацію структури директорії, що підвищує масштабованість та продуктивність у умовах змінного навантаження. Для оцінки ефективності реалізовано імітаційну модель функціонування системи в середовищі з обмеженими обчислювальними ресурсами (одноядерний процесор і диск) та використанням буферного пулу сторінок пам’яті для моделювання операцій розщеплення сторінок і динамічної перебудови директорії. Розроблена симуляційна модель показала, що запропонований алгоритм перевищує традиційні статичні схеми хешування за метриками пропускної здатності та частоти блокувань, що робить його перспективним для використання в оперативних базах даних, хмарних обчислювальних середовищах та розподілених інформаційних системах, де критично важливо забезпечити високу продуктивність і збереження цілісності даних при високих рівнях транзакційного навантаження. Задача високопродуктивної обробки даних з динамічними хеш-структурами є важливою для масштабованих систем, зокрема для баз даних і хмарних обчислень, де забезпечення швидкого паралельного доступу до даних.
Завантаження
Посилання
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
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Юлія Костюк, Павло Складанний, Світлана Рзаєва, Наталія Мазур
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
