Алгоритм хешування з підвищеною колізійною стійкістю для підтримки консистентності в розподілених базах даних

Автор(и)

  • В. Нікітін КПІ ім. Ігоря Сікорського, Україна
  • Є. Крилов КПІ ім. Ігоря Сікорського, Україна

DOI:

https://doi.org/10.20535/1560-8956.41.2022.271338

Ключові слова:

розподілені бази даних, розподілені системи, хешування, хеш- функції, узгодженість, стійкість до зіткнень, узгодженість даних

Анотація

Об’єктом дослідження є методи забезпечення консистентності у розподілених системах. Розподілені системи дозволяють використовувати будь-які послуги незалежно від геолокації користувача і при цьому зберігати продуктивність на високому рівні. Зі збільшенням обсягів та швидкості обміну інформації у сучасних системах, тим складніше підтримка консистентності між різними вузлами. Це може призводити до зниження продуктивності або некоректної роботи під час використання кінцевими користувачами. Критичність цього залежить від галузі, в якій працює система і наскількі узгодженість даних важлива. Ця робота є продовженням минулої праці, в якій було проведено порівняння минулої версії алгоритму з існуючими. Одним з основних недоліків була нестала довжина результуючого хеш-значення. В цій роботі описано наступну версію з кодовою назвою PH2. Детально описано сам алгоритм хешування та його математичний опис. Окрім цього, наведено приклади хешування з різними розмірами
блоків та можливі випадки колізій. Наведено результати експериментів оцінки колізійної стійкості та продуктивності, порівняно з існуючими SHA алгоритмами. На даний момент, є декілька варіантів використання розробленого алгоритму. Першим з них може бути використання у вже існуючій технології підтримки узгодженості, яка називається Active Anti Entropy. Дана технологія використовує дерево Меркла для отримання структурованих хеш-значень, які використовуються для пошуку змінених фрагментів даних. Можно було б використовувати алгоритм PH2 для хешування самих даних та отримання хеш-значень найнижчого рівня, а для побудови кореневого хеш-значення - використовувати вже існуючі алгоритми. Другим способом використання PH2 може бути створення повністю окремої технології, яка б використовувалась сугубо для узгодженості критично важливих даних.

Бібл. 5, іл. 10, табл. 2.

Посилання

Combined indexing method in nosql databases / V. Nikitin та ін. // Adaptive Systems of Automatic Control Interdepartmental scientific and technical collection. 2021. №38 (1). C.3-9 URL: https://doi.org/10.20535/1560-8956.38.2021.232948;

Gilbert S., A. Lynch N. Perspectives on the CAP Theorem // Computer. 2012. № 45 (2). P.1-10 URL: https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf

RRG: redundancy reduced gossip protocol for real-time N-to-N dynamic group communication / V. Wing-Hei Luk та ін. // Journal of Internet Services and Applications. 2013. № 4 (14). C.1-19 URL: https://rdcu.be/cZ1Fk

Comparison of hashing methods for supporting of consistency in distributed databases / V. Nikitin та ін. // Adaptive Systems of Automatic Control Interdepartmental scientific and technical collection. 2022. No 1 (40). P.48-53 URL: http://asac.kpi.ua/article/view/261646/258069;

Modification of hashing algorithm to increase rate of operations in NoSQL databases / V. Nikitin та ін. // Adaptive Systems of Automatic Control Interdepartmental scientific and technical collection. 2021. No 2 (39). P.39-43 URL: http://asac.kpi.ua/article/download/247395/244688;

##submission.downloads##

Опубліковано

2022-12-01